2.1 密码学的基本概念

密码学是一个非常庞大而复杂的信息处理系统，涉及信息的机密性、完整性、认证性、不可否认性等许多方面。密码学中加密和解密信息的主要目的是使得授权人员以外的人无法读取信息。

被加密的消息称为明文，明文经过加密变换成为另一种形式，称为密文。对明文进行加密操作时所采用的一组规则称为加密算法，对密文进行解密操作时所采用的一组规则称为解密算法。加密算法和解密算法都依赖于一组秘密参数，分别称为加密密钥和解密密钥。加密算法和解密算法统称为密码算法。密码算法可以根据密钥的特点分为对称密钥算法和非对称密钥算法。对称密钥算法也称为私钥密码算法，非对称密钥算法也称为公钥密码算法。

在消息传输或处理系统中，除了合法的用户以外，还存在通过各种方法窃取机密信息的攻击者，他们通过分析已经得到的算法信息和截获的信息，推断出密钥或明文，这一过程称为密码分析。如果攻击者通过一定的明文和密文信息能够获得密钥信息，那么密码就是不安全的。根据密码分析者对明文和密文掌握的程度，攻击方式可以分为5种：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击、选择文本攻击。

2.1.1 保密通信模型

在不安全的信道上实现安全的通信是密码学研究的基本问题。消息发送者对需要传送的消息进行数学变换处理，然后在不安全的信道上进行传输，接收者在接收端通过相应的数学变换处理得到信息的正确内容，而信道上的消息截获者，虽然可能截获到数学变换后的消息，但无法得到消息本身。图2-1展示了一个基本的保密通信模型。

一般情况下，在密码算法具体实现过程中，加密密钥和解密密钥是成对使用的，而且是一一对应的关系。根据由加密密钥得到解密密钥的算法复杂度的不同，密钥算法又可分为对称密钥算法和非对称密钥算法。

2.1.2 密码算法分类

密码算法的分类方法有很多。按照是否能进行可逆的加密变换，密码算法可以分为单向函数密码算法和双向函数密码算法。如果根据对明文信息的处理方式不同，密码算法可以分为序列密码算法和分组密码算法。典型的密码算法的分类方法是按照密钥的使用策略的不同将其分为对称密码算法和非对称密码算法。下面将分别介绍对称密码算法和非对称密码算法以及典型的加解密算法，并对典型的序列密码算法和分组密码算法做简要介绍。

对称密码算法是一种传统密码算法。在对称加密系统中，加解密过程采用相同的密钥，即使二者不同，也能够由其中的一个很容易地推导出另一个，所以对称密码算法也称为私钥密码算法。对称密码算法的优点是运算速度比较快、具有很高的吞吐率、使用的密钥长度相对较短、密文与明文的长度相同或扩张较小，是目前用于信息加密的主要算法。对称密码算法的缺点是密钥的分发需要安全通道、密钥量大、难管理、不能解决不可否认的问题。

非对称密码算法也称为公钥密码算法，在这种密码算法中，加密密钥和解密密钥是不同的，加密密钥是公开的而且由加密密钥去推导解密密钥是不可行的。非对称密码算法简化了密钥分发和管理过程。由于在对称密码算法中，加解密密钥相同，通信双方必须妥善保管他们共同的密钥，从而保证数据的机密性与完整性。当用户数量庞大且分布很广时，密钥的分发和保存就成为问题，密钥的安全性严重影响着加密系统的安全性。在非对称密码算法中，如果两个用户要交换数据，发送方会用接收方的公钥对数据进行加密，接收方则用自己的私钥来解密。这一过程中，公钥是可以公开的，用户只要保管好自己的私钥即可，因此加密密钥的分发将变得十分简单。与对称密码算法相比，非对称密码算法的缺点是加密解密的算法一般比较复杂，密钥对的生成与加解密速度也比较慢；同等安全强度下，非对称密码算法需要的密钥位数要多一些。因此，实际网络系统中的加密普遍采用非对称和对称密码相结合的混合加密算法，即加解密时采用对称密码，密钥传送则采用非对称密码。这样既解决了密钥管理的难题，又提升了加解密的速度。

非对称密码算法在密钥分发和管理、鉴别认证、不可否认性等方面均有广泛应用。典型的非对称密码算法有RSA、椭圆曲线密码算法（ECC）、ElGamal公钥加密算法和NTRU公钥加密算法等。

序列密码一次只对明文消息的单个字符进行加解密变换。分组密码将明文消息编码表示后的二进制序列划分成固定大小的组，每组分别在密钥控制下进行加解密变换。典型的分组密码算法有数据加密标准（Data Encryption Standard，DES）算法及其变形三重DES（Triple DES）、广义DES（GDES）、AES（Advanced Encryption Standard）、RC6和IDEA算法等。典型的序列密码算法有RC4、A5和HC算法等。

2.1.3 古典密码简介

密码学的发展历史大致分为3个阶段：古典密码时期、近代密码时期和现代密码时期。古典密码历史悠久，主要分为替换密码和换位密码两种。替换密码，即明文中每一个字符被替换成密文中的另外一个字符。换位密码也称为置换密码，即明文的字母保持不变，但打乱其顺序。尽管这些密码大都比较简单，但在今天仍有参考价值。

对称密码算法就可以看作是古典密码算法的延伸。在本节中，我们将举例介绍两种典型的古典密码。

1.凯撒密码

凯撒密码作为一种古老的对称加密算法，在古罗马的时候就已经很流行，它的基本思想是：通过把字母移动一定的位数来实现加密和解密。

比如，Alice要将明文“mobile internet security”加密成密文，传送给Bob。为了运算方便，先把字母进行数字化。图2-2展示了字母与数字的映射关系。

加密过程如下。

1）Alice先将明文“mobile internet security”中的字母根据图2-2的映射关系转换为数字：（12，14，1，8，11，4，8，13，19，4，17，13，4，19，18，4，2，20，17，8，19，24）。

2）加密之前，双方需要协商一个密钥。于是Alice与Bob商定加密方式为明文字母后移6位，即加密密钥及解密密钥同为K=6。

3）开始加密：将明文字母映射得到的数字代入加密函数E（m）=m+6（mod 26）中计算得到：（18，20，7，14，17，10，14，19，25，10，23，19，10，25，24，10，8，0，23，14，25，4），然后把这些数字根据图2-2的映射关系替换成字母即可得到密文（s，u，h，o，r，k，o，t，z，k，x，t，k，z，y，k，i，a，x，o，z，e），这就是加密后的结果。

4）解密其实就是上述加密过程的逆过程：Bob收到密文“suhorkotzkxtkzykiaxoze”，然后将密文按照图2-2的映射关系转换为：（18，20，7，14，17，10，14，19，25，10，23，19，10，25，24，10，8，0，23，14，25，4）。使用解密函数D（c）=c-6（mod 26）将密文转换后的数字代入计算，得到（12，14，1，8，11，4，8，13，19，4，17，13，4，19，18，4，2，20，17，8，19，24），即可还原出明文“mobile internet security”。

凯撒密码继续扩展就可以得到移位密码，其与置换密码是现代密码学的基石。移位密码可以用数学表达式表示为：E（m）=ax+b，其中a和b为整数且a与26互质。从式中可以看出，移位密码其实就是在凯撒密码中增加一个系数。

2.置换密码

置换密码是通过简单的换位来达成加密。比如，Alice想用置换密码来加密与Bob传递信息，事先约定密钥为一串字母“KEYWORD”。图2-3所示，把A到Z中前面的字母用KEYWORD替换，后面又补充了A到Z（去掉了KEYWORD中重复的字母）。这样就形成了加解密的字母置换表，实际中A到Z可以置换成任意的字母。这个字母置换的过程其实就是加密。

相应的解密过程的字母置换表就如图2-4所示，将A替换成H，B替换成I，依此类推即可实现解密。

现在，Alice想传递的信息明文是：M= “MONOALPHABETTICSUBSTITUTIONCIPHER”，要使用上面的置换密码加密，对照图2-3所示的加密过程的字母置换表就可以得到密文：C=“HJIJKGLAKEOQBYPSEPQBQSQBJIYBLAON”。如果需要对密文C进行解密，对照图2-4所示的解密过程的字母置换表就可以得到明文M。

2.1.4 密码算法的安全性

本节将从信息论和复杂度理论的角度来描述密码算法的安全性。对于所有的密码算法，安全性都是其重要的评价标准。这里所说的“安全性”，是指该密码系统对于破译攻击的抵抗力强度。密码学家一直在寻求刻画密码算法安全性的理论证明方法，目前评价密码算法安全性的方法有两种：无条件安全和有条件安全。无条件安全又称为理论上安全性，有条件安全又称为实际安全性。很多密码算法的安全性并没有在理论上得到严格证明，只是在算法思想得到实现之后，经过众多密码专家多年来的攻击都没有发现其弱点，没有找到破译它的有效方法，从而认为它在实际上是安全的。

我们定义一个五元组（P，C，K，E_k（），D_k（））来表示一个密码系统，其中P、C和K分别代表明文空间、密文空间和密钥空间，E_k（）代表加密函数，D_k（）代表解密函数。针对这一系统，若具有理论安全性，即具有完善保密性或无条件安全性，那么就意味着明文随机变量P和密文随机变量C相互独立。

为了用数学语言描述密码算法的保密性，下面假定明文P、密文C、密钥K都是随机变量；H（·）表示熵；H（·|·）表示条件熵；I（·；·）表示互信息。由于C=E_k（P）；P=D_k（C）。因此，（P，K）唯一地确定了C，而（C，K）也唯一地确定了P。用信息论的语言可表示为：

H（P|CK）=0

H（C|PK）=0

如果式I（P；C）=0成立，即P与C相互独立，此时我们称密码算法是理论上安全的，根据信息论的原理，可以推导出对于完善保密的密码算法必然满足

H（K）≥H（P）

这一结论表明，对于完善保密的密码算法，其密钥的不确定性要不小于明文消息的不确定性。比如，当明文P是n位长的均匀分布随机变量，为了达到完善保密，密钥K的长度必须至少是n位；而且，为了用n位长的密钥达到完善保密，密钥也必须是均匀分布的随机变量。这就意味着完善保密的密码算法需要消耗大量的密钥。

1949年，信息论创始人香农（Shannon）证明了“一次一密”算法，即密钥长度和明文长度一样长的密码算法是无条件安全的，具体证明过程可参考查看现代密码学的书籍，这里不做详细论述。例如，当明文P与密钥K是同长度同分布的随机变量，加密算法为C=P⊕K，其中⊕为逐位异或运算。由于⊕是群运算，那么密文C也是具有同样长度和分布的随机变量，且P和C相互独立，这就构成了一种理论上安全的密码算法。但在“一次一密”算法中，通信双方必须保证在每一次传递秘密消息时，所用的密钥对于攻击者来说都是完全未知的。也就是，每当传递一个新的消息，必须首先更换密钥，这种密码算法如果被正确使用，它就是理论上不可破译的。但是，由于密钥生成比较困难且不能重复使用，而密钥分发又是一个非常复杂的问题，这就限制了它的商用价值。

密码算法还有一种安全称为“计算上是安全的”，即指破解此密码系统是可行的，但是使用已知的算法和现有的计算工具不可能完成攻击所需的计算量。计算安全性是将密码算法的安全性问题与公认的数学难题挂钩，例如，密钥求解问题和某个NP问题。在实际场景中考虑密码算法安全性时，还需考虑破解一个密码系统所花费的成本不能超过被加密信息本身的价值，且破译的时间不能超过被加密信息的有效生命周期。密码算法是安全体系的基石，而密码算法的安全性依赖于密钥的安全性。从前面的介绍可知，某系统的保密强度能达到理论上的不可破译是最好的，否则也要求能达到实际的不可破译性，即破译该系统所付出的代价大于破译该系统后获得的收益。