2021上海“东华杯” Crypto&Misc 部分writeup by Et3rn1ty

阅读量    141935 | 评论 1

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

前言

昨天和wh1t3大佬一起打了上海的东华杯,太艰难了,虽然没进线下,诸神黄昏没顶住,但是我们两个人也算尽力了,给各位大佬递茶(我主攻Crypto,wh1t3全栈orz),Crypto和Misc方向wp如下。

 

Misc

checkin

把+-号删去后base64:

将.删去即可得到flag:
flag{dhb_7th}

project

打开压缩包发现里面还有压缩包

点开发现里面有个你来了文件,010打开:

三段密文,第一段base64:

第二段查找发现是:

第三段:

猜测是图片经过加密,后面在第二段文字中通过0宽隐写找到hurryup
最后在OurSecret隐写中试出:
flag{f3a5dc36-ad43-d4fa-e75f-ef79e2e28ef3}

Jumptiger

用IDA打开exe,发现hint:

int  main(int argc, const char **argv, const char **envp)
{
    int v4[100]; // [rsp+20h] [rbp-60h]
    int v5[101]; // [rsp+1B0h] [rbp+130h]
    int v6; // [rsp+344h] [rbp+2C4h]
    int v7; // [rsp+348h] [rbp+2C8h]
    int i; // [rsp+34Ch] [rbp+2CCh]

    printf("This is your hint!!!");
    v7 = 0;
    v6 = 0;
    for (i = 0; i <= 99; ++i)
    {
        if (i & 1)
            v4[v6++] = i;
        else
            v5[v7++] = i;
    }
    return 0;
}

即为奇数位与偶数位分离,在exe文件里面还发现许多base64文字,提取出来:

f = open("1.txt",’r’)
F2 = open("2.txt","w")
for line in file:
    s = ''
    for i in range(len(line)):
        if i & 2 == 1:
        #if i % 2 == 1:
            s += line[i]
    F2.write(s)

得到两张相似图片,很容易想到盲水印,bwmforpy3处理得到:

得到flag

 

Crypto

BlockEncrypt

这里应该是非预期了,只需要用pwntool不停地发送数字并接收处理即可得到flag,这里先不放wp,等官方吧(貌似暴露了出题人信息?)

Fermat’s Revenge

分析:

注意这里的hint-1011^n和1011^n均可模n,这样才算的快,不然得跑炸(至于为什么可以这样做相信大家都学过辗转相除法…)

值得一提的是,这种题一般题目都会再给一个条件比如(c1p+c2q)^c3 mod n = c4,然后构造差式求gcd,说明那些题目条件其实是给多了的 这里也算是一个强化版的。这题手慢了,抢了个三血orz

The_RSA

从题目可以发现是共私钥d,于是可以用格+LLL来打:

这种题有类似题,见lazzaro大佬blog。
la佬博客

My_CryptoSystem

emm…重头戏应该是这题
全场四支队伍解出,我侥幸拿了二血(膜一波春哥,春哥tql),乍一看挺难的(确实难搞),不过现在回想起来也没那么难(doge)

检索

首先观察这个密码系统,如此整洁对称的形式让我意识到这大概率不会是自己实现的系统,于是,将A,B的构造方法Google一下找到了一篇paper:
A Simple Public-Key Cryptosystem with a Double
Trapdoor Decryption Mechanism and its Applications

对论文内容大致阅读后定位到这么几个位置:

1.

2.

3.

分析

注意到第三张图片提供了解密的思路,一种方法是已知私钥a,另一种是已知N的分解,根据N的分解求a,r最终解密。在这里求a显然是不现实的(离散对数困难),并且又给了hint_p的部分,这就告诉我们要通过分解N来破解。

分解N

先看hint_p:

我们已知tmp和tmp关于s的函数,容易判断在s这个数量级tmp关于s大概率是递增的,于是便二分求得s,求得s之后:

实际上这里选2,3,5,7作为底数等都是可以的。

求a

分解N之后,我们可以通过论文给的方法求a(见第一张paper),这里还需要注意的一个点是论文为简便假定k为1,但是这里的k并不为1,需要我们手动计算,然后利用Theorem 2的方法对于每一个pk_i计算a_i(tips:Theorem 2可用二项式定理证明)

破解

r的求法和求a一致,但是要注意的是,我们求的是flag和Cipherpair的元素相乘的r,因为这个密码系统有个很好的同态性质:明文加密的乘积等于明文之和的加密,也即:

因此,根据paper,我们计算各个乘积m_i,然后再用每个m_i去减去msg里面的msg[i]即可得到flag对应的数,再转一下bytes就OK。
脚本如下(写的有点丑):

from gmpy2 import *
from Crypto.Util.number import *
tmp=2089820154361924508538446108269935994030991606156223866732111667565405536357951576932005538690066537157876197699892075508740495066305688019890842829635043384709521434078225616521711490046642353950430417257110729534241934599342763216934382507890843139336018657335470504043142686710682489530263596109599133035852965109994347644620820009305543437875083895364089690324078052120492016025852286525379384165456287789916135399608320421080142272824648234077271239
low=2**299
high=2**300
while low<high:
    mid=(low+high)//2
    if 160*mid**5-4999*mid**4+3*mid**3+1-tmp==0:
        print(mid)
        break
    if 160*mid**5-4999*mid**4+3*mid**3+1-tmp>0:
        high=mid
    if 160*mid**5-4999*mid**4+3*mid**3+1-tmp<0:
        low=mid
'''
mid=s=1671851834649376689415708146427915127601225639941524508075898365296193782691768373380348719
k=4754554704850256778735590524610198650134411842195769091014820818006719109076990463132664392410346996151618768679351242113559724888503360891602436068027480096077744129030903799750522449629563167331234800938157843104162908741560754165079655724386560424354241873270243951101550271418161866852414027840274660897560505560592778782999814888630027736110016694348246733240044893091852214993195382284720215971750824583201530096744098305208135579825277427773380365958535283046470144144352699812110234265819380925076898066919988177676804355154180985014979937373728326970953528209024041485612988673300305132326622171387609623970503906414505695241100228178195501703362993518592645115413103443814609075683842563042188195716372976033442192563213118978648065192441568907898818839116767361016811780259368084648202006311424864142848992635395305600087965119190953328660288340036554907015710158774036156031291945221415931203408213938539125767026567541875969985838907594310155023484089758562356095813394182426424280944183767485789076221330170873590842770602658661929426473703786140848071549104898060065424610476664198700570104078850887778740665433646775058466342677098034851582851695443468542495004414257971321957486355601109441528757660193703856176230053629793357594015242817161463498657786282023717157539990501344327727261042890805881309270880487651486594529545558459211814637383142541225166192984876428104067186747881829071952656638565990503611295971951908518213836344151288156790569510760651462369074980391496200052235424241684421857862330745967465958892344083059604778452476294040911064848849555467068424693645415363666565337347596180163710543280805007719475566945680597492608452049627829942996048259794057272565854394838938632624405485120604151384323523336231735350133769991732316995630786791632338370892271000890581982409887852570584336019474871417510375712633622
enc=364168919477452275177288189395167167414869138751489184121985413907426061521189393970652444284942775157741893738111375861214494173920580264532672043522061608401896421266479555082359535626662156907449852389982209715294593229701583629316457144094714298196692578461331610576142296232863576092889828437910977086226748575111279612562980180877983723799351156875374575484170690982501932819168284006234307298427566721414580939006864966569199025722100299365638622525673936609610504598686821434477304563148892550317386906790168057436099443902598482791064556278065210485874374001771842502199549744328867942054863716156649959254122968773220677404944484087356502367217643075476723977215258284732126778313821691240220358494906195595337467587283826886671071667739624158902810575893961303489588110532781981585943543589066675386749440182972320352693237913746048468302114626644130848467571134497767565522952060391503399095603790641234782395248309012843987299582268241927917521533701267462933390104019390924464437578002436804421167317073967104374674503105176814728528948427343735476621647120199885109276701712397024328154639390619983337164045167105500823328686232464764826915967847749327330082112747925074426990994720800715530110799953759001555151635338
n=600460780511284177330868641157000673695987686835854463954083292521995333969592493476167947697902815343802416956402564418461185330396778684350062798129905252415602638833115870421557152032066083785426187725812203898078332950694188015058597191293477786950516701485942990210094142645055791703877774275185986345295000660050751386157287259591424166939605047666820243010590903879946466905300504736860699776852427737320969397264311554513703069397528242470117293210115444740392661976555321130158074719793201646023527509673418511212992699499375312949376181154323600672900826407492059853483127089996044006946816995754323677989191449755823864894528385752425068828417493523554498899275159519125970770207694118193871998744238080679525515188046496167114634756062798259204179177568693208245438370548920354155955666309304316902455515568036303240220660822233185141222611614126905823148940923734420089361779356091645199137373856740769558091660626015486509102159187276152182990904489073030532569619103027852669097961046432285733898343974557625880905989744584411457208854260886074598950522064944003991979500370206557083222942598394096262028456760703040633872127687264365851652445324975052709564645931133722958347280735555568469689572544794624984967491279
'''
p=12040018098190209035343148584440204444027280502951398688022511007384797759543092623752033768876233081261249066681970136207504867285658418308047405879381139
q=13330911285322041682394916367787914488059745044202946512248393199577232273297817169660182673419431610710216030458758919521042880431157752957527934595931147
lam=(p-1)*(q-1)//2
n=p*q
pi=invert(lam,n)
g=7920399627581784560608149942910818490216191427930533960593394675850021704679797790627672141459219522856930356532684528060115600487043826391267174143260378623923371927066375111438678530230842521800629488159046765572087426270100182088998248200609197418046538693988349200947002645076435937540452507193564945923925340202807331612781673963093940545364867223990933803290688709597568633060921603794405844221034708913877792222558167269388751558633345912443237108638337991345821247636925148699047702095027489536775360965304641892716958029744054821381313766616755902131744721067109154300568332363667623275058256140501841491951
k=(pow(g,lam,n*n)-1)//n
def dec(h):
    c=pow(h,lam,n*n)
    a=(((c-1)*invert(k,n*n)%(n*n))//n)
    return a

with open('C:\\Users\\lenovo\\Desktop\\a.txt','r') as f:
    data=f.read()
    data=data.split(', ')
    data[0]=data[0][1:]
    data[-1]=data[-1][:-2]
L=[]
for i in data:
    term=int(i)
    term=dec(term)
    L.append(term)
with open('C:\\Users\\lenovo\\Desktop\\b.txt','r')as f:
    data1=f.read()
    data1=data1.split(', ')
L1=[]
B=[]
for j in data1:
    t=eval(j)[0]
    B.append(eval(j)[1])
    t=dec(t)
    L1.append(t)
L2=[]
for i in range(len(L)):
    L2.append((L[i]*L1[i])%n)
D=[]
for i in range(len(L)):
    tmp=pow(B[i],lam,n*n)*invert(pow(g,lam*L2[i],n*n),n*n)
    D.append(tmp)
M=[]
for i in range(len(D)):
    m=(((D[i]-1)%(n*n)//n)*pi)%n
    M.append(m)
m1=[123,456,789,123,456,789]
for i in range(len(M)):
    print(long_to_bytes(M[i]-m1[i]))

 

结语

完结撒花~
第一篇投稿,感谢支持~~~

分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多