首页 比赛

# DASCTF NOV X 联合出题人 2022 年度积分榜争夺赛！

# Crypto

# easy_hash

# 题目

+++

from Crypto.Util.number import bytes_to_long, long_to_bytes
from zlib import crc32
from secret import *
P = 93327214260434303138080906179883696131283277062733597039773430143631378719403851851296505697016458801222349445773245718371527858795457860775687842513513120173676986599209741174960099561600915819416543039173509037555167973076303047419790245327596338909743308199889740594091849756693219926218111062780849456373
def myhash(x):
    res = []
    end = b""
    bytescipher = long_to_bytes(x)
    a = bytescipher[:len(bytescipher) % 8]
    res.append(a)
    res.append(long_to_bytes(crc32(a)))
    t = (len(bytescipher) // 8)
    bytescipher = bytescipher[len(bytescipher) % 8:]
    for i in range(t):
        a = bytescipher[i*8:i*8+8]
        res.append(a)
        res.append(long_to_bytes(crc32(a)))
    for i in res:
        end += i
    res = bytes_to_long(end)
    res = (res + (res >> 500)) & 2**(500)-1
    return res
def encode(pt):
    a=[]
    b=[]
    a.append(myhash(pt))
    for i in range(3):
        a.append(myhash(a[i]))
    for j in range(4):
        secret=(a[0] + a[1] * a[j] + a[2] * a[j] ** 2 + a[3] * a[j] ** 3) % P
        b.append([a[j],secret])
    return b
pt = bytes_to_long(flag.encode())
FLAG=encode(pt)
print(FLAG[1])
#[1768672211043417187765307394749760760531160781992300779145800061219666992833602547480090118225665457075744297987672863699370162614965380859290914620736, 89139545215288033432210221492974990584987914397112840989583439688211128705545477536596587262069032020212762581490561288493533363888589066045095054475929099275247145877699370608950340925139625068446642116123285918461312297390611577025368805438078034230342490499137494400676347225155752865648820807846513044723]

+++

通过a1a_1 求得a_

a0=(secret−a1∗a1−a2∗a12−a3∗a13)a_0=(secret-a_1*a_1-a_2*a_1^2-a_3*a_1^3)%p

后面感觉要逆 myhash

但是我转字节之后就出来了

# exp

from Crypto.Util.number import *
from zlib import crc32
def myhash(x):
    res = []
    end = b""
    bytescipher = long_to_bytes(x)
    a = bytescipher[:len(bytescipher) % 8]
    res.append(a)
    res.append(long_to_bytes(crc32(a)))
    t = (len(bytescipher) // 8)
    bytescipher = bytescipher[len(bytescipher) % 8:]
    for i in range(t):
        a = bytescipher[i*8:i*8+8]
        res.append(a)
        res.append(long_to_bytes(crc32(a)))
    for i in res:
        end += i
    res = bytes_to_long(end)
    res = (res + (res >> 500)) & 2**(500)-1
    return res
a=[0,1768672211043417187765307394749760760531160781992300779145800061219666992833602547480090118225665457075744297987672863699370162614965380859290914620736]
for i in range(1,3):
    a.append(myhash(a[i]))
P = 93327214260434303138080906179883696131283277062733597039773430143631378719403851851296505697016458801222349445773245718371527858795457860775687842513513120173676986599209741174960099561600915819416543039173509037555167973076303047419790245327596338909743308199889740594091849756693219926218111062780849456373
secret=89139545215288033432210221492974990584987914397112840989583439688211128705545477536596587262069032020212762581490561288493533363888589066045095054475929099275247145877699370608950340925139625068446642116123285918461312297390611577025368805438078034230342490499137494400676347225155752865648820807846513044723
#secret=(a[0] + a[1] * a[1] + a[2] * a[1] ** 2 + a[3] * a[1] ** 3) % P
a0=(secret- (a[1] * a[1] + a[2] * a[1] ** 2 + a[3] * a[1] ** 3)) % P
print(bin(a0))
a0=long_to_bytes(a0)
import string
print(a0)
table=string.ascii_letters.encode()+b'_{}'+string.digits.encode()
print(table)
for i in a0:
    if i in table:
        print(chr(i),end='')
# LCG
# 题目
from Crypto.Util.number import *
key=b'*************'
key=bytes_to_long(key)
key=bin(key)[2:]
n=getPrime(256)
a=[getPrime(256)]
for i in range(1,len(key)):
    a.append(a[i-1]*2)
b=getPrime(256)
m=[]
for i in range(len(key)):
    m.append((a[i]*b)%n)
s=0
for i in range(len(key)):
    s+=m[i]*int(key[i])
seed=s
a = getPrime(300)
b = getPrime(300)
n = getPrime(300)
output = []
for i in range(10):
    seed = (a*seed+b)%n
    output.append(seed)
print("output = ",output)
print('m=',m)
state=int(key,2)
a=getPrime(256)
b=getPrime(256)
c=getPrime(256)
for _ in range(10**10000):
    state = (a * state + b) % c
flag=b'****************************************'
state_md5=hashlib.md5(str(state).encode()).hexdigest()
xorflag=xor(flag,state_md5).hex()
print('a=',a)
print('b=',b)
print('c=',c)
print('xorflag=',xorflag)
LCG 加背包（cv 库）
# exp
import hashlib
from Crypto.Util.number import *
from functools import reduce
from gmpy2 import *
from Crypto.Util.number import *
output =  [75581294523880849612962675076574164955427439308298754836702542570856707873339581806556114, 85105032146983524265511965363979041936757881362506442483720291395014453678757599185295866, 1135521205967352800446368309480529634045225881261100886117662161359310082444102071893527191, 668602662320826002160475166323016971968419541611162501120982012317608523771962990634779874, 649673553234341629614052928960182629959348742983379959653724041939165898600067312959677865, 785853955591839090537858092210736716046894245185520583713505441606094906159642640920286905, 937799570303158165818350743257433287791556030352377438071495081189542968310256239806349207, 734514754865608924980327625447363286114899547828404532253101460271494241963897226149955073, 1106313725444442262780946046218124519471559148520571880678416934586056489046936771811070897, 8768152099561586039808874499029856564696410477579827751292882367683300035228537162519939]
m= [72110328606337761986452574632319920368225905906258123752738204764660440229296, 54011682421724526639264309053337133761455956763651742732220904522794415369243, 17814390052498055944887777895371560547916058478438980691186304039062365649137, 35628780104996111889775555790743121095832116956877961382372608078124731298274, 71257560209992223779551111581486242191664233913755922764745216156249462596548, 52306145629033450225461382951669777408332612778647340756234927305972460103747, 14403316467115903117281925692036847841669370508430176739214349605418455118145, 28806632934231806234563851384073695683338741016860353478428699210836910236290, 57613265868463612469127702768147391366677482033720706956857398421673820472580, 25017556945976227604614565324992075758359109018576909140459291836821175855811, 50035113891952455209229130649984151516718218037153818280918583673642351711622, 9861252992953913084817421088665596058440581025443131788581662340758238333895, 19722505985907826169634842177331192116881162050886263577163324681516476667790, 39445011971815652339269684354662384233762324101772527154326649363032953335580, 78890023943631304678539368709324768467524648203545054308653298726065906671160, 67571073096311612023437897207346829960053441358225603844051092445605348252971, 44933171401672226713234954203390952945111027667586702914846679884684231416593, 89866342803344453426469908406781905890222055335173405829693359769368462833186, 89523710815737909519298976602261104805448255621482306886131214532210460577023, 88838446840524821704957112993219502635900656194100108999006924057894456064697, 87467918890098646076273385775136298296805457339335713224758343109262447040045, 84726862989246294818905931338969889618615059629806921676261181211998428990741, 79244751187541592304171022466637072262234264210749338579266857417470392892133, 68280527584132187274701204721971437549472673372634172385278209828414320694917, 46352080377313377215761569232640168123949491696403839997300914650302176300485, 2495185963675757097882298253977629272903128343943175221346324294077887511621, 4990371927351514195764596507955258545806256687886350442692648588155775023242, 9980743854703028391529193015910517091612513375772700885385297176311550046484, 19961487709406056783058386031821034183225026751545401770770594352623100092968, 39922975418812113566116772063642068366450053503090803541541188705246200185936, 79845950837624227132233544127284136732900107006181607083082377410492400371872, 69482926884297456930826248043265566490804358963498709392909249814458335654395, 48756878977643916528011655875228426006612862878132914012562994622390206219441, 7304783164336835722382471539154145038229870707401323251870484238253947349533, 14609566328673671444764943078308290076459741414802646503740968476507894699066, 29219132657347342889529886156616580152919482829605293007481936953015789398132, 58438265314694685779059772313233160305838965659210586014963873906031578796264, 26667555838438374224478704415163613636682076269556667256672242805536692503179, 53335111676876748448957408830327227273364152539113334513344485611073385006358, 16461248562802499564273977449351747571732450029362164253433466215620304923367, 32922497125604999128547954898703495143464900058724328506866932431240609846734, 65844994251209998257095909797406990286929800117448657013733864862481219693468, 41481013711468999180550979383511273598863745186032809254212224718435974297587, 82962027422937998361101958767022547197727490372065618508424449436871948595174, 75715080054924999388563077322742387420459125695266732243593393867217432100999, 61221185318899001443485314434182067865922396341668959713931282727908399112649, 32233395846847005553329788657061428756848937634473414654607060449290333135949, 64466791693694011106659577314122857513697875268946829309214120898580666271898, 38724608596437024879678314416943008052399895489029153845172736790634867454447, 77449217192874049759356628833886016104799790978058307690345473581269734908894, 64689459594797102185072417456469325234603726907252110607435442156013004728439, 39169944398643207036503994701635943494211598765639716441615379305499544367529, 78339888797286414073007989403271886988423197531279432883230758610999088735058, 66470802803621830812375138595241067001850540013694360993206012215471712380767, 42732630816292664291109436979179427028705224978524217213156519424416959672185, 85465261632585328582218873958358854057410449957048434426313038848833919344370, 80721548474219659830796907705415001139825044865232364079370572691141373599391, 71234122157488322327952975199527295304654234681600223385485640375756282109433, 52259269524025647322265110187751883634312614314335941997715775744986099129517, 14309564257100297310889380164201060293629373579807379222176046483445733169685, 28619128514200594621778760328402120587258747159614758444352092966891466339370, 57238257028401189243557520656804241174517494319229516888704185933782932678740, 24267539265851381153474201102305775374039133589594529004152866861039400268131, 48535078531702762306948402204611550748078267179189058008305733722078800536262, 6861182272454527280255964197920394521160679309513611243355962437631135983175, 13722364544909054560511928395840789042321358619027222486711924875262271966350, 27444729089818109121023856791681578084642717238054444973423849750524543932700, 54889458179636218242047713583363156169285434476108889946847699501049087865400, 19569941568321439150454586955423605363575013903353275120439893995571710641451, 39139883136642878300909173910847210727150027806706550240879787991143421282902, 78279766273285756601818347821694421454300055613413100481759575982286842565804, 66350557755620515869995855432086135933604256177961696190263646958047220042259, 42492140720290034406350870652869564892212657307058887607271788909567974995169, 84984281440580068812701741305739129784425314614117775214543577819135949990338, 79759588090209140291762642400175552593854774179371045655831650631745434891327, 69310201389467283249884444589048398212713693309877586538407796256964404693305, 48411427987983569166128048966794089450431531570890668303560087507402344297261, 6613881185016140998615257722285471925867208092916831833864670008278223505173, 13227762370032281997230515444570943851734416185833663667729340016556447010346, 26455524740064563994461030889141887703468832371667327335458680033112894020692, 52911049480129127988922061778283775406937664743334654670917360066225788041384, 15613124169307258644203283345264843838879474437804804568579215125925110993419, 31226248338614517288406566690529687677758948875609609137158430251850221986838, 62452496677229034576813133381059375355517897751219218274316860503700443973676, 34696018563507071819985426550816043736039940453573931775378216000874422858003, 69392037127014143639970853101632087472079880907147863550756432001748845716006, 48575099463077289946300865991961467969163906765431222328257358996971226342663, 6941224135203582558960891772620228963331958481997939883259212987415987595977, 13882448270407165117921783545240457926663916963995879766518425974831975191954, 27764896540814330235843567090480915853327833927991759533036851949663950383908, 55529793081628660471687134180961831706655667855983519066073703899327900767816, 20850611372306323609733428150620956438315480663102533358891902792129336446283, 41701222744612647219466856301241912876630961326205066717783805584258672892566, 83402445489225294438933712602483825753261922652410133435567611168517345785132, 76595916187499591544226584993664944531527990255955762097879717330508226480915, 62982857584048185754812329776027182088060125463047019422503929654489987872481, 35756740377145374175983819340751657201124395877229534071752354302453510655613, 71513480754290748351967638681503314402248791754459068143504708604907021311226, 52817986717630499370294437151703921829501728460053631513753912203287577533103, 15426998644310001406948034092105136684007601871242758254252319400048689976857, 30853997288620002813896068184210273368015203742485516508504638800097379953714, 61707994577240005627792136368420546736030407484971033017009277600194759907428, 33207014363529013921943432525538386497064959921077561260763050193863054725507, 66414028727058027843886865051076772994129919842155122521526100387726109451014, 42619082663165058354132889890850839013263984635445740269796695768925753812679, 85238165326330116708265779781701678026527969270891480539593391537851507625358, 80267355861709236082890719352100649078060083492918456305931278069176550161367, 70325736932467474832140598492898591181124311936972407838607051131826635233385, 50442499073983952330640356774494475387252768825080310903958597257126805377421, 10676023357016907327639873337686243799509682601296117034661689507727145665493, 21352046714033814655279746675372487599019365202592234069323379015454291330986, 42704093428067629310559493350744975198038730405184468138646758030908582661972, 85408186856135258621118986701489950396077460810368936277293516061817165323944, 80607398921319519908597133191677193817159066571873367781331527117107865558539, 71005823051688042483553426172051680659322278094882230789407549227689266027729, 51802671312425087633466012132800654343648701140899956805559593448852066966109, 13396367833899177933291184054298601712301547232935408837863681891177668842869, 26792735667798355866582368108597203424603094465870817675727363782355337685738, 53585471335596711733164736217194406849206188931741635351454727564710675371476, 16961967880242426132688632223086106723416522814618765929653950122894885653603, 33923935760484852265377264446172213446833045629237531859307900245789771307206, 67847871520969704530754528892344426893666091258475063718615800491579542614412, 45486768250988411727868217573386146812336327468085622663976095976632620139475, 764561711025826122095594935469586649676799887306740554696686946738775189601, 1529123422051652244191189870939173299353599774613481109393373893477550379202, 3058246844103304488382379741878346598707199549226962218786747786955100758404, 6116493688206608976764759483756693197414399098453924437573495573910201516808, 12232987376413217953529518967513386394828798196907848875146991147820403033616, 24465974752826435907059037935026772789657596393815697750293982295640806067232, 48931949505652871814118075870053545579315192787631395500587964591281612134464, 7654924220354746294595311528804384183634530526398286227920424176036759179579, 15309848440709492589190623057608768367269061052796572455840848352073518359158, 30619696881418985178381246115217536734538122105593144911681696704147036718316, 61239393762837970356762492230435073469076244211186289823363393408294073436632, 32269812734724943379884144249567439963156633373508074873471281810061681783915, 64539625469449886759768288499134879926313266747016149746942563620123363567830, 38870276147948776185895736786967052877630678445167794720629622233720262046311, 77740552295897552371791473573934105755261356890335589441259244467440524092622, 65272129800844107409942106936565504535526858731806674109262983928354583095895, 40335284810737217486243373661828302096057862414748843445270462850182701102441, 80670569621474434972486747323656604192115724829497686890540925700365402204882, 71132164451997872611332654436010501409235594610130869007826346394204339320415, 52055354113044747889024468660718295843475334171397233242397187781882213551481, 13901733435138498444408097110133884711954813293929961711538870557237962013613, 27803466870276996888816194220267769423909626587859923423077741114475924027226, 55606933740553993777632388440535538847819253175719846846155482228951848054452, 21004892690156990221623936669768370720642651302575188919055459451377231019555, 42009785380313980443247873339536741441285302605150377838110918902754462039110, 84019570760627960886495746679073482882570605210300755676221837805508924078220, 77830166730304924439350653146844258790145355371737006579188170604491383067091, 65451358669658851545060466082385810605294855694609508385120836202456301044833]
a= 102146678855348749881681741830301892566150942749854546938156269348575567682569
b= 57926598868103510549704115342815226386495366694945712679089221082045615713293
c= 79112540456632613121737537841885533313599936328220061653608162113976717833173
xorflag= 0x2079677330734e7d07116d73543d03316c6501555c02403b7201080612101049
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
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]) * modinv(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)
# N[i+1] = (A*N[i]+B) % M
# A,B,N 均未知
sequence = []
modulus, multiplier, increment = crack_unknown_modulus(output)
multiplier=multiplier+modulus
increment=increment+modulus
print('A = '+str(multiplier))
print('B = '+str(increment))
print('N = '+str(modulus))
d=[]
seed=(output[0]-increment)*invert(multiplier,modulus)%modulus
print(seed)
for i in range(10):
    seed = (multiplier*seed+increment)%modulus
    d.append(seed)
print("output = ",d)
print(d==output)
a=[1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1]
x=''
a= 102146678855348749881681741830301892566150942749854546938156269348575567682569
b= 57926598868103510549704115342815226386495366694945712679089221082045615713293
c= 79112540456632613121737537841885533313599936328220061653608162113976717833173
xorflag= 0x2079677330734e7d07116d73543d03316c6501555c02403b7201080612101049
state=1459518099080641908882248947391577149455413355
s=[state]
for i in range(3):
    s.append((a*s[i]+b)%c)
# f(n)=f(n-1)*a+b
#[a,1][0,1]*[f(n-1)][b]=[f(n)][b]
#[a,1][0,1]*[f(0)][b]
# m = Matrix(Zmod(c), [[a,1],[0,1]])
# v=vector(Zmod(c),[s[0],b])
# print(m^(10**10000)*v)
f=5413978693489756582509930284917854732906886271552898511650182850401353715151
state_md5=hashlib.md5(str(f).encode()).hexdigest().encode()
state=bytes_to_long(state_md5)
print(state)
print(long_to_bytes(xorflag^state))
 更新于   阅读次数  次