在密码学中的应用

第八章在密码学中的应用 II 古典密码的两大机制 代替密码 字母表范围内替换 换位密码 在消息内变换字母的位置 2 1代替密码1 描述密钥是字母表的任意组合 有一个明密对应表 密钥空间巨大 26 单表代替密码的两个特例 移位密码和仿射密码 2 举例首先选加密表 为了便于记忆 协商一个密钥 DOYOULIKETHISBOOK去掉重复字母 再进行补充 形成加密表 abcdefghijklmnopqrstuvwxyzDOYULIKETHSBACFGJMNPQRVWXZ 第二节代替与换位 第二节代替与换位 2 2换位密码1 机制 单个字符不变而位置改变 如将文本翻转 明文computersystems密文SMETSYSRETUPMOC2 特点 1 密文长度与明文长度相同 2 唯密文攻击可能得到多种不同的破译结果 如keep peek live evil vile3 分组换位密码针对固定大小的分组进行操作 举例 明文canyouunderstand 1 列换位法设密钥k 4 将明文进行分组排列 密文 CODTAUEANURNYNSD 明文 canyouunderstand 明文 canyouunderstand 1234 1234 第二节代替与换位 按列读出 type 密文 YNSDNURNCODTAUEA 明文 canyouunderstand 明文 canyouunderstand 1234 3421 YNSDNURNCODTAUEA 2 密钥为字符串type 第二节代替与换位 3 矩阵换位法 置换矩阵作为密钥 明文 canyouunderstand canyouunderstand ncyauonurdsentda 密文 NCYAUONURDSENTDA 按置换矩阵的阶4分组 canyouunderstand NCYAUONURDSENTDA 明文 canyouunderstand 解密置换矩阵 说明 第二节代替与换位 第二节代替与换位 2 3频率攻击 1 原理 利用自然语言的频率攻击字母出现的频率有规律 e 11 67t 9 53o 7 81a 7 73 the 4 65to 3 02of 2 61and 1 85 2 应用 对古典密码进行唯密文攻击 3 举例 对仿射密码的攻击密文 JFFGJFDMGFSJHYQHTAGHQGAFDCCFP统计字母出现的次数 F 6G 4H 3J 3 猜测 e 4 F 5 t 19 G 6 则有 Ea b e FEa b t G 第二节代替与换位 Ea b x 7x 3 26 解密函数为 E15 7 x 15x 7 26 解密后的明文为 meetmeaftermidnightinthealley 第二节代替与换位 4 举例 对代替密码的攻击KOSBMKKBSISSYFSJNFKBMESKOS IDYIFPKFJSSMK e ee e e ee t t t tt o o o o n i i i l k b b s s d d b a y 分析 由ESROL得到er s o l或re s o l loser或sorel 那么 由VIERD得到drive或irevd所以比较合理的明文是 loserdrive 5 举例 对换位密码的攻击ESROLVIERD 第二节代替与换位 作业 1 解密由仿射密码加密的密文 VCLLCPBKLCLJKXXCHCP 2 解密用简单换位密码加密的密文 EAGGARDAIREP 3 1群1 二元运算定义 设s为集合 函数f s s s称为s上的二元运算或代数运算 满足 可计算性 s中任何元素都可以进行这种运算 单值性 运算结果唯一 封闭性 s中任何两个元素运算结果都属于s 2 群的定义定义 设是代数系统 为G上的二元运算 如果 运算是可结合的 则称半群 若为半群 并且二元运算 存在单位元e G 则称为幺半群 若为半群 并且二元运算 存在单位元e G G中的任何元素x都有逆元x 1 G 称为群 简记为G 第三节置换 举例 1 是群 其中Z为整数集合 是普通的加法 单位元是0 整数x的逆元是 x 2 是群 Z6 0 1 2 3 4 5 为模6加法 显然 满足结合律 单位元是0 由于1 5 0 2 4 0 3 3 0 所以1和5互为逆元 2和4互为逆元 3和0的逆元仍然是3和0 3 群中元素的阶定义 设是群 a G n Z 则a的n次幂为en 0an an 1 an 0 a 1 mn中 30 0 35 15 3 5 15在群中 20 0 23 0 2 3 0 第三节置换 阶的定义 1 设是群 a G 使得等式ak e成立的最小正整数k称为a的阶 记做 a k a称为k阶元 若不存在这样的整数k 则a称为无限阶元 例如 在中 2和4是3阶元 3是2阶元 1和5是6阶元 0是1阶元 在中 0是1阶元 其他都是无限阶元 2 设为群 a G 且 a r 设k是整数 则ak e当且仅当r k 3 设为群 则群中任何元素a与其逆元a 1具有相同的阶 第三节置换 4 循环群和置换群定义1 设为群 如果存在一个元素a G 使得G ak k Z 则称G为循环群 记做G 称a为生成元 若 a n 则G称为n阶循环群 例如 是循环群 其中Z6 0 1 2 3 4 5 为模6加法 生成元为1或5 是循环群 生成元为1或 1 是循环群 Zn 0 1 n 1 生成元为1 第三节置换 定义3 设s 1 2 n s上的n 个置换构成集合sn 则称sn与置换的复合运算 构成的群为s上的n元对称群 的任意子群称为s上的n元置换群 第三节置换 定义2 设s 1 2 n s上的任何双射映射函数 s s称为s上的n元置换 记为 3 2置换概念1 置换一个集合X的置换f定义为X到自身的一个双射函数f 对应有n个元素的集合X 共有n 个置换 问题 对于集合X 给定某个状态 经过多少次置换返回初始状态 Sn 1 2 3 n 1 n 表示n个元素的置换群置换g为满足g k ik的一个置换 平凡置换e 没有移动任何元素的置换 即对于所有的i 有e i i 置换与集合内容无关 第三节置换 2 置换的合成或乘积设g和h是两个置换 先应用h 再应用g 记为 g h或gh注意 g h h g置换的合成满足结合律 g h k g h k 3 逆置换对于任意置换g 存在一个逆置换g 1 满足 g g 1 g 1 g e4 图表记法用来计算两个置换的乘积 如 第三节置换 5 循环最简单的置换是不同长度的循环 一个k循环满足 f i1 i2 f i2 i3 f ik 1 ik f ik i1 对于任意j i1 i2 ik 有f j j 举例 则 可见 g h h g 具有不可交换性 记作 i1 i2 ik 12 13 第三节置换 6 结论 1 如果g是一个k循环 那么gk e 注意 一个k循环有k种表示法 比较 123 与 132 123 231 312 如 则 即 对某个集合应用g操作k次 不会对集合产生任何影响 第三节置换 2 置换的阶是置换被多次应用后却不产生任何实际影响所需要的重复次数 若置换g是一个k循环 则有gk e g的阶为k 3 不相交的循环若g i1 ik 和h j1 jl 分别为k循环和l循环 且 i1 i2 ik 和 j1 j2 jl 是不相交的列表 则有 gh hg这样的循环g和h称为不相交的循环 第三节置换 一个置换g的阶k 不相交循环分解中各循环长度的最小公倍数 如 思考 如果一副50张的牌洗得好 重复洗8次后所有的牌将返回初始位置 阶为4 4 置换的不相交循环分解任何置换都可以表示为不相交循环的乘积 并且本质上只有这一种表示方法 1457 23 6 第三节置换 3 3切牌最简单的切牌 选择一个随机点把一副牌一分为二 然后交换两部分 n张牌 0 1 n 1i 1 n 1 0 1 i切牌过程为 fi x x n i 1 n如 n 6 i 10 1 2 3 4 52 3 4 5 0 1置换过程为 f1 x x 4 6 第三节置换 若n张牌的位置编号为 1 2 n 1 ni 1 n 1 n 1 i则切牌过程为 fi x x n i 1 n 1 第三节置换 如 n 6 i 21 2 3 4 5 63 4 5 6 1 2置换过程为 f1 x x 3 6 1 2n张牌 1 2 n n 1 2n 1 2n两半交错 n 1 1 n 2 2 2n 1 n 1 2n n1 n 1 2 n 2 n 1 2n 1 n 2n命题 对一副有2n张牌1 2 2n 1 2n的完美快速洗牌过程为 f x 2x 2n 1 推论 若e为2模2n 1的阶 即e是满足2e 1mod2n 1的最小正整数 那么对一副有2n张牌经过e次洗牌后 所有的牌都第一次返回到它们的起始位置 不好的洗牌 完美洗牌 第三节置换 3 4洗牌 然后按列读取这些数 0 n 2n mn n 1 n 1 2n 1 mn n 1 mn 1对于数x 行 x n列 x n 3 5分组交错给定正整数m和n 针对mn个元素 一个m n分组交换的置换定义为 按行将mm个数据写成m n的矩阵的形式 第三节置换 然后按列读取这些数 0 4 8 1 5 9 2 6 10 3 7 11对应的置换过程为 例 12个数据0 1 2 3 4 5 6 7 8 9 10 11 进行3 4分组交错 对应的循环分解为 数据 置换位置 阶为5 按4行3列写出 第三节置换 命题 忽略两个不动点0和mn 1 m n分组交错对集合 1 2 3 mn 2 的作用是 x mx mn 1 举例 3 6分组交错 3x 17 3x 17 分析 快速洗牌 去掉两个不动点完美的快速洗牌 x 2x 2n 1 第三节置换 作业 1 计算乘积 第三节置换 用不相交循环的乘积表示上述的结果 并确定阶 2 S5中任意元素的最大阶是多少 S14呢 3 确定对一副20张牌的完美快速洗牌的循环分解 4 找出3 5的分组交错置换的循环分解 第四节现代对称密码 香农提出的现代密码设计准则 Kerchhoff原则 系统的安全性不依赖于对密文或加密算法的保密 而依赖于密钥 惟一需要保密的是密钥 决定了古典密码学与现代密码学 一个好的密码将融合混淆和扩散混淆 混淆明文的不同部分 扩散 对攻击者隐藏一些语言的局部特征 现代密码将结合换位和代替 代替密码在混淆上是有效的 换位密码扩散性较好 4 1数据加密标准DES DataEncryptionStandard 1976年被采纳作为联邦标准 并授权在非密级的政府通信中使用 应用广泛 DES是一个分组加密算法 对称密码 64位分组 密钥长度为64位 实际长度为56位 第四节现代对称密码 现代密码算法的特点 只要保证密钥安全 就能保证加密信息的安全 对称密码算法 很好地融合了混淆和扩散 DES AES IEDA RC6等非对称密码算法 基于数学难题 RSA ECC ElGamal等 DES的整个算法是公开的 系统的安全性靠密钥保证 算法包括三个步骤 初始置换IP 16轮迭代的乘积变换 逆初始变换IP 1 1 初始置换IP初始置换IP可将64位明文M m1m2 m64的位置进行置换 得到乱序的64位明文组M0 m58m50 m7 2 逆初始置换IP 1逆初始置换IP 1将16轮迭代后的64比特数据的各字节按列写出 将前四列插到后四列中 再对各列进行逆序 然后将元素按行读出即可得到输出的密文组 IP和IP 1的作用主要是打乱输入的ASCII码字划分关系 并将明文校验码变成IP输出的一个字节 第四节现代对称密码 第四节现代对称密码 第四节现代对称密码 第四节现代对称密码 举例 设64位明文M为 0000000011111111010101010001000110001000110011000011001110101010则经过IP置换后的M0为 0010011001001110001001100100111010110010110000101011001011000010转换过程如下 第四节现代对称密码 3 乘积变换乘积变换是DES算法的核心部分 将经过IP置换后的数据分成32位的左右两组 在迭代过程中彼此左右交换位置 每次迭代时只对右边的32位进行一系列的加密变换 然后把左边的32位与右边得到的32位逐位进行异或操作 作为下一轮迭代时左边的段 迭代公式为 Li Ri 1 Ri Li 1 f Ri 1 ki 按位异或操作运算符 即按位作模2相加运算 运算规则为 1 0 1 0 1 1 0 0 0 1 1 0 f的功能是将32比特的数据经过选择扩展运算E 密钥加密运算 选择压缩运算S和置换运算P转换为32比特的输出 第四节现代对称密码 第四节现代对称密码 1 选择扩展运算E选择扩展运算下可将输入的32比特Ri 1扩展成48位的输出 令s表示E原输入数据比特的下标 则E的输出是将原下标s为0或1 模4 的各比特重复一次得到的 实现数据扩展 第四节现代对称密码 2 密钥加密运算密钥加密运算将48比特的子密钥ki与选择扩展运算E输出的48比特数据进行按位异或运算 举例 设32比特数据Ri 1为00000000111111110000000011111111 48比特子密钥ki为000000001111111101010101101010101100110010001000 求Ri 1经过选择扩展运算E后与子密钥ki异或后的结果 第四节现代对称密码 16个子密钥ki的产生 64比特初始密钥k经过换位函数PC 1将位置号为8 16 24 32 40 48 56和64的8位奇偶位去掉并换位 换位后的数据分为2组 经过循环左移位LSi和换位函数PC 2变换后得到每次迭代加密用的子密钥ki 第四节现代对称密码 第四节现代对称密码 LSi表示求子密钥ki时将Ci 1和Di 1进行循环左移 其移位位数为 3 选择压缩运算选择压缩运算可将密钥加密运算后的48比特数据从左至右分成8组 每组为6比特 并行迭入8个S盒后压缩成32比特输出 每个S盒的输入为6比特 输出为4比特 以完成压缩变换 对于某个S盒Si 假设其输入为b1b2b3b4b5b6 在Si表中找到b1b6行 b2b3b4b5列的整数 转换为4位二进制就是输出的4比特数据 第四节现代对称密码 第四节现代对称密码 第四节现代对称密码 举例 设S5的输入为b1b2b3b4b5b6 110110 则 b1b6 2 10 2 2 b2b3b4b5 2 1011 2 11在S5中找到行为2 列为11的数据5转换为4位二进制为0101 所以S5的输出为0101 4 置换运算PS1 S8盒的输出合成32比特数据后 用换位表p进行置换 得到的32比特数据就是f Ri 1 ki 的输出 第四节现代对称密码 DES的解密算法和加密算法相同 只是在解密过程中将子密钥的顺序颠倒 DES的出现在密码史上是个创举 以前任何设计者对于密码体制细节都是严加保密的 自公布以来 它一直活跃在国际保密通信的舞台上 成为商用保密通信和计算机通信的最常用的加密算法 由于DES的安全性完全依赖于密钥 而其64位的密钥太短 因而出现了许多DES的改进算法 如三重DES 分组反馈连接式DES以及密码反馈模式DES等 随着新的攻击手段和改进的加密算法的不断出现 DES也许将完成它的历史使命 高级加密标准AES评选于2000年10月结束 Rijdael算法为AES的唯一算法 第四节现代对称密码 4 DES的安全性 1 差分分析1990年Biham和Shamir提出差分密码分析 是一种比穷举攻击有效的选择明文的攻击方法 差分分析的攻击方法是针对DES和其他类似的有固定S盒的算法 DES的S盒恰好最适宜于抗差分分析 最佳差分分析的总结表明对16轮DES的攻击需选择明文247 分析的复杂性为237 2 线性密码分析MitsuruMatsui提出了线形密码分析 使用线性近似值来逼近分组密码的操作 攻击完整的16轮DES 当已知明文的平均数为243时 可得到密钥 是最有效的攻击DES的方法 第四节现代对称密码 第四节现代对称密码 4 2序列密码1 随机数生成器 1 任意