密码学与信息安全 第12章 散列算法和MAC算法.ppt

第12章散列算法和MAC算法 第12章散列算法和MAC算法 消息认证是用来验证消息完整性的一种机制或服务 产生消息认证符的函数分为如下三类 消息加密 整个消息的密文作为认证符 消息认证码 MAC 它是消息和密钥的函数 它产生定长的值 以该值作为认证符 目前有两种MAC HMAC和CMAC散列函数 它是将任意长的消息映射为定长的散列值的函数 以该散列值作为认证符 目前主要有 MD5 SHA 1 SHA256 SHA 384 SHA 512 Whirlpool等 在数字签名方案中也要用到散列函数 对需要签名的消息用一个函数 产生一个固定长度的消息摘要 MessageDigest 最后对消息摘要进行签名 得到确定长度的签名消息 典型的安全散列函数的总体结构 典型的安全散列函数的总体结构 散列函数将输入消息分为L个固定长度的分组 每一分组长为b位 最后一个分组不足b位时需要将其填充为b位 最后一个分组还需要一些空间保存输入的总长度 散列函数中重复使用了压缩函数f 它的输入是前一步中得出的n位结果 称为链接变量 和一个b位分组 输出为一个n位分组 链接变量的初值由算法在开始时指定 其终值即为散列值 通常b n 因此称其为压缩函数 散列函数可归纳如下 CV0 IV 初始n位值CVi f CVi 1 Yi 1 1 i LH M CVL 安全散列算法 安全散列算法 SHA 是由美国标准与技术协会 NIST 设计 并于1993年作为联邦信息处理标准 FIPS180 发布 修订版于1995年发布 FIPS180 1 通常称之为SHA 1 SHA 1产生160比特的散列值 2002年 NIST发布了修订版2 FIPS180 2 其中给出了三种新的SHA版本 散列值长度依次为256 384和512比特 分别称为SHA 256 SHA 384 SHA 512 这些新的版本和SHA 1具有相同的基础结构 使用了相同的模算术和二元逻辑运算 2005年 NIST宣布了逐步废除SHA 1的意图 到2010年 逐步转而依赖SHA的其他版本 安全散列算法 所有的长度以比特为单位 安全性是指对输出长度为n比特散列函数的生日攻击产生碰撞的工作量大约为2n 2 SHA 512逻辑原理 为模264的逐字加 SHA 512逻辑原理 这个过程包含下列步骤 步骤1 附加填充位 填充消息使其长度模1024与896同余 即长度 896 mod1024 即使消息已经满足上述长度要求 仍然需要进行填充 因此填充位数在1到1024之间 填充由一个1和后续的0组成 步骤2 附加长度 在消息后附加一个128比特的块 将其看做是128比特的无符号整数 它包含填充前消息的长度 SHA 512逻辑原理 步骤3 初始化散列缓冲区 散列函数的中间结果和最终结果保存于512比特的缓冲区中 缓冲区用8个64比特的寄存器 a b c d e f g h 表示 并将这些寄存器初始化为下列64比特的整数 a 6A09E667F3BCC908e 510E527FADE682D1b BB67AE8584CAA73Bf 9B05688C2B3E6C1Fc 3C6EF372FE94F82Bg 1F83D9ABFB41BD6Bd A54FF53A5F1D36F1h 5BE0CD19137E2179 SHA 512逻辑原理 步骤4 以1024比特的分组 16个字 为单位处理消息 算法的核心是具有80轮运算的模块 每一轮 如t 使用一个64比特的值Wt 该值由当前被处理的1024比特消息分组Mi导出 每一轮还使用附加的常数Kt 其中0 t 79 用来表示轮数 这些常数如下获得 前80个素数取三次根 取小数部分的前64比特 第80轮的输出和第一轮的输入Hi 1进行模264相加产生Hi步骤5 输出 所有的N个1024比特分组都处理完以后 从第N阶段输出的是512比特的消息摘要 Ho IVHi SUM64 Hi 1 abcdefghi MD HN SHA 512轮函数 SHA 512轮函数 T1 h Ch e f g Wt KtT2 Maj a b c a T1 T2b ac bd ce d T1f eg fh g SHA 512轮函数 其中 t 步骤数 0 t 79Ch e f g eANDf NOTeANDg Maj a b c aANDb aANDc bANDc ROTR28 a ROTR34 a ROTR39 a ROTR14 e ROTR18 e ROTR41 e ROTRn x 对64比特的变量x循环右移n比特Wt 64比特字 从当前的1024比特输入分组导出Kt 64比特附加常数 模264加 SHA 512轮函数 前16个Wt直接取自当前分组的16个字 余下的值按如下方式导出 Wt 1512 Wt 2 Wt 7 0512 Wt 15 Wt 16其中 0512 x ROTR1 x ROTR8 x SHR7 x 1512 x ROTR19 x ROTR61 x SHR6 x SHRn x 对64比特变量x向左移动n位 右边填充0 HMAC 对于MAC 一种策略是利用hash函数来设计 因为 1 一般像md5 sha 1这样的散列函数 其软件执行速度比诸如des这样的对称分组密码钥要快 2 可以利用密码散列函数代码库 由于散列函数不是专为MAC设计的 其不依赖于秘密钥 所以不能直接用于MAC 目前提出了许多方案 其中HMAC是最受支持的一种方案 它是IP安全里必须实现的MAC方案 并且在其他Internet协议中也使用了HMAC HMAC设计目标 不必修改而直接使用现有的hash函数 特别地 很容易免费得到软件上执行速度较快的散列函数及其代码 如果找到或者需要更快或更安全的hash函数 应能很容易地替代原来嵌入的hash函数 应保持hash函数的原有性能 对密钥的使用和处理应较简单 如果已知嵌入的hash函数的强度 则完全可以知道认证机制抗密码分析的强度 HMAC算法 H 嵌入的hash函数IV 作为散列函数的输入值M HMAC的消息输入Yi M的第i个分组L M中的分组数b 每一分组所含的位数n 嵌入的散列函数所产生散列码长K 密钥 若k