糖醋小鸡块的blog
0%

2024-Hgame-week4-wp-crypto

发表于 分类于 Valine：

简单记录一下。

lastRSA

题目：

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
from Crypto.Util.number import *
from secret import flag

def encrypt(P,k,leak0):
    round=40
    t=114514
    x= leak0+2*t if k==1 else 2*t*leak0
    enc=2024
    while(round):
        enc+=pow(x,round,P)
        round-=1
    return enc

m=bytes_to_long(flag)
p=getStrongPrime(512)
q=getStrongPrime(512)
assert len(bin(p)[2:])==512 and len(bin(q)[2:])==512
e=0x10001
leak0=p^(q>>13)
n=p*q
enc1=encrypt(n,1,leak0)
enc2=encrypt(n,0,leak0)
c=pow(m,e,n)

print(f"enc1={enc1}")
print(f"enc2={enc2}")
print(f"c={c}")
print(f"n={n}")

"""
enc1=2481998981478152169164378674194911111475668734496914731682204172873045273889232856266140236518231314247189371709204253066552650323964534117750428068488816244218804456399611481184330258906749484831445348350172666468738790766815099309565494384945826796034182837505953580660530809234341340618365003203562639721024   
enc2=2892413486487317168909532087203213279451225676278514499452279887449096190436834627119161155437012153025493797437822039637248773941097619806471091066094500182219982742574131816371999183859939231601667171386686480639682179794271743863617494759526428080527698539121555583797116049103918578087014860597240690299394   
c=87077759878060225287052106938097622158896106278756852778571684429767457761148474369973882278847307769690207029595557915248044823659812747567906459417733553420521047767697402135115530660537769991893832879721828034794560921646691417429690920199537846426396918932533649132260605985848584545112232670451169040592        
n=136159501395608246592433283541763642196295827652290287729738751327141687762873360488671062583851846628664067117347340297084457474032286451582225574885517757497232577841944028986878525656103449482492190400477852995620473233002547925192690737520592206832895895025277841872025718478827192193010765543046480481871       
"""

题目的enc1和enc2给了两个关于leak0这个量的表达式，这两个表达式都可以看作是以leak0为根的多项式，所以可以用GCD把leak0求出来。

求出leak0后，由于leak0是$p \oplus (q >> 13)$，所以有两种办法可以把p、q求出来。

第一种办法是爆破q的高13位，然后当作普通的剪枝来做，将所有剪出来的p去检查能否被n整除

第二种办法就是，注意到这里由于p进行了13位的移位，所以leak0的高13位其实就是p的高13位，而利用p的高位，可以用n整除他得到q的高位，然后就可以利用leak0去进一步得到p的后续的高位，反复进行上述步骤就可以逐步把完整的p求出来。需要注意的是由于可能有进位，所以可能会产生两bit甚至以上的误差(极端一点的情况，最末位的0111…由于进位变成10…)，不过这种概率并不高，所以控制2bit的误差已经可以解决绝大部分情况了。

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

e=0x10001
enc1=2481998981478152169164378674194911111475668734496914731682204172873045273889232856266140236518231314247189371709204253066552650323964534117750428068488816244218804456399611481184330258906749484831445348350172666468738790766815099309565494384945826796034182837505953580660530809234341340618365003203562639721024   
enc2=2892413486487317168909532087203213279451225676278514499452279887449096190436834627119161155437012153025493797437822039637248773941097619806471091066094500182219982742574131816371999183859939231601667171386686480639682179794271743863617494759526428080527698539121555583797116049103918578087014860597240690299394   
c=87077759878060225287052106938097622158896106278756852778571684429767457761148474369973882278847307769690207029595557915248044823659812747567906459417733553420521047767697402135115530660537769991893832879721828034794560921646691417429690920199537846426396918932533649132260605985848584545112232670451169040592        
n=136159501395608246592433283541763642196295827652290287729738751327141687762873360488671062583851846628664067117347340297084457474032286451582225574885517757497232577841944028986878525656103449482492190400477852995620473233002547925192690737520592206832895895025277841872025718478827192193010765543046480481871       

#part1 get leak0
PR.<x> = PolynomialRing(Zmod(n))
f1 = -enc1+2024
for i in range(1,41):
    f1 += (x+2*114514)^i
f2 = -enc2+2024
for i in range(1,41):
    f2 += (2*114514*x)^i
def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()
leak0 = int(-gcd(f1, f2)[0])


#part2 get p,q
ph = leak0 >> (512-13)
phh = ph

while(ph.bit_length() < 512):
    try:
        qh = n // 2^(n.bit_length()-(2*ph.bit_length()-2)) // ph
        temp_xor = ((leak0>>(512-13-qh.bit_length())) & ((1<<(qh.bit_length()))-1))
        ph = (phh << qh.bit_length()) + (qh ^^ temp_xor)
    except:
        break

for i in range(2^(512-ph.bit_length())):
    p = 2^(512-ph.bit_length())*ph + i
    if(n % p == 0):
        q = n // p
        break

#part3 get flag
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(int(pow(c,d,n))))


#hgame{Gr0bn3r_ba3ic_0ften_w0rk3_w0nd3rs}

DexterJie师傅后面有问到我说这个题flag是groebner，所以leak0的求解也许出题人是用groebner做的。既然是一个变量两个方程那groebner肯定是可以，不过有个小问题就是一定要设置多元多项式环，不然sage应该会报错。



transformation

题目：

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
#!/usr/bin/env python
# coding: utf-8



from Crypto.Util.number import *
from secret import Curve,gx,gy

# flag = "hgame{" + hex(gx+gy)[2:] + "}"

def ison(C, P):
    c, d, p = C
    u, v = P
    return (u**2 + v**2 - c**2 * (1 + d * u**2*v**2)) % p == 0

def add(C, P, Q):
    c, d, p = C
    u1, v1 = P
    u2, v2 = Q
    assert ison(C, P) and ison(C, Q)
    u3 = (u1 * v2 + v1 * u2) * inverse(c * (1 + d * u1 * u2 * v1 * v2), p) % p
    v3 = (v1 * v2 - u1 * u2) * inverse(c * (1 - d * u1 * u2 * v1 * v2), p) % p
    return (int(u3), int(v3))

def mul(C, P, m):
    assert ison(C, P)
    c, d, p = C
    B = bin(m)[2:]
    l = len(B)
    u, v = P
    PP = (-u, v)
    O = add(C, P, PP)
    Q = O
    if m == 0:
        return O
    elif m == 1:
        return P
    else:
        for _ in range(l-1):
            P = add(C, P, P)
        m = m - 2**(l-1)
        Q, P = P, (u, v)
        return add(C, Q, mul(C, P, m))

c, d, p = Curve

G = (gx, gy)
P = (423323064726997230640834352892499067628999846, 44150133418579337991209313731867512059107422186218072084511769232282794765835)
Q = (1033433758780986378718784935633168786654735170, 2890573833121495534597689071280547153773878148499187840022524010636852499684)
S = (875772166783241503962848015336037891993605823, 51964088188556618695192753554835667051669568193048726314346516461990381874317)
T = (612403241107575741587390996773145537915088133, 64560350111660175566171189050923672010957086249856725096266944042789987443125)
assert ison(Curve, P) and ison(Curve, Q) and ison(Curve, G)
e = 0x10001
print(f"eG = {mul(Curve, G, e)}")

# eG = (40198712137747628410430624618331426343875490261805137714686326678112749070113, 65008030741966083441937593781739493959677657609550411222052299176801418887407)

这个题依然基于扭曲爱德华曲线，只是最后为了求解flag还需要再映射回来，具体推导可以参考之前写过的另一篇博客：

Crypto趣题-曲线 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

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

#part1 get c2、d
P = (423323064726997230640834352892499067628999846, 44150133418579337991209313731867512059107422186218072084511769232282794765835)
Q = (1033433758780986378718784935633168786654735170, 2890573833121495534597689071280547153773878148499187840022524010636852499684)
S = (875772166783241503962848015336037891993605823, 51964088188556618695192753554835667051669568193048726314346516461990381874317)
T = (612403241107575741587390996773145537915088133, 64560350111660175566171189050923672010957086249856725096266944042789987443125)
if(0):
    PR.<c,d> = PolynomialRing(ZZ)
    f1 = P[0]**2 + P[1]**2 - c**2 * (1 + d * P[0]**2*P[1]**2)
    f2 = Q[0]**2 + Q[1]**2 - c**2 * (1 + d * Q[0]**2*Q[1]**2)
    f3 = S[0]**2 + S[1]**2 - c**2 * (1 + d * S[0]**2*S[1]**2)
    f4 = T[0]**2 + T[1]**2 - c**2 * (1 + d * T[0]**2*T[1]**2)
    res = ideal([f1,f2,f3,f4]).groebner_basis()
    print(res)
p = 67943764351073247630101943221474884302015437788242536572067548198498727238923
d = p - 59163782230252684822841652225303740075401079121772957375715728037523200623623
c2 = p - 55035035862773596757724513019504552123843780200057245245581766079309471393995
#get c
PR.<c> = PolynomialRing(Zmod(p))
f = c^2 - c2
#print(f.roots())

c = 60799864652963819347231403856892915722262395658296749944775205023739430037843
#c = 7143899698109428282870539364581968579753042129945786627292343174759297201080


#part2 map to ECC
F = GF(p)
a = 1
dd = F(d*c^4)
A = F(2) * F(a+dd) / F(a-dd)
B = F(4) / F(a-dd)
a = F(3-A^2) / F(3*B^2)
b = F(2*A^3-9*A) / F(27*B^3)

def edwards_to_ECC(x,y):
    x1 = F(x) / F(c)
    y1 = F(y) / F(c)
    #now curve is a*x^2+y^2 = 1+dd*x^2*y^2

    x2 = F(1+y1) / F(1-y1)
    y2 = F(x2) / F(x1)
    #now curve is By^2 = x^3 + Ax^2 + x

    x3 = (F(3*x2) + F(A)) / F(3*B)
    y3 = F(y2) / F(B)
    #now curve is y^2 = x^3 + ax + b

    return (x3,y3)
 
def ECC_to_edwards(x,y):
    x2 = (F(x) * F(3*B) - F(A)) / F(3)
    y2 = F(y) * F(B)
    #now curve is By^2 = x^3 + Ax^2 + x

    x1 = F(x2) / F(y2)
    y1 = F(1) - (F(2) / F(x2+1))
    #now curve is a*x^2+y^2 = 1+dd*x^2*y^2

    x_ = F(x1) * F(c)
    y_ = F(y1) * F(c)
    #now curve is a*x^2+y^2 = c^2(1+d*x^2*y^2)
    
    return (x_,y_)
 
E = EllipticCurve(GF(p), [a, b])
eG = (40198712137747628410430624618331426343875490261805137714686326678112749070113, 65008030741966083441937593781739493959677657609550411222052299176801418887407)
eG = E(edwards_to_ECC(eG[0],eG[1]))


#part3 inverse
e = 65537
key_d = inverse(e,eG.order())
G = key_d*eG
gx,gy = ECC_to_edwards(G[0],G[1])
flag = "hgame{" + hex(gx+gy)[2:] + "}"
print(flag)

#hgame{7c91b51150e2339628f10c5be61d49bbf9471ef00c9b94bb0473feac06303bcc}