现代密码学-第5章Hash函数与消息认证-20091110

1 现代密码学 21世纪高等学校计算机规划教材 代渊 信息科学与技术学院 者：何大可 彭代渊 唐小虎 何明星 梅其祥 出版社：人民邮电出版社 2 现代密码学 代渊 信息科学与技术学院 2009年 11月 第 5章 3 第 5章 全 于分组密码与离散对数的 息认证 4 5 数据安全 机密性 完整性 认证性 密码技术主要保证数据的机密性 6 射成固定长度消息的函数。 n*n*ii* h )(:0任意长度消息集合消息集合长度为字母表将 或称为哈希函数、散列函数。对于任何消息 x ，将 h(x)称为 列值、消息摘要（ 7 设 x、 x是两个不同的消息，如果 h(x)=h(x) 则称 x和 x是 ）碰撞 . 8 单向 给定一个 y，如果寻找一个消息 x，使得 y=h (x)是计算上不可行的，则称 弱抗碰撞 任给一个消息 x，如果寻找另一个不同的消息 x，使得 h(x) =h(x)是计算上不可行的，则称 强抗碰撞 （ 如果寻找两个不同的消息 x和 x，使得 h(x)=h(x)是计算上不可行的，则称 9 安全 对任意的消息 x，计算 h(x)是容易的； 是强抗碰撞的。 10 11 对 生日悖论（ 生日问题：假设每个人的生日是等概率的，每年有 365天，在 ，问 511. 5213 6 511 365( 2k 人生日相同的概率为：人中至少有有 P(365,23)=在 23个人中，至少有两个人生日相同的概率大于 个数字比人们直观猜测的结果小得多，因而称为生日悖论。 12 生日攻击法 生日悖论原理可以用于构造对 设 别把消息 表示成 个 变形的消息 。消息与其变形消息具有不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、使用缩写、使用意义相同的单词、去掉不必要的单词等。 13 生日攻击法 分别把消息 表示成 个 变形的消息 14 生日攻击法 计算真消息 的变形发生碰撞的概率 由于 以对于给定 的变形 n。由于 以 1 1 / 2 为消息 此 的变形都不碰撞的概 率是： 的变形发生碰撞的概率是： 2 15 生日攻击法 当 r=R=2n/2时， P(n)=1e1于 4比特的 日攻击的时间复杂度约为 232，所以是不安全的。 为了抵抗生日攻击，建议 28 比特 . 16 中间相遇攻击（ 用于攻击一类具有特殊结构的 分析 讨论一类利用加密变换构造的 设加密体制为： ,对于消息 m=(其散列值的计算分以下两步： （ 1） EK( （ 2） d=h(m)= 其中 这类 17 中间相遇攻击（ 用于攻击一类具有特殊结构的 分析 讨论一类利用加密变换构造的 攻击方式 : 假设攻击者要找出一个假消息 M=(使得 M与 d。攻击者首先产生消息 息 个变形 . 18 中间值集合 假消息的 第 1部分 形 1,2 1,r V 2,R 消息的 第 2部分 2,1 DK d 目标摘要 EK(d=h(m)=EK( 19 .,.,2,1|),(,.,2,1|),(:.,.,2,1|,.,2,1|:,2,22,1,11,2,1 计算令这里 设加密变换 么可以使用生日攻击法来分析集合 2中出现相同元素的概率。 如果集合 2有相同元素，例如 i= j=2, j, d)，则有 d=j, h1,i )，即 M与 d。 EK(d=h(m)=EK( 20 21 压缩函数（ 迭代技术 设 的比特串。重复应用压缩函数 f，对消息 后得到 )1(1,01,0: tf 22 计算消息 h(x)的步骤 预处理 : 用一个公开算法在消息 到比特串 y，使 得 有 y= x | x) = | y 2 | | 其中 | t (i =1, 2, r)， x)称为 填充函数 。典型的填充函数是先添加 x|的值，再添加若干比特（例如 0）。 迭代过程 : 设 复使用压缩函数 f，依次计算 f (| (i =1, 2, r). 输出变换 : 设 g: 0,1m0,1 h(x)=g( 23 用上述方法构造的 多数实用 在预处理阶段，必须保证变换 x为如果预处理变换 x存在 xx使得 y=y，从而h(x)=h(x)，即能够找到 对于任意无碰撞的压缩函数，都可以使用迭代技术构造一个无碰撞的 24 第 5章 全 于分组密码与离散对数的 息认证 25 D:息摘要 ) 1990年 10月 , 著名密码学家 R. L. 出了一种作为 320 (联网研究和开发机构工作记录 )公开发表 ,称为 于 1992年 4月作为 321公开发表 . 直接构造法 : 不依赖任何密码系统和假设条件 算法简洁 计算速度快 特别适合 32位计算机软件实现 倾向于使用低端结构 . 26 x，对输入消息按 512位的分组为单位进行处理，输出 128位的散列值MD(x)。整个算法分为五个步骤。 步骤 1: 增加填充位 在消息 其长度与 448模 512同余。也就是说，填充后的消息长度比 512的某个倍数少 64位。 即使消息本身已经满足上述长度要求，仍然需要进行填充。 例如，若消息长为 448，则仍需要填充 512位使其长度为 960位。填充位数在 1到 512之间。填充比特的第一位是 1，其它均为 0。 27 步骤 2: 附加消息长度值 用 64位表示原始消息 将其附加在步骤 1所得结果之。若填充前消息长度大于 264，则只使用其低 64位。填充方法是把 64比特的长度分成两个 32比特的字，低 32比特字先填充，高 32比特字后填充。 步骤 1与步骤 2一起称为消息的预处理 经预处理后，原消息长度变为 512的倍数 设原消息 Y=1 ， 其中 i =0,1, L1）是 512比特 在后面的步骤中，将对 512比特的分组 28 例 假设消息为 : x=“01100001 01100010 01100011 01100100 01100101=(61 62 63 64 65)16, |x|=40=(28)16. 步骤 1在 个“ 1”和 407个“ 0”，将 48比特的 x | 1 | 0 (407个 ) = x | 800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. =61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. 29 例 假设消息为 : x=“01100001 01100010 01100011 01100100 01100101=(61 62 63 64 65)16, |x|=40=(28)16. 经步骤 2处理后的比特串为（ 16进制表示）： x2=28(64位 ) =61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 28000000 00000000. 30 步骤 3: 初始化 28位的缓冲区里，缓冲区用 4个 32位的寄存器表示。 4个缓冲区记为 A、 B、 C、 D，其初始值为下列 32位整数（ 16进制表示）： A=67 45 23 01, B=D 9, C=98 C D=10 32 54 76. 上述初始值以小端格式存储 (字的最低有效字节存储在低地址位置 )为： 字 A=01 23 45 67, 字 B=89 D 字 C=C 8, 字 D=76 54 32 10. 31 步骤 4: 以 512位的分组 (16个字 )为单位处理消息 其压缩函数为 : . 1 2 85 1 21 2 851,01,0: H步骤 4是 以 512比特作为分组，重复应用压缩函数 消息 1开始，依次对每个分组 至最后分组 ，然后输出消息 见， 中 512比特分组的数目 L。 32 加法是指缓冲区中的4个字与 32相加 . 1 2 85 1 21 2 851,01,0: 一轮要对缓冲区 6次迭代，每次迭代的运算形式为 : ( ( , , ) )sa b L a g b c d X k T i 其中 a、 b、 c、 、 B、 C、 算结束后再将（ a、 b、 c、 d）循环右移一个字。 34 g 每一轮使用一个基本逻辑函数 g，每个基本逻辑函数的输入是三个 32位的字，输出是一个 32位的字，它执行位逻辑运算，即输出的第 基本逻辑函数 符号 、 、 和 分别表示逻辑操作 35 g 基本逻辑函数 b c d F G H I 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 0 36 字组 X 把当前处理的 512比特的分组 6个 32比特的字 , 分别记为 X0,1,15. 在每一轮的 16步迭代中 , 每一步迭代使用一个字 ,迭代步数不同使用的字也不相同 . 因此 , 16步迭代恰好用完 16个字 . 37 对于不同轮处理过程 , 使用 16个字的顺序不一样 . 第一轮中，使用顺序为 X0,1,15 。 第二轮中使用顺序由下列置换确定 : 2(i)= (1+5i) 6 第三轮中使用顺序由下列置换确定 : 3(i)= (5+3i) 6 第四轮中使用顺序由下列置换确定 : 4(i)= 7i 6. 例如 : 第三轮处理过程的第 X3(i)= X(5+3i) 6; 第 8步迭代使用字 X3(8)=X(5+38)=X29=X23. 38 T1=2=3=2420704=5=6=47877=8=9=69809810=811=12=89513=614=15=16=4917=18=19=26520=21=22=02441453 T23=24=25=2126=27=28=45529=30=31=67632=833=34=877135=69936=37=38=439=40=41=28942=43=44=0488145=46=47=148=49=50=43251=52=53=65554=855=56=8584557=658=59=60=461=62=63=264=常数表 T： 64个 32位常数 Ti =232i)的整数部分 (i=1,2,64). 39 常数表 T： 64个 32位常数 Ti =232i)的整数部分 (i=1,2,64). 常数表 机化” 32位的输入数据，即消除输入数据的规律性。 的元素 T16(k1)+1, 16(k1)+2,16 k (k=1,2,3,4)， 第 T16( k1)+ i(i=1,2,16). 40 循环左移位数 s Ls(v)表示对 32位的变量 步数轮数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 7 5 4 6 12 9 11 10 17 14 16 15 22 20 23 21 7 5 4 6 12 9 11 10 17 14 16 15 22 20 23 21 7 5 4 6 12 9 11 10 17 14 16 15 22 20 23 21 7 5 4 6 12 9 11 10 17 14 16 15 22 20 23 21 41 步骤 5: 输出 依次对消息的 12比特的分组进行处理，第 D(x)。 可将 V = ) ) (i=0,1, L1) . 第三步定义的缓冲区 L =消息经第一步和第二步处理后分组的个数 消息的第 12位分组 使用基本逻辑函数 输入字的模 232相加 散列值 . 42 28位 目前，对 T. 1992）已经证明，对单轮的 用差分密码分析，可以在合理的时间内找出散列值相同的两条消息。这一结果对 是，目前尚不能将这种攻击推广到具有四轮运算的 B. . 1993）说明了如何找到消息分组和使它们产生相同的输出 . 也就是说 , 对一个 512位的分组 , 这种情况称为伪碰撞（ 43 H. 1996）找到了 给定一个 512位的分组 ,可以找到另一个 512位的分组 ,对于选择的初始值 们的 到目前为止 , 尚不能用这种方法对使用 我国山东大学王小云教授（ 2004）提出的攻击对于 V，王小云找到了许多 512位的分组对，它们的 国际密码学家 造了符合 对 64数量级 . 所以 , 必须设计新的 使其与 44 第 5章 全 于分组密码与离散对数的 息认证 45 全 安全 美国标准与技术研究所（ 计并于 1993年作为联邦信息处理标准（ 80）发布 修改版于 1995年发布（ 801），通常称之为。该标准称为 安全 174也给出了 ，它基本上是复制 801的内容，但增加了 算法的输入是长度小于 264的任意消息 x，输出 160位的散列值。 46 算法步骤 处理消息的过程与 输入消息按 512位的分组为单位进行处理，整个算法分为五个步骤 步骤 1: 增加填充位 在消息右边增加若干比特，使其长度与 448模 512同余。即使消息本身已经满足上述长度要求，仍然需要进行填充。填充位数在 1到 512之间。填充比特的第一位是“ 1”，其它均为“ 0”。 步骤 2: 附加消息长度值 用 64位表示原始消息 将其附加在步骤 1所得结果之后。 步骤 1与步骤 2一起称为消息的预处理 经预处理后，原消息长度变为 512的倍数。设原消息 =1 ，其中 i =0,1, L1）是 512比特。在后面的步骤中，将对 512比特的分组 47 算法步骤 步骤 3: 初始化缓冲区 算法的中间结果和最终结果保存在 160位的缓冲区里，缓冲区用 5个 32位的寄存器表示。 5个缓冲区记为 A、 B、 C、 D、 E，其初始值为下列 32位整数（ 16进制表示）： A=67 45 23 01, B=D 9, C=98 C D=10 32 54 76, E=2 0. 其中，前 4个初始值与 以大端格式存储缓冲区的值，即字的最高有效字节存于低地址字节位置。因此，上述初始值存储为（十六进制）： 字 A=67 45 23 01, 字 B=D 9, 字 C=98 C 字 D=10 32 54 76, 字 E=2 0. 48 算法步骤 步骤 4: 以 512位的分组（ 16个字）为单位处理消息 是迭代 压缩函数为： . 1 6 05 1 21 6 0S H A 1,01,0: H步骤 4是 算法的主循环，它以 512比特作为分组，重复应用压缩函数 消息 1开始，依次对每个分组 至最后分组 ，然后输出消息 循环次数等于消息 12比特分组的数目 L。 49 的 压缩函数 由四轮处理组成 加法是模 232相加 160) 512) B C D A E K, W60,61,79, 20 步 B C D A E K, W20,21,39, 20 步 B C D A E K, W40,41,59, 20 步 B C D A E K, W0,1,19, 20 步 + + + + + (160) 50 的压缩函数 压缩函数 一轮要对缓冲区 0次迭代，每次迭代的运算形式为 B ) ,A,),( A )D)C,( B ,(,B,A, 305 A B C D E A B C D E + + f + 30 中 A、 B、 C、 D、算结束后再将（ A、 B、C、 D、 E）循环右移一个字。 51 (C)(B的压缩函数 基本逻辑函数 f 每一轮使用一个基本逻辑函数 f，每个基本逻辑函数的输入是三个 32位的字，输出是一个 32位的字，它执行位逻辑运算，即输出的第 轮数 基本逻辑函数 f f(B, C, D) 1 2 3 4 , C, D) , C, D) , C, D) , C, D) 52 的压缩函数 基本逻辑函数 f 基本逻辑函数 B C D 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 53 的压缩函数 字组 t（ 0t79）代表迭代步数，依次表示第一、二、三、四轮处理过程进行的迭代次序 t79)是 32比特的字，它的前面 16个字 1, i，其余字为 ).,17,16()( 3814161 加法常数表 03030302223252 1 0迭代步数 十六进制 十进制 0t19 20t39 40t59 60t79 54 算法步骤 步骤 5: 输出 第 D(x) 的处理过程归纳如下： V = (i=0,1, L1) 其中： 第三步定义的缓冲区 处理第 L =消息经第一步和第二步处理后分组的个数 输入字的模 232相加 散列值 . 55 和 与 以它们的性质极为相似 抗穷举攻击的能力 抗穷举攻击的能力比 用穷举攻击方法产生具有给定散列值的消息 128数量级 需要的代价为 2160数量级 用穷举攻击方法产生两个具有相同散列值的消息 64数量级 需要的代价为 280数量级 抗密码分析的能力 算法抗密码分析的能力似乎并不弱 56 和 速度 执行的速度比 简洁性 和 需要使用大的程序和置换表 数据的存储方式 使用 两种方式没有本质的差异 57 第 5章 全 于分组密码与离散对数的 息认证 58 于分组密码与离散对数的 利用已有的密码算法构造 如果密码算法是安全的，那么利用它所构造的 59 用分组密码算法构造 已知条件 设 钥为 k，对于任意的消息 x，首先对 组的长度为 n。设消息 x=x1 其中 )n（ 1 i L） . 60 用分组密码算法构造 基于分组密码 首先选取一个初始值 : F(2)n， 然后依次计算 : 最后定义 x)= 1( ) ( 1 ) ,i k i x y i L IV=y0 k y1 k y2 k yL=x) 61 基于分组密码 首先选取一个初始值 : F(2)n， 然后依次计算 : 最后定义 x)= 用分组密码算法构造 1( ) ( 1 ) ,i i k iy x E y i L IV=y0 x1 k x2 k yL=x) k 在密钥公开的情况下，基于分组密码 们甚至不是弱无碰撞的 . 62 基于一些困难数学问题，诸如离散对数问题、因子分解问题、背包问题等可以构造出一些 些 1992年）提出的基于离散对数问题构造的 运行速度不是很快 可以证明是安全的 . 设 q=(p1)/2是一个素数， 和 是 设离散对数 是计算上不可行的。定义 于离散对数问题的 .m o d),(,:2121* 63 用反证法，如果 么可以证明离散对数 能被有效计算 . 设 ( ( ( h(h(那么 于离散对数问题的 .m o dm o d 24314321 p p 记 d=x4p1)。因为 p1=2q，且 以 d1,2, q, p1。下面对 64 于离散对数问题的 情况 1： d =1 此时 x4p1有逆，设 y=(x41 p1)，则存在整数 k，使得 (x4y=1+ (p1) k，则有 .m o d )()1()()1()( 313124 因此，可计算离散对数 ).1(m o d)()(l o g 1243131 65 于离散对数问题的 情况 2： d =2 因为 p1=2q,且 所以 x4q)=1. 设y=(x41 q，则存在整数 k，使得 (x4y=1+有 .m o d,m o d)1(,m o o )(1)(21243124p p p p ).1(m o d)1(l o g)(),1(m o d)()(l o 或由于 q=1 p，所以 ).1(m o d)(),1(m o d)()(l o 容易检验二式中哪一个成立 . 即离散对数 能被有效计算 . 66 于离散对数问题的 情况 3： d = q 因为 0x2q1, 0x4q1 (q1)x4x2q1 x4q1)= 情况 3不存在 . 情况 4： d =p1 这种情况只有在 x2=样就有 .m o 所以 x1=( (与已知矛盾 ! 即情况 4也不存在 . 67 第 5章 全 于分组密码与离散对数的 息认证 68 息认证 认证（ 防止网络系统遭受主动攻击的重要技术 认证的主要目的有两个 第一，验证消息的发送者是真的，而不是冒充的，称为 实体认证 ，包括信源、信宿等的认证和识别。 第二，验证信息的完整性，即验证数据在传送或存储过程中未被篡改、重放或延迟，称为 消息认证 。 69 消息认证码 带密钥的 息认证码 ( 消息认证码是实现消息认