24

加密算法的安全性如何依赖于大数分解？

例如，我在一些数学编程论坛上读到，通过使用二次筛或通用数域筛，可以在商用硬件上相对轻松地分解 256 位数字。

这如何转化为能够破坏 RSA、AES 等算法的安全性？能够将数字分解为密钥的长度是否足够？

是否有任何了解密码学和加密算法的人可以对此有所了解？

4

4 回答 4

9

RSA，密码算法，依赖于数论，特别是两个大素数的乘法以及难以分解的事实，以区分公钥和私钥。

这是一个关于雅虎答案的问题，有人给出了一些细节：http ://answers.yahoo.com/question/index?qid=20070125183948AALJ40l

它依赖于几个事实：

分解大数并不困难，而是分解两个大数，它们的唯一因数本身就是大素数，因为找到这些素数很困难。

快速搜索我的书签给了我这个：如果你对它的工作原理感兴趣的话，可以了解rsa 加密的数学原理。此外，这里也有一些解释——只需重新阅读我的 num-theory 笔记就可以清楚了。

  • n = p*q 给你一个很大的数给定 p,q 素数。
  • phi(n) = (p-1)(q-1)。这是费马小定理的扩展更多关于我们为什么需要这个以及为什么它在我的博客上起作用：http: //vennard.org.uk/weblog/2010/02/a-full-explanation-of-the-rsa -算法/
  • 这意味着，如果我们选择一个数字 E 与 (p-1)(q-1) 互质（没有公素因数），我们可以找到 Es inverse mod phi(n)。

  • 我们这样做，我们发现 DE = 1(p-1)(q-1) 或者更确切地说我们使用 euclid 的最大公约数算法，扩展版本来解决。

  • 现在，鉴于以上所有情况，如果我们取 T^E (pq)，我们得到 C。但是，如果我们取 (T^E)^D (pq)，我们又得到 T。

AES 不一样——它不是公钥加密。AES 采用一个密钥并在加密和解密这两个方向上使用它。该过程基本上很难撤消，就像哈希一样，但设计为可逆的。然而，它并不依赖于将大量数分解为素数来保证其安全性。它完全依赖于密钥的强度以及无法从算法中推断出密钥或给定已知明文和算法的密钥。

Wikipedia 上有一篇关于高级别的 AES 的好文章，其中有一个很好的链接，可以向您展示它是如何工作的 - 请参见此处和此处。我特别喜欢后一个链接。

于 2010-02-20T03:42:32.057 回答
4

加密算法的安全性如何依赖于大数分解？

缺少的短语是“公钥”，如“公钥加密算法的安全性如何......”

在现代密码学中有两大类密码，对称（秘密密钥）和公钥（使用公钥/私钥对）。

在每个类别中，您会发现密钥大小相对接近。对于像 RSA 和 DH/DSA 这样的公钥系统，它们都用于 OpenPGP 电子邮件加密，如今（2010 年初），常用密钥大小为 1024 位或更大。这与用于加密和解密消息的合适密钥的数学要求有关。简而言之，对于 RSA，生成两个随机大素数的因数并与它们进行乘法比对没有小因数的非常大的数进行因式分解要容易得多。正如您发现的那样，对非常大的数字进行因式分解是通过蛮力破解RSA 所需的“问题”或方法。

Diffie-Hellman / 数字签名算法 (DH/DSA) 基于不同的数学问题，计算离散对数。

由于公钥和私钥对的属性，搜索空间仅限于大素数的因子，这变得非常稀疏，因此尝试变得更加智能而不是简单地尝试分解每个非常大的数字是有意义的。

而对于 AES、RC6、RC4、Twofish、DES 和 Triple-DES 等对称密码，这些算法使用给定位长的随机密钥。任何重要的（即 0x000...000 可能是一个糟糕的密钥选择）随机密钥都是合适的。所以这些系统，如果没有针对算法本身的攻击，你可以简单地通过密钥空间搜索蛮力（即尝试所有 2^256 个可能的密钥）来解密没有密钥的消息。由于任何键都适合，因此键的密度为 2^256。

我忽略了量子计算（理论和实践），主要是因为a）我不能给出一个可靠的答案，b）它代表了一个巨大的范式转变，它可能会颠覆许多应用数学和计算复杂性的计算机科学，这种基本认识仍然是一个移动的目标。哦，我的大多数敌人还没有量子计算机。:)

我希望能解释这两种加密系统（例如 RSA 和 AES）之间的一般区别。

侧边栏：密码学是一个丰富而复杂的主题，其中的基础知识可能足够简单易懂，甚至可以编写一个幼稚的（“教科书”）实现，安全实现的复杂微妙之处使其最适合不是密码学专家的程序员使用高级密码系统，包括使用众所周知的标准协议来提高系统密码不是系统中可利用缺陷的机会。

于 2010-02-20T05:26:47.540 回答
1

AES 有很大不同，AES 创建了一个 SPN，即替代置换网络。它基于加密时生成的多项式函数生成 s-box（替换框）。它通过 10-14 轮字节级替换和位级置换来运行它，密钥的位长度决定了轮数和轮密钥。

RSA 基于大素数的因子，这些因子在计算上极难完成，但初始加密却很容易。

于 2010-02-20T04:16:50.973 回答
0

RSA 因因式分解而被破坏。实际上，RSA 是两种算法，一种用于（非对称）加密，一种用于数字签名；两者都使用相同的原语。在 RSA 中，有一个公共值（模数，通常记为n），它是两个（或多个）不同的质因数的乘积。因式分解n揭示了私钥。当n的大小时，因式分解变得更加困难增加。当前记录（今年早些时候发布）是针对 768 位整数的；非常聪明的人花了四年的时间进行大型计算和辛勤工作。同样的人公开承认，他们几乎不知道如何在 1024 位整数上尝试相同的特技（最著名的因式分解算法的一部分需要大量快速 RAM，而对于 1024 位整数）整数，需要一台可笑的巨大机器）。当前对 RSA 的密钥长度建议是短期 1024 位，长期安全性 2048 位。请注意，RSA 的计算成本也随着密钥大小的增加而增加，因此我们不想在没有充分理由的情况下使用非常大的密钥。使用 1024 位密钥，一台基本 PC 每秒（和每个内核）将产生大约 1000 个 RSA 签名，而使用 2048 位密钥则要少八倍。这还是相当不错的。

还有其他非对称加密算法和数字签名算法。与 RSA 有点相关的是 Rabin-Williams 加密算法。保理也打破了它。然后是基于离散对数的算法（在以大素数为模的乘法组中）：Diffie-Hellman（密钥交换），DSA（签名），El Gamal（加密）......对于这些算法，分解不是直接的威胁; 但是它们依赖于数论的相同部分，并且最着名的离散对数算法与最着名的分解算法非常相似（并且具有相同的名称：GNFS - as General Number Field Sieve）。因此，人们怀疑因式分解的进步将源于数论的进步，这也可能对离散对数有所启发。

离散对数算法可以应用于其他组，最流行的是椭圆曲线。椭圆曲线不受因式分解的影响。如果分解变得容易，从而刮掉 RSA 并间接危害 DSA 和 Diffie-Hellman，那么我们将切换到 ECDH 和 ECDSA；标准和实现已经存在并被部署。

“对称密码学”，即散列函数（MD5、SHA-256...）、认证码（HMAC、CBC-MAC...）、对称加密（AES、3DES...）、随机数生成（RC4.. .) 和相关活动，完全不受因式分解的影响。对于这些算法，密钥只是一堆比特，没有任何特殊结构；没有什么可考虑的。

于 2010-02-22T00:46:00.373 回答