嵌入式设备身份认证系统培训课程.doc

1 52 目目 录录 摘 要 1 ABSTRACT 2 第 1 章 绪论 3 1 1研究背景 3 1 2 国内外研究状况 3 1 2 1 古典密码学 4 1 2 2 现代密码学 4 1 2 3 总线介绍 9 1 3 小结 11 第 2 章 相关算法的描述 12 2 1 分组密码 12 2 1 1 分组密码的基本原理 12 2 1 2 数据加密标准 DES 13 2 1 3 高级加密标准 AES 19 2 2 HASH 函数 23 2 2 1 Hash 函数的性质 23 2 2 2 基于分组密码的 Hash 函数 24 2 2 3 Hash 函数 MD5 26 2 2 4 SHA 1 散列算法 30 第 3 章 嵌入式设备身份验证系统的实现方案 33 3 1 系统架构 33 3 1 1 总体设计方案 33 3 1 2 协议帧及其说明 34 3 1 3 功能模块图及其说明 34 3 2 开发板介绍和串口通信函数介绍 38 3 2 1 开发板介绍 38 3 2 2 串口通信 API 介绍 40 3 3 核心代码及其流程 40 3 3 1 系统的注册流程和代码 40 3 3 2 数据包认证码生成流程 43 结 束 语 45 参考文献 46 致 谢 47 1 52 嵌入式设备身份认证系统嵌入式设备身份认证系统 摘摘 要要 在现实世界中 身份欺诈是种常见现象 因此常常需要证明个人的身份 同 样地 在数据通信过程中也存在身份的欺诈 通信和数据系统的安全性很大程度上取 决于能否验证设备或终端的真实身份 而这一功能通常都要通过密码学方法来完成 所以 本文首先介绍了密码学的基础知识和其发展历程 然后在此基础上 详细分析 了几个可用于系统设计的重要算法 包括DES SHA 1和MD5等算法 利用以上算法 的特点 本文提出了可用于身份认证系统实现的具体方案 利用该方案可实现嵌入式 设备通信过程中交互式的身份认证 从而保证嵌入式设备在通信过程中的安全性 关键词关键词 身份认证 密码学 嵌入式设备 The Authentication System of Embedded Device Abstract In the real world identity fraud is a common phenomenon therefore there s a frequecy need to prove the identity of individuals there is also identity fraud in data communication The security of communication and data system mainly depends on the identity verification of the devices or terminators And the verification is usually accomplished by methods of cryptography So the basic knowledge and development of cryptography are firstly discussed in the paper Secondly a number of important algorithms that could be used in the design of system is analyzed including DES SHA 1 and MD5 algorithm Baseing on these algorithms a program that can be applied to the authentication system of embedded device is presented in the article The program can used to relize the interaction authentication of embedded device so as to ensure the security of the communications of embedded device Keywords Authentication Cryptography Embedded Devices 3 52 第 1 章 绪论 1 1 研究背景 随着科技的飞速发展 安全性逐渐成为一个潜在的巨大问题 安全性是一个涉及 面很广泛的问题 其中也会涉及到是否构成犯罪行为的问题 在其最简单的形式中 它主要关心的是确保无关人员不能读取 更不能修改传送给其他接收者的信息 此时 它关心的对象是那些无权使用 但却试图获得服务的人 安全性也处理合法消息被截 获和重播的问题 以及发送者是否曾发送过该条消息的问题 大多数安全性问题的出现都是由于有恶意的人试图获得某种好处或损害某些人而 故意引起的 可以看出保证安全不仅仅是使它没有编程错误 它包括要防范那些聪明 的 通常也是狡猾的 专业的 并且在时间和金钱上是很充足 富有的人 同时 必 须清楚地认识到 能够制止偶然实施破坏行为的敌人的方法对那些惯于作案的老手来 说 收效甚微 安全性可以被粗略地分为 4 个相互交织的部分 保密 鉴别 反拒认以及完整性 控制 保密是保护信息不被未授权者访问 这是人们提到的安全性时最常想到的内容 鉴别主要指在揭示敏感信息或进行事务处理之前先确认对方的身份 反拒认主要与签 名有关 保密和完整性通过使用注册过的邮件和文件锁来实现 1 2 国内外研究状况 随着信息技术的发展与应用 信息安全的内涵在不断的延伸 从最初的信息保密 性发展到信息的完整性 可用性 可控性和不可否认性 进而又发展为 攻 攻击 防 防范 测 检测 控 控制 管 管理 评 评估 等多方面的基础理论和实施技术 信 息安全是一个综合 交叉学科领域 它要综合利用数学 物理 通信和计算机诸多学 科的长期知识积累和最新发展成果 进行自主创新研究 加强顶层设计 提出系统的 完整的 协同的解决方案 与其他学科相比 信息安全的研究更强调自主性和创新性 自主性可以避免 陷门 体现国家主权 而创新性可以抵抗各种攻击 适应技术发展 的需求 就理论研究而言 一些关键的基础理论需要保密 因为从基础理论研究到实际应 用的距离很短 现代信息系统中的信息安全其核心问题是密码理论及其应用 1 5 其基 础是可信信息系统的构作与评估 密码学从其发展 6 11 来看 可分为古典密码学与现代密码学 12 古典密码 以字 符为基本加密单元的密码 以及现代密码 以信息块为基本加密单元的密码 1 2 1 古典密码学 古典密码有着悠久的历史 在电报特别是无线电报发明以后 得到了深入研究 常用的有单表密码和多表密码 其思路都是改变字母表中字母的顺序 其中单表密码 在古代就已经得到了很长的发展 到了现代 密码学有了一个奇妙的发展历程 当然 密而不宣总是扮演主要角色 如下图 1 1 所示为一般的数据加密模型 图1 1一般数据加密模型 明文 X 用加密算法 E 和加密密钥 K 得到密文 Y Ek X 在传送过程中可能出现密 文截取者 到了收端 利用解密算法 D 和解密密钥 K 解出明文为 Dk Y Dk Ek X X 其中 截取者也可称为攻击者或入侵者 在这里 我们假定加密密钥和解密密钥 都是一样的 但实际上 它们可以是不一样的 即使不一样 二者之间也具有某种关联 性 密钥通常是由一个密钥源提供 当密钥需要向远地传送时 一定要通过另一个安 全信道 密码编码学是密码体制的设计学 而密码分析学则是在未知密钥的情况下 从密文推演出明文或密钥的技术 密码编码学与密码分析学合起来即为密码学 早在几千年前人类就已经有了思想和方法 但直到 1949 年 创始人香农 C E Shannon 发表著名文 Communication Theory of Secrecy Systems 论证了一般经典 加密方法得到的密文几乎都是可破的 密码学的研究曾面临着危机 但从 20 世纪 60 年代起 随着电子技术 计算技术的迅速发展以及结构代数 可计算性和计算复杂性 理论等学科的研究 密码学又进入了一个新的发展时期 在 20 世纪 70 年代后期 美 国的数据加密标准 DES Data Encryption Standard 和公开密钥密码体制 public key crypto system 的出现 成为近代密码学发展史上的两个重要里程碑 1 2 2 现代密码学 按现代密码学 13 14 的观点大致可被分为对称密码学和非对称密码学 1 对称钥匙密码 对称密码 15 学指的是传送方与接收方都拥有相同的钥匙 直到1976年这都还是唯 5 52 一的公开加密法 对称密码算法有时也叫传统密码算法 就是加密密钥能够从解密密 钥中推算出来 反过来也成立 设密钥为 K 则加解密过程为 加密 EK M C 1 1 解密 DK C M 1 2 在此算法中 加 解密双方所用的密钥都有保守秘密 由于计算速度快而广泛应 用于对大量数据如文件的加密过程中 如 RD4和 DES 对称密码体制从加密模式上可 分为序列密码和分组密码两大类 1 序列密码 序列密码一直作为军事和外交场合使用的主要密码技术之一 它的主要原理是通 过有限状态随机产生性能优良的伪随机序列 使用该序列加密信息流 得到密文序列 序列密码的优点是错误扩展小 速度快 利于同步 安全程度高 2 分组密码 分组密码学将明文分成固定长度的组 用同一密码和算法对每一块加密 输出也 是固定长度的密文 对称密码体制存在的最主要的问题是 由于双方都是使用相同的密钥 因此在发 送和接受之前必须完成密钥的分发 所以密钥的分发便成了该加密体系中最薄弱 也 是风险最大的环节 所使用的手段均很难安全地完成此项工作 这样 密钥更新的周 期加长 给他人破译密钥提供了机会 在史上破获他国情形不乎两种方式 一种是在 敌方更换 密码本 的过程中截获对方密码本 另一种是敌人密钥变动周期太长 被长 期跟踪 找出规律从而破解 在对称算法中 尽管由于密钥强度增强 跟踪找出规律 破解密钥的机会大大减少 但密钥分发的困难问题几乎无法解决 例如 设有 n 方参 加与通信 若 n 方都采用同一个对称密钥 一但密钥被破解 整个系统就崩溃 若采 用不同的对称密钥则需 n n 1 个密钥 密钥数与参与通信的人数的平方数成正比 可见 大系统的密钥的管理几乎成为不可能 3 利用对称密码体制实现数字签名 许多人提出了利用对称密钥加密算法进行数字签名的方法 认为非对称加密算法 的安全性不如那些 有保证的 对称密钥加密算法高 而且 大多数非对称加密算法的 运算量都是很大 Lamport 发明了一种签名方法 并且由 Diffie 和 Hellman 做了具体描述 所以有时 又称其为 Lamport Diffie 签名 这种签名方法的基础是利用一组签名 密钥的个数由报 文分组长度决定 设报文分组长度为 nbit 则需要2n 个签名密钥 设这2n 个签名密钥 为 1 1 2 2 n n 这些密钥由发方秘密保存 对签名的验证信息由2n 个密钥产生 并且要公开 它们的选择方法是 随机选择 2n 个数 1 U1 2 U2 n Un 利用签名密钥对这2n 个数进行一次加密运算 又得到 另一组2n 个数 1 V1 2 V2 n Vn 它与第一组数的关系是 i E 1 i Vi E 1 Ui i 1 2 3 n 1 3 同时将发方选取的 1 U1 2 U2 n Un和计算上得到的2n 个数 1 V1 2 V2 n Vn传到发端 发方的签名过程如下 检查待发报文分组 M 第一位 如果为0那么就取 1 如果 为1就取 1 然后再取 M 的第二位进行检查 如果为0那么就取 2 如果为1就取 2 如此继续下去 直到报文的 n 个 bit 全部检查完毕 最后形成的签名由 n 个密钥组成 例如 M 01101101001 那么对它的签名是 1 2 3 4 5 6 7 8 9 10 11 收方对这个签名进行验证时 首先检查 M0第一位 如果为0就认为签名中的第一 组信息为密钥 1 如果为1就认为签名中的第一组信息为 1 如此继续下去 收方就会 得到 n 个密钥 由于收方由发放的验证信息 i Vi i Ui i 1 2 n 所以收方就可以利 用得到的 n 个密钥检验验证信息 如果满足 i E i i 或 Vi E i Ui i 1 2 n 那么收方就 认为该报文是由确定的发方发送过来的 否则就认为发方身份不确定 取上式或下式 进行验证取决于 M 各位的值 如果为0 就验证上式 如果为1就验证下式 这种方法 的优点是安全性比较好 因为它是逐位进行签名的 只要有一位改动 收方得到的签 名就不对了 但是 应当看到 这种方法有其严重的缺点 1 签名太长 如果每个签名密钥的长度为 Mbit 那么对一个长度为 nbit 的报文进行 签名将得到一个 m nbit 长的签名 2 签名密钥及相应的验证信息只能用一次 因为重复使用相同的签名密钥是极不安 全的 2 非对称钥匙密码学 非对称钥匙密码学 相对于对称钥匙密码学 又称公钥密码学 最大的特点在于 加密与解密使用不同的钥匙 公开密钥算法也称非对称算法 加密密钥不同于解密密 钥 而且解密密钥不能根据加密密钥计算出来 加密密钥叫做公开密钥 简称公钥 解密密钥叫做私人密钥 简称私钥 公钥 K1 加密 EK1 M C 1 4 签名 DK2 M C 1 5 私钥 K2 解密 DK2 C M 1 6 验签 EK1 C M 7 52 1 7 在对称密码学中 加密和解密使用相同的钥匙 也许对不同的信息使用不同的钥 匙 但都面临钥匙管理的难题 由于每对通讯方都必须使用异于他组的钥匙 当网络 成员的数量增加时 钥匙数量成二次方增加 更尴尬的难题是 当安全的通道不存在 于双方时 如何建立一个共有的钥匙以利安全的通讯 如果有通道可以安全地建立钥 匙 何不使用现有的通道 这个鸡生蛋 蛋生鸡的矛盾是长年以来密码学无法在真实 世界应用的阻碍 除了加密外 公开钥匙密码学最显著地成就是实现了数字签名 数 字签名名符其实是普通签章的数字化 他们的特性都是某人可以轻易制造签章 但他 却难以仿冒 数字签名可以永久地与被签署信息结合 无法自信息上移除 数字签名 大致包含两个算法 一个是签署 使用私密钥处理信息或信息的杂凑而产生签章 另 一个是验证 使用公开钥匙验证签章的真实性 RSA 和 DSA 是两种最流行的数字签名 机制 数字签名是公开钥匙基础建设以及许多网络安全机制的基础 公钥密码体制有 两种基本的模型 一种是加密模型图1 2 一种是认证模型图1 3 以下是两种模型的示 意图 Alice 加密 Bob 解密 明 文 密文明 文 Bob 的私钥Bob 的公钥 图1 2加密模型 Alice 加密 Bob 解密 明 文 密文明 文 Bob 的私钥Bob 的公钥 图1 3 解密模型 1 公钥密码体制有如下的优点 1 可以支持众多的安全服务 如数据的保密性 完整性 源认证 不可抵赖性和数 字签名等 2 减化了密钥发布和管理的难度 密钥对可以由通信实体自己产生 然后将公钥进 行公开发布 而私钥妥善保留 这样私钥根本就没有在外界流通过 可以确保私钥的 安全 而公钥密码技术也不需要事先各方建立关系以交换密钥 只要取得了对方的公 钥既可以进行保密传输 这样公钥系统在解决密钥的保密性的同时 也解决了密钥分 发的问题 3 非常适合于分布式系统中的使用 因为它需要分发的密钥的数目与参与者的数目 一样 这样在参与者数目很大的情况下 公钥技术仍表现出良好的性能 2 公钥密码体制的缺点 1 与对称密码算法相比 非对称 即公钥 密码算法相对加解密速度比较慢 它们可 能要比同等强度的对称密码算法慢上10倍到100倍 当加密较短的消息时 这种速度上 的差异表现的并不十分明显 但若加密较长的消息 非对称密码的速度是无法忍受的 所以非对称算法不会应用在需要大规模加密的情况或用于加密实时消息 如对实时语 音信息加密 2 要想让非对称密钥算法取得与对称密钥算法相同的安全强度 就必须使用更长的 密钥 3 公钥加密提供安全服务 公钥加密可以提供众多的安全服务 如数据的保密性 完整性 消息源认证 身份 认证 抗抵赖服务 进行密钥发布及进行数字签名等 以下是这些服务的简介 1 消息保密性服务 显然 公钥密码系统可以用来加密消息 加密的强度是由所使用的特定算法和所 采用的密钥长度所决定的 通常 每个算法的健壮性和所使用的陷门单向函数的类型 直接相关 这一服务的前提是 使用接收者的公钥加密的消息 只有使用接收者的私 钥才能解密 由于接受者的公钥是公开的 因此任何人都可以用接收者的公钥解密消 息 然后发送给接收者 而只有接收者才知道自己的私钥 因此只有接收者自己才能 解密发送给他的密文 这便保证了消息的安全传递 即实现了消息的保密性 实现保 密性时使用的加密模型只能保证消息的保密性而不能同时认证发送者的身份 2 消息源认证 身份认证 服务 这个服务要求发送者使用自己的私钥进行消息加密 而接收者使用发送者的公钥 进行解密 因为私钥只有发送者自己知道 所以只要能用发送者的公钥解密 则便能 自动对发送者的身份进行认证 16 这种利用公钥进行身份认证的模型 但并不能同时 保证消息的保密性 3 消息完整性服务 使用可以获得的公钥进行加密可以实现数据传输的机密性 但不能同时保证消息 的完整性 因为 窃听者可以中途拦截密文 不让其发送到接收者 而把另外一个消 息用接收者的公钥加密 再发送给接收者 这时接收者会误以为被替换的消息是来自 真实的消息源的 这就破坏了消息的完整性 而用另一种方法 即用发送者的私钥加 9 52 密 接收者用发送者的公钥解密 这样虽然可以保证消息的完整性 但却无法同时保 证消息的机密性 要想同时保证消息的完整性 机密性和消息源认证可以使用数字签名和公钥的混 合方案 4 抗抵赖服务 根据公钥密码学的基本前提 私钥只是所有者具有 因此能够使用相关公钥进行解 密 那么所有者就无法抵赖了 然而 若私钥丢失或被破解 那么所有者就可以否认 对于强度较高的抗抵赖服务来说 私钥从来都不会泄露出去 就连所有者都无法知道 可以保护私钥的拥有方篡改硬件对于这一点非常重要 如智能卡等 5 密钥发布服务 公钥密码学可以用来在不安全的公网上建立密钥连接 简单的说 现在会话密钥 成了要加密的消息内容 会话密钥用对方的公钥来加密 接受方用自己的私钥解开消 息内容 然后双方都获得了相同的会话密钥 这时便建立了密钥连接 注意 这时 需要对发送者的身份进行严格的认证 以防止密钥欺骗 4 利用非对称密码体制进行数字签名 设 E 为加密算法 D 为解密算法 Ke 为加密密钥 Kd 为解密密钥 对于非加密 算法 Ke Kd 并且在已知 Ke 与 Kd 两者中的任意一个时 要想获得另一个从计算上是 不可能的 利用这种算法产生签名的过程如下 设 A 要向 B 发送一份报文 M 该报文由两部分组成 一部分称作报头 用 H 表示 它包括发送方的身份 接收方的身份 发送序号等 另一部分是要发送的报文数据信 息 用 T 表示 签名者必须将他的签名验证信息公开 在这里将加密密钥 Ke 公开 而 将解密密钥 Kd 保密 A 对 M 进行签名时 利用它的解密密钥 Kd 对 T 进行一次解密 运算 S Dkd T 1 8 将签名后的报文 Ms H S 1 9 发送给 B B 收到后做如下操作以验证签名 1 根据 H 中的信息识别出发送者的身份 2 在公开的签名信息薄中查出 A 用于签名验证的加密密钥 Ke 3 利用查到的 Ke 对 S 进行一次加密运算 T Eke S 4 检查 T 是否正确 如果 T 是正确的 那么 B 就可以断定确实 T 是由 A 发送过来的数据 因为只有 A 才知道 Kd 并且还保证在已知 Ke 的前提下任何人都无法从计算上得到 Kd 如果 T 不 正确 说明消息在传输途中被修改过 这样 这种方法就完全满足了对数字签名的两 个要求 1 2 3 总线介绍 1 CAN 总线 CAN 是控制网络 Control Area Network 的简称 最早由德国 BOSCH 公司推出 用于 汽车内部测量与执行部件之间的数据通信 其总线规范现已被 ISO 国际标准组织制订 为国际标准 得到了 Motorola Intel Philips Siemence NEC 等公司的支持 已广泛应 用在离散控制领域 CAN 支持多主点方式工作 网络上任何节点均可在任意时刻主动 向其它节点发送信息 支持点对点 一点对多点和全局广播方式接收 发送数据 它采 用总线仲裁技术 当出现几个节点同时在网络上传输信息时 优先级高的节点可继续传输 数据 而优先级低的节点则主动停止发送 从而避免了总线冲突 已有多家公司开发生产 了符合 CAN 协议的通信芯片 如 Intel 公司的82527 Motorola 公司的 MC68HC05X4 Philips 公司的82C250 等 另外 插在 PC 机上的 CAN 总线接口卡 具有接口简单 编 程方便 开发系统价格便宜等优点 2 RS 232总线 RS 232是一条串行外总线 其主要特点是 所需传输线比较少 最少只需要三条 线 一条发 一条收 一条地线 即实现全双工通信 传输距离远 用电平传送为15米 电流环传送可达千米 有多种可供选择的传送速率 例如 300 600 1200 2400 4800 9600 19200波特等 采用非归零码负逻辑工作 电平 3V 为逻辑1 而电平 3V 为逻辑0 具有较好的抗干扰性 3 RS 485总线 针对 RS 232 C 的不足 出现了一些新的接口标准 RS 485的电气标准就是其中 的一种 RS 485是美国电气工业联合会 EIA 制定的利用平衡双绞线作传输线的多点 通讯标准 它采用差分信号进行传输 最大传输距离可以达到1 2 km 最大可连接32个 驱动器和收发器 接收器最小灵敏度可达 200 mV 最大传输速率可达2 5 Mb s 由此 可见 RS 485协议正是针对远距离 高灵敏度 多点通讯制定的标准 RS 485是的 在 RS 422的基础上发展起来的 能实现一点对多点的通信 也能实现多点双向通信 但同一时刻只能有一个发送器 其余的为接受器 即一主多从的通信方式 目前市场 上可供选择的 RS 485总线芯片很多 其中包括可支持128个节点的 MAX1487和支持 400个节点的 SP485R 利用该芯片可直接组成简单的通信网络 RS 485收发器采用平 11 52 衡发送 差分接收的方式 即在发送端将 TTL 信号转换成差分信号输出 在接收端 接收器将差分转换成 TTL 信号 因此具有较高的共模抑制能力 同时接收器具有较高 的灵敏度 能检测低达200mV 的电压 数据传输可达1200m 如降低数据传输速率 则通信距离可更长 当通信速率为1200bps 时 理论距离可达15km 当传输距离超过 300m 时 在网络的二端需接入120 的匹配电阻 以减少因阻抗不匹配而引起的反射 吸收噪声 从而有效抑制噪声干扰 1 3 小结 本章主要简单地叙述了密码学的发展历史和状况 从古典密码学谈到现代密码学 的出现 对现代密码学我们又做了很多分类 如对称密码学和非对称密码学 对对称 密码学与非对称密码学在不同的领域的应用进行了一定的阐述 尤其是其在数字签名 方面的应用 分析通过二者来实现身份认证的可行性 本文是以对称密码学的思想作 为最基础 利用对称密码学具有相同的加密密钥和解密密钥来实现嵌入式设备与主机 之间的通信 只有拥有该密钥的用户才是合法用户 其次在本章中 还有比较性地介 绍了一下非对称密码学 在当今有很多的认证系统都是采用了非对称密码学的思想 对两者在不同的领域应用做了个简单的叙述 本章最后对本次设计牵涉到的几种总线 做了个简单的介绍 通过本章可以对本次设计所牵涉到的内容做个大致的了解 当然 很多内容还会在后面的章节中做更加详细的介绍 第 2 章 相关算法的描述 2 1 分组密码 2 1 1 分组密码的基本原理 设 n 是一个分组密码 17 的分组长度 k 是密钥 x x0 x1x2 xn 2xn 1 2 1 为明文 其中 xi GF 2 0 i n 1 y y0y1y2 ym 2ym 1 2 2 为相应的的密文 其中 yj GF 2 0 j m 1 则 y Ek x x Dk y 2 3 其中 Ek和 Dk分别表示在密钥 k 控制下的加密和解密变换 如果 n m 则分组密码 对明文加密后有数据扩展 如果 n m 则分组密码对明文加密后有数据压缩 如果 n m 则分组密码对明文加密后既无数据扩展也无数据压缩 我们通常考虑的分组密 码都是这种既无数据扩展也无数据压缩的分组密码 对于一个分组长度为 n 密钥长度为 t 的分组密码 我们通常假定每个明文分组和密 文分组都是 GF 2 n中的向量 GF 2 N GF 2 GF 2 总共 n 个 GF 2 相乘表示 GF 2 上的 n 维向量空间 1 置换 定义 设 S 是一个有限集合 是从 S 到 S 得一个映射 如果对任意 u v S 当 u v 时 u v 则称 为 S 上的一个置换 对于一个分组长度为 n 的分组密码 不同的密钥应该对应不同的加密和解密变换 给 定密钥 k 对于任意的 u v GF 2 n 如果 u v 则一定有 Ek u Ek v 2 4 这是因为如果 Ek u Ek v 则在解密时将难以准确地恢复明文 因此 对于给定 的密钥 k 加密变换 Ek 为 GF 2 n上的一个置换 解密变换 Dk 为 Ek 的逆置换 设计 一个分组长度为 n 的分组密码就是构造 GF 2 n上的置换 不同的密钥应该对应不同的 置换 如果密钥长度为 t 则密钥量为 2t 因为 GF 2 n上共有 2n 个不同的置换 所以必须 有 2t 2n 为便于密钥管理 通常 t 不能太大 当然 密钥长度 t 也不能太小 难以抵 抗对密钥的穷举搜索攻击 在设计分组密码时 另外一要求是加密变换和解密变换都能够容易地计算 并且 13 52 便于软件和硬件实现 2 扩散与混淆 扩散和混淆是 C E Shannon 提出的设计密码体制的两种基本方法 其目的是为了抵 抗对手对密码体制的统计分析 在分组密码的设计中 充分利用扩散和混淆 可以有 效地抵抗对手从密文的统计特性推测明文和密钥 扩散和混淆是现代分组密码的设计 基础 所谓扩散就是让明文中的每一位影响密文中的许多位 或者说让密文中的每一位 受明文的许多位的影响 这样可以隐蔽明文的统计特性 当然 理想的情况是让明文 中的每一位影响密文中的所有位 或者让密文中的每一位受明文中的所有位的影响 所谓混淆就是将密文与密钥之间的统计关系变得尽可能复杂 使得对手即使获取 了关于密文的一些统计特性 也无法推测密钥 使得复杂的非线性代替变换可以达到 比较好的混淆效果 而简单的线性代替变换得到的混淆效果则不理想 2 1 2 数据加密标准 DES 1 DES 概述 数据加密算法 Data Encryption Algorithm DEA 的数据加密标准 Data Encryption Standard DES 是规范的描述 它出自 IBM 的研究工作 并在 1997 年被美国政府正式 采纳 它很可能是使用最广泛的密钥系统 特别是在保护金融数据的安全中 最初开 发的 DES 是嵌入硬件中的 通常 自动取款机 Automated Teller Machine ATM 都使 用 DES DES 使用一个 56 位的密钥以及附加的 8 位奇偶校验位 产生最大 64 位的分 组大小 这是一个迭代的分组密码 使用称为 Feistel 的技术 其中将加密的文本块分 成两半 使用子密钥对其中一半应用循环功能 然后将输出与另一半进行 异或 运算 接着交换这两半 这一过程会继续下去 但最后一个循环不交换 DES 使用 16 个循环 攻击 DES 的主要形式被称为蛮力的或彻底密钥搜索 即重复尝试各种密钥直到有 一个符合为止 如果 DES 使用 56 位的密钥 则可能的密钥数量是 256个 随着计算 机系统能力的不断发展 DES 的安全性比它刚出现时会弱得多 然而从非关键性质的 实际出发 仍可以认为它是足够的 不过 DES 现在仅用于旧系统的鉴定 而更多地 选择新的加密标准 高级加密标准 Advanced Encryption Standard AES DES 的常见变体是三重 DES 使用 168 位的密钥对资料进行三次加密的一种机制 它通常 但非始终 提供极其强大的安全性 如果三个 56 位的子元素都相同 则三重 DES 向后兼容 DES DES 处理的明文分组长度为 64 位 密文分组长度也是 64 位 使用密钥长度为 56 位 DES 解密过程和加密相似 解密时使用与加密相同的算法 不过子密钥的使用次 序要反过来 DES 的整个体制是公开 系统安全性完全靠密钥的保密 2 DES 的一般设计准则 1 随机性 输出与输入间是无规律 2 雪崩效应 改变输入中的 1 位 平均要导致一半的输出位被改变 3 完全性 每个输出位都是所有输入位的一个复杂函数 4 非线性性 加密函数对任何密钥值都是非仿射的 即非线性的 5 相关免疫性 输出是统计上独立于任何输入位的子集 不会与输入位的任何子集相 关 DES 中重复交替使用代替运算 S 和换位运算 P 两种变换 以达到混乱和扩散目的 3 DES 加密原理 DES 算法的加密过程经过了两个阶段 如图 2 1 所示 首先 64 位的明文在一个 初始置换 IP 后 比特重排产生了经过置换的输入 明文组被分成右半部分和左半部分 每部分 32 位 以 L0和 R0表示 接下来的阶段是由对同一个函数进行 16 次循环组成的 16 轮迭代称为乘积变换或函数 F 这个函数本身既包含有代替函数 将数据和密钥结 合起来 最后 1 轮的输出由 64 位组成 其左边和右边两个部分经过交换后就得到预输 出 最后阶段 预输出通过一个逆初始置换 IP 1算法就生成了 64 位的密文结果 64 位明文 初始置换 IP 乘积变换 逆初始置换 IP 1 64 位密文 图 2 1 DES 加密处理略图 DES 的详细加密计算如下图 2 2 所示 1 初始置换 IP 与逆初始置换 IP 1 初始置换表和逆初始置换表分别如图 2 3 和图 2 4 所示 表中的数字代表初始置换 15 52 或逆初始置换时 64 位输入分组的位序号 表中的位置代表置换后输出的位顺序 很容易看出 这两个置换是彼此反向的 如经过 IP 置换后 输入消息的第 1 位被置换 到第 40 位的位置输出 再经过逆初始置换后 第 40 位又回到了第 1 位的位置 K1 K2 Kn 输入 初始置换 IP L0 R0 L1 R0 R1 L0 F R0 K1 L2 R1 R2 L0 F R1 K2 L15 R14 R15 L14 F R14 K15 R16 L15 F R15 K16 L16 R15 逆初始置换 IP 1 输出 F F F F 图 2 2 DES 的加密计算流程 初始置换 IP 表中的位序号表现出这样的特征 整个 64 位按 8 行 8 列排列 最右边 一列按 2 4 6 8 和 1 3 5 7 的次序排列 往左边各列的位序号依次为紧邻其右 边一列各位序号加 8 逆初始置换 IP 1 则是初始置换的逆过程 相应地 表中位序号表现出这样的特征 整个 64 位依然按 8 行 8 列排列 左边第二列按 8 7 6 5 4 3 2 1 的次序排列 往右边隔一列的位序号依次为当前列各位序号加 8 认为最右边一列的隔列位最左边一 列 输入 64 位输入 64 位 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 40 32 24 16 8 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 输出 64 位 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 输出 64 位 图 2 3 初始置换 IP 图 2 4 逆初始置换 IP 1 2 每个循环的详细过程 图 2 5 所示给出了一个循环的内部结构 每个 64 位的中间结果的左 右两个部分 被当成独立的 32 位数据处理 每轮变换的逻辑关系为 Li Ri 1 Ri Li 1 F Ri 1 K i 2 5 17 52 Li 1 32 位 R i 1 32 位 R i 32 位 轮 密 钥 产 生 器 F 变 换 扩展变换 E 选择压缩变换 S 盒代替 置换运算 P Li 32 位 32 位 48 位 48 位 图 2 5 DES 算法的一轮迭代处理过程 输入 32 位 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 输出 48 位 输入 32 位 来自 S 盒 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 输出 32 位 图 2 6 扩展变换 E 图 2 7 P 变换 在这个循环中使用的轮密钥 K i的长度是 48 位 输入的 R i 1是 32 位 先被扩展到 48 位如图 2 6 由此可知扩展变换 E 将 32 位扩展为 48 位输出 扩展后得到的 48 位结 果再与各 K i进行异或 这样得到的 48 位结果再经过一个代替函数 S 产生 32 位的输出 19 52 最后进行 P 图 2 7 变换 E 48 位密钥 Ki 48 位 S1S2S3S4S5S6S7S8 P 32 位 R i 1 32 位 图 2 8 F Ri 1 Ki 函数的计算 3 密钥的产生 28bit28bit C0D0 LS1LS1 C1D1 56bit LS2 LS2 PC 2 C2D2 Pc 2 LS16LS16 C16D16 PC 16 K1 48bit K2 48bit K16 48bit PC 1 图 2 9 DES 16 个子密钥生成过程 如上图 2 9 所示子密钥 Ki 的产生 其中 PC 1 表示置换选择 1 PC 2 表示置换选 择 2 LSn 表示左移 n 位 在 DES 的 16 轮迭代中 使用了不同的子密钥 但这 16 个 子密钥由同一个原始密钥 56bit 移位产生而来 并没有使用独立子密钥 据分析 使用 独立子密钥将会降低 DES 对差分攻击的抵抗力 子密钥产生的过程为 将原始密钥 64bit 其中包括 8 个校验位 经过初始变换 得到有效密钥 56bit 将其分为两个 28bit 数据 然后进行循环左移位得到新的 56bit 密钥 再经过一个压缩变换得到每一轮的 48bit 子密钥 用来和上面的 48 位数据进行异或运算 需要注意的是 产生子密钥过 程中每一轮对两个 28bit 数据的循环左移位位数是经过精心计算的 不能随意更改 如 果改变移位的位数将会降低 DES 对相关密钥密码分析的抵抗力 4 DES 算法的安全强度 对 DES 的分析主要由三种方法 1 蛮力攻击 255次尝试 2 差分密码分析法 247尝试 3 线性密码分析法 243次尝试 对 DES 脆弱性的争论主要集中在以下三个方面 1 DES 的半公开性 DES 的内部结构即 S 盒的设计标准是保密的 至今未公布 这样 用户无法确信 DES 的内部结构不存在任何隐藏的弱点和陷阱 2 密钥太短 IBM 原来的 Lucifer 算法的密钥长度是 128 位 而提交作为标准的只有 56 位 批评者担心这个密钥长度不足以抵御穷举搜索攻击 不太可能提供足够的安全 性 1998 年前只有 DES 破译机的理论设计 1998 年后出现实用化的 DES 破译机 3 软件实现太慢 1993 年前只有硬件实现得到授权 1993 年后软件 固件和硬件得到 同等对待 2 1 3 高级加密标准 AES 1 AES 加密算法原理 随着对称密码的发展 DES 数据加密标准算法由于密钥长度较小 56 位 已经不 适应当今分布式开放网络对数据加密安全性的要求 因此1997 年 NIST 公开征集 新的数据加密标准 即 AES 经过三轮的筛选 比利时 Joan Daeman 和 Vincent Rijmen 提交的 Rijndael 算法被提议为 AES 的最终算法 此算 法将成为美国新的数 据加密标准而被广泛应用在各个领域中 AES 作为新一代的数据加密标准汇聚了 强安全性 高性能 高效率 易用和灵活等优点 AES 设计有三个密钥长度 128 192 256 位 相对而言 AES 的 128 密钥比 DES 的 56 密钥强 1021 倍 AES 算法主要包括三个方面 轮变化 圈数和密钥扩展 本文以128 为例 介绍算法 的基本原理 结合 AVR 汇编语言 实现高级数据加密算法AES 其目的是确定 21 52 一个非保密 公开披露的 全球免费使用的分组密码算法 用于保护21 世纪政府 敏感子信息 并希望取代渐进没落的原有数据加密标准DES 算法 AES 算法是一个数据块长度和密钥长度都可变的迭代分组加密算法 数据块长 度和密钥长度可分别为 128 192 256 位 在加密之前 对数据块做预处理 首先 把数据块写成字的形式 每个字包含4 个字节 每个字节包含 8bit 信息 其次 把字记为列的形式 这样数据块就可以记为以下的形式表 2 1 表 2 1 数据块的处理 a0 0a0 1a0 2a0 3a0 4a0 5 a1 0a1 1a1 2a1 3a1 4a1 5 a2 0a2 1a2 2a2 3a2 4a2 5 a3 0a3 1a3 2a3 3a3 4a3 5 其中 每列表示一个字 aj a0 j a1 j a2 j a3 j 每个 ai j表示一个 8bit 的字节 即 aj GF 28 x x4 1 ai j GF 28 2 6 如果用 Nb 表示一个数据块中字 的个数 那么 Nb 4 6 8 类似地 用 Nk 表示密钥中字的个数 那么 Nk 4 6 8 例如 Nk 6 的密钥可记为如下表 2 2 形式 表 2 2 Nk 6 的密钥表示 k0 0 k0 1 k0 2 k0 3 k0 4k0 5 k1 0 k1 1 k1 2 k1 3 k1 4k1 5 k2 0 k2 1 k2 2 k2 3 k2 4k2 5 k3 0 k3 1 k3 2 k3 3 k3 4k3 5 AES 是分组密钥 算法输入 128 位数据 密钥长度也是 128 位 用 Nr 表示 对一个数据分组加密的轮数 每一轮都需要一个与输入分组具有相同长度的扩展密 钥 Expandedkey i 的参与 由于外部输入的加密密钥K 长度有限 所以在算法中要 用一个密钥扩展程序 Keyexpansion 把外部密钥 K 扩展成更长的比特串 以生成各 轮的加密和解密密钥 对不同的分组长度 其对应的轮变化次数是不同的 其关系如下表 2 3 所示 表 2 3 密钥与轮数的关系 标 准 密钥长度 N k 个字 分组大小 N b个字 轮数 N r AES 128 4 4 10 AES 192 6 4 12 AES 256 8 4 14 AES 加密和解密过程如下图 2 10 所示 明文块经过白化技术处理后 进入轮 函数 而轮函数又由字节代换 行移变换 列变换和密钥4 个变换组成 AES 的 加密与解密流程如图 2 10 所示 128 位数据分组 与扩展密钥 异或 运算 S 盒变换 行变换 列变换 与扩展密钥异或 S 盒变换 与扩展密钥异或运算 行变换 128 位加密数据 128 位加密数据分组 与扩展密钥 异或 运算 反行变换 反 S 盒变换 反 S 变换 反行变换 反列变换 与扩展密钥异或 128 位解密数据 图 2 10 AES 的加密与解密流程 1 圈变化 AES 每一个圈变换由以下三个层组成 非线性层 进行字节变换 Subbyte 线行混合层 进行 ShiftRow 和列变换 MixColumn 运算 密钥加层 进行 AddRoundKey 运算 23 52 1 Subbyte 变换是作用在状态中每个字节上的一种非线性字节转换 可以通过计算 出来的 S 盒进行映射 这个变换是 可逆的 它定义为 2 7 0 1 1 0 0 0 1 1 11111000 01111100 00111110 00011111 10001111 11000111 11100011 11110001 1 jiji aaSubByte 其中 a 1i j是 ai j在 GF 28 中的乘法逆 2 行移变换 ShiftRow 在此变换的作用下 数据块的第 0 行保持不变 第 1 行循环左移 C1位 第 2 行循环左移 C2位 第 3 行循环左移 C3位 其中移位值 C1 C2和 C3与加密块长 Nb 有关 它将状态中的行按照不同的偏移量进行循环移位 而这个偏移量也是根据 Nb 的不同而选择的 如表 2 4 图 2 4 偏移量与 Nb 的关系 Nb C1 C2C3 4 1 2 3 6 1 2 3 8 1 2 4 3 在 MixColumn 变换中 把状态中的每一列看作 GF 28 上的多项式 a x 与固定多 项式 c x 相乘的结果 b x c x a x 的系数这样计算 运算不是普通的乘法运算 而是特殊的运算 即 b x c x a x mod x 4 1 2 8 对于这个运算 b0 02 a0 03 a1 a2 a3 令 xtime a0 02 a0 其中 符号 表示模一个八次不可约多项式的同余乘法 2 9 3 2 1 0 3 2 1 0 02010103 03020101 01030201 01010302 a a a a b b b b 对于逆变化 其矩阵 C 要改变成相应的 D 即 b x d x a x 4 密钥加层运算 addround 是将圈密钥状态中的对应字节按位 异或 5 根据线性变化的性质 解密运算是加密变化的逆变化 2 轮变化 3 密钥扩展 AES 算法利用外部输入密钥 K 密钥串的字数为 Nk 通过密钥的扩展程序得到 共计 4 Nr 1 字的扩展密钥 它涉及如下三个模块 1 位置变换 rotword 把一个 4 字节的序列 A B C D 变化成 B C D A 2 S 盒变换