0%

2022ACTF·密码复现

前言

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

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:根据数据大小特性,开方近似求解