2022赣育杯

Crypto

Wilson

from os import urandom
from gmpy2 import next_prime
from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(512)
q = next_prime(p)
f = open('flag.txt', 'rb')
flag = bytes_to_long(f.read() + urandom(80))
f.close()

N = 1
a = p * q
for i in range(1, p):
    N = (N * i) % a
e = 65537
m = N * flag % a
c = pow(m, e, a)
f = open('Encode.txt', 'w')
f.write(f'a = {a}\n')
f.write(f'c = {c}\n')
f.close()
'''
a = 156853895847604116708242664263151514811095704969640303272039451331791888050995073274981545693518063639560286348739938318495685137088495867703518198511200409009953879436648706837731243061114851474801565873584183542649886358523850682697732574913523360866915083642887238043256280849100274825940626065115676325169
c = 3459715117165130065996389169943285249501133832272446001239391765859259811270526185228996906338576254353123756173289118671028939933226544773197852424767051933844004667155191851195814295922794480300237399956789038592856532530692732011427288405114650955620859282144504446058845961744702163836107847961388150810
'''

p,q近似，对a开根求前后素数得p,q，解密得到m。根据题目名称，需要用到Wilson定理。公式如下
$$
m = N*flag = (p-1)!*flag = -flag \mod p\
==>flag = -m \mod p
$$
但是仅仅只通过对模数p应用Wilson定理是不能求出flag的，还需要对模数q应用Wilson定理，公式如下
$$
m = N*flag = (p-1)!*flag\mod p*q
$$

$$
==>m*p*……*(q-1) = (q-1)!*flag\mod p*q
$$

$$
==>flag = -m*p*……*(q-1) \mod q
$$

然后对这两个结果运用中国剩余定理即可求出flag。

代码如下

import gmpy2
from Crypto.Util.number import *

def broadcast_attack(data):
    def extended_gcd(a,b):
        x,y = 0,1
        lastx,lasty = 1,0
        while b:
            a,(q,b) = b,divmod(a,b)
            x,lastx = lastx-q*x,x
            y,lasty = lasty-q*y,y
        return (lastx,lasty,a)
    def chinese_remaindor_theorem(items):
        N = 1
        for a,n in items:
            N *= n
        result = 0
        for a,n in items:
            m = N//n
            r,s,d = extended_gcd(n,m)
            if d != 1:
                N = N//n
                continue
            result += a*s*m
        return result%N ,N
    x, n = chinese_remaindor_theorem(data)
    return x

a = 156853895847604116708242664263151514811095704969640303272039451331791888050995073274981545693518063639560286348739938318495685137088495867703518198511200409009953879436648706837731243061114851474801565873584183542649886358523850682697732574913523360866915083642887238043256280849100274825940626065115676325169
c = 3459715117165130065996389169943285249501133832272446001239391765859259811270526185228996906338576254353123756173289118671028939933226544773197852424767051933844004667155191851195814295922794480300237399956789038592856532530692732011427288405114650955620859282144504446058845961744702163836107847961388150810

tmp = int(gmpy2.iroot(a, 2)[0])
q = gmpy2.next_prime(tmp)
p = a // q
assert p*q == a and p < q and isPrime(p)
e = 65537
d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(c, d, a)
assert pow(m, e, a) == c
mp = (-m) % p
mq = (-m) % q
for i in range(p, q):
    mq = (mq*i) % q

data = [(mp,p),(mq,q)]
f = broadcast_attack(data)
print(long_to_bytes(f))
'''code 2
from gmpy2 import invert
from Crypto.Util.number import long_to_bytes
from functools import reduce
a = 156853895847604116708242664263151514811095704969640303272039451331791888050995073274981545693518063639560286348739938318495685137088495867703518198511200409009953879436648706837731243061114851474801565873584183542649886358523850682697732574913523360866915083642887238043256280849100274825940626065115676325169
c = 3459715117165130065996389169943285249501133832272446001239391765859259811270526185228996906338576254353123756173289118671028939933226544773197852424767051933844004667155191851195814295922794480300237399956789038592856532530692732011427288405114650955620859282144504446058845961744702163836107847961388150810
p = 12524132538727147976454683542869473176723933298740764667643646868771435739017779964538584767004546975861773724104399289331497224456192089483187179727966053
q = 12524132538727147976454683542869473176723933298740764667643646868771435739017779964538584767004546975861773724104399289331497224456192089483187179727966173
e = 65537
assert p < q
m = pow(c,int(invert(e,(p-1)*(q-1))),a)
flag1 = -m % p
flag2 = -m*reduce(lambda x,y:x*y,range(p,q)) % q
flag = (flag1*q*int(invert(q,p)) + flag2*p*invert(p,q)) % a
print(long_to_bytes(flag))
'''

lost_N

import gmpy2
from Crypto.Util.number import *
# part1
flag = b'SangFor{}'
d = getPrime(435)
count = 5
while count > 0:
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p-1) * (q-1)
    e = gmpy2.invert(d, phi)
    print('c =', pow(bytes_to_long(flag), e, n))
    print('n =', n)
    print('e =', e)
    count -= 1

# part2
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001
s = pow(900*p - 218*q, n-p-q, n)
c = pow(last_n, e, n)
print('n =', n)
print('c =', c)
print('s =', s)
'''
c = 13007070082982086015048648249698272815655157209727275797297990841215796701955079738986996208838342773211678208282162295881823413924960399315068498509939876883297864092435101096694113071462267388158595518905101264654742860199638059278239359756219217345342001728599121265614144789005805619626458575126846199823
n = 145575036089862184772968012014750816659166028840828357885024516131565102712346345625910708214596157522939248398359985832422106056149116726640753670919394145037581595172384392223713667048639158944450925280598688178812170253438103664700756173806183649477673497327790421063029596049211220930285435947389700047717
e = 6104905725583061487097813130111812725712623687061285535333592835899028572315489283518324105546236465450024687400996793197533588656449965379858202658832799573292015786259804984314040621630959455897094519928941186899832366216111359619637121411868069759469878142871432060850651758192209783752650530390826992241
c = 59089700172263364510471541430195724136973801897202789650586019199451669728729101831161257990233999290546484165767660146638244043033774379664984894178111808280076960669616271416462197675878517863817855762681885790347812435849975072020273928469523961698304409181769820692602979823921421820511589311465948726144
n = 171055961405321566289532118753767563629109197214150143506779656820887080836894368955104877312070939117885512468517951216152955714212079279910802095156350517032659766690101321767892798466184405283403136505441356956934759143173462058806620784497304916652269667097971495139608875846338091109621496242787157524093
e = 30639328953696065722075015079387560065304228779854040351182305267894609577068955234152835797506237100956072519388029280776532681675227753068574540049244778077615881093270476533536257809592871380358708151151683035275615961208943826349952952069226829397420921321531951316523368786223865432179572145636266109841
c = 24257648301491609274972482189063774024772127961295257418254600487615473027418329077996964279110710299066082437371516700591657843057597234861450272363240630164504734590903528165056021531272324846249133757036680429476939369309982196345252669711604534774523215422683385359295249160897422071732828044179085194829
n = 99735998821682404719682435155046621256882035421263371444758755082217342389922499214602126376005623406797486880520535486455942687180959663032781490782870080236095770591995437146834606144553095293546973559144743704707021952152013362323293717685161426469215016058837362232410103330238322051089471439573994907641
e = 81580834845272005549352820344384188734735397414102222005750919291263464191246301214086773744759605577533897859454210564034313392997143493147211816886655474145064723790935089304983994174659126346174766206623180477360887938029897557683160392738708450965784921553806400996559956745732829531154835363767773681061
c = 105310270039347542993580213074911114373638987155564864341577443142664062749969114572669295115218200093381519732560445712425129105002834596010587656544575627162469582470245756143405705971157024449801127133755773536097173259762599166367688198314997549663330392481942723997656023552049910279885657664434799986156
n = 118810172988175650374012494943583618875926370822995080847518376655089884052560062524542984436965153851285471302754389325839857100631601002627184437173686224779115595776898914116490948408328080895524604124937295381872443370706017215743101755848741173976351916104362193751372512936063892260855907424754174906407
e = 57970672598245590037421993575987847127437841761387257183798066822318596392918179916711068560675528926294272336883938499809087281773070750919594701600347605662910664129043903749270935721912605279738208730075557097647316659218872977257614306133047318781156168440924237849014715453590776000659069078250493480521
c = 50430341205487530895874157969557709374947862873979946417751686643857339147558892228311050765271667685452170747716439387141655285820549605442067496018168606163031122498272292974227360674531814593351170403519198099247839499352696883293133549658442172721339510734646474794377043195182186423251146266787514560008
n = 80837118813383038376595037732171926303253457956240963765871280771175535050976501573174357090322706934194338649978803681581485022992041019276854467388155755920855237665754031077890133388056350355753218650482718197635332681450734918373003830855184694566883308495322647552169761087814135330222306083205629967447
e = 51172856769626923894369204019063376718507295306271724506808987836327051371415876890252665691760404489737902233106400428873399230724307065583727090788789453353097657968301923726049631007431604461521879288667433292135840271678776989737261214286587609316530839676362375173635542358540766454865624476392874630929
c = 24533435736573623334539431528997922833496063510219641412038735658846891237553927656156039267456590702682308774830590768888594750053426705504840854071081487058180327084899496154314864910274839867793265086899109787190447838634454294468362549369144295591261617705578124672391399319219038350878856530074063011081

?
?
?
?
?

e = 71905546659735491498365580186225996341462093571074706903142472266442052559638067842283521897292088493599089076218507596455101425837547743511983105386966540811629138324774640350969049873787070380161376295760563611617178869788237730560614549740931199083194226891873779907795120035746039593933256380499568775673



n = 20955464633057600258987829727550073699845816289000240676927869818926752810905511184835302717855745473943671910742784074561535017974853574714483642916831791020944940633062963043482236587316552330558006573820423830770910893877191630012247591380869307656539553888318621170921800017818132160253923739647771452839191101104391894609403591447166963426444018303147924843072923713248135717578047687411974516038299879758561542241544862102935741869647633013298181782208467117482306148238724598730801037692668154263059348953587766571379262442743822007387408949824805991797355089583176028081305319076896384126383926193964322235633
c = 14815997295683082265558346455845370590765145583224067337292601455640475216349267044144296003388877395546880235511728120803143112914764263292087421926972160283428440959367872665892349776616002018624301524264223581314248857537034849571849747613963209414193510408342387107662655487869098045345428379025731617851483935711671021438908270746316921057871871545763798735895118697635903815383424855759281301248295597297869474539060531099443223045844791615425429748703429968627505406271675074549912664863784774239200764403372298995457799473112713379340870305136776932539188516395526955161359417473843082895317392495109895085666
s = 14728527428626630951705148488338433865446345521255631461200851513782412494843597938863837697938230856843797646287742397249258609197032095158567448934855031190354034543862057663422053672290704598313096289223478302733688501373756860855445632789922930577582465209872782549135254792729915747104521949095814028476908208917363509089190935273004331739978623136706041729628143765893264698948654175039064609891374587695812144855411176143224066975193255513405865992328257766815240718115442741846443490733767716842367336385132648983241895710001620533668392060358573295789752856876282590472528110546264872047138094995909454134250
'''

审计代码，part1中的RSA加密共用一个私钥d，而e,n不同，因此可以使用共私钥指数攻击(RSA | Lazzaro (lazzzaro.github.io))。但由于缺少最后一个n，需要通过part2求出。求解part2的公式推导如下
$$
s = (900*p-218*q)^{n-p-q}\mod n
$$
根据Euler定理有
$$
s*(900*p-218*q) = (900*p-218*q)^{n-p-q+1}=(900*p-218*q)^{φ(n)}=1\mod n
$$
即
$$
900*p-218*q = s^{-1}\mod n
$$
假设解出为tmp，联立如下公式，建立方程解出p,q
$$
\begin{cases}
900*p-218*q=tmp\\
n=p*q
\end{cases}
==>900*p^2-tmp*p-218*n=0
$$
得到p,q后，容易解出last_n。得到所有(c,n,e)之后，构建格如下
$$
L = \left[\matrix{
M & e0 & e1 & e2 & e3 & e4 & e5\\
0 & -n0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & -n1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & -n2 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & -n3 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & -n4 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & -n5\\
}\right]
$$
其中$M=\lfloor n_5^{\frac{1}{2}}\rfloor$。再利用LLL进行规约，取第一个分量的第一个值除以M就是私钥d了，随便拿一个密文解密即可得到flag。

part2代码如下：

#python
import gmpy2

e = 0x10001
n = 20955464633057600258987829727550073699845816289000240676927869818926752810905511184835302717855745473943671910742784074561535017974853574714483642916831791020944940633062963043482236587316552330558006573820423830770910893877191630012247591380869307656539553888318621170921800017818132160253923739647771452839191101104391894609403591447166963426444018303147924843072923713248135717578047687411974516038299879758561542241544862102935741869647633013298181782208467117482306148238724598730801037692668154263059348953587766571379262442743822007387408949824805991797355089583176028081305319076896384126383926193964322235633
c = 14815997295683082265558346455845370590765145583224067337292601455640475216349267044144296003388877395546880235511728120803143112914764263292087421926972160283428440959367872665892349776616002018624301524264223581314248857537034849571849747613963209414193510408342387107662655487869098045345428379025731617851483935711671021438908270746316921057871871545763798735895118697635903815383424855759281301248295597297869474539060531099443223045844791615425429748703429968627505406271675074549912664863784774239200764403372298995457799473112713379340870305136776932539188516395526955161359417473843082895317392495109895085666
s = 14728527428626630951705148488338433865446345521255631461200851513782412494843597938863837697938230856843797646287742397249258609197032095158567448934855031190354034543862057663422053672290704598313096289223478302733688501373756860855445632789922930577582465209872782549135254792729915747104521949095814028476908208917363509089190935273004331739978623136706041729628143765893264698948654175039064609891374587695812144855411176143224066975193255513405865992328257766815240718115442741846443490733767716842367336385132648983241895710001620533668392060358573295789752856876282590472528110546264872047138094995909454134250

tmp = gmpy2.invert(s,n)

delta = tmp**2 - 4*900*(-218*n)
if delta >=0:
    delta = int(gmpy2.iroot(delta,2)[0])
    p1 = (tmp+delta)//(2*900)
    # p2 = (tmp-delta)//(2*900)
    print(f'p = {p1}')

p = p1
q = n//p
assert p*q == n

d = gmpy2.invert(e,(p-1)*(q-1))
last_n = pow(c,d,n)
print(f'last_n = {last_n}')

part1代码如下：

#sage
c0 = 13007070082982086015048648249698272815655157209727275797297990841215796701955079738986996208838342773211678208282162295881823413924960399315068498509939876883297864092435101096694113071462267388158595518905101264654742860199638059278239359756219217345342001728599121265614144789005805619626458575126846199823
n0 = 145575036089862184772968012014750816659166028840828357885024516131565102712346345625910708214596157522939248398359985832422106056149116726640753670919394145037581595172384392223713667048639158944450925280598688178812170253438103664700756173806183649477673497327790421063029596049211220930285435947389700047717
e0 = 6104905725583061487097813130111812725712623687061285535333592835899028572315489283518324105546236465450024687400996793197533588656449965379858202658832799573292015786259804984314040621630959455897094519928941186899832366216111359619637121411868069759469878142871432060850651758192209783752650530390826992241
c1 = 59089700172263364510471541430195724136973801897202789650586019199451669728729101831161257990233999290546484165767660146638244043033774379664984894178111808280076960669616271416462197675878517863817855762681885790347812435849975072020273928469523961698304409181769820692602979823921421820511589311465948726144
n1 = 171055961405321566289532118753767563629109197214150143506779656820887080836894368955104877312070939117885512468517951216152955714212079279910802095156350517032659766690101321767892798466184405283403136505441356956934759143173462058806620784497304916652269667097971495139608875846338091109621496242787157524093
e1 = 30639328953696065722075015079387560065304228779854040351182305267894609577068955234152835797506237100956072519388029280776532681675227753068574540049244778077615881093270476533536257809592871380358708151151683035275615961208943826349952952069226829397420921321531951316523368786223865432179572145636266109841
c2 = 24257648301491609274972482189063774024772127961295257418254600487615473027418329077996964279110710299066082437371516700591657843057597234861450272363240630164504734590903528165056021531272324846249133757036680429476939369309982196345252669711604534774523215422683385359295249160897422071732828044179085194829
n2 = 99735998821682404719682435155046621256882035421263371444758755082217342389922499214602126376005623406797486880520535486455942687180959663032781490782870080236095770591995437146834606144553095293546973559144743704707021952152013362323293717685161426469215016058837362232410103330238322051089471439573994907641
e2 = 81580834845272005549352820344384188734735397414102222005750919291263464191246301214086773744759605577533897859454210564034313392997143493147211816886655474145064723790935089304983994174659126346174766206623180477360887938029897557683160392738708450965784921553806400996559956745732829531154835363767773681061
c3 = 105310270039347542993580213074911114373638987155564864341577443142664062749969114572669295115218200093381519732560445712425129105002834596010587656544575627162469582470245756143405705971157024449801127133755773536097173259762599166367688198314997549663330392481942723997656023552049910279885657664434799986156
n3 = 118810172988175650374012494943583618875926370822995080847518376655089884052560062524542984436965153851285471302754389325839857100631601002627184437173686224779115595776898914116490948408328080895524604124937295381872443370706017215743101755848741173976351916104362193751372512936063892260855907424754174906407
e3 = 57970672598245590037421993575987847127437841761387257183798066822318596392918179916711068560675528926294272336883938499809087281773070750919594701600347605662910664129043903749270935721912605279738208730075557097647316659218872977257614306133047318781156168440924237849014715453590776000659069078250493480521
c4 = 50430341205487530895874157969557709374947862873979946417751686643857339147558892228311050765271667685452170747716439387141655285820549605442067496018168606163031122498272292974227360674531814593351170403519198099247839499352696883293133549658442172721339510734646474794377043195182186423251146266787514560008
n4 = 80837118813383038376595037732171926303253457956240963765871280771175535050976501573174357090322706934194338649978803681581485022992041019276854467388155755920855237665754031077890133388056350355753218650482718197635332681450734918373003830855184694566883308495322647552169761087814135330222306083205629967447
e4 = 51172856769626923894369204019063376718507295306271724506808987836327051371415876890252665691760404489737902233106400428873399230724307065583727090788789453353097657968301923726049631007431604461521879288667433292135840271678776989737261214286587609316530839676362375173635542358540766454865624476392874630929
c5 = 24533435736573623334539431528997922833496063510219641412038735658846891237553927656156039267456590702682308774830590768888594750053426705504840854071081487058180327084899496154314864910274839867793265086899109787190447838634454294468362549369144295591261617705578124672391399319219038350878856530074063011081
n5 = 108185319218897738268746205017540795873825112956591206743419271090891318238813558017643338501521098978024727760981025765573563469927135773358034691827660887010169178863498411277779419515872567620180674209868666624722965176088860357351459585091952847193607478681852858872736580818017021511957182389670032728751
e5 = 71905546659735491498365580186225996341462093571074706903142472266442052559638067842283521897292088493599089076218507596455101425837547743511983105386966540811629138324774640350969049873787070380161376295760563611617178869788237730560614549740931199083194226891873779907795120035746039593933256380499568775673

M=int(iroot(int(n5),int(2))[0])
n_l = [n0,n1,n2,n3,n4,n5]
L = []
L.append([M,e0,e1,e2,e3,e4,e5])
for i in range(1,7):
    t = [0]*7
    t[i] = n_l[i-1]
    L.append(t)

L = matrix(ZZ,L)
L = L.LLL()
d = int(abs(L[0][0])//M)
print(d)
m = int(pow(c0,d,n0))
print(long_to_bytes(m))