02Chapter02-1

第2章密码学基础内容提要◎密码学的基本概念，加密类型，混合加密方法◎加密领域中两种主流加密技术：DES加密（DataEncryptionStandard）和RSA加密（Rivest-Shamir-Adleman）◎密码学应用，密码分析与攻击2.1密码学概述密码学是一门古老而深奥的学科，对一般人来说是非常陌生的。长期以来，只在很小的范围内使用，如军事、外交、情报等部门。计算机密码学是研究计算机信息加密、解密及其变换的科学，是数学和计算机的交叉学科，也是一门新兴的学科。随着计算机网络和计算机通信技术的发展，计算机密码学得到前所未有的重视并迅速普及和发展起来。2.1.1密码学的发展密码学的历史比较悠久，在四千年前，古埃及人就开始使用密码来保密传递消息。两千多年前，罗马国王JuliusCaesar（恺撒）就开始使用目前称为“恺撒密码”的密码系统。但是密码技术直到20世纪40年代以后才有重大突破和发展。特别是20世纪70年代后期，由于计算机、电子通信的广泛使用，现代密码学得到了空前的发展。密码学相关科学大致可以分为3个方面：密码学（Cryptology）是研究信息系统安全保密的科学，密码编码学（Cryptography）主要研究对信息进行编码，实现对信息的隐藏。密码分析学（Cryptanalytics）主要研究加密消息的破译或消息的伪造。密码学的发展大致经过3个阶段：第一阶段是1949年之前，密码学是一门艺术，这阶段的研究特点是：1.密码学还不是科学，而是艺术2.出现一些密码算法和加密设备3.密码算法的基本手段出现，主要针对字符4.简单的密码分析手段出现，数据的安全基于算法的保密。该阶段具有代表性的事件是：1883年Kerchoffs第一次明确的提出了编码的原则：加密算法应建立在算法的公开且不影响明文和密钥的安全的基础上。这个原则得到广泛承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。第二阶段是1949-1975年，密码学成为一门独立的科学，该阶段计算机的出现使基于复杂计算的密码成为可能。主要研究特点是：数据安全基于密钥而不是算法的保密。第三阶段是1976年以后，密码学中公钥密码学成为主要研究方向，该阶段具有代表性的事件是：1976年，Diffie和Hellman提出了不对称密钥。1977年，Rivest，Shamir和Adleman提出了RSA公钥算法。1977年，DES算法出现。80年代，出现IDEA和CAST等算法。90年代，对称密钥密码算法进一步成熟，Rijndael，RC6等出现，逐步出现椭圆曲线等其他公钥算法。2001年，Rijndael成为DES算法的替代者。2004年8月，山东大学信息安全所所长王小云在国际会议上首次宣布了她及她的研究小组对MD5、HAVAL-128、MD4和RIPEMD等四个著名密码算法的破译结果，引起世界轰动。这阶段的主要特点是：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能。2.1.2密码技术简介计算机网络的广泛应用，产生了大量的电子数据，这些电子数据需要传输到网络的许多地方。有意的计算机犯罪和无意的数据破坏对这些数据产生了很大的威胁。国家机密、企业经济信息、银行网上业务等中的任何差错都会使国家安全、企业经营受到巨大的损害。原则上来说对电子数据的攻击有两种形式。（1）被动攻击，即非法从传输信道上截取信息，或从存储载体上偷窃信息。（2）主动进攻，即对传输或存储的数据进行恶意的删除、修改等。虽然对这些行为已经建立相应的法律，但由于这种犯罪形式的特殊性，对于它的监督、甚至量刑都是很困难的。因此在不断完善相应法律和监督的同时，还需要加强自我保护，密码技术是一种有效而经济的方法。经典的密码学是关于加密和解密的理论，主要用于保密通信。目前，密码学已经得到了更加深入、广泛的发展，其内容已经不再是单一的加解密技术，已被有效、系统地用于保证电子数据的保密性、完整性和真实性。保密性就是对数据进行加密，使非法用户无法读懂数据信息，而合法用户可以应用密钥读取信息。完整性是对数据完整性的鉴别，以确定数据是否被非法篡改，保证合法用户得到正确、完整的信息。真实性是数据来源的真实性、数据本身真实性的鉴别，可以保证合法用户不被欺骗。现代密码技术的应用已经深入到数据处理过程的各个环节，包括：数据加密、密码分析、数字签名、信息鉴别、零知识认证、秘密共享等。密码学的数学工具也更加广泛，有概率统计、数论、代数、混沌和椭圆曲线等。常用密码学专业术语包括：消息和加密、鉴别、完整性和抗抵赖性、算法和密钥、对称算法和公开密钥算法（非对称算法），等等。2.1.3消息和加密遵循国际命名标准，加密和解密可以翻译成“Encipher”（译成密码）和“Decipher（解译密码）。也可以这样命名：“Encrypt”（加密）和“Decrypt”（解密）。消息被称为明文，用某种方法伪装消息以隐藏它的内容的过程称为加密，加了密的消息称为密文，而把密文转变为明文的过程称为解密。图2-1表明了加密和解密的过程。加密解密明文密文原始明文明文用M（Message，消息）或P（Plaintext，明文）表示，它可能是比特流、文本文件、位图、数字化的语音流或者数字化的视频图像等。密文用C（Cipher）表示，也是二进制数据，有时和M一样大，有时稍大。通过压缩和加密的结合，C有可能比P小些。加密函数E作用于M得到密文C，用数学公式表示为：E（M）=C。解密函数D作用于C产生M，用数据公式表示为：D（C）=M。先加密后再解密消息，原始的明文将恢复出来，D（E（M））=M必须成立。2.1.4鉴别、完整性和抗抵赖性除了提供机密性外，密码学需要提供三方面的功能：鉴别、完整性和抗抵赖性。这些功能是通过计算机进行社会交流至关重要的需求。（1）鉴别：消息的接收者应该能够确认消息的来源；入侵者不可能伪装成他人。（2）完整性：消息的接收者应该能够验证在传送过程中消息没有被修改；入侵者不可能用假消息代替合法消息。（3）抗抵赖性：发送消息者事后不可能虚假地否认他发送的消息。2.1.5算法和密钥密码算法也叫密码函数，是用于加密和解密的数学函数。通常情况下，有两个相关的函数：一个用做加密，另一个用做解密。如果算法本身是保密的，这种算法称为受限制的算法，受限制的算法具有历史意义。受限制的密码算法不可能进行质量控制或标准化，每个用户组织必须有他们自己的唯一的算法，这样的组织不可能采用流行的硬件或软件产品。但窃听者却可以买到这些流行产品并学习算法，进而破解密码。尽管有这些主要缺陷，受限制的算法对低密级的应用来说还是很流行的。现代密码学用密钥解决了这个问题，密钥用K表示。K可以是很多数值里的任意值，密钥K的可能值的范围叫做密钥空间。加密和解密运算都使用这个密钥，即运算都依赖于密钥，并用K作为下标表示，加解密函数表达为：EK（M）=CDK（C）=MDK（EK（M））=M加密、解密过程如图2-2所示。有些算法使用不同的加密密钥和解密密钥，也就是说加密密钥K1与相应的解密密钥K2不同，在这种情况下，加密和解密的函数表达式为：EK1（M）=CDK2（C）=M函数必须具有的特性是，DK2（EK1（M））=M，如图2-3所示。加密解密明文密文原始明文密钥密钥加密解密明文密文原始明文加密密钥解密密钥2.1.6对称算法基于密钥的算法通常有两类：对称算法和公开密钥算法。对称算法有时又称为传统密钥算法，加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加、解密的密钥是相同的。对称算法要求发送者和接收者在安全通信之前，协商一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加解密。对称算法的加密和解密表示为：EK（M）=CDK（C）=M对称算法可分为两类：序列算法和分组算法。一次只对明文中的单个比特或者字节进行运算的算法称为序列算法或序列密码。另一类算法是对明文的一组比特或者字节进行运算，称为分组算法或分组密码。现代计算机密码算法的典型分组长度为64位，这个长度已经足以防止被分析破译。2.1.7公开密钥算法公开密钥算法的加密的密钥和解密的密钥不同，而且解密密钥不能根据加密密钥计算出来，或者至少在可以计算的时间内不能计算出来。之所以叫做公开密钥算法，是因为加密密钥能够公开，即陌生者能用加密密钥加密信息，但只有用相应的解密密钥才能解密信息。加密密钥叫做公开密钥（简称公钥），解密密钥叫做私人密钥（简称私钥）。公开密钥K1加密表示为：EK1（M）=C。公开密钥和私人密钥是不同的，用相应的私人密钥K2解密可表示为：DK2（C）=M。2.2加密类型简介从古到今有无数种加密方法，但归类起来，古代主要是代替密码、置换密码以及两者的结合，计算机出现以后的现代密码则分为对称密码和非对称密码，以及分组密码和序列密码。2.2.1Scytale密码和恺撒密码最先有意识的使用一些技术的方法来加密信息的可能是公元前500年的古希腊人。他们使用的是一根叫scytale的棍子。送信人先绕棍子卷一张纸条，然后把要写的信息打纵写在上面，接着打开纸送给收信人。如果不知道棍子的粗细是不可能解密里面的内容的，如图2-4所示。公元前50年，著名的恺撒大帝发明了一种密码叫做恺撒密码。在恺撒密码中，每个字母都与其后第三位的字母对应，然后进行替换，比如“a”对应于“d”，“b”对应于“e”，以此类推。如果到了字母表的末尾，就回到开始，例如“z”对应于“c”，“y”对应于“b”，“x”对应于“a”，如此形成一个循环。当时罗马的军队就用恺撒密码进行通信。恺撒密码明文字母表：ABCDEFG……XYZ恺撒密码密文字母表：DEFGHIJ……ABC于是就可以从明文得到密文：比如：明文为“veni，vidi，vici”得到的密文“YHAL，YLGL，YLFL”，意思是“我来，我见，我征服”，曾经是恺撒征服本都王法那西斯后向罗马元老院宣告的名言。26个字符代表字母表的26个字母，从一般意义上说，也可以使用其它字符表，一一对应的数字也不一定要是3，可以选其它数字。2.2.2代替密码和置换密码从古代密码出现一直到现代计算机诞生，在这19个世纪中，密码学是由基于字符的密码算法构成的。不同的密码算法是字符之间互相代替或者是互相之间换位，好的密码算法是结合这两种方法，每次进行多次计算。代替密码（SubstitutionCipher)是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。置换密码(PermutationCipher)又称换位密码（TranspositionCipher)，加密过程中明文的字母保持相同，但顺序被打乱了。1、代替密码在经典密码学中，有4种类型的代替密码：（1）简单代替密码（SimpleSubstitutionCipher)，又称单字母密码（MonoalphabeticCipher)。明文的一个字符用相应的一个密文字符代替。恺撒密码就是一种简单的代替密码，它的每一个明文字母都由其右边第三个字母代替。ROT13是建立在UNIX系统上的简单的加密程序，它也是简单代替密码。在这种密码中A被N代替，B被O代替，等等，每个字母是环移13所对应的字母。用ROT13加密文件两遍便恢复出原始的文件：P=ROT13（ROT13（P））简单代替密码很容易破解，因为它没有把明文的不同字母的出现频率掩盖起来。代替密码（2）多名码代替密码（HomophonicSubstitution）：它与简单代替密码相似，只是映射是一对多的，每个明文字母可以加密成多个密文字母。例如，A可能对应于5、13、25B可能对应于7、9、31、42当对字母的赋值个数与字母出现频率成比例时，安全性将有所提高。这是因为密文符号的相关分布会近似于平的，可以挫败频率分析。1401年DuchyMantua公司就开始使用多名码代替密码，比简单代替密码难破译，但仍不能掩盖明文语言的所有统计特性，用已知明文攻击，较容易破解，但用唯密文攻击要困难一些。（3）多字母代替密码（PloygramCipher)：字符块被成