2023-ISCTF-wp-crypto

这个比赛也没有参加，要到了附件写写wp。

夹里夹气

题目：

嘤嘤？嘤嘤？ 嘤嘤？嘤嘤？嘤嘤？ 嘤嘤嘤嘤嘤？嘤嘤嘤嘤嘤？ 嘤嘤嘤 嘤嘤？嘤嘤？嘤嘤嘤嘤嘤？ 嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤？嘤嘤嘤嘤嘤嘤 嘤嘤？嘤嘤？嘤嘤？嘤嘤？ 嘤嘤？嘤嘤？嘤嘤？ 嘤嘤嘤嘤嘤？嘤嘤？嘤嘤？ 嘤嘤嘤嘤嘤？嘤嘤？ 嘤嘤？嘤嘤？嘤嘤？嘤嘤？ 嘤嘤？嘤嘤？嘤嘤嘤嘤嘤嘤嘤嘤？嘤嘤嘤 嘤嘤？嘤嘤？嘤嘤？ 嘤嘤？嘤嘤？嘤嘤嘤嘤嘤？ 嘤嘤？嘤嘤嘤嘤嘤嘤嘤嘤嘤 嘤嘤？嘤嘤？嘤嘤嘤嘤嘤嘤嘤嘤？嘤嘤嘤 嘤嘤？嘤嘤嘤嘤嘤嘤嘤嘤嘤 嘤嘤嘤嘤嘤？嘤嘤？ 嘤嘤嘤嘤嘤？ 嘤嘤？嘤嘤？嘤嘤嘤嘤嘤？ 嘤嘤？嘤嘤嘤嘤嘤嘤嘤嘤嘤 嘤嘤？嘤嘤？嘤嘤嘤嘤嘤嘤嘤嘤？嘤嘤嘤 嘤嘤嘤嘤嘤？嘤嘤？ 嘤嘤？嘤嘤嘤嘤嘤嘤嘤嘤嘤 嘤嘤嘤嘤嘤？ 嘤嘤？嘤嘤？嘤嘤嘤嘤嘤？ 嘤嘤？嘤嘤嘤嘤嘤嘤嘤嘤嘤 嘤嘤嘤嘤嘤？嘤嘤？ 嘤嘤嘤嘤嘤嘤 嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤？嘤嘤嘤

和moectf的猫言喵语一样，按照如下方式做替换：

嘤嘤？ -> .
嘤嘤嘤 -> -

得到：

.. ... -.-. - ..-. ----.-- .... ... -... -.. .... ..--.- ... ..-. .--- ..--.- .--- -.. -. ..-. .--- ..--.- -.. .--- -. ..-. .--- -.. -- -----.-

然后解摩斯密码：

ISCTFHSBDH_SFJ_JDNFJ_DJNFJDM

signin

题目：

from Crypto.Util.number import *
from secret import flag

def genKey(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
    
    N = p*p*q
    d = inverse(N, (p-1)*(q-1)//GCD(p-1, q-1))
    return N,d

def encrypt(message,N):
    m = bytes_to_long(flag)
    c = pow(m, N, N)
    return c

nbits = 1024
m = bytes_to_long(flag)
N,d = genKey(nbits)
c = encrypt(m,N)

print('c =', c)
print('N =', N)
print('d =', d)

"""
c = 29897791365314067508830838449733707533227957127276785142837008063510003132596050393885548439564070678838696563164574990811756434599732001622138564176327233154381380717648392357672642893142367607369679906940371540867456654151408884171467638060523066406441697453971996011548195499549200103123841556085936672833238264876038160712793697159776332101536779874757463509294968879216810485825310481778472384531442206034564488532399171243463881900578407746982324779260941957792455217641883334131366614310644607114128868153897806362954456585661855569432513785225453501792356175649676419772626548071916379318631677869452985829916084336045071072493567871623113923140668031380684940109024609167449291380675124701557542736834722898328082888430566229322840781411336263268594978558564310744076581639469210462567543585251718744340216155557606004995449505782302864725856877289388008819135023371948017425832082773421030256964953984562211638060
N = 3231913372897424708803097969843687520868057190788284975066875241636436021279559026753076528399891936983240045179193386905918743759145596242896507856007669217275515235051689758768735530529408948098860529277921046146065473333357110158008648799207873976745048714516868561754202543130629713461365314627535982379718931633528922076268531363809414255082933615667770491818402126891370106045838695484124212397783571579791558324350069782623908757815983802849109451590357380624488436968737140312471089662428308113246310588336044438265822574558816510054763215983649467009345458480077882624118620789015758507736272402998721366662352794082495441303895025585316667229865533166614969641012195668280586477033200418153345241668242651407009849656745509386158276185301334443855737552801531617549980843398648751032649895403939319648954908487619711555700124294191702406981128355348449748466449951568451135718146828444185238617155432417897711198169
d = 220908195398117048628110042133057032501548264225985823161565460390793825899523662424732910718579350524590368287207857059670558852106434615134645183432670023784725430385048028248108677670095524205518013647694485975996499747580966911259433184798952372110628624294686853944766950244209186984164963987120416687012811346656498861438432610431705868541829977481875385468143747334359481673214618931159403123892213161430602430294790913847722073762999311674428134241956293914716183107414340330449465142849402354034926378025006749405210014879947411570380433942279355488861684317611066949685697268714760755591128598654573304969
"""

Schemidt-Samoa密码，不了解原理的话搜一搜就好了。

exp：

from Crypto.Util.number import *

c = 29897791365314067508830838449733707533227957127276785142837008063510003132596050393885548439564070678838696563164574990811756434599732001622138564176327233154381380717648392357672642893142367607369679906940371540867456654151408884171467638060523066406441697453971996011548195499549200103123841556085936672833238264876038160712793697159776332101536779874757463509294968879216810485825310481778472384531442206034564488532399171243463881900578407746982324779260941957792455217641883334131366614310644607114128868153897806362954456585661855569432513785225453501792356175649676419772626548071916379318631677869452985829916084336045071072493567871623113923140668031380684940109024609167449291380675124701557542736834722898328082888430566229322840781411336263268594978558564310744076581639469210462567543585251718744340216155557606004995449505782302864725856877289388008819135023371948017425832082773421030256964953984562211638060
n = 3231913372897424708803097969843687520868057190788284975066875241636436021279559026753076528399891936983240045179193386905918743759145596242896507856007669217275515235051689758768735530529408948098860529277921046146065473333357110158008648799207873976745048714516868561754202543130629713461365314627535982379718931633528922076268531363809414255082933615667770491818402126891370106045838695484124212397783571579791558324350069782623908757815983802849109451590357380624488436968737140312471089662428308113246310588336044438265822574558816510054763215983649467009345458480077882624118620789015758507736272402998721366662352794082495441303895025585316667229865533166614969641012195668280586477033200418153345241668242651407009849656745509386158276185301334443855737552801531617549980843398648751032649895403939319648954908487619711555700124294191702406981128355348449748466449951568451135718146828444185238617155432417897711198169
d = 220908195398117048628110042133057032501548264225985823161565460390793825899523662424732910718579350524590368287207857059670558852106434615134645183432670023784725430385048028248108677670095524205518013647694485975996499747580966911259433184798952372110628624294686853944766950244209186984164963987120416687012811346656498861438432610431705868541829977481875385468143747334359481673214618931159403123892213161430602430294790913847722073762999311674428134241956293914716183107414340330449465142849402354034926378025006749405210014879947411570380433942279355488861684317611066949685697268714760755591128598654573304969

pq = GCD(pow(2,n*d,n)-2,n)
p = n//pq
q = pq//p
phi_n = (p-1)*(q-1)
m = pow(c,d,p*q)
print(long_to_bytes(m))

#ISCTF{aeb8be10-ff19-42cf-8cfd-2ce71ac418e8}

1zRSA

题目：

from secret import flag
from Crypto.Util.number import *
import gmpy2

e = 65537
def genKey(nbits):
    while 1:
        p1 = getPrime(3*nbits)
        p2 = gmpy2.next_prime(p1)
        q1 = getPrime(nbits)
        q2 = getPrime(nbits)
        print(abs((p1 - p2)*q1*q2 / p2) < 0.5)
        if (abs((p1 - p2)*q1*q2 / p2) < 0.5):
            n1 = p1 * q1
            n2 = p2 * q2
            return n1,n2

def encrypt(message,e,n):
    m = bytes_to_long(message)
    cipher = pow(m,e,n)
    return cipher

e = 65537
nbits = 512
N1,N2 = genKey(nbits)
c = encrypt(flag,e,N1)

print("c =",c)
print("N1 =",N1)
print("N2 =",N2)

"""
c = 10514867898770499427284608506159580569755258729683776720082395249877529851029152305989048383470182992945743997295638334301128554841767619528809377736651238576700664675871769469687466885347209033023021132575700436470105289467423655742323143373578268184141573237433927498143740155552829633601489926767185335051352605346248971754473960051955670785777007641909166041398566067524811394639822575661469340152913706417365065683835945980239268665146900957692685590242386540944646586739158427428484471978559453954674292300496568823382513505511940062159025700312492163454304120916055466108498000990408937265075788135466153131436
N1 = 29306627985861300819651846356448043523015086509329909246911330574896611830331438353458702041787309531570626136669100576501108581024502570212983369979387658041578384466200573362881060761873478590684611265249166591510948597798713864127744488747451815919677861684787135464097885906630772472111899455047125676738720391327331161464894360886214160668909531050207033060523194208723151015702926842472554933849380343375654696115359960495727909221926251630408376527033291123026893207722440649867394971680316008434251667567174806214522621693042164997381729300075394393372808917061813346794422821819494227772694592990703688149467
N2 = 18405525902524887428651801489049128242565457677879715229456940729064725933277139190670749899959483734341103740185991771024797037242681566772189045321838652668819112989587974866361063424698215713773139281840970499871668796770682692589505769008516630604297570518689639885716307469568821629424402742264467677407820449195383921766157185602677665872353099155904715047452319853202981674101731121033360393547940246101864940155160699277417096395998766928213545196492031975135121409309520198853066288180944871441224241681478164494169741263236267316380581883196836731872676312125837497320438964940186318916950049777255612191899
"""

题目给出了N1，N2，分别有：

$$N_1 = p_1q_1$$ $$N_2 = p_2q_2$$

并且：

$$p_1 \approx p_2$$

所以有：

$$\frac{N_1}{N_2} = \frac{p_1q_1}{p_2q_2} \approx \frac{q_1}{q_2}$$

因此可以用连分数展开N1/N2得到q1/q2，而事实上，题目的这段代码：

abs((p1 - p2)*q1*q2 / p2) < 0.5

就是在用勒让德理论保证能够连分数展开得到q1，q2。

exp：

from Crypto.Util.number import *

c = 10514867898770499427284608506159580569755258729683776720082395249877529851029152305989048383470182992945743997295638334301128554841767619528809377736651238576700664675871769469687466885347209033023021132575700436470105289467423655742323143373578268184141573237433927498143740155552829633601489926767185335051352605346248971754473960051955670785777007641909166041398566067524811394639822575661469340152913706417365065683835945980239268665146900957692685590242386540944646586739158427428484471978559453954674292300496568823382513505511940062159025700312492163454304120916055466108498000990408937265075788135466153131436
N1 = 29306627985861300819651846356448043523015086509329909246911330574896611830331438353458702041787309531570626136669100576501108581024502570212983369979387658041578384466200573362881060761873478590684611265249166591510948597798713864127744488747451815919677861684787135464097885906630772472111899455047125676738720391327331161464894360886214160668909531050207033060523194208723151015702926842472554933849380343375654696115359960495727909221926251630408376527033291123026893207722440649867394971680316008434251667567174806214522621693042164997381729300075394393372808917061813346794422821819494227772694592990703688149467
N2 = 18405525902524887428651801489049128242565457677879715229456940729064725933277139190670749899959483734341103740185991771024797037242681566772189045321838652668819112989587974866361063424698215713773139281840970499871668796770682692589505769008516630604297570518689639885716307469568821629424402742264467677407820449195383921766157185602677665872353099155904715047452319853202981674101731121033360393547940246101864940155160699277417096395998766928213545196492031975135121409309520198853066288180944871441224241681478164494169741263236267316380581883196836731872676312125837497320438964940186318916950049777255612191899
e = 65537

def continuedFra(x, y):
    cF = []
    while y:
        cF += [x // y]
        x, y = y, x % y
    return cF


def Simplify(ctnf):
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]:
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)


def getit(c):
    cf = []
    for i in range(1, len(c)):
        cf.append(Simplify(c[:i]))
    return cf


cf = continuedFra(N1, N2)
for (q2, q1) in getit(cf):
    if (N1 % q1 == 0 and q1 != 1):
        p1 = N1 // q1
        phi = (p1-1)*(q1-1)
        d = inverse(e,phi)
        print(long_to_bytes(pow(c,d,N1)))
        exit()

#ISCTF{6f3af9a9-2727-4d48-afb4-9ca82de893f3}

EasyAES

题目：

from secret import flag,key
from Crypto.Util.number import *
from Crypto.Cipher import AES
import os

assert(len(flag)==39)
assert(len(key)==16)

def padding(msg):
    tmp = 16 - len(msg)%16
    pad = hex(tmp)[2:].zfill(2)
    return bytes.fromhex(pad*tmp)+msg

def encrypt(message,key,iv):
    aes = AES.new(key,AES.MODE_CBC,iv=iv)
    enc = aes.encrypt(message)
    return enc

iv = os.urandom(16)
message = padding(flag)
hint = bytes_to_long(key)^bytes_to_long(message[:16])
enc = encrypt(message,key,iv)

print(enc)
print(hex(hint))

"""
b'bsF\xb6m\xcf\x94\x9fg1\xfaxG\xd4\xa3\x04\xfb\x9c\xac\xed\xbe\xc4\xc0\xb5\x899|u\xbf9e\xe0\xa6\xdb5\xa8x\x84\x95(\xc6\x18\xfe\x07\x88\x02\xe1v'
0x47405a4847405a48470000021a0f2870
"""

注意到题目的padding填充在了flag串前面，为9字节的b”\x09”，再加上flag头”ISCTF{“的六字节，我们只需要爆破一字节就可以得到message的前十六个字节，从而用hint还原出key。

还原出key后，一个block一个block解密就可以得到flag。

exp：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from pwn import xor

enc = b'bsF\xb6m\xcf\x94\x9fg1\xfaxG\xd4\xa3\x04\xfb\x9c\xac\xed\xbe\xc4\xc0\xb5\x899|u\xbf9e\xe0\xa6\xdb5\xa8x\x84\x95(\xc6\x18\xfe\x07\x88\x02\xe1v'
hint = 0x47405a4847405a48470000021a0f2870

for i in range(256):
    prefix = b"\x09" * 9 + b"ISCTF{" + long_to_bytes(i)
    key = long_to_bytes(bytes_to_long(prefix) ^ hint)
    aes1 = AES.new(key,AES.MODE_ECB)

    iv = xor(aes1.decrypt(enc[:16]) , prefix)
    aes = AES.new(key,AES.MODE_CBC,iv=iv)
    m = str(aes.decrypt(enc))
    if(len(m) < 70):
        print(m)

#ISCTF{1b106cea3fb848e7bea310c9851f15c1}

七七的欧拉

题目：

import gmpy2
import libnum
from crypto.Util.number import *

flag=b'ISCTF{*************}'
m=bytes_to_long(flag)

p=libnum.generate_prime(1024)
e=libnum.generate_prime(512)

c=pow(m,e,n)
output = open('output1.txt', 'w')
output.write('e=' + str(e) + '\n')
output.write('n=' + str(n) + '\n')
output.write('c=' + str(c) + '\n')
output.close()

e=8401285423075497989963572888601376313375827722858883767564499066473101615084214973041844878664837606157257039358849583049856161628241418012475432529735909
n=4321524416983780646994834778612486851863709339970595612409550086067211224407144019110798099401660010305645681548980160563216101786447875231976835115531375372678886339587480251211072894186558627897353793098608766868067029578667171419890150599640781594755080391489447462042167529203389236065727274166091741227068469987681083794139925327545810024038937132463518225611578727737940746784891867532498184642892826569777559107609493212332054559366409007685504768163376250281644004067745087899653778023414105973047620041288118404657934689253192043728590231618132716567084621670074256312939305265244486145758609971249077639085204680923108132415216543541472534580414274250979940330459551536830268428508217821060604260805109071534457808355664329902779603050878055690772430842865701249378096775899778255848773171108341331128673249899037133851535556515961699925809139476576825524135111237249709241579903807179252011010794867269715170739895392375920757559721516050680666658719990497863646989338960261844762127142439486275294670858114079687572243312184222126710967744971775585723045524467708387051034760208768956889939050498139189352842087278125173957182804116052402778416216669522309692266036094371308166663738284209615212016564171075874421472070422416318901926525719485991792111414333398004433143751908199358861514725313334333703539239414806773743941986164981642517673117412666430463318509571757766510835600758060976848374353352239044908034501477295696684294816091801944163877509558909040753907584672390823893991672246726026216973013330313971007514064831801564703364591696610900089228302936595848024616691878437618798864186634802647568239526771151323609650598156701595265876736712670677452013054393336294483452480213271032488201259990782289047132105989846972462094302132564809025802421057537091870932014884606863807260521123084423689494401900014232257381801590783735595575258160274248494498550583673688754220860142413631521279464318987425447302135444093663034598455694901199312497459228254746451233078954904159983269585883146959928222698672413648364391121696092287848931565798557217897678221379451042304811449415982434055522599829843482810025780349284547491767219221510351411192251236517341826619338084348136539121415210345488359563985046136632077665460793346345051213014836088333266911684271237227766588616771431226302155269893547077232087387411935345207081799500649921586279416751311277417949192360648342427657867424947189027886922112452681434778850977010752230391327878892161
c=1319666577538961333645698288755316431847498788803191213042970951363587036899021668814931340784440773619019635330248746606532233949080268712626456845590851812018539646705520729734738948568349756255640832936325965096602018372418260009779997764653043892043725224481361578258532294625476542003357969893609762981355267857532927948279737945466285738730414948695579002627741734690862181161919734547857550654813379550806374778412603233570494684223057004866601064851006909940259029023083838730497564657690493780040030061594915385886594845808342023634855913932575150487723897981518504381563064479784253539091893925934095008385592529031453149337783826491324308222762190756839839091742536583068791632135883271750510776330897598323339568926234205068941397524390446254057404779041850572848212437589629794980799894974937730065394307284096622814438575278571743516485062058882794531407454597341604166586040406867868323002258035737328450923576878935675998377134860357842547595516243737449809845708319003744144753130977649201725370898918939022097783844477196723482879094829249203949784703408369396219233552019108990900029123063369670129291960293576115301371071209198455299007327352602249399500334424934488528506773472420414119617828578424633182320749576697196936762283306228974126242434663703609495003656244194067493769815032134577138807799395279843708630774412341952691146906264694889245375545635688534662371202213660012977431598746482601668122679279419039288257069843297770840263002870206849857995148396439717143553611140228607531647245352254251824086797704561756363448681983654454393569932173970943157225527780067126895832370645456372127507057750232257828579628856504832975775855059816283684123444984393171125206440588627925736223222718784319209561804023835238526792966229582251575475514349566824846911411659740321154272534589694497411065971714157409318007179403833025337349924938487211920583780456897879801099476865645416182025930390267064170271613760577949655548949317295792361772032185463678410983568470647837758657058230086368185901572658482084202212103405161775243930901117532775865963215971025744893777631306256061896284125630451368067313753222195227231131526000755922331413457862253392530308284156400411897252674398583100198330007779643967156773216464341590817951828849769679134515304258819218015083183653130972243262400248230445031327719507314015062447355358100770763425336581258193908638241498461735819218673116282476452340137513156421147748432605954889277898079292196216

factordb分解后可以发现n是一个素数的8次方，因此其欧拉函数值为：

$$\phi(n) = (p-1)p^7$$

然后求解d进行解密即可。

exp：

from Crypto.Util.number import *
from gmpy2 import iroot

e=8401285423075497989963572888601376313375827722858883767564499066473101615084214973041844878664837606157257039358849583049856161628241418012475432529735909
n=4321524416983780646994834778612486851863709339970595612409550086067211224407144019110798099401660010305645681548980160563216101786447875231976835115531375372678886339587480251211072894186558627897353793098608766868067029578667171419890150599640781594755080391489447462042167529203389236065727274166091741227068469987681083794139925327545810024038937132463518225611578727737940746784891867532498184642892826569777559107609493212332054559366409007685504768163376250281644004067745087899653778023414105973047620041288118404657934689253192043728590231618132716567084621670074256312939305265244486145758609971249077639085204680923108132415216543541472534580414274250979940330459551536830268428508217821060604260805109071534457808355664329902779603050878055690772430842865701249378096775899778255848773171108341331128673249899037133851535556515961699925809139476576825524135111237249709241579903807179252011010794867269715170739895392375920757559721516050680666658719990497863646989338960261844762127142439486275294670858114079687572243312184222126710967744971775585723045524467708387051034760208768956889939050498139189352842087278125173957182804116052402778416216669522309692266036094371308166663738284209615212016564171075874421472070422416318901926525719485991792111414333398004433143751908199358861514725313334333703539239414806773743941986164981642517673117412666430463318509571757766510835600758060976848374353352239044908034501477295696684294816091801944163877509558909040753907584672390823893991672246726026216973013330313971007514064831801564703364591696610900089228302936595848024616691878437618798864186634802647568239526771151323609650598156701595265876736712670677452013054393336294483452480213271032488201259990782289047132105989846972462094302132564809025802421057537091870932014884606863807260521123084423689494401900014232257381801590783735595575258160274248494498550583673688754220860142413631521279464318987425447302135444093663034598455694901199312497459228254746451233078954904159983269585883146959928222698672413648364391121696092287848931565798557217897678221379451042304811449415982434055522599829843482810025780349284547491767219221510351411192251236517341826619338084348136539121415210345488359563985046136632077665460793346345051213014836088333266911684271237227766588616771431226302155269893547077232087387411935345207081799500649921586279416751311277417949192360648342427657867424947189027886922112452681434778850977010752230391327878892161
c=1319666577538961333645698288755316431847498788803191213042970951363587036899021668814931340784440773619019635330248746606532233949080268712626456845590851812018539646705520729734738948568349756255640832936325965096602018372418260009779997764653043892043725224481361578258532294625476542003357969893609762981355267857532927948279737945466285738730414948695579002627741734690862181161919734547857550654813379550806374778412603233570494684223057004866601064851006909940259029023083838730497564657690493780040030061594915385886594845808342023634855913932575150487723897981518504381563064479784253539091893925934095008385592529031453149337783826491324308222762190756839839091742536583068791632135883271750510776330897598323339568926234205068941397524390446254057404779041850572848212437589629794980799894974937730065394307284096622814438575278571743516485062058882794531407454597341604166586040406867868323002258035737328450923576878935675998377134860357842547595516243737449809845708319003744144753130977649201725370898918939022097783844477196723482879094829249203949784703408369396219233552019108990900029123063369670129291960293576115301371071209198455299007327352602249399500334424934488528506773472420414119617828578424633182320749576697196936762283306228974126242434663703609495003656244194067493769815032134577138807799395279843708630774412341952691146906264694889245375545635688534662371202213660012977431598746482601668122679279419039288257069843297770840263002870206849857995148396439717143553611140228607531647245352254251824086797704561756363448681983654454393569932173970943157225527780067126895832370645456372127507057750232257828579628856504832975775855059816283684123444984393171125206440588627925736223222718784319209561804023835238526792966229582251575475514349566824846911411659740321154272534589694497411065971714157409318007179403833025337349924938487211920583780456897879801099476865645416182025930390267064170271613760577949655548949317295792361772032185463678410983568470647837758657058230086368185901572658482084202212103405161775243930901117532775865963215971025744893777631306256061896284125630451368067313753222195227231131526000755922331413457862253392530308284156400411897252674398583100198330007779643967156773216464341590817951828849769679134515304258819218015083183653130972243262400248230445031327719507314015062447355358100770763425336581258193908638241498461735819218673116282476452340137513156421147748432605954889277898079292196216

p = iroot(n,8)[0]
phi = (p-1)*p**7
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

#ISCTF{3237saq-21se82-3s74f8-8h84ps7-9qw45v7-6bs531-s26h23-c7iu01}

ezRSA

题目：

from secret import flag,key
from Crypto.Util.number import *
from random import randint,getrandbits
from sympy import factorial as factor
from gmpy2 import is_prime as is_strongPrime
from gmpy2 import gcd
from libnum import s2n

def step1(m):
	p,q = getPrime(1024),getPrime(1024)
	n=p*q
	e=getPrime(512)
	phi = (p-1)*(q-1)
	while gcd(e,phi) != 1:
		e=getPrime(512)
	d = pow(e,-1,phi)
	k = randint(800,1500)
	f = factor(k)
	# print(f"\n\n\n\n{k=}\n\n\n\n")
	leak = (pow(e, 2) + (e*d - 1)*f)*getPrime(256) + k
	print(f"{n=}")
	print(f"{leak=}")
	e = 65537
	c = pow(m,e,n)
	return c


def step2(m):
	#the key number is three part 
	assert key < 10**9
	assert (is_prime(key) and not is_strongPrime(key))

	p,q = getPrime(512),getPrime(512)
	n=p*q
	leak1 = pow(p,q,n) + pow(q,p,n)
	print(f"{n=}")
	print(f"{leak1=}")
	e=0x10001
	c = pow(m,e,n)
	seed = getrandbits(64)
	a = getPrime(256)
	b = getPrime(256)
	leak2 = []
	for i in range(10):
		leak2.append(seed := (seed * a + b) % p)
	print(f"{leak2 = }")
	seed = (seed * a + b) % p
	base = key ^ seed
	final = []
	while c > 0:
		final.append(c % base)
		c //= base

	return final


# def most(lis):
# 	return lis.count(True) > lis.count(False)

def is_prime(p):
	check = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
	return all([pow(i,p-1,p)==1 for i in check])


def main():
	assert len(flag) == 2
	print("step1:")
	print("c =",step1(s2n(flag[0])))
	print("step2:")
	print("final =",step2(s2n(flag[1])))


if __name__ == "__main__":
	main()

题目套了四个问题，所以我也就分成四个问题分别阐述一下思路。

step1

这个问题可以参考我这一篇里的2048bit e一题：

Crypto趣题-RSA(一) | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

step2

这个部分对应着剩下的三个小问题。

1、leak1

给出如下式子：

$$leak_1 = p^q + q^p \quad(mod\;n)$$

要求恢复p(不过其实不用这个，也可以用后面的LCG求出p来，但这里就按出题人的思路走一遍吧)。

这一部分思路是这样的，首先对于：

$$t_1 = p^q \quad(mod\;n)$$

在模p和模q下分别有：

$$t_1 = 0 \quad(mod\;p)$$ $$t_1 = p \quad(mod\;q)$$

CRT组合可以得到：

$$t_1 = p*p*inverse(p,q) = p*(1+kq) = p + kn$$

所以就有：

$$t_1 \equiv p \quad(mod\;n)$$

也就是说：

$$p^q \equiv p \quad(mod\;n)$$

对于q^p也是同理，所以leak1其实也就等于p+q，与n=pq联立解方程就可以解出p和q了。

2、LCG

没有什么好讲.

3、求key

如果直接用他给的这个函数爆破的话，相信马上会发现需要的时间很长，不太合理，因此需要尽可能减少爆破时间。

而注意到key的几个限制如下：

#the key number is three part 
assert key < 10**9
assert (is_prime(key) and not is_strongPrime(key))

其中，is_prime函数是：

def is_prime(p):
	check = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
	return all([pow(i,p-1,p)==1 for i in check])

这其实是在说key是一个对100以内素数均成立的费马伪素数。

而费马伪素数定义是指，对某个底数a，如果一个数n满足如下式子却又不是素数，则称他为以a为底的费马伪素数：

$$a^{n-1} \equiv 1 \quad(mod\;n)$$

费马伪素数的数量是很少的，因此，我们可以不完全check100以内的所有素数，而只在以2为底的费马伪素数中找key就好，就可以大大节省时间。

完整exp：

from Crypto.Util.number import *
from sympy import factorial
from gmpy2 import iroot,powmod
from tqdm import *


#part1 get flag1
n=11947241219140615237486309604628973391930339499486798714294498785973885463922548820705069266901903036359254530976927762175262118185159625298369758973935607721381080656199430417818042316007700805008489750740972102287526203064312544340176751751266738219862839022892152635044837041435349904947659346174437695051460882295109851494351994498403791853684239883961766735230202016890875913906900424655711952381425165331389205409282026144667620577946333963601349932905443037145145394667138672752796990411249984169798953060016353748467221154507518574580014882822860853751863757579945329482337792853278715658322366578632817369803
leak=4825516411405566882589539973300777582630401687252523937619475044718073214792109569356301252345907914527064817796240727881691399437316660502564323688151311441558823720142071322647007043253626474853010585775710666373651910201889816367922377400970334479040370865879692204764210349607801862666059991789964453439198722962928173197103040385999540054988070333338229570681105393323319767364566644771731595597298210924296456293443125736685469259629163687986114207231233692023613120260155832741199446052855856512791809968963821161765216500389495853488545132008219841635172896843241988125093920217328861507191614658581776695350233593334984646128341640512614300048002219790302478025661133721688232990437685571940604588227022076092857294647830142309441330515812342199940466483115991318018705011472671758063610572930560763516803732693572940939851140384123593105367117155740563057395940645038058194280259524467405820813428765139386968927021061208348111646257434870000866555555283176852834141906387086839051793789126474095527358879630274092172435022326207193319806666865704778907868548658370890623182731938070419969709739233504224100413506514936517272134494776127809327563935813198793891897000404156963455000732616317276241867836699641699825594195079194154957636030485909612033254350828892222046169586844737908349421869385194421981553067305581842171364022745759111602699744161574724372962242132415149146766136601016174658042678857388889036814591399168640678928083442174651493660991088328784105160030857387096251561933704301600695757426945716557961698202485226605485682131045560193822624290720243852434254301324766198129736640005205530445739302632191151740246117208267182630330046600955724262084795763080838384593939971523865769318326101179866187596006185138294477350533316908592086441208575935282494961976691089358976722199557082176285926812134290542838960814502829473372780200310674359645482281037654052483716329497333729594792122297988611883754886634452292313599416610842690057657285337854049766320641249317238780428383587602425132767334811708075065922641191109650660427678019567095309270443930385437292172296652003394183918270707887845018685247162812541929998945735270109736669595830167257239265204520272132384023622231518288514767919183916561550558812478144292894132331163501566746036390319663066054892756826660841952717280005731719082266616429646501565960817772663658546555336959754321712751857740551378987853931613973604348308746819562341219749677392565068390386908064199536445684309718116754288299091975226013592388160308117145043236992250577771659408413506586402897189336742792418163003231783947003853396754144599319566763313339145462208172531322682800226151072022731913191728047323245146556315571396082728252085753230639541374982105041248659074695696205654079837224195868428271353983820725017250413714060967825638577327604252122887136259380946072629481202720339169708229866846597577227829317443910036825722430374711816074735238082313198164126791797947010044130222158124667234003098164746100341636238823175289796896896408971518797835906067939914494546110471749352544064300485882179448030898818405400902242119590645639910708635188342567159795613212660990908765619684401061336405049960091659288716162966504703741105477420409053115823924764680153604215949521605456710353305498258615912458036292507652321420277318757146737030628878096962452278346772976364597137682209395761868224382621093921689415088745975049380393255899867417274843474628482169247388041616142896804170033688742622605192409970919836724035274730923747265191248135577704760607590
c = 4058526944014006069084945174812818814825704864122299028618329411106188952604728150732223145114766938864644072527523082946069975859381918224872075058517683896020489424720005770218969436595364473179601299857281520204212872074837132357469599147175121200219338329188718982224238281009625352190581095607599976922610436817213692622671732783554216636941121695116377777616027462234472833366922829073660312229117800995468022619934881890343086653577149166193139948443894324239522101581089953817527886638425552917578146958961373353776642091545344162923084513872918786615317499139918810812014781753970806739855831453833956364967

#确定k
for i in range(800,1500):
    t = factorial(i)
    ae2 = int((leak-i) % t)
    if(len(bin(ae2)[2:]) > 256+512+512):
        k = i-1
        print(k)
        break

ae2 = int((leak-k) % factorial(k))
temp = leak // factorial(k)
a = GCD(ae2,leak-k-ae2)
e = iroot(ae2//a,2)[0]
d = int((((leak - k)//a - e**2) // factorial(k) + 1) // e)

kphin = e*d-1
d = inverse(65537,kphin)
print(long_to_bytes(pow(c,d,n)))


#part2 get flag2
n=138222025039224144545251830624229986468723531196582463907557734108529994926504669875900898789473948111199016914847829105939167293515822413866727879262875702026534563930475309506834431656926222982363543666448736091756871792887144283877167509418070979449484508499296324616988840431116233637168977730122017878289
leak1=23535059927033628406212169278224758389583882623183004031205822980722154537430761635153622180505243837027568034322858038302626132200979370182327110682738910
leak2 = [362437850887271063413256292444148642949623196635276044583204094265607936120337004605360832421011, 1932915843524327487337992118762711929552569713433223514001673251237692307587356544615955431611435994003602897830069566867051943572065473955405337889221398, 11222178024143398739150445814520244630341642052876364179793404105841311693968292227072031763726153574031884490677131749512430325919668649359617953965112844, 5408933876805830533113961512210040977462510675785228477646978801328722923647434079128879371684477664804744431834418916837956820965870203842552250165916773, 1447143741705069323823257922715038721270982554690635708441585728089036094805730054505696492295730683300002193478561819037345041940787115528445592303142510, 3707657531268843465369646969917923274507341341483950204025637357600814449263032574496424566705812439915548150679438579110456264431525526309588664326456861, 9263925820149827740182684692442727161206242182976684575667062235695526783971703826794731732152445051579616121306722939129265340347908823003172137299057843, 207494591333501391015462321304802957885928775185602834554977737560856036337667840127810136802887548047878444936730742505483927963807357904024967768148122, 7052936859446617933917872361389151092893299250603966165472023802877016733939957851026719428770748111897050866474067880613419756475700748999497496482278608, 1169538791889404037461397919075674424569430764451305755000680272926397357803359328850780774937432248011264334398346178303234064891680342161511829008635621]
final = [2268617516274900905319941795987877533673889507146326516564545408684476960310333170888941124460992562245780101836116975666368936099249664924148379487909122, 1445275952377746701088629016221431744592935398639655895336779954310077866709012082302847692239730041591520169244063854849129773530127510048494782550102381, 7]
#LCG -> get p
c1,c2,c3,c4,c5 = leak2[:5]
t1 = c2-c1
t2 = c3-c2
t3 = c4-c3
t4 = c5-c4
T1 = t4*t2 - t3*t3
T2 = t3*t1 - t2*t2
p = GCD(T1,T2)

for i in range(2,1000):
    while(p % i == 0):
        p //= i
q = n // p
phi = (p-1)*(q-1)
d = inverse(65537,phi)
#求a,b
a = inverse((c2-c1),p)*(c3-c2) % p
b = (-a*c2 + c3) % p
seed = (leak2[-1]*a+b)%p

#get key
from gmpy2 import is_prime as is_strongPrime
def is_prime(p):
	return powmod(2,p-1,p)==1

#check
for key in trange(1,10**9,2):   
    if(is_prime(key) and not is_strongPrime(key)) :  
        base = key ^ seed
        flag2 = 0
        for i in range(len(final)):
            flag2 += (base**i) * final[i]
        flag2 = powmod(flag2,d,n)
        temp = str(long_to_bytes(flag2))
        if(r"\x" not in temp):
            print(temp)
            exit()

#ISCTF{yOu_kn0W_RSAgcd_and_g0Od_at_LCG_also_like_Carmichael_number}

不过看解出来的flag中，提示key是一个Carmichael_number，也就是卡迈克尔数。

卡迈克尔数是在费马伪素数的基础上定义的。一个数n被称作卡迈克尔数，需要他是以任意与n互素的a为底的费马伪素数。

听上去有点绕，其实也就是要求n对任意与他互素的a都满足：

$$a^{n-1} \equiv 1 \quad(mod\;n)$$

那么结合flag内容应该可以猜到，出题人的预期应该是去OEIS上找3个因子的卡迈克尔数的数列，从而减小爆破复杂度。

但是，这样其实是不太合理的。因为就按照题目提示来说，满足要求的key并不一定就是卡迈克尔数。因为check只用了100以内的素数，不能保证key对任意与他互素的a都满足

$$a^{key-1} \equiv 1 \quad(mod\;key)$$

具体来说，比如key与100以内的素数都满足上面的式子，他就可以通过check；但是如果key与100以上的素数(比如101)不满足上面的式子，他依然是满足题目要求的key，但是他不是卡迈克尔数。所以用卡迈克尔数严格来说可能会漏掉不少符合要求的key，因此用以2为底的费马伪素数来爆破key更加合理。

baby_group

task.py：

from Per import P,Block
from secret import flag
import hashlib
from libnum import s2n

mask = P(256)

print(mask**2)
mask_hash = hashlib.sha512(str(mask).encode()).hexdigest()
print("the mask hash is:" + mask_hash)

mul = P(256)
print(f"{mul=}")
temp = hashlib.sha512(str(mask * mul).encode()).hexdigest()

msg = s2n(flag) ^ int(temp,16)

worker = Block()
print(f"pubkey(q,h):{worker.getPublicKey()}")
c = worker.enc(msg)
print(f"{c=}")
dec = worker.dec(c)

Per.py：

import random
from gmpy2 import invert,sqrt,gcd

class P:
	def __init__(self, data):
		if type(data) is int:
			self.size = data
			self._list = [i+1 for i in range(self.size)]
			self._initialize()			
		elif type(data) is list:
			self._list = data
			self.size = len(self._list)

	def __mul__(self, other):
		return P(self._iterList(self.getList(),other.getList()))

	def __repr__(self):
		return str(self._list)

	def __len__(self):
		return len(self._list)

	def __pow__(self, other):
		tempList = self._list
		for _ in range(1,other):
			tempList = self._iterList(tempList, tempList)
		return P(tempList)

	def __str__(self):
		return str(self._list)

	def getList(self):
		return self._list

	def _initialize(self):
		for i in range(10):
			random.shuffle(self._list)

	def _iterList(self, List1,List2):
		new_list = []
		for elem in List1:
			new_list.append(List2[elem - 1])
		return new_list

pass

class Block():
	def __init__(self):
		while True:
			self.q = random.getrandbits(2048)
			self.f = random.randint(1, sqrt(self.q // 2))
			self.g = random.randint(sqrt(self.q // 4), sqrt(self.q // 2))
			if gcd(self.f, self.q * self.g) == 1:
				break

		self.h = invert(self.f, self.q) * self.g % self.q
		
	def getPublicKey(self):
		return (int(self.q), int(self.h))
	
	def enc(self, m):
		assert m < sqrt(self.q//4)
		r = random.randint(1, sqrt(self.q // 2))
		e = (r * self.h + m) % self.q
		
		return int(e)

	def dec(self, e):
		a = self.f * e % self.q
		b = invert(self.f, self.g) * a % self.g
		return b

output.txt：

[82, 237, 32, 83, 30, 200, 116, 114, 4, 147, 171, 152, 193, 19, 170, 136, 186, 8, 124, 159, 225, 6, 180, 125, 74, 14, 255, 60, 187, 132, 222, 121, 56, 79, 57, 229, 87, 27, 72, 197, 201, 191, 75, 38, 135, 177, 165, 149, 17, 172, 173, 59, 210, 108, 31, 142, 163, 227, 178, 226, 73, 256, 190, 12, 103, 238, 129, 157, 219, 131, 67, 28, 68, 236, 168, 209, 245, 93, 61, 122, 208, 137, 49, 94, 111, 18, 161, 106, 54, 175, 70, 16, 110, 5, 218, 81, 233, 45, 91, 188, 151, 104, 148, 184, 228, 248, 150, 176, 167, 35, 130, 242, 126, 156, 42, 169, 232, 102, 50, 214, 179, 205, 9, 235, 97, 84, 246, 36, 76, 240, 52, 144, 98, 86, 99, 21, 64, 217, 15, 202, 206, 55, 244, 65, 23, 53, 250, 78, 22, 215, 25, 66, 143, 107, 195, 80, 196, 254, 174, 33, 162, 252, 141, 153, 43, 185, 211, 220, 115, 127, 216, 251, 139, 95, 146, 48, 239, 241, 37, 199, 13, 160, 90, 223, 123, 181, 120, 164, 118, 112, 128, 192, 249, 39, 2, 207, 71, 182, 145, 62, 3, 92, 183, 194, 100, 24, 133, 10, 117, 234, 29, 11, 140, 166, 85, 224, 230, 134, 189, 63, 46, 58, 231, 247, 47, 154, 44, 77, 89, 101, 69, 40, 26, 243, 253, 41, 51, 105, 155, 138, 1, 212, 20, 203, 213, 198, 158, 88, 109, 34, 119, 221, 113, 96, 204, 7]

the mask hash is:91881f508f08fbafec1a6879fc3a1f215135c94c78f03fae8534d54dc05bd4a122a4e4508d32b9e02be08fbbb42a9e3335fc433c20e2da2e012d11b7324f6952

mul=[114, 189, 92, 56, 252, 161, 202, 250, 131, 9, 111, 226, 223, 24, 14, 6, 99, 208, 195, 216, 141, 116, 167, 34, 5, 129, 15, 158, 178, 197, 4, 187, 27, 200, 144, 76, 74, 154, 86, 249, 93, 112, 46, 104, 25, 248, 40, 225, 38, 98, 186, 169, 64, 118, 33, 88, 26, 106, 183, 43, 201, 198, 242, 135, 110, 218, 244, 120, 83, 212, 192, 185, 148, 142, 11, 45, 232, 107, 18, 170, 60, 130, 247, 67, 65, 211, 182, 213, 134, 254, 70, 191, 210, 176, 145, 217, 82, 229, 125, 193, 155, 41, 113, 103, 49, 231, 133, 75, 109, 238, 126, 245, 163, 233, 227, 181, 51, 12, 143, 234, 239, 59, 240, 209, 42, 205, 230, 253, 203, 219, 23, 136, 32, 87, 102, 94, 85, 62, 172, 236, 124, 100, 256, 196, 50, 101, 206, 150, 89, 29, 61, 69, 246, 237, 16, 37, 184, 90, 162, 22, 36, 10, 31, 52, 190, 17, 55, 115, 251, 77, 214, 122, 1, 255, 151, 157, 241, 224, 3, 44, 48, 175, 194, 138, 179, 159, 160, 53, 80, 73, 8, 35, 156, 117, 58, 140, 221, 180, 72, 123, 147, 95, 228, 97, 71, 204, 39, 149, 2, 19, 173, 139, 146, 54, 96, 220, 79, 66, 57, 127, 243, 188, 165, 47, 235, 119, 7, 199, 30, 177, 63, 78, 105, 207, 153, 28, 132, 168, 84, 166, 171, 108, 21, 215, 164, 174, 121, 128, 91, 68, 20, 222, 81, 137, 13, 152]

pubkey(q,h):(18172777775303192159727657832771688633216215598877965158949208820296023901084764760222881725262986702478735713462424007788959106272018399708244805316198640706589775789778454299532286932532522325791791312289833643271330941006206604894333175027113622330874626579800679513666624938603337561309816936129926352661091319564303604867093095700819543458178063985869752612663625872468653351930763784372987474747809415652595112648835928004343413910248386752899307068129610089712815257479121368111201632430687614657790581254030567845143865728745079851692195657361359959987504557281840928862881924309178036648485188421874327022341, 392638098592460228418508462226385074690422702429214284385732305774317959159895775092251586043956914155602546821559652111400517952111932579557319610857122515237088379905875982863782386657213421074126519458271560586678974481499715849371311979995450766948182818105567819897007307737370051632369390705725712223883589110699340619034611462216676501782567065261228166297471411589579035544131060706331012337024260046692910523900152236991203944000276133732456285962825434272960749340504092014446362862600803570698206213069473248298100863523331832957430305801141935737006263947843411592717969844892834332104365594346376118846)
c=4605640253217003331334964510174592254013178259349707648547335080743845433538772185582533054930473399495034133342299169373655297635370654237814250924077096784419954824350471683280656146814012837777204413608581553756866045890045788846665715321962704221105416079118007959490372975054302058194463432668018727266982561600329852084442818715440190956213811944269576719501924787366260795121132011879061730892865163591549129768412164655406373350666250339077746317309673325358941772202710386313434421388779073207650619564862431076222163014501544922959835509589742031678624743915535537547452120771609556012990490607104696154771

题目第二部分是一个NTRU，没有太多好讲，主要问题在于第一部分。

而第一部分的问题可以抽象为：已知一个置换的平方，如何还原这个置换？

这个问题可以见我写的这篇中的sqrt一题，我详细解释了还原方法：

Crypto趣题-其他 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

相比起sqrt，ISCTF的这个题目的置换拆分出的环简单很多，需要考虑的情况很少，复杂度就比较低。

exp：

from Crypto.Util.number import *
import hashlib
from itertools import combinations
from tqdm import *

class Per:
	def __init__(self, data):
		if type(data) is int:
			self.size = data
			self._list = [i+1 for i in range(self.size)]
			self._initialize()			
		elif type(data) is list:
			self._list = data
			self.size = len(self._list)

	def __mul__(self, other):
		return Per(self._iterList(self.getList(),other.getList()))

	def __repr__(self):
		return str(self._list)

	def __len__(self):
		return len(self._list)

	def __pow__(self, other):
		tempList = self._list
		for _ in range(1,other):
			tempList = self._iterList(tempList, tempList)
		return Per(tempList)

	def __str__(self):
		return str(self._list)

	def getList(self):
		return self._list

	def _initialize(self):
		for i in range(10):
			random.shuffle(self._list)

	def _iterList(self, List1,List2):
		new_list = []
		for elem in List1:
			new_list.append(List2[elem - 1])
		return new_list

#part1 get mask
if(0):
    P2 = [82, 237, 32, 83, 30, 200, 116, 114, 4, 147, 171, 152, 193, 19, 170, 136, 186, 8, 124, 159, 225, 6, 180, 125, 74, 14, 255, 60, 187, 132, 222, 121, 56, 79, 57, 229, 87, 27, 72, 197, 201, 191, 75, 38, 135, 177, 165, 149, 17, 172, 173, 59, 210, 108, 31, 142, 163, 227, 178, 226, 73, 256, 190, 12, 103, 238, 129, 157, 219, 131, 67, 28, 68, 236, 168, 209, 245, 93, 61, 122, 208, 137, 49, 94, 111, 18, 161, 106, 54, 175, 70, 16, 110, 5, 218, 81, 233, 45, 91, 188, 151, 104, 148, 184, 228, 248, 150, 176, 167, 35, 130, 242, 126, 156, 42, 169, 232, 102, 50, 214, 179, 205, 9, 235, 97, 84, 246, 36, 76, 240, 52, 144, 98, 86, 99, 21, 64, 217, 15, 202, 206, 55, 244, 65, 23, 53, 250, 78, 22, 215, 25, 66, 143, 107, 195, 80, 196, 254, 174, 33, 162, 252, 141, 153, 43, 185, 211, 220, 115, 127, 216, 251, 139, 95, 146, 48, 239, 241, 37, 199, 13, 160, 90, 223, 123, 181, 120, 164, 118, 112, 128, 192, 249, 39, 2, 207, 71, 182, 145, 62, 3, 92, 183, 194, 100, 24, 133, 10, 117, 234, 29, 11, 140, 166, 85, 224, 230, 134, 189, 63, 46, 58, 231, 247, 47, 154, 44, 77, 89, 101, 69, 40, 26, 243, 253, 41, 51, 105, 155, 138, 1, 212, 20, 203, 213, 198, 158, 88, 109, 34, 119, 221, 113, 96, 204, 7]

    for i in range(len(P2)):
        P2[i] -= 1

    #拆环
    lenlist = []
    count = 0
    for i in range(len(P2)):
        len = 1
        t = 0
        loc = P2[i]
        chain = [loc]
        while(1):
            t = P2[loc]
            loc = t
            chain.append(loc)
            len += 1
            if(t == i):
                #print(i,",",len)
                if(len == 2):
                    print(chain)
                break
    #print(lenlist.count(2))
    #64*2 + 29*2 + 20*2 + 9*2 + 4*2 + 3*1 + 1

    chain64 = [[81, 136, 63, 11, 151, 65, 237, 104, 227, 76, 244, 212, 139, 201, 91, 15, 135, 20, 224, 46, 164, 42, 74, 167, 219, 62, 189, 111, 241, 211, 10, 170, 215, 223, 246, 157, 253, 95, 80, 207, 9, 146, 249, 33, 78, 60, 72, 67, 156, 195, 206, 132, 97, 44, 134, 98, 90, 69, 130, 51, 58, 177, 240, 0],[236, 50, 172, 138, 14, 169, 126, 245, 197, 181, 159, 32, 55, 141, 54, 30, 221, 57, 226, 43, 37, 26, 254, 203, 193, 38, 71, 27, 59, 225, 153, 106, 149, 214, 84, 110, 129, 239, 137, 216, 229, 100, 150, 24, 73, 235, 40, 200, 2, 31, 120, 178, 36, 86, 160, 161, 251, 220, 45, 176, 238, 154, 194, 1]]
    chain29 = [[29, 131, 143, 64, 102, 147, 77, 92, 109, 34, 56, 162, 140, 205, 23, 124, 96, 232, 25, 13, 18, 123, 234, 252, 112, 125, 83, 93, 4],[113, 155, 79, 121, 204, 99, 187, 163, 152, 142, 243, 202, 182, 89, 174, 145, 52, 209, 233, 242, 19, 158, 173, 94, 217, 133, 85, 17, 7]]
    chain20 = [[6, 115, 168, 114, 41, 190, 127, 35, 228, 88, 53, 107, 175, 47, 148, 21, 5, 199, 61, 255],[108, 166, 210, 28, 186, 119, 213, 165, 184, 122, 8, 3, 82, 48, 16, 185, 180, 12, 192, 248]]
    chain9 = [[68, 218, 188, 117, 101, 103, 183, 222, 230],[39, 196, 70, 66, 128, 75, 208, 116, 231]]
    chain4 = [[179, 198, 144, 22],[171, 250, 118, 49]]
    chain3 = [[105, 247, 87]]

    #p1 : 191 -> 191
    locdic = {}
    locdic[191] = 191

    #chain3
    chain3r = [0 for i in range(3)]
    for i in range(3):
        chain3r[2*i%3] = chain3[0][i]
    #添加入位置字典
    for i in range(3):
        locdic[chain3r[i]] = chain3r[(i+1)%3]


    #处理偶环插入
    #chain4
    for i in range(4):
        #造一个副本
        locdic1 = locdic
        chain4r = [0 for j in range(8)]
        for j in range(8):
            if(j % 2 == 0):
                chain4r[j] = chain4[0][j//2]
            else:
                chain4r[j] = chain4[1][(j//2 + i) % 4] 
        #添加入位置字典
        for i in range(8):
            locdic1[chain4r[i]] = chain4r[(i+1)%8]


        #chain9
        for i in range(9):
            #造一个副本
            locdic2 = locdic1
            chain18r = [0 for j in range(118)]
            for j in range(18):
                if(j % 2 == 0):
                    chain18r[j] = chain9[0][j//2]
                else:
                    chain18r[j] = chain9[1][(j//2 + i) % 9] 
            #添加入位置字典
            for i in range(18):
                locdic2[chain18r[i]] = chain18r[(i+1)%18]


            #chain20
            for i in trange(20):
                #造一个副本
                locdic3 = locdic2
                chain40r = [0 for j in range(40)]
                for j in range(40):
                    if(j % 2 == 0):
                        chain40r[j] = chain20[0][j//2]
                    else:
                        chain40r[j] = chain20[1][(j//2 + i) % 20] 
                #添加入位置字典
                for i in range(40):
                    locdic3[chain40r[i]] = chain40r[(i+1)%40]
                

                #chain29
                for i in range(29):
                    #造一个副本
                    locdic4 = locdic3
                    chain58r = [0 for j in range(58)]
                    for j in range(58):
                        if(j % 2 == 0):
                            chain58r[j] = chain29[0][j//2]
                        else:
                            chain58r[j] = chain29[1][(j//2 + i) % 29] 
                    #添加入位置字典
                    for i in range(58):
                        locdic4[chain58r[i]] = chain58r[(i+1)%58]
                    


                    #chain64
                    for i in range(64):
                        #造一个副本
                        locdic5 = locdic4
                        chain128r = [0 for j in range(128)]
                        for j in range(128):
                            if(j % 2 == 0):
                                chain128r[j] = chain64[0][j//2]
                            else:
                                chain128r[j] = chain64[1][(j//2 + i) % 64] 
                        #添加入位置字典
                        for i in range(128):
                            locdic5[chain128r[i]] = chain128r[(i+1)%128]
                        
                        P = [locdic5[j] for j in range(256)]
                        tt = [0 for k in range(256)]
                        for op in range(256):
                            tt[op] = P[P[op]]
                        if(tt != P2):
                            print("Bad!")
                        P = [locdic5[j]+1 for j in range(256)]  
                        check = hashlib.sha512(str(P).encode()).hexdigest()
                        if(check == "91881f508f08fbafec1a6879fc3a1f215135c94c78f03fae8534d54dc05bd4a122a4e4508d32b9e02be08fbbb42a9e3335fc433c20e2da2e012d11b7324f6952"):
                            print(P)
                            exit()

mask = Per([87, 245, 52, 116, 114, 166, 4, 5, 7, 154, 38, 221, 36, 20, 16, 170, 42, 94, 159, 19, 246, 214, 251, 146, 135, 243, 216, 81, 48, 156, 190, 59, 75, 215, 244, 193, 1, 171, 254, 118, 70, 186, 33, 11, 25, 66, 182, 187, 115, 145, 140, 32, 97, 167, 63, 168, 203, 242, 121, 208, 111, 123, 31, 252, 205, 177, 184, 240, 117, 201, 104, 96, 130, 99, 56, 231, 2, 164, 85, 144, 60, 161, 169, 18, 61, 84, 82, 248, 109, 206, 41, 15, 153, 8, 253, 28, 210, 151, 236, 148, 98, 71, 100, 67, 155, 88, 250, 211, 54, 143, 73, 58, 134, 30, 17, 83, 219, 197, 199, 22, 178, 65, 256, 174, 53, 86, 21, 13, 223, 68, 3, 80, 101, 126, 74, 127, 162, 196, 92, 173, 90, 220, 35, 122, 172, 125, 107, 188, 120, 34, 45, 46, 110, 147, 228, 132, 138, 39, 124, 43, 137, 64, 183, 93, 160, 200, 108, 142, 49, 136, 27, 23, 202, 235, 24, 29, 238, 179, 241, 119, 128, 165, 141, 129, 62, 191, 149, 78, 40, 222, 181, 192, 229, 158, 77, 217, 102, 47, 50, 185, 131, 139, 163, 247, 103, 175, 230, 226, 69, 233, 176, 44, 51, 6, 79, 255, 207, 113, 232, 55, 152, 112, 76, 204, 198, 10, 212, 195, 249, 133, 209, 189, 234, 26, 95, 91, 213, 239, 105, 157, 37, 227, 14, 57, 237, 225, 194, 106, 89, 150, 180, 12, 218, 72, 224, 9])
mul = Per([114, 189, 92, 56, 252, 161, 202, 250, 131, 9, 111, 226, 223, 24, 14, 6, 99, 208, 195, 216, 141, 116, 167, 34, 5, 129, 15, 158, 178, 197, 4, 187, 27, 200, 144, 76, 74, 154, 86, 249, 93, 112, 46, 104, 25, 248, 40, 225, 38, 98, 186, 169, 64, 118, 33, 88, 26, 106, 183, 43, 201, 198, 242, 135, 110, 218, 244, 120, 83, 212, 192, 185, 148, 142, 11, 45, 232, 107, 18, 170, 60, 130, 247, 67, 65, 211, 182, 213, 134, 254, 70, 191, 210, 176, 145, 217, 82, 229, 125, 193, 155, 41, 113, 103, 49, 231, 133, 75, 109, 238, 126, 245, 163, 233, 227, 181, 51, 12, 143, 234, 239, 59, 240, 209, 42, 205, 230, 253, 203, 219, 23, 136, 32, 87, 102, 94, 85, 62, 172, 236, 124, 100, 256, 196, 50, 101, 206, 150, 89, 29, 61, 69, 246, 237, 16, 37, 184, 90, 162, 22, 36, 10, 31, 52, 190, 17, 55, 115, 251, 77, 214, 122, 1, 255, 151, 157, 241, 224, 3, 44, 48, 175, 194, 138, 179, 159, 160, 53, 80, 73, 8, 35, 156, 117, 58, 140, 221, 180, 72, 123, 147, 95, 228, 97, 71, 204, 39, 149, 2, 19, 173, 139, 146, 54, 96, 220, 79, 66, 57, 127, 243, 188, 165, 47, 235, 119, 7, 199, 30, 177, 63, 78, 105, 207, 153, 28, 132, 168, 84, 166, 171, 108, 21, 215, 164, 174, 121, 128, 91, 68, 20, 222, 81, 137, 13, 152])
temp = hashlib.sha512(str(mask * mul).encode()).hexdigest()


#part2 get flag
q,h = (18172777775303192159727657832771688633216215598877965158949208820296023901084764760222881725262986702478735713462424007788959106272018399708244805316198640706589775789778454299532286932532522325791791312289833643271330941006206604894333175027113622330874626579800679513666624938603337561309816936129926352661091319564303604867093095700819543458178063985869752612663625872468653351930763784372987474747809415652595112648835928004343413910248386752899307068129610089712815257479121368111201632430687614657790581254030567845143865728745079851692195657361359959987504557281840928862881924309178036648485188421874327022341, 392638098592460228418508462226385074690422702429214284385732305774317959159895775092251586043956914155602546821559652111400517952111932579557319610857122515237088379905875982863782386657213421074126519458271560586678974481499715849371311979995450766948182818105567819897007307737370051632369390705725712223883589110699340619034611462216676501782567065261228166297471411589579035544131060706331012337024260046692910523900152236991203944000276133732456285962825434272960749340504092014446362862600803570698206213069473248298100863523331832957430305801141935737006263947843411592717969844892834332104365594346376118846)
c=4605640253217003331334964510174592254013178259349707648547335080743845433538772185582533054930473399495034133342299169373655297635370654237814250924077096784419954824350471683280656146814012837777204413608581553756866045890045788846665715321962704221105416079118007959490372975054302058194463432668018727266982561600329852084442818715440190956213811944269576719501924787366260795121132011879061730892865163591549129768412164655406373350666250339077746317309673325358941772202710386313434421388779073207650619564862431076222163014501544922959835509589742031678624743915535537547452120771609556012990490607104696154771
L = Matrix(ZZ, [[1, h],
                [0, q]])
f, g = L.LLL()[0]
f,g = abs(f),abs(g)
m = (f*c) % q % g * inverse(f, g) % g

flag = long_to_bytes(m ^^ int(temp,16))
print(flag)

#ISCTF{You_can_very_good_at_permutation_and_lattice_base}

Beyond hex,meet heptadecimal

题目：

ID71QI6UV7NRV5ULVJDJ1PTVJDVINVBQUNT

说实话，不会。到时候偷看一下其他师傅的wp再补。