第2章 数 据 加 密

1 第2章数据加密 2 1数据加密概述2 2对称密码体制2 3非对称密码体制2 4密钥的管理2 5软件与硬件加密技术2 6信息伪装与数字水印 2 密码学的发展历史 第1阶段 1949年以前 密码技术表现为一种艺术 第2阶段 从1949年到1975年 密码学成为了一门学科 标志 1949年Shannon发表的 保密系统的信息理论 一文 第3阶段 1976年至今 开创了公钥密码学的新纪元 标志 1976年Diffie和Hellman发表了 密码学新方向 一文 密码学 Cryptology 一字源于希腊文 krypto s 及 logos 两字 直译即为 隐藏 及 讯息 之意 3 2 1数字加密概述 一个加密系统采用的基本工作方式称为密码体制 密码体制的基本要素是密码算法和密钥 其中密码算法是一些公式 法则或程序 而密钥是密码算法中的可变参数 密码算法分为加密和解密算法 前者是将明文变换成密文 后者是将密文变换成明文 密钥相应地也分为加密密钥和解密密钥 4 加密和解密 加密 解密 明文M 密文C 原始明文M E M C D C M D E M M 5 组成部分 X 明文 plain text 作为加密输入的原始信息 Y 密文 cipher text 对明文变换的结果 E 加密 encrypt 是一组含有参数的变换 D 解密 decrypt 加密的逆变换 Z 密钥 key 是参与加密解密变换的参数 一密码系统由算法以及所有可能的明文 密文和密钥 分别称为明文空间 密文空间和密钥空间 组成 6 加密和解密 1 Alice要将明文 在不安全信道上发给Bob 设X x1x2 xn 其中xi P Alice用加密算法ek作yi ek xi 1 i n结果的密文是Y y1y2 yn 在信道上发送 Bob收到后解密 xi dk yi 得到明文X x1x2 xn 2 加密函数ek必须是单射函数 就是一对一的函数 3 好的密钥算法是唯密钥而保密的 4 若Alice和Bob在一次通信中使用相同的密钥 那么这个加密体制为对称的 否则称为非对称的 7 密码体制的分类 几种不同的分类标准按操作方式进行分类 操作方式 是明文变换成密文的方法 替代操作 置换操作 混合操作 按照使用密钥的数量进行分类对称密钥 单密钥 公开密钥 双密钥 按照对明文的处理方法进行分类流密码 分组密码 8 Kerckhoffs假设 AugusteKerckhoff 1883 假定 密码分析者知道对方所使用的密码系统 包括明文的统计特性 加密体制 操作方式 处理方法和加 解密算法 密钥空间及其统计特性 不知道密钥 在设计一个密码系统时 目标是在Kerckhoffs假设的前提下实现安全 9 密码系统 一个好的密码系统应满足 系统理论上安全 或计算上安全 系统的保密性是依赖于密钥的 而不是依赖于对加密体制或算法的保密 否则称为 含糊安全性 企图使算法保密的做法 加密和解密算法适用于密钥空间中的所有元素 系统既易于实现又便于使用 10 加密的功能 保密性 基本功能 使非授权者无法知道消息的内容 鉴别 消息的接收者应该能够确认消息的来源 完整性 消息的接收者应该能够验证消息在传输过程中没有被改变 不可否认性 发送方不能否认已发送的消息 11 2 1 1保密通信模型首先来看一个保密通信系统的基本模型 如图2 1所示 A向B发送一报文 为了不被E窃听 A对报文进行加密 然后在通信信道上进行传输 B收到报文后进行解密 得到原来的报文 12 图2 1保密通信系统的模型 13 2 1 2经典加密方法1 换位加密法 Transposition 1 铁轨法 RailroadMethod 铁轨法是换位算法最基本的形式 首先 它要求明文的长度必须是4的倍数 不符合要求则在明文最后加上一些字母以符合加密的条件 例如 明文 STRIKEWHILETHEIRONISHOT 就不满足条件 空白不计 故在尾端加上字母 使明文的长度变成4的倍数 接着将明文以从上到下的顺序逐列写出 表示如下 SRKWIEHIOIHTTIEHLTERNSOE 14 依序由左而右再由上而下地写出字母即为密文 表示如下 SRKWIEHIOIHTTITIEHLTERNSOE为方便起见 将密文每4个字母一组 其间用空格隔开 SRKWIEHIOIHTTIRHLYRTNSOE 15 这就是为什么要使密文长度为4的倍数的原因了 接收方收到此密文后 因为知道加密的顺序 因此 接收方可将密文以一直线从中分为两个部分 如下所示 SRKWIEHIOIHT TIRHLYRTNSOE然后左右两半依序轮流读出字母便可以还原成原来的明文了 当然 在写明文时也可以写成三列或四列等 写法不同 则解法也相应不同 16 2 路游法路游法可以说是一种铁轨法的推广 同样 此法也必须将明文的长度调整为4的倍数 之后将调整过的明文依由左而右由上而下的顺序 此顺序称之为排列顺序 填入方格矩阵中 依前例 可以得到如下矩阵 17 有了此矩阵后 便可以依照某一事先规定的路径 称为游走路径 来游走矩阵并输出所经过的字母 此即为密文 如果以如图2 2所示的游走路径来走 则可以得到如下的密文 ETNETOEKILROHIIRTHESIHWS 18 图2 2游走路径 19 3 密钥法密钥法最大的好处是就是将加密者和解密者双方所持有的加 解密信息具体化 密钥法大致来说与路游法相似 首先也是将明文填入一个矩阵 见路游法中的矩阵 接着 任意挑选一个密钥 如以 PREDIC 这个英文单字为加 解密双方所协议的共同密钥 然后 将密钥写于矩阵上方 如下所示 20 21 接着依照加密密钥字母的顺序分别依序读出其相对应的列便可得到密文 即先读出字母C对应的列 再依次读出字母DEIPR对应的列 得到密文如下 ETNEILRORIIHKEOTSWHIHTES 22 2 替换加密法 Substitution 替换加密法与此思路完全相反 对于明文的每一个字母并不去改变它的位置 只是将它以别的字母或符号取代 23 24 1 旋转替换法假设有一个由两个同心圆所组成的密码转盘 如图2 3所示 25 图2 3密码转盘图 图2 4旋转后的密码转盘 26 2 LewisCarroll sVigenere代换法 一种以移位代换为基础的周期代换密码 为1858年法国密码学家维吉尼亚提出 构成明文 每个字符惟一对应一个0 25间的数字 密钥 一个字符串 其中每个字符同明文一样对应一个数字 代表位移值 如a表示位移0 b表示位移1 c表示位移2 加密过程 将明文数字串依据密钥长度分段 并逐一与密钥数字串相加 模26 得到密文数字串 最后 将密文数字串转换为字母串 27 例如 明文为System 密钥为dog 加密过程如下 明文 System密钥 dogdog密文 Vmgwrs在这个例子中 每三个字母中的第一 第二 第三个字母分别移动 mod26 3个 14个和6个位置 28 首先构造一个维吉尼亚方阵 它的基本阵列是26行26列的方阵 方阵的第一行是按正常顺序排列的字母表 第二行是第一行左移循环1位得到的 依此类推 得到其余各行 然后在基本方阵的最上方附加一行 最左侧附加一列 分别依序写上a到z26个字母 表的第一行与与附加列上的的字母a相对应 表的第二行与附加列上的字母b相对应 最后一行与附加列上的字母z相对应 如果把上面的附加行看作是明文序列 则下面的26行就分别构成了左移0位 1位 2位 25位的26个单表代换加同余密码的密文序列 加密时 按照密钥字的指示 决定采用哪一个单表 29 30 维吉尼亚密码密钥字encryptionencryptione明文 publickeydistribution密文 thdcgrdmmqmfvrgqnbwbr 由于密钥字比明文短 所以要重复书写密钥字 以得与明文等长的密钥序列 31 2 1 3现代密码体制1 对称密码体制和非对称密码体制对称密码体制又称为秘密密钥密码体制 或单密钥密码体制 隐蔽密钥密码体制 即加密密钥和解密密钥相同或一个可由另一个导出 非对称密码体制又称为公开密钥密码体制 即加密密钥公开 解密密钥不公开 从一个推导出另一个是不可行的 32 2 分组密码体制和序列密码体制这是根据密码算法对明文信息的加密方式进行分类的方法 如果密文仅与给定的密码算法和密钥有关 与被处理的明文数据段在整个明文 或密文 中所处的位置无关 则称为分组密码体制 分组密码体制就是将明文分成固定长度的组 如64bit一组 用同一密钥和算法对每一组加密 输出也是固定长度的密文 如果密文不仅与给定的密码算法和密钥有关 同时也是被处理的明文数据段在整个明文 或密文 中所处的位置的函数 则称为序列密码体制 33 3 确定型密码体制和概率密码体制如果一个加密过程可以描述为 当明文和密钥确定后 密文的形式也就惟一地确定 则称为确定型密码体制 前面提到的加密方法中 多数属于这一类 如果一个加密过程可以描述为 当明文和密钥确定后 密文的形式仍是不确定的 最后产生出来的密文通过客观随机因素从一个密文集合中选出 则称为概率密码体制 4 单向函数密码体制和双向变换密码体制 34 2 2对称密码体制 2 2 1美国数据加密标准 DES 美国数据加密标准 DataEncryptionStandard DES 是在20世纪70年代中期由美国IBM公司的一个密码算法发展而来的 1977年美国国家标准局公布DES密码算法作为美国数据加密标准 直到今日 尽管DES已经经历了30多个年头 但在已知的公开文献中 还是无法完全地 彻底地把DES给破解掉 明文和密文的长度均为64位 密钥长度为56位 35 DES的产生背景 美国国家标准局 NBS 1973年公开征求计算机加密算法标准 要求如下 该算法必须提供较高的安全性 该算法必须完全确定并且易于理解 该算法的安全性不应依赖于算法本身 而是应该依赖于密钥 该算法必须对所有的用户有效 该算法必须适用于各种应用 该算法必须能够通过价格合理的电子器件得以实现 该算法必须能够有效使用 该算法必须能够得以验证 该算法必须能够得以出口 36 DES的生命期 NBS最终采纳了IBM的LUCIFER方案 于1975年公开发表 1977年正式颁布为数据加密标准 DES DataEncryptionStandard 1979年 美国银行协会批准使用DES 1980年 DES成为美国标准化协会 ANSI 标准 1984年 ISO开始在DES基础上制定数据加密的国际标准 DES的发展 如衍生出可抗差分分析攻击的变形DES以及密钥长度为128比特的三重DES等 现已经确定了选用Rijndael算法作为高级加密算法AES 37 DES的抗攻击能力 38 上表中攻击者配有如下计算机资源的攻击能力 39 DES算法描述 算法设计中采用的基本变换和操作 置换 P 重新排列输入的比特位置 交换 SW 将输入的左右两部分的比特进行互换 循环移位将输入中的比特进行循环移位 作为输出 一个复杂变换 fK 通常是一个多阶段的乘积变换 与密钥Key相关 必须是非线性变换 实现对密码分析的扰乱 是密码设计安全性的关键 40 DES的加密过程 41 DES的加密过程 利用传统的换位和置换加密 假定信息空间由 0 1 组成的字符串 信息被分成64比特的块 密钥是56比特 经过DES加密的密文也是64比特的块 明文 m m1m2 m64mi 0 1 i 1 2 64 密钥 k k1k2 k64ki 0 1 i 1 2 64 其中k8 k16 k64是奇偶校验位 起作用的仅为56位 加密算法 Ek m IP 1 T16 T15 T1 IP m 其中IP为初始置换 IP 1是IP的逆 Ti i 1 2 16 是一系列的变换 解密算法 Ek 1 c IP 1 T1 T2 T16 IP c 42 DES的加密过程 第一步 初始置换IP 对于给定的明文m 通过初始置换IP获得 并将分为两部分 前面32位记为 后面32位记为 即 43 初始变换IP 初始变换IP 44 IP中各列元素位置号数相差为8 相当于将原明文各字节按列写出 将阵中元素按行读得的结果 19172533414957210182634425058311192735435159412202836445260513212937455361614223038465462715233139475563816243240485664输入64个二进制位明码文数据区组m m1m2 m64按初始换位表IP进行换位 得到m58m50 m7记成L0 R0左右两部分 45 DES的加密过程 第二步 乘积变换 16轮 在每一轮中依据下列方法计算 16轮中的计算方法相同 其中 为第i轮使用的子密钥 各均为的一个置换选择 所有构成密钥方案 函数中的变量为32位字符串 为48位字符串 函数输出的结果为32位字符串 46 DES的加密过程 第二步各轮中的加密过程 47 1 加密函数f Ri 1 Ki Ri 1 32位 48位结果 48位Ki 选择函数组 S1 S8 32位结果 Ri 1 Ki 置换运算P 32位 48 乘积变换中的一次迭代 49 32位 置换运算P 32位加密函数输出 32位 Ri 右32位 Ri 1 Li 1 模2加 Li 左32位 50 扩展置换E Ri 1 32位 3212345456789891011121312131415161716171819202120212223242524252627282928293031321 选择运算E 选择运算E的结果 48位 51 使用密钥 在第i次迭代中 用48位二进制的密钥 由56位密钥生成 下边会介绍 K i k1 i k2 i k48 i 与E R i 1 按位相加 逻辑异或 输出仍是48位 共8行 每行6位 B1 B1 1 B1 2 B1 3 B1 4 B1 5 B1 6 B2 B2 1 B2 6 B8 B8 1 B8 6 作为8个Si选择函数的输入 明文与密钥模2加 52 S1 S2 S8选择函数 其功能是把6bit数据变为4bit数据 Si i 1 2 8 的功能表 S盒是DES的最敏感部分 其原理至今未公开 人们担心S盒隐藏陷门 使得只有他们才可以破译算法 但研究中并没有找到弱点 美国国家安全局透露了S盒的几条设计准则 所有的S盒都不是它输入的线性仿射函数 就是没有一个线性方程能将四个输出比特表示成六个比特输入的函数 改变S盒的1位输入 输出至少改变2位 这意味着S盒是经过精心设计的 它最大程度上增大了扩散量 S盒的任意一位输出保持不变时 0和1个数之差极小 即如果保持一位不变而改变其它五位 那么其输出0和1的个数不应相差太多 53 将以上第j个 1 j 6 二进制的块 记为Bj bj1bj2bj3bj4bj5bj6 输入第j个选择函数Sj 各选择函数Sj的功能是把6位数变换成4位数 做法是以bj1bj6为行号 bj2bj3bj4bj5为列号 查找Sj 行列交叉处即是要输出的4位数 在此以S1为例说明其功能 我们可以看到 在S1中 共有4行数据 命名为0 1 2 3行 每行有16列 命名为0 1 2 3 14 15列 现设输入为 B1 101100令 列 0110行 10坐标为 2 6 然后在S1表中查得对应的数为2 以4位二进制表示为0010 此即选择函数S1的输出 54 使用选择函数S的例子 012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613 S1 101100 102 0010 输入6位 输出4位 55 置换P 单纯换位表 8个选择函数的输出 32位 1672021291228171152326518311028241432273919133062211425 置换P 加密函数的结果X 32位 56 迭代 把L i 1 与X i 按位相加 形成R i 且令R i 为L i 即得到经第i次迭代加密后的输出L i R i 其中L i R i 1 R i L i 1 f R i 1 K i i 0 1 2 15 57 2 密钥ki的生成 58 置换选择1 密钥计算的目的在于产生加密和解密时所需要的16个子密钥 记作K i 初始密钥Key值为64位 但DES算法规定 其中第8 16 64位是奇偶校验位 不参与DES运算 故Key实际可用位数便只有56位 即 经过子密钥换位表PC 1的变换后 Key的位数由64位变成了56位 此56位分为C0 D0两部分 各28位 59 5749413325179158504234261810259514335271911360524436 6355473931331576254463830221466153453729211352820124 密钥 64位 C0 28位 D0 28位 密钥置换选择1 不考虑各字节第8位 60 循环移位 循环移位规则 轮数 12345678910111213141516位数 1122222212222221 61 置换选择2 56位分为C0 D0两部分 然后分别进行第1次循环左移 得到C1 D1 将C1 28位 D1 28位 合并得到56位 再经过子密钥换位表PC 2 便得到了密钥K1 48位 子密钥换位表PC 2给出了选择及选择后的次序 可以看出去掉了第9 18 22 25 35 38 43 54位 62 Ci 28位 Di 28位 1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932 Ki 48位 去掉第9 18 22 25 35 38 43 54位 56位变成48位 密钥置换2 63 DES的加密过程 第三步 初始置换的逆置换 应用初始置换的逆置换对进行置换 得到密文c 即 在最后一轮计算之后 将 而非左右部分交换后的结果 作为的输入 以便DES能够同时被用于加密和解密 64 DES的抗攻击能力DES用软件进行解码需要用很长时间 而用硬件解码速度非常快 但幸运的是当时大多数黑客并没有足够的设备制造出这种硬件设备 在1977年 人们估计要耗资两千万美元才能建成一个专门计算机用于DES的解密 而且需要12个小时的破解才能得到结果 所以 当时DES被认为是一种十分强壮的加密方法 65 1997年开始 RSA公司发起了一个称作 向DES挑战 的竞技赛 1997年1月 用了96天时间 成功地破解了用DES加密的一段信息 一年之后 在第二届赛事上 这一记录41天 1998年7月 第2 2届DES挑战赛 DESChallengeII 2 把破解DES的时间缩短到了只需56个小时 第三届DES挑战赛 DESChallengeIII 把破解DES的时间缩短到了只需22 5小时 美国国家安全局NSA每隔年对该算法进行评估 1994年 决定1998年12月之后不再使用DES 66 三重DES解决其密钥长度问题的方法 即采用三重DES 这种方法用两个密钥对明文进行三次加密 假设两个密钥是K1和K2 其算法的步骤 1 用密钥K1进行DES加密 2 用K2对步骤1的结果进行DES解密 3 用步骤2的结果使用密钥K1进行DES加密缺点 花费原来三倍时间优点 112位密钥长度 很 强壮 的加密方式 67 68 4 DES的安全性 1 弱密钥 WeakKey 所谓的弱密钥是指在所有可能的密钥中 有某几个特别的密钥会降低DES的安全性 所以使用者一定要避免使用这几个弱密钥 2 半弱密钥 Semi weakKey 除了上述的弱密钥之外 还有另外一种被称为半弱密钥的初始密钥 半弱密钥所产生的子密钥只有两种可能 每一种可能的子密钥刚好各出现8次 69 3 DES的互补性 Complement 在DES的明文m 密文C与密钥K之间存在着互补的特性 如果以密钥K对明文m加密得到密文C 那么以密钥对明文加密 亦可到 4 S 盒的设计原则S 盒为整个DES加密系统安全性的关键所在 但其设计规则与过程一直因为种种不为人知的因素所限 未被公布出来 70 2 2 2国际数据加密算法 IDEA 国际数据加密算法 InternationalDataEncryptionAlgorithm IDEA 是由瑞士联邦理工学院XuejiaLai和JamesMassey的在1990年提出的 IDEA是近年来提出的用来替代DES的许多算法中的一种 是一个对称分组密码算法 71 1 设计原理IDEA是一种使用128位密钥以64位分组为单位加密数据的分组密码算法 与此相对照 DES使用56位密钥以64位的分组为单位进行加密 IDEA的设计目标可以归结为与密码强度和使用的方便性两方面有关 其中密码强度包括分组长度 密钥长度 混淆 Confusion 和扩散 Diffusion 使用的方便性指方便硬件和软件实现 通过由超大规模集成电路 VLSI 进行的硬件实现的设计目标是取得高速度 而软件实现则有灵活和低价的优点 72 2 IDEA加密方法IDEA加密方法包括8轮的重复运算 加上最后的输出变换运算 Transformation 64位的明文分组在每一轮中都是被分成4份 每份16位为一单元来处理 每一轮中有6个不同的子密钥参与作用 73 图2 6IDEA加密流程 74 图2 7IDEA单轮运算结构 75 图2 8IDEA中最后的输出变换运算 76 3 子密钥生成过程从图2 6中可以看出 IDEA一次完整的加密运算需要52个子密钥 这52个16位的子密钥都是由一个128位的加密密钥产生的 将128位分成8份 每份16位 相当于Z1 Z2 Z8的子密钥 Z1的16位对应于加密密钥中最高有效 MostSignificant 的16位 而Z8的16位对应于加密密钥中最低有效 LeastSignificant 的16位 将加密密钥循环左移25位以后 用同样的方法可以得到另外的8个子密钥Z8 Z9 Z16 重复同样的步骤 每循环25位 可以得到另外的新的8个子密钥 如此 Z1 Z2 Z52可以依此陆续生成 77 4 IDEA解密方法使用与加密算法同样的结构 可以将密文分组当作输入而逐步恢复明文分组解密过程 与加密过程中惟一不同的是子密钥的生成方法 78 2 2 3高级加密标准 AES 1997年1月 NITS召集密码学专家研制一种新的加密体制 AES要求 1 它必须是一个对称的块密码算法 2 必须公开所有的设计 3 必须支持128 192和256位密钥长度 4 软件实现和硬件实现必须都是可能的 5 算法必须是公有的 或者毫无歧视地授权给大众使用 79 1998年8月 从提交的算法中选出了15种 1999年8月 侯选算法缩小到了5种 最终获胜的是Rijndael 荣代尔 算法 它是比利时密码学家 Rijmem Daemem 设计的 美国政府在2001年12月采纳了AES 并使其成为了联邦信息处理标准197 AES的加密 数据块128位 密钥128位 轮函数9轮 数据块128位 密钥192位 轮函数11轮 数据块128位 密钥256位 轮函数13轮 在128位密钥空间中有2128 3X1038个密钥 即使NSA想办法创建一台内含10亿个并行处理器的机器 且每个处理器每秒钟可以计算1012个密钥 也需要1010年才能搜索完整个密钥空间 80 1 设计基本原理 1 该算法的设计目标有以下3点 能抗击所有的已知攻击 在广大范围平台上的快速和代码简洁 设计简单 81 2 在大多数加密算法中都是采用的Feistel结构的轮变换 而Rijndael算法彻底改变了这种结构 每一轮的变换由3层组成 每一层都实现一定的功能 线性混合层 确保多轮之上的高度扩散 非线性层 并行使用多个S 盒 可优化最坏情况非线性特性 密钥加层 轮密钥 子密钥 简单异或到中间级状态上 82 2 算法详细描述Rijndael是一种具有可变分组长度和可变密钥长度的重复的分组密码 分组长度和密钥长度可独立选择为128 192和256bit 83 3 Rijndael加密和解密算法 1 Rijndael加密算法用伪C代码表示如下 Rijndael State CipherKey KeyExpansion CipherKey ExpandedKey AddRoundKey State ExpandedKey For i 1 i Nr i Round State ExpandedKey Nb i FinalRound State ExpandedKey Nb Nr 84 2 Rijndael解密算法解密算法用伪C代码表示如下 I Rijndael State CipherKey I KeyExpansion CipherKey I ExpandedKey AddRoundKey State I ExpandedKey Nb Nr For i Nr 1 i 0 i Round State I ExpandedKey Nb i FinalRound State I ExpandedKey 85 其中I KeyExpansion的伪C代码如下 I KeyExpansion CipherKey I ExpandedKey KeyExpansion CipherKey I ExpandedKey For i 1 i Nr i InvMixColumn I ExpandedKey Nb i 86 2 2 4分组密码的工作模式 已经提出的分组密码工作模式有 电子代码簿 ECB 模式 密码分组链接 CBC 模式 密码反馈 CFB 模式 输出反馈 OFB 模式 级连 CM 模式 又称多重加密模式 87 1 电子代码簿 ECB 模式 为了使用DES加密一长段明文 最简单的做法是将它分割成连续的8字节 64位 数据块 然后用同样的密钥逐个加密这些数据块 如有必要 将最后一片明文填充至64位 这项技术称为ECB模式 例子 88 2 密码分组链接 CBC 模式 基本原理如图 89 密码分组链接 CBC 模式 密文分组被反馈到输入端 明文分组与的异或结果被作为DES加密算法的输入 从而得到下一个密文分组 即 解密过程为 密文分组为无须保密的事先设定的初值 不同的明文x 而非明文分组 对应不同的 各密文分组不仅与与之对应的明文分组有关 也和此前的所有明文分组 即 有关 90 密码分组链接 CBC 模式 优点 能够隐蔽明文的数据模式 能够在一定程度上防止分组的重放 插入和删除等攻击 缺点 易导致错误传播 由于任何一个明文或密文分组出错都会导致其后的密文分组出错 但实际上 这种错误传播的影响并不大 至多影响两个密文分组 例如 加密过程中 xi的传输错误至多影响到yi和yi 1 91 3 密码反馈 CFB 模式 基本原理如图 92 密码反馈 CFB 模式 实质上是一种自同步流密码 适用于必须按比特或者字符对明文进行加密的情况 采用该模式实现DES算法时 反馈的密文分组的长度与此前的密文分组长度不同 而是通常为事先设定的n值 与明文相加的只是密文分组的最左边n位 反馈的密文分组同时反馈到密钥产生器 93 优点 能够隐蔽明文的数据模式 能够在一定程度上防止分组的重放 插入和删除等攻击 适用于用户数据格式的需要 缺点 对错误传输敏感 该模式即使密文在传输中只有一位偶然发生翻转 则在解密过程中 坏字节位于寄存器中所涉及的8个字节将遭到破坏 一旦字节移出了寄存器以后 后面产生的明文仍然是正确的 降低了数据加密的速率 94 4 输出反馈 OFB 模式 基本原理如图 95 输出反馈 OFB 模式 优点 能够克服错误传播 缺点 很难发现密文被篡改 不具备自同步能力 96 5 级连 CM 模式 基本原理如图 97 该模式的提出主要是为了增加密钥的长度 并采用不同的密钥和分组密码算法对同一明文连续进行多次加密 但如果所选用的加密算法成群 则由于群的封闭性特点 即任意次级连加密等于一次加密 级连模式并不能增加破译的难度 已证明采用级连模式能提高DES的安全性 如 三重DES 98 2 3非对称密码体制 背景 对称密钥编码所面临的难题密钥分配 密钥必须在安全信道上传输 通信密钥太多 管理和分发困难 数字签名和认证 密码体制上的突破Diffie Hellman NewDirectioninCryptography 1976年首次公开提出了 公开密钥密码编码学 的概念 这是一个与对称密码编码截然不同的方案 提出公开密钥的理论时 其实用性并没有得到证明 当时还未发现满足公开密钥编码理论的算法 直到1977年 RSA算法的提出 99 基本特征 两个密钥 使用一个密钥进行加密 用另一个相关的密钥进行解密用加密密钥生成的密文只有使用其对应的解密密钥才能解密 两个密钥的关系满足 两个密钥是不相同 且在仅知道密码算法和加密密钥的情况下 要推断解密密钥在计算上是不可行的 100 优点 密钥管理加密密钥是公开的 解密密钥需要妥善保存 在当今具有用户量大 消息发送方与接收方具有明显的信息不对称特点的应用环境中表现出了令人乐观的前景 数字签名和认证只有解密密钥能解密 只有正确的接收者才拥有解密密钥 101 2 3 1非对称密码体制的原理公开密钥算法有一个重要特性 仅仅知道密码算法和加密密钥而要确定解密密钥 在计算上是不可能的 另外 某些算法 如RSA 还具有以下特性 两个相关密钥中任何一个都可以用作加密而让另一个用作解密 102 如图2 9所示 公开密钥加密过程重要步骤如下 1 网络中的每个端系统都产生一对用于它将接收的报文进行加密和解密的密钥 2 每个系统都通过把自己的加密密钥放进一个登记本或者文件来公布它 这就是公开密钥 另一个则是私有的 3 如果A想给B发送一个报文 A就用B的公开密钥加密这个报文 4 B收到这个报文后就用他的保密密钥解密报文 其他所有收到这个报文的人都无法解密 因为只有B才有B的私有密钥 103 图2 9公开密钥的加密过程 104 公钥密码算法 加密与解密由不同的密钥完成加密 X Y Y EKU X 解密 Y X X DKR Y DKR EKU X 两个密钥中任何一个都可以用作加密而另一个用作解密 不是必须的 X DKR EKU X EKU DKR X 105 2 3 2RSA算法1 欧拉定理在数论中 欧拉定理 也称费马 欧拉定理 是一个关于同余的性质 欧拉定理表明 若n a为正整数 且n a互质 即 a n 1则a n 1 modn 其中 n 是比n小但与n互素的正整数的个数 106 2 RSA加密算法 这种算法1978年就出现了 它是第一个既能用于数据加密也能用于数字签名的算法 它易于理解和操作 也很流行 算法的名字以发明者的名字命名 RonRivest AdiShamir和LeonardAdleman RSA是被研究得最广泛的公钥算法 从提出到现在已三十多年 经历了各种攻击的考验 逐渐为人们接受 普遍认为是目前最优秀的公钥方案之一 RSA的安全性依赖于大数的因子分解 但并没有从理论上证明破译RSA的难度与大数分解难度等价 即RSA的重大缺陷是无法从理论上把握它的保密性能如何 而且密码学界多数人士倾向于因子分解不是NPC问题 107 3 RSA算法实现步骤 生成两个大素数p和q 保密 计算n pq 公开 n p 1 q 1 保密 选择随机数e 即加密密钥 使之满足0 e n gcd e n 1 公开 计算解密密钥d e 1mod n 即ed 1mod n 保密 公布整数n和加密密钥e 加密算法 c E m me modn 解密算法 D c cd modn 108 例子1 明文 SUZANNE P 3 q 11n p q 33 n p 1 q 1 20由0e 3由ed 1mod n d 7 109 举例2 取两个质数p 11 q 13 p和q的乘积为n p q 143 算出另一个数 n p 1 q 1 120 再选取一个与 n 120互质的数 例如e 7 则公开密钥 n e 143 7 对于这个e值 可以算出其逆 d 103 因为e d 7 103 721 满足e dmod n 1 即721mod120 1成立 则秘密密钥 n d 143 103 110 设张小姐需要发送机密信息 明文 m 85给李先生 她已经从公开媒体得到了李先生的公开密钥 n e 143 7 于是她算出加密值 c memodn 857mod143 123并发送给李先生 李先生在收到密文c 123后 利用只有他自己知道的秘密密钥计算 m cdmodn 123103mod143 85 所以 李先生可以得到张小姐发给他的真正的信息m 85 实现了解密 111 4 RSA安全性讨论若n pq被因子分解 则RSA便被击破 因为若p q已知 则 n p 1 q 1 便可算出 解密密钥d关于e满足下式 de 1 mod n 为了安全起见 对p和q还要求如下 1 p和q的长度相差不大 2 p 1和q 1有大素数因子 满足这些条件的素数称作安全素数 112 RSA的安全性 就目前的计算机水平用1024位的密钥是安全的 2048位是绝对安全的 RSA实验室认为 512位的n已不够安全 应停止使用 现在的个人需要用668位的n 公司要用1024位的n 极其重要的场合应该用2048位的n 113 RSA的缺点 A 产生密钥很麻烦 受到素数产生技术的限制 因而难以做到一次一密 B 分组长度太大 为保证安全性 n至少也要600bits以上 使运算代价很高 尤其是速度较慢 较对称密码算法慢几个数量级 且随着大数分解技术的发展 这个长度还在增加 不利于数据格式的标准化 目前 SET SecureElectronicTransaction 协议中要求CA采用2048比特长的密钥 其他实体使用1024比特的密钥 114 RSA算法的脆弱性 P q选择不当 则变换周期性 封闭性而泄密例 p 17 q 11 e 7 则n 187 设m 123 则C1 1237mod187 183C2 1837mod187 72C3 727mod187 30C4 307mod187 123明文m经过4次加密 恢复成明文 总之 RSA对用户要求太苛刻 密钥不能常更换 115 RSA的选择密文攻击 RSA在选择密文攻击面前很脆弱 一般攻击者是将某一信息作一下伪装 Blind 让拥有私钥的实体签署 然后 经过计算就可得到它所想要的信息 实际上 攻击利用的都是同一个弱点 即存在这样一个事实 乘幂保留了输入的乘法结构 XM d X d M dmodn前面已经提到 这个固有的问题来自于公钥密码系统的最有用的特征 每个人都能使用公钥 但从算法上无法解决这一问题 主要措施有两条 一条是采用好的公钥协议 保证工作过程中实体不对其他实体任意产生的信息解密 不对自己一无所知的信息签名 另一条是决不对陌生人送来的随机文档签名 签名时首先使用One WayHashFunction对文档作HASH处理 116 RSA的公共模数攻击 若系统中共有一个模数 只是不同的人拥有不同的e和d 系统将是危险的 最普遍的情况是同一信息用不同的公钥加密 这些公钥共模而且互质 那么该信息无需私钥就可得到恢复 设P为信息明文 两个加密密钥为e1和e2 公共模数是n 则 C1 P e1modnC2 P e2modn密码分析者知道n e1 e2 C1和C2 就能得到P 总之 如果知道给定模数的一对e和d 一是有利于攻击者分解模数 一是有利于攻击者计算出其它成对的e 和d 而无需分解模数 解决办法只有一个 那就是不要共享模数n 117 2 3 3椭圆曲线算法 1985年 N Koblitz及V S Miller分别提出了椭圆曲线密码体制 ECC 已经开发出的椭圆曲线标准的文档有 IEEEP1363P1363a ANSIX9 62X9 63 ISO IEC14888等 标准的产生将极大地促进椭圆曲线密码被更大规模地得以使用 近年来 ECC已走向工程实现和实际使用阶段 目前 德国 日本 法国 美国 加拿大等许多西方国家的密码学研究小组和公司已经实现了椭圆曲线密码体制 优点 密钥尺度较小 参数选择较灵活 具有由数学难题保证的安全性 实现速度较快 118 一个公钥密码系统的有效性需要考虑以下几个因素 计算开销 密钥长度和带宽 安全性和存储空间等方面 1 计算开销决定了变换公钥和私钥所需的计算量 2 密钥长度决定存储密钥对和系统参数需要的比特数 119 表2 10ECC RSA DSA的系统参数和密钥对长度比较 120 3 带宽是指传送一加密消息或一签名所传输的比特数 4 加密算法的安全性能一般通过该算法的抗攻击强度来反映 5 ECC的密钥尺寸和系统参数与RSA或DSA相比要小得多 121 通过以上分析可见 ECC与其他公钥加密系统相比 能提供更好的加密强度 更快的执行速度和更小的密钥长度 因此ECC可用较小的开销 所需的计算量 存储量 带宽 软件和硬件实现的规模等 和时延 加密和签字速度高 实现较高的安全性 特别适合用于计算能力和集成电路空间受限 如IC卡 带宽受限 如无线通信和某些计算机网络 和要求高速实现的情况 122 2 4密钥的管理密钥是加密解密算法中的可变部分 采用密码技术保护的系统 其安全性在很大程度上取决于对密钥的保护 而不仅仅是对算法和硬件本身的保护 因此 密钥的保密和密钥的安全管理在信息系统 通信系统等现代系统安全中是极其重要的 密钥管理包含了密钥自产生到最终销毁的整个过程中的各种安全问题 如 密钥的产生 存储 装入 分配 保护 遗忘 丢失和销毁 123 所有的密码技术都依赖于密钥 密钥的管理本身是一个很复杂的课题 而且是保证安全性的关键点 密钥管理方法因所使用的密码体制 对称密码体制和公钥密码体制 而异 124 密钥管理的目的 目的 维持系统中各实体之间的密钥关系 以抗击各种可能的威胁 1 密钥的泄露 2 秘密密钥或公开密钥的身份的真实性丧失 3 未经授权使用 125 2 4 1密钥长度 决定密钥长度需要考虑多方面的因素 数据价值有多大 数据要多长的安全期 攻击者的资源情况怎样 选择比需要的密钥长度更长的密钥 126 不同安全需求的密钥长度 127 2 4 2密钥生成 尽量避免容易记忆的安全性差的密钥 如用户的姓名 简写字母 帐户姓名和其他有关的个人信息等 字典攻击 最好的密钥还是随机密钥 但不容易记忆 128 2 4 3密钥分配 解决两个主要问题 引进自动密钥分配机制 减轻负担 提高系统的效率 尽可能减少系统中驻留的密钥量 提高安全性 129 典型的两类自动密钥分配途径 集中式分配方案 利用网络中的密钥分配中心 keydistributioncenter KDC 来集中管理系统中的密钥 密钥分配中心接收系统中用户的请求 为用户提供安全地分配密钥的服务 分布式分配方案 分布式分配方案是指网络中各主机具有相同的地位 它们之间的密钥分配取决于它们自己的协商 不受任何其他方面的限制 通常采取两种方案的混合 主机采用分布式方式分配密钥 而主机对于终端或它所属的通信子网中的密钥可采用集中方式分配 130 1 对称密钥分配的基本方法 密钥由A选取并通过物理手段发送给B 密钥由第三方选取并通过物理手段发送给A和B 如果A B事先已有一密钥 则其中一方选取新密钥后 用已有的密钥加密新密钥并发送给另一方 如果A和B与第三方C分别有一保密信道 则C为A B选取密钥后 分别在两个保密信道上发送给A B 131 密钥分类 基本密钥 basekey 用于启动和控制某种算法结构的密钥产生器 产生用于加密数据的密钥流 会话密钥 sessionkey 两个用户在一次通话或交换数据时采用的密钥 例如 数据加密密钥 文件加密密钥等 主密钥 hostmasterkey 对密钥进行加密时采用的密钥 132 密钥分配实例 假定两个用户A B分别与密钥分配中心有一个共享的主密钥KA和KB A希望与B建立一个逻辑连接 并希望有一个一次性会话密钥来保护该连接上的数据传送 分配过程见下图 133 密钥分配实例 1 A向KDC发出会话密钥请求 表示请求的消息由两个数据项组成 一是A和B的身份 二是这次业务的惟一识别符N1 每次请求所用的N1都应不同 且为防止假冒 应使敌手对N1难以猜测 因此用随机数作为这个识别符最为合适 134 2 KDC对A的请求发出应答 应答是由KA加密的消息 因此只有A才能成功地对这一消息解密 并且A可相信这一消息的确是由KDC发出的 消息中包括A希望得到的两项 一次性会话密钥KS A在第1步中发出的请求 包括一次性随机数N1 目的是使A将收到的应答与发出的请求相比较 看是否匹配 因此A能验证自己发出的请求在被KDC收到之前 未被他人篡改 而且A还能根据一次性随机数相信自己收到的应答不是重放的对过去的应答 此外 消息中还有B希望得到的两项 一次性会话密钥Ks A的身份 例如A的网络地址 IDA这两项由KB加密 将由A转发给B 以建立A B之间的连接并用于向B证明A的身份 135 3 A存储密钥并向B转发 因为转发的是加密后的密文 所以转发过程不会被窃听 B收到后 可得到会话密钥Ks 并从IDA可知另一方是A 而且还从知道的确来自KDC 这一步完成后 会话密钥就安全地分配给了A B 然而还能继续以下两步 4 B用会话密钥加密另一个一次性随机数 并将加密结果发送给A 5 A以作为对B的应答 其中是对进行某种变换 例如 加1 的函数 并将应答用会话密钥加密后发送给B 这两步可使B相信第3步收到的消息不是一个重放消息 136 2 公钥加密体制的密钥分配 包括两方面内容 公钥密码体制所用的公钥的分配 如何用公钥体制来分配对称密钥密码体制中使用的密钥 137 公钥的分配 公开发布 公用目录表 公钥管理机构 公钥证书 138 1 公开发布 指用户将自己的公钥发给每一其他用户 或向某一团体广播 比较简单 缺陷 任何人都可伪造这种公开发布 即发布伪造的公钥 139 2 公用目录表 建立一个公用的公钥动态目录表 目录表的建立 维护以及公钥的分布由某个可信的实体或组织承担 公用目录表的建立过程如下 1 管理员为每个用户都在目录表中建立一个目录 目录中有两个数据项 一是用户名 二是用户的公钥 2 每个用户都亲自或以某种安全的认证通信在管理者那里注册自己的公钥 3 用户如果由于自己的公钥用过的次数太多或由于与公钥相关的秘密钥己被泄露 则可随时用新公钥替换现有的公钥 4 管理员定期公布或定期更新目录表 例如 像电话号码本一样公布目录表或在发行量很大的报纸上公布目录表的更新 5 用户可通过电子手段访问目录表 这时从管理员到用户必须有安全的认证通信 优点 安全性高于公开发布 缺点 易受攻击 140 3 公钥管理机构 在公钥目录表的基础上 由一个公钥管理机构对公钥的分配进行更严密的控制 系统要求 每个用户都可靠地知道管理机构的公钥 而且只有管理机构自己知道相应的私钥 141 4 公钥证书 用户通过公钥证书相互交换自己的公钥而无需和公钥管理机构联系 公钥证书由证书管理机构CA CertificateAuthority 为用户建立 其中的数据项包括与该用户的秘钥相匹配的公钥及