Python 中 RSA 的模逆解释
Explanation of Modular Inverse for RSA in Python
我在 python 中找到了一个 python 脚本来执行 RSA 的模逆。但是,我无法理解 python 中的模逆是如何工作的。
能否请您特别解释和详细说明 modinv 和 egcd
请评论代码以获得更多理解。
这是 link 中的 python 代码示例,
https://gist.github.com/ofaurax/6103869014c246f962ab30a513fb5b49
#!/usr/bin/env python3
p = 61
q = 53
n = p*q
phi = (p-1)*(q-1)
# Took from SO
def egcd(a, b):
if a == 0:
return (b, 0, 1)
g, y, x = egcd(b%a,a)
return (g, x - (b//a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('No modular inverse')
return x%m
e = 17
d = modinv(e, phi)
print('P =', p)
print('Q =', q)
print('N =', n)
print('Phi =', phi)
print('E =', e)
print('D =', d)
print('(E*D)%Phi =', (e*d)%phi)
谢谢
您正在使用 Extended Euclidean algorithm 查找 d
,时间:
d⋅e ≡ 1 (mod λ(n));
你的情况 e = 17
和 λ(n) = phi
.
我在 python 中找到了一个 python 脚本来执行 RSA 的模逆。但是,我无法理解 python 中的模逆是如何工作的。 能否请您特别解释和详细说明 modinv 和 egcd 请评论代码以获得更多理解。
这是 link 中的 python 代码示例, https://gist.github.com/ofaurax/6103869014c246f962ab30a513fb5b49
#!/usr/bin/env python3
p = 61
q = 53
n = p*q
phi = (p-1)*(q-1)
# Took from SO
def egcd(a, b):
if a == 0:
return (b, 0, 1)
g, y, x = egcd(b%a,a)
return (g, x - (b//a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('No modular inverse')
return x%m
e = 17
d = modinv(e, phi)
print('P =', p)
print('Q =', q)
print('N =', n)
print('Phi =', phi)
print('E =', e)
print('D =', d)
print('(E*D)%Phi =', (e*d)%phi)
谢谢
您正在使用 Extended Euclidean algorithm 查找 d
,时间:
d⋅e ≡ 1 (mod λ(n));
你的情况 e = 17
和 λ(n) = phi
.