RSA中leak=p^q%n + q^p%n问题
以ISCTF2024crypto蓝鲨的费马这道题为例子讲解自己学到的一个解决方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import libnum
import gmpy2
from Crypto.Util.number import *
flag=b'ISCTF{********}'
m=bytes_to_long(flag)
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
n=p*q
e=0x10001
c=pow(m,e,n)
d=inverse(e,(p-1)*(q-1))
leak = (d+(pow(p,q,n)+pow(q,p,n)))%n
print("c=", c)
print("n=", n)
print("leak=", leak)
"""
c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997
n= 13424018200035368603483071894166480724482952594135293395398366121467209427078817227870501294732149372214083432516059795712917132804111155585926502759533393295089100965059106772393520277313184519450478832376508528256865861027444446718552169503579478134286009893965458507369983396982525906466073384013443851551139147777507283791250268462136554061959016630318688169168797939873600493494258467352326974238472394214986505312411729432927489878418792288365594455065912126527908319239444514857325441614280498882524432151918146061570116187524918358453036228204087993064505391742062288050068745930452767100091519798860487150247
leak= 9192002086528025412361053058922669469031188193149143635074798633855112230489479254740324032262690315813650428270911079121913869290893574897752990491429582640499542165616254566396564016734157323265631446079744216458719690853526969359930225042993006404843355356540487296896949431969541367144841985153231095140361069256753593550199420993461786814074270171257117410848796614931926182811404655619662690700351986753661502438299236428991412206196135090756862851230228396476709412020941670878645924203989895008014836619321109848938770269989596541278600166088022166386213646074764712810133558692545401032391239330088256431881
"""
|
$1.\text{leak} = d + p + q$ 其中 leak 简写为 L
$2. m = \text{pow}(c, d, n)，即 m = c^d \mod n.$
$3.d = L - (p + q) .$
根据欧拉函数的定义：$\phi = (p - 1)(q - 1) = pq - p - q + 1$
由于 n = pq ，因此：$\phi = n + 1 - (p + q)$
根据欧拉定理:$c^\phi \equiv1 \mod n$
代入 $\phi$的表达式：$c^{n + 1 - (p + q)} \equiv 1 \mod n$
可以进一步推导：$c^{n + 1} \equiv c^{p + q} \mod n$
因此:$c^{n + 1} \equiv c^{p + q} \mod n$
已知 d = L - (p + q) ，代入 $c^d \mod n = m$ ：
$c^{L - (p + q)} \mod n = m$
根据前面的推导：$c^{n + 1} \equiv c^{p + q} \mod n$
因此：$c^{L - (n + 1)} \mod n = m$
$m = \text{pow}(c, L - n - 1, n)$
1
2
3
4
5
6
7
8
9
| c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997
n= 13424018200035368603483071894166480724482952594135293395398366121467209427078817227870501294732149372214083432516059795712917132804111155585926502759533393295089100965059106772393520277313184519450478832376508528256865861027444446718552169503579478134286009893965458507369983396982525906466073384013443851551139147777507283791250268462136554061959016630318688169168797939873600493494258467352326974238472394214986505312411729432927489878418792288365594455065912126527908319239444514857325441614280498882524432151918146061570116187524918358453036228204087993064505391742062288050068745930452767100091519798860487150247
leak= 9192002086528025412361053058922669469031188193149143635074798633855112230489479254740324032262690315813650428270911079121913869290893574897752990491429582640499542165616254566396564016734157323265631446079744216458719690853526969359930225042993006404843355356540487296896949431969541367144841985153231095140361069256753593550199420993461786814074270171257117410848796614931926182811404655619662690700351986753661502438299236428991412206196135090756862851230228396476709412020941670878645924203989895008014836619321109848938770269989596541278600166088022166386213646074764712810133558692545401032391239330088256431881
from Crypto.Util.number import long_to_bytes, inverse
m=pow(c,leak-n-1,n)
print(m)
flag=long_to_bytes(m)
print(flag)
|