信息安全信息安全.pdf

信息安全信息安全信息安全信息安全 第二讲第二讲第二讲第二讲 密码学基础密码学基础密码学基础密码学基础( 一一一一) 王昭 北京大学信息科学技术学院 软件研究所-信息安全研究室 王昭 北京大学信息科学技术学院 软件研究所-信息安全研究室 2003年春季北京大学工程硕士研究生课程2003年春季北京大学工程硕士研究生课程 安全服务安全服务 安全服务（安全服务（Security Services）： 计算机通信网络中，主要的安全保护措 施被称作安全服务。 根据 ）： 计算机通信网络中，主要的安全保护措 施被称作安全服务。 根据ISO7498-2, 安全服务包括：安全服务包括： 1. 数据机密性（数据机密性（Data Confidentiality） 2. 数据完整性（数据完整性（Data Integrity） 3. 鉴别（鉴别（ Authentication） 4. 访问控制（访问控制（Access Control） 5. 抗抵赖（抗抵赖（Non-repudiation） 安全威胁安全威胁 安全服务安全服务 假冒攻击假冒攻击 认证服务认证服务 授权侵犯授权侵犯 访问控制服务访问控制服务 窃听攻击窃听攻击 机密性服务机密性服务 完整性破坏完整性破坏 完整性服务完整性服务 服务的否认服务的否认 非否认服务非否认服务 拒绝服务拒绝服务 认证服务， 访问控制服务， 完整性服务 认证服务， 访问控制服务， 完整性服务 用于对付典型安全威胁的安全服务用于对付典型安全威胁的安全服务 信息安全核心技术信息安全核心技术密码技术密码技术 密码技术，是实现所有安全服务的重要基础。密码技术，是实现所有安全服务的重要基础。 对称密码算法对称密码算法 公钥密码算法公钥密码算法 完整性算法:散列算法(消息摘要算法)完整性算法:散列算法(消息摘要算法) 抗否认:数字签名抗否认:数字签名 密钥管理。密钥管理。 信息安全核心技术信息安全核心技术密码技术密码技术 密码技术，是实现所有安全服务的重要基础。密码技术，是实现所有安全服务的重要基础。 应用领域应用领域:保密、鉴别、数字签名保密、鉴别、数字签名 对称密码算法对称密码算法 公钥密码算法公钥密码算法 完整性算法:散列算法(消息摘要算法)完整性算法:散列算法(消息摘要算法) 抗否认:数字签名抗否认:数字签名 密钥管理。密钥管理。 密码从军事走向生活密码从军事走向生活 电子邮件电子邮件263.net 自动提款机自动提款机 电话卡电话卡: IP卡、卡、201电话卡电话卡 银行取钱银行取钱 信用卡购物信用卡购物 基本概念基本概念 密码学密码学(Cryptology): 是研究信息系统安全保密 的科学 是研究信息系统安全保密 的科学. ?密码编码学密码编码学(Cryptography): 主要研究对信息 进行编码 主要研究对信息 进行编码,实现对信息的隐蔽实现对信息的隐蔽. ?密码分析学密码分析学(Cryptanalytics):主要研究加密消 息的破译或消息的伪造 主要研究加密消 息的破译或消息的伪造. 基本术语基本术语 消息被称为消息被称为明文(Plaintext)明文(Plaintext)。用某种方法伪装消息以 隐藏它的内容的过程称为 。用某种方法伪装消息以 隐藏它的内容的过程称为加密(Encrtption)加密(Encrtption)，被加密 的消息称为 ，被加密 的消息称为密文(Ciphertext)密文(Ciphertext)，而把密文转变为明文 的过程称为 ，而把密文转变为明文 的过程称为解密(Decryption)解密(Decryption)。 对明文进行加密操作的人员称作对明文进行加密操作的人员称作加密员加密员或或密码员 (Cryptographer). 密码员 (Cryptographer). 密码算法(Cryptography Algorithm):密码算法(Cryptography Algorithm):是用于加密和解 密的数学函数。 是用于加密和解 密的数学函数。 密码员对明文进行加密操作时所采用的一组规则称作密码员对明文进行加密操作时所采用的一组规则称作 加密算法(Encryption Algorithm).加密算法(Encryption Algorithm). 所传送消息的预定对象称为所传送消息的预定对象称为接收者(Receiver).接收者(Receiver). 接收者对密文解密所采用的一组规则称为接收者对密文解密所采用的一组规则称为解密算法 (Decryption Algorithm). 解密算法 (Decryption Algorithm). 加解密过程示意图加解密过程示意图 加密和解密算法的操作通常都是在一组密钥的 控制下进行的 加密和解密算法的操作通常都是在一组密钥的 控制下进行的,分别称为分别称为加密密钥加密密钥(Encryption Key) 和和解密密钥解密密钥(Decryption Key). 明文 明文 密文 加密算法 解密算法 密钥 密钥 密码学的目的密码学的目的：Alice和和Bob两个人在不安全的信道上进 行通信，而破译者 两个人在不安全的信道上进 行通信，而破译者Oscar不能理解他们通信的内容。 加密通信的模型 不能理解他们通信的内容。 加密通信的模型 Alice加密机 解密机 Bob 安全信道 密钥源 Oscar xyx k 密码体制密码体制 密码体制：密码体制：它是一个五元组（它是一个五元组（P,C,K,E,D)满足条件： （ 满足条件： （1）P是可能明文的有限集；（明文空间） （ 是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间） （ 是可能密文的有限集；（密文空间） （3）K是一切可能密钥构成的有限集；（密钥空间）是一切可能密钥构成的有限集；（密钥空间） *（4）任意）任意k K,有一个加密算法和相应的解密算 法，使得和分别为加密解密 函数，满足 有一个加密算法和相应的解密算 法，使得和分别为加密解密 函数，满足dk(ek(x)=x, 这里这里 x P。 Ee k Ddk CPek: PCdk: 密码算法分类密码算法分类-i 按照保密的内容分按照保密的内容分: ?受限制的（受限制的（restricted)算法算法:算法的保密性基于 保持算法的秘密。 算法的保密性基于 保持算法的秘密。 ?基于密钥（基于密钥（key-based)的算法的算法:算法的保密性基 于对密钥的保密。 算法的保密性基 于对密钥的保密。 密码算法分类密码算法分类-ii 基于密钥的算法，按照密钥的特点分类：基于密钥的算法，按照密钥的特点分类： ? 对称密码算法（对称密码算法（symmetric cipher)：又称：又称传统密码算 法（ 传统密码算 法（conventional cipher)，就是加密密钥和解密密钥 相同，或实质上等同，即从一个易于推出另一个。又 称 ，就是加密密钥和解密密钥 相同，或实质上等同，即从一个易于推出另一个。又 称秘密密钥算法秘密密钥算法或或单密钥算法单密钥算法。 ? 非对称密钥算法（非对称密钥算法（asymmetric cipher):加密密钥和解密 密钥不相同，从一个很难推出另一个。又称 加密密钥和解密 密钥不相同，从一个很难推出另一个。又称公开密钥 算法（ 公开密钥 算法（public-key cipher) 。 公开密钥算法用一个密钥进行加密公开密钥算法用一个密钥进行加密, 而用另一个进行解 密 而用另一个进行解 密.其中的加密密钥可以公开其中的加密密钥可以公开,又称公开密钥（又称公开密钥（public key)，简称公钥，简称公钥.解密密钥必须保密解密密钥必须保密,又称私人密钥 （ 又称私人密钥 （private key)私钥私钥.简称简称私钥私钥。 密码算法分类密码算法分类-iii 按照明文的处理方法：按照明文的处理方法： ?分组密码（分组密码（block cipher):将明文分成固定长度 的组，用同一密钥和算法对每一块加密，输出 也是固定长度的密文。 将明文分成固定长度 的组，用同一密钥和算法对每一块加密，输出 也是固定长度的密文。 ?流密码（流密码（stream cipher):又称又称序列密码序列密码.序列密 码每次加密一位或一字节的明文，也可以称为 流密码。 序列密码是手工和机械密码时代的主流 序列密 码每次加密一位或一字节的明文，也可以称为 流密码。 序列密码是手工和机械密码时代的主流 密码算法分类密码算法分类-iv 对称密钥密码又可分为：对称密钥密码又可分为： ?分组密码 每次对一块数据加密 多数网络加密应用 DES,IDEA,RC6,Rijndael 分组密码 每次对一块数据加密 多数网络加密应用 DES,IDEA,RC6,Rijndael ?流密码 每次对一位或一字节加密 手机 One-time padding,Vigen 流密码 每次对一位或一字节加密 手机 One-time padding,Vigenre,Vernamre,Vernam 密码算法分类密码算法分类-v 公开密钥密码:公开密钥密码: ?大部分是分组密码，只有概率密码体制属于 流密码 每次对一块数据加密 数字签名,身份认证 RSA,ECC,ElGamal 大部分是分组密码，只有概率密码体制属于 流密码 每次对一块数据加密 数字签名,身份认证 RSA,ECC,ElGamal 加密解密速度慢加密解密速度慢 密码学的起源和发展密码学的起源和发展-i 三个阶段：三个阶段： 1949年之前 密码学是一门艺术 1949年之前 密码学是一门艺术 19491975年 密码学成为科学 19491975年 密码学成为科学 1976年以后 密码学的新方向 1976年以后 密码学的新方向公钥密码学公钥密码学 密码学的起源和发展密码学的起源和发展-ii 1949年之前:1949年之前: 古典密码（classical cryptography)古典密码（classical cryptography) ?密码学还不是科学,而是艺术密码学还不是科学,而是艺术 ?出现一些密码算法和加密设备出现一些密码算法和加密设备 ?密码算法的基本手段(substitution 26(mod 6 23 0 3 3 3 19 14 7 7 = = + G X A = 19 14 7 19 19 19 6 23 0 15 任意的单表代替密码算法任意的单表代替密码算法 设设P=C=Z/(26)，K是由是由26个符号个符号0，1,25的所有可能 置换组成。任意 的所有可能 置换组成。任意K，定义，定义e (x)= (x)=y 且且 d (y)= -1(y)=x, -1是的逆置换。是的逆置换。 注：注： 1*. 置换的表示： 置换的表示： 2*密钥空间密钥空间K很大，很大，|k|=26! 41026，破译者穷举搜索 是不行的，然而，可由统计的方式破译它。 ，破译者穷举搜索 是不行的，然而，可由统计的方式破译它。 3*移位密码、乘数密码、仿射密码算法都是替换密码的 特例 移位密码、乘数密码、仿射密码算法都是替换密码的 特例 0 1 2 3 23 24 25 0 1 2 3 23 24 25 )( 单表替换密码的破译单表替换密码的破译 通过字母的使用频率破译通过字母的使用频率破译 对抗频率分析的办法对抗频率分析的办法 多名或同音代替密码多名或同音代替密码 多表代替密码多表代替密码 多字母代替密码多字母代替密码 多名代替密码多名代替密码 与简单代替密码类似，只是映射是一对多的， 每个明文字母可以加密成多个密文字母。 例如， 与简单代替密码类似，只是映射是一对多的， 每个明文字母可以加密成多个密文字母。 例如， A可能对应于可能对应于5、13、25 B可能对应于可能对应于7、9、31、42 当对字母的赋值个数与字母出现频率成比例时。 这是因为密文符号的相关分布会近似于平的， 可以挫败频率分析。 当对字母的赋值个数与字母出现频率成比例时。 这是因为密文符号的相关分布会近似于平的， 可以挫败频率分析。 然而，若明文字母的其它统计信息在密文中仍 很明显时，那么同音代替密码仍然是可破译的。 然而，若明文字母的其它统计信息在密文中仍 很明显时，那么同音代替密码仍然是可破译的。 多表代替密码多表代替密码 多表代替密码： 是以一系列（两个以上）代换 表依此对明文消息的字母进行代换的方法。 多表代替密码： 是以一系列（两个以上）代换 表依此对明文消息的字母进行代换的方法。 ?非周期多标代替密码： 代换表是非周期的无限序列 一次一密密码（ 非周期多标代替密码： 代换表是非周期的无限序列 一次一密密码（one time padding):对每个明文 每次采用不同的代换表。 对每个明文 每次采用不同的代换表。 ?周期多表代替密码：代换表个数有限，重复使 用。 周期多表代替密码：代换表个数有限，重复使 用。 Vigenre cipher (1858) 是一种多表移位代替密码是一种多表移位代替密码 设设d为一固定的正整数，为一固定的正整数，d个移位代换表个移位代换表=（ （ 1， ，2, d) 由密钥序列由密钥序列K（ k1,k2,kd)给定 ，第给定 ，第i+td个明文 字母由表 个明文 字母由表i决定，即密钥决定，即密钥ki决定决定 ek(xi+td)=(xi+td+ki,) mod q =y dk(yi+td)= (xi+td-ki) mod q =x 例子：例子：q=26, x=polyalphabetic cipher, K=RADIO 明文明文 x=p o l y a l p ha b e t i c c i p h e r 密钥密钥 k=RAD I ORADI ORADI ORADIO 密文密文 y=GOOGOCPKTP NTLKQZPKMF 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 密钥密钥: cryptographycryptographycr 明文明文: yourpackagereadyroomathree 密文密文: AFSGIOI PG PG 滚动密钥密码滚动密钥密码 对于周期代换密码，当密钥的长度对于周期代换密码，当密钥的长度d和明文一 样长时，就成为滚动密钥密码。 和明文一 样长时，就成为滚动密钥密码。 VigenVigenre本人建议密钥与明文一样长re本人建议密钥与明文一样长 Vernam密码密码 1918年，Gillbert Vernam建议密钥与明文一 样长并且没有统计关系的密钥内容，他采用的 是二进制数据: 加密：Ci= Pi Ki 解密Pi= Ci Ki 核心：构造和消息一样长的随机密钥 1918年，Gillbert Vernam建议密钥与明文一 样长并且没有统计关系的密钥内容，他采用的 是二进制数据: 加密：Ci= Pi Ki 解密Pi= Ci Ki 核心：构造和消息一样长的随机密钥 多字母代替密码多字母代替密码-Playfair Playfair:将明文中的双字母组合作为一个单元 对待，并将这些单元转换为密文的双字母组合。 将明文中的双字母组合作为一个单元 对待，并将这些单元转换为密文的双字母组合。 55变换矩阵: I与J视为同一字符 C I P H E R A B D F G K L M N(cipher) O Q S T U V W X Y Z 55变换矩阵: I与J视为同一字符 C I P H E R A B D F G K L M N(cipher) O Q S T U V W X Y Z 加密规则:按成对字母加密 1)相同对中的字母加分隔符(如x) 2)balloon ? ba lx lo on 3)同行取右边: he ? EC 4)同列取下边: dm ? MT 5)其他取交叉: kt ? MQ OD ? TR 加密规则:按成对字母加密 1)相同对中的字母加分隔符(如x) 2)balloon ? ba lx lo on 3)同行取右边: he ? EC 4)同列取下边: dm ? MT 5)其他取交叉: kt ? MQ OD ? TR Playfair举例举例 以前面的55变换矩阵(cipher)为例以前面的55变换矩阵(cipher)为例 C I P H E R A B D F G K L M N(cipher) O Q S T U V W X Y Z (1)balloon ba lx lo on db sp gs ug (2)book bo ok sr qg (3)fill fi lx lx ae sp sp C I P H E R A B D F G K L M N(cipher) O Q S T U V W X Y Z (1)balloon ba lx lo on db sp gs ug (2)book bo ok sr qg (3)fill fi lx lx ae sp sp Playfair密码分析密码分析 Playfair有26X26=676种字母对组合Playfair有26X26=676种字母对组合 字符出现几率一定程度上被均匀化字符出现几率一定程度上被均匀化 基于字母频率的攻击比较困难基于字母频率的攻击比较困难 依然保留了相当的结构信息依然保留了相当的结构信息 Hill密码（密码（1929） 基于矩阵的线性变换: 基于矩阵的线性变换: K是一个m*m矩阵,在K是一个m*m矩阵,在Z/(26)上可逆,即存在K上可逆,即存在K-1 -1使得: KK 使得: KK-1 -1 = I (在= I (在Z/(26) ) 对每一个对每一个k K,定义定义ek(x)=xK (mod 26) 和和 dk(y)=yK-1(mod 26) 注：明文与密文都是注：明文与密文都是 m元的向量（元的向量（x1, x2 , xm);(y1, y2,ym)，Z/(26)为同余类环。在这个环上的可逆矩阵为同余类环。在这个环上的可逆矩阵 Amxm,是指行列式是指行列式detAmxm的值的值 Z*/(26),它为它为Z/(26)中全 体可逆元的集合。 中全 体可逆元的集合。Z*/(26)= a Z/(26)|(a,26)=1， Z*/(26)=1,3,5,7,9,11,15,17,19,21,23,25 Hill密码的例子密码的例子-i 例子：当例子：当 m=2时，明文元素时，明文元素x=(x1,x2),密文元素密文元素y=(y1,y2) (y1,y2)=(x1,x2)K 若若K= ,可得可得K-1= 若对明文若对明文july加密，它分成加密，它分成2个元素（个元素（j,u),(l,y),分别对应 于（ 分别对应 于（9,20）,（11,24）,有 （ 有 （9,20）（）（9960,72140）（）（3,4） 且 （ ） 且 （11,24 ）(12172,88168) （11,22） 于是对 ） 于是对 july加密的结果为加密的结果为DELW。 73 811 73 811 1123 187 73 811 73 811 Hill密码的例子密码的例子-ii 为了解密，为了解密，Bob计算 且 因此，得到了正确的明文 计算 且 因此，得到了正确的明文“july” )20, 9( 1123 187 )4, 3(= )24,11( 1123 187 )22,11(= Hill密码分析密码分析 完全隐藏了字符(对)的频率信息完全隐藏了字符(对)的频率信息 线性变换的安全性很脆弱，易被已知明文攻击击破。线性变换的安全性很脆弱，易被已知明文攻击击破。 对于一个mxm的hill密码，假定有m个明文-密文对，明 文和密文的长度都是m.可以把明文和密文对记为： P 对于一个mxm的hill密码，假定有m个明文-密文对，明 文和密文的长度都是m.可以把明文和密文对记为： Pj j=(p=(p1j 1j,p ,p2j 2j,p ,pmj mj)和C )和Cj j=(C=(C1j 1j,C ,C2j 2j, ,C ,Cmj mj), C ), Cj j=KP=KPj j,1j m 定义mxm的方阵X=（P ,1j m 定义mxm的方阵X=（Pij ij) Y=(C ) Y=(Cij ij),得到Y=KX，K=YX ),得到Y=KX，K=YX-1 -1 例子：friday PQCFKU K(5 17)=(15 16) K(8 3)=(2 5) K(0 24)=(10 20) 例子：friday PQCFKU K(5 17)=(15 16) K(8 3)=(2 5) K(0 24)=(10 20) 因此，因此， K = 38 175 52 1615 = = 152 19 38 175 1 1 X = = 38 197 52 1615 152 19 K 置换密码置换密码 换位密码把明文按列写入,按行读出换位密码把明文按列写入,按行读出 密钥包含3方面信息: 行宽,列高,读出顺序密钥包含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 完全保留字符的统计信息完全保留字符的统计信息 使用多轮加密可提高安全性使用多轮加密可提高安全性 古典密码小结古典密码小结 Substitution Ri= Li-1 F(Ri-1,Ki) 解密:解密: Ri-1 = Li Li-1 = Ri F(Ri-1,Ki) = Ri F(Li,Ki) 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 DES示意图示意图 DES的描述的描述 DES利用利用56比特串长度的密钥比特串长度的密钥K来加密长度为来加密长度为64位的 明文，得到长度为 位的 明文，得到长度为64位的密文位的密文 输入输入64比特明文数据比特明文数据 初始置换初始置换IP 在密钥控制下在密钥控制下 16轮迭代轮迭代 初始逆置换初始逆置换IP-1 输出输出64比特密文数据比特密文数据 DES算法框图算法框图 交换左右交换左右32比特比特 DES加解密过程 令 加解密过程 令i表示迭代次数，表示逐位模表示迭代次数，表示逐位模2求和，求和，f为加密 函数。 为加密 函数。DES的加密和解密过程表示如下。 加密过程： 解密过程： 的加密和解密过程表示如下。 加密过程： 解密过程： )(64 16, 2 , 1),( 16, 2 , 1 )64( 1616 1 11 1 00 LRIPbit ikRFLR iRL bitIPRL iiii ii 明文 密文 L L 初始置换初始置换IP和初始逆置换和初始逆置换IP1 Li-1（32比特）比特）Ri-1（32比特）比特） Li（32比特）比特） 48比特寄存器比特寄存器 选择扩展运算选择扩展运算E 48比特寄存器比特寄存器 子密钥子密钥Ki （48比特）比特） 32比特寄存器比特寄存器 选择压缩运算选择压缩运算S 置换运算置换运算P Ri（32比特）比特） Li=Ri-1 DES的一轮迭代的一轮迭代 DES: Function F Expansion: 32 ? 48 S-box: 6 ? 4 Permutation: 选择扩展运算选择扩展运算 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 选择压缩运算选择压缩运算 S-Box-i S-Box-ii S-Box 对每个盒，对每个盒，6比特输入中的第比特输入中的第1和第和第6比特组成 的二进制数确定的行，中间 比特组成 的二进制数确定的行，中间4位二进制数用来 确定的列中相应行、列位置的十进制数的 位二进制数用来 确定的列中相应行、列位置的十进制数的4位 二进制数表示作为输出。例如S2的输入为 位 二进制数表示作为输出。例如S2的输入为 101001，则行数和列数的二进制表示分别是，则行数和列数的二进制表示分别是11 和和0100，即第，即第3行和第行和第4列，的第列，的第3行和第行和第4列的 十进制数为 列的 十进制数为3，用，用4位二进制数表示为位二进制数表示为0011，所 以S2的输出为 ，所 以S2的输出为0011。 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 子密钥的产生子密钥的产生 k1 （ 56 位 ） (48 位 ) ki （ 56 位 ） （ 48 位 ） 64 位 密 钥 置 换 选 择 1 C 0（ 28 位 ） D 0（ 28 位 ） 循 环 左 移循 环 左 移 C 1（ 28 位 ） D 1（ 28 位 ） 循 环 左 移循 环 左 移 C i（ 28 位 ） D i（ 28 位 ） 置 换 选 择 2 置 换 选 择 2 密 钥 表 的 计 算 逻 辑 循 环 左 移 ： 1 1 9 1 2 1 10 2 3 2 11 2 4 2 12 2 5 2 13 2 6 2 14 2 7 2 15 2 8 2 16 1 置换选择置换选择1（PC-1） 和置换选择 ） 和置换选择2（PC-2） 对对DES的讨论的讨论 F函数(S-Box)设计原理未知F函数(S-Box)设计原理未知 密钥长度的争论密钥长度的争论 DES的破译DES的破译 弱密钥与半弱密钥弱密钥与半弱密钥 互补密钥互补密钥 S-Box问题问题 1976年美国年美国NSA提出了下列几条提出了下列几条S盒的设计准则：盒的设计准则： 1. S盒的每一行是整数盒的每一行是整数0，15的一个置换的一个置换 2. 没有一个没有一个S盒是它输入变量的线性函数盒是它输入变量的线性函数 3.改变改变S盒的一个输入位至少要引起两位的输出改变盒的一个输入位至少要引起两位的输出改变 4.对任何一个对任何一个S盒和任何一个输入盒和任何一个输入X，S（X）和）和 S(X 001100）至少有两个比特不同（这里）至少有两个比特不同（这里X是长度为是长度为6 的比特串）的比特串） 5.对任何一个对任何一个S盒，对任何一个输入对盒，对任何一个输入对e,f属于属于0,1, S(X) S(X 11ef00) 6. 对任何一个对任何一个S盒，如果固定一个输入比特，来看一个 固定输出比特的值，这个输出比特为 盒，如果固定一个输入比特，来看一个 固定输出比特的值，这个输出比特为0的输入数目将接 近于这个输出比特为 的输入数目将接 近于这个输出比特为1的输入数目的输入数目。 密钥长度密钥长度 关于关于DES算法的另一个最有争议的问题就是担 心实际 算法的另一个最有争议的问题就是担 心实际56比特的密钥长度不足以抵御穷举式攻 击，因为密钥量只有个 比特的密钥长度不足以抵御穷举式攻 击，因为密钥量只有个 早在早在1977年，年，Diffie和和Hellman已建议制造一个 每秒能测试100万个密钥的 已建议制造一个 每秒能测试100万个密钥的VLSI芯片。每秒测 试100万个密钥的机器大约需要一天就可以搜 索整个密钥空间。他们估计制造这样的机器大 约需要 芯片。每秒测 试100万个密钥的机器大约需要一天就可以搜 索整个密钥空间。他们估计制造这样的机器大 约需要2000万美元。万美元。 1756 102 在在CRYPTO93上，上，Session和和Wiener给出了一个非常 详细的密钥搜索机器的设计方案，这个机器基于并行 运算的密钥搜索芯片，所以 给出了一个非常 详细的密钥搜索机器的设计方案，这个机器基于并行 运算的密钥搜索芯片，所以16次加密能同时完成。此 芯片每秒能测试5000万个密钥，用 次加密能同时完成。此 芯片每秒能测试5000万个密钥，用5760个芯片组成的 系统需要花费 个芯片组成的 系统需要花费10万美元，它平均用万美元，它平均用1.5天左右就可找到天左右就可找到 DES密钥。密钥。 1997年年1月月28日，美国的日，美国的RSA数据安全公司在数据安全公司在RSA安全 年会上公布了一项 安全 年会上公布了一项“秘密密钥挑战秘密密钥挑战”竞赛，其中包括悬 赏 竞赛，其中包括悬 赏1万美元破译密钥长度为万美元破译密钥长度为56比特的比特的DES。美国克罗拉 多洲的程序员 。美国克罗拉 多洲的程序员Verser从从1997年2月年2月18日起，用了日起，用了96天时 间，在 天时 间，在Internet上数万名志愿者的协同工作下，成功地 找到了 上数万名志愿者的协同工作下，成功地 找到了DES的密钥，赢得了悬赏的的密钥，赢得了悬赏的1万美元。万美元。 1998年年7月电子前沿基金会（月电子前沿基金会（EFF）使用一台）使用一台 25万美圆的电脑在万美圆的电脑在56小时内破译了小时内破译了56比特密钥 的 比特密钥 的DES。 1999年年1月月RSA数据安全会议期间，电子前沿 基金会用 数据安全会议期间，电子前沿 基金会用22小时小时15分钟就宣告破解了一个分钟就宣告破解了一个DES 的密钥。的密钥。 DES的破译的破译 1990年，以色列密码学家年，以色列密码学家Eli Biham和和Adi Shamir提出了差分密码分析法，可对提出了差分密码分析法，可对DES进行 选择明文攻击。 进行 选择明文攻击。 线性密码分析比差分密码分析更有效线性密码分析比差分密码分析更有效 弱密钥与半弱密钥弱密钥与半弱密钥 弱密钥: EK弱密钥: EK EK= I，DES存在4个弱密钥EK= I，DES存在4个弱密钥 半弱密钥: EK1= EK2，至少有12个半弱密钥半弱密钥: EK1= EK2，至少有12个半弱密钥 互补密钥互补密钥 将密钥的将密钥的0换成换成1，1换成换成0，就得到该密钥的补 密钥。如果用原密钥加密一组明文，则用补密 钥可以将明文的补码加密成密文的补码。 ，就得到该密钥的补 密钥。如果用原密钥加密一组明文，则用补密 钥可以将明文的补码加密成密文的补码。 设设X表示表示X的补码，则的补码，则 Ek(M)=C Ek (M )=C 这表明对这表明对DES的选择明文攻击只需测试一半的 可能密钥 的选择明文攻击只需测试一半的 可能密钥:255个密钥。个密钥。 分组密码的操作模式分组密码的操作模式 实用中数据格式的多样性实用中数据格式的多样性 安全的工作模式安全的工作模式 分组密码的操作模式分组密码的操作模式 电子密码本电子密码本ECB (electronic codebook mode) 密码分组链接密码分组链接CBC (cipher block chaining) 密码反馈密码反馈CFB (cipher feedback) 输出反馈输出反馈OFB (output feedback) ?美国美国NSB在在FIPS PUB 74和和81中规定中规定 ?ANSI 在在ANSI X3.106中规定中规定 ? ISO和和ISO/IEC在在ISO 9732 ISO/IEC 10116中 规定 中 规定 电子密码本（电子密码本（ECB） ?Ci= EK(Pi) Pi= DK(Ci) Ci= EK(Pi) Pi= DK(Ci) ECB特点特点 简单和有效简单和有效 可以并行实现可以并行实现 不能隐藏明文的模式信息不能隐藏明文的模式信息 相同明文?相同密文相同明文?相同密文 同样信息多次出现造成泄漏同样信息多次出现造成泄漏 对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放 误差传递：密文块损坏?仅对应明文块损坏误差传递：密文块损坏?仅对应明文块损坏 ?适合于传输短信息适合于传输短信息 密码分组链接密码分组链接CBC Ci=EK(Ci-1Pi) Pi=EK(Ci) Ci-1Ci=EK(Ci-1Pi) Pi=EK(Ci) Ci-1 CBC特点特点 没有已知的并行实现算法没有已知的并行实现算法 能隐藏明文的模式信息能隐藏明文的模式信息 需要共同的初始化向量需要共同的初始化向量IV 相同明文?不同密文相同明文?不同密文 初始化向量初始化向量IV可以用来改变第一块可以用来改变第一块 对明文的主动攻击是不容易的对明文的主动攻击是不容易的 信息块不容易被替换、重排、删除、重放信息块不容易被替换、重排、删除、重放 误差传递：密文块损坏?两明文块损坏误差传递：密文块损坏?两明文块损坏 安全性好于安全性好于ECB 适合于传输长度大于适合于传输长度大于64位的报文，还可以进行用户鉴 别 位的报文，还可以进行用户鉴 别,是大多系统的标准如是大多系统的标准如 SSL、IPSec 密码反馈密码反馈CFB CFB:分组密码?流密码 Si为移位寄存器,j为流单元宽度 加密: Ci=Pi(EK(Si)的高j位) Si+1=(Sij)|Ci 解密: Pi=Ci(EK(Si)的高j位) Si+1=(Sij)|Ci CFB:分组密码?流密码 Si为移位寄存器,j为流单元宽度 加密: Ci=Pi(EK(Si)的高j位) Si+1=(Sij)|Ci 解密: Pi=Ci(EK(Si)的高j位) Si+1=(Sij)|Ci CFB加密示意图加密示意图 Ci=Pi (EK(Si)的高的高j位位) ; Si+1=(Sij)|Ci CFB解密示意图解密示意图 Pi=Ci (EK(Si)的高的高j位位); Si+1=(Sij)|Ci CFB特点特点 分组密码?流密码分组密码?流密码 没有已知的并行实现算法没有已知的并行实现算法 隐藏了明文模式隐藏了明文模式 需要共同的移位寄存器初始值需要共同的移位寄存器初始值IV 对于不同的消息，对于不同的消息，IV必须唯一必须唯一 误差传递：一个单元损坏影响多个单元误差传递：一个单元损坏影响多个单元 输出反馈输出反馈OFB OFB:分组密码?流密码 Si为移位寄存器,j为流单元宽度 加密: Ci=Pi(EK(Si)的高j位) Si+1=(Sij)|(EK(Si)的高j位) 解密: Pi=Ci(EK(Si)的高j位) Si+1=(Sij)|(EK(Si)的高j位) OFB:分组密码?流密码 Si为移位寄存器,j为流单元宽度 加密: Ci=Pi(EK(Si)的高j位) Si+1=(Sij)|(EK(Si)的高j位) 解密: Pi=Ci(EK(Si)的高j位) Si+1=(Sij)|(EK(Si)的高j位) OFB加密示意图加密示意图 Ci=Pi (EK(Si)的高的高j位位);Si+1=(Sij)|(EK(Si)的高的高j位位) OFB解密示意图解密示意图 Pi=Ci (EK(Si)的高的高j位位); Si+1=(Sij)|(EK(Si)的高的高j位位) OFB特点特点 OFB:分组密码?流密码分组密码?流密码 没有已知的并行实现算法没有已知的