对称密码学

对称密钥密码是使用相同密钥对数据进行加密和解密的算法。目标是使用短密钥安全有效地发送长消息。
最著名的对称密钥密码是2001年标准化的AES。它如此广泛，以至于现代处理器甚至包含执行AES操作的特殊指令集。这里的第一部分将指导了解AES的内部工作原理，展示其独立组件如何协同工作，使其成为安全密码。到最后构建自己的AES解密代码。
我们可以将对称密钥密码分为两种类型，块密码和流密码。块密码将明文分解为固定长度的块，并通过加密函数将每个块与密钥一起发送。流密码同时通过将伪随机密钥流与数据进行异或运算，一次加密一个字节的明文。AES是一种分组密码，但可以使用CTR等操作模式转换为流密码。
块密码只指定如何加密和解密单个块，并且必须使用一种操作模式将密码应用于较长的消息。这是现实世界中实现经常失败的地方，因为开发人员不理解使用特定模式的微妙含义。剩下的挑战是如何攻击各种模式的常见误用。

Keyed Permutations

AES和所有分组密码一样，执行“密钥置换”。这意味着它将每个可能的输入块映射到唯一的输出块，并使用一个密钥来确定要执行的置换。

“块”只是指固定数量的位或字节，可以表示任何类型的数据。AES处理一个块并输出另一个块。我们将具体讨论AES的变体，它适用于128位（16字节）块和128位密钥，称为AES-128。

使用相同的密钥，可以反向执行排列，将输出块映射回原始输入块。重要的是，输入和输出块之间有一对一的对应关系，否则我们将无法依靠密文将其解密回最初的明文。

问：一对一对应的数学术语是什么？（crypto{术语}）

试了function和reflection都不对，又试了个双射（bijection），这次成功了，想了想确实双射更符合这个意思。

Resisting Bruteforce

如果分组密码是安全的，攻击者应该无法将AES的输出与随机的比特排列区分开来。此外，没有比简单地对每个可能的密钥进行粗暴处理更好的方法来撤销排列。这就是为什么学者们认为密码理论上是“坏的”，如果他们能够找到一种比暴力破解密钥所需的步骤更少的攻击，即使这种攻击实际上是不可行的。

暴力攻击128位密钥空间有多难？有人估计，如果你将整个比特币挖矿网络的力量转向破解AES-128密钥，那么破解密钥的时间将是宇宙年龄的一百倍。

事实证明，有一种对AES的攻击比暴力攻击更好，但只是轻微的。它将AES-128的安全级别降低到126.1位，并且已经8年多没有改进。鉴于128位提供了巨大的“安全余量”，尽管进行了广泛的研究，但仍缺乏改进，因此不认为这对AES的安全性有可信的风险。但是的，在非常狭义的意义上，它“打破”了AES。
最后，虽然量子计算机有可能通过Shor算法彻底破解RSA等流行的公钥密码系统，但据认为，通过Grover算法，量子计算机只会将对称密码系统的安全级别降低一半。这就是为什么人们建议使用AES-256的原因之一，尽管它的性能较差，因为在量子未来，它仍然可以提供非常充分的128位安全性。

问：针对AES的最佳单密钥攻击的名称是什么？（crypto{术语}）

打开“有一种对AES的攻击比暴力攻击更好”对应的超链接，看到这种攻击方式叫Biclique attack。

Structure of AES

为了实现不可能在没有密钥的情况下反转的密钥置换，AES在输入上应用大量点对点混合操作。这与RSA这样的公钥密码系统形成鲜明对比，后者基于优雅的个人数学问题。AES虽然不那么优雅，但速度非常快。
在高级别上，AES-128以“密钥计划表”开始，然后在同一个状态上运行10轮。起始状态只是我们要加密的明文块，表示为4x4字节矩阵。在10个循环的过程中，状态被多次可逆变换。

根据克劳德·香农（Claude Shannon）在20世纪40年代建立的安全密码的理论性质，每个转换步骤都有一个明确的目的。我们将在下面的挑战中详细了解其中的每一项。

以下是AES加密阶段的概述：

1.KeyExpansion：
 从128位密钥导出11个单独的128位“round keys”：每个AddRoundKey步骤中使用一个。
2.Initial key addition（初始密钥添加）：
 AddRoundKey：第一轮密钥的字节与矩阵进行⊕操作。
3.循环。此阶段循环10次，共9个主循环加上一个“最后循环”：
 ①SubBytes-根据查找表（“S-box”），矩阵的每个字节被替换为不同的字节。
 ②ShiftRows-矩阵的最后三行在一列或两列或三列上进行转置。

 ③MixColumns-对矩阵的列进行线性变换，合并每列中的四个字节。这在最后一轮被跳过。
 ④AddRoundKey-当前循环密钥的字节与矩阵进行⊕操作。

其中包含一个bytes2matrix函数，用于将初始明文块转换为状态矩阵。编写一个matrix2bytes函数，将该矩阵转换回字节，并将生成的明文作为flag提交：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def bytes2matrix(text):
    """ Converts a 16-byte array into a 4x4 matrix.  """
    return [list(text[i:i+4]) for i in range(0, len(text), 4)]

def matrix2bytes(matrix):
    """ Converts a 4x4 matrix into a 16-byte array.  """
    ????

matrix = [
    [99, 114, 121, 112],
    [116, 111, 123, 105],
    [110, 109, 97, 116],
    [114, 105, 120, 125],
]

print(matrix2bytes(matrix))

编写函数遍历转化即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def matrix2bytes(matrix):
    flag=''
    for i in matrix:
        for j in i:
            flag+=chr(j)
    return flag

matrix = [
    [99, 114, 121, 112],
    [116, 111, 123, 105],
    [110, 109, 97, 116],
    [114, 105, 120, 125],
]

print(matrix2bytes(matrix))#crypto{inmatrix}

Round Keys

现在我们将跳过KeyExpansion阶段的更精细的细节。重点是它接受了我们的16字节密钥，并从初始密钥中生成了11个4x4矩阵，称为“轮密钥”。这些轮密钥允许AES从我们提供的单个密钥中获得额外的里程。
接下来的初始密钥添加阶段只有一个AddRoundKey步骤。AddRoundKey步骤很简单：它将当前状态与当前轮密钥进行异或运算，比如对矩阵$a_{2,2}$的数值进行异或：

AddRoundKey也作为每一轮的最后一步出现。AddRoundKey使AES成为“键控排列”而不仅仅是排列。这是AES中唯一将密钥混合到状态中的部分，但对于确定发生的排列至关重要。
正如在前面的挑战中所看到的，如果知道密钥，XOR是一个容易反转的操作，但如果不知道，则很难反转。

完成add_round_key函数，然后使用matrix2bytes函数获取下一个flag：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
state = [
    [206, 243, 61, 34],
    [171, 11, 93, 31],
    [16, 200, 91, 108],
    [150, 3, 194, 51],
]

round_key = [
    [173, 129, 68, 82],
    [223, 100, 38, 109],
    [32, 189, 53, 8],
    [253, 48, 187, 78],
]


def add_round_key(s, k):
    ???


print(add_round_key(state, round_key))

根据XOR运算和上一节学到的定义矩阵转字节：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
state = [
    [206, 243, 61, 34],
    [171, 11, 93, 31],
    [16, 200, 91, 108],
    [150, 3, 194, 51],
]

round_key = [
    [173, 129, 68, 82],
    [223, 100, 38, 109],
    [32, 189, 53, 8],
    [253, 48, 187, 78],
]

def matrix2bytes(matrix):#矩阵转字节
    flag=''
    for i in matrix:
        for j in i:
            flag+=chr(j)
    return flag

def add_round_key(s, k):#写一个函数返回异或后的矩阵
    matrix=[]
    for i in range(len(s)):
        res=[]
        for j in range(len(s)):
            res.append(s[i][j]^k[i][j])
        matrix.append(res)
    return matrix

print(matrix2bytes(add_round_key(state, round_key)))
#crypto{r0undk3y}

Confusion through Substitution

每个AES循环的第一步是SubBytes。这涉及获取状态矩阵的每个字节，并将其替换为预设16x16查找表中的不同字节。查找表被称为“Substitution box”或简称“S-box”。

1945年，美国数学家克劳德·香农发表了一篇关于信息论的开创性论文。它认为“混淆”是安全密码的一个基本属性。“混淆”意味着密文和密钥之间的关系应该尽可能复杂。只要给出一个密文，就应该没有办法了解有关密钥的任何信息。
如果密码的混淆性很差，则可以将密文、密钥和明文之间的关系表示为线性函数。例如，在凯撒密码中，密文=明文+密钥。这是一个明显的关系，很容易逆转。更复杂的线性变换可以使用Gaussian elimination等技术来解决。即使是低阶多项式，例如方程$x^4+51x^3+x$，也可以使用代数方法有效地求解。然而，多项式的阶数越高，通常就越难求解——只能用越来越多的线性函数来逼近。
S-box的主要目的是以抵抗线性函数逼近的方式变换输入。S-box的目标是高度非线性，虽然AES的不是完美的，但它非常接近。S盒中的快速查找是对输入字节执行非线性函数的捷径。该函数涉及在Galois域$2^8$中取模逆，然后应用复杂的仿射变换。表达函数的最简单方法是通过以下高次多项式：

为了制作S-box，已经对0x00到0xff的所有输入值和输入到查找表中的输出值计算了函数。实现sub_bytes，通过逆S-box发送状态矩阵，然后将其转换为字节以获得flag：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
s_box = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)

inv_s_box = (
    0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
    0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
    0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
    0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
    0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
    0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
    0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
    0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
    0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
    0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
    0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
    0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
    0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
    0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
    0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D,
)

state = [
    [251, 64, 182, 81],
    [146, 168, 33, 80],
    [199, 159, 195, 24],
    [64, 80, 182, 255],
]

#s中元素数值代表替换对应的位置，如251替换后为sbox里的第251个元素
def sub_bytes(state, sbox=s_box):
    list=[]
    for i in state:
        res=[]
        for j in i:
            res.append(sbox[j])
        list.append(res)
    return list

def matrix2bytes(matrix):
    flag=''
    for i in matrix:
        for j in i:
            flag+=chr(j)
    return flag

print(matrix2bytes(sub_bytes(state, sbox=inv_s_box)))#crypto{l1n34rly}

Diffusion through Permutation

我们已经看到了S-box替换是如何产生的。香农描述的另一个关键性质是“扩散”。这涉及到密码输入的每个部分应该如何扩展到输出的每个部分。
替代本身会产生非线性，但它不会将其分布到整个矩阵。如果没有扩散，在同一位置的同一字节将得到每一轮应用于它的相同变换。这将允许密码分析师分别攻击状态矩阵中的每个字节位置。我们需要通过加扰状态（以可逆的方式）来替换替换，以便应用于一个字节的替换影响状态中的所有其他字节。进入下一个S盒的每一个输入都会变成多个字节的函数，这意味着系统的代数复杂性会随着每一轮的增加而大大增加。

理想的扩散量会导致明文中一个比特的变化，从而导致密文中统计上一半比特的变化。这种理想的结果被称为雪崩效应。

ShiftRows和MixColumns步骤结合起来实现了这一点。它们协同工作，确保每个字节在两个回合内影响状态中的其他每个字节。
ShiftRows是AES中最简单的转换。它使状态矩阵的第一行保持不变。第二行向左移动一列，环绕。第三行移动两列，第四行移动三列。维基百科说得好：“这一步的重要性在于避免列被独立加密，在这种情况下，AES会退化为四个独立的分组密码。”

MixColumns更复杂。它在Rijndael的Galois域中执行状态矩阵列和预设矩阵列之间的矩阵乘法。因此，每列的每一个字节都会影响结果列的所有字节。

本题提供了执行MixColumns和ShiftRows操作的代码。在实现inv_shift_rows之后，获取矩阵，在其上运行inv_mix_columns，然后inv_shift-rows，转换为字节，获得flag。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]
    return s

#根据shift_rows(s)函数的转换法则逆回去即可
def inv_shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[1][3], s[2][3], s[3][3], s[0][3]
    return s

# learned from http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)


def mix_single_column(a):
    # see Sec 4.1.2 in The Design of Rijndael
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)


def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])


def inv_mix_columns(s):
    # see Sec 4.1.3 in The Design of Rijndael
    for i in range(4):
        u = xtime(xtime(s[i][0] ^ s[i][2]))
        v = xtime(xtime(s[i][1] ^ s[i][3]))
        s[i][0] ^= u
        s[i][1] ^= v
        s[i][2] ^= u
        s[i][3] ^= v
    mix_columns(s)
    return s

def matrix2bytes(matrix):#别忘了矩阵转换字节
    flag=''
    for i in matrix:
        for j in i:
            flag+=chr(j)
    return flag

state = [
    [108, 106, 71, 86],
    [96, 62, 38, 72],
    [42, 184, 92, 209],
    [94, 79, 8, 54],
]

print(matrix2bytes(inv_shift_rows(inv_mix_columns(state))))
#crypto{d1ffUs3R}

Bringing It All Together

除了KeyExpansion阶段之外，我们还概述了AES的所有组件。我们已经展示了SubBytes如何提供混淆，ShiftRows和MixColumns如何提供扩散，以及这两个属性如何协同工作，在状态上重复循环非线性转换。最后，AddRoundKey将密钥播种到这个替换置换网络中。

解密涉及反向执行“AES结构”挑战中描述的步骤，应用反向操作。请注意，KeyExpansion仍然需要首先运行，而轮密钥将以相反的顺序使用。AddRoundKey及其逆函数与XOR具有自逆特性相同。
这里提供了密钥扩展码，以及由AES-128正确加密的密文。复制到目前为止已编码的所有构建块，并完成实现图中所示步骤的解密函数。解密的明文是flag：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
N_ROUNDS = 10#十轮循环

#部分所用参量
key        = b'\xc3,\\\xa6\xb5\x80^\x0c\xdb\x8d\xa5z*\xb6\xfe\\'
ciphertext = b'\xd1O\x14j\xa4+O\xb6\xa1\xc4\x08B)\x8f\x12\xdd'
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)
s_box = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)
inv_s_box = (
    0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
    0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
    0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
    0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
    0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
    0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
    0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
    0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
    0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
    0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
    0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
    0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
    0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
    0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
    0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D,
)

#字节转矩阵;矩阵转字节
def bytes2matrix(text):
    """ Converts a 16-byte array into a 4x4 matrix.  """
    return [list(text[i:i+4]) for i in range(0, len(text), 4)]

def matrix2bytes(matrix):
    flag=''
    for i in matrix:
        for j in i:
            flag+=chr(j)
    return flag

#AddRoundKey阶段
def add_round_key(s, k):
    matrix=[]
    for i in range(len(s)):
        res=[]
        for j in range(len(s)):
            res.append(int(s[i][j])^k[i][j])
        matrix.append(res)
    return matrix

#SubBytes阶段
def sub_bytes(state, sbox=s_box):
    flag=[]
    for i in state:
        res=[]
        for j in i:
            res.append(sbox[j])
        flag.append(res)
    return flag

#ShiftRous阶段
def inv_shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[1][3], s[2][3], s[3][3], s[0][3]
    return s

#MixColumns阶段
def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])

def mix_single_column(a):
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)
def inv_mix_columns(s):

    for i in range(4):
        u = xtime(xtime(s[i][0] ^ s[i][2]))
        v = xtime(xtime(s[i][1] ^ s[i][3]))
        s[i][0] ^= u
        s[i][1] ^= v
        s[i][2] ^= u
        s[i][3] ^= v
    mix_columns(s)
    return s

#KeyExpansion阶段
def expand_key(master_key):
    r_con = (
        0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
        0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
        0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
        0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
    )
    key_columns = bytes2matrix(master_key)
    iteration_size = len(master_key) // 4
    i = 1
    while len(key_columns) < (N_ROUNDS + 1) * 4:
        word = list(key_columns[-1])
        if len(key_columns) % iteration_size == 0:
            word.append(word.pop(0))
            word = [s_box[b] for b in word]
            word[0] ^= r_con[i]
            i += 1
        elif len(master_key) == 32 and len(key_columns) % iteration_size == 4:
            word = [s_box[b] for b in word]
        word = bytes(i^j for i, j in zip(word, key_columns[-iteration_size]))
        key_columns.append(word)
    return [key_columns[4*i : 4*(i+1)] for i in range(len(key_columns) // 4)]

def decrypt(key, ciphertext):
    #前置操作
    round_keys = expand_key(key)
    matrix=bytes2matrix(ciphertext)
    #第一轮（加密的最后一轮，没有inv_mix_columns）
    matrix=add_round_key(matrix,round_keys[10])
    matrix=inv_shift_rows(matrix)
    matrix=sub_bytes(matrix, sbox=inv_s_box)  
    #进行接下来完整的九轮
    for i in range(N_ROUNDS-1,0,-1):
        matrix=add_round_key(matrix,round_keys[i])
        matrix=inv_mix_columns(matrix)
        matrix=inv_shift_rows(matrix)
        matrix=sub_bytes(matrix, sbox=inv_s_box)
    #别忘了最开始的add_round_key
    matrix=add_round_key(matrix,round_keys[0])
    #把解密出的矩阵转明文
    plaintext=matrix2bytes(matrix)
    return plaintext

print(decrypt(key, ciphertext))#crypto{MYAES128}

Modes of Operation Starter

前一组挑战展示了AES如何对数据块执行密钥排列。实际上，我们需要对消息进行比单个块更长的加密。操作模式描述了如何在较长的消息上使用AES之类的密码。
如果使用不当，所有模式都有严重的弱点。这一类别的挑战将与API交互并利用这些弱点，来获取flag。

所提供的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Cipher import AES

KEY = ?
FLAG = ?

@chal.route('/block_cipher_starter/decrypt/<ciphertext>/')
def decrypt(ciphertext):
    ciphertext = bytes.fromhex(ciphertext)

    cipher = AES.new(KEY, AES.MODE_ECB)
    try:
        decrypted = cipher.decrypt(ciphertext)
    except ValueError as e:
        return {"error": str(e)}

    return {"plaintext": decrypted.hex()}


@chal.route('/block_cipher_starter/encrypt_flag/')
def encrypt_flag():
    cipher = AES.new(KEY, AES.MODE_ECB)
    encrypted = cipher.encrypt(FLAG.encode())

    return {"ciphertext": encrypted.hex()}

首先使用encrypted_flag()获取程序加密的AES密文：

1
{"ciphertext":"8ca64f9c03ef853d2fb33add832335cf941f5098477acf878da62721e465b5a1"}

然后再用decrypt(ciphertext)获得密文解密出的明文：

1
{"plaintext":"63727970746f7b626c30636b5f633170683372355f3472335f663435375f217d"}

对其进行转字节即可（当然，API中也有辅助转字节的程序）：

1
2
hex='63727970746f7b626c30636b5f633170683372355f3472335f663435375f217d'
print(bytes.fromhex(hex))#b'crypto{bl0ck_c1ph3r5_4r3_f457_!}'

此页面为您提供了一种与挑战功能交互的便捷方式。如果需要，还可以使用GET的方式直接从routes/endpoints发送和接收数据。

看到大佬的方法使用python的requests库直接编写程序进行交互，有点厉害，学习一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import requests

BASE_URL = "http://aes.cryptohack.org/block_cipher_starter"

#获取加密标志的密文
r = requests.get(f"{BASE_URL}/encrypt_flag")
data = r.json()
ciphertext = data["ciphertext"]
print("ciphertext", ciphertext)

#将密文发送到解密函数
r = requests.get(f"{BASE_URL}/decrypt/{ciphertext}")
data = r.json()
plaintext = data["plaintext"]
print("plaintext", plaintext)

#将十六进制转换为ASCII得到flag
print("flag", bytearray.fromhex(plaintext).decode）
'''
ciphertext 8ca64f9c03ef853d2fb33add832335cf941f5098477acf878da62721e465b5a1
plaintext 63727970746f7b626c30636b5f633170683372355f3472335f663435375f217d
flag crypto{bl0ck_c1ph3r5_4r3_f457_!}
'''

稍微学习一下requests库：

我们首先知道这道题目的url，作为BASE_URL，等下要对其进行get请求。

题目中已经告诉了我们这题使用get请求的方法：

@chal.route('/block_cipher_starter/decrypt/<ciphertext>/')

@chal.route('/block_cipher_starter/encrypt_flag/')

requests.get(url)可以返回一个response响应对象，以这道题为例：

1
2
3
4
5
6
import requests

url='http://aes.cryptohack.org/block_cipher_starter'

r=requests.get(f'{url}')
print(r.content)#返回网站文本b'<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><me…………

根据题目所给代码形式，我们可以知道其返回值为json格式，我们可以直接获取内容：

1
2
3
4
5
6
7
8
9
10
import requests

BASE_URL = "http://aes.cryptohack.org/block_cipher_starter"

#获取加密标志的密文
r = requests.get(f"{BASE_URL}/encrypt_flag")
data = r.json()#{"ciphertext":"8ca64f9c03ef853d2fb33add832335cf941f5098477acf878da62721e465b5a1"}
ciphertext = data["ciphertext"]
print("ciphertext", ciphertext)
#ciphertext 8ca64f9c03ef853d2fb33add832335cf941f5098477acf878da62721e465b5a1

我们在第六行使用了get请求使用了encrypt_flag模块，并得到了返回值，变量data为获取的字典信息，用变量ciphertext得到所得到的密文。

用相同的方法，我们也可以使用get请求得到解密的文本（注意get请求格式），然后解码就能得到flag。

Passwords as Keys

对称密钥算法中的密钥必须是随机字节，而不是密码或其他可预测数据。应使用加密安全伪随机数生成器（CSPRNG）生成随机字节。如果密钥以任何方式都是可预测的，那么密码的安全级别就会降低，并且攻击者可以访问密文对其进行解密。
仅仅因为密钥看起来像是由随机字节组成的，并不意味着它一定是这样的。在这种情况下，密钥是使用哈希函数从简单的密码中派生出来的，这使得密文可以破解。

提供的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from Crypto.Cipher import AES
import hashlib
import random

# /usr/share/dict/words from
# https://gist.githubusercontent.com/wchargin/8927565/raw/d9783627c731268fb2935a731a618aa8e95cf465/words
with open("/usr/share/dict/words") as f:
    words = [w.strip() for w in f.readlines()]
keyword = random.choice(words)

KEY = hashlib.md5(keyword.encode()).digest()
FLAG = ?

@chal.route('/passwords_as_keys/decrypt/<ciphertext>/<password_hash>/')
def decrypt(ciphertext, password_hash):
    ciphertext = bytes.fromhex(ciphertext)
    key = bytes.fromhex(password_hash)
    cipher = AES.new(key, AES.MODE_ECB)
    try:
        decrypted = cipher.decrypt(ciphertext)
    except ValueError as e:
        return {"error": str(e)}

    return {"plaintext": decrypted.hex()}

@chal.route('/passwords_as_keys/encrypt_flag/')
def encrypt_flag():
    cipher = AES.new(KEY, AES.MODE_ECB)
    encrypted = cipher.encrypt(FLAG.encode())

    return {"ciphertext": encrypted.hex()}

在代码提供的网站链接里有随机密钥的词库，全部复制下来到文本里，我们可以遍历逐个进行AES解密，以含有flag头作为目标。

现学了一下AES库的使用，要求解密的密钥和密文都为字节形式即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Cipher import AES
import hashlib

text="c92b7734070205bdf6c0087a751466ec13ae15e6f1bcdd3f3a535ec0f4bbae66"

with open("words.txt","r") as f:
    for words in f:
        words=words.strip()
        key_1 = hashlib.md5(words.encode()).hexdigest()
        key=bytes.fromhex(key_1)
        cipher = AES.new(key, AES.MODE_ECB)
        ciphertext = bytes.fromhex(text)
        flag = cipher.decrypt(ciphertext)
        if b'crypto{' in flag:
            print(flag)#b'crypto{k3y5__r__n07__p455w0rdz?}'
            break

ECB Oracle

AES_ECB是最简单的模式，每个明文块完全独立加密。在这种情况下，输入被添加到secret flag并被加密。我们不提供解密功能。

提供代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

KEY = ?
FLAG = ?

@chal.route('/ecb_oracle/encrypt/<plaintext>/')
def encrypt(plaintext):
    plaintext = bytes.fromhex(plaintext)

    padded = pad(plaintext + FLAG.encode(), 16)
    cipher = AES.new(KEY, AES.MODE_ECB)
    try:
        encrypted = cipher.encrypt(padded)
    except ValueError as e:
        return {"error": str(e)}

    return {"ciphertext": encrypted.hex()}

被这题卡了很久……

了解一下ECB加密的方式：

先观察一下代码，ECB模式将自己输入的和plaintext和flag组合起来，变成”\crypto{xxxxxx}”的这种形式进行加密，

由于ECB的分块加密特点，代码中分组为16一组，所以我们输入相同长度的不同明文，得到的后半段密文是不受影响的，因为它和前面我们输入的部分不是同一个加密块。所以我们可以布设一个“陷阱”，来骗到flag。

想想如果我们分别输入以下内容：

1
2
AAAAAAAAAAAAAAAA crypto{…………
AAAAAAAAAAAAAAAc rypto{…………

这题里面flag头由于我们是知道的，先假设我们先不知道flag头第一位为c，我们先输入16个填充字符A，那么这16个A分在第一块，flag在后面的块；但是我们如果只输入了15个A作为填充字符，那么就会把第二块的首位提到第一个块里进行加密，这样我们就获得了来自flag的首字母和我们的填充字符组合的密文。

我们可以遍历数字字母和一些符号字符，组合成这样的填充块：

1
'AAAAAAAAAAAAAAA' + i

将这个填充块发送，获得密文，与之前获得的含有flag首字母的密文进行比较，如果相等，不就代表了我们遍历到了flag的首字母吗。

进而减少一个填充字母A，末尾加上c，然后根据一开始的逻辑开始寻找第二个字母：

1
2
AAAAAAAAAAAAAAAc crypto{…………
AAAAAAAAAAAAAAcr ypto{…………

这样我们又获得了含有第二个字母r的密文，接着遍历，比较返回值又可以得到第二个字母，一遍一遍循环，最终就能复原flag。

注意我们一开始并不知道flag的具体长度，简单思考一下，由于填充字符需要大于flag的长度我们才能得到完整的flag，所以我们可以估计一下flag长度，设置一个合理的填充字符初始值。

以上的理论都已具备，实践开始：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import requests
import string
import binascii,json
import time

url='http://aes.cryptohack.org/ecb_oracle/encrypt/'

flag=''
filler='A'*32#填充字符
mark=string.ascii_lowercase+string.digits+'{'+'_'+'}'+'!'+string.ascii_uppercase
while 1:
    #发送捕获目标ECB值
    res=requests.get(url+(binascii.hexlify(filler[:-1].encode())).decode())
    target=json.loads(res.text)["ciphertext"][:64]
    print('target:',target)
    for i in mark:
        #遍历比较ECB值
        r = requests.get(url+(binascii.hexlify((filler[:-1]+flag+i).encode())).decode())
        print(' ',i,'  :',json.loads(r.text)["ciphertext"][:64])
        if json.loads(r.text)["ciphertext"][:64]==target:
            flag+=i
            print(' find :',flag)
            break
        time.sleep(1)
    if flag[-1]=='}':
        print(' flag :',flag)
        break
    filler=filler[:-1]

注意这里需要设置一个缓冲时间，避免因为过于频繁发送get请求出错，总共跑下来需要一段时间，等就行了。

ECB CBC WTF

在这里，您可以在CBC中加密，但只能在ECB中解密。这不应该是缺点，因为它们是不同的模式。

题目所给代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Cipher import AES

KEY = ?
FLAG = ?

@chal.route('/ecbcbcwtf/decrypt/<ciphertext>/')
def decrypt(ciphertext):
    ciphertext = bytes.fromhex(ciphertext)
    cipher = AES.new(KEY, AES.MODE_ECB)
    try:
        decrypted = cipher.decrypt(ciphertext)
    except ValueError as e:
        return {"error": str(e)}
    return {"plaintext": decrypted.hex()}

@chal.route('/ecbcbcwtf/encrypt_flag/')
def encrypt_flag():
    iv = os.urandom(16)
    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    encrypted = cipher.encrypt(FLAG.encode())
    ciphertext = iv.hex() + encrypted.hex()
    return {"ciphertext": ciphertext}

这里我们需要了解一下CBC加密的加密流程，比较一下ECB模式：

我们先获得密文：

1
{"ciphertext":"c8c4aecc754d37c54d3e1c263db6bf79f87422fca703f4bb72ae314a7ced8e2fa5d8a53eeb2e575a7b8e3ed790f2c306"}

然后再得到相应的明文：

1
{"plaintext":"e0cb2f6b2c06ebff12dfa02a837798eaabb6d7bc01224cf62e5c431348d5d44ca74054cc9667ab8a45f1106b5dccaf52"}

密文和明文都是96位16进制，也就是48字节，由于iv为16位，所以块密码分组16一组，我们可以分成三组，这里注意到：ciphertext = iv.hex() + encrypted.hex()，这里我们得到的“密文”是由第一组iv和后面两组密文得到。

我们可以发现，CBC模式除了进行了一个额外的异或环节之外和ECB没有什么区别，我们使用解密函数得到的明文是在没有异或的基础上得到的，所以我们需要进行一步异或。根据上面的算法，我们有：

把这两个式子逆回去就能得到明文：

得到flag：

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *

cipherlist=['c8c4aecc754d37c54d3e1c263db6bf79',#iv
'f87422fca703f4bb72ae314a7ced8e2f',#cipher1
'a5d8a53eeb2e575a7b8e3ed790f2c306']#cipher2

plainlist=['e0cb2f6b2c06ebff12dfa02a837798ea',#useless
'abb6d7bc01224cf62e5c431348d5d44c',#plain1
'a74054cc9667ab8a45f1106b5dccaf52']#plain2

print(long_to_bytes(int(cipherlist[0],16)^int(plainlist[1],16))+long_to_bytes(int(cipherlist[1],16)^int(plainlist[2],16)))

LAZY CBC

我只是一个懒惰的开发人员，希望我的CBC加密能够工作。这些关于初始化向量的讨论是什么？听起来不重要。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from Crypto.Cipher import AES

KEY = ?
FLAG = ?

@chal.route('/lazy_cbc/encrypt/<plaintext>/')
def encrypt(plaintext):
    plaintext = bytes.fromhex(plaintext)
    if len(plaintext) % 16 != 0:
        return {"error": "Data length must be multiple of 16"}

    cipher = AES.new(KEY, AES.MODE_CBC, KEY)
    encrypted = cipher.encrypt(plaintext)

    return {"ciphertext": encrypted.hex()}


@chal.route('/lazy_cbc/get_flag/<key>/')
def get_flag(key):
    key = bytes.fromhex(key)

    if key == KEY:
        return {"plaintext": FLAG.encode().hex()}
    else:
        return {"error": "invalid key"}


@chal.route('/lazy_cbc/receive/<ciphertext>/')
def receive(ciphertext):
    ciphertext = bytes.fromhex(ciphertext)
    if len(ciphertext) % 16 != 0:
        return {"error": "Data length must be multiple of 16"}

    cipher = AES.new(KEY, AES.MODE_CBC, KEY)
    decrypted = cipher.decrypt(ciphertext)

    try:
        decrypted.decode() # ensure plaintext is valid ascii
    except UnicodeDecodeError:
        return {"error": "Invalid plaintext: " + decrypted.hex()}

    return {"success": "Your message has been received"}

这题我们需要得到key，系统会返回flag，明文和密文都是我们自己设置的。z

你可以为我的网站获取cookie，但它不会帮助你阅读flag……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from Crypto.Cipher import AES
import os
from Crypto.Util.Padding import pad, unpad
from datetime import datetime, timedelta

KEY = ?
FLAG = ?

@chal.route('/flipping_cookie/check_admin/<cookie>/<iv>/')
def check_admin(cookie, iv):
    cookie = bytes.fromhex(cookie)
    iv = bytes.fromhex(iv)
    try:
        cipher = AES.new(KEY, AES.MODE_CBC, iv)
        decrypted = cipher.decrypt(cookie)
        unpadded = unpad(decrypted, 16)
    except ValueError as e:
        return {"error": str(e)}
    if b"admin=True" in unpadded.split(b";"):
        return {"flag": FLAG}
    else:
        return {"error": "Only admin can read the flag"}

@chal.route('/flipping_cookie/get_cookie/')
def get_cookie():
    expires_at = (datetime.today() + timedelta(days=1)).strftime("%s")
    cookie = f"admin=False;expiry={expires_at}".encode()
    iv = os.urandom(16)
    padded = pad(cookie, 16)
    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    encrypted = cipher.encrypt(padded)
    ciphertext = iv.hex() + encrypted.hex()
    return {"cookie": ciphertext}

这道题目中get_cookie函数返回包含“admin=False”的纯文本密文，密文的前16个字节是iv。在check_admin函数中，输入文本通过iv进行解密，如果解密文本包含字符串“admin=True”，则即可得到flag。

我们要做的就是改一下生成的cookie中的admin，使其为True返回flag。

但是如果我们只改变密文，iv不变，用这个程序的key是复原不出带有“admin=True”的明文的。

由于True和False由于一个字母之差，会改变块加密的块结构，我在测试中的时候返回了以下内容：

1
{"error":"Padding is incorrect."}

所以，综合看起来，我们不能改变密文，那么我们可以生成一个新的iv，使其和密文异或能异或出含有True的明文：$plain\Rightarrow^{E_{iv}}cipher\Rightarrow^{D{iv’}}fake$

从这个理论关系分析，我们能知道：$fake=D(cipher)\oplus iv’$

那么这个新iv该如何得到？不难发现其构成都为我们已知的量：

那么问题就简单多了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
import requests

url='https://aes.cryptohack.org/flipping_cookie/'

r=requests.get(url+'get_cookie/')
data=r.json()['cookie']
iv=data[:32]
plain1=b'admin=False;expi'#块加密，我们只用第一块做异或即可
fake=b'admin=True;expir'#注意块长度相等
cipher1=data[32:64]
fakeiv=bytes_to_long(plain1)^bytes_to_long(fake)^int(iv,16)

rr=requests.get(url+'check_admin/'+data[32:]+'/'+hex(fakeiv)[2:])
print(rr.json()['flag'])

Symmetry

一些分组密码模式，如OFB、CTR或CFB，将分组密码转换为流密码。流密码背后的思想是产生一个伪随机密钥流，然后将其与明文进行异或运算。流密码的一个优点是它们可以处理任意长度的明文，而不需要填充。
OFB是一种晦涩难懂的密码模式，目前与使用CTR相比没有任何实际好处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Cipher import AES

KEY = ?
FLAG = ?

@chal.route('/symmetry/encrypt/<plaintext>/<iv>/')
def encrypt(plaintext, iv):
    plaintext = bytes.fromhex(plaintext)
    iv = bytes.fromhex(iv)
    if len(iv) != 16:
        return {"error": "IV length must be 16"}
    cipher = AES.new(KEY, AES.MODE_OFB, iv)
    encrypted = cipher.encrypt(plaintext)
    ciphertext = encrypted.hex()
    return {"ciphertext": ciphertext}

@chal.route('/symmetry/encrypt_flag/')
def encrypt_flag():
    iv = os.urandom(16)
    cipher = AES.new(KEY, AES.MODE_OFB, iv)
    encrypted = cipher.encrypt(FLAG.encode())
    ciphertext = iv.hex() + encrypted.hex()
    return {"ciphertext": ciphertext}

注意到OFB模式中对iv进行反复加密，每段不同的iv参与每块的异或运算，根据异或的运算性质，明文生成的密文也可以看做明文，再进行一次相同iv的异或运算又能得到密文（最初的明文）：

题目生成iv和flag用OFB加密后的密文，所以利用这里的iv和密文我们可以用encrypt函数进行加密得到flag：

1
2
3
4
5
6
7
8
import requests

url='https://aes.cryptohack.org/symmetry/'

r=requests.get(url+'encrypt_flag/')
data=r.json()['ciphertext']
rr=requests.get(url+'encrypt/'+data[32:]+'/'+data[:32])
print(bytes.fromhex(rr.json()['ciphertext']))

Bean Counter

我一直在努力让PyCrypto的计数器模式做我想做的事情，所以我自己把ECB模式变成了CTR。我的计数器可以向上和向下移动，以甩掉密码分析师！他们不可能读到我的照片。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from Crypto.Cipher import AES

KEY = ?

class StepUpCounter(object):
    def __init__(self, value=os.urandom(16), step_up=False):
        self.value = value.hex()
        self.step = 1
        self.stup = step_up
    def increment(self):
        if self.stup:
            self.newIV = hex(int(self.value, 16) + self.step)
        else:
            self.newIV = hex(int(self.value, 16) - self.stup)
        self.value = self.newIV[2:len(self.newIV)]
        return bytes.fromhex(self.value.zfill(32))
    def __repr__(self):
        self.increment()
        return self.value

@chal.route('/bean_counter/encrypt/')
def encrypt():
    cipher = AES.new(KEY, AES.MODE_ECB)
    ctr = StepUpCounter()
    out = []
    with open("challenge_files/bean_flag.png", 'rb') as f:
        block = f.read(16)
        while block:
            keystream = cipher.encrypt(ctr.increment())
            xored = [a^b for a, b in zip(block, keystream)]
            out.append(bytes(xored).hex())
            block = f.read(16)
    return {"encrypted": ''.join(out)}

根据加密程序和加密方式图我们可以知道，如果我们能得到和明文密文一起异或的值，就能复原png图片，但是png图片的开头16字节是相同的，我们可以根据这种方法和密文异或得到这个值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from pwn import xor
import requests

url='https://aes.cryptohack.org/bean_counter/'

header=bytes.fromhex('89504e470d0a1a0a0000000d49484452')
r=requests.get(url+'encrypt/')
data=bytes.fromhex(r.json()['encrypted'])
enc=data[:16]
num=xor(header,enc)
print(num)
png=b''
for i in range(0,len(data)-1,16):
	png+=xor(num,data[i:16+i])
with open("flag.png",'wb') as f:
	f.write(png)

这里需要注意python的异或符号^是在整数上的异或，如果异或结果前面带0会被忽略掉，为了保证png文件的完整性我们需要在字节上进行异或，这里用了pwn库的xor。

RSA

RSA Starter 1

RSA中的所有操作都涉及模幂运算。
模幂运算是密码学中广泛使用的一种运算，通常写为：$2^{10} \bmod 17$
可以将此视为将某个数提高到某个幂（$2^{10}=1024$），然后将除法的余数除以其他数（$1024 \bmod 17=4$）。
在RSA中，模幂运算与素因子分解问题一起帮助我们构建”trapdoor函数”。这是一个在一个方向上很容易计算的函数，但在相反的方向上很难计算，除非你有正确的信息。它允许我们对消息进行加密，只有拥有密钥的人才能执行反向操作来解密它。
计算$101^{17}\bmod 22663$

1
print(pow(101,17,22663))#19906

RSA Starter 2

RSA加密是具有指数$e$和模量$n$的消息的模幂，通常是两个素数的乘积：$n=pq$。
指数和模数一起构成RSA公钥（N，e）。$e$最常见的值是0x10001或65537。
使用指数$e=65537$和素数$p=17$和$q=23$加密数字12。你得到的密文是多少？

1
2
3
4
5
6
7
e=65537
p=17
q=23
n=p*q
m=12
c=pow(m,e,n)
print(c)#301

RSA Starter 3

RSA依赖于模n的因子分解的难度。如果可以找到素数，那么我们可以计算n的欧拉函数，从而解密密文。
给定$n=pq$和两个素数：

1
2
p = 857504083339712752489993810777
q = 1029224947942998075080348647219

$n$的欧拉函数是多少？

由于$p$和$q$都是素数且互不相等，$phi=(p-1)(q-1)$

RSA Starter 4

私钥d用于解密用相应公钥创建的密文（它也用于对消息进行“签名”）。
私钥是一条秘密信息或“trapdoor”，它允许我们快速反转加密功能。如果RSA实现得很好，如果您没有私钥，解密密文的最快方法是首先对模数进行因子分解。
在RSA中，私钥是对指数$e$关于$n$的欧拉函数的模逆。

1
2
3
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537

求d：

1
2
3
4
5
6
7
8
import gmpy2

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
print(d)#121832886702415731577073962957377780195510499965398469843281

RSA Starter 5

我使用上一题的公钥参数加密了一个秘密号码：
N=882564595536224140639625987659416029426239230804614613279163
e=65537
使用您在上一个挑战中为这些参数找到的私钥来解密此密文：
c=77578995801157823671636298847186723593814843845525223303932

1
2
3
4
d=121832886702415731577073962957377780195510499965398469843281
n=882564595536224140639625987659416029426239230804614613279163
e=65537
print(pow(c,d,n))#13371337

RSA Starter 6

如何确保收到你信息的人知道是你写的？我们可以通过签署消息来防止发出的消息被攻击。
假设你写了一条消息$m$。你用你朋友的公钥来加密这条消息：$c=m^{e_0} \bmod n_0$
要签署此消息，需要计算消息的哈希值：$H(m)$，并使用您的私钥“加密”：$s=H(m)^{d_1} \bmod n_1$

在真正的密码系统中，最好使用单独的密钥来加密和签名消息。

你的朋友可以使用他们的私钥解密消息：$m=c^{d_0} \bmod n_0$。使用您的公钥，他们计算$S=s^{e_1} \bmod n_1$
现在，通过计算$H(m)$并将其与$S$进行比较：确保$H(m)=S$，他们可以确保你发送给他们的消息就是他们收到的消息。

下面使用你的私钥和SHA256哈希函数对crypto{Immut4ble_m3ssag1ng}进行签名，这里提供了n和d。

哈希函数的输出需要转换为一个可以用于RSA数学的数字.

1
2
3
4
5
6
7
8
9
import hashlib

text='crypto{Immut4ble_m3ssag1ng}'
n = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689

h=int(getattr(hashlib,'sha256')(text.encode()).hexdigest(),16)
s=pow(h,d,n)
print(s)

或者：

1
2
3
4
5
6
7
8
9
import hashlib

text=b'crypto{Immut4ble_m3ssag1ng}'
n = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689

h=int(hashlib.sha256(text).hexdigest(),16)
s=pow(h,d,n)
print(s)

或者：

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Hash import SHA256
from Crypto.Util.number import *

text=b'crypto{Immut4ble_m3ssag1ng}'
n = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689

h=SHA256.new(text).digest()
h=bytes_to_long(h)
s=pow(h,d,n)
print(s)

Factoring

到目前为止，我们一直在使用小素数的乘积作为模数，但小素数对RSA没有多大好处，因为它们可以使用现代方法进行因子分解。
现在，建议使用长度至少为1024位的素数乘以两个这样的1024位素数，得到2048位的模数。具有2048位模数的RSA被称为RSA-2048。
有人说，要真正做到经得起未来考验，你应该使用RSA-4096甚至RSA-8192。然而，这里有一个折衷方案；生成大质数需要更长的时间，加上大模数的模幂运算可以预测地更慢。

将150位数字510143758735509025530880200653196460532653147分解为其两个组成素数，给出较小的答案。

用factordb，得到两个因子19704762736204164635843 5889363174021185185929

Inferius Prime

这是我的超强RSA实现，因为它有1600位，应该是牢不可破的……至少我这么认为！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD

e = 3

while True:
    p = getPrime(100)
    q = getPrime(100)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    if d != -1 and GCD(e, phi) == 1:
        break

n = p * q

flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag
'''
n = 742449129124467073921545687640895127535705902454369756401331
e = 3
ct = 39207274348578481322317340648475596807303160111338236677373
'''

研究了半天也没发现他这个RSA强壮在哪……

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2

#yafu
p=752708788837165590355094155871
q=986369682585281993933185289261
c=39207274348578481322317340648475596807303160111338236677373
n=p*q
phi=(p-1)*(q-1)
e=3
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

Monoprime

为什么每个人都如此痴迷于将RSA的两个素数相乘。为什么不只用一个呢？

1
2
3
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942

本题中，$n$只是个质数，没有因子：

1
2
3
4
import gmpy2

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591 
print(gmpy2.is_prime(n))#true

好像不影响做题：

1
2
3
4
5
6
7
8
9
10
11
import gmpy2
from Crypto.Util.number import *

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

phi=(n-1)
d=gmpy2.invert(e,phi)
m=pow(ct,d,n)
print(long_to_bytes(m))

Square Eyes

得到2048位的素数需要很长时间，所以我只生成了一个并使用了两次。

如果你被卡住了，再看看欧拉函数。

1
2
3
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

那就直接开方就行了，这里求解欧拉函数：$\phi(n)=\phi(p^2)=p\phi(p) $

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
import gmpy2

n=535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e=65537
c=222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896
p=gmpy2.iroot(n,2)[0]
phi=p*(p-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

Manyprime

使用一个素因子绝对是个坏主意，所以我将尝试使用30以上的因子。

1
2
3
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464

试了下sympy库直接求欧拉函数，不大行，用yafu分解出了因子，可以求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import gmpy2
from Crypto.Util.number import *

n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464

#yafu
list=[13099895578757581201,
9303850685953812323,
17138336856793050757,
16898740504023346457,
15998365463074268941,
12973972336777979701,
15824122791679574573,
12955403765595949597,
14100640260554622013,
15364597561881860737,
14523070016044624039,
13572286589428162097,
11282698189561966721,
9389357739583927789,
12834461276877415051,
11492065299277279799,
11530534813954192171,
11473665579512371723,
9282105380008121879,
14963354250199553339,
11403460639036243901,
10638241655447339831,
11328768673634243077,
15669758663523555763,
16656402470578844539,
17174065872156629921,
17281246625998849649,
12132158321859677597,
14178869592193599187,
14278240802299816541,
10336650220878499841,
11665347949879312361]

phi=1
for i in list:
    phi*=(i-1)
d=gmpy2.invert(e,phi)
m=pow(ct,d,n)
print(long_to_bytes(m))

Salty

最小的指数应该是最快的，对吧？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

e = 1
d = -1

while d == -1:
    p = getPrime(512)
    q = getPrime(512)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)

n = p * q

flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag
'''
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767                                                                  
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
'''

根据ct长度就能知道m的1次方小于n，ct=m，直接转就行：

1
2
3
4
5
from Crypto.Util.number import *

ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485

print(long_to_bytes(ct))

Modulus Inutilis

我的素数现在应该足够大了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

e = 3
d = -1

while d == -1:
    p = getPrime(1024)
    q = getPrime(1024)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)

n = p * q

flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag

'''
n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
'''

e=3，ct很小，跟上题类似的原理：

1
2
3
4
5
6
from Crypto.Util.number import *
import gmpy2

ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

print(long_to_bytes(gmpy2.iroot(ct,3)[0]))

Everything is Big

1
2
3
N = 0x8da7d2ec7bf9b322a539afb9962d4d2ebeb3e3d449d709b80a51dc680a14c87ffa863edfc7b5a2a542a0fa610febe2d967b58ae714c46a6eccb44cd5c90d1cf5e271224aa3367e5a13305f2744e2e56059b17bf520c95d521d34fdad3b0c12e7821a3169aa900c711e6923ca1a26c71fc5ac8a9ff8c878164e2434c724b68b508a030f86211c1307b6f90c0cd489a27fdc5e6190f6193447e0441a49edde165cf6074994ea260a21ea1fc7e2dfb038df437f02b9ddb7b5244a9620c8eca858865e83bab3413135e76a54ee718f4e431c29d3cb6e353a75d74f831bed2cc7bdce553f25b617b3bdd9ef901e249e43545c91b0cd8798b27804d61926e317a2b745
e = 0x86d357db4e1b60a2e9f9f25e2db15204c820b6e8d8d04d29db168c890bc8a6c1e31b9316c9680174e128515a00256b775a1a8ccca9c6936f1b4c2298c03032cda4dd8eca1145828d31466bf56bfcf0c6a8b4a1b2fb27de7a57fae7430048d7590734b2f05b6443ad60d89606802409d2fa4c6767ad42bffae01a8ef1364418362e133fa7b2770af64a68ad50ad8d2bd5cebb99ceb13368fb31a6e7503e753f8638e21a96af1b6498c18578ba89b98d70fa482ad137d28fe701b4b77baa25d5e84c81b26ee9bddf8cbb51a071c60dd57714de379cd4bc14932809ba18524a0a18e4133665cfc46e2c4fcfbc28e0a0957e5513a7307c422b87a6182d0b6a074b4d
c = 0x6a2f2e401a54eeb5dab1e6d5d80e92a6ca189049e22844c825012b8f0578f95b269b19644c7c8af3d544840d380ed75fdf86844aa8976622fa0501eaec0e5a1a5ab09d3d1037e55501c4e270060470c9f4019ced6c4e67673843daf2fd71c64f3dd8939ae322f2b79d283b3382052d076ebe9bb50b0042f1f7dd7beadf0f5686926ade9fc8370283ead781a21896e7a878d99e77c3bb1f470401062c0e0327fd85da1cf12901635f1df310e8f8c7d87aff5a01dbbecd739cd8f36462060d0eb237af8d613e2d9cebb67d612bcfc353ef2cd44b7ac85e471287eb04ae9b388b66ea8eb32429ae96dba5da8206894fa8c58a7440a127fceb5717a2eaa3c29f25f7

维纳攻击，直接上脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import gmpy2
from Crypto.Util.number import *

def f2c(p,q):
 a=[]
 while q:
  a.append(p//q)
  p,q=q,p%q
 return a

def c2f(a):
  x,y=0,1
  for a in a[::-1]:
    x,y=y,x+a*y
  return (x,y)

def sf(a):
 f=[]
 for i in range(1,len(a)):
  f.append(c2f(a[:i]))
 return f

def solve_p_q(n,phi):
  x=n-phi+1  
  y=x*x-4*n  
  z=gmpy2.iroot(y,2)[0]  
  q=(x+z)//2
  p=(x-z)//2
  return p,q

def wiener_attack(e,n):
 a=f2c(e,n)
 for (d,k) in sf(a):
  if d!=0 and k!=0:
    phi=(e*d-1)//k
    (p,q)=solve_p_q(n,phi)
    if p*q==n:
      m=pow(c,d,n)
      print(long_to_bytes(m))
      break

n=0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
e=0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c=0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474

wiener_attack(e,n)

Crossed Wires

我让我的朋友在发送给我之前加密我们的秘密flag，但他们没有使用我的密钥，而是使用了自己的密钥！你能帮忙吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime

FLAG = b"crypto{????????????????????????????????????????????????}"

p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)

my_key = (N, d)

friends = 5
friend_keys = [(N, getPrime(17)) for _ in range(friends)]

cipher = bytes_to_long(FLAG)

for key in friend_keys:
    cipher = pow(cipher, key[1], key[0])

print(f"My private key: {my_key}")
print(f"My Friend's public keys: {friend_keys}")
print(f"Encrypted flag: {cipher}")
'''
My private key: (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
My Friend's public keys: [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
Encrypted flag: 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
'''

根据$n,d$，有算法可以因式分解：

我们知道$ed\equiv 1 \bmod phi$

可以假设$k=ed-1$

我们从$[0,n]$之间随机取一个整数$g$，当$k\bmod 2=0$时，让$k$值缩小一半，$x=(g^k\bmod n)-1$，如果$x≠0$而且$x,n$的最大公因数大于$1$，这个最大公因数就为$p$，否则继续循环：

1
2
3
4
5
6
7
8
9
def pq(n,e,d):
    while 1:
        k=e*d-1
        g=random.randint(0,n)
        while k%2==0:
            k=k//2
            x=pow(g,k,n)-1
            if x!=0 and gmpy2.gcd(x,n)>1:
                return gmpy2.gcd(x,n)

注意到这个题里进行了多次加密，使用同一个$n$和不同的$e$，所以我们可以计算多个$d$，因式分解后我们可以求出$\phi(n)$，所以就能求出每次加密的$d$，进而求解。

注意这里加密次序和解密次序无关，我们解密的时候没有必要按照相反的顺序进行解密，因为有：

最终求得flag：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from Crypto.Util.number import *
import gmpy2
import random 

def pq(n,e,d):
    while 1:
        k=e*d-1
        g=random.randint(0,n)
        while k%2==0:
            k=k//2
            x=pow(g,k,n)-1
            if x!=0 and gmpy2.gcd(x,n)>1:
                return gmpy2.gcd(x,n)

list=[
(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), 
(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), 
(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), 
(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), 
(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]

n=21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
d=2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
c=20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
e=65537

p=pq(n,e,d)
q=n//p
phi=(p-1)*(q-1)

for e in list:
  dd=gmpy2.invert(e[1],phi)
  m=pow(c,dd,n)
print(long_to_bytes(m))

Everything is Still Big

好吧，这一次我保护了自己。现在没有什么能阻止我和我的超级计算机！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long, inverse
from random import getrandbits
from math import gcd

FLAG = b"crypto{?????????????????????????????????????}"

m = bytes_to_long(FLAG)

def get_huge_RSA():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p*q
    phi = (p-1)*(q-1)
    while True:
        d = getrandbits(512)
        if (3*d)**4 > N and gcd(d,phi) == 1:
            e = inverse(d, phi)
            break
    return N,e


N, e = get_huge_RSA()
c = pow(m, e, N)

print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')
'''
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
'''

还是用维纳攻击：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import gmpy2
from Crypto.Util.number import *

def f2c(p,q):
 a=[]
 while q:
  a.append(p//q)
  p,q=q,p%q
 return a

def c2f(a):
  x,y=0,1
  for a in a[::-1]:
    x,y=y,x+a*y
  return (x,y)

def sf(a):
 f=[]
 for i in range(1,len(a)):
  f.append(c2f(a[:i]))
 return f

def solve_p_q(n,phi):
  x=n-phi+1  
  y=x*x-4*n  
  z=gmpy2.iroot(y,2)[0]  
  q=(x+z)//2
  p=(x-z)//2
  return p,q

def wiener_attack(e,n):
 a=f2c(e,n)
 for (d,k) in sf(a):
  if d!=0 and k!=0:
    phi=(e*d-1)//k
    (p,q)=solve_p_q(n,phi)
    if p*q==n:
      m=pow(c,d,n)
      print(long_to_bytes(m))
      break

n = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
wiener_attack(e,n)

Endless Emails

题目给了一系列的cne数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/env python3

from Crypto.Util.number import bytes_to_long, getPrime
from secret import messages


def RSA_encrypt(message):
    m = bytes_to_long(message)
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    e = 3
    c = pow(m, e, N)
    return N, e, c


for m in messages:
    N, e, c = RSA_encrypt(m)
    print(f"n = {N}")
    print(f"e = {e}")
    print(f"c = {c}")

首先想到的就是用中国剩余定理，由于给的组数过多，直接写个数组爆破求解就行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from libnum import *
from Crypto.Util.number import *
import gmpy2

n = [14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021,
20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123,
19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147,
12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961,
17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823,
25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263,
19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897]

c = [6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225,
5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172,
5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153,
1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577,
8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805,
23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749,
15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144]

e = 3

for i in range(7):
    for j in range(7):
        for k in range(7):
            if i!=k and j!=k and i!=j:
                m_e=solve_crt([c[i],c[j],c[k]], [n[i],n[j],n[k]])
                t=long_to_bytes(gmpy2.iroot(m_e,e)[0])
                if b'crypto' in t:
                    print(t)

Infinite Descent

找到大素数很慢，所以我设计了一个优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import random
from Crypto.Util.number import bytes_to_long, isPrime

FLAG = b"crypto{???????????????????}"

def getPrimes(bitsize):
    r = random.getrandbits(bitsize)
    p, q = r, r
    while not isPrime(p):
        p += random.getrandbits(bitsize//4)
    while not isPrime(q):
        q += random.getrandbits(bitsize//8)
    return p, q

m = bytes_to_long(FLAG)
p, q = getPrimes(2048)
n = p * q
e = 0x10001
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

随机生成$p,q$，如果不是质数就加一个小很多的数，直到出现质数为止，猜测因数差很小，尝试使用yafu，结果n位数太大运行不了，试了试sympy库，有了：

1
2
3
4
5
6
7
8
9
10
11
import sympy
import gmpy2
from Crypto.Util.number import *

n=383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
c=98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
e = 0x10001
phi=sympy.totient(n)
d=gmpy2.invert(e,int(phi))
m=pow(c,d,n)
print(long_to_bytes(m))

当然，考虑pq很接近也可以考虑使用费马因式分解进行分解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from sympy.ntheory.primetest import is_square
import sympy

def fermat(n):
    a=int(sympy.sqrt(n))
    b=a*a-n
    while not is_square(b):
        a+=1
        b=a*a-n
    else:
        p=int(a-sympy.sqrt(b))
        q=n//p
        if p*q==n:
            return p,q

Marin’s Secrets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#!/usr/bin/env python3

import random
from Crypto.Util.number import bytes_to_long, inverse
from secret import secrets, flag


def get_prime(secret):
    prime = 1
    for _ in range(secret):
        prime = prime << 1
    return prime - 1


random.shuffle(secrets)

m = bytes_to_long(flag)
p = get_prime(secrets[0])
q = get_prime(secrets[1])
n = p * q
e = 0x10001
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

这题生成的指数在二进制下都为0b11111……形式，所以理论上可以爆破出pq求解RSA：

最终在2000-3000的区间找到了p和q：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
import gmpy2

n=658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
c=400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
e = 0x10001

for i in range(2000,3000):
    for j in range(2000,3000):
        if (2**i-1)*(2**j-1)==n:
            p=2**i-1
            q=2**j-1
            assert p*q==n
            print(p,q)
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m).decode())

也可以直接判断是否为n的因子，这样更快一点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
import gmpy2

n=658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
c=400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
e = 0x10001

t=2
while n%(2**t-1):
    t+=1
p=2**t-1
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

Signing Server

提供了nc：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener

class Challenge():
    def __init__(self):
        self.before_input = "Welcome to my signing server. You can get_pubkey, get_secret, or sign.\n"

    def challenge(self, your_input):
        if not 'option' in your_input:
            return {"error": "You must send an option to this server"}

        elif your_input['option'] == 'get_pubkey':
            return {"N": hex(N), "e": hex(E) }

        elif your_input['option'] == 'get_secret':
            secret = bytes_to_long(SECRET_MESSAGE)
            return {"secret": hex(pow(secret, E, N)) }

        elif your_input['option'] == 'sign':
            msg = int(your_input['msg'], 16)
            return {"signature": hex(pow(msg, D, N)) }

        else:
            return {"error": "Invalid option"}
        
listener.start_server(port=13374)

靶机提供了加密和解密的服务，直接把他传回来的secret再传回去解密就得到flag了：

1
2
3
4
5
6
7
8
9
10
11
12
13
from pwn import *
import json

p=remote('socket.cryptohack.org',13374)
data = p.recvline()

p.send(json.dumps({'option': 'get_secret'}).encode())
data = json.loads(p.recvline())

p.send(json.dumps({'option': 'sign', 'msg': data['secret']}).encode())
data = json.loads(p.recvline())

print(bytes.fromhex(data['signature'][2:]).decode())

Diffie-Hellman

Diffie-Hellman Starter 1

模$n$的整数集合，加上加法和乘法运算，就是一个环。这意味着将集合中的任意两个元素相加或相乘将返回集合中的另一个元素。
当模是质数：$n=p$时，保证了集合中每个元素有逆元，因此环被提升为域。我们将该域称为有限域$F_p$。
Diffie-Hellman协议与一些有限域$F_p$的元素一起工作，其中素模通常是大素数。
给定素数$p=991$，元素$g=209$，求逆元素$d$，使得$gd \bmod 991=1$。

1
2
3
import gmpy2

print(gmpy2.invert(209,991))

Diffie-Hellman Starter 2

有限域$F_p$的每个元素都可以用于在重复的乘法作用下生成子群$H$。换句话说，对于元素$g:H=\{g,g^2,g^3,…\}$
$F_p$的本原元素是其子群$H=F_p$的元素，即$F_p$的每个元素，可以被写为某个整数$n$的$g^n \bmod p$。因此，本原元素有时被称为有限域的生成元。
对于$p=28151$的有限域，找到最小元素$g$，它是$F_p$的本原元素。

这个问题可以用蛮力解决，但也有一些聪明的方法来加速计算。

一开始想的是将所有生成的写进数组，然后看看数组不重复元素的数量，得到了本原元素7：

1
2
3
4
5
6
7
8
9
p=28151

for j in range(2,p):
    list=[]
    for i in range(1,p):
        list.append(pow(j,i,p))
    if len(set(list))==p-1:
        print(j)
        break

然后看了wp，感觉wp优化的算法比较好一些：

我们可以计算$j^i$通过检查它生成的循环是否在大小上小于$p$，如果我们在p个元素之前检测到一个循环，$j$就不能成为$Fp$的本原元素，因为$j^1=j$，我们就可以以$j$自身作为判断基准，如果$j^n=j,n≠1$出现在$p$的中间，说明这个数的任意次方无法覆盖到所有的元素，生成的子群$H$大小小于有限域，也就不是本原元素，省去了一大部分的计算空间：

1
2
3
4
5
6
7
8
9
10
11
12
13
p=28151

def generator(j):
    for i in range(2,p):
        if pow(j,i,p)==j:
            return p
    return j

for j in range(2,p):
    res=generator(j)
    if res==j:
        print(j)
        break

Diffie-Hellman Starter 3

使用Diffie-Hellman协议是因为离散对数被认为是精心选择的群的“困难”计算。
Diffie-Hellman的第一步是建立一个素数$p$和有限域$g$的一些本原元素。必须仔细选择这些本原元素，以避免使用有效算法求解离散对数的特殊情况。例如，一个安全素数$p=2q+1$通常是这样选取的，即$p-1$的唯一因子是$2，q$，其中$q$是其他一些大素数。这保护DH免受Pohlig–Hellman算法的影响。
然后，用户选择一个秘密整数$a<p$并计算$g^a \bmod p$。这可以在不安全的网络上传输，由于离散对数的假设困难，秘密整数应该无法计算。

计算：$g^a \bmod p$

1
2
3
g: 2
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
a: 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815
1
2
3
4
5
g=2
p=2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
a=972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815

print(pow(g,a,p))

Diffie-Hellman Starter 4

现在是时候使用从朋友Alice收到的数据来计算共享秘密了。与之前一样，我们将使用NIST的参数：

NIST是一家美国标准机构，为密码学等提供标准。这里的参数是建议在DH中使用的参数。

1
2
g: 2
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919

您已从Alice收到以下整数：

1
A: 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601

生成秘密整数b并计算公共整数B，然后发送给Alice：

1
2
b: 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
B: 518386956790041579928056815914221837599234551655144585133414727838977145777213383018096662516814302583841858901021822273505120728451788412967971809038854090670743265187138208169355155411883063541881209288967735684152473260687799664130956969450297407027926009182761627800181901721840557870828019840218548188487260441829333603432714023447029942863076979487889569452186257333512355724725941390498966546682790608125613166744820307691068563387354936732643569654017172

你和Alice现在可以计算共享的秘密，如果只知道$g,p,a,B$，这是不可行的。
你的共享秘密是什么？

一些计算原理：$x$为共享的秘密。

我们接收消息并解密：

Alice解密：

外界很容易知道$A,B,p,g$，但是如果不知道$a,b$的话无法解密。

1
2
3
4
p=2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A=70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
b=12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
print(pow(A,b,p))

Diffie-Hellman Starter 5

Alice想向您发送她的秘密flag，并要求您与她生成共享秘密。她还告诉你她将使用NIST标准：

1
2
g: 2
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919

您从Alice收到以下整数：

1
A: 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784

然后生成您的秘密整数并计算您的公共整数，然后将其发送给Alice。

1
2
b: 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
B: 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581

每个人单独使用共享密钥来导出AES私钥。这允许您通过通道加密大量数据，而无需再次交换密钥。
Alice向您发送以下初始化向量(IV,Initialization Vector，AES加密用的)和密文：

1
{'iv': '737561146ff8194f45290f5766ed6aba', 'encrypted_flag': '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'}

本题提供了辅助用的解密脚本，按照上一题的算法进行计算然后利用脚本就可以得到flag：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib

def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))

def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

p=2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A=112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
b=197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
    
shared_secret = pow(A,b,p)
iv = '737561146ff8194f45290f5766ed6aba'
ciphertext = '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'

print(decrypt_flag(shared_secret, iv, ciphertext))

Parameter Injection

我们不仅可以拦截Alice和Bob的DH密钥交换，还可以重写他们的消息。想一想如何利用他们计算的DH方程，从而避免了破解任何离散对数问题的需要。
在恢复共享秘密后，使用“Diffie Hellman Starter 5”中的脚本解密flag。

这题提供了nc的IP和端口：

1
2
nc socket.cryptohack.org 13371
Intercepted from Alice: {"p": "0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", "g": "0x02", "A": "0xc318d5046d10f20bdeb4503a1fe6a32c41ec005d5dc722d965798354a91e0a92b49ea77fa3527463fbb6bdd4db715ff0cdaac66d82455e99c8c8502e5dd57b0f825e865ac1176e4a53488156a552b50b22f1e0be1d1b1d86539aff371efabda697bb05d56a14bbe87c4f922ec319e8b2ddb71797f8540f0209a6fb41aa3a1e7ef8038ad228e5fc1ad55d135a1cfde873ee870a4a711d62ec7ed3fa146d90204d6bca87a5fc6def686474d857b36af2d9b3e0775611e1b65dfd98b43ccfaa807a"}

我先去简单了解了一下这种交互方式：

根据之前学习的知识，本来，Bob会获得来自Alice的$p,g,A$，然后Bob操作完后发送Alice参数$B$，Alice会用B解密$x=B^a\bmod p=g^{ab}\bmod p$出$x$，然后和flag进行AES加密，继续返回给Bob加密后的密文和IV。

现在我们作为一个中间人，获得了来自Alice的$p,g,A$，要由我们发送给Bob来自Alice的消息，Bob再进行他的操作，然后发送给我们$B=g^b$，由我们发送给Alice，接着Alice会用B解密$x=B^a\bmod p=g^{ab}\bmod p$出$x$，然后和flag进行AES加密，返回密文和IV。

所以，我们可以在这其中做些手脚，做到能破解shared_secret值即可，更确切的说，能确定$x$。

这里，我们可以发现，由于是Alice对密文进行AES加密，我们可以在发送B的时候把B参量的赋值做修改，也就是想办法更改$x=B^a\bmod p$得到$x$，注意到如果我们修改为$B=p$，那么Alice计算$x=p^a\bmod p=0$，相当于我们通过篡改消息进而改变了其中的shared_secret值，而Alice就用这个$x=0$和flag进行了加密。

测试了一下，发送{“B”: “0x1”}也可以，这样shared_secret值为1。

经过一顿操作，我们获得了来自Alice加密后的密文和IV:

1
2
3
4
5
6
nc socket.cryptohack.org 13371
Intercepted from Alice: {"p": "0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", "g": "0x02", "A": "0x52b419729fd1684676c85e486c4ef45abb31256df25b44047d5ef739adf8532f52d2d335a102d448e778036f4ebac886b19b009fab6064527a59e7ad1cbf2062417fe498b42657c5c3ec7e7fb0468643e25ae3206dcf3167c077925eca7a02db4c6e5f6cbe8566ad0f5ff9f107229722899572d73caa4996cbd6474c82bae6ff1e72e1d3f7b53a2aa79631bb5ababd4c180badf2fb63aecbb4de4987aa4e3640196588347a3a38433576a7be28e591042dd8d66b12333b2160cebe90a06533e4"}
Send to Bob: {"p": "0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", "g": "0x02", "A": "0x52b419729fd1684676c85e486c4ef45abb31256df25b44047d5ef739adf8532f52d2d335a102d448e778036f4ebac886b19b009fab6064527a59e7ad1cbf2062417fe498b42657c5c3ec7e7fb0468643e25ae3206dcf3167c077925eca7a02db4c6e5f6cbe8566ad0f5ff9f107229722899572d73caa4996cbd6474c82bae6ff1e72e1d3f7b53a2aa79631bb5ababd4c180badf2fb63aecbb4de4987aa4e3640196588347a3a38433576a7be28e591042dd8d66b12333b2160cebe90a06533e4"}
Intercepted from Bob: {"B": "0xfdd60ec58ec3cf5fdadccddfcc845c1b568701b1f0b8f3cf38841991f37fede4bd4fbfdb72d0addc2ed41845c3130fe458bd49e22e9821544bbd4adbab53dc984a58b3259c33b6c52bb7e6b38fc096a79456f39648132db9f2c24170a5fd13c875cd296d8222e32d54749304855dcbf4ca521b3e80e859a0efb3156d22dc107edb531aea31ce7532a29494815311701159deb975ce44e3a9c324d6efe055bd912d094ede150a6a94b80af8aaa1aa1f499aacc49ffef7381399589581d450aade"}
Send to Alice: {"B": "0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff"}                                             
Intercepted from Alice: {"iv": "255e4edb2b3cf8d7cd85c8cd122b8ad0", "encrypted_flag": "d8b3126d77cd7fb1ed7146998fd2a8fe306b4a0b432c92899c6a135bcd6687de"}

此时得到的encrypted_flag是用shared_secret=0得到的，所以我们就不需要其他参量了，直接进行破解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib

def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))

def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

shared_secret = 0
iv = '255e4edb2b3cf8d7cd85c8cd122b8ad0'
ciphertext = 'd8b3126d77cd7fb1ed7146998fd2a8fe306b4a0b432c92899c6a135bcd6687de'

print(decrypt_flag(shared_secret, iv, ciphertext))

Export-grade

Alice和Bob正在使用遗留代码库，需要协商他们都支持的参数。你在谈判过程中处于中间，之后可以被动观察。这次你怎么会毁了他们的一天？

还是提供了ip和端口，连上之后得到：

1
2
nc socket.cryptohack.org 13379
Intercepted from Alice: {"supported": ["DH1536", "DH1024", "DH512", "DH256", "DH128", "DH64"]}

Alice让Bob选择代码库，按照我的想法一定是数越小越有利于我们计算，那就给他修改一下吧：

1
2
3
4
5
6
Send to Bob: {"supported": ["DH64"]}
Intercepted from Bob: {"chosen": "DH64"}
Send to Alice: {"chosen": "DH64"}
Intercepted from Alice: {"p": "0xde26ab651b92a129", "g": "0x2", "A": "0xb682744d51366ecd"}
Intercepted from Bob: {"B": "0x18935f1e4e70d06e"}
Intercepted from Alice: {"iv": "c3135ee738013b680be8b7d9d79eb2cb", "encrypted_flag": "6f2f80da1d750d2e9ec91234d2b2fb3d8729992fc2a1e2984a721565813f49ea"}

我们得到了64位的几个参数，但是我们需要知道$x$，我们有$A=g^a\bmod p$，但是我们不知道$a$，我们需要求解一个一元的离散对数方程，不过数应该不算大，本人暂时水平有限，先交给网站帮忙解一下吧：

Discrete logarithm calculator离散对数计算器

我们得到了$a$，下面的一切都好说了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib

def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))

def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

a=2767330524943000155
B=0x18935f1e4e70d06e
p=0xde26ab651b92a129

shared_secret = pow(B,a,p)
iv = 'c3135ee738013b680be8b7d9d79eb2cb'
ciphertext = '6f2f80da1d750d2e9ec91234d2b2fb3d8729992fc2a1e2984a721565813f49ea'

print(decrypt_flag(shared_secret, iv, ciphertext))#crypto{d0wn6r4d35_4r3_d4n63r0u5}