第2章-网络安全

1

密码学的发展（cryptography）2.1数据加密技术概述•传统密码学~1976/77-1949年Shannon的“保密通信的信息理论”•现代密码学1976/77~today

-1976:Diffie&Hellman

“公钥密码学的新方向”，掀起公钥密码研究的序幕。

-1977:美国国家标准局公布了美国的数据加密标准DES(DataEncryptionStandard)第2章数据加密技术23

加密是一种限制对网络上传输数据的访问技术，原始数据（明文）被加密设备和密钥加密(Encrypt)而产生的经过编码后的数据称为密文。将密文还原为原始明文的过程称为解密(Decrypt)，它是加密的反向处理。下图是信息加密传递过程。

加密的概念（Encrypt）

其中，E表示加密算法，D表示解密算法，K表示加密密钥，K’表示解密密钥。明文M密文C=E(M,K)E(M,K)传输终端D(C,K’)传输终端明文M出发地加密密钥解密密钥目的地图2.1数据加密模型4

密码体制5

密码体制分类

如图2.1数据加密模型所示，当加密密钥K与解密密钥K’相同时，这样的加密体制称为私钥（单钥或对称）加密体制。当加密密钥K与解密密钥K’不同时，这样的加密体制称为公钥（双钥或非对称）加密体制。图2.2是对称密码体制的加密过程。6ENetworkorStoragePlainTextCipherTextCipherTextDOriginalPlainTextBobSecretKeyAliceSecretKey图2.2对称密码加密模型72.2传统加密技术

希腊密码(二维字母编码查表)公元前2世纪82.2传统加密技术

凯撒密码

凯撒密码是每个字母向前推移k位，并认为Z后边又是A。这种影射关系表示为：F(a)=(a+k)mod26，其中a是明文字母，k是密钥。设k=3，那么字母间的影射关系为：

假设明文为COMPUTE，则凯撒密码是：FRPSXWH。优点：简单易记。缺点：安全性差。9

单表置换密码

在凯撒密码的基础上，将字母表重新打乱。比如，在字母表中首先排列出密钥中出现的字母，然后在密钥后填上剩余的字母。注意不能出现重复字母。例如，密钥是TsinghuaUniversity，那么字母间的影射关系为：

ABCDEFGHIJKLMNOPQRSTUVWXYZTSINGHUAVERYBCDFJKLMOPQWXZ

假设明文为COMPUTE，则密码是：IDBFOMG。假设密文为LMONGCM，则明文为：STUDENT

优点：比凯撒密码的安全性好。

10

多表置换-维吉利亚密码

Vigenere是法国的密码学家，以他名字命名的加密算法是多表密码的典型代表。这种加密以26个字母为基础进行循环移位，排列在一起，形成26*26的方阵，该方阵称为维吉利亚方阵（见下页）。给一个信息加密时，把密钥反复写在明文的下面，明文字母对应维吉利亚方阵的选择列，密钥字母对应选择行，两者的交叉点就是密文字母。

假设明文为HOWAREYOU，密钥为YOUR。则加密过程为：

11

ABCDEFGHIJKLMNOPQRSTUVWXYZAABCDEFGHIJKLMNOPQRSTUVWXYZBBCDEFGHIJKLMNOPQRSTUVWXYZACCDEFGHIJKLMNOPQRSTUVWXYZABDDEFGHIJKLMNOPQRSTUVWXYZABCEEFGHIJKLMNOPQRSTUVWXYZABCDFFGHIJKLMNOPQRSTUVWXYZABCDEGGHIJKLMNOPQRSTUVWXYZABCDEFHHIJKLMNOPQRSTUVWXYZABCDEFGIIJKLMNOPQRSTUVWXYZABCDEFGHJJKLMNOPQRSTUVWXYZABCDEFGHIKKLMNOPQRSTUVWXYZABCDEFGHIJLLMNOPQRSTUVWXYZABCDEFGHIJKMMNOPQRSTUVWXYZABCDEFGHIJKLNNOPQRSTUVWXYZABCDEFGHIJKLMOOPQRSTUVWXYZABCDEFGHIJKLMNPPQRSTUVWXYZABCDEFGHIJKLMNOQQRSTUVWXYZABCDEFGHIJKLMNOPRRSTUVWXYZABCDEFGHIJKLMNOPQSSTUVWXYZABCDEFGHIJKLMNOPQRTTUVWXYZABCDEFGHIJKLMNOPQRSUUVWXYZABCDEFGHIJKLMNOPQRSTVVWXYZABCDEFGHIJKLMNOPQRSTUWWXYZABCDEFGHIJKLMNOPQRSTUVXXYZABCDEFGHIJKLMNOPQRSTUVWYYZABCDEFGHIJKLMNOPQRSTUVYXZZABCDEFGHIJKLMNOPQRSTUVYXY12

矩阵换位密码

把明文中的字母按给定的顺序安排在一个矩阵中，然后用另一种顺序选择矩阵的字母产生密文。在该方案中，矩阵的行数和列数，以及给定的置换矩阵就是密钥。

假设将明文ENGINEERING安排在3*4的矩阵中，即：

1234ENGINEERING

给定一个置换为：

13现在根据给定的位置，按第2列，第4列，第1列，第3列的次序排列，得到：

1234NIEGERNENIG则密文为：NIEGERNENIG，密钥K=(3*4,f)。其解密过程为：第3列为明文的第1列，第1列为明文的第2列，第4列为明文的第3列，第2列为明文的第4列。得到：

1234ENGINEERING则明文为：ENGINEERING14

简单异或运算

异或运算规则：

经常可以用异或运算对文件做一些简单的加密运算

15#include"stdio.h"main(){FILE*fi,*fo;charfname1[50],fname2[50];charc;intk=1;/*key*/printf("input_filename:");scanf("%s",fname1);printf("output_filename:");scanf("%s",fname2);if((fi=fopen(fname1,"rb"))!=NULL){ if((fo=fopen(fname2,"wb"))!=NULL) {while((c=fgetc(fi))!=EOF){ c^=k; fputc(c,fo); }fclose(fo); } fclose(fi);}}162.4现代加密技术

密码分析

常用的密码分析攻击有四类：

(1)唯密文攻击(ciphertext-onlyattack)

密码分析者有一些消息的密文，这些消息都是用同一加密算法加密。密码分析者的任务是恢复尽可能多的明文，或者是加密消息的密钥。

(2)已知明文攻击(known-plaintextattack)

密码分析者不仅可得到一些消息的密文，而且知道这些消息的明文。密码分析者的任务是用加密信息推出加密的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。17

(3)选择明文攻击(chosen-plaintextattack)

密码分析者可得到所需要的任何明文所对应的密文，这些密文与待解的密文是用同一密钥加密得来的。

(4)选择密文攻击(chosen-ciphertextattack)

密码分析者可得到所需要的任何密文所对应的明文，解密这些密文所使用的密钥与待解的密文的密钥是一样的。

上述四种攻击的强度按顺序递增，唯密文攻击是最弱的一种攻击，选择密文攻击是最强的一种攻击。18

对称密码体制

序列密码一直作为军事和外交场合使用的主要密码技术之一。其工作原理是：将明文M看成连续的比特流或字符流(m1m2m3•••.)，并用密钥序列K(k1k2k3•••)中第i个元素ki对明文中的mi进行逐位加密，即：

EK(M)=Ek1(m1)Ek2(m2)•••

加密和解密过程如图2.3所示。

1、流密码（序列密码）对称密码算法分为流密码和分组密码两类。19密钥序列发生器加密算法密钥序列发生器解密算法I0I0mi明文信息mi明文信息mi’密文信息其中，I0用于初始化密钥序列产生器图2.3序列密码加密和解密过程kiki20...10101101...01110100...11011001流密码加密的例子plaintextstreamkeystreamciphertextstream21...10101101...01110100...11011001流密码解密的例子plaintextstream(thesame!)keystreamciphertextstream22Apseudo-randomnumbergenerator(PRNG)isanalgorithmthatexpandsarandombutrelativelyshortkey,sayof64bits,intoalongbitsequencethatpreservestherandomnesspropertyoftheoriginalshortkeyrelativelyshortkey(say64bits)longoutput为了加强算法的安全性，常常使用伪随机数产生器增加密钥的长度。23...10101101...01110100...11011001Encryptionplaintextstreamlongoutputkeystreamciphertextstream24...10101101...01110100...11011001Decryptionplaintextstreamlongoutputkeystreamciphertextstream25

2、分组密码（BlockCiphers）迭代密码明文：X=Y(0)密文：Y=Y(r)迭代函数:F迭代次数:r种子密钥：k迭代的子密钥：Z(i)（1）DES算法(DataEncryptionStandard)DES由IBM在70年代提出的，1976年被美国政府定为数据加密标准。其工作原理是：将一个需要加密的明文分为若干个长度为64比特的数据块，逐次对每一个数据块进行加密。

DES密钥长度56比特(约1018)，进行16轮的迭代编码，获得长度为64比特的密文。由于DES的密钥太短，不能抵御穷举攻击。1997年，RSA公司以$10,000为悬赏，攻破DES。有人编写了特定的程序在Internet上发布，70000个用户（机器）加入了对DES的攻击，结果，在遍历了1/4的密钥空间后，破解了DES。1998年，电子边境基金学会（EFF）使用一台价值25万美圆的电脑在56小时内破译了56位的DES。27

DES有16轮，这意味着要在明文分组上16次实施相同的组合技术。加密过程

DES使用56位密钥对64位数据块进行加密，需要进行16轮编码。2829一轮DES

假设Bi是第i次迭代的结果，Li和Ri是Bi的左半部分和右半部分，Ki是第i轮的48位密钥，且f是实现代替、置换及密钥异或等运算的函数，那么每一轮就是：

Li=Ri-1 Ri=Li-1⊕f(Ri-1,Ki)

算法概要

DES对64位的明文分组进行操作。通过一个初始置换，将明文分组分成左半部分和右半部分，各32位长。30初始置换（IP置换） 初始置换在第一轮运算之前执行，对输入分组实施如下表所示的变换。此表应从左向右、从上向下读。例如，初始置换把明文的第58位换到第1位的位置，把第50位换到第2位的位置，把第42位换到第3位的位置，等等。58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157目的：打乱原来输入x的ASCII码字的划分关系。31密钥置换 一开始，由于不考虑每个字节的第8位，DES的密钥由64位减至56位，如下表所示。每个字节第8位可作为奇偶校验位以确保密钥不发生错误。在DES的每一轮中，从56位密钥产生出不同的48位子密钥（SubKey），这些子密钥Ki由下面的方式确定。57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124注意：第8、16、24、32、40、48、56、64共8个奇偶校验位并未处理。32

首先，56位密钥被分成两部分，每部分28位。然后，根据轮数，这两部分分别循环左移l位或2位。下表给出了每轮移动的位数。

轮12345678910111213141516位数112222221222222133

移动后，就从56位中选出48位。因为这个运算不仅置换了每位的顺序，同时也选择子密钥，因而被称作压缩置换。这个运算提供了一组48位的集。下表定义了压缩置换（也称为置换选择）。例如，处在第33位位置的那一位在输出时移到了第35位的位置，而处在第18位位置的那一位被略去了。1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932注意：第9、18、22、25、35、38、43、54被略去了。34

因为有移动运算，在每一个子密钥中使用了不同的密钥子集的位。虽然不是所有的位在子密钥中使用的次数均相同，但在16个子密钥中，每一位大约使用了其中14个子密钥。扩展置换 这个运算将数据的右半部分Ri从32位扩展到了48位。由于这个运算改变了位的次序，重复了某些位，故被称为扩展置换。 这个操作有两个方面的目的：它产生了与密钥同长度的数据以进行异或运算，它提供了更长的结果，使得在替代运算时能进行压缩。35

下图显示了扩展置换，有时它也叫做E盒。对每个4位输入分组，第1和第4位分别表示输出分组中的两位，而第2和第3位分别表示输出分组中的一位。

36

下表给出了哪一输出位对应于哪一输入位。例如，处于输入分组中第3位的位置的位移到了输出分组中第4位的位置，而输入分组中第21位的位置的位移到了输出分组中第30和第32位的位置。

尽管输出分组大于输入分组，但每一个输入分组产生唯一的输出分组。321234545678989101112131213141516171617181920212021222324252425262728292829303132137S盒代替 压缩后的密钥与扩展分组异或以后，将48位的结果送入，进行代替运算。替代由8个代替盒，或S盒完成。每一个S盒都有6位输入，4位输出，且这8个S盒是不同的。（DES的这8个S盒占的存储空间为256字节。）48位的输入被分为8个6位的分组，每一分组对应一个S盒代替操作：分组1由S-盒1操作，分组2由S-盒2操作，依次类推。38

每个S盒是一个4行、16列的表。盒中的每一项都是一个4比特位的数（0-15）。S盒的6个位输入确定了其对应的输出在哪一行哪一列。下面列出所有的8个S盒。

14413121511831061259070157414213110612119538411481362111512973105015128249175113141006131518146113497213120510313471528141201106911501471110413158126932151381013154211671205149S盒1：S盒2：39713143069101285111241513811565034721211014910690121171315131452843150610113894511127214100914631551131271142813709346102851412115113649815301112125101471101306987415143115212S盒3：S盒4：401211015926801334147511101542712956113140113891415528123704101131164321295151011141760813212417101168531513014914112124713150151039864211110137815912563014181271142136150910453S盒5：S盒6：414112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S盒7：S盒8：132846151111093145012711513810374125611014927114191214206101315358211474108131512903561142

输入位以一种非常特殊的方式确定了S盒中的项。假定将S盒的6位的输入标记为b1、b2、b3、b4、b5、b6。则b1和b6组合构成了一个2位的数，从0到3，它对应着表中的一行。从b2到b5构成了一个4位的数，从0到15，对应着表中的一列。 例如，假设第6个S盒的输入（即异或函数的第31位到36位）为110011。第1位和最后一位组合形成了11，它对应着第6个S盒的第三行。中间的4位组合在一起形成了1001，它对应着同一个S盒的第9列。S盒6的第三行第9列处的数是14（记住：行、列的记数均从0开始而不是从1开始），则值1110就代替了110011。43P盒置换

S盒代替运算后的32位输出依照P盒进行置换。该置换把每输入位映射到输出位，任意一位不能被映射两次，也不能被略去，这个置换叫做直接置换。下表给出了每位移到的位置。例如，第21位移到了第4位处，同时第4位移到了第31位处。最后，将P盒置换的结果与最初的64位分组的左半部分异或，然后左、右半部分交换，接着开始另一轮。167202129122817115232651831102824143227391913306221142544末置换

末置换是初始置换的逆过程，下表列出了该置换。应注意DES在最后一轮后，左半部分和右半部分并未交换，而是将R16与L16并在一起形成一个分组作为末置换的输入。4084816562464323974715552363313864614542262303754513532161293644412522060283534311511959273424210501858263314194917572545DES解密 在经过所有的代替、置换、异或和循环移动之后，获得了这样一个非常有用的性质：加密和解密可使用相同的算法。

DES使得用相同的函数来加密或解密每个分组成为可能，二者的唯一不同之处是密钥的次序相反。这就是说，如果各轮的加密密钥分别是K1，K2，K3…，K16那么解密密钥就是K16，K15，K14……，K1。为各轮产生密钥的算法也是循环的。密钥向右移动，每次移动个数为0，1，2，2，2，2，2，2，1，2，2，2，2，2，2，1。46DES举例 已知明文m=computer，密钥k=program，用ASCII码表示为：m=0110001101101111011011010111000001110101011101000110010101110010k=01110000011100100110111101100111011100100110000101101101

因为k只有56位，必须插入第8，16，24，32，40，48，56，64位奇偶校验位，合成64位。而这8位对加密过程没有影响。47m经过IP置换后得到L0=11111111101110000111011001010111R0=00000000111111110000011010000011密钥k通过PC-1得到C0=1110110010011001000110111011D0=1011010001011000100011100110再各自左移一位，通过PC-2得到48位k1=001111011000111111001101001101110011111100000110R0（32位）经E作用膨胀为48位，10000000000101111111111010000000110101000000011048再和k1作异或运算得到（分成8组）101111011001100000110011101101111110101101001110通过S盒后输出位32比特，01110110001101000010011010100001S盒的输出又经过P置换得到01000100001000001001111010011111这时：所以，第一趟的结果是：000000001111111100000110100000111011101110011000111010001100100049

如此，迭代16次以后，得到密文：0101100010101000010000011011100001101001111111101010111000110011

明文或密钥每改变一位，都会对结果密文产生剧烈的影响。任意改变一位，其结果大致有将近一半的位发生了变化。DES算法的实现硬件实现1984年，DES芯片每秒加密25.6万次1987年，DES芯片每秒加密51.2万次目前最快的DES芯片每秒加密1G比特（DEC:美国数字设备公司开发）软件实现在IBM3090大型机上，DES软件实现每秒加密3.2万次在80486处理器，速度为66MHz，总线宽32位的微机上，DES软件实现每秒加密4.3万次S-盒的设计S-盒是DES的心脏S-盒的设计原理尚未公开密码学家怀疑NSA设计S-盒时隐藏了“陷门”DES的安全性二重DES的结构

y=DESK2(z)=DESK2(DESK1(x))明文:xzDES密钥:K1DES密钥:K2密文:y二重DES的安全性密钥长度为112bit,强度极大增加.(2)二重DES（3）三重DES(TripleDES)

三重DES是DES的加强版，它能够使用两个密钥，主要对信息逐次做三次加密。密钥长度是112位。加密：E=DES,解密：D=DES-1y=EK1[DK2(EK1(x))]明文:xE密钥:K1E密钥:K1密文:yuD密钥:K2v加密-解密-加密模式(EDE:encrypt-decrypt-encrypt)已被密钥管理标准ANSX.917和ISO8732采用缺点是要花费3倍DES的运行时间54(4)国际数据加密IDEA-------

（InternationalDataEncryptionAlgorithm)算法1990年，XuejiaLai(来学嘉，旅居瑞士中国学者)和J.L.Massey(国际著名密码学家)提出一个建议加密标准(PES:proposedencryptionstandard)1991年，设计出改进型建议加密标准(IPES),能够抗击差分密码分析1992年，改名为国际数据加密算法

(IDEA:internationaldataencryptionalgorithm)是DES之后又一个成功的分组密码，已被用于Internet的E-mail加密系统PGP和其他加密系统分组长度:64密钥长度:12855XuejiaLai(来学嘉)简介国际著名密码学家1982年获西安电子科技大学学士学位1984年获该校应用数学硕士学位1988年获瑞士苏黎世高工通信技术硕士学位1992年获瑞士苏黎世高工技术科学博士学位1994年加入瑞士r3安全工程中心，该中心于1998年6月成为Entrust(瑞士)公司2001年加入瑞士S.W.I.S.中心2004年到上海交大任教，兼任科学院研究生院名誉教授，西南交通大学顾问教授设计了IDEA加密算法。对Hash函数的分析和构造研究的成果得到国际上普遍应用,包括最近对MD4,SHA的碰撞攻击。在差分破译法的研究中，提出差分，高阶差分，马尔科夫密码的概念,用马尔科夫链理论将差分破译法公式化，使得推导差分密码分析复杂度的下界成为可能。设计了欧洲Eurochip电话卡中的认证算法。审核过欧洲银行Eurocard智能卡系统的安全性。分析评估欧洲电讯标准局的专用密码。分析及改进付费电视系统中使用的密码及密钥管理系统。参与过中国金融认证中心的建设。主编了ISO-13888不可抵赖标准、ISO-11770密钥管理标准及ISO-18033加密算法标准。并参与欧盟KRISIS，ICE-CAR和PKIChallenge项目。现任2006亚密会(Asiacrypt)程序委员会主席,中国密码学会常务理事。XuejiaLai(来学嘉)简介国际著名密码学家来学嘉博士2005年6月在西南交通大学讲学IDEA基本运算逐位异或:

全体16位二进制向量(Z216,)是一个群mod(216=65536)整数加法:⊞

全体小于216的非负整数(Z65536,⊞)是一个群mod(216+1=65537)整数乘法:⊙

全体小于216+1的正整数(Z65537*,⊙)是一个群将216=65536视为0，则(Z65537*,⊙)等同于(Z65536,⊙)

例:0000000000000000⊙1000000000000000=0⊙215=216⊙215=216215

mod(216+1)=(216+1-1)215

mod(216+1)=(216+1)215-1215

mod(216+1)=-215

mod(216+1)=216+1-215

mod(216+1)=215+1=1000000000000001.58IDEA基本运算三个运算

,⊞,⊙都使Z216成为群Z216中三个运算

,

⊞,⊙任何两个都不满足分配律,例

a⊞(b⊙c)(a⊞b)⊙(a⊞c).Z216中三个运算

,⊞,⊙任何两个都不满足结合律,例

a⊞(bc)(a⊞b)c.三个运算

,⊞,⊙

的混合使用,获得良好的非线性性，混淆与扩散效果显著，具有很高的安全性.例：设运算数长为2bit，22=4,a=10,b=11,有

ab=1011=01;

a⊞b=10⊞11=2+3=5=1=01mod4;a⊙b=10⊙11=23=6=1=01mod5.59IDEA基本运算乘/加结构MA(multiplication/addition)⊞⊙⊞⊙K2(16bit)K1(16bit)G2(16bit)G1(16bit)F2(16bit)F1(16bit)输入：

F1,F2:16bit

子密钥K1,K2:16bit输出：

G1,G2:16bit非线性结构

MA:{0,1}16{0,1}16{0,1}16{0,1}16{0,1}16{0,1}1660IDEA算法框图8轮迭代输入:4个16bit子串

6个16bit子密钥输出:4个16bit子串输出变换输入:4个16bit子串

4个16bit子密钥输出:4个16bit子串子密钥生成算法

K(128bit)

K1,K2,…,K52(16bit).…………

第2轮W21W23W22W24W11W13W12W14K7K12…

第1轮K1K6…X1X3X2X4

明文:X(64bit)

第8轮W81W83W82W84W71W73W72W74K43K48…

输出变换K49K52…Y4Y3Y2Y1

密文:Y(64bit)61IDEA的子密钥生成算法将128bit的K依次分为8个16bit的子密钥:

K1,K2,…K8将K循环左移25位得L25K，依次分为8个16bit的子密钥:K9,K10,…K16重复上一步…62IDEA的轮结构输入:4个16bit子串:I1,I2,I3,I46个16bit子密钥:

Z1,Z2,Z3,Z4,Z5,Z6输出:4个16bit子串O1,O2,O3,O4⊞⊞⊙⊙⊞⊙⊞⊙O1O2O3O4I1I2I3I4Z2Z1Z3Z4Z5Z663IDEA的输出变换输入:4个16bit子串:W81,W82,W83,W844个16bit子密钥:

K49,K50,K51,K52输出:4个16bit子串Y1,Y2,Y3,Y4W81W82W83W84⊞⊞⊙⊙Y1Y2Y3Y4K51K52K50K49密文:Y=IDEAK(X)=Y1||Y2||Y3||Y464IDEA特性IDEA算法软、硬件实现容易，速度快。软件实现比DES快两倍安全性好：用穷举攻击要试探2128=1038个密钥，如用每秒运行100万次的计算机进行搜索，大约需要1013年.IDEA能抵抗差分攻击和线性攻击IDEA的安全缺陷：存在大量的弱密钥IDEA的设计适合于16位CPU,对于32CPU实现不太方便65（4）AES（AdvancedEncryptionStandard）1997年4月15日，（美国）国家标准技术研究所（NIST）发起征集高级加密标准（AdvancedEncryptionStandard）AES的活动，活动目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。作为进入AES候选过程的一个条件，开发者承诺放弃被选中算法的知识产权。

对AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。661998年8月12日，在首届AES会议上指定了15个候选算法。1999年3月22日第二次AES会议上，将候选名单减少为5个，这5个算法是RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES会议上，对这5个候选算法的各种分析结果进行了讨论。2000年10月2日，NIST宣布了获胜者—Rijndael算法，2001年11月出版了最终标准FIPSPUB197。67分组长度（bit）128192256密钥长度（bit）128192256表1.分组长度和密钥长度的不同取值68AES

算法的一般描述69RijndaelRound的构成ByteSubstitution(字节置换)ByteRotation(字节移位)MixColumn(列混合)+RoundKey一般的轮变换ByteSubstitutionByteRotation+RoundKey最后一轮的轮变换轮密钥加7071AES

算法加密部分的实现明文分组和密钥的组织排列方式01234567891011121314150481215913261014371115Fig1.以明文分组为128bits为例组成的阵列72048121591326101437111504812162015913172126101418223711151923048121620242815913172125292610141822263037111519232731Fig2.以明文分组（或密钥）为128bits、192bits、256bits为例组成的阵列73

一些相关的的术语定义和表示状态（State）：密码运算的中间结果称为状态。State的表示：状态用以字节为基本构成元素的矩阵阵列来表示，该阵列有4行，列数记为Nb。Nb=分组长度（bits）÷32Nb可以取的值为4，6，8，对应的分组长度为128，192，256bits。密码密钥（CipherKey）的表示：CipherKey类似地用一个4行的矩阵阵列来表示，列数记为Nk。Nk=密钥长度（bits）÷32Nk可以取的值为4，6，8，对应的密钥长度为128，192，256bits。74Fig3.当Nb=6时的状态和Nk=4时的密钥布局a0,0a0,1a0,2a0,3a0,4a0,5a1,0a1,1a1,2a1,3a1,4a1,5a2,0a2,1a2,2a2,3a2,4a2,5a3,0a3,1a3,2a3,3a3,4a3,5Nb=6BlockLength=192bitsK0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3Nk=4KeyLength=128bits75表2.轮数（Round）的不同取值轮数（Round）BlockLength=128BlockLength=192BlockLength=256KeyLength=128101214KeyLength=192121214KeyLength=2561414147676用伪代码表示的Rijndael轮变换一般的轮变换Round(State,RoundKey){ByteSubstitution;ByteRotation;MixColumn;AddRounKey;}结尾轮变换FinalRound(State,RoundKey){ByteSubstituion;ByteRotation;AddRoundKey;}77用伪代码表示的Rijndael加密算法Rijndael(State,CipherKey){

KeyExpansion(CipherKey,ExpandedKey);AddRoundKey(State,ExpandedKey);For(i=1;i<Rnd;i++)Round(State,ExpandedKey+Nb*i);FinalRound(State,ExpandedKey+Nb*Rnd);}78与一些其它算法的比较：与DES相比：1.无DES中的弱密钥和半弱密钥；2.紧凑的设计使得没有足够的空间来隐藏陷门。与IDEA相比：无IDEA中的弱密钥。具有扩展性：密钥长度可以扩展到为32bits倍数的任意密钥长度，分组长度可以扩展到为64bits倍数的任意分组长度。圈数和循环移位偏移量作为参数，要重新定义。79

3、对称密码的弱点

对称密码体制的优点是计算速度快，有较强的保密强度。但是，它有三个致命弱点：

1、密钥分配非常困难；

2、难以解决数字签名验证问题。

3、要为每一个通信对象维护一个密钥。若要与100人秘密通信，则要保留100个密钥。大量密钥的维护比较困难、容易泄密。80当某一贸易方有n”个贸易关系,那么他就要维护“n”个专用密钥(即每把密钥对应一贸易)对称密钥加密中的密钥81

非对称密码体制ENetworkPlainTextCipherTextCipherTextDPlainTextAliceBobBob:SecretKey82明文密文非对称密钥加密技术加密我的：私有密钥或你的：公共密钥我的：公共密钥或你的：私有密钥831、基本概念

为了解决上述问题，1976年，Diffi和Hellman首次提出公开非对称密钥加密体制。即每个人都有一对密钥，其中一个为公开的（公钥），一个为私有的（私钥）。使用两个密钥——一个用来加密数据，一个用来解密数据。两个密钥是数学上相关联的——用其中之一加密的数据，只能够用另一个密钥解密。密钥对由用户自己或信任机构产生。当与多个通信对象进行通信时，只要生成一对密钥。W.Diffie&M.Hellman:NewDirectionsinCryptography,IEEETransactionsonInformationTheory,Vol.IT-22,No.6,Nov.1976,pp.644-654.84通信方甲生成一对密钥并将其中的一把作为公开密钥向其他通信方公开非对称密钥加密中的密钥852、非对称密钥加密的原理使用数学上的理论；数学上某些复杂的计算问题：正向计算容易，反向计算困难。计算机不可能在有效的时间内算出反向结果（从而不可能破解密码）。例如：计算两个大数的乘积，非常容易。分解一个很大的数（如200多位）非常困难，假如这个大数只含有两个非常大的素数（各100多位）作为因子。863、RSA算法（1）RSA背景

RSA算法是由Rivest、Shamir、Adleman于1977年提出的，RSA的取名就来自于这三个发明者的姓名的第一个字母，他们在1982年创办RSA公司，该公司在公钥密码系统的研制和商业应用推广方面有非常重要的地位。

RSA算法的理论基础是数论中的欧拉定理，其安全性是基于大数分解的困难性。1978年,R.Rivest,A.Shamir,L.Adleman提出RSA密码体制

R.Rivest,A.Shamir,L.Adleman,Amethodforobtainingdigitalsignaturesandpublic-keycryptosystem,Comm.ACM21(2)(1978),pp.120-126.数学基础是欧拉定理，安全性基于大合数因式分解的困难性安全,易懂.可用于加密与数字签名.ISO,ITU,SWIFT把RSA选为加密标准;Internet的E-Mail的保密系统GPG,国际VISA和MASTER组织的电子商务协议(SET协议)都将RSA作为传送会话密钥和数字签名的标准.3、RSA算法RSA密码体制算法密钥生成算法(1)选取两个大素数p,q(2)计算n=pq,(n)=(p-1)(q-1)(3)随机选取e:1<e<(n)，与(n)互素(4)根据欧几里德算法计算e的逆d=e1:1<e<(n)，ed1mod(n).(5)公钥:PK=(n,e),

私钥:SK=(p,q,d).(6)明文空间和密文空间:

Zn={0,1,2,…,n-1}90加密算法:设消息m:0m<n，解密算法:设密文c:0c<n，解密算法正确性证明（P为素数）例

设p=11,q=13.令

n=1113=143,

(n)=(p-1)(q-1)=(11-1)(13-1)=120,取公钥:PK=(n,e)=(143,e=17)，计算:d=e-1=17-1=113(mod120)(因为:17113=1921=16120+1).私钥:SK=(p,q,d)=(11,13,113).对于明文:m=24,密文:c=EPK(m)=2417=7(mod143).对于密文:c=7,解密:m=DSK(c)=7113=24(mod143).RSA密码算法的实现模幂算法:me(modn)—(高效算法：平方乘算法)b=0?b(mod2)=0?输出c==unsignedlongqe2(unsignedlongx,unsignedlongr,unsignedlongn){unsignedlonga,b,c;c=1;a=x;b=r;while(b)/*b非0，则继续处理*/{if(b&1)/*表示指数为奇数*/c=(c*a)%n;/*把两个指数为1的数相乘，变为一个数*/b>>=1;/*指数除以2*/a=(a*a)%n;}returnc;}main(){unsignedlonga=1520,b=13,n=2573,congruent;congruent=qe2(a,b,n);printf(“Resultis:%ld”,congruent);}95RSA密码体制的安全性攻击方法

：分解n已知n=pq

(n)=(p-1)(q-1)

d=e-1mod(n).分解n的最新水平:二进制表示有512位.n应为1024,2048位.96对RSA的选择密文攻击它们不攻击基本的算法，而是攻击协议。

情况1：假设A在B的通信时进行窃听，得到用B的公钥加密的密文C。显然，A要得到明文M，必须计算：97

情况2：

假设A想得到B对消息m3的伪造签名，A可以做如下攻击：注意：千万不要对陌生人提交的随机消息进行签名。98RSA的公共模数攻击

若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设m

为信息明文，两个加密密钥为e1和e2，公共模数是n，则两个密文为：

密码分析者知道n、e1、e2、C1和C2，就能得到m。因为e1和e2互质，故用扩展Euclidean算法能找到r和s，满足：r*e1+s*e2=1注意：不要在一组用户间共享n。99100p和q要足够大:n=pq

为1024位,或2048位.p和q应为强素数(strongprime).

如果素数p

满足以下条件,则称为强素数.(1)p-1有大素数因子r;(2)p+1有大素数因子s;(3)r-1有大素数因子t.

例如:理想的强素数为:

r=2t+1;p=2r+1=4t+3;p=2s-1.RSA密码的安全参数|p-q|要大.

如果|p-q|较小,则(p+q)/2n1/2,((p-q)/2)2=((p+q)/2)2-n.可求出p和q.

例:对于n=164009,有n1/2405.令

(p+q)/2=405,((p-q)/2)2=4052-n=16p+q=810,p-q=8p=409,q=401164009=409401.加密指数e的选择

为使加密速度快,应使e的二进制表示中,1的个数尽量小,但不能太小.

可取:e=3,216+1=65537(在二进制表示中只有2个1).解密指数d的选择

在d的二进制表示中,1的个数尽量小,但不能太小.3dn1/4.1034、ElGamal算法1045、椭圆曲线密码系统

有限域上的椭圆曲线设p