E-mail: hjbin@infosec.pku.edu.cn 密码学基础（3） 胡建斌 北京大学网络与信息安全研究室 E-mail: hjbin@infosec.pku.edu.cn http://infosec.pku.edu.cn/~hjbin

目 录 消息鉴别与散列函数 散列算法 数字签名

消息鉴别与散列函数 Message Authentication and Has Functions

网络通信的攻击威胁 泄露：把消息内容发布给任何人或没有合法密钥的进程 流量分析：发现通信双方之间信息流的结构模式，可以用来确定连接的频率、持续时间长度；还可以发现报文数量和长度等 伪装：从一个假冒信息源向网络中插入消息 内容篡改：消息内容被插入、删除、变换、修改 顺序修改：插入、删除或重组消息序列 时间修改：消息延迟或重放 否认：接受者否认收到消息；发送者否认发送过消息

鉴别和认证 鉴别：authentication 真伪性 认证：Certification 资格审查 (1) A process used to verify the integrity of transmitted data, especially a message 用来验证发送的数据,特别是一个信息的完整性的过程 (2) The act of establishing the identity of users when they start to use the system 在用户开始使用系统时对其身份进行的确认 认证：Certification 资格审查 In computer security, the technical evaluation made as part of and in support of the accreditation process, that established the extent to which a particular computer system or network design and implementation meet prespecified security requirements 计算安全学用语,指为了鉴定一个计算机系统或网络的设计和它提供的手段在多大程度上能满足预定的安全要求而进行的技术评估

鉴别的结构 任何消息认证或数字签名机制可以看到两个层次： 底层必须有某种函数产生一个认证标识：一个用于认证一个报文的值 高层认证协议以底层函数为原语，使接收者完成报文的鉴别

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

鉴别模型

鉴别系统的组成 鉴别编码器和鉴别译码器可抽象为鉴别函数 一个安全的鉴别系统，需满足 （1）指定的接收者能够检验和证实消息的合法性、真实性和完整性 （2）消息的发送者和接收者不能抵赖 （3）除了合法的消息发送者，其它人不能伪造合法的消息

鉴别函数分类 消息加密：整个消息的密文作为认证标识 消息鉴别码(MAC)：公开函数+密钥产生一个固定长度的值作为认证标识 散列函数：一个公开函数将任意长度的消息映射到一个固定长度的哈希值，作为认证标识

鉴别函数分类 消息加密：整个消息的密文作为认证标识 消息鉴别码(MAC)：公开函数+密钥产生一个固定长度的值作为认证标识 散列函数：一个公开函数将任意长度的消息映射到一个固定长度的哈希值，作为认证标识

消息加密

对称加密－保密和鉴别 B A

对称加密－保密和鉴别

明文M的自动确定 M定义为有意义的明文序列，便于自动识别 强制定义明文的某种结构，这种结构是易于识别但又不能复制且无需借助加密的 可以在加密前对每个报文附加检错码，即所谓的帧检验序列号或检验和FCS 内部差错控制和外部差错控制

差错控制 更难于构造

公钥加密－保密性 B A

公钥加密－鉴别和签名 B A

公钥加密－保密、鉴别和签名 B A

消息鉴别码 MAC

消息鉴别码 使用一个密钥生成一个固定大小的小数据块，并加入到消息中，称MAC， 或密码校验和（cryptographic checksum） 2、接收者可以确信消息来自所声称的发送者 3、如果消息中包含顺序码（如HDLC,X.25,TCP），则接收者可以保证消息的正常顺序 MAC函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少

消息鉴别 B A

消息鉴别与保密，鉴别与明文连接 B A

消息鉴别与保密，鉴别与密文连接 B A

消息鉴别 VS 常规加密 保密性与真实性是两个不同的概念 根本上,信息加密提供的是保密性而非真实性 加密代价大(公钥算法代价更大) 鉴别函数与保密函数的分离能提供功能上的灵活性 某些信息只需要真实性,不需要保密性 – 广播的信息难以使用加密(信息量大) – 网络管理信息等只需要真实性 – 政府/权威部门的公告

散列函数 Hash Function

散列函数 H(M): 输入为任意长度的消息M; 输出为一个固定长度的散列值，称为消息摘要(MessageDigest） H(M)又称为：哈希函数、数字指纹（Digital finger print)、压缩（Compression)函数、数据鉴别码（Dataauthentication code）等

散列函数基本用法(1)

散列函数基本用法(2)

散列函数基本用法(3)

散列函数基本用法(4)

散列函数基本用法(5)

散列函数基本用法(6)

消息鉴别码 MAC

K M MAC 函数域：任意长度的报文 值域：所有可能的MAC和所有可能的密钥 MAC一般为多对一函数

对MAC的强行攻击 函数域：任意长度的报文 值域：所有可能的MAC和所有可能的密钥 假设

对MAC的强行攻击 假设 假设攻击者已经获得报文的明文和相应的MAC,即

对MAC的强行攻击

对MAC的强行攻击 如果 k≤n，则第一轮就可以产生一个唯一对应。仍然可以有多于一个key产生这一配对，这时攻击者只需对一个新的(message, MAC)进行相同的测试 由此可见，强力攻击企图发现authentication key不小于甚至大于对同样长度的解密key的攻击

对MAC的其它攻击 设M = (X1 || X2 || … || Xm) 是一个由64位Xi数据块连接而成 定义 CK(M) = EK[(M)] 其中  为异或操作；E为 ECB工作模式的DES算法 则 Key length = 56 bit MAC length = 64 bit 强力攻击需要至少256次加密来决定K

对MAC的其它攻击 设 M’ = ( Y1 || Y2 || … || Ym-1 || Ym) 其中 Y1, Y2, …, Ym-1是替换 X1, X2,…,Xm-1的任意值，而 Ym = Y1Y2 , …,  Ym-1  (M) 则 CK(M’) = EK[(M’)] = EK[Y1Y2 , …,  Ym-1  Ym ] = EK[Y1Y2 , …,  Ym-1  (Y1Y2 , …,  Ym-1  (M)) ] = EK[(M)] 这时消息M’ 和 MAC= CK(M) = EK[(M)]是一对可被接收者认证的消息 用此方法，任何长度为64(m-1)位的消息可以被插入任意的欺骗性信息

MAC应具备的性质 如果一个攻击者得到M和CK(M)，则攻击者构造一个消息M’使得CK(M’)=CK(M)应具有计算复杂性意义下的不可行性 CK(M)应均匀分布，即：随机选择消息M和M’， CK(M)= CK(M’)的概率是2-n，其中n是MAC的位数 令M’为M的某些变换，即：M’=f(M)，（例如：f可以涉及M中一个或多个给定位的反转），在这种情况下，Pr[CK(M)= CK(M’)] = 2-n

基于DES的报文鉴别码

基于DES的报文鉴别码 算法来源 使用CBC(Cipher Block Chaining)方式，初始向量为IV=0 FIPS publication (FIPS PUB 113) ANSI standard (X9.17) 使用CBC(Cipher Block Chaining)方式，初始向量为IV=0

基于DES的报文鉴别码 算法来源 使用CBC(Cipher Block Chaining)方式，初始向量为IV=0 FIPS publication (FIPS PUB 113) ANSI standard (X9.17) 使用CBC(Cipher Block Chaining)方式，初始向量为IV=0

基于DES的报文鉴别码 O1 = EK(D1) O2 = EK(D2O1) O3 = EK(D3O2) … 将数据按64位分组，D1, D2, … , DN，必要时最后一个数据块用0向右填充 运用DES算法E，密钥K 数据认证码(DAC)的计算如下： O1 = EK(D1) O2 = EK(D2O1) O3 = EK(D3O2) … ON = EK(DNON-1)

FIPS PUB 113

目 录 消息鉴别与散列函数 散列算法 数字签名

散列函数

散列函数的定义 散列函数： M:变长报文 H(M):定长的散列值 主要用于为文件、报文或其它分组数据产生指纹

散列函数的要求 H能用于任意大小的分组 H能产生定长的输出 对任何给定的x，H(x)要相对易于计算，使得硬件和软件实现成为实际可能 对任何给定的码h，寻找x使得H(x)=h在计算上是不可行的，即单向性 对任何给定的分组x，寻找不等于x的y，使得H(x)=H(y)在计算上是不可行的，即弱抗冲突性 寻找对任何的(x,y)对使得H(x)=H(y)在计算上是不可行的，即强抗冲突性

Hash vs MAC MAC需要对全部数据进行加 MAC速度慢 Hash是一种直接产生鉴别码的方法

Hash函数通用结构 由Ron Rivest于1990年提出MD4 几乎被所有hash函数使用 具体做法: – 把原始消息M分成一些固定长度的块Yi – 最后一块padding并使其包含消息M长度 – 设定初始值CV0 – 压缩函数f, CVi=f(CVi-1,Yi-1) – 最后一个CVi为hash值

MD5

MD5描述 Merkle于1989年提出hash function模型 Ron Rivest于1990年提出MD4 1992年, Ron Rivest 完成MD5 (RFC 1321) 在最近数年之前,MD5是最主要的hash算法 现行美国标准SHA-1以MD5的前身MD4为基础

MD5描述 输入：任意长度的报文 输入分组长度：512 bit 输出：128 bit 报文

MD5描述－step 1 附加长度值 对报文进行填充，使其比特数与448模512同余，即填充长度为512的整数倍减去64 填充方法：填充比特串的最高位为1，其余各位均为0

MD5描述－step 2 附加长度值 |M2|为512的倍数: Y0,Y1,…,YL-1

MD5描述－step 3 初始化MD缓存 MD为128bit，用于存放散列函数的中间及最终结果 MD可表示为4个32bit的寄存器(A,B,C,D)，初始化如下：

MD5描述－step 4 压缩：4个循环的压缩算法

MD5描述－step 5 输出

HMD5

单个512bit分组的MD5处理过程(MD5压缩函数） 当前正在处 理的512 比特分组 128bit 的缓存值 更新缓存 T[0,1…64] 单个512bit分组的MD5处理过程(MD5压缩函数）

每步操作形式

单个512bit分组的MD5处理过程(MD5压缩函数） X[0..15]:保存当前512bit待处理输入分组的值 X[k] = M[q×16 + k] = 在第q个512位数据块中的第k个32位字 每次循环(4)的每步(16)内，X[i]的使用循序各不相同 单个512bit分组的MD5处理过程(MD5压缩函数）

MD5的安全性 Berson表明，对单循环MD5，使用不用的密码分析可能在合理的时间内找出能够产生相同摘要的两个报文，这个结果被证明对四个循环中的任意一个循环也成立，但作者没有能够提出如何攻击包含全部4个循环MD5的攻击 Boer和Bosselaers显示了即使缓存ABCD不同，MD5对单个512bit分组的执行将得到相同的输出(伪冲突） Dobbertin的攻击技术：使MD5的压缩函数产生冲突，即寻找 MD5被认为是易受攻击的，逐渐被SHA-1和RIPEMD-160替代

其它常用Hash算法 SHA-1 RIPEMD-160 HMAC

Hash小结 Hash函数把变长信息映射到定长信息 Hash函数不具备可逆性 Hash函数速度较快

目 录 消息鉴别与散列函数 散列算法 数字签名

报文鉴别的局限性 信宿方伪造报文 信源方否认已发送的报文 用于保护通信双方免受第三方攻击 无法防止通信双方的相互攻击 引入数字签名，是笔迹签名的模拟

数字签名的性质 传统签名的基本特点 数字签名是传统签名的数字化 能与被签的文件在物理上不可分割 签名者不能否认自己的签名 签名不能被伪造 容易被验证 数字签名是传统签名的数字化 能与所签文件“绑定” 容易被自动验证

数字签名的性质 必须能够验证作者及其签名的日期时间 必须能够认证签名时刻的内容 签名必须能够由第三方验证，以解决争议

数字签名的设计要求 签名必须是依赖于被签名信息的一个位串模板 签名必须使用某些对发送者是唯一的信息，以防止双方的伪造与否认 必须相对容易生成该数字签名 必须相对容易识别和验证该数字签名 伪造该数字签名在计算复杂性意义上具有不可行性，既包括对一个已有的数字签名构造新的消息，也包括对一个给定消息伪造一个数字签名 在存储器中保存一个数字签名副本是现实可行的

数字签名分类 签名方式 安全性 可签名次数 直接数字签名direct digital signature 仲裁数字签名arbitrated digital signature 安全性 无条件安全的数字签名 计算上安全的数字签名 可签名次数 一次性的数字签名 多次性的数字签名

直接数字签名

直接数字签名

直接数字签名

直接数字签名的缺点 验证模式依赖于发送方的保密密钥 – 发送方要抵赖发送某一消息时，可能会声称其私有密钥丢失或被窃，从而他人伪造了他的签名 – 通常需要采用与私有密钥安全性相关的行政管理控制手段来制止或至少是削弱这种情况，但威胁在某种程度上依然存在 – 改进的方式例如可以要求被签名的信息包含一个时间戳（日期与时间），并要求将已暴露的密钥报告给一个授权中心 X的某些私有密钥确实在时间T被窃取，敌方可以伪造X的签名及早于或等于时间T的时间戳

仲裁数字签名

仲裁数字签名 引入仲裁者 仲裁者在这一类签名模式中扮演敏感和关键的角色 – 所有从发送方X到接收方Y的签名消息首先送到仲裁者A – A将消息加上日期并与已被仲裁者验证通过的指示一起发给Y 仲裁者在这一类签名模式中扮演敏感和关键的角色 – 所有的参与者必须极大地相信这一仲裁机制工作正常

仲裁数字签名－单密钥加密方式1 数字签名

仲裁数字签名－单密钥加密方式

仲裁数字签名－单密钥加密方式2

仲裁数字签名－双密钥加密方式

仲裁数字签名－双密钥加密方式

数字签名算法 普通数字签名算法 – EIGamal – RSA – DSS/DSA 不可否认的数字签名算法 群签名算法 盲签名算法

数字签名算法 DSA

DSA

DSA

DSA

DSA分析 基于离散对数的难度，对手通过r恢复k，或通过s恢复x都很难 签名产生的计算任务仅是计算 另一个需要完成的工作只是确定逆元