《密码学基础课件北大课件》由会员分享，可在线阅读，更多相关《密码学基础课件北大课件（78页珍藏版）》请在金锄头文库上搜索。
1、网络与信息安全 密码学基础(一),潘爱民，北京大学计算机研究所 http:/ 经典密码算法 现代密码算法 AES 随机数发生器,对称加密算法的基本模型,加密: E: (X,K) Y, y = E(x,k),解密: D: (Y,K) X, x = D(y,k),对称加密算法研究,对称加密算法的特点 算法强度足够 安全性依赖于密钥，不是算法 速度快 两门学科 密码学 密码分析,用对称加密算法建立起来的安全通讯,密码学,三种考虑角度 （1）从明文到密文的变换 替换(substitution) 置换(transposition) （2）钥匙的数目 对称、单钥加密法 双钥、公钥加密 （3）明文的处理方
2、式 分组加密（块加密算法） 流方式加密,密码分析,发现X和K的过程被称为密码分析 分析的策略取决于加密的技术以及可利用的信息，在加密算法设计和攻击时都需要用到的技术 根据可利用信息的不同，可分为5类： （1）只有密文 （2）已知部分明文-密文对 （3）选择明文 （4）选择密文 * （1）（2）（3）常见、（4）不常见,加密算法的有效性,Unconditionally secure，绝对安全？ 永不可破，是理想情况，理论上不可破，密钥空间无限，在已知密文条件下，方程无解。但是我们可以考虑： 破解的代价超过了加密信息本身的价值 破解的时间超过了加密信息本身的有效期 Computationally
3、secure， 满足上述两个条件,直觉：什么是一个好的加密算法,假设密码(password)k是固定的 明文和密文是一个映射关系：单射，即 Ek(x1) != Ek(x2) if x1 != x2 通常情况是：明文非常有序 好的密码条件下，我们期望得到什么样的密文 随机性 如何理解随机性 静态：特殊的点 动态：小的扰动带来的变化不可知,考虑设计一个加密算法,打破明文本身的规律性 随机性(可望不可及) 非线性(一定要) 统计意义上的规律 多次迭代 迭代是否会增加变换的复杂性 是否存在通用的框架，用于迭代 复杂性带来密码分析的困难和不可知性 实践的检验和考验,已有密码算法的讨论,经典密码算法 替换
4、技术 置换技术 现代密码算法 DES 其他密码算法 AES密码算法 Rijndael,经典密码算法,替换技术 Caesar加密制 单表替换加密制 Playfair加密制 Hill加密制 多表加密制 置换技术 改变字母的排列顺序，比如 用对角线方式写明文，然后按行重新排序 写成一个矩阵，然后按照新的列序重新排列 转轮加密体制 多步结合,经典密码算法特点,要求的计算强度小 DES之前 以字母表为主要加密对象 替换和置换技术 数据安全基于算法的保密 密码分析方法基于明文的可读性以及字母和字母组合的频率特性,现代密码算法,DES(Data Encryption Standard) IDEA Blowf
5、ish RC5 CAST-128 ,分组密码算法设计指导原则,Diffusion(发散) 小扰动的影响波及到全局 密文没有统计特征，明文一位影响密文的多位，增加密文与明文之间关系的复杂性 Confusion(混淆) 强调密钥的作用 增加密钥与密文之间关系的复杂性 结构简单、易于分析,Feistel分组加密算法结构之动机,分组加密算法，一一映射 当n较小时，等价于替换变换 当n较大时，比如n=64，无法表达这样的任意变换。 Feistel结构很好地解决了二者之间的矛盾,Feistel分组加密算法结构之思想,基本思想：用简单算法的乘积来近似表达大尺寸的替换变换 多个简单算法的结合得到的加密算法比任
6、何一个部分算法都要强 交替使用替换变换和排列(permutation) 混淆(confusion)和发散(diffusion)概念的应用,Feistel 结构图,Feistel结构定义,加密: Li = Ri-1; Ri = Li-1F(Ri-1,Ki) 解密: Ri-1 = Li Li-1 = RiF(Ri-1,Ki) = RiF(Li,Ki),Feistel分组加密算法特点,分组大小。越大安全性越高，但速度下降，64比较合理 密钥位数。越大安全性越高，但速度下降，64广泛使用，但现在已经不够用128 步数，典型16步 子钥产生算法。算法越复杂，就增加密码分析的难度 每一步的子函数。函数越复
7、杂，就增加密码分析的难度 快速软件实现，包括加密和解密算法 易于分析。便于掌握算法的保密强度以及扩展办法。,Feistel分组加密算法 之解密算法,Feistel分组加密算法之解密算法推导,DES算法,1977年由美国的标准化局(NBS，现为NIST)采纳 64位分组、56位密钥 历史： IBM在60年代启动了LUCIFER项目，当时的算法采用128位密钥 改进算法，降低为56位密钥，IBM提交给NBS(NIST)，于是产生DES,DES算法基本结构,DES: 每一轮,Li = Ri-1 Ri = Li-1F(Ri-1,Ki),DES: Function F,Expansion: 32 48
8、S-box: 6 4 Permutation,DES: 32位到48位的扩展表,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,DES: S-box,S(1): 14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07 00 15 07 04 14 02 1
9、3 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,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,DES 之每步密钥产生过程,PC-1 在第一步之前 PC2 左移位数目表 1或者2位,DES的强度,56位密钥的使用 理论上
10、的强度，97年$100000的机器可以在6小时内用穷举法攻破DES 实际攻破的例子，97年1月提出挑战，有人利用Internet的分布式计算能力，组织志愿军连接了70000多个系统在96天后攻破 DES算法的本质 关键在于8个S-BOX 针对DES的密码分析 差分分析法 线性分析法,差分分析法,属于选择明文攻击 基本思想：通过分析特定明文差对结果密文差的影响来获得可能性最大的密钥 差分在DES的16步加密过程中的传递，每一个S-BOX对于差分传递的概率特性 子密钥不影响每一步的输入差分，但是影响输出的差分 针对每一个DES步骤，用差分法可以推导出该步的密钥,每一步的差分分析法,针对DES的密码
11、分析,差分分析法 247对选择明文，经过247量级的计算可攻破 线性分析法 思想：用线性近似描述DES变换 根据247已知明文，可以找到DES的密钥,二重DES,C = EK2(EK1(P) P = DK1(DK2(C),针对两重分组加密算法的中间相会攻击,三重DES,C=EK3(DK2(EK1(P) P=DK1(EK2( DK3(C),分组密码的用法,电子簿模式(electronic codebook mode)ECB 密码块链接(cipher block chaining)CBC 密码反馈方式(cipher feedback)CFB 输出反馈方式(output feedback)OFB,电
12、子簿模式ECB,相同明文相同密文 同样信息多次出现造成泄漏 信息块可被替换 信息块可被重排 密文块损坏仅对应明文块损坏 适合于传输短信息,密码块链接CBC,需要共同的初始化向量IV 相同明文不同密文 初始化向量IV可以用来改变第一块 密文块损坏两明文块损坏 安全性好于ECB,密码反馈方式CFB,CFB:分组密码流密码 需要共同的移位寄存器初始值IV 对于不同的消息，IV必须唯一 一个单元损坏影响多个单元: (W+j-1)/j W为分组加密块大小，j为流单元位数,输出反馈方式OFB,OFB:分组密码流密码 需要共同的移位寄存器初始值IV 一个单元损坏只影响对应单元,分组密码与序列(流)密码,定义
13、： 分组密码(block cipher)是对一个大的明文块(block)进行固定变换的操作 序列密码(stream cipher)也叫流密码，是对单个明文位(组)的随时间变换的操作 相互转换 序列密码 异或One-time pad,其他的密码算法,IDEA Blowfish RC5 CAST-128 RC2 RC4,IDEA算法,90年首次出现，91年修订，92公布细节 有望取代DES 128位密钥，64位分组 设计目标可从两个方面考虑 加密强度 易实现性,IDEA设计思想,得到confusion的途径 按位异或 以216(65536)为模的加法 以216+1 (65537)为模的乘法 互不满
14、足分配律、结合律 得到diffusion的途径 乘加(MA)结构 实现上的考虑 软件和硬件实现上的考虑,IDEA 加密算法,IDEA 每一轮,BLOWFISH算法,作者为Bruce Schneier93 BLOWFISH算法特点 采用了Feistel结构，16轮 快速：18时钟周期一个字节 紧凑：消耗不到5k内存 简单：结构简单，易于实现和判定算法强度 安全性可变：通过选择不同的密钥长度选择不同的安全级别。从32位到32*14=448位不等 子密钥产生过程复杂，一次性,BLOWFISH算法讨论,BLOWFISH算法可能是最难攻破的传统加密算法，因为S-BOX密钥相关 算法本身的特点 由于子密钥
15、和S-BOX产生需要执行521个BLOWFISH加密算法，所以不适合于密钥频繁变化的应用场合 子密钥和S-BOX产生可以保存起来 与Feistel分组密钥算法不同，每一步的两个部分都参与运算，不是简单的传递 密钥变长带来灵活性 速度快，在同类算法中相比较是最快的,RC5加密算法,作者为Ron Rivest 算法特点 三个参数 参数w：表示字长，RC5加密两字长分组，可用值为16、32、64 参数r：表示轮数，可用值0,1,255 参数b：表示密钥K的字节数，可用值0,1,255 RC5版本：RC5-w/r/b 算法作者建议标定版本为RC5-32/12/16,RC5加密算法,三个基本运算 字的加
16、法，模2w + 按位异或 左循环移位 算法： LE0 = A + S0 RE0 = B + S1 for i = 1 to r do LEi = (LEi-1REi-1) REi-1 + S2*i REi = (REi-1LEi) LEi + S2*i+1,RC5加、解密算法结构,CAST-128加密算法,RFC 214497定义 密钥48-128位，8位增量 16轮Feistel分组结构 64位分组 特殊处： 每一步两个子密钥 每一步的F不同,CAST-128每步细节图,CAST-128算法之讨论,S-Box是固定的，但设计时尽量保证了非线性。设计者认为，选择一个好的非线性S-BOX比随机的S-BOX更可取 子密钥的产生过程采用了与其他算法不同的产生法来加强其强度。目标是对抗已知明文攻击。Blowfish
