GKCTF2020 密码学 writeup

小学生的密码学

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

def c2i(c):
return ord(c)-ord('a')


def i2c(i):
return chr(i+ord('a'))

c = 'welcylk'
ans = ''
for i in c:
ans += i2c(((c2i(i) - 6) * inverse(11, 26)) % 26)
print(base64.b64encode(bytes(ans.encode())))
>>> b'c29yY2VyeQ=='

babycrypto

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
n = 0xb119849bc4523e49c6c038a509a74cda628d4ca0e4d0f28e677d57f3c3c7d0d876ef07d7581fe05a060546fedd7d061d3bc70d679b6c5dd9bc66c5bdad8f2ef898b1e785496c4989daf716a1c89d5c174da494eee7061bcb6d52cafa337fc2a7bba42c918bbd3104dff62ecc9d3704a455a6ce282de0d8129e26c840734ffd302bec5f0a66e0e6d00b5c50fa57c546cff9d7e6a978db77997082b4cb927df9847dfffef55138cb946c62c9f09b968033745b5b6868338c64819a8e92a827265f9abd409359a9471d8c3a2631b80e5b462ba42336717700998ff38536c2436e24ac19228cd2d7a909ead1a8494ff6c3a7151e888e115b68cc6a7a8c6cf8a6c005L
e = 65537
c = 1422566584480199878714663051468143513667934216213366733442059106529451931078271460363335887054199577950679102659270179475911101747625120544429262334214483688332111552004535828182425152965223599160129610990036911146029170033592055768983427904835395850414634659565092191460875900237711597421272312032796440948509724492027247376113218678183443222364531669985128032971256792532015051829041230203814090194611041172775368357197854451201260927117792277559690205342515437625417792867692280849139537687763919269337822899746924269847694138899165820004160319118749298031065800530869562704671435709578921901495688124042302500361
high_p = 0xe4e4b390c1d201dae2c00a4669c0865cc5767bc444f5d310f3cfc75872d96feb89e556972c99ae20753e3314240a52df5dccd076a47c6b5d11b531b92d901b2b512aeb0b263bbfd624fe3d52e5e238beeb581ebe012b2f176a4ffd1e0d2aa8c4d3a2656573b727d4d3136513a931428b00000000000000000000000000000000L

R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
p = high_p + x
x0 = p.small_roots(X = 2^128, beta = 0.1)[0]

P = int(p(x0))
Q = n // P

assert n == P*Q
d = inverse_mod(65537, (P-1)*(Q-1))
print(long_to_bytes(power_mod(c, d, n)))
>>> b'flag{3d0914a1-1e97-4822-a745-c7e20c5179b9}'

汉字的秘密

当铺密码,阴间密码题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
deCode = {'口': '0', '由': '1', '中': '2', '人': '3', '工': '4',
'大': '5', '土': '5', '王': '6', '夫': '7', '井': '8', '士': '5', '壮':'6'}

def decrypt(string):
key = ''
for i in string:
if i in deCode:
key += str(deCode[i])
else:
key += i
return key

ss = decrypt("王壮 夫工 王中 王夫 由由井 井人 夫中 夫夫 井王 土土 夫由 土夫 井中 士夫 王工 王人 土由 由口夫")
list1 = ss.split()
list1 = [int(i) for i in list1]
list1 = [list1[i] + (i + 1) for i in range(len(list1))]

flag = ''
for i in list1:
flag += str(chr(int(i)))
print(flag.lower())
>>> clag{you_are_good}

Backdoor

考点:ROCA (Return of Coppersmith’s attack) RSA

https://crocs.fi.muni.cz/public/papers/rsa_ccs17

由于素数的生成算法不安全,攻击方法由论文可知,由论文下方引的链接可以得到写好的轮子

image-20200524152746970

image-20200524152809312

image-20200524152311317

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
# Hardcoded parameters for efficiency
# Found using params.py
param = \
{
512: {
"n": 39,
"a_max": 62,
"k_max": 37,
"M": 0x924cba6ae99dfa084537facc54948df0c23da044d8cabe0edd75bc6,
"M_prime": 0x1b3e6c9433a7735fa5fc479ffe4027e13bea,
"m": 5,
"t": 6,
"c_a": 0x80000
},
1024: {
"n": 71,
"a_max": 134,
"k_max": 37,
"M": 0x7923ba25d1263232812ac930e9683ac0b02180c32bae1d77aa950c4a18a4e660db8cc90384a394940593408f192de1a05e1b61673ac499416088382,
"M_prime": 0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e,
"m": 4,
"t": 5,
"c_a": 0x40000000
},
2048: {
"n": 126,
"a_max": 434,
"k_max": 53,
"M": 0x7cda79f57f60a9b65478052f383ad7dadb714b4f4ac069997c7ff23d34d075fca08fdf20f95fbc5f0a981d65c3a3ee7ff74d769da52e948d6b0270dd736ef61fa99a54f80fb22091b055885dc22b9f17562778dfb2aeac87f51de339f71731d207c0af3244d35129feba028a48402247f4ba1d2b6d0755baff6,
"M_prime": 0x16928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6,
"m": 7,
"t": 8,
"c_a": 0x400000000
}
}

# https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage
def coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX):
"""
Coppersmith revisited by Howgrave-Graham

finds a solution if:
* b|N, b >= N^beta , 0 < beta <= 1
* |x| < XX
"""
#
# init
#
dd = pol.degree()
nn = dd * mm + tt

#
# checks
#
if not 0 < beta <= 1 :
raise ValueError("beta should belongs in (0, 1]")

if not pol.is_monic():
raise ArithmeticError("Polynomial must be monic.")


#
# Coppersmith revisited algo for univariate
#

# change ring of pol and x
polZ = pol.change_ring(ZZ)
x = polZ.parent().gen()

# compute polynomials
gg = []
for ii in range(mm):
for jj in range(dd):
gg.append((x * XX)**jj * N**(mm - ii) * polZ(x * XX)**ii)
for ii in range(tt):
gg.append((x * XX)**ii * polZ(x * XX)**mm)

# construct lattice B
BB = Matrix(ZZ, nn)

for ii in range(nn):
for jj in range(ii+1):
BB[ii, jj] = gg[ii][jj]

# LLL
BB = BB.LLL(early_red=True, use_siegel=True)

# transform shortest vector in polynomial
new_pol = 0
for ii in range(nn):
new_pol += x**ii * BB[0, ii] / XX**ii

# factor polynomial
potential_roots = new_pol.roots()

return [i[0] for i in potential_roots]

# Top level of the attack, feeds the queue for the workers
def roca(N):

# Key is not always of perfect size, infer from size
keylength = int(log(N, 2))
if keylength < 1000 :
keylength = 512
elif keylength < 2000 :
keylength = 1024
elif keylength < 4000 :
keylength = 2048
else:
keylength = 4096

# bruteforce
M_prime = param[keylength]['M_prime']
c_prime = discrete_log(N, Mod(65537, M_prime))
ord_prime = Zmod(M_prime)(65537).multiplicative_order()
top = (c_prime + ord_prime)/2
beta = 0.5
mm = param[keylength]['m']
tt = param[keylength]['t']

XX = int((2*pow(N, beta)) / M_prime)

# Bruteforce until p, q are found
a_prime = floor(c_prime/2)
while a_prime < top:

# Construct polynomial
m_inv = int(inverse_mod(M_prime, N))
k_tmp = int(pow(65537, a_prime, M_prime))
known_part_pol = int(k_tmp * m_inv)
F = PolynomialRing(Zmod(N), implementation='NTL', names=('x',))
(x,) = F._first_ngens(1)
pol = x + known_part_pol

# Get roots of polynomial using coppersmith
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)

# Check if roots are p, q
for root in roots:
factor1 = k_tmp + abs(root) * M_prime
if mod(N, factor1) == 0:
factor2 = N // factor1
return int(factor1), int(factor2)
a_prime += 1

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import base64

with open('./pub.pem', 'r') as f:
key = RSA.import_key(f.read())
e = key.e
n = key.n
print(n)
with open('flag.enc', 'r') as f:
c = base64.b64decode(f.read())

N = n
print ("[+] Factoring %i" % N)

factor1, factor2 = roca(N)
q = factor1
p = factor2

print ("[+] Found factors of N:")
print ("[+] p =" , factor1)
print ("[+] q =" , factor2)

assert(p * q == n)
d = inverse(e, (q - 1) * (p - 1))
c = bytes_to_long(bytes.fromhex(str(c)[2:-1]))
print(long_to_bytes(pow(c, d, n)))

>>> b'flag{760958c9-cca9-458b-9cbe-ea07aa1668e4}'

Checkin

蚁剑上传exp,然后包含exp,即可得到flag,改为如下命令

exploit.php 地址: https://github.com/mm0r1/exploits

image-20200524155907250

得到flag! 万年没做web了😁

image-20200524155538065

Pokemon

👴青结

image-20200524165726337

评论