保密通信有很长的历史，在国家的军事和外交、经济商务、企业管理和保护个人隐私方面都有要求。

通讯双方为了保密，内部有一套秘密约定，这个秘密约定叫做密钥。如果别人掌握了这把秘密钥匙，就可以破译他们的密码。

在军事、经济与政治斗争或竞争中，如果一方密码被对方破译，常常会招致败局或蒙受损失，为此各国政府或军事、经济集团千方百计做好保密工作，为了保护密码，甚至不惜牺牲生命。

现代京剧«红灯记»讲述了这样一个故事：上级为了保持和柏山游击队的联系，派交通员将一本密电码送给游击队，日本侵略军通过叛徒的口供，了解到这一情报，追查密电码，共产党员李玉和为了保护密电码，任凭敌人严刑拷打、百般折磨，坚强不屈，虽然壮烈牺牲，密电码最终还是安全地送到游击队手中。

为保证保密通信，历史上出现了多种加密方法。

最早使用的加密体制可能是凯撒密码体制。公元2世纪苏托尼厄斯写的«凯撒传»中，对罗马帝国凯撒大帝在«高卢战记»中所描述的送给被敌人围困的西塞罗的密信的加密方法作了详细的介绍。

凯撒密码的加密方法是取一个数k（1≤k≤25），然后将明文中的每个英文字母改用在它k位之后的那个字母代替，这样，明文就成了密文，其中k就是密钥。凯撒密码在公元9世纪被阿拉伯人找到破译方法，这在阿拉伯科学家阿尔·金迪«关于破译加密信息»的手稿中有详细的描述。

1586年，法国外交官维吉尼亚把凯撒密码做了另一种改进，增加密钥的长度，克服了凯撒密码的缺点，提高了密码的保密程度。二百年后，维吉尼亚密码被英国人巴比奇和德国人卡西斯基找到破译方法。由于英国情报机关的要求，巴比奇破译维吉尼亚密码的事一直到20世纪才公诸于众。直到一战结束，破译在与加密的角逐中占据上风。

加密体制在一战之后得到新的突破。利用电线通信技术中的移位寄存器，方便而快速地生成周期长度很大的二元周期序列，极大地增加了密钥的周期长度，再结合数学上的考虑，使密钥不仅周期长，而且具有数字平衡特性，增加破译的难度。这就是用M序列的流密码体制。

第二次世界大战期间，破译工作已取得惊人的成绩。欧美各国集聚了一批数学家从事破译工作。

1942年，英军和德军在北非展开激战，春夏之交，德国著名的“沙漠之狐”隆梅尔率领德国非洲军团横扫北非，英军一溃千里，6月退守阿拉曼，后来才守住阵地。8月，英国名将蒙哥马利出任英国非洲军司令，他率军反攻，同时，英军有效地切断了德军的补给线，几乎每支横穿地中海的德军补给船队都受到英国海空军的拦截。隆梅尔指挥德军进行了顽强的抵抗，终因补给不足、增援无望而败北。这一仗是非洲战争的转折点，从此盟军掌握了战场上的主动权。对阿拉曼战役，史家论述甚详，但其中的一个细节——英军何以能准确地拦截到几乎所有的德军补给船队？——却一直是个谜。直到20世纪70年代才露出谜底：当时数学家图灵领导的一个小组成功地破译了德军的密码！

破译工作最出色的是在美国，1942年美国破译了日本的“紫密”，但日本人长期不知此事，导致日本突袭中途岛海战失败。1943年4月美国破译了日本联合舰队长官山本五十六视察前线阵地的详细日程表，在4月18日派18架战斗机在预定的时间和地点打下山本的座机，成为密码史上精彩的一页。美国数学家申农在此期间建立了通信理论。

1976年，美国斯坦福大学年轻数学家狄菲和计算机专家海尔曼联名发表«密码学中的新方向»，突出奇招，创造了一种新型的加密体制，用这种方法制造的密码，即使公开密钥，任何人也无法破译。这是一个奇迹。第二年，美国麻省理工学院计算机科学实验室的Rivest，Shamir和Adleman三人联合设计了一个密钥方案，这就是著名的RSA方案。他们的编码方法，来自于古老的因数分解，这更是一个奇迹！(www.daowen.com)

公元前3世纪，希腊数学家欧几里德在«几何原本»中叙述了以下定理并且给出了证明：

每个大于1的整数都可惟一分解成有限个素数的乘积。

这叫算术基本定理，是初等数论的基石，是小学算术的基本问题之一。这个定理在理论上是很漂亮的，但是，要把一个相当大的数分解，看起来简单，做起来却不那么容易。现在普遍使用的方法，只能是用一个一个较小的素数去试除。一般来说，为分解整数N，需要试除次。当N很大时，人工分解是无能为力的，只能用计算机。用现在最好的计算机和算法，分解一个100位整数，所花的时间不到一小时，而分解一个200位整数，要用几万年。也就是说，用试除法分解一个200位数字，几乎是不可能的。另一方面，用计算机把两个100位数字相乘，是轻而易举的事。求积的容易与分解之困难给数学家以启示，可否利用这个矛盾编制密码，使我方编码轻而易举，对方破译难上加难，甚至完全不可能。RSA公钥方案就是基于算术基本定理和费马小定理的一种编码方案。

举一个例子来说明RSA公钥方案。

某女士公开了一个密钥，这个密钥是两个正整数N和e，其中N是一个比较大的数，比如是一个200位的数，e是一个较小的数。有一位先生想给这位女士发出一个信息。他可以将这个信息按照通行的编码方法译成一串数字，记为M。将M连乘e次，得到Me，然后用N去除，得到余数C。这位先生只要将C发送给女士就行了。

女士有一个自己掌握的秘密数字d，她将收到的C连乘d次，得到Cd，再除以N，得到余数，这个余数就是真实的信息M。她只需将M按通行的办法还原就得到了那位先生的准确信息。

女士的数字d是她根据N＝p·q精心选用的，d是她编码的惟一秘密，其他任何人都不知道。

d是这样选取的：女士先选好大的素数p和q，然后选取e和d，使ed－1是（p－1）（q－1）的倍数，而且使e与p－1、q－1没有公因数。于是

，k为整数。

别人为什么不能破译呢？其原因是N太大，任何人不能把N分解为p·q，当然无从知道d。

这样，你可以选两个数N和e，作为通讯密钥，像电话号码一样，对外公开。任何人只要查一下“电话本”，就可以向你发出密电，其他人无法破译。

从密码严格保密到公开密钥，这是古代算术在20世纪产生的伟大业绩。