d泄露可谓十分的有意思首先当 d泄露之后，我们自然可以解密所有加密的消息。但更让有趣的是，我们甚至可以通过d来暴力分解n！
让我们先做一些概念学习：
非平凡因子："非平凡因子"指的是一个数的除了 1 和其自身之外的因子。
在RSA加密中，对于公钥n来说，p和q便是n的非平凡因子。
phi_n：我们熟知 phi_n = （p - 1）* (q - 1)，因为p，q都是素数的前提下，
phi_n 一定是偶数
现在我们来推导一下！（markdown）
点击查看代码
d泄露攻击
$$
\\\because ed \equiv 1 \mod(\varphi (n))
\\\therefore ed -1 = k*\varphi (n)
\\\because \varphi(n)定为偶数,则k*\varphi (n)也定为偶数
\\\therefore k*\varphi (n) = 2^s*t,t为奇数
\\ ed-1=2^s*t
\\\
\\ 现在取a\in (1,n),且gcd(a,n)互素
\\ 在RSA中，对a加密后再解密的结果一定是a本身
\\\therefore [a^emod(n)]^d\mod(n)=a^{ed} = a
\\ \therefore a^{ed}\equiv a \mod (n),即a^{ed-1}\equiv 1 \mod(n)
\\\
\\ 存在i\in[1,s]
\\满足a^{2^{i-1}*t} \ne 1 mod(n)
\\a^{2^{i}*t} \equiv 1 \mod(n)
\\\therefore gcd(a^{2^{i}*t} -1,n) 就是n的一个非平凡因子
\\ 如果其值存在，则即为p或q
$$
点击查看代码
import random
import gmpy2
def divide_pq(e, d, n):
k = e*d - 1
while True:
g = random.randint(2, n-1)
t = k
while True:
if t % 2 != 0:
break
t //= 2
x = pow(g, t, n)
if x > 1 and gmpy2.gcd(x-1, n) > 1:
p = gmpy2.gcd(x-1, n)
return (p, n//p)
p, q = divide_pq(e, d, n)
print(f'p = {p}')
print(f'q = {q}')
点击查看代码
import random
import gmpy2
def divide_pq(e, d, n):
k = e * d - 1
while True:
g = random.randint(2, n - 1)
t = k
while True:
if t % 2 != 0:
break
t //= 2
x = pow(g, t, n)
if x > 1 and gmpy2.gcd(x - 1, n) > 1:
p = gmpy2.gcd(x - 1, n)
return (p, n // p)
# p = 6751788336718135611881440926631484238733538077377103183012544626346234262328435250389232211938937998065704308647916026301101523875116044195586310810923821
# q = 12402588751139524578452451938456304104001492173035282851387360863863313418150723173638115660331023967180020603500960295594170887264192001521378179502103171
e =65537
n = 83739654075055389419094040679499978317807032425743347244231335401408081087572348218356771927173166192623289416362919050555004087700693931417253044924154169325873978503942212803082126635050615297045103833859387741876837484185939701141609259298247415272215167890828753143376301351408280063326963058390963536391
d = 58798047844299004453948921524460236236790304883278630546680399791973933311058131253553314521151831617039930254249850404342426768142008829241920340697236698787582166056883284678344786130283168233001777772799171471649533660940060952103395560044866458057917980199108661955186270420330674674394267383356367158873
p, q = divide_pq(e, d, n)
print(f'p = {p}')
print(f'q = {q}')