encryption - 能够分解大量数字如何决定流行加密算法的安全性？

Question

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

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

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

有没有熟悉密码学和加密算法的人可以对此有所了解？

Answer 1

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

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

它依赖于几个事实:

n=p.q易计算难逆

费马小定理:http://en.wikipedia.org/wiki/Fermat%27s_little_theorem

数论的各种结果。

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

快速搜索我的书签给了我这个: the mathematical guts of rsa encryption如果您对它的工作原理感兴趣。另外，这里也有一些解释 - 只需重新阅读我的 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-algorithm/

这意味着，如果我们选择一个数 E 互质(无公质因数)到 (p-1)(q-1) 我们可以找到 Es 反模 phi(n)。

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

现在，考虑到以上所有内容，如果我们取 T^E (pq) 我们得到 C。然而，如果我们取 (T^E)^D (pq) 我们又得到 T。

AES 不一样——它不是公钥密码学。 AES 使用一个 key 并在加密和解密两个方向上使用它。这个过程基本上很难撤销，就像一个散列，但被设计为可逆的。然而，它的安全性并不依赖于将大数分解为素数。它完全依赖于 key 的强度，并且无法从算法或已知明文和算法的情况下推断出 key 。

维基百科有 a good article on AES高层次的，有一个很好的链接，向你展示它是如何工作的 - 见 here和 here .我特别喜欢后一个链接。