20220423-DASxFATE-CryptoSecPartWriteUp

 

special_rsa

考点

  • 有限域开方
  • 回溯

题目

代码。。不知道哪里来的数据,第15行的c1应该写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
from Crypto.Util.number import *
def getPrime1(bitLength, e):
while True:
i = getPrime(bitLength)
if (i - 1) % e ** 2 == 0:
return i
flag=b'DASCTF{????????????????????}'
m = bytes_to_long(flag)
lenth = ((len(bin(m)) - 2) // 2) + 9
e=113
p = getPrime1(lenth, e)
q = getPrime1(lenth, e)
n=p*q
print(f"n = {n}")
c1 = pow(m, e, n)
for i in range(26):
lenth = ((len(bin(c)) - 2) // 2) + 9
p = getPrime1(lenth, e)
q = getPrime1(lenth, e)
n=p*q
print(f"n = {n}")
c=pow(c,e,n)
print(f"e = {e}")
print(f"c = {c}")

getPrime1,可知$(e,\ \varphi(n))=e$,要用有限域开方求根。然后经实践,所有的$n$都能用factordb分解(看下la佬整理的$e|p-1,\ e|q-1$

这道题的关键在于筛选,113次的方程,有113个根,则每次就有113*113=12769种情况

尚师傅提醒每次正确的解是要小于上一个$n$的,即中国剩余定理求出来的解大小一般是$p_i\times q_i$,而正确的解大小是$p_{i-1}\times q_{i-1}$,也就是小于上一个$n$

1
mi = crt(int(x[0]), int(y[0]), pi, qi)

当然在做的时候发现经过上面的筛选,还存在一些漏网之鱼。第一步筛选已经去除掉了绝大部分(但是搞不懂为什么还会有两三组解的情况),再用下类似回溯的思想,就能找到正确那条路获得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
#!/usr/bin/env python
# coding: utf-8
from Crypto.Util.number import *
import re

e = 113
c = 1028324919038104683475485759234995158466543298184637219012354053883391759172761125802189697762778242175407876548832454351014064525118465877297277847501477586955680645311999174005606833294172830817159
ps = [953730950786751671162019537171974567, 232079231415308325450092906880606082069, 88067722275537586769787599991567203589751, 24335212484189159197840692460327461505035059, 7832299017937880395583715032476962329929226581, 1656848589754467667368312855929759764100120657831, 385788223643735590500185001710758495904528462058461, 135813272566456906193934636644217527100917542578856697, 37185691759470013533730603170661686570987787098353146897, 6623023178993627032758350846838617937710601663528839184727, 954412804126450754097808991490470782833291028309980575506163, 350121371461894793578110243222665782247737840410076591434903787, 66882708962198932251728043152245270662769508317424500666902658099, 43449898447639409732732812916430042263570178747794530133229640125923, 11136261905010083405430254612464029672882837025885682392810368001188527, 2623629589005115152329094552749299711026240699896424120660145647226563547, 262775599542220820608778738911414710660835549772895468394761119434220071003, 102366458668689911004027849640392002821642295855327735994412634235696717329671, 15874438801602936764330936047390981280096007684699625987478211613419079727910193, 4479430800690915874719403516331677127806963529247809966024777708496270901092401687, 1328165608715012145707239303399129070657427496129541416861187541092152796676371237057, 368461902207817023013078031477042541053987571003677386333567043030477451518424731838173, 206721456778089912780641186795393376537372828449722520397829606593267585681448641482345737, 43870497594014737833600078975099212558645315030912084285417550950854483979406797450479252891, 14702310219802004876082313481498680940324963613770096574742182597840558294030859405666549879531, 5952590790902091635268726673538951527433355660839816621733964706901441977862333411532558667717227, 978009050697262759337388871320370165458800566798280419667959552859180906066907114053826258140106617]


def get_roots(ii, ci):
pi, qi = ps[ii], qs[ii]
R.<x> = Zmod(pi)[]
f = x ^ e - ci
f = f.monic()
res1 = f.roots()

R.<x> = Zmod(qi)[]
f = x ^ e - ci
f = f.monic()
res2 = f.roots()

sol = []
for x in res1:
for y in res2:
mi = crt([int(x[0]), int(y[0])], [pi, qi])
if ii != 0 and mi < ns[ii - 1]:
sol.append(mi)
print(f'No.{ii} x = {x}, y = {y}')
elif long_to_bytes(mi).startswith(b'DASCTF'):
print(long_to_bytes(mi))
return
if not sol:
return
for jj in sol:
get_roots(ii - 1, jj)


ns = []
qs = []
with open('output.txt', 'r') as fp:
regex = r'[n] = (\d+)'
output = fp.readlines()
for i in range(len(output)):
if re.findall(regex, output[i]):
ns.append(int(re.findall(regex, output[i])[0]))
qs.append(ns[i] // ps[i])
assert False not in [ps[i] * qs[i] == ns[i] for i in range(len(ns))]

get_roots(len(ns) - 1, c)

image-20220424164955140

最后提一个细节,关于python的for循环

对于下面这段代码的运行结果,注意一下,和c不同,在for循环内容更改出现在for语句这一行的变量,其对循环均没有影响

1
2
3
4
5
6
7
8
9
10
11
12
13
14
tot = 0
t = 100
for i in range(t):
i -= 1
tot += 1
print(f'times = {tot}')
tot = 0
t = 100
for i in range(t):
t += 1
tot += 1
print(f'times = {tot}')
# times = 100
# times = 100

CVE OF RSA

题目关键代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def special_rsa(self):
kbits = 37
abit = 62
M = 962947420735983927056946215901134429196419130606213075415963491270
while True:
k = getRandomNBitInteger(kbits)
a = getRandomNBitInteger(abit)
p = k * M + pow(0x10001, a, M)
if isPrime(p):
break
while True:
l = getRandomNBitInteger(kbits)
b = getRandomNBitInteger(abit)
q = l * M + pow(0x10001, b, M)
if isPrime(q):
break
n = p * q
self.send(b'n = ' + str(n).encode())
flag = open('flag', 'rb').read()
m = bytes_to_long(flag)
c = pow(m, 0x10001, n)
self.send(b'c = ' + str(c).encode())
self.request.close()

p和q由如下方式产生,M可以被完全分解
$$
p=k\times M+65537^a\ mod\ M\notag
$$
17年的ROCA(Return of Coppersmith’s attack)漏洞。简单转述一下就是,一些硬件采用以上方法快速产生RSA的私钥,这样产生的公钥$n$会带有一个指纹,但由于$M$是光滑数,这个指纹可以很快被攻击者确定,从而分解$n$

有个仓库总结了很多密码的攻击,其中就有ROCA,https://github.com/jvdsn/crypto-attacks.git

其中在roca.py文件最后添加下面这段代码

1
2
3
4
5
6
7
8
# Some logging so we can see what's happening.
logging.basicConfig(level=logging.DEBUG)

M = 962947420735983927056946215901134429196419130606213075415963491270
N = 14481363580917358871472996410471767154481047067466167591298208947805462002275531552979475988627964256677709787930755013972295770123571982960720640872341517
p_, q_ = factorize(N, M, 5, 6)

print(f"Found p = {p_} and q = {q_}")

参数根据论文,The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli,n是512位的,则m和t分别取5和6

image-20220424135657852

image-20220424135416087

然后用sage运行

1
$ sage -python attacks/factorization/roca.py

同时跑了五六个n,有一些出的挺快的,但大部分都跑不出来(要跑很久)

image-20220424134747147

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

n = 14481363580917358871472996410471767154481047067466167591298208947805462002275531552979475988627964256677709787930755013972295770123571982960720640872341517
c = 3679892564888936950542940140902963743841717939818025696558626052971555790204073416047068709668040686939721666022034628127241497612925260505783618939964139

p = 111425929610175462966231922510304239063491575573222700849341403103622849511679
q = 129964036482177256444505240482938730532498372430648951070700710194345995195123
d = invert(0x10001, n - p - q + 1)
m = pow(c, d, n)
print(long_to_bytes(m))
# flag{e28e6991-080d-4587-900d-db3c47139453}

Reference

  1. CVE-2017-15361
  2. The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli