简单密码体制及分析

总目录第1章简单密码体制及分析第2章分组密码第3章香农理论第4章序列密码和移位寄存器第5章RSA公钥密码体制第6章其它公钥密码体制第7章数字签名第1章简单密码体制及分析1.1密码学的基本概念1.2一些简单密码体制与它的破译密码学既属于计算机科学,也可算是应用数学,更确切地说,它是二者之间的边缘学科,数学无疑是其重要的工具.计算机的出现和广泛普及,使人类社会步入信息化时代,也使安全保密研究揭掉了神秘的面纱,成为大家感兴趣并能为更多人服务的科学.信息在社会中的地位和作用越来越重要，已成为社会发展的重要战略资源.1.1密码学的基本概念1.引言信息安全所面临的威胁来自很多方面，并且随着时间的变化而变化。这些威胁可以宏观地分为人为威胁和自然威胁。自然威胁可能来自于各种自然灾害、恶劣的场地环境、电磁辐射和电磁干扰、网络设备自然老化等。这些事件有时会直接威胁信息的安全，影响信息的存储媒质。我们主要讨论人为威胁，也就是对信息的人为攻击。这些攻击手段都是通过寻找系统的弱点，以便达到破坏、欺骗、窃取数据等目的，造成经济上和政治上不可估量的损失。根据美国FBI的调查,美国每年因为网络安全造成的经济损失超过1.70亿美元.面对如此严重危害计算机数据安全的种种威胁,必须采取措施确保计算机数据的安全保密.确保数据安全就是采取措施免受未授权的泄露、篡改和毁坏，主要包括数据秘密性、真实性和完整性。要确保计算机数据的安全保密，必须综合采取各种措施才能奏效，除法律、行政、教育等措施外，最重要的是要采取技术保护措施。技术措施可分为访问控制技术和密码技术两大类。我们主要讨论密码技术.密码学的发展历程第一次世界大战前，密码学重要的进展很少出现在公开文献中1918年，20世纪最有影响的分析文章，重合指数及其在密码学中的应用问世1949年，Shanon发表了题为“保密系统的通信理论”1949—1967密码学文献很少1976年，W.Diffie,M.Hellman提出了公开密钥密码1977年，美国联邦政府正式颁布DES1977年—至今，公开的密码学研究爆炸性的增长2.密码学的基本概念通信双方采用保密通信系统保护需要发送的消息，使未授权者不能提取信息。发送方将要发送的消息称为明文，明文被变换成看似无意义的随机消息，称为密文，这种变换过程称为加密；其逆过程，即由密文恢复出原明文的过程称为解密。对明文进行加密操作的人员称为加密员或密码员。密码员对明文进行加密时所采用的一组规则称为加密算法。传送消息的预定对象称为接收者，接收者对密文进行解密时所采用的一组规则称为解密算法。加密和解密算法的操作通常都是在一组密钥控制下进行的，分别称为加密密钥和解密密钥。传统密码体制所用的加密密钥和解密密钥相同，或实质上等同，即从一个易于得出另一个，称其为单钥或对称密码体制。若加密密钥和解密密钥不相同，从一个难于推出另一个，则称为双钥或非对称密码体制。密钥是密码体制安全保密的关键，它的产生和管理是密码学中的重要研究课题。在信息传输和处理系统中，除了预定的接收者外，还有非授权者，他们通过各种办法（如搭线窃听、电磁窃听、声音窃听等）来窃取机密信息，称其为截收者。截收者虽然不知道系统所用的密钥，但通过分析可能从截获的密文推断出原来的明文或密钥，这一过程称为密码分析，从事这一工作的人员称为密码分析员，研究如何从密文推演出明文、密钥或解密算法的学问称为密码分析学。对一个保密通信系统采取截获密文进行分析的这类攻击称为被动攻击。现代信息系统还可能遭受的另一类攻击是主动攻击，非法入侵者、攻击者或黑客主动向系统采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利己害人的目的。这是现代信息系统中更为棘手的问题。一个密码系统，它由以下几部分组成：明文消息空间M，密文消息空间C，密钥空间K，在单钥体制下，此时密钥ke=kd∈K需经安全的密钥信道由发送方传给接收方；加密变换Eke：M→C，其中ke∈K，由加密器完成；解密变换Dkd：C→M，由解密器实现。称(M,C,K,EKe,DKd)为密码系统。对于给定明文消息m∈M，密钥ke∈K，加密变换将明文m变换为密文c，即c=f(m,ke)=Eke(m)m∈M,ke∈K接收方利用通过安全信道送来的密钥k（k∈K，单钥体制下）或用本地密钥发生器产生的解密密钥kd（双钥体制下）控制解密操作D，对收到的密文进行变换得到明文消息，即：m=Dkd(c)m∈M,kd∈K而密码分析者，则用其选定的变换函数h，对截获的密文c进行变换，得到的明文是明文空间中的某个元素,即m′=h(c)一般m′≠m。如果m′=m，则分析成功。密码系统模型为了保护信息的保密性，抗击密码分析,密码系统应当满足下述要求：①系统即使达不到理论上是不可破的，也应当为实际上不可破的。就是说，从截获的密文或某些已知的明文密文对，要决定密钥或任意明文在计算上是不可行的。②系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。③加密和解密算法适用于所有密钥空间中的元素。④系统便于实现和使用。15密码学分类：密码编制学和密码分析学密码系统的组成：（1）明文空间M；（2）密文空间C；（3）密钥空间K，对任意k∈K，k=（kd，ke）；（4)加密算法E，C=E（M，ke）；（5）解密算法D，M=D（C，kd）。一个密码系统包含明文字母空间、密文字母空间、密钥空间和算法。密码系统的两个基本单元是算法和密钥。密码系统的两个基本单元中，算法是相对稳定的，视为常量；密钥则是不固定的，视为变量。为了密码系统的安全，频繁更换密钥是必要的。一般来说算法是公开的，真正需要保密的是密钥。因此在密钥的分发和存储时应当特别小心。密码体制根据密钥可划分为两大类，即单钥体制和双钥体制。密码体制分类单钥体制的加密密钥和解密密钥相同。采用单钥体制的系统的保密性主要取决于密钥的保密性，与算法的保密性无关，即由密文和加解密算法不可能得到明文。换句话说，算法无需保密，需保密的仅是密钥。密钥可由发送方产生然后再经一个安全可靠的途径（如信使递送）送至接收方，或由第三方产生后安全可靠地分配给通信双方。如何产生满足保密要求的密钥以及如何将密钥安全可靠地分配给通信双方是这类体制设计和实现的主要课题。密钥产生、分配、存储、销毁等问题，统称为密钥管理。这是影响系统安全的关键因素，即使密码算法再好，若密钥管理问题处理不好，就很难保证系统的安全保密。双钥体制是由Diffie和Hellman于1976年首先引入的。采用双钥体制的每个用户都有一对选定的密钥：一个是可以公开的，可以像电话号码一样进行注册公布；另一个则是秘密的。因此双钥体制又称为公钥体制。双钥密码体制的主要特点是将加密密钥和解密密钥分开，因而可以实现多个用户加密的消息只能由一个用户解读，或由一个用户加密的消息而使多个用户可以解读。前者可用于公共网络中实现保密通信，而后者可用于实现对用户的认证。根据对明文的划分与密钥的使用方法不同,可将密码体制分为两种方式：一是明文消息按字符（如二元数字）逐位地加密，称之为流密码或序列密码；另一种是将明文消息分组（含有多个字符），逐组地进行加密，称之为分组密码。nikmEcnikmEceiiiii1),,(1),,(密码体制一般可分为传统密码序列密码、分组密码、公钥密码、量子密码体制。广泛应用于军事、商业经济、网络间的通信等领域，涉及了数学、物理、计算机科学、电子学、系统工程、语言学等学科内容。密码分析者攻击密码的方法主要有以下三种穷举攻击统计分析攻击数学分析攻击密码编制与密码分析示意图MM=DAB（C）明文C=EAB(M)密文明文密钥KAB密钥KAB密码分析员发送方A接收方B密码系统的攻击类型的划分是由攻击者可获取的信息量决定。其中，最困难的攻击类型是唯密文攻击，这种攻击的手段一般是穷搜索法，即对截获的密文依次用所有可能的密钥试译，直到得到有意义的明文。只要有足够多的计算时间和存储空间，原则上穷举攻击总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。敌手因此还需对密文进行统计分析，为此需要知道被加密的明文的类型，比如英文文本、法文根据密码分析者可利用的数据来分类文本、MD-DOS执行文件等。唯密文攻击时，敌手知道的信息量最少，因此最易抵抗。然而，很多情况下，敌手可能有更多的信息，也许能截获一个或多个明文及其对应的密文，也许知道消息中将出现的某种明文格式。例如ps格式文件开始位置的格式总是相同的，电子资金传送消息总有一个标准的报头或标题。这时的攻击称为已知明文攻击，敌手也许能够从已知的明文被变换成密文的方式得到密钥。根据密码分析者可利用的数据来分类，破译密码的类型分为三种仅知密文攻击已知明文攻击：计算机程序易受这种攻击选择明文攻击：计算机文件系统和数据库易受这种攻击攻击类型分类人为攻击可分为被动攻击和主动攻击被动攻击----即窃听，是对系统的保密性进行攻击，如搭线窃听、对文件或程序的非法拷贝等，以获取他人的信息。被动攻击又分为两类，一类是获取消息的内容，很容易理解；第二类是进行业务流分析，假如我们通过某种手段，比如加密，使得攻击者从截获的消息无法得到消息的真实内容，然而敌手却有可能获得消息的格式、确定通信双方的位置和身份以及通信的次数和消息的长度，这些信息可能对通信双方来说是敏感的。被动攻击因不对消息做任何修改，因而是难以检测的，所以抗击这种攻击的重点在于预防而非检测。主动攻击这种攻击包括对数据流的某些篡改或产生某些假的数据流。主动攻击又可分为以下三个子类：①中断：是对系统的可用性进行攻击，如破坏计算机硬件、网络或文件管理系统。②篡改：是对系统的完整性进行攻击，如修改数据文件中的数据、替换某一程序使其执行不同的功能、修改网络中传送的消息内容等。③伪造：是对系统的真实性进行攻击。如在网络中插入伪造的消息或在文件中插入伪造的记录。绝对防止主动攻击是十分困难的，因为需要随时随地对通信设备和通信线路进行物理保护，因此抗击主动攻击的主要途径是检测，以及对此攻击造成的破坏进行恢复。1.2一些简单密码体制与它的破译1.置换密码—把明文中的字母重新排列，字母本身不变例：明文为thiscryptosystemisnotsecure。排成矩阵：thiscryptosystemisnotsecure密文为tysnuhptoritetesomscsierysc。2.单表代替密码首先构造一个密文字母表，然后用密文字母表中的字母或字母组来代替明文字母表中的字母或字母组，各字母或字母组的相对位置不变，但其本身改变了。设A={a0，a1，…，an-1}为含n个字母的明文字母表，B={b0，b1，…，bn-1}为含n个字母的密文字母表，定义一个由A到B的一一映射。f：A→B，f（ai）=bi设明文M=（m0，m1，…，mn-1），则相应的密文C=（f（m0），f（m1），…，f（mn-1））1.因子设a，b(b≠0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，且称b是a的因子。数论简介整数具有以下性质：①a|1，那么a=±1。②a|b且b|a，则a=±b。③对任一b(b≠0)，b|0。④b|g，b|h，则对任意整数m、n有b|(mg+nh)。这里只给出④的证明，其他3个性质的证明都很简单。性质④的证明：由b|g，b|h知，存在整数g1、h1，使得g=bg1,h=bh1所以mg+nh=mbg1+nbh1=b(mg1+nh1),因此b|(mg+nh)。2.素数称整数p(p1)是素数，如果p的因子只有±1，±p。任一整数a(a1)都能惟一地分解为以下形式：其中p1p2…pt是素数，ai0(i=1,…,t)。例如91=7×11，11011=7×112×131212ttappp这一性质称为整数分解的惟一性，也可如下陈述：设P是所有素数集合，则任意整数a(a1)都能惟一地写成以下形式：其中ap≥0,等号右边的乘积项取所有的素数，然而大多指数项ap为0。相应地，任一正整数也可由非0指数