Maple在二进制域椭圆曲线密码中的应用*

2019-10-09刘星江

通信技术 2019年9期

刘星江，曾玲

（中国电子科技集团公司第三十研究所，四川成都 610041）

0 引言

Maple是一个具有强大的符号运算能力、数值计算能力和图形处理能力的交互式计算机代数系统。它可以借助键盘和显示器代替原来的笔和纸来进行各种科学计算、数学推理、猜想的证明等。Maple最早由加拿大滑铁卢大学的符号计算机研究小组于上世纪八十年代开发出来，由于其在高精度数值计算和符号计算方面的优势，自问世以来就常用于解决各种各样的数学问题，比如微积分、线性代数、组合论等。

Maple在数值计算方面和其他程序设计语言（比如C语言）有很大的不同，最主要的不同是Maple中定义的变量没有类型区别，同时变量的位宽没有严格的限制要求。例如，在C语言中定义的整型变量一般为32比特或者64比特，而在Maple中定义的整型变量没有这个限制。关于Maple的详细内容可参见文献[1]。

由于Maple中对变量的位宽没有限制，所以对处理大整数的运算来说，Maple显得非常方便。利用这个特点采用Maple实现RSA密码算法（Rivest，Shamir，Adleman一起提出的一种非对称加密算法）、椭圆曲线密码（Elliptic Curve Cryptography，ECC）等将是非常方便快捷的。在文献[2]中，介绍了Maple在素数域椭圆曲线密码中的应用。本文主要介绍Maple在二进制域椭圆曲线密码中的应用。

1 二进制域上的运算及Maple实现

设p是一个素数，m是一个正整数。由有限域理论（可参见文献[3]）知道，在同构意义下存在唯一的pm元域，记作Fpm。特别地，当p=2时，有限域F2m就称为二进制域。对于二进制域F2m可以如下构造。

首先，选择一个二元域F2上的m次不可约多项式f(z)，f(z)在二元域上的多项式环F2[z]中生成一个主理想(f(z))，商环F2[z]/(f(z))即是二进制域F2m。具体地说，二进制域F2m中的元素即是二元域上次数小于m次的多项式，其中的加减乘除运算则是模不可约多项式f(z)的模加、模减、模乘、模除运算。下面分别介绍这些运算在Maple中的实现。

1.1 模加减

由于二元域中加法和减法完全相同，所以二进制中的模加与模减也完全相同，即是两个多项式同次项系数做异或运算即可。在Maple中可以如下实现。

1.2 模乘

如上所述，二进制域中的乘法运算即是多项式的模乘运算，在Maple中可以如下实现。

1.3 模逆

由于模除运算可以转换成一次模逆运算加上一次模乘运算，实现了模逆运算便可以实现模除运算。对于模逆运算来说，由于在二进制域中对任意的非零元a∈F2m，有a2m-1=1（可参见文献[3]）。所以a-1=a2m-2。这样就把模逆运算转换成了模乘运算。在Maple中模逆运算可以如下实现。

2 二进制域上椭圆曲线运算及Maple实现

设m是一个正整数，二进制域F2m上的非奇异椭圆曲线E可以由如下方程定义：

其中b≠0（可参见文献[4]）。

令E(F2m)表示该椭圆曲线上的所有有理点添加上一个无穷远点∞组成的集合。在该集合E(F2m)上定义如下的加法运算：

（1）对任意一点P∈E(F2m)，有P+∞=∞+P=P；

（2）对任意一点P=(x,y)=E(F2m)，有P+(x,x+y)=(x,x+y)+P=∞，这里称(x,x+y)为P的负点，记为-P；

（3）（点加运算）设P=(x1,y1)∈E(F2m)，Q=(x2,y2)∈E(F2m)，且P≠±Q，则P+Q=(x3,y3)，这里x3=λ2+λ+x1+x2+a，y3=λ(x1+x3)+x3+y1，其中λ=(y1+y2)/(x1+x2)；

（4）（倍点运算）设P=(x1,y1)∈E(F2m)，且P≠ -P，则2P=(x3,y3)，这里x3=λ2+λ+a，y3=x12+λx3+x3，其中λ=x1+y1/x1。

在该加法运算下E(F2m)便组成一个交换群。

设P∈E(F2m)，k是一个正整数，Q=kP是k个点P相加。已知k和点P计算点Q是比较容易的，其计算过程成为椭圆曲线上的点乘运算。反之，已知点P和点Q计算k是比较困难的，它称为椭圆曲线上的离散对数问题。该离散对数问题是一大数学难题，椭圆曲线密码体制也正是基于该难题来构建的。

在关于椭圆曲线的各种密码协议中，点乘运算都是其中运算量最大的运算部分。而点乘运算又可以由多次的点加运算和倍点运算组成，在上述定义中可以看到每次点加和倍点运算都包含了一次运算量较大的模逆。为了提高运算效率，把模逆省去，同时也为了让无穷远点有坐标表示，可以采用射影坐标来表示椭圆曲线上的点，这里采用LD射影坐标（以下简称LD坐标）表示，可参见文献[4-5]。普通坐标与LD坐标之间的相互转换关系如下。

普通坐标转换成LD坐标：

LD坐标转换成普通坐标：

由此可见，普通坐标转换成LD坐标是容易的，LD坐标转换成普通坐标可如下实现。

在LD坐标下的点加和倍点运算规则参见文献[4-5]，这里不再赘述。点加和倍点在Maple中可如下实现。

（1）倍点运算：

（2）点加运算：

有了点加和倍点运算后，点乘运算便容易实现，这里采用从左向右扫描点乘标量的方式实现，具体如下。

（3）点乘运算：

3 椭圆曲线密码体制的Maple实现

椭圆曲线密码作为一种公钥密码体制，具有数字签名、密钥协商、公钥加密等功能。它可以用于确保数据来源的可靠性、不可抵赖性、不可伪造性、不可篡改性等。关于椭圆曲线相关的密码协议可参见文献[6-8]。

下面将以数字签名为例，讨论如何在Maple中实现椭圆曲线数字签名协议（Elliptic Curve Digital Signature Algorithm，ECDSA）。ECDSA签名协议分为两个部分，一部分是签名生成算法，输入私钥、消息的杂凑值、随机数，签名运算输出签名值；一部分是验证签名算法，输入公钥、消息的杂凑值、签名值，验签运算返回该签名的有效性。关于ECDSA协议的详细内容可参见文献[4]。

首先选择一个二进制域F2m，取其中的模数多项式为z4+z+1，然后再选择其上的一条椭圆曲线y2+xy=x3+z3x2+(z3+1)，选择其上的点G=(z3,1)为基点，它的阶n=11。选择签名用的私钥d=5，它对应的公钥为Q=(z3+z+1,z)。