对于RSA，我如何计算秘密指数？ [英] For RSA, how do i calculate the secret exponent?

问题描述

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

给定p和q两个素数，phi =（p-1）（q-1） ，和公众指数（0x10001），我如何获得秘密指数'd'？

我已经读过我必须做的： d = e ^-1 mod phi ，使用模块化反转和欧几里得方程式，但我不明白上述公式如何映射到 a ^-1 ≡ x mod m 公式在模块化反向维基页面上，或如何映射到欧几里德GCD方程式。

有人可以帮助，欢呼

解决方案

您可以使用扩展欧几里德算法来解决一致的 d

  de = 1 mod phi（m）
  

对于RSA加密， e 是加密密钥， d 是解密密钥，加密
和解密都通过求幂mod $ code>米。如果您使用密钥 e 加密消息 a
，然后使用密钥 d ，您计算（a ^e ） ^de = a ^de mod m 。但
自 de = 1 mod phi（m），告诉我们，一个 ^de 是一致的
到 ¹ mod m - 换句话说，你得到原始 a 。

没有已知的有效方法来获取解密密钥 d 只知道
加密密钥 e 和模数 m ，而不知道因子分解 m = pq ，所以
RSA加密被认为是安全的。

For RSA, how do i calculate the secret exponent?

Given p and q the two primes, and phi=(p-1)(q-1), and the public exponent (0x10001), how do i get the secret exponent 'd' ?

I've read that i have to do: d = e^-1 mod phi using modular inversion and the euclidean equation but i cannot understand how the above formula maps to either the a^-1 ≡ x mod m formula on the modular inversion wiki page, or how it maps to the euclidean GCD equation.

Can someone help please, cheers

解决方案

You can use the extended Euclidean algorithm to solve for d in the congruence

de = 1 mod phi(m)

For RSA encryption, e is the encryption key, d is the decryption key, and encryption and decryption are both performed by exponentiation mod m. If you encrypt a message a with key e, and then decrypt it using key d, you calculate (a^e)^d = a^de mod m. But since de = 1 mod phi(m), Euler's totient theorem tells us that a^de is congruent to a¹ mod m -- in other words, you get back the original a.

There are no known efficient ways to obtain the decryption key d knowing only the encryption key e and the modulus m, without knowing the factorization m = pq, so RSA encryption is believed to be secure.

这篇关于对于RSA，我如何计算秘密指数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！