密码学基础笔记(四)

第12章 消息认证码

完整性（Integrity）：指信息在存储或传输过程中保持未经授权不能改变的特性。

消息认证码的定义及使用方式

消息认证码，又称密码校验和或者MAC，是一种认证技术，它利用密钥来生成一个固定长度的短数据块，并将该数据块附加在消息之后。

A和B共享密钥K。A想发送消息M给B，A首先计算MAC=CK(M)，其中CK(·)是密钥控制的公开函数，然后发送M‖MAC给B，B收到后做与A相同的计算，求得一新MAC，并与收到的MAC做比较。

1550751645468

如果只有双方知道K，且B计算得到的MAC与接收到的MAC一致，则可实现以下功能：

  1. 接收方相信发送方发来的消息未被篡改：因为攻击者不知道密钥，所以不能在篡改消息后计算出正确的MAC，而如果只篡改消息不修改MAC，则接收方计算的新MAC将与收到的MAC不同。
  2. 接收方相信发送方不是冒充的：因为其他人不知道密钥，所以其他人不可能对发送的消息计算出正确的MAC 。

MAC与加密类似，不同之处在于MAC不可逆。

上述过程中，由于在发送过程中消息是以明文形式存在，因此这一过程只提供认证性而不提供保密性。为提供保密性可在MAC函数以后或以前进行加密。

1550751811375

1550751820324

数据认证算法

数据认证算法是最为广泛使用的一种消息认证码，已作为FIPS Publication（FIPS PUB 113）并被ANSI选为X9.17标准。

算法基于CBC模式的DES算法，其初始向量取为零向量。将数据分为64比特长的分组D1，D2，…，DN，其中最后一个分组不够64比特的话，可在其右边填充一些0，然后按以下过程计算数据认证码。

1550751939053

HMAC

近年来研究构造MAC的兴趣主要是基于Hash函数的构造方法，这是因为：\

  • Hash函数(如MD5、SHA)的软件实现快于分组密码。
  • Hash函数的库代码来源广泛。

Hash函数并不是为用于MAC而设计的，由于Hash函数不使用密钥，因此不能直接用于MAC。目前已提出了很多将Hash函数用于构造MAC的方法，其中HMAC就是其中之一，已作为RFC
2104被公布，并在IPSec和其他网络协议（如SSL）中得以应用。

HMAC的设计目标

RFC2104列举了HMAC的以下设计目标：

  1. 可不经修改而使用现有的Hash函数，特别是那些易于软件实现的、源代码可方便获取且免费使用的Hash函数。
  2. 其中镶嵌的Hash函数可易于替换为更快或更安全的Hash函数。
  3. 保持镶嵌的Hash函数的最初性能，不因用于HMAC而使其性能降低。
  4. 以简单方式使用和处理密钥。
  5. 在对镶嵌的Hash函数合理假设的基础上，易于分析HMAC用于认证时的密码强度。

算法描述

1550752207866

HMAC算法的实现如下：

  • H是算法中嵌入的Hash函数，如MD5、SHA-1。
  • M是HMAC的输入消息，mi (i=1, 2, …, L)是M的第i个分组，每个分组为b bit。
  • K为密钥：

当K的长度大于b bit时，用H(K)值替代原来的K，即length(K)>b，则K←H(K)。

当K的长度小于b bit时，将K的右边填充0，使其成为长度为b bit，记为K+，即length(K) < b，则K+ ← (K || 00…0)。如果K的长度刚好等于b bit，则不作处理。

  • ipad为00110110（即0x36）重复b/8次后的序列。
  • opad为01011100（即0x5C）重复b/8次后的序列。
  1. 将K+与ipad逐比特异或得到b bit的分组Si，即计算Si =K+Åipad。
  2. 把输入消息M=m1m2…mL附加在Si的右端，得到Si||M。
  3. 将Si||M作为Hash函数H的输入，得到n比特的输出H(Si||M)。
  4. 将K+与opad逐比特异或得到b bit的分组S0，即计算S0=K+Åopad。
  5. 将第3）步得到的H(Si||M)填充到b bit后附加在S0的右端。
  6. 将第5）步后的值作为Hash函数H的输入，得到的输出即为消息M的消息认证码HMACK(M)。

HMAC的安全性

HMAC的安全性取决于镶嵌的Hash函数的安全性，它的设计者已经证明了对HMAC的攻击等价于对内嵌Hash函数的下述两种攻击之一：

  1. 攻击者能够计算压缩函数的一个输出，即使IV是随机的和秘密的。
  2. 攻击者能够找出哈希函数的碰撞，即使IV是随机的和秘密的。

第13章 数字签名

数字签名简介

1976年，Diffie和Hellman首次提出数字签名的概念，当时在学术界和计算机网络界受到了广泛重视。

数字签名需求

  • 签名必须与消息相关。
  • 签名必须使用发送方某些独有的信息，防止伪造和否认。
  • 产生和验证签名都比较容易。
  • 无论是从给定的签名伪造消息，还是从给定的消息伪造签名在计算上都是不可行的。
  • 保存数字签名的副本是可行的。

算法描述

(1) 参数定义和密钥生成

  • 选两个大素数p和q；（保密）
  • 计算n=p×q, ϕ(n)=(p−1)×(q−1); （n公开, ϕ(n)保密）
  • 随机选一整数e，1<e<ϕ (n), 且 gcd(ϕ(n), e) = 1（公钥e公开）

  • 计算d，满足 d×e ≡ 1 (mod ϕ(n))（私钥d保密）

    (2) 签名算法

​ 设消息为m，私钥为d，签名s如下：

1550752832169

(3) 验证算法

​ 接收者收到签名(m, s)时，验证如下：

1550752836199

若等式成立，则s是发送者对消息m的有效签名。由于s是用发送者的私钥经过签名算法所得，别人做不出这样的签名，可有效防止发送者的抵赖行为。

当对较长的消息签名时，需对每个消息分组分别签名，这样运算量就很大。

  • 为提高RSA签名方案的效率，对大容量消息签名前，签名者可使用一个Hash函数h来产生消息摘要h(m)，再计算签名：s = Sig**sk(m) ≡ (h(m))d mod n**。
  • 接收者收到签名后先计算h(m), 再检验等式：h(m) ≡ s**e mod n** 是否成立，如果等式成立，则s是发送者对m的有效签名；否则，签名无效。

ElGamal数字签名方案

(1) 参数定义和密钥生成

  • p是大素数
  • g是Zp的一个生成元（即本原元素）
  • x是一个随机数，且x∈Zp
  • 计算：y ≡ g**x mod p**
  • 公钥为pk=(y, p, g)；私钥为sk=x

(2) 签名算法

​ 签名者选取随机数k∈Zp*并用私钥(p, g, y, x)计算：

r ≡ g**k (mod p) s ≡ (h(m)-xr)k**-1 mod (p-1)

生成签名(r, s)，其中h(m)为消息摘要。

​ (3) 验证算法

​ 验证者用公钥(y, p, g)验证签名(r, s)：

y**rrs ≡ g**h(m) (mod p)

如果等式成立，则签名有效；否则，签名无效。

ElGamal签名方案的安全性

  1. ElGamal签名方案的安全性依赖于离散对数问题的困难性。若能求离散对数，则由y和g，可求出私有密钥x，该签名方案就不安全。
  2. 素数p必须足够大，且p-1至少包含一个大素数因子。
  3. ElGamal签名是一个概率算法，对同一个消息m所产生的签名依赖于随机数k。随机数k不能泄露，且每次都不相同，否则用x=(h(m)-sk)r-1 mod (p-1)就可以计算出私钥。

Schnorr数字签名方案

(1) 参数定义和密钥生成

  • p：大素数，p≥2512
  • q：大素数，q|(p-1)，q≥2160
  • g：g∈RZ*p, 且gq≡1 (mod p)
  • x：用户A的私钥，1<**x<q
  • y：用户A的公钥，y≡gx (mod p)

(2) 签名过程

  1. 选择随机数1<k<q，计算r≡gk (mod p)
  2. 计算e=H(r, m)**; s≡xe+k (mod q)**

  3. 签名内容(e, s)

    (3) 验证过程

  4. 计算r′≡g**sy-e (mod p)**

  5. 验证H(r′, m)=e是否成立

数字签名标准（DSS）

数字签名标准（Digital Signature Standard，DSS）由美国国家标准和技术研究所（NIST）于1991年公布。

  • DSS的核心是数字签名算法（Digital Signature Algorithm，DSA）。
  • 它是ElGamal的变形，设计中使用了SHA-1算法。
  • DSS的安全性还是基于求解离散对数的困难性。

DSS的签名与验证过程:

1550753095888

(1) 参数定义和密钥生成

  • p是满足2L-1<p<2L的大素数，其中L是512~1024比特且是64的倍数；q是长160比特的素数，满足q|(p-1)；
  • x是随机或者伪随机数，满足0<x<q；
  • g≡h(p-1)/q mod p，其中h满足1<h<p-1；
  • 计算：y≡g**x mod p**；
  • 公钥：k1=(p, q, g, y)，私钥：k2=x。

(2) 签名算法

​ 签名者选取一个随机数k，0<k<q。首先使用SHA-1计算出消息摘要h(m)，再使用签名算法生成签名(r, s)：

r ≡ g**k (mod p) (mod q) s ≡ (h(m)+xr)k**-1 mod q

​ (3) 验证算法

​ 验证者利用公钥k1=(p, q, g, y)验证签名(r, s)：

g**u1yu2 (mod p) (mod q) ≡ r**

其中: u1≡h(m)s-1 (mod q)， u2≡rs-1 (mod q)

第14章 密钥管理和分发

基于对称加密的对称密钥分发

对于对称加密来说，通信双方必须使用相同的密钥并且该密钥要对其他人保密，在限制攻击者攻陷密钥所需的数据总数时，频繁的密钥交换是安全的。因此，任何密码系统的强度取决于密钥分发技术，即在想要交换数据的两者之间传递密钥且不被其他人知道的方法。

1550753516318

对A和B来说，密钥的分发能以以下不同的方式：

1.A选择一个密钥后以物理的方式传递给B。

2.第三方选择密钥后以物理的方式传递给A和B。

3.如果A和先前或者最近使用过一个密钥，则一方可以将新密钥用旧密钥加密后发送给另一方。如果A和B到第三方C有加密连接，C可以在加密连接上传送密钥给A和B。

密钥分发方案

1550753558731

层次密钥控制

大型网络需要层次体系的KDC，例如有本地KDC，每一个KDC负责其所在的整个内部网络的一个域。

1550753574370

透明的密钥控制方案

面向连接的自动密钥分发协议。

1550753594981

分布式密钥控制

密钥分发中心必须是可信的，而且是防破坏的，但如果密钥是完全分布式的，则无此要求。虽然对只使用对称加密的大型网络，完全分布式是不实用的，但是局部环境下还是很有用的。

1550753614839

基于非对称加密的对称密钥分发

简单密钥分发方案

1550753634986

如果PUA和IDA没有经过认证绑定，则易遭受中间人攻击。类似于Diffie-Hellman密钥交换的中间人攻击。

确保保密性和身份认证的密钥分发方案

1550753650146

公钥分发

公钥的公开发布

无控制的公钥分发。

1550753674497

公开可访问的目录

管理员维护一个动态可访问的公钥目录。

1550753690915

公钥授权

管理员维护一个公钥目录且他自己也有公私钥。

1550753705690

公钥证书

通信双方使用证书来交换密钥而不是通过管理员。

1550753722992

X.509证书

X.509的核心是与每个用户相关的公钥证书。这些用户证书由一些可信的签证机构（Certificate
Authority CA）创建并被CA或用户放入目录服务器中。目录服务器本身不创建公钥和证书，仅仅为用户获得证书提供一种简单的存取方式。

CA用自己的私钥签署证书，如果用户知道相应的公钥，则用户就可以验证证书是CA签署的。

CA生成的用户证书有以下特点：

  • 任何可以访问CA公钥的用户均可获得证书中的用户公钥。

  • 只有CA可以修改证书。

由于证书不可伪造，因此证书可以存放在目录中而不需要对目录进行特别保护。

证书撤销

每一个证书都有一个有效期，这与信用卡相似。通常，新的证书会在旧证书失效前发放，另外，还可能由于以下原因提前撤回证书：

1.用户私钥被认为不安全。

2.用户不再信任该CA。

3.CA证书被认为不安全。

每个CA必须保留一张表，其中包含所有被CA撤销且还未到期的证书，包括发给用户和其他CA的证书，这张表也应被放在目录中。

每个放在目录中的证书撤销列表CRL均被其发行商签名，并包含发行商的名字、表创建时间、下一张CRL表发放的时间以及每个撤销证书的入口。每个入口中包含该证书的序列号和撤销时间。

当一个用户在一个消息中接收到了一个证书，用户必须确定该证书是否已被撤销。用户可以在接到证书时检查目录，为了避免目录搜索时的延迟，用户可以将证书和CRL缓存。

公钥基础设施PKI

RFC 4949（互联网安全术语）定义了PKI系统是由硬件，软件，人，策略和程序构成的一整套体系。这些程序是用来创建，管理，存储，分发和撤销建立在非对称密码算法之上的数字证书。

创建PKI的主要目的就是用来安全、便捷、高效地获得公钥。PKIX（Public Key Infrastructure X. 509）工作组在X.
509的基础上建立了一个可以用来构建网络认证体系的基本模型。

PKIX的元素：

  • 端实体：可以是终端用户、设备（如应用服务器、路由器等），或是其他可以在一个公钥数字证书作用范围中被认证的实体。终端实体支持PKI相关的设备。
  • 签证机构（CA）：证书和CRL的发行人，常常在其上运行着一个或多个注册机构（RA），同时它还承担一些其他的管理任务。
  • 注册机构（RA）：承担一些CA的管理任务。一般来说都是和端实体注册进程相关的任务。
  • CRL发布点：CA可以通过它来发布证书撤销列表。
  • 签证存取库：提供了存取数字证书和CRL的方法，可以被终端用户检索。

第15章 用户认证

远程用户认证原理

认证一个用户的身份大致有四个常用方法：

  • 知道什么：如口令、个人身份号PIN或者之前准备问题的答案。
  • 拥有什么：如加密密钥、电子密钥卡和物理密钥，这种类型的认证信息称为令牌。
  • 静态生物特征：如指纹、虹膜和脸。
  • 动态生物特征：如声音模式、手写特征和打字节奏。

基于对称加密的远程用户认证

双向认证

(1) Needham-Schroeder协议

① A→KDC：IDA‖IDB‖N1

② KDC→A：EKa[KS‖IDB‖N1‖EKB[KS‖IDA]]

③ A→B：EKb[KS‖IDA]

④ B→A：EKs[N2]

⑤ A→B：EKs[f(N2)]

1550754509110

(2) Denning协议

​ 为防止重放攻击，可在第②步和第③步加上时戳：

① A→KDC：IDA‖IDB

② KDC→A：EKA[KS‖IDB‖T‖EKB[KS‖IDA‖T]]

③ A→B：EKB[KS‖IDA‖T]

④ B→A：EKS[N1]

⑤ A→B：EKS[f(N1)]

1550754522663

(3) NEUM93协议

​ 为了防止时钟不同步，同时加入随机数和时间戳。

① A→B：IDA‖NA

② B→KDC：IDB‖NB‖EKB[IDA‖NA‖TB]

③ KDC→A：EKA[IDB‖NA‖KS‖TB]‖EKB[IDA‖KS‖TB]‖NB

④ A→B：EKB[IDA‖KS‖TB]‖EKS[NB]

以上协议为A、B双方建立共享的会话密钥提供了一个安全有效的手段。如果A保留由协议得到的票据，就可在有效时间范围内不再求助于认证服务器：

​ ① A→B：EKB[IDA‖KS‖TB], N′A

​ ② B→A：N′B，EKS[N′A]

​ ③ A→B：EKS[N′B]

B在收到票据后，可通过TB检验票据是否过时，而新产生的随机数N′A、N′B则向双方保证了没有重放攻击。

单向认证

电子邮件等网络应用有一个最大的优点就是不要求收发双方同时在线，发送方将邮件发往接收方的信箱，邮件在信箱中存着，直到接收方阅读时才打开。

① A→KDC：IDA‖IDB‖N1

② KDC→A：EKA[KS‖IDB‖N1‖EKB[KS‖IDA]]

③ A→B：EKB[KS‖IDA]‖EKS[M]

​ 本协议不要求B同时在线，但保证了只有B能解读消息，同时还提供了对消息的发方A的认证。

Kerberos

Kerberos是MIT开发的认证服务系统，它建立了一个中心认证服务器用以向用户和服务器提供相互认证。

用户希望访问网络服务器，服务器要求认证用户的访问请求，并仅允许通过认证的用户访问，以防未授权用户得到服务和数据。以Kerberos V4为例，系统使用的协议是基于Needham-Schroeder认证协议。

1550754594047

Kerberos V4

如果网络环境未加任何保护手段，则任一用户都可获取任一服务器（V）提供的服务。这时明显的安全威胁是假冒，即敌手可假装是一客户以获取访问服务器的特权。为防止这种假冒，服务器应能够确定客户的身份，但在开放环境中则给服务器增加了过重的负担。为此引入一个称为认证服务器AS（authentication server）的第三方来承担对用户的认证，AS知道每个用户的口令，并将口令存在一个中心数据库。

Kerberos认证系统设置了两个服务器：

  • 认证服务器（Authentication Server, AS）
  • 票据许可服务器（Ticket-Granting Server, TGS）

1550754622584

Kerberos V4**的认证过程**

​ 分为三个阶段六个步骤：

  • 阶段1 (认证服务交换)
  • 阶段2 (票据许可服务交换)
  • 阶段3 (客户与业务服务器的认证交换)

后记

以Rivest的话结尾：

密码学是一门研究如何在敌人存在的环境中安全通信的学科。