XCTF2023

ezCrypto

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
# ezCrypto.py
import random
import string

characters = string.printable[:-6]
digits = string.digits
ascii_letters = string.ascii_letters


def Ran_str(seed : int, origin: str):
    random.seed(seed)
    random_sequence = random.sample(origin, len(origin))
    return ''.join(random_sequence)

rseed = int(input())
assert rseed <= 1000 and rseed >= 0

map_string1 = Ran_str(rseed, characters)
map_string2 = Ran_str(rseed * 2, characters)
map_string3 = Ran_str(rseed * 3, characters)

def util(flag):
    return flag[9: -1]

def util1(map_string: str, c):
    return map_string.index(c)

def str_xor(s: str, k: str):
    return ''.join(chr((ord(a)) ^ (ord(b))) for a, b in zip(s, k))

def mess_sTr(s : str, index : int):
   
    map_str = Ran_str(index, ascii_letters + digits)
    new_str = str_xor(s, map_str[index])
    
    if not characters.find(new_str) >= 0:
        new_str = "CrashOnYou??" + s
    
    return new_str, util1(map_str, s)
    
def crypto_phase1(flag):
    flag_list1 = util(flag).split('_')
    newlist1 = []
    newlist2 = []
    index = 1
    k = 0
    for i in flag_list1:
        if len(i) % 2 == 1:
            i1 = ""
            for j in range(len(i)):
                p, index = mess_sTr(i[j], index)
                i1 += p
           
            p, index = mess_sTr(i[0], index)
            i1 += p
            
            i1 += str(k)
            k += 1
            newlist1.append(i1)
        
        else:
            i += str(k)
            k += 1
            newlist2.append(i)
    
    return newlist1, newlist2
        
def crypto_phase2(list):
    newlist = []
    for i in list:
        str = ""
        for j in i:
            str += map_string1[util1(map_string3, j)]
           
        newlist.append(str)
    return newlist

def crypto_phase3(list):
    newlist = []
    for i in list:
        str = ""
        for j in i:
            str += map_string2[util1(map_string3, j)]
            
        newlist.append(str)
    return newlist

def crypto_final(list):
    str=""
    for i in list[::-1]:
        str += i
    return str

if __name__ == '__main__':
    format="sixstars{XXX}"
    flag="Nothing normal will contribute to a crash. So when you find nothing, you find A Crashhhhhhhh!!! "
    
    flaglist1, flaglist2 = crypto_phase1(flag)
    cipher = crypto_final(crypto_phase3(crypto_phase2(flaglist1) + flaglist1) + crypto_phase2(crypto_phase3(flaglist2)))
    
    print("map_string2: " + map_string2)
    print("cipher: " + cipher)

1
2
map_string2: \W93VnRHs<CU#GI!d^7;'Lyfo`qt68&Y=Pr(b)O2[|mc0z}BvKkh5~lJeXM-iNgaTZ]*4F?upw>A,x@DQ.Sj:_$E/%"+{1
cipher: &I1}ty~A:bR>)Q/;6:*6`1;bum?8i[LL*t`1;bum?8i[LL?Ia`1;bum?8i[LL72;xl:mvHF"z4_/DD+c:mvHF"z4_/DDzbZ:mvHF"z4_/DDr}vS?

write up

比较常规的自定义加密题

只需要逆着加密的逻辑倒推就行

本题分为以下几个关键解题步骤：

  • 爆破rseed值

  • 分割cipher

  • 还原flag

爆破rseed值

根据rseed不变随机数不变的原理，以及output里给定的map_string2的值，我们可以写个脚本爆破出rseed的值：

1
2
3
4
5
6
7
8
9
10
11
12
13
import string
import random
characters = string.printable[:-6]

for rseed in range(1000):
    random.seed(rseed*2)
    random_sequence = random.sample(characters, len(characters))
    map_string2 = ''.join(random_sequence)
    print(map_string2)
    if(map_string2=='''\W93VnRHs<CU#GI!d^7;'Lyfo`qt68&Y=Pr(b)O2[|mc0z}BvKkh5~lJeXM-iNgaTZ]*4F?upw>A,x@DQ.Sj:_$E/%"+{1'''):
        print(rseed)
        break
# rseed = 667

那么此时map_string1和map_string3均为已知值：

1
2
3
4
5
6
map_string1 = Ran_str(rseed, characters)
map_string3 = Ran_str(rseed*3, characters)
print(f'map_string1 = {map_string1}')
print(f'map_string3 = {map_string3}')
# map_string1 = d*T[RJDKkbZ>"Fs\&X}Q6:h7a{VUj#=Y1tLI~P^qBg9A.)Mz@frvGwn<ie,y|m;'3x54]8-p%W(oS!0lN`?2+H/_Euc$CO
# map_string3 = .2K6b@/~5+=l<7wXj8TaJ?]Z,CMRkY&gG(}tsf)Du^OUx-qdQNiyV$01L["moA*3P'IF#pnhe`\;v>H:z%!c{|WEBS94_r
分割cipher

cipher由两段flaglist1和一段flaglist2代换后拼接而成

同时这两段flaglist1又使用了不同的代换方式，这也是这道题目的突破口

首先我们可以写出反向代换函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def decrypt_phase2(list):
    newlist = []
    for i in list:
        str = ""
        for j in i:
            str += map_string3[util1(map_string1, j)]

        newlist.append(str)
    return newlist

def decrypt_phase3(list):
    newlist = []
    for i in list:
        str = ""
        for j in i:
            str += map_string3[util1(map_string2, j)]

        newlist.append(str)
    return newlist

通过判断条件flaglist1_re0 == flaglist1_re1，我们可以确定cipher中哪一部分属于crypto_phase3(crypto_phase2(flaglist1))，哪一部分属于crypto_phase3( flaglist1)，哪一部分属于crypto_phase2(crypto_phase3(flaglist2))

完整脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def util1(map_string: str, c):
    return map_string.index(c)

def decrypt_phase2(list):
    newlist = []
    for i in list:
        str = ""
        for j in i:
            str += map_string3[util1(map_string1, j)]

        newlist.append(str)
    return newlist


def decrypt_phase3(list):
    newlist = []
    for i in list:
        str = ""
        for j in i:
            str += map_string3[util1(map_string2, j)]

        newlist.append(str)
    return newlist


cipher = '''&I1}ty~A:bR>)Q/;6:*6`1;bum?8i[LL*t`1;bum?8i[LL?Ia`1;bum?8i[LL72;xl:mvHF"z4_/DD+c:mvHF"z4_/DDzbZ:mvHF"z4_/DDr}vS?'''

for i in range(len(cipher)):
    for j in range(i,len(cipher)):
        flaglist2_re = decrypt_phase3(decrypt_phase2(cipher[0:i]))
        flaglist1_re0 = decrypt_phase2(decrypt_phase3(cipher[j:]))
        flaglist1_re1 = decrypt_phase3(cipher[i:j])
        if(flaglist1_re0 == flaglist1_re1):
            print(f'i = {i} j = {j}')
            break
    else:
        continue
    break
# i = 20 j = 66
flaglist2_re = ''.join(flaglist2_re)
flaglist1_re = ''.join(flaglist1_re0)

print(f"flaglist2_re = {flaglist2_re}")
print(f"flaglist1_re = {flaglist1_re}")
还原flag

此时得到的flaglist1_re 和flaglist2_re如下：

其实已经带有一定的语义了

接下来观察加密时的第一步，也就是crypto_phase1(）函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def crypto_phase1(flag):
    flag_list1 = util(flag).split('_')
    newlist1 = []
    newlist2 = []
    index = 1
    k = 0
    for i in flag_list1:
        if len(i) % 2 == 1:
            i1 = ""
            for j in range(len(i)):
                p, index = mess_sTr(i[j], index)
                i1 += p
           
            p, index = mess_sTr(i[0], index)
            i1 += p
            
            i1 += str(k)
            k += 1
            newlist1.append(i1)
        
        else:
            i += str(k)
            k += 1
            newlist2.append(i)
    
    return newlist1, newlist2

flag中的每个用_隔开的元素在进行转换时都会在末尾增加递增的标志k

那么我们就可以利用k将flaglist1_re 和flaglist2_re进一步分割：

flaglist2序列中的元素不需要变化，关键就在于将flaglist1中的元素根据题目的异或规则复原

鉴于flaglist1只有两个元素，且字符长度均为3，考虑直接正向爆破，脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def decrypt_phase1(flag_list1,index):

    k = 0
    i1 = ""
    for j in range(len(i)):
        p, index = mess_sTr(i[j], index)
        i1 += p

    p, index = mess_sTr(i[0], index)
    i1 += p
    return i1,index

import itertools
alphabet = string.ascii_letters + string.digits
for i in itertools.product(alphabet, repeat=3):
    i = ''.join(i)
    _,index = decrypt_phase1(i,1)
    if(_=='CrashOnYou??TDa>'):
        print(i)
        break
for i in itertools.product(alphabet, repeat=3):
    i = ''.join(i)
    _,index1 = decrypt_phase1(i,index)
    if(_=='CrashOnYou??FRCrashOnYou??nw'):
        print(i)
        break

爆破结果如下

遂最终flag为 sixstars{TrY_F1nD_s0m3_F4n_ln_cR7PtO}

NepCTF2023

random_RSA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# RSA_random.py
from gmpy2 import next_prime, invert as inverse_mod
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from random import getrandbits
from math import lcm
from sys import exit

global_bits = 1024

BANNER = rb"""
.--------.--------.--------.--------.--------.--------.--------.--------.--------.--------.--------.
| N.--.  | E.--.  | P.--.  | C.--.  | T.--.  | F.--.  | H.--.  | A.--.  | P.--.  | P.--.  | Y.--.  |
|  :/\:  |  (\/)  |  :():  |  :/\:  |  :/\:  |  :/\:  |  (\/)  |  :():  |  :/\:  |  :/\:  |  (\/)  |
|  :\/:  |  :\/:  |  ()()  |  (__)  |  :\/:  |  (__)  |  :\/:  |  ()()  |  :\/:  |  :\/:  |  :\/:  |
|  '--'n |  '--'e |  '--'p |  '--'c | '--'t  |  '--'f |  '--'h |  '--'a |  '--'p |  '--'p |  '--'y |
`--------`--------`--------`--------'--------`--------`--------`--------`--------`--------`--------`
"""


def generate_prime(bits: int):
    p = (getrandbits(bits - 32) << 32)
    return next_prime(p)


def generate_private_key(bits: int):
    p, q = generate_prime(bits), generate_prime(bits)
    n, phi = p * q, lcm(p-1, q - 1)

    d = inverse_mod(0x10001, phi)
    privateKey = RSA.construct((int(n), int(0x10001), int(d), int(p), int(q)))
    return privateKey, p > q


if __name__ == "__main__":
    print(BANNER.decode())
    print("Welcome to the world of random RSA.")
    print("Please make your choice.")
    for _ in range(8):
        choice = input()

        if choice == '1':
            p, q = generate_prime(global_bits), generate_prime(global_bits)
            N = p*q
            d = generate_prime(global_bits-32)
            e = inverse_mod(d, (p * p - 1) * (q * q - 1))
            print(f"{int(N)}")
            print(f"{int(e)}")

        elif choice == '2':
            privateKey, signal = generate_private_key(global_bits)
            Cipher = PKCS1_v1_5.new(privateKey)
            c = (Cipher.encrypt(flag.encode()))
            print(c)
            exit()

        else:
            exit()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1
22537824826661390223424247613988068034762851961157584494237475399272684698931837582845353300058708376928066803405952833371270343886811582482596041025703562011290683776244440183058564931536167588068982985446423691731289919792182527017708444670021961040693402133847603155628894661303844045174158892135246551752887296981551783741194429738125411950353273196689940793799918342870149922450137468917079363770653597792198995114960248957648399949770607031773274269305508205502788420176566800613727078909046810965678172896900712370390242747304193464562017569375391573425033201518897326268974895428864607294404834217486889626067
138734597932681432146593418071500104975097303947235094754561455609462297555431740773778233199030836536181432380163420879026102996000812679067503821183989703625007081183136453867034603133623214624347743902763056646758303457573028872281836337816161325620419859404564303343891497751416698105376363608315824345809065611898005422541630568343931058614508204741013188215685621271052482911000416811907896612076443855215829082314173006789532402139226514279369930916581792561410304609979179181212657266021728705826301323934157434591614855280547917537852436113654407688546561597461431646587315004899280385693864467900922100139871785655120697706496224116446681145092889309317515443325835174244973690025382177377962932105743284683009382320913496757661606711346067741870427773815722572964498484063351551391418412838281736894948235137587183065029215731250865241317657697517413333042995868451419526992362575295353213512321908674676945279408691460555734014052988319778462382048778709139419333524385417952528530366999004891284914825847790181862255603834009637969575260079574396804250215455740325558291131627689579437078295278863294097845252667171535763807924168498127261282731290505289608262179438124625649642636182083776300283319289915374624961712653
1
6274546339544888768644789843311419134818004096768603845365518977306935493052521497519175028089437236761423867823262516191490597273908631998081154618285312153434770073720976098867396742471680890293254752267605499255169326711848016278766753778762031405366921683792056789407853305249437106982348618425021256460636482851698435376389919364204769613192430479123706318293585495289879180851132554973818815070788262098611224093020341849237428117879027244911203346180853298544223713486928469372908721392827684780137693677209345445942919962990053250395024484583187421075440641480216037229722393785452525034345237210128057575471
6816229639274112360127375160129976283803780671835649464662216953274788670298119581490308251091527765523862793876248484976964516014521928193402406674543559617331132672377525907986916620128585686125738095495763839466668090496434574665174465481239266885391258338614183207608126631709820109879956875736614878909323605565935381337508623639537061259891127144542904865315473351573299736626413254743748115425609364728057333519641010517774252868076778182331567470953952498350730833750070954728558468762716771017777706375771619651064685534393033318515482257223763229174514686211337316905863509879412175617527218834684703000403031425463770536830127898992834855679772246235520604090201191704944952028218549992251035280635917847240965148800849625354939856660848785382830964868230182487528332536748623696072982084155943005225059557342296182817587500114794828507381124146190353878908176849950890467106544577637908359501063238750187093982399537914521258266082734645849446560162705750663487079882805604564517075915685197992097212331440571415385599231910976013688951015114926830356741094239761437270621663346419901696795850688564776378820503827041193837318548510119014302810053953658676697019697630188625116410092169127152796058863748764013682497939
1
7033242934313911617915370463753973061696207288498842695764035487588917876242440540290488008869797904974691714697721721283947971355999106035289016138345801910133073068174108170229491675603212395933924016278358008639554322624843932897396960609189051209643497519694057494944289167537022332119761934070861532451907286657700650146806555444747940730420147901212379535719653643484173080079172941837018636441478229515012901998513559519866730685829684707622706175764190994709063196495343830929136973633289340950272653728043308354240012161431695518275611578691206149580893537585370503416436231040785800664617370845457636507373
40741835840719057027068319492970583470528881382803716418364653870080058622156909377738185420827467314413512511492397920252164414117956834276649844216914404018920028811630177722875369807281893530197017252963630372370374747148813182542589995731838473868063073754954223509497830267809800926245205430476741139619912913673282788675304357813092521700071091744825240512494990728254527083377716674388696819784313808339878265621192173538020777314766219688491638667567106959131093575346705953518495833259604515597325271001238649465380577080494672991745328792235370276741154715574780192691254866861858895341850694654596225740569111073008359702667896467205706781036648628893475072715410255037942273267206315235983153223008531618610230257086119285886173157484398906439752068495678556357613795791467066810705197121410350568328793810636815141728035779662700816654743489502219781077759760073393120940600454699774737362141583979261402813400146968416902616192346695791038404476286201688240239025132255687828236074960774939024752010058639702283427958154036115595796747847178223186808400212601781457541710579621507634949928138998458710132991536600694493869256759751952918863741648153998280321586670085877464297833501428147851192475762142481144210374729
1
5515220884021336970862275167937432706774086760307345493758355407082611881687417106041988561159707722043326906871782788179830793948626803415269881180057295971488161156406028310765335645191428913247696931231456149936758576038023948926465001362260538823507280619462580966749698141504616966770774464155308261944306936232188699464903857962214868960712031476255910121174209368035150601980593184875627393772346196517700195653925532105502535054739699193987090827673963909885997488402164076254118140966268626515017282801146838949997254682432624148069106412023256666757294808355473524248706584183253743746190667825344090735507
27545943436008205192466392146312275350052102340430590890066877373758488661449966774264552635128283215901820155231852994114772623236202481567239435535874760075504493562802626826291928384929323141604652686825513232209696424056756056541825020640169349125845012860406119215734155235823894038092632924099305318778218652782677929386981577810863948946016157839892403075950672327144434254914185650678383059840146557984115295339556244196605497494527019904188910500861412232834797080022272944616867030441521591763706703002065878450561713457527825688019967574810777811525255417243854717475915696113904995939128551197394619709767245589535610868051403872023084015959957890496719349590202804330300807904240587346054105871805966443483086940518302471177065206963143195767481445443418680777155432537987693729107638243548705745742678482316001891443966000174798210175352044800967369982858441628494534591240045812587764064373766987145633774419795741123588607411147213782886833718361722110440999096835034976152742315282032748045708702842770686418432412624392434147272156772744489786263382751791372640135423212833649821848146145001585638446209712930087341278823672429673683111970980096308606491748867960268649616693094935181469752524997580584805349947123
1
707553297879923177356335146532069623604428585457029141654099064083758325344279627925920242519099318326658381470467974653239791175600875958131324367593537709893757926812352231940885134981358322400240925105397807784118834519851991635527957423795609390852936897290132734999038988026169418881785178960809515864390576812740883128033281324731111796202403861022853438825679072942969660472810765800934597235296834952521633103134547244231864541397925943463303930419782291345864716578886463639342118925306182423459228179791865664561840052927559355777744624399481245874427367436123249916802781395498558815808117816153851090809
476835325934189547836292777026041023371148571156463962012880958757944085399758738205283286399334722871894505046090766077229508600863632592015531531628092534860787027986660362296593590421952597122675521182585430259524898100255109700079833179961062981203497736752842526581854959840861895967740417318894425795071380577844789103318524725820756481753291260159826108893063109122213128545709370987322299362649554540926858127317326803313301356181179057881338863137280346277075415080842612942892560322933543217284701560108922901787612676458288276321967842403370403729030083964189266042501688426026969035742389856235451962236823285702151842172397039927227613155422065105587425258233562606059105631111048246890263847875100561204728076387995554893554018520146391083332662983471855734865236713621339367638774664903571940938222768477809946896904342352640218457067049228700063560561986208213880901466761766658005909132289894836214335025796250817129190015222343382401433477141447507445689525537850173095088031348312523535651644177815593848154982006431125144136434640061160594700287452918506662927231440240394313973842561113424179351101333205521687471664502208193453348226748463761211023487451484937024753345544403740598530714590979500824361898349
1
1174140632671015958261680882885689282089461375073396795698409666883472485597284663141211586467308831657514141409046557743901220588742234762871975650828276609892436013463956505148941718047758019452108677333838067737690070001391918566731891662155223281759699605140519220454976428865373529394744215204895977525725731538112915575334028817210061259374241384161149774887685139129929524748236393300647250180543352420479715186567359381371734233117769316250064423204561965836088727262981245272806674341083098416951592697842269090172337779893183460941187775737310053977539420950749247856094432739662593564239070582498797381009
825353942467438234491111084516936797128140027203784474891798800414336605361414186661583004143257383201569203822551344974068949165344273763876615373043877527773093928960467215872693727816191117465919988153853161000881030542114914941352759498799545196523052122861955253519302407772691186951213308450636061291872775729603561683435521768308933690835080550772642833337817896300004822744605680361933350735805267937934286244922586652389425557655335013436726671473028595770338968627940302482280711760107774414537585937863168754668453885061204249986101071167028988095045568258441130714118233523745169679090945421590869375509998154504396878014511907888539167694131925238588859598725184662191826531994202286022429433690565056627911001834268776824700846906219148406027748395811448518747553045711021410331182717382379956168706606051002858514214330540368543514307421082375954175404302844792700585694756351868096269476974857475405543355119725892926139966042877395445749171112669690253373756673197045102745144246028153147601058742572746575386811945290093484519058179624368946654749995012889984471094647410670938250873437031330589096177392536521956944850884417890645930238421186410678500251283295562754926225650213865444544000297930194777658433889
1
6276624371571322127032717528988403355942748255487183219267886395660971429723684209001382203088006753614931749563754635436959672532470203173873966609604425233662748651974072780833472364097044853853352453104215290154805673093406690509685785395377452785503947795433224239515836453030100902644138118585267917947442229874047104299588820831133871052908583498858437224506062430779962591008533689175035855935205810375775549031261102987287032561315490868731527768409029395091316808354032134723564697369468445597956717874050607045073658705017638915547090694446609245551301975852518033673640951339784531542368356313947923717367
4834448583556238562695333814669633473578395694994823308285848875447286856609545266763235079125953453630747057984939339519480845072027717047444425002584145597569095137335784562707662997300157488660880747910032450465764286421150106071387112517350098642033395129426783691267842349041299351180374740785056277266915618733246024742289334731264695226009208450387864801281044160267289921056725461400497169893204466841683255565774720703277610021920414649471524369642392114034753099895659454683133776017380599332734563716104395584378176004067527173821613141103789428693603220181387443973578566586053743228232089818664884161874519177760253682885066533216475221265861892995346645326152399587288537613784309794325645046905177498808889470249663668654810130597749775576909495987678548653910285369470549673317992925013277276466958694013901591757010380010612703667696761086495736918715214768477207011152740334849526812828915367533869104564994266525693597782393511548424817920580128787463341705437149065550280692381207426443987434943692728197680277851234773705473049444481734019328425281093760302507469963769149697884104863580140750939967048592895251133501980796441364382320329398348046615652832468150610453087912158467236578469248525561624767339227
2
b"\t\xb9d\x82@\xe1-\xaa\xff\x86\t\xb2\x0e\xe51\x1ek\xa0\xb5'\xc2:\x95\x9c\xfb\x9f\xf0I\x1f\x05&\xf6\xfa\x99A\x1c\x00\xea\xcd\xa25\xb9=\xe4\x87L\\Q\x0f\xad#\xf3\x9fC\x93\xa3\x01\xc4\xc8\xc4\xf3\x88RM\x92\x95\x99\xa5\xf5e\x1dDs2\x8c\x8d\xc3\xb5#\xd9\x01Z\xa6\x92\x10\xb8g\x8a\n\xea\xf6\xd4\xfan\xba\xedZiLU.-D\x18\x9dif\xea1\x9dz8Z\x1e\x9a\x0c\xd8$S\xa3\xf2\xa7\xa3\x1b\xf9\xb9\x96\xfd\t}\xd4Su8\xb5+\xde\xb7\xd3\xa4\xbaa_\x0f\xccj\x86\x8d\x91\x9aJ!Z|\xcf\xa9\xae\xb9\xfe\x15\xd8\x04\xa7:\x86\xe6\x1e\xdc\x88\xbd\x1a3\x99\xc3N~\x08\x04\x18(\x8dG\xa8\x86\xd3\x03\xceF4\xb2Xp\x17:-\x1a\x1f;.\xefd\xbf7p\xe1\xca\x8a\x97\xfa\xcf\x1es\x0f\x0fJ\x87\x16\x91\xd1l\x13\xcb<\xe9\x8c\x8ai\x80\xec\xe8\xeb\x87\xee\xb0\xabR\xdc\xa8D\x7f+\xa9|,\xa5\xce\xce-\xec\x86]i\xa8\x82\x8b)"

比赛时的心路历程

random库中的getrandbits()方法用于返回一个指定大小（以位为单位）的整数。

该方法使用的伪随机数生成算法是梅森算法

此处用到randcrack库中的predict_getrandbits()方法，当给出的随机数够多时，可以预测下一个随机数

具体使用RandCrack.submit()提交，最后用RandCrack.predict_getrandbits()预测

正好这一题循环了8次，那么前七次的数据可以用于预测第8次生成的随机数

具体要解决的是如何用每次的N、e算出p、q、d

可以试一下拓展维纳攻击，不过这个题的e和d定义比较奇怪

复现write up

事实上比赛时我对MT19937和拓展维纳攻击的分析是正确的

可惜没去查论文

因为这题的涉及到变种RSA扩展维纳攻击

MT19937攻击使用python库extend_mt19937_predictor即可

本题完整sage脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
from gmpy2 import gcd,next_prime,invert,iroot
from extend_mt19937_predictor import ExtendMT19937Predictor
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
from tqdm import tqdm
from sage.all import *
def factor_N_with_e(n,e):
    convergents = continued_fraction(ZZ(e) / ZZ(int(n^2 -9/4*n +1))).convergents()
    for c in convergents:
        k = c.numerator()
        d = c.denominator()
        if pow(pow(2,int(e),int(n)),int(d),n) == 2:
            phi = (e*d - 1)//k
            p_add_q = iroot(n^2+1 -phi +2*n,2)[0]
            p_sub_q = iroot(n^2+1 -phi -2*n,2)[0]
            p = (p_add_q + p_sub_q)//2
            q = n//p 
            return p,q

Ns=[]
es=[]
Ns.append(22537824826661390223424247613988068034762851961157584494237475399272684698931837582845353300058708376928066803405952833371270343886811582482596041025703562011290683776244440183058564931536167588068982985446423691731289919792182527017708444670021961040693402133847603155628894661303844045174158892135246551752887296981551783741194429738125411950353273196689940793799918342870149922450137468917079363770653597792198995114960248957648399949770607031773274269305508205502788420176566800613727078909046810965678172896900712370390242747304193464562017569375391573425033201518897326268974895428864607294404834217486889626067)
es.append(138734597932681432146593418071500104975097303947235094754561455609462297555431740773778233199030836536181432380163420879026102996000812679067503821183989703625007081183136453867034603133623214624347743902763056646758303457573028872281836337816161325620419859404564303343891497751416698105376363608315824345809065611898005422541630568343931058614508204741013188215685621271052482911000416811907896612076443855215829082314173006789532402139226514279369930916581792561410304609979179181212657266021728705826301323934157434591614855280547917537852436113654407688546561597461431646587315004899280385693864467900922100139871785655120697706496224116446681145092889309317515443325835174244973690025382177377962932105743284683009382320913496757661606711346067741870427773815722572964498484063351551391418412838281736894948235137587183065029215731250865241317657697517413333042995868451419526992362575295353213512321908674676945279408691460555734014052988319778462382048778709139419333524385417952528530366999004891284914825847790181862255603834009637969575260079574396804250215455740325558291131627689579437078295278863294097845252667171535763807924168498127261282731290505289608262179438124625649642636182083776300283319289915374624961712653)

Ns.append(6274546339544888768644789843311419134818004096768603845365518977306935493052521497519175028089437236761423867823262516191490597273908631998081154618285312153434770073720976098867396742471680890293254752267605499255169326711848016278766753778762031405366921683792056789407853305249437106982348618425021256460636482851698435376389919364204769613192430479123706318293585495289879180851132554973818815070788262098611224093020341849237428117879027244911203346180853298544223713486928469372908721392827684780137693677209345445942919962990053250395024484583187421075440641480216037229722393785452525034345237210128057575471)
es.append(6816229639274112360127375160129976283803780671835649464662216953274788670298119581490308251091527765523862793876248484976964516014521928193402406674543559617331132672377525907986916620128585686125738095495763839466668090496434574665174465481239266885391258338614183207608126631709820109879956875736614878909323605565935381337508623639537061259891127144542904865315473351573299736626413254743748115425609364728057333519641010517774252868076778182331567470953952498350730833750070954728558468762716771017777706375771619651064685534393033318515482257223763229174514686211337316905863509879412175617527218834684703000403031425463770536830127898992834855679772246235520604090201191704944952028218549992251035280635917847240965148800849625354939856660848785382830964868230182487528332536748623696072982084155943005225059557342296182817587500114794828507381124146190353878908176849950890467106544577637908359501063238750187093982399537914521258266082734645849446560162705750663487079882805604564517075915685197992097212331440571415385599231910976013688951015114926830356741094239761437270621663346419901696795850688564776378820503827041193837318548510119014302810053953658676697019697630188625116410092169127152796058863748764013682497939)

Ns.append(7033242934313911617915370463753973061696207288498842695764035487588917876242440540290488008869797904974691714697721721283947971355999106035289016138345801910133073068174108170229491675603212395933924016278358008639554322624843932897396960609189051209643497519694057494944289167537022332119761934070861532451907286657700650146806555444747940730420147901212379535719653643484173080079172941837018636441478229515012901998513559519866730685829684707622706175764190994709063196495343830929136973633289340950272653728043308354240012161431695518275611578691206149580893537585370503416436231040785800664617370845457636507373)
es.append(40741835840719057027068319492970583470528881382803716418364653870080058622156909377738185420827467314413512511492397920252164414117956834276649844216914404018920028811630177722875369807281893530197017252963630372370374747148813182542589995731838473868063073754954223509497830267809800926245205430476741139619912913673282788675304357813092521700071091744825240512494990728254527083377716674388696819784313808339878265621192173538020777314766219688491638667567106959131093575346705953518495833259604515597325271001238649465380577080494672991745328792235370276741154715574780192691254866861858895341850694654596225740569111073008359702667896467205706781036648628893475072715410255037942273267206315235983153223008531618610230257086119285886173157484398906439752068495678556357613795791467066810705197121410350568328793810636815141728035779662700816654743489502219781077759760073393120940600454699774737362141583979261402813400146968416902616192346695791038404476286201688240239025132255687828236074960774939024752010058639702283427958154036115595796747847178223186808400212601781457541710579621507634949928138998458710132991536600694493869256759751952918863741648153998280321586670085877464297833501428147851192475762142481144210374729)

Ns.append(5515220884021336970862275167937432706774086760307345493758355407082611881687417106041988561159707722043326906871782788179830793948626803415269881180057295971488161156406028310765335645191428913247696931231456149936758576038023948926465001362260538823507280619462580966749698141504616966770774464155308261944306936232188699464903857962214868960712031476255910121174209368035150601980593184875627393772346196517700195653925532105502535054739699193987090827673963909885997488402164076254118140966268626515017282801146838949997254682432624148069106412023256666757294808355473524248706584183253743746190667825344090735507)
es.append(27545943436008205192466392146312275350052102340430590890066877373758488661449966774264552635128283215901820155231852994114772623236202481567239435535874760075504493562802626826291928384929323141604652686825513232209696424056756056541825020640169349125845012860406119215734155235823894038092632924099305318778218652782677929386981577810863948946016157839892403075950672327144434254914185650678383059840146557984115295339556244196605497494527019904188910500861412232834797080022272944616867030441521591763706703002065878450561713457527825688019967574810777811525255417243854717475915696113904995939128551197394619709767245589535610868051403872023084015959957890496719349590202804330300807904240587346054105871805966443483086940518302471177065206963143195767481445443418680777155432537987693729107638243548705745742678482316001891443966000174798210175352044800967369982858441628494534591240045812587764064373766987145633774419795741123588607411147213782886833718361722110440999096835034976152742315282032748045708702842770686418432412624392434147272156772744489786263382751791372640135423212833649821848146145001585638446209712930087341278823672429673683111970980096308606491748867960268649616693094935181469752524997580584805349947123)

Ns.append(707553297879923177356335146532069623604428585457029141654099064083758325344279627925920242519099318326658381470467974653239791175600875958131324367593537709893757926812352231940885134981358322400240925105397807784118834519851991635527957423795609390852936897290132734999038988026169418881785178960809515864390576812740883128033281324731111796202403861022853438825679072942969660472810765800934597235296834952521633103134547244231864541397925943463303930419782291345864716578886463639342118925306182423459228179791865664561840052927559355777744624399481245874427367436123249916802781395498558815808117816153851090809)
es.append(476835325934189547836292777026041023371148571156463962012880958757944085399758738205283286399334722871894505046090766077229508600863632592015531531628092534860787027986660362296593590421952597122675521182585430259524898100255109700079833179961062981203497736752842526581854959840861895967740417318894425795071380577844789103318524725820756481753291260159826108893063109122213128545709370987322299362649554540926858127317326803313301356181179057881338863137280346277075415080842612942892560322933543217284701560108922901787612676458288276321967842403370403729030083964189266042501688426026969035742389856235451962236823285702151842172397039927227613155422065105587425258233562606059105631111048246890263847875100561204728076387995554893554018520146391083332662983471855734865236713621339367638774664903571940938222768477809946896904342352640218457067049228700063560561986208213880901466761766658005909132289894836214335025796250817129190015222343382401433477141447507445689525537850173095088031348312523535651644177815593848154982006431125144136434640061160594700287452918506662927231440240394313973842561113424179351101333205521687471664502208193453348226748463761211023487451484937024753345544403740598530714590979500824361898349)

Ns.append(1174140632671015958261680882885689282089461375073396795698409666883472485597284663141211586467308831657514141409046557743901220588742234762871975650828276609892436013463956505148941718047758019452108677333838067737690070001391918566731891662155223281759699605140519220454976428865373529394744215204895977525725731538112915575334028817210061259374241384161149774887685139129929524748236393300647250180543352420479715186567359381371734233117769316250064423204561965836088727262981245272806674341083098416951592697842269090172337779893183460941187775737310053977539420950749247856094432739662593564239070582498797381009)
es.append(825353942467438234491111084516936797128140027203784474891798800414336605361414186661583004143257383201569203822551344974068949165344273763876615373043877527773093928960467215872693727816191117465919988153853161000881030542114914941352759498799545196523052122861955253519302407772691186951213308450636061291872775729603561683435521768308933690835080550772642833337817896300004822744605680361933350735805267937934286244922586652389425557655335013436726671473028595770338968627940302482280711760107774414537585937863168754668453885061204249986101071167028988095045568258441130714118233523745169679090945421590869375509998154504396878014511907888539167694131925238588859598725184662191826531994202286022429433690565056627911001834268776824700846906219148406027748395811448518747553045711021410331182717382379956168706606051002858514214330540368543514307421082375954175404302844792700585694756351868096269476974857475405543355119725892926139966042877395445749171112669690253373756673197045102745144246028153147601058742572746575386811945290093484519058179624368946654749995012889984471094647410670938250873437031330589096177392536521956944850884417890645930238421186410678500251283295562754926225650213865444544000297930194777658433889)

Ns.append(6276624371571322127032717528988403355942748255487183219267886395660971429723684209001382203088006753614931749563754635436959672532470203173873966609604425233662748651974072780833472364097044853853352453104215290154805673093406690509685785395377452785503947795433224239515836453030100902644138118585267917947442229874047104299588820831133871052908583498858437224506062430779962591008533689175035855935205810375775549031261102987287032561315490868731527768409029395091316808354032134723564697369468445597956717874050607045073658705017638915547090694446609245551301975852518033673640951339784531542368356313947923717367)
es.append(4834448583556238562695333814669633473578395694994823308285848875447286856609545266763235079125953453630747057984939339519480845072027717047444425002584145597569095137335784562707662997300157488660880747910032450465764286421150106071387112517350098642033395129426783691267842349041299351180374740785056277266915618733246024742289334731264695226009208450387864801281044160267289921056725461400497169893204466841683255565774720703277610021920414649471524369642392114034753099895659454683133776017380599332734563716104395584378176004067527173821613141103789428693603220181387443973578566586053743228232089818664884161874519177760253682885066533216475221265861892995346645326152399587288537613784309794325645046905177498808889470249663668654810130597749775576909495987678548653910285369470549673317992925013277276466958694013901591757010380010612703667696761086495736918715214768477207011152740334849526812828915367533869104564994266525693597782393511548424817920580128787463341705437149065550280692381207426443987434943692728197680277851234773705473049444481734019328425281093760302507469963769149697884104863580140750939967048592895251133501980796441364382320329398348046615652832468150610453087912158467236578469248525561624767339227)

random_number = []
for i in range(0,7):
    p,q = factor_N_with_e(int(Ns[i]),int(es[i]))
    if p > q:
        random_number.append((p>>32,1024-32))
        random_number.append((q>>32,1024-32))
    else:
        random_number.append((q>>32,1024-32))
        random_number.append((p>>32,1024-32))
    d = int(inverse_mod(es[i], (p*p-1)*(q*q-1)))
    random_number.append((d>>32,1024-64))
bits = 1024


def gen2(bits: int):
    p = (predictor.predict_getrandbits(bits - 32) << 32)
    return next_prime(p)
e = 0x10001
c = b"\t\xb9d\x82@\xe1-\xaa\xff\x86\t\xb2\x0e\xe51\x1ek\xa0\xb5'\xc2:\x95\x9c\xfb\x9f\xf0I\x1f\x05&\xf6\xfa\x99A\x1c\x00\xea\xcd\xa25\xb9=\xe4\x87L\\Q\x0f\xad#\xf3\x9fC\x93\xa3\x01\xc4\xc8\xc4\xf3\x88RM\x92\x95\x99\xa5\xf5e\x1dDs2\x8c\x8d\xc3\xb5#\xd9\x01Z\xa6\x92\x10\xb8g\x8a\n\xea\xf6\xd4\xfan\xba\xedZiLU.-D\x18\x9dif\xea1\x9dz8Z\x1e\x9a\x0c\xd8$S\xa3\xf2\xa7\xa3\x1b\xf9\xb9\x96\xfd\t}\xd4Su8\xb5+\xde\xb7\xd3\xa4\xbaa_\x0f\xccj\x86\x8d\x91\x9aJ!Z|\xcf\xa9\xae\xb9\xfe\x15\xd8\x04\xa7:\x86\xe6\x1e\xdc\x88\xbd\x1a3\x99\xc3N~\x08\x04\x18(\x8dG\xa8\x86\xd3\x03\xceF4\xb2Xp\x17:-\x1a\x1f;.\xefd\xbf7p\xe1\xca\x8a\x97\xfa\xcf\x1es\x0f\x0fJ\x87\x16\x91\xd1l\x13\xcb<\xe9\x8c\x8ai\x80\xec\xe8\xeb\x87\xee\xb0\xabR\xdc\xa8D\x7f+\xa9|,\xa5\xce\xce-\xec\x86]i\xa8\x82\x8b)"
for sign in tqdm(range(0,1<<7)):
    predictor = ExtendMT19937Predictor()
    for i in range(7):
        if (sign>>i)&1 == 1:
            predictor.setrandbits(*random_number[3*i])
            predictor.setrandbits(*random_number[3*i+1])
        else:
            predictor.setrandbits(*random_number[3*i+1])
            predictor.setrandbits(*random_number[3*i])
        predictor.setrandbits(*random_number[3*i+2])
    p,q = gen2(bits),gen2(bits)
    phi = lcm(p-1,q-1)
    d = invert(e,phi)
    n = p*q

    privateKey = RSA.construct((int(n),int(e),int(d),int(p),int(q)))
    Cipher = PKCS1_v1_5.new(privateKey)
    flag = (Cipher.decrypt(c,'\x00'))
    print(flag)

Out:

1
b'NepCTF{c4e4356067fb3bedc53dde7af59beb1c}'

考点

拓展维纳攻击

论文地址：A new attack on three variants of the RSA cryptosystem

sage脚本：

1
2
3
4
5
6
7
8
9
10
11
12
def factor_N_with_e(n,e):
    convergents = continued_fraction(ZZ(e) / ZZ(int(n^2 -9/4*n +1))).convergents()
    for c in convergents:
        k = c.numerator()
        d = c.denominator()
        if pow(pow(2,int(e),int(n)),int(d),n) == 2:
            phi = (e*d - 1)//k
            p_add_q = iroot(n^2+1 -phi +2*n,2)[0]
            p_sub_q = iroot(n^2+1 -phi -2*n,2)[0]
            p = (p_add_q + p_sub_q)//2
            q = n//p 
            return p,q

关于维纳攻击的详细内容后面会单独写一篇文章总结，因为在Crypto题中经常出现

MT19937攻击

概念

梅森旋转算法（Mersenne twister）是一个伪随机数发生算法。由松本真和西村拓士在1997年开发，基于有限二进制字段上的矩阵线性递归。可以快速产生高质量的伪随机数，修正了古典随机数发生算法的很多缺陷。

Python中使用的梅森算法为MT19937，周期为$2^{19937}-1$

也就是说，其生成的数据在624*32后会达到循环，我们必须需要624个32位由梅森算法产生的随机数才能找到循环点，并以此预测之后的随机数

工具

较为好用的工具为python的库Extend_MT19937_Predictor

下载：pip install extend_mt19937_predictor

每次进行预测操作时，先定义一个predictor

1
2
from extend_mt19937_predictor import ExtendMT19937Predictor
predictor = ExtendMT19937Predictor()

然后将数据喂给它，需要标明投喂数据的位数

1
2
3
predictor.setrandbits(数据,位数)
#example
predictor.setrandbits(random.getrandbits(256), 256)

当数据超过19938位之后，便可以进行预测以及回溯操作

1
2
3
4
#预测操作，括号中注明预测的位数
predictor.predict_getrandbits(64)
#回溯操作，括号中注明预测的位数
predictor.backtrack_getrandbits(64)

蓝帽杯2023

DHRSA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
# chall.py
# sage
from sage.all import *
from Crypto.Util.number import getPrime,getStrongPrime, isPrime, bytes_to_long
from secret import r,g
from secret import flag

assert r.bit_length() == 512 and isPrime(r)
FLAG = bytes_to_long(flag)

def gen_DH_key(g,r):
    x = randint(2,r-1)
    return x, pow(g,x,r)

def gen_RSA_parameters(g,r):
    main_key = gen_DH_key(g,r)
    sub_key = gen_DH_key(g,r)
    x, X = main_key
    w, W = sub_key
    print(f"[+] Public DH Keys { X = }")
    print(f"[+] Public DH Keys { W = }")
    while True:
        c, C = gen_DH_key(g,r)
        t1 = randint(0,1)
        t2 = randint(0,1)
        p = ZZ(C * W^t1 * pow(X, c, r) % r)
        if not is_prime(p):
            continue
        q = ZZ(pow(W, -t2, r) * pow(X, -c, r) % r)
        if not is_prime(q):
            print(f"[+] Try {c ,C}")
            continue
        return p,q
    
p, q = gen_RSA_parameters(g,r)
n = p*q
e = 65537
c = pow(FLAG,e,n)
print(f"{ c = }")
print(f"{ n = }")
# out.txt
[+] Public DH Keys  X = 197551296081022143608034360606381334253374533627365455002683616928330857539205836504075700389569213696043700490195977045586318090211726350917451410932216
[+] Public DH Keys  W = 10625560347436147537644301075885059900758953251551866239435327407977591190018531918316486861730777808988185029637608372445416280896280058313924537678128258
[+] Try (9771395973011655803041049350400889693558053786906788399593857181577256033087775470396528142785531153656250742163382306394790826547696369519066900832598632, 8139606023160038223737079478941118590185130735073983268534523900466799026361464500424904356248753891316780445417573842978538788878976916399246204378441056)
[+] Try (8272821018041191335817314516024870641634584838709754134295649414123178842937800314505950304166260273130361466329869880024580711311122266329063823157928578, 6731047210123888962354325580924677204725121336252367061814596228770531939085170702108835833376855510135160514592212524395740859425722612967050674897558554)
[+] Try (9224196545381524434689958500941052085722509493323098161219607220849299786695264643219965900283680542442505315754998495711744726427299710433730839117822341, 8618477079542034439812499299348172601780082410118486479357089433765711733400709574657418048464225715724091467457454996920521245517408697962287328781660172)
[+] Try (1008469491610938216099437983993305774398678547360061529021095399886442276321623596589458980857784117593111375842386009804225494459153563491699302948435260, 9243753430474436162138755988303772102594989764465818886594050158035773372691908643200174705510107166901553683916448850166844368808268900160791189879886461)
[+] Try (7616413788891104674175703849368746136014029498968757620534065604935400737852925875633996435081025804169137754721194517660132118370608033038162779303724417, 5081325787403850070122342963066210472728109263877409302015934601768721956580972368361384922036489915214279268746375195256103574903758346112788101331060421)
[+] Try (7584549797616896430743312033954227311758800006881758430848397006388599762762869550122276429056861398410906389124143882721771887174154825862686488628829556, 1628416782427642576537753826054924818984220964280741905185643986017630454253562852051349318488828073385103084138926801432973213673304459124585445072035446)
[+] Try (4857850091039904852357309328743353934107579830869744999969242154323443783533786032181281694960711385606506579359066323294671727886753617501542207839926790, 1436555309056212704783260154843715809916541935750195541226776332006326501592432597657580990741764167962753224321573279559350979014777173060581697942160790)
[+] Try (4779727649310569079487754450225462592903787505885564750560744245118977747200287996364352093535624060190258736345242819222383024403591273643223505871273937, 8457854453119605903801540115672523550270614339671410689633028758723786021115482172319549655156915937495339811221100830546511268665457084873839271917131026)
[+] Try (6240985007555841990183784512088706027373526355604287377336898927100013200525239698399664369530638033756622723154794368086253680721133641187916109948879111, 7516353799796514587790845891436757011323761869044622559902758322970504358548733636938457083535644723388210752578649311718854524047992380524533863744945353)
[+] Try (1440004269550837930069561548693107407163496872089856298023372643037792305541293783438854412197014895824653797468093046886645122408623089543218627931731325, 9434919345479338423866102885320010476913815819406622512632495616332678841660980531307718949753248131094030185131327688989259983673428169616967926536549981)
[+] Try (8686467414540984479883981478664234832161994713954432326787817013306458410596539074149482305300161480885280412716015692242140611122632851558942831571969449, 2376239907248313997443412718623933371621229548870946158597654591040113647645833393016706072537549866458668992268347350086597733853645352669964694698209002)
[+] Try (6397234126429549747756931006796154340671325181680459289481852293242757656214345178451346712629678435704959420962366420623987135911533358778558089423502498, 9555521900012304016219328488701400452052438846888508591910947639752080094465009622568296701465965949214617545676819204984390042310077453137495863845140433)
[+] Try (5154817535857960073707963384183439709586920855602419290358137674661940402006427565850098044416106066822250682276679669427811522910392723378330585054966700, 10496354188266114334878155842846706785121191402898647321044421232085059338092949629088561418326794767424754926615669196297619927139682997591511869107757767)
[+] Try (6184278632740706257559650240918607859111635320246236350819849684258206208438537742565177660943106119452934940861754989735447208681922747166941649495976923, 1684156496026762626171388002895398201456656580507920519170549327618625423797366792075116257872626605002727580286505567977884867816788235806054395449066065)
[+] Try (514519457570888784111073733278759745960446948568600524535727800070517989361086156941193628192360355612444575477626855845530581162562486612799738968800436, 5279615925666476607393445956667230310409008481693792914481184221733250114518482573243209594428350182047703213893421465095795062348864307647570060060929176)
[+] Try (5311179737168594393380387500131139705986775208655298446331668896011718110177021579502837999280939324755245947626117007502618967826854797851195037805622236, 7950931857867551139311900477185535034704935066837216411367230952920436620973145933605969605301127988180373211783836800949372831376277678318587671147544812)
[+] Try (8033599809537397449739222496469120219661376235214159758353162913590149327454313351545152320436531803584693342228310830634381278274606584366951286641362730, 7363787374432448634707849149426821610638073413299588217259428219319013703633673213128364594170782521444300561327439516770200289550957339013848496654479674)
[+] Try (2051625798280743150753404437482448207490537448098276190886365473636618906352671153607072757637879642085246666882064116331781620620841788195957363592387053, 183450164326164222959035748035117444906396515108356683081562421715885871762215055266356577117853857983960152113987173865737809535655981046541363297829205)
[+] Try (2539152850168044131443627430873275266571063321601722994164719426048365057966357258486918206613866328867765905303734883912389577646355187342721384787506424, 585756688754350904695498684365256423604945135941557021419402686079315456435190920620640430630667903578283746531894135845972607789350856875988416502844449)
[+] Try (9008908156612389991869885743985152554064654014600155665167153423864293462953589139136986609123719868913243556793248046592418855144217044361551263069240329, 9289266081720210076238040168621209559442099796466275176059195696650031235127294873962598972974303719540193547570326682610716804488839647659399702777957625)
[+] Try (6803170457708082062222117551095454287816962526481935030699353660846602430067188624302070998045883149555451692203871683262881999463532897654910797581195808, 1643238506993581048346556120580389927181837132286120379981936140856072993887401596354919001634656489755991432524216993664019969824657062288544062028928533)
[+] Try (4342007382390611975323457544296213170925503797306373729093603079594595092127747819980737254901463722358222828653606693041546906868729342511025828114827555, 493026654262682081757325540069692089465639980280029378402651778901949559259891879708898948140085681814535573742826826476110468079719504023996492906928688)
[+] Try (2183664030657588356550029801438062011696791479721050550709966793162412846063789309880633528422512509596396589027054806885718000781675200132948682901735072, 4073523873469606498132661552527997945998461149945931939857824343164584528157149801459596694594269553069502164902110100517378462894925649504277727979281804)
[+] Try (2676285609364173142435111238008478736925861736006673806161674291385422525644573866393884559955797190936826061311631872102982470113155601869660746965071177, 5526482056568056411108977820792619135217540155238365597030616097363450824489623669450770143884401364973046003465586645009073389711906524301615929500348726)
[+] Try (8615874523824944863326511893784594675845807173709888717969574953112250736770386882455890231726119912526638461175690953959512359266034187901901745135706561, 5107189939984481100533490360348985070143842143450775903588073100128259350554726370669643384672212451094463934881485403663403067465232413753838963311526164)
[+] Try (1922646621448654308731099545672266646199287008430733010575325812508661111446471076682347110401317422369989378526004562648871357970249460937394842515685185, 1338120870830450195003052688429825997002475569804112786250323375715461269426478757154438256599704658856730012976479429755682431385902070463000523922633485)
[+] Try (6894871210132644262428509750998583740904489962095581087369230603087765684170566562618210470507349665138476792990203975299249821414179702286974952108308908, 4504561167146108444334786062824835552812933921903812225075224152011097132132118554220621595724113517743942246047411740399148959904624805479075676539627179)
[+] Try (8398850863544147035551562678201580675747803434116699749690629994755381632713482161869699483278515661816496168924359580050657657882041095486710223992321329, 3703218408290286096237533977791248727917587395526646685991666829723493582004703462287201605547754231978350368593066630613342669719057740600396410750130713)
[+] Try (1103558165483499140082633087824207492178842328222110372040372946709534675630035763166805943256640202241094017653484224302180964104596684146937840328056737, 4235755736045407691815950643821304187431993958805648566903603216981196118628996746825748374999189542155866127214016604808037761824195261283013629856811915)
[+] Try (7616579463842058663956538981992016396022484825826970703537944742179864728054422301128359842636130918256966522509540733872238802637426513398702545806054711, 7613956756687648883142522461784563921781848082096750733536680658594629733709520676386003626030270049444324311590771818500145651113869039994374079094176389)
[+] Try (6093447739151580910739487321763042257093662388037797880895310207982236604441330252766468220299149762533760095283275798097190217074233307392113562823550055, 5582983596876204457658414033643566916925741632988960872444165950150568674358568563750393895942021859292068409582131557028759494904690654084568015540958387)
[+] Try (10465708577087930103510908920924173959169681089467884381473219422666982876773505479708456794740072800789393882374346444466352555495590221538783880064776747, 5560992116323139630261388939207466766129106144662938095552878745416852271253443975908911908133192704735692594156704890845632323597567684452235384416207560)
[+] Try (10605081135879456867591725577517023044111094541257015514457259942700651158240017447609481228325274221251138332472541861502584164767676203023712244274563455, 9427064851222629681715722784660850738968685559393550747518608089108082562625632566953024798342737795332503266772616759203825637407245190460310558481011553)
[+] Try (7012967814560006293648272691588998637134646550513726240939227681138521268647913550031357555656822375449692357834760862939125678022083697005023949012937826, 7751396645197086848500999313322914076346713513943719371985230447422327437680224631606199418400131531054197437203771034578401374585091741737281898844967403)
[+] Try (9566656433910278946608540460883633932965000205012896340833001038283123101223701427477589683926930217368102196484226996825067156057344586227513445332021767, 546093125292516349289304554067672438202855144942643384818235748136017154830766962667037846395737218002229971788635923471525750360984025965229960880138015)
[+] Try (2721818943333539016612702886003757042711221957746352716329164140315057299599294376527853842627041607856599108409067242878086913811106172846700928991925332, 8708958215469085753181574046119339162501035682760128157682876145155787404749378257091769354933553751411564910339364737060790592181298353503681772458140296)
[+] Try (4144627466364250800792304430295727495765908688276307878705582041004315000843879026660231248370219826205974342880901591994064400526974281681872092036583360, 6503617996420087519121999497592564753358269947368728580707909964656915488241450906561184006580947106530919025122027342914550816267613360293886470939638147)
[+] Try (9540229122766028258950784907897705565229274273296271759903007071156790536497946170835990412260104194662363036458196704652014673749423907001422969301809735, 3133970773026394333676271959039363252995983077058359556442048424274114546996306660500141330973026720710258226380296916344738000286752906153301531192145588)
[+] Try (1639227724203684234308217138545474026323237719482542327552473107710807011133804919537706806005714199832933437746623612694760178087234912102227060818821785, 8270247841707725063403103311221827713218425321540707437203780169848645054354422606444548218532045886590764337285894491599474684125156258721180140005227879)
[+] Try (9812993094473406654107168236073328125261683326416570529798110665650382711989965459219636103724052319209618994008458512967332799786202713476231778145396012, 6348941299458047229603035571553554254637277183847732341685362698641456768747093952193394610221610467378544424914425383192254952105296121873394965907483421)
[+] Try (2295945877832163407010322597202468334423912618570523561408751634022642288041211919141444020534567414838616766574885544294608146290275196633317265741751883, 5994603535835080395017357896928637354820646460778770882917760856532399920260202826867821549261784608902276626362339800015674269038970155327507870854956789)
[+] Try (9510449404755931940739075753727979306152379874217663126425580183559239591750519861496413596214874972534376534993718874211977861576694865786452346685079911, 4425254452956426634646344097191468359576571843417153278931037524323172136339917846491397351511099933539635058142094213472513676095819902241563092702688501)
[+] Try (10068147483643758261431583499786421277358011934810052604576663733186448278692924596285775100821424123316623283150527146388692332413482534235601982259977735, 2486099330626766737257165308745024530097078778638782229355520177306987440002696878039888805275868528396743863481534888478552983793450062429371941132535078)
[+] Try (2631234993744978915205564833565878360368731366415913670587100334887962760531396262264711195036515169369826941240935633330766040802965514627738944637938312, 4167116570391804600255654075462038844507091559173265725625706455067299132147050347586004334123441342458308129150386241209679630518761986850258774882817936)
[+] Try (6245294849421435385844087800549243031764408455344779721346137213398733894945891825456797247066883570457936878961279970460851977076618685374684565064011000, 10185168995554407266816276622812659886483756602705301925351101031752727294301531965596293802652862084495500685833881517475134558625964721775303100038614160)
[+] Try (6360363966721028786772622616611684728619548477569800250827865049949218224355237880474537231095562612445154765235574973379248267372638478052576176958426893, 5456722125978665120229905841107251183374955393168570741251463630873840897267613318536370613164271366075428107312082239190184994439809325775182251507346825)
[+] Try (1374748162508202790788170508306104425630569793823780168413397583022077368721695853340144854392562470438547910808098360313836434314988050372444336622005939, 2939543075586963360992868413324864290837308216610370795940797957094565066506489483089379278658514795189713701943386974203309580258770009927268150497535566)
[+] Try (5923217938277229682931188522357086770659121539648879409111011010394233354709847779031983270180639474376432548198701507987857799064509215702865822042304601, 8743821334723368976778894507033225804145157545090682229505938930782456568432992185052055300701880227956622698441050884506223378607674824402614530393729367)
[+] Try (7912839476386587387207319066546154431303391126303542720169612844312157005989844595260178178012638805394179538160638000205856329132154797855491159908316825, 9157713754021073809434421172656952683393171530300224019784181318620517764533872565796337369744270420561987117136110183189161447503240922447481705416792933)
[+] Try (6989926221520213501850965026707723308003729842929136196471532798477250492469686905792383597327729987647258260679589434132606672791962970232535673677457343, 5878746531427980282714190471263188376089128406106851686623310774890789241719381568167580210027581541900359110459878728688406025608100014784866859967415069)
[+] Try (7743517306425849045036228617259140769029348885373635895025449298661791309426243487821079837754283770418719515017823088333131732906019584031613089554304420, 4723171396311923892248342600001144805520828588734579829312137837892547473549988680030764497200183283689846461436720606808050677973475562028290802376894040)
[+] Try (8228064864747011743632289680585658563799395413457976150375450901737657367769151734010130073897880115256353583883179331874018722072209939664833555092694721, 2843792191169572505424299937637335345928688319904295706002781014868972565908100208212634694593060855068754141546774316683717972204080538819157716088784950)
[+] Try (4450010894214163101815316096785687407009534536454667314772668698898901466717062024203232842836467444518468762248095700604843848000837792037078167960588129, 5649760949181251560547472271598936178113043683541495970916235935289470274241813254378868964502496661853777833292127852117859645515779670872354035434010971)
[+] Try (3345145753946526259843311380078979114463790107484347721093757348344369710001786833260087626842713916819817705043732430232104986213669502412941799451378137, 4449864701816030502869094392702038297167798303739676692580712480289620671504896451221373121095485571657769741067946182294271935296786038388717131050743105)
[+] Try (411849644960126121049073725849225927315782894933779533599764821078891693733248333351876043256232845616011887951112364725817456430915422262433159009162810, 6015559474636248088561229697316533148096304587912722704321346276808664704462122988070466258472892491390452320498582384705624788234989258086915479317589554)
[+] Try (9070143529402968690182170891432541186624926767431297375488478998005501150531907444673746153178512705131935537332064808055931815290499208703009298348987029, 404470006641663392206752968026191050354477219085475176007692089093673919513513760805174543858749324166919507964495235284709646802332010921978754916213842)
[+] Try (8213219975300001733306975337422619448976655134956761580838409562843071867497978077677323154897320151428562911412904177153952495821256190104983710364972232, 6400060591708772742036825960295348204573787431673486966335080578765346768135800288344580251211949027002658413241092081227396455353862253913043273557206036)
[+] Try (8349268362247390165742295418698754062525395439803096486083911273583071915526604580013826747245858881943244980602181641712932537086321708434534161167021746, 4139621554482255887742647243977351847150733617205749719993940245058866579901045219083635101090422724513229414103870573743420533567984369212416328299201648)
[+] Try (7509668912649960854961670452151045790218876057511153068414836771472470302685381796706603632853037886139531473147215132055911891985689199108998563497337555, 3168193697707475529193822215328153723009219332354194589973887573663124790963735981601241436331461792216723819214300690004321006157765917632838358657075965)
[+] Try (2131204693980301034358939270790217044118874047688648828664882105193013493634681490541248365340356833966291527168399270652784557243494787018476812050661672, 7458978598400749076925462287692314594837852961494454950837549434543148869247423634127441385921463980373281159265749886433453416941713109715452118403890765)
[+] Try (94628342448609390736618683703832565995079347007818829426672834242066920587964251445868380536604059942251553430692068690115557207157069742355783092463878, 10491155550479668966723346610934052049109810767277413338024524325905994360818069675936484156539236718504294063495115065935392782490138348869081026608020887)
[+] Try (8730838489034161299210542834892857189755559366635478365056603032000438656615452617258885131782074530795256008985786448336781306335727153569211343667279688, 8076329104944759931627228905172809552808063163769317826043905443799635345365021015532382100166858241152720115250871898592915217180839896374819810099249842)
 c = 61040814411609979711931510878805548760848686739454567580358315369154260598969544907138563610735920809370306294050956464828615417082277087799410050319871691154003766481799397897519555113273982347768485719165972634089532894585256662433949694618032747408071953491187718726218120284389638124624152241321006634774
 n = 66022752859576751705544115674843820574619778139841743306742674741819040147745776264697779394213058328572691946505564202779552568613562176486470653760142864852745249430164256770469301179840812051842363261404790355057115296671805975126795017665392798621718740402876024901551851638786170466127104615340863081593

复现write up

exp如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import re
from sage.all import *

with open('out.txt', 'r') as file:
    content = file.read()
numbers = re.findall(r'\d+', content)
X = int(numbers[0])
W = int(numbers[1])
pairs = re.findall(r'Try \((\d+), (\d+)\)', content)
c_list = [int(pair[0]) for pair in pairs]
C_list = [int(pair[1]) for pair in pairs]

R = matrix(ZZ,len(c_list),2)
for i,c in enumerate(c_list):
    R[i,0] = c
    R[i,1] = 1

M = R.transpose().right_kernel_matrix()
M = M.LLL()

def compute_kn(coff):
    res_right = 1
    res_left = 1
    for i ,cof in enumerate(coff):
        if cof > 0:
            res_right = res_right * C_list[i]**cof
        else:
            res_left = res_left * C_list[i]**(-cof)
    return res_left - res_right

r = compute_kn(M[0])
for l in M[1:]:
    assert list(l*R) == [0,0]
    r = gcd(compute_kn(l),r)
    r = factor(r,limit = 2**20)[-1][0]
    if r.nbits() <= 512:
        break
print(f"[+] r = {r}")
# print(factor(r-1))

g, x, y = xgcd(c_list[2],c_list[1])
g = pow(C_list[2],x,r)*pow(C_list[1],y,r)
assert pow(g,c_list[2],r) == C_list[2]
print(f"[+] g = {g}")

n = int(numbers[-1])
C_pos = [n*pow(W,x,r) % r for x in [-1,0,1]]

for C in C_pos:
    G = IntegerModRing(r)
    g = G(g)
    C = G(C)
    c = discrete_log(C, g)
    assert pow(g,c,r) == C
    p = int(C*pow(W,0,r)*pow(X,c,r) % r)
    if n%p == 0:
        q = n//int(p)
        print(f"[+] p = {p}")

c = int(numbers[-2])
phi = (p-1)*(q-1)
d = inverse_mod(65537,phi)
m = pow(c,d,n)
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(int(m)))

NSSCTF 2nd

EzRSA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# task.py
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
assert m.bit_length()<200
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3
c = pow(m, e, n)
kbits = 103
m = (m >> kbits) << kbits
Mod = getPrime(1024)
hint1 = (2021-2023*m) % Mod
hint2 = pow(2, 2023, Mod)
print('n =',n)
print('c =',c)
print('hint1 =',hint1)
print('hint2 =',hint2)
'''
n = 115383855234466224643769657979808398804254899116842846340552518876890834212233960206021018541117724144757264778086129841154749234706140951832603640953383528482125663673926452745186670807057426128028379664506531814550204605131476026038420737951652389070818761739123318769460392218629003518050621137961009397857
c = 5329266956476837379347536739209778690886367516092584944314921220156032648621405214333809779485753073093853063734538746101929825083615077
hint1 = 153580531261794088318480897414037573794615852052189508424770502825730438732573547598712417272036492121110446656514226232815820756435437665617271385368704576530324067841094570337328191161458300549179813432377043779779861066187597784486306748688798924645894867137996446960685210314180286437706545416961668988800
hint2 = 130939024886341321687705945538053996302793777331032277314813607352533647251650781154105954418698306293933779129141987945896277615656019480762879716136830059777341204876905094451068416223212748354774066124134473710638395595420261557771680485834288346221266495706392714094862310009374032975169649227238004805982
'''

复现write up

比赛时我被这两个hint给迷惑住了，还以为这题考点是明文高位泄漏，一直在尝试用hint1和hint2解出m

殊不知忽略了e=3这一信息

因为n的位数也不是很大，所以直接使用低加密指数分解攻击即可

exp如下：

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
from Crypto.Util.number import *
n = 115383855234466224643769657979808398804254899116842846340552518876890834212233960206021018541117724144757264778086129841154749234706140951832603640953383528482125663673926452745186670807057426128028379664506531814550204605131476026038420737951652389070818761739123318769460392218629003518050621137961009397857
e = 3
c = 5329266956476837379347536739209778690886367516092584944314921220156032648621405214333809779485753073093853063734538746101929825083615077

m = 0
for i in range(200000):
    if gmpy2.iroot(c + n * i, e)[1] == 1:
        m = gmpy2.iroot(c + n * i, e)[0]
        print(long_to_bytes(m))
        break