20220709-蓝帽杯-CryptoSecWriteUp

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

 

corrupted_key

  • 考点：RSA 已知cf+dq低位泄漏

  • 题目

    脚本

    1
    2
    3
    4
    5
    6
    7
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import PKCS1_OAEP
    from secret import flag

    key = RSA.generate(1024)
    open("flag.enc",'wb').write(PKCS1_OAEP.new(key.publickey()).encrypt(flag))
    open('priv.pem','wb').write(key.exportKey('PEM'))

    corrupted key

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    -----BEGIN RSA PRIVATE KEY-----
    MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
    UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
    dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB








    yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
    zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA==
    -----END RSA PRIVATE KEY-----

通过学习PEM文件格式，https://www.jianshu.com/p/c93a993f8997，可以获得模数、指数、低120的dq还有cf

我所能想到的是将下面这个等式模$q-1$，在这个多项式下用CopperSmith
$$
ed=k\varphi+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
from Crypto.Util.number import *

c = 96458723724899437870554342796876171017896652413964521193266438981853945238446913579867464909353925601873532290626111170073532116639383463734148270579305067733147411306325252107181823453497914478588342362177625026365513002442585949837516090367171824895036711246039928723021679235071368954348296729327873680822
c1 = ''.join('''MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB'''.split('\n'))
c2 = ''.join('''yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA=='''.split('\n'))
n = b'''\x00\xd7\x15%\x06\xaa\x9c\xec\x05\xe53]kF\xf5I\x14\x07\xc3\x19\x9f\xd5\x10\x91\xf1\xf6\x03\r7b\xb9\xe0?I\xc9\xdc\xdc\x07PT\xe0\xcc\x14\x8b\x97KA\x85K\xd9;N\xe1j*\x87n\xe6 \x05\xe8\x0e\xf8\x06\xb7\xaa;d\xb1\xbf\x9b\x1f\xa7s\xe3S\xd0\xcd\xb9\xff\x97\x83\xdd\xd5\xf5\xe6t\x99\xad\x10\xf3a\xe98\xd0\x0b\x82\xa6\xa4\xc4*\x055\xc5\xe7g!y\x8e\x86\xb4\\\xd4\xb8\xd0;\r~u\xc2\xbe\x87f\xa1\xe8C\xbd\xc6A'''
n = bytes_to_long(n)
e = 0x10001
cf = b'''\x00\xe3\x01l\xb3`\x9c\x1dd<\x16t9\xc3\xb98\xb8\x81\xf4#\x7f$\x86\r;\x1c\xb8Zbm\\\xcdG&\x96N\x0f\x82p\xd6\xc4\xdf\x9e\xbf\xeb\xccS\x8eN\xe5\xe1\xa7\xb76\x8e\xdeQ\xecj\xe9\x17\xf7\x8e\xb5\x98'''
cf = bytes_to_long(cf)
dp_bar = b'''\xc9\x0b\xce\xcf\x1c\xba\xb35\x85\x85\xe8\xa0A\xd1\xb1'''
dp_bar = bytes_to_long(dp_bar)

def coppersmith(k):
    F.<x> = PolynomialRing(Zmod(n))
    f = e * (x * 2 ^ 120 + dp_bar) + k - 1
    f = f.monic()
    x0 = f.small_roots(X=2^392)
    return x0

from tqdm import tqdm
for k in tqdm(range(e, -1, -1)):
    x0 = coppersmith(k)
    if len(x0) != 0:
        print(x0)
        break

解法一

泄漏$d$低位，再CopperSmith构造等式

别人的做法，首先根据$(1)$两边模$q-1$再化成等式可得
$$
ed_q=k(q-1)+1
$$
爆破$k$可以求出低位的$q$

现在题目变成泄漏$q$的低120位，换做往常还是不能做，泄漏的位数太少了，但这里有$cf$，有一个比较变态的做法
$$
cf\cdot q^2-q\equiv 0\ (mod\ p)\notag
$$
看似上面这个模等于啥也没干，但是却可以用CopperSmith把$q$解出来，不知道为啥，但也是个新颖的思路

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
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import *
from gmpy2 import *
from tqdm import tqdm

n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
cf = 0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598
d_low = 0xc90bcecf1cbab3358585e8a041d1b1
q_low = []
for i in tqdm(range(1, e, 2)):
    try:
        q0 = invert(i, 2 ** 120) * (e * d_low + i - 1) % 2 ^ 120
        q_low.append(q0)
    except:
        continue
PR.<x> = Zmod(n)[]
roots = []
for i in tqdm(range(len(q_low))):
    f = cf * (2^120*x + int(q_low[i])) ^ 2 - (2^120*x + int(q_low[i]))
    root = f.monic().small_roots(X = 2^(512-120))
    if root:
        q = 2^120*int(root[0]) + int(q_low[i])
        p = n // q
        assert p * q == n
        d = inverse(e, (p - 1) * (q - 1))
            rsa = RSA.construct((int(n), int(e), int(d), int(p), int(q)))
        # c = bytes_to_long(open('flag.enc', 'rb').read())
        c = 96458723724899437870554342796876171017896652413964521193266438981853945238446913579867464909353925601873532290626111170073532116639383463734148270579305067733147411306325252107181823453497914478588342362177625026365513002442585949837516090367171824895036711246039928723021679235071368954348296729327873680822
        c = long_to_bytes(c)
        print(PKCS1_OAEP.new(rsa).decrypt(c))
# c = 96458723724899437870554342796876171017896652413964521193266438981853945238446913579867464909353925601873532290626111170073532116639383463734148270579305067733147411306325252107181823453497914478588342362177625026365513002442585949837516090367171824895036711246039928723021679235071368954348296729327873680822
# p = 12112790828812363063315417237469719611888243756064158121348026938824270601623590308149025542977097905953795136774300936003505715307199422663647014200158449
# q = 12469144192094336933187534132907623337514842804208163244218540727384104398951558782195384932941310035462094951428865175221316720981428462265191789302379089
# d = inverse(e, (p - 1) * (q - 1))
# rsa = RSA.construct((n, e, d, p, q))
# print(PKCS1_OAEP.new(rsa).decrypt(open('flag.enc', 'rb').read()))
# flag{f1bf5c44-e2b4-424f-baff-b38b73a82e72}

image-20220711185037329

解法二

官方的正规解法：CopperSmith求出$dq$，再$dp$泄漏攻击

依旧是借助$(1)$，在化成$(2)$后将$kq$单独放到一边，得到
$$
ed_q+k-1=kq\notag
$$
已知$d_q$低位，$k$可以爆破，但是$q$不知道，不能构造一元CopperSmith。所以就想能不能把$q$给干掉，将其替换成已知低位的$kq$，于是就有
$$
cf\cdot q\equiv1\ (mod\ p)\rightarrow cf\cdot q-1\equiv0\ (mod\ p)\rightarrow cf\cdot (kq)^{x+1}-k\cdot (kq)^x\equiv0\ (mod\ n)\notag
$$
把$kq$代入上式可以，令$x=1$，就能得到一个模$n$等式，并且未知数个数为1，已知其低120位，设其高位为$x$，最终列出
$$
t = e\cdot (x+dp_l)-k+1\notag
$$
$$
cf\cdot t^2-k\cdot t\equiv 0\ (mod\ n)\notag
$$

用CopperSmith求解

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
from Crypto.Util.number import *
from exploit.rsa.leakdpFracN import divide_pq
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

c = 96458723724899437870554342796876171017896652413964521193266438981853945238446913579867464909353925601873532290626111170073532116639383463734148270579305067733147411306325252107181823453497914478588342362177625026365513002442585949837516090367171824895036711246039928723021679235071368954348296729327873680822
c1 = ''.join('''MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB'''.split('\n'))
c2 = ''.join('''yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA=='''.split('\n'))
n = b'''\x00\xd7\x15%\x06\xaa\x9c\xec\x05\xe53]kF\xf5I\x14\x07\xc3\x19\x9f\xd5\x10\x91\xf1\xf6\x03\r7b\xb9\xe0?I\xc9\xdc\xdc\x07PT\xe0\xcc\x14\x8b\x97KA\x85K\xd9;N\xe1j*\x87n\xe6 \x05\xe8\x0e\xf8\x06\xb7\xaa;d\xb1\xbf\x9b\x1f\xa7s\xe3S\xd0\xcd\xb9\xff\x97\x83\xdd\xd5\xf5\xe6t\x99\xad\x10\xf3a\xe98\xd0\x0b\x82\xa6\xa4\xc4*\x055\xc5\xe7g!y\x8e\x86\xb4\\\xd4\xb8\xd0;\r~u\xc2\xbe\x87f\xa1\xe8C\xbd\xc6A'''
n = bytes_to_long(n)
e = 0x10001
cf = b'''\x00\xe3\x01l\xb3`\x9c\x1dd<\x16t9\xc3\xb98\xb8\x81\xf4#\x7f$\x86\r;\x1c\xb8Zbm\\\xcdG&\x96N\x0f\x82p\xd6\xc4\xdf\x9e\xbf\xeb\xccS\x8eN\xe5\xe1\xa7\xb76\x8e\xdeQ\xecj\xe9\x17\xf7\x8e\xb5\x98'''
cf = bytes_to_long(cf)
dq_bar = b'''\xc9\x0b\xce\xcf\x1c\xba\xb35\x85\x85\xe8\xa0A\xd1\xb1'''
dq_bar = bytes_to_long(dq_bar)

def coppersmith(k):
    F.<x> = PolynomialRing(Zmod(n))
    tmp = e * (x * 2 ^ 120 + dq_bar) + k - 1
    f = cf * tmp ^ 2 - k * tmp
    f = f.monic()
    x0 = f.small_roots(X=2^392)
    return x0

from tqdm import tqdm
for k in tqdm(range(e, -1, -1)):
    x0 = coppersmith(k)
    if len(x0) != 0:
        dq = int(x0[0] << 120) + dq_bar
        p, q = divide_pq(e, dq, n)
        d = inverse(e, n - p - q + 1)
        key = RSA.construct((int(n), int(e), int(d)))           # must add int()
        print(PKCS1_OAEP.new(key).decrypt(open('flag.enc', 'rb').read()))
        break

image-20220714092634925

另外直接将PKCS1_OAEP写入文件的内容当成$c$是错的

RSA密钥文件格式

手撕PEM，小实验一下

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.PublicKey import RSA
from base64 import *
from Crypto.Util.number import long_to_bytes

key = RSA.generate(1024)
cont = key.exportKey('PEM')
# print(cont.decode())

c = ''.join(''''MIICXAIBAAKBgQDKGq9TTDZq8d8bjHGBvBTLCv+VzlHp6dqSD8j6tOeidSjhBVvw
BCIsHOeISc6A2xVlYh8RDtZwdNt5sYG4r2qExEybnKOSHIRdrAtQtlcMq+Igzz80
uAZ5rrv4GwP86B6KBcMLCQZw2iA9Ut5VO8bsEbx4+qbRklGSeiuD0V+jHQIDAQAB
AoGAEVUD2ic8DM8yAgEjrtY8C5mlh5RfuVQLzDY8VyZygvUnN1JSqx0U99GBbae0
D6A6OoKVWszPSRT3HtLr5rRsdFAAH3JtkxOckD+pl6zYdWjxIrRxI3ZwQMapJV3P
GEI4mt3foYcQewC9e7PmnQuaC7VLCuz75tCVwa8TV6boXWUCQQDc4laKq/IPfbS6
BtcFU0TlI8mBwJGoDLKt+5YB4c3nCYNEjb/8btO1b1i/ldl9qsgrCsXzOsPKg1mk
XrTUCM/rAkEA6jwIUC+kfbM0nk5LdF4u7SWSJ+yJHmmXEwFGIhnQkSTzBoLMkuKd
WIirD1gMYYUhq0OgxyFNVFQITYgeN9afFwJBALWFhB1eBQVaBwXBzT7hGYM9j8ID
4S+7j7OPR82wJagylx/lZdsrsOwv3z1DBoNRsEI/DkI/DtwEacy8z9pYi5UCQFKU
QZYLheFvCZD6J23qOn8O7N04bgsTzNg9bb1d/oL9VNSpznfGfxSUckJhl1PWPM2F
dSxfGEUvrxGueIDVIJcCQGUz3r6/0csCC06aQFZE/y1LvzfmZNEyrTY4pLq2QFif
ZihZ0hFLIF7/8x/s4LH4u9TEJctvc46We31/wL4f1Sk='''.split('\n'))

print(b64decode(c))
n = 141922422162179017903127585740733292572168561849445377008084607260848440837899202013613994221251833956396740748218860865627125387303232010980772920302901970895962267669411141364137560651832837189240644578805960981842828200127571251887961801814486793715132007244098977233800900588064918877074282156319288828701
e = 0x10001
d = 12171007522857319381238253318351994781875551832519536046982694574694017938812266074388236449458713766466807278106098911329167549909820889661040390462523611239298122892357825060171192914736392814191400078975478302074496640294564924161354815518818393075514178864568095461878185396950184140746495040638346091877
p = 11568640743445096899087582701840791920416346538267286644696280445889201611816852678096203713970033443624441112801937495058400134469307102394543137970769899
q = 12267856294404649670607892358949867977588327036687686342888422897170960672423334427787576824476551036688316206161248780078052957870595041033189662792261399
dp = 9507054841699589984147260771102451611300236383386476709493145433185843422940202504492200430703237273703787928243385409903647015308115139856345336601152405
dq = 4325019754981452166553173824763670897694100983912431038229351527215695657969408760761584487076471484851054304337330867505430727552376496072018053295317143
cf = 5300411165607780716414732822919524340053628209205783274101215577479096542425160668007906344942502152526592241185925153869158983775649429578743583673931049
for i in [n, e, d, p, q, dp, dq, cf]:
    print(long_to_bytes(i))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
0\x82\x02\\\x02\x01\x00\x02\x81\x81\x00
	\xca\x1a\xafSL6j\xf1\xdf\x1b\x8cq\x81\xbc\x14\xcb\n\xff\x95\xceQ\xe9\xe9\xda\x92\x0f\xc8\xfa\xb4\xe7\xa2u(\xe1\x05[\xf0\x04",\x1c\xe7\x88I\xce\x80\xdb\x15eb\x1f\x11\x0e\xd6pt\xdby\xb1\x81\xb8\xafj\x84\xc4L\x9b\x9c\xa3\x92\x1c\x84]\xac\x0bP\xb6W\x0c\xab\xe2 \xcf?4\xb8\x06y\xae\xbb\xf8\x1b\x03\xfc\xe8\x1e\x8a\x05\xc3\x0b\t\x06p\xda =R\xdeU;\xc6\xec\x11\xbcx\xfa\xa6\xd1\x92Q\x92z+\x83\xd1_\xa3\x1d

\x02\x03
	\x01\x00\x01

\x02\x81\x80
	\x11U\x03\xda\'<\x0c\xcf2\x02\x01#\xae\xd6<\x0b\x99\xa5\x87\x94_\xb9T\x0b\xcc6<W&r\x82\xf5\'7RR\xab\x1d\x14\xf7\xd1\x81m\xa7\xb4\x0f\xa0::\x82\x95Z\xcc\xcfI\x14\xf7\x1e\xd2\xeb\xe6\xb4ltP\x00\x1frm\x93\x13\x9c\x90?\xa9\x97\xac\xd8uh\xf1"\xb4q#vp@\xc6\xa9%]\xcf\x18B8\x9a\xdd\xdf\xa1\x87\x10{\x00\xbd{\xb3\xe6\x9d\x0b\x9a\x0b\xb5K\n\xec\xfb\xe6\xd0\x95\xc1\xaf\x13W\xa6\xe8]e

\x02A\x00
	\xdc\xe2V\x8a\xab\xf2\x0f}\xb4\xba\x06\xd7\x05SD\xe5#\xc9\x81\xc0\x91\xa8\x0c\xb2\xad\xfb\x96\x01\xe1\xcd\xe7\t\x83D\x8d\xbf\xfcn\xd3\xb5oX\xbf\x95\xd9}\xaa\xc8+\n\xc5\xf3:\xc3\xca\x83Y\xa4^\xb4\xd4\x08\xcf\xeb
	
\x02A\x00
	\xea<\x08P/\xa4}\xb34\x9eNKt^.\xed%\x92\'\xec\x89\x1ei\x97\x13\x01F"\x19\xd0\x91$\xf3\x06\x82\xcc\x92\xe2\x9dX\x88\xab\x0fX\x0ca\x85!\xabC\xa0\xc7!MTT\x08M\x88\x1e7\xd6\x9f\x17

\x02A\x00
	\xb5\x85\x84\x1d^\x05\x05Z\x07\x05\xc1\xcd>\xe1\x19\x83=\x8f\xc2\x03\xe1/\xbb\x8f\xb3\x8fG\xcd\xb0%\xa82\x97\x1f\xe5e\xdb+\xb0\xec/\xdf=C\x06\x83Q\xb0B?\x0eB?\x0e\xdc\x04i\xcc\xbc\xcf\xdaX\x8b\x95
	
\x02@
	R\x94A\x96\x0b\x85\xe1o\t\x90\xfa'm\xea:\x7f\x0e\xec\xdd8n\x0b\x13\xcc\xd8=m\xbd]\xfe\x82\xfdT\xd4\xa9\xcew\xc6\x7f\x14\x94rBa\x97S\xd6<\xcd\x85u,_\x18E/\xaf\x11\xaex\x80\xd5 \x97

\x02@
	e3\xde\xbe\xbf\xd1\xcb\x02\x0bN\x9a@VD\xff-K\xbf7\xe6d\xd12\xad68\xa4\xba\xb6@X\x9ff(Y\xd2\x11K ^\xff\xf3\x1f\xec\xe0\xb1\xf8\xbb\xd4\xc4%\xcbos\x8e\x96{}\x7f\xc0\xbe\x1f\xd5)

Reference

  1. 官方wp

something else

RSA - Corrupted key 1

RSA - Corrupted key 2

RSA - Corrupted key 3

God Like RSA

Plaid CTF 2014

0CTF 2016 Quals – Equation

Corrupted Keys