密码算法与应用基础.ppt

1,二、对称密钥密码,密码算法与应用基础,2,信息安全引论 对称密钥密码 对称密钥密码应用基础 公开密钥密码 数字签名与Hash函数 公开密钥密码应用基础 密钥交换与密钥管理,内容提要,3,对称密钥密码,概述 古典密码 Feistel结构 DES Some post DES algorithms 分组密码工作模式 Rijndael ,整理发布,4,加密与解密,加密与解密 加密: E: (X,K) Y, y = E(x,k) 固定k,Ek:X Y Ek是单值映射, Ek(x1) != Ek(x2) if x1 != x2 Ek逆映射解密,记为Dk : Y X 许多时候,YX,这样可以执行多次加密: EkEk.Ek,5,密码分类,密码系统的几种分类 按执行的操作 替换(substitution)与换位(permutation) 按密钥的数量 单密钥(对称密钥)与双密钥(公开密钥) 按明文处理方式 流密码(stream cipher)与分组密码(block cipher),6,密码分析,密码分析(破译) Ciphertext only 已知: Ciphertext Known plaintext(已知明文攻击) 已知: 部分明文密文对 Chosen plaintext(选择明文攻击) 可以选择任意明文并得到对应的密文 Chosen ciphertext(选择密文攻击) 可以选择部分密文并得到对应的明文,7,密码算法的安全性,密码算法的安全性 Unconditionally secure 无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性. Onetime pad Computationally secure 破译的代价超出信息本身的价值; 破译的时间超出了信息的有效期.,8,关于对称密码.,关于对称密码. 历史悠久 经验比例大 理论结果少 算法复杂 破译的代价或者时间难于准确估计 密钥长度 数据块大小 ,9,古典密码,Substitution Monoalphabetic cipher Playfair cipher Hill cipher Vigenre cipher Onetime pad Transposition 小结 ,10,Monoalphabetic cipher,Caesar cipher E(p) = (p+3) mod 26 abcdefghijklmnopqrstuvwxyz DEFGHIJKLMNOPQRSTUVWXYZABC 例子: crypt = FUBSW 任意的单表替换密码 abcdefghijklmnopqrstuvwxyz SDVJKLTIOXCFAWQZUPYREGHBNM 例子: crypt = VPNZR,11,单表替换密码的破译,密钥空间为26! 4 * 1026 通过字母的使用频率破译,12,Playfair cipher,55变换矩阵: 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,13,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,14,Playfair cipher-小结,Playfair有26*26种字母对组合 字符出现几率一定程度上被均匀化 基于字母频率的攻击比较困难 依然保留了相当的结构信息 ,15,Hill cipher,基于矩阵的线性变换: C = KP K是一个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 17 完全隐藏了字符(对)的频率 线性变换的安全性很脆弱 ,16,Vigenre cipher,多表代换密码 一个单代换表的集合 密钥决定何时使用哪个单表 Vigenre cipher使用Caesar密码作为基础单代换表集合: EK(P) = (K-a)+P mod 26 (子)密钥与明文一样长,17,Vigenre cipher-例子,EK(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,18,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 ,19,Onetime pad,Vigenre本人建议密钥与明文一样长 Gillbert Vernam建议密钥与明文一样长并且没有统计特性: Ci = Pi Ki 进一步的改进是使用完全随机的串作为密钥: Onetime pad 密钥的交换与保管十分困难 加密的信息有长度限制 ,20,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 完全保留字符的统计信息 使用多轮加密可提高安全性 ,21,古典密码小结,Substitution & permutation 密码分析 多轮加密 数据安全基于算法的保密 ,22,分组密码设计要求,Diffusion(弥散) 密文没有统计特征，明文一位影响密文的多位，密钥的一位也影响密文的多位 Confusion(混淆) 明文与密文、密钥与密文的依赖关系充分复杂 结构简单、易于分析,23,Feistel,结构图,24,Feistel结构定义,加密: Li = Ri-1; Ri = Li-1F(Ri-1,Ki) 解密: Ri-1 = Li Li-1 = RiF(Ri-1,Ki) = RiF(Li,Ki),25,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 ,26,DES,DES概述 DES结构详解 DES安全性分析 多重DES ,27,Some post DES algorithms,IDEA Blowfish RC5 CAST-128 ,28,分组密码工作模式,Electronic Codebook Mode Cipher Block Chaining Mode Cipher Feedback Mode Output Feedback Mode ,29,AES介绍,1997年NIST宣布征集AES算法 要求: 与Tripe DES比要快且至少一样安全,分组128位,密钥128/192/256位 1998年确定第一轮15个候选者 1999年确定第二轮五个候选者: MARS, RC6, Rijndael, Serpent, Twofish 2000年底Rijndael成为胜利者,30,有限域GF(28)(一),字节b=b7b6b5b4b3b2b1b0看成系数属于0,1的多项式: b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 如:A7 10100111 x7+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+x mod (x8+x4+x3+x+1) m(x)不可约,31,有限域GF(28)(二),对次数低于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(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.,32,有限域GF(28)上多项式,4-byte向量GF(28)元素为系数多项式(4次) 加法: 对应系数的加法(XOR) 乘法: 多项式模乘, M(x)=x4+1 xj 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| xb(x) = b3x4+b2x3+b1x2+b0x = b2x3+b1x2+b0x+b3 即按字节循环左移位.,33,Rijndael简介,不属于Feistel结构 加密、解密相似但不对称 支持128/192/256(/32=Nb)数据块大小 支持128/192/256(/32=Nk)密钥长度 结构简单 速度快,34,Rijndael简介(续),数据/密钥的矩阵表示,Number of rounds,35,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); ,36,Rijndael: AddRoundKey,按字节在GF(28)上相加(XOR),=,37,Rijndael: ByteSub,ByteSub(S-box)非线性、可逆 独立作用在每个字节上 先取乘法的逆,再经过GF(2)上一个仿射变换,aij,bij,38,Rijndael: ShiftRow,第一行保持不变,其他行内的字节循环移位,39,Rijndael: MixColumn示意图,列作为GF(28)上多项式乘以多项式c(x) 模M(x) = x4+1,40,Rijndael: MixColumn,多项式c(x) = 03x3+ 01x2+ 01x+ 02 M(x) = x4+1=(x2+1)(x2+1) c(x)与模M(x) = x4+1互素 b(x)=c(x)a(x) |b0| |02 03 01 01| |a0| |b1| |01 02 03 01| |a1| |b2| = |01 01 02 03| |a2| |b3| |03 01 01 02| |a3| c(x)的逆: 0Bx3+ 0Dx2+ 09x+ 0E,41,Rijndael: AddRoundKey,按字节在GF(28)上相加,=,42,Rijndael: Key schedule(1),主密钥生成子密钥数组, (Nr+1)*Nb个字 Nk=6 KeyExpansion(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; Wi=Wi-Nktemp; ; ; Rconi=(xi-1, 00, 00, 00); xi-1为GF(28)上的数.,43,Rijndael: Key schedule(2),Nk6 KeyExpansion(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; ; ; Rconi=(xi, 00 , 00 , 00); xi为GF(28)上的数.,44,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); ,45,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(),46,Rijndael安全性,没有发现弱密钥或补密钥 能抵抗已知的密码分析手段 ,47,DES示意图,48,DES: single round,Li = Ri-1 Ri = Li-1F(Ri-1,Ki),49,DES: Function F,Expansion: 32 48 S-box: 6 4 Permutation: ,50,DES: Subkey generation,51,DES安全性分析,差分密码分析 线性密码分析 密钥短穷举破译 字典攻击 F函数(S-Box)设计原理未知 轮数问题 弱密钥与半弱密钥 小结 ,52,多重DES,DES是否构成一个闭合群? 任给K1,K2,是否存在K3,使得: EK1EK2 = EK3 Double DES Triple DES ,53,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,54,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,55,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,56,DES: 差分密码分析,破解DES: 247个选择明文(255个已知明文) 破解Lucifer(18轮128位): 24个选择明文221次计算 DES对差分密码分析的抵抗力很强 ,57,DES: 线性密码分析,破解DES: 243个已知明文 DES对线性密码分析的抵抗力稍弱 ,58,DES: 穷举破译,DES密钥长度: 56位, 2561017 计算机能力为100MIPS次(108)/秒,1万台计算机协同工作一天，计算能力为: 108*10000*24*36001017 1017/1017 = 1天 ,59,DES: 字典攻击,考虑选择明文攻击 DES块大小: 64位, 2641020 计算机能力为100MIPS(108)/秒,1万台计算机协同工作一天，计算能力为: 108*10000*24*36001017 1020/1017 = 1000天 适用于任意64位块的加密 ,60,DES: S-box设计准则,S-box是DES的核心(全部非线性所在) S-box每行是015的一个置换 S-box输出不是输入的线性或者放射变换 S-box输入一位改变, 输出至少二位改变 S(x)与S(x001100)至少二位不同 S(x) != S(x00ef00), 对任意e,f0,1 固定一位,其它五位变化,输出数字中的0和1的总数接近相等 ,61,DES: 弱密钥与半弱密钥,弱密钥: EKEK = I 半弱密钥: EK1 = EK2 不影响安全性 互补性: 若y=DESk(x),则把x,y,k都取补,等式仍然成立. ,62,Double DES,C = EK2(EK1(P) P = DK1(DK2(C),63,Double DES安全性,中间相会(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-16 ,64,Triple DES,C=EK3(DK2(EK1(P) P=DK1(EK2( DK3(C),65,Triple DES分析,With two keys: C=EK1(DK2(EK1(P) 256可选择明文256次计算 With three keys: C=EK3(DK2(EK1(P) 比two-key更安全 Tripe DES速度慢 ,66,Electronic Codebook Mode,ECB: Ci = EK(Pi) Pi = DK(Ci) 相同明文相同密文 同样信息多次出现造成泄漏 信息块可被替换 信息块可被重排 密文块损