作为一个非密码学家,有一件事总是让我震惊:为什么使用质数如此重要?是什么让它们在密码学中如此特别?
有人能简单解释一下吗?(我知道有很多入门知识,应用密码学是圣经,但如我所说:我不打算实现我自己的加密算法,我发现的东西只是让我的大脑爆炸-请不要十页的数学公式)。
作为一个非密码学家,有一件事总是让我震惊:为什么使用质数如此重要?是什么让它们在密码学中如此特别?
有人能简单解释一下吗?(我知道有很多入门知识,应用密码学是圣经,但如我所说:我不打算实现我自己的加密算法,我发现的东西只是让我的大脑爆炸-请不要十页的数学公式)。
当前回答
为了更具体地说明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的计算是非常困难的。
更抽象地说,许多密码学协议使用各种活板门函数,这些函数易于计算但难以反演。数论是这类活板门函数的丰富来源(例如大素数的乘法),而素数是数论的绝对中心。
其他回答
最基本和一般的解释:密码学都是关于数论的,所有的整数(除了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.
我建议你读《代码中的数学之旅》这本书。这本书有一种很好的接地气的感觉,这是令人惊讶的,因为它是关于密码学的。这本书总结了Sarah Flannery从一个孩子学习谜题到在16岁时创建Cayley-Purser (CP)算法的旅程。它对单向函数、数论、质数以及它们与密码学的关系给出了令人惊讶的详细解释。
让这本书更具体地回答你的问题的是Sarah试图使用矩阵实现一个新的公钥算法。它比使用质数要快得多,但发现了一个可以利用它的循环漏洞。事实证明她的算法更适合作为私人加密机制。这本书是使用质数进行加密的一个很好的证明,因为它经受住了时间的考验和非常聪明的人的挑战。
因为没有人知道一个快速的算法把一个整数分解成质因数。然而,检查一组质因数是否乘以某个整数是非常容易的。
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.
简单的?是的。
如果你把两个大素数相乘,你会得到一个只有两个(大)素数因数的巨大非素数。
分解这个数字是一个非平凡的操作,这一事实是许多密码学算法的来源。有关更多信息,请参阅单向函数。
附录: 再解释一下。两个质数的乘积可以用作公钥,而质数本身可以用作私钥。对数据所做的任何操作,如果只能通过知道这两个因素中的一个来撤销,那么解密起来就不是简单的了。