现代密码学基础

现代密码学基础徐江峰郑州大学信息工程学院E-mail:jfxu@2008年5月绪论古典密码学密码学信息论基础对称加密技术非对称加密技术数字签名Hash函数身份认证密钥管理课程内容参考文献应用密码学－－协议、算法与C源程序

(美)BruceSchneier

著，吴世忠、祝世雄、张文政译密码编码和密码分析－－原理与方法

(德)F.L.Bauer著，吴世忠、宋晓龙、李守鹏译密码编码学与网络安全－－原理与实践

(美)WilliamStallings著刘玉珍、王丽娜、傅建明译计算机密码学卢开澄编著现代密码学基础章照止主编

绪论古典密码学密码学信息论基础对称加密技术非对称加密技术数字签名Hash函数身份认证密钥管理课程内容密码学发展历史密码学中的术语绪论密码学发展历史1949年之前密码学是一门艺术1949～1975年密码学成为科学1976年以后密码学的新方向——公钥密码学第1阶段－古典密码密码学还不是科学,而是艺术出现一些密码算法和加密设备密码算法的基本手段出现，针对的是字符简单的密码分析手段出现主要特点：数据的安全基于算法的保密Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。第1阶段—古典密码20世纪早期密码机Kerckhoff加密原则

1883年Kerckhoff第一次明确提出了编码的原则,该原则已得到普遍承认，成为传统密码和现代密码的分界线。计算机使得基于复杂计算的密码成为可能相关技术的发展1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson实验室的HorstFeistel等几篇技术报告主要特点：数据的安全基于密钥而不是算法的保密

第2阶段1949~19751976年：Diffie&Hellman

的

“NewDirectionsinCryptography”提出了不对称密钥密1977年Rivest,Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能第3阶段1976~密码学发展历史密码学中的术语绪论信息传递的一般问题信源、信道、信宿攻击的种类：中断（Interruption)（干扰）截取（Interception)(侦听）修改（Modification）伪造（Fabrication)角色：通信双方、可信第三方、不可信第三方介质：软件、硬件、数据数据的性质可用性(Availability)：保证信息和信息系统确实为授权者所用，防止由于计算机病毒或其它人为因素造成系统的拒绝服务，或者为非法者所用。保密性(Confidentiality)：保证信息不泄漏给未经授权的人。完整性(Integrity)：防止信息被未经授权的篡改。真实性(Authenticity)：保证信息不是伪造的。不可否认性:保证信息行为人不能过后否认自己的行动。被动攻击截取获取消息内容流量分析主动攻击中断修改伪造破坏可用性破坏完整性破坏真实性攻击分类破坏机密性安全性攻击举例获取对信息的非授权访问；冒充别的用户以推卸责任或使用他人的许可证，以达到以下目的：制造欺诈信息篡改合法信息使用欺诈性的身份来获得非授权访问欺诈性地对交易进行认证或签注抵赖欺诈引起的责任；安全性攻击举例（续）声称收到了别的用户的信息，其实这是自己伪造的；声称已经将消息发送给接收方，而当时根本没有发送；否认收到的信息或接收信息的时间；扩大他的合法权限；未经授权修改他人的权限；将自身作为中继插入到其他用户的通信线路中；阻止其他用户间的通信，特别是通过秘密介入，使合法通信被拒绝．密码学(Cryptology):是研究信息系统安全保密的科学。密码编码学(Cryptography):主要研究对信息进行编码，实现对信息的隐蔽。密码分析学(Cryptanalysis):主要研究加密消息的破译或消息的伪造。密码学概念EncryptDecryptPlaintextCiphertextPlaintextAliceBobEveInsecureChannelC=E(P)P=D(C)Emustbeinvertible加密通信过程明文(Plaintext)

：发送者要传递给接收者的源信息，消息的初始形式。密文(Cyphertext)

：明文加密后的表现形式，是发送者在信道上传递给接收者的信息。密钥(Key)：是加密和解密时用到的数据，只有加密者和解密者知道。加密(Encrypt)：把明文转换成密文的过程，C=E(P)。解密(Decrypt)：把密文转换成明文的过程，P=D(C)。破译：攻击者利用各种手段，对加密密钥或算法进行破解。密码学术语密码体系是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）（4）任意k∈K，有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x))=x

，这里x∈P。密码体系形式化描述

Kerckhoff加密原则SecurityshoulddependonlyonthekeyDon’tassumeenemywon’tknowalgorithmSecuritythroughobscurityisn’tLookathistoryofexamplesBettertohavescrutinybyopenexperts“Theenemyknowsthesystembeingused.”ClaudeShannon密码分析试图破译单条消息试图识别加密的消息格式，以便借助直接的解密算法破译后续的消息试图找到加密算法中的普遍缺陷（无须截取任何消息）密码分析的条件与工具已知加密算法截取到明文、密文中已知或推测的数据项数学或统计工具和技术语言特性计算机技巧与运气密码分析类型加密方案的安全性无条件安全(unconditionallysecure)：无论提供的密文有多少，如果由一个加密方案产生的密文中包含的信息不足以唯一地决定对应的明文除了一次一密(one-time-pad)的方案外，没有无条件安全的算法计算上安全(computationallysecure):破译的成本超过加密信息的价值破译的时间超过密文信息有效生命周期攻击的复杂性分析数据复杂性（datacomplexity）用作攻击输入所需要的数据处理复杂性（processingcomplexity）完成攻击所需要的时间存储需求（storagerequirement）进行攻击所需要的数据量穷尽攻击穷尽攻击(exhaustivekeysearch)：也称为穷举攻击或蛮力攻击(bruteforceattack)．攻击者对一条密文尝试所有可能的密钥，直到把它转化为可读的有意义的明文．平均而言，获得成功至少要常使所有可能密钥的一半．差分分析（differentialcryptanalysis）是一种较新的攻击方法。密钥搜索所需平均时间1995年硬件穷举攻击的平均时间和金钱估计花费的金钱（美元）密钥长度（位）4056648011212810万2秒35小时1年70000年年年100万0.2秒3.5小时37天7000年年年1000万0.02秒21分钟4天700年年年1亿2毫秒2分钟9小时70年年年10亿0.2毫秒13秒1小时7年年年绪论古典密码学密码学信息论基础对称加密技术非对称加密技术数字签名Hash函数身份认证密钥管理课程内容替代(SubstitutionCipher)

置换(PermutationCipher)古典密码学也称为代换，就是将明文字符用其它字母、数字或符号代替．它又分为单字母代换(MonogramSubstitution)和多字母代换(PolygramSubstitution)．单字母代换又分为单表代换(MonoalphabeticSubstitution)和多表代换(Polyalphabetic).替代对明文的所有字母都用一个固定的明文字母表到密文字母表的映射设则其中是一个字母表映射:

a

J,b

L,...单表代换密码恺撒密码（Caesar）破译以下密文：wuhdwb

lpsrvvleohTREATYIMPOSSIBLE加密算法：字母表：(密码本）

ABCDEFGHIJKLMNOPQRSTUVWXYZ

defghijklmnopqrstuvwxyzabc恺撒密码的特点单字母密码（简单替换技术）简单，便于记忆缺点:(1)结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构；(2)密钥空间大小只有26，而需要测试的密钥只有２５个；(3)明文所用语言已知，且其意义易于识别．单字母替换－－使用密钥使用密钥keyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopqrstuvwxzspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectaulrbdfghijkmnoqvwxyz泄露给破译者的信息更少使用置换：密钥空间大小：，大于56位DES的密钥空间，穷举攻击很困难，但基于语言统计规律仍可破译．

单字母替换－－使用置换单字母变换－－使用句子作密钥任意置换较难记忆，有时使用密钥句子：

themessagewastransmittedanhourago源字母表：abcdefghijklmnopqrstuvwxyz代换字母表：HEMESAGWRNIDOUBCFJKLPQVXYZ明文：pleaseconfirmreceipt密文：CDSTKSEBUARJOJSESRCL英文字母相对使用频率例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ多字母替换密码--平稳分布单字母替换E1和E2，分别用于明文信息中奇数和偶数位置的字符，从而打乱密文中的字母分布频率特性（通常E2应为的E1补充）例1：E1(T)=a,E2(T)=bE1(X)=b,E2(X)=a E1(a)=(3*a)mod26E2(a)=(5*a+13)mod26

TREATYIMPOSSIBL

E

fumnf

dyvtf

czysh

h多字母替换密码--平稳分布例2：E1(a)=a E2(a)=25-aABCDEFGHIJKLMNOPQRSTUVWXYZzyxwvutsrqponmlkjihgfedcbaItwasthebestoftimes,itwastheworstoftimes…Ig

wzs

ghv

bvsg

ou

trmvs

rt

dah

tse

doisg

ou

trmvsPlayfair密码把明文中的双字母音节作为一个单元并将其转换成密文的“双字母音节”．加密算法基于一个由密钥词构成的字母矩阵．例：MONARCHYBDEFGI/JKLPQSTUVWXZ密钥词：monarchyPlayfair密码（续）如果该字母对两个字母相同，那么在它们之间加一个填充字母，比如x。如：balloon先把它变成balxloon四个字母对。落在矩阵同一行的明文字母对中的字母由其右边字母代换，最右边的用最左边的代换。如ar变成RM.落在矩阵同一列的明文字母对中的字母由其下边字母代换，最下边的用最上边的代换。如mu变成CM.其他的每组明文字母对中的字母按照如下方式代换：它所在的行是该字母的所在行，列是另一字母所在列。如hs变成BP,ea变成IM(或JM).Playfair密码分析字母对26*26=676个；单个字母在使用频率的统计规律上比字母对要强得多；密文仍然完整的保留了明文语言结构，容易攻破。一次一密(one-timepad)乱码本它是一个大的不重复的真随机字母集，写在几张纸上，粘成一个乱码本；每个密钥仅对一个消息使用一次，使用过销毁；接收者有一个同样的乱码本；密钥序列的长度等于消息的长度。产生、分配、保存与使用存在一定问题与难度。PolyalphabeticSubstitutionCipher-ExampleBreaktheplaintextinto3-characterdiagramsSubstitutethediagramasfollows:1stletterisreplacedwiththeletter3positionstoitsright2nd：7positionstoitsright3rd：10positionstoitsrightPlaintext:THISCIPHERISCERTAINLYNOTSECURE

THISCIPHERISCERTAINLYNOTSECURECipher

WOSVJSSOOUPCFLBWHSQSIQVDVLMXYO替代(SubstitutionCipher)

置换(PermutationCipher)古典密码学

置换的基本思想是保持明文字符不变，通过重排而改变它们的位置，也称为换位加密（TranspositionCipher)。置换

设m为固定的正整数，P=C=(Z/(26))m,K是由{1,2,..,m}的所有置换构成，对一个密钥π∈K，定义

eπ(x1,x2,..,xm)=(xπ(1),,..,xπ(m))和

dπ(y1,y2,..,ym)=(yπ(1),,..,yπ(m))

这里π－1为π的逆置换注：这里的加密与解密仅仅用了置换，无代数运算例子：设m=6，取密钥

而若给定的明文是：cryptography首先找分成6个字母长的明文组：crypto|graphy

求得的密文是：YTCOPRAHGYPR置换例子置换矩阵把明文按照列（行）顺序写入矩阵，按照行（列）读出；读出的顺序就是密钥；绪论古典密码学密码学信息论基础对称加密技术非对称加密技术数字签名Hash函数身份认证密钥管理课程内容保密系统的数学模型Shannon保密系统模型信息量和熵定义1：设随机变量,则X的不确定性或熵定义为联合熵和条件熵

条件熵H(X|Y)理解为观察到Y后X还保留的不确定性，通常将其成为含糊度，而将H(Y|X)称为散布度，I(X,Y)=H(X)-H(X|Y)表示X上减少量。联合熵和条件熵（续）定理1，当且仅当X和Y独立是等号成立。定理2定理3，当且仅当X和Y独立是等号成立。联合熵和条件熵（续）定理4设(P,C,K,e,d)是一个密码系统，则H(K|C)=H(K)+H(P)-H(C)证明：由于

H(K,P,C)=H(C|K,P)+H(K,P)=H(P|K,C)+H(K,C)而H(C|K,P)=H(P|K,C)=0,H(K,P)=H(K)+H(P),H(K,C)=H(C)+H(K|C)故结论成立完善保密性定义2一个完善保密系统(P,C,K,e,d)称为是完善的或无条件的保密系统，如果H(P|C)=H(P)或I(P,C)=0.

Shnnon证明，仅当可能的密钥数目至少与可能的消息数目一样多时，完全保密才是可能的。即密钥必须至少与消息本身一样长，并且不重复使用。一次一密的加密Shannon在1949给出了完全安全（无条件安全）的加密系统的充要条件： 对所有的明文M和秘文E成立，即与M无关。其中，是当明文为M时，密文为E的条件概率；是在所有情况下秘文为E的概率。一次一密加密是完全安全的，也是唯一完全安全的加密体制。混乱与扩散

混乱(Confusion)与扩散(Diffusion)是Shannon提出的隐蔽明文消息中冗余度的基本技术。混乱用于掩盖明文和密文之间的关系。实现的简单方法是通过替代。扩散通过将明文冗余度分散到密文中使之分散开来。实现的简单方法是通过简单换位。单向函数单向函数是现代密码学的一个基本工具，它可以用来构造伪随机序列生成器（密钥流生成器），单向陷门函数可用来构造公钥密码体制，单向杂凑（Hash）函数可以用于数字签名和消息完整性检测等。定义：函数称为强单向函数，若满足：（1）计算f(x)使容易的；（2）计算f(x)的逆是困难的。单向函数（续）单向函数计算容易值得是f(x)在多项式时间内可计算，其逆计算是困难的指的是用任一个多项式时间算法来计算f(x)的逆，若算法的输入y=f(x)由中随机抽取，计算出结果为x的概率是可以忽略的。候选单向函数例1整数因子分解n=pq例2背包问题有一个背包，其容积为s，有n种东西体积分别为，要从中挑选出若干件把其装满。即求，使得。绪论古典密码学密码学信息论基础对称加密技术非对称加密技术数字签名Hash函数身份认证密钥管理课程内容对称加密结构对称加密流加密(StreamCipher)

流密码又称为序列密码，一直是作为军事和外交场合使用的主要密码技术之一，它的主要加密方法是使用优良的伪随机序列作为密钥，对信息流进行逐比特加密，得到密文序列。所以，序列密码算法的安全强度完全决定于它所产生的伪随机序列的好坏。

块加密(BlockCipher)块密码也称为分组密码，其工作方式是将明文分成固定长度的组（块），用同一密钥和算法对每一块加密，输出也是固定长度的密文。

流加密结构图明文密钥流密文流加密密钥流的周期性密钥流生成器DES数据加密标准DES（DataEncryptionStandard）是美国国家标准局开始研究除国防部以外的其他部门的计算机系统的数据加密标准。1977年1月，美国政府采纳1BM公司设计的方案作为非机密数据的正式数据加密标准（DES）。DES被授权用于所有公开的和私人的非保密通信场合，后来它又曾被国际标准组织采纳为国际标准。在1973年，NBS发布了公开征集标准密码算法的请求，他们确定的设计准则为：（1）必须提供高度的安全性；（2）具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又便于理解和掌握；（3）安全性应不依赖于算法的保密，其加密的安全性仅以加密密钥的保密为基础；（4）必须适用于不同的用户和不同的场合；（5）实现经济、运行有效；（6）必须能够验证，允许出口。数据加密算法设计标准DES算法描述初始置换与逆置换LiandRiare32-bitlong算法每一轮迭代的结构密钥置换密钥的64位中产生出56位56位密钥分成两部分,每部分28位,然后根据轮数,这两部分分别循环左移1位或2位.57106314492556415947613351395325433145173523379271529119721581162135035454260462834523820264430121836224轮位112132425262728291102112122132142152161密钥置换(续)从56位中选出48位1423414417195249111231392443756126473458555331630462874042152751506204536211333291024832详细结构函数F(R,K)扩展置换32位扩展成48位,其中16位重复S盒S盒的输入是6位,输出是4位数据产生方法:

设S盒的6位输入为b1,b2,b3,b4,b5,b6,则b1和b6组合成的2位数对应行号;b2b3b4b5组合成一个4位数对应表中的列.查找S盒种对应位置的元素,得到一个4位数.S盒(1-4)S盒(5-8)S盒的输入S盒的输出P盒置换S盒代替运算后的32位输出依照P盒进行置换.DES解密解密与加密算法相同,不同之处是密钥的次序相反.加密时为K1,k2,……,K16,解密时为k16,k15,……,k1.产生密钥的算法也是循环的,密钥向右移动.雪崩效应(TheAvalancheEffect)DES的安全性弱密钥:算法的任一周期的密钥都相同;半弱密钥:一些密钥对把明文加密成相同的密文;迭代的次数密钥长度S盒的安全性差分攻击线性分析DES加密与解密例子已知明文m=computer,密钥k=program密文:0101100010101000010000011011100001101001111111101010111000110011高级加密标准(AES)AES的起源AES的设计原则AES算法描述1.AES的起源1997年9月，NIST征集AES方案，以替代DES。1999年8月，以下5个方案成为最终候选方案：MARS,RC6,Rijndael,Serpent,Twofish。2000年10月，由比利时的JoanDaemen和VincentRijmen提出的算法最终胜出。（Rijndael

读成RainDoll。）http://www.esat.kuleuven.ac.be/~rijmen/rijndael/2.AES的设计原则能抵抗所有已知的攻击；在各种平台上易于实现，速度快；设计简单。

Rijndael是一个分组密码算法，其分组长度和密钥长度相互独立，都可以改变。分组长度（bit）128192256密钥长度（bit）128192256表1.分组长度和密钥长度的不同取值3.

AES

算法的一般描述RijndaelRound的构成ByteSubstitutionByteRotationMixColumn+RoundKey一般的轮变换ByteSubstitutionByteRotation+RoundKey最后一轮的轮变换3.

AES

算法加密部分的实现01234567891011121314150481215913261014371115Fig1.以明文分组为128bits为例组成的阵列048121591326101437111504812162015913172126101418223711151923048121620242815913172125292610141822263037111519232731Fig2.以明文分组（或密钥）为128bits、192bits、256bits为例组成的阵列

一些相关的的术语定义和表示状态（State）：密码运算的中间结果称为状态。State的表示：状态用以字节为基本构成元素的矩阵阵列来表示，该阵列有4行，列数记为Nb。Nb=分组长度（bits）÷32

Nb可以取的值为4，6，8，对应的分组长度为128，192，256bits。密码密钥（CipherKey）的表示：CipherKey类似地用一个4行的矩阵阵列来表示，列数记为Nk。Nk=密钥长度（bits）÷32

Nk可以取的值为4，6，8，对应的密钥长度为128，192，256bits。Fig3.当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=128bitsFig4.分组长度和密钥长度均为128bits时的Rijndael加密算法框图Data/KeyAdditionRnd0Rnd1Rnd8FinalRndKeyScheduleCipherTextKeyPlainText表2.轮数（Round）的不同取值轮数（Round）BlockLength=128BlockLength=192BlockLength=256KeyLength=128101214KeyLength=192121214KeyLength=256141414用伪代码表示的Rijndael轮变换一般的轮变换Round(State,RoundKey){ByteSubstitution;

ByteRotation;

MixColumn;

AddRounKey;}结尾轮变换FinalRound(State,RoundKey){ByteSubstituion;

ByteRotation;

AddRoundKey;}ByteSubstitution(字节替代)

ByteSubstitution是一个非线性的字节替代，独立地在每个状态字节上进行运算。它包括两个变换。

1.在有限域GF()上求乘法逆，‘00’映射到它自身。

2.在GF(2)上进行下面的仿射变换：

y01

11

1

1

000x00y10

11

1

1

100x11y2001

1

1

110x21y3000

1

1

111x30y4＝

1

00

0

1

111x4＋

0y51

10

0

0

111x50y61

11

0

0

011x61y71

11

1

0

001x71Fig6.ByteSubstitution

该变换可以用一个256字节的表来实现B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3取逆仿射变换ByteRotation(字节移位)在ByteRotation变换中，状态阵列的后3行循环移位不同的偏移量。第1行循环移位C1字节，第2行循环移位C2字节，第3行循环移位C3字节。偏移量C1、C2、C3与分组长度Nb有关，如下表所示：NbC1C2C3412361238134Fig7.ByteRotation04812159132610143711150481259131101426153711循环左移1字节循环左移2字节循环左移3字节MixColumn(列混合)将状态的列看作是有限域GF(28)上的多项式a(x)，与多项式c(x)=03x3+01x2+01x+02相乘(模x4＋1)。令b(x)=c(x)×a(x)，写成矩阵形式为：

b002030101a0

b1=01

020301a1

b20101

0203a2

b303010102a3Fig8.MixColumn

这一运算作用在每一列上A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3×C(X)2.4AddRoundKey(轮密钥加)将轮密钥与状态按比特异或。轮密钥是通过KeySchedule过程从密码密钥中得到的，轮密钥长度等于分组长度。A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3＋B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A3,3＋K3,3＝B3,3(mod2)Fig7.Rijndael加密及解密的标准结构Block,KeyLength=128bitsPlaintext(128bits)ByteSubstitutionMixColumn＋Ciphertext(128bits)

K0Kii=10ByteRotationfori=1to10Ciphertext(128bits)

K10InvMixCoumnInvByteRotationInvByteSubstitution＋＋

Ki＋Plaintext(128bits)i=9fori=9to0加密解密用伪代码表示的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);}提前进行密钥扩展后的Rijndael加密算法描述Rijndael(State,ExpandedKey){

AddRoundKey(State,ExpandedKey);For(i=1;i<Rnd;i++)Round(State,ExpandedKey+Nb*i);

FinalRound(State,ExpandedKey+Nb*Rnd);}AES

的密钥调度

密钥调度包括两个部分：密钥扩展和轮密钥选取。密钥bit的总数＝分组长度×（轮数Round＋1）例如当分组长度为128bits和轮数Round为10时，轮密钥长度为128×(10＋1)＝1408bits。将密码密钥扩展成一个扩展密钥。从扩展密钥中取出轮密钥：第一个轮密钥由扩展密钥的第一个Nb个4字节字，第二个圈密钥由接下来的Nb个4字节字组成，以此类推。密钥扩展K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3K0K1K2K3K0K1K2K3K4K5K6K7+++K0K1K2K3K4K5K6K7ByteSubstitutionByteRotate+RconWi-4Wi-3Wi-2Wi-1WiByteSubstituionByteRotate+Rcons+Keyexpansion4=<i<4(Rnd+1)imod4=0imod4!=0

轮密钥选取K0K1K2K3K4K5K6K7K8K9K10K11K12轮密钥0轮密钥1轮密钥2AES的解密算法解密算法与加密算法不同每个阶段均可逆，因此易证解密函授的确可以恢复明文AES

算法的设计原理

GF(28)中乘法使用的多项式是8次不可约多项式列表中的第一个多项式。ByteSubstitution（称为S盒）在设计时考虑到抵抗差分密码分析、线性密码分析的要求，应满足以下条件：1.可逆性；2.输入比特的线性组合与输出比特的组合之间的最大非平凡相关性的极小化；3.异或差分表中最大非平凡值的极小化；4.GF(28)中代数表示的复杂性；5.描述的简单性。满足前3条准则的S盒的构造方法已被给出，AES的作者从众多候选构造中选择将x映射到它的逆的S盒。该映射过于简单，为了抵抗插入攻击，加入仿射变换：b(x)=(x7

+x6

+x2

+x)+a(x)(x7

+x6

+x5

+x4

+1)modx8

+1模数多项式x8+1选择为可能是最简单的模数多项式。可以找到其它的S盒满足以上准则。MixColumn变换符合以下准则：1.可逆性；2.GF(2)中的线性性；3.适当的扩散性能；4.8位处理器上实现速度快；5.对称性；6.描述的简单性。选择模数多项式x4＋1可满足准则2、5、6。准则1、3、4要求系数的值要小，故选00、01、02、03。ByteRotation符合以下准则：1.4个位移量互不相同且C0＝0；2.能抵抗差分截断攻击；3.能抗Square攻击；4.简单。从满足准则2和准则3出发，AES的作者选取了最简单的组合。与一些其它算法的比较：与DES相比：1.无DES中的弱密钥和半弱密钥；2.紧凑的设计使得没有足够的空间来隐藏陷门。与IDEA相比：无IDEA中的弱密钥。具有扩展性：密钥长度可以扩展到为32bits倍数的任意密钥长度，分组长度可以扩展到为64bits倍数的任意分组长度。圈数和循环移位偏移量作为参数，要重新定义。关于有限域G(28)的一些解释G(28)可看为8位二进制比特串的集合直观上有限域的运算可为密码算法的实现带来方便只有满足一些规则后，G(28)才是有限域G(28)上的运算加法按位异或乘法可通过对多个中间结果的移位运算和异或一个特定的比特串（比如00011011）实现。绪论古典密码学密码学信息论基础对称加密技术非对称加密技术数字签名Hash函数身份认证密钥管理课程内容数学基础素数Fermat定理和Euler定理素性测试中国剩余定理离散对数素数235711131719232931374143535961717379838997101103107109113127131139149151163167173179181191193197199211223227229233241251257263269271277281283293307311313317331337347349353359367373379383389397401409419421431433439443449457461463467479487491499素数Fermat

定理Euler定理nnn111110211221124221032131223224214624854158252062168261276171627188418628129619182928104208308Miller和Rabin提出的算法：考察奇数n，设n-1=2kq选择整数1<a<n-1计算若n为素数，要么序列的第一个元素为1，要么该序列中存在元素n-1.素数测试Miller和Rabin提出的算法：考察奇数n，设n-1=2kq选择整数1<a<n-1计算若n为素数，要么序列的第一个元素为1，要么该序列中存在元素n-1.素数测试中国剩余定理RSA的基本原理

RSA体制是根据寻求两个大素数容易，而将他们的乘积分解开则极其困难这一原理来设计的。RSA中的密钥RSA中的加密与解密RSA中密钥中参数的选择RSA中密钥中参数的选择（示例一）RSA中密钥中参数的选择（示例二）RSA算法的安全性RSA安全性取决于对模n因数分解的困难性。1999年8月，荷兰国家数学与计算机科学研究所家们的一组科学家成功分解了512bit的整数，大约300台高速工作站与PC机并行运行，整个工作花了7个月。1999年9月，以色列密码学家Adi

Shamir设计了一种名叫“TWINKLE”的因数分解设备，可以在几天内攻破512bit的RSA密钥。（但要做到这一点，需要300-400台设备，每台设备价值5000美圆）。椭圆曲线加密（EllipticCurveCryptography）椭圆曲线密码介绍椭圆曲线理论是代数、几何、数论等多个数学分支的交叉点，近年来被广泛应用于公钥密码学研究中。椭圆曲线的一般方程 y2+axy+by=x3+cx2+dx+e

其中a,b,c,d,e属于集合F,F可以是有理数域，也可以是复数域。一般采用如下方程：椭圆曲线密码示意图椭圆曲线上的加法:P+Q=R椭圆曲线上一点的2倍:P+P=R.有限域上椭圆曲线Ep(a,b)加法公式:P+O=P如果P=(x,y)，则P+(x,-y)=O，(x,-y)点是P的负点，记为-P。而且(x,-y)也在Ep(a,b)中如果P=(x1,y1)，Q=(x2,y2)，则P+Q=(x3,y3)为

x3=

2-x1-x2(modp)

y3=

(x1-x3)-y1(modp)

其中，如果PQ，则=(y2-y1)/(x2-x1)

如果P=Q，则=(3x12+a)/(2y1)椭圆曲线用于加密找到一个难题：考虑等式Q=kP，其中Q、P属于Ep(a,b)，k<p已知k和P，计算Q，是容易的已知Q和P，计算k，是困难的选择Ep(a,b)的元素G,使得G的阶n是一个大素数G的阶是指满足nG=O的最小n值秘密选择整数r，计算P=rG，然后公开(p,a,b,G,P)，P为公钥保密r加密M：先把消息M变换成为Ep(a,b)中一个点Pm然后，选择随机数k，计算密文Cm=(kG,Pm+kP)如果k使得kG或者kP为O，则要重新选择k.解密Cm:(Pm+kP)-r(kG)=Pm+krG-rkG=Pm加密信息有扩张椭圆曲线密码的安全性

难点:从P和kP获得k对椭圆曲线研究的时间短椭圆曲线要求密钥长度短,速度快对比:ECCRSAKeysizeMIPS-Yrs1503.8

10102057.1

10182341.6

10285123

1047682

10810243

101112801

101415363

101620483

1020信息认证和散列函数

（MessageAuthenticationandHashFunctions)1信息认证网络系统安全要考虑两个方面。一方面，用密码保护传送的信息使其不被破译；另一方面，就是防止对手对系统进行主动攻击，如伪造，篡改信息等。认证（authentication）则是防止主动攻击的重要技术，它对于开放的网络中的各种信息系统的安全性有重要作用。认证的主要目的有二：第一，验证信息的发送者是真正的，而不是冒充的，此为信源识别；第二，验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等。保密和认证同时是信息系统安全的两个方面，但它们是两个不同属性的问题，认证不能自动提供保密性，而保密性也不能自然提供认证功能。一个纯认证系统的模型如下图所示：窜扰者信宿信源认证编码器认证译码器信道安全信道密钥源在这个系统中的发送者通过一个公开的无扰信道将消息送给接收者，接收者不仅想收到消息本身，而且还要验证消息是否来自合法的发送者及消息是否经过篡改。系统中的密码分析者不仅要截收和破译信道中传送的密报，而且可伪造密文送给接收者进行欺诈，将其称为系统的窜扰者(tamper)更加合适。实际认证系统可能还要防止收方、发方之间的相互欺诈。上述标出的认证编码器和认证译码器可抽象为认证函数。一个安全的认证系统，首先要选好恰当的认证函数，然后在此基础上，给出合理的认证协议(AuthenticationProtocol)。2认证函数

（AuthenticationFunctions)可用来做认证的函数分为三类：(1)信息加密函数(Messageencryption)

用完整信息的密文作为对信息的认证。(2)信息认证码MAC(MessageAuthenticationCode)

是对信源消息的一个编码函数。(3)散列函数(HashFunction)

是一个公开的函数，它将任意长的信息映射成一个固定长度的信息。

对于（1），用信息加密函数作认证的方式，信息加密函数分二种，一种是常规的对称密钥加密函数，另一种是公开密钥的双密钥加密函数。下图的通信双方是，用户A为发信方，用户B为接收方。用户B接收到信息后，通过解密来判决信息是否来自A，信息是否是完整的，有无窜扰。信源信宿MEEk(M)DMA方B方kkDk(Ek(M))(a)常规加密：具有机密性，可认证KUb(B方的公钥)MEEKUb(M)DMA方B方DkRb(b)公钥加密：具有机密性MEEkRa(M)DMA方B方KRaKUa(c)公钥加密：认证和签名MEEkRa(M)EEKUb(EkRa(M))A方KRaKUbDEkRa(M)DMB方KRbKUa(d)公钥加密：机密性，可认证和签名对于（2），信息认证码(MAC)

设S为通信中的发方A发送的所有可能的信源集合。为了达到防窜扰的目的，发方A和收方B设计一个编码法则。发方A根据这个法则对信源S进行编码，信源经编码后成为消息，M表示所有可能的消息集合。发方A通信时，发送的是消息。用简单的例子说明：设S={0,1},M={00,01,10,11},定义四个不同的编码法则e0,e1,e2,e3:00011011e001e101e201e301这样就构成一个认证码MAC。发方A和收方B在通信前先秘密约定使用的编码法则。例如，若决定采用e0，则以发送消息00代表信源0；发送消息10代表信源1，我们称消息00和10在e0之下是合法的。而消息01和11在e0之下不合法，收方将拒收这二个消息。信息的认证和保密是不同的两个方面，一个认证码可具有保密功能，也可没有保密功能。认证编码的基本方法是要在发送的消息中引入多余度，使通过信道传送的可能序列集Y大于消息集X。对于任何选定的编码规则(相应于某一特定密钥):发方从Y中选出用来代表消息的许用序列，即码字；收方根据编码规则唯一地确定出发方按此规则向他传来的消息。窜扰者由于不知道密钥，因而所伪造的假码字多是Y中的禁用序列，收方将以很高的概率将其检测出来而被拒绝。认证系统设计者的任务是构造好的认证码(AuthenticationCode),使接收者受骗概率极小化。令x∈X为要发送的消息，k∈K为发方选定的密钥，y=A(x,k)∈Y是表示消息X的认证码字，Ak={y=A(x,k)|x∈X}为认证码。Ak是Y中的许用(合法)序列集，易见Y=Ak∪Ak。接收者知道认证编码A(.,.)和密钥k,故从收到的y,唯一确定出消息x。窜扰者虽然知道X,Y,y,A(.,.),但不知具体密码k,他的目的是想伪造出一个假码字y*，使y*∈Ak,以使接收者收到y*后可用密钥k解密，得到一个合法的消息x*。这样，窜扰者欺诈成功。消息认证消息认证是使意定的消息接收者能够检验收到的消息是否真实的方法。检验内容应包括：(1)证实报文的源和宿；(2)报文内容是否曾受到偶然的或有意的篡改；(3)报文的序号和时间栏。总之，消息认证使接收者能识别：消息的源，内容的真伪，时间性和意定的信宿。这种认证只在相应通信的双方之间进行，而不允许第三者进行上述认证。认证不一定是实时的。可用消息认证码MAC对消息做认证。.利用函数f和密钥k，对要发送的明文x或密文y变换成rbit的消息认证码f(k,x)(或f(k,y))，将其称为认证符附加在x(或y)之后发出，以x//As(或y//As)表示，其中“//”符号表示数字的链接。接收者收到发送的消息序列后，按发方同样的方法对接收的数据(或解密后)进行计算，应得到相应的rbit数据。

两种实用的MAC算法

(一)十进制移位加MAC算法

Sievi于1980年向ISO提出一项消息认证法的建议[Davies等1984]，这种认证法称为十进制移位加算法(DecimalShiftandAddAlgorithm)，简记为DSA。它特别适用于金融支付中的数值消息交换业务。消息按十位十进制数字分段处理，不足十位时在右边以0补齐，下面举例说明。令x1=1583492637是要认证的第一组消息，令b1=5236179902和b2=4893524771为认证用的密钥。DSA算法是以b1和b2并行对x1进行运算。先算x1+b1,x1+b2(mod1010),而后根据b2的第一位数值4对x1+b2循环左移4位，记作R(4)(x1+b1)再与(x1+b1)相加得

R(4)(x1+b1)+(x1+b1)

P1(mod1010)类似地，右路在b1的第一位数值5控制下运算结果为

R(5)(x1+b2)+(x1+b2)=Q1(mod1010)表：左路 右路第b1=5236179902 b2=4893224771一+x1=1583492637 +x1=1583492637轮b1+x1=6819672539b2+x1=6477017408+R(4)(b1+x1)=2539681976+R(5)(b2+x1)=1740864770P1=9359354506Q1=8217882178第+x2=5283586900+x2=5283586900二P1+x2=4642941406Q1+x2=3501469078轮+R(8)(P1+x2)=4294140646+R(9)(Q1+x2)=7835014690P2=8937082052Q2=1336483768

….

….第P10=7869031447Q10=3408472104十P10+Q10=1277403551(mod1010)轮403551+1277

认证符404828(mod1010)将第二组消息x2=528358586900分别与P1和Q1相加，其结果又分别以P1和Q1的第一位控制循环移位后进行相加得到P2和Q2，依此类推。直至进行十轮后得P10和Q10。计算P10+Q10(mod1010),并将结果的后6位数与前4位数在(mod1010)下相加，得6位认证符！(二)采用DES的认证算法：有二种基于DES的认证算法，一种按CFB模式，一种按CBC模式运行。在CBC模式下，消息按64bit分组，不足时以0补齐，送入DES系统加密，但不输出密文，只取加密结果最左边的r位作为认证符。(64bit)x1,..xnAs(24bitor32bit)64比特寄存器DES选左r位+y1,y2,…,yn(64bit数组)yn利用CBC模式下DES的认证法

r取大小可由通信双方约定。美国联邦电信建议采用24bit[见FTSC-1026],而美国金融系统采用32bit[ABA,1986]64bit寄存器DES选左边k位选左边r位As+yixi利用工作于CFB模式下DESk对于（3），散列函数(HashFunction)

若对相当长的文件通过签名认证怎么办？如一个合法文件有数兆字节长。自然按160比特分划成一块一块，用相同的密钥独立地签每一个块。然而，这样太慢。

解决的办法：引入可公开的密码散列函数(Hashfunction)。它将取任意长度的消息做自变量，结果产生规定长度的消息摘要。[如，使用数字签名标准DSS，消息摘要为160比特]，然后签名消息摘要。对数字签名来说，散列函数h是这样使用的：消息：x任意长消息摘要：Z=h(x)160bits

签名：y=sigk(Z)320bits(签名一个消息摘要)验证签名:(x,y),其中y=sigk(h(x))，使用公开的散列函数h，重构作Z'=h(x)。然后检验Verk(Z,y),来看Z

=Z'。

(一)无碰撞的散列函数用以认证的散列函数，能否减弱认证方案的安全性？这个问题是要分析的。签名的对象由完整消息变成消息摘要，这就有可能出现伪造。

(a)伪造方式一：Oscar以一个有效签名(x,y)开始，此处y=sigk(h(x))。首先他计算Z=h(x)，并企图找到一个x'=x满足h(x')=h(x)。若他做到这一点，则(x',y)也将为有效签名。为防止这一点，要求函数h具有无碰撞特性。

定义1(弱无碰撞)，散列函数h称为是弱无碰撞的，是指对给定消息x∈X，在计算上几乎找不到异与x的x'∈X使h(x)=h(x')。