当前位置：文档之家 › 信息安全原理与实践-第二版05 哈希函数及其他

信息安全原理与实践-第二版05 哈希函数及其他

  • 格式：ppt
  • 大小：1.46 MB
  • 文档页数：40

下载文档原格式

  / 40

合集下载

信息安全原理与实践-第二版01 引言

信息安全原理与实践-第二版01 引言
关的问题
• 什么样的软件缺陷是安全问题，它们又是如何被攻击者利用的？Alice 网银怎么能够确保软件正在正常运行？ • 虽然bug可能(而且也确实会)带来安全缺陷的增加，但这些问题却是善 意的软件开发工程师们在无意之间造成的。另一方面，有些软件在编 写的时候就存有不良企图。 • 操作系统
8
1.3.1 密码学技术
• 密码学技术(或者直白地说“密码”)是基本的信息安全工具之一。密 码学技术的用途非常广泛，能够为机密性、完整性以及许多其他关键 的信息安全功能提供有力的支撑。
主要内容： • 几个经典的密码系统 • 学习现代密码技术：对称密钥密码学和公开密钥密码 • 哈希函数 • 与密码学有关的几个特定议题 • 密码分析，即破解密码系统的方法
9
1.3.2 访问控制
• 访问控制解决的是身份认证和授权的问题。在身份认证领域，我们将 关注许多有关口令的议题，口令是今天最常用的身份认证形式，但这 主要是因为口令的成本低廉，而绝不是因为在诸多选择中这种方式最 为安全。 主要内容： • 如何安全地存储口令 • 口令的替代方案，包括生物特征和智能卡 • 授权 • 多级安全性：隐藏通道和接口控制。 • 防火墙
5
1.2.2 CIA并不是全部
软件层面的信息安全机制
• 在一台独立的计算机上进行身份认证，典型的过程需要验证Bob的口 令。为了确保安全，这会用到密码学领域的一些精巧技术。另一方面， 通过网络的身份认证将打开门户，面对许多类型的攻击，而这些攻击 往往与在一台独立计算机上相对应的那些情形无关。 • 授权就是将约束施加在已认证用户的操作行为上。既然身份认证和授 权都是针对资源访问的问题，那么我们把这两个议题放在“访问控制” 这个标题下统一讨论。 • 授权就是将约束施加在已认证用户的操作行为上。既然身份认证和授 权都是针对资源访问的问题，那么我们把这两个议题放在“访问控制” 这个标题下统一讨论。这就涉及到授权和访问控制的问题。

哈希函数.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算法实验原理及哈希函数简介

任务一 MD5算法111111*********一．哈希函数简介信息安全的核心技术是应用密码技术。

密码技术的应用远不止局限于提供机密性服务,密码技术也提供数据完整性服务。

密码学上的散列函数(Hash Functions)就是能提供数据完整性保障的一个重要工具。

Hash函数常用来构造数据的短“指纹”：消息的发送者使用所有的消息产生一个附件也就是短“指纹”，并将该短“指纹”与消息一起传输给接收者。

即使数据存储在不安全的地方，接收者重新计算数据的指纹，并验证指纹是否改变，就能够检测数据的完整性。

这是因为一旦数据在中途被破坏，或改变，短指纹就不再正确。

散列函数是一个函数，它以一个变长的报文作为输入，并产生一个定长的散列码，有时也称为报文摘要，作为函数的输出。

散列函数最主要的作用于是用于鉴别，鉴别在网络安全中起到举足轻重的地位。

鉴别的目的有以下两个：第一，验证信息的发送者是真正的，而不是冒充的，同时发信息者也不能抵赖，此为信源识别；第二，验证信息完整性，在传递或存储过程中未被篡改，重放或延迟等。

二．哈希函数特点密码学哈希函数（cryptography hash function，简称为哈希函数）在现代密码学中起着重要的作用，主要用于对数据完整性和消息认证。

哈希函数的基本思想是对数据进行运算得到一个摘要，运算过程满足：z压缩性：任意长度的数据，算出的摘要长度都固定。

z容易计算：从原数据容易算出摘要。

z抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的摘要都有很大区别。

z弱抗碰撞：已知原数据和其摘要，想找到一个具有相同摘要的数据（即伪造数据），在计算上是困难的。

z强抗碰撞：想找到两个不同的数据，使它们具有相同的摘要，在计算上是困难的。

三．针对哈希函数的攻击与传统密码体制的攻击方式相比，对散列函数的攻击方法主要有两种：z穷举攻击：它可以用于任何类型的散列函数的攻击，最典型的方式就是所谓的“生日攻击”。

Hash函数在信息安全中的重要运用

Hash函数在信息安全中的重要运用

封面作者：PanHongliang仅供个人学习Hash函数在信息安全中的重要运用学号：09008010124姓名：罗杨摘要：随着计算机和Internet在各行各业的广泛应用，信息高速化的交互传递过程中，信息安全问题备受关注。

而基于hash函数的各种算法的产生和运用，为信息上一把牢固的安全之锁，md5、sha-1文件校验，加密存储，数字签名，PKI建设等对各种信息有充分的安全保障，能有效地防止攻击，保证真实信息不被修改或者泄露。

关键词：哈希 hash md5 数字签名 PKI 散列校验公钥私钥一、定义Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。

这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。

简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里，叫做Hash值。

二、算法举例1、MD4MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是Message Digest 的缩写。

它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。

MD4散列的例子：MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729dMD4 ("message digest") = d9130a8164549fe818874806e1c7014b2、MD5MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。

信息安全原理与技术(第2版)部分试题及答案

信息安全原理与技术(第2版)部分试题及答案

《信息安全原理与技术》第2版部分习题与参考答案选择题1.如果m表示明文,c表示密文,E代表加密变换,D代表解密变换,则下列表达式中描述加密过程的是( A )A、c=E(m)B、c=D(m)C、m=E(c)D、m=D(c)2.将获得的信息再次发送以在非授权情况下进行传输，这属于（D ）A 窃听B篡改C 伪装D 重放3. DES加密过程用以下形式交换，其中正确的是( B )A、L i-1=R i-1R i-1=L i-1⊕f(R i,K i) i=1,2,3, (16)B、L i=R i-1R i=L i-1⊕f(R i-1,K i) i=1,2,3, (16)C、L i-1=R i+1 R i=L i+1⊕f(R i-1,K i) i=1,2,3, (16)D、L i-1=R i-1R i=L i+1⊕f(R i-1,K i) i=0,1,2,3, (15)4. 在不知道密钥的情况下，通过获取密文而恢复明文的方法是。

（ C ）A、密钥管理B、数据加密解密算法C、密码分析D、密码编码5. RSA属于（ B ）A、传统密码体制B、非对称密码体制C、现代密码体制D、对称密码体制6.下面哪个加密算法被选为AES( B )A MARSB RijndaelC TwofishD E27. AES中输入密钥扩展为44个字所组成的数组，每一轮有4个字的密钥，这里一个字的位数是（ C ）A、8B、16C、32D、648. DES中子密钥的位数是（ B ）A、32B、48C、56D、649. 如果使用两密钥的Triple-DES，则下面正确的是（A ）A C = E K1[D K2[E K1[P]]]BC = E K1[E K2[E K1[P]]]C C = E K3[D K2[E K1[P]]] D C = E K1[D K2[D K1[P]]]答案：ADBCB BCBA1. DES中如果S盒输入为110011，则对应输入位置为（ B ）A、第2行第9列B、第4行第10列C、第3行第10列D、第3行第11列2. 密码编码学的目的是（ A ）A．伪装信息B．破译加密消息C．窃取信息 D．密码分析3. 每次加密一位或者一个字节是（ B ）A、离散密码B、流密码C、随机密码D、分组密码4. 在下列密码体制中，加密密钥k1 解密密钥k2 是相同的。

哈希函数的原理及应用

哈希函数的原理及应用

哈希函数的原理及应用哈希函数是将输入数据映射到固定长度的输出数据的一种函数。

它具有以下几个特点：确定性、高效、不可逆和均匀分布。

哈希函数的原理基于数学原理和位运算。

它将输入数据通过一系列操作转化为固定位数的哈希值。

哈希函数的设计要考虑尽量减小冲突的概率，即不同的输入数据得到相同的哈希值的概率尽量低。

常见的哈希函数有MD5、SHA-1和SHA-256等。

1.数据完整性验证：哈希函数常被用来验证数据在传输过程中是否被篡改。

发送方可以计算出数据的哈希值并一并发送给接收方。

接收方在接收到数据后重新计算哈希值并与发送方发送的哈希值进行比对，如果不一致则说明数据被篡改过。

2.数据加密：哈希函数是密码学中不可或缺的组成部分。

通过哈希函数，可以将明文消息转换为不可逆的哈希值，从而保护消息的机密性。

常用的密码哈希函数有MD5和SHA系列。

3.密码存储与验证：在用户注册和登录认证等场景中，哈希函数常被用来存储和验证用户密码。

通常使用带有“加盐”的哈希函数来存储用户密码，以增加密码的安全性。

4.唯一标识符生成：哈希函数可以将大范围的输入数据映射为固定长度的哈希值。

这种特性使得它可以用来生成唯一的标识符，如文件的唯一标识符、URL的短链接等。

5.数据分片与散列存储：哈希函数可以将大数据集分割成小数据块并散列存储。

这样做既能减少存储空间的占用，又能提高数据的检索效率。

例如，分布式存储系统中常用的一致性哈希算法就是通过哈希函数将数据分布到不同的节点上。

6.布隆过滤器：布隆过滤器是一种基于哈希函数的数据结构，用于快速判断一些数据是否属于集合中。

布隆过滤器通过哈希函数将元素映射到一个位向量中，并用多个不同的哈希函数来减小冲突的概率，从而提高查询效率。

总的来说，哈希函数是一种非常重要的技术，广泛应用在数据完整性验证、数据加密、标识符生成、数据存储和检索等领域。

在实际应用中，我们需要选择合适的哈希函数来满足我们的需求，并注意哈希函数的安全性和冲突概率。

哈希函数的工作原理及应用

哈希函数的工作原理及应用1. 哈希函数是什么？哈希函数（Hash Function）是一种将任意输入数据映射到固定大小的输出值的算法。

它的主要作用是将任意长度的输入转换为固定长度的哈希值，通常是一个较短的字符串。

哈希函数是一种单向函数，即无法通过哈希值逆向推导出原始输入数据。

2. 哈希函数的工作原理哈希函数的工作原理可以简单概括为以下几个步骤：2.1. 输入处理哈希函数接收一个输入数据，并对其进行处理。

输入数据可以是任意长度的字节流，例如一段文字、文件内容等。

2.2. 算法运算哈希函数使用特定算法对输入数据进行运算，以生成一个固定长度的哈希值。

常用的哈希算法有MD5、SHA-1、SHA-256等。

2.3. 哈希值输出哈希函数将计算得到的哈希值输出，通常是一个较短的字符串。

哈希值具有以下特点：•固定长度：无论输入数据的长度如何，哈希值的长度是固定的。

•唯一性：不同的输入数据经过哈希函数计算得到的哈希值几乎是唯一的。

•高度离散性：输入数据的微小变化会导致哈希值产生较大的变化。

2.4. 校验和与冲突校验和是哈希函数的一个重要应用，用于验证数据的完整性。

通过计算输入数据的哈希值，并与预先计算好的校验和进行比较，可以判断数据是否被篡改。

然而，由于输入数据的长度可能远大于哈希值的长度，哈希函数的输出空间有限，难免会出现哈希冲突的情况，即不同的输入数据计算得到相同的哈希值。

针对哈希冲突，常见的解决方法包括拉链法、开放定址法等。

3. 哈希函数的应用哈希函数在计算机科学和密码学领域有广泛的应用，以下是一些常见的应用场景：3.1. 数据完整性校验哈希函数常用于验证数据的完整性。

发送方计算数据的哈希值，并将其附加到数据中一起发送。

接收方收到数据后，重新计算哈希值，并与发送方传递的哈希值进行比较，从而判断数据是否在传输过程中被篡改。

3.2. 数据加密哈希函数在密码学中被广泛用于数据加密。

将敏感数据通过哈希函数进行加密，可以将数据转化为一串乱码，提供一定的数据保护。

第五章 信息安全原理与技术ch05-Hash函数和数字签名


攻击者可以按此方法不时对密钥停止测试，直到将 婚配数缩写到足够小的范围。平均来讲，假定 k=a n,那么需a次循环
2021/7/25
Ch5-音讯认证与数字签名
针对MAC算法的攻击
• 攻击者针对下面的MAC算法，那么不需求运用穷举攻击 即可取得密钥信息。
• 设音讯M＝(X1||X2||…||Xm)，即由64位分组Xi结合而成。 定义
2021/7/25
Ch5-音讯认证与数字签名
Yuval的生日攻击〔续〕
• (3) 攻击者在上述两个音讯集合中找出可以发生 相反散列值的一对音讯。依据〝生日悖论〞实际， 能找到这样一对音讯的概率是十分大的。假设找 不到这样的音讯，攻击者再发生一条有效的音讯 和伪造的音讯，并添加每组中的明文数目，直至 成功为止。
• 伪装：攻击者生成一个音讯并宣称这条 音讯是来自某合法实体，或许攻击者冒 充音讯接纳方向音讯发送方发送的关于 收到或未收到音讯的欺诈应对。
• 内容修正：对音讯内容的修正，包括拔 出、删除、转换和修正。
• 顺序修正：对通讯双方音讯顺序的修正， 包括拔出、删除和重新排序。
• 计时修正：对音讯的延迟和重放。在面
满足H(m) = h的m在计算上是不可行的； • 给定Hash函数的描画，关于给定的音讯m1，找到满
足m2 m1且H(m2)=H(m1)的m2在计算上是不可行 的； • 找就任何满足H(m1)=H(m2)且m1 m2的音讯对 (m1, m2)在计算上是不可行的。
2021/7/25
Ch5-音讯认证与数字签名
Ch5-音讯认证与数字签名
认证的目的
• 可提招认证功用的认证码的函数可分为 三类：
• 加密函数：运用音讯发送方和音讯接纳 方共享的密钥对整个音讯停止加密，那 么整个音讯的密文作为认证符。

信息安全原理与实践教程第5章

置了。
PPT文档演模板
信息安全原理与实践教程第5章
④ 方法4：DOS下破解。该方法直接在 MS-DOS 环境下 便可完成，在MS-DOS环境下输入：“COPY CON ”后按【回车】键，继续输入如下十个字符： “ALT+176 ALT+17 ALT+230 p ALT+176 ALT+20 ALT+230 q ALT+205”，再按【空格】键，然后按【F6】键，再按【回 车】键保存，运行文件后，重新开机即可。
注：“用户密码”的权限低于“管理员密码”。
PPT文档演模板
信息安全原理与实践教程第5章
2) BIOS密码的破解 如果遗忘了BIOS密码该怎么办呢？有以下几种方法可以 解决这个问题。对于用户设置的这两种密码，破解方法是有 所区别的。
(1) 破解“USER PASSWORD”。 ① 方法1：Debug法。其原理是：通过向CMOS芯片写入 数字导致开机检测时无法通过其奇偶校验，从而CMOS芯片 恢复出厂设置，实现清除BIOS密码的目的。具体操作步骤如 下：
AWI BIOS的通用密码有：AMI、BIOS、PASSWORD、
HEWITT RAND、AMI_SW、LKWPETER、A.M.I。
PPT文档演模板
信息安全原理与实践教程第5章
② 方法2：CMOS 放电。目前的主板大多数使用纽扣电 池为BIOS提供电力，也就是说，如果没有电，其中的信息就 会丢失了。再次通电时，BIOS就会回到未设置的原始状态， 当然BIOS密码也就没有了。
PPT文档演模板
信息安全原理与实践教程第5章
打开电脑机箱，找到主板上银白色的纽扣电池并小心将 它取下，再把机箱尾部电源插头拔掉，用金属片短接电池底 座上的弹簧片，大概30秒后，再将电池装上。此时，CMOS 会因断电而失去内部储存的信息。再开机时，系统就会提示 “CMOS Checksum Error-DeFaults Loaded”，即提示CMOS在 检查时发现了错误，已经载入了系统的默认值，BIOS密码破 解成功。

harsh函数-概述说明以及解释

harsh函数-概述说明以及解释1.引言1.1 概述概述部分的内容可以描述一下harsh函数是什么以及它的重要性和作用。

可以参考以下内容：概述：随着计算机科学的快速发展，数据安全和隐私保护变得尤为重要。

在这个数字化时代，我们需要一种可靠的方法来保护数据的完整性和安全性。

在这方面，hash函数扮演着至关重要的角色。

Hash函数是一种常见的密码算法，主要用于将数据转换为固定长度的字符串。

它通过对任意长度的数据应用哈希算法，生成一个唯一的哈希值。

这个哈希值可以用来验证数据的完整性，检测数据的变化和确定数据的唯一性。

在hash函数的世界里，harsh函数是一种特殊类型的hash函数，它具有许多独特的特点和优势。

与传统的hash函数相比，harsh函数不仅具有更高的效率和更低的冲突率，还可以提供更好的数据安全性和隐私保护。

harsh函数的工作原理是将输入数据通过一系列复杂而精确的计算，转换为一个唯一的哈希值。

这个哈希值具有不可逆的特性，即无法通过哈希值来恢复原始数据。

这种不可逆的特性使得harsh函数成为密码学中重要的工具，广泛应用于数字签名、数据验证、身份验证等各个领域。

此外，harsh函数还具有较低的碰撞概率，即不同的输入数据生成相同哈希值的概率非常低。

这使得harsh函数在数据完整性验证等关键应用场景中更加可靠。

另外，harsh函数还具有良好的计算性能和效率，使得它能够承担大规模数据处理的任务。

总的来说，harsh函数在确保数据安全性和完整性方面发挥着重要作用。

它的独特特性使其在各个领域得到广泛应用，同时也推动了数据安全和密码学的发展。

未来，随着计算机技术的不断进步，人们对于更加高效和安全的harsh函数算法的需求也将不断增加。

1.2文章结构文章结构部分的内容可以描述整篇文章的组织架构和章节安排：在本文中，我将按照如下结构来阐述关于harsh函数的相关知识。

首先，我将在引言部分进行概述，简要介绍harsh函数的定义、背景和应用领域。

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

1 365/ 365 364 / 365 363/ 365 (365 N 1) / 365
设置这个表达式等于1/2，并解出N，我们得到N = 23
生日 悖论
8
• 延伸
对于一个生成N位二进制长度输出的安全哈希函数来说，一个计算开 销大约以2N /2为因子的强力破解方式，就能够对其发起有效的攻击。 相比较而言，对于一个密钥长度为N位二进制数的安全对称密钥加密 方案来说，对其强力破解的计算开销的因子是2N-l。 所以，安全哈希函数的输出必须是对称加密密钥二进制位数的大约两 倍长，才能够获得与后者基本相当的安全水平。
•
• • •
4
哈希函数在数字签名上的应用 • 以前
Alice对一条消息M实施签名，是通过使用她自己的私钥进行“加密”计算得到的，即要计 算S = [M]Alice。如果Alice发送消息M和签名S给Bob，Bob就能够通过执行验证过程M = {S}Alice来验证该签名的有效性。但是，如果消息M很大，[M]Alice就是一个成本很高的计算， 更不用提发送消息M和签名S的带宽需求了，这两者都会很大。相比之下，在计算一个MAC 时，加密的速度会很快，而且在发送时，我们也仅仅需要伴随着消息发送少量附加的校验 位(比如MAC)而已。
• •
• •
10
• 在这个攻击中，Trudy获得了Alice对于一条Trudy自选消息的签名，但 是并没有以任何方式攻击潜在的公开密钥加密系统。 • 这个攻击是一个针对哈希函数h的强力攻击，而哈希函数h是用于计算 数字签名的。 • 为了防止此类攻击，我们可以选择一个哈希函数，使得该哈希函数的 输出值的长度n足够大，以至于Trudy无法完成2n/2个哈希值的计算。
3
5.2 什么是加密哈希函数
一个加密哈希函数h(x)，必须满足下列所有条件：
• 压缩——对于任何长度的输入值x，输出值y = h(x)的长度都比较小。在实际使 用中，通常输出值是固定长度的(比如160位长度的二进制值)，而无论输入值 的长度是多少。 高效——对于任何的输入值x，必须能够很容易地计算出h(x)。当然，伴随着 输入值x的长度增加，计算h(x)所需要的计算量也会随之增加，但是，这不能 增长得太快。 单向——给定任意值y，要想找到一个值x，使得h(x) = y，将是计算不可行的 。换一种不同的说法，即对于哈希运算，没有行之有效的逆运算。 抗弱碰撞性——给定x和h(x)，要想找到任意y，满足y≠x，并且h(y) = h(x)，这 是不可能的。 抗强碰撞性——要想找到任意的x和y，使得x≠y，并且h(x) = h(y)，这是不可 能的。也就是说，我们不能够找到任何两个输入，使得它们经过哈希后会产 生相同的输出值。
5
签名的正确方法
• 假设没有碰撞，那么对h(M)签名和对消息M实施签名的效果一样好。 事实上，对哈希值实施签名比起仅仅对消息本身实施签名，实际上会 更加安全。 • 现在数字签名的安全性不仅依赖于公钥系统的安全性，而且也依赖于 哈希函数本身的安全性——如果二者中有任何一个比较弱，签名体制 就可能会被破解。
1 (364 / 365) N
设置这个表达式等于1/2，并解出N，得到N = 253。
7
• 真正的生日问题
我们给房间里的N个人分别编上号码1，2，3，…，N。编号为1的人的生 日是一年365天中的一天。如果所有人的生日各不相同，那么编号为2的 人必须与编号为1的人的生日不相同，也就是说，编号为2的人的生日只 能是剩余的364天中的任意一天。同样，编号为3的人的生日只能是再剩 余的363天中的任意一天，依此类推。假设所有的生日都是概率相等的， 考虑上述情况的补集，其最后的概率计算如下式所示
6
5.3 生日问题
假如你和其他N个人同在一个房间里。那么，N必须多大，你才有指望找 到至少一个人和你有相同的生日呢？或者说：N必须多大，才会使得“有 某个人与你生日相同”的概率大于1/2呢？
你的生日是在一年中特定的一天。如果一个人和你的生日不同，那么他 或她的生日必定是在其他364天中的一天。假设所有的生日都是概率相等 的，那么“一个随机选择的人不与你的生日相同”的概率就是364/365。 这样，所有的N个人都跟你的生日不同的概率就是(364/365)N，于是，至 少有一个人与你的生日相同的概率就是：
15
Tiger算法的过程 • 首先对输入值X进行附加填充位，使其长度满足512位二进制长的倍数， 表示为： X=(X ,X ,...,X ) ，其中每一个Xi都是一个512位二进制长的分组。 • 对每一个Xi使用一个外层的轮运算。假设a，b和c都是64位二进制长的 值。对于第一轮运算，(a, b, c)的初始值以16进制形式表示如下：
19
• 小结
fm,i由下式给定：
•
每一个Si都是一个S-box(即查找表)，将8位二进制映射为64位二进制。
18
密钥调度算法 • 假设令W为密钥调度算法的512位二进制输入值。同上，我们将W写作 W= (w0, w1,…, w7)，其中每一个wi都是一个64位二进制值，我们再令 为wi的二进制补数。 • 密钥调度算法如下，其中最后的计算结果W= (w0, w1,…, w7)给出了该 算法的输出值。Βιβλιοθήκη 115.5 非加密哈希
非加密哈希运算的例子
X ( X 0 , X1, X 2 ,..., X n 1 )
（1）其中，每个Xi是一个字节，定义哈希函数h(X)为：
h X ( X 0 X1 X 2 ... X n 1 ) mod 256
这毫无疑问提供了压缩功能，因为任何长度的输入都被压缩为8位二进制的输出。但是，这 个哈希很容易被破解，因为生日问题的结论告诉我们，只需对24 = 16个随机选择的输入执 行哈希运算，我们就有望找到一个碰撞。 对两个字节进行互换，就总是能够产生一个碰撞，类似如下这种情况：
• 使用哈希函数之后
假设Alice有一个加密哈希函数h。那么，h(M)可以被看做文档M的一个“指纹”，也就是说， h(M)比M小得多，但是它能够标识出M。如果M'不同于M，那么即使仅仅相差一个单独的二 进制位，哈希函数执行的结果也几乎肯定会不同。而且，哈希函数的抗碰撞特性意味着， 想要将消息M替换为任何不同的消息M'，使得h(M) = h(M')是不可能的 1. 一旦哈希值发生相 同的情况，该怎么办呢？好的，这说明你已经发现了一个碰撞，也就意味着你已经攻破了 这个哈希函数，于是你就成为一个著名的密码破解专家了。所以，这是个双赢的好事。
例子 假设给定的除数是10011，而有趣的是数据恰好是10101011。那么，我们先对数 据附加上4个0(附加的位数要比除数的二进制位数少1)，然后执行如下长除法运算：
CRC校验和就是长除法运算的余数——在这个例子中，就是1010。
13
5.6 Tiger Hash
• MD5
MD指的是消息摘要(Message Digest)，它的前身是MD4，而MD4本身又 继承自MD2。 所有的MD系列算法都是由加密领域的大师级人物Ron Rivest所发明。 MD5算法生成128位的输出值。
W=(w0 ,w1,...,w7 )
17
• 对于函数fm,i，当i = 0,1,2, ... ,7时，其各自的输入值分别如下
其中各自对应的函数fm,i-1的输出标记为(a, b, c)。每一个fm,i都依赖于a，b，c， wi和m，其中wi是512位二进制输入值W的第i个64位子分组。
• c写作： c (c0 ,c1,...,c7 ) ，其中每一个ci都是一个单独的字节。
Information Security: Principles and Practice, 2nd Edition [美]Mark Stamp 张 戈 著 译
1
第5章 哈希函数及其他
2
5.1 引言
本章内容 • 加密哈希函数 • 加密哈希函数的标准应用 • 哈希函数的高级应用 • 加密相关的副作用问题
14
Tiger算法特点
算法的输入先被分成512位二进制长度的分组，如果需要的话，就对输入 值进行附加填充位，以补足成512的倍数位的长度。 算法输出192位二进制长度的哈希值。 算法实现中使用了4个S-box，这4个S-box的每一个都将8位二进制位映射 为64位。 算法还使用了一个“密钥调度”的算法，不过由于这里没有密钥的概念， 该算法实际是施加到了输入分组上。
h(00000001, 00001111) h(00000000,00010001) 00010001
12
循环冗余校验，或简称为CRC
• • 循环冗余校验码的计算本质上是长除法，将余数作为CRC计算的“哈希”值。 与常规的长除法不同，CRC在计算中使用XOR运算替代了减法。 在一个CRC的计算过程中，除数被指定作为算法的一部分，数据作为被除数。
• SHA-1算法
SHA表示安全哈希算法(Secure Hash Algorithm)，是美国政府的一个标准。 SHA-1算法实际上非常类似于MD5算法。两个算法在实践中的主要不同在 于SHA-1生成160位二进制长的输出值，比MD5提供了更可观的安全边际。 所谓雪崩效应，是所有加密哈希函数都会追求的一个理想特性。其目标是：在 输入值中任何小的变化，都应该级联传递并导致输出结果较大的变化——就像 雪崩一样。理想情况下，任何输入值的变化引发的输出值变化都是不相关的， 这样，攻击者将不得不实施穷举式检索来寻找碰撞。
h(10101010,00001111) = h(00001111,10101010) = 10111001
（2）我们将哈希函数h(X)定义为：
h X (nX 0 (n 1) X1 (n 2) X 2 ... 2X n 2 X n 1 ) mod 256
虽然该函数在交换输入字节顺序的情况下能够输出不同的结果，但是仍然逃不过生日问题 带来的麻烦。