1.2 密码学和现代密码学

密码学（Cryptography，源于希腊语kryptós“隐藏的”和gráphein“书写”）是研究如何隐密地传递信息的学科。在现代特别指对信息及其传输的数学性研究，常被认为是数学和计算机科学的分支，它与信息论也密切相关。著名的密码学者Ron Rivest解释道：“密码学是如何在敌人存在的环境中通信”，这是从工程学的角度来看的，在此也可以看出密码学与纯数学的异同。在密码学中，研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学。密码学是信息安全等相关领域（如认证、访问控制）的核心，在这些领域中密码学的首要目的是隐藏信息的含义，而不是隐藏信息的存在。因此也可以说密码学是研究编制密码和破译密码的技术。

1.2.1 传统密码体制

传统密码体制主要通过字符间的简单置换和代换来实现对信息的加/解密。现在来看，传统密码体制的技术、思想以及破译方法相对简单，但它们反映了密码设计和破译的基本思想，可以作为学习现代密码学的入门资料，对于理解、设计和分析现代密码学具有很好的借鉴价值。下面介绍两种主要的传统密码体制：置换密码和代换密码。

1.置换密码（Permutation Cipher）

置换密码又称换位密码，是指根据一定的规则重新排列明文，以便打破明文的结构特征。置换密码的特点是保持明文的所有字符不变，只是利用置换打乱明文的位置和次序。最常见的置换密码有两种：一种是列置换密码，另一种是周期置换密码。

定义1.1 有限集X上运算σ：X→X被称为一个置换，则σ 是一双射函数，即σ 既是单射又是满射，并且σ 的定义域和值域相同。也就是说，任意x∈X，存在唯一的x′∈X使得σ (x) x′。同理可以定义置换σ 的逆置换σ-1：X→X，这是因为σ-1也是双射函数，并且σ-1的定义域和值域相同。也就是说，任意x′∈X，存在唯一的x∈X使得σ-1(x′)=x。

定义1.2 设n为一固定整数，P、C和K分别为明文空间、密文空间和密钥空间。明/密文是长度为n的字符序列，分别记为X=（x1,x2,…,xn）∈P和Y=（y1,y2,…,yn）∈C，K是定义在{1,2,…,n}的所有置换组合集合。对于任何一个密钥σ∈K（即一个置换），定义置换密码如下：

eσ(x1,x2,…,xn)=(xσ(1),xσ(2)),…,xσ(n))

上式中，σ-1是σ 的逆置换，密钥空间K的大小为n!。

（1）列置换密码

列置换密码是一种常见的置换密码方式，列置换密码的加密方法如下：

① 把明文字符以固定的宽度m（分组长度）水平地（按行）写出，即每行有m个字符；若明文长度不是m的整数倍，不足的地方用双方约定的方式填充。

② 按1,2，…，m的某一置换σ 交换列的位置次序得到字符矩阵。

③ 把矩阵按1,2，…，m列的顺序读出得密文序列c。

相应的解密过程就是上述加密过程的逆过程，故密文c的解密过程如下：

① 将密文c以分组宽度n按列写出得到字符矩阵。

② 按加密过程用的置换σ 的逆置换σ -1交换列的位置次序得到字符矩阵。

③ 把矩阵按1,2，…，m列的顺序读出得明文序列p。

（2）周期置换密码

周期性置换密码是将明文p串按固定长度m分组，然后对每组中的子串按1,2，…，m的某个置换重新排列位置从而得到密文，其中密钥包含分组长度信息。解密时同样对密文c按长度m分组，并按σ 的逆置换σ -1把每组子串重新排列位置得到明文p。

2.代换密码（Substitution Cipher）

代换密码是将明文中的字符替换为其他字符的密码体制。基本方法是：建立一个代换表，加密时将待加密的明文字符通过查表代换为相应的密文字符，这个代换就是密钥。代换是传统密码体制中最基本的技巧，它在现代密码学中也有广泛的应用。按照一个明文是否总是被一个固定的字母代替进行划分，代换密码主要分为单表代换密码和多表代换密码。

1）单表代换密码

单表代换密码是指明文消息中相同的字母，在加密时都是用同一固定的字母来代换。单表代换密码又分为移位密码、基于密钥的单表代换密码和仿射密码3类，由于移位密码可以看成仿射密码特例，下面只介绍基于密钥的单表代换密码和仿射密码。

（1）基于密钥的单表代换密码

基于密钥的单表代换密码很多，其基本思想是类似的。首先选取一个英文单词或字母串作为密钥，去掉其中重复的字母得到一个无重复字母的字母序列，然后将字母表中的其他字母顺序依次写在此字母序列后面，如果密钥中的字母序列有重复则后出现的字母不再出现，从而使所有的字母建立一一对应关系，也就是字母代换表。这种单表代换密码的破译难度稍高，而且密钥更改便捷，增加了单表代换密码体制的灵活性。

（2）仿射密码

仿射密码的加密算法就是一个线性变换，即对任意的明文字符 x，对应的密文字符为y=e(x)=ax+b(mod 26)，其中a,b∈字母表，并且要求gcd(a,26)=1，函数e(x)称为仿射加密函数。仿射加密函数要求gcd(a,26)=1，即要求a和26互为素数，否则e(x)=ax+b(mod 26)就不是一个单射函数。当gcd(a,26)=1时，仿射加密函数的解必然唯一。

2）多表代换密码

多表代换密码是以一系列代换表对明文消息的字母序列进行代换的加密方法，即明文消息中出现的同一个字母，在加密时不是完全被同一个固定的字母代换，而是根据其出现的位置次序用不同的字母代换。如果代换表序列是非周期的无限序列，则相应的密码称为非周期多表代换密码，它是理论上不可破译的密码体制。但实际应用中经常采用的是周期多表代换密码，它通常使用有限个代换表，代换表被重复使用以完成消息的加密，它是一种比单表密码体制更为安全的密码体制。

多表代换密码利用从明文字符到密文字符的多个映射隐藏单字母出现的统计特性（频率特性）。它将明文字符划分为长度相同的明文组，然后在对明文组进行替换。这样统一字母在明文序列中的位置不同就有不同的密文，能更好抵抗统计密码分析。多表代换密码体制有很多，比较典型的有Playfair密码和Vigenere密码。

（1）Playfair密码

Playfair密码（Playfair Cipher）是1854年由Charles Wheatstone提出的，此后由他的朋友Lyon Playfair将该密码公布，所以称为Playfair密码。

Playfair密码将明文字母按两个字母一组分成若干个单元，然后将这些单元替换为密文字母组合，替换时基于一个5×5字母矩阵，该矩阵使用一个选定的关键词来构造，其构造方法如下。第一步是编制密码表。在这个5×5的密码表中，共有5行5列字母。第一列（或第一行）是密钥，其余按照字母顺序。密钥是一个单词或词组，若有重复字母，可将后面重复的字母去掉。当然也要把使用频率最少的字母去掉，假如密钥是“live and learn”，去掉后则为“liveandr”。如果密钥过长可以占用第二列或行。第二步是整理明文。将明文每两个字母组成一对，如果成对后有两个相同字母紧挨或最后一个字母是单个的，就插入一个字母X。最后编写密文。对明文加密规则如下：

若p1p2在同一行，对应密文c1c2分别是紧靠p1p2右端的字母。其中第一列被看做是最后一列的右方。

若p1p2在同一列，对应密文c1c2分别是紧靠p1p2下方的字母。其中第一行被看做是最后一行的下方。

若p1p2不在同一行，不在同一列，则c1c2是由p1p2确定的矩形的其他两角的字母（至于横向替换还是纵向替换要事先约好，或自行尝试）。

Playfair解密算法首先将密钥填写在一个5×5的矩阵中（去除重复字母），矩阵中其他未用到的字母按顺序填在矩阵剩余位置中，根据替换矩阵由密文得到明文。

对密文解密规则如下：

若c1c2在同一行，对应明文p1p2分别是紧靠c1c2左端的字母。其中最后一列被看做是第一列的左方。

若c1c2在同一列，对应明文p1p2分别是紧靠c1c2上方的字母。其中最后一行被看做是第一行的上方。

若c1c2不在同一行，不在同一列，则p1p2是由c1c2确定的矩形的其他两角的字母。

（2）Vigenere密码

Vigenere密码是由法国密码学家Blaise de Vigenere于1858年提出的一种密码代换，它是多表代换密码的典型代表。

定义1.3 设m为某一固定的正整数，P，C和K分别为明文空间、密文空间和密钥空间，并且 P=K=C=（Z26）m，对于一个密钥 k=（k1,k2,…,km），定义Vigenere密码的加密函数为：ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)，与之对应的解密函数为：dk(y1,y2,…,ym)=(y1-k1,y2-k2,…, ym-km)。

其中k=(k1,k2,…,km)是一个长为m的密钥字，密钥空间大小为26 m，所以对于一个相对小的m，穷举密钥也需要很长的时间。当明文长度超过m时，可将明文串按长度m分组，然后对每一组使用密钥k加密。

1.2.2 现代密码学

随着科学的发展，密码学占据的位置越来越重要，基于数学模式下的密码学与越来越多的学科联系也更加紧密，密码学的应用越来越广泛，其主要研究内容如图1.1所示。

1.现代密码学理论

在密码学理论中，关键内容是从安全的需要出发，合理定义一些具备一定性质要求的对象，这些对象称为密码原语（Cryptographic Primitive），进而探讨使用密码原语解决安全问题的方式，这些解决安全问题的方式称为范式（Paradigm）。通常基于已证明存在或合理假设存在的原语，证明通过范式构造的解决方案（包括通用构造方法，以及基于某些具体困难问题或者数学结构构造的实际方案）满足预先定义的安全需求。常用范式总结如下。

① OAEP变换，通过将明文填充，将明文转化为格式化的明文，原始明文扩散到这种格式化的明文中，并引入随机性，产生了概率加密和明文敏感性的效果，使得基于单射的单向陷门置换构造的公钥加密方案为IND—CCA2安全的方案。这种填充方法使用了伪随机发生器和Hash函数。

② 安全公钥加密的典型范式如混合加密（Hybrid Encryption），即用非对称密钥算法加密临时的随机密钥，然后利用临时的随机密钥使用对称密钥算法加密消息。使用非对称加密作为原语。

③ IND—CCA2安全的公钥加密的通用转化方法。包括：Fujisaki-Okamoto转化方法（FO Conversion）、Pointcheval转化方法和Okamoto-Pointcheval转化方法。

④ 安全数字签名的一个典型范式是Hash-and-Sign范式。所谓Hash-and-Sign范式就是先将消息用Hash函数求值，然后再对散列值进行签名。也有文献将这种范式称为Hash-and-Decrypt范式，它使用Hash函数作为原语。

⑤ 零知识证明中将交互零知识转变成非交互零知识的Fiat-Shamir启发式（Hurisitics），也称Fiat-Shamir范式。该变换是知识签名的基础，也是将基于身份的识别协议转化为签名方案的一般方法。

⑥ PSS构造方法是使用Hash-and-Sign范式前的填充方法，该填充方法和OAEP填充方法具有某些相似性。

⑦ 基于随机预言模型，可以将原始明文随机化，从而得到更安全的公钥加密和签名。因为如果一个明文消息是随机化的，则从密文找到明文的任何信息（如一个比特）和求单向函数的逆一样困难。

⑧ 特定应用背景下的范式，如E1Gamal一般签名形式，Schnorr缩短素数域元素的表示，但又不降低DLP的困难程度。

2.密码系统的安全性测度

一个密码系统最起码的安全性要求是：破译者从截获的密文中，无法用穷举所有可能的密钥来破译该系统。如果破译者没有足够的时间来试每个密钥，或即使穷举了所有密钥，还是不能破译该系统，则称它是穷举破译安全的。对于密码分析，通常有如下三种攻击类型。

① 仅知密文攻击：密码分析者除了拥有所截获的密文外，没有其他可利用的信息。

② 已知明文攻击：密码分析者仅知道当前密钥下的一明密对。

③ 选择明文攻击：密码分析者能获得当前密钥下的一些特定的明文所对应的密文。

密码的安全性表现在以下两个方面。

（1）完全保密性

设明文M出现的概率为p(M)，密文C出现的概率为P(C)，在收到密文C的条件下发送的明文为M的条件概率为P(M/C)。如果对所有的M和C有p(M/C)-p(M)，则称该密码是完全保密的。这就是说，如果不论截获多少密文，关于原明文仍一无所知，即密文与明文是统计独立的。一个密码系统是完全保密的充分必要条件是：对每个密文C都有P(C/M)=p(C)，就是说，在给定发送明文M下（在某个密钥下加密）收到一个特定密文C的概率，和在发送其他消息M下（在另一个密钥下加密）收到C的概率相同。在一个完全保密的密码系统中，密钥数至少应等于明文数。否则，对于给定的密文C，将会有一些明文M找不到密钥K将C解密为M，这意味着 p(M/C)=0，于是，密码分析者可能从考虑的范围中除去某些可能的明文消息，这将导致破译该密码的机会增大。一次一密钥密码系统是完全保密的密码系统的一个例子。但是，由于一次一密钥密码系统所需要的密钥量至少应等于明文的数量，这就使得密钥的分配和管理极为困难。一旦密钥得不到安全的分配和管理，系统也就没有安全性可言，因而一次一密钥密码系统并不实用。在密码学中，绝大多数密码系统是不完全保密的。

（2）计算安全性

实际上，密码分析者不会拥有无限的计算能力，因此，一个实用的密码系统的安全性不依赖于破译该密码理论上的不可能性，而是极大地依赖于攻击的实际困难程度。如果一个针对该密码最佳攻击方法的困难程度超过了密码分析者的计算能力则称该密码系统是计算安全的，或实际安全的。Shannon用密码的工作特性W(n)就仅知密文攻击刻画了这样一种困难性。一个密码的工作特性W(n)定义为当n个密文已知时确定所使用的密钥所需要的工作量，人们也可以针对其他攻击探讨密码的工作特性。说一个密码系统是计算安全的意义是指对该密码最佳攻击的复杂度（一般理解为实施该攻击所使用运行的平均次数）超过了密码分析者的计算能力。要证明一个密码是计算上安全的将意味着寻找一个关于解某个计算问题的复杂度下界。目前对实际中所有的计算问题，这都是难以做到的。因此，一个密码安全性的评估实际上依赖于目前已知道的关于该密码的最佳攻击的复杂度。