《应用密码学》——基础知识及协议结构模块（笔记）

一、基础知识

1.1 专业术语

消息和加密

• 明文（plaintext）：即消息（message）。
• 加密（encryption）：隐藏明文的过程。又叫做“译成密码”（encipher）。
• 密文（ciphertext）：加密后的消息。
• 解密（decryption）：密文转变成明文的过程。又叫做“解密密码”（decipher）。
• 密码编码学（cryptography）：使用消息保密的技术和科学。
• 密码编码者（cryptographer）：从事此行的人
• 密码分析者（cryptanalyst）：从事密码分析的专业人员
• 密码分析学（cryptanalysis）：破译密文的科学和技术
• 密码学（cryptology）：包含密码编码学和密码分析学
• 密码学家（cryptologist）：精于密码学的人。

加密可用如下式子表示：

$$E(M)=C$$
明文用$M$或者$P$表示， 对计算机而言为简单的二机制数据。
解密可用如下式子表示：

$$D(C)=M$$
密文用$C$表示，计算机中也为二进制数据。有时和$M$一样大或者比$M$大，压缩后可能比$M$小。

由此下列等式必须成立：
$$D(E(M))=M$$

其他作用

除了提供机密外，还有：

• 鉴别（authentication）：接收者可以确认消息的来源
• 完整性（integrity）：校验消息在传送中有没有被修改
• 抗抵赖（nonrepudiation）：发送者事后不可能虚假地否认他发送的消息

算法和密钥

• 密码算法（cryptographic algorithm）：也叫做密码（cipher），适用于加密和解密的数学函数。（一般有两个函数，一个用于加密，一个用于解密）

• 受限制的算法（restricted algorithm）：算法的保密性是基于算法的保密，（如换位密码等）具有历史意义。一旦算法泄露或者用户离开，每个人都要改变算法。

现代密码学用密钥解决了这个问题。

• 密钥（key）：用$K$表示。
• 密钥空间（keyspace）：密钥$K$的取值范围。

加密和解密运算都使用这个密钥，上述式子可以改为：

$$E_K(M)=C$$
$$D_K(C)=M$$

由于计算机的算法安全性都基于密钥安全性，而不是古代的算法细节安全性，因此算法可以公开，分析。

• 密码系统（cryptosystem）：由算法以及所有可能的明文、密文和密钥组成。

对称算法

• 对称算法（symmetric algorithm）：又叫做传统密码算法，其加密密钥能够从解密密钥中推算出来，反过来也可以。
  • 序列算法（stream algorithm）/序列密码（stream cipher） ：一次支队明文中的单个位（有时对字节）运算。
  • 分组算法（block algorithm）：对明文的一组位进行运算。现代计算机密码算法典型分组长度为64位。

加解密表示为：

$$E_K(M)=C$$
$$D_K(C)=M$$

公开密钥算法

• 公开密钥算法（public-key algorithm，也叫做非对称算法）：作用加密的密钥不同于作用解密的密钥。且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内）。所有人都可以使用公开的密钥进行加密，但只有对应的解密密钥可以解开。
  • 公开密钥（public key）：简称公钥。
  • 私人密钥（private key）：简称私钥。

假设$K_1$与$K_2$分别为公钥和私钥，加解密可以改为：

$$E_{K_1}(M)=C$$
$$D_{K_2}(C)=M$$

此外，有时候会用私钥进行加密而公钥进行解密，这用于数字签名。即，接收者可以用对应私钥的公钥进行解密，如果可以解开，就可以确定发送人。此时加解密为：

$$E_{K_2}(M)=C$$
$$D_{K_1}(C)=M$$

密码分析

• 泄露（compromise）：密钥通过非密码分析的方式丢失，
• 攻击（attack）：对密码/密钥进行分析的行为

一些攻击方式如下：

1. 唯密文攻击（ciphertext-only attack）：密码分析者有一些消息的密文，这些消息都用相同加密算法加密。通过这些密文恢复更多的密文或推算出密钥进行解密。
2. 已知明文攻击(known-plaintext attack)：密码分析者不仅有一些消息的密文，还有这些消息的明文。通过这些推出密钥或者一个算法进行解密。
3. 选择明文攻击（chosen-plaintext attack）：密码分析者不仅有一些消息的密文，还有这些消息的明文，同时还可以选择被加密的明文。这使得密码分析者能选定特定的明文进行加密，那些块可能产生更多密钥信息。通过这些推出加密密钥或者一个算法进行解密。
4. 自适应明文攻击（adaptive-chosen-plaintext attack）：为 选择明文攻击特殊情况。密码分析者不仅能选择被加密的明文，还可以基于以为以前加密结果修正这个选择。
5. 选择密文攻击（chosen-ciphertext attack）：密码分析者能选择不同的被加密的密文，并可得到对应的明文。（主要用于公开密钥算法，有时也用于对称算法）当选择明文+选择密文攻击一起使用，被称为选择文本攻击（chosen-text attack）。
6. 选择密钥攻击(chosen-key attack)：并不表示密码分析者能选择密钥，仅表示密码分析者具有不同密钥之间关系的有关知识。
7. 软磨硬泡攻击(rubber-hose cryptanalysis)：密码分析者威胁、勒索某人，直到得到密钥。行贿又叫做购买密钥攻击（purchase-key attack）。
8. 蛮力攻击（brute-force attack）：逐一尝试可能的密钥，并检查所得明文是否有意义。

算法的安全性

破译算法可分为不同类别，安全性递减顺序为：

1. 全部破译（total break）：密钥已被获取
2. 全盘推导（global deduction）：找到了替代算法$A$，在不知道密钥情况下，可以进行解密
3. 实例（局部）推导（instance （local）deduction）：密码分析者从截获密文中找出了明文
4. 信息推导（information deduction）：密码分析者获得一些有关密钥或明文的信息。

• 无条件保密（unconditionally secure）：无论密码分析者有多少密文，都没有足够信息恢复出明文。

也有不同方式衡量哦攻击的复杂性：

1. 数据复杂性（data complexity）：用于攻击输入所需要的数据量。
2. 处理复杂性（processing complexity）：完成攻击所需要的时间，也叫做工作因素（work factor）。
3. 存储需求（storage requirement）：进行攻击所需要的存储量。

1.2 简单异或

• 异或（XOR）：即代码中“^”运算，数学符号为$\oplus$。

$$0\oplus 0=0$$
$$0\oplus 1=1$$
$$1\oplus 1=0$$
$$1\oplus 0=0$$

此外：
$$a\oplus a=0$$
$$a\oplus b\oplus b=a$$

1.3 计算机算法

计算机密码算法最通用的为：

1. 数据加密标准（Data Encryption Standard，DES），是最通用的对称加密算法。为美国和国际标准。国内对标的为国密SM4。
2. RSA（以三个发明者命名），是最流行的公开密钥算法，可以做加密与数字签名。国内对标为国密SM2。
3. 数字签名算法（Digital Signature Algorithm，DSA，也是数字签名标准的一部分），另一种公开密钥算法，不能做加密。

国密即国家密码局认定的国产密码算法。主要有SM1，SM2，SM3，SM4。密钥长度和分组长度均为128位。
SM1为对称加密。其加密强度与AES相当。该算法不公开，调用该算法时，需要通过加密芯片的接口进行调用。
SM2为非对称加密，基于ECC。该算法已公开。由于该算法基于ECC，故其签名速度与秘钥生成速度都快于RSA。ECC 256位（SM2采用的就是ECC 256位的一种）安全强度比RSA 2048位高，但运算速度快于RSA。
SM3消息摘要。可以用MD5作为对比理解。该算法已公开。校验结果为256位。
SM4无线局域网标准的分组数据算法。对称加密，密钥长度和分组长度均为128位。

二、协议结构模块

2.1 协议概述

• 协议（protocol）：是一系列步骤，它包括两方或者多方，设计它的目的是要完成一项任务。协议包含了开始到结束的序列，且每一步必须要依次执行，且两方或者多方都要遵守。
• 密码协议（cryptographic protocol）：使用密码学的协议。相互信任或者不信任的各方也能够在网络上完成这些协议。“不可能完成或知道得比协议中规定的多”。

2.1.1 协议类型

• 仲裁协议：必须要有仲裁者，比如律师、公证人。
  • 仲裁者（arbitrator）：完成协议过程中，值得信任的第三方。
• 裁决协议：雇佣仲裁者代价高昂，因此将仲裁协议拆分为两个低级得子协议（subprotocol）。
  • 非仲裁子协议：执行协议的各方每次想要完成的。
  • 仲裁子协议：尽在例外情况下（有争议的时候）才执行。此时仲裁者称为裁决者。
  • 裁决者：并不直接参阅每一个协议，仅在有需要确定协议是否公平地执行时才参与。比如：法官。
• 自动执行协议（self-enforcing protocol）：协议本身就保证了公平性，需要仲裁者来完成协议，也不要裁决者来解决争端。

2.1.2 对协议的攻击分类

我们在此假设密码算法和密码技术都是安全的，只关注对协议本身的攻击。

• 被动攻击（passive attack）：类似密文攻击，攻击者只能观察协议并试图获取消息。
• 主动攻击（active attack）：在协议中引入新的消息，删除原有消息，用另外的消息代替原来的消息，重放旧的消息，破环通信信道，或者改变存储在计算机中的消息等（该类攻击依赖于网络）。

攻击者可能是与协议有关的一方，这类攻击者被称为骗子（cheater）。

• 被动骗子（passive cheater）：遵守协议，但是图获取协议外的其他消息。
• 主动骗子（active cheater）：在协议的执行过程中，试图通过欺骗来破坏协议。

2.2 使用对称密码系统通信

在使用对称密码时，会有如下问题：

1. 密钥必须秘密分配
2. 密钥泄露了，获取者可以用该密钥去解密所有传送的消息，也能够假装是协议中的一方
3. 假设网络每对用户使用不同的密钥，那么密钥总数随着用户数的增加而增加。

2.3 单向函数

单向函数（one-way function）：其概念是公开密钥密码的中心。

单向函数计算起来相对容易，但求逆非常困难。就比如我们把盘子打碎很容易，但是把盘子拼回去却很困难。

陷门单向函数（trapdoor one-way function）：可以理解为有后门的单项函数，是一种特殊的单向函数。虽然逆向很困难，但是知道某些秘密后，逆向就很简单（可以理解为还原魔方）。在公开密钥密码中，这个后门就是私钥。

2.4 单向散列函数

• 单向散列函数（one-way hash function）：又叫压缩函数，收缩函数，消息摘要，指纹，密码校验和，信息完整性校验（Message Integrity Check，MIC），操作校验码（Manipulation Detection Code，MDC）。

它将可变长输入串（预映射，pre-image）转换为固定长度输出串（散列值，hash value）的一种函数。比如MD5和国密SM3。

无论输入的字符多长，最后输出的都是固定长度，因此会出现两个不同字符结果是一个散列值的情况，即其结果为多对一，这种情况就是冲突（collision）。好的散列函数是无冲突的（collision-free）：难以产生两个预映射的值，是它们的散列值相同。

消息鉴别码

消息鉴别码（Message Authentication Code，MAC）：也叫数据鉴别码（DAC）。嗲有秘密密钥的单项散列函数，只有拥有密钥某些人才能验证散列值。

2.5 使用公开密钥密码系统通信

在使用改密码通信中，只需要将公钥发送给参与者即可，由于是公钥，则不需要担心泄露。

2.5.1 混合密码系统

混合密码系统（hybrid cryptosystem）：公开密钥算法不用来加密消息，通常用来加密密钥（如：SSL/TLS）。用和公开密钥密码保护与分发会话密钥（session key）。会话密钥用在对称算法中，对通信消息进行加密。
理由如下：

1. 公开密钥算法比对称算法慢。
2. 公开密钥密码系统对选择明文攻击是脆弱的。如果$C=E(P)$，当$P$是$n$个可能明文集中的一个明文时，密码分析者只需要加密所有$n$个可能的明文，并能与$C$比较结果（因为公钥公开）。虽然不能恢复解密密钥，但他可以知道$P$。

2.6 数字签名

2.6.1 使用对称密码系统和仲裁者对文件签名

仲裁者和参与者A共享秘密密钥$K_A$，与参与者B共享秘密密钥$K_B$。$K_A$与$K_B$是两组对称密钥。

参与者A与参与者B的通信均经过仲裁者，参与者A与参与者B互不知道对方的密钥。仲裁者会A发向B的消息解密后重新加密给B，反之也是。双方事后也不可能修改文件，因为密钥不一致。

此时，仲裁者就成了瓶颈，负责解密和加密，且一旦它犯错了或者密钥数据库泄露了，将引发混乱。

2.6.2 数字签名树

在某些公开文档中放入树的根文件，从而鉴别它。根节点对一个消息签名，并鉴别树中的子节点，这些节点的每一个都对消息签名，并对它的子节点进行鉴别，一直延续下去。又可以叫做Merkle 可信树，一次签名即可批量认证大量数据。

2.6.3 使用公开密钥密码系统对文件签名

使用私钥进行加密，接收者用公开密钥解密。

此处不再需要仲裁者做中间层。

2.6.4 文件签名和时间标记

数字签名经常包括时间标记，避免日期和时间部分被篡改。

2.6.5 使用公开密钥密码系统和单向散列函数对文件签名

公开密钥密码算法对长文件签名效率太低，通常先用单向散列函数将文件中要签名的部分散列后，在进行加签。

这样做的计算速度就大大地提高了，且两个不同文件使用160位的单向散列函数，每一位散列值都相同的概率为$\frac{1}{2^{160}}$。

此外，这也意味着签名和文件可以分开保存，数据库也只需要存储文件的散列值以及日期等重要信息。

签名可以表示为：
$${Ｓ}_K(M)$$

验签可以表示为：

$${Ｖ}_K(M)$$

2.6.6 多重签名

一般采用单向散列函数进行：
A、B两人都对文件的散列值签名，随后B将签名交给A，A通过把A、B、文件一同发给C即可。

2.7 带加密的数字签名

2.7.1 重发消息作为收据

B收到了A的消息后，他再把消息送回发送者作为接受确认。
A发送加签+加密消息给B：

• A->B：$E_B(S_A(M))$

B收到了后解密+验签得到$M$

• B：$V_A(D_B(E_B(S_A(M))))=M$

B最后把收到的消息再加签加密返回：

• B->A：$E_A(S_B(M))$

A最后再校验

• A：$V_B(D_A(E_A(S_B(M))))=M$

但是如果我们加签和解密是同一个算法，就会有问题。因为数字签名操作是加密操作的逆过程。换言之就是公钥可以解密。

我们用$E_X$替换$V_X$，$D_X$替换$S_X$。即，

• $E_B(S_A(M))$替换为：$E_B(D_A(M))$
• $V_A(D_B(E_B(S_A(M))))=M$替换为：$E_A(D_B(E_B(D_A(M))))=M$

在这个过程中，如果有一个用户C，他持有自己的公钥和私钥并加入这个流程。

在A->B的过程变为A->C->B，B收到的结果为$E_B(D_A(M))$，但此时他会以为消息来自于C（C告知B消息来自于C），于是B由原来的：$E_A(D_B(E_B(D_A(M))))=M$改为了： $E_M(D_B(E_B(D_A(M))))=E_M(D_A(M))$。

此时如果B报错结束则无问题，如果B将结果即上送报文再次返还就会有B->C：$E_M(D_B(E_M(D_A(M))))$。

最后C只需要：用自己的私钥解密，用A和B的公钥解密即可获取到$Ｍ$。

2.7.2 阻止重新发送攻击

使用如下的一种即可解决：

1. 数字签名和解密使用不同密钥或者加密和数字签名操作稍微不同
2. 数字签名和解密使用不同算法
3. 使用时间标记，让输入和输出消息不同
4. 用单向散列函数的数字签名

2.7.3 对公开密钥密码系统的攻击

如何攻击，最主要的就是攻击者用自己的公开密钥作为替换，使用者认为自己可信。

• 密钥鉴定机关（Key Certification Authority）或密钥分配中心（Key Distribution Center，KDC）是用私人密钥对公开密钥进行签名，进行公钥签发。通过这种方式认定公钥是可信的且可以使用。

在有KDC介入的情况下，攻击者的进攻就会变得困难。

2.8 随机数与伪随机序列的产生

2.8.1 伪随机序列

伪随机序列发生器（pseudo-random-sequence generator）：即能产生伪随机序列的机器。一个序列发生器产生的一个有序序列的周期足够长，使得实际应用中相当长的有序序列都不是周期性的，且他能通过我们所找到的所有随机性统计校验，我们认定其为伪随机。

周期大于$2^{256}$位的随机数序列就能大量应用。

但某种意义上，一些随机序列发生器的结果是可以干涉的，这也是为什么密码分析者用它来对系统进行攻击。

2.8.2 密码学意义上的安全伪随机序列

密码学意义上的安全伪随机序列（cryptographically secure pseudo-random sequence）
除了要求有2.8.1中性质，还要有：

• 它是不可预测的。即使给出产生序列的算法或硬件以及所有以前产生的位序列的全部知识，也不可能通过计算预测下一个随机位是什么。

2.8.3 真正的随机序列

真正的随机序列（real random）：它不能重复产生。如果你用完全同样的输入对序列发生器操作两次（至少达到与人为做到的最精确），你将得到两个不相关的随机序列。

参考文献

【1】《应用密码学》【美】布鲁斯·施奈