为什么有的密码可以公开

密码，顾名思义旨在保密，怎么可以公开呢？但是，现代的保密通信专家确实发明了一种“公开”加密密钥的密码体系。它是由狄菲和赫尔曼于1976年首先提出的，至今不过10多年。

这种“公开密钥”的密码体制的基本思想是这样的：每—个通信方都有一个加密密钥和一个解密的密钥，加密密钥是公开的，而解密密钥是严格保密的，只有他本人才知道。

如果甲要发送某个消息P给乙，甲首先要在公开的密钩表中查到乙的加密密钥f，然后将明文P加密，成密文f（P），并发送到乙。

乙收到密文f（P）之后，用只有他自己知道的解密密钥f^-1，将密文还原成明文P。

传统的密码学，如果加密密钥被第三者掌握，那么解密密钥随即也就知道了，而在公开密钥的密码体制中，加密密钥与解密密钥不相干，即使知道了加密密钥，也无法破译密文。

目前使用的公开密钥的密码体系有两种，一种叫背包式，一种叫RSA式。

背包式密码体制与数学中的“背包问题”有关。所谓“背包问题”是这样的：一个旅行者的背包容积为M，他有若干件物品容积分别为a₁，a₂，…，a_n，背包容不下所有的物品，为此，他要从中挑选出若干件装进背包，问怎样挑选，使背包装得无空隙？

一般的背包问题至今还没有找到完整的解法，但对于简单的类型还是不难求解的。例如，背包容积为14，物品容积a₁=1，a₂=3，a₃=5，a₄=10，a₅=21，那么，我们可以挑出a₁，a₂，a₄三件物品装进背包里去就可以了。如果把挑出的物品记为1，挑剩的物品记为0，那么依次可得11010，这个二进制数也就是这个背包问题的解。

我们可以把11010看作一个信息（明文），从而把其中的1和0依次与a₁=1，a₂=3，a₃=5，a₄=10，a₅=21相乘，其和为14，这个过程可以看作加密，所得的结果14，可以看作密文。如果第三者截得了密文14，也知道了a₁，a₂，…，a₅这一组数值，很快可以求得11010这一个二进制数（明文），因为这只是解一个简单的背包问题而已。这种方式的编码方法没有什么价值。为此，密码专家在此基础上做了点手脚。譬如，对上面的a₁，a₂，…，a₅中的每一个数都乘以7，再除以45，所得余数分别是b₁=7，b₂=21，b₃=15，b₄=25，b₅=12。然后将明文11010中的1和0分别依次与b₁，b₂，…，b₅相乘，得到结果为53（密文）。这样一来b₁，b₂，…，b₅就成了加密的密钥，它是可以公开的。第三者即使截获了密文53，也查到了b₁，b₂，…，b₅仍然难以求出明文11010，因为这是个难解的一般背包问题。但收信人乙利用只有自己知道的7和45这两个数（解密密钥），却可以轻而易举地将b₁，b₂，…，b₅还原成a₁a₂，…，a₅，将53还原成M=14。再从M=14和a₁，a₂，…，a₅求出明文11010。

RSA体制涉及到整数的分解。至今，对于很大的整数，我们还没有一套办法能够将它们分解为质数的积。RSA体制正是利用这一点设计的。

RSA体制的基本思想是这样的：取两个质数（一般应该取很大的质数，譬如是六七十位的质数，这里为简便起见，取得很小），假定这两个质数是p=5，q=11。将它们相乘，得n=55。然后，算出

l=（p-1）（q-1）=40。

再取一个与l互质的数e，譬如e=7。n和e就可以作为加密密钥加以公开。

如果发信人甲，要将明文“3”告诉乙，那么，就可以利用乙的加密密钥n（=55）、e（=7）加密。方法是这样的：求出3的e（=7）次幂，再除以”（=55）得到余数42。这个“42”就是密文。

乙收到“42”之后，利用只有自己知道的解密密钥d=23解密。解密方法是这样的：求出42的d（=23）次幂，再除以n（=55），余数是3（明文）。

如果第三者收到密文42，即使他查出乙的加密密钥n和e，也无法破译密码。因为解密时要用到d（=23），而求d，必须要将n分解为p与q的积，要知道n是几百位的大数，要将它分解谈何容易！所以，第三者只能对着公开的大数n“望数兴叹”！

科学工作者预计，几十年内大整数分解问题难以解决，所以RSA体制或许可以通行一段时间。原先以为一般背包问题难以解决，所以背包体制也是保险的。但是，最近有消息说，背包体制是不安全的。真是有“矛”必有“盾”，“矛”进步了，“盾”也不能一成不变的。