信息加密与鉴别

第四章信息加密与鉴别内容提要本章介绍密码学的基本概念。介绍加密领域中两种主流的加密技术：DES加密（DataEncryptionStandard）RSA加密（Rivest-Shamir-Adleman）并用程序实现这两种加密技术的算法。最后介绍目前常用的加密工具PGP（PrettyGoodPrivacy），使用PGP产生密钥，加密文件和邮件。4.1信息加密基础

4.1.1信息加密的发展1、密码学概述密码学是一门古老而深奥的学科，对一般人来说是非常陌生的。长期以来，只在很小的范围内使用，如军事、外交、情报等部门。计算机密码学是研究计算机信息加密、解密及其变换的科学，是数学和计算机的交叉学科，也是一门新兴的学科。密码技术简介密码学的历史比较悠久，在四千年前，古埃及人就开始使用密码来保密传递消息。两千多年前，罗马国王JuliusCaesare（恺撒）就开始使用目前称为“恺撒密码”的密码系统。但是密码技术直到本20世纪40年代以后才有重大突破和发展。特别是20世纪70年代后期，由于计算机、电子通信的广泛使用，现代密码学得到了空前的发展。中途岛之战中途岛，陆地面积约5.2平方公里，有三条交叉的飞机跑道。该岛距美国旧金山和日本横宾均相距2800海里，处于亚洲和北美之间的太平洋航线的中途，故名中途岛。

中途岛海战日本海军联合舰队司令山本五十六日本海军苍龙和飞龙号航空母舰美舰载40毫米高炮向来袭日机猛烈开火美国海军上将尼米兹约瑟夫·罗谢福特少校，美国密码专家，1940年，他帮助破解了日本海军的通讯密码JN-25，1942年中途岛战役前破译日军攻击目标。

1942年6月，中途岛之战，美国军队和日本帝国海军作战的场面。中途岛海战中美、日损失比较

类别国家航空母舰飞机(架)人员(人)日本4赤城、加贺、苍龙、飞龙3222000美国1约克顿号147307偷袭珍珠港：

1941年12月7日清晨，日本皇家海军的飞机和微型潜艇突然袭击美国海军基地珍珠港以及美国陆军和海军在夏威夷欧胡岛上的飞机场的事件。这次袭击最终将美国卷入第二次世界大战。2、基本概念（1）消息和加密遵循国际命名标准，加密和解密可以翻译成：“Encipher（译成密码）”和“（Decipher）（解译密码）”。也可以这样命名：“Encrypt（加密）”和“Decrypt（解密）”。消息被称为明文。用某种方法伪装消息以隐藏它的内容的过程称为加密，加了密的消息称为密文，而把密文转变为明文的过程称为解密，图表明了加密和解密的过程。明文密文明文用M（Message，消息）或P（Plaintext，明文）表示，它可能是比特流、文本文件、位图、数字化的语音流或者数字化的视频图像等。密文用C（Cipher）表示，也是二进制数据。加密函数E作用于M得到密文C：E（M）=C。解密函数D作用于C产生明文M，D（C）=M。先加密后再解密消息，原始的明文将恢复出来：D（E（M））=M必须成立。鉴别、完整性和抗抵赖性

除了提供机密性外，密码学需要提供三方面的功能：鉴别、完整性和抗抵赖性。鉴别：消息的接收者应该能够确认消息的来源；入侵者不可能伪装成他人。完整性：消息的接收者应该能够验证在传送过程中消息没有被修改；入侵者不可能用假消息代替合法消息。抗抵赖性：发送消息者事后不可能虚假地否认他发送的消息。（2）算法和密钥

密钥用K表示。密钥K的可能值的范围叫做密钥空间。加密和解密运算都使用这个密钥，即运算都依赖于密钥，并用K作为下标表示，加解密函数表达为：EK（M）=CDK（C）=MDK（EK（M））=M，如图所示。有些算法使用不同的加密密钥和解密密钥，也就是说加密密钥K1与相应的解密密钥K2不同，在这种情况下，加密和解密的函数表达式为：EK1（M）=CDK2（C）=M函数必须具有的特性是，DK2（EK1（M））=M，如图所示。4.2传统加密技术4.2.1替代密码概述替代密码是通过密钥字母表用一组密文字母来代替一组明文字母以隐藏明文，但保持明文字母的位置不变。如果密钥字母表由一个字母表构成替代密码，称为单表替代密码，如果由多个字母表构成替代密码，称为多表替代密码。替代密码单表替代密码多表替代密码20世纪早期密码机1、单表替代密码单表替代密码的代表是凯撒密码，又叫循环移位密码。其加密方法是把明文中的所有字母都用它右边的第k个字母替代，并认为Z后面又是A。其映射关系函数为：F(a)=(a+k)modna—明文字母；n—字符集字母个数；k—密钥ABCDEF…VWXYZ（k=3）DEFGHI…YZABC1、单表替代密码单表替代密码的优点：密钥简单、易记；单表替代密码的缺点：这种密码是很容易破译的，因为最多只需尝试25次即可轻松破译密码。凯撒密码的优点是密钥简单易记。但它的密码文与明码文的对应关系过于简单，故安全性很差2、多表替代密码周期替代密码是一种常用的多表替代密码，又叫维吉尼亚密码。其加密表是以字母表移位为基础把26个英文字母进行循环移位，排列在一起，形成26*26方阵，称为维吉尼亚表。ABCDEFGHIJKLMNOPQRSTUV…ZAB…ZABCDEFGHIJKLMNOPQRSTUV…ZBCDEFGHIJKLMNOPQRSTUVW…A…………..ZABCDEFGHIJKLMNOPQRSTU…Y2、多表替代密码周期替代密码在实际使用时，往往把某个容易记忆的词或词组当作密钥，然后把密钥反复写在明文下方或上方。加密时，以明文字母选择列，以密钥字母选择行，两者的交点就是加密生成的密文字母；解密时做逆操作即可。重点难点：多表替代密码周期多表密码，每张表=caesar密码密钥不断重复密钥字母决定移位的次数假设密钥为deceptive：key:decep

tivedecept

ived

eceptiveplaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJVigenère密码3.换位密码（1）换位密码概述（2）列换位法（3）矩阵换位法维吉尼亚密码的破解维吉尼亚密码(VigenereCipher)对字频信息的隐藏还不够彻底。在19世纪50年代,英国人查尔斯-巴贝奇对其的破解.其实其破解的基本思想如下:

比如在密文中,经常出现了同一个子串(比如UPK),而且每个字串之间的距离都是3的整数倍.那么解密者就很容易推测出秘匙的长度为3.其原因也是十分简单的:

当秘匙在重复了N次之后,其还是用第一个字母去加密UPK相应的明文.尤其是对THE,YOU,WHAT这类高频词汇当使用了弱秘匙的话,更容易遭受破解.换位密码概述换位密码是采用移位法进行加密的。它把明文中的字母重新排列，本身不变，但位置变了。换位密码是靠重新安排字母的次序，而不是隐藏他们。换位加密方法有列换位法和矩阵换位法等。换位密码……列换位法矩阵换位法1、列换位法列换位法是将明文字符分割成若干个（例如3个）一列的分组，并按一组后面跟着另一组的形式排好，不全的组用不常用的字符填满。最后取各列来产生密文。密钥为组中字符的个数。明文分组换位C1C2C3C4C5C6C7C8C9……C1C2C3C4C5C6C7C8C9……C1C2C3C4C5C6C7C8C9……C1C4C7…C2C5C8…C3C6C9…C1C4C7…C2C5C8…C3C6C9…C1C4C7…C2C5C8…C3C6C9…密文加密案例列换位法将明文字符分割成为五个一列的分组并按一组后面跟着另一组的形式排好。如明文是：

WHATYOUCANLEARNFROMTHISBOOK

分组排列为：WHATYOUCANLEARNFROMTHISBOOKXXX密文为：WOLFHOHUERIKACAOSXTARMBXYNNTOX2、矩阵换位法矩阵换位法是将明文字符按给定的顺序排列在一矩阵中，然后用另一种顺序选出矩阵的字母来产生密文。密钥为矩阵的行数、列数以及给定的置换矩阵。明文矩阵换位C1C2C3C4C5C6C7C8C9……C1C2C3C4C5C6C7C8C9……C1C2C3C4C5C6C7C8C9……C1C4C7…C2C5C8…C3C6C9…密文C1C4C7…C2C5C8…C3C6C9…C3C1C2C6C4C5C9C7C8………C3C1C2C6C4C5C9C7C8…….C3C1C2C6C4C5C9C7C8…….4.3对称算法基于密钥的算法通常有两类：对称算法和公开密钥算法（非对称算法）。对称算法有时又叫传统密码算法，加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加解密的密钥是相同的。对称算法要求发送者和接收者在安全通信之前，协商一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加解密。对称算法的加密和解密表示为：EK（M）=CDK（C）=M4.3.1DES对称加密技术DES(DataEncryptionStandard)算法发明人：IBM公司W.Tuchman和C.Meyer.基础：1967年美国HorstFeistel提出的理论；产生：美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准，于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告，最终选定DES。2、DES算法的原理

DES算法的入口参数有三个：Key、Data、Mode。其中：Key为8个字节共64位，是DES算法的工作密钥；Data也为8个字节64位，是要被加密或被解密的数据；Mode为DES的工作方式有两种：加密或解密。3、DES算法的实现步骤

输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特DES算法一般描述

64bitsplaintext56bitskey初始置换IP第1轮置换选择1循环左移置换选择2K1第2轮置换选择2循环左移K2第16轮K16置换选择2循环左移32bits对换逆初始置换IP－164bitsciphertext48bits3、DES算法的实现步骤第一步：变换明文。对给定的64位比特的明文X，首先通过一个置换IP表来重新排列X，从而构造出64位比特的X0，X0=IP(X)=L0R0，其中L0表示X0的前32比特，R0表示X0的后32位。

第二步：按照规则迭代。Li=Ri-1

Ri=Li⊕f(Ri-1,Ki)（i=1,2,3…16）经过第一步变换已经得到L0和R0的值，其中符号⊕表示的数学运算是异或，f表示一种置换，由S盒置换构成，Ki是一些由密钥编排函数产生的比特块。f和Ki将在后面介绍。第三步：对L16R16利用IP-1作逆置换，就得到了密文y。加密过程如图所示。3、DES算法的实现步骤

DES加密需要四个关键点：

1、IP置换表和IP-1逆置换表。2、函数f。3、子密钥Ki。4、S盒的工作原理。

DES对64位的明文分组进行操作，通过一个初始置换，将明文分组成左半部分和右半部分，各32位长。然后进行16轮完全相同的运算，这些运算被称为函数f，在运算过程中数据与密匙结合。经过16轮后，左，右半部分合在一起经过一个末置换，这样就完成了。（1）IP置换表和IP-1逆置换表5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725输入的第58位作为第1位输入的第50位作为第2位输入的第7位作为第64位输入的第40位作为第1位输入的第8位作为第2位输入的第25位作为第64位IP与IP-1互逆M=(m1,m2,…..)12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455561234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556IP(M)=(m58,m50

)=(m1

1,m1

2,…..)5850423426181026052443628201246254463830221466456484032241685749413325179161584537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602834242105018582633141949175725IPIP-159514335271911 357585960616263643534311511959275758596061626364（1）IP置换表和IP-1逆置换表输入的64位数据按置换IP表进行重新组合，并把输出分为L0、R0两部分，每部分各长32位。比如：置换前的输入值为D1D2D3…D64，则经过初始置换后的结果为：L0=D58D50...D8，R0=D57D49...D7。经过16次迭代运算后。得到L16、R16，将此作为输入，进行逆置换，即得到密文输出。逆置换正好是初始值的逆运算，例如，第20位经过初始置换后，处于第14位，而通过逆置换IP-1，又将第14位换回到第20位。DES的一轮迭代（F函数）Li-1

（32

bit）Ri-1

（32bit）选择扩展运算E盒48bit寄存器48bit寄存器选择压缩运算S盒32bit寄存器置换运算PRi=Li-1⊕f(Ri-1,ki)

（32

bit）（32bit）⊕⊕Li

=Ri-1轮开始：64bit分成左右两半子密钥Ki

（48bit）扩展置换E盒(ExpandBox)将输入的32bit块扩展到48bit的输出块；48bit的输出块再分成8个6bit块；0102030405060708091011121314151617181920212223242526272829303132010203040506070809101112131415161718192021222324252627282930313232040812162024280509131721252901扩展置换函数E扩展位扩展位固定位压缩替代S盒(SubstitutionBox)48bit块通过S盒压缩成32bit块；S盒将6个输入位映射为4个输出位48bit寄存器32bit寄存器

S1S2S3S4S5S6S7S86bit4bit共8个S盒将E的选位结果与Ki作异或操作，得到一个48位输出。分成8组，每组6位，作为8个S盒的输入。S盒S1盒1441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S2盒1518146113497213120510313471528141201106911501471110413158126932151381013154211671205149作用：将6个输入位映射为4个输出位；方法：若定义a1a2a3a4a5a6，将a1a6组成2位二进制数，对应S盒表中的行号；将a2a3a4a5组成一个4位的2进制数，对应S盒表中的列号；映射到交叉点的数据就是该S盒的输出。

S1输入为101011的输出是？A1a6=11a2a3a4a5=01011001S1S2S3S4S5S6S7S8D01230123012301230123012301230123014041515130131013131713103214411121094413161317214151121131480761013861512112811513311041121511121371488471090413141190421121041522111113813414314821471111499035061121171525121471384817421413461510363860612107410197291541216109451526911241534159615111107131421285093415312106111321381341563890713111372691215817101171487811174141251007103138618138531013101471421383101559125111211414159851560671131410910120159106121170861381152714509151310141231559562106129321127125214823531512031341956036109111211714131061271412351214111510594141077128151411130125931012690111251111151213361014016520145015313951000935411105121027093471113010155201435140356511214215142414821480553118689312956157801310515981712159414961431186131621272811表

选择函数S盒表例

S盒应用实例：设B1=101100，求S1(B1)则S1(B1)的值位于列号为2的列和行号为6的行，即等于2，因此S1(B1)的输出是0010。S盒DES中其它算法都是线性的，而S盒运算则是非线性的，S盒不易于分析，它提供了更好的安全性；所以S盒是算法的关键所在；提供了密码算法所必需的混乱作用置换函数P（Permutaion）P置换的目的是：提供雪崩效应；明文或密钥的一点小的变动都引起密文的较大变化；P的功能是对输入进行置换，P换位表如表所示:1607202129122817011523260518311002082414322703091913300622110425DES中子密钥的生成假设密钥为K，长度为64位，但是其中第8、16、24、32、40、48、64用作奇偶校验位，实际上密钥长度为56位。DES中子密钥的生成64bit密钥置换选择1C0（28bit）D0（28bit）循环左移循环左移C1（28bit）D1（28bit）循环左移循环左移置换选择2置换选择2循环左移1234567811222222091011121314151612222221密钥表的计算逻辑：Ci（28bit）Di（28bit）(56bit)(56bit)Ki

K0

(48bit)(48bit)(56bit)子密钥ki

由于不考虑每个字节的第8位，DES的密匙由64位减至56位，每个字节第8位作为奇偶校验确保密匙不发生错误。

假设密钥为K，长度为64位，但是其中第8、16、24、32、40、48、64用作奇偶校验位，实际上密钥长度为56位。K的下标i的取值范围是1到16，用16轮来构造。构造过程如图所示。第一轮：对C0作左移LS1得到C1，对D0作左移LS1得到D1，对C1D1应用PC2进行选位，得到K1。其中LS1是左移的位数，如表所示第二轮：对C1，D1作左移LS2得到C2和D2，进一步对C2D2应用PC2进行选位，得到K2。如此继续，分别得到K3，K4…K16。置换选择-1（7*8）置换选择-2（6*8）

574941332517915850423426181025951432527191136052443663554739312315762544638302214661534537292113528201241417112415328156211023191242681672720132415231374755304051453348444939563453464250362932假设密钥为K，长度为64位，但是其中第8、16、24、32、40、48、64用作奇偶校验位，实际上密钥长度为56位。对于给定的密钥K，应用PC1变换进行选位，选定后的结果是56位子密钥换位表PC-2给出了选择及选择后的次序，可以看出去掉了第9、18、22、25、35、38、43、54位函数f函数f有两个输入：32位的Ri-1和48位Ki，f函数的处理流程如图所示。DES例题：

明文M=“SECURITY”，密钥K=“COMPUTER”。

SECURITY的ASCII码为：[53

4543

55

5249

5459]16，转换成二进制：M=(01010011010001010100001101010101

01010010010010010101010001011001)2；IP置换表：经过IP置换后的排列结果：11111111

110110010100101010101111L00000000000000000

10100000

00010101

R0DES例题：K=“COMPUTER”的ASCII码用二进制表示：[434F4D5055544552]16K=0100001101001111010011010101000001010101

0101010001000101K加上第8、16、24、…、64位的奇同位检查码，并去掉末8位结果如下：K’=(0100

0011

1010

0111

1101

00111010

1011

0000

0100

1010

1011

0101

0001

1000

1010)2密钥是64位，加入8个奇同校验位，为72位，去掉字母R，变成64位密钥长度不是64的整数倍一般右补0x00；当然加密和解密应该实现同样的补位原则。即当加密是右补

0x00，解密时要把补位的0x00去掉就可以还原数据。在此，安全性肯定是不影响，但有一个问题就是要加密的数据中末尾有0x00的问题如何解决，这是应考虑用别的补位数据，如0xff等。

DES例题：K’经过PC-1置换后得到C0，D0C0=1010111001000101001010100100D0=1010

1111

0001

0010

1010

1000

0100因为是第一次迭代，故左移1位C0D0得到C1D1为：C1=0101110010001010010101001001D1=0101111000100101010100001001C1D1在经过PC-2置换得48位子密钥K1：K1=000001011100000100000111000000100011101111110001DES例题：将32位R0进行扩展置换后得48位：E(R0)=100000000000

0000

00000001010100000000

000010101010然后将E(R0)与K1进行异或得A：A=100001011100000100000110010100100011

1011

0101

1011将结果A分为8组，A1=100001，查S1盒坐标(3，0)得B1=15；A2=011100，查S2盒坐标(0，14)得B2=5；A3=000100，查S3盒坐标(0，2)得B3=9；A4=000110，查S4盒坐标(0，3)得B4=3；A5=010100，查S5盒坐标(0，10)得B5=3；A6=100011，查S6盒坐标(3，1)得B6=3；A7=101101，查S7盒坐标(3，6)得B7=10；A8=011011，查S8盒坐标(1，13)得B8=14DES例题：合并B1B2…B8得数据B：B=11110101100100110011

001110101110进行置换P得：X0=10101100111000101110011110110011将L0与X0按位异或，形成R1：R1=01010011001110111000110100011100令L1=R0至此，求出第一轮迭代结果L1R1，依次类推可求出L16R16，在经过逆初始置换即可获得密文。DES密钥的产生K=[science]的ASCII码是：[736369656e6365]其二进制表示是：(01110011)(01100011)(01101001)(01100101)(01101110)(01100011)(01100101)共56個位元加入奇同位检查码结果如下：(01110011)(10110000)(11011010)(00101100)(01010111)(01110011)(10001100)(11001011)共64位按照置换选择1矩阵进行排列：结果如下：(11000110)(10110101)(00101011)

(00111011)(01010101)(10001100)(11000111)将结果分成KL0及KR0：KL0=1100011010110101001010110011KR0=1011010101011000110011000111按照循环移位表分别向左移动一位：KL1=1000110101101010010101100111KR1=0110101010110001100110001111经过置换选择2，生成K1：K1=00101101110110001100111000110111

0111111101000000DES的解密过程DES的运算是对合运算（模2相加、异或），解密和加密可共用同一个运算。不同点：子密钥使用的顺序不同。第一次解密迭代使用子密钥K16，第二次解密迭代使用子密钥K15，第十六次解密迭代使用子密钥K1。

在数学中，对合函数是指函数f(x)满足f(f(x))=x。DES运算是对合运算，是指解密和加密可以共用同一运算(只是子密钥使用的顺序不同)DES算法的安全性DES算法具有比较高安全性，到目前为止，除了用穷举搜索法对DES算法进行攻击外，还没有发现更有效的办法。而56位长的密钥的穷举空间为256，如果一台计算机的速度是每一秒种检测一百万个密钥，则它搜索完全部密钥就需要将近228.5年的时间。f函数（S盒）的设计原理未知；DESCHALLDES分组加密算法是美国政府于1977年公布的数据加密标准，已在银行业和金融业使用了近二十年，自从其公布起，DES就一直不断地被人们研究和攻击，它是世界上最知名的、使用最广泛的分组密码算法。目前攻击DES的最有效的办法是密钥穷举攻击，Verser设计了一个密钥穷举攻击程序，用以穷举所有可能的DES密钥，直至找到正确的那一个密钥，这个计算机程序可以从Internet上分发和下载。他把这项计划命名为DESCHALL，这项计划开始时只有几百人参与，最终吸引了数万名志愿者参加。每有一名新的志愿者加入，DESCHALL小组就为其分配一部分密钥空间让其测试，这样，正确的密钥最终会在某一名志愿者的计算机中出现。1997年1月28日，美国的RSA数据安全公司在RSA安全年会上公布了一项“秘密密钥挑战”(Secret-KeyChallange)竞赛，分别悬赏$1000、$5000、$10000用于攻破不同密钥长度的RC5密码算法，同时还悬赏$10000破密钥长度为56bits的DES算法。美国克罗拉多州的程序员RockeVerser从97年3月13日起，在Internet上数万名志愿者的协同工作下，在RSA挑战赛公布之后的第140天、DESCHALL计划实施的第96天，6月17日的晚10点39分，盐湖城iNetZ公司的职员Michael

Sanders在他那台主频为奔腾90Hz、16M内存的PC机上成功地解出了DES的明文，找到了正确的密钥。

密钥长度(bit) 穷举时间40 78秒48 5小时56 59天64 41年72 10，696年80 2，738，199年88 700，978，948年96 179，450，610，898年112 11，760，475，235，863，837年128 770，734，505，057，572，442，069年DESCHALL搜索速度估算4.4非对称（公开）密钥算法公开密钥算法（非对称算法）的加密的密钥和解密的密钥不同，而且解密密钥不能根据加密密钥计算出来，或者至少在可以计算的时间内不能计算出来。之所以叫做公开密钥算法，是因为加密密钥能够公开，即陌生者能用加密密钥加密信息，但只有用相应的解密密钥才能解密信息。加密密钥叫做公开密钥（简称公钥），解密密钥叫做私人密钥（简称私钥）。公开密钥K1加密表示为：EK1（M）=C。公开密钥和私人密钥是不同的，用相应的私人密钥K2解密可表示为：DK2（C）=M。4.4.2RSA公开密钥加密技术公开密钥加密基本思想是利用求解某些数学难题的困难性。用户的加密密钥与解密密钥不再相同，理论上通过加密密钥求解解密密钥是不可能的。RSA是由MIT的Rivest,Shamir&Adleman

在1977提出最著名的且被广泛应用的公钥加密体制，RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。1.RSA算法描述加密：C=MemodN,where0≤M<N解密：M=CdmodN公钥为（e，N），私钥为（d，N）2.RSA密钥产生过程随机选择两个大素数p,q计算N=p.q注意ø(N)=(p-1)(q-1)选择e使得1<e<ø(N),且gcd(e,ø(N))=1解下列方程求出de.d