北京大学网络信息安全课件-数据加密算法.ppt

网络与信息安全网络与信息安全 第二讲第二讲 密码学基础密码学基础( (一一) ) 王 昭 北京大学信息科学技术学院 软件研究所-信息安全研究室 2002-2003年度北京大学硕士研究生课程 本课程的助教 高睿：g_ 张锦懋： 刘鹏： 请大家把自己的姓名、Email地址及简单情况 发给高睿 密码学部分的安排 密码学基础（一） 密码学基础（二） 密码学基础（三） 密码学基础（四） 密码实际应用中的一些问题 信息安全的含义 通信保密通信保密（COMSEC）：60-70年代 信息保密 信息安全信息安全（INFOSEC）：80-90年代 机密性、完整性、可用性、不可否认性 等 信息保障信息保障（IA）：90年代- 基本的通讯模型 通信的保密模型 通信安全-60年代（COMSEC） 发方收方 信源编码 信道编码 信道传输 通信协议 发方 收方 敌人 信源编码 信道编码 信道传输 通信协议 密码 信息安全的含义 (80-90年代) 信息安全的三个基本方面 保密性 Confidentiality 即保证信息为授权者享用而不泄漏给未经授权者。 完整性 Integrity 数据完整性，未被未授权篡改或者损坏 系统完整性，系统未被非授权操纵，按既定的 功能运行 可用性 Availability 即保证信息和信息系统随时为授权者提供服务，而 不要出现非授权者滥用却对授权者拒绝服务的情况。 信息安全的其他方面 信息的不可否认性Non-repudiation ： 要求无论发送方还是接收方都不能抵赖所 进行的传输 鉴别Authentication 鉴别就是确认实体是它所声明的。适用于用 户、进程、系统、信息等 审计Accountability 确保实体的活动可被跟踪 可靠性Reliability 特定行为和结果的一致性 安全需求的多样性 保密性 一致性 可用性 可靠性 可认证，真实性 责任定位，审计性 高性能 实用性 占有权 信息保障 美国人提出的概念美国人提出的概念: : Information Assurance 保护保护（P Protect） 检测检测（D Detect） 反应反应（R React） 恢复恢复（R Restore） 保护 Protect 检测 Detect 反应 React 恢复 Restore 密码从军事走向生活 电子邮件 263.net 自动提款机 电话卡: IP卡、201电话卡 银行取钱 信用卡购物 基本概念 密码学(Cryptology): 是研究信息系统安全保 密的科学. 密码编码学(Cryptography): 主要研究对信息 进行编码,实现对信息的隐蔽. 密码分析学(Cryptanalytics):主要研究加密消 息的破译或消息的伪造. 基本术语 消息被称为明文(Plaintext)。用某种方法伪装消息 以隐藏它的内容的过程称为加密(Encrtption)，被加 密的消息称为密文(Ciphertext)，而把密文转变为明 文的过程称为解密(Decryption)。 对明文进行加密操作的人员称作加密员或密码员 (Cryptographer). 密码算法(Cryptography Algorithm):是用于加密和 解密的数学函数。 密码员对明文进行加密操作时所采用的一组规则称作 加密算法(Encryption Algorithm). 所传送消息的预定对象称为接收者(Receiver). 接收者对密文解密所采用的一组规则称为解密算法 (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。 密码算法分类-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 流密码 每次对一位或一字节加密 手机 One-time padding,Vigenre,Vernam 密码算法分类-v 公开密钥密码: 大部分是分组密码，只有概率密码体制属于 流密码 每次对一块数据加密 数字签名,身份认证 RSA,ECC,ElGamal 加密解密速度慢 密码学的起源和发展-i 三个阶段： 1949年之前 密码学是一门艺术 19491975年 密码学成为科学 1976年以后 密码学的新方向公钥密码学 密码学的起源 隐写术(steganography): 通过隐藏消息的存在来保护消息. 隐形墨水 字符格式的变化 图象图像 example-i (象形文字的修改)Modified Hieroglyphics, c. 1900 B.C. 密码学的第一个例子是对标准书写符号的修改 例如:古埃及法老坟墓上的文字 思想:代替(substitution) example-ii Spartan Scytale, c. 500 B.C. 斯巴达人用于加解密的一种军事设备 发送者把一条羊皮螺旋形地缠在一个圆柱形 棒上 思想：置换（permutation) example-iii Polybius Checkerboard , 205123 B.C. 明文:POLYBIUS 密文:3534315412244543 12345 1ABCDE 2FGHIJK 3LMNOP 4QRSTU 5VWXYZ Example-iv Caesar Cipher, c. 50 B.C. A B C D E F G X Y Z D E F G H I J A B C 明文:Caesar cipher is a shift substitution 密文:FDHVDU FLSKHU LV D VKLIW VXEVWLWXWLRQ Example -V Nomenclator 代码本 c.1400 字母、符号、单词、短语 代码 代码 字母、符号、单词、短语 应用：World War II 密码学的起源和发展-ii 1949年之前: 古典密码（classical cryptography) 密码学还不是科学,而是艺术 出现一些密码算法和加密设备 密码算法的基本手段(substitution (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。 Hill密码的例子-ii 为了解密，Bob计算 且 因此，得到了正确的明文“july” Hill密码分析 完全隐藏了字符(对)的频率信息 线性变换的安全性很脆弱，易被已知明文攻击击破。 对于一个mxm的hill密码，假定有m个明文-密文对， 明文和密文的长度都是m.可以把明文和密文对记为： Pj=(p1j,p2j,pmj)和Cj=(C1j,C2j,Cmj), Cj=KPj,1j m 定义mxm的方阵X=（Pij) Y=(Cij),得到Y=KX，K=YX-1 例子：friday PQCFKU K(5 17)=(15 16) K(8 3)=(2 5) K(0 24)=(10 20) 因此， 置换密码 换位密码把明文按列写入,按行读出 密钥包含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:TTNAAPTMTSUOAODWCOIXPET Z 完全保留字符的统计信息 使用多轮加密可提高安全性 古典密码小结 Substitution Ri = Li-1F(Ri-1,Ki) 解密: Ri-1 = Li Li-1 = RiF(Ri-1,Ki) = RiF(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的加密和解密过程表示如下。 加密过程： 解密过程： 初始置换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 位二进制数表示作为输出。例如的输入为 101001，则行数和列数的二进制表示分别是11 和0100，即第3行和第4列，的第3行和第4列的 十进制数为3，用4位二进制数表示为0011，所 以的输出为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 子密钥的产生 置换选择1（PC-1） 和置换选择2（PC-2） 对DES的讨论 F函数(S-Box)设计原理未知 密钥长度的争论 DES的破译 弱密钥与半弱密钥 S-Box问题 1976年美国NSA提出了下列几条S盒的设计准则： 1. S盒的每一行是整数0，15的一个置换 2. 没有一个S盒是它输入变量的线性函数 3.改变S盒的一个输入位至少要引起两位的输出改变 4.对任何一个S盒和任何一个输入X，S（X）和 S(X001100）至少有两个比特不同（这里X是长度为 6的比特串） 5.对任何一个S盒，对任何一个输入对e,f属于0,1, S(X) S(X11ef00) 6. 对任何一个S盒，如果固定一个输入比特，来看一 个固定输出比特的值，这个输出比特为0的输入数目 将接近于这个输出比特为1的输入数目。 密钥长度 关于DES算法的另一个最有争议的问题就是担 心实际56比特的密钥长度不足以抵御穷举式攻 击，因为密钥量只有 个 早在1977年，Diffie和Hellman已建议制造一个 每秒能测试100万个密钥的VLSI芯片。每秒测 试100万个密钥的机器大约需要一天就可以搜 索整个密钥空间。他们估计制造这样的机器大 约需要2000万美元。 在CRYPTO93上，Session和Wiener给出了一个非常 详细的密钥搜索机器的设计方案，这个机器基于并行 运算的密钥搜索芯片，所以16次加密能同时完成。此 芯片每秒能测试5000万个密钥，用5760个芯片组成的 系统需要花费10万美元，它平均用1.5天左右就可找到 DES密钥。 1997年1月28日，美国的RSA数据安全公司在RSA安 全年会上公布了一项“秘密密钥挑战”竞赛，其中包 括悬赏1万美元破译密钥长度为56比特的DES。美国 克罗拉多洲的程序员Verser从1997年2月18日起，用了 96天时间，在Internet上数万名志愿者的协同工作下 ，成功地找到了DES的密钥，赢得了悬赏的1万美元 。 1998年7月电电子前沿基金会（EFF）使用一台 25万美圆圆的电脑电脑 在56小时时内