✒️2. 信息安全与密码学

2.1 密码技术发展简介

2.1.1 古典密码技术

在古代中国，有妇女们使用“女书”，对于不该知道内容的男人而言，这就是一种密码技术。而西方使用字母文字的民族,早期的密码技术主要以字母的代替(Substitution)以及字母的位移(Transposition)为主，有时也用混合代码法代替整个单字或词组。

在中世纪，西方数学与语言学都处于很高的水平，这也为密码分析学(Cryptanalysis)提供了可能的环境。在欧洲还处于黑暗时期时，远在中东与近东的人们早已熟悉用频率分析破译的单字母代换密码。

16世纪，一种名为Vigenere密码的多字母代换密码诞生了，这在当时被视为无法破译的密码，一直到19世纪才被破译，而破译的方法仍是以频率分析为主。

在这个时期,破译密码的技术要高于编译密码的技术。第一次世界大战爆发时，密码学家还无法提供高明的密码编译方法，只能将多字母代换与移位结合产生密码，如Playfair或ADFGVX被勉强使用。但在

第一次世界大战末期,却发明了一种真正无法破译的密码:一次一密密码(One-TimePad)。在冷战时期，美苏之间领导人的热线就使用了这种密码技术。然而此类密码技术所需成本极高,每加密一次就要用不同的密钥,这在军事应用上尤其困难,故无法大量使用。

第二次世界大战前后使用的是滚轮(Rotor Machine)编码。最著名的应属德国采用的Enigma密码机，这种密码机拥有如同天文数字的密钥数量，这是无法用传统的频率分析法破译的。然而在德国发动战争之前，Enigma密码机被波兰密码分析师成功破译。

常用的古典密码技术有恺撒密码、仿射密码、维吉尼亚密码、福尔摩斯密码、Fairplay密码、Hill密码以及Enigma密码机等。

1.1.2 现代密码技术

1949年，香农(C. E. Shannon)发表的论文《保密系统的通信理论》(Communication Theory of Secrecy Systems)标志着现代密码学的真正开始。密码学的真正蓬勃发展和广泛应用是从20世纪70年代中期开始的，源于计算机网络的普及和发展。1973年，美国的国家标准局(National Bureau of Standards,NBS)认识到建立数据加密标准的迫切性，开始征集联邦数据加密标准。很多公司着手这项工作并提交了建议，最后IBM公司的Lucifer加密系统获得了胜利。经过两年多的公开讨论之后，1977年1月15日NBS决定使用这个算法，并将其更名为数据加密标准(Data Encryption Standards,DES)。数据加密标准(DES)和高级加密标准(AES)完全公开了加密、解密算法，使得密码学得以在商业等民用领域广泛应用，从而给密码学这门学科带来巨大的生命力，使其得到了迅速发展。

1976年以前的所有密码系统均属于对称密码学范畴。但在1976年,W.Diffie和M.E.Hellman在刊物 IEEE Transactions on Information Theory 发表了一篇著名论文《密码学的新方向》(New Directions in Cryptography)，在这篇经典论文中二人提出了一个崭新的密码设计思想，不仅加密算法本身可以公开，甚至加密用的密钥也可以公开，这就是著名的公钥密码体制思想。这篇经典论文为现代密码学的发展开辟了一个崭新的思路，标志着公钥密码体制的诞生。公钥密码的思想给密码学的发展带来质的飞跃，开创了公钥密码学的新纪元，导致了密码学的一场革命，可以说“没有公钥密码体制就没有现代密码学”。

就在公钥密码思想提出大约一年后的1978年。美国麻省理工学院的Rivest、Shamir和Adleman提出RSA公钥密码体制。这是迄今为止第一个成熟的、最成功的公钥密码体制。其安全性是基于数论中的大整数因子分解，该问题是数论中的困难问题，至今没有有效的破解算法，这使得该体制具有较高的安全性。此后不久，人们又相继提出了Rabin、ElGamal、Goldwasser-Micali 概率公钥密码、ECC和NTRU等公钥密码体制。由于近年来其他相关学科的进步和发展,出现了一些新的密码技术，如DNA密码、混沌密码和量子密码等。

2.2 密码学的基本概念

密码学主要是研究信息安全保密的学科，它包括两个分支：密码编码学和密码分析学。密码编码学主要研究对信息进行变换，以保护信息在信道的传递过程中不被敌手窃取、解读和利用的方法；密码分析学则与密码编码学相反，它主要研究如何分析和破译密码：两者相互对立又相互促进。

2.2.1 密码系统的组成

从数学的角度来讲，一个密码系统是由密码方案确定的一簇映射，它在密钥的控制下将明文空间中的每一个元素映射到密文空间上的某个元素，具体使用哪一个映射由密钥决定。这里需要说明的是，密码学中术语“系统”、“体制”、“方案”和“算法”本质上是一回事。 一个密码系统(Cryptosystem)可以用一个五元组 S={M,C,K,E,D}来描述。

1. 明文空间$M$：全体明文的集合。

2. 密文空间$C$：全体密文的集合。

3. 密钥空间$K$：全体密钥的集合，通常每个密钥$k$都由加密密钥$k_{e}$和解密密钥$k_d$组成，$k=\langle k_e,k_d\rangle,k_e$和$k_d$可能相同也可能不相同。

4. 加密算法$E$：由加密密钥控制的加密变换的集合。

5. 解密算法 $D$：由解密密钥控制的解密变换的集合。

6. 设$m\in M$是一个明文，$k=\langle k_e,k_d\rangle\in K$是一个密钥，则有一个加密算法$E_k\in E$和相应的解密算法$D_{k_d}\in D$，使得$E_{k_t}:M\to C$和$D_{k_d}:C\to M$分别为加密、解密函数，满足：

   $$c=E_{k_e}(m)\in C\\ m=D_{k_d}(c)\in M$$

   以上描述说明：如果一个明文 $m$ 是用$E_{{k}{e}}$加密的，且得到相应的密文 $c$，随后只要用$D{k_{d}}$解密，就可获得起初的明文 $m$，显然，每个加密函数 $E_{k_e}$一定是个双射函数，否则在一个模棱两可的情况下，解密无法进行。

密码系统模型：

2.2.2 密码体制的分类

密码体制的分类方法有很多,常用的分类方法有如下几种：

1. 根据加密算法与解密算法所使用的密钥是否相同，可以将密码体制分成对称密码体制(也叫单钥密码体制、秘密密钥密码体制)和非对称密码体制(也叫双钥密码体制、公开密钥密码体制)。

   DES、AES、IDEA 等都是对称密钥密码体制的例子，此外所有的古典密码体制也都是单钥密码体制。RSA、EIGamal、椭圆曲线密码等都是非对称密钥密码体制的典型代表。对称密钥密码体制基于复杂的非线性变换实现；非对称密钥密码体制一般基于某个数学上的难题实现。

2. 根据密码算法对明文信息的处理方法，可分为流密码和分组密码。

   流密码逐位或逐字节地加密明文消息字符，也称序列密码；分组密码将明文分成固定长度的组，用同一密钥和算法对每一组加密，输出也是固定长度的密文。

3. 按照是否能进行可逆的加密变换，又可分为单向函数密码体制以及人们通常所指的双向变换密码体制。

   单向函数是一类特殊的密码体制，其性质是可以容易地把明文转换成密文，但再把密文转换成原来的明文却是困难的(有时甚至是不可能的)。单向函数只适用于某种特殊的、不需要解密的场合(如密钥管理和信息完整性鉴别技术)，以及双向变换密码算法中某些环节。典型的单向函数包括MD5、SHA-1等。

2.2.3 密码系统的安全性

1. Kerckhoffs 原理 现代密码学最重要的假设之一是Kerckhoffs 原理(Kerckhoffs's Principle)，由Auguste Kerckhoffs 在1883年提出。Kerckhoffs原理指在密码算法的分析当中，一般先假设密码攻击者了解密码方案的全部知识，可以得到相当数量的密文，知道明文的统计特性和密钥的统计特性，但不知道每一个密文c所用的特定的密钥k，这时整个密码系统的安全性全部寄托于密钥的保密之上，即“一切秘密寓于密钥之中”。一个可靠的密码体制必须遵循Kerckhoffs 原理。

2. 密码系统安全性的评估方法 密码系统安全性评估主要有三种方法。

3. 无条件安全性 对于一个密码系统来说,若攻击者无论得到多少密文也求不出确定明文的足够信息，这种密码系统就是理论上不可破译的，称该密码系统具有无条件安全性(Unconditionally Secure)或理论安全性。

4. 实际安全性

   1. 计算安全性。若一个密码系统原则上虽可破译，但为了由密文得到明文或密钥却需付出十分巨大的计算，而不能在希望的时间内或实际可能的经济条件下求出准确的答案，这种密码系统就是实际不可破译的，或称该密码系统具有计算安全性。

   2. 可证明安全性。一个密码系统为可证明安全是指该密码安全性问题可转化成密码研究人员公认的困难问题。事实上，公开密钥密码系统RSA是可证明安全的，因为该密码系统的安全性问题，在大量的研究下，一般可转化成素因数分解的问题，而素因数分解的问题,一般认为是很困难的。

5. 密码系统的安全因素

   1. 所使用的密码算法的保密强度 密码算法的保密强度取决于密码设计的水平、破译技术的水平以及攻击者对于加密系统知识的多少。密码系统所使用的密码算法的保密强度提供了该系统安全性的技术保证。

   2. 密码算法以外不安全的因素 即使密码算法能够达到实际不可破译,攻击者也可能不通过对密码进行破译的途径，而是通过其他各种非技术手段(例如用金钱收买密钥管理人员等)攻破一个密码系统。因此，密码算法的保密强度并不等价于密码系统整体上的安全性。一个密码系统必须同时完善技术与制度要求，才能保证整个系统的安全。

2.2.4 密码分析

1. 密码分析的类型

   常见的密码分析有四种类型

   1. 纯密文攻击 纯密文攻击(Ciphertext-Only Attack)是指攻击者手中除了截获的密文外，没有其他任何辅助信息，尝试恢复成相应明文，或者找出密钥。

   2. 已知明文攻击 已知明文攻击(Known-Plaintext Attack)是指攻击者除了掌握密文，还掌握了部分明文和密文的对应关系。例如，如果是遵从通信协议的对话，由于协议中使用固定的关键字，如login、password等，通过分析可以确定这些关键字对应的密文。

   3. 选择明文攻击 选择明文攻击(Chosen-Plaintext Attack)是指攻击者知道加密算法，同时能够选择明文并得到相应明文所对应的密文。这是比较常见的一种密码分析类型。例如,攻击者截获了有价值的密文,并获取了加密使用的设备，向设备中输入任意明文可以得到对应的密文，以此为基础，攻击者尝试对有价值的密文进行破解。

   4. 选择密文攻击 选择密文攻击(Chosen-Ciphertext Attack)是指攻击者知道加密算法，同时可以选择一些对攻击有利的特定密文，并将密文破译成对应的明文。采用选择密文攻击这种攻击方式，攻击者的攻击目标通常是加密过程使用的密钥。基于公开密钥密码系统的数字签名，容易受到这种类型的攻击。

   上述每种攻击的目的是决定所使用的密钥。这四种攻击类型的强度按顺序递增，纯密文攻击是最弱的一种攻击，选择密文攻击是最强的一种攻击。如果一个密码系统能够抵抗选择密文攻击，那么它当然能够抵抗其余三种攻击。

2. 密码分析的方法

   1. 穷举攻击法 穷举攻击法的破解思路是尝试所有的可能以找出明文或者密钥。对于一个完善的现代密码系统，采用穷举攻击法进行破解需要付出的代价很可能超过密文破解产生的价值。

   2. 统计分析法 统计分析法是通过分析明文和密文的统计规律来破解密文的一种方法。统计分析法首先需要获得密文的统计规律，在此基础上，将密文的统计规律与已知的明文统计规律对照比较，提取明文、密文的对应关系,进而完成密文破解。要对抗统计分析攻击，密码系统在设计时应当着力避免密文和明文在统计规律上存在一致，从而使攻击者无法通过分析密文的统计规律来推断明文内容。

   3. 数学分析法 大部分现代密码系统以数学难题作为理论基础。数学分析法是指攻击者针对密码系统的数学基础和密码学特性，利用一些已知量，如一些明文和密文的对应关系，通过数学求解破译密钥等未知量的方法。对于基于数学难题的密码系统，数学分析法是一种重要的破解手段。

2.3 古典密码体制

2.3.1 古典密码技术的分类

2.3.2 代换密码

1. 单表代换密码

   单表代换密码是对明文的所有字母都用一个固定的明文字母表到密文字母表的映射， 即$f{:}\mathbb{Z}_q\to\mathbb{Z}_q$。令明文$m=m_0,m_1,\cdotp\cdotp\cdotp$，则相应的密文为$c=e_k(m)=c_0c_1\cdots=f(m_0)f(m_1)...$。常见的单表代换密码有移位密码、代换密码和仿射密码等。

   1. 移位密码

      移位密码(Shift Cipher)的基础是数论中的模运算。在密码的数学描述中，字母表中的26个字母都被编码为数字，如表1

      定义：设$x,y,k\in\mathbb{Z}_{26}$，则： 加密：$e_k(x)\equiv(x+k)mod 26$ 解密：$d_k(y)\equiv(y-k)mod 26$

      其中著名的凯撒密码k取3。

      安全性分析：移位密码是极不安全的(mod 26)，因为它可被穷举密钥搜索所分析：仅有26个可能的密钥，尝试每一个可能的解密规则$d_k$，直到一个有意义的明文串被获得。平均一个明文在尝试26/2=13次解密规则后，将显现出来。

      

      表1
   2. 代换密码

      定义：令$P=C=\mathbb{Z}_{26},K$由 26 个数字 $0,1,\cdotp\cdotp\cdotp,25$的所有可能置换组成。对任意的置换 $\pi\in K$，定义：

      ​ 加密：$e_\pi(x)=\pi(x)$ 解密：$d_\pi(y)=\pi^{-1}(y)$

      ​ 其中$,\pi^-1$是$\pi$的逆置换。

      由于代换密码的一个密钥刚好对应于26个英文字母的一种置换。所有可能的置换有26!种，这个数值超过了4.0×1026，是一个非常大的数。即使对现代计算机来说，穷举密钥搜索也是不可行的。

   3. 仿射密码

      定义：令 $P=C=\mathbb{Z}_{26}$，且 $K={(a,b)\in\mathbb{Z}_{26}\times\mathbb{Z}_{26}|\gcd(a,26)=1}$，对任意的 $k=(a,b)\in K,x,y\in\mathbb{Z}_{26}$,其定义如下。

      ​ 加密：$e_k(x)=(ax+b)$mod 26 ​ 解密：$d_k(y)=a^{-1}(y-b)$mod 26

      为了能对密文进行解密，必须保证所选用的仿射函数是一个双射函数。换句话说，对任意 $y\in\mathbb{Z}_{26}$,下面的同余方程要求有唯一解$x:$

      $$ax+b\equiv y(\text{mod 26})$$

      上述同余方程等价于：

      $$ax\equiv y-b(\text{mod 26})$$

      显然，对任意$y\in\mathbb{Z}_{26}$,都相应有$y-b\in\mathbb{Z}_{26}$。故只需研究同余方程$ax\equiv y({\mathrm{mod~}}26)$ $(y\in\mathbb{Z}_{26})$即可。数论知识告诉我们，当且仅当$\gcd(a,26)=1(\gcd$表示最大公约数)时，上述同余方程对每个 y 有唯一解。因为 26$=2\times13$，故所有与 26 互素的数为 $a\in{1,3,5,7,9,11,15,17,19,21,23,25}$，即满足$a\in\mathbb{Z}_{26},\gcd(a,26)=1$的$a$只有 12 种候选，参数$b$的取值可为$\mathbb{Z}_{26}$中的任何数。因此，仿射密码的密钥空间为 12×26=312(当然，这个密钥太小，是很不安全的)。

2. 多表代换密码

   多表代换密码是以一系列(两个以上)代换表依次对明文消息的字母进行代换的加密方法。令明文字母表为$\mathbb{Z}_q,f=(f_1,f_2,...)$为代换序列，明文字母序列为 $x=(x_1,x_2,...)$, 则相应的密文字母序列为$c=e_k(x)=f(x)=f_1(x_1),f_2(x_2),...$

   有名的多表代换密码有 Vigenere,Beaufort、Running-Key 和转轮机(Machine)等密码。

   Vigenere 密码(维吉尼亚密码)是由法国密码学家 Blaise de Vigenere 于 1858 年提出的，它是一种以移位代换(当然也可以用一般的字母代换表)为基础的周期代换密码，是多表代换密码的典型代表，如定义 2-4 所示。

   定义：设$m$是某固定的正整数，令$P=C=K=(\mathbb{Z}_{26})^{26}$，对一个密钥 $k=(k_1,k_2,\cdotp\cdotp\cdotp,k_m)$，定义如下。

   ​ 加密：$e_k(x_1,x_2,\cdots,x_m)=(x_1+k_1,x_2+k_2,\cdots,x_m+k_m)$

   ​ 解密$:d_k(y_1,y_2,\cdotp\cdotp\cdotp,y_m)=(y_1-k_1,y_2-k_2,\cdotp\cdotp\cdotp,y_m-k_m)$

   所有的运算都在$\mathbb{Z}_{26}$中。

   使用上述方法，对应 $A\leftrightarrow0,B\leftrightarrow1,...,Z{\leftrightarrow}25$,则每个密钥 $k=(k_1,k_2,\cdotp\cdotp\cdotp,k_m)$为长为 $m$ 的字母串，称为密钥字。维吉尼亚密码一次加密$m$个明文字母，当明文串的长度大于$m$，将明文按m一组分段，然后逐段使用密钥字k。

   示例：设m=6，且密钥字为CIPHER，其对应密钥串k=(2,8,15,7,4,17)。假定明文串是thiscryptosystemisnotsecure。 首先将明文中转化为数字串，按6个一组分段，然后模26“加”上密钥字得:

   则密文为：VPXZGIAXIVWPUBTTMJPWIZITWZT

   
3. 多字母代换密码——希尔密码

   多字母代换密码的特点是每次对$L>1$个字母进行代换，这样做的优点是容易将字母的频率信息隐蔽或均匀化而有利于抗统计分析。 希尔密码(Hill Cipher)是一种多字母代换密码，这种密码体制于 1929 年由 Lester S. Hill 提出，其主要思想是利用线性变换的方法进行密码变换处理。

   定义：设$m\geqslant2$是某个固定的正整数，$P=C=(\mathbb{Z}_{26})^m$,且$K=${定义在$\mathbb{Z}_{26}$上的 $m\times m$ 可逆矩阵}，对任意的密钥 $k$，密码变换定义如下。

   ​ 加密：$e_k(x)=xk$

   ​ 解密：$d_k(y)=yk^{-1}$

   以上运算都是在$\mathbb{Z}_{26}$上进行的。

   可以看出，当 $m= 1$ 时 ,系统退化为单字母仿射代换密码，可见希尔密码是仿射密码体制的推广。 当$m=2$时，可以将每一个明文单元使用$x=(x_1,x_2)$来表示，同样密文单元使用$y=(y_1,y_2)$来表示。具体加密中$,y_1,y_2$ 将被表示为 $x_1,x_2$ 的线性组合。 例如：

   $$y_{1}=(11x_1+3x_2)\bmod26\\y_{2}=(8x_1+7x_2)\bmod26$$

   这样可以使用矩阵形式将上式简记为 $y=xk$,即：

   $$(y_1,y_2)=(x_1,x_2)\begin{pmatrix}11&8\\3&7\end{pmatrix}$$

   其中$,k=\begin{pmatrix}11&8\\3&7\end{pmatrix}$为密钥。

2.2.3 置换密码

置换密码的特点是保持明文的所有字母不变，利用置换打乱明文字母的位置和次序，所以有时也称换位密码(Transposition Cipher)。

定义在有限集$X$上的置换为一双射函数$\pi:X\to X$。换句话说$,\pi$既是单射，又是满射，即对任意的$x\in X$，存在唯一的$x^\prime\in X$,使得$\pi(x^\prime)=x$。这样，可以定义置换$\pi$的逆置换 $\pi^{-1}:X\to X$ 为：

$$\pi^{-1}(x)=x^{\prime}$$

当且仅当$\pi(x^{\prime})=x$时$,\pi^{-1}$也是$X$上的一个置换。

定义：设$m$为一正整数。$P=C=(\mathbb{Z}_{26})^m$，且$K$由所有定义在集合${1,2,\cdotp\cdotp\cdotp,m}$上的置换组成。对任意的密钥(置换)π，定义变换如下。 加密：$e_n(x,x_{2},\cdots,x_{m})=(x_{\pi(1)},x_{\pi(2)},\cdots,x_{\pi(m)})$ 解密$d_\pi(y_1,y_2,\cdotp\cdotp\cdotp,y_m)=(y_n^{-1}(1),y_{\pi^{-1}(2)},\cdotp\cdotp\cdotp,y_{\pi^{-1}(m)})$

其中$,\pi^{-1}$为置换$\pi$的逆置换。 示例：

假定m=6，密钥为如下置换$\pi$：

假定给出明文为：shesellsseashellsbytheseashore

首先,将明文分为6个字母一组:shesel lsseas hellsb ythese shore

每6个字母按π重排,得到密文:EESLSHSALSESLSHBLEHSYEETHRAEOS