密码学基础课件北大）课件.ppt

网络与信息安全密码学基础(一) 潘爱民，北京大学计算机研究所 panaimin@ /InfoSecCourse 内容 对称加密算法 经典密码算法 现代密码算法 AES 随机数发生器 对称加密算法的基本模型 加密: E: (X,K) ? Y, y = E(x,k) 对称加密算法研究 对称加密算法的特点 算法强度足够 安全性依赖于密钥，不是算法 速度快 两门学科 密码学 密码分析 用对称加密算法建立起来的安全通讯 密码学 三种考虑角度 （1）从明文到密文的变换 替换(substitution) 置换(transposition) …… （2）钥匙的数目 对称、单钥加密法 双钥、公钥加密 （3）明文的处理方式 分组加密（块加密算法） 流方式加密 密码分析 发现X和K的过程被称为密码分析 分析的策略取决于加密的技术以及可利用的信息，在加密算法设计和攻击时都需要用到的技术 根据可利用信息的不同，可分为5类： （1）只有密文 （2）已知部分明文-密文对 （3）选择明文 （4）选择密文 * （1）（2）（3）常见、（4）不常见 加密算法的有效性 Unconditionally secure，绝对安全？ 永不可破，是理想情况，理论上不可破，密钥空间无限，在已知密文条件下，方程无解。但是我们可以考虑： 破解的代价超过了加密信息本身的价值 破解的时间超过了加密信息本身的有效期 Computationally secure， 满足上述两个条件 直觉：什么是一个好的加密算法 假设密码(password)k是固定的 明文和密文是一个映射关系：单射，即 Ek(x1) != Ek(x2) if x1 != x2 通常情况是：明文非常有序 好的密码条件下，我们期望得到什么样的密文 随机性 如何理解随机性 静态：特殊的点 动态：小的扰动带来的变化不可知 考虑设计一个加密算法 打破明文本身的规律性 随机性(可望不可及) 非线性(一定要) 统计意义上的规律 多次迭代 迭代是否会增加变换的复杂性 是否存在通用的框架，用于迭代 复杂性带来密码分析的困难和不可知性 实践的检验和考验 已有密码算法的讨论 经典密码算法 替换技术 置换技术 现代密码算法 DES 其他密码算法 AES密码算法 Rijndael 经典密码算法 替换技术 Caesar加密制 单表替换加密制 Playfair加密制 Hill加密制 多表加密制 置换技术 改变字母的排列顺序，比如 用对角线方式写明文，然后按行重新排序 写成一个矩阵，然后按照新的列序重新排列 转轮加密体制 多步结合 经典密码算法特点 要求的计算强度小 DES之前 以字母表为主要加密对象 替换和置换技术 数据安全基于算法的必威体育官网网址 密码分析方法基于明文的可读性以及字母和字母组合的频率特性 现代密码算法 DES(Data Encryption Standard) IDEA Blowfish RC5 CAST-128 …… 分组密码算法设计指导原则 Diffusion(发散) 小扰动的影响波及到全局 密文没有统计特征，明文一位影响密文的多位，增加密文与明文之间关系的复杂性 Confusion(混淆) 强调密钥的作用 增加密钥与密文之间关系的复杂性 结构简单、易于分析 Feistel分组加密算法结构之动机 分组加密算法，一一映射 当n较小时，等价于替换变换 当n较大时，比如n=64，无法表达这样的任意变换。 Feistel结构很好地解决了二者之间的矛盾 Feistel分组加密算法结构之思想 基本思想：用简单算法的乘积来近似表达大尺寸的替换变换 多个简单算法的结合得到的加密算法比任何一个部分算法都要强 交替使用替换变换和排列(permutation) 混淆(confusion)和发散(diffusion)概念的应用 Feistel结构图 Feistel结构定义 加密: Li = Ri-1; Ri = Li-1?F(Ri-1,Ki) 解密: Ri-1 = Li Li-1 = Ri?F(Ri-1,Ki) = Ri?F(Li,Ki) Feistel分组加密算法特点 分组大小。越大安全性越高，但速度下降，64比较合理 密钥位数。越大安全性越高，但速度下降，64广泛使用，但现在已经不够用—〉128 步数，典型16步 子钥产生算法。算法越复杂，就增加密码分析的难度 每一步的子函数。函数越复杂，就增加密码分析的难度 快速软件实现，包括加密和解密算法 易于分析。便于掌握算法的必威体育官网网址强度以及扩展办法。 Feistel分组加密算法之解密算法 Feistel分组加密算法之解密算法推导 DES算法 1977年由美国的标准化局(NBS，现为NIST)采纳 64位分组、5