2023WMCTF——Crypto部分题目复现

未分类
1.3k 词

总感觉先贴参考有点乱，这次我把参考的博客啥的都扔最后面。

badprime涉及了一个漏洞 干脆单独拿出来了。

目录

signin</h2>

源码：

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
from Crypto.Util.number import *
from random import randrange
from secret import flag
 
def pr(msg):
    print(msg)
 
pr(br"""
                        ....''''''....                        
                     .`",:;;II;II;;;;:,"^'.                    
                  '"IlllI;;;;;;;;;;;;;Il!!l;^.                 
                `l><>!!!!!!!!iiiii!!!!!!!!i><!".               
             ':>?]__++~~~~~<<<<<<<<<<<<<<<<~~+__i".            
           .:i+}{]?-__+++~~~~~~<<<<<~~~~~~+_-?[\1_!^           
          .;<_}\{]-_++~<<<<<<<<<<<<<<<<<<<~+-?]\|]+<^          
          .!-{t|[?-}(|((){_<<<<<<<<<_}1)))1}??]{t|]_"          
           !)nf}]-?/\){]]]_<<<<<<<<<_]]}}{\/?-][)vf?`          
          '!tX/}]--<]{\Un[~~<<<<<~~<~-11Yz)<--?[{vv[".         
         .<{xJt}]?!ibm0%&Ci><<<<<<<<!0kJW%w+:-?[{uu)},         
          !1fLf}]_::xmqQj["I~<<<<<<>"(ZqOu{I^<?[{cc)[`         
          `}|x\}]_+<!<+~<<__~<<<<<<+_<<_+<><++-[1j/(>          
           !\j/{]-++___--_+~~<i;I>~~~__-______?}(jf}`          
            ;~(|}?_++++~~++~+]-++]?+++~~~~+++-[1/]>^           
              ;\([?__+_-?]?-_-----__-]?-_+++-]{/].             
               l||}?__/rjffcCQQQQQLUxffjf}+-]1\?'              
                ,[\)[?}}-__[/nzXXvj)?__]{??}((>.               
                 .I[|(1{]_+~~~<~~<<<~+_[}1(1+^                 
                    ,~{|\)}]_++++++-?}1)1?!`                   
                      ."!_]{11))1{}]-+i:'                      
                          .`^","^`'.                           
""".decode())
 
def gen_prime(bit):
    while 1:
        P = getPrime(bit)
        if len(bin(P)) - 2 == bit:
            return P
 
pq_bit = 512
offset = 16
 
P,Q = [gen_prime(pq_bit) for i in range(2)]
N = P * Q
gift = int(bin(P ^ (Q >> offset))[2+offset:],2)
pr(N)
pr(gift)
 
inpP = int(input())
if inpP != P:
    pr(b"you lose!")
    exit()
 
secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]
 
results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1)  for ri in results]
 
pr(bs)
pr(rs)
inpsecret = int(input())
if inpsecret == secret:
    pr(flag)

第一部分

和前两天七月赛类似的问题，比赛的时候改了深搜的写法但是没有出来结果（深搜部分+cooper；深搜+爆破gift高位，前一个2小时没出东西，后一个代码没跑完）。

解法一：来自学长tr0uble。在确定p的高位后通过N//p求出p的高x位，然后再利用gift异或求p接下来的x位，不停重复（考虑进位x选择一个小于16的数）。不过因为这次无法直接从gift获得p的高16位，所以爆破p的高16位。这种解法显然效率比深搜高。七月赛那题只复现了深搜简直是大伏笔啊啊啊啊啊啊

以下是核心部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
xbits=8
for p_high in range(1,2**16):
    p_highbit=bin(p_high)[2:].zfill(16)
    for i in range((512-16)//xbits):
        p0=int(p_highbit.ljust(512,'0'),2)
        qbar=N//p0
        q_highbit=bin(qbar)[2:]
        left=i*xbits
        right=left+xbits
        p_xbits=bin(int(q_highbit[left:right],2)^int(gift[left:right], 2))[2:].zfill(xbits)
        p_highbit+=p_xbits
    p=int(p_highbit,2)
    q=N//p
    if p*q==N:
        print(p)
        break

x选择8还挺巧妙的，七月赛wp中有见过选择10还是5的，会导致留下几位需要爆破，8是刚刚好求出p，同理x=4也一样.

ljust函数用于右填充0直到512位，并且左对齐，和zfill刚好相反

解法二：来自石氏是时试。思路是深搜，但搜法是爆破phigh然后从高位进行深搜。

gift的条件用在了 if v=='0',一次淘汰一半；

N的条件用在了if tp*tq>N if (tp+(1<<(l+1)))*(tq+(1<<(l+17)))<N

和低位搜比可以减少一个2**15的爆破，从O(n^2)到了O（n）。所以在较短时间内出的来结果，不过代价是fac函数里面打了不少“补丁”。

同样重新整合了一份核心代码：

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
def fac(allgift,tp,tq):
    global p 
    if p != 0:
        return
    if len(allgift) == 0:
        return
    if tp*tq>N:
        return
    if N%(tp+1)==0:
        print(tp+1)
        p=tp+1
        return
    
    prebit = allgift[0]
    allgift0 = allgift[1:]
    l = len(allgift0)

    if (tp+(1<<(l+1)))*(tq+(1<<(l+17)))<N:
        return

    if prebit == '0':
       fac(allgift0, tp, tq)
       fac(allgift0, tp+(1<<l), tq+(1<<(l+16)))
    else:
       fac(allgift0, tp+(1<<l), tq)
       fac(allgift0, tp, tq+(1<<(l+16)))
 
 
N = 98979914203938129582559002435937496221944524872097792710858591458834482668375238153375967732236519828009052634712155154350690793290568934757567632244582037302853487654784427703489685593524935643730962265977918060749885961377108833870686012325836049467328687008560530162352822066119244817994253171179069223963
gift = 155694596915298991572712835680119486137562835299346062724576858196467035731310426290930425057431831070744019220387957576198359284021046204571309474734
offset = 16
allgift = bin(gift)[2:].zfill(512-offset)
p = 0
for phigh in range(2**15):
    tp = (1<<511)+ (phigh<<512-offset-1)
    tq = 1<<(511)
    fac(allgift,tp,tq)
    if p != 0:
        break

深搜还真是深奥orz

解法三：官方wp。

第二部分

hnp，但是改过一点的hnp

看到了新的wp，可以复现构造的矩阵了。

ri=(bis)%p %2*16

ri=bi*s+k*p+l*2**16

l*2*16=bi\s-ri (mod p)

inv=inverse(2**16,p)

l=bi*s*inv-ri*inv+k*p

大小:ri——16bits；bi,s,p——512bits;l——（512-16）bits

构造：

（ 公式块在网页上显示不出来矩阵，总之改成截图。）

lattice

其中

n=37,K=2**496(因为l为496位，对于由512位的p决定大小的格而言较小，若K过大会导致不是最短向量)

tmpb = [int(bi * inverse_mod(2**16,p)) for bi in bs]

tmpc = [int(ri * inverse_mod(2**16,p)) for ri in rs]

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
from gmpy2 import *

p = 9463395021022080495725625579099709864198202996192818493676075430361086175809577174253865589866353281287908307347544682931439681148579311956298173287376473
b = [6099745272052586004179912608738971034534930536137743613897081917185107394368705591323971750395506839750452649288267772188419489756675205679949408086451232, 3951191747812729045440242820895124607189480251095163295242628450942998752364973601131023646206377502005591988554681151953526704565202075013281769088815523, 1404420597554404030107272770922253996678162333687352195618251218863999850248824692838151822875031075053556888677319712477280556217652901167451648905364386, 4488294572333656708259420377539737505003996159677656468026097114601711607985567015550450770914323371829296766770532559711193361180597308950367687185966302, 5481102322187479419436505829074865646684095327365195150222467418442873465357487402747218531517017371054667814520443813042860956594726076176855372054132653, 2713802788133698269409249999536200419140314121130473258656206052429002170951741696862581935955915442467962543363756219468741646383480138223283730677285687, 4388471418937878873760244311226931102311967761139597301227595095454037495066960891301104963760391091058605030114648033892461656189445282496553583505973028, 736776464731641575781839292404124851285324500513593675528872423711514787996001241149637426869001948983773230073266488914216375314221965655672656410584443, 8708590989237325341864969642266721092908150322862807883501307022447092127465507299112990850265948137001397701186114982614486130822490540038423320215334626, 9267802304424548397960617736597723635936811251609846290761762903654804678628923862108480264307805107896646269881938313148864202456071920121260093838052525, 3247108183860325987343060073325154780063121072412546176464075975152503493018889336496636379292425449406827070404175667145192082945885628262842725864496476, 455724435639473173230575250620919313737714978926744740871167992567140510847659696368128186714204899204016766561731806278682654146614456839201295265351084, 9020040064239438957325652010732562703496153379776291386479249377336002129977498901663356523568148111515751758815532962162768918028366620424504879498916260, 7688416580027582769915116662018701330731542853610728083638475681090388890585799679692871117954618858316092856071130163834051800086038254809868956867017534, 2914081803071475210765607707004526189627879912343305436165346830733180111712927683631299251265551199278425089831815911602268284636090898745079700939295508, 1682447624444059192944751083327557927345592086507420627567050313041103192041463642408780131750529259046595170811376763889856062916108841799386014250209204, 5341034619247476123738204666831636378756603282709541857595527812139022510035477000927339770989486054395218479620330803691178416464134942884723827374332572, 8376329702107133848458122442144946089340952412870283575988871694491609215583935392751355281411100977914041577559011007450313560473364023276862308392837927, 9416263788845104843254295633755080717027180798661946550343273052573861692993756745844265654941124801439244186152547374828735493445699134588163894749640836, 2932216738770537817881515093909708415125754815604299999068133848728425671241756819969645781862996905460305910366082553247028095515273709817106865465122590, 8097717669926537250731305609873869963442989665404721303119492230921259587448045170648745406003491170455200904721392690716080842205006420218957357208236777, 2320095372469412381123081241813969183059217183055092564165616040030126466741691823966421813308525807455783827406201671916779545841711101790509143391460558, 2333972164269303480468982231430944844261058855427800172027932923131801032739273832904738225066210544462847760672864166563796956687623202151756145595323299, 9437506711046580131962727129679057367842176159058408153672713703801123411305447877847753662475828865148714651927615052959365575959980181945973888298104933, 5802961795945602293929959252989205060907182950209184792016006564685164829079522333038011701596715377738492900250485584441351844045455427769773524087524156, 529599427933984238231472476175004896612420169200926563371105835757115041890610229232923121353193340603425988395343027602415343623433336040543795697317090, 6402196372034668863055877348065973921962422590516519136977866652600902486323081042430853494022971845631884452544526687998575817840711058028440421779395606, 1230624307875405241534590705586346034433600380745178644341864997283918237998339933919925940523713299382838409046998100995049951280382526255707022024214853, 4939399750563474831690751351208621006534538497525744056731033390661498923441407195386308647381246454241105286776645577202434999611495000302402098783151142, 3991859998040542133259043036343592584436362790235923761833962209989024458819225460294422336721726048826788046849829864060207989750046644621835589699009365, 240857736341741610087615111623321249370900668053282004036464835672779328135852021912344864307291860960709711372109427660351057177543937799209410049857688, 3616083502398202892601882038165628001289992103457989351932690769228627486934029132426774534679657144138989265564646117621513540781010324410148517674825531, 5404612891952879264496112103405811484626424108411041737043110667122266883638660766432812414542841773559389510234873119005979364687689717241678676878972572, 2034451564894992453342874697889924929640864497213866812897528594902646690104681644785346511630568960798405400466505451930160617969903308178504532997741868, 6157490304505265465913231571555412606905748047618103662427174891510009729459475829640015546085845764226272377180939793932164111694580454672032316588788226, 4975964317099024183607476155053005595563615534064262974131837949918711606891694740515965242556735284295717544308022169459365947195601426949094207557584822, 5428476883706514219777167145065847042077736528683727164449312172005302805331073867565107042753732467573625669359225318663458427411189319424302379038071051, 1671914205500553673647970410143909519671590636952787351672356207441593565754364343607635690418391473360926097632568317796984733317042685849430234554815858]
r = [48997, 62415, 23955, 36908, 52443, 4523, 22645, 22555, 31815, 15691, 47858, 27532, 21464, 23465, 45849, 59181, 27490, 6614, 16702, 57463, 52700, 28969, 31173, 41233, 61893, 36368, 17734, 53549, 17913, 33308, 63024, 61345, 33511, 53005, 26113, 59084, 35720, 44204]

M = matrix(QQ,40,40)
inv = invert(2 ** 16,p)

for i in range(38):
    M[i,i] = p
    M[-2,i] = b[i] * inv
    M[-1,i] = -r[i] * inv
    
M[-2,-2] = 2 ** 496 / p
M[-1,-1] = 2 ** 496

L = M.LLL()

res = L[1][-2].numerator() / 2 ** 496
# 或 res = L[1][-2] / (2 ** 496 / p) % p
print(res)
# 1005444529226476196286726437221411001182466035947403146822894574200213482908472882296123424897230218596631139138335919912390102402492391521467426075919696
# wmctf{we1c0me_brOo0Oo!hope_y0u_h4v3_fun_iN_the_fTcmWWmcTf/}

和官方wp稍有不同，tmpb与tmpc没有进行左移16操作，格的右下两个数据也稍有不同，但是对于hnp的介绍以及本题推导更清晰，所以还是用了（见最后一个参考博客）

题外话，markdown语言在博客上显示的很难受，急需一个解决方案

WMCTF 2023] crypto_石氏是时试的博客-CSDN博客

WMCTF2023 Crypto_无趣的浅的博客-CSDN博客

https://blog.wm-team.cn/index.php/archives/39/

WMCTF-2023-Crypto_Emmaaaaaaaaaa的博客-CSDN博客