椭圆曲线密码体制初探

由上节的内容可知，有限域椭圆曲线上的任意两个点相加，结果仍然是曲线上的点。所有的点都落在某一个区域内，组成一个有限阿贝尔群，与密码长度相对应。密码长度越长，这个区域就越大，安全层次就越高，但计算机速度越慢，反之亦然。

椭圆曲线密码体制的安全性在于求解椭圆曲线点群上的离散对数问题的困难性。已知椭圆曲线E_p（a，b）和点G，随机生成一个整数d，容易计算Q=d×G，但给定Q和G计算d就相对困难。

1.一般的椭圆曲线密码

选取一个有限域GF（p）和定义在该域上的椭圆曲线E_p（a，b），在E_p（a，b）选取一个拥有素数阶n的点G（x，y），阶n是满足nG=O的最小正整数。其中有限域GF（p）、椭圆曲线参数a、b，点G（x，y）和阶n都是公开信息。

（1）密钥的生成

系统建立后，每个参与用户进行下列运算：

1）在区域[1，n-1]中随机选取一个整数d。

2）计算Q=dG。

用户的公钥为点Q，私钥为整数d。

（2）加密过程

当用户A发送消息M给用户B时，A执行下列步骤：

1）查找B的公钥Q。

2）将消息M表示成一个域元素m∈GF（p）。

3）在区域[1，n-1]中随机选取一个整数k。

4）计算点（x₁，y₁）=kG。

5）计算点（x₂，y₂）=kQ，如果x₂=0，则返回步骤3）。

6）计算c=mx₂。

7）传送加密数据（x₁，y₁，c）给B。

（3）解密过程

当用户B解密从A收到的密文（x₁，y₁，c）时，B执行下列步骤：

1）使用自己的私钥d，计算点（x₂，y₂）=d（x₁，y₁）。

2）通过计算m=c·x₂^-1，恢复出消息m。

2.椭圆曲线ElGamal密码（ECELG）

当用户A发送消息M给用户B时，可以使用椭圆曲线ElGamal密码来完成。首先选取一条椭圆曲线E_p（a，b），设G∈E_p（a，b）为椭圆曲线上的一个本原元素，m→P_m是明文空间到椭圆曲线的嵌入（即将明文转换为椭圆曲线上的点）。

（1）加密过程

用户B选取私钥d_B，产生一个公钥P_B=d_BG。

用户A为了向B发送信息P_m，选取随机数k作为他的私钥并向B发送密文

C_m=（kG，P_m+kP_B）。

（2）解密过程

B收到C_m=（kG，P_m+kP_B）后，首先计算

（P_m+kP_B）-d_BkG=P_m+k（d_BG）-d_BkG=P_m(www.xing528.com)

再把P_m变换成消息m。

攻击者若要由C_m得到P_m，就必须知道k。而要得到k，只有通过椭圆曲线上两个已知点G和kG，即必须求椭圆曲线上的离散对数，这被公认是十分困难的。

【例5-18】 设G=（6，4）为椭圆曲线E₂₃（1，1）：y²≡x³+x+1（mod 23）上的一个生成元，消息m编码后的信息为P_m=（5，4），用户B的私钥d_B=3，则公钥为

P_B=d_BG=3（6，4）=（7，12）若用户A想向B发送信息P_m，选取随机数k=2，那么

kG=2（6，4）=（13，7）

P_m+kP_B=（5，4）+2（7，12）=（5，4）+（17，3）=（5，19）所以A向B发送的密文为

C_m=（kG，P_m+kP_B）=（（13，7），（5，19））B收到密文C_m后，解密如下

P_m=（5，19）-3（13，7）=（5，4）

3.椭圆曲线密钥协商（ECDH）

选取一个有限域上的椭圆曲线E_p（a，b），取E_p（a，b）上的一个本原元素G∈E_p（a，b），要求满足nG=O的最小值n是一个足够大的素数，E_p（a，b）和G作为公开参数。

通信双方A和B基于椭圆曲线密码体制进行密钥协商的处理过程如下：

1）A选择一个比n小的整数d_A作为私钥，产生E_p（a，b）上的一个点P_A=d_AG作为公钥。

2）B类似地选择一个私钥d_B，并计算出他的P_B=d_BG。

3）A计算K_AB=d_AP_B

B计算K_BA=d_BP_A产生出双方共享的秘密密钥。实际上容易得知它们是相同的。这是因为

K_AB=d_AP_B=d_A（d_BG）=d_B（d_AG）=d_BP_A=K_BA

易见，椭圆曲线Diffie-Hellman密码协商（ECDH）的安全性基于椭圆曲线上的离散对数的难解性。

【例5-19】 取E₂₁₁（0，-4），即椭圆曲线为y²≡x³-4（mod 211）。取G=（2，2）可计算241G=O。用户A和B密钥交换的过程如下：

1）设A的私钥为d_A=121，则A的公钥为

P_A=d_AG=121（2，2）=（115，48）

A将公钥（115，48）发送给B。

2）B收到（115，48）后，用自己的私钥d_B=203计算

K_BA=d_BP_A=203（115，48）=（161，169）

计算B的公钥为

P_B=d_BG=203（2，2）=（130，203）

B将公钥（130，203）发送给A。

3）A收到（130，203）后，计算

K_AB=d_AP_B=121（130，203）=（161，169）

可见，（161，169）是A和B共享的秘密密钥。