椭圆曲线加密教学中辅助软件的开发与应用

2018-04-02方贤进吴艳婷

计算机教育 2018年3期

方贤进，吴艳婷，王丽

（安徽理工大学计算机科学与工程学院，安徽淮南 232001）

0 引言

椭圆曲线加密（Elliptic Curve Cryptography,ECC）已经广泛地使用在TLS、PGP和SSH中，这3项技术是现代IT世界的加密基础，当今流行的比特币（BitCoin）、区块链（Block Chain）等加密货币技术更是以此为基础。

在中国知网（CNKI）上搜索“椭圆曲线”“教学”两个关键词，可检索到5 835条文献，但几乎都是关于ECC学术方面的论文，教研类的论文只有郎荣玲、刘建伟等人在《计算机教育》发表的“信息安全数学基础理论教学方法研究”[1]，但也只简单提及“椭圆曲线密码体制来源于对椭圆曲线的研究，因此在讲授这个部分内容时一定要把椭圆曲线的物理意义以及其应用讲清楚”。

现代密码学[2]中ECC的教与学存在一定困难，首先椭圆曲线加密涉及椭圆曲线几何、集合论、Abel群、有限域等数学知识，另外椭圆曲线加密运算要应用模运算、扩展的欧几里得算法、有限域上的点加运算、倍点运算等，有些运算不仅抽象（例如点的逆元运算、点加运算、2倍点运算等），而且计算量很大（例如有限域上点集合计算、多倍点运算）。在教学过程中笔者发现，学生觉得椭圆曲线加密算法具有神秘感，难以直观理解。鉴于此，利用HTML5新功能结合CSS、jQuery框架开发基于Web的可视化工具软件，用于辅助讲解椭圆曲线及其代数与几何特性、椭圆曲线下Abel群的定义及几何意义、有限域GF（p）上椭圆曲线点的计算等，为学生更好地理解椭圆曲线加密算法及其应用（如加解密、数字签名等）奠定基础。椭圆曲线加密教学方法探讨的设计框架见图1。

图2　（a）实数域上的一般椭圆曲线

图2　（b）奇异椭圆曲线（4a3+27b2=0）

图3　椭圆曲线加密教学辅助软件的功能模块

1 椭圆曲线及其代数几何特性的认识教学

椭圆曲线在代数学和几何学上已被广泛研究了150多年，有坚实的理论基础。椭圆曲线密码体制以椭圆曲线为基础，因此在讲解椭圆曲线密码体制之前，先要让学生搞清楚椭圆曲线的代数与几何特性，这样才能更好地理解椭圆曲线的基本原理及相关理论。

无论是实数域还是有限域上的椭圆曲线，学生都觉得比较抽象。为了让学生更好地理解椭圆曲线上点的各种运算及其几何意义，有必要让学生对各种椭圆曲线的特性有直观的了解，如关于x轴的对称性、根的判别式与奇异曲线等。因此，利用开发的可视化软件，在讲解椭圆曲线的几何特性时通过改变html5页面表单中数字型输入框参数a、b的值，可以形象地得到实数域上各种不同的椭圆曲线，见图2（a）、2（b）。

该辅助软件基于Web架构，采用HTML5+jQuery框架的Web前端开发技术，不需要后端（Server）支持。软件的主要功能是椭圆曲线加密基础理论的辅助教学及可视化，其功能模块见图3，具体软件参见作者个人网站http://star.aust.edu.cn/～xjfang/crypto。

2 椭圆曲线下的Abel群的定义及几何意义的教学

椭圆曲线上所有的点、点加运算、点的纯量乘法构成一个Abel群（交换群）。但是，在讲解这部分内容时，涉及群论的很多概念和知识，如椭圆曲线上所有点及运算构成Abel群的单位元概念、逆元概念、点加运算、点的纯量乘法运算、点加运算的结合律、交换律等。如果缺乏形象、直观地展示与验证，往往比较枯燥、乏味。

椭圆曲线上两个不相等的非零点P=（xP ,yP）、Q=（xQ,yQ），它们的点加运算P+Q=R=（xR,yR）的代数计算公式为

其中m=（yP-yQ）/（xP-xQ）。

为了更清晰地讲解点加运算，可以用可视化的方法演示点加运算的代数计算结果以及其几何意义：椭圆曲线上点加运算的几何意义是连接两个点P与Q，PQ的延长线与曲线的交点关于x轴的对称点即为这两个不同点P与Q之和。图4（a）是椭圆曲线上的两个点P（1, 2）、Q（3, 4）相加得到点R（-3, 2）及其几何意义，点R（-3, 2）是PQ延长线与椭圆曲线的交点（-3, -2）的对称点。图4（a）同时验证了椭圆曲线下群的定义一条规则：椭圆曲线上3个连成一线的非单位元点P、Q、-R，它们的和为P+Q+（-R）=O。图4（b）演示了椭圆曲线上群的定义的另一条规则：若P、Q互为逆元，即P与Q关于x轴对称，或者说Q=-P，则P+Q=O，其表示无穷远点O是平行于y轴的直线的一种抽象。

纯量乘法又称为倍点运算，即nP=P+P+ +P，纯量乘法的计算基础是两个相同点的点加运算。如果P（xP,yP）是椭圆曲线上的点，按照以下规则计算2P=P+P=R=（xR,yR）。

其中m=（3x2p+a）/2yp。

当纯量乘法运算中的n比较大时，其运算是反复通过倍加（double and add）算法实现的。例如，计算151P，将n=151表示成二进制形式：151=27+24+22+21+20，151P=27P+24P+22P+21P+20P，

2P利用公式（2）计算，4P利用2P计算，以此类推，反复利用倍加运算完成计算。

图5（a）是椭圆曲线上点的标量乘法及计算结果的可视化；图5（b）表示两个相同点相加（P+P=2P）的结果及几何意义，即过该点做椭圆的切线，切线与椭圆曲线交点的对称点即为两个相同点相加的结果；图5（b）与5（c）表示两个相同点的点加运算（P+P）与点P的二倍纯量乘法（2P）的结果与几何意义的一致性。

图4　（a）不相同的两个点的加法运算

图4　（b）互为逆元的两个点的加法运算

图5　（a）点的纯量乘法

图5　（b）两个相同点相加的几何意义

图5　（c）2P纯量乘法的几何意义

3　有限域GF（p）上椭圆曲线点的计算的教学

3.1　有限域GF（p）上椭圆曲线点集合计算演示

椭圆曲线，对每个x=0,1,…,p-1计算x3+ax+b（modp），如果其值是一个模p的平方根，则找到椭圆曲线上的两个点（x,y）、（x,p-y）。该算法的执行过程可通过图5中的可视化工具演示，选择参数n=1，对点P横坐标x的输入框依次选择0～p-1，则计算出椭圆曲线在有限域GF（p）上的所有离散点并显示出来。与实数域椭圆曲线一样，在有限域GF（p）上的椭圆曲线的这些离散点及其运算仍然构成一个Abel群（交换群）。

3.2　有限域GF（P）上椭圆曲线的点的纯量乘法、循环子群、阶及其可视化

有限域GF（p）上一个椭圆曲线所有点构成的Abel群中点的数量称为群的阶，记为N。当p是一个很大的素数时，可以利用Schoof算法[3]在多项式时间内计算N的值。椭圆曲线上所有离散点构成的Abel群的阶N=100，见图6。

图6　有限域GF（p）上椭圆曲线点集合的计算与可视化

有限域GF（p）上椭圆曲线点的纯量乘法的代数计算与实数域上一样（参见2.1节），但是有限域上椭圆曲线的纯量乘法具有自身的特殊性，见图7。

假设有椭圆曲线，其上的一个P（3,6），若对P进行纯量乘法计算会发现其结果只有5个不同的值（O,P,2P,3P,4P），并且循环出现。

可以验证纯量乘法在加法运算下是封闭的，即对有限域上椭圆曲线的某个点P迭代地进行纯量乘法得到的点集合构成一个循环子群，P称为循环子群的生成元（generator）或基元（base point）。有限域 GF（p）上的椭圆曲线的循环子群是椭圆曲线加密算法及其他加密系统的基础。

由P生成的椭圆曲线上子群的阶是指一个最小的正整数n，满足nP=O。例如，椭圆曲线上的一个点P（12,3）生成的子群的阶是50，见图8。

图7　有限域上椭圆曲线点的纯量乘法的特性

图8　有限域椭圆曲线上点的集合、点P作为生成元构成的子群及其阶

3.3　有限域上GF（p）上椭圆曲线的点加运算及其可视化

有限域GF（p）上的椭圆曲线点加运算与实数域的差别是所有计算都是在模p下进行，但是由于有限域GF（p）上椭圆曲线的点都是离散的，从直观的角度不存在几何意义上3个点连成一线的问题。因此，有限域GF（p）上的椭圆曲线点加运算的几何意义是不同于实数域。有限域GF（p）上椭圆曲线上的3个离散点p、Q、R连成一线是指3个点的坐标满足线性方程y=mx+c（modp），其中参数m、c可由其中两个点的坐标计算确定。

因此，有限域上GF（p）上椭圆曲线两个点相加P+Q=R的几何意义是：首先由P、Q确定斜率为m的一组平行线(满足线性方程y=mx+c（modp）），若椭圆曲线的点集合中某个离散点R’落在某一条平行线上，则R’关于x轴的对称点R就是P+Q的结果。椭圆曲线上的两个点P（16,20）、Q（41,120）进行点加运算，计算斜率c=83，得到满足方程的一组平行线，在点集合中容易验证R’=（86, 46）满足该方程，则R’的逆元R=（86, -46）=（86,-46+127）=（86, 81）即为点P与Q相加的结果，见图9。

4 结语

笔者针对椭圆曲线加密教学过程中若干难点问题设计了几个教学内容，包括椭圆曲线及其代数几何特性的认识与可视化、椭圆曲线下的Abel群运算规则的几何意义可视化教学、有限域GF（p）上椭圆曲线点集合计算与可视化教学、有限域GF（p）上椭圆曲线的点的纯量乘法、循环子群、阶及其可视化、有限域上GF（p）上椭圆曲线的点加运算与可视化等。椭圆曲线加密教学中的辅助工具软件可访问笔者的课程建设网站http://star.aust.edu.cn/～xjfang/crypto/。下一步拟进行ECC基本参数生成、明文映射到椭圆曲线上的点的算法、加解密算法、数字签名算法等相关教学内容的可视化设计，并力争达到工业级别的ECC加解密教学演示系统、数字签名教学演示系统。