密码算法与应用基础课件

二、对称密钥密码密码算法与应用基础1二、对称密钥密码密码算法与应用基础1信息安全引论对称密钥密码对称密钥密码应用基础公开密钥密码数字签名与Hash函数公开密钥密码应用基础密钥交换与密钥管理内容提要2信息安全引论内容提要2对称密钥密码概述古典密码

Feistel结构

DES

SomepostDESalgorithms分组密码工作模式

Rijndael

整理发布3对称密钥密码概述整理发布3加密与解密加密与解密加密:E:(X,K)Y,y=E(x,k)固定k,Ek:XYEk是单值映射,Ek(x1)!=Ek(x2)ifx1!=x2Ek逆映射解密,记为Dk:YX

许多时候,YX,这样可以执行多次加密:EkEk…...Ek4加密与解密加密与解密4密码分类密码系统的几种分类按执行的操作

替换(substitution)与换位(permutation)按密钥的数量

单密钥(对称密钥)与双密钥(公开密钥)按明文处理方式

流密码(streamcipher)与分组密码(blockcipher)5密码分类密码系统的几种分类5密码分析密码分析(破译)Ciphertextonly已知:CiphertextKnownplaintext(已知明文攻击)已知:部分明文密文对Chosenplaintext(选择明文攻击)

可以选择任意明文并得到对应的密文Chosenciphertext(选择密文攻击)

可以选择部分密文并得到对应的明文6密码分析密码分析(破译)6密码算法的安全性密码算法的安全性Unconditionallysecure无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性.OnetimepadComputationallysecure破译的代价超出信息本身的价值;破译的时间超出了信息的有效期.7密码算法的安全性密码算法的安全性7关于对称密码...关于对称密码...历史悠久经验比例大理论结果少算法复杂破译的代价或者时间难于准确估计密钥长度数据块大小8关于对称密码...关于对称密码...8古典密码SubstitutionMonoalphabeticcipherPlayfaircipherHillcipherVigenérecipherOnetimepadTransposition

小结

9古典密码Substitution9MonoalphabeticcipherCaesarcipherE(p)=(p+3)mod26abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC例子:crypt=>FUBSW任意的单表替换密码abcdefghijklmnopqrstuvwxyzSDVJKLTIOXCFAWQZUPYREGHBNM例子:crypt=>VPNZR10MonoalphabeticcipherCaesarci单表替换密码的破译密钥空间为26!>4*1026通过字母的使用频率破译11单表替换密码的破译密钥空间为26!>4*10261Playfaircipher5×5变换矩阵:I与J视为同一字符 CRYPT OGAHB DEFIK(cryptography) LMNQS UVWXZ加密规则:按成对字母加密成对重复字母加分隔符(如x) balloonbalxloon同行取右边:rtYC同列取下边:fwNY其他取交叉:lyNC,GKBE12Playfaircipher5×5变换矩阵:I与J视为同Playfaircipher-例子以前面的5×5变换矩阵(cryptography)为例: CRYPT OGAHB DEFIK LMNQS UVWXZExamples

looklookUDBD

fillfilxlxIKQUQU

jigsawjxigsawxQPEHNBXZ

cryptocryptoRYPTCB13Playfaircipher-例子以前面的5×5变换矩阵(Playfaircipher-小结Playfair有26*26种字母对组合字符出现几率一定程度上被均匀化基于字母频率的攻击比较困难依然保留了相当的结构信息

14Playfaircipher-小结Playfair有26*Hillcipher基于矩阵的线性变换:C=KPK是一个m*m矩阵,在Z26上可逆,即存在K-1使得:

KK-1=I(在Z26上)171705040915

K=211821K-1=151706020219240017完全隐藏了字符(对)的频率线性变换的安全性很脆弱15Hillcipher基于矩阵的线性变换:C=KP1Vigenérecipher多表代换密码 一个单代换表的集合 密钥决定何时使用哪个单表Vigenérecipher使用Caesar密码作为基础单代换表集合: EK(P)=(K-a)+Pmod26(子)密钥与明文一样长16Vigenérecipher多表代换密码16Vigenérecipher-例子EK(P)=(K-a)+Pmod26abcdefghijklm00010203040506070809101112nopqrstuvwxyz13141516171819202122232425key:cryptographycryptographycrplain:yourpackagereadyroomathreecipher:AFSGIOI17Vigenérecipher-例子EK(P)=(K-aVigenérecipher-破译依然保留了字符频率某些统计信息间距是密钥长度整数倍子串有相同密文:abcdefghijklm00010203040506070809101112nopqrstuvwxyz13141516171819202122232425key:cryptographycryptographycrplain:yourpackagereadyroomathreecipher:AFSGIOIPGPG18Vigenérecipher-破译依然保留了字符频率某些统OnetimepadVigenére本人建议密钥与明文一样长GillbertVernam建议密钥与明文一样长并且没有统计特性:

Ci=Pi

Ki进一步的改进是使用完全随机的串作为密钥:Onetimepad密钥的交换与保管十分困难加密的信息有长度限制19OnetimepadVigenére本人建议密钥与明文一样Transposition换位密码把明文按列写入,按行读出密钥包含3方面信息:行宽,列高,读出顺序key:4312567plaintext:attackpostponeduntiltwoamxyzciphertext:TTNAAPTMTSUOAODWCOIXPETZ完全保留字符的统计信息使用多轮加密可提高安全性20Transposition换位密码把明文按列写入,按行读出古典密码小结Substitution&permutation密码分析多轮加密数据安全基于算法的保密21古典密码小结Substitution&permutati分组密码设计要求Diffusion(弥散)密文没有统计特征，明文一位影响密文的多位，密钥的一位也影响密文的多位Confusion(混淆)明文与密文、密钥与密文的依赖关系充分复杂结构简单、易于分析22分组密码设计要求Diffusion(弥散)22Feistel结构图23Feistel结构图23Feistel结构定义加密:Li=Ri-1;Ri=Li-1F(Ri-1,Ki)解密:Ri-1=LiLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki)24Feistel结构定义加密:Li=Ri-1;RiFeistel结构分析Blocksize(64128)Keysize(56128~256)Numberofrounds(16)SubkeygenerationRoundfunction(F)Fastsoftwareencryption/decryptionEasyhardwareimplementationSimplestructureEaseofanalysis25Feistel结构分析Blocksize(64128DESDES概述DES结构详解

DES安全性分析

多重DES

26DESDES概述26SomepostDESalgorithmsIDEABlowfishRC5CAST-128……27SomepostDESalgorithmsIDEA分组密码工作模式ElectronicCodebookMode

CipherBlockChainingMode

CipherFeedbackMode

OutputFeedbackMode

28分组密码工作模式ElectronicCodebookMoAES介绍1997年NIST宣布征集AES算法要求:与TripeDES比要快且至少一样安全,分组128位,密钥128/192/256位1998年确定第一轮15个候选者1999年确定第二轮五个候选者:MARS,RC6,Rijndael,Serpent,Twofish2000年底Rijndael成为胜利者29AES介绍1997年NIST宣布征集AES算法29有限域GF(28)(一)字节b=b7b6b5b4b3b2b1b0看成系数属于{0,1}的多项式:b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0如:‘A7’10100111x7+x5+x2+x+1加法:{0,1}上加法(等价于按位XOR)乘法:多项式模乘,模为(‘11B’): m(x)=x8+x4+x3+x+1如:(x7+x6+x+1)(x5+x+1)=x12+x11+x5+x2+1=x6+x4+x2+xmod(x8+x4+x3+x+1)m(x)不可约30有限域GF(28)(一)字节b=b7b6b5b4b3b2b1有限域GF(28)(二)对次数低于8的b(x)(非0),扩展Euclid算法可计算出a(x),c(x)使得:b(x)a(x)+m(x)c(x)=1

b(x)a(x)=1modm(x)

b-1(x)=a(x)modm(x)集合{0…255}构成有限域GF(28)GF(28)上b(x)乘x(‘02’):记作xtime(b)xb(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x若b7为0,则从字节上看是一个左移位;否则,还需要减去m(x),从字节上看是与‘1B’作XOR.31有限域GF(28)(二)对次数低于8的b(x)(非0),扩展有限域GF(28)上多项式4-byte向量～GF(28)元素为系数多项式(<4次)加法:对应系数的加法(XOR)乘法:多项式模乘,M(x)=x4+1 xjmodM(x)=xjmod4a(x)=a3x3+a2x2+a1x+a0,b(x)=b3x3+b2x2+b1x+b0d(x)=a(x)b(x)=d3x3+d2x2+d1x+d0modM(x)|d0||a0a3a2a1||b0||d1||a1a0a3a2||b1||d2|=|a2a1a0a3||b2||d3||a3a2a1a0||b3|xb(x)=b3x4+b2x3+b1x2+b0x=b2x3+b1x2+b0x+b3即按字节循环左移位.32有限域GF(28)上多项式4-byte向量～GF(28)元素Rijndael简介不属于Feistel结构加密、解密相似但不对称支持128/192/256(/32=Nb)数据块大小支持128/192/256(/32=Nk)密钥长度结构简单速度快33Rijndael简介不属于Feistel结构33Rijndael简介(续)数据/密钥的矩阵表示Numberofrounds34Rijndael简介(续)数据/密钥的矩阵表示NumberRijndael:overview首轮前执行AddRoundKey(State,RoundKey)Round(State,RoundKey){ ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State,RoundKey);}FinalRound(State,RoundKey){ ByteSub(State); ShiftRow(State); AddRoundKey(State,RoundKey);}35Rijndael:overview首轮前执行AddRounRijndael:AddRoundKey按字节在GF(28)上相加(XOR)=36Rijndael:AddRoundKey按字节在GF(28Rijndael:ByteSubByteSub(S-box)非线性、可逆独立作用在每个字节上先取乘法的逆,再经过GF(2)上一个仿射变换aijbij37Rijndael:ByteSubByteSub(S-boxRijndael:ShiftRow第一行保持不变,其他行内的字节循环移位38Rijndael:ShiftRow第一行保持不变,其他行内Rijndael:MixColumn示意图列作为GF(28)上多项式乘以多项式c(x)模M(x)=x4+139Rijndael:MixColumn示意图列作为GF(28Rijndael:MixColumn多项式c(x)=‘03’x3+‘01’x2+‘01’x+‘02’M(x)=x4+1=(x2+1)(x2+1)c(x)与模M(x)=x4+1互素b(x)=c(x)a(x)|b0||02030101||a0||b1||01020301||a1||b2|=|01010203||a2||b3||03010102||a3|c(x)的逆:‘0B’x3+‘0D’x2+‘09’x+‘0E’40Rijndael:MixColumn多项式c(x)=‘Rijndael:AddRoundKey按字节在GF(28)上相加=41Rijndael:AddRoundKey按字节在GF(28Rijndael:Keyschedule(1)主密钥生成子密钥数组,(Nr+1)*Nb个字Nk<=6KeyExpansion(byteKey[4*Nk],wordW[Nb*(Nr+1)]){for(i=0;i<Nk;i++)W[i]=(Key[4*i],Key[4*i|+1],Key[4*i+2],Key[4*i+3]);for(i=Nk;i<Nb*(Nr+1);i++){temp=W[i-1];if(i%Nk==0)temp=ByteSub(temp<<<8)^Rcon[i/Nk];W[i]=W[i-Nk]^temp;};};Rcon[i]=(xi-1,‘00’,‘00’,‘00’);xi-1为GF(28)上的数.42Rijndael:Keyschedule(1)主密钥生成Rijndael:Keyschedule(2)Nk>6KeyExpansion(byteKey[4*Nk],wordW[Nb*(Nr+1)]){for(i=0;i<Nk;i++)W[i]=(Key[4*i],Key[4*i|+1],Key[4*i+2],Key[4*i+3]);for(i=Nk;i<Nb*(Nr+1);i++){temp=W[i-1];if(i%Nk==0)temp=ByteSub(temp<<<8)^Rcon[i/Nk];elseif(i%Nk==4)temp=ByteSub(temp<<<8);W[i]=W[i-Nk]^temp;};};Rcon[i]=(xi,‘00’,‘00’,‘00’);xi为GF(28)上的数.43Rijndael:Keyschedule(2)Nk>64Rijndael:encryptstructureRijndael(State,CipherKey){KeyExpansion(CipherKey,ExpandedKey);AddRoundKey(State,ExpandedKey)For(i=1;i<Nr;++i){ ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State,ExpandedKey+Nb*i);}ByteSub(State);ShiftRow(State);AddRoundKey(State,ExpandedKey+Nb*i);}44Rijndael:encryptstructureRijRijndael:decryptstructureAddRoundKey()For(i=1;i<Nr;++i){ByteSub();ShiftRow();MixColumn();AddRoundKey()}ByteSub();ShiftRow();AddRoundKey()I_AddRoundKey()I_ShiftRow();I_ByteSub();For(i=1;i<Nr;++i){I_AddRoundKey()I_MixColumn();I_ShiftRow();I_ByteSub();}I_AddRoundKey()

I_AddRoundKey()For(i=1;i<Nr;++i){I_ShiftRow();I_ByteSub();I_AddRoundKey()I_MixColumn();}I_ShiftRow();I_ByteSub();I_AddRoundKey()45Rijndael:decryptstructureAddRijndael安全性没有发现弱密钥或补密钥能抵抗已知的密码分析手段46Rijndael安全性没有发现弱密钥或补密钥46DES示意图47DES示意图47DES:singleroundLi=Ri-1Ri=Li-1F(Ri-1,Ki)48DES:singleroundLi=Ri-1RDES:FunctionFExpansion:3248S-box:64Permutation:49DES:FunctionFExpansion:32DES:Subkeygeneration50DES:Subkeygeneration50DES安全性分析差分密码分析

线性密码分析

密钥短穷举破译

字典攻击

F函数(S-Box)设计原理未知

轮数问题弱密钥与半弱密钥

小结51DES安全性分析差分密码分析51多重DESDES是否构成一个闭合群?

任给K1,K2,是否存在K3,使得: EK1•EK2=EK3DoubleDES

TripleDES

52多重DESDES是否构成一个闭合群?52DES:Expansiontable32|01020304|0504|05060708|0908|09101112|1312|13141516|1716|17181920|2120|21222324|2524|25262728|2928|29303132|0153DES:Expansiontable32|010DES:S-box(S1)1404130102151108

03100612050900070015070414021301

10061211090503080401140813060211

15120907031005001512080204090107

051103141000061354DES:S-box(S1)1404130102DES:Permutation160720212912281701152326051831100208241432270309191330062211042555DES:Permutation160720212DES:差分密码分析破解DES:247个选择明文(255个已知明文)破解Lucifer(18轮128位):24个选择明文＋221次计算DES对差分密码分析的抵抗力很强56DES:差分密码分析破解DES:247个选择明文(255DES:线性密码分析破解DES:243个已知明文DES对线性密码分析的抵抗力稍弱57DES:线性密码分析破解DES:243个已知明文57DES:穷举破译DES密钥长度:56位,256~1017计算机能力为100MIPS次(108)/秒,1万台计算机协同工作一天，计算能力为: 108*10000*24*3600~10171017/1017=1天58DES:穷举破译DES密钥长度:56位,256~10DES:字典攻击考虑选择明文攻击DES块大小:64位,264~1020计算机能力为100MIPS(108)/秒,1万台计算机协同工作一天，计算能力为: 108*10000*24*3600~10171020/1017=1000天适用于任意64位块的加密59DES:字典攻击考虑选择明文攻击59DES:S-box设计准则S-box是DES的核心(全部非线性所在)

S-box每行是0~15的一个置换

S-box输出不是输入的线性或者放射变换S-box输入一位改变,输出至少二位改变S(x)与S(x001100)至少二位不同S(x)!=S(x00ef00),对任意e,f{0,1}固定一位,其它五位变化,输出数字中的0和1的总数接近相等60DES:S-box设计准则S-box是DES的核心(全部DES:弱密钥与半弱密钥弱密钥:EKEK=I半弱密钥:EK1=EK2不影响安全性互补性:若y=DESk(x),则把x,y,k都取补,等式仍然成立.61DES:弱密钥与半弱密钥弱密钥:EKEK=I61DoubleDESC=EK2(EK1(P))P=DK1(DK2(C))62DoubleDESC=EK2(EK1(P))PDoubleDES安全性中间相会(meet-in-the-middle)攻击C=EK2(EK1(P))X=EK1(P)=DK2(C)给定明文密文对(P,C)

对所有256个密钥,加密P,对结果排序对所有256个密钥,解密C,对结果排序逐个比较,找出K1,K2使得EK1(P)=DK2(C)一个明文密文对,误警次数2112/264=248两个明文密文对,误警次数248/264=2-1663DoubleDES安全性中间相会(meet-in-theTripleDESC=EK3(DK2(EK1(P)))P=DK1(EK2(DK3(C)))64TripleDESC=EK3(DK2(EK1(P)))TripleDES分析Withtwokeys:C=EK1(DK2(EK1(P))) 256可选择明文＋256次计算Withthreekeys:C=EK3(DK2(EK1(P))) 比two-key更安全TripeDES速度慢65TripleDES分析Withtwokeys:C=ElectronicCodebookModeECB: Ci=EK(Pi)Pi=DK(Ci)相同明文相同密文同样信息多次出现造成泄漏信息块可被替换信息块可被重排密文块损坏仅对应明文块损坏适合于传输短信息66ElectronicCodebookModeECB:ECB示意图67ECB示意图67CipherBlockChainingModeCBC: 加密: Ci=EK(Ci-1Pi)

解密: Pi=EK(Ci)Ci-1需要共同的初始化向量C-1(IV)相同明文不同密文初始化向量IV可以用来改变第一块 P0=EK(C0)C-1密文块损坏两明文块损坏安全性好于ECB68CipherBlockChainingModeCBC:CBC示意图69CBC示意图69CipherFeedbackModeCFB:分组密码流密码

Si为移位寄存器,j为流单元宽度

加密:Ci=Pi(EK(Si)的高j位)

Si+1=(Si<<j)|Ci

解密:Pi=Ci(EK(Si)的高j位)

Si+1=(Si<<j)|Ci

需要共同的移位寄存器初始值S0一个单元损坏影响多个单元: (W+j-1)/jW为分组加密块大小70CipherFeedbackModeCFB:分组密码CFB加密示意图Ci=Pi(EK(Si)的高j位);Si+1=(Si<<j)|Ci

71CFB加密示意图Ci=Pi(EK(Si)的高j位);CFB解密示意图Pi=Ci(EK(Si)的高j位);Si+1=(Si<<j)|Ci

72CFB解密示意图Pi=Ci(EK(Si)的高j位);OutputFeedbackModeOFB:分组密码流密码

Si为移位寄存器,j为流单元宽度

加密:Ci=Pi(EK(Si)的高j位)

Si+1=(Si<<j)|(EK(Si)的高j位)

解密:Pi=Ci(EK(Si)的高j位)

Si+1=(Si<<j)|(EK(Si)的高j位)

需要共同的移位寄存器初始值S0一个单元损坏只影响对应单元安全性较CFB差73OutputFeedbackModeOFB:分组密码OFB加密示意图Ci=Pi(EK(Si)的高j位);Si+1=(Si<<j)|(EK(Si)的高j位)74OFB加密示意图Ci=Pi(EK(Si)的高j位);SOFB解密示意图Pi=Ci(EK(Si)的高j位);Si+1=(Si<<j)|(EK(Si)的高j位)75OFB解密示意图Pi=Ci(EK(Si)的高j位);SIDEA1990年发表,1992修改64位块,128位密钥,不属于Feistel结构运算:XOR,216模加,(216+1)模乘三种运算均不满足分配律与结合律有大量弱密钥难以直接扩展到128位块76IDEA1990年发表,1992修改76实习作业之一实现DES,要求:Linux平台,C和/或C++语言;四种模式(ECB,CBC,CFB和OFB)的加解密加解密正确性测试及性能测试提交完整源码(能编译并运行)与性能测试报告十月十日前完成77实习作业之一实现DES,要求:77二、对称密钥密码密码算法与应用基础78二、对称密钥密码密码算法与应用基础1信息安全引论对称密钥密码对称密钥密码应用基础公开密钥密码数字签名与Hash函数公开密钥密码应用基础密钥交换与密钥管理内容提要79信息安全引论内容提要2对称密钥密码概述古典密码

Feistel结构

DES

SomepostDESalgorithms分组密码工作模式

Rijndael

整理发布80对称密钥密码概述整理发布3加密与解密加密与解密加密:E:(X,K)Y,y=E(x,k)固定k,Ek:XYEk是单值映射,Ek(x1)!=Ek(x2)ifx1!=x2Ek逆映射解密,记为Dk:YX

许多时候,YX,这样可以执行多次加密:EkEk…...Ek81加密与解密加密与解密4密码分类密码系统的几种分类按执行的操作

替换(substitution)与换位(permutation)按密钥的数量

单密钥(对称密钥)与双密钥(公开密钥)按明文处理方式

流密码(streamcipher)与分组密码(blockcipher)82密码分类密码系统的几种分类5密码分析密码分析(破译)Ciphertextonly已知:CiphertextKnownplaintext(已知明文攻击)已知:部分明文密文对Chosenplaintext(选择明文攻击)

可以选择任意明文并得到对应的密文Chosenciphertext(选择密文攻击)

可以选择部分密文并得到对应的明文83密码分析密码分析(破译)6密码算法的安全性密码算法的安全性Unconditionallysecure无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性.OnetimepadComputationallysecure破译的代价超出信息本身的价值;破译的时间超出了信息的有效期.84密码算法的安全性密码算法的安全性7关于对称密码...关于对称密码...历史悠久经验比例大理论结果少算法复杂破译的代价或者时间难于准确估计密钥长度数据块大小85关于对称密码...关于对称密码...8古典密码SubstitutionMonoalphabeticcipherPlayfaircipherHillcipherVigenérecipherOnetimepadTransposition

小结

86古典密码Substitution9MonoalphabeticcipherCaesarcipherE(p)=(p+3)mod26abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC例子:crypt=>FUBSW任意的单表替换密码abcdefghijklmnopqrstuvwxyzSDVJKLTIOXCFAWQZUPYREGHBNM例子:crypt=>VPNZR87MonoalphabeticcipherCaesarci单表替换密码的破译密钥空间为26!>4*1026通过字母的使用频率破译88单表替换密码的破译密钥空间为26!>4*10261Playfaircipher5×5变换矩阵:I与J视为同一字符 CRYPT OGAHB DEFIK(cryptography) LMNQS UVWXZ加密规则:按成对字母加密成对重复字母加分隔符(如x) balloonbalxloon同行取右边:rtYC同列取下边:fwNY其他取交叉:lyNC,GKBE89Playfaircipher5×5变换矩阵:I与J视为同Playfaircipher-例子以前面的5×5变换矩阵(cryptography)为例: CRYPT OGAHB DEFIK LMNQS UVWXZExamples

looklookUDBD

fillfilxlxIKQUQU

jigsawjxigsawxQPEHNBXZ

cryptocryptoRYPTCB90Playfaircipher-例子以前面的5×5变换矩阵(Playfaircipher-小结Playfair有26*26种字母对组合字符出现几率一定程度上被均匀化基于字母频率的攻击比较困难依然保留了相当的结构信息

91Playfaircipher-小结Playfair有26*Hillcipher基于矩阵的线性变换:C=KPK是一个m*m矩阵,在Z26上可逆,即存在K-1使得:

KK-1=I(在Z26上)171705040915

K=211821K-1=151706020219240017完全隐藏了字符(对)的频率线性变换的安全性很脆弱92Hillcipher基于矩阵的线性变换:C=KP1Vigenérecipher多表代换密码 一个单代换表的集合 密钥决定何时使用哪个单表Vigenérecipher使用Caesar密码作为基础单代换表集合: EK(P)=(K-a)+Pmod26(子)密钥与明文一样长93Vigenérecipher多表代换密码16Vigenérecipher-例子EK(P)=(K-a)+Pmod26abcdefghijklm00010203040506070809101112nopqrstuvwxyz13141516171819202122232425key:cryptographycryptographycrplain:yourpackagereadyroomathreecipher:AFSGIOI94Vigenérecipher-例子EK(P)=(K-aVigenérecipher-破译依然保留了字符频率某些统计信息间距是密钥长度整数倍子串有相同密文:abcdefghijklm00010203040506070809101112nopqrstuvwxyz13141516171819202122232425key:cryptographycryptographycrplain:yourpackagereadyroomathreecipher:AFSGIOIPGPG95Vigenérecipher-破译依然保留了字符频率某些统OnetimepadVigenére本人建议密钥与明文一样长GillbertVernam建议密钥与明文一样长并且没有统计特性:

Ci=Pi

Ki进一步的改进是使用完全随机的串作为密钥:Onetimepad密钥的交换与保管十分困难加密的信息有长度限制96OnetimepadVigenére本人建议密钥与明文一样Transposition换位密码把明文按列写入,按行读出密钥包含3方面信息:行宽,列高,读出顺序key:4312567plaintext:attackpostponeduntiltwoamxyzciphertext:TTNAAPTMTSUOAODWCOIXPETZ完全保留字符的统计信息使用多轮加密可提高安全性97Transposition换位密码把明文按列写入,按行读出古典密码小结Substitution&permutation密码分析多轮加密数据安全基于算法的保密98古典密码小结Substitution&permutati分组密码设计要求Diffusion(弥散)密文没有统计特征，明文一位影响密文的多位，密钥的一位也影响密文的多位Confusion(混淆)明文与密文、密钥与密文的依赖关系充分复杂结构简单、易于分析99分组密码设计要求Diffusion(弥散)22Feistel结构图100Feistel结构图23Feistel结构定义加密:Li=Ri-1;Ri=Li-1F(Ri-1,Ki)解密:Ri-1=LiLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki)101Feistel结构定义加密:Li=Ri-1;RiFeistel结构分析Blocksize(64128)Keysize(56128~256)Numberofrounds(16)SubkeygenerationRoundfunction(F)Fastsoftwareencryption/decryptionEasyhardwareimplementationSimplestructureEaseofanalysis102Feistel结构分析Blocksize(64128DESDES概述DES结构详解

DES安全性分析

多重DES

103DESDES概述26SomepostDESalgorithmsIDEABlowfishRC5CAST-128……104SomepostDESalgorithmsIDEA分组密码工作模式ElectronicCodebookMode

CipherBlockChainingMode

CipherFeedbackMode

OutputFeedbackMode

105分组密码工作模式ElectronicCodebookMoAES介绍1997年NIST宣布征集AES算法要求:与TripeDES比要快且至少一样安全,分组128位,密钥128/192/256位1998年确定第一轮15个候选者1999年确定第二轮五个候选者:MARS,RC6,Rijndael,Serpent,Twofish2000年底Rijndael成为胜利者106AES介绍1997年NIST宣布征集AES算法29有限域GF(28)(一)字节b=b7b6b5b4b3b2b1b0看成系数属于{0,1}的多项式:b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0如:‘A7’10100111x7+x5+x2+x+1加法:{0,1}上加法(等价于按位XOR)乘法:多项式模乘,模为(‘11B’): m(x)=x8+x4+x3+x+1如:(x7+x6+x+1)(x5+x+1)=x12+x11+x5+x2+1=x6+x4+x2+xmod(x8+x4+x3+x+1)m(x)不可约107有限域GF(28)(一)字节b=b7b6b5b4b3b2b1有限域GF(28)(二)对次数低于8的b(x)(非0),扩展Euclid算法可计算出a(x),c(x)使得:b(x)a(x)+m(x)c(x)=1

b(x)a(x)=1modm(x)

b-1(x)=a(x)modm(x)集合{0…255}构成有限域GF(28)GF(28)上b(x)乘x(‘02’):记作xtime(b)xb(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x若b7为0,则从字节上看是一个左移位;否则,还需要减去m(x),从字节上看是与‘1B’作XOR.108有限域GF(28)(二)对次数低于8的b(x)(非0),扩展有限域GF(28)上多项式4-byte向量～GF(28)元素为系数多项式(<4次)加法:对应系数的加法(XOR)乘法:多项式模乘,M(x)=x4+1 xjmodM(x)=xjmod4a(x)=a3x3+a2x2+a1x+a0,b(x)=b3x3+b2x2+b1x+b0d(x)=a(x)b(x)=d3x3+d2x2+d1x+d0modM(x)|d0||a0a3a2a1||b0||d1||a1a0a3a2||b1||d2|=|a2a1a0a3||b2||d3||a3a2a1a0||b3|xb(x)=b3x4+b2x3+b1x2+b0x=b2x3+b1x2+b0x+b3即按字节循环左移位.109有限域GF(28)上多项式4-byte向量～GF(28)元素Rijndael简介不属于Feistel结构加密、解密相似但不对称支持128/192/256(/32=Nb)数据块大小支持128/192/256(/32=Nk)密钥长度结构简单速度快110Rijndael简介不属于Feistel结构33Rijndael简介(续)数据/密钥的矩阵表示Numberofrounds111Rijndael简介(续)数据/密钥的矩阵表示NumberRijndael:overview首轮前执行AddRoundKey(State,RoundKey)Round(State,RoundKey){ ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State,RoundKey);}FinalRound(State,RoundKey){ ByteSub(State); ShiftRow(State); AddRoundKey(State,RoundKey);}112Rijndael:overview首轮前执行AddRounRijndael:AddRoundKey按字节在GF(28)上相加(XOR)=113Rijndael:AddRoundKey按字节在GF(28Rijndael:ByteSubByteSub(S-box)非线性、可逆独立作用在每个字节上先取乘法的逆,再经过GF(2)上一个仿射变换aijbij114Rijndael:ByteSubByteSub(S-boxRijndael:ShiftRow第一行保持不变,其他行内的字节循环移位115Rijndael:ShiftRow第一行保持不变,其他行内Rijndael:MixColumn示意图列作为GF(28)上多项式乘以多项式c(x)模M(x)=x4+1116Rijndael:MixColumn示意图列作为GF(28Rijndael:MixColumn多项式c(x)=‘03’x3+‘01’x2+‘01’x+‘02’M(x)=x4+1=(x2+1)(x2+1)c(x)与模M(x)=x4+1互素b(x)=c(x)a(x)|b0||02030101||a0||b1||01020301||a1||b2|=|01010203||a2||b3||03010102||a3|c(x)的逆:‘0B’x3+‘0D’x2+‘09’x+‘0E’117Rijndael:MixColumn多项式c(x)=‘Rijndael:AddRoundKey按字节在GF(28)上相加=118Rijndael:AddRoundKey按字节在GF(28Rijndael:Keyschedule(1)主密钥生成子密钥数组,(Nr+1)*Nb个字Nk<=6KeyExpansion(byteKey[4*Nk],wordW[Nb*(Nr+1)]){for(i=0;i<Nk;i++)W[i]=(Key[4*i],Key[4*i|+1],Key[4*i+2],Key[4*i+3]);for(i=Nk;i<Nb*(Nr+1);i++){temp=W[i-1];if(i%Nk==0)temp=ByteSub(temp<<<8)^Rcon[i/Nk];W[i]=W[i-Nk]^temp;};};Rcon[i]=(xi-1,‘00’,‘00’,‘00’);xi-1为GF(28)上的数.119Rijndael:Keyschedule(1)主密钥生成Rijndael:Keyschedule(2)Nk>6KeyExpansion(byteKey[4*Nk],wordW[Nb*(Nr+1)]){for(i=0;i<Nk;i++)W[i]=(Key[4*i],Key[4*i|+1],Key[4*i+2],Key[4*i+3]);for(i=Nk;i<Nb*(Nr+1);i++){temp=W[i-1];if(i%Nk==0)temp=ByteSub(temp<<<8)^Rcon[i/Nk];elseif(i%Nk==4)temp=ByteSub(temp<<<8);W[i]=W[i-Nk]^temp;};};Rcon[i]=(xi,‘00’,‘00’,‘00’);xi为GF(28)上的数.120Rijndael:Keyschedule(2)Nk>64Rijndael:encryptstructureRijndael(State,CipherKey){KeyExpansion(CipherKey,ExpandedKey);AddRoundKey(State,ExpandedKey)For(i=1;i<Nr;++i){ ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State,ExpandedKey+Nb*i);}ByteSub(State);ShiftRow(State);AddRoundKey(State,ExpandedKey+Nb*i);}121Rijndael:encryptstructureRijRijndael:decryptstructureAddRoundKey()For(i=1;i<Nr;++i){ByteSub();ShiftRow();MixColumn();AddRoundKey()}ByteSub();ShiftRow();AddRoundKey()I_AddRoundKey()I_ShiftRow();I_ByteSub();For(i=1;i<Nr;++i){I_AddRoundKey()I_MixColumn();I_ShiftRow();I_ByteSub();}I_AddRoundKey()

I_AddRoundKey()For(i=1;i<Nr;++i){I_ShiftRow();I_ByteSub();I_AddRoundKey()I_MixColumn();}I_ShiftRow();I_ByteSub();I_AddRoundKey()122Rijndael:decryptstructureAddRijndael安全性没有发现弱密钥或补密钥能抵抗已知的密码分析手段123Rijndael安全性没有发现弱密钥或补密钥46DES示意图124DES示意图47DES:singleroundLi=Ri-1Ri=Li-1F(Ri-1,Ki)125DES:singleroundLi=Ri-1RDES:FunctionFExpansion:3248S-box:64Permutation:126DES:FunctionFExpansion:32DES:Subkeygeneration127DES:Subkeygeneration50DES安全性分析差分密码分析

线性密码分析

密钥短穷举破译

字典攻击

F函数(S-Box)设计原理未知

轮数问题弱密钥与半弱密钥

小结128DES安全性分析差分密码分析51多重DESDES是否构成一个闭合群?

任给K1,K2,是否存在K3,使得: EK1•EK2=EK3DoubleDES

TripleDES

129多重DESDES是否构成一个闭合群?52DES:Expansiontable32|01020304|0504|05060708|0908|09101112|1312|13141516|1716|17181920|2120|21222324|2524|25262728|2928|29303132|01130DES:Expansiontable32|010DES:S-box(S1)1404130102151108

03100612050900070015070414021301

10061211090503080401140813060211

15120907031005001512080204090107

0511031410000613131DES:S-box(S1)1404130102DES:Permutation1607202129122817011523260518311002082414322703091913300622110425132DES:Permutation160720212DES:差分密码分析破解DES:247个选择明文(255个已知明文)破解Lucifer(18轮128位):24个选择明文＋221次计算DES对差分密码分析的抵抗力很强133DES:差分密码分析破解DES:247个选择明文(255DES:线性密码分析破解DES:243个已知明文DES对线性密码分析的抵抗力稍弱134DES:线性密码分析破解DES:243个已知明文57DES:穷举破译DES密钥长度:56位,256~1017计算机能力为100MIPS次(108)/秒,1万台计算机协同工作一天，计算能力为: 108*10000*24*3600~10171017/1017=1天135DES:穷举破译DES密钥长度:56位,256~10DES:字典攻击考虑选择明文攻击DES块大小:64位,264~1020计算机能力为100MIPS(108)/秒,1万台计算机协同工作一天，计算能力为: 108*10000*24*3600~10171020/1017=1000天适用于任意64位块的加密136DES:字典攻击考虑选择明文攻击59DES:S-box设计准则S-box是DES的核心(全部非线性所在)

S-box每行是0~15的一个置换

S-box输出不是输入的线性或者放射变换S-box输入一位改变,输出至少二位改变S(x)与S(x001100)至少