作为一个非密码学家，有一件事总是让我震惊:为什么使用质数如此重要?是什么让它们在密码学中如此特别?
有人能简单解释一下吗?(我知道有很多入门知识，应用密码学是圣经，但如我所说:我不打算实现我自己的加密算法，我发现的东西只是让我的大脑爆炸-请不要十页的数学公式)。
当前回答
有一些很好的资源可以加强加密。这里有一个:
http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx
从那一页开始:
In the most commonly used public-key cryptography system, invented by Ron Rivest, Adi Shamir, and Len Adleman in 1977, both the public and the private keys are derived from a pair of large prime numbers according to a relatively simple mathematical formula. In theory, it might be possible to derive the private key from the public key by working the formula backwards. But only the product of the large prime numbers is public, and factoring numbers of that size into primes is so hard that even the most powerful supercomputers in the world cant break an ordinary public key.
布鲁斯·施奈尔的《应用密码学》是另一本。我强烈推荐这本书;读起来很有趣。
其他回答
为了更具体地说明RSA如何使用素数的性质，RSA算法主要依赖于欧拉定理，该定理指出，对于相对素数“a”和“N”，a^e等于1模N，其中e是N的欧拉totient函数。
质数是怎么进来的?为了有效地计算N的欧拉totient函数，需要知道N的质因数分解。在RSA算法中，对于一些质数“p”和“q”，N = pq，那么e = (p - 1)(q - 1) = N - p - q + 1。但是如果不知道p和q, e的计算是非常困难的。
更抽象地说，许多密码学协议使用各种活板门函数，这些函数易于计算但难以反演。数论是这类活板门函数的丰富来源(例如大素数的乘法)，而素数是数论的绝对中心。
Cryptographic algorithms generally rely for their security on having a "difficult problem". Most modern algorithms seem to use the factoring of very large numbers as their difficult problem - if you multiply two large numbers together, computing their factors is "difficult" (i.e. time-consuming). If those two numbers are prime numbers, then there is only one answer, which makes it even more difficult, and also guarantees that when you find the answer, it's the right one, not some other answer that just happens to give the same result.
给你的另一个资源。现在安全了!第30集(约30分钟的播客，链接到文本)讨论了密码学问题，并解释了为什么质数很重要。
因为每找到一个因子，分解算法的速度就会大大加快。将两个私钥设置为素数可以确保找到的第一个因子也是最后一个因子。理想情况下，两个私钥的值也几乎相等，因为只有较弱的密钥的强度才重要。
有一些很好的资源可以加强加密。这里有一个:
http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx
从那一页开始:
In the most commonly used public-key cryptography system, invented by Ron Rivest, Adi Shamir, and Len Adleman in 1977, both the public and the private keys are derived from a pair of large prime numbers according to a relatively simple mathematical formula. In theory, it might be possible to derive the private key from the public key by working the formula backwards. But only the product of the large prime numbers is public, and factoring numbers of that size into primes is so hard that even the most powerful supercomputers in the world cant break an ordinary public key.
布鲁斯·施奈尔的《应用密码学》是另一本。我强烈推荐这本书;读起来很有趣。
