破译密码的奥妙

世上万物总是相生相克。既然有人研究密码，也就有人研究破译密码的办法。

密码之所以会被破译，是因为它有一个致命的弱点，即“设密”与“解密”使用的是同一个“密钥”。这样，密钥的得与失，便事关着大局。

本世纪 70 年代，许多研究密码的专家发现，把一些正向容易逆向困难的

数学问题用来设密，可以收到极好的效果！例如，把两个 50 位的质数相乘， 这是一件容易的事；但要从它们的乘积分解出这两个质数来，即使用电子计算机也需用 100 万年。后者看起来似乎是个有限的时间，但实际上可以看成是无限的！上述问题寓难于易，寓无限于有限，这正是构造一切密码的规律！

现在我们就利用上面的例子来设置密码。令合数 n＝pq，P、p 为质数。加密时，先选一个既不能整除 p－1，又不能整除 q－1 的质数 r；然后，将需要加密的明码 a 乘方 r 次，再除以 n 得到余数 a′，则 a′便是密码。从明码求密码的过程是很容易的，两者的关系用式子可以写成：

ar≡a′（modn） 以上算式的意思是：ar 和 a′除以 n，余数相同。

解密时，关键是要找一个 s，使它满足sr≡1（mod（p－1）（q－1））数学上可以证明，此时必有：

（a′）s≡a（modn）

其实，这一点是不难验证的。上一节说过，公元 1736 年，欧拉证明了费

尔马小定理。过了 24 年，公元 1760 年，欧拉又将这个定理推广为更一般的。即若 C 与 n 互质，则

Cφ（n）≡1（mod n）

1 1 1

式中φ（n） = n(1 - p )(1- q ) (1 - t )

其中 p，q⋯，t 是 n 的质因子。

由于我们加密时选取 n＝pq（p、q 为质数），因而

1 1

φ（n） ＝pq(1 - p)(1 - q )

＝（P－1）（q-1） 这样，根据欧拉定理，便有：

（a′）（p－1）（q－1）≡1（mod n）

∵ Sr≡1（mod（p－1）（q－1）

∴ Sr≡1＋k（p－1）（q－1），（k∈N）

从而 （a′）s≡a′·（a′）k（p－1）（q-1）（mod n）

≡a′·1k（mod n）

≡a′（mod n）

∵ ar≡a’（mod n）

∴ （a’）sr≡ar（mod n）

这与解密中的算式（a’）s≡a（mod n），没有矛盾！

现在我们回到密码的设置上面来。很明显，无论是加密时由 a 求 a’， 或解密时由 a’求 a，对于知道 p、q 的人都是很容易的。举例说，设

p=5，q＝7，n＝35；a＝9

选 r＝5，它显然既不整除 p－1＝4，也不整除 q－1＝6

ar=95≡4（mod35） 从而 a′＝4 即为相应于 a＝9 的密码。

解密时，算得（p－1）（q－1）＝4×6＝24。显然可以取 S＝5，（sr＝ 25＝1＋24），由

（a′）s＝45≡9（mod35）

可以还原出明码 a＝9

上述密码几乎可以是公开的，即使把 n 和 r 告诉对方也无妨！关键在于n 的分解。选取的质数 p、q 越大则 n 的分解越难。

自从快速鉴别质数的方法出现之后，有人甚至用 100 位的质数来构造密码。