密码为什么一定要用质数？

看到了一篇科普文章，就很奇怪为什么一定要用质数？
为什么文中说，要求pqr必须是质数？是质数的话，就算很大，但理论上就算不知道质数是多少，也一定有唯一的幂。而如果大家商量好找三个合数的话（只要这三个合数不是彼此的几次方的话，比如4 16 64这样的），那岂不是只要不知道这三个合数是多少，就永远也不可能破解开了，同时也能保证知道这3个合数的情况下幂是唯一的？

我猜我这个问题对于数学大神，甚至一般的数学学者来说肯定特别白痴……但是还是求解答呀……

呜…

说一点个人的理解吧…

首先这个例子很明显是不恰当的。看起来像是在拙劣地模仿RSA而失败了（关于为什么不恰当，一会会有说明）

那么进入正题。

首先，关于为什么不用合数。

在这个例子里，合数当然是没有问题的。

我们把这n个数（题中为三个）的全部m个素因子提取出来，并定义aij为第i个数中第j个因子的次数。

那么只要这个矩阵A的秩是n，问题就是理论上可解的。

那么基于此，我们就能构造出一个反例

6,12,24

那么解密一方是无法确认144=6×24=12×12的原始信息的。

在RSA演算法中也是类似——如果使用合数，并不是「安全性下降」这种问题，而是「加密-解密」的逆运算就不成立。

然后我们来说，文中的例子为什么是糟糕的。

我们要明确的一个前提是，在我们的讨论中，密钥应当被多次使用——不然如果是一次性密码本（密钥长度=密文长度）的话，简单的xor就能够构成即使在数学上也是不可破译的密码了。

那么，在这个问题里。如果Eve收到了几段不同的信息——那么不去取一下最大公约数的话岂不是屑。

毕竟取最大公约数又没有什么太高的复杂度（摊手）

只要多做几个来回，很轻易地，窃听者Eve就可以还原出这几个素数。然后的事情就……

如果大家商量好找三个合数的话（只要这三个合数不是彼此的几次方的话，比如4 16 64这样的），那岂不是只要不知道这三个合数是多少，就永远也不可能破解开了

就事论事吧，不说RSA了。

你的论点不成立

首先，你应当注意到，我们在这里的约定是「一次性」的，我们不会在每次传递信息之后重新约定pqr——但与此同时，传递信息可能会有多次。

某些时候，传递的信息可能会有一定的规律，比如如果你传递ASCII码英文字母的话，传递的信息的大小是受到限制的——同时你应当注意，如果你传递的字母需要组成单词（而不是传递一串乱码），那么，我们可以很方便地判定某个解是否是密码

注意到这一点，破译合数密码会简单很多：

比如，合数可以继续分解成更小的质数：

破译者没必要知道合数的任何信息，破译者只需要看合数的几个素因子就好。

把质数改成合数，对破译者来说，只是小麻烦而非大麻烦。

——然而，如果改成合数，很可能破坏分解难度/增加需要传递的信息的长度

得不偿失

关键是：你需要对因式分解的难度有一定的认知：

一年有多少秒：3.15e+07。太湖之光超级计算机每秒浮点数运算次数：125.436PFlops(Peta,e+15)，即1.25e+17。那么，使用太湖之光超级计算机对200位素数穷举法因数分解需要2.52e+191年，地球的年龄约4.5e+10年，宇宙的年龄约1.4e+11年。大家可以想像一下这个时间尺度。

关于素数可以看这篇文章

离散数学极简教程（三）——素数的故事?

mp.weixin.qq.com

用不用质数取决于加密的方式。

你的例子单从传递信息角度可以用合数，只要pqr互质就行。（不互质的话，加密没问题，解密可能出现多解）

从分解角度，你的pqr如果是合数，那么结果含有更多较小的素因子，如果对方从小因子开始试除，那么分解会更快。

当然，因子分解目前没有特别好的方法，有的方法对小因子多的快，有的对几个因子差不多大的快，具体快慢要看对方用哪种方法，而你应该从最坏的情况考虑。

也就是说，你很可能降低了破解难度。

谢邀，做过一点密码学的研究，学过一点RSA密钥公里体系，也有图像加密的研究，但是仍然不是很了解，但我想用质数的原因是因为他足够特殊，如果说整个自然数是一座大厦，素数毫无疑问是组成这座大厦的基石，因为任给一个自然数除0和1，都可以在变换次序的意义下进行唯一的素数的分解，而中国剩余定理(对就那个韩信点兵问题)其实就算是RSA加密的理论，也是只针对素数展开的(点兵问题是3，5，7吧，不记得很清，但是肯定是素数)这个跟解法有关，至于有没有基于非素数的加密方法呢，我不清楚可能是有的，对比较特殊的合数，开个脑洞，比如说平方数，费马数或者菲比拉契数，但是我真不了解不胡说。密码理论是一个非常高深的学科，数论，群论等很多理论都需要用到。但是为什么密码一定要用质数呢，我只能说够简单够经典，如果用其他的比如费马数，菲比拉契数，那么加密耗费内存就很大，相比这两者而言，用孪生素数可能还代价小点，当然素数是最理想最简单的了。

RSA不是拿素数这么玩的。这只是个简单例子，用来展现「质因数分解是困难的」这个事情。

因为合数能拆分成更小的质数你等于降低了破解难度用更大的数传递了更少的信息比如同样是210你用14和15做因子只能传递1 1这个信息我用 2 3 5 7能传递1 1 1 1这个信息两条信息的破解难度相同而用11和 13作为因子传递 1 1这个信息他需要的数143更小反而比210更难破解

数论密码已经有人说了。我补充下吧，很多密码都用有限域为基础。而有限域的元素个数是必定是 q^n for some positive prime number q and some natural number n. 为什么用有限域，因为很多问题放到有限域上会变得很难，比如MQ problem, 在有限域上解多变数二次多项式组，因为没有度量空间，就没有办法逼近用numerical 办法。