Harry's Blog

温故知新

0%

2022ACTF·密码复现

发表于 更新于   阅读次数： Valine：
本文字数： 7.8k 阅读时长 ≈ 7 分钟
如题

前言

跟最后一门高数考试撞了，考完后全力打了半天，没出

impossible RSA

题目

  • server.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
  • public.pem
  • flag

题解

25号在预习高数，简单看了下题目，观察到$q = inv(e, p)$,以为考察的是$e=inv(q, p)$,便就放那了

26号考完时，Mu_chen师傅已经出了（师傅🐮），便也没再花时间在这题上

赛后发现我的思路是错的，题还是做少了，没有题感

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
import gmpy2
import libnum

# 读取密文c
with open('flag', 'rb') as f:
    c = libnum.s2n(f.read())

n = 15987576139341888788648863000534417640300610310400667285095951525208145689364599119023071414036901060746667790322978452082156680245315967027826237720608915093109552001033660867808508307569531484090109429319369422352192782126107818889717133951923616077943884651989622345435505428708807799081267551724239052569147921746342232280621533501263115148844736900422712305937266228809533549134349607212400851092005281865296850991469375578815615235030857047620950536534729591359236290249610371406300791107442098796128895918697534590865459421439398361818591924211607651747970679849262467894774012617335352887745475509155575074809
e = 65537

# e*q = kp+1
# n*e = p*q*e = p*(kp+1)
# k确实大不了

for k in range(1, 9999999):
    print(k)
    p = gmpy2.iroot((n*e)//k, 2)
    if n % p[0] == 0:  # 不需要也不能判断是否整除
        p = p[0]
        break

q = n // p
phi = (p-1)*(q-1)
d = int(gmpy2.invert(e, phi))
m = int(pow(c, d,n))
print(libnum.n2s(m))
# b'ACTF{F1nD1nG_5pEcia1_n_i5_nOt_eA5y}'

不再用LaTex数学公式赘述一遍了，代码、解题思路很清晰

主要还是要归纳下解题思路

总结

这大抵是CTF赛事中Crypto里一种常见的手法

  • 遍历较小的值，近似求解

    题做少了，这也能卡住🤕

  • gmpy2.iroot()

    居然会给出近似结果

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


def leak(a, b):
    # 可求出p、q、phi、d
    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)  # a**4
    q = pow(b, 4)  # b**4
    rp = randrange(0, pow(2, 24))
    rq = randrange(0, pow(2, 24))
    pp = next_prime(p + rp)  # p + rp + p_
    qq = next_prime(q + rq)  # q + rq + q_
    if pp % pow(2, 4) == (pp - p) % pow(2, 4) and qq % pow(2, 4) == (qq - q) % pow(2, 4):  # a、b是偶数
        # p % 16 = 0, a^4 mod 2^4 = 0, a = 2*k
        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=======
n_ = 122146249659110799196678177080657779971
tmp = 90846368443479079691227824315092288065
'''

题解

先聚焦一下，题目生成密钥的过程

  • $a、b∈ [1, 2^{256}]$

  • $p = a^4; q = b^4$

  • $rp、rq∈ [1, 2^{24}]$

  • $pp = next\_prime(p + rp)$

    $qq = next\_prime(q + rq)$

  • $n = pp * qq$

  • $rp = pp - p$

    $rq = q - q$

    注意：这里的rp、rq都放大了，不过还是在$2^{24}$范围内

然后leak函数泄漏的内容如下：

  • $(Prime)p1、q1 ∈ [1, 2^{64}]$
  • $n1 = p1*q1$
  • tmp = (pow(rp, e) + pow(rq, e) + 0xdeadbeef) % n1

扎扎实实看了半天，啥也不会🤧

  • 直接用small_roots()

    报错，幂为65537的运算溢出了

  • 直接在范围$2^{24}$内爆破

    巨慢无比，不可能得到

看题解后，学习之

先不管有没有用、怎么用，最好先看看如何从leak里获得rp、rq

遍历rp、rq速度太慢，看wp里用的是：遍历rp，用rp来表达rq，再校验rq的比特位

学到！（还是有疑惑的，为什么满足比特位的只有这么一个值

  • rp、rq爆破

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    from gmpy2 import *
    from Crypto.Util.number import *

    n_ = 122146249659110799196678177080657779971
    tmp = 90846368443479079691227824315092288065

    p = 8949458376079230661
    q = 13648451618657980711
    e = 65537
    phi = (p-1)*(q-1)
    d = int(invert(e, phi))

    for rp in range(1, pow(2, 24)):
        print(rp)
        rp_e = pow(rp, e, n_)
        # print((pow(a, e) + pow(b, e) + 0xdeadbeef) % n)
        rq_e = (tmp - rp_e - 0xdeadbeef) % n_
        # rq_e = gmpy2.iroot() 哒咩！用d
        rq = int(pow(rq_e, d, n_))
        if len(str(rq)[2:]) <= 24:
            print('rp', rp)  # 405771
            print('rq', rq)  # 11974933
            if (pow(rp, e) + pow(rq, e) + 0xdeadbeef) % n_ == tmp:
                break

or

中间相遇攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from tqdm import tqdm

n0 = 122146249659110799196678177080657779971
c = (90846368443479079691227824315092288065-0xdeadbeef)%n0
e = 65537

dic = {}
for i in tqdm(range(1,2**24)):
    tmp =(c-pow(i,e,n0))%n0
    dic[tmp]=i

for i in tqdm(range(2**24)):
    t = pow(i,e,n0)
    if t in dic.keys():
        print(i,dic[t])

接下来，拿到rp、rq后，再观察n的构成

$pp = p+rp=a^4+rp$, $qq = q+rq=b^4+rq$

$n = pp•qq = (p•q+rq•p+rp•q+rp•rq) = (ab)^4+rq•a^4+rp•b^4+rp•rq$

由于a、b与rp、rq的巨大大小差距，对其开开四次方，可得到ab

$\sqrt[4]{n} = ab$, 对之再四次方，即可得到$pq = (ab)^4$

于是$rq•a^4+rp•b^4 = rq•p+rp•q=n - (ab)^4 - rp•rq$

一个式子解二元方程，是难题，计算机最好解的是一元方程

于是我们转化成一元，方法是两边同时乘q（p也行）

$rq•p•q+rp•q^2 = rq•n+rp•q^2=(n - (ab)^4 - rp•rq)•q$

上式中只有一个未知量q，解出来后再代回来就得到p了

于是，$pp=p+rp, qq=q+rq$, 此题结束

总代码如下

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
# sage
from gmpy2 import *
import libnum

n_ = 122146249659110799196678177080657779971
tmp = 90846368443479079691227824315092288065

p = 8949458376079230661
q = 13648451618657980711
e = 65537
phi1 = (p-1)*(q-1)
d1 = int(invert(e, phi1))

for rp in range(1, pow(2, 24)):
    print(rp)
    rp_e = pow(rp, e, n_)
    # print((pow(a, e) + pow(b, e) + 0xdeadbeef) % n)
    rq_e = (tmp - rp_e - 0xdeadbeef) % n_
    # rq_e = gmpy2.iroot() 哒咩！用d
    rq = int(pow(rq_e, d1, n_))
    if len(str(rq)[2:]) <= 24:
        rp = int(rp)
        rq = int(rq)
        print('rp =', rp)  # 405771
        print('rq =', rq)  # 11974933
        if (pow(rp, e) + pow(rq, e) + 0xdeadbeef) % n_ == tmp:
            break

n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840
pq = int((iroot(n, 4)[0])**4)

tmp1 = n-pq-rp*rq
var('q')  # 申明变量
q = int(str(solve([rq*pq+rp*(q**2)==tmp1*q], [q])[0]).split('q ==')[-1])  # 求解
p = (tmp1-rp*q)//rq
pp = p+rp
qq = q+rq
phi = (pp-1)*(qq-1)
d = int(invert(e, phi))
m = int(pow(c,d,n))
print(libnum.n2s(m))
# ACTF{lsb_attack_in_RSA|a32d7f}

总结

  • 手法1：遍历一变量，表达并验证另一变量
  • 手法2：根据数据大小特性，开方近似求解