消息认证

消息认证 (Message Authentication)：是一个证实收到的消息来自可信的源点且未被篡改的过程。

鉴别的目的

鉴别的主要目的有二：
第一，验证信息的发送者是真正的，而不是冒充的，此为信源识别；
第二，验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等。

鉴别模型

一个单纯鉴别系统的模型

鉴别系统的组成

鉴别编码器和鉴别译码器可抽象为鉴别函数。一个安全的鉴别系统，需满足

1. 接收者能够检验和证实消息的合法性、真实性和完整性
2. 消息的发送者和接收者不能抵赖
3. 除了合法的消息发送者，其它人不能伪造合法的消息

首先要选好恰当的鉴别函数，该函数产生一个鉴别标识，然后在此基础上，给出合理的鉴别协议(Authentication Protocol)，使接收者完成消息的鉴别。

鉴别函数

可用来做鉴别的函数分为三类：

1. 消息加密函数(Message encryption)：用完整信息的密文作为对信息的鉴别。
2. 消息鉴别码MAC(Message Authentication Code)：公开函数+密钥产生一个固定长度的值作为鉴别标识
3. 散列函数(Hash Function)：是一个公开的函数，它将任意长的信息映射成一个固定长度的信息。

加密认证

用完整信息的密文作为对信息的鉴别

对称密码体制加密认证

公钥密码体制加密认证

公钥密码体制加密认证

• 使用公开密钥加密信息的明文只能提供保密而不能提供认证。为了提供认证，发送者A用私钥对信息的明文进行加密，任意接收者都可以用A的公钥解密。
• 采用这样的结构既可提供了认证，也可提供数字签名。因为只有A 能够产生该密文，其它任何一方都不能产生该密文。
  • 从效果上看A 已经用私钥对信息的明文进行了签名。
  • 应当注意只用私钥加密不能提供保密性。因为，任何人只要有A的公开密钥就能够对该密文进行解密。
• 保密性与真实性是两个不同的概念。根本上，信息加密提供的是保密性而非真实性。
• 加密代价大(公钥算法代价更大)。
• 鉴别函数与保密函数的分离能提供功能上的灵活性。
  广播的信息难以使用加密(信息量大)
  某些信息只需要真实性,不需要保密性

消息认证码

带密钥的hash函数

适用于：通信双方基于共享的同一密钥来认证彼此之间交互的信息。

MAC 函数将密钥和数据块作为输入，产生hash值作为MAC码。

设M是变长的消息，K是仅由收发双方共享的密钥，则M的MAC由如下的函数C生成：MAC = Ck(M )
这里的Ck(M )是定长的。发送者每次将MAC附加到消息中，接收者通过重新计算MAC来对消息进行认证。
如果收到的MAC与计算得出的MAC相同，则接收者可以认为：

• 消息未被更改过
• 消息来自与他共享密钥的发送者

MAC函数类似于加密函数，主要区别在于MAC 函数不需要可逆性，而加密函数必须是可逆的，因此认证函数比加密函数更不易破解。

因为收发双方共享相同的密钥，上述过程只提供认证而不提供保密，也不能提供数字签名

MAC的基本用法

HMAC简介

ash函数用来构造MAC：HMAC为其中之一

散列函数：

概念

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

散列函数(又称杂凑函数)是对不定长的输入产生定长输出的一种特殊函数：h = H(M)
其中M是变长的消息
h=H(M)是定长的散列值或称为消息摘要。

散列函数H是公开的，散列值在信源处被附加在消息上，接收方通过重新计算散列值来保证消息未被篡改。

由于函数本身公开，传送过程中对散列值需要另外的加密保护(如果没有对散列值的保护，篡改者可以在修改消息的同时修改散列值，从而使散列值的认证功能失效)。

散列函数的基本用法：消息认证

散列函数的基本用法：数字签名

散列函数的基本用法：其他应用

单向口令文件

入侵检测和病毒检测

构建随机函数或伪随机函数

两个简单的Hash函数

分组对应位异或
移位分组对应位异或

Hash函数的安全需求（重点）

散列函数的目的是为文件、消息或其他的分组数据产生“指纹”。用于消息认证的散列函数H必须具有如下性质：

1. 输入长度可变：H能用于任何大小的数据分组
2. 输出长度固定：H都能产生定长的输出
3. 效率：对于任何给定的x，H(x)要相对易于计算
4. 抗原像攻击：对任何给定的散列码h，寻找x使得H(x)=h在计算上不可行
5. 抗第二原像攻击：对任何给定的分组x，寻找不等于x的y，使得H(x)=H(y)在计算上不可行(弱抗冲突)
6. 抗强抗攻击：寻找任何的(x，y)，使得H(x)=H(y)在计算上不可行(强抗冲突)
7. 伪随机性：H的输入输出满足伪随机性测试标准

散列(Hash)函数的安全性需求

Oscar以一个x开始。首先他计算Z=h(x)，并企图找到一个x’满足h(x’)=h(x)。若他做到这一点，x‘也将为有效。为防止这一点，要求函数h具有无碰撞特性。

• 定义1(弱无碰撞)，散列函数h称为是弱无碰撞的，是指对给定消息x∈X，在计算上几乎找不到不等于x的x’∈X，使h(x)=h(x’)。
• 定义2(强无碰撞)，散列函数h被称为是强无碰撞的，是指在计算上几乎不可能找到任意的相异的x，x’，使得h(x)=h(x’)。
  注：强无碰撞自然含弱无碰撞！

前两条要求具有实用性
第2条和第3条是单向性质，即给定消息可以产生一个散列码，而给定散列码不可能产生对应的消息
第4条性质是保证一个给定的消息的散列码不能找到与之相同的另外的消息，即防止伪造
第6条是对已知的生日攻击方法的防御能力。

散列函数的生日攻击

假定使用64位的散列码，是否安全?

如果采用传输加密的散列码和不加密的报文M，对手需要找到M ‘，使得H(M’)=H(M)，以便使用替代报文来欺骗接收者。
一种基于生日悖论的攻击可能做到这一点。

生日问题：一个教室中，最少应有多少学生，才使至少有两人具有相同生日的概率不小于1/2？

生日问题：
假定一年按365天计算。每人生日在一年365天中的任何一天是等可能的，即都等于1/365
他们生日各不相同的概率为：
365364363…(365-n+1)/365n
因而，n个人中至少有两个人生日相同的概率为：
P = 1 - 365364363…(365-n+1)/365n
若要使P≥0.5，n = 23即可，在64人的班级中，“至少两人生日相同”的概率为0.997（n=46，p>=94.15%)

给定一个散列函数，有n个可能的输出（m位），输出值为H(x)，如果H有k个随机输入，k必须为多大才能使至少存在一个输入y使得H(y)=H(x)的概率大于0.5。
对单个y，H(y) = H(x)的概率为1/n，H(y) ≠ H(x)的概率为1-(1/n)。
如果产生k个随机值y，他们之间两两不等的概率等于每个个体不匹配概率的乘积，即[1-(1/n)]k。
这样，至少有一个匹配的概率为1-[1-(1/n)]k≈1-[1-(k/n)]=k/n。要概率等于0.5，只需k=n/2=2m-1。
对长度为m位的散列码，共有2m个可能的散列码，若要使任意的x，y 有H(x)=H(y)的概率为0.5，只需k=2m/2。

散列函数的结构

由Merkle于1989年提出
Ron Rivest于1990年提出MD4
几乎被所有hash函数使用

具体做法：
把原始消息M分成一些固定长度的块Yi
最后一块padding并使其包含消息M长度
设定初始值CV0
重复使用压缩函数f，CVi = f(CVi-1,Yi-1)
最后一个CVi为hash值

MD5算法、SHA算法

MD5简介

Merkle于1989年提出hash function模型
Ron Rivest于1990年提出MD4
1992年, MD5 (RFC 1321) developed by Ron Rivest at MIT
MD5把数据分成512-bit块
MD5的hash值是128-bit
在最近数年之前，MD5是最主要的hash算法
美国标准SHA-1以MD5的前身MD4为基础
该算法以一个任意长度的报文作为输入，产生一个128bit的报文摘要作为输出。输入是按512bit的分组进行处理的。

MD5算法

MD5小结

MD5使用小数在前
Dobbertin在1996年找到了两个不同的512-bit块，它们在MD5计算下产生相同的hash
MD5不是足够安全的
MD5在线查询破解
http://www.md5.org.cn/
http://www.cmd5.com/
http://md5jiami.51240.com/
MD5的32位和16位加密算法
MD5通常是32位的编码，而在不少地方会用到16位的编码。16位就是从32位MD5散列中把中间16位提取出来。
admin 的摘要：
16位：7a57a5a743894a0e
32位：21232f297a57a5a743894a0e4a801fc3

SHA简介

SHA-512逻辑
步骤1 附加填充位：消息长为模1024与896同余
步骤2 附加长度：最后128位：128位无符号整数表明消息的长度
初始化Hash缓冲区：Hash函数的中间结果和最终结果保存在512位的缓冲区中，缓冲区用8个64位寄存器（a,b,c,d,e,f,g,h）
以1024位的分组（128个字节）为单位处理消息
输出

SHA1算法

SHA Summary

• Applications of cryptographic hash functions
  Message authentication
  Digital signatures
  Other applications
• Requirements and security
  Security requirements for cryptographic hash functions
  Brute-force attacks
  Cryptanalysis
• Hash functions based on cipher block chaining
• Secure hash algorithm (SHA)
  SHA-512 logic
  SHA-512 round function
• SHA-3
  The sponge construction
  The SHA-3 Iteration Function f

数据签名体制

数字签名(Digital Signature)是一种防止源点或终点抵赖的鉴别技术。

消息认证（Message authentication）保护双方之间的数据交换不被第三方侵犯，但它并不保证双方自身的相互欺骗。

假定A发送一个认证的信息给B，双方之间的争议可能有多种形式：
B伪造一个不同的消息，但声称是从A收到的。
A可以否认发过该消息，B无法证明A确实发了该消息。

例如：股票交易指令亏损后抵赖。

数字签名原理

一个数字签名至少应满足以下几个条件：

依赖性：数字签名必须是依赖于要签名报文的比特模式(类似于笔迹签名与被签文件的不可分离性)
唯一性：数字签名必须使用对签名者来说是唯一的信息，以防伪造和否认
可验证：数字签名必须是在算法上可验证的
抗伪造：伪造一个数字签名在计算上不可行，无论是通过以后的数字签名来构造新报文，还是对给定的报文构造一个虚假的数字签名(类似笔迹签名不可模仿性)
可用性：数字签名的产生、识别和证实必须相对简单，并且其备份在存储上是可实现的

数字签名的类别：

以方式分：
直接数字签名direct digital signature
仲裁数字签名arbitrated digital signature

以安全性分
无条件安全的数字签名
计算上安全的数字签名

以可签名次数分
一次性的数字签名
多次性的数字签名

数字签名算法

普通数字签名算法

RSA

A的公钥私钥对{KUa||KRa}
A对消息M签名: SA=EKRa(M)
问题：
速度慢
信息量大
第三方仲裁时必须暴露明文信息
hash函数的无碰撞性保证了签名的有效性

签名与加密

签名提供真实性(authentication)、加密提供保密性(confidentiality)
“签名+加密”提供“真实性+保密性”
两种实现方式： (A→B)

1. 先签名，后加密： EKUb{M||SigA(M)}
2. 先加密，后签名： {EKUb(M)||SigA(EKUb(M))}

方式2的问题：
发生争议时，B需要向仲裁者提供自己的私钥
安全漏洞：攻击者E截获消息，把SigA(EKUb(M))换成SigE(EKUb(M))，让B以为该消息来自E
保存信息多：除了M，SigA(EKUb(M))，还要保存EKUb(M)
∵KUb可能过期

EIGamal

EIGamal签名方案由T.ElGamal于1985年提出，其变体用于DSS中，其安全性依赖于有限域上离散对数的困难性上。
构造参数：
全局参数，p：一个大素数，g：Zp中乘法群Zp的一个生成元。
私钥参数，x：用户的私钥，x∈Zp
公钥参数，y：用户的公钥，y＝gx mod p
算法中常还使用一个随机数k

EIGamal签名方案签名过程

给定要签名的明文M：
生成一个随机数k，k∈Zp*
计算r：r = gk mod p
计算s：s = (H(M) – xr)k-1 mod p – 1，到此，签名结果为(r，s)
把消息和签名结果(M，r，s)发给接收者

EIGamal签名方案认证过程

取得发送方的公钥y；
预查合法性：若1≤r≤p－1，继续；否则，签名不合法
计算v1：v1＝yrrs mod p；
计算v2：v2＝gH(M) mod p；
比较v1和v2 ：如果v1＝v2，表示签名有效；否则，无效

EIGamal签名方案证明：

先对s进行处理，有：
S = (H(M) – xr)k-1 mod p – 1
ks = (H(M) – xr)k-1k mod p – 1 = (H(M) – xr) mod p – 1
H(M) = xr+ks mod p – 1
考察认证过程中的等式v2 = gH(M) mod p
v2 = g xr+ks mod ( p－1) mod p = (g x)r(g k)s mod p
v2 = yrrs mod p
因为v2 = v1所以该算法成立

DSS/DSA

数字签名标准
美国国家标准与技术研究所（NIST）公布的联邦信息标准FIPS186，称为数字签名算法（DSA）。

FIPS186-3的最新版本包括三个算法
DSA
基于RSA的数字签名算法RSA-PSS
椭圆曲线的数字签名算法ECDSA

与RSA不同，DSA算法是一种密钥方案，但不能用于加密或密钥交换。DSA的安全性建立在离散对数的困难性上。

全局公开密钥分量
p：素数，其中2L-1