Ξ 第 3 期 2000 年 8 月 微　处　理　机 M ICRO PROCESSOR S N o. 3 A ug. , 2000 基于单片机的实时 3D ES 加密算法的实现 郑　磊 　易　波 国防科技大学电子工程学院 (长沙 410073) 　　摘　要　首先简要介绍了 3D ES 加密算法, 接着给出了用单片机来实时实现该算 法时为了提高运算速度而采用的两种方法, 并给出了实际测试结果。 关键词　信息安全　3D ES　并行存储　并行处理 The Im p lem e n ta tion of the Re a l- tim e 3D ES Enc ryp tion A lgo rithm B a s e d on the S ing le C h ip C om pute r ZhengL ei, et al C olleg e of E lectron ic E ng ineering , N a tiona l U n iversity of D ef ence T echnology , C hang sha 410073 　　Abstract　T he 3D ES encryp tion algo rithm is b riefly in troduced in th is p ap er at first, and tw o m ethod s w h ich are u sed to save com p u ting tim e in the im p lem en tation of th is algo rithm are p rovided, at last the resu lt of the p ractical test is attached. Keywords　info rm ation secu rity, 3D ES, p aralle sto rage, p aralle p rocessing 1　引　言 2　3D ES 加密算法简介 现代社会已进入信息时代, 社会的发展越 来越需要信息安全技术的广泛应用。 而单片机 技术是迄今为止发展较为成熟且应用非常广泛 的一门技术, 如果能够将单片机技术和信息安 全技术紧密结合起来将对信息安全技术的广泛 应用起到强有力的推动作用。 数据加密技术是信息安全技术的核心, 许 多优秀、成熟的加密算法 (如 3D ES 1 、R SA 2 ) 的运算复杂度都非常大。 由于单片机的工作频 率一般不高, 机器字长较短, 指令的位运算功能 不强, 因此使用它来实现这些算法时运算速度 通常无法满足实时应用的要求, 如何提高用单 片机实现这些算法时的实时运算速度已成为实 现这一结合急待解决的问题。 本文针对这一问 题给出了用单片机来实现 3D ES 加密算法时提 高实时运算速度的两种方法。 男, 24 岁, 硕士研究生, 研究方向: 数据压缩和数据加密 　收稿日期: 1999- 11- 26 3D ES (又名 3 重 D ES) 加密算法是基于 (D ata Encryp tion Standard) 且强度更高 D ES 2 的一种加密算法, 其算法可以用式 (1. 1) 和式 (1. 2) 表示。 令 D ESK 表示密钥 K 作用下的加 密变换, 且 D ES- 1 K 为相应的解密变换。 128b it 密钥 K 被分成密钥 KL (K 的左边 64 b it) 和 KR (K 的右边 64 b it)。 明文M 被加密成 C= D ESKL [D ES- 1 (1. 1) KR [D ESKL (M ) 密文 C 的解密过程是加密的逆过程 KL (C) KL [D ESKR [D ES- 1 M = D ES- 1 (1. 2) 由式 (1. 1) (1. 2) 不难看出, 提高 3D ES 运 算速度的关键是如何提高D ES 算法的运算速 度。D ES 算法的运算步骤如图 1, 其中耗时最多 的是乘积变换部分 (其原理见图 2, 图中L I- 1 和 R I- 1分别是进行一次迭代时的左边 32 比特和右 边 32 比特) , 如果能减少这部分的用时则整个算 

　3 期 郑磊等: 基于单片机的实时 3D ES 加密算法的实现 ·14· 法的运算速度将得以提高。 下面给出了用单片机 来实现该算法时提高运算速度的两种方法。 3　通过改进选择压缩运算 S 的查找策 略来提高 3D ES 的运算速度 传 统 的 选 择 压 缩 运 算 S 将 前 面 送 来 的 48b it 数据自左至右分成 8 组, 每组 6b it, 而后 并行送入 8 个 S 盒, 每个 S 盒输出 4b it。 以 S1 (见表 1) 为例, 当输入的数据为 x 6x 5x 4x 3x 2x 1 时, 先 找 到 x 6x 1 对 应 的 S1 中 的 一 行, 再 找 x 5x 4x 3x 2 对应的 S1 中的一列, 行列交叉处的数 据即为 x 6x 5x 4x 3x 2x 1 经过 S1 的输出, 这种查找 方法是二维查找。用单片机实现这一过程时, 首 先要从 x 6x 5x 4x 3x 2x 1 这六个比特位中提取 x 6x 1 这两位, 分别计算出 x 6x 1 和 x 5x 4x 3x 2 的值, 然 后在表 S1 中进行二维查找。由于用单片机实现 位提取时要用到多句的位运算指令, 这就使得 在完成乘积变换的 16 次迭代时要在这部分耗 去大量的时间, 而且二维查找也使算法执行速 度降低。 图 2　乘积变换框图 ( I= 1～ 16) 表 1　S1 函数 列 行 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 1 4 8 2 15 2 6 9 2 14 13 4 13 7 14 8 4 15 1 12 14 0 4 15 11 13 2 1 　　通过改进选择压缩运算 S 中的查找策略可 以大量减少位运算且将原来的二维查找变为一 维查找, 而运算结果与原来的选择压缩运算 S 的运算结果完全一致。 在选择压缩运算 S 中改 进后的查找策略是将原有的各 S 盒重新排列, 得到新的 S′盒, 其输出是输入的线性函数且与 S 盒等价。 具体的排列方法是这样的: 以 S1 为 例, 将 S1 表中的每个值按其对应的二进制数 x 6x 5x 4x 3x 2x 1 (x 6 是最高位, x 1 是最低位) 按由小 到大的顺序排列成一个一维数组 S1′(见表 2) , 当 输 入 为 x 6x 5x 4x 3x 2x 1 时, 输 出 为 S1′ [ x 6x 5x 4x 3x 2x 1 ]。 例 如, 输 入 x 6x 5x 4x 3x 2x 1 = 101100 时, 按以前的查找方法将在 S1 的第二 行 (x 6x 1= 10) 第六列 (x 5x 4x 3x 2= 0110) 交叉处找 到 输 出 值 2; 而 采 用 新 的 查 找 方 法 只 需 由 12 11 7 14 6 12 9 2 9 5 10 0 5 9 3 10 10 6 12 11 3 10 15 5 8 1 11 7 x 6x 5x 4x 3x 2x 1 = 101100 = 38 在 S1′中 找 到 S1′ 38 = 2 。 其它七个 S 盒也采用类似方法进行 重排。 7 8 0 13 0 3 5 6 新的查找方法不需要进行位提取, 这就省 去了大量的位操作, 而且新的查找方法进行的 是一维查找, 因此使得整个运算速度得以提高。 在用单片机实现加密算法时可以将重新排列得 到 S1′盒按一维数组的方式存放在内部 ROM 中, 每个 S1′盒占用 ROM 中连续的 64 个字节。 4　采用数据并行存放的方式来提高运算 速度 通常人们使用硬件来实现 3D ES 加密算法 时, 明文、密文以及中间数据都是按位连续存放 的。 如 64b it 数据 d1d2d3. . . d63d64在 RAM 中的 存放方式见表 3。 

·24· 微　处　理　机 表 2　S1′函数 2000 年　 输入 x 6x5x 4x3x 2x 1 输出 输入 x 6x5x4x 3x2x 1 输出 输入 x6x 5x4x 3x 2x1 输出 输入 x6x5x 4x3x 2x 1 输出 000000 000001 000010 000011 000100 000101 000110 000111 001000 001001 001010 001011 001100 001101 001110 001111 14 0 4 15 13 7 1 4 2 14 15 2 11 13 8 1 010000 010001 010010 010011 010100 010101 010110 010111 011000 011001 011010 011011 011100 011101 011110 011111 3 10 10 6 6 12 12 11 5 9 9 5 0 3 7 8 100000 100001 100010 100011 100100 100101 100110 100111 101000 101001 101010 101011 101100 101101 101110 101111 4 15 1 12 14 8 8 2 13 4 6 9 2 1 11 7 110000 110001 110010 110011 110100 110101 110110 110111 111000 111001 111010 111011 111100 111101 111110 111111 15 5 12 11 9 3 7 14 3 10 10 0 5 6 0 13 表 3　一般的数据存放方式 d1d2d3d4d5d6d7d8 d9d10d11d12d13d14d15d16 …d57d58d59d60d61d62d63d64 　　　第一字节　　　　第二字节　　　　　　　…　　　第八字节 这种存放方式使得在乘积变换中对数据进 行选择扩展运算 E 和置换运算 P 时要用到大 量的位运算, 从而严重影响了 3D ES 的运算速 度, 限制了它的实时应用。 我们将采用一种新的数据存放方式, 即将 每组数据的 64 个比特位分开分别存放到 64 个 字节中, 属于同一组数据的各个比特占用每个 字节中相同位置的比特位, 这样 64 个字节可以 并行存放 8 组数据。 例如有 8 组数据 a～ h, 每 个字母代表一组 64b it 的数据, 属于同一组数 据的不同比特位用字母加下标表示, 这样这八 组数据的存放方式如表 4。 表 4　改进后的数据存放方式 第 1 字节 第 2 字节 第 3 字节 第 4 字节 … 第 63 字节 第 64 字节 高位　　　　低位 a1b1c1d1e1f1g1h 1 a2b2c2d2e2f2g2h 2 a3b3c3d3e3f3g3h 3 a4b4c4d4e4f4g4h 4 … a63b 63c63d63e63f63g63h 63 a64b 64c64d64e64f64g64h 64 数据采用这种方式存放后, 在进行选择扩 展运算 E 和置换运算 P 时将不必象以往那样 频繁地使用位操作指令, 替代它们的是简捷的 字节交换; 而且由于数据是按位并行存储的, 所 以每做一次换位运算时八组数据同时得到了处 理, 这种并行处理的方式大大提高了整个算法 的运算速度。 数据采用这种方式存放后在进行 选择压缩运算 S 时, 先要从不同的字节中提出 属于同一组数据的连续 6 个比特位, 然后计算 出它们表示的二进制值, 因此使得采用这种方 式存放后的选择压缩运算 S 耗时比以前略长, 但是由于有并行处理的优势 (对于机器字长越 长的单片机这种优势越明显, 当机器字长为 16 位时可以并行处理 16 组数据) , 整个 3D ES 算 法的速度还是有了很大的提高。 5　实际测试结果 笔者用 A T 89C51 3 实现 3D ES 加密算法 时 (使用 8M 的外部时钟) , 采用以上介绍的两 种方法后对 64 byte 字节明文进行加密所用的 时间由以前的 150m s 提高到 12m s (也即42. 7k s) , 完全满足了通过调制解调器进行串行 b it 通信的需要。 由以上的分析和实际测试的结果我们可看 出, 本文给出的两种方法切实可行, 而且可以作 为用单片机实现别的加密算法时提高运算速度 的借鉴。 参考文献 1　刘尊全著. 刘氏高强度公开加密算法设计原理与装 置. 北京: 清华大学出版社, 1998 2　王育民, 何大可著. 保密学—— 基础与应用. 西安: 西安电子科技大学出版社, 1990 3　余永权著. A TM EL 89 系列 (M CS- 51 兼容) F lash 单片机原理及应用. 北京: 电子工业出版社, 1997