密码算法与应用基础

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Institute of Computer Science & Technology, Peking University,二、对称密钥密码,密码算法与应用基础,1,信息安全引论,对称密钥密码,对称密钥密码应用基础,公开密钥密码,数字签名与,Hash,函数,公开密钥密码应用基础,密钥交换与密钥管理,内容提要,2,对称密钥密码,概述,古典密码,Feistel,结构,DES,Some post DES algorithms,分组密码工作模式,Rijndael,整理发布,3,加密与解密,加密与解密,加密:,E: (X,K),Y, y = E(x,k),固定,k,E,k,:X,Y,E,k,是单值映射,E,k,(x,1,) != E,k,(x,2,) if x,1,!= x,2,E,k,逆映射解密,记为,D,k,: Y,X,许多时候,Y,X,这样,可以执行多次加密:,E,k,E,k,.,E,k,4,密码分类,密码系统的几种分类,按执行的操作,替换(,substitution),与换位(,permutation),按密钥的数量,单密钥(对称密钥)与双密钥(公开密钥),按明文处理方式,流密码(,stream cipher),与分组密码(,block cipher),5,密码分析,密码分析(破译),Ciphertext,only,已知:,Ciphertext,Known plaintext(,已知明文攻击),已知: 部分明文密文对,Chosen plaintext(,选择明文攻击),可以选择任意明文并得到对应的密文,Chosen,ciphertext,(,选择密文攻击),可以选择部分密文并得到对应的明文,6,密码算法的安全性,密码算法的安全性,Unconditionally secure,无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性.,Onetime pad,Computationally secure,破译的代价超出信息本身的价值;,破译的时间超出了信息的有效期.,7,关于对称密码.,关于对称密码.,历史悠久,经验比例大,理论结果少,算法复杂,破译的代价或者时间难于准确估计,密钥长度,数据块大小,8,古典密码,Substitution,Monoalphabetic,cipher,Playfair,cipher,Hill cipher,Vigen,re cipher,Onetime pad,Transposition,小结,9,Monoalphabetic cipher,Caesar cipher,E(p) = (p+3) mod 26,abcdefghijklmnopqrstuvwxyz,DEFGHIJKLMNOPQRSTUVWXYZABC,例子:,crypt = FUBSW,任意的单表替换密码,abcdefghijklmnopqrstuvwxyz,SDVJKLTIOXCFAWQZUPYREGHBNM,例子:,crypt = VPNZR,10,单表替换密码的破译,密钥空间为26! 4 * 10,26,通过字母的使用频率破译,11,Playfair cipher,5,5变换矩阵,:,I,与,J,视为同一字符,C R Y P T,O G A H B,D E F I K (cryptography),L M N Q S,U V W X Z,加密规则:按成对字母加密,成对重复字母加分隔符(如,x),balloon,ba,lx lo on,同行取右边:,rt,YC,同列,取下边:,fw,NY,其他,取交叉:,ly,NC, GK,BE,12,Playfair cipher-例子,以前面的55变换矩阵(,cryptography),为例:,C R Y P T,O G A H B,D E F I K,L M N Q S,U V W X Z,Examples,look,lo ok,UD BD,fill,fi lx lx,IK QU QU,jigsaw,jx ig sa wx,QP EH NB XZ,crypto,cr yp,to,RY PT CB,13,Playfair cipher-小结,Playfair,有26*26种字母对组合,字符出现几率一定程度上被均匀化,基于,字母,频率的攻击比较困难,依然保留了相当的结构信息,14,Hill cipher,基于矩阵的线性变换:,C = KP,K,是一个,m*m,矩阵,在,Z,26,上可逆,即存在,K,-1,使得:,KK,-1,= I (,在,Z,26,上),17 17 05 04 09 15,K = 21 18 21 K,-1,= 15 17 06,02 02 19 24 00 17,完全隐藏了字符(对)的频率,线性变换的安全性很脆弱,15,Vigenre cipher,多表代换密码,一个单代换表的集合,密钥决定何时使用哪个单表,Vigen,re cipher,使用,Caesar,密码作为基础单代换表集合:,E,K,(P) = (K-a)+P mod 26,(,子),密钥与明文一样长,16,Vigenre cipher-,例子,E,K,(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 25,key:,cryptographycryptographycr,plain:,yourpackagereadyroomathree,cipher:AFSGIOI,17,Vigenre cipher-,破译,依然保留了字符频率某些统计信息,间距是密钥长度整数倍子串有相同密文:,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 25,key:,cryptographycryptographycr,plain:,yourpackagereadyroomathree,cipher:AFSGIOI PG PG,18,Onetime pad,Vigen,re,本人建议密钥与明文一样长,Gillbert Vernam,建议密钥与明文一样长并且没有统计特性:,C,i,= P,i,K,i,进一步的改进是使用完全随机的串作为密钥:,Onetime pad,密钥的交换与保管十分困难,加密的信息有长度限制,19,Transposition,换位密码把明文按列写入,按行读出,密钥包含3方面信息: 行宽,列高,读出顺序,key: 4 3 1 2 5 6 7,plaintext: 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 z,ciphertext,:TTNAAPTMTSUOAODWCOIXPETZ,完全保留字符的统计信息,使用多轮加密可提高安全性,20,古典密码小结,Substitution & permutation,密码分析,多轮加密,数据安全基于算法的保密,21,分组密码设计要求,Diffusion(,弥散,),密文没有统计特征，明文一位影响密文的多位，密钥的一位也影响密文的多位,Confusion(,混淆),明文与密文、密钥与密文的依赖关系充分复杂,结构简单、易于分析,22,Feistel,结构图,23,Feistel,结构定义,加密:,L,i,=,R,i,-1,;,R,i,= L,i-1,F(,R,i,-1,K,i,),解密:,R,i,-1,= L,i,L,i-1,=,R,i,F(,R,i,-1,K,i,),=,R,i,F(L,i,K,i,),24,Feistel,结构分析,Block size(64,128),Key size(56, 128256,),Number of rounds(16),Subkey,generation,Round function(F),Fast software encryption/decryption,Easy hardware implementation,Simple structure,Ease of analysis,25,DES,DES,概述,DES,结构,详解,DES,安全性分析,多重,DES,26,Some post DES algorithms,IDEA,Blowfish,RC5,CAST-128,27,分组密码工作模式,Electronic Codebook Mode,Cipher Block Chaining Mode,Cipher Feedback Mode,Output Feedback Mode,28,AES介绍,1997年,NIST,宣布征集,AES,算法,要求: 与,Tripe DES,比要快且至少一样安全,分组128位,密钥128/192/256位,1998,年确定第一轮15个候选者,1999,年确定第二轮五个候选者:,MARS, RC6,Rijndael, Serpent,Twofish,2000,年底,Rijndael,成为胜利者,29,有限域GF(2,8,),(一),字节,b=b,7,b,6,b,5,b,4,b,3,b,2,b,1,b,0,看成系数属于0,1的多项式:,b,7,x,7,+b,6,x,6,+b,5,x,5,+b,4,x,4,+b,3,x,3,+b,2,x,2,+b,1,x+b,0,如:,A7,10100111,x,7,+x,5,+x,2,+x+1,加法: 0,1上加法(等价于按位,XOR),乘法: 多项式模乘,模为(11,B):,m(x) = x,8,+x,4,+x,3,+x+1,如: (,x,7,+x,6,+x+1)(x,5,+x+1)=x,12,+x,11,+x,5,+x,2,+1,=x,6,+x,4,+x,2,+x mod (x,8,+x,4,+x,3,+x+1),m(x),不可约,30,有限域GF(2,8,),(二),对次数低于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),集合0255构成有限域,GF(2,8,),GF(2,8,),上,b(x),乘,x(02):,记作,xtime,(b),x,b(x)=b,7,x,8,+b,6,x,7,+b,5,x,6,+b,4,x,5,+b,3,x,4,+b,2,x,3,+b,1,x,2,+b,0,x,若,b,7,为0,则从字节上看是一个左移位;否则,还需要减去,m(x),从字节上看是与1,B,作,XOR.,31,有限域GF(2,8,)上多项式,4-,byte,向量,GF(2,8,),元素为系数多项式(4次),加法: 对应系数的加法(,XOR),乘法: 多项式模乘,M(x)=x,4,+1,x,j,mod M(x) =,x,j,mod 4,a(x)= a,3,x,3,+a,2,x,2,+a,1,x+a,0, b(x)= b,3,x,3,+b,2,x,2,+b,1,x+b,0,d(x) = a(x)b(x) = d,3,x,3,+d,2,x,2,+d,1,x+d,0,mod M(x),|d,0,| |a,0,a,3,a,2,a,1,| |b,0,|,|d,1,| |a,1,a,0,a,3,a,2,| |b,1,|,|d,2,| = |a,2,a,1,a,0,a,3,| |b,2,|,|d,3,| |a,3,a,2,a,1,a,0,| |b,3,|,x,b(x) = b,3,x,4,+b,2,x,3,+b,1,x,2,+b,0,x = b,2,x,3,+b,1,x,2,+b,0,x+b,3,即按字节循环左移位.,32,Rijndael简介,不属于,Feistel,结构,加密、解密相似但不对称,支持128/192/256(/32=,Nb,),数据块大小,支持128/192/256(/32=,Nk,),密钥长度,结构简单,速度快,33,Rijndael简介(续),数据/密钥的矩阵表示,a,00,a,01,a,02,a,03,a,04,a,05,a,10,a,11,a,12,a,13,a,14,a,15,a,20,a,21,a,22,a,23,a,24,a,25,a,30,a,31,a,32,a,33,a,34,a,35,k,00,k,01,k,02,k,03,k,10,k,11,k,12,k,13,k,20,k,21,k,22,k,23,k,30,k,31,k,32,k,33,Nr,Nb=4,Nb=6,Nb=8,Nk=4,10,12,14,Nk=6,12,12,14,Nk=8,14,14,14,Number of rounds,34,Rijndael: 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,); ,35,Rijndael: AddRoundKey,按,字节在,GF(2,8,),上,相加(,XOR),a,00,a,01,a,02,a,03,a,04,a,05,a,10,a,11,a,12,a,13,a,14,a,15,a,20,a,21,a,22,a,23,a,24,a,25,a,30,a,31,a,32,a,33,a,34,a,35,k,00,k,01,k,02,k,03,k,04,k,05,k,10,k,11,k,12,k,13,k,14,k,15,k,20,k,21,k,22,k,23,k,24,k,25,k,30,k,31,k,32,k,33,k,34,k,35,=,b,00,b,01,b,02,b,03,b,04,b,05,b,10,b,11,b,12,b,13,b,14,b,15,b,20,b,21,b,22,b,23,b,24,b,25,b,30,b,31,b,32,b,33,b,34,b,35,36,Rijndael: ByteSub,ByteSub,(S-box),非线性、可逆,独立作用在每个字节上,先取乘法的逆,再经过,GF(2),上一个仿射变换,a,00,a,01,a,02,a,03,a,04,a,05,a,10,a,11,a,12,a,13,a,14,a,15,a,20,a,21,a,22,a,23,a,24,a,25,a,30,a,31,a,32,a,33,a,34,a,35,b,00,b,01,b,02,b,03,b,04,b,05,b,10,b,11,b,12,b,13,b,14,b,15,b,20,b,21,b,22,b,23,b,24,b,25,b,30,b,31,b,32,b,33,b,34,b,35,S-box,a,ij,b,ij,37,Rijndael: ShiftRow,第一行保持不变,其他行内的字节循环移位,38,Rijndael: MixColumn示意图,列作为,GF(2,8,),上多项式乘以多项式,c(x),模,M(x) = x,4,+1,39,Rijndael: MixColumn,多项式,c(x) = 03x,3,+ 01x,2,+ 01x+ 02,M(x) = x,4,+1=(x,2,+1),(x,2,+1),c(x),与模,M(x) = x,4,+1,互素,b(x)=c(x),a(x),|b,0,| |02 03 01 01| |a,0,|,|b,1,| |01 02 03 01| |a,1,|,|b,2,| = |01 01 02 03| |a,2,|,|b,3,| |03 01 01 02| |a,3,|,c(x),的逆:,0,Bx,3,+ 0Dx,2,+ 09x+ 0E,40,Rijndael: AddRoundKey,按,字节在,GF(2,8,),上,相加,a,00,a,01,a,02,a,03,a,04,a,05,a,10,a,11,a,12,a,13,a,14,a,15,a,20,a,21,a,22,a,23,a,24,a,25,a,30,a,31,a,32,a,33,a,34,a,35,k,00,k,01,k,02,k,03,k,04,k,05,k,10,k,11,k,12,k,13,k,14,k,15,k,20,k,21,k,22,k,23,k,24,k,25,k,30,k,31,k,32,k,33,k,34,k,35,=,b,00,b,01,b,02,b,03,b,04,b,05,b,10,b,11,b,12,b,13,b,14,b,15,b,20,b,21,b,22,b,23,b,24,b,25,b,30,b,31,b,32,b,33,b,34,b,35,41,Rijndael: Key schedule(1),主密钥生成子密钥数组, (,Nr+1)*,Nb,个字,Nk,=6,KeyExpansion,(byte Key4*,Nk, word W,Nb,*(Nr+1) ,for(i=0;i,Nk,;i+),Wi=(Key4*i, Key4*i|+1, Key4*i+2, Key4*i+3);,for(i=,Nk,;i,Nb,*(Nr+1);i+) ,temp=Wi-1;,if(i%,Nk,= 0),temp=,ByteSub,(temp6,KeyExpansion,(byte Key4*,Nk, word W,Nb,*(Nr+1) ,for(i=0;i,Nk,;i+),Wi=(Key4*i, Key4*i|+1, Key4*i+2, Key4*i+3);,for(i=,Nk,;i,Nb,*(Nr+1);i+) ,temp=Wi-1;,if(i%,Nk,= 0),temp=,ByteSub,(temp8),Rcon,i/,Nk,;,else if(i%,Nk,= 4),temp=,ByteSub,(temp8);,Wi=Wi-,Nk,temp;,; ;,Rcon,i=(,x,i, 00 , 00 , 00);,x,i,为,GF(2,8,),上的数.,43,Rijndael: encrypt structure,Rijndael(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);,44,Rijndael: decrypt structure,AddRoundKey(),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();,I_AddRoundKey(),I_MixColumn();,I_ShiftRow();,I_ByteSub();,I_AddRoundKey(),45,Rijndael安全性,没有发现弱密钥或补密钥,能抵抗已知的密码分析手段,46,DES,示意图,47,DES: single round,L,i,= R,i-1,R,i,= L,i-1,F(R,i-1,K,i,),48,DES: Function F,Expansion: 32,48,S-box: 6, 4,Permutation:,49,DES: Subkey generation,50,DES,安全性,分析,差分密码分析,线性密码分析,密钥,短,穷举破译,字典攻击,F,函数(,S-Box),设计原理未知,轮数,问题,弱密钥与半弱密钥,小结,51,多重,DES,DES,是否构成一个闭合群?,任给,K,1,K,2,是否存在,K,3,使得:,E,K1,E,K2,= E,K3,Double DES,Triple DES,52,DES: Expansion table,32 | 01 02 03 04 | 05,04 | 05 06 07 08 | 09,08 | 09 10 11 12 | 13,12 | 13 14 15 16 | 17,16 | 17 18 19 20 | 21,20 | 21 22 23 24 | 25,24 | 25 26 27 28 | 29,28 | 29 30 31 32 | 01,53,DES: S-box(S1),14,04 13 01 02 15 11 08,03,10 06 12 05 09 00 07,00,15 07 04 14 02 13 01,10,06 12 11 09 05 03 08,04,01 14 08 13 06 02 11,15,12 09 07 03 10 05 00,15,12 08 02 04 09 01 07,05,11 03 14 10 00 06 13,54,DES: Permutation,16 07 20 21 29 12 28 17,01 15 23 26 05 18 31 10,02 08 24 14 32 27 03 09,19 13 30 06 22 11 04 25,55,DES: 差分密码分析,破解,DES: 2,47,个,选择,明文(2,55,个,已知,明文),破解,Lucifer(18,轮128位,): 24,个选择明文2,21,次计算,DES,对差分密码分析的抵抗力很强,56,DES: 线性密码分析,破解,DES: 2,43,个,已知,明文,DES,对线性密码分析的抵抗力稍弱,57,DES: 穷举破译,DES,密钥长度: 56位, 2,56,10,17,计算机能力为100MIPS次(10,8,),/秒,1万台计算机协同工作一天，计算能力为:,10,8,*10000*24*360010,17,10,17,/10,17,= 1天,58,DES: 字典攻击,考虑选择明文攻击,DES,块大小: 64位, 2,64,10,20,计算机能力为100MIPS(10,8,),/,秒,1万台计算机协同工作一天，计算能力为:,10,8,*10000*24*360010,17,10,20,/10,17,= 1000天,适用于任意64位块的加密,59,DES: S-box设计准则,S-box,是,DES,的核心(全部非线性所在),S-box每行是015的一个置换,S-box输出不是输入的线性或者放射变换,S-box输入一位改变,输出至少二位改变,S(x),与,S(x,001100),至少二位不同,S(x) != S(x,00ef00),对,任意,e,f,0,1,固定一位,其它五位变化,输出数字中的0和1的总数接近相等,60,DES: 弱密钥与半弱密钥,弱密钥:,E,K,E,K,= I,半弱密钥:,E,K1,= E,K2,不影响安全性,互补性,: 若,y=,DES,k,(x),则把,x,y,k,都取,补,等式仍然成立.,61,Double DES,C = E,K2,(,E,K1,(P),P = D,K1,(D,K2,(C),62,Double DES,安全性,中间相会(meet-in-the-middle)攻击,C = E,K2,(,E,K1,(P),X = E,K1,(P) = D,K2,(,C),给定明文密文对(,P,C),对所有2,56,个密钥,加密,P,对结果排序,对所有2,56,个密钥,解密,C,对结果排序,逐个比较,找出,K,1,K,2,使得,E,K1,(P) = D,K2,(,C),一个明文密文对,误警次数2,112,/2,64,=2,48,两个明文密文对,误警次数2,48,/2,64,=2,-16,63,Triple DES,C=E,K3,(D,K2,(,E,K1,(P),P=D,K1,(,E,K2,(,D,K3,(C),64,Triple DES,分析,With two keys: C=E,K1,(D,K2,(,E,K1,(P),2,56,可选择明文2,56,次计算,With three keys: C=E,K3,(D,K2,(,E,K1,(P),比,two-key,更,安全,Tripe DES,速度慢,65,Electronic Codebook Mode,ECB:,C,i,= E,K,(P,i,),P,i,= D,K,(,C,i,),相同明文,相同,密文,同样信息多次出现造成泄漏,信息块可被替换,信息块可被重排,密文块损坏,仅,对应明文块损坏,适合于传输短信息,66,ECB示意图,67,Cipher Block Chaining Mode,CBC:,加密:,C,i,=E,K,(,C,i,-1,P,i,),解密:,P,i,=E,K,(,C,i,),C,i,-1,需要共同的初始化向量,C,-1,(IV),相同明文,不同,密文,初始化向量,IV,可以用来改变第一块,P,0,=E,K,(C,0,),C,-1,密文块损坏,两,明文,块,损坏,安全性好于,ECB,68,CBC示意图,69,Cipher Feedback Mode,CFB:分组密码,流密码,S,i,为,移位寄存器,j,为流单元宽度,加密:,C,i,=P,i,(,E,K,(,S,i,),的高j位),S,i,+1,=(,S,i,j)|,C,i,解密:,P,i,=,C,i,(,E,K,(,S,i,),的高j位),S,i,+1,=(,S,i,j)|,C,i,需要共同的移位寄存器初始值,S,0,一个单元损坏影响多个单元:,(,W+j-1)/j,W,为,分组加密块大小,70,CFB加密示意图,C,i,=P,i,(,E,K,(S,i,),的高j位),; S,i+1,=(S,i,j)|C,i,71,CFB解密示意图,P,i,=C,i,(,E,K,(S,i,),的高j位),; S,i+1,=(S,i,j)|C,i,72,Output Feedback Mode,O,FB:分组密码,流密码,S,i,为,移位寄存器,j,为流单元宽度,加密:,C,i,=P,i,(,E,K,(,S,i,),的高j位),S,i,+1,=(,S,i,j)|,(,E,K,(,S,i,),的高j位),解密:,P,i,=,C,i,(,E,K,(,S,i,),的高j位),S,i,+1,=(,S,i,j)|,(,E,K,(,S,i,),的高j位),需要共同的移位寄存器初始值,S,0,一个单元损坏只影响对应单元,安全性较,CFB,差,73,OFB加密示意图,C,i,=P,i,(,E,K,(S,i,),的高j位),;S,i+1,=(S,i,j)|,(,E,K,(S,i,),的高j位),74,OFB解密示意图,P,i,=C,i,(,E,K,(S,i,),的高j位),; S,i+1,=(S,i,j)|,(,E,K,(S,i,),的高j位),75,IDEA,1990年发表,1992修改,64位块,128位密钥,不属于,Feistel,结构,运算:,XOR,2,16,模加, (,2,16,+1)模乘,三种运算均不满足分配律与结合律,有大量弱密钥,难以直接扩展到128位块,76,实习作业之一,实现,DES,要求:,Linux,平台,C,和/或,C+,语言,;,四种模式(,ECB, CBC, CFB,和,OFB),的加解密,加解密正确性测试及性能测试,提交完整源码(能编译并运行)与性能测试报告,十月十日前完成,77,