2024-Hgame-week4-wp-crypto

2024-Hgame-week4-wp-crypto

天璇冬季招新其实挪用了week4的第一道题，的一小部分的一小部分。。。

那个椭圆曲线不是要转化一下嘛，我就把转化的部分去掉，只留下了求阶和消元的部分，基本上是周赛第二周的水平。

可惜没人做出来。

另一道题是强网杯青少年赛的原题（其实也不是原题，我改了变量名字防止了搜索，基本也算是原题吧）也更一下吧，放在另一个博客里。

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
57
#!/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)

一眼丁真椭圆曲线 给了四个点 显然是要消元了。
$$
\begin{aligned}p_{1}^{2}+p_{2}^{2}-c^{2}(1-dp_{1}^{2}p_{2}^{2})=0\text{(mod p)}\end{aligned}
$$

$$
\begin{aligned}q_{1}^{2}+q_{2}^{2}-c^{2}(1-dq_{1}^{2}q_{2}^{2})=0\text{(mod p)}\end{aligned}
$$

$$
\begin{aligned}s_{1}^{2}+s_{2}^{2}-c^{2}(1-ds_{1}^{2}s_{2}^{2})=0\text{(mod p)}\end{aligned}
$$

$$
\begin{aligned}t_{1}^{2}+t_{2}^{2}-c^{2}(1-dt_{1}^{2}t_{2}^{2})=0\text{(mod p)}\end{aligned}
$$

简单消元
$$
\begin{aligned}p_{1}^{2}+p_{2}^{2}-q_{1}^{2}-q_{2}^{2}=c^{2}d(p_{1}^{2}p_{2}^{2}-q_{1}^{2}q_{2}^{2})\text{(mod p)}\end{aligned}
$$

$$
\begin{aligned}s_{1}^{2}+s_{2}^{2}-t_{1}^{2}-t_{2}^{2}=c^{2}d(s_{1}^{2}s_{2}^{2}-t_{1}^{2}t_{2}^{2})\text{(mod p)}\end{aligned}
$$

再消元
$$
\begin{aligned}(p_{1}^{2}+p_{2}^{2}-q_{1}^{2}-q_{2}^{2})(p_{1}^{2}p_{2}^{2}-q_{1}^{2}q_{2}^{2})^{-1}=(s_{1}^{2}+s_{2}^{2}-t_{1}^{2}-t_{2}^{2})(s_{1}^{2}s_{2}^{2}-t_{1}^{2}t_{2}^{2})^{-1}\text{(mod p)}\end{aligned}
$$
移一下
$$
\begin{aligned}(p_{1}^{2}+p_{2}^{2}-q_{1}^{2}-q_{2}^{2})(s_{1}^{2}s_{2}^{2}-t_{1}^{2}t_{2}^{2})=(s_{1}^{2}+s_{2}^{2}-t_{1}^{2}-t_{2}^{2})(p_{1}^{2}p_{2}^{2}-q_{1}^{2}q_{2}^{2})\text{(mod p)}\end{aligned}
$$

$$
\begin{aligned}(p_{1}^{2}+p_{2}^{2}-q_{1}^{2}-q_{2}^{2})(s_{1}^{2}s_{2}^{2}-t_{1}^{2}t_{2}^{2})-(s_{1}^{2}+s_{2}^{2}-t_{1}^{2}-t_{2}^{2})(p_{1}^{2}p_{2}^{2}-q_{1}^{2}q_{2}^{2})=kp\end{aligned}
$$

到这里已经很明显了 同样构造s和t的式子 求公因数即可

求出公因数p后再求c和d就很容易了 不多赘述

然后是转换步骤 这里主要参考了[Rohald (ariana1729.github.io)](https://ariana1729.github.io/writeups/2021/Crypto CTF/Rohald/2021-07-31-Rohald.html)

$u^2+v^2-c^2(1+du^2v^2)=0\quad(\mathrm{mod~}p)$

$u\to\frac{2cx}y,v\to\frac{c(x-1)}{x+1}$

$\frac{y^2}{c^4d-1}+x^3-\frac{2(c^4d+1)}{c^4d-1}x^2+x=0\quad(\mathrm{mod~}p)$

$x\to\frac x{1-c^4d}+\frac23\frac{c^4d+1}{c^4d-1},y\to\frac y{1-c^4d}$

$y^2=x^3+\frac1{27}\left(-9-126c^4d-9c^8d^2\right)x+\frac1{27}\left(-2+66c^4d+66c^8d^2-2c^{12}d^3\right)$

一气呵成得到椭圆曲线

接下来求阶即可

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
from Crypto.Util.number import *
from gmpy2 import *
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))
    
P = (423323064726997230640834352892499067628999846, 44150133418579337991209313731867512059107422186218072084511769232282794765835)
Q = (1033433758780986378718784935633168786654735170, 2890573833121495534597689071280547153773878148499187840022524010636852499684)
S = (875772166783241503962848015336037891993605823, 51964088188556618695192753554835667051669568193048726314346516461990381874317)
T = (612403241107575741587390996773145537915088133, 64560350111660175566171189050923672010957086249856725096266944042789987443125)
#(u**2 + v**2 - c**2 * (1 + d * u**2*v**2)) % p == 0
t1 = (P[0]**2+P[1]**2-Q[0]**2-Q[1]**2)*(S[0]**2*S[1]**2-T[0]**2*T[1]**2)
t2 = (S[0]**2+S[1]**2-T[0]**2-T[1]**2)*(P[0]**2*P[1]**2-Q[0]**2*Q[1]**2)
t3 = (S[0]**2+S[1]**2-Q[0]**2-Q[1]**2)*(P[0]**2*P[1]**2-T[0]**2*T[1]**2)
t4 = (P[0]**2+P[1]**2-T[0]**2-T[1]**2)*(S[0]**2*S[1]**2-Q[0]**2*Q[1]**2)
p = GCD(t1-t2,t3-t4)
c2d = ((P[0]**2+P[1]**2-Q[0]**2-Q[1]**2)*(inverse((P[0]**2*P[1]**2-Q[0]**2*Q[1]**2),p)))%p
c2 = (P[0]**2+P[1]**2-c2d*(P[0]**2*P[1]**2))%p
c = pow(c2,(p+1)//4,p)
d = (c2d*(inverse(c2,p)))%p
Curve = c,d,p

e = 0x10001
order = 67943764351073247630101943221474884302071957392340923189748226436548954126268
k = inverse(e,order)
eG = (40198712137747628410430624618331426343875490261805137714686326678112749070113, 65008030741966083441937593781739493959677657609550411222052299176801418887407)
G = mul(Curve, eG, k)
print(G)
assert (mul(Curve, G, e)==eG)
flag = "hgame{" + hex(G[0]+G[1])[2:] + "}"
print(flag)

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       
"""

第一步多项式gcd 第二部一个简单的算法（我还以为是剪枝 其实不是）

因为这个第二步 leak0的高13位就是p的高13位了，所以利用p的高位整除得到q的高位后，还可以返回来异或得出p的后续的高位，比较简单。

简单放个脚本吧 真要说的话 要说很多 少说点的话 其实也没什么好说的（

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
#sage部分
from Crypto.Util.number import *
def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

enc1=2481998981478152169164378674194911111475668734496914731682204172873045273889232856266140236518231314247189371709204253066552650323964534117750428068488816244218804456399611481184330258906749484831445348350172666468738790766815099309565494384945826796034182837505953580660530809234341340618365003203562639721024   
enc2=2892413486487317168909532087203213279451225676278514499452279887449096190436834627119161155437012153025493797437822039637248773941097619806471091066094500182219982742574131816371999183859939231601667171386686480639682179794271743863617494759526428080527698539121555583797116049103918578087014860597240690299394   
c=87077759878060225287052106938097622158896106278756852778571684429767457761148474369973882278847307769690207029595557915248044823659812747567906459417733553420521047767697402135115530660537769991893832879721828034794560921646691417429690920199537846426396918932533649132260605985848584545112232670451169040592        
n=136159501395608246592433283541763642196295827652290287729738751327141687762873360488671062583851846628664067117347340297084457474032286451582225574885517757497232577841944028986878525656103449482492190400477852995620473233002547925192690737520592206832895895025277841872025718478827192193010765543046480481871       
t=114514
enc=2024
R.<x> = PolynomialRing(Zmod(n))  # 定义一个多项式环，变量为x，系数在有理数集QQ上
f = (x+2*t)^1+(x+2*t)^2+(x+2*t)^3+(x+2*t)^4+(x+2*t)^5+(x+2*t)^6+(x+2*t)^7+(x+2*t)^8+(x+2*t)^9+(x+2*t)^10+(x+2*t)^11+(x+2*t)^12+(x+2*t)^13+(x+2*t)^14+(x+2*t)^15+(x+2*t)^16+(x+2*t)^17+(x+2*t)^18+(x+2*t)^19+(x+2*t)^20+(x+2*t)^21+(x+2*t)^22+(x+2*t)^23+(x+2*t)^24+(x+2*t)^25+(x+2*t)^26+(x+2*t)^27+(x+2*t)^28+(x+2*t)^29+(x+2*t)^30+(x+2*t)^31+(x+2*t)^32+(x+2*t)^33+(x+2*t)^34+(x+2*t)^35+(x+2*t)^36+(x+2*t)^37+(x+2*t)^38+(x+2*t)^39+(x+2*t)^40-enc1+enc  # 定义一个多项式f
g = (x*2*t)^1+(x*2*t)^2+(x*2*t)^3+(x*2*t)^4+(x*2*t)^5+(x*2*t)^6+(x*2*t)^7+(x*2*t)^8+(x*2*t)^9+(x*2*t)^10+(x*2*t)^11+(x*2*t)^12+(x*2*t)^13+(x*2*t)^14+(x*2*t)^15+(x*2*t)^16+(x*2*t)^17+(x*2*t)^18+(x*2*t)^19+(x*2*t)^20+(x*2*t)^21+(x*2*t)^22+(x*2*t)^23+(x*2*t)^24+(x*2*t)^25+(x*2*t)^26+(x*2*t)^27+(x*2*t)^28+(x*2*t)^29+(x*2*t)^30+(x*2*t)^31+(x*2*t)^32+(x*2*t)^33+(x*2*t)^34+(x*2*t)^35+(x*2*t)^36+(x*2*t)^37+(x*2*t)^38+(x*2*t)^39+(x*2*t)^40-enc2+enc  # 定义一个多项式g
print(-GCD(f,g).monic().coefficients()[0])

#python部分
from Crypto.Util.number import *
leak0=13168452015078389807681744077701012683188749953280204324570483361963541298704796389757190180549802771265899020301416729606658667351017116721327316272373584
enc1=2481998981478152169164378674194911111475668734496914731682204172873045273889232856266140236518231314247189371709204253066552650323964534117750428068488816244218804456399611481184330258906749484831445348350172666468738790766815099309565494384945826796034182837505953580660530809234341340618365003203562639721024   
enc2=2892413486487317168909532087203213279451225676278514499452279887449096190436834627119161155437012153025493797437822039637248773941097619806471091066094500182219982742574131816371999183859939231601667171386686480639682179794271743863617494759526428080527698539121555583797116049103918578087014860597240690299394   
c=87077759878060225287052106938097622158896106278756852778571684429767457761148474369973882278847307769690207029595557915248044823659812747567906459417733553420521047767697402135115530660537769991893832879721828034794560921646691417429690920199537846426396918932533649132260605985848584545112232670451169040592        
N=136159501395608246592433283541763642196295827652290287729738751327141687762873360488671062583851846628664067117347340297084457474032286451582225574885517757497232577841944028986878525656103449482492190400477852995620473233002547925192690737520592206832895895025277841872025718478827192193010765543046480481871       
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
assert (encrypt(N,1,leak0)==enc1)
#leak0=p^(q>>13)
pbar = leak0 >>(512-13)


qbar = (N>>(1024 - pbar.bit_length()*2))//pbar
while True:
    try:
        qbar = (N>>(1024 - pbar.bit_length()*2))//pbar
        qbar = qbar>>4
        leak0s = leak0^(qbar<<(512-13-qbar.bit_length()))
        pbar = leak0s >> (512-13-qbar.bit_length())
    except:
        break

for i in range(64):
    if N%((pbar<<4)+i) == 0:
        p = (pbar<<4)+i
        q = N//p
        print("[+] p =",p)
        print("[+] q =",q)
        break
phi = (p-1)*(q-1)
e=0x10001
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,N)))

#CTF #Crypto #Web #Misc #Hgame
2024-Hgame-week4-wp-crypto
https://py-thok.github.io/2024/03/20/2024-Hgame-week4-wp-crypto/
作者
PYthok-Ptk
发布于
2024年3月20日
许可协议