应用密码学课件

第1章绪论学习要点：了解信息安全问题的由来、根源、紧迫性和重要性了解密码学在信息安全中的重要作用了解密码学的发展简史了解网络信息安全的机制和安全服务了解安全性攻击的主要形式及其分类§1-1网络信息安全概述网络信息安全问题的由来网络信息安全问题的根源网络信息安全的重要性和紧迫性一、网络信息安全问题的由来通信与计算机网络技术的快速发展和公众信息系统商业性应用步伐的加快对网络环境和网络信息资源的依赖程度日渐加深大量网络中存储和传输的数据需要保护互联网是一个开放系统（资源丰富、高度分布、广泛开放、动态演化、边界模糊等特点）黑客袭击事件不断发生并逐年递增二、网络信息安全问题的根源网络自身的安全缺陷协议不安全和业务不安全网络的开放性

业务基于公开的协议连接是基于主机上的社团彼此信任的原则远程访问人的因素

人为的无意失误黑客攻击管理不善三、网络信息安全的重要性和紧迫性国家信息基础设施逐渐形成，计算机网络已经成为信息化社会发展的重要保证网络信息安全关系到国家主权的安全、社会的稳定、民族文化的继承和发扬等网络信息安全关系到公私财物和个人隐私的安全近年来，计算机犯罪案件数量急剧上升，计算机犯罪已经成为普遍的国际性问题§1－2密码学在网络信息安全中的作用现实世界数字世界机密性（门窗、锁）完整性（报警器）身份证明签字认证（身份证明）数字签名（签字）门窗、锁报警器密码学在网络信息安全中的作用（续）密码技术是实现网络信息安全的核心技术，是保护数据最重要的工具之一当前信息安全的主流技术和理论都是基于现代密码学的密码学在网络信息安全中具有举足轻重的作用辩证观§1－3密码学的发展历史古代加密方法

大约起源于公元前440年出现在古希腊战争中的隐写术斯巴达人于公元前400年应用scytale我国古代的藏头诗、藏尾诗、漏格诗以及绘画等Polybius校验表特点：主要基于手工的方式实现，简单Polybius校验表123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ古典密码阿拉伯人是第一个清晰地理解密码学原理的人：设计并且使用代替和换位加密，并发现了字母频率分布关系欧洲的密码学起源于中世纪的罗马和意大利1860年，密码系统在外交通信中已得到普遍使用一次世界大战期间，敌对双方使用加密系统用于战术通信二十世纪20年代，转轮机的出现是密码学发展的重要标志之一二次世界大战期间，转轮机得到广泛的使用二次大战后，电子学开始被引入到密码机中古典密码

单表代替密码：Caesar密码多表代替密码：Vigenere密码、Hill密码转轮密码：Enigma密码特点文字置换保留手工实现方式，开始出现机械变换的实现方式比古代加密方法更复杂，但其变化量仍然比较小已经初步体现出近代密码系统的雏形特别是转轮机的出现，大大提高了密码加密速度在外交、军事领域得到过广泛应用近代密码

1949年Claude

Shannon发表Thecommunicationtheoryofsecrecysystems1976年W.Diffie和M.Hellman发表了Newdirectionsincryptography，提出了适应网络上保密通信的公钥密码思想1978年RSA公钥密码体制的出现1978年美国批准批准DES用于政府等非机密单位及商业上的保密通信二十世纪70年代，开始形成密码学科特点与计算机技术、电子通信技术紧密相关密码理论蓬勃发展，密码算法设计与分析互相促进，出现了大量的密码算法和各种攻击方法密码使用的范围也在不断扩张，出现了许多通用的加密标准，促进网络和技术的发展出现了一些新的密码技术，如混沌密码、量子密码等§1－4网络信息安全的机制和安全服务安全机制

概念：用来保护系统免受侦听、阻止安全攻击及恢复系统的机制特定的安全机制：加密、数字签名、访问控制、数据完整性、认证交换、流量填充…通用的安全机制:

可信功能、安全标签、事件检测、安全审计跟踪、安全恢复安全服务概念：加强数据处理系统和信息传输的安全性的一类服务目的：利用一种或多种安全机制阻止安全攻击数据的性质Interruption--Interception--Modification--Fabrication--

Availability

Availability

AvailabilityConfidentiality

Availability

Integrity

Availability

Authenticitycontentorigin特点及防护被动攻击难以检测重点是防止，提供机密性主动攻击难以防止重点是检测，发现并恢复第2章密码学基础学习要点：了解密码学的基本概念了解密码系统的定义、安全条件及其分类了解信息安全模型了解密码体制的基本内涵§2－1密码学相关概念密码学密码编码学（密码编码者）密码分析学（密码分析者）明文、密文、密钥、加密算法、解密算法密码分析分类唯密文攻击（Ciphertextonly）破译者已知：加密算法、待破译的密文

已知明文攻击（Knownplaintext）破译者已知：加密算法、一定数量的密文和对应的明文选择明文攻击（Chosenplaintext）破译者已知：加密算法、选定的明文和对应的密文选择密文攻击（Chosenciphertext）破译者已知：加密算法、选定的密文和对应的明文选择文本攻击（Chosentext）破译者已知：加密算法、选定的明文和对应的密文、选定的密文和对应的明文

分析唯密文攻击是最困难的上述攻击的强度是递增的一个密码体制是安全的，通常是指在前三种攻击下的安全性§2－2密码系统概念：用于加密与解密的系统是明文与加密密钥作为加密变换的输入参数，经过一定的加密变换处理以后得到的输出密文，由它们所组成的这样一个系统密码系统的安全条件密码系统的安全性只寓于密钥，通常假定算法是公开的这要求加密算法本身非常强壮破译算法分级全部破译（totalbreak）全部推导（globaldeduction）实例推导（instancededuction）信息推导（informationdeduction）衡量攻击方法的复杂性数据复杂性（datacomplexity）处理复杂性（processingcomplexity）存储需求（storagerequirement）评价密码体制安全性的三个途径计算安全性可证明安全性无条件安全性一个密码系统实际安全的条件

每一个加密函数和每一个解密函数都能有效地计算破译者取得密文后将不能在有效的时间或成本范围内破解出密钥或明文一个密码系统是安全的必要条件：穷举密钥搜索将是不可行的CryptographySystemThetypeofoperationsusedfortransformingplaintexttociphertextsubstitutiontranspositionThenumberofkeyusedsymmetric,singlekey,secret-key,orconvetionalencryptionasymmetric,two-key,public-keyencryptionThewayinwitchtheplaintextisprocessedblockcipherstreamcipher§2－3安全模型网络传输中的信息安全动态数据的安全网络安全模型计算机系统中的信息安全静态数据的安全网络访问安全模型网络安全模型网络访问安全模型§2－4密码体制对称密码体制非对称密码体制传统密码体制对称密码算法的优、缺点优点：加/解密处理速度快、保密度高等。缺点：如何把密钥安全地送到收信方，是对称密码算法的突出问题。对称密码算法的密钥分发过程十分复杂，所花代价高多人通信时密钥组合的数量会出现爆炸性膨胀，使密钥分发更加复杂化通信双方必须统一密钥，如果发信者与收信人素不相识，这就无法向对方发送秘密信息了存在数字签名困难问题公钥密码体制公开密钥密码体制的优、缺点优点：网络中的每一个用户只需要保存自己的私有密钥。密钥少，便于管理密钥分配简单，不需要秘密的通道和复杂的协议来传送密钥可实现数字签名缺点：加密、解密处理速度相对较慢，同等安全强度下所要求的密钥位数多一些加密解密明文密文原来的明文加密解密明文密文原来的明文加密解密明文密文原来的明文KKKEKD公开密钥密码体制与常规密码体制的比较

分类常规密码体制公开密钥密码体制运行条件加密和解密使用同一个密钥和同一个算法。用同一个算法进行加密和解密，而密钥有一对，其中一个用于加密，另一个用于解密。发送方和接收方必须共享密钥和算法。发送方和接收方每个使用一对相互匹配、而又彼此互异的密钥中的一个。安全条件密钥必须保密。密钥对中的私钥必须保密。如果不掌握其他信息，要想解密报文是不可能或至少是不现实的。如果不掌握其他信息，要想解密报文是不可能或者至少是不现实的。知道所用的算法加上密文的样本必须不足以确定密钥。知道所用的算法、公钥和密文的样本必须不足以确定私钥。第3章古典密码学习要点了解古典密码的基本概念了解隐写术了解代替及其实现方法了解换位及其实现方法§3-1隐写术诗情画意传“密语”早妆未罢暗凝眉，

迎户愁看紫燕飞，

无力回天春已老，

双栖画栋不如归。诗情画意传“密语”水洗尘埃道未甞，甘于名利两相忘。心怀六洞丹霞客，口诵三清紫府章。十里采莲歌达旦，一轮明月桂飘香。日高公子还相觅，见得山中好酒浆。洗尘埃道未甞于名利两相忘怀六洞丹霞客诵三清紫府章里采莲歌达旦轮明月桂飘香高公子还相觅得山中好酒浆牛郎织女会佳期下弹琴又赋诗

寺静惟闻钟鼓響停始觉星斗移

多少黄冠归道观幾而作尽忘机

几时得到桃源洞彼仙人下象棋牛郎织女会佳期，月下弹琴又赋诗。

寺静惟闻钟鼓響，音停始觉星斗移。

多少黄冠归道观，见幾而作尽忘机。

几时得到桃源洞，同彼仙人下象棋。诗情画意传“密语”王先生：来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。王先生：来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。隐写术（信息隐藏）的另外一些例子悠扬琴声奏响“进军号角”显微镜里传递情报魔术般的密写术网络与数字幽灵量子技术隐形传递信息隐写术的优点☆能够被某些人使用而不容易被发现他们间在进行秘密通信☆加密则很容易被发现谁与谁在进行秘密通信，这种发现本身可能具有某种意义或作用隐写术的缺点☆形式简单但构造费时，要求有大量的开销来隐藏相对较少的信息☆一旦该系统的构造方法被发现，就会变得完全没有价值☆隐写术一般无稳健性§3-2代替就是明文中的字母由其他字母、数字或符号所取代的一种方法具体的代替方案称之为密钥。代替密码体制

加密：解密：著名的Caesar密码举例设明文为：China，对应的数字为：278130。加密:C：对应着字母F；

h：对应着字母K；

i：对应着字母L；

n：对应着字母Q；

a：对应着字母D。所以明文“China”基于Caesar密码被加密为“FKLQD”。解密：F：对应着C；

K：对应着H；

L：对应着I；

Q：对应着N；

D：对应着A。即“FKLQD”经Caesar密码解密恢复为“CHINA”(不区分大小写)Caesar密码的特点属于单字母简单替换密码已知加密与解密算法：

C=E(P)=(P+3)mod26P=D(C)=(C-3)mod26明文语言集已知且易于识别结构过于简单代替密码的实现方法分类单表代替密码

使用密钥的单表代替加密仿射加密

多表代替密码

Playfair密码Hill密码Vigenere密码使用密钥的单表代替加密设密钥为：spectacular。明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ对应的密文：spectaulrbdfghijkmnoqvwxyz如果明文为“China”，则对应的密文为：elrhs

仿射加密

加密：解密：仿射加密要求，,否则就褪化为。故密钥空间大小为:仿射加密的例子密钥：，7-1(mod26)=15加密函数：解密函数：设明文：China,首先转换为数字：2,7,8,13,0加密：“China”经仿射加密变换成“RAHQD”

解密：原始消息“China”得到恢复单表代替密码的特点：密钥量很小，不能抵抗穷尽搜索攻击没有将明文字母出现的概率掩藏起来，很容易受到频率分析的攻击频率分析攻击常见的三字母组合：THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH等。

常见的双字母组合：TH、HE、IN、ER、RE、AN、ON、EN、AT；频率分析攻击的一般方法：第一步：对密文中出现的各个字母进行出现的频率统计第二步：根据密文中出现的各个字母的频率，和英语字母标准频率进行对比分析，做出假设，推论加密所用的公式第三步：证实上述假设或继续作其他假设Playfair密码

基于一个5×5字母矩阵该矩阵使用一个关键词（密钥）来构造构造方法：从左至右，从上至下依次填入关键词的字母（去除重复的字母），然后再以字母表顺序依次填入其他的字母。字母I和J被算作一个字母加密方法：P1、P2同行：对应的C1和C2分别是紧靠P1、P2右端的字母。其中第一列被看作是最后一列的右方。（解密时反向）P1、P2同列：对应的C1和C2分别是紧靠P1、P2下方的字母。其中第一行看作是最后一行的下方。（解密时反向）P1、P2不同行、不同列：C1和C2是由P1和P2确定的矩形的其它两角的字母，并且C1和P1、C2和P2同行。（解密时处理方法相同）P1＝P2：则插入一个字母于重复字母之间，并用前述方法处理若明文字母数为奇数时：则在明文的末端添加某个事先约定的字母作为填充例子：密钥是：PLAYFAIR

IS

A

DIGRAM

CIPHER。如果明文是：P＝playfaircipher明文两个一组：playfaircipher对应密文为:

LAYFPYRSMRAMCDPlayfair密码的特点：有676种双字母组合，因此识别各种双字母组合要困难得多各个字母组的频率要比单字母呈现出大得多的范围，使得频率分析困难得多Playfair密码仍然使许多明文语言的结构保存完好，使得密码分析者能够利用Hill密码

明文：密文：其中，

……矩阵形式：例子：P＝HILL，对应：7，8，11，11。密钥：加密：＝（9,8,8,24）＝（JIIY）

解密：＝（7,8,11,11）＝（HILL）Hill密码的特点：Hill密码完全隐藏了单字母的频率字母和数字的对应可以改成其它方案，使得更不容易攻击成功能比较好地抵抗频率法的分析，对抗仅有密文的攻击强度较高易受已知明文攻击Vigenere密码

例子p＝datasecurity,k=best首先将明文分解成长为4的序列：

datasecurity密文：＝EELT

TIUN

SMLR威胁代替密码的因素：频率分析考虑最可能的字母及单词重复结构分析持久性、组织性、创造性和运气明文已知且易于识别§3-3换位换位就是重新排列消息中的字母，以便打破密文的结构特性典型处理方法：将明文按行写在一张格纸上，然后再按列的方式读出结果为了增加变换的复杂性，可以设定读出列的不同次序（即密钥）例子：明文：cryptographyisanappliedscience密钥：encry密文：yripdncohniirgyaeepaspsctpalce第四章密码学的数学引论学习要点：了解数论、群论、有限域理论的基本概念了解模运算的基本方法了解欧几里德算法、费马定理、欧拉定理、中国剩余定理了解群的性质了解有限域中的计算方法1、除数(因子)的概念：

设z为由全体整数而构成的集合，若b≠0且

使得a=mb,此时称b整除a.记为b∣a,还称b为a的除数(因子).注:若a=mb+r且0<r<b,此时b不整除a,记为

2、素数(质数)的概念:

整数p>1被称为素数是指p的因子仅有1,-1,p,-p。§4－1数论§算术基本定理：任何一个不等于0的正整数a都可以写成唯一的表达式a＝P1α1P2α2…Ptαt，这里P1＜P2＜P3…＜Pt是素数，其中αi>0§最大公约数：若a,b,c∈z，如果c∣a，c∣b，称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足d是a和b的公约数。对a和b的任何一个公约数c有c∣d。注：1*.等价的定义形式是：

gcd（a,b）＝max{k∣k∣a且k∣b}2*．若gcd（a,b）=1，称a与b是互素的。带余除法：

a∈z,>0，可找出两个唯一确定的整数q和r,

使a=qm+r,0<=r<m,q和r这两个数分别称为以m去除a所得到的商数和余数。(若r=0则m∣a）整数同余：定义：如果amodm=bmodm，则称整数a模正整数m同余于整数b，并写a≡b（modm）是指m∣（a－b）,m称为模数。

注：1*.m∣a-b

a=q1m+r,b=q2m+r即a和b分别除以m有相同的余数。“同余”二字的来源就在于此。二、模算术2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质：

自反性：对任意整数a有：a≡a（modm）

对称性：如果a≡b(modm)，则b≡a（modm）

传递性：如果a≡b(modm）b≡c（modm），则a≡c(modm)

于是，全体整数集合z可按模m（m>1）分成一些两两不交的等价类。3*.对于某个固定模m的同余式可以象普通的等式那样相加、相减和相乘，可结合：(1)[a(modm)±b(modm)]modm=(a±b)(modm)(2)[a(modm)*b(modm)]modm=a*b(modm)(3)[(a*b)modm+(a*c)modm]=[a*(b+c)]modm

例子.通过同余式演算证明：（1）560－1是56的倍数（2）223－1是47的倍数。解： 注意53=125≡13(mod56)

于是有56≡169≡1(mod56)

对同余式的两边同时升到10次幂， 即有56∣560-1。同理,注意到26=64≡17(mod47), 于是223=(26)3·25=(26·26)26·25

≡289*(17)*(32)mod47≡7*17*32(mod47)≡25*32(mod47)≡1(mod47)

于是有47∣223-1定理：(消去律)对于ab≡ac（modm）来说，若gcd(a,m)＝1则b≡c(modm)例如1：附加条件不满足的情况6×3=18≡2mod86×7=42≡2mod8但3≡7mod8例如2：附加条件满足的情况

5×3＝15≡7mod85×11=55≡7mod83≡11mod8原因：模m的乘法运算返回的结果是0到m-1之间的数，如果乘数a和模数m有除1以外的共同因子时将不会产生完整的余数集合。Z801234567乘以606121824303642模8后的余数06420642Z801234567乘以505101520253035模8后的余数05274163扩展的欧几里德算法描述ExtendedEUCLID(d,f)：1）(X1,X2,X3)←(1,0,f)；(Y1,Y2,Y3)←(0,1,d)2）如果Y3=0返回X3=gcd(d,f)；无逆元3）如果Y3=1返回Y3=gcd(d,f)；Y2=d-1modf4）Q=max_int(X3/Y3)5）(T1,T2,T3)←(X1-Q·Y1,X2-Q·Y2,X3-Q·Y3)6）(X1,X2,X3)←(Y1,Y2,Y3)7）(Y1,Y2,Y3)←(T1,T2,T3)8）回到2）例：求gcd(20,117)和20-1mod117QX1X2X3Y1（T1）Y2（T2）Y3(T3)-101170120501201-51711-517-1635-1636-35216-352-7411=gcdFormat定理§

Format定理：如果p是素数并且a是不能被p整除的正整数,那么，ap-1≡1(modp)

Format定理的另一种形式：对gcd（a，p）＝1有ap≡a(modp)例子：a=7,p=19,求ap-1modp解：72=49≡11mod1974≡121mod19≡7mod1978≡49mod19≡11mod19716≡121mod19≡7mod19ap-1=718=716×72≡7×11mod19≡1mod19例子：比24小而与24互素的正整数为：1、5、7、11、13、17、19、23。故

这12个数是：｛1,2,4,5,8,10,11,13,16,17,19,20｝欧拉定理（Euler）（文字表述）：若整数a与整数n互素，则aφ(n)≡1(modn)注：1*.n＝p时，有ap-1≡1(modp)为Format定理！2*.易见aφ(n)+1≡a(modn)阶与本原元am=1modn，如果a与n互素，则至少有一个整数m（如m=phi(n)）满足这一方程，称满足方程的最小正整数m为模n下a的阶。如果a的阶m=phi（n），则称a为n的本原元。本原元并不一定唯一并非所有的整数都有本原元，只有以下形式的整数才有本原元：2,4,pa,2pa（a为整数，p为奇素数）例子：n＝19，a＝3，在mod19下的幂分别为3、9、8、5、15、7、2、6、18、16、10、11、14、4、12、17、13和1。即3的阶为18＝phi(19)，所以3为19的本原元。中国剩余定理例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？答曰：二十三。23≡2*70+3*21+2*15(mod105)（口诀：三人同行七十稀，五树梅花廿一枝，

七子团圆月正半，除百零五便得知。）问，70，21，15如何得到的？原问题为：求解同余方程组注意：若x0为上述同余方程组的解，则x0

=x0+105*k(k∈z)也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组(1) (2) (3) 的特殊解

=? =? =?以方程（1）为对象，相当于解一个这样的同余方程35y≡1(mod3)，为什么呢？原因是，从（1）的模数及条件知，x应同时是5和7的倍数，即应是35的倍数，于是可以假设x＝35y有：35y≡1(mod3)相当于2y≡1(mod)3

解出y=2（mod3）

于是x35*270(mod105)类似地得到（2）、（3）方程的模105的解21、15。

于是有：

得

中国剩余定理：设自然数m1,m2,…mr两两互素，并记M=m1m2…mr，b1…..br表示r个整数，则同余方程组（A）在模M同余的意义下有唯一解。证明：M=m1m2…mr，令Mj=M/mj=m1m2…mj-1mj+1…mr求yj使：Mjyj≡1modmjj=1,2,….r由于（Mj,mj)=1，所以yj是存在的。令：x0≡b1M1y1+b2M2y2+…+brMryrmodM(B)

可证明x0便是（A）式的解。为证明这一点，注意j=h时mh|Mj。故Mj≡0modmh,即x0中各项除第h项外，其余都模mh同余0。又Mhyh≡1modmh,所以：

X0≡bhMhyhmodmh≡bhmodmh。即满足(A)式，x0是其解。下面证明x0是模M的唯一解。如若不然，设x1和x2是（A）式模M的两个解，则有：x1≡x2≡bjmodmj(j=1…r)那么，x1-x2≡0modmj,即mj|(x1-x2)（j=1…r)因此，M｜（x1-x2),即x1-x2≡0modM所以x1，x2是模M的相同解，从而证明了对于模M式（A）的解是唯一的。

例如：x≡1mod2x≡2mod3x≡3mod5解：M=2×3×5=30M1=15,M2=10,M3=615y1≡1mod2,y1=110y2≡1mod3,y2=16y3≡1mod5,y3=1所以,x=1×15×1+2×10×1+3×6×1=53≡23mod30§4－2群论群的概念是由一个非空集合G组成，在集合G中定义了一个二元运算符“·”，并满足以下性质的代数系统，记为｛G,·｝

交换群：有限群无限群有限群的阶循环群循环群的生成元群的性质群中的单位元是唯一的群中每一个元素的逆元是唯一的(消去律)对任意的，如果，或，则§4－3有限域理论

域的概念域是由一个非空集合F组成，在集合F中定义了两个二元运算符：“+”和“·”，并满足：域记为｛F,+,·}

两个定义：有限域有限域的阶域的实质：域是一个可以在其上进行加法、减法、乘法和除法运算而结果不会超出域的集合。如有理数集合、实数集合、复数集合都是域，但整数集合不是有限域的两个定理密码学常用素域GF(p)或阶为2m的域GF(2m)GF(p)有限域中的计算

生成元与逆元生成元可证明：在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次方幂的形式，g称为GF(p)的生成元逆元

生成元的例子有限域GF（23），5是GF（23）的生成元50＝151＝552＝253＝1054＝455＝2056＝857＝1758＝1659＝11510＝9511＝22512＝18513＝21514＝13515＝19516＝3517＝15518＝6519＝7520＝12521＝14522＝1GF（2m)域生成元与逆元生成元：逆元例子：GF（24）取：GF（24）的元素：（0000）(0001)(0010)(0011)(0100)(0101)(0110)(0111)(1000)(1001)(1010)(1011)(1100)(1101)(1110)(1111)例子（续）生成元为：a=x第五章对称密码体制学习要点：了解对称密码体制的基本概念了解分组密码原理了解分组密码操作模式了解DES和AES两种典型的对称密码算法§5－1分组密码对分组密码算法的要求分组长度足够大密钥量足够大

密码变换足够复杂

分组密码原理

扩散就是将每一位明文的影响尽可能迅速地作用到较多的输出密文位中去，以便隐藏明文的统计特性。混乱是指密文和明文之间的统计特性关系尽可能地复杂化。乘积密码指依次使用两个或两个以上的基本密码，所得结果的密码强度将强于所有单个密码的强度Feistel结构的实现依赖于参数：分组长度密钥长度迭代轮数子密钥生成算法轮函数分组密码的操作模式

电子密码本（ECB）模式密码分组链接（CBC）模式计数器（CRT）模式输出反馈（OFB）模式密码反馈（CFB）模式ECB模式ECB模式的优缺点模式操作简单明文中的重复内容将在密文中表现出来，特别对于图像数据和明文变化较少的数据适于短报文的加密传递CBC模式CBC模式的特点同一个明文分组重复出现时产生不同的密文分组加密函数的输入是当前的明文分组和前一个密文分组的异或；对每个分组使用相同的密钥。将明文分组序列的处理连接起来了。每个明文分组的加密函数的输入与明文分组之间不再有固定的关系有助于将CBC模式用于加密长消息CTR模式CTR模式的特点使用与明文分组规模相同的计数器长度处理效率高（并行处理）预处理可以极大地提高吞吐量可以随机地对任意一个密文分组进行解密处理，对该密文分组的处理与其它密文无关实现的简单性适于对实时性和速度要求较高的场合OFB模式CFB模式影响密码操作模式选择的因素安全性高效性所能实现的功能§5－2数据加密标准（DES）DES的加密处理略图S1盒的定义循环左移位

轮序12345678910111213141516移位数11222222122222213DES的优、缺点优点：密钥长度增加到112位或168位，可以有效克服穷举搜索攻击；相对于DES，增强了抗差分分析和线性分析的能力；具备继续使用现有的DES实现的可能。缺点：处理速度相对较慢，特别是对于软件实现。明文分组的长度仍为64位，就效率和安全性而言，与密钥的增长不相匹配。§5－3高级加密标准（AES）1997年9月12日：美国NIST提出征集该算法的公告1998年8月20日：NIST召开了第一次候选大会，并公布了15个候选算法1999年3月22日：NIST从15个候选算法中公布了5个进入第二轮选择：MARS，RC6，Rijindael，SERPENT和Twofish2000年10月2日：以安全性、性能、大小、实现特性为标准而最终选定了Rijndael算法2001年：正式发布AES标准Rijndael算法是由两位比利时的密码专家发明的，它很快而且所需的内存不多，这个算法非常可靠Rijndael算法的设计策略是宽轨迹策略,是针对差分分析和线性分析提出来的，是一个分组迭代密码，具有可变的分组长度和密钥长度

Rijndael汇聚了安全性能、效率、可实现性和灵活性等优点破译时间：AES的基本运算

字节代替SubBytes列混淆MixColumns轮密钥加AddRoundKey行移位ShiftRows

“三代替、一换位”有限域GF（28）上的字节运算

加法“+”：字节的按位异或运算（）+（）＝（）其中，＝＋，i＝0，1,…,7。乘法“•”

是普通多项式乘法，但系数运算可看作比特的乘法和异或运算，即看作域{0,1}上的运算例子（01110011）（10010101）所以，（01110011）（10010101）＝（01110000）

乘法的实际计算方法讨论再看前面的例子（01110011）•（10010101）＝（01110000），即（73）•（95）＝（70）

（01110011）•（10010101）＝[(00000001)+(00000010)+(00010000)+(00100000)+(01000000)]•(10010101）＝(00000001)•(10010101）⊕(00000010)•(10010101）⊕(00010000)•(10010101）⊕(00100000)•(10010101）⊕(01000000)•(10010101）＝(10010101)⊕[(00101010)⊕(00011011)]⊕(00010000)•(10010101）⊕(00100000)•(10010101）⊕(01000000)•(10010101）＝(10010101)⊕(00110001)⊕[(10001000)⊕(00011011)]⊕(00100000)•(10010101）⊕(01000000)•(10010101）＝(10010101)⊕(00110001)⊕(10010011)⊕[(00100110)⊕(00011011)]⊕(01000000)•(10010101）＝(10010101)⊕(00110001)⊕(10010011)⊕(00111101)⊕(01111010)＝(01110000)＝（70）基于表操作的有限域乘法运算例子查对数表：{73}={03}(15)，{95}={03}(16)则{73}•{95}={03}(15)•{03}(15)

＝｛03｝(15)＋（16）＝｛03｝(2B)

查反对数表：｛03｝(2B)

表示的域元素为｛70｝说明{73}•{95}＝｛70｝

对数表－{xy}={03}L(xy)

L(xy)y0123456789abcdefx000190132021ac64bc71b6833eedf0316404e00e348d81ef4c7108c8f8691cc127dc21db5f9b9276a4de4a6729ac909783652f8a05210fe12412f082453593da8e4968fdbbd36d0ce94135cd2f140468338566ddfd30bf068b62b325e2982288911067e6e48c3a3b61e423a6b2854fa853dba72b790a159b9f5eca4ed4ace5f373a7578af58a850f4ead6744faee9d5e7e6ade892cd7757aeb160bf559cb5fb09ca951a0a7f0cf66f17c449ecd8431f2da4767bb7bccbb3e5afb60b1863b52a16caa55299dc97b2879061bedcfcbc95cfcd373f5bd1d5339843c41a26d47142a9e5d56f2d3abe441192d923202e89b47cb8267799e3a5f674aeddec531fe180d638c80c0f77007反对数表－域元素{E}={03}(xy)

E(xy)y0123456789abcdefx00103050f113355ff1a2e7296a1f8133515fe13848d87395a4f702060a1e2266aa2e5345ce43759eb266abed97090abe631353f5040c143c44cc4fd168b8d36eb2cd44cd467a9e03b4dd762a6f108182878885839eb9d06bbddc7f8198b3ce49db769a6b5c457f9103050f00b1d2769bbd661a37fe192b7d8792adec2f7193aee92060a08fb163a4ed26db7c25de73256fa153f419c35ee23d47c940c05bed2c749cbfda75a9fbad564acef2a7e829dbcdf7a8e8980b9bb6c158e82365afea256fb1c843c554cfc1f2163a5f407091b2d7799b0cb46cad45cf4ade798b8691a8e33e42c651f30ee12365aee297b8d8c8f8a8594a7f20d17f394bdd7c8497a2fd1c246cb4c752f601查表求任意域元素的逆方法：除了｛00｝外所有的域元素都有逆

如果，则，或用十六进制表示为：例子查对数表：{95}={03}(16)其逆为：{95-1}={03}(ff)-(16)={03}(e9)查反对数表：{03}(e9)

＝{8a}

故{95}的逆为{8a}

字运算—系数在有限域GF(28)上的多项式运算

例子S盒变换—SubBytes是一个基于S盒的非线性置换映射方法：把输入字节的高4位作为S盒的行值，低4位作为列值，然后取出S盒中对应行和列的元素作为输出SubBytes变换的两个步骤步一：把S盒中的每个字节映射为它在有限域GF(28)中的乘法逆步二：例子“95”的乘法逆为“8a”，二进制表示为“10001010”结果为“00101010”，十六进制表示为“2a”列混合变换－MixColumns

行移位运算－ShiftRows

轮密钥加变换－AddRoundKey

AES的解密

InvCipher(bytein[4*Nb],byteout[4*Nb],wordw[Nb*(Nr+1)])beginbytestate[4,Nb]state=inAddRoundKey(state,w[Nr*Nb,(Nr+1)*Nb-1])forround=Nr-1step-1downto1InvShiftRows(state)

InvSubBytes(state)

AddRoundKey(state,w[round*Nb,(round+1)*Nb-1])InvMixColumns(state)

endforInvShiftRows(state)InvSubBytes(state)AddRoundKey(state,w[0,Nb-1])out=stateend逆字节代替－InvSubBytes

逆S盒y0123456789abcdefx052096ad53036a538bf40a39e81f3d7fb17ce339829b2fff87348e4344c4dee9cb2547b9432a6c2233dee4c950b42fac34e3082ea16628d924b2765ba2496d8bd125472f8f66486689816d4a45ccc5d65b69256c704850fdedb9da5e154657a78d9d84690d8ab008cbcd30af7e45805b8b345067d02c1e8fca3f0f02c1afbd0301138a6b83a9111414f67dcea97f2cfcef0b4e673996ac7422e7ad3585e2f937e81c75df6ea47f11a711d29c5896fb7620eaa18be1bbfc563e4bc6d279209adbc0fe78cd5af4c1fdda8338807c731b11210592780ec5fd60517fa919b54a0d2de57a9f93c99cefea0e03b4dae2af5b0c8ebbb3c83539961f172b047eba77d626e169146355210c7d仿射变换的逆变换例子输入：“2a”，二进制表示“00101010”仿射结果为“10001010”，十六进制表示为“8a”再计算乘法逆：“8a”在GF（28）中的乘法逆为“95”逆行移位－InvShiftRows

与行移位相反，逆行移位将态State的后三行按相反的方向进行移位操作逆列混淆－InvMixColumns

S

S‘验证：0E•47⊕0B•37⊕0D•94⊕09•ED=870E•47=（00001110）•（01000111）＝[(00000010）⊕(00000100)⊕(00001000))•（01000111）=(00000010)•（01000111）⊕(00000100)•（01000111）⊕(00001000)•01000111）=(10001110)⊕[(00011100)⊕(00011011)]⊕(00001000)•（01000111）=(10001110)⊕(00000111)⊕(00001110)=(10000111)0B•37=(00001011)•(00110111)=[(00000001)⊕(00000010)⊕(00001000)]•(00110111)=(00110111)⊕(01101110)⊕[(10111000)⊕(00011011)]=(11111010)0D•94=(00001101)•(10010100)=[(0000001)⊕(00000100)⊕(00001000)]•(10010100)=(10010100)⊕(01100110)⊕(11001100)=(00111110)09•ED=(00001001)•(11101101)=[(00000001)⊕(00001000)]•(11101101)=(11101101)⊕(00101001)=(11000100)0E•47⊕0B•37⊕0D•94⊕09•ED=(10000111)⊕(11111010)⊕(00111110)⊕(11000100)=(10000111)=87（十六进制表示）密钥扩展

根据输入密钥得到w[0]、w[1]、w[2]、w[3]，作为扩展密钥的基础扩展密钥：对w数组中下标不为4的倍数的元素：w[i]=w[i-1]⊕w[i-4](i不为4的倍数)

对w数组中下标为4的倍数的元素：将一个字的四个字节循环左移一个字节，即

[b0,b1,b2,b3]－＞[b1,b2,b3,b0]基于S盒对输入字中的每个字节进行S代替将步骤1和步骤2的结果再与轮常量Rcon[i]相异或前10个轮常数Rcon[i]

Rcon[i]=(RC[i],‘00',‘00',‘00')RC[0]=‘01’RC[i]=2•(RC[i-1])

第6章非对称密码体制学习要点：了解非对称密码体制的提出背景、基本思想了解非对称密码体制的基本应用方向了解三种典型的公钥密码体制

DH密钥交换算法RSAECC§6－1概述问题的提出：

密钥管理困难传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。如:n=100时C(100,2)=4,995n=5000时C(5000,2)=12,497,500陌生人间的保密通信问题

数字签名的问题传统加密算法无法实现抗抵赖的需求公钥密码体制公钥密码又称为双钥密码、非对称密码公钥密码体制提出的标志性文献：W.DiffieandM.E.Hellman,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654对公钥密码体制的要求（1）参与方B容易通过计算产生一对密钥（公开密钥KUb和私有密钥KRb）。（2）在知道公开密钥和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文：C＝EKUb（M）（3）接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文：M＝DKRb（C）＝DKRb（EKUb（M））（4）敌对方即使知道公开密钥KUb，要确定私有密钥KRb在计算上是不可行的。（5）敌对方即使知道公开密钥KUb和密文C，要想恢复原来的报文M在计算上也是不可行的。（6）加密和解密函数可以以两个次序中的任何一个来使用:

M＝DKRb（EKUb（M））M=EKUb(DKRb(M))注：1*.仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，δ称为陷门信息。

2*.当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开密钥，记为Pk。f函数的设计者将δ保密，用作解密密钥，此时δ称为秘密密钥，记为Sk。由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk，他自然可以解出x=f-1(y)。

3*.单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。是满足下列条件的函数f：(1)给定x，计算y=f(x)是容易的(2)给定y,计算x使y=f(x)是困难的(3)存在δ，已知δ时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的陷门单向函数公开密钥密码系统的分析方法强行攻击(对密钥)。公开密钥算法本身可能被攻破。可能报文攻击(对报文本身的强行攻击)。公钥密码系统的应用类型加密/解密数字签名会话密钥交换例子：简单数字签名例子续：安全数字签名一个素数q和一个整数a（均公开），a是q的一个原根用户A选择一个随机数XA<q，并计算类似地，用户B选择一个随机数XB<q,并计算每一方都对X的值保密存放而使得Y的值对于另一方可以公开得到用户A计算密钥：用户B计算密钥：双方以K作为加、解密密钥，以对称密钥算法进行保密通信§6－2

Diffie-Hellman密钥交换算法原根（本原元）对于一个素数q，如果数值：，……，是各不相同的整数，并且以某种排列方式组成了从1到q-1的所有整数则称整数a是素数q的一个原根DH例子素数q=97,它的一个本原元a=5A和B分别选择随机数Xa=36和Xb=58A计算公开密钥：Ya=536mod97=50mod97B计算公开密钥：Yb=558mod97=44mod97A计算会话密钥：K=4436mod97=75mod97B计算会话密钥：K=5058mod97=75mod97§6－3

RSA由Rivest,Shamir和Adleman在1978年提出来的数学基础:Euler定理，并建立在大整数因子分解的困难性之上明文空间P＝密文空间C=Zn密钥的生成选择互异素数p,q，计算n=p*q,

(n)=(p-1)(q-1),选择整数e使(

(n),e)=1,1<e<

(n),计算d,使d=e-1mod

(n)公钥Pk={e,n}私钥Sk={d,n}加密(用e,n)明文：M<n密文：C=Me(modn)解密(用d,n)

密文：C明文：M=Cd（modn)RSA密码体制描述若Bob选择了p=7和q＝17则n=119,

(n)=6×16＝96＝25×3，一个正整数e能用作加密指数，当且仅当e不能被2，3所整除假设Bob选择e=5，那么用辗转相除法将求得：d=e-1

77(mod96)Bob的解密密钥d={77,119}，公开｛5,119｝现假设Alice想发送明文19给Bob注：RSA的安全性基于：加密函数ek(x)=xe(modn)是一个单向函数，所以对敌人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知

(n)=(p-1)(q-1)，从而解出解密私钥dRSA的例子步骤：Bob为实现者Bob寻找出两个大素数p和qBob计算出n=pq和

(n)=(p-1)(q-1).Bob选择一个随机数e(0<e<

(n))，满足（e，

(n)）＝1Bob使用辗转相除法计算d=e-1(mod

(n))Bob在目录中公开n和e作为她的公开钥密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的d。RSA密码体制描述要求：若使RSA安全，p与q必为足够大的素数，使分析者没有办法在有效时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常p和q的长度相同；(2)p-1和q-1分别含有大素因子p1和q1(3)gcd(p1-1,q1-1)应该很小。为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定e＝216＋1，ISO/IEC9796中甚至允许取e＝3。这时加密速度一般比解密速度快10倍以上。RSA密钥的生成例：p=47,q=61,(n)=(47-1)(61-1)=2760时，SK=167是否为秘密密钥的候选者？

用欧氏算法计算：gcd(2760,167)=1即可证明。QX1X2X3Y1Y2Y3－1027600116716011671－168811－1688－117791－117792－33982－339－1728171－17281719－3142319－3142－7412231用RSA算法加密与解密的过程：例：明文=“RSAALGORITHM”(1)明文用数字表示空白=00，A=01,B=02,…,Z=26(两位十进制数表示)

1819010001120715180920081300(2)利用加密变换公式C=mPKmodr,即C=18191223mod2867=2756 PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223(mod2867) =18191024·1819128·181964·18194·18192·18191(mod2867) =27562756200105420669234704081815选择两个大素数p和q，通常要求每个均大于10100。计算n＝pｘq和z＝(p－1)(q－1)。选择一与z互素的数、令其为d。找到一个e满足e×d＝1(modz)。选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0<m<n。加密P时，计算C＝Pe(modn)，解密C时计算P＝Cd(modn)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开(e,n)，为实现解密需要(d,n)。RSA算法归纳如何计算abmodn？如何判定一个给定的整数是素数？如何找到足够大的素数p和q?问题……

要点1：(axb)modn=[(amodn)x(bmodn)]modn]

要点2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的问题：am m的二进制表示为bkbk-1…b0,

则计算ammodnammodn=[

a(2i)]modn =

[a(2i)modn]bi

0bi

0如何计算abmodn？快速取模指数算法计算abmodnc0;d1forikdownto0doc2×cd(d×d)modnifbi=1thencc+1d(d×a)modnreturnd快速取模指数算法：例子i9876543210bi1000110000c=01248173570140280560d=17491575261602412981666717560mod561=1MillerandRabin,WITNESS算法

WITNESS(a,n)判定n是否为素数，a是某个小于n的整数1.令bkbk-1…b0

为(n-1)的二进制表示，2.d13.forikdownto04. doxd5. d(dd)modn6. ifd=1andx1andxn-17. thenreturnTRUE8. ifbi=19. thend(da)modn10.ifd111.thenreturnTRUE12.returnFALSE

返回值：TRUE:n一定不是素数FALSE:n可能是素数应用：随机选择a<n,计算s次，如果每次都返回FALSE，则这时n是素数的概率为

(1-1/2s)如何判定一个给定的整数是素数？1.随机选一个奇数n(伪随机数发生器)2.随机选择一个整数a<n3.执行概率素数判定测试,如果n未测试通过,则拒绝数值n,转向步骤14.如果n已通过足够的测试,则接受n,否则转向步骤2;说明：①随机选取大约用

ln(N)/2的次数，如ln(2200)/2=70②好在生成密钥对时才用到，慢一点还可忍受。 ③确定素数p和q以后，只需选取e,满足gcd(e,(n))=1,计算d=e-1mod(n)（扩展的欧拉算法）如何找到足够大的素数p和q?p和q在长度上应仅差几个数位，即p和q应是1075

到10100（p-1）和（q-1）都应包含一个较大的素数因子gcd(p-1,q-1)应比较小如果e<n且d<n1/4,则d可以很容易确定建议－数字签名方案：一个签名方案是由签署算法与验证算法两部分构成。可由五元关系组（M,A,K,S,V）来描述：(1)M是由一切可能消息所构成的有限集合；(