9 椭圆曲线密码体制

椭圆曲线的计算方式

椭圆曲线的定义

素域定义：
  有限域最直观的例子就是阶为素数的域。域$GF(p)$的元素可以用整数$0，1，...，p-1$来表示。域的两种操作就是模整数加法和整数乘法模$p$;

  假设 $p$ 是一个素数，整数环$Z_p$表示为$GF(p)$，也称为是拥有素数个元素的素数域或伽罗瓦域。$GF(p)$中所有的非零元素都存在逆元，$GF(p)$内的算术运算都是模 $p$ 实现的。

椭圆曲线定义：

  $Z_p(p>3)$上的椭圆曲线指满足以下条件的所有对$(x,y)\in Z_p$的集合$$y^2\equiv x^3+a\ast x+bmodp$$  以及一个无穷大的虚数点$\sigma$，其中$$a,b\in Z_p$$  并且满足条件$4\cdot a^3+27\cdot b^2\ne 0modp.$

  椭圆曲线的定义要求该曲线是非奇异的。从地理位置上说，这意味着该曲线的图不会自我相交或没有顶点;如果曲线的判别式$-16(4a^3+27b^2)$不等于0，就可以保止这一尽。

椭圆曲线上的群操作

  假设用加法符号$“+”$表示群操作(注意：将操作选择命名为“加法”完全是随意的，我们也可以将其称为乘法。)。“加”意味着给定两个点及其对应的坐标，比如$P=(x_1,y_1)$和$Q=(x_2,y_2)，$我们需要计算第三个点$R$的坐标，使得:$$P+Q=R$$$$(x_1,y_1)+(x_2,y_2)=(x_3,y_3)$$
  必须区分两种情况: 两个不同点的加法(即相异点相加) 和 同一点与自身的加法(即相同点相加)。

  相异点相加P + Q ：这个主要是针对计算 $R=P+Q$，且$P\ne Q$的情况。构建的方法为: 画一条经过$Р$ 和 $Q$的线，该线与椭圆曲线的交点就是第三个点。根据定义，将第三个点关于$x$轴映射，得到的映射点就是点$R$。图9-4显示了实数上椭圆曲线的相异点相加。

  相同点相加P + P： 这主要针对的是$P+Q$但$P=Q$的情况。因此,可以写作$R=P+P=2P$。构建方法为：画一条经过$Р$点的切线，即可得到此切线与椭圆曲线的第二个交点; 将此交点关于$x$轴映射，得到的对称点就是相同点相加的结果$R$。图9-5显示了实数上椭圆曲线的相同点相加。

  事实证明，如果椭圆曲线上的点采用这种方式进行相加，则点的集合也满足群所需的大多数条件，即闭合性、结合性、存在单位元和逆元。

椭圆曲线上的相同点相加与相异点相加：
$$x_3=s^2-x_1-x_{2}modp$$$$y_3=s(x_1-x_3)-y_{1}modp$$  其中$$s=\{\begin{array}{ll}\frac{y_2-y_1}{x_2-x_1}modp,& \text{当P=Q(相异点相加)}\\ \frac{3x_1^2+a}{2y_1}modp,& \text{当P=Q(相同点相加)}\end{array}$$

注意: 在相异点加法中，参数$s$指的是经过$Р$和$Q$的直线的斜率；而在相同点加法中，参数$s$指的是经过点$P$的切线的斜率。

那么现在问题来了：椭圆曲线上的所有点是否都满足$$P+\sigma =P$$的单位元(或中性元)$\sigma$。事实证明，满足这个条件的点$(x,y)$是不存在的。所以，我们将一个无穷的抽象点定义为单位元$\sigma$。这个无穷点可以看作是位于y轴正半轴的无穷远处，或y轴负半轴的无穷远处。

  根据群的定义，现在可将任何群元素$P$的逆元$-P$定义为: $$P+(-P)=\sigma .$$

  那么我们如何找到$-P$? 如果使用 tangent-and-chord方法，则点$P=(x_p,y_p)$的逆元为点$-P=(x_p,-y_p)$，即其逆元是该点关于$x$轴对称的点。下图显示了点$Р$与其对应的逆元， 从图中可知，找到点$P=(x,,y,)$的逆元非常简单，只需得到其$y$坐标的负数即可。对素数域$GF(p)$上的椭圆曲线而言，实现起来非常容易，因为$-y_p\equiv p-y_{p}modp$，因此可以得到:$$-P=(x,p-y_p)。$$

示例：考虑小型域$Z_{17}$上的曲线:
$$E:y^2\equiv x^3+2x+2mod17$$点$P=(5,1)$的相同点加法为:$$2P=P+P=(5,1)+(5,1)=(x_3,y_3)$$$$s=\frac{3x_1^2+a}{2y_1}=(2\ast 1{)}^{-1}(3\ast 5^2+2)=2^{-1}\ast 9\equiv 9\ast 9\equiv 13mod17$$$$x_3=s^2-x_1-x_2=13^2-5-5=159\equiv 6mod17$$$$y=s\ast (x_1-x_3)-y_1=13\ast (5-6)-1=-14\equiv 3mod17$$$$2P=(5,1)+(5,1)=(6,3)$$

  检查结果$2P=(6,3)$是否真的是曲线上的一个点:
$$y^2\equiv x^3+2\ast x+2mod17$$$$3^2\equiv 6^3+2\ast 6+2mod17$$$$9=230\equiv 9mod17$$

使用椭圆曲线构建离散对数问题

定理一： 曲线上的点与$\sigma$一起构成了循环子群。在某些条件下，椭圆曲线上的所有点可以形成一个循环群。

示例：找到以下曲线上的所有点:$$E:y^2\equiv x^3+2x+2mod17$$  曲线上的所有点恰好形成了一个循环群，而且该群的阶为#E=19。

  从本原元$P=(5,1)$开始，计算$P$的所有幂值。更确切地讲，由于群操作为加法，所以需要计算$P，2P，...，(\#E)P$。以下是得到的元素的列表:

定理二（Hasse’s定理）：给定一个椭圆曲线$E$模$p$,曲线上点的个数表示为$\#E$，并且在以下范围内:
$$p+1-2\sqrt{p}\le \#E\le p+1+2\sqrt{p}$$

  Hasse’s定理也称为Hasse’s边界，它说明了点的个数大概在素数p的范围内。这个结论具有非常大的实用性。例如，如果需要一个拥有$2^{160}$个元素的椭圆曲线，我们必须使用一个长度大约为$160$位的素数。

注意： 在密码体制中, $d$ 通常为整数, 也是私钥, 而公钥$T$是曲线上的一个点, 坐标为$T=(x_T,y_T)$。

椭圆曲线离散对数问题(ECDLP)

  给定一个椭圆曲线$E$，考虑本原元$Р$和另一个元素$T$。则$DL$问题是找到整数$(1\le d\le \#E)$，满足:$$\underset{d次}{\underbrace{P+P+\dots \dots +P}}=dP=T.$$

基于椭圆曲线的Diffie-Hellman密钥交换

  可以实现基于椭圆曲线的密钥交换，这也称为椭圆曲线Diffie-Hellman密钥交换或ECDH。首先必须统一域参数，即实现所需要的合适的椭圆曲线以及此曲线上的一个本原元。

ECDH域参数

椭圆曲线 Diffie-Hellman 密钥交换(ECDH)

  证明此协议的正确性非常简单。

  证明:Alice 计算$$aB=a(bP)$$  而Bob计算$$bA=b(aP).$$
由于点加法具有结合性(提示:结合性是群的一个属性)，双方计算得到的结果相同，即点$T_{AB}=abP.$

  从协议中可以看出，Alice和 Bob分别选择了自己的私钥 $a$ 和 $b$，这两个私钥都是非常大的整数。双方都使用各自的私钥计算出各自的公钥 $A$ 和 $B$，而且这两个公钥都是曲线上的点。公钥是通过点乘法计算得到的，双方彼此交换公钥参数。然后，Alice和 Bob利用他们收到的公钥以及各自的私钥参数再次执行点乘计算，便可得到联合密钥$T_{AB}$。联合密钥$T_{AB}$可以用来得到会话密钥，比如作为AES算法的输入。注意: $(x_{AB},y_{AB})$的两个坐标并不是独立的: 给定$x_{AB}$，将$x$的值代入到椭圆曲线方程中就可计算出另一个坐标。因此，会话密钥生成时可以只用其中一个坐标。

示例：对于拥有如下域参数的ECDH。椭圆曲线为$y^2=x^3+2\ast x+2mod17$ ，它构成了阶为$\#E=19$的循环群。基点为$P=(5，1)$，该协议的工作方式如下:

参考资料：《深入浅出密码学》–Christof Paar,Jan Pelzl著