对称密码学和非对称密码学简介

[TOC]

密码学历史

要了解现代的对称密码学和非对称密码学，可以先简单了解下密码学的历史，这一节摘取一些维基百科“密码学”词条来进行介绍。

密码学(cryptology)分成密码使用学(cryptography)和密码分析学，前者顾名思义是从使用者的角度对使用密码进行加密解密，而后者是从破解者的角度，对密码进行分析破译。密码学也可以分成古典密码学和现代密码学，古典密码学主要关注信息的保密书写和传递，以及与其相对应的破译方法。而现代密码学不只关注信息保密问题，还同时涉及信息完整性验证、信息发布的不可抵赖性、以及在分布式计算中产生的来源于内部和外部的攻击的所有信息安全问题。

密码学是数学和计算机科学的分支，同时其原理大量涉及信息论（但是在国内学科中“密码学”学科是军事学门类一级学科“军队指挥学”下的二级学科）。同时，我们生活中常用的密码(password)虽然也是密码学研究的对象，但是和密码学中更常见的秘钥(key)、密码算法(cipher, cypher, encode, code)是不一样的。

古代中国就记录了密码学的使用，周朝兵书《六韬．龙韬》中写姜子牙征战时与主将通信的方式使用阴符和阴书，阴符是以八等长度的符来表达不同的消息和指令，至于阴书则运用了移位法，把书一分为三，分三人传递，要把三份书重新拼合才能获得还原的信息。

古时西方由于字母少，发展出了接近现代密码学的密码，比如转置密码：将字母顺序重新排列，例如help me变成ehpl em；凯撒密码：每个字母被往后位移三格字母所取代；映射密码：凯撒密码的升级版，把字母随意一一配对互换。

到了中世纪，西方发明出了多字符加密法，最典型的例子是维吉尼亚加密法：加密重复使用到一个关键字，用哪个字母取代端视轮替到关键字的哪个字母而定。这个关键字可以看作是秘钥，假如用秘钥ABC加密apple，那先重复秘钥到等长ABCAB，然后对应着移位，a移位A对应的量，p移位B对应的量…e移位B对应的量。

在一战时期，西方打仗时使用的就是类似上面这样的加密方式，用人手+密码本进行加密，而二战时，德国就发明了密码机，用机械代替人手。

德国雪毕伍斯发明了恩尼格码密码机（ENIGMA，直译为“谜”），下面这个视频介绍了这个密码机。

158,962,555,217,826,360,000 (Enigma Machine) - Numberphile - YouTube

下面这个C站的纪录片介绍了当时的密码战

【央视】丘吉尔智斗希特勒，英国如何用密码战抗击德国？智破密码 密码风云（三）_哔哩哔哩_bilibili

第二次世界大战后计算机与电子学的发展促成了更复杂的密码，而且计算机可以加密任何二进制形式的资料，不再限于书写的文字，以语言学为基础的破密术因此失效。多数计算机加密的特色是在二进制字符串上操作，而不像经典密码学那样直接地作用在传统字母数字上。然而，计算机同时也促进了破密分析的发展，抵消了某些加密法的优势。

现代密码学的一个特点是，即使敌人知道了使用何种算法。对好的加密法来说，密钥的秘密性理应足以保障资料的机密性，这被叫做柯克霍夫原则。现代密码学还分成了对称密码学和非对称密码学，1976年以前的加密算法都基于对称算法，之后，非对称算法（公钥算法）被Diffie和Hellman发明了。如今，对称算法（DES、AES）和非对称算法（RSA）都广泛应用于各方面。

对称密码学

如图，对称密码学说的就是编码和解码使用同一个秘钥的加密算法，加密算法可以被公开，发送和接收双方要事先得到同一个秘钥。常见的对称加密算法有AES、ChaCha20、3DES、Salsa20、DES、Blowfish、IDEA、RC5、RC6、Camellia以及我国的SM1。

DES

DES是一种对称密钥加密块密码算法，使用56位秘钥对64位明文块进行加密。对于已经转换成二进制的明文，需要将其分解成以64为单位的分组，然后每组都使用秘钥进行加密。DES作为强加密，拥有混淆(Confusion)和扩散(Diffusion)特征，混淆指的是秘钥和密文之间关系尽可能模糊，扩散指的是一个明文符号的影响能波及到多位密文（即改动一个位就会导致密文发生较大变化）。

如图，DES加密过程主要阶段为：

graph LR
A(64bit明文) --> B[初始置换IP]
B --> C[16轮加密变换]
C --> D[逆初始置换IP]
D --> E(64bit密文)

初始置换IP就是简单的把明文按照某种规则替换，比如把第1位替换成58位、第2位替换成50位……

16轮加密变换每一轮都需要一个48bit的轮秘钥$K_i$，由那个56bit的秘钥经过置换和移位算法产生。

每一轮的变换如下图，64bit的输入分成左半边和右半边，每次只变换一半，输出的左半总是输入的右半，输出的右半是$左半 \oplus f(右半)$。这个f分成E盒、S盒和置换P。E盒把32位的输入拓展成48位的输出，这增加了DES的扩散特性。然后48位的秘钥和这个48位的输出进行XOR，结果送进S盒生成32位输出，S盒是DES的核心，是算法中唯一的非线性元素，提供了DES的混淆特性（非线性：$S(a) \oplus S(b) \neg S(a+b)$）。之后输入进P盒置换得到$f(右半)$。

进行16轮次这样的加密后，再逆置换IP就能得到最终的密文

DES的解密十分简单，和加密过程几乎一样，改变的只有轮秘钥$K_i$的顺序，将$K_i$反向就是解密过程。

目前DES已经不再安全，56bit的秘钥太短了，破解DES的方式主要是暴力攻击，2008年有人就在一天以内暴力破解出了DES。

DES有10个不那么安全的秘钥，很容易被破解，但是这数量很少，可以忽略。

AES

AES是用来替换DES的高级加密标准，分别有AES-128、AES-192和AES-256三种方案，里面的数字就是秘钥的位数。AES还有五种加密模式，即CBC、ECB、CTR、OCF、CFB，使用时要注意秘钥长度和加密模式的选择。

AES和DES很像，都是分组加密的算法，AES加密的是128bit的明文块，同时AES的解密也很简单，就是把加密流程倒置。加密的流程如下图：

AES和DES都是照顾了硬件的加密算法，能够高效安全地加密，现在AES仍然是最流行的加密算法之一。截至2006年，针对AES唯一的成功攻击是旁道攻击或社会工程学攻击。

非对称密码学

如图，非对称密码学使用两个秘钥，一个是公开秘钥(public key)，一个是私有秘钥(private key)；公钥用来加密，私钥用来解密；公钥可以公开，而私钥不能公开。直观来看，这种加密方式就像邮箱（不是电子邮箱！！），邮差可以随意将信从小缝投入你的信箱，但是他无法拿出来，只有你用钥匙才能打开信箱取出信件。

目前常用的非对称密码有RSA、DH、DSA、ECDH、ECDSA。

非对称密码学的特点

非对称密码解决了对称密码的三个问题：秘钥分配、秘钥数量、用户欺骗。

秘钥分配指的是虽然用秘钥传输密文是安全的，但是秘钥本身还得保密，假如你想要和地球另一边的人使用对称加密方式进行通信，你得先找到方法把通信的秘钥安全送到他那。而非对称密码可以安全地公布公钥。

秘钥数量问题指的是n个用户假如要互相通信，那就需要$\frac{n(n-1)}{2}$个秘钥，每个人都要保存$n-1$个秘钥，这样太麻烦了。

用户欺骗则是一种更巧妙的问题，在对称通信中，AB双方都有相同的秘钥，假如A是用户，B是淘宝，A向B发送了购买一件商品的加密信息，但是A后来又后悔了，于是A欺骗说：“我没有发送这条信息，既然B也有秘钥，那么B可以伪造这份信息。”

根据Understanding Cryptography: A Textbook for Students and Practitioners这本书，非对称密码学的主要功能如下：

1. 秘钥建立：在不安全信道上建立秘钥
2. 不可否认性：A发送了消息给B，不能否认
3. 身份标识：可确信是谁发送了加密消息
4. 加密：加密 XD

同时，非对称密码学也有缺点，那就是耗时长，比对称密码学的方法能慢上一百倍甚至一千倍。所以实践中经常混合使用这两种方法进行通信。

非对称密码学的根基

目前非对称密码学主要建立在三种计算问题上，

1. 整数分解：素数相乘得到的因式很难分解回来

2. 离散对数：假设在整数范围内，对数$x=log_b(a)$，已知$x,b$，计算$a$容易；但是已知$a,b$，计算$x$就很麻烦。

3. 椭圆曲线：椭圆曲线通用方程为$y^2=x^3+ax+b$，任何一条不垂直的直线与曲线的交点不超过3个。定义一种运算，曲线上两个点为AB，AB连直线得到C’，C’关于x轴有对称点C，称作$A \ dot \ B=C$。给定一个初始点A，一个动点B，经过n次dot运算之后得出Z，从A Z求出n比较困难。

   

数字签名和数字证书

**数字签名（英语：Digital Signature，又称公钥数字签名）**是一种功能类似写在纸上的普通签名、但是使用了公钥加密领域的技术，以用于鉴别数字信息的方法。解决的问题是：确认收到的文件没有被改动。

数字签名将非对称密码反过来使用，加密的秘钥当作私钥，解密的秘钥当作公钥，对一份文件进行签名的过程就是用Hash函数得到文件的摘要，然后用私钥对其进行加密，得到摘要的密文，即数字签名。接收者收到消息后用同一种Hash函数计算出摘要，然后用被公钥解密的数字签名来比对，假如有变动则说明消息收到篡改。

由于非对称密码的性质，公钥不能计算出私钥，所以接收者可以知道发送者是谁、消息是否被改动过，并且可以确信发送者发送了消息。

Hash函数：

又叫做单向散列函数，能够根据任意长度的消息快速生成固定长度的一个值，不同的消息生成的值不同。假如两个不同的消息生成出了同一个散列值，那就叫做碰撞，Hash具有抗碰撞性。Hash生成的值无法推算回原来的值。目前的具体Hash算法有MD4、MD5、SHA-1、SHA-256、SHA-384、SHA-512等。

Hash函数可以用作密码管理，密码明文存放在数据库不安全，所以一般存的是Hash之后的密文，用户输入密码后，服务器Hash得到的值和数据库中的密文进行比对来认证。

Hash函数还可以用来快速检索，假如要从许多文件中检索一个文件，那就可以直接用文件的Hash值来比较。

Hash最后的一个常用功能就是这里说的数字签名啦~

然而，假如一开始发送者就是别人假装的，那么接收者收到的数字签名就是坏人伪造的、收到的公钥也是坏人的，要确信公钥来自发送者，还需要数字证书技术。

**数字证书（digital certificate）或身份证书（identity certificate）**是用于公开密钥基础建设的电子文件，用来证明公开密钥拥有者的身份。此文件包含了公钥信息、拥有者身份信息（主体）、以及数字证书认证机构（发行者）对这份文件的数字签名，以保证这个文件的整体内容正确无误。

发送者发送自己的数字签名公钥时，发送一个由权威认证中心（CA）认证过的证书，这个证书由CA的私钥加密，你可以用CA的公钥解密出证书内容，然后向CA求证是否正确。这个过程相当于接收者和发送者完全信任一个第三方，而第三方能证明某个公钥属于某个发送者。

实际应用中，由于需要CA的企业太多了，所以采用分级管理，假如你不信任B，那么查看C给B的证书；假如不信任C，那么查看D给C的证书……直到最后就是Google、政府机构这些最权威的CA了。

你也可以自己给自己证明颁发证书，但是并没有什么用，浏览器或者别的电脑软件会发出警告。

参考文献：

深入浅出密码学 清华大学出版社

密码学 - 维基百科，自由的百科全书 (wikipedia.org)

对称密钥加密 - 维基百科，自由的百科全书 (wikipedia.org)

Symmetric vs. Asymmetric Encryption - What are differences? (ssl2buy.com)

DES加密教程详细解读_zxh2075的专栏-CSDN博客

Data Encryption Standard - YouTube

RSA加密算法 - 维基百科，自由的百科全书 (wikipedia.org)

椭圆曲线密码学【科普】 | 学习软件编程 (hubwiz.com)

公开密钥认证 - 维基百科，自由的百科全书 (wikipedia.org)