当前位置：文档之家 › 现代密码学：第41讲 Hash函数

现代密码学：第41讲 Hash函数

  • 格式：pdf
  • 大小：369.51 KB
  • 文档页数：18

下载文档原格式

  / 18

合集下载

现代密码学：第41讲 Hash函数

现代密码学：第41讲 Hash函数

电子科技大学信软学院——现代密码学廖永建Hash 函数的定义
Hash 函数使用方式
Hash 函数满足条件及安全性定义
电子科技大学信软学院——现代密码学廖永建
电子科技大学信软学院——现代密码学廖永建Hash 函数的定义
Hash 函数使用方式
Hash 函数满足条件及安全性定义
电子科技大学信软学院——现代密码学廖永建
电子科技大学信软学院——现代密码学廖永建Hash 函数的定义
Hash 函数使用方式
Hash 函数满足条件及安全性定义
提供认证提供保密
提供认证
提供认证
提供认证提供保密
Bob
提供认证
提供认证提供保密。

密码学--HASH函数

密码学--HASH函数
声称者A 验证者（系统）B 口令表

A

H(mA）(m为口令）
A


H (m A )
'
H(mA）
A：口令m’
=
是 接受
否
拒绝
Hash函数在银行应用举例采用Hash函数，银行操作人员不能获取到用户的密码
THE END！
由m计算H(m)容易
H
由H(m)计算上m不容易
HASH函数的安全性要 求
② 抗弱碰撞性：对于任何给定消息及其散列 值，不可能找到另一个能映射出该散列值的 消息； input
M m H output
m’
给定H(M)
HASH函数的安全性要 求
③ 抗强碰撞性：对于任何两个不同的消息， 它们的散列值必定不同，很难找到两条消息m 和m’，使得H(m)=H(m’)。 input M m m’ H(m)=H(m’) H output
YL-1
b n
CVi-1
f
n
CVi
压缩函数基本结构
HASH填充
在生成散列值之前，对输入消息进行分 组时，如果最后一块报文不足分组长度 要求，就要进行填充。
全部填充0
填充比特 的最高位为 1，其余为0
HASH函数的应用
Hash算列函数由于其单向性和随机性的特点, 主 要运用于提供数据完整性 ( 包括数字签名、以及与 数字签名联系起来的数字指纹的应用 ) 知识证明、 密钥推导、伪随机数生成等方面。 1．数字签名的应用
HASH函数的概念
对于Hash函数H有下面六个要求：
任意长度
m 消息
（1）能够接受任意长度的消息作为输入；
（2）能够生成较短的固定长度的输出； （3）对任何消息输入都应该能够容易和快速

HASH函数简介

HASH函数简介

② 弱单向性：已知x，找出x’ （x’ ≠x）,使得 h(x’ )= h(x) 在计算上是不可行的，满足这一 性质的单向散列函数称为弱单向散列函数。
Hash函数的安全性
问题 碰撞
实例：Hash函数h：X → Y
找出：x，x’∈X使得x’ ≠x,并且h(x’ )= h(x) ③ 强单向性：找出任意两个不同的输入x，x’ 使得h(x’ )= h(x)在计算上是不可行的，满足 这一性质的单向散列函数，则称其为强单向 散列函数
它适用在32位字长的处理器上用高速软件实 现--它是基于 3ash算法：
MD5:1992年4月Ron Rivest公布的MD4的改 进RFC 1321称为MD5 它对输入仍以512位分组，其输出是4个32位 字的级联，与 MD4 相同。MD5比MD4来得 复杂，并且速度较之要慢一点，但更安全， 在抗分析和抗差分方面表现更好。
Hash算法
从密码分析的角度来看，MD5被认为是易受 攻击的 2004年山东大学王小云教授破译了MD5， 采用”比特追踪法”(模差分方法)可以很 快的找到一个碰撞。而且这种攻击已经部 分的可实用化，即找到有意义的碰撞。
Hash算法
著名的Hash算法：
SHA1:安全杂凑算法(secure hash algorithm,
Hash函数
Hash函数
在实际的通信保密中，除了要求实现数 据的保密性之外，对传输数据安全性的 另一个基本要求是保证数据的完整性。 密码学中的Hash函数可为数据完整性提 供保障
数据的完整性是指数据从 发送方产生后，经过传输 或存储以后，未被以未授 权的方式修改的性质。
Hash函数
Hash函数通用来构造数据的短“指纹”（函 数值）；一旦数据改变，指纹就不再正确。 即使数据被存储在不安全的地方，通过重新 计算数据的指纹并验证指纹是否改变，就能 够检测数据的完整性。

哈希函数.ppt

哈希函数.ppt
二次探测法：如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-
k*k(k<=m/2)称二次探测再散列，用公式表达如下：
例：在长度为11的哈希表中已填有关键字分别17,60,29的 记录，现有第四个记录，其关键字为38，由哈希函数得到 地址为5，若用线性探测再散列，如下：
哈希函数 哈希表中的元素是由哈希函数确定的。将
数据元素的关键字K作为自变量，通过一定的函数关系 （称为哈希函数）计算出的值，即为该元素的存储地址。 表示为：
Addr = H（key） 这个函数就是哈希函数
二、冲突及冲突处理
由于哈希函数是一个压缩映像，因此，在一般情况下， 很容易产生“冲突”现象
在哈希元素（地址）求解过程中，不同关键字值对应到同一 个存储地址的现象称为冲突。即关键字K1 K2， 但哈希函 数值 H（K1）= H（K2）。 均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突 后，必须解决；也即必须寻找下一个可用地址。 处理冲突是建立哈希表过程中不可缺少的一部分。
0 1 2 3 4 5 6 7 8 9 10
(a)插入前
60 17 29

0 12 3 4 5
6
7
8
9 10
(b)线性探测再散列
60 17 29 38
0 1 2 3 4 5 6 7 8 9 10 38 60 17 29
(c)二次探测再散列
0123
45
6
7
8 9 10
38
60 17 29
(d)伪随机探测再散列，伪随机数列为9,5,3,8,1...
解题思路：首先，明确一下几格概念：什么是hash表、 什么是hash函数、什么是线性探查法、冲突在哪里； 其次逐一求余；最后找出冲突，利用线性探查法解决 问题。

HASH函数

HASH函数
B C D
A
MD4 (1990年10月作为RFC1320发表) by Ron Rivest at MIT
• MD4的设计目标 • 安全性： • 速度：32位体系结构下计算速度快. • 简明与紧凑：易于编程. • 有利的小数在前的结构(Intel 80xxx, Pentium ) • MD4与MD5的区别 • MD4用3轮,每轮16 步,MD5用4轮,每轮16步. • MD4中第一轮没有常量加；MD5中64步每一步用了一 个不同的常量 T[i]； • MD5用了四个基本逻辑函数，每轮一个；MD4用了三 个. • MD5每轮加上前一步的结果；MD4没有.
y 取 k 个随机值得到函数的 k 个输出中至少有一个 等于h(x)的概率为 1-[1-1/n]k 由(1+x)k≈1+kx，其中|x|<<1，可得
1-[1-1/n]k≈1-[1-k/n]=k/n
给定 h(x) ，如果对 h 随机取 k 个输入，至少有一个 输入 y 使得 h(y)=h(x) 的概率为 1-[1-1/n]k≈1-[1-k/n]=k/n • 若使上述概率等于0.5，则 k=n/2。特别地，如果 h 的输出为 m 比特长，即可能的输出个数 n=2m，则 k=2m-1。
• 生日攻击(基于生日悖论) 在k个人中,找一个与某人生日相同的人的 概率超过0.5时,只需k>183; 而在此人群中, 至少有两个人生日相同的概率超过0.5,只 需k>23.
将生日悖论推广为下述问题：已知一个在1到n 之间均匀分布的整数型随机变量，若该变量的 k 个 取值中至少有两个取值相同的概率大于0.5，则k至 少多大？ n! P(n, k ) 1 与上类似， (n k )!n k 令P(n, k)>0.5，可得 k 1.18 n n 若取 n=365，则

《现代密码学》散列函数与消息鉴别ppt课件

《现代密码学》散列函数与消息鉴别ppt课件

• SHA–1产生音讯摘要的过程类似MD5，如下图
填充位
L×512 bit＝ N×32 bit K bit
这一步为MD5的主循环，包括四轮。每个循环 都以当前的正在处置的512比特分组Yq和128比 特缓冲值ABCD为输入，然后更新缓冲内容。
3.MD5的输出
由A、B、C、D四个存放器的输出按低位字节在 前的顺序(即以A的低字节开场、D的高字节终 了)得到128位的音讯摘要。
• 单个512比特分组的MD5主循环处置：
对散列函数必需具有的性质的了解： 系统能够存在的伪造方式 伪造方式一：假设攻击者截获某一音讯摘要h,假
设H的逆函数H-1是易求的，可算出H-1(h)=m, 满足h=H(m)。为防止这一点，必需求求散列 函数H为单向的，即计算H的逆函数H-1在计算 上是不可行的。 伪造方式二：从一个有效签名(m,y)开场，此处y= sigk(H(m))。首先计算h=H(m)，并企图找到一 个m’=m满足H(m’)=H(m)。假设做到这一点， 那么(m’,y)也将为有效签名。为防止这一点， 要求函数h具有弱抗冲突特性，即，对给定音 讯m，在计算上几乎找不到不同于m的m’ ∈ X 使H(m)=H(m’)。
(1)单向性：对任何给定的码h，寻觅m使得 H(m) = h在计算上是不可行的
(2)具有弱抗碰撞性〔week collision resistance〕 ：对于任何给定的音讯m， 寻觅一个与m不同的音讯m’使得 H(m)=H(m’)在计算上不可行。
(3)具有强抗碰撞性〔 strong collision resistance 〕：寻觅恣意两个不同的音讯 m和m’使得使得H(m)=H(m’)在计算上不 可行。
对散列函数的生日攻击
• 假定其输出为m比特，那么寻觅一个音讯，使其散 列值与给定散列值一样那么需求计算2m次；而寻 觅两个音讯具有一样的散列值仅需求实验2m/2个 随机的音讯。

哈希函数名词解释

哈希函数名词解释哈希函数(hash function)是解决密码学上的一个很有用的函数，它能将很多不同的信息结合成一个特征向量。

分组密码体制是数据加密和解密所采用的主要方法，是指把需要加密的文件分为若干组，每组给定一个加密密钥，对这些文件进行加密，其余部分对外宣称是无密文件。

这种方法安全性较高，但效率低下，因此，只在少数场合使用。

哈希函数也可用于对任意长度的数据块进行加密，例如，使用一个512位的字符数组，即可将信息长度扩展至32766位(1K字节)，因而使用计算机中的哈希函数对任意大小的信息块都可以进行加密，不再受限于密码长度。

哈希函数的基本原理是：根据文件或数据块的特征，生成一个32位的特征向量(公钥)，对该特征向量计算，得到两个32位的特征向量(私钥)。

这两个向量相减就是文件或数据块的密文，如果两个特征向量之和等于所要求的密文，那么这个文件或数据块就是被加密了的;否则就是未加密的。

当然，如果特征向量相减后的值不等于所要求的密文，则说明这个文件或数据块还没有被加密。

1.数据预处理方法。

一般分为三步进行：首先，计算数据的安全哈希值，称作SHA1(sha-1)值;其次，对哈希值和文件加密密钥进行比较，以确认哈希值的正确性;最后，用哈希值来加密数据，哈希值就是加密数据的公钥。

2.数据加密方法。

一般包括数据分组、密钥预处理、哈希函数三步：首先对分组数据进行加密;其次是对加密后的数据进行分组;第三步是选取一个具有足够密钥长度并且具有适当排列顺序的哈希函数对数据进行加密。

2.1.1.1.数据分组方法。

分组时，按哈希函数值的大小对分组后的数据块逐个编号，并且使用固定的哈希函数值，作为下一轮分组和计算哈希值的依据。

这样做，可以保证数据被加密的安全性和实现简单。

2.1.2.1.密钥预处理方法。

密钥预处理时，要按哈希函数值从大到小的顺序进行，先对大的密钥执行密钥变换，再将小密钥插入到大的密钥中去。

同时，由于密钥预处理使用了小密钥，为提高哈希值计算速度，要尽量降低小密钥长度，常用的密钥变换有“距离变换”和“数据变换”。

Hash函数


4 Hash函数的需求 函数的需求
– H能用于任何大小的数据分组 能用于任何大小的数据分组; 能用于任何大小的数据分组 – H产生定长输出 产生定长输出; 产生定长输出 – 对任意给定的 H(x)要相对易于计算 使得 对任意给定的x, 要相对易于计算,使得 要相对易于计算 软硬件实现都实际可行; 软硬件实现都实际可行 – 对任意给定的码 寻求 使得 对任意给定的码h, 寻求x使得 使得H(x)=h在计算 在计算 上是不可行的(单向性 单向性); 上是不可行的 单向性 – 任意给定分组 寻求不等于 的y, 使得 任意给定分组x, 寻求不等于x的 H(y)= H(x)在计算上不可行 弱抗攻击性 在计算上不可行(弱抗攻击性 在计算上不可行 弱抗攻击性); – 寻求对任何的 寻求对任何的(x,y)对使得 对使得H(x)=H(y)在计算 对使得 在计算 上不可行(强抗攻击性 强抗攻击性); 上不可行 强抗攻击性
Hash函数 散列 哈希函数 函数(散列 哈希函数) 函数 散列,哈希函数
1 Hash函数 函数
– Hash函数是将任意长度的报文映射成一个 函数是将任意长度的报文映射成一个 较短的定长输出报文的函数. 较短的定长输出报文的函数 – 如下形式: h = H(M), M是变长的报文,h是定 如下形式: M是变长的报文 是变长的报文,h是定 长的Hash值. 长的 值 – Hash函数的目的是为文件、报文或其它的 函数的目的是为文件、 函数的目的是为文件 分组数据产生“数字指报文认证的方式 续.) 码提供报文认证的方式(续 码提供报文认证的方式 – (d) A->B: Ek(M || EKRa( H(M) ) )
• 提供认证和数字签名 • 提供保密 仅A和B共享 提供保密(仅 和 共享 共享K)

hash函数的应用原理

Hash函数的应用原理概述在计算机科学中，散列函数（也称为哈希函数）是一种将任意长度的数据映射为固定长度值（通常称为哈希值或散列值）的函数。

Hash函数的应用非常广泛，特别是在数据结构和加密算法中有很多重要的应用。

本文将讨论Hash函数的应用原理以及其在不同领域中的使用。

Hash函数的原理Hash函数的原理非常简单。

它将输入的数据作为原始素材，并对其进行处理，生成一个固定长度的哈希值。

这个哈希值是唯一的，并且当输入的数据发生改变时，哈希值也会随之改变。

Hash函数有以下几个特点： 1. 快速计算：Hash函数需要在有限的时间内生成哈希值，这要求Hash函数具有高效的计算性能。

2. 哈希碰撞概率低：Hash函数应该具备将输入数据均匀分布到哈希值空间中的能力，以降低哈希碰撞（两个不同的输入得到相同的哈希值）的概率。

3. 单向性：Hash函数是一种单向函数，也就是说，可以通过输入来计算哈希值，但无法从哈希值反推出原始的输入数据。

4.输入相同则输出一致：对于相同的输入数据，Hash函数应该始终生成相同的哈希值。

Hash函数的应用示例下面列举了一些Hash函数在不同领域中的应用示例。

数据结构1.散列表（Hash table）：Hash函数被广泛用于实现散列表。

散列表是一种高效的数据结构，它通过Hash函数将关键字映射到数组的索引位置，并在该位置存储对应的值。

数据完整性验证1.文件校验：Hash函数常被用于校验文件的完整性。

将文件的内容作为输入，生成一个哈希值，并将该哈希值与预先计算好的校验和进行比对，以验证文件是否被篡改。

密码存储1.密码加密：Hash函数可以用于对用户密码进行加密存储。

当用户设置密码时，Hash函数将密码作为输入，并生成一个哈希值。

在用户登录时，系统将用户输入的密码再次计算哈希值，与存储的哈希值进行比对，以验证密码的正确性。

数据签名1.数字签名：Hash函数在数字签名中起到重要的作用。

hash函数的主要应用

hash函数的主要应用哈希函数（Hash Function）是一种将任意长度的输入数据映射为固定长度的输出数据的数学函数。

它能够为输入数据生成唯一、固定长度的输出，通常称为哈希值、散列值或摘要。

哈希函数的主要应用包括密码学、数据完整性验证、数据查找和分布式系统等领域。

密码学应用：哈希函数在密码学中广泛应用于密码存储和验证、数字签名、消息认证码等方面。

一种常见的应用是将用户密码的哈希值存储在数据库中，而不是明文密码。

这样即使数据库遭到非法获取，也无法直接获悉用户的密码。

在用户验证过程中，输入的密码与数据库中存储的密码哈希值进行比较，从而验证用户身份。

数据完整性验证：哈希函数在数据完整性验证中扮演重要角色。

通过将文件、文档或消息的哈希值与事先计算得到的哈希值进行比对，我们能够快速检测出任何篡改、修改或数据损坏的情况。

常见的应用包括文件传输时对文件的哈希校验，确保文件在传输过程中没有被篡改；还有数字证书中对公钥进行哈希计算，以提供公钥的完整性验证。

数据查找：哈希函数常被用来加速数据查找的过程。

在哈希表（Hash Table）中，根据键值通过哈希函数计算得到对应的索引位置，从而可以快速地找到对应的数据。

哈希函数将键值映射到一个唯一的哈希码，通过哈希码即可在常数时间内找到存储在哈希表中的数据。

哈希表的应用包括缓存系统、数据库索引和字典等。

分布式系统：在分布式系统中，哈希函数常被用于数据的分布和负载均衡。

通过将数据的关键信息进行哈希计算，将其映射到不同的节点或服务器上进行存储。

这样可以确保数据的均匀分布在整个系统中，避免负载不均衡情况的发生。

哈希函数的应用还包括一致性哈希算法，用于解决节点的动态增减和数据重新分布的问题。

网络安全：哈希函数在网络安全领域也有重要应用，如网络数据包的分析、防火墙和入侵检测系统。

哈希函数可以用来快速计算数据包的哈希值，从而可以实现对网络流量的监控和分析，以检测异常流量和攻击。

此外，哈希函数还能用来加密数据，确保数据在网络传输过程中的保密性和完整性。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

电子科技大学信软学院——现代密码学廖永建Hash 函数的定义
Hash 函数使用方式
Hash 函数满足条件及安全性定义
电子科技大学信软学院——现代密码学廖永建
电子科技大学信软学院——现代密码学廖永建Hash 函数的定义
Hash 函数使用方式
Hash 函数满足条件及安全性定义
电子科技大学信软学院——现代密码学廖永建
电子科技大学信软学院——现代密码学廖永建Hash 函数的定义
Hash 函数使用方式
Hash 函数满足条件及安全性定义
提供认证提供保密
提供认证
提供认证
提供认证提供保密
Bob
提供认证
提供认证提供保密。