对于RSA,我如何计算秘密指数？

Question

对于RSA,我如何计算秘密指数？

给定p和q两个素数,并且phi =(p-1)(q-1)和公共指数(0x10001),我如何获得秘密指数'd'？

我已经读过我必须做的事情:d = e ^-1 mod phi使用模块化反演和欧几里德方程但我无法理解上面的公式如何映射到模块化反转维基页面上的a ^- 1≡xmod m公式,或它如何映射到欧几里德GCD方程.

有人可以帮助,欢呼

Answer 1

您可以使用扩展的欧几里德算法来求解d同余

de = 1 mod phi(m)

对于RSA加密,e是加密密钥,d是解密密钥,加密和解密都是由指数模块执行的m.如果a 使用密钥加密消息e,然后使用密钥对其进行解密,则d计算(a ^e)^d = a ^de mod m.但是,因为de = 1 mod phi(m),欧拉的赋形定理告诉我们一个^de与¹ mod m一致 - 换句话说,你得到了原始的a.

在不知道因子分解的情况下,没有已知的有效方法来获得d仅知道加密密钥e和模数的解密密钥,因此认为RSA加密是安全的.mm = pq