网鼎杯半决赛

发表于 分类于 阅读次数： Waline： 本文字数： 908 阅读时长 ≈ 3 分钟

网鼎杯半决赛Crypto题解

全场一解嘻嘻，其实题目并不难，套了挺多层

RSA加密分析

task.py

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
# sagemath
import random
from Crypto.Util.number import *

flag = b''

k = 3
d = k/(2*(k+1))
ns = []
pqs = []
es = []

for i in range(3):
    p = getPrime(512)
    q = getPrime(512)
    if p < q:
        tmp = p
        p = q
        q = tmp
    n = p*q
    ns.append(n)
    pqs.append((p,q))

n = min(ns)
x = random.randint(0,int(n^(d/2)))
x = next_prime(x)

for i in range(3):
    p,q = pqs[i][0],pqs[i][1]
    bound1 = int((p-q)/(3*(p+q)) * x * n ^ 0.25)
    bound2 = int((p-q)/(3*(p+q)) * x^2 * n ^ 0.25)
    z = random.randint(bound1,bound2)
    f = (p-1)*(q-1)
    e = inverse(x^2,f) * z % f
    es.append(e)

e = 8462913
c = pow(bytes_to_long(flag),e,ns[0])

print(f'ns={ns}')
print(f'es={es}')
print(f'c={c}')

'''
ns=[58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167, 77621328849675766747673031143217563980503830449890233197117569566535170499356584333526498228802079135043121885950830320777642529199704224484173792215691924850086027618183393165197503325417741686635820334799489140360184827244176669486536901652827052817389390205607840551799799037689580359943641014734459153393, 112244920700186260026594736958318991062998987080230137582151100770199379608284829383065111800934933346946496041561749555085922429662611986339400029890877247514987095240380019377389184545006798594193383230298132838994539491402564579629017309643629910561998268286162916487705908044261914142200286678017692930877]
es=[46762963588977775648213636278524171408894671002158172701955774077187382885695296449518850546775920334764033057745226744111631183010556541467024035131602309988991836959736948179491431343087734419406823467043032520956443072556932946767546576469286010676651317873358203560021064830688914958086524112915123700678, 49605058941818136068558533413619424099600243928109466352604646203354430655695939177245076016870792265350960174089601299549033530643078866868937787258274475767441534991912769995268058506952466739575911255510940326565376471493045685544056383561868628029099619187607579109612157304977780126730283103824111801708, 35433601810279274137096137736120773703247868305827931187532982974242279082633517463016086358856291932337981126992048059591164336008738979183437333221010305682689432537562502148059203087673302900990705589870381203411821061168753251557946997898741497047442934600089950257888693394999451561437497637827070063398]
c=45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729
'''

加密用的是$n_1$，给出下面三个式子
$$
e_1 \equiv x^{-2}\times z_1 \mod phi_1
$$

$$
e_2 \equiv x^{-2}\times z_2 \mod phi_2
$$

$$
e_3 \equiv x^{-2} \times z_3 \mod phi_3
$$

则有
$$
e_1x^2 \equiv z_1 \mod phi_1
$$

$$
e_2x^2 \equiv z_2 \mod phi_2
$$

$$
e_3x^2 \equiv z_3 \mod phi_3
$$

记$phi_i = n_i - y_i$，其中$y_i = p_i + q_i - 1$，那么有：

$$
e_1x^2 = z_1 + k_1(n_1 - y_1)
$$

$$
e_2x^2 = z_2 + k_2(n_2 - y_2)
$$

$$
e_3x^2 = z_3 + k_3(n_3 - y_3)
$$

移项
$$
e_1x^2 - k_1n_1 = z_1 - k_1y_1
$$

$$
e_2x^2 - k_2n_2 = z_2 - k_2y_2
$$

$$
e_3x^2 - k_3n_3 = z_3 - k_3y_3
$$

构造格
$$
\begin{pmatrix}
x^2 & k_1 & k_2 & k_3
\end{pmatrix}
\begin{pmatrix}
M & e_1 & e_2 & e_3\\
0 & -n_1 & 0 & 0\\
0 & 0 & -n_2 & 0\\
0 & 0 & 0 & -n_3
\end{pmatrix}
=
\begin{pmatrix}
x^2M & z_1 - k_1y_1 & z_2 - k_2y_2 & z_3 - k_3y_3
\end{pmatrix}
$$

这里能规约出$x^2$，还有$z_1 - k_1y_1$，利用等式$e_1x^2 - k_1n_1 = z_1 - k_1y_1$，求出$k_1$

然后对上式同模$n_1$，有
$$
f = e_1x^2 - (z_1 - k_1y_1) \mod n_1
$$
未知量为$y_1,z_1$，用二元copper

经过测试copper出来的结果是(p + q - 1)的高位，低250位是未知的

构造一个RealField(2048)可以解得p的高位，大约低254位是未知的，我选择直接模掉256位然后爆破8位进行一元coppersmith。

恢复出p之后发现e和$(p-1)(q-1)$的公因数是$e$，并且gcd(e,p-1) = 3。先求出$m^3 \equiv c^{d’} \mod p$，然后在模p下构造多项式$f = m^e - m_p^{3} \mod p$进行求解

exp

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
from Crypto.Util.number import *
import gmpy2
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

ns = [58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167, 77621328849675766747673031143217563980503830449890233197117569566535170499356584333526498228802079135043121885950830320777642529199704224484173792215691924850086027618183393165197503325417741686635820334799489140360184827244176669486536901652827052817389390205607840551799799037689580359943641014734459153393, 112244920700186260026594736958318991062998987080230137582151100770199379608284829383065111800934933346946496041561749555085922429662611986339400029890877247514987095240380019377389184545006798594193383230298132838994539491402564579629017309643629910561998268286162916487705908044261914142200286678017692930877]
es = [46762963588977775648213636278524171408894671002158172701955774077187382885695296449518850546775920334764033057745226744111631183010556541467024035131602309988991836959736948179491431343087734419406823467043032520956443072556932946767546576469286010676651317873358203560021064830688914958086524112915123700678, 49605058941818136068558533413619424099600243928109466352604646203354430655695939177245076016870792265350960174089601299549033530643078866868937787258274475767441534991912769995268058506952466739575911255510940326565376471493045685544056383561868628029099619187607579109612157304977780126730283103824111801708, 35433601810279274137096137736120773703247868305827931187532982974242279082633517463016086358856291932337981126992048059591164336008738979183437333221010305682689432537562502148059203087673302900990705589870381203411821061168753251557946997898741497047442934600089950257888693394999451561437497637827070063398]
c = 45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729
e = 8462913
n1,n2,n3 = ns
e1,e2,e3 = es

n = [n1,n2,n3]
M = isqrt(max(n))

Ge = [[M,e1,e2,e3],
    [0,-n1,0,0],
    [0,0,-n2,0],
    [0,0,0,-n3]]

Ge = Matrix(ZZ,Ge)

line = Ge.LLL()[0]
dM = line[0]
x_2 = abs(dM) // M
x = gmpy2.iroot(x_2,2)[0]
assert isPrime(x)

tmp = abs(line[1])
k1 = (e1 * x_2 - tmp) // n1 + 1

R.<y,z> = PolynomialRing(Zmod(n1))
f = (e1 * x_2) - (z - k1 * y)
res = small_roots(f,(2^513,2^630),m=1,d=2)
y = int(res[0][0])

hint = y >> 250
n = 58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167

R.<x> = PolynomialRing(RealField(2048))
f = x * ((hint << 250) - x) - n1
res = f.roots()
pbits = 512
for root in res:
    phigh = int(root[0])
    p_high = phigh >> 256
    for i in trange(2**8):
     p4 = p_high << 8			#这里需要先爆破8位，使得知道264位以后再恢复p
     p4 = p4 + i
     kbits = pbits - p4.bit_length()
     p4 = p4 << kbits
     R.<x> = PolynomialRing(Zmod(n))
     f = x + p4
     x = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
     if x:
         p = p4 + int(x[0])
         q = n // p
         print(f"p = {p}")
         print(f"q = {q}")
         break
        
 """
 p = 7595466686419558151205913432118661460574378336265188601308332178368424478703273480167149453312906478797521330243646557948961908036589158891684701262055023
q = 7696200979887856341831037613988614280823562431557099321251289719686349578851157595313091133333376255237947592610103860940743200558583228583143108125315529
 """
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *

p = 7595466686419558151205913432118661460574378336265188601308332178368424478703273480167149453312906478797521330243646557948961908036589158891684701262055023
q = 7696200979887856341831037613988614280823562431557099321251289719686349578851157595313091133333376255237947592610103860940743200558583228583143108125315529
n = 58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167
e = 8462913
c = 45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729

phi = (p-1)*(q-1)

d_p = inverse(e // 3,p-1)
m_3p = pow(c,d_p,p)

R.<x> = PolynomialRing(Zmod(p))
f = x^3 - m_3p
res = f.roots()
for m in res:
    print(long_to_bytes(int(m[0])))
    # flag{N3w_Attacks_4_key_equat1ons}
-------------已经到底啦！-------------