椭圆曲线加密算法中 模逆 的研究

陈子昊

华北电力大学 北京 102206

摘要;随着互联网时代的快速发展，个人的信息安全受到了人们普遍地关注并越来越受到大众重视。椭圆曲线加密算法是目前最为安全的信息加密算法之一，因为其占用相对较小的空间的条件下兼具很高的安全性，因此，椭圆曲线加密算法已经成为目前使用最多的加密标准。在椭圆曲线加密算法中最关键的步骤是倍点运算，在倍点运算中最占用资源最多的是模逆运算，本文主要对模逆运算中所用到的欧几里得算法，欧几里得算法的推论进行了研究，并对相关算法进行了证明，使用软件进行了算法的验证。

关键词：椭圆曲线加密算法，模逆，欧几里得算法

1. 引言

现如今，对椭圆曲线的研究已经有一百多年的历史，因此有着非常厚重的理论积累。二十世纪末期，Koblitz和Miller两位科学家在经过长期的研究之后，将椭圆曲线应用到了加密算法，椭圆曲线密码体制（EllipticCurveCrypsystem，ECC）就此诞生^[1]。

椭圆曲线加密算法是一种非对称加密算法，在实现过程中模逆算法要占用大量的资源，因此模逆是椭圆曲线加密算法中一个关键的步骤。在目前实现的模逆的算法研究中，主要有基于蒙哥马利的模逆算反，基于欧几里得算法的模逆算法以及基于费马小定理的模逆算法。本文主要研究了基于欧几里得算法的模逆算法的理论基础，并进行相关算法和推论的推导，最后使用编程语言对算法进行了验证。

2. 椭圆曲线加密算法中的模逆运算

在椭圆曲线加密算法中关键的步骤是倍点运算，但是在二维坐标下进行倍点运算需要进行大量的模逆运算，可以通过坐标的变换，将椭圆曲线上的点由二维坐标转化为雅克比坐标系下的坐标从而进行大量模逆运算的消减，只进行少数的模逆运算。

坐标转换的规则是椭圆曲线方程在标准射影坐标系下进行花间，然后遵循标准射影坐标系下的运算即可进行椭圆曲线的倍点运算。椭圆曲线算法是在二维坐标系下进行的，雅可比坐标下的点是在雅可比坐标系下进行的，目的是为了避免求逆运算来加速运算，因此计算完成之后还要把雅可比坐标映射到二维坐标，才是椭圆曲线能用的点。

3. 欧几里得算法以及推论

3.1 逆元的定义

在进行欧几里得算法的证明之前需要先引入模逆元的概念，逆元的计算都是在一个域内进行的，在椭圆曲线的计算中是在P内进行的，P是一个256位的大素数，可以用数学表达式通俗的表达逆元的含义，ax≡1（modP），也就是ax-nP=1，x为所求逆元，n为整数。

3.2欧几里得算法

欧几里德算法（Euclidean algorithm）又叫辗转相除法，可以用来求两个数的最大公约数^[2]。此算法可以用来解决求两个数的最大公约数，此算法用在椭圆曲线算法中，是在大素数域P的范围内进行计算的，因此可以知道任何数和P都是互质的，因此它们的最大公约数只能是1。欧几里得算法可以表示公式（1）所示。

(a,b)=(b,a%b) (1)

证明：设d=(a,b)

r=a-bq₁(q₁为整数，0

∵d，为a,b的最大公约数

∴a/d为整数，且b/d也为整数

∴(a-bq₁)也为整数

∴r/d=(a-bq₁)/d中r/d为整数

又∵r为小于b的数，且b的最大共因数为d

∴所以r的最大共因数也是d

∴有（a,b）=(b,r)=(b,a%b)

有推论：如果a和b是两个整数，可以知道通过欧几里得算法得到的表达式中，最后一个不等于0的余数就是（a,b）的最大公约数。

根据以上证明可以推得公式（2），根据公式（2）可以推得公式（3）的表达式。

a=bq₁+r₁ (01

b=r₁q₂+r₂ (021) （2-2）

r₁=r₂q₃+r₃ (032) （2-3）

......

r_k-1=r_kq_k+1+r_k+1 (0k+1k) （2-4）

......

r_n-1=r_nq_n+1+r_n+1 (0nn-1) （2-5）

r_n-1=r_nq_n+1+r_n+1 (0n+1n) （2-6）

可以知道在公式（2-6）中，r_n+1=0，且a,b两个数是互素的，并由公式（1）可以知道r_n=1，将每一步中的余数的表达式代入上一步中，经过移项和简化就可以得到公式（3）。

r_k=aQ_n(-1)^n-1-bP_n(-1)^n-1 （3）

其中Q₀=0，Q₁=1，P₀=1，P₁=q₁并且可以得到公式（4）。

Q_n=q_nQ_n-1+Q_n-2 P_n=q_nP_n-1+P_n-2 （4）

在椭圆曲线加密算法中取b=P,则通过Q_n可以计算出a的逆元。

4. 算法测试

通过将算法描述具象化，可以将算法描述为如下所示，gcd(a,b)中，a,b为输入的两个整数且a>b，输出为a,b的最大公因数。mod_invese（d,n）中，d在n的域内要求逆元的元素，输出为d的模n逆元。

算法的测试数据来自于随机选取的数据，算法测试结果如图所示。

参考文献

[1]Laue R , Huss S A . Parallel Memory Architecture for Elliptic Curve Cryptography over( mathbb{Gmathbb{F{left( p ight) )Aimed at Efficient FPGA Implementation[J]. journal of signal processing systems, 2008, 51(1):39-55.

[2]Motzkin T . The Euclidean algorithm[J]. Bulletin of the American Mathematical Society, 1949, 55(12):1142-1146.