r1ngs's blog

hgame2019几道有意思的Crypto

2019-02-03

week 1

perfect_secrecy

描述:

Mom told me OTP is perfect secrecy!(结果加上hgame{})

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
import binascii
import string
import random

def strxor(a, b):
return "".join(hex(x ^ y)[2:].zfill(2) for (x, y) in zip(a, b))


fp = open('poem.txt', 'rb')
flag = "*********************************"
strings = fp.readlines()
key = hex(random.randint(2**511, 2**512))[2:]
strs = [strxor(i[:-3], binascii.unhexlify(key)) for i in strings]
result = strxor(flag.encode('utf-8'), binascii.unhexlify(key))
print(strs)
print(result)

'''
output:
['daaa4b4e8c996dc786889cd63bc4df4d1e7dc6f3f0b7a0b61ad48811f6f7c9bfabd7083c53ba54',
'c5a342468c8c7a88999a9dd623c0cc4b0f7c829acaf8f3ac13c78300b3b1c7a3ef8e193840bb',
'dda342458c897a8285df879e3285ce511e7c8d9afff9b7ff15de8a16b394c7bdab920e7946a05e9941d8308e',
'd9b05b4cd5ce7c8f938bd39e24d0df191d7694dfeaf8bfbb56e28900e1b8dff1bb985c2d5aa154',
'd9aa4b00c88b7fc79d99d38223c08d54146b88d3f0f0f38c03df8d52f0bfc1bda3d7133712a55e9948c32c8a',
'c4b60e46c9827cc79e9698936bd1c55c5b6e87c8f0febdb856fe8052e4bfc9a5efbe5c3f57ad4b9944de34',
'd9aa5700da817f94d29e81936bc4c1555b7b94d5f5f2bdff37df8252ffbecfb9bbd7152a12bc4fc00ad7229090',
'c4e24645cd9c28939a86d3982ac8c819086989d1fbf9f39e18d5c601fbb6dab4ef9e12795bbc549959d9229090',
'd9aa4b598c80698a97df879e2ec08d5b1e7f89c8fbb7beba56f0c619fdb2c4bdef8313795fa149dc0ad4228f',
'cce25d48d98a6c8280df909926c0de19143983c8befab6ff21d99f52e4b2daa5ef83143647e854d60ad5269c87',
'd9aa4b598c85668885df9d993f85e419107783cdbee3bbba1391b11afcf7c3bfaa805c2d5aad42995ede2cdd82977244',
'e1ad40478c82678995df809e2ac9c119323994cffbb7a7b713d4c626fcb888b5aa920c354be853d60ac5269199',
'c4ac0e53c98d7a8286df84936bc8c84d5b50889aedfebfba18d28352daf7cfa3a6920a3c',
'd9aa4f548c9a609ed297969739d18d5a146c8adebef1bcad11d49252c7bfd1f1bc87152b5bbc07dd4fd226948397',
'c4a40e698c9d6088879397d626c0c84d5b6d8edffbb792b902d49452ffbec6b6ef8e193840',
'c5ad5900df8667929e9bd3bf6bc2df5c1e6dc6cef6f2b6ff21d8921ab3a4c1bdaa991f3c12a949dd0ac5269c']
'c2967e7fc59d57899d8bac852ac3c866127fb9d7f1e5b68002d9871cccb8c6b2aa'
'''

非预期解

自己非预期了,直接通过暴破$key$的每一个字节判断每条$cipher$的对应位置的字节是不是都是大小写字母或者空格,把$key​$恢复了出来,当时的解题脚本已经删了,有个截图凑合看吧2333

比较巧合的是刚好除了第一个字节有多种可能以外,其他的字节都只有一种可能

预期解

首先,如果我们运行下面的代码,程序输出结果是空,这说明任意两个字母异或的结果都不是字母

1
2
3
4
5
6
7
8
from string import letters
from Crypto.Util.strxor import strxor

for i in letters:
for j in letters:
tmp = strxor(i, j)
if tmp in letters:
print 1

而对于空格来说,空格和任意字母(大写/小写)异或的结果都是这个字母的(小写/大写),而$C_1\;xor\;C_2 = m_1\;xor\;m_2$

所以,如果两个密文异或的结果里面有字母的话,就很有可能一个是字母一个是空格,那么我们再将其中一个密文和另外几个密文异或也是字母或者chr(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from string import letters
from Crypto.Util.strxor import strxor
from libnum import n2s

cipher = [
'daaa4b4e8c996dc786889cd63bc4df4d1e7dc6f3f0b7a0b61ad48811f6f7c9bfabd7083c53ba54',
'c5a342468c8c7a88999a9dd623c0cc4b0f7c829acaf8f3ac13c78300b3b1c7a3ef8e193840bb',
'dda342458c897a8285df879e3285ce511e7c8d9afff9b7ff15de8a16b394c7bdab920e7946a05e9941d8308e',
'd9b05b4cd5ce7c8f938bd39e24d0df191d7694dfeaf8bfbb56e28900e1b8dff1bb985c2d5aa154',
'd9aa4b00c88b7fc79d99d38223c08d54146b88d3f0f0f38c03df8d52f0bfc1bda3d7133712a55e9948c32c8a',
'c4b60e46c9827cc79e9698936bd1c55c5b6e87c8f0febdb856fe8052e4bfc9a5efbe5c3f57ad4b9944de34',
'd9aa5700da817f94d29e81936bc4c1555b7b94d5f5f2bdff37df8252ffbecfb9bbd7152a12bc4fc00ad7229090',
'c4e24645cd9c28939a86d3982ac8c819086989d1fbf9f39e18d5c601fbb6dab4ef9e12795bbc549959d9229090',
'd9aa4b598c80698a97df879e2ec08d5b1e7f89c8fbb7beba56f0c619fdb2c4bdef8313795fa149dc0ad4228f',
'cce25d48d98a6c8280df909926c0de19143983c8befab6ff21d99f52e4b2daa5ef83143647e854d60ad5269c87',
'd9aa4b598c85668885df9d993f85e419107783cdbee3bbba1391b11afcf7c3bfaa805c2d5aad42995ede2cdd82977244',
'e1ad40478c82678995df809e2ac9c119323994cffbb7a7b713d4c626fcb888b5aa920c354be853d60ac5269199',
'c4ac0e53c98d7a8286df84936bc8c84d5b50889aedfebfba18d28352daf7cfa3a6920a3c',
'd9aa4f548c9a609ed297969739d18d5a146c8adebef1bcad11d49252c7bfd1f1bc87152b5bbc07dd4fd226948397',
'c4a40e698c9d6088879397d626c0c84d5b6d8edffbb792b902d49452ffbec6b6ef8e193840',
'c5ad5900df8667929e9bd3bf6bc2df5c1e6dc6cef6f2b6ff21d8921ab3a4c1bdaa991f3c12a949dd0ac5269c']

target = 'c2967e7fc59d57899d8bac852ac3c866127fb9d7f1e5b68002d9871cccb8c6b2aa'

for i in range(len(cipher)):
cipher[i] = cipher[i][0:len(target)]
cipher[i] = n2s(int(cipher[i], 16))
target = n2s(int(target, 16))


def check(j, i):
for pos in range(len(cipher)):
if strxor(cipher[j][i], cipher[pos][i]) not in letters + chr(0):
return False
return True

def find(i):
for j in range(len(cipher)):
for k in range(len(cipher) - j - 1):
if strxor(cipher[j][i], cipher[k+j+1][i]) in letters:
if check(j, i):
return strxor(strxor(cipher[j][i], target[i]), ' ')
elif check(k+j+1, i):
return strxor(strxor(cipher[k+j+1][i], target[i]), ' ')
else:
pass
return '?'

flag = ''
for i in range(len(target)):
flag += find(i)

print flag

最终输出结果为:

?TP_is_not_safe_if_more_than_once

其中?代表这个位置是不确定的,那么很显然应该是题目描述里的OTP的O了

week 2

HILL

描述:

hill密码,秘钥是3x3矩阵,flag的密文是TCSHXZTCXAPBDKJVJDOHJEAE,flag中含有BABYSHILL,flag是有意义的英文,最终提交格式: hgame{有意义的英文}

预期解

$KP=C$

$P=K^{-1}C$

$PC^{-1}=K^{-1}$

BABYSHILL和C中连续的3X3矩阵的逆相乘就是K的逆

这里要注意的是Hill密码的逆矩阵和线性代数里的不一样,这个坑踩了一天= =

完整解题脚本

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
from gmpy2 import invert
from numpy import *


cipher = [
['T', 'H', 'T', 'A', 'D', 'V', 'O', 'E'],
['C', 'X', 'C', 'P', 'K', 'J', 'H', 'A'],
['S', 'Z', 'X', 'B', 'J', 'D', 'J', 'E']
]
for i in range(3):
for j in range(8):
cipher[i][j] = ord(cipher[i][j])-65

plain = [
['B', 'Y', 'I'],
['A', 'S', 'L'],
['B', 'H', 'L']
]
'''
plain = [
['0', 'B', 'H'],
['B', 'Y', 'I'],
['A', 'S', 'L']
]

plain = [
['A', 'S', 'L'],
['B', 'H', 'L'],
['Y', 'I', '0']
]
'''
for i in range(3):
for j in range(3):
plain[i][j] = ord(plain[i][j])-65

def to_int(m):
for i in range(3):
for j in range(3):
m[i][j] = int(round(m[i][j]))
return matrix(m)

def get_inv_matrix(m):

'''print int(round(linalg.det(m)))
print invert(int(round(linalg.det(m))), 26)'''
try:
kk = invert(int(round(linalg.det(m))), 26)
inv_m = linalg.inv(m)
tmp = inv_m * linalg.det(m)

test_real_inv = array(kk * tmp)
for i in range(3):
for j in range(3):
test_real_inv[i][j] = int(round(test_real_inv[i][j])) % 26
return matrix(test_real_inv)
except:
print int(round(linalg.det(m)))
return m

def flag(m):
str = ''
for i in range(8):
for j in range(3):
str+=chr(int(round(m[j][i])%26)+97)
print str

'''
for i in range(26):
plain[0][0] = i
'''
new_cipher = matrix(cipher)
new_plain = matrix(plain)

cipher_matrix = []
for i in range(6):
tmp = []
tmp.append(cipher[0][i:i+3])
tmp.append(cipher[1][i:i+3])
tmp.append(cipher[2][i:i+3])
cipher_matrix.append(tmp)


C_1 = []
for i in range(6):
C_1.append(get_inv_matrix(to_int(array(cipher_matrix[i]))))

K_1 = []
for i in range(6):
K_1.append(dot(new_plain, C_1[i]))


for j in range(6):
'''print array(dot(K_1[j], new_cipher))'''
flag(array(dot(K_1[j],matrix(cipher))))
print '-'*65


'''
test = [
[6, 24, 1],
[13, 16, 10],
[20, 17, 15]
]
print get_inv_matrix(test)
'''

流氓解

当然,这个题还可以爆破,但是如果直接对$K$进行爆破的话,一共有$26^9=5429503678976$种可能,这是不太现实的

然而我们可以对$K^{-1}$的每一行进行爆破,这样就很快了,而且,由于直接爆破$K^{-1}​$,跳过了求逆矩阵,使得这种方法简单得多,具体代码如下

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
from numpy import *

cipher = [
['T', 'H', 'T', 'A', 'D', 'V', 'O', 'E'],
['C', 'X', 'C', 'P', 'K', 'J', 'H', 'A'],
['S', 'Z', 'X', 'B', 'J', 'D', 'J', 'E']
]
for i in range(3):
for j in range(8):
cipher[i][j] = ord(cipher[i][j])-65

plain = [
['B', 'Y', 'I'],
['A', 'S', 'L'],
['B', 'H', 'L']
]

for i in range(3):
for j in range(3):
plain[i][j] = ord(plain[i][j])-65


K = []
for i in range(26):
for j in range(26):
for k in range(26):
tmp = []
tmp.append(i)
tmp.append(j)
tmp.append(k)
K.append(tmp)

cipher_matrix = []
for i in range(8):
tmp = []
for j in range(3):
tmp.append(cipher[j][i])
cipher_matrix.append(tmp)

def multi(a, b):
assert len(a) == len(b) == 3
num = 0
for i, j in zip(a, b):
num += i*j
return chr((num%26)+65)

'''
for key in K:
str = ''
for i in range(len(cipher_matrix)):
str += multi(key, cipher_matrix[i])
if 'BHL' in str:
print key, str
'''

K1 = [[5, 1, 23], [5, 14, 10], [9, 8, 11], [15, 4, 17], [24, 25, 25], [25, 23, 1]]
K2 = [[6, 9, 23], [21, 4, 3], [21, 17, 5], [23, 20, 23]]
K3 = [[1, 15, 16], [4, 18, 17], [5, 0, 2], [14, 2, 3], [16, 12, 19], [24, 0, 11]]

def flag(m):
str = ''
for i in range(8):
for j in range(3):
str+=chr(int(round(m[j][i])%26)+97)
print str

for k1 in K1:
for k2 in K2:
for k3 in K3:
K = []
K.append(k1)
K.append(k2)
K.append(k3)
flag(array(dot(matrix(K),matrix(cipher))))

在输出的结果里查找$BABYSHILL$就可以找到正确的flag了

week 3

P4ndd!n@!

描述:

Aris跑了过来 嘴里大喊”CBC!” 并递给了我一张纸条
lpFsOPZm9UztVP30SHertuXoWkOEP4Ij7UcjGM1xvFIw78Ti15UwL9YY0xn4syBxW/2BgzRtsZHGksUmWgfr5Q==(参数要用base64编码一发)

URL: http://47.95.212.185:23450/padding?text

其实这道题就是一个非常单纯的padding oracle,主要的坑就是没有给源代码,有点搞不懂逻辑,通过py出题人仔细分析,可以得到:

题目给的base64编码的字符串是IV+cipher,我们首先要做的就是解密cipher,给的接口的回显的Error的意思是padding正确,也就是填充的个数和填充的值都正确,但是解密的值不正确,回显的Something error!的意思就是padding不正确

我们可以通过对plain对应的前一段的cipher的值做更改,利用cbc翻转字节攻击逐位枚举plain,依据Error​的回显来判断枚举是否成功,也就可以恢复所有的明文了

最后一个地方稍微脑洞一点,解密的值是If you R Aris, I will give you flag. 意思是得构造cipher使得解密的明文是Aris,然后才给你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
from Crypto.Util.strxor import strxor
from base64 import *
import requests

def xor(a, b):
return chr(ord(a)^ord(b))

def get_source_code(url):
web = requests.get(url)
return web.text

url = 'http://47.95.212.185:23450/padding?text='

str = 'lpFsOPZm9UztVP30SHertuXoWkOEP4Ij7UcjGM1xvFIw78Ti15UwL9YY0xn4syBxW/2BgzRtsZHGksUmWgfr5Q=='
cipher = b64decode(str)


cipher_list = list(cipher)
'''
for i in range(1, 17):
cipher_list[63-16] = xor(xor(cipher[63-16], chr(i)), chr(1))
state = get_source_code(url+b64encode(''.join(cipher_list)))
if state == 'Error':
print i
'''

flag1='lag.'

'''
cipher_list[63-16-12] = xor(xor(cipher[63-16-12], '.'), chr(17))
cipher_list[63-16-13] = xor(xor(cipher[63-16-13], 'g'), chr(17))
cipher_list[63-16-14] = xor(xor(cipher[63-16-14], 'a'), chr(17))
cipher_list[63-16-15] = xor(xor(cipher[63-16-15], 'l'), chr(17))
'''
cipher_list = cipher_list[:48]



flag2 = ' will give you f'

'''
for i in range(16):
for k in range(i):
cipher_list[47 - k - 16] = xor(xor(cipher[47 - k - 16], flag2[-k-1]), chr(i + 1))
for j in range(256):
cipher_list[47 - i - 16] = xor(xor(cipher[47 - i - 16], chr(j)), chr(i+1))
state = get_source_code(url + b64encode(''.join(cipher_list)))
if state == 'Error':
flag2=chr(j)+flag2
print flag2
break
'''

flag3 = 'If you R Aris, I'
'''
cipher_list = cipher_list[:32]

for i in range(16):
for k in range(i):
cipher_list[31 - k - 16] = xor(xor(cipher[31 - k - 16], flag3[-k-1]), chr(i + 1))
for j in range(32, 256):
cipher_list[31 - i - 16] = xor(xor(cipher[31 - i - 16], chr(j)), chr(i+1))
sleep(0.5)
state = get_source_code(url + b64encode(''.join(cipher_list)))
if state == 'Error':
flag3=chr(j)+flag3
print flag3
break
'''
fake_flag = flag3+flag2+flag1

print fake_flag



IV = cipher[:16]
tmp1 = strxor(strxor(IV[0:4], 'If y'), 'Aris')
tmp2 = strxor(strxor(IV[4:16], 'ou R Aris, I'), chr(12)*12)
print get_source_code(url+b64encode(tmp1+tmp2+cipher[16:32]))

babyRSA

描述:

e = 12
p = 58380004430307803367806996460773123603790305789098384488952056206615768274527
q = 81859526975720060649380098193671612801200505029127076539457680155487669622867
ciphertext = 206087215323690202467878926681944491769659156726458690815919286163630886447291570510196171585626143608988384615185921752409380788006476576337410136447460

这道题已经告诉了$p、q$但是由于$e$是$12$不是素数,和$\varphi(n)$不互素,所以不能用普通的RSA求逆元的算法解这道题,这个时候就需要我们打出题人冷静分析了

由于$m^{12}\equiv c\;(mod\;n)​$则$(m^4)^3\equiv c\;(mod\;n)​$,而$3​$是一个奇素数,所以$3​$的逆元$d​$存在,那么我们有$m^4\equiv c^d\;(mod\;n)​$,当时我觉得4是一个小公钥指数,那么直接用小公钥指数暴破攻击就可以了,于是我就用多进程直接开冲,暴破了1亿多次都没有出结果,而已经有人做出来的时候我就觉得自己的思路应该错了

此时已经临近深夜,正打算挂机暴破一整晚的我突然就想到怎么做了(这周的crypto题给我最深的感触的就是如果思路正确很快就能出答案,如果不正确或者有偏差就会既费时又费力),$m^4\equiv (m^2)^2\equiv c^d\;(mod\;n)​$,而$(m^2)^2​$可以看做是两个Rabin加密,且$p、q​$都是模$4​$余$3​$的素数,直接可以秒解了(话说是不是真的有人暴破小公钥指数做出来的?)

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
import gmpy2
from libnum import *


p = 58380004430307803367806996460773123603790305789098384488952056206615768274527
q = 81859526975720060649380098193671612801200505029127076539457680155487669622867
n = p*q
fn = (p-1)*(q-1)
d1 = gmpy2.invert(3, fn)
c = 206087215323690202467878926681944491769659156726458690815919286163630886447291570510196171585626143608988384615185921752409380788006476576337410136447460

c1 = pow(c, d1, n)

c1 = 0x2a9428e86d9010e3f77d5d50c03c62f041db75a63fc74ed65de56d09

inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)


mp = pow(c1, (p + 1) / 4, p)
mq = pow(c1, (q + 1) / 4, q)


a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c)

for i in (a, b, c, d):
s = '%x' % i
if len(s) % 2 != 0:
s = '0' + s
print n2s(int(s, 16))

basicmath

描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
> from Crypto.Util.number import *
>
> flag = '*******************'
>
> m = int(flag.encode('hex'), 16)
> p = getPrime(256)
> while(p % 4 != 3):
> p = getPrime(256)
> a = pow(m, 2, p)
> print(p)
> print(a)
>
> '''
> p = 96844604612122594734846587450751002272823339993969599631517516290673675281347
> a = 5491280935375344696344639339035431520073311126446116169370534450549651945232
> '''
>

题目的要求就是解一个二次同余方程$m^2\equiv a\;(mod\;p)$,模数$p$是一个模$4$余$3$的奇素数

由欧拉判别定理,$a$是模$p$的平方剩余的充要条件是$a^{(p-1)/2} \equiv 1(mod\;p)$那么$a^{(p-1)/2}a \equiv a(mod\;p)$即$a^{(p+1)/2} \equiv a(mod\;p)$

又有$(a^{(p+1)/4})^2\equiv a\;(mod\;p)$,则令$k=\frac{p+1}{4}$,由于$p$模$4$余$3$,故$k$是一个整数,$(a^k)^2\equiv a \;(mod\;p)$,即$m^2\equiv (a^k)^2\;(mod\;p) $

所以$m\equiv ± a^k\;(mod\;p)​$

1
2
3
4
5
6
7
from libnum import *

p = 96844604612122594734846587450751002272823339993969599631517516290673675281347
a = 5491280935375344696344639339035431520073311126446116169370534450549651945232
k = (p+1)/4
print n2s(pow(a, k, p))
print n2s(p-pow(a, k, p))

week 4

easy_rsa

描述:

m为17位十进制数,提交格式hgame{m}

1
2
3
4
5
6
7
8
9
10
11
12
> e1:0x33240
> e2:0x3e4f
>
> n:0x9439682bf1b4ab48c43c524778c579cc844b60872275725c1dc893b5bcb358b9f136e4dab2a06318bb0c80e202a14bc54ea334519bec023934e01e9378abf329893f3870979e9f2f2be8fff4df931216a77007a2509f49f697bf286285e97fac5dc6e4a164b5c2cc430887b18136437ba67777bda05aafdeaf918221c812b4c7d1665238f84ab0fab7a77fcae92a0596e58343be7a8e6e75a5017c63a67eb11964970659cd6110e9ec6502288e9e443d86229ef2364dfecb63e2d90993a75356854eb874797340eece1b19974e86bee07019610467d44ec595e04af02b574a97fa98bdb2e779871c804219cab715f4a80fef7f8fb52251d86077560b39c1c2a1
>
> c1:0x7c7f315a3ebbe305c1ad8bd2f73b1bb8e300912b6b8ba1b331ac2419d3da5a9a605fd62915c11f8921c450525d2efda7d48f1e503041498f4f0676760b43c770ff2968bd942c7ef95e401dd7facbd4e5404a0ed3ad96ae505f87c4e12439a2da636f047d84b1256c0e363f63373732cbaf24bda22d931d001dcca124f5a19f9e28608ebd90161e728b782eb67deeba4cc81b6df4e7ee29a156f51a0e5148618c6e81c31a91036c982debd1897e6f3c1e5e248789c933a4bf30d0721a18ab8708d827858b77c1a020764550a7fe2ebd48b6848d9c4d211fd853b7a02a859fa0c72160675d832c94e0e43355363a2166b3d41b8137100c18841e34ff52786867d
>
> c2:0xf3a8b9b739196ba270c8896bd3806e9907fca2592d28385ef24afadc2a408b7942214dad5b9e14808ab988fb15fbd93e725edcc0509ab0dd1656557019ae93c38031d2a7c84895ee3da1150eda04cd2815ee3debaa7c2651b62639f785f6cabf83f93bf3cce7778ab369631ea6145438c3cd4d93d6f2759be3cc187651a33b3cc4c3b477604477143c32dfff62461fdfd9f8aa879257489bbf977417ce0fbe89e3f2464475624aafef57dd9ea60339793c69b53ca71d745d626f45e6a7beb9fcbd9d1a259433d36139345b7bb4f392e78f1b5be0d2c56ad50767ee851fac670946356b3c05d0605bf243b89c7e683cc75030b71633632fb95c84075201352d6
>
> c1=pow(m, e1, n)
> c2=pow(m, e2, n)
>

很明显的一个共模攻击

但是如果直接跑的话会报错,因为$e_1$和$e_2$是不互素的,下意识的算了一下$e_1$和$e_2$的$gcd$,为$3$

那么我们可以用共模计算$m^3​$为多少,然后用小公钥指数暴破就可以了

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
import gmpy2
from multiprocessing import Pool

N = 0x9439682bf1b4ab48c43c524778c579cc844b60872275725c1dc893b5bcb358b9f136e4dab2a06318bb0c80e202a14bc54ea334519bec023934e01e9378abf329893f3870979e9f2f2be8fff4df931216a77007a2509f49f697bf286285e97fac5dc6e4a164b5c2cc430887b18136437ba67777bda05aafdeaf918221c812b4c7d1665238f84ab0fab7a77fcae92a0596e58343be7a8e6e75a5017c63a67eb11964970659cd6110e9ec6502288e9e443d86229ef2364dfecb63e2d90993a75356854eb874797340eece1b19974e86bee07019610467d44ec595e04af02b574a97fa98bdb2e779871c804219cab715f4a80fef7f8fb52251d86077560b39c1c2a1
e = 3
cipher = 211655262573966881062823795220179644607412162371069

def calc(j):
print j
a, b = gmpy2.iroot(cipher + j * N, 3)
if b == True:
m = a
print 'success! m->'+str(m)
pool.terminate()
exit()

def SmallE():
inputs = range(0, 130000000)
pool.map(calc, inputs)
pool.close()
pool.join()

if __name__ == '__main__':
pool = Pool(4)
print 'start'
SmallE()

MixedRSA_Easy

描述:

47.95.212.185 38610
由CNSS友情赞助 比心

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
> from Crypto.Util.number import getPrime
> from signal import alarm
>
>
> def gcd(a, b):
> while b != 0:
> a, b = b, a % b
> return a
>
>
> def ex_gcd(m, n):
> x, y, x1, y1 = 0, 1, 1, 0
> while m % n:
> x, x1 = x1 - m // n * x, x
> y, y1 = y1 - m // n * y, y
> m, n = n, m % n
> return n, x, y
>
>
> def inv(x, p):
> g, y, k = ex_gcd(x, p)
> if y < p:
> y += p
> return y
>
>
> def xor(a, b):
> return bytes(x ^ y for x, y in zip(a, b))
>
>
> class MixedRSA:
> n = e = d = iv = BLOCK = 0
>
> def __init__(self, iv, block=256):
> self.BLOCK = block
> p = getPrime(block * 4)
> q = getPrime(block * 4)
> self.n = p * q
> phi = (p - 1) * (q - 1)
> self.e = getPrime(64)
> self.d = inv(self.e, phi)
> iv *= block // len(iv)
> self.iv = iv.rjust(block, b'\x00')
>
> def padding(self, s):
> return b'\x00' * (-len(s) % self.BLOCK) + s
>
> def rsa_encrypt(self, m):
> c = pow(int(m.hex(), 16), self.e, self.n)
> c = hex(c)[2:].rjust(self.BLOCK * 2, '0')
> return bytes.fromhex(c)
>
> def rsa_decrypt(self, c):
> m = pow(int(c.hex(), 16), self.d, self.n)
> m = hex(m)[2:].rjust(self.BLOCK * 2, '0')
> return bytes.fromhex(m)
>
> def encrypt(self, plaintext):
> plaintext = self.padding(plaintext)
> imd = self.iv
> for i in range(0, len(plaintext), self.BLOCK):
> m = xor(imd[-self.BLOCK:], plaintext[i: i + self.BLOCK])
> imd += self.rsa_encrypt(m)
> imd = imd[self.BLOCK:]
> cipher = self.iv
> for i in range(0, len(imd), self.BLOCK):
> c = self.rsa_encrypt(cipher[-self.BLOCK:])
> cipher += xor(c, imd[i: i + self.BLOCK])
> return cipher[self.BLOCK:]
>
> def decrypt(self, cipher):
> cipher = self.iv + cipher
> imd = b''
> for i in range(self.BLOCK, len(cipher), self.BLOCK):
> c = self.rsa_encrypt(cipher[i - self.BLOCK: i])
> imd += xor(c, cipher[i: i + self.BLOCK])
> imd = self.iv + imd
> plaintext = b''
> for i in range(self.BLOCK, len(imd), self.BLOCK):
> m = self.rsa_decrypt(imd[i: i + self.BLOCK])
> plaintext += xor(m, imd[i - self.BLOCK: i])
> return plaintext
>
>
> if __name__ == '__main__':
> alarm(60)
> mix = MixedRSA(FLAG)
> while True:
> print("Choose:\n[1] Encrypt (hex)\n[2] Decrypt (hex)")
> op = input()
> if op == '1':
> msg = bytes.fromhex(input())
> print(mix.encrypt(msg).hex())
> elif op == '2':
> msg = bytes.fromhex(input())
> print(mix.decrypt(msg).hex())
> else:
> print('Bye')
> break
>

这题告诉我一个道理:代码看着费劲就画图

因为加密的时候用了大量的异或运算,所以我下意识去尝试加密chr(0),在加密512个chr(0)的时候发现后一半不是全为0的,通过推算发现是E(E(IV))其中E表示RSA加密

手绘了一个比较丑的流程图,通过对流程图的分析,可以发现如果解密E(E(IV))+chr(0)*256的话那么第二块的明文就是E(IV),进而就可以很简单的得到IV

exp:

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
from socket import *
from libnum import *


def connect(host, port):
s = socket()
s.connect((host, port))
return s

def h2s(s):
return n2s(int(s, 16))

def s2h(s):
return ''.join(['{:02x}'.format(s2n(i)) for i in s])


def send1(s, mess):
print '1'
s.send('1\n')

print s2h(mess)
s.send(s2h(mess)+'\n')
res = s.recv(1024)
print res
return res

def send2(s, mess):
print '2'
s.send('2\n')

print mess
s.send(mess+'\n')

res = s.recv(1024)
print res
return res

def main():
host = '47.95.212.185'
port = 38610
s = connect(host, port)

print s.recv(1024)
res = send1(s, chr(0)*512)
'''print res'''

print s.recv(1024)
EE_iv =res[512:]
res = send2(s, EE_iv+s2h(256*chr(0)))
p1 = res[:512]
p2 = res[512:]
E_iv = p2

print s.recv(1024)
res = send2(s, E_iv+s2h(chr(0)*256))
print h2s(res[:512])

if __name__ == '__main__':
main()

Sign_in_SemiHard

描述:

47.95.212.185 38611
仍然是由CNSS友情赞助 大量的心!
hint:不要想着一步到位 一段一段来 或者 碰碰运气(如果你比较欧的话

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
> from Crypto.Cipher import AES
> from hashlib import md5
> from os import urandom
> import string
> from signal import alarm
>
>
> class Sign:
> block = T = 0
> key = salt = ""
>
> def __init__(self, key, salt):
> self.key = key
> self.salt = salt
> self.block = len(key)
>
> def register(self, username):
> if b'admin' in username:
> return None
> sig = md5(self.salt + username).digest()
> padlen = self.block - len(username) % self.block
> username += bytes([padlen] * padlen)
> iv = urandom(self.block)
> aes = AES.new(self.key, AES.MODE_CBC, iv)
> c = aes.encrypt(username)
> return iv + c + sig
>
> def login(self, cipher):
> if len(cipher) % self.block != 0:
> return None
> self.T -= 1
> iv = cipher[:self.block]
> sig = cipher[-self.block:]
> cipher = cipher[self.block:-self.block]
> aes = AES.new(self.key, AES.MODE_CBC, iv)
> p = aes.decrypt(cipher)
> p = p[:-p[-1]]
> return [p, md5(self.salt + p).digest() == sig]
>
>
> if __name__ == '__main__':
> unprintable = b""
> for i in range(256):
> if chr(i) not in string.printable:
> unprintable += bytes([i])
> alarm(60)
> s = Sign(urandom(16), urandom(16))
> while True:
> print("Choose:\n[1] Register\n[2] Login")
> op = input()
> if op == '1':
> user = input("Input your username(hex): ")
> token = s.register(bytes.fromhex(user))
> if not token:
> print("Sorry, invalid username.")
> else:
> print("Your token is: %s" % token.hex())
> elif op == '2':
> token = input("Input your token: ")
> res = s.login(bytes.fromhex(token))
> if not res:
> print("Sorry, invalid token.")
> elif not res[1]:
> user = res[0].hex()
> print("Sorry, your username(hex) %s is inconsistent with given signature." % user)
> else:
> user = res[0].strip(unprintable).decode("Latin1")
> print("Login success. Welcome, %s!" % user)
> if user == "admin":
> print("I have a gift for you: %s" % FLAG)
> else:
> print("See you")
> break
>

考点:

  • cbc翻转字节攻击

  • hash长度拓展攻击

思路:

  1. 加密chr(20)*5得到md5(salt+chr(20)5)
  2. hash长度拓展攻击得到chr(20)5…admin的签名sig
  3. 加密chr(20)*5…adm1n,得到cipher
  4. 利用cbc反转攻击更改密文,使得最后一块明文为admin,然后提交密文,根据回显拿到倒数第二块明文
  5. 利用倒数第二块明文更改倒数第三块密文,依次类推,最后更改iv使得最终的明文为chr(20)*5…admin
  6. 然后利用sig绕过签名验证,由于admin之前的明文都是不可见字符,所以最终明文就是admin,拿到flag

exp如下,写的很丑

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
from socket import *
from Crypto.Util.strxor import strxor
from re import *
from libnum import *
from hashpumpy import hashpump

def connect(host, port):
s = socket()
s.connect((host, port))
return s

def h2s(s):
return n2s(int(s, 16))

def s2h(s):
return hex(s2n(s))[2:].strip('L')

def pad(msg):
pad_length = 16-len(msg)%16
return msg+chr(pad_length)*pad_length

def get_token(res):
reg = 'Your token is: (.+)\n'
regexp = compile(reg)
str_1 = regexp.findall(res)
token = str_1[0]
return token

def get_plain(res):
reg = 'Sorry, your username\(hex\) (.+) is inconsistent'
regexp = compile(reg)
str_1 = regexp.findall(res)
plain = str_1[0]
return plain

def send1(s, mess):
print '1'
s.send('1\n')
print s.recv(1024)
print s2h(mess)
s.send(s2h(mess)+'\n')
res = s.recv(1024)
print res
return res

def send2(s, mess):
print '2'
s.send('2\n')
print s.recv(1024)
print mess
s.send(mess+'\n')
res = s.recv(1024)
print res
return res

def main():
host = '47.95.212.185'
port = 38611
s = connect(host, port)

print s.recv(1024)

res = send1(s, chr(20)*5)
token1 = get_token(res)

iv1 = token1[:32]
cipher1 = token1[32:-32]
sig1=token1[-32:]


f_sig, mess = hashpump(sig1, chr(20)*5, 'admin', 16)

mess_list = list(mess)
mess_list[-2] = '1'
plain = ''.join(mess_list)

res = send1(s, plain)
token2 = get_token(res)

iv2 = token2[:32]
cipher2 = token2[32:-32]
sig2=token2[-32:]

cipher2_list = list(h2s(cipher2))
cipher2_list[51-16] = strxor(strxor(cipher2_list[51-16], '1'), 'i')
cipher2 = s2h(''.join(cipher2_list))

res = send2(s, iv2+cipher2+f_sig)
plain = get_plain(res)
'''print plain'''
'''print plain[32*2:48*2]'''


cipher2_list = list(h2s(cipher2))
cipher2_list[16:32] = strxor(strxor(''.join(cipher2_list[16:32]), h2s(plain[32*2:48*2])), mess[32:48])
cipher2 = s2h(''.join(cipher2_list))

res = send2(s, iv2+cipher2+f_sig)
plain = get_plain(res)


cipher2_list = list(h2s(cipher2))
cipher2_list[0:16] = strxor(strxor(''.join(cipher2_list[0:16]), h2s(plain[16*2:32*2])), mess[16:32])
cipher2 = s2h(''.join(cipher2_list))

res = send2(s, iv2+cipher2+f_sig)
plain = get_plain(res)

'''print iv2'''
f_iv_list = list(h2s(iv2))
f_iv_list[0:16] = strxor(strxor(''.join(f_iv_list[0:16]), h2s(plain[0*2:16*2])), mess[0:16])
f_iv = s2h(''.join(f_iv_list))

res = send2(s, f_iv+cipher2+f_sig)
print res
if __name__ == '__main__':
main()

参考文章

[1] B 为A 的模m 逆矩阵

[2] Stanford - Cryptography I

[3] 初等数论

Tags: CTF

1000000