《密码算法与应用基础课件.ppt》由会员分享，可在线阅读，更多相关《密码算法与应用基础课件.ppt（77页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、二、对称密钥密码二、对称密钥密码密码算法与应用基础密码算法与应用基础1信息安全引论信息安全引论对称密钥密码对称密钥密码对称密钥密码应用基础对称密钥密码应用基础公开密钥密码公开密钥密码数字签名与数字签名与HashHash函数函数公开密钥密码应用基础公开密钥密码应用基础密钥交换与密钥管理密钥交换与密钥管理内容提要内容提要2对称密钥密码对称密钥密码=概述概述=古典密码古典密码 =Feistel结构结构 =DES =Some post DES algorithms=分组密码工作模式分组密码工作模式 =Rijndael 整理发布整理发布3加密与解密加密与解密u加密与解密加密与解密 加密加密:E:(X,K
2、)Y,y=E(x,k)固定固定k,Ek:X Y Ek是单值映射是单值映射,Ek(x1)!=Ek(x2)if x1!=x2 Ek逆映射解密逆映射解密,记为记为Dk:Y X 许多时候许多时候,Y X,这样这样可以执行多次加密可以执行多次加密:Ek Ek.Ek 4密码分类密码分类密码系统的几种分类密码系统的几种分类u按执行的操作按执行的操作 替换替换(substitution)与换位与换位(permutation)u按密钥的数量按密钥的数量 单密钥单密钥(对称密钥对称密钥)与双密钥与双密钥(公开密钥公开密钥)u按明文处理方式按明文处理方式 流密码流密码(stream cipher)与分组密码与分组密
3、码(block cipher)5密码分析密码分析密码分析密码分析(破译破译)uCiphertext only 已知已知:CiphertextuKnown plaintext(已知明文攻击已知明文攻击)已知已知:部分明文密文对部分明文密文对uChosen plaintext(选择明文攻击选择明文攻击)可以选择任意明文并得到对应的密文可以选择任意明文并得到对应的密文uChosen ciphertext(选择密文攻击选择密文攻击)可以选择部分密文并得到对应的明文可以选择部分密文并得到对应的明文6密码算法的安全性密码算法的安全性密码算法的安全性密码算法的安全性uUnconditionally secu
4、re无论破译者有多少密文无论破译者有多少密文,他也无法解出对应他也无法解出对应的明文的明文,即使他解出了即使他解出了,他也无法验证结果的他也无法验证结果的正确性正确性.Onetime paduComputationally secure破译的代价超出信息本身的价值破译的代价超出信息本身的价值;破译的时间超出了信息的有效期破译的时间超出了信息的有效期.7关于对称密码关于对称密码.关于对称密码关于对称密码.u历史悠久历史悠久u经验比例大经验比例大u理论结果少理论结果少u算法复杂算法复杂x 破译的代价或者时间难于准确估计破译的代价或者时间难于准确估计v密钥长度密钥长度v数据块大小数据块大小8古典密码
5、古典密码uSubstitution Monoalphabetic cipher Playfair cipher Hill cipher Vigenre cipher uOnetime pad uTransposition u小结小结 9Monoalphabetic cipheruCaesar cipher E(p)=(p+3)mod 26 abcdefghijklmnopqrstuvwxyz DEFGHIJKLMNOPQRSTUVWXYZABC 例子例子:crypt=FUBSWu任意的单表替换密码任意的单表替换密码 abcdefghijklmnopqrstuvwxyz SDVJKLTIOXCF
6、AWQZUPYREGHBNM 例子例子:crypt=VPNZR10单表替换密码的破译单表替换密码的破译u密钥空间为密钥空间为26!4*1026u通过字母的使用频率破译通过字母的使用频率破译11Playfair cipheru55变换矩阵变换矩阵:I与与J视为同一字符视为同一字符C R Y P TO G A H BD E F I K(cryptography)L M N Q SU V W X Zu加密规则加密规则:按成对字母加密按成对字母加密 成对重复字母加分隔符成对重复字母加分隔符(如如x)balloon ba lx lo on 同行取右边同行取右边:rt YC 同列同列取下边取下边:fw N
7、Y 其他其他取交叉取交叉:ly NC,GK BE12Playfair cipher-例子例子u以前面的以前面的55变换矩阵变换矩阵(cryptography)为例为例:C R Y P TO G A H BD E F I KL M N Q SU V W X ZuExamples looklo okUD BD fillfi lx lxIK QU QU jigsawjx ig sa wxQP EH NB XZ cryptocr yp toRY PT CB13Playfair cipher-小结小结uPlayfair有有26*26种字母对组合种字母对组合u字符出现几率一定程度上被均匀化字符出现几率一定
8、程度上被均匀化u基于基于字母字母频率的攻击比较困难频率的攻击比较困难u依然保留了相当的结构信息依然保留了相当的结构信息 14Hill cipheru基于矩阵的线性变换基于矩阵的线性变换:C=KPuK是一个是一个m*m矩阵矩阵,在在Z26上可逆上可逆,即存在即存在K-1使使得得:KK-1=I(在在Z26上上)17 17 05 04 09 15 K=21 18 21 K-1 =15 17 06 02 02 19 24 00 17u完全隐藏了字符完全隐藏了字符(对对)的频率的频率u线性变换的安全性很脆弱线性变换的安全性很脆弱15Vigenre cipheru多表代换密码多表代换密码一个单代换表的集合
9、一个单代换表的集合密钥决定何时使用哪个单表密钥决定何时使用哪个单表uVigenre cipher使用使用Caesar密码作为基密码作为基础单代换表集合础单代换表集合:EK(P)=(K-a)+P mod 26u(子子)密钥与明文一样长密钥与明文一样长16Vigenre cipher-例子例子uEK(P)=(K-a)+P mod 26 a b c d e f g h i j k l m 000102 030405 060708 091011 12 n o p q r s t u v w x y z 131415 161718 192021 222324 25key:cryptographycryp
10、tographycrplain:yourpackagereadyroomathreecipher:AFSGIOI17Vigenre cipher-破译破译u依然保留了字符频率某些统计信息依然保留了字符频率某些统计信息u间距是密钥长度整数倍子串有相同密文间距是密钥长度整数倍子串有相同密文:a b c d e f g h i j k l m 000102 030405 060708 091011 12 n o p q r s t u v w x y z 131415 161718 192021 222324 25key:cryptographycryptographycrplain:yourpac
11、kagereadyroomathreecipher:AFSGIOI PG PG18Onetime paduVigenre本人建议密钥与明文一样长本人建议密钥与明文一样长uGillbert Vernam建议密钥与明文一样长建议密钥与明文一样长并且没有统计特性并且没有统计特性:Ci=Pi Kiu进一步的改进是使用完全随机的串作为进一步的改进是使用完全随机的串作为密钥密钥:Onetime padu密钥的交换与保管十分困难密钥的交换与保管十分困难u加密的信息有长度限制加密的信息有长度限制19Transpositionu换位密码把明文按列写入换位密码把明文按列写入,按行读出按行读出u密钥包含密钥包含3方
12、面信息方面信息:行宽行宽,列高列高,读出顺序读出顺序key:4 3 1 2 5 6 7plaintext:a t t a c k p o s t p o n e d u n t i l t w o a m x y zciphertext:TTNAAPTMTSUOAODWCOIXPETZu完全保留字符的统计信息完全保留字符的统计信息u使用多轮加密可提高安全性使用多轮加密可提高安全性20古典密码小结古典密码小结uSubstitution&permutationu密码分析密码分析u多轮加密多轮加密u数据安全基于算法的保密数据安全基于算法的保密21分组密码设计要求分组密码设计要求uDiffusion(
13、弥散弥散)密文没有统计特征，明文一位影响密密文没有统计特征，明文一位影响密文的多位，密钥的一位也影响密文的文的多位，密钥的一位也影响密文的多位多位uConfusion(混淆混淆)明文与密文、密钥与密文的依赖关系明文与密文、密钥与密文的依赖关系充分复杂充分复杂u结构简单、易于分析结构简单、易于分析22Feistel结构图结构图23Feistel结构定义结构定义u加密加密:Li =Ri-1;Ri=Li-1 F(Ri-1,Ki)u解密解密:Ri-1=Li Li-1=Ri F(Ri-1,Ki)=Ri F(Li,Ki)24Feistel结构分析结构分析uBlock size(64 128)uKey si
14、ze(56 128256)uNumber of rounds(16)Subkey generation Round function(F)lFast software encryption/decryptionlEasy hardware implementationlSimple structurelEase of analysis25DESuDES概述概述uDES结构结构详解详解 uDES安全性分析安全性分析 u多重多重DES 26Some post DES algorithmsuIDEA uBlowfishuRC5uCAST-12827分组密码工作模式分组密码工作模式uElectroni
15、c Codebook Mode uCipher Block Chaining Mode lCipher Feedback Mode lOutput Feedback Mode 28AES介绍介绍l1997年年NIST宣布征集宣布征集AES算法算法要求要求:与与Tripe DES比要快且至少一样安比要快且至少一样安全全,分组分组128位位,密钥密钥128/192/256位位l1998年确定第一轮年确定第一轮15个候选者个候选者l1999年确定第二轮五个候选者年确定第二轮五个候选者:MARS,RC6,Rijndael,Serpent,Twofishl2000年底年底Rijndael成为胜利者成为胜
16、利者29有限域有限域GF(28)(一一)l字节字节b=b7b6b5b4b3b2b1b0看成系数属于看成系数属于0,1的的多项式多项式:b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0如如:A7 10100111 x7+x5+x2+x+1l加法加法:0,1上加法上加法(等价于按位等价于按位XOR)l乘法乘法:多项式模乘多项式模乘,模为模为(11B):m(x)=x8+x4+x3+x+1如如:(x7+x6+x+1)(x5+x+1)=x12+x11+x5+x2+1 =x6+x4+x2+x mod(x8+x4+x3+x+1)lm(x)不可约不可约30有限域有限域GF(28)(二二
17、)l对次数低于对次数低于8的的b(x)(非非0),扩展扩展Euclid算法可计算法可计算出算出a(x),c(x)使得使得:b(x)a(x)+m(x)c(x)=1 b(x)a(x)=1 mod m(x)b-1(x)=a(x)mod m(x)l集合集合0255构成有限域构成有限域GF(28)lGF(28)上上b(x)乘乘x(02):记作记作xtime(b)x b(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x若若b7为为0,则从字节上看是一个左移位则从字节上看是一个左移位;否则否则,还需还需要减去要减去m(x),从字节上看是与从字节上看是与1B作作XOR.31
18、有限域有限域GF(28)上多项式上多项式u4-byte向量向量GF(28)元素为系数多项式元素为系数多项式(4次次)u加法加法:对应系数的加法对应系数的加法(XOR)u乘法乘法:多项式模乘多项式模乘,M(x)=x4+1xj mod M(x)=xj mod 4 a(x)=a3x3+a2x2+a1x+a0,b(x)=b3x3+b2x2+b1x+b0 d(x)=a(x)b(x)=d3x3+d2x2+d1x+d0 mod M(x)|d0|a0 a3 a2 a1|b0|d1|a1 a0 a3 a2|b1|d2|=|a2 a1 a0 a3|b2|d3|a3 a2 a1 a0|b3|ux b(x)=b3x4
19、+b2x3+b1x2+b0 x=b2x3+b1x2+b0 x+b3即按字节循环左移位即按字节循环左移位.32Rijndael简介简介u不属于不属于Feistel结构结构u加密、解密相似但不对称加密、解密相似但不对称u支持支持128/192/256(/32=Nb)数据块大数据块大小小u支持支持128/192/256(/32=Nk)密钥长度密钥长度u结构简单结构简单u速度快速度快33Rijndael简介简介(续续)u数据数据/密钥的矩阵表示密钥的矩阵表示uNumber of rounds34Rijndael:overviewu首轮前执行首轮前执行AddRoundKey(State,RoundKey
20、)uRound(State,RoundKey)ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey);uFinalRound(State,RoundKey)ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey);35Rijndael:AddRoundKeyu按按字节在字节在GF(28)上上相加相加(XOR)=36Rijndael:ByteSubuByteSub(S-box)非线性、可逆非线性、可逆u独立作用在每个字节上独立作用在每个字节上
21、u先取乘法的逆先取乘法的逆,再经过再经过GF(2)上一个仿射变换上一个仿射变换aijbij37Rijndael:ShiftRowu第一行保持不变第一行保持不变,其他行内的字节循环移位其他行内的字节循环移位38Rijndael:MixColumn示意图示意图u列作为列作为GF(28)上多项式乘以多项式上多项式乘以多项式c(x)u模模M(x)=x4+139Rijndael:MixColumnu多项式多项式c(x)=03x3+01x2+01x+02uM(x)=x4+1=(x2+1)(x2+1)uc(x)与模与模M(x)=x4+1互素互素ub(x)=c(x)a(x)|b0|02 03 01 01|a0
22、|b1|01 02 03 01|a1|b2|=|01 01 02 03|a2|b3|03 01 01 02|a3|uc(x)的逆的逆:0Bx3+0Dx2+09x+0E40Rijndael:AddRoundKeyu按按字节在字节在GF(28)上上相加相加=41Rijndael:Key schedule(1)u主密钥生成子密钥数组主密钥生成子密钥数组,(Nr+1)*Nb个字个字uNk=6KeyExpansion(byte Key4*Nk,word WNb*(Nr+1)for(i=0;iNk;i+)Wi=(Key4*i,Key4*i|+1,Key4*i+2,Key4*i+3);for(i=Nk;iN
23、b*(Nr+1);i+)temp=Wi-1;if(i%Nk=0)temp=ByteSub(temp6KeyExpansion(byte Key4*Nk,word WNb*(Nr+1)for(i=0;iNk;i+)Wi=(Key4*i,Key4*i|+1,Key4*i+2,Key4*i+3);for(i=Nk;iNb*(Nr+1);i+)temp=Wi-1;if(i%Nk=0)temp=ByteSub(temp8)Rconi/Nk;else if(i%Nk=4)temp=ByteSub(temp8);Wi=Wi-Nktemp;uRconi=(xi,00,00,00);xi为为GF(28)上的数上
24、的数.43Rijndael:encrypt structureRijndael(State,CipherKey)KeyExpansion(CipherKey,ExpandedKey);AddRoundKey(State,ExpandedKey)For(i=1;iNr;+i)ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,ExpandedKey+Nb*i);ByteSub(State);ShiftRow(State);AddRoundKey(State,ExpandedKey+Nb*i);44Rijndael:d
25、ecrypt structureAddRoundKey()For(i=1;iNr;+i)ByteSub();ShiftRow();MixColumn();AddRoundKey()ByteSub();ShiftRow();AddRoundKey()I_AddRoundKey()I_ShiftRow();I_ByteSub();For(i=1;iNr;+i)I_AddRoundKey()I_MixColumn();I_ShiftRow();I_ByteSub();I_AddRoundKey()I_AddRoundKey()For(i=1;iNr;+i)I_ShiftRow();I_ByteSub
26、();I_AddRoundKey()I_MixColumn();I_ShiftRow();I_ByteSub();I_AddRoundKey()45Rijndael安全性安全性l没有发现弱密钥或补密钥没有发现弱密钥或补密钥l能抵抗已知的密码分析手段能抵抗已知的密码分析手段46DES示意图示意图47DES:single roundLi=Ri-1 Ri=Li-1 F(Ri-1,Ki)48DES:Function FExpansion:32 48 S-box:6 4 Permutation:49DES:Subkey generation50DES安全性安全性分析分析u差分密码分析差分密码分析 u线性
27、密码分析线性密码分析 u密钥密钥短短穷举破译穷举破译 u字典攻击字典攻击 uF函数函数(S-Box)设计原理未知设计原理未知 u轮数轮数问题问题u弱密钥与半弱密钥弱密钥与半弱密钥 u小结小结51多重多重DESuDES是否构成一个闭合群是否构成一个闭合群?任给任给K1,K2,是否存在是否存在K3,使得使得:EK1EK2=EK3uDouble DES uTriple DES 52DES:Expansion table32|01 02 03 04|0504|05 06 07 08|0908|09 10 11 12|1312|13 14 15 16|1716|17 18 19 20|2120|21 2
28、2 23 24|2524|25 26 27 28|2928|29 30 31 32|0153DES:S-box(S1)14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 0700 15 07 04 14 02 13 01 10 06 12 11 09 05 03 0804 01 14 08 13 06 02 11 15 12 09 07 03 10 05 0015 12 08 02 04 09 01 07 05 11 03 14 10 00 06 1354DES:Permutation16 07 20 21 29 12 28 1701 15 23 26 0
29、5 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04 2555DES:差分密码分析差分密码分析u破解破解DES:247个个选择选择明文明文(255个个已知已知明文明文)u破解破解Lucifer(18轮轮128位位):24个选择明文个选择明文221次计算次计算uDES对差分密码分析的抵抗力很强对差分密码分析的抵抗力很强56DES:线性密码分析线性密码分析u破解破解DES:243个个已知已知明文明文uDES对线性密码分析的抵抗力稍弱对线性密码分析的抵抗力稍弱57DES:穷举破译穷举破译uDES密钥长度密钥长度:56位位,2561017u计算机能
30、力为计算机能力为100MIPS次次(108)/秒秒,1万万台计算机协同工作一天，计算能力为台计算机协同工作一天，计算能力为:108*10000*24*36001017u1017/1017=1天天58DES:字典攻击字典攻击u考虑选择明文攻击考虑选择明文攻击uDES块大小块大小:64位位,2641020u计算机能力为计算机能力为100MIPS(108)/秒秒,1万台万台计算机协同工作一天，计算能力为计算机协同工作一天，计算能力为:108*10000*24*36001017u1020/1017=1000天天u适用于任意适用于任意64位块的加密位块的加密59DES:S-box设计准则设计准则uS-b
31、ox是是DES的核心的核心(全部非线性所在全部非线性所在)S-box每行是每行是015的一个置换的一个置换 S-box输出不是输入的线性或者放射变换输出不是输入的线性或者放射变换 S-box输入一位改变输入一位改变,输出至少二位改变输出至少二位改变 S(x)与与S(x 001100)至少二位不同至少二位不同 S(x)!=S(x 00ef00),对对任意任意e,f 0,1 固定一位固定一位,其它五位变化其它五位变化,输出数字中的输出数字中的0和和1的总数接近相等的总数接近相等60DES:弱密钥与半弱密钥弱密钥与半弱密钥u弱密钥弱密钥:EK EK=Iu半弱密钥半弱密钥:EK1=EK2u不影响安全性
32、不影响安全性u互补性互补性:若若y=DESk(x),则把则把x,y,k都取都取补补,等式仍然成立等式仍然成立.61Double DES C=EK2(EK1(P)P=DK1(DK2(C)62Double DES安全性安全性l中间相会中间相会(meet-in-the-middle)攻击攻击 C=EK2(EK1(P)X=EK1(P)=DK2(C)u给定明文密文对给定明文密文对(P,C)对所有对所有256个密钥个密钥,加密加密P,对结果排序对结果排序 对所有对所有256个密钥个密钥,解密解密C,对结果排序对结果排序 逐个比较逐个比较,找出找出K1,K2使得使得EK1(P)=DK2(C)一个明文密文对一
33、个明文密文对,误警次数误警次数2112/264=248两个明文密文对两个明文密文对,误警次数误警次数248/264=2-1663Triple DESC=EK3(DK2(EK1(P)P=DK1(EK2(DK3(C)64Triple DES分析分析uWith two keys:C=EK1(DK2(EK1(P)256可选择明文可选择明文256次计算次计算 uWith three keys:C=EK3(DK2(EK1(P)比比two-key更更安全安全lTripe DES速度慢速度慢65Electronic Codebook ModelECB:Ci=EK(Pi)Pi=DK(Ci)u相同明文相同明文相同
34、相同密文密文u同样信息多次出现造成泄漏同样信息多次出现造成泄漏u信息块可被替换信息块可被替换u信息块可被重排信息块可被重排u密文块损坏密文块损坏仅仅对应明文块损坏对应明文块损坏 适合于传输短信息适合于传输短信息66ECB示意图示意图67Cipher Block Chaining ModelCBC:加密加密:Ci=EK(Ci-1 Pi)解密解密:Pi=EK(Ci)Ci-1 u需要共同的初始化向量需要共同的初始化向量C-1(IV)u相同明文相同明文不同不同密文密文u初始化向量初始化向量IV可以用来改变第一块可以用来改变第一块P0=EK(C0)C-1u密文块损坏密文块损坏两两明文明文块块损坏损坏 安
35、全性好于安全性好于ECB68CBC示意图示意图69Cipher Feedback ModelCFB:分组密码分组密码流密码流密码 Si 为为移位寄存器移位寄存器,j为流单元宽度为流单元宽度 加密加密:Ci=Pi(EK(Si)的高的高j位位)Si+1=(Sij)|Ci 解密解密:Pi=Ci(EK(Si)的高的高j位位)Si+1=(Sij)|Ci u需要共同的移位寄存器初始值需要共同的移位寄存器初始值S0u一个单元损坏影响多个单元一个单元损坏影响多个单元:(W+j-1)/j W为为分组加密块大小分组加密块大小70CFB加密示意图加密示意图Ci=Pi(EK(Si)的高的高j位位);Si+1=(Sij
36、)|Ci 71CFB解密示意图解密示意图Pi=Ci(EK(Si)的高的高j位位);Si+1=(Sij)|Ci 72Output Feedback ModelOFB:分组密码分组密码流密码流密码 Si 为为移位寄存器移位寄存器,j为流单元宽度为流单元宽度 加密加密:Ci=Pi(EK(Si)的高的高j位位)Si+1=(Sij)|(EK(Si)的高的高j位位)解密解密:Pi=Ci(EK(Si)的高的高j位位)Si+1=(Sij)|(EK(Si)的高的高j位位)u需要共同的移位寄存器初始值需要共同的移位寄存器初始值S0=一个单元损坏只影响对应单元一个单元损坏只影响对应单元=安全性较安全性较CFB差差7
37、3OFB加密示意图加密示意图Ci=Pi(EK(Si)的高的高j位位);Si+1=(Sij)|(EK(Si)的高的高j位位)74OFB解密示意图解密示意图Pi=Ci(EK(Si)的高的高j位位);Si+1=(Sij)|(EK(Si)的高的高j位位)75IDEAl1990年发表年发表,1992修改修改l64位块位块,128位密钥位密钥,不属于不属于Feistel结结构构l运算运算:XOR,216模加模加,(216+1)模乘模乘l三种运算均不满足分配律与结合律三种运算均不满足分配律与结合律l有大量弱密钥有大量弱密钥l难以直接扩展到难以直接扩展到128位块位块76实习作业之一实习作业之一l实现实现DES,要求要求:Linux平台平台,C和和/或或C+语言语言;四种模式四种模式(ECB,CBC,CFB和和OFB)的的加解密加解密加解密正确性测试及性能测试加解密正确性测试及性能测试提交完整源码提交完整源码(能编译并运行能编译并运行)与性与性能测试报告能测试报告十月十日前完成十月十日前完成77