潜心的博客

复现ACTF2022的一道Crypto题-RSA LEAK

2022-7-20 CryptoRSA中途相遇攻击ACTF2022

# RSA LEAK

We leak something for you~

# 题目

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
'''
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

# 官方Writeup

ACTF-2022/writeup_en.md at main ·team-s2/ACTF-2022 (github.com) (opens new window)

Firstly, using meet-in-the-middle attack(just brute force), we can easily get the rq and rq. Here, rq and rq are about and we also know . Based on this fact, we have . Finally, using these two equation, we can solve the and . Knowing the and -> get flag~

大致意思：使用中途相遇攻击得到rp和rq。因为 rp 和 rq 大约为 ，且 ，所以可以得到 。最后，通过这两个方程求解出 和 ，在拿到 和 之后便能求出flag了。

# 中途相遇攻击

中途相遇攻击（meet-in-the-middle attack） (opens new window)可成倍减少解密已被多个密钥加密的文本所进行的蛮力排列操作。

假设ENC是加密函式，DEC是解密函式，也就是 ，而 ， 为两次加密用的密钥，则可以推导出：

当攻击者已知明文P与密文C时，攻击者可以穷举所有 的组合，将产生出来的第一层密文 ，用大量空间储存下来。

再穷举所有 的组合，将 的值与前面储存下来的结果比对，进而得出正确的 ， 。

这使得攻击者计算的量从 ， 各自的可能组合数相乘，变成相加。

# 复现

中途相遇攻击求出 和 

from tqdm import tqdm

n = 122146249659110799196678177080657779971
c = 90846368443479079691227824315092288065
e = 65537

c = c - (0xdeadbeef%n)
dic = {}
for rp in tqdm(range(2**24)):
    rq = c - pow(rp, e, n)
    dic[rq] = rp

for rq in tqdm(range(2**24)):
    if pow(rq, e, n) in dic.keys():
        print(f"rp = {dic[pow(rq,e,n)]}")
        print(f"rq = {rq}")
        break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
rp = 405771
rq = 11974933
1
2

已知 和 相对于 和 来说是非常大的，所以 ，记 ，则

对于 ，将式子展开可得

两边同时乘以 ，得

整理可得

通过求根公式求出 

import gmpy2
from Crypto.Util.number import *

n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
flag = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840

rp = 405771
rq = 11974933

t = pow(gmpy2.iroot(n, 4)[0], 4)
for k1 in range(1000):
    for k2 in range(1000):
        a = rq + k2
        b = t + rp*rq + rp*k2 + k1*rq + k1*k2 - n
        c = (rp + k1) * t
        delta = pow(b,2) - 4*a*c
        roots = gmpy2.iroot(delta, 2)
        if roots[1]:
            p = (-b + roots[0])//(2*a)
            pp = p+rp+k1
            if isPrime(pp):
                print(f"{k1 = }")
                print(f"{k2 = }")
                qq = n//pp
                phi = (pp-1)*(qq-1)
                d = gmpy2.invert(e, phi)
                m = pow(flag, d, n)
                print(long_to_bytes(int(m)))
                exit()
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
k1 = 0
k2 = 0
b'ACTF{lsb_attack_in_RSA|a32d7f}'
1
2
3

复现CISCN2022-华南分区赛的一道Crypto题-BlindSignatureRSA