密码的加密与破译

密码的加密与破译
密码学是在编码与破译的斗争实践中逐步发展起来的，并随着先进科学技术
的应用，已成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、
信息论、计算机科学等有着广泛而密切的联系。它的现实研究成果，特别是各国
政府现用的密码编制及破译手段都具有高度的机密性。
中国古代秘密通信的手段，已有一些近于密码的雏形。宋曾公亮、丁度等编
撰《武经总要》“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉
字，分别代表40种情况或要求，这种方式已具有了密本体制的特点。
1871年，由上海大北水线电报公司选用6899个汉字，代以四码数字，成为中
国最初的商用明码本，同时也设计了由明码本改编为密本及进行加乱的方法。在
此基础上，逐步发展为各种比较复杂的密码。
在欧洲，公元前405年，斯巴达的将领莱杉德使用了原始的错乱密码；公元
前一世纪，古罗马皇帝凯撒曾使用有序的单表代替密码；之后逐步发展为密本、
多表代替及加乱等各种密码体制。

二十世纪初，产生了最初的可以实用的机械式和电动式密码机，同时出现了商
业密码机公司和市场。60年代后，电子密码机得到较快的发展和广泛的应用，
使密码的发展进入了一个新的阶段。
密码破译是随着密码的使用而逐步产生和发展的。1412年，波斯人卡勒卡尚
迪所编的百科全书中载有破译简单代替密码的方法。到16世纪末期，欧洲一些
国家设有专职的破译人员，以破译截获的密信。密码破译技术有了相当的发展。
1863年普鲁士人卡西斯基所著《密码和破译技术》，以及1883年法国人克尔克
霍夫所著《军事密码学》等著作，都对密码学的理论和方法做过一些论述和探讨。
1949年美国人香农发表了《秘密体制的通信理论》一文，应用信息论的原理分
析了密码学中的一些基本问题。
自19世纪以来，由于电报特别是无线电报的广泛使用，为密码通信和第三者
的截收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分激烈
的隐蔽战线。
1917年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942
年，美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，
从而能以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。在保卫英伦
三岛和其他许多著名的历史事件中，密码破译的成功都起到了极其重要的作用，
这些事例也从反面说明了密码保密的重要地位和意义。
我国明确规定严格禁止直接使用国外的密码算法和安全产品，这主要有两个
原因：一是国外禁止出口密码算法和产品，所谓出口的安全的密码算法国外都有
破译手段，二是恐怕国外的算法和产品中存在“后门”，关键时刻危害我国安全。
当今世界各主要国家的政府都十分重视密码工作，有的设立庞大机构，拨出
巨额经费，集中数以万计的专家和科技人员，投入大量高速的电子计算机和其他
先进设备进行工作。与此同时，各民间企业和学术界也对密码日益重视，不少数
学家、计算机学家和其他有关学科的专家也投身于密码学的研究行列，更加速了
密码学的发展。

3.3 RSA体制的数学基础
定理1（Fermat定理）如果p是一个素数，则必有11(mod)pxp，对任何
整数0x（10.1） 或 (mod)pxxp，对任何整数x （10.2）
证明：命题（10.1）与（10.2）的等价性是明显的，我们只要证等式（10.2）
就可以了。因为对任何整数x总有

0(11)(1)(1)1(mod)ppppipiixxCxxp


（10.3）

以下我们用归纳法证（10.3）
当2x时，（10.2）显然成立。因为这时由（10.3）式可得

2(21)1112(mod)ppp

如我们假定当1xy时命题成立，证当xy时命题成立，因为由
（10.3）式可得
(1)111(mod)ppyyyyp
其中第一个等式由（10.3）式得到，而第二个等式由归纳法假定可得，
所以定理得证。

定义3 记()n为小于整数n且与n互素的整数个数，这时称()n为欧拉函
数。
定理2 如果npq，且,pq是两个不同的素数，那么()(1)(1)npq

证明 记,EF为集合{1,2,...,1}n的两个子集，且分别是,pq的倍数，这

时有11nEqp ，11nFpq，其中E表示集合E的元素个

数，而A表示数A的整数部分。这时有
10nEFpq








因此有 21(1)(1)EFEFpqnpq
而 ()()cccnEFEF
1(1)(1)nEFpq
其中,ccEF分别表示集合,EF的余集，故定理得证。
定理3 如果npq，且,pq是两个素数，那么()1(mod)nxn
证明 由定理1可得，对任何整数0x有
11(mod)pxp，11(mod)qxq


这时 ()(1)(1)1(mod,mod)npqyxxpq
因此1y是pq的倍数，也就是有 1(mod)1(mod)ypqn。定理得
证
以下记,()(mod)eenExxn，其中e是变数，因此这是函数是易计算的。

定理4 如果npq，且,pq是两个不同的素数，而,ed满足方程式
1(mod())edn
那么,,(),()endnExEx是nZ上的1-1变换，且互为逆变换。
证明 由,ed的定义可知，总有一个整数r存在，使1()edrn成立。
这时由定理3可得 1()(mod)deededrnxxxxxn
此即它们互为逆函数，因为 ,,,,()()(mod)endndnenEExEExxn
关于,,(),()endnExEx函数的1-1性由以下讨论可得。如果(mod)xxn，
那么必有(mod)eexxn，否则，(mod)eexxn成立，那么必有


(mod)ddeexxxxn


，这与(mod)xxn的定义矛盾，定理得证。

3.4 RSA数字签名
数字签名的目的是使接收者能够确证发送者的签名，但不能伪造;发送者
发出签了名的消息给接收者后就不能否认他所签发的消息，一旦收发双方就
消息内容与来源发生争执时，应能给仲裁者提供发送者对所发消息签了名的
证据。
政治、军事、外交等活动中签署文件，商业上签定契约和合同以及日常
生活中在书信、从银行取款等事务中的签字，传统上都采用手写签名或印鉴。
签名起到认证、核准和生效作用。随着信息时代的来临，人们希望通过数字
通信网络进行迅速的、远距离的贸易合同的签名，数字或电子签名法应运而
生，并开始用于商业通信系统，诸如电子邮递、电子转帐、办公室自动化等
系统中。

发送者A用其秘密密钥KAS对信息M进行加密运算，得到()KADSM，再

用B的公开密钥KBP做加密运算得到(())KBKAEPDSM，然后将其传送给接收
者B；B先用自己的秘密密钥KBS进行解密运算，得到()KADSM，再用A的
公开加密密钥KAP做加密运算恢复出明文(())KAKAEPDSMM。在此过程中，
因为除A外没有别人能具有A的解密密钥KAS，所以除A外没有别人能产生
密文()KADSM，这样，信息M就被签名了。若A要抵赖曾发送信息M给B，
B可将M及()KADSM出示给公证机关，公证机关很容易用KAP去证实A确实
发送消息M给B。反之，如果B将M伪造成M，则B不能在第三者面前
出示()KADSM，这样就证明B伪造了M。因此，用RSA算法实现数字签名，
操作简便，且可实现对信息的加密和信息来源的鉴别。