2022 川渝网安比赛_初赛Crypto复现

2022 川渝网安比赛_初赛Crypto复现

middlersa1

keywords: dp低位泄露

$Problem$

from Crypto.Util.number import *

FLAG = b'xxx'

p = getPrime(512)
q = getPrime(512)
e = 0x10001
d = inverse(e, (p-1)*(q-1))
dp = d % (p-1)

print('dp:', dp&(2**(512-160)-1))
print('N:', p*q)
print('c:', pow(bytes_to_long(FLAG), e, p*q))

'''
dp: 1642122247947767590084047512154856959705749371720710428047250478126321193705946117104552307567185209952017
N: 53290208062987048378703574235428685467319210471478014757229530639473548433668122104609082311237893278140109351209752453324855439700478949142631006593125874482133364050198292529339327668306943207846561273907830779959709641714284066463679953568692820076085446240980505949826504849495848235048490118010959579651
c: 12164583901228226723569831803555747425419794714331207509347997795520206866173813478558747259319024376651968008838562856265966903471803669392265118265704723742518812401306445616633449971845569756343283456918105040589961351125414282181230864299705837250020888494290318050869813023592249838047791552928679622761
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

$Analysis$

dp低位泄露对比d的低位泄露的攻击方式即可

d的低位泄露，Coppersmith 攻击 (ruanx.net)

这里dp低位泄露即是
KaTeX parse error: Expected 'EOF', got '&' at position 2: &̲e\cdot d \equiv…
其中，$k$的大小在$(1,e+1)$之间；数学推导很简单，关键是如何实现在模$2^{161}$的意义爆破求解$p_{low}$，并且通过coppersmith定理来求解完整$p$

首先在模的意义求解同余式，使用

p = var('p')
solve_mod([e * dp_low == 1 + k * (p_low - 1)], 2^161)
1
2

该sagemath自带的函数会返回满足同余式的解$p$（且是在模$2^{161}$意义下的解）

将遍历$k$的过程中得到的每个$p_{low}$，尝试代入small_roots进行恢复完整的$p$，以n % p == 0作为判断条件

使用coppersmith时，构造$k^{\prime }\cdot 2^{161}+p_{low}$进行求解，同时考虑使用另外一种传参方式small_roots(beta, epsilon)，此时该函数求解的意义是
$$k^{\prime }\le \frac{1}{2}{n}^{{\beta }^2-ϵ}$$
通过传入适当的$\beta$和$ϵ$，使得构造式有解

$Solution1$

from Crypto.Util.number import*
import gmpy2
from tqdm import tqdm

def get_p(p_low, mod):
    F.<z> = PolynomialRing(Zmod(N))
    f = mod * z + p_low
    f = f.monic()
    res = f.small_roots(beta=0.44, epsilon= 1/28)

    if len(res) > 0:
        return 1, res[0]
    return 0, 0

dp_low = 1642122247947767590084047512154856959705749371720710428047250478126321193705946117104552307567185209952017
N = 53290208062987048378703574235428685467319210471478014757229530639473548433668122104609082311237893278140109351209752453324855439700478949142631006593125874482133364050198292529339327668306943207846561273907830779959709641714284066463679953568692820076085446240980505949826504849495848235048490118010959579651
c =  12164583901228226723569831803555747425419794714331207509347997795520206866173813478558747259319024376651968008838562856265966903471803669392265118265704723742518812401306445616633449971845569756343283456918105040589961351125414282181230864299705837250020888494290318050869813023592249838047791552928679622761
e = 0x10001
mod = 2^351

tag = 0
for k in tqdm(range(1, e + 1)):
    p = var('p')
    p_low = solve_mod([e * dp_low == 1 + k * (p - 1)], mod)
    if len(p_low) != 0:
        # print(p_low)
        for i in range(len(p_low)):
            result = get_p(int(p_low[i][0]), mod)
            if result[0]:
                p = int(mod * result[1] + int(p_low[i][0]))
                print(p)
                tag = 1
                break
    if tag == 1:
        break
q = N // p
phi = (p-1) * (q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, N)
print(long_to_bytes(m).decode())
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

求解没有问题，但是因为遍历每个$k$时涉及的计算量比较多，会很慢；所以可以考虑引入进程池来使每个核都来跑这个脚本

$Solution2$

# type:ignore
from multiprocessing import Pool
from Crypto.Util.number import *
import gmpy2
from tqdm import tqdm

def get_p(p_low, mod):
    F.<z> = PolynomialRing(Zmod(N))
    f = mod * z + p_low
    f = f.monic()
    res = f.small_roots(beta=0.44, epsilon= 1/28)

    if len(res) > 0:
        return 1, res[0]
    return 0, 0

def get_p_low(k):
    print("Now is: %d" %k)
    p = var('p')
    p_low = solve_mod([e * dp_low == 1 + k * (p - 1)], mod)
    if len(p_low) != 0:
        for i in range(len(p_low)):
            result = get_p(int(p_low[i][0]), mod)
            if result[0]:
                p = int(mod * result[1] + int(p_low[i][0]))
                print(p)
                return p 



if __name__ == "__main__":
    dp_low = 1642122247947767590084047512154856959705749371720710428047250478126321193705946117104552307567185209952017
    N = 53290208062987048378703574235428685467319210471478014757229530639473548433668122104609082311237893278140109351209752453324855439700478949142631006593125874482133364050198292529339327668306943207846561273907830779959709641714284066463679953568692820076085446240980505949826504849495848235048490118010959579651
    c =  12164583901228226723569831803555747425419794714331207509347997795520206866173813478558747259319024376651968008838562856265966903471803669392265118265704723742518812401306445616633449971845569756343283456918105040589961351125414282181230864299705837250020888494290318050869813023592249838047791552928679622761
    e = 0x10001
    mod = 2^351

    pool = Pool()

    result = pool.map(get_p_low, range(1, e + 1))
    for i in result:
        if i != None:
            p = i
            break
    pool.close()
    pool.terminate()
    print(p)
    assert type(p) == int
    q = N // p
    phi = (p-1) * (q-1)
    d = gmpy2.invert(e, phi)
    m = pow(c, d, N)
    print(long_to_bytes(m).decode())
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

soeasy_rsa

keywords: 两个相差很大的数的平方和

$Problem$

from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
p = getPrime(1024)
q = getPrime(200)

a = p**2 + q**2
n = p * q
e1 = getPrime(16)
e2 = next_prime(e1)
m = bytes_to_long(flag)
c1 = powmod(m,e1,n)
c2 = powmod(m**3,e2,3*n)

print('a =', a)
print('c1 =', c1)
print('c2 =', c2)

'''
a = 23804021940078676408342301332036892900004728136480076479530219752065125327318821647722459216095770264965388973551323635311313178838670860487788476788686756050157264721772586844596306406576857878507037529439070526513923394974678433717664180257965624133033383511215139076867891548866207158515487182813656668091870588002638518245252590786003914393372830494390833657940568569618842104970029260363695053572749495893999945220493935637334868029460448282514843103145795102173534495304156971490358608124680851055950154432367509652612855903019752959349069234185596982394068554146096092741880878895682860091022727772496856721290
c1 = 75949211970645260477840809230795170598275394663655585446502049744151634977806266592064437936389888280642329073167371358021391264606028082728274944584341647324957857195053188220196244561623697425292916511744852569537275299008074069250282222480373555169325242455879869868679935977005580843853804599341730525546675515324718058489296906319060874296111833437083796029771812
c2 = 77907941155376849046818020584594846942386293571953448410760364023962818506838837521412252753647936913064982141652362831680077554268552176063108954360620095019160785058740575077744544616439692739387312706279917959252426192939648962492950940347253817951644007140862267776520611944302335981903665518644840891111449931544355548130487697653008605945892957382219567188182572
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

$Analysis$

将已知量$p^2+q^2$直接开方即可得到较大的数$p$，因为开方会使得含有较小的数$q^2$的部分丢失，剩余的正好使$p^2$

接着爆破$e$即可

$Solution$

from Crypto.Util.number import *
from tqdm import tqdm
import gmpy2

a = 23804021940078676408342301332036892900004728136480076479530219752065125327318821647722459216095770264965388973551323635311313178838670860487788476788686756050157264721772586844596306406576857878507037529439070526513923394974678433717664180257965624133033383511215139076867891548866207158515487182813656668091870588002638518245252590786003914393372830494390833657940568569618842104970029260363695053572749495893999945220493935637334868029460448282514843103145795102173534495304156971490358608124680851055950154432367509652612855903019752959349069234185596982394068554146096092741880878895682860091022727772496856721290
c1 = 75949211970645260477840809230795170598275394663655585446502049744151634977806266592064437936389888280642329073167371358021391264606028082728274944584341647324957857195053188220196244561623697425292916511744852569537275299008074069250282222480373555169325242455879869868679935977005580843853804599341730525546675515324718058489296906319060874296111833437083796029771812
c2 = 77907941155376849046818020584594846942386293571953448410760364023962818506838837521412252753647936913064982141652362831680077554268552176063108954360620095019160785058740575077744544616439692739387312706279917959252426192939648962492950940347253817951644007140862267776520611944302335981903665518644840891111449931544355548130487697653008605945892957382219567188182572

p = gmpy2.iroot(a, 2)[0]
q = gmpy2.iroot(a - p ** 2, 2)[0]
n = p * q
fai_n = (p - 1) * (q - 1)
for e in tqdm(range(2**16)):
    try:
        d = gmpy2.invert(e, fai_n)
        m1 = pow(c1, d, n)
        try:
            print(long_to_bytes(m1).decode())
            break
        except:
            continue
    except:
        continue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23