DES算法实现与分析论文

项目报告 项目报告 DESDES 算法的实现与分析算法的实现与分析 组员 柴彦廷 121041302 李雨潇 121041316 唐均 121041328 王森 121041333 王钰 121041334 熊枫 121041337 目录目录 1 引言 2 2 项目研究 2 2 1 框架设计 模块划分 3 2 2 DES 加密技术简介 3 3 方案设计 3 3 1 明文的输入与转化 4 3 2 S 盒及 P 盒原理简介 4 3 3 子密钥的产生 5 3 4 16 轮循环加密 5 4 仿真结果输出 5 5 DES 算法特点总结 8 6 参考文献 8 7 程序代码 9 一 引言 项目的选题目的和意义 I DES 采用分组乘积密码体制 它是由 IBM 开发 是对早期被称为 Lucifer 密码体制的改进 DES 在 1975 年 3 月 17 日首次在联邦记录中公布 而且声明 对比算法征求意见 到 1977 年 2 月 15 日拟议中的 DES 被采纳为 非密级 应 用的一个联邦标准 最初预期 DES 作为一个标准只能使用 10 15 年 然而 出于种种原因 可 能是 DES 还没有受到严重的威胁 事实证明了 DES 要长寿得多 在其被采用后 大约每隔 5 年被评审一次 DES 的最后一次评审是在 1999 年 1 月 但是 随着 计算机计算能力的提高 由于 DES 的密钥过短 仅有 56 位 对 DES 的成功攻击 也屡见报端 尽管如此 DES 的出现是现代密码学历史上非常重要的事件 它 对于我们分析掌握分组密码的基本理论与设计原理仍然具有重要的意义 本课题是在 Matlab 的环境下对 DES 算法的实现和分析 探究 DES 算法的原 理 二 项目研究 2 1 框架设计 模块划分 2 1 1 总体分为三个模块 1 数据初始化 明文的输入 字符串形式 及转化为数字串 2 产生子密钥 3 16 轮循环加密及密文输出 2 1 2 总体流程图 II 2 2 DES 加密技术简介 DES 是一个 16 轮的 Feistel 型结构密码 它的分组长度为 64 比特 用一 个 56 比特的密钥来加密一个 64 比特的明文串 输出一个 64 比特的密文串 其 中 使用密钥为 64 比特 实用 56 比特 另 8 位用作奇偶校验 加密的过程是 先对 64 位明文分组进行初始置换 然后分左 右两部分分别经过 16 轮迭代 然后再进行循环移位与变换 最后进行逆变换得出密文 加密与解密使用相同 的密钥 因而它属于对称密码体制 假设输入的明文数据是 64 比特 首先经过初始置换 IP 后把其左半部分 32 比特记为 L0 右半部分 32 比特记为 R0 即成了置换后的输入 然后把 R0 与密 钥产生器产生的子密钥 k1 进行运算 其结果计为 f R0 k1 再与 L0 进行摸 2 加得到 L0 f R0 k1 把 R0 记为 L1 放在左边 而把 L0 f R0 k1 记为 R1 放在 右边 从而完成了第一轮迭代运算 在此基础上 重复上述的迭代过程 一直 迭代至第 16 轮 所得的第 16 轮迭代结果左右不交换 即 L15 f R15 k16 记 为 R16 放在左边 而 R15 记为 L16 放在右边 成为预输出 最后经过初始置换 的逆置换 IP 1 运算后得到密文 III 3 方案设计 3 1 明文的输入与转化为数字串 由于输入的明文和密钥都是 16 进制表示的字符串格式 因此在输入后要将 字符串转换为 01 数字串 程序 MB 定义变量 MB for i 1 16 开始循环 Mi M i 将输入字符串 M 的第 i 位赋值给 M i MBi 0000 dec2bin hex2dec Mi 将 16 进制数转化为 2 进制 MBi MBi end 3 end MBi str2num MBi 1 str2num MBi 2 str2num MBi 3 str2num MBi 4 字符串矩阵被转换成一个数值矩阵 MB MB MBi end M MB 3 2S 盒及 P 盒原理简介 S 盒运算 在密码函数 f R k 中有 8 个 S 盒 称为 8 个不同的选择函数 分别用 S1 S2 S8 表示 每个 S 盒都是将 6 位作为输入 得到一个 4 位块作为输出 以 S1 为例 若 B 是 6 位的一个块 则 S1 B 计算如下 B 的第一和最后一 位表示从 0 到 3 之间的二进制数 令该数为 i 而 B 的中间 4 位表示从 0 到 15 之间的二进制数 令该数为 j 在该表 S1 中查第 i 行 j 列的数 它是从 0 到 15 之间的一个数 且唯一地由 4 位块代表 则该块就是输入 B 的 S1 的输出 S1 B 例如对于输入为 101000 而言 行是 10 即第 2 行 而列是由 0100 确定 即第 5 列 S1 盒的第 2 行与第 5 列的交叉处即为 B 因而输出为 1101 因此 1101 就 是 S 盒 S1 在输入为 101000 时的输出 P 盒运算 置换函数 P 是通过输入块的位 从 32 位输入中得到 32 位的输出 函数 P 的输出 P C 是通过 C 的第 16 位为 P C 的第 1 位 取第 7 位为 P C 的第 2 位 取第 25 为 P C 的第 32 位 现在我们就令 S1 S2 S8 为 8 个不同的选择函数 P为置换函数 E为 扩展函数 为了计算 f R k 先规定 B1 B2 B8 每个为 6 位块 且 B1 B2 B8 k E R IV 于是有 f R k P S1 B1 S2 B2 S8 B8 因此 在 f R k 的计算中将 k E R 分成 8 个块 即每块 6 位 即 Bi 然后每个 Bi 取作 Si 的一个输入就得到每个都为 4 位的 8 个块 Si Bi i 1 2 8 的输出 再将此 8 块连接成 32 位的整块 这个整块就构成了 P 的输出 经 P 置换 即为 f R k 的输出 3 3子密钥的产生 在 DES 中 每一轮迭代都使用了一个轮密钥 轮密钥是从用户输入的密钥 k 64 位 产生的 实用密钥是 56 位 另 8 位是奇偶校验位 输出密钥 k 的第 8 16 64 位为奇偶校验位 每一字节的最后一位 这些位的值使得每 个字节恰好包含了奇数个 1 这样如果输入密钥中某个字节中存在一个错误 奇偶校验可以帮助查到这些错误 输入的密钥 k 先经过一个置换 称为 置换选择 1 进行重排 置换结 果 56 位 被当成两个 28 比特的量 C0 与 D0 其中 C0 是置换结果的前 28 位 而 D0 是置换结果的后 28 位 注意到 在置换选择 1 中不出现第 8 16 24 32 40 48 6 4 位 因此实际 64 位的密钥 k 在经过置换选择 1 后 奇偶校验位被删除掉而仅保留下有效的 56 位密钥 置换选择 1 与初始置换 IP 的含义类似 例如 置换结果 C0 的第 7 位是输入密钥 k 的第 9 位 而置换 结果 D0 的第 10 位是输入密钥的第 54 位 在计算第 i 轮迭代所需要的子密钥时 首先对 Ci 1 与 Di 1 进行循环 左移 分别得到 Ci 与 Di 循环的次数取决于 i 的值 如果 i 1 2 9 和 16 循环左移的次数是 1 否则循环左移的次数等于 2 这些经过移位的值将作 为下一个循环的输入 然后 以 Ci Di 作为另外一个由 DES 算法固定的置换选 择 称为 置换选择 2 的输入 所得到的置换结果即为第 i 轮迭代所需要 的子密钥 ki 3 4 16 轮循环加密 以经过 S1 为例 B R Ki 1 6 x B 1 2 B 6 1 将第一比特与第六比特组合在一起形成行号 x y B 2 8 B 3 4 B 4 2 B 5 1 将第二三四五比特组合在一起形成列号 y C 0000 dec2bin S1 x y 将由盒 s1 查到的十进制数转化为四位二 进制 C C end 3 end 将 C 编号为 C 1 C 2 C 3 C 4 C1 str2num C 1 str2num C 2 str2num C 3 str2num C 4 V 4 测试 对于相同的明文 当密钥不同时 经过 DES 加密所得的密文是不同的 对于相同的密钥 不同明文通过 DES 加密所得密文不同 5 DES 算法特点总结 算法特点 分组比较短 密钥太短 密码生命周期短 运算速度较慢 DES 算法具有极高安全性 到目前为止 除了用穷举搜索法对 DES 算法进行攻击外 还没有发现更有效的办法 而 56 位长的密钥的穷举空间为 256 这意味着如果一台计算机 的速度是每一秒钟检测一百万个密钥 则它搜索完全部密钥就需要将近 2285 年的时间 可见 这是难以实现的 然而 这并不等于说 DES 是不可破解的 而实际上 随着硬件 VI 技术和 Intemet 的发展 其破解的可能性越来越大 而且 所需要的时间越来越少 使用 经过特殊设计的硬件并行处理要几个小时 6 参考文献 1 1 美 帕尔 美 佩尔茨尔 深入浅出密码学 常用加密技术原理与应用 M 清华大学出版社 2012 2 2 加 斯廷森 密码学原理与实践 M 电子工业出版社 2009 3 3 CleveMoler MATLAB 数值计算 M 北京航空航天大学出版社 2015 7 程序代码 function C DEST M K 数据加密标准 DES 算法的 Matlab 实现 输入明文 M 和密钥 K 用 16 进制数表示 字符串格式 第一步 数据初始化 以字符串形式输入的明文转换成 01 数字串 MB for i 1 16 Mi M i MBi 0000 dec2bin hex2dec Mi 将 16 进制数转化为 2 进制 MBi MBi end 3 end MBi str2num MBi 1 str2num MBi 2 str2num MBi 3 str2num MBi 4 字符串矩阵被转换成一个数值矩阵 MB MB MBi end M MB 以字符串形式将输入的密钥转化成 01 数字串 KB for i 1 16 Ki K i KBi 0000 dec2bin hex2dec Ki KBi KBi end 3 end VII KBi str2num KBi 1 str2num KBi 2 str2num KBi 3 str2num KBi 4 KB KB KBi end K KB E 32 1 2 3 4 5 4 5 6 7 8 9 8 9 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 1 将 32 比特变成 48 比特的扩展换位表 功能表 S 盒 S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 S2 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 S4 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 VIII 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 S5 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 S6 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 S7 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S8 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 1 9 13 30 6 22 11 4 25 直接换位表 单纯换位表 P 盒置换表 PC1 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 1 1 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 4 5 37 29 21 13 5 28 20 12 4 将密钥去除奇偶校验的去除表 PC2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 将 56 比特的密钥经过压缩换位变成 48 比特的轮密钥 第二步 产生子密钥 Ki zeros 16 48 K PC1 K PC1 经过密钥初始置换 C0 K PC1 1 28 将密钥分成左边 28 比特 D0 K PC1 29 56 右边 28 比特 IX for i 1 16 if i 1 i 2 i 9 i 16 在置换之后 密钥到的左右两部分都根据比特移位 表左移一位 或者两位 由移位表可知第 1 2 9 16 轮循环左移 1 位 C0 C0 2 end C0 1 D0 D0 2 end D0 1 else 其它轮循环左移 2 位 C0 C0 3 end C0 1 2 D0 D0 3 end D0 1 2 end K LS C0 D0 Ki i K LS PC2 将循环移位之后 56 比特压缩置换变为 48 比特的轮密钥 k1 k2 k3 k4 到 k16 end 第三步 16 轮循环加密 L M 1 32 输入的左半部分明文 R M 33 64 输入的右半部分明文 以下是 16 轮迭代 for i 1 16 E0 reshape E 1 48 把 E 盒转换成 1 48 的行 向量 R E R E0 E 盒扩展 R Ki mod R E Ki i 2 与子密钥 mod2 相加 经过 S1 盒 B R Ki 1 6 x B 1 2 B 6 1 将第一比特与第六比特组合 在一起形成行号 y B 2 8 B 3 4 B 4 2 B 5 1 将第二三四五比特组合在一起形成 列号 y C 0000 dec2bin S1 x y 将由盒 s1 查到的十进制数 转化为四位二进制 C C end 3 end 将 C 编号为 C 1 C 2 C 3 C 4 X C1 str2num C 1 str2num C 2 str2num C 3 str2num C 4 经过 S2 盒 B R Ki 7 12 x B 1 2 B 6 1 y B 2 8 B 3 4 B 4 2 B 5 1 C 0000 dec2bin S2 x y C C end 3 end C2 str2num C 1 str2num C 2 str2num C 3 str2num C 4 经过 S3 盒 B R Ki 13 18 x B 1 2 B 6 1 y B 2 8 B 3 4 B 4 2 B 5 1 C 0000 dec2bin S3 x y C C end 3 end C3 str2num C 1 str2num C 2 str2num C 3 str2num C 4 经过 S4 盒 B R Ki 19 24 x B 1 2 B 6 1 y B 2 8 B 3 4 B 4 2 B 5 1 C 0000 dec2bin S4 x y C C end 3 end C4 str2num C 1 str2num C 2 str2num C 3 str2num C 4 经过 S5 盒 B R Ki 25 30 x B 1 2 B 6 1 y B 2 8 B