作为一个非密码学家,有一件事总是让我震惊:为什么使用质数如此重要?是什么让它们在密码学中如此特别?
有人能简单解释一下吗?(我知道有很多入门知识,应用密码学是圣经,但如我所说:我不打算实现我自己的加密算法,我发现的东西只是让我的大脑爆炸-请不要十页的数学公式)。
作为一个非密码学家,有一件事总是让我震惊:为什么使用质数如此重要?是什么让它们在密码学中如此特别?
有人能简单解释一下吗?(我知道有很多入门知识,应用密码学是圣经,但如我所说:我不打算实现我自己的加密算法,我发现的东西只是让我的大脑爆炸-请不要十页的数学公式)。
当前回答
最基本和一般的解释:密码学都是关于数论的,所有的整数(除了0和1)都是由质数组成的,所以你在数论中要处理很多质数。
More specifically, some important cryptographic algorithms such as RSA critically depend on the fact that prime factorization of large numbers takes a long time. Basically you have a "public key" consisting of a product of two large primes used to encrypt a message, and a "secret key" consisting of those two primes used to decrypt the message. You can make the public key public, and everyone can use it to encrypt messages to you, but only you know the prime factors and can decrypt the messages. Everyone else would have to factor the number, which takes too long to be practical, given the current state of the art of number theory.
其他回答
有一些很好的资源可以加强加密。这里有一个:
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加密算法通常用于安全的商业网站,它是基于这样一个事实:取两个(非常大的)素数并将它们相乘很容易,而做相反的事情则非常困难——这意味着:取一个非常大的数,给定它只有两个素数因子,并找到它们。
给你的另一个资源。现在安全了!第30集(约30分钟的播客,链接到文本)讨论了密码学问题,并解释了为什么质数很重要。
质数本身并不重要,重要的是处理质数的算法。特别是求一个数(任何一个数)的因式。
如你所知,任何数字至少有两个因数。质数有一个独特的性质,它只有两个因数:1和质数本身。
The reason factoring is so important is mathematicians and computer scientists don't know how to factor a number without simply trying every possible combination. That is, first try dividing by 2, then by 3, then by 4, and so forth. If you try to factor a prime number--especially a very large one--you'll have to try (essentially) every possible number between 2 and that large prime number. Even on the fastest computers, it will take years (even centuries) to factor the kinds of prime numbers used in cryptography.
事实上,我们不知道如何有效地分解一个大数字,这赋予了密码算法的优势。如果有一天,有人想出了如何做到这一点,我们目前使用的所有加密算法都将过时。这仍然是一个开放的研究领域。