CTFshow-大吉大利杯-easysignin

​ 考察的是对LCG伪随机算法的攻击。

​ 题目：

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from random import getrandbits
from secret import flag

def genpq(k):
    while True:
        p = getPrime((k + 3) // 4)
        q = getPrime((k + 3) // 4)
        if ((p ** 2) * (q ** 2)).bit_length() == k:
            return (p, q)

def genseq(t, k):
	x = getrandbits(k)
	y = getrandbits(k)
	r = []
	r += [pow(x * getrandbits(k)+y, pow(getrandbits(k), t - 1, t), t)]
	for i in range(len(flag)):
		r += [pow(x * r[i] +y, pow(getrandbits(k), t - 1, t), t)]
	return r

(p, q) = genpq(2021)
e = getPrime(0x0123)
r = [genseq(p, p.bit_length() // 4), genseq(q, q.bit_length() // 4), genseq(e, e.bit_length() // 4)]
c = pow(bytes_to_long(flag), e, 2021 * p * q)

out = open('output.txt','w')
out.write(str(r) + "\n")
out.write(str(c) + "\n")
out.close()

​ 其实就是RSA套上了LCG进行混淆，看起来复杂实际上考点就两个：

1.费马小定理：题中r += [pow(x * r[i] +y, pow(getrandbits(k), t - 1, t), t)]

这里指数部分可化简为1

2.对LCG算法的破解：

def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)

完整脚本：

import numpy as np
from functools import reduce
from math import gcd
from gmpy2 import *

output = [[52410740454341322584968668119249347590637310744053575667199658377254616720, 645233054655774190743329734650633925675658559407235845892000719418629264735950925156778060047916782135118939609, 7943518660704895786672594284269647711181509726633514226380530196425485458539625694575495231887385619012015881286882728587606040595061922764546504652, 88914058098690563261741069739196350367736459872642989654182096322219071679192700322294625591039910568014594162793682719562807511893126265269018965631844, 21848556616661858554457567702772141873495700440964466396641152668611914726571047215318351614761015187840557741595013435098462212054082613351365353879971, 30981990147740324963531127581242040452010812929397936350977330949621677682914852118175610889739709323337510806201042485424717012639070029274069982697770, 86391152218016366813847004247404056131417771687236374092616383814217301192122912423701248555978593644222324385731750478659656390099667206731986826034783, 11919788822817325862607995189694676040563253448913899451812469694262245578863190210002110273555634880385761984875510033893001873388959689185144905903209, 113172562380439676720883790279148843121957456418188815624366983390069987176782078966213846939157552371083567965339468376209438408527447055279432563530293, 53639431322349477360106465790490257401135940987536122273392905439789302677727263369595453217090741732679101465032774237786279512056854438308525173657159, 66494591146164538399359207417261107297618965139951036147349388185500471848417939882942051000401169375606555137676945793825997569250321049050064328504686, 68140755777619578564543055029117317295128399240486821374257706188512954130154120098052147911199011456619478205381967508904616755976025013771737828736712, 108937156773321279370931816069281780172829105656866216917516598661018254865761711673453882295854673659374303771527203182421483883387191105457655039518598, 23851657909638071121522950452985193121203677553882352681904178324157544934072951198267420469049884225406011127813710965228771378971223671119499320807527, 73593420351924535735583383759106213752911143688405196033083181161847427289244164307112764704106027032275168673202117613094614344445994185733167048206528, 45149231454111577928491035214773110610124553323394642764742046515465337002110008680672172596244297975180829797354612671475605687567668633260989146225109, 116595530380208734174324933018691232247236449545224536610877958513488572395417607779848679300427540247845082936159111075084099286531721388893818985053741, 19184570673197822395630076591747812314740067696017031829688067440093395269633819900129824384419564803863978782409207577313654883568996185370309615089861, 25053641421607032412936267237167725716755999385160231284419862285097826856694410270421890957270689086653085525341558101625176940863016775431803134278503, 41834644301798766586022917842507064432100240754373142283841634039601045968196848660974947416021443814036134492045552003431910969249042558378746090903740, 42360644234440625880638052651286919014389438067342750959116570502193321560916125003972414759569882508574236473191565962375571182326447121493190045921270, 64154129476091746233508446729279257596903523952542574303253450285299398583980541526259161563202739149004027272968609086796202499698823078817922156242997, 99743770056582602741303337738692194013086027384260039696324929460010638859447328004451799213553786836333122482774819971466325395235923612135604232226628, 76016751544879152402468315780586583194677362762856804802274327372452749909986720770385321555358806909857936245178757512784557916380481731086991902054287, 15290970738221187280390322268161848800499662337983876912254205399494853703975899722962615773380166218671937854689533200852650284347709468624816742506301, 67706974286610751556509787688743881517790029217389913481852566524040229236517365403017047098395951124264255110450504690606926248507428249271556983456901, 93639585966460526678788701909900876014525038540391772469992121354765056693895744954209300307081001946602586071602887248893957063725982565677570972746179, 116294621911461475477765026959041413149677852360214402280735648748333959155194969755168263936256009261138274595240480200664019902568187683340477743969899, 5600077388578735042597674074656979994549617482972881863164687525745536334190390401329680675467385619222535929475803379568900871335069384301033734714233, 14950370510302209746655108744292059719774565235701177358607157704462080787582712898381047410531181256769171281519411806803555715962755361346294970645323, 62016127245313515166454506817734613861723408949410899879216139989641932810248154680978274902855232651990299832297039642288310178403863342787840550299197, 95333439043968773649754476810195845118762991943266271403726184079242047672417932848967803488781971181275041399864016152589549446967782464066482170680045, 17892190659451591126424119305367671928739240611597727166543577571172322192576331228580357825811249660239169745390013910560069896203797045063231158722853, 47343585379646662714119978325645155712476914243757156114505021559030784519828048323795389199684946739451189942398561417829509539613791387644014640880892, 107633502313698058424938275622569640009485699854002361851653372416279664993830018051561865544743074946977906999458321566411251984151075748983779536801656, 101301834848265959280691115298109056299094420476120335636075492785328213139655230146061664228486248771534280699591814762729915638378841230330876525933001, 100833383873897711880618620396289395792480753105857884143070890861779172346713570088651208648247678032376842604846315923312830531728252064463150986767877, 110832079086180425600051267498601847526388754584982689270788472799404147017261513262539159424820032777910677631796771424828022748042489660903717952947232], [2447835208216480089797117166098772864739983439147154550843410133502162338263, 90343453249141616309012786446354427397838634661038147051928857871447909510509540184081882802706067411363905232391, 3334350089247517867244794106926436317086273858623518082485947115508154733111001565093191192674670220618972600184165291699923904558749567306156634412295, 10773127238350735566139610265473489634284355749344684347913928639165091011956627111779426812064973544315989779523475733083567151499479793829671206141097, 106073688178033729190829682109679728245170052489478284990130508152039157863313154674078420619615011691032124222115566415769268517103742200043347846746310, 96864656966701608190452551924897023075560536848477610188768188296307194880004203630087264191421619540332532988322143583373922117130397679868254621842062, 90007570555125944092169218313738703993888121021783637142913909308099775085919518984873236408360228986382651525244328621860786089655176559888337945973265, 107604402646950221603694740182904829452610405361494187112972298194020162739490546852179057650360974702490340526819923399009740841491688354483369514169504, 106563280130150122326814032245025170948640642468357539265829858841580809022713867834571254297385660279367044782111285768058114284965175416454533853149098, 34006794372719255946701440846013876868985083446980545795344603308580913114300387951211231095472417358606631528579058832071833342645392417576288348171281, 80528690688989385531407273709213599547356208780618772147048236656262530606555256335153687882045380456243914208416285214393577589279953053395148801048043, 25252035922809872666372710839612084651799975462368368568421254228924839144802392424596779526739759011515745889793921767279843129898429087648706961214380, 15441075054379206603678761656461990005728026633190896788589499872488783507420374230165723864117983219469482787021780166107230849440690930291658692943884, 15730255840343160294128109470006774677678596243801516284827627241776907423825237162176372972699529694206547624329200148008905292241372763696643556851248, 15929374919958330762187534489183857327423262543417435665674052288372574077203981789863180537536922526152815069819616552018951188431418135256962942313150, 16820416513541190327907989962230541088691747266081952862738221010557935254064045592670849585275377539144509827653431170474288972399346359112627171936199, 62613123636486933874885881624168137103745407796444871779926315982802027799075166745074790838012194635812853433064138182942124531618582978708688026203712, 103390317097626211538390057925702534478424865400956004756449501914108837524902468766472576617059468680745338232757547345497585919880616072977553233278603, 106855090961917607608766903030826427305834559006355051082927925151921938627824191628649167300491312597092422279212561689251186535550087727802277317012637, 78550566353218314794723213322674271780550941969941432645092204751089489784529040122660556916516795686398814802277195824477145440164288404226182667432413, 27234374989834250512863591479223580820709377656219659243546791666422683600672138485672126972130292224970890443705416445427654052263167668188984214509496, 89073500384217027637576686609574923520864474465437796981228200517382920934009159891695058762467754821583073917774195612915842601271956467375250874741115, 81523221328096138331223676561475793372150203835133425580501094268867250067873677785078977441798107146380161414152017043957710432372886446496269471249870, 69426635873092086451473939772373894337793035157602866886753621226137855012060402481656332348663588598120734258884064385818693263157949512108768237653037, 27038496127031393485308453098136903958592822859537990682349040311778748501331008447014951690343425476063063582655448477055880499291781315998134395062551, 86563190395140161836966058609094941013946825669471943800850341447296711952143605563471041765702929391516506170236643633037511742900440430412347138373811, 92654519757605791295431607106260304699360787251056766515059747102627521170620749248095214607497002308663852187075958446074495640666063038994344066529674, 47978472743885278893083282341878167737725647616340703972452890584651298269018115725710882998002541867355534242320731285507237225498136712897684035221694, 33937234952409141712999986890445630797610786424992916483378338039398873916932446399890479122582956874435985731634172335771866950539140459057793782237502, 53536716653947884337358943672946218345105772801556349741322007215929226375220858833185514799016429985979192211191664179249403984470298515297769983151764, 15571885519410418984279068975979417469158262995629377377010899727496518373589643663028156863791907436837054446354508286361951842342722672331011023846114, 8566869430523038374329005968331909880668039196226700509945801110864252361948997146164771896223981284735805514278445995598366675322977971551419425480644, 87201260842977762054169640055047984836895338107976452298751798557901196013452620843946503586203236027871183035720513488012632267170999498276073312805571, 93478630791498129840635935563160804999341438068212212075961484875554801063436616116564312106399142481823172612186464441144737797880760682581757444561694, 49399628737188601660367894914908547591976252279392032109588827791264737386179351022649986152248431169393115396754709411287013944596327999564120047443685, 401770084546389936795883960043586247087806968600408302529922285961914019164988332998528995717095956973083747814499516267750284263835592854038001543364, 46910295459783203906544465622227903475837618852453968036856768892034422511892075866806031498301570602549864578109096480551648362399275135770250479266764, 48705341969973174964195737555908215932127208480896065769947732952516004887948769345944422825151845846335939723147282687407339303320406462649862333812892], [6763996718934951285742307562806923397006813, 12234833447991510153841494781985313133191586854789667980564533023, 22130576894138701986742918639431233979778270965194566122306861346111716828577556403873, 767648503612570945278792619619046535101078814202096337589566648572901378566441587067065, 1534503080514914991237881845264698854398689474324594013087679222396116209460382272347120, 2150152040945137216175051477345156832872965887696888090617763887196376039836211151684155, 1519134084444926105081859598135660300537196230332783741163873836023160842189452416751204, 1347961026269871555909121507968616952100851882185690586872363417766328195659354367286160, 442978203022900661788725058674237344919172289937224290573991574448751808619506704123728, 434277065671750016380827889451816552550232352950909430034013985469154609260218730764780, 979776898630843046146074197140740184861751729514455753655622904091278621814340310325052, 873700620112565719323179396419879070723310944684570011051348198205453537590517739575294, 1256514485942478003559638390025523283241250878990443282316967845337571713994674756627249, 2201413023234946734277012190477530998161056783942361564091571454780425152722167887757333, 15845440233510397242131879469914499447138153273633842521183302623397377025857347058355, 719557135712047144341175773587928323041035301800224566640992208827132114843710118060603, 1872194680805780497350808471632655890088399919927439303351392835028632946050942049128363, 739802156645251387441611149162232326760167809822024988834688224156162966157182526727210, 1842345264759627182982545223023325564813297247358347573262929227611626782102112032498792, 1942056684591589139535850561429570147021382203103121319949566652649463471174580278445972, 1897401671012077468168242201956275317342401618250346254943410859299471001683176665446266, 1299697210304599531296837763293611409445703982993464696432211710136915756408352763838420, 6339661487999740913576932261380541287960678716377148820725064627689077214923145744267, 206550580254594047163709231196572177167911612047377521986355302588778287613331054094422, 2095017194382050543451996020322766986862239168048229828922060511851698524762340797229358, 38154091093834482476428418031816301638508654861013053691521551593888386192530215738249, 2312527000380201589293545236295238368648424299462645212556813668113451665892155924195549, 1148055457422644367319939159612923263814575289811148258779972071041630980150900639103033, 2491032359438353539795070569649180009224077260857699946936305612971624383446047213147218, 2502865604540348808929226301472051722005592649019284150593000357524824393775392671519130, 1039938101331801857780518763744667966269026413223284682004343257200589049680488254035897, 316947919834210211954441725158411391798247265696200080865972078867990121934703299224598, 1191200775168680784071665067183230700343262160056248368421562785231813797955113569864397, 517875043776615303660143356495634794257910735766828738806709874383193521216795724710570, 177783588672600341630231835251624651899982858825356048074013206591129692021093027549523, 1181655045918151017173609506041984644632154476633196738728202200703641104893529622554198, 1943728872455114467893276648701066972260927692980375525686315254866764954534482612584812, 841323196734187035327534237852681191366390226431490238525430672327199713070166890155539]]
output = np.array(output)

def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * invert(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)

rp = output[0]
rq = output[1]
re = output[2]

c = 1499341850116033218583322015832654376326982200720069022052964940686970117688218295301399005244875933100636608594036976589026918517646244220826168516373612155557984806411945784862108964553911520434368098212111129654894447128360717210621466898152738161667124194644244479881039031313468828783882375812512993823

xp, yp, p = crack_unknown_modulus(rp)
xq, yq, q = crack_unknown_modulus(rq)
xe, ye, e = crack_unknown_modulus(re)
print(p)
print(q)
print(e)

for i in (0,pow(2,1000)):
    if pow(i,e,2021*p*q) == c:
        print(i)