20220423-DASxFATE-CryptoSecPartWriteUp

Posted on Edited on In , Views: Symbols count in article: 6.4k Reading time ≈ 6 mins.

 

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