密码学--HASH函数.

1、密码学密码学 HASH函数函数 保密性保密性: 怎样保持明文的秘密性，使得明文只能被某些怎样保持明文的秘密性，使得明文只能被某些 人阅读？人阅读？ 用加密的用加密的方法方法 完整性完整性: 怎样确定一列信号在产生后没有被篡改？怎样确定一列信号在产生后没有被篡改？ 用什么方法？用什么方法？ 在实际的通信保密中，除了要求实现数在实际的通信保密中，除了要求实现数 据的据的保密性保密性之外，对传输数据安全性的之外，对传输数据安全性的 另一个基本要求是保证数据的另一个基本要求是保证数据的完整性完整性。 HashHash函数是一个将任意函数是一个将任意 长度的消息序列映射为长度的消息序列映射为 较短的、固

2、定长度的一较短的、固定长度的一 个值的函数。个值的函数。 ) 1( 1 , 0 1 , 0: tf mtm 密码学密码学中的中的HashHash函数的主要功能是提供有函数的主要功能是提供有 效的数据完整性检验。效的数据完整性检验。 l HashHash函数也称为散函数也称为散列列函数，是函数，是一公开函数一公开函数， 不需要密钥，通常不需要密钥，通常记为记为H，用于将任意长的消用于将任意长的消 息息M映射为较短的、固定长度的一个值作为映射为较短的、固定长度的一个值作为 认证符，记为认证符，记为H(M)，经常称函数值经常称函数值H(M)为散为散 列值、哈希值、杂凑值、杂凑码或消息摘要列值、哈希值

3、、杂凑值、杂凑码或消息摘要 、数组指纹。、数组指纹。 l 从从密码角度看密码角度看，HashHash函数也可以看作是一种函数也可以看作是一种 单向密码体制单向密码体制，即它从一个明文到密文是不，即它从一个明文到密文是不 可逆映射，只有加密过程，不能解密可逆映射，只有加密过程，不能解密。 HASH函数的具体描述函数的具体描述 l 散散列值是消息中所有比特的函数，因此提列值是消息中所有比特的函数，因此提 供了一种错误检测能力，即改变消息中任供了一种错误检测能力，即改变消息中任 何一个比特或几个比特都会使散列值发生何一个比特或几个比特都会使散列值发生 改变。改变。 l 在在密码学和数据安全技术中，散

4、列函数是密码学和数据安全技术中，散列函数是 实现有效、安全可靠数字签字和认证的重实现有效、安全可靠数字签字和认证的重 要工具要工具，是安全认证协议中的重要模块。，是安全认证协议中的重要模块。 HASH函数的具体描述函数的具体描述 HASH函数函数的的概念概念 Hash散列函数一般模型散列函数一般模型 对于对于HashHash函数函数H有下面六个要求：有下面六个要求： （1）能够接受任意长度的消息作为输入；能够接受任意长度的消息作为输入； （2）能够能够生成较短的固定长度的输出；生成较短的固定长度的输出； （3）对对任何消息输入都应该能够容易和快速任何消息输入都应该能够容易和快速 地计算出散列值

5、；地计算出散列值； （4）应该应该是一个单向函数是一个单向函数难以或不可能难以或不可能 反推。也就是说，给定反推。也就是说，给定H(m)，恢复恢复m在在 计算上是不可行的；计算上是不可行的； （5）应该应该能够抵抗弱冲突，即当两个不同消能够抵抗弱冲突，即当两个不同消 息输入生成相同的输出时，就产生了冲突；息输入生成相同的输出时，就产生了冲突； （6）应该应该能够抵抗强冲突，即找到两个有意能够抵抗强冲突，即找到两个有意 义的消息义的消息m1和和m2，使得使得H(m1)=H(m2)几几 乎是不可能的。乎是不可能的。 HASH函数的安全性要求函数的安全性要求 单向性：由消息的散列值倒算出消息在计单向

6、性：由消息的散列值倒算出消息在计 算上不可行，即给定算上不可行，即给定H(m)，计算，计算m在计算上在计算上 不可行；不可行； M output H 由m计算H(m)容易 input output H M 由H(m)计算上m不容易 input HASH函数的安全性要求函数的安全性要求 抗弱碰撞性：对于任何给定消息及其散列抗弱碰撞性：对于任何给定消息及其散列 值，不可能找到另一个能映射出该散列值的值，不可能找到另一个能映射出该散列值的 消息；消息； output H M 给定给定H(M) m m input HASH函数的安全性要求函数的安全性要求 抗强碰撞性：对于任何两个不同的消息，抗强碰撞性

7、：对于任何两个不同的消息， 它们的散列值必定不同，很难找到两条消息它们的散列值必定不同，很难找到两条消息m 和和m，使得，使得H(m)=H(m)。 output H(m)=H(m) H M m m input 1979年年，MerKle基于数据压缩函数基于数据压缩函数f建议了一个散列建议了一个散列 函数的一般结构如下图函数的一般结构如下图所示所示。 MD系列、系列、SHA系列大多数散列函数都使用该结构。系列大多数散列函数都使用该结构。 HASH函数的一般结构函数的一般结构 HASH函数的一般结构函数的一般结构 HASHHASH函数函数输入消息输入消息M，并将其分为并将其分为L个固定长度的分个固

8、定长度的分 组，若最后一个数据块不满足输入分组长度要求，按组，若最后一个数据块不满足输入分组长度要求，按 照一定规则进行填充照一定规则进行填充 该该散列函数重复使用一个压缩函数散列函数重复使用一个压缩函数f。压缩函数压缩函数f有有 两个输入，一个是前一阶段的两个输入，一个是前一阶段的n位位输入输入，另外一个，另外一个 源于消息的源于消息的b位分组，并产生一个位分组，并产生一个n位的输出，算法位的输出，算法 开始时需要一个初始变量开始时需要一个初始变量IV，最终的输出值通过一最终的输出值通过一 个输出变换函数个输出变换函数g得到消息散列值，通常得到消息散列值，通常bn,故称故称f 为压缩函数，如

9、下图所示：为压缩函数，如下图所示： 压缩函数基本结构压缩函数基本结构 HASH填充填充 全部填充全部填充0 填充比特填充比特 的最高位为的最高位为 1，其余其余为为0 在在生成散列值之前，对输入消息进行分生成散列值之前，对输入消息进行分 组时，如果最后一块报文不足分组长度组时，如果最后一块报文不足分组长度 要求，就要进行填充。要求，就要进行填充。 Hash算列函数由于其单向性和随机性的特点算列函数由于其单向性和随机性的特点, , 主主 要运用于提供数据完整性要运用于提供数据完整性( (包括数字签名、以及与包括数字签名、以及与 数字签名联系起来的数字指纹的应用数字签名联系起来的数字指纹的应用)

10、) 知识证明、知识证明、 密钥推导、伪随机数生成等方面。密钥推导、伪随机数生成等方面。 1数字签名的应用数字签名的应用 HASH函数的应用函数的应用 在进行数字签名过程中使用用户的私钥加在进行数字签名过程中使用用户的私钥加 密消息的密消息的HashHash值，其它任何知道该用户公钥的值，其它任何知道该用户公钥的 人都能够通过数字签名来验证消息的完整性。人都能够通过数字签名来验证消息的完整性。 在这种情况下，攻击者要想篡改消息，则需要在这种情况下，攻击者要想篡改消息，则需要 知道用户的私钥。知道用户的私钥。 2生成程序或文档的生成程序或文档的“数字指纹数字指纹” HASH函数的应用函数的应用 HASH函数可以将任意长度的输入变换为固定长度的函数可以将任意长度的输入变换为固定长度的 输出，不同的输入对应着不同的输出，因此，可以输出，不同的输入对应着不同的输出，因此，可以 基于基于HASH函数变换得到程序或文档的散列值输出，函数变换得到程序或文档的散列值输出， 即即“数字指纹数字指纹”。 3用于安全存储口令用于安全存储口令 如果基于如果基于HASH函数生成口令的散列值，然后在函数生成口令的散列值，然