消息认证方式
(3) 对散列值使用公开密钥密码算法进行加密，并将 结果连接到消息之后，密钥为发送方A私有。
消息认证方式
(4) 通信双方共享一个秘密值S，将S串接到消息头部，然后 计算散列值，该散列值作为消息认证码。
散列算法SHA－1
散列函数的安全要求
1. H能用于任何大小的数据分组能产生定长的输出； 2. 对于任何给定的x， H(x)要相对易于计算； 3. 对任何给定的散列码h 寻找x使得H(x)=h在计算 上不可行（单向性）； 4. 对任何给定的分组x ，寻找不等于x的y ，使得 H(x)=H(y)在计算上不可行（弱抗冲突）； 5. 寻找任何的(x,y) 使得H(x)=H(y)在计算上不可行 (强抗冲突）。
散列算法SHA－1
SHA-1中迭代过程
• 每个循环以当前处理的512比特分组Yq和160比特的缓存值
ABCDE为输入，然后更新缓存的内容，每个循环也使用一 个额外的常数值Kt ，其中0 ≤ t ≤ 79。Kt值用十六进制表示。
散列算法SHA－1
SHA-1中的Wt 产生
• 80个32比特字Wt 的值是通过如下过程由512比特的分组
消息认证方式
(1) 消息经过散列运算后，将散列值连接到消息之后， 然后对所有数据（原消息+对应散列值）使用单钥加 密，密钥为发送方A和接受方B共享，保证消息来自 A并且不被篡改。
消息认证方式
(2) 仅仅对散列值使用对称密码算法加密，并将结果 连接到消息之后，密钥为发送方A和接受方B共享， 保证散列值来自A并且不被篡改 。
消息认证的练习题
Alice希望通过长度为2bit的信息发送单位信息（1或0）给Bob，他 们有4种可能的密钥进行认证，请问： （1） 下表对于A的操作是必需的，请为Bob构造类似的表格用于 认证
（2）攻击者冒充Alice的成功概率是多少？
（3）攻击者对截获的消息进行替代的成功概率是多少？
密钥／消息 1 0 00 1 01
数字签名
• RSA数字签名的安全性质
依赖性。散列函数取得报文的信息摘要，从而使对之 进行加密产生的签名依赖于消息。
唯一性。RSA私钥的保密性使得签名是唯一的。 可验证。Hash函数的输出信息摘要的字节数很少如 SHA的160字节,产生签名相对简单;同样地签名的识别 与证实相对简单。 抗伪造。散列函数的单向性与抗冲突性，还有RSA私 钥的保密性，使得伪造数字签名不可行。
散列算法SHA－1
SHA-1输出（散列值）
• 输出：所有L个512比特的分组处理完成之后，第L
阶段产生的输出便是160比特的报文摘要。
散列算法SHA－1
SHA-1的安全性（和MD5以及 RIPEMD-160的比较）
1. 抗强力攻击的能力：对与弱碰撞攻击这三个算法都是无懈可击 的，MD5 很容易遭遇强碰撞的生日攻击，而SHA-1和 RIPEMD-160目前是安全的*。 2. 抗密码分析攻击的能力：对MD5的密码分析已经取得了很大的 进展，RIPEMD-160 设计时就考虑了抗已知密码分析攻击， SHA-1也有很高的抗密码分析攻击的能力，RIPEMD-160 应该 比SHA-1有更强的抗密码分析攻击的能力。 3. 计算速度：三个算法的主要运算都是模232加法和按位逻辑运算， 因而都易于在32 位的结构上实现，但SHA-1和RIPEMD-160的 迭代次数较多、复杂性较高，因此速度较MD5慢。 4. 存储方式：低位字节优先与高位字节优先都没有明显的优势。 • *2005年山东大学王小云教授给出一种攻击方法，用269次操作可 以找到两个独立的消息使得它们有相同的SHA-1值，而此前认为 需要280的操作。
日攻击的方法无法奏效。
散列算法SHA－1
• 散列函数的安全要求（判断题）
1. 使用接收者的公钥加密信息可以实现信息认证。 2. 消息认证码是在一个公开函数作用下，产生固定 长度的数值作为认证码。 3. 设强抗碰撞的散列函数h(.)可以将任意长的消息 散列成定长的n比特散列值,对于所有的消息x， x’,x≠x’，都有h(x) ≠h(x’). 4. 如果散列函数h(.)是强抗冲突的，那么h(h(.))也是 强抗冲突的。
散列算法SHA－1
• SHA-1中的数据处理框架
处理512比特分组 序列核心是一个包含 四个循环的模块,每个 循环由20个处理步骤 组成,四个循环结构相 似但使用不同的原始 逻辑函数。
散列算法SHA－1
• SHA-1中单个步骤处理过程
A,B,C,D,E←（E+ft(B,C,D)+S5(A)+Wt+Kt),A,S30(B),C,D
• 给定消息M，进行下述工作。 (1) 选择秘密随机数k∈Zp*；
(2) 计算 H(M)；
(3) 计算
• r=gk mod p • s=(H(M)－xr)k--1 mod (p－1) • (r,s)作为数字签名.
2
3 4
10
01 11
00
11 10
数字签名
安全目标
前面介绍的消息认证能保护通信双方以防止第三方的 攻击，却无法防止通信双方的一方对另一方的欺骗，因此除 了认证之外还需要其它机制来防止通信双方的抵赖行为，最 常见的解决方案就是采用数字签名。
数字签名
数字签名的要求
• 传统签名的基本特点: • 能与被签的文件在物理上不可分割 • 签名者不能否认自己的签名 • 签名不能被伪造 • 容易被验证 • 数字签名是传统签名的数字化,基本要求: • 能与所签文件“绑定” • 签名者不能否认自己的签名 • 签名不能被伪造 • 容易被自动验证
散列算法SHA－1
散列函数的安全要求：第二类生日攻击
• （由存在碰撞转化成特定碰撞）
• 敌手对消息M(m比特)产生2m /2个变形，同时准备
一个假冒的M’，并对M’产生2m /2个变形。 • 敌手分别在两个消息集合中找到散列值相同的m1 和m2，概率大于0.5 • 将m1交给A签名，由于m1 和m2的散列值相同，所 以A对两个消息的签名也相同。 • 敌手将此签名和M’一起交给欲接受者。
散列算法SHA－1
散列函数的安全要求：第一类生日攻击
• H有n个输出，H(x)是一个特定的输出，如果对H随
机取k个输入，至少有一个y使H(y)=H(x)的概率为 0.5时，k有多大？
• H(y)=H(x)的概率为1/n，不等的概率为1-(1/n)。取
k个值都不等的为[1-(1/n)]k.至少有一个相等的概率 为1－[1-1/n]k，近似等于k/n。所以概率为0.5，k为 n/2。
数字签名
ElGamal签字体制
参数 • p：一个大素数； • g：是Zp中乘群Zp*的一个生成元或本原元素； • M：消息空间，为Zp*； • S：签字空间，为Zp*×Zp－1； • x：用户私钥x属于Zp*； • y：用户公钥，y＝gx mod p • p，g，y为公钥，x为私钥。
数字签名
ElGamal签名过程
散列算法SHA－1
迭代型散列函数的一般结构
散列算法SHA－1
• SHA－1工作过程示意图
散列算法SHA－1
SHA-1中的数据填充
• SHA-1算法的输入为不超过264比特长的任意消息，
输出为一个160 比特长的消息摘要。输入按512比 特长的分组进行处理处理过程如下： 对消息进行填充在原始的消息后面附加填充比特 串（填充是必须的）,使得数据长度比特数与448 模512同余，填充的比特数规定第1位是1，其余各 位是0；
散列算法SHA－1
SHA-1中的数据预处理
附加消息的长度:用64比特的二进制数表示原始消息的 长度后,所得的64 比特数据附加在第1步所得的数据后 面,高位字节优先; 初始化MD缓存:使用一个160比特的缓存来存放该散列 函数的中间及最终结果,该缓存可以表示为5个32比特 的寄存器,这些寄存器被初始化为以下32比特长的整数 (十六进制表示）: • A=67452301 B=EFCDAB89 C=98BADCFE • D=10325476 E=C3D2E1F0
散列算法SHA－1
发展历史
Ron Rivest于1990 提出了一个称为MD4的散列函数，它的设计 没有基于任何假设和密码体制，这种直接构造方法受到人们的 广泛关注，不久它的一些缺点也被提出。为了增强安全性和克 服MD4的缺陷，Rivest于1991年对MD4 作了六点改进，并将改 进后的算法称为MD5。 MD5曾经是使用最普遍的安全散列算法，然而随着对MD5分析 的深入，从密码分析和强力攻击的角度来看，MD5也被认为是 易受攻击的。 安全散列算法SHA （Secure Hash Algorithm）， 由美国国家标 准和技术协会NIST 提出并作为联邦信息处理标准（FIPS PUB 180 ）在1993年公布。1995年又发布了一个修订版FIPS PUB 180-1 通常称为SHA-1 ，SHA是基于MD4算法的。
散列算法SHA－1
散列函数的安全要求：第一类生日攻击
• 会场参加会议的人中，问使参会人员中至少有两个同
日生的概率超过0.5的参会人数仅为23人。 t个人都不同时生日概率为 至少有两人同日生的概率为 解之，当t＝ 23时，p>0.5。 对于n比特散列值的生日攻击，由上式可计算出，当 进行2n/2次的选择明文攻击下成功的概率将超过0.63。
散列算法SHA－1
• 利用散列函数的HMAC
MAC可用分组加密算法产生， ANSI标准(X9.17): M=(X1,X2,…,Xt)ΔM1=EK(X1), ΔMj+1=EK(Xj+1⊕ΔMj), 1≤j<t 缺点：速度慢，加密算法出口受 限制 hash函数可用来构造MAC: HMAC作为RFC2104并在 SSL中使用
消息认证方式
消息散列码
•
散列函数(又称杂凑函数)是对不定长的输入， 产生定长输出的一种特殊函数h = H ( M )， 其中M是变长的消息，h是定长的散列（码） 值或称为消息摘要，散列函数H 是公开的。 散列值在信源处被附加在消息上。