密码的加密与破译.doc

密码的加密与破译 密码学是在编码与破译的斗争实践中逐步发展起来的，并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、信息论、计算机科学等有着广泛而密切的联系。它的现实研究成果，特别是各国政府现用的密码编制及破译手段都具有高度的机密性。中国古代秘密通信的手段，已有一些近于密码的雏形。宋曾公亮、丁度等编撰武经总要“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密本体制的特点。 1871年，由上海大北水线电报公司选用6899个汉字，代以四码数字，成为中国最初的商用明码本，同时也设计了由明码本改编为密本及进行加乱的方法。在此基础上，逐步发展为各种比较复杂的密码。 在欧洲，公元前405年，斯巴达的将领莱杉德使用了原始的错乱密码；公元前一世纪，古罗马皇帝凯撒曾使用有序的单表代替密码；之后逐步发展为密本、多表代替及加乱等各种密码体制。 二十世纪初，产生了最初的可以实用的机械式和电动式密码机，同时出现了商业密码机公司和市场。60年代后，电子密码机得到较快的发展和广泛的应用，使密码的发展进入了一个新的阶段。 密码破译是随着密码的使用而逐步产生和发展的。1412年，波斯人卡勒卡尚迪所编的百科全书中载有破译简单代替密码的方法。到16世纪末期，欧洲一些国家设有专职的破译人员，以破译截获的密信。密码破译技术有了相当的发展。1863年普鲁士人卡西斯基所著密码和破译技术，以及1883年法国人克尔克霍夫所著军事密码学等著作，都对密码学的理论和方法做过一些论述和探讨。1949年美国人香农发表了秘密体制的通信理论一文，应用信息论的原理分析了密码学中的一些基本问题。 自19世纪以来，由于电报特别是无线电报的广泛使用，为密码通信和第三者的截收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分激烈的隐蔽战线。 1917年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942年，美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，从而能以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。在保卫英伦三岛和其他许多著名的历史事件中，密码破译的成功都起到了极其重要的作用，这些事例也从反面说明了密码保密的重要地位和意义。 我国明确规定严格禁止直接使用国外的密码算法和安全产品，这主要有两个原因：一是国外禁止出口密码算法和产品，所谓出口的安全的密码算法国外都有破译手段，二是恐怕国外的算法和产品中存在“后门”，关键时刻危害我国安全。当今世界各主要国家的政府都十分重视密码工作，有的设立庞大机构，拨出巨额经费，集中数以万计的专家和科技人员，投入大量高速的电子计算机和其他先进设备进行工作。与此同时，各民间企业和学术界也对密码日益重视，不少数学家、计算机学家和其他有关学科的专家也投身于密码学的研究行列，更加速了密码学的发展。 3.3 RSA体制的数学基础定理1（Fermat定理）如果是一个素数，则必有，对任何整数（10.1） 或 ，对任何整数 （10.2）证明：命题（10.1）与（10.2）的等价性是明显的，我们只要证等式（10.2）就可以了。因为对任何整数总有 （10.3）以下我们用归纳法证（10.3） 当时，（10.2）显然成立。因为这时由（10.3）式可得如我们假定当时命题成立，证当时命题成立，因为由（10.3）式可得其中第一个等式由（10.3）式得到，而第二个等式由归纳法假定可得，所以定理得证。定义3 记为小于整数且与互素的整数个数，这时称为欧拉函数。定理2 如果，且是两个不同的素数，那么 证明 记为集合的两个子集，且分别是的倍数，这时有 ，其中表示集合的元素个数，而表示数的整数部分。这时有 因此有 而 其中分别表示集合的余集，故定理得证。定理3 如果，且是两个素数，那么 证明 由定理1可得，对任何整数有 ，这时 因此是的倍数，也就是有 。定理得证以下记，其中是变数，因此这是函数是易计算的。定理4 如果，且是两个不同的素数，而满足方程式 那么是上的1-1变换，且互为逆变换。 证明 由的定义可知，总有一个整数存在，使成立。这时由定理3可得 此即它们互为逆函数，因为 关于函数的1-1性由以下讨论可得。如果，那么必有，否则，成立，那么必有，这与的定义矛盾，定理得证。3.4 RSA数字签名 数字签名的目的是使接收者能够确证发送者的签名，但不能伪造;发送者发出签了名的消息给接收者后就不能否认他所签发的消息，一旦收发双方就消息内容与来源发生争执时，应能给仲裁者提供发送者对所发消息签了名的证据。政治、军事、外交等活动中签署文件，商业上签定契约和合同以及日常生活中在书信、从银行取款等事务中的签字，传统上都采用手写签名或印鉴。签名起到认证、核准和生效作用。随着信息时代的来临，人们希望通过数字通信网络进行迅速的、远距离的贸易合同的签名，数字或电子签名法应运而生，并开始用于商业通信系统，诸如电子邮递、电子转帐、办公室自动化等系统中。发送者A用其秘密密钥对信息进行加密运算，得到，再用B的公开密钥做加密运算得到，然后将其传送给接收者B；B先用自己的秘密密钥进行解密运算，得到，再用A的公开加密密钥做加密运算恢复出明文。在此过程中，因为除A外没有别人能具有A的解密密钥，所以除A外没有别人能产生密文，这样，信息就被签名了。若A要抵赖