3.2.3
椭圆曲线算法

ElGamal算法的思路可以从 中推广到其他类型的群。椭圆曲线加密算法就是一个很好的例子。椭圆曲线算法于20世纪80年代被提出，稍晚于RSA和ElGamal算法。在相同密钥长度的情况下，攻击椭圆曲线算法的计算复杂度远高于RSA和ElGamal算法。而且，一般情况下椭圆曲线算法的计算复杂度也较低。但是，椭圆曲线的数学原理比之前提到的大整数分解、离散对数等都更复杂。在下面的篇幅中，我们试图以较为简明的语言阐述其基本原理。

在代数中常用方程式来定义曲线，例如直线、圆周和抛物线等。椭圆曲线也一样，它由一个二元方程来定义。

为了构建加密算法，我们先要在椭圆曲线上构建数学运算，这就是椭圆曲线上的“加法”。这里的加法运算和简单的加法或模和是完全不同的。从几何的角度来看，椭圆曲线上两个点{ P , Q }的加法 P + Q 过程等效为定位一个点 U ，使得 U 是“ P 和 Q 点连线的延长线与曲线的交点的 x 轴对称点”。

依此类推，可继续利用 P 和2 P 在椭圆曲线上定位3 P 这个点。通过合理地构造椭圆曲线，我们可以保证在 n 足够大的时候， nP 总是曲线上的某个点。这里又一次用到了“生成元”的概念。在一定条件下，椭圆曲线上所有的点都可以用 P 的多次“加法”来得到。

于是，引申出椭圆曲线加密中用到的数学难题，即：

给定两个点 P 和 Q ，若已知 P = nQ ，求 n 。

由于 n 足够大，通过 P 和 Q 求解 n 是很困难的。Bob确定椭圆曲线上的某个点 G ，然后根据一个秘密的随机数 k 来计算出 F = kG ，其中{ G , F }为公钥， k 为私钥。

然后是基于上述密钥的加密和解密过程。现简要介绍如下。

当Alice得到公钥后，分两个步骤构建密文。

• Step 1：找出一个随机数 r ，然后在椭圆曲线上找到 rG ；
• Step 2：用公钥加密明文 m ，即 s = m + rF 。Alice把两部分密文{ rG , s }一并发给Bob。

Bob解密的过程比较简单。当Bob收到密文后，利用私钥和两部分密文进行运算，计算方式为：

m = s – krG

由于 krG = rF ，所以很容易验证上述加密、解密过程成立。

实际上，上述算法的几何意义非常容易理解。Bob生成私钥的过程，就是利用点 G 和随机选择的秘密参数 k 来找到点 F 。Alice利用 rF 加法操作将明文对应的点在椭圆曲线上搬运到密文对应的点，然后Bob利用 krG 加法操作把密文映射回明文。

研究表明，当椭圆曲线的参数 p 很大时，从 G 和 F 来推算 k 是非常困难的。例如，如果 p 是一个200位的数，那么椭圆曲线上可能的点的数量级是2 ¹⁶⁰ 。在这样一个巨大的集合中，在椭圆曲线上回溯 k 基本是不可能做到的。但是反过来，如果已知 n ，则有快速算法可以直接由 P 求出 Q 。这和公钥加密算法中“易验证，难推算”的精神是一致的。 FH7GnccMjhyFndyDvi16YtyZ4xvx58TzlqmOlt/1+kaWr/LSDm0YgMN0/GVol7Ho