Crypto

MyErrorLearn

def XennyOracle():
    r = getPrime(512)
    d = invert(secret+r, p) - getPrime(246)
    print('> r =', r)
    print('> d =', d)

def task():
    for _ in range(3):
        op = int(input())
        if op == 1:
            XennyOracle()
        elif op == 2:
            ss = int(input())

            if ss == secret:
                print('flag: ', flag)

Tương tác với bài toán 3 lần, hai lần đầu lấy dữ liệu, lần cuối cùng xác thực secret để lấy flag

[(s+r1)^{-1}-x \equiv d1 \pmod{p}\ (s+r2)^{-1}-y \equiv d2 \pmod{p} ]\(x,y\) lần lượt là hai số nguyên tố trong dữ liệu

[(d1+x)^{-1}-r1 \equiv s \pmod{p}\ (d2+y)^{-1}-r2 \equiv s \pmod{p} ]Trừ hai phương trình

[(d1+x)^{-1}-r1-(d2+y)^{-1}+r2 \equiv 0 \pmod{p} ]Nhân với\((d1+x)(d2+y)\)

[(d2+y) - (d1+x) + (r2-r1)(d1+x)(d2+y) \equiv 0 \pmod{p} ]Một bài toán Coppersmith bậc hai Xây dựng phương trình\(f = (r1-r2)*(d1+x)*(d2+y)-(d2+y-d1-x)\), Tìm một hàm giải Coppersmith đa biến

#sagemath
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 []


r1 = 10416632501801974694227453996514471230510822844141537215435310761282236706010374287476167228551720127564766961486909719901188052844926828718157982353509009
r2 = 10945694515092921935765033073472221225431374672659751536595840465276073402439042169265480667452817278318006398182876136457632746343409326182238053908029751
d1 = 56888336937500044415702919773416114217028770468080853282740190270108239476041614796007252946794331087237297216052651102131387831331715788882702697436356478481466698200484763202280365937244685692432494727290180152495648130890129145398986742781650456719538128804602194272879452329225793378627305015814235006449
d2 = 39564785910816285169732671501865632983688744846819855674275371020624933955200211958646008885482995237194222616193536005648361431696101118452470392982186472493910970565702639588941011814416028774758786985291250896861107704070339750852212760711413327701632586870290470689206960878069267347698863426921542358105
p = 117772635282729418285879412631216935490806524671311266185546790504745904196135114727754422648999093257461858612228556910365982066740540367638744157494110844029055193511998422999596748975390734628418184477450856691002269702533884505178634105672240426552752649855510423531462598366536500750787631689349504137087

import itertools
R.<x,y> = PolynomialRing(Zmod(p))
f = (r1-r2)*(d1+x)*(d2+y)-(d2+y-d1-x)
ans = small_roots(f, bounds=(2^246,2^246), m=2)
x, y = ans[0]
secret = 1/(d1+x)-r1
print(secret)

LockbyLock

Trong cuộc thi, tôi đã nhập sai dữ liệu và mất 30 phút để chạy

Sau khi kết thúc cuộc thi, tôi đã sửa lại và lấy được kết quả chỉ sau 3 phút

Gửi lần lượt 2 và 4 để lấy n thông qua RSA đồng dạng và gcd

from pwn import *
from Crypto.Util.number import *
from gmpy2 import gcd

io = remote('tcp.cloud.dasctf.com', 21488)

io.recvuntil(b'msg1 = ')
m1 = int(io.recvline())
io.recvuntil(b'msg2 = ')
m2 = int(io.recvline())
io.recvuntil(b'msg3 = ')
m3 = int(io.recvline())

io.sendline(b'2')
io.recvuntil(b'msg1 = ')
m11 = int(io.recvline())
io.recvuntil(b'msg2 = ')
m12 = int(io.recvline())
io.recvuntil(b'msg3 = ')
m13 = int(io.recvline())

io.sendline(b'4')
io.recvuntil(b'msg1 = ')
m21 = int(io.recvline())
io.recvuntil(b'msg2 = ')
m22 = int(io.recvline())
io.recvuntil(b'msg3 = ')
m23 = int(io.recvline())

n = gcd(m11**2-m21, m12**2-m22, m13**2-m23)
print('n = ', n)
print('m1 = ', m1)
print('m2 = ', m2)
print('m3 = ', m3)
print('m11 = ', m11)
print('m12 = ', m12)
print('m13 = ', m13)
print('m21 = ', m21)
print('m22 = ', m22)
print('m23 = ', m23)

Sử dụng thuật toán Pollard's kangaroo để giải bài toán lôgarit rời rạc cho dữ liệu lấy được khi gửi 2 (hoặc 4), độ phức tạp thời gian khoảng 10^7

Ps: Trong cuộc thi, tôi đã lấy sai dữ liệu ban đầu nên đã mất thời gian chạy qwq

#sagemath
n =  27950092418645918795271296476246539971431421044767995947796205802943478655421653573048132032794234798415984952652376438949021032706491508283019165573213412785457536560835247461258996700097675642961189941397147832121215798258718677899047430424242917316567794068767871489924536948337626278187554943376441787903310776418948278970828056614007480123321047526250014275143243282932429377977743696352171804147086603083279288062958658420062643379022044426846987241250137102448598685606712521741583607474213255315746187154198844169065935475113145789594643131816301778344794413391236892556628344738627222814821415207388109885721
m11 =  20376839897483150202591245279988785405360453405518229860314688355462074916580107129330682477462552663163126795528589023633648581007626813266919326759350958000841142246828917207676253853232169554216424361180522508797731315528852217133666113558436155410718944260169577145534697157368360316333345542201829151854115374449392740319226345217386316755786443394636434084405240052107608897042547234279512095541661926355330342347645389032183986346153775559868246848334225734203525123266991086247401891517240101646138518686721872066661769309263715716056740461960894538873962031902453537598108351613389507079566414498498479169599
print('e1 = ', discrete_log_lambda(m11,mod(2,n),(10**14,10**15)))
m13 =  25654168760396958029792298552570736468682480823084565803373285663407780762485503411904748880883813230583714779620465503738003648395595616814054655108314643554108891626126605868539398053448468263238189719286443578861455115451473982124850952368091893597737777395501987491639060745712330371967127518105827612033705562056542312813576000021698561975189704496509514959272625270304453384259337771998645760374945175685616354851961881768292039874827087997461444008148949745457037468733732431091509683231366382582177637282818474046552143645887960397145203641778786138850215567179584185583145503621183907129930648092263851567807
print('e2 = ', discrete_log_lambda(m13,mod(2,n),(10**14,10**15)))

#e1 = 710179922790353
#e2 = 871767685631399

Bước cuối cùng, tấn công RSA cùng modulus, áp dụng trực tiếp

e1 = 710179922790353
e2 = 871767685631399
m1 =  18750007013174536423532792814200623641168684158537875023748157501043254834580359946005782798296094859389089373500698907014613039137711295832309784735974363506728965819640087175515796834513477450080858989016689349728236691024985081556114367071105810780697020942697446551986754568210757566280492351447198167578093986707571108589625817862709984743133957428410783190472709108509345889765505376018262071861959201900814249687461034976969943031661314448282010075462891703692709064089097420481900561158105185207229830775312377353386152497009445846705513245630211941745950480797566412389719032698035360150224973575890501234349
m3 =  7797790268283288534585277663447783093020314808581197168654721551908450973265373361401405475956787957261162271142906099769330725245515346716540341701573417181548009002140256280036084891830998092431760582730910699403915059015408500826152174941526987251255119134941854685885210496410310463675404149461859807594357045329568535924128371829778827795984952587210383466369410277156253887474458529307937131048870052343339798306152534342663301893903024266179991962280108122818029085323024355732887033339956485454178220409801766544479498601241502177418664898422266425022618582009534572842700671485483690331035082266707254176987
n =  27950092418645918795271296476246539971431421044767995947796205802943478655421653573048132032794234798415984952652376438949021032706491508283019165573213412785457536560835247461258996700097675642961189941397147832121215798258718677899047430424242917316567794068767871489924536948337626278187554943376441787903310776418948278970828056614007480123321047526250014275143243282932429377977743696352171804147086603083279288062958658420062643379022044426846987241250137102448598685606712521741583607474213255315746187154198844169065935475113145789594643131816301778344794413391236892556628344738627222814821415207388109885721

from gmpy2 import *
_, s1, s2 = gcdext(e1, e2)
m = pow(m1, s1, n) * pow(m3, s2, n)
m %= n
flag = long_to_bytes(m)
print(flag)