一、忆儿时
当我们小的时候，或多或少会玩过一些密语的游戏；就是以一种很顽皮的方式传达信息给对方，懂的人就知道你在讲什么，不懂的人就鸭子听雷似的根本不晓得你在胡说些什么。比如我们要说:
「寄钱来」, 但讲的时候将每个字注音的最后一个音不发出来，如果只有一个音就还是发那个音。所以讲出来就变成
「ㄐㄑ一ㄌ」,
请问你抓得到是什么意思吗？这个例子当然还不够格称之为密码，仅仅是一个有趣的开场白而已。现在让我们看看真正密码的例子，由这些例子中我们也能体会到数论在密码术中的份量。难怪 Bruce Schneier11Bruce Schneier (布鲁斯
施奈尔) 是国际闻名的一位信息安全专家及作家，他是 Counterpane Internet Security,
Inc.(专精于密码术与计算机安全的一个顾问公司) 的创始者同时也是这个公司的 CTO (Chief Technical
Officer)。他所写的应用密码术 (Applied Cryptography)
一书被誉为密码术的圣经，是最好的入门介绍书之一。其著作翻译成中文者有「秘密与谎言」, 由商周出版社于 2001 年 9 月 16 日初版发行。说: 「These days almost all cryptologists are also theoretical mathematicians-they have to be」。
二、一个例子
现在我们用英文的二十六个字母来传达这个信息 首先我们用 NUMBER THEORY 当成所谓的 (加密) 钥匙，将重复的字母去掉剩下 NUMBERTHOY, 然后把这些字母放在依序排列的二十六个字母下面，再将其余字母依序排列如下:
很显然的这是个一一对应，我们把上一行的字母用下一行相对应的字母顶替，那么所要传达的信息就变成为 换句话说 LEFB DGFEX 是 SEND MONEY 的密文。
三、安全性可虑？
代换法虽然对长一点的信息来说并不是一个妥当保持信息安全的好方法，但谁能识破其真相呢？值得怀疑！因为从观察 LEFB DGFEX 中，重复的字母提供了唯一的线索。由此线索推论出来与原信息同一形式的信息可能是
当然你如果知道那加密的钥匙以及整个方法，你就能如法制作上表并将整个过程逆推回去得到原先的信息。这意味着解密的钥匙很容易就可以从加密的钥匙得到，此乃传统密码术的特性，通常称之为对称式密码系统。所以这整个信息的安全性，完全掌控在那
(加密的) 钥匙，只要能保住此钥匙的秘密性则安全性大抵上没问题。此处尚有多重的困难需要考虑:
此钥匙是传递信息的双方都要知道的，只要有一方没保住，安全性就被破坏了。
何况有时候传递信息的对象是多方的，而人多嘴杂，安全性更是可虑。
从另一个角度来看，如果钥匙很复杂，复杂到必须「写下来」; 那么被发现的机会更是有增无减。
而且利用此法互通信息时，也必须事先安排好如何让要秘密通信息的双方或多方同意或知道此钥匙。这整个的「事先安排」也要妥善极机密的进行才可以。
由于这种种的原因，刺激人们去探讨「更高杆的」或「更深入的」密码术。所以我们希望「信息的安全性」不会受制于「钥匙的秘密性」,
亦即我们希望「信息的安全性」能独立于「钥匙的秘密性」。换句话说，我们希望即使钥匙是公开的，信息仍然能维持其安全性。更具体的说，我们想要达到的目标是:
「给你钥匙，你只能将原信息变成密码文，却无法将密码文破解回归其庐山真面目。」
这对传统的密码系统来说是不可能的，因为解密钥匙与加密钥匙是对称的，公开加密钥匙就等于是公开解密钥匙。所以我们必须将加密钥匙与解密钥匙之间的对称性打破，唯有如此才能突破僵局。很自然的，说到钥匙就会联想到门。有许多公共建筑物的大门，当你从门内到门外只要将门一推即可，毫无困难；但反过来则否，必须有钥匙才能从门外回到建筑物内。从门内将门一推，表面上好像是不需钥匙；实际上那推的动作因为每个人都知道，可以看成是公开的钥匙。门里门外是全然不同的两个世界。
四、来自数论的灵感
如何能达到上面的目标呢？乍看之下似乎不可能，但门的比喻给我们一些启发或暗示。在数论中有类似的例子。譬如，找出两个很大的质数 与 (说是一百位数好了) , 然后将这两个质数相乘得到其乘积为 。这整个过程比起其逆过程 (给你 , 找出这两个质数) 来得简单，而且简单得许多。
下面的例子中为了方便说明起见，我们取较小的两个质数 与 ; 如 至少 25, 那你就查验 26,27,28 都不是，29 是也； 至少 40, 下一个数 41 就是了。这个步骤很快，然后将其相乘得到 , 这个步骤也很快。反之，给你 1189, 那你就得试 2,3,5,7,11,13,17,19,23 等共九个除法之后的 29 才得到整除:
这里因为 1189 很小，感觉不出找 29 会有困难，但当 为一 200 位数的整数时，其困难度可想而知！我们还会用到整数 , 此数与 互质。在我们的例子中可取 , 此处 是公开的钥匙，而 与 则保持秘密。这次我们将 26 个英文字母及空白用整数来表示如下:
再一次的我们要传递 SEND MONEY 这一信息。先将其化为对应的数字，如下:
因为 1189 是四位数，所以我们将信息分为三位数一组，如下:
(在尾巴加了一个 0, 因为最后一组数 25 不是三位数)。我们用 来表示这些三位数，然后按照下面的法则转换成密码: 此处 为介于 0 与 之间的整数，亦即被 除的余数。
所以收到的密文为: 如何将这些密文 破解回归其庐山真面目 呢？令 为 与 的最小公倍数 (注意：若不知 则 就无从知道), 且令 为同余方程式 中的最小正整数解。解出得 , 然后计算 即可得 。
为何如此呢？且将此问题暂时摆在一旁，我们先来算 。第一个碰到的是 , 即将 848 自乘 187 次，这是一个很大的数。表面上你得执行 186 次的乘法，这相当花时间。如果只是平方，速度就非常快。重复此一运算，我们就得到 4 次方、8 次方、16 次方、32 次方、64 次方、128 次方 , 这提供了一个解决 的计算问题。先将 187 写成 (即 187 之二进制表示法为 10111011) 再依次计算 848 的 次方如下：(这儿我们引进负数，为的是将每个数的大小调成比 小；如此可稍稍减少所要执行的计算量，特别是当你用手算时这是一大帮助。)
所以我们得到
值得注意的是，原来需执行 186 次乘法的计算，用上面的算法只需 12 次。同法可算出其他的如下:
所以我们就得到原来的 为何这个方法行得通呢？从 到 其运算为 而解密 则计算 我们要证明 。实际上我们假设 都是小于 的正整数，所以只要证明 即可！由定义可知 而 为同余方程式 中的最小正整数解，此处 为 与 的最小公倍数 (因我们取 与 及 互质，因此 与 互质，所以此同余式有解)。令 。若 , 则费马小定理告诉我们 。因 , 所以 。因此 若 , 则上面的同余式显然成立。同理 因此
五、计算之复杂度的分析
经过上面的一番计算之后，让人深深的觉得这些计算最好是由计算机来代劳。我们同时也注意到分解 的困难度是整个方法的安全性之关键，但在上例中有些计算却比分解 来得复杂得多。当然如果你有办法算出 848 自乘 187 次，则分解 1189 应该是简单之至。这好像有点似是而非，如何解释这种似是而非的现象呢？这就牵涉到整个计算当中数字的大小以及计算的复杂度的问题。记得吗？在实际的应用当中，质数 与 都是 100 位数之大，相乘之后就变成 200 位数。所以在加密或解密的计算很大次方的过程当中，虽然我们不可嗤之以鼻的轻看其计算量，但比起要分解一个 200 位数 (就目前已知的算法) 的计算量是来的少，而且少很多。
要分析这其中的奥秘，我们就得将所涉及到的运算分解成一些最基本的运算，如加法、减法、乘法、除法、以及相互比较
(Comparison)。当然，数字的大小会影响到计算机去执行这些运算的时间。所以为了简单起见，我们假设所有这些运算所需的时间都是一样的，比如说一秒一百万次。
在解密的过程中，最困难的地方似乎是将一个数自乘 次，此处 为同余方程式 中的最小正整数解，而 所以我们可假设 。首先我们把 连续除以 2, 将之化为二进制数。这需要几次的除法呢？很明显的，这个数目就是 的二进制表示法的位数，说是 吧！则 所以我们得知 的一个上界为 。此数随着 的增加而增加，但成长的非常缓慢；如 是 200 位数，而 比 700 还小。
我们在上面用了平方法来处理次幂的计算，先做了 次的平方然后除以 得其余数。这需要少于 700 次的乘法及少于 700 次的除法，所以合起来不会超过 2100 次的基本运算。若要我们用手去算，门都没有！但对计算机来说这可是轻而易举的事情，不吭半声所有的计算就结束了。接着将这些所得到的平方数两两相乘再除以 得其余数，这不超过 次的乘法也不超过 次的除法，所以所需要的基本运算合起来不会超过 3500 次。
再来我们得估计一下解同余方程式 所需的基本运算的次数。这需要将 与 辗转相除，不难证明其次数会少于 , 即 1400 次的除法。逆推回去，将 1 写成 与 的线性组合，所需要的基本运算跟前面的辗转相除法合起来不会超过 2800 次。
所以加密与解密合起来所需要的基本运算最多不会超过 10000
次，而以一秒一百万次的速度来执行这些基本运算的计算机，在一秒钟里面就可以完成十件这种计算的工作。也许一秒作一百万次基本运算的计算机是快过现有的任何一部计算机，但这样的假设只不过是提供我们作为「比较」的用途。退一万步来想，我们假设那试图破解密文的人有如此快速的计算机可使用也是应该的，因为做最坏的打算才是上上之策！
六、谁还管生生世世夜夜朝朝？
话说回来，那试图破解密文的人必先分解那巨大无比的 200 位数 成为 , 由此来解出 然后再执行上述的计算来解密。如果此人所用来分解 的方法是除以从 1 开始一直到 的所有整数的话，那么光这项工作就得执行 次的除法。如果我们用一秒一百万次快速的的计算机也需要 秒钟，亦即 年左右才能算完。当然实际上只需除以其中的质数，但问题是要去判别在 100 位数之内何数为质数，这是相当头痛的事情。即使用现今最快速的计算机及最有效率的算法要分解一个 200 位数，也要 40 亿年才能完成。到那时候，谁还管何人会来看我们的信息呢？
本文转自数学传播