本文涉及：非对称密码、数字签名、抽象代数

欢迎捉虫。

0. 前言

在介绍数字签名之前，先谈一下MAC。

0.1. MAC是什么

抽象地来说，MAC就是一个 $M × K \rightarrow T$ 的映射——输入message和key，输出tag，该tag就是报文认证码。

至于具体构造MAC的方式，我们有HMAC、CBC-MAC、AES-GCM等等……

需要注意的是，key是构造MAC的必要条件（否则不能防止伪造）；如果不带key，那就是简单的hash函数而已。

0.2. 为什么需要MAC？

一言以蔽之，为了数据的完整性。（CIA三角中的I）

以下是一个关于cookie的例子:

HTTP协议是无状态协议，无状态意味着：协议对于交互性场景没有记忆能力。

所以，当客户端和服务器交互的过程中发生了状态的变化（例如网购时用户的购物车内容发生改变），这些数据往往保存在客户端上。假定某个cookie存储了购物车中所有的物品及其价格——考虑到同一物品在不同的用户购物车中或许存在不同的价格的情况（包括不限于满减、特权用户），我们必须确保用户擅自更改cookie中物品的价格是不可能的，也就是说，我们必须保证cookie的完整性。请注意，cookie并不对用户保密（购物车中的物品及其价格），反而需要用户悉知，因此这是一个纯粹的完整性问题。

由此可见，我们确实需要MAC

TBC

0.3. MAC的缺点是什么？/为什么需要数字签名？

MAC的一个非常显著的特点就是对称。Alice和Bob共享key，都可以构造tag并对(message,tag)进行验证——key的存在使得恶意第三方伪造正确的 (message,tag) 变得困难，但key的共享却带给了 Alice或Bob 抵赖的可能性。基于公钥密码思想的数字签名则解决了这个问题，但这不可避免地带来更多的开销，因此，在通信时若不要求：公开可验证、信任传递、不可抵赖性等特性的话，我们应当采用MAC来保证数据的完整性，而不是数字签名（考虑安全目标和敌手能力，再决定安全方案）。

1. 数字签名 安全定义

联想MAC的定义，应该很容易理解。

2. RSA-Based Signatures

2.1. Plain RSA Signatures

签名过程是教科书式RSA那一套，私钥签名，公钥验签，不再赘述了。

以下讨论敌手的攻击手段：

1.No-message attack:

给定 pk = (N,e) , 任取 $\sigma \in Z^*_N$

计算 $m = \sigma^{e}\ mod\ N$

立刻得到一对合法签名 $(m,\sigma)$

2.arbitrary message forgery:

给定 pk = (N,e)，任取 $m_1,m_2 \in Z_N^*$ 以及对应的 $\sigma_1,\sigma_2 \in Z^*_N$

计算 $m = m_1*m_2\ mod\ N$ , 那么对应的 $\sigma = \sigma_1*\sigma_2\mod\ N$

得到一对合法签名 $(m,\sigma)$ ，因为$\sigma ^e = (\sigma_1*\sigma_2)^{e} = (m_1^d)*(m_2^d)^e = m_1^{ed}*m_2^{ed} = m_1*m_2 = m\ mod\ N$

2.2. RSA-FDH

因为plain版本的RSA签名不可用，因此有了以下版本：

RSA full-domain hash

经过这个改进，显然no-message attack不再奏效。其次，为了避免第二种攻击，我们要求这里采用的hash函数没有所谓的“乘法关系”（more than 乘法同态？），即很难找出三元组$(m,m_1,m_2)$使得 $H(m) = H(m_1)*H(m_2)\ mod\ N$

后面还有一堆证明，太学术，不想看也不想写了。

3. DLP-Based Sig

3.1. Schnorr Sig

Gen（密钥生成）：

多项式时间算法 $\mathcal{G}(1^n)$ 用于生成 $(\mathbb{G},q,g)$

其中 $\mathbb{G}$ 为循环群 ，q为群阶，g为生成元。

（这三个是全局公钥参数,下文的是用户公\私钥参数）

其实具体的构造方式是：

选择素数p和q，使得q是p-1的素因子 (p>q)

选择整数 g 使得 $g^q = 1\ mod\ p$

Alice均匀随机抽取 $x \in \mathbb{Z}_q$ , 构造 $y = g^x\ mod\ p $ ，则有

$pk = (\mathbb{G},q,g,y)$

$sk = x$

Sign（签名）：

Alice均匀随机抽取 $k \in \mathbb{Z}_q$，构造 $I = g^k\ mod\ p$。该过程与m无关，可以预处理。

计算 $r = H(m||I)$ ， $s = (rx+k)\ mod\ q$

签名即为$(r,s)$

Vrfy（验签）：

Bob此时拥有 $pk，(m,(r,s))$

计算 $I' = g^{s}y^{-r}\ mod\ p$

判断 $H(m||I')$ 是否等于 $r$

证明:

$g^sy^{-r} = g^{rx+k}g^{-rx} = g^k\ mod\ p$

3.2. DSA and ECDSA

名词解释：

DSA:Digital Signature Algorithm

ECDSA:Elliptic Curve Digital Signature Algorithm

DSA和ECDSA的抽象表述：

3.2.1. DSA

DSA的公开参数选择与Schnorr签名方案完全一致：

Gen（密钥生成）：

多项式时间算法 $\mathcal{G}(1^n)$ 用于生成 $(\mathbb{G},q,g)$

其中 $\mathbb{G}$ 为循环群 ，q为群阶，g为生成元。

（这三个是全局公钥参数,下文的是用户公\私钥参数）

其实具体的构造方式是：

选择素数p和q，使得q是p-1的素因子 (p>q)

选择整数 g 使得 $g = h^{(p-1)/q}\ mod\ p$, 其中 h 是满足 1 < h < (p-1) 并且 $h^{(p-1)/q}\ mod\ p > 1$ 的任何整数

Alice均匀随机抽取 $x \in \mathbb{Z}_q$ , 构造 $y = g^x\ mod\ p $ ，则有

$pk = (\mathbb{G},q,g,y)$

$sk = x$

Sign（签名）：

Alice均匀随机抽取 $k \in \mathbb{Z}_q$

计算 $r = (g^k\ mod\ p)\ mod\ q $ ， $s = [k^{-1}(H(M)+xr)]\ mod\ q$

签名即为$(r,s)$

Vrfy（验签）：

Bob此时拥有 $pk，(M',(r',s'))$

计算 $w = (s')^{-1}\ mod\ q$

$u_1 = [H(M')w]\ mod\ q$

$u_2 = (r')w\ mod\ q$

$v = [(g^{u1})y^{u2}\ mod\ p]\ mod\ q$

判断 $v$ 是否等于 $r'$

证明:

TBC

3.2.2. ECDSA

与DSA没啥区别

ECDSA的全局域参数（全局公钥）：

一个素数 q

椭圆曲线：$y^2 = x^3 + ax + b$ ,其中 a 和 b 是 $Z_q$ 上的整数

椭圆曲线群上的生成元 $G = (x_g,y_g)$ ,

群阶 n

Gen（密钥生成）：

Alice均匀随机抽取 $d \in \mathbb{Z}_n$ , 构造 $Q = dG$ ，则有

$pk = (E_q(a,b),G,n,Q)$

$sk = d$

Sign（签名）：

Alice均匀随机抽取 $k \in \mathbb{Z}_q$

计算 $r = x \mod\ n $ ， $P = kG$ ，如果 r = 0 则重新选则k

计算$ s = k^{-1}(H(m)+dr)\ mod\ n$ , 如果 s = O，重新选择k

签名即为$(r,s)$

Vrfy（验签）：

Bob此时拥有 $pk，(m,(r,s))$

检验r和s的取值范围

计算 $w = (s)^{-1}\ mod\ n$

$u_1 = H(m)w$

$u_2 = rw$

$X = u_1G+u_2Q = (x_1,y_1)$

如果 X = O，拒绝该签名；否则计算 $v$ = $x_1\ mod\ n$

判断 v 是否等于 r

证明:

TBC

4. 数字证书与PKI

PKI:公钥基础设施。

我们都知道，公钥（非对称）密码可以用来传输对称密钥，也可以用来实现数字签名，但前提是公钥本身的完整性不受侵害。

为保护公钥本身的完整性，同样要利用到公钥密码。

如何利用公钥密码保护公钥的分发？这一说法有点套娃的感觉，其实不然。想象一把公钥，从属于受信任组织，能够被安全分发，我们就可以通过这唯一的受信任的公钥来安全地分发任意多的公钥（然后就能传输任意多的对称密钥与数字签名……）。因此从原理上来说，对于安全分发密钥这个问题，我们只用解决一次。

这原初的KEY，就是数字证书——一种将实体与公钥绑定的数字签名。

举个简陋的例子

Charlie持有密钥对 $(pk_C,sk_C)$ ,与此同时Bob持有密钥对$(pk_B,sk_B)$。如果Charlie对于Bob的公钥是$pk_B$这一事实非常有把握，那么Charlie就可以为Bob与他的pk颁发数字证书：

$cert_{C \rightarrow B} = Sign_{sk_C}(Bob's\ key\ is\ pk_B)$

然后把它发给Bob，Bob就可以利用这个证书向信任Charlie的人证明pk_B的实体是Bob

比方说Alice，是一个知悉$pk_C$并信任Charlie，但不知道Bob的人。Bob就可以向她发送$(pk_B,cert_{C \rightarrow B})$来建立初始信任。

4.1. CA

4.1.1. A single certifiicate authority

最最简单的PKI方案就是设立惟一的CA（颁证机构）

这个CA被所有人信任且负责所有人的颁证服务。

每个想要享受这项服务的人都需要从CA那里获取$pk_{CA}$（的一份合法copy）。很显然，这一步需要在十分安全的信道下完成，否则一份不合法的 $pk_{CA}$ 将会使得CA的信任破产。最容易想到的方式就是用物理手段传输：比方说，如果该CA从属于一家公司，那么它的雇员在入职的第一天便需要直接从公司的某个地方拿到 $pk_{CA}$（或许是一根USB），这种方式很不方便，但安全并且只需要被每个人执行一次。

另一个常用的方法就是把pk绑定在软件里面。

举个例子，一家CA的pk可以内置在浏览器中，使得浏览器可以自动验证其他人的证书是否真实。（实际上，当下的浏览器肯定不止拥有唯一的CA证书，这是下文将要讲述的多CA问题）

另一方面，怎样向CA证明，你是你且你的pk是你的?一个直接的方法就是亲自露面，Bob可以带上他的身份证明文件和 $pk_B$（的一份合法copy），只有这样CA才会为他颁发证书。

4.1.2. multiple CA

单一的CA很可能会带来一些问题：可能纯粹是因为某CA颁发的证书信息不充分(比方说某CA的证书只附带Bob的一种身份证明信息而Alice更倾向于两种)；更重要的是，整个信任系统的价值皆系于CA一点，如果CA被攻破，或者仅仅是一次颁证不够规范，整个系统的信任就会破产；再者，要求所有成员都到唯一的CA获取证书太不方便了。

因此着手构造多CA是很自然的事情。

操作系统/浏览器常常预装了许多CA的公钥，以此获得原初信任（信任根），而默认设置往往是对所有这些CA抱以相同程度的信任，用户也能自行设置自己信任的CA。

4.1.3. Certificate chains

另外一个能减轻单CA的负担的手段是证书链。

下面以链长为2的证书链为例子，不难推广到任意长的证书链中

假设Charlie是某个CA，为Bob颁发了证书。

在证书链模型下，Bob就可以为其他实体颁发证书了。

例如:

$cert_{B \rightarrow A} = Sign_{sk_B}(Alice's\ key\ is\ pk_A)$

现在，如果Alice想要与Dave通信（假设Dave知悉Charlie但不知悉Bob）

那么Alice可以发送

$pk_A , cert_{B \rightarrow A} , pk_B , cert_{C \rightarrow B}$

Dave可以从中得到什么信息?

首先他可以先验证$cert_{C \rightarrow B}$的正确性，那么此时Dave就可以信任$pk_B$了

然后验证$cert_{B \rightarrow A}$，他就可以信任$pk_A$

如果Dave相信Charlie只会给足够可信的人颁发证书，那么Dave或许就能接受$pk_A$作为Alice的认证密钥了。

本来，$cert_{C \rightarrow B}$仅仅传达了 B 的 公钥是 $pk_B$ 这个语意，但现在，Charlie为Bob颁发证书，传达了更进一步的信息：他认可Bob为他人颁证的能力。经过放权，现在Bob可以作为Charlie的代理，执行Charlie的职能了。

回到CA-based PKI 的话题上来，我们可以构造一个 root CA，n个 “second-level” CAs: $CA_1$ ,…$CA_n$。根CA可以为每个二级CA颁证，而二级CA就可以为拥有pk的其他实体颁证了。

这减轻了根CA的负担，同时其他人更方便地就能获取到证书了。但另一方面，维护那么多二级CA可能是困难的，他们的存在可能意味着系统的脆弱性（弱点）更高了。

4.1.4. “web of trust” model

最后一个介绍的PKI的例子是完全分布式（去中心化）的——信任网络模型。

在信任网络，任何人都可以为其他任何人颁发数字证书，每个人都可以选择对某些证书抱以多大的信任。

举个例子：

Alice 知悉三个CA $(C_1,C_2,C_3)$ 的三把公钥$pk_1,pk_2,pk_3$

Bob想要和Alice通信，他持有证书 $cert_{C_1 \rightarrow B} $, $cert_{C_3 \rightarrow B}$ , $cert_{C_4 \rightarrow B}$ ，他会把这些证书连同他的公钥$pk_B$ 发送给Alice

显然Alice无法验证$cert_{C_4 \rightarrow B}$ ，但她可以验证其余两个。

现在的问题是，Alice到底在多大程度上信任 $C_1$ 和 $C_3$

或许她会接受$pk_B$ , 如果她无条件信任 $C_1$ 的话；或者说，Alice认为 $C_1$ 或 $C_2$ 其中一个被攻破是可能的，但两个都被攻破的概率可以忽略，则她同样会接受$pk_B$……

4.2. 无效证书

天下没有不散的宴席，我们必须提供一种使得证书无效化的措施。

4.2.1. Expiration

Expiration:终结

在签证的时候带上一个截止日期

$cert_{C \rightarrow B} = Sign_{sk_C}(Bob's\ key\ is\ pk_B,date)$

4.2.2. Revocation

Revocation:撤销

在签证的时候带上一个（唯一的）序列号

$cert_{C \rightarrow B} = Sign_{sk_C}(Bob's\ key\ is\ pk_B,\#\#\#)$

###代表每个证书特有的序列号

如果Bob的$sk_B$泄露了，他可以向CA报告这个安全威胁（或者说是漏洞）

CA维护一个 certificate revocation list (CRL，证书吊销列表)，其中包含了每个被撤销的证书的序列号。CA每隔一段时间都会更新一次并为它签名。

签名后的CRL必须为所有潜在的使用者公开。

现在在验证证书的同时，也必须确认该证书是否在CRL之内。

5.TLS

TLS:Transport Layer Security (protocol)

主要介绍 TLS 1.3 的内容，但可能会有所简化与抽象

TLS 允许 client (e.g.,browser) 与 server (e.g.,website) 就一组共享密钥达成一致，然后使用这些密钥进行加密与验证后续通信。它包含两部分：负责密钥交换（和认证）的握手协议和使用共享密钥加密\认证的记录层协议。

5.1. 握手协议

在一切的开端，client C持有一系列的CA的pk簇${pk_1,...,pk_n}$

server S 持有（用来签名的）公私钥对$(pk_S,sk_S)$以及数字证书$cert_{i \rightarrow S}$，用以绑定 $pk_S$ 与 S。

其中 i 必须为 C 所知悉，于是有接下来的步骤：

1. C与S进行 DHE (Diffie-Hellman Ephemeral) 密钥交换，包括公共参数$(\mathbb{G},q,g)$ (可能是$Z_p^*$ , 或一个椭圆曲线群……)， 以及 一个随机数 $x$ 构造$g^x$ , 同时C会通知对方自己支持哪些加密算法

2. S与C进行 DHE 密钥交换，构造$g^y$。然后，S可以计算 $K = g^{xy}$ 。再通过密钥派生函数(key derivation function)，利用 $K$ 派生密钥 $k_S',k_C',k_S,k_C$ , 用在认证加密(authenticated encryption,AE)方案中。

   最后，S发送 $pk_S$ 和证书 $cert_{i \rightarrow S}$ , 以及 一份数字签名 $\sigma$ (用长期密钥$sk_S$签名从开端至今所有交换的握手消息)。这些值用 $k_S'$ 加密。

3. C 计算 K , 以相同的方法派生密钥 $k_S',k_C',k_S,k_C$ , 使用 $k_S'$ 解密上述密文恢复 $pk_S$、数字证书与 $\sigma$ 。C 验证数字证书，从而相信 $pk_S$ 是 S 的公钥，然后再验证 $\sigma$ 。最后，C利用 $k_C'$ 计算握手消息的MAC 并发给S。在进入记录层协议之前，S验证该tag。

在握手协议的最后，C和S共享会话密钥 $k_C$ 和 $k_S$,由此可以加密或认证后续通信。

5.1.1 为什么握手协议是安全的？

注意到，只要C验证S提供的数字证书的真实性，他就立刻知道 $pk_S$ 确实是 S的公钥。如果数字签名 $\sigma$ 是真实的,那么C立刻知道他确实在与S通信。（恶意第三方无法得到 $sk_S$ 从而C用 $pk_S$ 验签会不正确）

很重要的一点是，被签名的握手消息必须具有高熵值以防止重放攻击，这就是$N_C$ 的作用。

更进一步地，只要 S 为 DHE 中所有消息签名，那么C就知道其中没有任何值被主动敌手进行过中间人攻击。再者，DHE本身保证了被动窃听的敌手无法从中得到任何关于K的信息（从而导不出密钥）

TLS 1.2 版本允许 C 和 S 通过公钥加密方式交换密钥（而不是DH 密钥交换），在这种情况下，S持有的密钥对$(pk_S,sk_S)$ 就是用作公钥加密。此时C简单地选取K并用$pk_S$ 加密（该协议的细节略有不同，特别是C在验证$pk_S$的正确性之前便已完成加密过程）

但问题是，这种方案无法保证前向安全，因为sk_S作为S的长期密钥无法在完成一次通信后擦除。一旦敌手获得sk_S,他便可以解密以往的握手协议并恢复出会话密钥。

DHE则不会带来这方面的问题。注意到E指的是Ephemeral（短暂的），一旦握手完成，服务器中的随机秘密值y便可以立刻被擦除，没有了y，敌手便无从获取K。

TLS1.3 版本不允许通过公钥加密的方式交换密钥以保证前向安全。

5.2. 记录层协议

C用 $k_C$ 认证加密 信息

S用 $k_S$ 认证加密 信息

（双方不用同一个key是为了抵抗反弹攻击）

此外还需要序列号来抵抗重放攻击。

参考

Introduction to Modern Cryptography

现代密码学：IMC 学习笔记 - 0xFFFF