蛮力RSA

Question

我有一个密文c_t和一个RSA公钥对(e, n)。我也知道加密的消息是一个三个字母的词，其方式如下……(a-z，a-z，a-z)现在我想解密这封密文。

我的想法如下:我想像这样用暴力解密.

if(c_t && c = (aaa)^e mod n)
if(c_t && c = (baa)^e mod n)
if(c_t && c = (caa)^e mod n)
//...
if(c_t && c = (zzz)^e mod n)
{
  //match: decrypted
}

我的下一个想法是，对于这个迭代过程，我使用3个循环(i，j，k)来检查所有可能的组合。

但我不确定是否有更好的方法来解密这样的树-字母词。

Answer 1

您的方法将恢复纯文本，我相信这是在条件允许的情况下最好的方法。毕竟，在最坏的情况下，这种方法只需要26^3测试加密操作。加密是RSA -> m^e % n中最便宜的操作，e通常是65537。

如果实现是幼稚的，那么这就是恢复纯文本所需的全部内容。但是，RSA通常使用填充方案，为了安全起见，必须这样做。如果填充方案纯粹是确定性的，那么您只需在每次测试的加密测试上运行相同的填充方案。但是如果填充方案引入了任何伪随机字节--我不知道RSA是否存在这样的方案--这很容易使纯文本的恢复变得几乎不可能。

Answer 2

当没有足够多且没有随机填充的时候，尝试所有明文的想法是有效的。这在实践中永远不会成立(使用RSAES-OAEP、RSAES-PKCS1 1 1-v1_5或RSA-KEM)。

如果满足这些条件，那么尝试所有明文都有一个优点，即使n太大而无法考虑因素(对于低于几十位小数位的n来说，n分解可能是最快的攻击)。

关于代码的几点意见

• 在计算机科学中，重复的任务(如枚举所有三个字母的单词)不应该通过为每个值编写明确的代码来完成。一个简单的替代方法是3个嵌套循环；还有其他方法，使字母数成为一个参数。
• 在RSA中，计算x^e\bmod n不应该通过计算x^e然后减少模n来执行；这将是非常低效的。有更有效的模指数技术。