密码学系列之六：公钥密码体制

1. 概述

1.1 公钥密码体制的提出

随着计算机与网络技术的飞速发展，保密通信的需求越来越广泛，对称密码体制逐渐表现出以下局限性：

• 密钥分发问题：通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现。
• 密钥管理问题：在n nn个用户的网络中，每个用户要想和其它n − 1 n-1n−1个用户进行通信，须使用n − 1 n-1n−1个密钥，系统的总密钥量将达到n ( n − 1 ) / 2 n(n-1)/2n(n−1)/2。密钥的产生、保存、传递、使用和销毁等各个环节中都会变得很复杂，存在着安全隐患。
• 无法实现身份认证和消息的不可否认性

1976年，Whitefield Diffie和MartinHellman《密码学的新方向》(New Directions in Cryptography)中开创性的提出了公钥密码体制，又称非对称密码体制。

该体制中，用户A有一对密钥:加密密钥(公钥)P k P_kPk和解密密钥（私钥）S k S_kSk，两者是不同的，且从加密密钥(公钥)无法推出解密密钥（私钥）。若B要给A发送加密信息，需要在公开目录中查找A的加密密钥(公钥)P k P_kPk，用它加密消息；A收到密文后，用自己的解密密钥（私钥）S k S_kSkS解密密文。

在公钥密码体制之前，所有的密码算法都是基于代换和换位两个基本方法，建立在位(字符)方式的操作上。

公钥密码体制为密码学提供了新的理论和技术基础，开创了密码学的新纪元。

• 一方面公钥密码算法是建立在数学函数基础上的，而不是建立在位(字符)方式的操作上的
• 另一方面公钥密码算法是以非对称的形式使用两个密钥，对密钥分配、认证等方面有着深刻的意义。

1.2 公钥密码体制的原理

公钥密码体制的设计最终归结为一个陷门单向函数。陷门单向函数是满足以下条件的函数f ff：

• 正向计算容易。即如果知道密钥P k P_kPk和消息M MM，容易计算C = f P K ( M ) C=f_{P_K} (M)C=fPK(M) 。
• 不知道密钥S k S_kSk的情况下，反向计算不可行。即如果只知道加密后的消息C CC而不知道密钥S k S_kSk，则计算M = f − 1 ( C ) M=f^{-1}(C)M=f−1(C)不可行。
• 知道密钥S k S_kSk的情况下，反向计算容易。即如果知道加密消息C CC和密钥S k S_kSk，则计算M = f S k − 1 ( C ) M=f_{S_k}^{-1}(C)M=fSk−1(C)是容易的。密钥S k S_kSk相当于陷门。

公钥密码体制设计主要考虑以下几个问题：

• 公钥密码体制的安全性依赖的数学难题是什么
• 私有密钥和公开密钥是如何生成的，它们之间有着怎样的关系
• 安全的密钥长度是多少
• 如何实现公钥加密及私钥解密，反之亦然(数字签名)
• 公钥密码体制的安全分析

1.3 常见公钥密码体制

目前应用最广的公钥密码体制主要有3个:

• 基于大整数因子分解问题的RSA公钥密码体制
• 基于有限域乘法群上的离散对数问题的ElGamal公钥密码体制
• 基于椭圆曲线上离散对数问题的椭圆曲线公钥密码体制

此外，还有基于概率的平方剩余问题的公钥密码、基于格的短向量问题的公钥密码、基于余代数编码中的线性解码问题的公钥密码体制等。

2. RSA公钥密码

1978年，美国麻省理工学院的Rivest、Shamir、Adleman联合提出了RSA公钥密码体制，是第一个安全、实用的公钥码算法，已经成为公钥密码的国际标准，得到了广泛应用。

RSA的基础是数论的欧拉定理，其安全性依赖于大整数因子分解的困难性。RSA公钥密码体制可用于加密，也可用于数字签名，且具有安全、易实现等特点。

2.1 RSA密码体制

（1）公私密钥对生成

选取两个大素数p 、 q p、qp、q(不可泄露)，计算n = p q n=pqn=pq及n nn的欧拉函数φ ( n ) = ( p − 1 ) ( q − 1 ) \varphi(n) = (p-1)(q-1)φ(n)=(p−1)(q−1)

随机选取整数e ( 1 < e < φ ( n ) ) e(1<e<\varphi(n))e(1<e<φ(n))作为公钥，满足g c d ( e , φ ( n ) ) = 1 gcd(e,\varphi(n))=1gcd(e,φ(n))=1，即e ee与φ ( n ) \varphi(n)φ(n)互素

使用Euclid扩展算法计算私钥d ≡ e − 1   m o d   φ ( n ) d \equiv e^{-1} \bmod \varphi(n)d≡e−1modφ(n)，即e ee的逆元

（2）加解密算法

公钥：( e , n ) (e,n)(e,n)

私钥：d dd

加密：c ≡ m e   m o d   n c \equiv m^e \bmod nc≡memodn

解密：m ≡ c d   m o d   n m \equiv c^d \bmod nm≡cdmodn

（3）参数选择

素数p pp和q qq的选取应满足以下要求:

• 为避免椭圆曲线因子分解法，p pp和q qq的长度相差不能太大。如使用1024bit的数n nn，则p pp和q qq的模长都大致在512bit
• p pp和q qq差值不应该太小。如果p − q p-qp−q太小，则p ≈ q p\approx qp≈q，因此p ≈ n p\approx \sqrt{n}p≈n，故n nn可以简单地用所有接近n \sqrt{n}n的奇整数试除而被有效分解。
• g c d ( p − 1 , q − 1 ) gcd(p-1,q-1)gcd(p−1,q−1)应该尽可能小，从而减少不动点个数。
• p pp和q qq应为强素教，即p − 1 p-1p−1和q − 1 q-1q−1都应有大的素因子。

另外，为了防止低指数攻击，e ee和d dd不能选取太小的数。

2.2 RSA公钥密码安全性

RSA密码体制的安全性主要依赖于整数因子分解问题，分解模数n nn的素因子是攻击RSA最直接的方法。如果能够对模数n nn进行分解，便可算出φ ( n ) = ( p − 1 ) ( q − 1 ) \varphi(n)=(p-1)(q-1)φ(n)=(p−1)(q−1)，公钥d dd关于私钥e ee满足:d × e = 1 m o d ( φ ( n ) ) d \times e=1mod(φ(n))d×e=1mod(φ(n))，便不难求出私钥e ee，从而破解RSA公钥密码体制。

较早的因子分解分析法是试除法，基本思想是一个密码分析者完全尝试小于n nn的所有素数，直到因子找到。根据素数理论，尝试的次数上限为2 n log ⁡ n \frac{2\sqrt{n}}{\log\sqrt{n}}logn2n。但是对于大数n nn，这种方法的资源消耗在现实中是不可能实现的。

后来出现了一些比较重要的因子分解分析法，包括Pollard在1974年提出的p − 1 p-1p−1因子分解法、Williams提出的p + 1 p+1p+1因子分解法、二次筛(Quadratic Sieve)因子分解法、椭圆曲线因子分解法、数域筛(Number Field Sieve)因子分解法等。

3. ElGamal公钥密码

ElGamal公钥密码体制由T.ElGamal于1985年提出，该体制基于有限域上离散对数问题，既可用于加密，又可以用于数字签名。由于其较好的安全性，且同一明文在不同的时刻会生成不同的密文，在实际中得到了广泛的应用，尤其在数字签名方面的应用，著名的美国数字签名标准(DSS，Digital Signature Standard)其实就是ElGamal签名方案的一种变形。

(1)公私密钥对生成

随机选择一个大素数p pp，且要求p − 1 p-1p−1有大素数因子，g ∈ Z p ∗ g \in \boldsymbol Z^{*}_pg∈Zp∗是一个本原元(Z p Z_pZp是一个有p pp个元素的有限域，Z p ∗ Z^{*}_pZp∗是Z p Z_pZp中的非零元构成的乘法群)

选一个随机数x ( 1 < x < p − 1 ) x(1<x<p-1)x(1<x<p−1)作为私钥，计算y ≡ g x   m o d   p y \equiv g^x \bmod py≡gxmodp，公钥为( y , g , p ) (y,g,p)(y,g,p)

(2)加解密算法

公钥：( y , g , p ) (y,g,p)(y,g,p)

私钥：x xx

加密：C = ( c , c ′ ) C = (c,c^{'})C=(c,c′)，其中c ≡ g r   m o d   p , c ′ ≡ m y r   m o d   p c \equiv g^{r} \bmod p, c^{'} \equiv m y^{r} \bmod pc≡grmodp,c′≡myrmodp

解密：m ≡ ( c ′ / c x )   m o d   p m \equiv (c^{'}/c^{x}) \bmod pm≡(c′/cx)modp

ElGamal公钥密钥体制每次加密运算需要选择一个随机数，密文既依赖于明文，又依赖于选择的随机数，因此对于同一个明文，不同的时刻生成的密文不同。此外，ElGamal加密使得消息扩展了两倍，即密文的长度是对应明文长度的两倍。

4. 其他公钥密码体制

（1）MH背包公钥密码

背包算法是由Ralph Merkle和Martin Hellman于1978年提出的，它是第一个公钥密码算法，实现了如何将NP完全问题用于设计公钥密码算法，其安全性基于背包难题。背包问题是NP完全类问题（随着背包中物品数目的增多而计算量呈指数增长），至今没有多项式时间的求解方法。

1983年Shamir发现了MH密码算法变换的缺陷，即可以从普通的背包向量重构出超递增背包向量,利用“陷门对”及公钥成功地破解了私钥，从而证明MH背包密码是不安全的。

(2) Rabi公钥密码

1979年，M.O.Rabin在论文《Digital Signature and Public-Key as Factorization》中提出了一种新的公钥密码体制，即Rabin公钥密码体制，该体制是**基于合数模下求解平方根困难性(等价于分解大整数)**构造的一种公钥密码体制。

Rabin公钥密码体制是RSA钥密码体制的特例，它不是以一一对应的陷门单向函数为基础，对同一密文，可能有两个以上对应的明文。破译该体制等价于对大整数的因子分解。

（3）椭圆曲线公钥密码

1985年，Koblitz和Miller将椭圆曲线引入密码学，提出了基于有限域G F ( p ) GF(p)GF(p)的椭圆曲线上的点集构成群，在这个群上定义离散对数系统并构造出基于离散对数的一类公钥密码体制，即椭圆曲线密码体制（ECC，Elliptic Curve Cryptosystem），其安全性基于椭圆曲线上离散对数问题（ECDLP，Elliptic Curve Discrete Logarithem Problem）的难解性.

基于椭圆曲线上离散对数问题被公认要比整数因子分解问题(RSA密码体制的基础)和基于有限域的离散对数问题(ElGamal密码体制的基础)难解得多。因此，ECC仅需要较小的密钥长度就可提供与RSA和ElGamal相当的安全性（ECC的160位密钥就可达到RSA的1024位密钥的安全水平）。

（4）Goldwasser-Micali概率公钥密码

1984年S.Goldwasser与S.Micali提出了概率公钥密码体制的概念，该体制的安全性基于数论中的平方剩余问题(也叫二次剩问题)的难解性。

在Goldwasser-Micali概率公钥密码系统中，对于固定的明文m mm和加密密钥k kk,消息发送者在加密时引入随机数x xx.当引入不同的x xx时，明文m mm所对应的密文也就不同。即，相同的明文m mm可对应多个不同的密文c cc。由于每次加密是针对每个明文比特选取一个随机数而计算出相应的密文，因而称该密码体制为概率公钥密码体制。由于加密后数据扩展了log ⁡ 2 n \log_2{n}log2n倍,因此用该密码体制进行加密时运算量大,速度慢,适用于单个二进制加密、解密。