cryptography - RSA私有指数确定

Question

我的问题是关于 RSA 签名的。

如果是 RSA 签名：

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

• x -> 原始消息
• y -> 加密消息
• n -> 模数（1024 位）
• e -> 公共指数
• d -> 私有指数

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

Answer 1

如果可以因式分解 n = p*q，则 d*e ≡ 1 (mod m) 其中 m = φ(n) = (p-1)*(q-1)，（φ(m) 是欧拉的总函数）在这种情况下，您可以使用扩展欧几里得算法从 e 确定 d。（对于某些 k，d*e - k*m = 1）

所有这些都非常容易计算，除了因式分解，它被设计为非常困难，因此公钥加密是一种有用的技术，除非您知道私钥，否则无法解密。

因此，从实际意义上回答您的问题，不，您不能从公钥中导出私钥，除非您可以等待数百或数千个 CPU 年来分解 n。

---

公钥加密和解密是逆运算：

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

其中 (x ^φ(n) ) ^k = 1 mod n 因为欧拉定理。

Answer 2

在两种情况下答案是肯定的。一，有人因素n。第二，有人将算法作为一个米奇，并说服签名者使用 x 的几个可能的特殊值之一。

应用密码学第 472 和 473 页描述了两种这样的方案。我不完全了解它们在实践中的工作方式。但解决方案是使用无法由想要确定 d 的人（又名攻击者）完全控制的 x。

有几种方法可以做到这一点，它们都涉及散列 x，以可预测的方式调整散列值以删除一些不需要的属性，然后对该值进行签名。这样做的推荐技术称为“填充”，尽管有一种非常出色的技术不能算作填充方法，可以在实用密码学中找到。

Answer 3

不，否则私钥将毫无用处。