2024“国城杯”⽹络安全挑战赛 Crypto WriteUp

Curve

#sagemath
from Crypto.Util.number import *

def add(P, Q):
    (x1, y1) = P
    (x2, y2) = Q

    x3 = (x1*y2 + y1*x2) * inverse(1 + d*x1*x2*y1*y2, p) % p
    y3 = (y1*y2 - a*x1*x2) * inverse(1 - d*x1*x2*y1*y2, p) % p
    return (x3, y3)

def mul(x, P):
    Q = (0, 1)
    while x > 0:
        if x % 2 == 1:
            Q = add(Q, P)
        P = add(P, P)
        x = x >> 1
    return Q

p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
e=0x10001

gx=bytes_to_long(b'D0g3xGC{*****************}')

PR.<y>=PolynomialRing(Zmod(p))
f=(d*gx^2-1)*y^2+(1-a*gx^2)
gy=int(f.roots()[0][0])

assert (a*gx^2+gy^2)%p==(1+d*gx^2*gy^2)%p

G=(gx,gy)

eG = mul(e, G)
print(eG)

#eG = (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)

原题：Ch3mtr4ils.github.io/2024/03/05/ECC中的常见曲线/index.html at 6d773859f58bc4d47bb55278da1ee473993744da · Ch3mtr4ils/Ch3mtr4ils.github.io

from Crypto.Util.number import *

p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
c = 1
e = 0x10001

eG = (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)
F = GF(p)

A = (2 * (a + d)) / (a - d)
B = 4 / (a - d)
a = (3 - A ^ 2) / (3 * B ^ 2)
b = (2 * A ^ 3 - 9 * A) / (27 * B ^ 3)


def TEd_to_ECC(x, y):
    x1 = F(1 + y) / F(1 - y)
    y1 = F(x1) / F(x)
    u = F(x1) / F(B) + F(A) / F(3 * B)
    v = F(y1) / F(B)
    return (u, v)


def ECC_to_TEd(x, y):
    x1 = F(B) * F(x) - F(A) / F(3)
    y1 = F(B) * F(y)
    u = F(x1) / F(y1)
    v = (F(x1) - F(1)) / (F(x1) + F(1))
    return (u, v)


E = EllipticCurve(F, [a, b])
o = E.order()
eG = E(TEd_to_ECC(eG[0], eG[1]))
t = inverse(e, o)
G = ECC_to_TEd((t * eG)[0], (t * eG)[1])

print(long_to_bytes(int(G[0])))
# D0g3xGC{SOlvE_The_Edcurv3}

EZ_sign

from Crypto.Util.number import *
from gmpy2 import *
from hashlib import*
import random,os

flag = b'D0g3xGA{***************}'
msg = b'e = ?'

def sign(pub, pri, k):
    (p,q,g,y) = pub
    x = pri
    r = int(powmod(g, k, p) % q)
    H = bytes_to_long(sha1(os.urandom(20)).digest())
    s = int((H + r * x) * invert(k, q) % q)
    return (H,r,s)

k1 = getPrime(64)
k2 = k1 ** 2
pri = bytes_to_long(msg)
a = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
b = 829396411171540475587755762866203184101195238207
g = 87036604306839610565326489540582721363203007549199721259441400754982765368067012246281187432501490614633302696667034188357108387643921907247964850741525797183732941221335215366182266284004953589251764575162228404140768536534167491117433689878845912406615227673100755350290475167413701005196853054828541680397
y = 97644672217092534422903769459190836176879315123054001151977789291649564201120414036287557280431608390741595834467632108397663276781265601024889217654490419259208919898180195586714790127650244788782155032615116944102113736041131315531765220891253274685646444667344472175149252120261958868249193192444916098238

pub = (a, b, g, y)

H1, r1, s1 = sign(pub, pri, k1)

H2, r2, s2 = sign(pub, pri, k2)

p = getPrime(128)
q = getPrime(128)
n = p * q
c = powmod(bytes_to_long(flag), e, n)

C = p**2 + q**2

print(f'(H1, r1, s1) = {H1}, {r1}, {s1}')
print(f'(H2, r2, s2) = {H2}, {r2}, {s2}')
print(c)
print(C)

'''
(H1, r1, s1) = 659787401883545685817457221852854226644541324571, 334878452864978819061930997065061937449464345411, 282119793273156214497433603026823910474682900640
(H2, r2, s2) = 156467414524100313878421798396433081456201599833, 584114556699509111695337565541829205336940360354, 827371522240921066790477048569787834877112159142
c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
C = 179093209181929149953346613617854206675976823277412565868079070299728290913658
'''

首先要解出e的值

由题目已知

s1k1≡H1+xr1mod  qs_1k_1\equiv H_1+xr_1 \mod q
s2k12≡H2+xr2mod  qs_2k_1^2 \equiv H_2+xr_2 \mod q

上面的式子乘r2r_2,下面式子乘r1r_1

r2s1k1≡h1r2+xr1r2mod  qr_2s_1k_1\equiv h_1r_2+xr_1r_2 \mod q

r1s2k12≡h2r1+xr1r2mod  qr_1s_2k_1^2\equiv h_2r_1+xr_1r_2 \mod q

两式相减得：

r1s2k2+H1r2−r2s1k−r1H2≡0mod  qr_1s_2k^2+H_1r_2-r_2s_1k-r_1H_2\equiv 0 \mod q

解模方程

from gmpy2 import *
from Crypto.Util.number import long_to_bytes
H1 = 659787401883545685817457221852854226644541324571
r1 = 334878452864978819061930997065061937449464345411
s1 = 282119793273156214497433603026823910474682900640
H2 = 156467414524100313878421798396433081456201599833
r2 = 584114556699509111695337565541829205336940360354
s2 = 827371522240921066790477048569787834877112159142
q = 829396411171540475587755762866203184101195238207

P.<k> = PolynomialRing(Zmod(q))
f = r1*s2*k^2+H1*r2-r2*s1*k-r1*H2
roots_with_multiplicities = f.roots(multiplicities=True)
print("Roots with multiplicities:", roots_with_multiplicities)

得到k1=9455554284687443083

from gmpy2 import *
from Crypto.Util.number import long_to_bytes
k1 = 9455554284687443083
x = ((k1*s1 - H1)*gmpy2.invert(r1,q)) % q
print(long_to_bytes(x))

b'e = 44519'

解$$p2+q2=C$$方程

不能用sagemath的two_squares()函数（虽然它确实很快，但只有一组解，而且这组解不是我们要的解）

用sympy库的cornacchia函数，可以得到方程ax2+by2=max^2+by^2=m所有的正整数解（要求x,yx,y互质）

from sympy.solvers.diophantine.diophantine import cornacchia
a = 1
b = 1
m = 179093209181929149953346613617854206675976823277412565868079070299728290913658
solutions = cornacchia(a, b, m)
print(solutions)

得到

{(366147916608975462877987617004979518093, 212200170463729600479653952183489384503), (399661297475592982293435778542228355087, 139154793241392602890445837550424516283), (302951519846417861008714825074296492447, 295488723650623654106370451762393175957), (347432454257893250496407965506777649463, 241627603783727624224706687817893681267), (411800265284112683889770914584779351243, 97538457512222161659361018727247943103), (418433117922332896279236283423489909057, 63300355510251304584114633515453587403), (385935421767853150067085999079428269993, 173629085716646134993835981317457288147), (422854698361903371427733980562270024707, 16944416637726545286802875167254662553)}

得到全部八组解

筛选出两个都是素数的解

from gmpy2 import *
L=[(366147916608975462877987617004979518093, 212200170463729600479653952183489384503), (399661297475592982293435778542228355087, 139154793241392602890445837550424516283), (302951519846417861008714825074296492447, 295488723650623654106370451762393175957), (347432454257893250496407965506777649463, 241627603783727624224706687817893681267), (411800265284112683889770914584779351243, 97538457512222161659361018727247943103), (418433117922332896279236283423489909057, 63300355510251304584114633515453587403), (385935421767853150067085999079428269993, 173629085716646134993835981317457288147), (422854698361903371427733980562270024707, 16944416637726545286802875167254662553)]
for i in L:
    (p,q)=i
    if is_prime(p) and is_prime(q):
        print(p,q)

找到

302951519846417861008714825074296492447

295488723650623654106370451762393175957

这组，就是我们要的解，然后解RSA

from Crypto.Util.number import *
from gmpy2 import *
e = 44519
c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
p = 302951519846417861008714825074296492447 
q = 295488723650623654106370451762393175957
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c, d, n)  
print(long_to_bytes(m))

比赛之后去问了一下出题人，怎么找到179093209181929149953346613617854206675976823277412565868079070299728290913658这个数的，平方和有8组不同的解……

出题人答复：以前线下碰到被坑了，所以拿来出题了。。

BabyRsa

from secret import flag
from Crypto.Util.number import*
from gmpy2 import*

flag = b'D0g3xGC{****************}'

def gen_key(p, q):
    public_key = p*p*q
    e = public_key
    n = p*q
    phi_n = (p-1)*(q-1)
    private_key = inverse(e,phi_n)
    return public_key,private_key,e

p = getPrime(512)
q = getPrime(512)

N,d,e = gen_key(p,q)

c = gmpy2.powmod(bytes_to_long(flag),e,N)

print(N)
print(d)
print(c)

'''
n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175
'''

在这里，我们使用NN作为ee的值，并给出了dd，但这个dd只是实际dd的一部分，即 D=kdD = kd。

因此，我们有： Nd≡1(modφ(n))N d \equiv 1 \pmod{\varphi(n)}

对于任意正整数 a>1a > 1，我们可以取 aNda^{Nd} 并对 nn 取模，得到： aNd≡a1+k1φ(n)(modn)a^{Nd} \equiv a^{1+k_1 \varphi(n)} \pmod{n}

根据欧拉定理，知道： aφ(n)≡1(modn)a^{\varphi(n)} \equiv 1 \pmod{n}

由于 1的任意次方都等于 1，我们可以得到： aNd≡a(modn)a^{Nd} \equiv a \pmod{n} 移项后，得到： $$a^{Nd} - a = k_2n$$

这个优化后的表达清晰地呈现了公式的推导过程和逻辑。

from Crypto.Util.number import*
from gmpy2 import*
N = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175
a = 2
kn = pow(a,N*d,N) - a
n = gmpy2.gcd(N,kn)
p = N // n
q = n // p
assert p*q==n
print(q)
print(p)
print(long_to_bytes(int(pow(c,d,n))))
## b'D0g3xGC{W1sh_Y0u_Go0d_L@ucK-111}'