PQ的逆元（经典题型）

1.题目

import gmpy2
from Crypto.Util.number import *
from flag import flag
assert flag[:5] == b'flag{'

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
e = 65537
n = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
p1 = gmpy2.invert(p, q)
q1 = gmpy2.invert(q, p)
c = pow(m, e, n)
print("e =", e)
print("phi =", phi)
print("c =", c)
print("p1 =", p1)
print("q1 =", q1)

# e = 65537
# phi = 103353321956115038268423787343445070695359887368027370681447341228954864923636288271897754707468715365241011076414233333950293702268964610841807786075315263703184515226519703647902896165428316408079585140357062630398533351243945259031003806832553031784193884890635972425654006981418100329336467730722015449728
# c = 4238859180193743703874646266230712254362933077505981135654972544307362590857240819674650694367933000662827730234640492947226884583246718212575474579589474903911055232580317102461167022897821779489616445964656800903788165643509487511833774681684801836250043990682800975568345915312079015663025291547154175193
# p1 = 5347052276294853375406538979756123498239831969668341868320572937717598227684446389494724980496894340486024338899363022032191210900806952386789716568970415
# q1 = 4604244678419597578777300939314955289400274698198899071164909838162424604575576676047516169416535477557901148261466975870483833592339588914985473051501447

2.思路

\[ \begin{gather} p_1p \equiv 1\ (mod\ q)\\ \downarrow\\ p_1p = 1+k_1q\\ \downarrow\\ p_1p-1 = k_1q,\ \ \ \ \ \ \enclose{circle} 1\\ \ \\ q_1q \equiv 1\ (mod\ p)\\ \downarrow\\ q_1q = 1+k_2p\\ \downarrow\\ q_1q-1 = k_2p\ \ \ \ \ \ \enclose{circle} 2\\\\ \end{gather} \]

1、2式相乘得

\[ \begin{gather} (p_1p-1)(q_1q-1)=k_1k_2pq\\ \downarrow ^{(n=p*q)} \\ p_1q_1pq-p_1p-q_1q+1=kn\\ \downarrow \\ p_1q_1n-p_1p-q_1q+1=kn\\ \downarrow \\ -p_1p-q_1q+1=kn-p_1q_1n\\ \downarrow \\ p_1p+q_1q-1=p_1q_1n-kn\\ \downarrow \\ p_1p+q_1q-1=(p_1q_1-k)n\\ \downarrow ^{(p_1q_1-k)合并为k} \\ p_1p+q_1q-1=kn \end{gather} \]

因为左式\(p_1p+q_1q-1\)的位数为512+512=1024，而右式中n的位数也是1024（因为n=p*q），所以k只能为1才能保证左右两式位数相同

所以\(p_1p+q_1q-1=n\)

联立两式

\[ \begin{gather} p_1p+q_1q-1=n \ \ \ \ \ \ \ \enclose{circle}{1}\\\\ \phi(n)=(p-1)(q-1)\enclose{circle} 2\\ \end{gather} \]

即可得出p和q，然后按常规方法解出m，即可得到flag

3.解题脚本

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

e = 65537
phi = 103353321956115038268423787343445070695359887368027370681447341228954864923636288271897754707468715365241011076414233333950293702268964610841807786075315263703184515226519703647902896165428316408079585140357062630398533351243945259031003806832553031784193884890635972425654006981418100329336467730722015449728
c = 4238859180193743703874646266230712254362933077505981135654972544307362590857240819674650694367933000662827730234640492947226884583246718212575474579589474903911055232580317102461167022897821779489616445964656800903788165643509487511833774681684801836250043990682800975568345915312079015663025291547154175193
p1 = 5347052276294853375406538979756123498239831969668341868320572937717598227684446389494724980496894340486024338899363022032191210900806952386789716568970415
q1 = 4604244678419597578777300939314955289400274698198899071164909838162424604575576676047516169416535477557901148261466975870483833592339588914985473051501447

p = sympy.symbols("p")
q = sympy.symbols("q")
f1 = p1*p + q1*q - 1 - p*q
f2 = (p - 1) * (q-1) - phi
p_q = sympy.solve([f1,f2],[p,q])
p = p_q[1][0]
q = p_q[1][1]
n = p*q
d = gmpy2.invert(e, phi)
m = pow(c, int(d), int(n))
print(long_to_bytes(m))
# b'flag{Y0u_g0t_th3_fl4g_0f_C3ypt0}'