3.3　非对称密钥加密

加密用哪个密钥、解密也必须用哪个，似乎就像锁定保险箱用这把钥匙、打开保险箱就一定用这把那样必然。然而这种“自然而然”的状况在1976年被Diffie和Hellman打破了，他们在《密码学新方向》一文中提出的技术颠覆了“一把钥匙开一把锁”的思维定式，开创了密码学的新领域。

3.3.1　非对称密钥加密技术原理

非对称密钥加密（asymmetric key cryptography）也称公开密钥加密（public key cryptography）或公钥加密、双密钥加密，其方法是使用一对密钥来加密和解密，其中一个是只有密钥拥有者自己掌握的、保密的私钥（private key），另一个是通信过程中由其他方使用的、可以公开的公钥（public key）。

公钥体制的优越性在于分离出两个相关的密钥，其中的公钥不需要保密，而私钥绝对不在网络上传输，因此就不存在密钥泄露问题。公钥和私钥的使用规则为：

•　用公钥加密的数据用且只能用对应的私钥解密。

•　用私钥加密的数据用且只能用对应的公钥解密。

假设Alice有一对密钥priKeyA和pubKeyA，Bob有priKeyB和pubKeyB，他们需要在网络上传输信息。利用非对称密钥加密技术，Alice和Bob有三种可选方法，如图3.14（a）、（b）和（c）所示，获得的效果完全不同。

（1）Alice用自己的私钥priKeyA加密，可以确保信息是由其发出的，其他人没有其私钥就无法假冒，同时Alice也不能否认其发送的信息，该过程具有确权性；但用于解密的Alice的公钥pubKeyA是公开的，说明除了Bob以外的其他人也能获得公钥并能够解密，因此方法（a）不具有保密性。

（2）Alice用Bob的公钥pubKeyB加密，使得只有握有私钥priKeyB的Bob才能解密，其他人则无法轻易解密，达到了保密的效果；但由于Bob的公钥是公开的，任何人都能进行加密发送，并不能指证该密文是Alice加密发出的，因此方法（b）不具有确权性。

（3）方法（a）和（b）从安全效果上基本上是“互补”的关系，方法（c）就是对两种方法的综合，既能确认发送者，又能保护信息的私密性。

对于公钥加密的几种方法，擅于找破绽的Bob还有话要说：“追根溯源，不管哪种方法，首先要把自己的公钥传播出去，这是一切操作的基础对不对？”

“是的。”Alice不知道Bob的葫芦里卖的什么药。

“假如有个‘中间人’攻击者拦截了你我发出的公钥，分别替换为他自己构造的密钥，会发生什么呢？”

“在方法（a）中我发送的信息你会拒绝认可，反而认可攻击者假冒我的身份发出的信息。”Alice越说越心惊，“方法（b）中攻击者可以解密我发给你的保密信息，然后可以篡改后再‘加密’发送给你。”

Alice和Bob探讨的就是公钥的安全发布问题，是公钥体系安全运行的前提条件。公钥不仅可以公开，而且是越公开越好，假如让自己的公钥变成“众所周知”，那么“中间人攻击”就没有空子可钻了。实际的网络系统中应建立严密、可靠的公钥传播机制，才能让需要者获取到真实可信的公钥。

公钥加密的重要作用是信息验证。如图3.15所示，Bob想公开自己的电子邮件地址，但又不希望被人恶意篡改，于是将名片信息用私钥加密后与名片一并发布，其他打算联络Bob却将信将疑的人就可以用Bob的公钥来验证，以确认这条信息真的是Bob发出的以及电子邮件地址真的属于Bob。

公钥加密的计算效率通常很低，甚至只有对称密钥加密方法的千分之一，因此不适合对大量的数据进行加密，一般用来加密会话密钥等短小数据。

常用的公钥加密算法有RSA、ElGamal等，目前技术含量最高、安全性最强的是ECC算法，该算法在比特币系统中得到充分运用，实现了虚拟货币资产的匿名持有和支付验证。

3.3.2　RSA算法

RSA算法于1977年被提出，以三位发明者Ron Rivest、Adi Shamir和Leonard Adleman姓氏的首字母来命名，是最早也是最著名的公开密钥加密算法，应用相当广泛。RSA算法的数学基础是数论中的欧拉（Euler）定理，安全性建立在大整数分解质数（素数）因子的困难性之上。

RSA算法公钥、私钥密钥对的生成步骤如下：

（1）选择不同的大质数p和q，计算n=p×q和φ（n）=（p-1）×（q-1）。

（2）选择大整数e，与φ（n）互质，且1＜e＜φ（n）。

（3）计算整数d，使d×e=1 modφ（n）。

（4）舍弃p和q，得：公钥pubKey={e，n}，私钥priKey={d，n}。

考查私钥的安全性：虽然攻击者可以从公开的公钥得到e和n，但以现有的数学理论成果，要分解一个整数为两个质数因子一般只能采用穷举法，而整数非常大时，计算机除法运算十分耗时，很难在有限时间内完成。1991年RSA实验室曾发起因子分解挑战赛，公布了54个十进制位数为100~617位的大整数，不论谁无论用何种方法，分解出一个即得重奖。结果在20年时间里，只有最小的18个数（二进制768位长度以下）被成功分解，可见其困难程度。虽然近年来陆续有一些数学研究成果，可以在一定程度上摆脱暴力试除，但二进制1024位乃至2048位以上大整数仍然保持相当高的安全性。既然攻击者难以分解大数n以获取至关重要的p和q，就无法获得d，因此私钥是安全的。

RSA密钥生成算法中，e与φ（n）互质的意思是两个数的最大公因数（Greatest Common Divisor，GCD）为1。可以运用辗转相除法，又名欧几里得算法（Euclidean），在判别e是否与φ（n）互质时，不需要先把两个数作质因数分解，即可直接求出最大公因数。

求解GCD的算法用代码表示如下（不失一般性，设p＞q，递归函数返回值就是p和q的最大公因数）：

此外，私钥中的d实际上是求e的modφ（n）乘法逆元，可使用扩展欧几里得算法。设求解k^-1 mod n，算法extended_euclid（k，n）程序流程如下：

使用公钥pubKey={e，n}的加密过程如下。对于明文M，若M＜n，将M作为一个大整数来计算，若M≥n，则进行分段计算：

C=M^e mod n

使用私钥priKey={d，n}的解密过程如下：

M=C^d mod n

解密与加密为互逆的运算，可简单证明如下（根据欧拉定理）：

M′=（M^e）^d mod n=M^e×d mod n=M¹ mod n=M

用私钥加密、公钥解密的计算公式同理可得。从计算方式来看，加密、解密都是指数运算，而且底和幂都是大整数，对计算机而言单次运算量很大，这正是公钥加密方法不太适用于大量信息的原因。

实际应用中应选择十进制100位以上的质数，n的长度至少要达到1024b。为了抵抗整数分解算法，对p和q另有如下要求：

（1）|p-q|很大，通常p和q的长度相近。

（2）p-1和q-1分别含有大素因子p₁和q₁。

（3）p₁-1和q₁-1分别含有大素因子p₂和q₂。

（4）p+1和q+1分别含有大素因子p₃和q₃。

3.3.3　ElGamal算法

ElGamal算法是一种公开密钥加密技术，其安全性原理依赖于计算有限域上离散对数这一难题。ElGamal密钥对的产生流程如下：

首先选择一个质数p和两个随机数g和x（g，x＜p），计算：

y=g^x mod p

则公钥为{y，g，p}，私钥为x。其中g和p可由一组用户共享。

ElGamal进行公钥加密时，设明文为M，需选择一个随机数k，使k与（p-1）互质（可采用欧几里得辗转相除法），并计算：

a=g^k mod p

b=y^kM mod p

所得（a，b）即为密文，长度是明文的两倍。用私钥解密时计算：

求解时可采用扩展欧几里得算法，先求a^x（mod p）乘法逆元，再与b相乘，以降低计算难度。

在运用ElGamal时，质数p必须足够大，且p-1应至少包含一个大质数因子，并保证g对于p-1的大质数因子不可约。ElGamal的一个不足之处是其密文长度为明文的两倍，增加了存储空间和传输带宽的占用。

3.3.4　ECC算法

椭圆曲线加密算法（Ellipse Curve Cryptography，ECC）是基于椭圆曲线理论的公钥加密技术。在数学上，对椭圆曲线的性质和功能的研究已逾150年，但是在加密技术上的应用是在1985年由Neal Koblitz和Victor Miller首次提出。与其他建立在大质数因子分解困难性基础上的加密方法不同，ECC利用椭圆曲线方程式的数学性质产生密钥，正向计算比较容易，反过来却非常困难。

与RSA方法相比，ECC可以使用164b密钥产生一个安全级相当于RSA方法的1024b密钥提供的保密强度，而且计算量较小、处理速度更快、存储空间和传输带宽占用较少，具有较大的技术优势。

与一般加密方法采用的对数据进行函数运算的方式大相径庭，椭圆曲线加密是有限离散域的、曲线上坐标点的转换，其技术原理必须从抽象的射影平面开始去理解。

1. 射影平面

平面上的两条直线只有相交、平行两种情况。相交线只有一个交点，若有两个交点则为重合；平行线没有交点。

定义平行线相交于无穷远点P_∞，如图3.16所示，这样，平面上任何两条直线都统一为有唯一的交点。P_∞具有以下性质：

（1）一条直线只有一个无穷远点，一对平行线有公共的无穷远点（即交点）。

（2）任何两条不平行的直线有不同的无穷远点（否则会造成两个交点）。

（3）平面上全体无穷远点构成一条无穷远直线。

平面上全体无穷远点（无穷远直线）与全体平常点构成射影平面（projective plane）。

对普通平面上点（x，y），令x=X/Z，y=Y/Z，Z≠0，则投影为射影平面上的点（X∶Y∶Z）。例如点（1，3）可投影为（Z∶3Z∶Z），即可为（1∶3∶1）、（2.3∶6.9∶2.3）等多种赋值。

对普通平面上的直线ax+by+c=0，作同理变换，得到对应于射影平面上的直线为aX+bY+cZ=0。

对平行线aX+bY+c₁Z=0和aX+bY+c₂Z=0，易解得Z=0，说明射影平面上平行线交点即无穷远点P_∞的坐标为（X∶Y∶0）。

2. 椭圆曲线

一条椭圆曲线（ellipse curve）是在射影平面上满足威尔斯特拉斯方程（Weierstrass）的所有点的集合。射影平面上统一的椭圆曲线方程为

Y²Z+a₁XYZ+a₃YZ²=X³+a₂X²Z+a₄XZ²+a₆Z³

椭圆曲线方程是一个齐次方程，且要求椭圆曲线上的每个点都必须是非奇异的（光滑的）、可导的，即方程的偏导数F_X（X，Y，Z）、F_Y（X，Y，Z）和F_Z（X，Y，Z）不能同时为0。

令Z=0，代入椭圆曲线方程得X=0，说明椭圆曲线上有一个无穷远点O_∞，其坐标为（0∶Y∶0）。无穷远点O_∞和普通平面上的平常点（即曲线）一起，共同组成射影平面上的椭圆曲线。

运用射影平面与普通平面的点的转换关系，椭圆曲线方程可转换为普通平面方程：

y²+a₁xy+a₃y=x³+a₂x²+a₄x+a₆

对椭圆曲线的平常点（x，y）求导，并计算过该点的切线的斜率k，有：

F_x（x，y）=a₁y-3x²-2a₂x-a₄

F_y（x，y）=2y+a₁x+a₃

椭圆曲线的形状并非如其名呈椭圆状，例如，方程Y²Z=X³+XZ²+Z³可转换为普通方程y²=x³+x+1，曲线如图3.17（a）所示；方程Y²Z=X³-XZ²可转换为普通方程y²=x³-x，曲线如图3.17（b）所示。

而且并非所有形式类似的方程都是椭圆曲线方程，例如，如图3.18（a）和（b）所示的方程Y²Z=X³+X²和Y²Z=X³就不属于椭圆曲线，因为0点为奇异点（不可导）。

3. 椭圆曲线加法

在椭圆曲线中引入阿贝尔（Abel）加法群（又称交换群）的概念，可进一步实现对椭圆曲线上的点的运算。

任意取椭圆曲线上两点P、Q（若P、Q两点重合，则作P点的切线），过两点作直线交于椭圆曲线的另一点R′，过R′做y轴的平行线交椭圆曲线于R，定义P+Q=R。可见，加法的和也在椭圆曲线上，并同样遵循加法的交换律、结合律。

例如，图3.17（b）所示的椭圆曲线方程为Y²Z=X³-XZ²，普通方程为y²=x³-x，加法运算过程如图3.19所示，其中图3.19（a）和图3.19（b）分别为P、Q重合与不重合两种情况。

如图3.20（a）所示，椭圆曲线无穷远点O_∞与椭圆曲线上一点P的连线交椭圆曲线于另一点P′，过P′作y轴的平行线必交椭圆曲线于P（两条线重合），根据加法定义，有O_∞+P=P。可见，无穷远点O_∞与普通加法中零相当，因此把O_∞称为零元。同时易知P+P′=O_∞，于是P′被称为P的负元，记作-P。如图3.20（b）所示，还可推出：如果椭圆曲线上的3个点A、B、C处于同一直线上，则其和等于零元，即A+B+C=O_∞。

再进一步，如图3.21所示，若有k个相同的点P相加，记作kP，有：

P+P+P=2P+P=3P

在图3.19所示曲线上，若已知点P、Q的坐标分别为（x₁，y₁）、（x₂，y₂），令R=P+Q，设：-R（即R′）的坐标为（x₃，y₃），R的坐标为（x₄，y₄），显然有x₃=x₄。

因为P、Q、-R三点共线，所以设共线方程为y=kx+b，分两种情况：

（1）若P≠Q（P、Q两点不重合），则直线斜率为：

（2）若P=Q（P、Q两点重合），则直线为椭圆曲线的切线，代入斜率公式可得：

因此，P、Q、-R三点的坐标值（x₁，y₁）、（x₂，y₂）、（x₃，y₃）就是椭圆曲线统一方程与共线方程组成的方程组的解（即三个交点）。将共线方程代入后得：

（kx+b）²+a₁x（kx+b）+a₃（kx+b）=x³+a₂x²+a₄x+a₆

将其整理（按次数归并）并化为一般方程为：

x³+（a₂-ka₁-k²）x²+（a₄-a₁b-2kb-ka₃）x+a₆-a₃b=0

根据三次方程根与系数的关系可知：当三次项系数为1时，-x₁x₂x₃等于常数项，x₁x₂+x₂x₃+x₃x₁等于一次项系数，-（x₁+x₂+x₃）等于二次项系数，列方程组可解出x₁、x₂、x₃，再根据共线方程可求出y₁、y₂、y₃。

由于-（x₁+x₂+x₃）=a₂-ka₁-k²，即x₄=x₃=k²+ka₁-a₂-x₁-x₂，又由于k=，即可求出：y₃=y₁-k（x₁-x₃）。

由于R就是R′作y轴平行线与曲线的交点，因此将x=x₄代入椭圆曲线统一方程，并化为一般方程，得：

根据二次方程根与系数的关系，有-（a₁x₄+a₃）=y₃+y₄，则可求出y₄=-y₃-（a₁x₄+a₃）。所得R（x₄，y₄）即为P、Q的和。

4. 有限域椭圆曲线

由于信息的明文、密文都是整数型数值，因此信息加密（即整数间的变换）应当是在有限域上进行的，域的最大值、最小值由信息长度决定（并非无穷大），而且信息是离散型的整数，所以必须对实数域上的椭圆曲线进行改进，以适合有限数量的整数运算的需要。另外，椭圆曲线的选择很重要，并不是所有椭圆曲线都适合加密。

定义有限域F_p：

（1）F_p中有p（p为质数）个元素0，1，2，…，p-2，p-1。

（2）F_p的加法是a+b≡c（mod p）。

（3）F_p的乘法是a×b≡c（mod p）。

（4）F_p的除法是a÷b≡c（mod p）。

（5）F_p的单位元是1，零元是0。

（6）F_p域内运算满足交换律、结合律、分配律。

以椭圆曲线y²=x³+ax+b为例，将其定义在F_p上，即对应y²=x³+ax+b（mod p）上的所有点（x，y）再加上无穷远点O_∞。无穷远点O_∞是零元，O_∞+O_∞=O_∞，O_∞+P=P。P（x，y）的负元是-P=P′（x，-y），有P+（-P）=O_∞。

选择质数p，应有x，y∈[0，p-1]。将这条椭圆曲线记为E_p（a，b）。选择两个小于p的非负整数a、b，满足约束条件：4a³+27b²≠0（mod p）。

以一条简单的椭圆曲线为例。设p=23，a=b=1，椭圆曲线可记为E₂₃（1，1），曲线如图3.22所示。可见离散域上的椭圆曲线已经变成一些不连续的点，其坐标均为整数。

如果已知曲线上两点P（3，10）、Q（9，7），则P的负元-P=（3，-10），即（3，13），斜率，因为2×12=1（mod 23），所以2的乘法逆元为12，即1/2，同时-12（mod 23）=11（mod 23），所以有k=11。

根据P和Q的和R（x，y）的计算公式，有：

因此P+Q的坐标为（17，20）。

另外，过P（3，10）的切线斜率k′根据公式可计算为：

则可同理计算R（x，y）的坐标为：

因此2P的坐标为（7，12），依此类推可得3P、4P及任意nP。

如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O_∞（显然（n-1）P=-P），则将n称为P的阶，若n不存在，则P是无限阶的。事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在的。

5. 椭圆曲线加密

在椭圆曲线E_p（a，b）上选择一个点G为基点（Base Point），n为阶（nG=O_∞），并选择一个整数k（k＜n）。计算K=kG，K也是椭圆曲线上的点。则点k为私钥，K为公钥（椭圆曲线E_p（a，b）和G也是公钥的组成部分）。

不难发现，给定k和G，根据加法法则，计算K很容易；但反过来，即使已知K和G，求k却是非常困难的（k是大数），唯一途径是暴力破解，但耗时漫长。这就是椭圆曲线加密算法安全性的数学依据。

椭圆曲线加密的基本原理是对曲线上的点实施变换，所以首先需要将待加密的明文数据进行编码，转化为椭圆曲线上的一个点（坐标形式），才能符合加密运算的条件。解密后的数据同样是曲线上的点，则需要反过来进行译码，恢复为明文数据的表达方式。

根据数论定义，令n为正整数，若整数a满足与n互质（即有GCD（a，n）=1），且使得x²=a（mod n）有解，则称a为模n的平方剩余，记为QR_n，否则a称为模n的平方非剩余，记为QNR_n。

设：明文m∈（0，M），M为与m相同二进制长度的最大整数。又设函数f（x）：y²=x³+ax+b（标准椭圆曲线方程），有限域E_p（a，b）元素个数为p（p为质数）。

选择整数k，满足Mk＜p，令x_i=mk+i（i=1，2，…，k-1），依次计算f（x_i）=x³+ax+b（mod p）。若找到f（x_i）是模p的平方剩余（QR_p），则用x_m表示此时的x_i，y_m表示f（x_i）的平方根，这样明文m即编码成为椭圆曲线上的点（x_m，y_m）。

译码计算非常简单，由于i∈（0，k），只需取解密后的x′_m坐标值进行除法运算并取整[x′_m/k]，即恢复明文m。

因为模p的平方剩余和平方非剩余各占一半，所以k次内找到的概率不小于1-（1/2）^k，编码成功率很高。另外也可设计其他不同的编码、译码方法。

需要进行公钥加密、私钥解密来传输保密数据时，密钥生成方法和加密、解密的操作过程如下：

（1）接收方选定一条椭圆曲线E_p（a，b），并取椭圆曲线上一点作为基点G；选择一个随机数为私钥k，并生成公钥K=kG。接收方将椭圆曲线E_p（a，b）和点K、G（即公钥）传给发送方。

（2）发送方收到公钥后，先将待传输的明文编码到E_p（a，b）上的一点M，并产生一个随机数r（r＜n）。计算C₁=M+rK和C₂=rG。发送密文C₁和C₂。

（3）接收方收到密文后，进行解密计算M′=C₁-kC₂，M′经过译码即为明文。解密运算的原理证明如下：

C₁-kC₂=M+rK-k（rG）=M+r（K-kG）=M

如需要用私钥加密原消息作签名，然后用公钥来验证签名，则密钥对由发送方生成，密钥生成方法不变，公钥被传给接收方，之后进行的加密、验证过程如下：

（1）发送方生成随机数r，计算S₁=rG。对原消息M作单向函数运算h=Hash（M），计算S₂=（h+kM）/r。

（2）接收方收到原消息M和密文S₁、S₂后，计算验证hG/S₂+MK/S₂=S₁是否成立。原理证明如下：

椭圆曲线方程的选择对于加密算法而言至关重要，是加密强度的基础。选择不当可能造成加密强度不足，甚至可能存在安全漏洞（假如是故意为之，则为安全后门）。

通常将F_p上的一条椭圆曲线描述为T=（p，a，b，G，n，h）。其中：p、a、b用来确定一条椭圆曲线，G为基点，n为点G的阶，h是椭圆曲线上所有点的个数m与n相除的商的整数部分。这6个参量取值的选择，直接影响了加密的安全性。参量值一般要求满足以下几个条件：

•　p越大安全性越好，但会导致计算速度变慢，200b左右可满足一般安全要求；

•　n应为质数；

•　h≤4；

•　p≠n×h；

•　pt≠1（mod n），1≤t＜20；

•　4a³+27b²≠0（mod p）。

比特币系统中即采用椭圆曲线加密法为签名算法，并选用了Secp256k1曲线，参照SEC标准（Standards for Efficient Cryptography）。F_p上的椭圆曲线参量T=（p，a，b，G，n，h）定义如下（方程式为y²=x³+7，曲线如图3.23所示）：

•　有限域采用256b的质数p：

p=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

=2²⁵⁶-2³²-2⁹-2⁸-2⁷-2⁶-2⁴-1

•　椭圆曲线E为y²=x³+ax+b，其中：a=0，b=7。

•　基点G选择分为两种情况：

（1）压缩格式下G=02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

（2）非压缩格式下G=04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

•　基点G的阶n为：

n=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE

BAAEDCE6 AF48A03B BFD25E8C D0364141

•　h=1。