ACTF2022

impossible RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from Crypto.PublicKey import RSA

e = 65537
flag = b'ACTF{...}'

while True:
    p = getPrime(1024)
    q = inverse(e, p)
    if not isPrime(q):
        continue
    n = p * q;
    public = RSA.construct((n, e))
    with open("public.pem", "wb") as file:
        file.write(public.exportKey('PEM'))
    with open("flag", "wb") as file:
        file.write(long_to_bytes(pow(bytes_to_long(flag), e, n)))
    break

$$
e*q = 1 \ mod\ p\\
==>e*q = 1 + k*p(可以知道k的值近似e)\\
==>e*q^2-q-k*n=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
from Crypto.Util.number import *
import gmpy2
import rsa
from z3 import *

with open("public.pem",'rb') as f:
    keydata = f.read()
    pubckey = rsa.PublicKey.load_pkcs1_openssl_pem(keydata)
    pubckey.n
    pubckey.e

n = pubckey.n
e = pubckey.e
print(f'n = {n}')
print(f'e = {e}')

with open("flag", "rb") as f:
    c = bytes_to_long(f.read())

print(f'c = {c}')

for k in range(1,e):
    print(f"k = {k}")
    deta = 1 + 4 * k * e * n
    if gmpy2.iroot(deta,2)[0] >= 0:
        #p = int((gmpy2.iroot(deta,2)[0]+1)/(2*e))
        p = int(gmpy2.iroot(deta,2)[0]+1)//(2*e)#前面需要int化，淦！
        q = n//p
        if p*q == n:
            phi = (p - 1) * (q - 1)
            d = gmpy2.invert(e, phi)
            m = pow(c, d, n)
            flag = long_to_bytes(m)
            if b'ACTF' in flag:
                print(flag)
                break

RSA LEAK

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
from sage.all import *
from secret import flag
from Crypto.Util.number import bytes_to_long


def leak(a, b):
    p = random_prime(pow(2, 64))
    q = random_prime(pow(2, 64))
    n = p*q
    e = 65537
    print(n)
    print((pow(a, e) + pow(b, e) + 0xdeadbeef) % n)


def gen_key():
    a = randrange(0, pow(2,256))
    b = randrange(0, pow(2,256))
    p = pow(a, 4)
    q = pow(b, 4)
    rp = randrange(0, pow(2,24))
    rq = randrange(0, pow(2,24))
    pp = next_prime(p+rp)
    qq = next_prime(q+rq)
    if pp % pow(2, 4) == (pp-p) % pow(2, 4) and qq % pow(2, 4) == (qq-q) % pow(2, 4):
        n = pp*qq
        rp = pp-p
        rq = qq-q
        return n, rp, rq
    
n, rp, rq = gen_key()
e = 65537
c = pow(bytes_to_long(flag), e, n)
print("n =", n)
print("e =", e)
print("c =", c)
print("=======leak=======")
leak(rp, rq)

'''
n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840
=======leak=======
122146249659110799196678177080657779971
90846368443479079691227824315092288065
'''

法一

论文：8.pdf (upm.edu.my)

通过上述论文可知，我们要先求出rp(pp-p),rq(qq-q)。

令

1
2
3
leak_out = 90846368443479079691227824315092288065
leak_n = 122146249659110799196678177080657779971
tmp = 0xdeadbeef

该题中leak_n很小易分解出leak_p,leak_q，且rp,rq的范围在[0,1<<24]左右，故可以对rp进行枚举（枚举范围可以减半，即rp,rq的值对调），有等式$rq^e = leak\_out - tmp - rq^e\quad (mod\quad leak\_n)$，然后解密得到rq，通过以下条件筛选出rp,rq

1
2
1)rq in [0,1<<24)
2)rp*rq ≡ n (mod 16)

然后再根据论文中的步骤写出算法：

vCJKgI.png

代码：

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
from Crypto.Util.number import *
from gmpy2 import iroot,invert
from tqdm import tqdm
from math import ceil,floor

n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840

leak_n = 122146249659110799196678177080657779971
leak_p = 8949458376079230661
leak_q = 13648451618657980711
leak_phi = (leak_p - 1)*(leak_q - 1)
leak_d = invert(e,leak_phi)
leak_out = 90846368443479079691227824315092288065
leak_out -= 0xdeadbeef
m = 4
'''
for rp in tqdm(range(1,16777216)):
    rpe = pow(rp,e,leak_n)
    rq = pow(leak_out-rpe,leak_d,leak_n)
    #if rq.bit_length() in range(23,25):
    if rq.bit_length() <= 24 and n%16 == (rp*rq)%16:
        print(rp,rq)
        break
'''
#rp, rq = 405771, 11974933
rq, rp = 405771, 11974933
start = ceil(iroot(rp*rq,2)[0])
edge = floor(rq/2+2**(m/2-1)*rp+1)
print(f'start = {start}')
print(f'edge = {edge}')

for i in tqdm(range(start,edge)):
    sigma = (int(iroot(n,2)[0]) - i)**2#整数化
    z = (n - rp*rq)%sigma
    delta = z**2 - 4*sigma*rp*rq
    if delta < 0:
        continue
    if iroot(delta,2)[1]:
        x1, x2 = (z+int(iroot(delta,2)[0]))//2, (z-int(iroot(delta,2)[0]))//2#整数化
        print(f'x1 = {x1}')
        assert x1**2 - z*x1 + sigma*rp*rq == 0
        maybe_p = int(n//(x1//rp+rq))
        if n%maybe_p == 0:
            p = maybe_p
            q = n//p
            print(f'p = {p}\nq = {q}')
            break
        print(f'x2 = {x2}')
        assert x2**2 - z*x2 + sigma*rp*rq == 0
        maybe_q = int(n//(x2//rq+rp))
        if n%maybe_q == 0:
            q = maybe_q
            p = n//q
            print(f'p = {p}\nq = {q}')
            break

phi = (p-1)*(q-1)
d = invert(e,phi)
flag = long_to_bytes(pow(c,d,n))
print(flag)

法二

rp,rq的求法同上。（rp = pp - p，rq = qq-q）
$$
\begin{cases}
pp = a^4+rp
\\qq = b^4+rq
\end{cases}
$$
比较各数值大小

1
2
3
a,b在256bit左右，a^4,b^4在1024bit左右
而rp,rq在24bit左右
故n=pp*qq=(a^4+rp)*(b^4+rq)≈a^4*b^4

于是可以联立方程
$$
\begin{cases}
n = (a^4+rp)*(b^4+rq)
\\n^{1/4} = a*b
\end{cases}
$$
解此方程可得到a,b，继而求出p,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
from Crypto.Util.number import *
from gmpy2 import iroot,invert
from tqdm import tqdm
from z3 import *

n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840
'''
for i in tqdm(range(1,16777216)):
    rpe = pow(rp,e,leak_n)
    rq = pow(leak_out-rpe,leak_d,leak_n)
    if rq.bit_length() <= 24 and n%16 == (rp*rq)%16:
        print(rp,rq)
        break
'''
rp, rq = 405771, 11974933

a,b = Ints('a b')
solver = Solver()
#solver.add(n == (a**4+rp)*(b**4+rq))
#solver.add(int(iroot(n,4)[0]) == a*b)#int化
solver.add( n == (a**4+rp)*(b**4+rq), int(iroot(n,4)[0]) == a*b )
if solver.check() == sat:
    result = solver.model()

a_, b_ = int(str(result[a])), int(str(result[b]))#必须先整数化，否则后面的p,q是式子
print(f'a = {a_},b = {b_}')
p = a_**4+rp
q = b_**4+rq
print(f'p = {p}\nq = {q}')

assert p*q == n
d = invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

参考：

ACTF WriteUp By Nu1L

8.pdf (upm.edu.my)

ACTF 2022 writeup - ふるつき (hatenablog.com)

Crypto
#RSA #Crypto
ACTF2022
http://example.com/2022/06/26/CTF/ACTF2022/
作者
gla2xy
发布于
2022年6月26日
许可协议