RSA私有指数确定 [英] RSA private exponent determination

问题描述

我的问题是关于RSA签名。

如果是RSA签名：

加密 - > y = x ^ d mod n，
decrypt - > x = y ^ e mod n

• li>
  
• y - >加密邮件


• n - >模数（1024位）


• / li>
  
• d - >私人指数

我知道x，y，n和e。知道这些可以确定d？

解决方案

如果你能够因素n = p * q，那么d * e≡ 1（mod m）其中m =φ（n）=（p-1）*（q-1），（φ（m）是 Euler的函数），在这种情况下，您可以使用扩展欧几里德算法来确定d。 （对于一些k，d * e-k * m = 1）

除了因子分解之外，这些都是非常容易计算的，公钥加密是一种有用的技术，无法解密，除非您知道私钥。

因此，为了在实际意义上回答您的问题，不能从公钥导出私钥，除非您可以等待成百上千的CPU - 年份到n。

---

公钥加密和解密是相反的操作：

x = y ^e mod n =（x ^d sup> mod n = x ^{k （n）+1} mod n = x *（x ^{= x mod n}

其中（x ^φ（n）） ^k = 1 mod n， a href =http://en.wikipedia.org/wiki/Euler%27s_theorem =nofollow>欧拉定理。

My question is about RSA signing.

In case of RSA signing:

encryption -> y = x^d mod n, decryption -> x = y^e mod n

• x -> original message
• y -> encrypted message
• n -> modulus (1024 bit)
• e -> public exponent
• d -> private exponent

I know x, y, n and e. Knowing these can I determine d?

解决方案

If you can factor n = p*q, then d*e ≡ 1 (mod m) where m = φ(n) = (p-1)*(q-1), (φ(m) is Euler's totient function) in which case you can use the extended Euclidean algorithm to determine d from e. (d*e - k*m = 1 for some k)

All these are very easy to compute, except for the factoring, which is designed to be intractably difficult so that public-key encryption is a useful technique that cannot be decrypted unless you know the private key.

So, to answer your question in a practical sense, no, you can't derive the private key from the public key unless you can wait the hundreds or thousands of CPU-years to factor n.

---

Public-key encryption and decryption are inverse operations:

x = y^e mod n = (x^d)^e mod n = x^de mod n = x^kφ(n)+1 mod n = x * (x^φ(n))^k mod n = x mod n

where (x^φ(n))^k = 1 mod n because of Euler's theorem.

这篇关于RSA私有指数确定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！