题目
import os
from Crypto.Util.number import *
from secret import flag
bits = 512
def pad(msg, length):
pad_length = length - len(msg) - 1
pad_data = os.urandom(pad_length)
return msg + b'\x00' + pad_data
def unpad(msg):
return msg.split(b"\x00")[0]
def challenge1(m):
p, q = [getPrime(bits) for i in range(2)]
if p <= q:
p, q = q, p
e = 0x10001
n = p * q
c = pow(m, e, n)
leak = (n + p) % (q-1)
print('-------- challenge 1 --------')
print(f'{e = }')
print(f'{c = }')
print(f'{n = }')
print(f'{leak = }')
def challenge2(m):
p, q = [getPrime(bits) for i in range(2)]
e = 0x10001
n = p * q
d = inverse(e, (p-1)*(q-1))
c = pow(m, e, n)
leak = d + p + q
print('-------- challenge 2 --------')
print(f'{e = }')
print(f'{c = }')
print(f'{n = }')
print(f'{leak = }')
def challenge3(m):
p, q = [getPrime(bits) for i in range(2)]
e = 0x10001
n = p * q
c = pow(m, e, n)
leak = (pow(p, q, n) + pow(q, p, n)) % n
print('-------- challenge 3 --------')
print(f'{e = }')
print(f'{c = }')
print(f'{n = }')
print(f'{leak = }')
assert len(flag) == 42
ms = []
for i in range(0, 42, 14):
ms.append(bytes_to_long(pad(flag[i:i+14], bits//4-1)))
m1, m2, m3 = ms
challenge1(m1)
challenge2(m2)
challenge3(m3)
"""
-------- challenge 1 --------
e = 65537
c = 112742443814287255411540092433156061065388404049949520959549377871297566383025041892192679147481155020865118811016470498351633875090973546567374001852295013083192495299811476604405637385307524194793969533646755764136014187430115618114840780368311166911900457224593131166970676797547489278410997707815915932756
n = 121127425328043404860413278637978444801342472819958112597540188142689720655042880213001676368390521140660355813910726809125567752172921410143437643574528335234973793653775043030021036875866776532570781661875022102733555943967261003246543180935987772711036868216508554536086688819118597075508026787867088355603
leak = 216638862637129382765636503118049146067015523924032194492700294200289728064297722088882791754351329407138196573832392846467607399504585045028165699421278
-------- challenge 2 --------
e = 65537
c = 7964477910021153997178145480752641882728907630831216554750778499596527781702830885213467912351097301767341858663701574005489585561370961723264247818377063081744522471774208105250855114831033452448184392499682147532404562876275189577321587660597603848038824026981539659156304028998137796242331160312370913038
n = 140571013522095816880929287025269553867630639381779595547026503691829940612178900269986625350464874598461222087427155791855120339533208468121389480964471710028253589422629569889402475311387750348466199387760629889238062977271925350490110043385800605640905324122017637306715108727700910035925728362455954862209
leak = 58442382248753295429370894053397615609981110383986887405127350139482893508400422595729520437678203735054593866306478994471465948872565590901376309380029015549809468112086393107585011072503638322671608471684607214064187044372418770555236721845694224676090744181562673509234801011420696349507624867568099759003
-------- challenge 3 --------
e = 65537
c = 54161995127842474543974770981473422085334044100057089719350274921419091368361244533281599379235907845996678762379778310924192757650322930707785543132446159092950451255660204858292974657119337026589911330412367633761103944916751660957776230135927005700707688661350641600954072696774954805514477330339449799540
n = 88207747624007183083381863279444163105330473097729276113333026679597864128605555600000789783468271680476780366740448641311570797876037993255307716167149079618302706650018518487351604778857406170722209469765782625409279109832638886179654096975665134276856272488090272822541461702907181545730309689190333058151
leak = 19596671928335648228117128090384865424885102632642665068992144783391306491716530155291726644158221224616817878768426330717188403310818678195631582453246848
"""
过程分析
本题考点主要是关于RSA的基础数论分析,通过各种等式变换得到关于p
和q
的等式,从而计算出p
和q
。
challenge 1
l
e
a
k
≡
(
n
+
p
)
m
o
d
(
q
−
1
)
leak \equiv (n+p) \space mod \space (q-1)
leak≡(n+p) mod (q−1)
∵
n
=
p
∗
q
\because n=p*q
∵n=p∗q
∴
l
e
a
k
≡
p
(
q
+
1
)
m
o
d
(
q
−
1
)
\therefore leak \equiv p(q+1) \space mod \space (q-1)
∴leak≡p(q+1) mod (q−1)
⇒
l
e
a
k
≡
2
∗
p
m
o
d
(
q
−
1
)
\Rightarrow leak \equiv 2*p \space mod \space (q-1)
⇒leak≡2∗p mod (q−1)
又
∵
p
>
q
,
∴
p
m
o
d
(
q
−
1
)
=
p
−
q
+
1
又\because p>q,\therefore p \space mod \space (q-1) = p-q+1
又∵p>q,∴p mod (q−1)=p−q+1
综上,
l
e
a
k
=
2
(
p
−
q
+
1
)
综上,leak = 2(p-q+1)
综上,leak=2(p−q+1)
此时联立
n
=
p
∗
q
,
可得如下方程组
此时联立n=p*q,可得如下方程组
此时联立n=p∗q,可得如下方程组
{
l
e
a
k
=
2
(
p
−
q
+
1
)
n
=
p
∗
q
\left\{\begin{matrix} leak = 2(p-q+1)\\ n = p*q \end{matrix}\right.
{leak=2(p−q+1)n=p∗q
解方程即可得到p
,q
。
challenge 2
e
d
≡
1
m
o
d
p
h
i
,
l
e
a
k
=
d
+
p
+
q
ed \equiv 1 \space mod \space phi,leak = d+p+q
ed≡1 mod phi,leak=d+p+q
∵
p
h
i
=
(
p
−
1
)
∗
(
q
−
1
)
=
n
−
(
p
+
q
)
+
1
\because phi = (p-1)*(q-1) =n-(p+q)+1
∵phi=(p−1)∗(q−1)=n−(p+q)+1
∴
p
+
q
=
n
−
p
h
i
+
1
\therefore p+q = n-phi+1
∴p+q=n−phi+1
⇒
e
∗
(
l
e
a
k
−
p
−
q
)
=
1
+
k
∗
p
h
i
\Rightarrow e*(leak-p-q) = 1+k*phi
⇒e∗(leak−p−q)=1+k∗phi
⇒
e
∗
(
l
e
a
k
−
n
+
p
h
i
−
1
)
=
1
+
k
∗
p
h
i
\Rightarrow e*(leak-n+phi-1) = 1+k*phi
⇒e∗(leak−n+phi−1)=1+k∗phi
⇒
(
e
−
k
)
∗
p
h
i
=
e
(
n
−
l
e
a
k
+
1
)
+
1
\Rightarrow (e-k)*phi = e(n-leak+1)+1
⇒(e−k)∗phi=e(n−leak+1)+1
∵
等式右边
>
0
且
p
h
i
>
0
,存在一个
k
使得上述等式成立,
∴
k
∈
[
1
,
e
)
\because 等式右边>0且phi>0,存在一个k使得上述等式成立,\therefore k \in [1,e)
∵等式右边>0且phi>0,存在一个k使得上述等式成立,∴k∈[1,e)
challenge 3
l
e
a
k
≡
p
q
+
q
p
m
o
d
n
leak \equiv p^q +q^p \space mod \space n
leak≡pq+qp mod n
l
e
a
k
≡
p
q
m
o
d
q
+
q
p
m
o
d
p
leak \equiv p^q \space mod\space q+q^p \space mod \space p
leak≡pq mod q+qp mod p
根据费马小定理
根据费马小定理
根据费马小定理
a
p
−
1
≡
1
m
o
d
p
a^{p-1} \equiv 1 \space mod \space p
ap−1≡1 mod p
⇒
l
e
a
k
=
p
+
q
\Rightarrow leak = p+q
⇒leak=p+q
此时联立
n
=
p
∗
q
,
可得如下方程组
此时联立n=p*q,可得如下方程组
此时联立n=p∗q,可得如下方程组
{
l
e
a
k
=
p
+
q
n
=
p
∗
q
\left\{\begin{matrix} leak = p+q\\ n = p*q \end{matrix}\right.
{leak=p+qn=p∗q
解方程即可得到p
,q
.
解题脚本
import gmpy2
from Crypto.Util.number import *
from sympy import *
def decode1():
#leak = (n + p) % (q-1)
#leak = (p*q+p) % (q-1)
#leak = p(q+1) % (q-1),(q+1) %(q-1) = 2
#leak = 2*p % (q-1),因为p>q 所以 p %(q-1) = (p-q+1)
#leak = 2*(p-q+1),构建方程组求p,q
e = 65537
c = 112742443814287255411540092433156061065388404049949520959549377871297566383025041892192679147481155020865118811016470498351633875090973546567374001852295013083192495299811476604405637385307524194793969533646755764136014187430115618114840780368311166911900457224593131166970676797547489278410997707815915932756
n = 121127425328043404860413278637978444801342472819958112597540188142689720655042880213001676368390521140660355813910726809125567752172921410143437643574528335234973793653775043030021036875866776532570781661875022102733555943967261003246543180935987772711036868216508554536086688819118597075508026787867088355603
leak = 216638862637129382765636503118049146067015523924032194492700294200289728064297722088882791754351329407138196573832392846467607399504585045028165699421278
p,q = symbols("p q")
eq = [p*q-n,2*(p-q+1)-leak]
result = list(nonlinsolve(eq, [p, q]))
p,q =int(result[1][0]),int(result[1][1])
phi =(p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag1 = long_to_bytes(m)
return flag1[:14]
def decode2():
#e*d = 1 +k*phi,leak = d+p+q
#e*(leak-p-q) = 1 + k*phi
#n-(p+q)+1 = phi ---->>> p+q = n-phi+1
#e*(leak-n-1+phi) = 1 +k*phi
#e*(leak-n-1)+e*phi = 1+k*phi
#(e-k)*phi = e*(n-leak+1)+1,爆破k找到符合条件的k即可求出phi,接下来就是RSA解密
e = 65537
c = 7964477910021153997178145480752641882728907630831216554750778499596527781702830885213467912351097301767341858663701574005489585561370961723264247818377063081744522471774208105250855114831033452448184392499682147532404562876275189577321587660597603848038824026981539659156304028998137796242331160312370913038
n = 140571013522095816880929287025269553867630639381779595547026503691829940612178900269986625350464874598461222087427155791855120339533208468121389480964471710028253589422629569889402475311387750348466199387760629889238062977271925350490110043385800605640905324122017637306715108727700910035925728362455954862209
leak = 58442382248753295429370894053397615609981110383986887405127350139482893508400422595729520437678203735054593866306478994471465948872565590901376309380029015549809468112086393107585011072503638322671608471684607214064187044372418770555236721845694224676090744181562673509234801011420696349507624867568099759003
for k in range(1,65537):
if (e*(n-leak+1)+1)%(e-k)==0:
phi = (e*(n-leak+1)+1)//(e-k)
d = gmpy2.invert(e, phi)
try:
m = pow(c,d,n)
flag2 = long_to_bytes(m)
if flag2[4:5]==b'-' and flag2[9:10]==b'-':
return flag2[:14]
except:
pass
def decode3():
#leak = p**q %n + q**p %n
#leak = p**q %q+q**p%p,费马小定理:a**(p-1) = 1 %p
#leak = p+q,构建方程组求p,q
e = 65537
c = 54161995127842474543974770981473422085334044100057089719350274921419091368361244533281599379235907845996678762379778310924192757650322930707785543132446159092950451255660204858292974657119337026589911330412367633761103944916751660957776230135927005700707688661350641600954072696774954805514477330339449799540
n = 88207747624007183083381863279444163105330473097729276113333026679597864128605555600000789783468271680476780366740448641311570797876037993255307716167149079618302706650018518487351604778857406170722209469765782625409279109832638886179654096975665134276856272488090272822541461702907181545730309689190333058151
leak = 19596671928335648228117128090384865424885102632642665068992144783391306491716530155291726644158221224616817878768426330717188403310818678195631582453246848
p,q = symbols("p q")
eq = [p*q-n,p+q-leak]
result = list(nonlinsolve(eq, [p, q]))
p,q =int(result[1][0]),int(result[1][1])
phi =(p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag3 = long_to_bytes(m)
return flag3[:14]
if __name__ == '__main__':
print(decode1()+decode2()+decode3())
flag:
文章来源:https://www.toymoban.com/news/detail-433188.html
flag{9dc4b6dd-b162-479c-b087-01d351073d14}
【可能是因为离着远了,喜欢的人会更喜欢,讨厌的人也就没那么讨厌了。】文章来源地址https://www.toymoban.com/news/detail-433188.html
到了这里,关于2023 数据安全产业人才能力挑战赛 --- math_exam wp的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!