赣育杯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 = ...
c = ...
'''
通过p、q的生成方式，对a开方后在附近寻找正确的p、q。
for i in range(1, p):
N = (N * i) % a
m = N * flag % a
$N \equiv (p-1)! \pmod a$
$m\equiv (p-1)!\cdot flag \pmod a \equiv -flag \pmod p$
得到关系式：$flag \equiv -m \pmod p$
但只靠这一个式子还不够
$m\cdot p\cdot …\cdot (q-1)\equiv (q-1)!\cdot flag \pmod a \equiv -flag \pmod q$
得到第二个关系式：$flag \equiv -m\cdot p\cdot …\cdot (q-1)\pmod q$
最后联立两个关系用剩余定理解出flag。
a = 156853895847604116708242664263151514811095704969640303272039451331791888050995073274981545693518063639560286348739938318495685137088495867703518198511200409009953879436648706837731243061114851474801565873584183542649886358523850682697732574913523360866915083642887238043256280849100274825940626065115676325169
c = 3459715117165130065996389169943285249501133832272446001239391765859259811270526185228996906338576254353123756173289118671028939933226544773197852424767051933844004667155191851195814295922794480300237399956789038592856532530692732011427288405114650955620859282144504446058845961744702163836107847961388150810
p = 12524132538727147976454683542869473176723933298740764667643646868771435739017779964538584767004546975861773724104399289331497224456192089483187179727966053
q = 12524132538727147976454683542869473176723933298740764667643646868771435739017779964538584767004546975861773724104399289331497224456192089483187179727966173
e = 65537
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,a)
ns = []
cs = []
ns.append(p)
ns.append(q)
c1 = (-m)%p
c2 = (-m)%q
for i in range(p,q):
c2 *= i%q
cs.append(c1)
cs.append(c2)
m = solve_crt(cs,ns)
print(long_to_bytes(m))
赣育杯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：公用私钥d对flag进行5次加密，可参考：
RSA | Lazzaro (lazzzaro.github.io)
但最后一组的n没给，通过part2求：
$s\equiv(900\cdot p-218\cdot q)^{n-p-q} \pmod n$
一开始我通过二项式定理展开，以及费马小定理，最后得到关系式：
$s = 2+k\cdot phi$
然后我就不知道咋求了，路走错了或许。
操作最初的s关系式：
$s\cdot (900\cdot p-218\cdot q)\equiv(900\cdot p-218\cdot q)^{phi} \pmod n$
运用欧拉定理：
$s\cdot (900\cdot p-218\cdot q)\equiv1 \pmod n$
$(900\cdot p-218\cdot q)\equiv s^{-1} \pmod n$
再结合$n = p*q$
直接解出p、q来：
e = 0x10001
n = ...
c = ...
s = ...
p,q = var("p,q")
f1 = 900*p-218*q == inverse_mod(s,n) % n
f2 = n == p*q
solve([f1,f2],p,q)
最后套模板解flag：
造格：
$\begin {bmatrix}
M & e_1 & e_2 & e_3 & e_4 & e_5 & e_6\
& -N_1& & & & & \
& &-N_2 & & & & \
& & & -N_3 & & & \
& & & & -N_4 & & \
& & & & & -N_5 & \
& & & & & & -N_6 \
\end{bmatrix}$
其中$M = [N_r^{\frac{1}{2}}]$
LLL算法后取第一个分量的第一个值的绝对值再除上M即为d，最后解基础RSA：
e = 0x10001
n = 20955464633057600258987829727550073699845816289000240676927869818926752810905511184835302717855745473943671910742784074561535017974853574714483642916831791020944940633062963043482236587316552330558006573820423830770910893877191630012247591380869307656539553888318621170921800017818132160253923739647771452839191101104391894609403591447166963426444018303147924843072923713248135717578047687411974516038299879758561542241544862102935741869647633013298181782208467117482306148238724598730801037692668154263059348953587766571379262442743822007387408949824805991797355089583176028081305319076896384126383926193964322235633
c = 14815997295683082265558346455845370590765145583224067337292601455640475216349267044144296003388877395546880235511728120803143112914764263292087421926972160283428440959367872665892349776616002018624301524264223581314248857537034849571849747613963209414193510408342387107662655487869098045345428379025731617851483935711671021438908270746316921057871871545763798735895118697635903815383424855759281301248295597297869474539060531099443223045844791615425429748703429968627505406271675074549912664863784774239200764403372298995457799473112713379340870305136776932539188516395526955161359417473843082895317392495109895085666
s = 14728527428626630951705148488338433865446345521255631461200851513782412494843597938863837697938230856843797646287742397249258609197032095158567448934855031190354034543862057663422053672290704598313096289223478302733688501373756860855445632789922930577582465209872782549135254792729915747104521949095814028476908208917363509089190935273004331739978623136706041729628143765893264698948654175039064609891374587695812144855411176143224066975193255513405865992328257766815240718115442741846443490733767716842367336385132648983241895710001620533668392060358573295789752856876282590472528110546264872047138094995909454134250
c1 = 13007070082982086015048648249698272815655157209727275797297990841215796701955079738986996208838342773211678208282162295881823413924960399315068498509939876883297864092435101096694113071462267388158595518905101264654742860199638059278239359756219217345342001728599121265614144789005805619626458575126846199823
n1 = 145575036089862184772968012014750816659166028840828357885024516131565102712346345625910708214596157522939248398359985832422106056149116726640753670919394145037581595172384392223713667048639158944450925280598688178812170253438103664700756173806183649477673497327790421063029596049211220930285435947389700047717
e1 = 6104905725583061487097813130111812725712623687061285535333592835899028572315489283518324105546236465450024687400996793197533588656449965379858202658832799573292015786259804984314040621630959455897094519928941186899832366216111359619637121411868069759469878142871432060850651758192209783752650530390826992241
c2 = 59089700172263364510471541430195724136973801897202789650586019199451669728729101831161257990233999290546484165767660146638244043033774379664984894178111808280076960669616271416462197675878517863817855762681885790347812435849975072020273928469523961698304409181769820692602979823921421820511589311465948726144
n2 = 171055961405321566289532118753767563629109197214150143506779656820887080836894368955104877312070939117885512468517951216152955714212079279910802095156350517032659766690101321767892798466184405283403136505441356956934759143173462058806620784497304916652269667097971495139608875846338091109621496242787157524093
e2 = 30639328953696065722075015079387560065304228779854040351182305267894609577068955234152835797506237100956072519388029280776532681675227753068574540049244778077615881093270476533536257809592871380358708151151683035275615961208943826349952952069226829397420921321531951316523368786223865432179572145636266109841
c3 = 24257648301491609274972482189063774024772127961295257418254600487615473027418329077996964279110710299066082437371516700591657843057597234861450272363240630164504734590903528165056021531272324846249133757036680429476939369309982196345252669711604534774523215422683385359295249160897422071732828044179085194829
n3 = 99735998821682404719682435155046621256882035421263371444758755082217342389922499214602126376005623406797486880520535486455942687180959663032781490782870080236095770591995437146834606144553095293546973559144743704707021952152013362323293717685161426469215016058837362232410103330238322051089471439573994907641
e3 = 81580834845272005549352820344384188734735397414102222005750919291263464191246301214086773744759605577533897859454210564034313392997143493147211816886655474145064723790935089304983994174659126346174766206623180477360887938029897557683160392738708450965784921553806400996559956745732829531154835363767773681061
c4 = 105310270039347542993580213074911114373638987155564864341577443142664062749969114572669295115218200093381519732560445712425129105002834596010587656544575627162469582470245756143405705971157024449801127133755773536097173259762599166367688198314997549663330392481942723997656023552049910279885657664434799986156
n4 = 118810172988175650374012494943583618875926370822995080847518376655089884052560062524542984436965153851285471302754389325839857100631601002627184437173686224779115595776898914116490948408328080895524604124937295381872443370706017215743101755848741173976351916104362193751372512936063892260855907424754174906407
e4 = 57970672598245590037421993575987847127437841761387257183798066822318596392918179916711068560675528926294272336883938499809087281773070750919594701600347605662910664129043903749270935721912605279738208730075557097647316659218872977257614306133047318781156168440924237849014715453590776000659069078250493480521
c5 = 50430341205487530895874157969557709374947862873979946417751686643857339147558892228311050765271667685452170747716439387141655285820549605442067496018168606163031122498272292974227360674531814593351170403519198099247839499352696883293133549658442172721339510734646474794377043195182186423251146266787514560008
n5 = 80837118813383038376595037732171926303253457956240963765871280771175535050976501573174357090322706934194338649978803681581485022992041019276854467388155755920855237665754031077890133388056350355753218650482718197635332681450734918373003830855184694566883308495322647552169761087814135330222306083205629967447
e5 = 51172856769626923894369204019063376718507295306271724506808987836327051371415876890252665691760404489737902233106400428873399230724307065583727090788789453353097657968301923726049631007431604461521879288667433292135840271678776989737261214286587609316530839676362375173635542358540766454865624476392874630929
c6 = 24533435736573623334539431528997922833496063510219641412038735658846891237553927656156039267456590702682308774830590768888594750053426705504840854071081487058180327084899496154314864910274839867793265086899109787190447838634454294468362549369144295591261617705578124672391399319219038350878856530074063011081
e6 = 71905546659735491498365580186225996341462093571074706903142472266442052559638067842283521897292088493599089076218507596455101425837547743511983105386966540811629138324774640350969049873787070380161376295760563611617178869788237730560614549740931199083194226891873779907795120035746039593933256380499568775673
p = 124747842154083293805692231855277895256934921313624636904327396275525774017050072578330947404448228794936942946293022730424800458009567941390255323958743055674887005480647490069819495857967048838107151822827979414023675813974014386486815765147595308605699043740228800181478865172840942392151996811830399497227
q = 167982582072836904955999896951525861118128682070402782861700729000627241162012457260382832134313272047198493783298403785132164092335743559203214923157817561355400845878661594804030032491845236418729855287163862232990488136112674875893415405693185631595909156907974548422517618349786316373371309935491225816179
phi = (p-1)*(q-1)
d = inverse_mod(e,phi)
last_n = pow(c,d,n)
n6 = last_n
M = int(sqrt(n1)
ns = [n1,n2,n3,n4,n5,n6]
es = [e1,e2,e3,e4,e5,e6]
A = Matrix(7,7)
A[0,0] =
for i in range(1,7):
A[i,i] = ns[i-1]
A[0,i] = es[i-1]
L = A.LLL()
b1 = abs(L[0][0])
d = b1 // M
m = pow(c1,d,n1)
print(long_to_bytes(m))
共私钥指数攻击可参考RSA | Lazzaro (lazzzaro.github.io)
2022第五空间5_vgcd
from random import getrandbits, seed
from Crypto.Util.number import getPrime, inverse, bytes_to_long, isPrime
from os import urandom
from secret import flag
def sample(rho, eta, gamma, p):
seed(urandom(8))
return p * getrandbits(gamma - eta) + getrandbits(rho)
def gen_vector(rho, eta, gamma, m, p, K):
v = vector([sample(rho, eta, gamma, p) for i in range(m)])
return K*v
rho = 6
m = 3
eta = 288
gamma = 512
p = getPrime(gamma)
q = getPrime(gamma)
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
c = pow(bytes_to_long(flag), e, n)
print(n)
print(c)
pp = p >> (gamma - eta)
assert isPrime(pp)
K = Matrix.random(Integers(pp), m, m).lift()
t1 = [gen_vector(rho, eta, gamma, m, pp, K) for i in range(1024)]
print(t1)
for i in range(4):
t2 = [gen_vector(rho, eta, gamma, m, pp, K) for i in range(512)]
print(t2)
想办法得到pp从而恢复p解出flag。
$t = K\cdot v$
$K\cdot v = \begin{bmatrix}
k_{11}&k_{12}&k_{13}\
k_{21}&k_{22}&k_{23}\
k_{31}&k_{32}&k_{33}\
\end{bmatrix}
\cdot
\begin{pmatrix}
pp\cdot r_{224}+r_6,&pp\cdot rr_{224}+rr_6,&pp\cdot rrr_{224}+rrr_6\
\end{pmatrix}$
$=\begin{pmatrix}
a_1\cdot pp+b_1 & a_2\cdot pp+b_2 &a_3\cdot pp+b_3 &
\end{pmatrix} $
其中：
$a_i = k_{1i}\cdot r_{224} + k_{2i}\cdot r_{224}+k_{3i}\cdot r_{224}$
$b_i = k_{1i}\cdot r_{6} + k_{2i}\cdot rr_{6}+k_{3i}\cdot rrr_{6}$
通过多组形如$a\cdot pp + b$的式子，找到两个式子，相减消去b后求gcd可以得到pp。
可能有这样的疑惑，不同的式子b是不同的，怎么能消去，这里用到生日攻击的理论。
在本题中，rho=6，即$r_6、rr_6、rrr_6$都是6位的，相对较小，那么b总共就只有$2^6\cdot 2^6\cdot 2^6\cdot = 2^{18}$种情况，题目一共给了3072个输出数据。带入生日悖论的公式：$P = 1-e^{-\frac{n(n-1)}{2N}} = 1-e^{-\frac{3072(3072-1)}{2\cdot 2^{18}}}$。算出来的概率是近似百分之百的。简单理解就是在这么多的数据中，大概率存在相同的$r_6、rr_6、rrr_6$。
所以我们只需要遍历所有结果，找到b相同的式子求gcd从而得到pp。
得到pp后就是基础的高位攻击，无需多说。
这道题主要是记一下生日攻击的思想。
可参考：
2022第五空间 - gla2xy’s blog (gal2xy.github.io)
【2022 第五空间】5_vgcd WriteUP_2vgcd_Mr_AgNO3的博客-CSDN博客
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com