N1CTF 2022 Crypto | hash

今年n1ctf密码方向相比其他几个方向来说比较简单，没有离谱的论文题，都是些简单有趣的trick，想起来也挺久没写blog了，太摆了太摆了！

这里就把比赛时候大致思路写一下

Brand_new_checkin

题目思路其实很简单，只是在梅森伪随机数的状态旋转时需要做一定的分析简化爆破量

def enc(m, k):
    s, t, n = k
    r = getrandbits(1024)

    return m * pow(r, s, n) % n, m * pow(r, t, n) % n

由于s，t给了并且m是单字节，从0-255爆破一下就行

m_enc=[]
for i in tqdm(range(len(c))):
    for j in range(0,256):
        m1=c[i][0]*inverse(j,n)%n
        m2=c[i][1]*inverse(j,n)%n
        if pow(m1,t,n)==pow(m2,s,n):
            m_enc.append(j)
            break

print(m_enc)

m解出后利用扩展欧几里得组一下指数把r(mod n)计算出来，注意到

我们可以计算一下的k的上限

[1, 2, 2, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1]

我取的最后20组，2的分布较少，爆破量是

拟合我选择的是向前8位拟合，最后筛出了24组，再向前20位拟合得到正确的随机数状态回到最开始把a算出来，最后直接解密就行

partS = recover_state(rn)
state = backtrace([0] * 32*62 + partS)[:624]
# print(state)
prng = Random()
prng.setstate((3, tuple(state + [0]), None))
a = [prng.getrandbits(1024) for w in range(62)]
a=a[0]

M=bytes(m_enc)
phi= abs(a*s-t*(a-1))
d=inverse(0x10001,phi)
m=pow(bytes_to_long(M),d,n)
print(long_to_bytes(m))

Ezdlp

拿到了47组方程，已知x，y求n

由于在未知模数的情况下不能进行太大的幂次计算，所以利用一下LLL

造个格求x的线性组合的较小值，同时线性系数尽可能小

mes=[]

A=Matrix(ZZ,47,48)
for i in range(47):
    A[i,i]=1
    A[i,47]=mes[i]

print(A.LLL()[:3])

按照约化出的结果组一下，求gcd，最后丢factordb把靠近n的比特的值取了

到这里基本是秒出思路的，结果pollard p-1那卡了我好几个小时，我还寻思这量级pc应该跑不出才对啊，最后pollard p-1的基础上改改丢服务器上也就一个半小时，还行

import sympy

p25=sympy.prime(1077872)
p30=sympy.prime(105097566)

import gmpy2
from tqdm import tqdm
import random

n = gmpy2.mpz(
    131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441
)

p1=[]
while p25<2**25:
    p1.append(p25)
    p25=sympy.nextprime(p25)

for i in tqdm(range(100000000)):
    p1.append(p30)
    p30=sympy.nextprime(p30)


ar = p1
random.shuffle(ar)

a = gmpy2.mpz(4)
for p in tqdm(ar):
    a = gmpy2.powmod(a, p, n)
    g = gmpy2.gcd(a - 1, n)
    if 1 < g < n:
        print(g)
        break

后面就求个离散对数，因为p-1光滑ph计算离散对数比较简单

n=131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441
p= 12980311456459934558628309999285260982188754011593109633858685687007370476504059552729490523256867881534711749584157463076269599380216374688443704196597025947
q=n//p
G=GF(p)
y=91561944814950778736488535643520052714900101756544637483800925876319855838327993556442983654484996766433049736153189800056457912285338408230393372558184963346036063617106521919740962726456954911219888157214487326900658606650604294547947205051640436119495039170478782141363198165616660075024383933961325219072058
g=0x10001
m=discrete_log(y,G(g))
print(bytes.fromhex(hex(m)[2:]))

Babyecc

关键在于利用椭圆曲线的表达式拼出一个关于m的高次多项式

一开始自己手动推的那个式子有点阴间，后面利用椭圆曲线的Division Polynomial比较简洁地表示了kG的坐标和G坐标的关系，这东西在复分析里有所体现有时间去学一手证明

利用这个关系最后得到7个12次的关于m的多项式，crt组一下

最后N在7000bits量级，12次的话利用coppersmith method就能算m

ecc=[[172294871449219734798107561390050953188521804048922822821089133469311203282838373380377875439026704763161795744755842077098168865000919622849058673563093367982208461406754463061486548381031910500664522644112851433538900220678158500614358889303283424512500613989230182706150280378108198120547975067586971516137,96364198848848705158285537079110423277195642567952259110364340716064235491391751428297894031158531380770390132279773351908864500464136898214435682124920058680787844361038830281655403525413688733800204992965035715298006768830075744486662160034641936095862260725417156381782604284050422013822430528431227361197,159671991296677830056301471254363341009296510275785264872785778012113694456980363802313449256308519721141732376201460773400245993593482589976204166133901861729668851862460623196007194950257183079347864250025089670843915918257755173390253034175544519724905752818035812997127673241875836037243219829705927834235,12488950718303582218034044014469231718831962762275496002247643231013156969740771432142283441219754679322796472657777272189002660471344265360278317729760143808888761286079001687689905847842340334026140684913862478238950679283842053262939984135114755914484999538131508882930756717834516619580846526035684240079],
[68223999778327454147340278776103578457271553299042143933393545815264609973076698756926443268448068478170652356574414692081569784751387548589991131379073395697581788909441130777261041802381911726085217610218552072019955091687392945670505312431379412346500975722411035854097380678429943612541679085918327184211,17770738203348676394013528065573927253738684355484382993047842078725009503696773096846474265836623641852326745278003624730438619552362071702422399552544609521188676816688215350418290389310564969049643786010837155281593524360805215661135722530433990410365868360692605842180028752038342347560333735922237369889,51098779961961751158122915158869440252746637314825788279336277128573162559246638101764647720433607480890890353266404408862366250798238531789338353122957455620883022785518154730850781795813200407904530871476660815008994170944440212300679621717029986782069464962522083711578039350861054405841275173019925642093,66166716533207612504484627791108393201158937155973610986551130733271280578971089095120371889664007733286220189256643852916722857958108530989447774212301117302384387307543583321894175828438280849870887046734108846642477438172082973113653660108354098554353657568190553303062608249271483295596847725316287446947],
[69746411945288680494756625186262685100915769718266292828317232438356233082561457717802913380129463210508761458218383450347346543878887508111863823958801568318184343480949172473544777648327814945820830887234292193752526478863127665281603760310028685488010810374501002997654985226277837410385612336235789850487,35863433752003593718423506765770617029528142232119703360783695175632253222988642577448933602236360173888236658825392990787632391883856639629797550839027484460834276938254229716767734096212580735483050576113358898294845949901713373921320977266743302353193505619551975822052525104591593619094885194563759053232,61506888586914853748952584136999168853842713393989804770066310267385965404827751126077340386083884094392293257188958096424196079983180753698925334131753282172406136172626322186930421581433234090454842658630759776836012464473239198489670974246600345527623012180678219362862337775047849600595500703273175382703,23074173610330067975119318094549104916729459916683840171011959880097244030586124074672098644510552431454003148712810460842866906744010629559390690271268680358736511730336715376566599109974114862237643003353529058235474898207867615210853332379567542323247567216796697852808056755511484166810776261406177054777],
[141780415980139617437215295846801567101402173619252056827987183835073254193657239443065408850513736462591151306400635298582358011825422183971334048391966413113755453698068836508230018713283240471925059428429812726435729369274579669831159812818547912726106821393226089324568082296082476059592963374588189677903,138746424736113892630456472492513519297466193136237748713651792342224061188757613931171106142936354280921317637536324608330692729231708881940151586955111567707002290198592160272885704125491274615556183787626484145861344784010051348839767532854926101536139055358860932766313079790639566311374298333660022416019,51726115599556454603920201657250521837735902629404616832316825062102322966835183071269936236690928753491837133603376577256803231041384630057026503126306733001505942744679790303330123718230247169888465167921020819210505089269412155033260560735554086852090518639465729269946494965164436190741639956526409236643,109654409762022740069514851260972908347716034747536569205325610944369939818174396230317316392277341065510361034050535743153611162427943916414124861678979771914963184421776448698855312979564147449272690263825911213298037101520123605413049352651130798112394668303713018564867048267647962314886530354112656660927],
[134695529317631291539146989750080778456288116909537330643076226015019499585100645219201149819193483942761047608937632376000045678037096949063251694636264176978864350498001325274216745015187611426633155307352514688833306265311483797036137536737138146820693626589997367590775993967122039778179174477656098285151,5739321199968321627369946084893217618156071099515645889496757563432120794798492968096997315087609783917559636235489259519655394193193715753364023338741839200775528051686566670968651457520145892918236829346679247967821973265175306801170339421046331421835781903320059400232340368113764816537593043564619129091,19673160600783884558420797494268753813890359647736289572838063131711269874000492472573124412257756881986515876284947639879236228461164246881762817017531477201318279812271247605969526804283198993102225186731231831294213792057134691470071907311239898997202853181993775441584378767147396666275272938837258357423,16897173108120076789922861933836017988034034913979337434078332952051799507194042012051980050429727113676699771772883294665409080790164523153924333774353032403848045609407735317482100956730663470698029136912240237112767052198706217408124644467054727063902614284435035076029952831418531957452256906889271788660],
[108631997335203066432695467871764765359535346338288176017618709868611883736328359105943651466896885704753893021031355220198313022607240746637026558990572053372001779938093596718948899761553876823305187704800253652009189892280549587130446638129290899670752310731109594745013563422110453795138476510927065537819,53186625650395498513439276601148324935331371411190607911833993964075202667438243234505710009859940105805328184291501428682891944699728069011511208448749132382024172290085402121472873185791975075398049469908097240414598661986593060452061227701643807521128142747260925759613091495839896971643248717676885197644,52709509084184104167650277788945043330126097533959255658173397630643774367938336071212214281041856314502929120225540280940224731284318314188334401609349175298441766962844025460361899368481713758076026229654035313132750449381123295594073954550981806651354410007449428669257683889916088487170632832744327614463,100260604505216418319923489428146996468156773172005794829064325549637959539041791314163531463726947409321908377241081956519122122262033227578640846072409813184989637914837945813897560451295053865278594114754492413312832734981399784589146893658856979887630033309457853967429746353718137461785133619446282493126],
[107338361645955025621587108367500347348984102219339572552748381028739611029946302714920823684765311935547487453509535204574142858361737866739285841603885839441733030101476343149903190982542554096941815202891147725076023628145124709929620451309674856615713933442851718371615889591966077523086598769484929332367,100872379615239890056528793994805290254429184626178615179949021889055871474237228059318594996850343091819482928969268211528584474928620075395005093777657472616646086984808630643337673511907312828907027299569420774094158785966357193601409625830742669863851550399504009908003166662860318527135193218238780676800,52637469044026090728662077516653409825725186092147185410215323273449329656983845536711234923756687817513771235055035977388966611329613167758082577958758423429648769821507972676781188078791048118663252233256924489724994317727922287107822238963194994782575166160292521918653409858431855957865223409101119244152,57971958593516466763891620734062821771076712450708456876484562483981622035231519724366540336500884101001407519929342324257929081898526022577405465205118192907601214300359691638071300661277784420068767639904239138656962018735555155063349452232501292852176876546222413194770858197241287367089881969293760207489]]


coeff=[]
N=[]
for i in range(len(ecc)):
    n,a,b,y=ecc[i]
    N.append(n)
    E=EllipticCurve(Zmod(n),[a,b])
    PR.<x>=PolynomialRing(Zmod(n))
    w2=(E.division_polynomial_0(4)//2)^2
    f2=64*y^2*(x^3+a*x+b)^3
    f=f2-w2
    coeff.append(list(f))
    

final=[]
for i in range(13):
    tmp=[]
    for j in range(7):
        tmp.append(int(coeff[j][i]))
    final.append(crt(tmp,N))
    
#print(final)
NN=prod(N)
PR.<x>=PolynomialRing(Zmod(NN))
f=PR(final).monic()

print(f.small_roots(X=2^350,beta=1,epsilon=0.03))

总的来说n1虽然卡在了考试周，但是密码就三题，两天的比赛实际也就打了一天，还空出一个下午预习了一下没听课的概率论，挺好（￣▽￣）