赣育杯2022

2022-10-09

Crypto

Wilson

由于rsa的私钥p和q取的很近所以费马分解得到两因子，威尔逊定理为：

$(p-1)!\equiv-1modp$

其中p为素数。之前遇到的题目，通常把flag放在modp下求解即可，示例；这题经过pad 明文的比特数已经超过p了，所以我们在modp下求出来的其实是flag模p后的结果，也就是低位部分；因为copper没办法做所以考虑在modq下再求一次，用crt处理，具体一点：已知$m=flag\cdot(p-1)!modn$，如果给m依次乘上$p,p+1,…q-1$，有$m_1=flag\cdot(q-1)!modn$，这时把$m_1modq$得到$flag\cdot(-1)\equiv m_1modq$，所以这里求逆就行了，最后来个crt即可。

from Crypto.Util.number import *
from gmpy2 import *
from sympy.ntheory.modular import *

def fermat(num):
    x = iroot(num, 2)[0]
    if x * x < num:
        x += 1

    # y^2 = x^2 - num
    while (True):
        y2 = x * x - num
        y = iroot(y2, 2)[0]
        if y * y == y2:
            break
        x += 1

    result = [int(x + y), int(x - y)]
    print(result)

a = 156853895847604116708242664263151514811095704969640303272039451331791888050995073274981545693518063639560286348739938318495685137088495867703518198511200409009953879436648706837731243061114851474801565873584183542649886358523850682697732574913523360866915083642887238043256280849100274825940626065115676325169
c = 3459715117165130065996389169943285249501133832272446001239391765859259811270526185228996906338576254353123756173289118671028939933226544773197852424767051933844004667155191851195814295922794480300237399956789038592856532530692732011427288405114650955620859282144504446058845961744702163836107847961388150810

fermat(a)
l = [12524132538727147976454683542869473176723933298740764667643646868771435739017779964538584767004546975861773724104399289331497224456192089483187179727966173, 12524132538727147976454683542869473176723933298740764667643646868771435739017779964538584767004546975861773724104399289331497224456192089483187179727966053]
assert l[0] > l[1]
p = l[1]

e = 65537
q = a//p
assert p*q == a

f = (p-1)*(q-1)
d = invert(e,f)
m = pow(c,d,a)

m1 = m*invert(-1, p)%p # 求出来的是flag mod p
for i in range(p, q):
    m = m*i%q
m2 = m*invert(-1, q) %q # 同理 flag mod q

sol = crt([p,q],[m1,m2])
print(sol[0])
print(long_to_bytes(int(sol[0])))

Lost_N

这题原本作为一道想要考查多个知识点的套题还是可以的，但题目脚本和output没对上，属于是很容易误导选手了…
首先是第二部分要去求last_n，根据欧拉定理把s对n求逆得到$(900\cdot p-218\cdot q) modn$，显而易见可以把模去掉，所以联立$p\cdot q=n$建立一元二次方程解出两因子；第一部分比较显然是共私钥指数攻击，用五组解出来的d并不满足题目要求的435比特，看了下output里有两组非常离谱的冗余的e和c，于是把last_n和这俩组合一下作为第六组数据造格，求解出的d刚好为435比特，解出了flag。这里为什么觉得离谱，是因为题目脚本写的是循环输出五次n e c，结果最后需要用六组去造格，也是逆天了。

from gmpy2 import *

c0 = 
n0 = 
e0 = 
c1 = 
n1 = 
e1 = 
c2 = 
n2 = 
e2 = 
c3 = 
n3 = 
e3 = 
c4 = 
n4 = 
e4 = 
c5 = 
n5 = 
e5 = 

n = max(n0,n1,n2,n3,n4) # 取最大者
M=iroot(int(n),int(2))[0]
a=[0]*7
a[0]=[M,e0,e1,e2,e3,e4,e5]
a[1]=[0,-n0,0,0,0,0,0]
a[2]=[0,0,-n1,0,0,0,0]
a[3]=[0,0,0,-n2,0,0,0]
a[4]=[0,0,0,0,-n3,0,0]
a[5]=[0,0,0,0,0,-n4,0]
a[6]=[0,0,0,0,0,0,-n5]

Mat = matrix(ZZ,a)
Mat_LLL=Mat.LLL()
#print(Mat_LLL[0][0])
d = abs(Mat_LLL[0][0])//M
print(d)

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

n = 20955464633057600258987829727550073699845816289000240676927869818926752810905511184835302717855745473943671910742784074561535017974853574714483642916831791020944940633062963043482236587316552330558006573820423830770910893877191630012247591380869307656539553888318621170921800017818132160253923739647771452839191101104391894609403591447166963426444018303147924843072923713248135717578047687411974516038299879758561542241544862102935741869647633013298181782208467117482306148238724598730801037692668154263059348953587766571379262442743822007387408949824805991797355089583176028081305319076896384126383926193964322235633
c = 14815997295683082265558346455845370590765145583224067337292601455640475216349267044144296003388877395546880235511728120803143112914764263292087421926972160283428440959367872665892349776616002018624301524264223581314248857537034849571849747613963209414193510408342387107662655487869098045345428379025731617851483935711671021438908270746316921057871871545763798735895118697635903815383424855759281301248295597297869474539060531099443223045844791615425429748703429968627505406271675074549912664863784774239200764403372298995457799473112713379340870305136776932539188516395526955161359417473843082895317392495109895085666
s = 14728527428626630951705148488338433865446345521255631461200851513782412494843597938863837697938230856843797646287742397249258609197032095158567448934855031190354034543862057663422053672290704598313096289223478302733688501373756860855445632789922930577582465209872782549135254792729915747104521949095814028476908208917363509089190935273004331739978623136706041729628143765893264698948654175039064609891374587695812144855411176143224066975193255513405865992328257766815240718115442741846443490733767716842367336385132648983241895710001620533668392060358573295789752856876282590472528110546264872047138094995909454134250

s_ = invert(s,n)
delta = iroot(s_**2 - 4*900*(-218*n),2)[0]
p = (s_ + delta)//(2*900)

q = n//p
assert p*q == n
e1 = 0x10001
f1 = (p-1)*(q-1)
d1 = invert(e1,f1)
last_n = pow(c,d1,n)
print(last_n)

dd = 52771251618246422496055097735715651807711833222951670020329880144899822430509798260393871381119460882023717774862539491823372729841
print(dd.bit_length())
cc = 13007070082982086015048648249698272815655157209727275797297990841215796701955079738986996208838342773211678208282162295881823413924960399315068498509939876883297864092435101096694113071462267388158595518905101264654742860199638059278239359756219217345342001728599121265614144789005805619626458575126846199823
nn = 145575036089862184772968012014750816659166028840828357885024516131565102712346345625910708214596157522939248398359985832422106056149116726640753670919394145037581595172384392223713667048639158944450925280598688178812170253438103664700756173806183649477673497327790421063029596049211220930285435947389700047717
m = pow(cc,dd,nn)
print(long_to_bytes(m))

Misc

byteMusic

图片的lsb有东西，分析hex可以在文件尾端看到一个passwd，猜测是cloacked-pixel隐写，恢复之后得一串指令：

a=64E3,80*(128<t*[[6.5,7.3,8.7,7.3,11,0,0,11,0,0,10,0,0,0,0,0,6.5,7.3,8.2,6.5,10,0,0,10,0,0,8.7,0,0,8.2,7.3,0,6.5,7.3,8.7,7.3,8.7,0,0,0,10,0,8.2,0,0,7.3,6.5,0,0,0,6.5,0,10,0,0,0,8.7,0,0,0,0,0,0,0][int(64*t/a%64)]][int(t/a)%1]%255)*(1-64*t%a/a)

google直接搜指令可以得到bytebeat这个项目，把指令放进去听一下可以确定是《Never Gonna Give You Up》，做一下md5即可。