公钥密码学算法类型综述

概念

公开密钥密码学（英语：Public-key cryptography）也称非对称式密码学（英语：Asymmetric cryptography）是密码学的一种算法，它需要两个密钥，一个是公开密钥，另一个是私有密钥；公钥用作加密，私钥则用作解密。

使用公钥把明文加密后所得的密文，只能用相对应的私钥才能解密并得到原本的明文，最初用来加密的公钥不能用作解密。由于加密和解密需要两个不同的密钥，故被称为非对称加密；不同于加密和解密都使用同一个密钥的对称加密。

公钥可以公开，可任意向外发布；私钥不可以公开，必须由用户自行严格秘密保管，绝不透过任何途径向任何人提供，也不会透露给被信任的要通信的另一方。

公钥密码，又称非对称密码，比较常见的是基于以下三种数学难题的公钥密码体制；

1. 大数因子分解难解性（RSA）

2. 离散对数难解性（ElGamal）

3. 椭圆曲线离散对数难解性（ECC）

历史

公钥加密思想最早由瑞夫·墨克在 1974 年提出，之后在 1976 年。惠特菲尔德·迪菲与马丁·赫尔曼两位学者以单向函数与单向暗门函数为基础，为发讯与收讯的两方创建密钥。

瑞夫·查尔斯·墨克（英语：Ralph Charles Merkle，1952 年 2 月 2 日－），生于美国，计算机科学家，对于 公开密钥加密 技术有重大贡献。1979 年在斯坦福大学取得电机工程博士学位。博士论文主题为〈加密，授权与公开金钥系统〉（Secrecy, authentication and public key systems）。

惠特菲尔德·迪菲（Whitfield Diffie），1944 年出生于 美国华盛顿 特区，现代密码学之父，公钥密码学先驱，2015 年 图灵奖 得主，美国国家工程院院士，英国皇家学会 外籍院士。

惠特菲尔德·迪菲于 1965 年获得 麻省理工学院 数学专业学士学位；1965 年至 1969 年担任 MITRE公司 研究助理；2015 年获得 ACM 图灵奖；2017 年当选为美国国家工程院院士。

马丁·赫尔曼，密码学和网络安全技术专家，主要论文有《密码学新动向》（New Directions in Cryptography）。迪菲与赫尔曼 1976 年发表了论文《密码学新动向》，在其中阐述了关于公开密钥加密算法的新构想，即在一个完全开放的信道内，人们无需事先约定，便可进行安全的信息传输。获得 2015 年度图灵奖。

单向函数 (One-way function) 是一种具有下述特点的单射函数：对于每一个输入，函数值都容易计算（多项式时间），但是给出一个随机输入的函数值，算出原始输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。 单向函数是否存在仍然是计算机科学中的一个开放性问题。

给定任意两个集合 X 和 Y。 函数 f：X→Y 称为单向的，如果对每一个 x 属于 X，很容易计算出函数 f（x）的值，而对大多数 y 属于 Y，要确定满足 y=f（x）的 x 是计算上困难的 (假设至少有这样一个 x 存在)。注意，不能将单向函数的概念与数学意义上的不可逆函数的概念混同，因为单向函数可能是一个数学意义上可逆或者一对一的函数，而一个不可逆函数却不一定是单向函数。

还没有人能够从理论上证明单向函数是存在的。单向函数存在性的证明将意味着计算机科学中一个最具挑战性的猜想 P=NP，即 NP 完全问题的解决，而关于 NP 完全性的理论却不足以证明单向函数的存在。有幸的是，现实中却存在几个单向函数的“候选”。说他们是“候选”，是因为他们表现出了单向函数的性质，但还没有办法从理论上证明它们一定是单向函数。

一个最简单的、大家熟知的“侯选”单向函数就是整数相乘。众所周知，不管给定两个多大的整数，我们很容易计算出它们的乘积，而对于一个 300 位左右的十进制整数，即使已知它是两个大小差不多（150 位左右的十进制数）的素数之积，用世界上计算能力最强的计算机，也没有办法在一个合理的时间内分解出构成这个整数的两个素数因子来。这里讲的“合理的时间”是指一个可度量的相当长的时间，比如人类或者地球的寿命等。

**单向函数不能直接用作密码体制，因为它的求逆困难，用它加密的信息谁都不能解密。**但是，单向函数在密码学领域里却发挥着非常重要的作用。

一个最简单的应用就是口令保护。我们熟知的口令保护方法是用对称加密算法进行加密。系统方只存放口令经单向函数运算过的函数值，验证是将用户口令重新计算函数值与系统中存放的值进行比对。动态口令认证机制多是基于单向函数的应用来设计的。

单向函数的另一个应用是大家熟知的用于数字签名时产生信息摘要的单向散列函数。

有些学者把现实中使用的密码算法分成三类，单向散列函数就是其中很重要的一类，另外两类分别是公开钥 (或非对称、双钥) 算法和秘密钥 (或对称、单钥) 算法。单向函数是这三类算法共同的基础。

发展和分类

最开始的情况：信息明文传递

但是出现了缺陷：中间信息传递的过程中可能被人（中间人）截获，可能导致：

1. 机密、隐私的信息被获取

2. 传递的关键信息被恶意改变

于是发送者和接受者找到一种方法，让中间人看不懂，这样就有效防止了机密、隐私信息被获取

因为即使传递的信息被获取，在被解密之前这个信息就是无用的信息

这里用一个比喻：一个带有锁的小箱子

（下面为演示）

私钥密码产生的原因：

1. 简单和高效： 私钥密码系统是最早的密码系统之一，它们通常基于置换和替换的原理，简单而高效。由于密钥是对称的，因此加密和解密的速度较快，适用于大量数据的加密和解密操作。

2. 适用于封闭环境： 在某些情况下，发送方和接收方在物理上是相互信任的，因此可以共享同一把密钥而不必担心密钥的安全性。在这种封闭环境下，私钥密码系统是一种简单而有效的加密方式。

3. 密钥管理简单： 私钥密码系统只需要管理一把密钥，因此密钥管理相对简单。在小规模系统中，可以轻松地管理和维护密钥，不需要复杂的密钥分发和更新机制。

公钥密码产生的原因：

1. 解决密钥配送问题： 对称密钥算法在使用过程中需要发送方和接收方共享同一把密钥，但是如何安全地将密钥传输给对方是一个挑战。公钥密码系统通过使用公钥和私钥，避免了密钥配送问题，公钥可以公开发布而私钥保留在接收方手中。

2. 提高通信安全性： 对称密钥算法存在一个重要问题是密钥管理的复杂性，特别是在大规模系统中。如果密钥泄漏或被破解，所有的通信都可能会暴露在风险之下。公钥密码系统通过使用非对称密钥对，降低了密钥管理的复杂性，并提高了通信的安全性。

3. 数字签名和身份验证： 公钥密码系统不仅可以用于加密通信，还可以用于数字签名和身份验证。发送方可以使用自己的私钥生成数字签名，接收方使用发送方的公钥验证数字签名，从而确保消息的完整性和真实性。

数据加密类型

背包算法

背包算法是由 Merkle 和 Hellman 开发的背包算法。只能用于加密，后来由 Shamir 将它改进，使之也能用于数字签名；

背包算法的安全性起源于背包难题，他是一个 NP 完全问题，但后来发现该算法并不安全，但是由于它证明了如何将 NP 完全问题用于公开秘钥密码学，因此，值得去学习。

RSA

一、历史

对称加密模式有一个最大弱点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥，就成了最头疼的问题。

1976 年，两位美国计算机学家 Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为 “Diffie-Hellman 密钥交换算法 “。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。

这种新的加密模式被称为 ” 非对称算法 ”。

（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。

（2）甲方获取乙方的公钥，然后用它对信息加密。

（3）乙方得到加密后的信息，用私钥解密。

如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

1977 年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做 RSA 算法。从那时直到现在，RSA 算法一直是最广为使用的 ” 非对称加密算法 “。毫不夸张地说，只要有计算机网络的地方，就有 RSA 算法。

这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长 RSA 密钥是 768 个二进制位。也就是说，长度超过 768 位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024 位的 RSA 密钥基本安全，2048 位的密钥极其安全。

二、数学概念

任意给定正整数 n，请问在小于等于 n 的正整数之中，有多少个与 n 构成互质关系？

计算这个值的方法就叫做欧拉函数，以φ(n) 表示。在 1 到 8 之中，与 8 形成互质关系的是 1、3、5、7，所以 φ(n) = 4。

欧拉函数的用处，在于欧拉定理。” 欧拉定理 ” 指的是：

如果两个正整数 a 和 n 互质，则 n 的欧拉函数 φ(n) 可以让下面的等式成立：

$$a^{\varphi (n)}{\equiv }_1(modn)$$

也就是说，a 的φ(n) 次方被 n 除的余数为 1。或者说，a 的φ(n) 次方减去 1，可以被 n 整除。比如，3 和 7 互质，而 7 的欧拉函数φ(7) 等于 6，所以 3 的 6 次方（729）减去 1，可以被 7 整除（728/7=104）。

欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。

欧拉定理可以大大简化某些运算。比如，7 和 10 互质，根据欧拉定理，

已知 φ(10) 等于 4，所以马上得到 7 的 4 倍数次方的个位数肯定是 1。

欧拉定理是 RSA 算法的核心。理解了这个定理，就可以理解 RSA。

还剩下最后一个概念：

如果两个正整数 a 和 n 互质，那么一定可以找到整数 b，使得 ab-1 被 n 整除，或者说 ab 被 n 除的余数是 1。

这时，b 就叫做 a 的模反元素，用于计算私钥

比如，3 和 11 互质，那么 3 的模反元素就是 4，因为 (3 × 4)-1 可以被 11 整除。显然，模反元素不止一个， 4 加减 11 的整数倍都是 3 的模反元素 {…,-18,-7,4,15,26,…}，即如果 b 是 a 的模反元素，则 b+kn 都是 a 的模反元素。

欧拉定理可以用来证明模反元素必然存在。

可以看到，a 的 φ(n)-1 次方，就是 a 的模反元素。

---

好了，需要用到的数学工具，全部介绍完了。RSA 算法涉及的数学知识，就是上面这些，下一次我就来介绍公钥和私钥到底是怎么生成的。

---

三、密钥的生成步骤

前面我介绍了一些数论知识。 有了这些知识，我们就可以看懂 RSA 算法。这是目前地球上最重要的加密算法。

第一步，随机选择两个不相等的质数 p 和 q。

选择了 61 和 53。（实际应用中，这两个质数越大，就越难破解。）p=61 q=53

第二步，计算 p 和 q 的乘积 n。

n = 61×53 = 3233

n 的长度就是密钥长度。3233 写成二进制是 110010100001，一共有 12 位，所以这个密钥就是 12bit。实际应用中，RSA 密钥一般是 1024 位，重要场合则为 2048 位。

第三步，计算 n 的欧拉函数φ(n)。

根据公式：

φ(n) = (p-1)(q-1)

算出φ(3233) 等于 60×52，即 3120。

第四步，在 1 和φ(n) 之间随机选择一个整数 e（e 和φ(n) 需要互质）

在 1 到 3120 之间，随机选择了 17。（实际应用中，常常选择 65537。）

第五步，计算 e 对于φ(n) 的模反元素 d。

所谓模反元素就是指有一个整数 d，可以使得 ed 被φ(n) 除的余数为 1。

ed ≡ 1 (mod φ(n))

这个式子等价于

ed - 1 = kφ(n)

于是，找到模反元素 d，实质上就是对下面这个二元一次方程求解。

ex + φ(n)y = 1

已知 e=17, φ(n)=3120，

17x + 3120y = 1

算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。

至此所有计算完成。

第六步，将 n（起初选择的两个质数的乘积）和 e（1 和φ(n) 之间选择的数）封装成公钥，n 和 d 封装成私钥。

在例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。

实际应用中，公钥和私钥的数据都采用 ASN.1 格式表达。

RSA 算法的可靠性

回顾上面的密钥生成步骤，一共出现六个数字：

p 　　q（选择的两个质数） 　　n（p*q） 　　φ(n)（n 的欧拉函数值） 　　e（1 和φn 之间随机选择的，非φn 因子的质数） 　　d（ex + φ(n)y = 1 x 的整数解）

这六个数字之中，公钥用到了两个（n 和 e），其余四个数字都是不公开的。其中最关键的是 d，因为 n 和 d 组成了私钥，一旦 d 泄漏，就等于私钥泄漏。

那么，有无可能在已知 n 和 e（公钥）的情况下，推导出 d（私钥）？

下面是计算 d 的步骤

（1）ed≡1 (mod φ(n))（就是 ed - 1 = kφ(n)）。只有知道 e 和φ(n)，才能算出 d。

（2）φ(n)=(p-1)(q-1)。只有知道 p 和 q，才能算出φ(n)。

（3）n=pq。只有将 n 因数分解，才能算出 p 和 q。

结论：如果因数分解 n 得到 pq，d 就可以算出，也就意味着私钥被破解。

可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。

你可能觉得：把一个数分解成质数的乘积不是很难

那么请你分解下面这个数：（逗号是分级）

1230，1866，8453，0117，7551，3049，4958，3849，6272，0772，8535，6959，5334，7921，9732，2452，1517，2640，0507，2636，5751，8745，2021，9978，6469，3899，5647，4942，7740，6384，5925，1925，5732，6303，4537，3154，8268，5079，1702，6122，1429，1346，1670，4292，1431，1602，2212，4047，9274，7377，9408，0665，3514，1959，7459，8569，0214，3413

事实上它等于这样两个质数的乘积：

33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 × 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

事实上，这大概是人类已经分解的最大整数（232 个十进制位，768 个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长 RSA 密钥就是 768 位。

四、加密与解密

有了公钥和密钥，就能进行加密和解密了。

（1）加密要用公钥 (n,e)

假设鲍勃要向爱丽丝发送加密信息 m，他就要用爱丽丝的公钥 (n,e) 对 m 进行加密。这里需要注意，m 必须是整数（字符串可以取 ascii 值或 unicode 值），且 m 必须小于 n。

所谓 ” 加密 “，就是算出下式的 c：

$$m^e\equiv c(modn)$$

爱丽丝的公钥是 (3233, 17)，鲍勃的 m 假设是 65，那么可以算出下面的等式：

$$65^{17}\equiv 2790(mod3233)$$

于是，c 等于 2790，鲍勃就把 2790 发给了爱丽丝。

（2）解密要用私钥 (n,d)

爱丽丝拿到鲍勃发来的 2790 以后，就用自己的私钥 (3233, 2753) 进行解密。可以证明，下面的等式一定成立：

$$c^d\equiv m(modn)$$

也就是说，c 的 d 次方除以 n 的余数为 m。现在，c 等于 2790，私钥是 (3233, 2753)，那么，爱丽丝算出

$$2790^{2753}\equiv 65(mod3233)$$

因此，爱丽丝知道了鲍勃加密前的原文就是 65。

至此，” 加密 — 解密 ” 的整个过程全部完成。

我们可以看到，如果不知道 d，就没有办法从 c 求出 m。而前面已经说过，要知道 d 就必须分解 n，这是极难做到的，所以 RSA 算法保证了通信安全。

你可能会问，公钥 (n,e) 只能加密小于 n 的整数 m，那么如果要加密大于 n 的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种 ” 对称性加密算法 “（比如 DES），用这种算法的密钥加密信息，再用 RSA 公钥加密 DES 密钥。

Rabin

Rabin 是 RSA 算法的一种特例，它使用的是平方剩余问题（Quadratic Residuosity Problem）而不是 RSA 算法中使用的欧拉函数（Euler’s Totient Function）。

在 Rabin 算法中，公钥和私钥都是一个大素数。加密过程如下：

$$C=P^{2}modN$$

其中：

• C 是密文

• P 是明文

• N 是公钥

解密过程如下：

$$P=C^{0.5}modN$$

其中：

• P 是明文

• C 是密文

• N 是私钥

Rabin 算法的安全性依赖于平方剩余问题，即很难确定一个数是否是一个大素数的平方剩余。

Rabin 算法的优点是计算速度快，缺点是安全性不如 RSA 算法。

ElGamal

EIGamal 产生的原因：

ElGamal 算法是一种非对称加密算法，在 1985 年由塔希尔•盖莫尔提出，主要用于加密和数字签名。它的产生源于对 RSA 算法的补充和拓展。具体来说，ElGamal 算法的产生主要有以下几个原因：

1. 安全性需求增加： RSA 算法在 1977 年被提出时是一种非常强大的加密算法，但随着计算能力的增强和密码学研究的进展，一些与 RSA 相关的攻击方法逐渐被发现，使得 RSA 算法的安全性受到了挑战。因此，需要一种更为安全的替代方案。

2. 多样性和选择： 在密码学中，通常会提供多种算法以供选择，以适应不同的安全需求和应用场景。ElGamal 算法的提出丰富了非对称加密算法的选择，并提供了一种新的加密和数字签名方案。

3. 数字签名需求增加： 除了加密外，数字签名也是信息安全领域中的重要需求。ElGamal 算法不仅可以用于加密，还可以用于数字签名，因此能够满足更广泛的安全需求。

4. 理论研究的推动： ElGamal 算法的提出也源于密码学理论研究的推动。许多密码学家在研究 RSA 算法的同时，也在探索其他可能的加密方案，并最终提出了 ElGamal 算法作为 RSA 算法的一个重要补充。

ElGamal 算法的产生是为了满足安全性需求增加、提供多样性和选择、满足数字签名需求以及推动密码学理论研究等多方面原因。它的出现丰富了密码学领域的算法选择，为信息安全提供了更多的保障。

EIGamal 算法介绍：

Ecc

椭圆曲线密码学（英语：Elliptic Curve Cryptography，缩写：ECC）是一种基于椭圆曲线数学的公开密钥加密算法。

CC 的主要优势是它相比 RSA 加密算法使用较小的密钥长度并提供相当等级的安全性。ECC 的另一个优势是可以定义群之间的 双线性映射，基于 Weil 对 或是 Tate 对；双线性映射已经在密码学中发现了大量的应用，例如 基于身份的加密。

数字签名类型

RSA 数字签名

DSA

数字签名算法（DSA）是用于数字签名的联邦信息处理标准之一，基于模算数和离散对数的复杂度。DSA 是 Schnorr 和 ElGamal 签名方案的变体。

美国国家标准技术研究所（NIST）于 1991 年提出将 DSA 用于其数字签名标准（DSS），并于 1994 年将其作为 FIPS 186 采用。已对初始规范进行了四次修订。DSA 已获得专利，但 NIST 已将此专利在全球范围内买断式授权。

DSA 的椭圆曲线密码学版本是 ECDSA。

DSA 算法工作在框架公钥加密、模算数和离散对数问题，这被认为是难解问题。该算法使用由公钥和私钥组成的密钥对。私钥用于生成消息的数字签名，并且可以通过使用签名者的相应公钥来验证这种签名。数字签名提供信息鉴定（接收者可以验证消息的来源），完整性（接收方可以验证消息自签名以来未被修改）和不可否认性（发送方不能错误地声称它们没有签署消息）。

DSA（Digital Signature Algorithm）是一种基于整数分解难题的数字签名算法，其原理依赖于离散对数问题的难解性。DSA 是 Schnorr 签名算法的一个变种，被设计用来提供数字签名的安全性。

ECDSA

ECDSA 是 Elliptic Curve Digital Signature Algorithm 的简称，主要用于对数据（比如一个文件）创建数字签名，以便于你在不破坏它的安全性的前提下对它的真实性进行验证。可以将它想象成一个实际的签名，你可以识别部分人的签名，但是你无法在别人不知道的情况下伪造它。而 ECDSA 签名和真实签名的区别在于，伪造 ECDSA 签名是根本不可能的。

你不应该将 ECDSA 与用来对数据进行加密的 AES（高级加密标准）相混淆。ECDSA 不会对数据进行加密、或阻止别人看到或访问你的数据，它可以防止的是确保数据没有被篡改。

原理非常简单，有一个数学方程，在图上画了一条曲线，然后你在这条曲线上面随机选取了一个点作为你的原点 (point of origin)。接着你产生了一个随机数，作为你的私钥 (Private key)，最后你用上面的随机数和原点通过一些复杂的魔法数学方程得到该条曲线上面的第二个点，这是你的公钥 (Public key)。

当你想要对一个文件进行签名的时候，你会用这个私钥（随机数）和文件的哈希（一串独一无二的代表该文件的数）组成一个魔法数学方程，这将给出你的签名。签名本身将被分成两部分，称为 R 和 S。为了验证签名的正确性，你只需要公钥（用私钥在曲线上面产生的点）并将公钥和签名的一部分 S 一起代入另外一个方程，如果这个签名是由私钥正确签名过的数字签名，那么它将给出签名的另外一部分 R。简单来说，一个数字签名包含两个数字，R 和 S，然后你使用一个私钥来产生 R 和 S，如果将公钥和 S 代入被选定的魔法数学方程给出 R 的话，这个签名就是有效的。仅仅知道公钥是无法知道私钥或者创建出数字签名

身份基加密

公钥身份化

该定义是传统公钥加密的演变，在身份基加密中直接将用户的身份（唯一标识特征）作为公钥。这样一来，每个人只需要保存一个私钥即可。

基于身份的加密方案（IBE）的思想，最早是由 Shamir 在 1984 年提出。方案中不必使用证书，直接将用户的身份（唯一标识特征）作为公钥，这样简化了公钥基础设施（PKI）中基于证书的密钥管理。该思想提出之后一直没有合适工具实现，成为一个公开问题。直到 2001 年，Dan Boneh 和 Matt Franklin 利用椭圆曲线上的双线性映射（即 Weil 对和 Tate 对）实现了第一个实用的身份基加密方案，这为身份基加密的研究开启了新的篇章。身份基加密主要由以下四个算法构成：

• 初始化算法（Setup） 给定安全参数，输出一个主公钥 mpk 和主私钥 msk。

• 密钥提取算法 (Keygen) 输入主私钥 msk 和身份串 ID，输出该身份下的私钥 skID。

• 加密算法 (Enc) 输入主公钥 mpk、身份串 ID 以及明文消息 x，输出密文 c。

• 解密算法 (Dec) 输入身份私钥 SKID 和密文 c，输出明文消息 x（或者解密失败）