ctf——Crypto¶

CTF（Capture The Flag）是信息安全领域中一种极具挑战性和趣味性的竞赛形式，参赛者通过破解各种加密、解密、编程和逆向工程等任务来获得“旗帜”（Flag）。在CTF竞赛中，密码学方向的任务主要涉及各种加密算法、解密技巧和密码破解的应用。具体来说，CTF密码学方向的任务通常包括经典密码破解（如凯撒密码、维吉尼亚密码等）、现代加密算法的攻击、密钥恢复、哈希碰撞以及密码协议的漏洞分析等。

需要运用对密码学知识的理解和实际操作技能，解决与加密算法、密文分析、数据泄露、漏洞利用等相关的问题。这考验了选手对密码学理论的掌握，还要求具备一定的编程能力、逆向思维以及创新性的解决问题的能力。CTF密码学方向的任务既可以是理论性的，如对传统密码学算法的分析，也可以是实践性的，如模拟现代加密算法的攻击。

Crypto方向题目类型：¶

1. 经典加密算法破解¶

对称加密（如AES、DES）：这些题目通常会给出加密文本和一些已知信息（比如密钥、明文等），考察选手如何通过分析和算法攻击破解加密数据。
非对称加密（如RSA、ECC）：RSA是CTF比赛中最常见的加密方式之一，题目可能包括公钥加密、私钥泄漏、密钥恢复、数字签名等，一般需要利用数学知识（如素因数分解、扩展欧几里得算法）破解这些加密。
哈希函数（如MD5、SHA）：这些题目一般会给出某个哈希值，要求选手找出原始数据，或是利用碰撞攻击、字典攻击等方法破解哈希值。

2. 编码和加密算法的组合¶

很多Crypto题目涉及到某种加密算法与编码方式（如Base64、Hex、URL编码等）结合，需要首先解码，再进行加密破解或逆向解密。

3. 流密码与分组密码¶

流密码（如RC4）：流密码生成的加密文本可能与某种特定的结构有关，需要通过分析密文流来恢复密钥。
分组密码（如DES、AES）：这类题目中，密文可能采用了某种模式（如ECB、CBC），破解时需要注意模式的特性，并利用它们的弱点进行攻击。

4. 密码学漏洞利用¶

这些题目通常会涉及到加密算法的漏洞或设计缺陷，选手需要找到漏洞并利用它进行破解。常见的漏洞包括时间攻击、侧信道攻击、重放攻击、密钥恢复等。
例如，某些加密算法可能使用不安全的随机数生成器，或者密钥长度不够，攻击者可以利用这些弱点进行攻击。

5. 数学问题¶

密码学问题往往需要一定的数学基础，特别是数论、代数、概率论等。常见的数学题目包括素数分解、离散对数问题、欧几里得算法等。
例如，RSA加密的安全性基于大数分解的困难性，所以如果你能利用某些优化算法对大数分解进行攻击，就能破解RSA。

6.古典密码¶

古典密码（Classical Cryptography）是指在现代计算机技术普及之前使用的加密技术，通常是通过简单的数学或逻辑方法来对信息进行加密和解密。常见的有凯撒密码、单表替换密码、栅栏密码、维吉尼亚密码、摩尔斯密码等等。

古典密码¶

1.凯撒密码¶

凯撒密码是最早的代换密码，使用单表代换。其基本思想是：通过把字母移动一定的位数来实现加密和解密。明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。例如，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推X将变成A，Y变成B，Z变成C。位数就是凯撒密码加密和解密的密钥。

例子如下：

2.维吉尼亚密码¶

在凯撒密码中，字母表中的每一字母都会作一定的偏移。
例如当偏移量为3时，A就转换为了D、B转换为了E……因为凯撒密码中所有字母的偏移量是一样的，因此容易受到字母频率攻击分析，攻击者可以根据密文中出现字母的频率来猜测是由明文中那个字母经过偏移得到的。

【维吉尼亚密码】则是由一些偏移量不同的恺撒密码组成。

为了生成密码，需要使用表格法。

这一表格包括了26行字母表，每一行都由前一行向左偏移一位得到。具体使用哪一行字母表进行编译是基于密钥进行的，在过程中会不断地变换。

下图是用来加解密的维吉尼亚表格：

例如，假设明文为：HEETIAN

然后选择某一关键词并重复而得到密钥，如关键词为LAB时，密钥为：LABLABL

对于明文的第一个字母H，对应密钥的第一个字母L，于是使用表格中L行字母表进行加密，得到密文第一个字母S。类似地，明文第二个字母为E，在表格中使用对应的A行进行加密，得到密文第二个字母E。以此类推，可以得到：

明文：HEETIAN

密钥：LABLABL

密文：SEFEIBY

解密的过程则与加密相反。

例如：根据密钥第一个字母L所对应的L行字母表，发现密文第一个字母S位于H列，因而明文第一个字母为H。

密钥第二个字母A对应A行字母表，而密文第二个字母E位于此行E列，因而明文第二个字母为E。以此类推便可得到明文。

3.栅栏密码¶

栅栏密码属于古典密码中最经典的移项式密码

我们以2栏栅栏密码为例来讲解它的加密和解密过程。

加密过程：明文：THERE_IS_A_CIPHER_

两个一组，得到：(TH) (ER) (E_) (IS) (A) (_C) (IP) (HE) (R)

先每组中取出第一个字母：TEEI__IHR

再从每组中取出第二个字母：HR_SACPE_

连在一起得到密文：TEEI__IHRHR_SACPE_

解密过程：

而解密的时候，我们先把密文从中间分开，变为两行：

TEEI__IHR

HR_SACPE_

再按上下上下的顺序组合起来：

THERE_IS_A_CIPHER_

那么如何将2栏密码扩展到多栏呢？在之前的明文中，CIPHER这个单词之后加了一个下划线，

目的就是为了让明文字符串的长度是2的倍数，

栅栏密码的分栏的一个前提就是分的栏数需是明文长度的因数，这样才会使得分出来的每个栏长度都一样。

对于多栏，我们还是用上面的例子来讲解。

上面的明文字符串（THERE_IS_A_CIPHER_）的长度是18

所以我们可以把它分为2，3，4，6，9栏，这里我们以6栏为例。

以每个元素相隔6个字符分割出栅栏。

    第一栏：TII

    第二栏：HSP

    第三栏：E_H

    第四栏：RAE

    第五栏：E_R

    第六栏：_C_

连接在一起得到密文：TIIHSPE_HRAEE_R_C_

4. 置换密码（Transposition Cipher）¶

置换密码是一种通过重新排列明文字母顺序来加密的密码方法。它不改变字母本身，而是改变它们的位置。

1. 选择明文¶

明文：HELLO WORLD

2. 选择密钥¶

密钥可以是一个数字序列，表示重新排列的顺序。例如，选择密钥：3 1 4 5 2。

3. 按密钥长度分组¶

根据密钥长度（5），将明文分组：

1	`H E L L O W O R L D`

补齐不足的字符（如果最后一组不足 5 个字符），可以用占位符（如 X）填充：

H E L L O
W O R L D
X

4. 重新排列字母¶

按照密钥顺序 3 1 4 5 2，重新排列每组字母：

第一组：H E L L O → L H L O E
第二组：W O R L D → R W L D O
第三组：X → 补齐 X X X X X → X X X X X

5. 生成密文¶

将重新排列后的字母按组拼接：

1	`密文：LHL OER WLD OX XXXXXX`

6.base64编码¶

编码（Encoding）是将信息从一种形式或格式转换为另一种形式的过程。在计算机科学和信息处理中，编码通常用于将数据转换为适合存储、传输或处理的格式。编码可以是简单的字符转换，也可以是复杂的算法处理，具体取决于应用的需求。

Base64编码是一种将二进制数据转换为文本编码的方法，通常用于在文本协议中传输二进制数据，如电子邮件附件或在URL中传递数据。

原理：

准备要编码的二进制数据：将要编码的二进制数据准备好，通常是字节的形式。

分组：将二进制数据分成固定大小的组，每组通常为3字节（24位）。如果最后一组不足3字节，通常需要进行填充，以便每组都有3字节。

将每个组的二进制数据转换为十进制：将每个3字节的二进制数据视为一个8bit*3=24bit位的二进制整数，再转化为一个十进制整数。

Base64编码：将每个十进制整数编码为Base64字符。

Base64字符集通常包括64个字符，通常是大写字母A到Z、小写字母a到z、数字0到9以及两个额外的字符（通常是"+"和"/"）。

以24位整数为例，将它分成4组，每组6位。这4组6位整数将被编码为4个Base64字符。

每个6位整数对应一个Base64字符，根据其在Base64字符集中的位置来选择。

如果原始数据不足3字节，会添加一个或两个额外的0位，以确保每个6位整数都有6位。

Base64编码的结果是一个文本字符串，其中包含一系列Base64字符，每4个字符分为一组，每组表示一个24位整数。

填充（可选）：如果原始数据的长度不是3的倍数，可以使用一个或两个填充字符“=”来补全Base64编码，以确保编码长度是4的倍数。

最终，Base64编码的结果就是表示输入二进制数据的文本字符串。在解码时，可以根据相同的算法将Base64编码的文本字符串还原为原始的二进制数据。

Base64编码是一种常见的数据表示方式，用于在各种情境中传输和存储二进制数据，因为它可以将二进制数据转换为纯文本，并且广泛支持各种编程语言和应用程序。

编码示例：base64编码 Man

编码示例：Base64的末尾补足

base64索引表：

|:-------:|:-----------:|:-------:|:-----------:|:-------:|:-----------:|:-------:|:-----------:|

| 0 | A | 16 | Q | 32 | g | 48 | w |

| 1 | B | 17 | R | 33 | h | 49 | x |

| 2 | C | 18 | S | 34 | i | 50 | y |

| 3 | D | 19 | T | 35 | j | 51 | z |

| 4 | E | 20 | U | 36 | k | 52 | 0 |

| 5 | F | 21 | V | 37 | l | 53 | 1 |

| 6 | G | 22 | W | 38 | m | 54 | 2 |

| 7 | H | 23 | X | 39 | n | 55 | 3 |

| 8 | I | 24 | Y | 40 | o | 56 | 4 |

| 9 | J | 25 | Z | 41 | p | 57 | 5 |

| 10 | K | 26 | a | 42 | q | 58 | 6 |

| 11 | L | 27 | b | 43 | r | 59 | 7 |

| 12 | M | 28 | c | 44 | s | 60 | 8 |

| 13 | N | 29 | d | 45 | t | 61 | 9 |

| 14 | O | 30 | e | 46 | u | 62 | + |

| 15 | P | 31 | f | 47 | v | 63 | / |

古典密码的类型还有很多，例如阿特巴什密码（Atbash Cipher）希尔密码（Hill Cipher）普莱费尔密码（Playfair Cipher）培根密码（Bacon's Cipher）等，课后同学们可以自行进行了解。

数论基础¶

1.整除¶

定义¶

设和是两个整数，且。如果存在一个整数，使得，则称整除，记作。

例子¶

整除的性质¶

自反性：对于任何整数，都有。
传递性：如果且，那么。
线性组合：如果且，那么对于任何整数和，都有。
倍数性质：如果，那么对于任何整数，都有。
因数性质：如果且，那么。
唯一性：如果且，那么。

2.同余¶

定义¶

设和是两个整数，是一个正整数。如果和除以的余数相同，即，那么我们称和模同余，记作。

例子¶

同余的性质¶

自反性：对于任何整数和正整数，都有。
对称性：如果，那么。
传递性：如果且，那么。
线性组合：如果且，那么对于任何整数和，都有
乘法性质：如果，那么对于任何整数，都有。
除法性质：如果且是和的公因数，

3.逆元¶

定义¶

在数论中，逆元通常指的是模的逆元。设是一个整数，是一个正整数，如果存在一个整数，使得，那么我们称是模的逆元，记作

此外，逆元的范围属于1 ~（m-1）

例子¶

求 3模 7 的逆元：
- 我们需要找到一个整数，使得。
- 。
- 因此，3 模 7的逆元是 5
求 2 模 9 的逆元：
- 我们需要找到一个整数，使得。
- 因此，2 模 9的逆元是 5。

逆元的性质¶

唯一性：如果 a 模 m的逆元存在，那么它是唯一的。
存在性：a模 m 的逆元存在当且仅当 a和 m互质，即。
逆元的逆元：如果 b是 a模 m的逆元，那么 a是 b模 m的逆元。

4.欧拉函数¶

定义¶

在数论中，欧拉函数表示小于或等于的正整数中与互质的数的个数。

性质¶

积性函数：如果和互质，即那么
：显然，1 与任何数互质。
质数的欧拉函数：对于质数
质数幂的欧拉函数：对于质数的幂
一般计算公式：如果，其中是质数，为正整数，那么

例子¶

计算 ϕ(10)：
- 小于或等于 10 的正整数中与 10 互质的数有：1, 3, 7, 9。
- ϕ(10)=4。
计算 ϕ(12)：
- 小于或等于 12 的正整数中与 12 互质的数有：1, 5, 7, 11。
- ϕ(12)=4

5.欧拉定理¶

定义¶

欧拉定理（Euler's Theorem）是数论中的一个重要定理，它描述了模运算中的一些性质。具体来说，对于任意整数和正整数，如果和互质（即），那么有：其中是欧拉函数，表示小于或等于n的正整数中与 n互质的数的个数。

例子¶

计算的最后两位数：
- 首先，我们需要计算。因为，所以：
- 由于，根据欧拉定理，我们有：
- 因此：
- 最后两位数是 27。

6.费马小定理¶

费马小定理（Fermat's Little Theorem）是数论中的一个基本定理。具体来说，如果是一个质数，且是一个不被整除的整数（即，那么有：

例子¶

计算：

- <font style="color:rgb(6, 6, 7);">根据费马小定理，因为 11 是质数且</font>![image](https://cdn.nlark.com/yuque/__latex/4a501d4a187b9106d7b2a51ee86a3278.svg)<font style="color:rgb(6, 6, 7);">，所以</font>![image](https://cdn.nlark.com/yuque/__latex/c2985d125279ff516a2d5b0e1bbab998.svg)