PKI相关密码体系学习总结.doc

PKI 相关密码体系学习总结相关密码体系学习总结 王文路王文路 前言前言 18831883 年荷兰语言学家和密码学家年荷兰语言学家和密码学家 Dr Dr AugusteAuguste KerckhoffsKerckhoffs 发表了著名的发表了著名的 KerckhoffKerckhoff 原则 就是密码系统的安全性只能依赖于密钥 不能依赖于算法或原则 就是密码系统的安全性只能依赖于密钥 不能依赖于算法或 者系统的任一部分 者系统的任一部分 1 对称密钥算法对称密钥算法 对称密钥算法 Symmetric key algorithms 指的是通信双方都掌握一个密 钥 加解密都由这个密钥完成的密码算法 对称加密算法分为分组密码 block cipher 也叫块状密码 算法和序列密码 stream cipher 也叫做流密码 算法 分 组密码算法中几个主要的是 DES 算法 3DES 算法 R5 算法 AES 算法和 IDEA 算法 序列密码算法中几个主要的是 R4 算法和 SSF33 算法 国家商密 1 1DES 算法算法 1 1 1产生背景产生背景 1973 年 5 月 15 日 当时美国的国家标准局 NBS 就是现在的美国国家 标准与技术研究所 NIST 在 联邦公报 上公开征集标准密码算法 他们制 定了一系列的设计准则 除了安全性 易于理解 适合应用 可以出口等等以 外 最重要的是算法的安全性必须依赖于密钥 而不依赖于算法 这个即著名 的 Kerckhoffs 原理的观点 是这次的结果不尽人意 1874 年 8 月同样的机构在 同样的地方以同样的方式发布了同样的内容 最后他们收到了一个来自 IBM 的 算法就是后来的 DES 这个算法由同样来自 IBM 的算法 Lucifer 路西法 发 展而来 这群发明这个算法的 IBM 的人员中 有个叫做 Horst Feiste 他出生在 柏林 二战时期来到美国 以他名字命名的分组密码著名的 Feistel 网络结构 一种设计分组密码的通用构造 而这个算法被改进之后成为 DES Data Encryption Standard 数据加密标准 的算法 1 1 2算法描述算法描述 对称密码算法的算法描述相对较长 但是阅读算法的数学知识使用较少 DES 是对 64 位的明文块进行加密 加密过程分为四步 生成子密钥 subkey 明文的初始置换 经过加密函数 S 盒和 P 盒 末置换 首先理解一个概念 置换 有一组数据要经过置换表的置换生成一组新数 据 例子如下 一组数据为 010110 置换表为 然后经过置换后的 数据的第一位是原数据的第二位就是 1 第三位是原数据的第四位就是 1 这样 经过置换之后的数据就是 101010 这样置换就完成了 下面我们进行 DES 的 加密过程 一 生成子密钥一 生成子密钥 DES 使用的密钥也是 64 位的数 就是 01001 这样的数值 去掉每个字节的第八位 因为每个第八位是用于奇偶校验的 parity check bits 经过一个密钥选择 这里是一个置换 所谓的 PC 1 得到 一个 56 位的值 那些第八位都去掉了 将这个 56 位的值分成前后 28 位 按照移位表 这个表只有 16 个值 为 1122222212222221 各进行前后 1 或 2 位的 16 轮移动 每次移动的 结果都进行合并得到 16 组 56 位的值 对这 16 组 56 位的值分别进行压缩置换 所谓的 PC 2 一种置换按照 表里的位置放置数据 没有提到的数据将被略去 这个表是 48 个项的 表 有 8 个位置没有在这个表中列出 得到 16 组 48 位的数 就是 16 组 48 位的子密钥 K1 K2 K16 这里从 1 开始计 二 明文的初始置换 二 明文的初始置换 initial permutation IP 置换 置换 现在开始对明文进行操作 对 64 位的明文按照 IP 置换表进行置换得到的 还是 64 位的数据 这里没有什么奇偶校验的东西 然后把这个值分成左 32 位 和右 32 位的两个值 L0和 R0 这里的数字 0 第一个不是 1 而是 0 代表对明 文经过 IP 置换后进行的 16 轮重复运算的第 1 轮 之前我们计算得到的 16 个子 密钥 k1 k2 k16将按照轮数参加到各轮的计算中 三 经过加密函数三 经过加密函数 F 的运算的运算 F 意思指 Feistel 网络 见 1 1 3 中的函数 F 的输入为 Ri 1和子密钥 Ki 扩展置换扩展置换 先对 Ri 1 32 位 进行扩展置换 规则如下 先对这 32 位进行 4 位 4 位 的分组 每个 4 位输入分组的第 1 位和第 4 位分别表示输出分组的两位 而第 2 3 位表示一位 这句话不好理解 通俗点讲就是第 1 位和第 4 位重 复两次 例如序号 1 2 3 4 输出后为 1 1 2 3 4 4 这样扩展之后 32 位的 Ri 1 变成了 48 位 然后将这 48 位的输出值与子密钥 Ki 它也是 48 位 进行 异或运算 运算符号为 得到的结果要进行 S 盒 substitution boxes 替代 S S 盒替代盒替代 这里经过与 Ki异或后的 48 位值进行分组 以 6 个为一组 自然分 8 214 653 组 对应着 8 个 S 盒进行操作 这里 8 个 S 盒每个 S 盒是个 4 行 16 列的 替代表 给个例子 S 盒 6 第 6 个 S 盒 1211015926801334147511 1015427129561131401138 91415528123704101131 1 6 432129515101 1 141760813 注意到每行都是 0 到 15 的一个排列 为什么这个 S 盒这么设计 由于原因 过度的复杂 我们这里不做讨论 但是知道这样子很安全 回来说 S 盒的 替代 举个 S 盒替换的例子 经过分组后的第 6 组为 110011 它是第 6 组 自然针对 S 盒 6 进行操作 110011 为输入 1 6 位是 11 对应 S 盒 6 的 第 3 行 从 0 开始计 如果 1 6 位是 00 就对应第 0 行 是 01 就对应第 1 行 中间的 1001 为 9 即第 9 列 当然也是从 0 开始计的 找到 S 盒 6 中的 这个位置的数 14 转化为布尔值是 1110 那么经过 S 盒 6 替代之 后的输出就是 1110 代替之前那个与 ki异或之后的值的第 6 组 即 110011 这样子 6 位的输入经过 S 盒替代之后变为 4 位 那么 8 组数经过 8 个 S 盒替代就是 32 位的值 这个 32 位的值马上要进行 P 盒置换 P P 盒替代盒替代 这个置换是直接置换 即没有省略和重复的置换 这样得到的还是一个 32 位的值 这步相对简单 这一系列动作完成后 将这个 32 位值与 Li 1 这里才用到 Li 1 异或运算 得到一个新的 32 位分组就是 Li 而 Li 1的值原封不动地成为 Ri 这时新出现的 Li和 Ri就要开始新的一轮运算了 四 末置换 四 末置换 final permutation 即 即 FP 对应一开始的对应一开始的 IP 在 DES 的最后一轮后 左半部分和右半部分并未交换 而是将 R16和 L16 直接合并在一起形成一个分组作为末置换的输入 末置换是初始置换的逆运算 即 IP 1 这时候得到的 64 位的数值即为密文 解密和加密使用相同的算法 二者的唯一区别在于子密钥的次序相反 如 果各轮加密的子密钥分别是 K1 K2 K1那么解密的子密钥就是 K16 K15 K1 1 1 3Feistel 网络网络 在密码学中 有相当大比例的分组密码算法使用这个以 IBM 的 Horst Feistel 的大叔命名的构造进行设计 这个网络最早出现在 IBM 的 Lucifer 路西 法 算法中 这个网络的设计者是 Horst Feistel 与 Don Coppersmith DES 算法 的设计者之一 Feistel 网络的思想是 取一个长度为 n 的分组 n 为偶数 然后分成长度 为 n 2 的两半部分 L 和 R 这样就可以定义一个迭代型的分组密码算法 其第 i 轮的输出取决于前一轮的输入 Li Ri 1 Ri Li 1 F Ri 1 Ki 其中 Ki是第 i 轮使用的子密钥 F 是任意一轮的轮函数 该函数保证了它的可逆性 异或被用来合并左半部分和轮函数的输出 于 是它肯定满足 Li 1 F Ri 1 Ki F Ri 1 Ki Li 1 加解密过程如图 使用 Feistel 网络或者基于 Feistel 网络设计的算法如下 Lucifer DES Triple DES Blowfish RC2 RC5 COST 28147 8 Camellia CAST 128 FEAL ICE KASUMI LOKI97 MAGENTA MISTY1 TEA MARS Twofish RC6 XTEA CAST 256 MacGuffin Skipjack 1 2三重三重 DES 算法算法 1 2 1算法描述算法描述 由于 DES 的密钥长度过短 只有 56 位 人们尝试简单地对数据进行多遍 加密 不幸的是仅仅应用两遍的 DES 的结果和 DES 安全性一样 一种叫做中 间相遇攻击 meet in the middle 或者叫做中间位面攻击 的方式可导致使用 和攻破 DES 一样的时间攻破两遍 DES 因此 不得不出现三重 DES Triple DES 而 3DES 的有效强度是 112 位 这只是原本天真的期望两遍 DES 所具 有的强度 3DES 目前的流行方式是加密 解密 加密 EDE 的模式 这种模式 和加密 加密 加密 EEE 的安全性一样 而且在三个密钥改成一个话 就等同于单次 DES 这种 3DES 的方式被引用为 3DES EDE 加密过程 M DES Ek1 DES Dk2 DES Ek3 C 解密过程 C DES Ek3 DES Dk2 DES Ek1 M 这里的三重 DES 又分两种 即 2TDS 2 key Triple DES 即 k1 k3 和 3TDES 3 key Triple DES 即三次使用的密钥各不相同 这里建议 3TDES 3DES 拥有 192 位密钥资料 168 位密钥和 24 位的奇偶校验位 但是只有 112 位的安全强度 1 2 2使用领域使用领域 IPSec 和 SSL 以及各种实用分组密码算法的地方大部分都采用 DES 或者 3DES 算法 1 3RC2 RC5 RC6 算法算法 RC 系列密码由 Ron Rivest 全名 Ronald L Rivest 设计 RC 代表 Rivest Cipher 或者 Ron s Code Ronald L Rivest 2002 年图灵奖得主 美国国家工程院院士 美国国家科学院院士 美国计算机协会院士 国际密码 研究学会院士 美国艺术与科学院院士 RC1 只存在在 Rivest 的记事本上 而 RC3 在他发明之后就被自己破解了 觉得不能拿出去丢人 就没发布 RC2 RC5 和 RC6 都是分组密码算法 而 RC4 是序列密码算法 见 1 6 RC2 和 RC4 算法都是 RSA 公司的商业秘密 但是后来都被匿名人士找出来放在互 联网上 算法被公开 1 3 1算法描述算法描述 RC2 加密算法加密算法 RC2 的一轮加密 RC2 是设计成取代 DES 的一种密钥长度可变的 64 位分组密码 也是 Feistel 网络的结构 在 SSL 中使用 128 位的密钥和 128 位有效密钥长度 现在 的 IBM Lotus Notes 也有应用 128 位的 RC2 加密算法 R5 加密算法加密算法 RC5 的一轮加密 RC5 算法的设计类似 Feistel 网络 它更加灵活 它是参数变量的分组密码 算法 分组大小 32 64 或者 128bits 密钥大小 0 2040bit 推荐 128bit 和 加密轮数 0 255 这三个参数都是可变的 RC5 加密算法使用了三种运算 异或 加 和循环 Enc C10 Key Enc C10 取最左一个字节 取最左一个字节 P10 XOR C10 C10 XOR P10 加密过程 解密过程 8 位 CFB 模式对 P10的加解密 CFB 模式也需要 IV 寄存器的前几位的产生 但是 CFB 模式下的 IV 必 须唯一 1 6 5OFB OFB output Feedback 输出反馈模式 OFB 与 CFB 模式极其相似 但是 它移位寄存器中的数和明文密文没有任何关系 离线的 寄存器中的数据作为 加密函数的输入 加密之后取这个加密输出的最左一个字节 8 位 OFB 的情况 下 有两个用处 一个是与明文块进行异或运算产生密文 密文只是异或产生 的 另一个返回到移位寄存器的最右端进行下一次操作 这里与明文进行异或 运算的移位器数据的加密输出称为密钥流 n 位的 OFB 定义如下 Ci Pi Si Si EK Si 1 这里的 Si就是密码流 S2 S3 S4 S5 S6 S7 S8 S9 S2 S3 S4 S5 S6 S7 S8 S9 Key Enc S10 Key Enc S10 取最左一个字节 取最左一个字节 P10 XOR C10 C10 XOR P10 加密过程 解密过程 8 位 OFB 模式对 P10的加解密 OFB 模式没有错误扩散 密文的单个错误只引起恢复明文的单个错误 1 6 6CTR CTR counter mode 计数模式 同 OFB 一样 CTR 模式也是一种流密码 模式 但是它生成密钥流的方式很是简单 就是使用瞬时值与计数值连接起来 然后对其加密就产生密钥流的一个密钥块 然后这部分与明文块进行异或就产 生密文 定义如下 Ki EK Nonce i Ci Pi Ki Nonce10 Counter10 Nonce10 Counter10 Key Enc Key Enc P10 XOR C10 C10 XOR P10 加密过程 解密过程 CTR 模式也没有错误扩散 可以分布式计算 其安全性依赖于加密算法和 系统提供的唯一瞬时值 1 7RC4 算法算法 1 7 1算法描述算法描述 RC4 算法是目前所知应用最广泛的对称序列密码 流密码 算法 该算法 以 OFB 方式工作 密钥流与明文相互独立 这里在了解 OFB 的工作模式后 对 RC4 的具体算法不做描述 RC4 广泛应用于商业密码产品中 2 摘要算法摘要算法 2 1哈希 哈希 hash 函数 函数 密码学的哈希 hash 函数 也被叫做杂凑函数或单向散列函数 H M 作用于任意长度的输入 M 输出为固定长度的值 h 的函数 h 叫做哈希值 hash value 也称为摘要或者校验和 密码学的哈希函数 H M 被要求有如下特性 给定 M 很容易计算出 h 但是给定 h 通过 H M 计算出 M 很难 对于给定的 M 找到另外一个不同的 M 满足 H M H M 很 难 找两个随机的不同的输入 M 和 M 满足 H M H M 很难 防碰撞 collision resistance 2 1 1 压缩函数压缩函数 大部分的哈希函数是建立在压缩函数的思想上的 压缩函数的输入是消息 分组和文本前一分组的输出 输出是到该点的所有分组的散列 即分组 Mi的散 列为 hi f Mi hi 1 2 1 2 生日攻击生日攻击 房子里面应有多少人才有可能使至少一人与你的生日相同 答案是 253 既 然这样 那么应该多少人才能使他们中至少两个人的生日相同呢 答案出乎意 料地低 23 人 对于仅有 23 人的屋子里 仍有 253 个不同对的人 寻找两个随机的具有相同生日的两个人类似于寻找两个随机的 M 和 M 满足 H M H M 这种攻击方式叫做生日攻击 birthday attack 假设一个哈希函数是安全的 而且攻击它最好的方式穷举攻击 其输出为 m 位的值 那么寻找一个输入 使其哈希值等于 m 需要计算 2m次 而寻找两 个输入具有相同的哈希值仅需要实验 2m 2个随机的数 意味着如果让对手破译 系统的可能性低于 1 280 那么应该使用 160 位的哈希函数 2 2MD2 MD4 和和 MD5 MD2 MD4 MD5 都是 Ron Rivest 设计的摘要算法 MD 意思为消息摘要 Message Digest 这三个算法都是产生 128 位的摘要值 但是 MD2 专门为 8 位的机器做过优化 它的安全性依赖于字节 byte 8bits 之间的随意置换 细节略去 MD4 算法设计并公布出来后 广大的密码分析学家对这个算法进行了破解 这个算法共三轮加密 但是前两轮和后两轮均被成功的攻击 Ron Rivest 马上 改进了该算法就是 MD5 MD5 算法以 512 位分组来处理明文 每一组又划分为 16 个 32 位的子分组 输出由 4 个 32 位的分组构成并级联成为一个 128 位的摘要 首先填充消息使其长度恰好为一个比 512 的倍数仅小 64 位的数 填充方法 是附在一个 1 在消息后边 后接要求的多个 0 然后在其后附上 64 位的消息长 度 填充前的 这两步的目的是使消息长度恰好为 512 位的整数位 同时确保 不同的消息在填充后不相同 这四个 32 位变量初始化为 A 0 x01234567 B 0 x89abcdef C 0 xfedcba98 D 0 x76543210 这些值被称为链接变量 0 x 为十六进制前缀 然后进行算法的主循环 循环次数是填充后的消息中 512 位消息分组的数目 主循环有四轮 MD4 只有三轮 每轮很相似但是不完全一样 主循环如 下图 MD5 主循环 每一轮进行 16 次操作 每次操作对 A B C 和 D 中的其中三个作一次非 线性函数运算 然后将所得结果加上第四个变量 以及文本的第一个分组和一 个常数 再将所得结果向右移动一个不定的数 并加上 A B C 或 D 中之一 最后用该结果取代 A B C 或 D 中的之一 以下为加密中用到的四个非线性函数 每轮一个 即第一轮使用 F 第二 轮使用 G 第三轮使用 H 第四轮使用 I 其中 为异或 是与 是或 是反 如图为一次操作 每轮 16 次 MD5 的一个操作过程 一次主循环要 64 次操作 所有的操作完成后 把最开始的 A B C D 分别加上生成的 A B C D 然后作为下一分组的继续运行算法 2 3SHA 1 美国国家标准和技术研究所 NIST 和美国国家安全局 NSA 共同设计 了用于安全散列标准 SHS 的安全散列算法 或安全哈希算法 SHA 但是 它有一个缺陷 NSA 随后改正了这个缺陷 现在见到的标准中的算法 SHA 1 SHA 1 与 MD5 很相似 也是基于 MD4 改进的 SHA 1 有由 5 个 32 位的字 组成的 160 位的状态 产生 160 位的散列值 或叫哈希值 SHA 1 总共也有 4 轮 3 公共密钥算法公共密钥算法 3 1数学基础数学基础 3 1 1素数的模运算素数的模运算 设 p 是素数 进行素数的模运算时 只需要使用 0 1 p 1 这些数 素数模 的基本规则是 把这些数作为整数进行运算 但是每一次的结果 r 都要对 p 进 行模运算 取模运算就是用 p 除以 r 丢弃所得的商 而把余数作为答案 例如 对 25 做模 7 运算 就是用 7 除 25 得到商为 3 余数为 4 余数就是答案 于 是 25 mod 7 4 由于模运算很常用 所以当表示方程的所有运算都是取模 p 运 算的时候 整个方程的书写都没有体现出任何模运算 只是把 mod p 加在方程 的后面 3 1 2三个数学难题三个数学难题 大整数因数分解问题大整数因数分解问题 给定两个素数 质数 p q 计算乘积 p q n 很容易 给定整数 n 求 n 的素因数 p q 使得 n p q 很难 离散对数问题离散对数问题 已知有限循环群 G k 0 1 2 及其生成元 g 和阶 n G 给定整数 a 计算 ga h 很容易 给定元素 h 计算整数 x 0 x n 使得 gx h 非常困难 椭圆曲线离散对数问题椭圆曲线离散对数问题 已知有限域 Fp上的椭圆曲线群 E Fp x y Fp Fp y2 x3 ax b a b Fp O 及点 P x y 的阶为一个大素数 给定整数 a 计算点 aP xa ya Q 很容易 给定点 Q 计算整数 x 使得 xP Q 非常困难 3 2密钥确立的方式密钥确立的方式 3 2 1RSA 算法共享会话密钥算法共享会话密钥 RSA 算法是由 Ron Rivest Adi Shamir 和 Leonard Adleman 在 1977 年发明 的 算法描述算法描述 选取两个大素数 p q 这两个数必须保密 为了安全性 可使这两个数长度 一样 然后得 n p q 选取随机的数 e 加密密钥 使 e 与 p 1 q 1 互素 互质 计算解密密钥 d 使得 e d 1mod p 1 q 1 即求 e 模 p 1 q 1 的唯一逆元 求得 d e 1 mod p 1 q 1 为解密密钥 这里 n e 为公钥 n d 为私钥 使用过程使用过程 对于明文 M 的一个分组 Mi 进行加密得密文 Ci Ci Mie mod n 解密 Mi Cid mod n 这一步在数学上可以得到证明 这样描述算法是在假定消息是一个数字 但是实际上 消息往往是一组字 串 因此必须使用一些规则将字串转换为数字 这个数字应该多少与 n 的大小 相当 但是不能比 n 大 以确保 Me n 否则 C Me mod n Me 即 mod n 没起作 用 PKCS 1 中规定了如何完成此类转换的标准过程 虽然 RSA 也可以加密数据 但是相对于对称加密算法来说 它的加密速度 过于慢 于是利用 RSA 的方式来共享加密密钥 会话密钥 首先产生一个随 机的会话密钥 经过适当的填充后 使用接收方的公钥进行加密 然后接收方 再利用自己的私钥对消息进行解密 去掉填充字节之后等到会话密钥 3 2 2DH Diffie Hellman 密钥交换 密钥交换 Diffie Hellman 算法是个首个公开 1976 年 发表的公共密码算法 很明 显这个算法是 Whitfield Diffie 和 Martin Hellman 发明的 它是一种密钥协商算 法 发送方不是产生一个密钥并针对接收方进行加密 而是由发送方与接收方 共同产生一个对他们来说是私有的密钥 发送与接收方共同拥有这个密钥对 要想计算出协商后的密钥 只要发送方组合使用其私用密钥和接收方的公用密 钥 或者接收方组合使用其私用密钥和发送方的公用密钥 首先 Alice 和 Bob 这两个人名是在密码协议讲解中普遍使用的人名 协 商出一个大的素数 n 和 g g 是模 n 的本原元 这两个数不必是秘密的 因为这 两个数要在不安全的途径上传递 Alice 选取一个大的随机整数 x 计算 X gx mod n 并发送给 Bob Bob 选取一个大的随机整数 y 计算 Y gy mod n 并发送给 Alice Alice 计算 k Yx mod n gxy mod n Bob 计算 k Xy mod n gxy mod n 在线路上的窃听者只知道 n g X 和 Y 除非他能计算离散对数 恢复出 x y 否则无济于事 3 2 3EIGamal 加密算法加密算法 Taher Elgamal 是美籍埃及人 著名的密码学家 EIGamal 算法以他的名字 命名 其安全性依赖于计算有限域上的离散对数的难度 见第二个数学难题 选择一素数 p 两个随机整数 g 和 x g 和 x 都小于 p 计算 y gx mod p 公共密钥是 y g 和 p 私人密钥是 x 它同 RSA 算法一样可以用来加密也可以用来数字签名 3 2 4椭圆曲线加密算法椭圆曲线加密算法 ECC Elliptic Curve Cryptography 基于有限域上椭圆曲线的离散对数计算 困难性 1985 年由 Koblitz 美国华盛顿大学 和 Miller IBM 公司 两人提出 定 义在有限域 Fp 或 F 2m 的椭圆曲线 y2 x3 ax b 上的点 x y 再加上无穷点 O 如按一定的规则运算 估且称为乘法 将组成一个群 数学中的一种代数 结构 有限域上椭圆曲线乘法群也有相对应的离散对数计算困难性问题 见数 学难题三 这里对 ECC 的算法不作描述 相对于 RSA 算法 ECC 算法的安全性能更好 处理速度更快 密钥存储空间更小 210 位的 ECC 就与 2048 位的 RSA 具有相 同的安全强度 3 3数字签名数字签名 3 3 1与摘要算法一起使用与摘要算法一起使用 RSA 进行数字签名进行数字签名 RSA 算法进行数字签名 先计算出消息的摘要值 使用 MD5 或者 SHA 1 并用签名者的私钥进行加密 就是签名 接收方收到摘要值和签名后使用 签名者的公钥对加密的摘要值进行解密 并与摘要值进行匹配 如果相同 则 签名是有