国城杯2024 WriteUP

Spreng 发布于 2025-01-27 最后更新于 13 天前 62 次阅读

摘要

国城杯2024的WriteUP，包括Crypto全解，待复现：crush's_secret3、esay_key、FunMz

前言

这次是2024年12月上旬的比赛，两人组队打的，我就做出来一道逆向，密码爆零了。我们校队的密码师傅直接ak了，我还得练啊。。

比赛WP：国城杯2024 WriteUP

Crypto

Curve

题目给出了eG、e、椭圆曲线的参数，要求G的x坐标。

只需要算出e的逆即可求出G，要算e的逆则需要椭圆曲线的阶，而题目中的椭圆曲线是Twisted Edwards Curve，需要将其转化为sage可解的Weierstrass Curve形式即可。

下面是转换公式：

Montgomery -> Weierstrass：

Twisted Edwards -> Montgomery：

from Crypto.Util.number import *

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


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


eG = (
    34120664973166619886120801966861368419497948422807175421202190709822232354059,
    11301243831592615312624457443883283529467532390028216735072818875052648928463,
)

# T -> M
J = 2 * (a + d) / (a - d)
K = 4 / (a - d)

# M -> W
A = (3 - J**2) / (3 * K**2)
B = (2 * J**3 - 9 * J) / (27 * K**3)

E = EllipticCurve(Zmod(p), [0, 0, 0, A, B])
od = E.order()
e_inv = int(pow(e, -1, od))
G = mul(e_inv, eG)

print(long_to_bytes(G[0]))

Ez_sign

两个部分，第一部分通过两个签名解出msg（e = ?），第二部分解一个二平方问题，来算RSA。

因为两个签名的k具有平方关系，利用这点消元，会得出一元二次同余方程，读者可自行计算。

然后用sage解一下即可

def solve_e(sign1, sign2, q):
    H1, r1, s1 = sign1
    H2, r2, s2 = sign2

    s1_inv = inverse(s1, q)
    s2_inv = inverse(s2, q)

    A = r1 * r1 * s1_inv * s1_inv
    B = 2 * H1 * r1 * s1_inv * s1_inv - r2 * s2_inv
    C = H1 * H1 * s1_inv * s1_inv - H2 * s2_inv

    P = PolynomialRing(Zmod(q), "x")
    x = P.gen()
    eq = A * x ^ 2 + B * x + C

    print(eq.roots())
    # [(91973915966463187834053272623425597244095846333, 1), (1865444199836044046649, 1)]

    print(long_to_bytes(91973915966463187834053272623425597244095846333))
    print(long_to_bytes(1865444199836044046649))  # b'e = 44519'

第二部分借用了脚本https://ask.sagemath.org/question/76636/sum-of-2-squares/

原理是将N在复数域分解因子，其中存在

本例中N的因子有768个，完全可以在合理的时间内求解。

def all_two_squares(n):
    return [
        (abs(d[0]), abs(d[1])) for d in divisors(GaussianIntegers()(n)) if norm(d) == n
    ]

完整代码：

from Crypto.Util.number import *


def all_two_squares(n):
    return [
        (abs(d[0]), abs(d[1])) for d in divisors(GaussianIntegers()(n)) if norm(d) == n
    ]


def solve_e(sign1, sign2, q):
    H1, r1, s1 = sign1
    H2, r2, s2 = sign2

    s1_inv = inverse(s1, q)
    s2_inv = inverse(s2, q)

    A = r1 * r1 * s1_inv * s1_inv
    B = 2 * H1 * r1 * s1_inv * s1_inv - r2 * s2_inv
    C = H1 * H1 * s1_inv * s1_inv - H2 * s2_inv

    P = PolynomialRing(Zmod(q), "x")
    x = P.gen()
    eq = A * x ^ 2 + B * x + C

    print(eq.roots())
    # [(91973915966463187834053272623425597244095846333, 1), (1865444199836044046649, 1)]

    print(long_to_bytes(91973915966463187834053272623425597244095846333))
    print(long_to_bytes(1865444199836044046649))  # b'e = 44519'


p = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
q = 829396411171540475587755762866203184101195238207
g = 87036604306839610565326489540582721363203007549199721259441400754982765368067012246281187432501490614633302696667034188357108387643921907247964850741525797183732941221335215366182266284004953589251764575162228404140768536534167491117433689878845912406615227673100755350290475167413701005196853054828541680397
y = 97644672217092534422903769459190836176879315123054001151977789291649564201120414036287557280431608390741595834467632108397663276781265601024889217654490419259208919898180195586714790127650244788782155032615116944102113736041131315531765220891253274685646444667344472175149252120261958868249193192444916098238

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

# solve_e((H1, r1, s1), (H2, r2, s2), q)
# ans = all_two_squares(C)
# print(ans)

e = 44519
ans = [
    (411800265284112683889770914584779351243, 97538457512222161659361018727247943103),
    (385935421767853150067085999079428269993, 173629085716646134993835981317457288147),
    (347432454257893250496407965506777649463, 241627603783727624224706687817893681267),
    (302951519846417861008714825074296492447, 295488723650623654106370451762393175957),
    (295488723650623654106370451762393175957, 302951519846417861008714825074296492447),
    (173629085716646134993835981317457288147, 385935421767853150067085999079428269993),
    (139154793241392602890445837550424516283, 399661297475592982293435778542228355087),
    (16944416637726545286802875167254662553, 422854698361903371427733980562270024707),
    (63300355510251304584114633515453587403, 418433117922332896279236283423489909057),
    (97538457512222161659361018727247943103, 411800265284112683889770914584779351243),
    (212200170463729600479653952183489384503, 366147916608975462877987617004979518093),
    (241627603783727624224706687817893681267, 347432454257893250496407965506777649463),
    (366147916608975462877987617004979518093, 212200170463729600479653952183489384503),
    (399661297475592982293435778542228355087, 139154793241392602890445837550424516283),
    (418433117922332896279236283423489909057, 63300355510251304584114633515453587403),
    (422854698361903371427733980562270024707, 16944416637726545286802875167254662553),
]


for p, q in ans:
    N = p * q
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    m = pow(c, d, N)

    try:
        print(long_to_bytes(int(m)).decode())
    except:
        pass
        
# D0g3xGC{EZ_DSA_@nd_C0mplex_QAQ}

BabyRSA

已知 ， ，，还原明文。

显然有 ，所以有 ，观察发现这里m替换成其他数依然成立

令 代入，即可求出 

from Crypto.Util.number import *


N = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175

pq = GCD(pow(2, N * d, N) - 2, N)
m = pow(c, d, pq)
m = long_to_bytes(m)
print(m)

 

To be continued......