基于椭圆曲线的因子分解算法.doc

基于椭圆曲线的因子分解算法 文旌 摘要: 阐述了代数几何中关于椭圆曲线的定义及相应的运算法则, 依据 p - 1 算法给出了基于椭圆曲线的因子分 解算法的原理与实现方式, 同时对此算法程序在运行过程中所涉及的若干子程序( 算法) 作了全面的分析. 本课题将研究椭圆曲线分解算法，一方面在理论上寻找点乘速度更快的椭圆曲线，另一方面在工程上将针对椭圆曲线分解法的开源代码ECM进行研究和改进，提高ECM的运行效率。Algorithm of factorization based on elliptic curveAbstract: This paper introduces the algebraic geometry on the elliptic curve is defined and the corresponding algorithms, according to p 1 algorithm is presented based on the elliptic curve factor solution algorithm principle and implementation method, at the same time this algorithm procedures involved in the operation process of a number of subroutines ( algorithm ) made a comprehensive analysis of this topic. The study of elliptic curve factorization algorithm, on the one hand the theory to produce faster elliptic curve, on the other hand, engineering, according to the elliptic curve factorization method source code for ECM research and improvement, improving the operational efficiency of ECM.自从 1976 年 Diffle 和 H ellman 提出了公钥密 码的概念以来, 出现了很多的公钥密码系统, 所有这 些系统的安全性都依赖于相应的数学问题. 其中的 RSA 公钥密码体制的安全性基于大整数的因子分 解问题很难解决, 本文将给出大整数的因子分解的 一个算法 $ $ 基于椭圆曲线的因子分解.1 椭圆曲线的群结构 1. 1 椭圆曲线的定义给定域K 及相应的代数闭域K , K 上的 Weier-strass 方程 Y2 Z+ a1 X YZ + a3 YZ2 = X 3 + a2 X 2 Z + a4 X Z2 + a6 Z3 ( a1 , a2 , a3 , a4 , a6 I K ) 决定射影平面P2 ( K) 上的一条曲线 E, 若此曲线为非奇异的, 则 称它为定义在 K 上的椭圆曲线, 常表示为 E/ K 1 . E 上的点( 0, 1, 0) 称为无穷远点, 记为5, 当 Z X 0时, 令 x = X / Z, y = Y/ Z, 前述的方程可变为 y 2 +a1 x y + a3 y = x 3 + a2 x 2 + a4 x + a6 , 曲线 E 由此方程 所有的解( x , y ) ( x , y I K ) 及无穷远点5 组成E 上任意点( 无穷远点除外) 均有射影坐标( X , Y, Z) 与仿射坐标( x , y ) 两种表示方式. 基于 K 的特征 的不同, 以相应的变量替换方式可以获得 E 的方程 的若干简化形式 2 .1. 2 椭圆曲线上的加法的定义Weier strass 方程所定义的椭圆曲线 E 是射影 平面P 2 ( K) 上的一条 3 次曲线, 平面上任意一条直 线与 E 都有 3 个交点( 不一定互不相同) . 任取两点P , Q I E, 连接 P, Q 的直线( 当 P = Q 时, 取通过 P的切线) 与 E 交于第三点R , 连接 R 与无穷远点5的 直线与 E 的第三个交点记为 P _ Q, 在实数平面上. 事实上, 椭圆曲线 E 对运算 _ 作成一个交换 群, 亦称为加法群, 同时可以将 _ 改写为+ .1. 3 椭圆曲线上的加法规则给定椭圆曲线 E:y 2 + a1 xy + a3 y = x 3 + a2 x 2 + a4 x + a6设 P= ( x , y ) I E, 则 P = ( x , - y - a1 x - a3 )令 P1 + P2 = P 3 , P i = ( x i , y i ) I E, i = 1, 2, 3.若 x 1 = x 2 , y 1 + y2 + a1 x 1 + a3 = 0, 则 P 1 + P2 = 5, 否则( 即 P1 + P2 X 5) , 令y 2 -y 1( x 1X x 2 )x 2 -x 1K=2+ 2a2 x 1 + a4 - a1 y 13x 1( x 1= x 2 )2y 1 + a1 x 1 + a3此时, P3 = ( x 3 , y 3 ) , x 3 = K2 + a1 K- a2 - x 1 - x 2 , y3 = K( x 1 - x 3 ) - y 1 - a1 x 3 - a3 3 .在实际应用中, 当 char( K ) X 2, 3 时, 给定椭圆 曲线 E/ K : y2 = x 3 + ax + b, 对 P = ( x , y ) , 有- P =( x , - y ) , 当 P 1 + P2 X 5时, 令y 2-y1( x 1X x 2 )x 2-x 1K=2a3x 1 +( x 1= x 2 )2y 1此时, P 1 + P2 = P3 = ( x 3 , y 3 ) , x 3 = K2 - x 1 - x 2 , y3 = K( x 1 - x 3 ) - y 1 .2 基于椭圆曲线的因子分解算法 2. 1 算法原理Pollard J M 在 1970 年给出了关于大整数因子 分解的 p - 1 算法, 此算法的基本思想是基于群 Zp 的元素的阶获得 N 的因子p ( 假设 p 是未知的奇素 数, N 是需分解的大整数) , 算法的实现涉及到费马 小定理: 若 p 是素数, a 是一个整数, 且 gcd( p , a) = 1, 则 ap- 1 S 1 ( mod p ) . 设存在 m, 使得( p - 1) | m, 则 am - 1 S 0 ( m od p ) , 于是 gcd( am - 1, N ) = p , 因令 P1 + P2 = P 3 , P i = ( x i , y i ) I E, i = 1, 2, 3.若 x 1 = x 2 , y 1 + y2 + a1 x 1 + a3 = 0, 则 P 1 + P2 = 5, 否则( 即 P1 + P2 X 5) , 令y 2 -y 1( x 1X x 2 )x 2 -x 1K=2+ 2a2 x 1 + a4 - a1 y 13x 1( x 1= x 2 )2y 1 + a1 x 1 + a3此时, P3 = ( x 3 , y 3 ) , x 3 = K2 + a1 K- a2 - x 1 - x 2 , y3 = K( x 1 - x 3 ) - y 1 - a1 x 3 - a3 3 .在实际应用中, 当 char( K ) X 2, 3 时, 给定椭圆 曲线 E/ K : y2 = x 3 + ax + b, 对 P = ( x , y ) , 有- P =( x , - y ) , 当 P 1 + P2 X 5时, 令y 2-y1( x 1X x 2 )x 2-x 1K=2a3x 1 +( x 1= x 2 )2y 1此时, P 1 + P2 = P3 = ( x 3 , y 3 ) , x 3 = K2 - x 1 - x 2 , y3 = K( x 1 - x 3 ) - y 1 .2 基于椭圆曲线的因子分解算法 2. 1 算法原理Pollard J M 在 1970 年给出了关于大整数因子 分解的 p - 1 算法, 此算法的基本思想是基于群 Zp 的元素的阶获得 N 的因子p ( 假设 p 是未知的奇素 数, N 是需分解的大整数) , 算法的实现涉及到费马 小定理: 若 p 是素数, a 是一个整数, 且 gcd( p , a) = 1, 则 ap- 1 S 1 ( mod p ) . 设存在 m, 使得( p - 1) | m, 则 am - 1 S 0 ( m od p ) , 于是 gcd( am - 1, N ) = p , 因此通过对 m 的选择可以实现N 的因子分解, 常取 m 为多个小素数因子的积, 这可以增加成功分解的可 能性 4 . 但是, 需要进一步说明的是: 若 N 没有 p - 1 光滑的素因子 p , 则 p - 1 算法不能实现对 N 的因 子分解. 为了避免 p - 1 算法所存在的问题, 可用域 Fp 上的随机椭圆曲线产生的群代替乘法群 Zp , 因 为椭圆曲线上的群的阶可以因曲线的不同而改变, 若相应群的阶不够光滑, 则可重新选择曲线. 应用域 Fp 上椭圆曲线的点所产生的群可以实现对大整数 N 的因子分解, 可消除 p - 1 算法的部分弱点, 增加 成功分解的可能性.此通过对 m 的选择可以实现N 的因子分解, 常取 m 为多个小素数因子的积, 这可以增加成功分解的可 能性 4 . 但是, 需要进一步说明的是: 若 N 没有 p - 1 光滑的素因子 p , 则 p - 1 算法不能实现对 N 的因 子分解. 为了避免 p - 1 算法所存在的问题, 可用域 Fp 上的随机椭圆曲线产生的群代替乘法群 Zp , 因 为椭圆曲线上的群的阶可以因曲线的不同而改变, 若相应群的阶不够光滑, 则可重新选择曲线. 应用域 Fp 上椭圆曲线的点所产生的群可以实现对大整数 N 的因子分解, 可消除 p - 1 算法的部分弱点, 增加 成功分解的可能性.由于 p 是未知的, 不能直接在域 Fp 上定义椭 圆曲线, 而应在环 Z/ N Z 上给出椭圆曲线E 5 , 但在 实际的应用中只需 E 上的一个子集即可. 若 N 与2, 3 互素, a, b I Z/ N Z 且( 4a3 + 27b2 , N ) = 1, 方程 y 2 = x 3 + ax + b 定义 Z / N Z 上的椭圆曲线 E a, b, 取 Ea, b 上的子集 V N = ( x , y , 1) | x , y I Z/ N Z G 5 ,其中5= ( 0, 1, 0) 4 , 在 V N 上定义/ 加法运算0, 设 P , Q I V N , R = P + Q, 若 P = 5, 则 R = Q; 若 Q = 5, 则 R = P. 当 P X 5, Q X 5 时, 记 P = ( x 1 , y 1 , 1) , Q( x 2 , y 2 , 1) , 计算 gcd( x 1 - x 2 , N ) , 若 gcd( x 1 - x 2 , N ) 是 N 的真因子, 则计算停止; 若 g cd ( x 1 - x 2 , N ) = 1, 计算 K= ( y1 - y 2 ) ( x 1 - x 2 ) - 1 , x 3 = K2 - x 1 - x 2 , y 3 = K( x 1 - x 3 ) - y 1 , 此时, R= P + Q = ( x 3 , y 3 , 1) I V N .若 g cd( x 1 - x 2 , N ) = N , 即 x 1 = x 2 , 计算 g cd ( y 1 + y 2 , N ) , 若 g cd( y 1 + y2 , N ) 是 N 的真因子, 则 计算停止; 若 g cd( y 1 + y 2 , N ) = N , 即 y 1 = - y 2 , 则R= 5; 若 g cd( y + y , N ) = 1, 计算 K= ( 3x 2 + a) ( y1211+ y2 ) - 1 , x 3 = K2 - x 1 - x 2 , y 3 = K( x 1 - x 3 ) - y 1 , 此 时, R= P+ Q= ( x 3 , y 3 , 1) I V N , 由以上的/ 加法0运算可知, 计算的结果或是得到 N 的一个真因子, 或是得到 R= P+ Q I V N .2. 2 算法的实现与分析在应用上述原理分解一个大的合数 N 时, 常适 当选择相应的椭圆曲线上的一个点 P, 通过计算 kP 以实现对N 的因子分解. 首先, 确定 Z/ N Z 上的椭 圆曲线: y 2 = x 3 + ax + b, 其中( 4a3 + 27b2 , N ) = 1,然后, 选取适当的点 P = ( A, B, 1) , 使得B2 = A3+ aA+ b( mod N ) , 进一步地, 计算 k P.在上述算法实现的过程中, 涉及到一些主要的 运算( 或算法) : 求两个整数的最大公因子的 Euclid-ean 算法; 求乘法群 Z* 中的元素的逆元的扩展 Eu-Nclidean 算法( 其中 Z* = a I Z | gcd( a, N ) = 1, ZNNN是模 N 的剩余类的集合 ) ; 椭圆曲线 Ea, b 上的子集 V N 中的点的加法运算、倍乘运算. 显然, 前两个算法 寓于最后的运算之中.其中的 Euclidean 算法的运行程序为 输入: 两个非负整数 a 和b , a b. 输出: a 和 b 的最大公因子.(1) 当 b X 0 时, 完成下列步骤: 置 ra m od b,ab, br .(2) 返回 a.前面的因子分解算法需要求( x 1 - x 2 ) - 1 ( 或( y1+ y2 )- 1) , 即( x 1*- x 2 ) 在 ZN 中的逆元( g cd( x 1 -x 2 , N ) = 1) , 可以应用扩展的 Euclidean 算法找到 s和t, 使得( x 1 - x 2 ) s + N t = 1, 此时, ( x 1 - x 2 ) - 1 = s ( m od N ) , 扩展 Euclidean 算法的运行程序为输入: 两个非负整数 a 和 b, a b;输出: gcd( a, b) = d, 以及满足等式 ax + by = d 的整数 x 和 y .( 1) 若 b = 0, 则置 d a, x 1, y 0, 并返回( d, x , y ) .( 2) 置 x 2 1, x 1 0, y2 0, y1 1.( 3) 若 b 0 时, 执行下列步骤:q a/ b , r a- qb, x x 2 - qx 1 , y y 2 - qy1 .ab, br, x 2 x 1 , y 2 y 1 , x 1 x , y 1 y.( 4) 置 da, x x 2 , yy 2 , 并返回( d, x , y ) .Euclidean 算法与扩展的 Euclidean 算法的时间复杂度为 O( ( lg n) 2 ) , 为多项式时间算法.关于椭圆曲线上的点倍乘 kP 的运算存在一般l- 1的算法, 首先取 k 的二进制表示k= E kj 2j , kjIj = 0 0, 1 , 依次做倍点计算 2P, 4P, 2l- 1 P ( 2j P=2 2j- 1 P, j = 2, , l - 1) , 然后将对应 kj = 1 的那 些项相加, 设 kj ( 0 j l - 1) 中有w 个1, 则该方 法需做 l - 1 次倍点运算, w - 1 次加法运算, w 的平 均值为 l/ 2. 但是, 此算法不能适用于前述椭圆曲线上的子集 V N 中的点倍乘kP 的运算, 因为它不满足前面的因子分解算法在作点倍乘 kP 运算的过 程中即实现对N 的因子分解的可能性. 事实上, 这 里的因子分解算法中的点倍乘 kP = P + P ,+ P ,k个P显然, 主要是通过椭圆曲线Ea, b 上的子集V N 中的点的加法运算来实现点倍乘kP 的运算, 同时需注意的 是: 点的加法运算过程中的每一步的结果须取模 N 的运算, 然而在 V N 中的点的加法运算过程中可能 实现对N 的因子分解使得算法停止. 现在, 给出椭 圆曲线 Ea, b 上的子集 V N 中的两点之和 P + Q 与倍 点 2P 的计算量, 以 S, M , I 分别表示在 V N 中进行一 次平方运算、乘法运算和求逆运算所需的时间, 依据 前述的 P + Q 的计算公式以及倍点公式可知, 它们 所需的计算量分别为 I + 2M + S 和I + 2M + 2S.但是, 通过计算 kP 能否实现对 N 的因子分解 的目的, 关键在于前述的 a, A, B( 均 I Z/ N Z) 的选取 是否适当, 若最初选取的 a, A, B未能实现对 N 的因 子分解, 则需重新选取 a, A, B直到成功分解 N 为 止.椭圆曲线分解算法，一方面在理论上寻找点乘速度更快的椭圆曲线，另一方面在工程上将针对椭圆曲线分解法的开源代码ECM进行研究和改进，提高ECM的运行效率。同时，本课题也将研究椭圆曲线的素性测定。因为素性测定也是现代数论中一个非常重要的研究课题。而且对于椭圆曲线素性测定的研究，也可以使我们对椭圆曲线的理解更深，恰当地把素性测定中的思想和方法应用于椭圆曲线分解法。同时研究超椭圆曲线分解算法，改进算法中用到的一些函数和亏格，降低时间复杂度。 素性测定和整数分解的方法在现代数论领域中是两个非常重要的研究课题。在有效时间内分解出任意一个大整数问题或判定出该数为素数迄今仍是一个不能完全解决的困难问题。虽然理论上已部分解决了大整数分解的问题，但在实际应用中远远没有解决。随着计算机的快速发展及其与信息的紧密结合，寻找大的素数和大整数因子分解成为现代密码学的重要理论基础，其中，大整数因子分解的困难性是现代密码学的安全基础。RSA密码是现代公钥密码的一个典型代表。目前广泛应用于网络银行USB Key,手机支付、电子护照等安全要求极高的领域。而RSA密码的安全性建立于大整数分解问题。大整数分解问题是计算数论的主要研究课题之一。目前分解100位以上大整数的最有效方法是数域筛分解法。而数域筛分解法又需要调用椭圆曲线分解方法，而且椭圆曲线分解过程在数域筛分解过程中占用了很大一部分时间。因此，提高椭圆曲线分解法的速度将有效地缩短大整数分解的时间。除了数域筛分解法，椭圆曲线分解算法是目前最有效的大整数分解方法之一，是一种概率型算法。基于椭圆曲线的素性测试和整数分解算法，是目前的研究热点问题之一。一方面，该问题的深入研究有利于推动现代数论，特别是计算数论，自身的发展。另一方面，鉴于RSA公钥密码系统安全性所面临的挑战，基于椭圆曲线的公钥密码学得到了飞速的发展，其中一大部分也是基于大整数分解的困难性的，进而利用椭圆曲线的工具更利于分析这些系统的安全性。因此，对于椭圆曲线素性测定和整数分解算法的研究具有重要的理论和实际应用意义。（1) 研究意义素性测定和整数分解是现代数论领域中是非常重要的研究课题。素性测定和整数分解是一个相辅相成的两个问题。在有效时间内分解出任意一个大整数问题或判定出该数为素数迄今仍是一个不能完全解决的困难问题。虽然理论上已部分解决了大整数分解的问题，但在实际应用中远远没有解决。随着计算机的快速发展与信息的紧密结合，大整数因子分解成为现代密码学的重要理论基础。自从1976年Diffle和Hellman提出了公钥密码的概念以来,出现了很多的公钥密码系统,所有这些系统的安全性都依赖于数学的计算困难问题.其中目前应用最广的RSA公钥密码体制就是基于大整数的分解问题。这个问题随着整数的增大，它的困难性急剧增加。目前分解大整数最快算法所需要的时间复杂度是亚指数时间。但是在数学上也没有证明：不存在多项式时间的算法可以解决这个问题。这就意味着RSA密码的安全性没有一个严格的数学证明。所以研究大整数分解问题具有重要的意义。 用于RSA密码的大整数分解问题一般是指：给定一个由两个素数p,q相乘而得的整数N，其中N是公开的，而p,q是保密的。要求分解整数N.当N大于100位时，分解N的最好算法是数域筛方法，而数域筛分解法又需要调用椭圆曲线分解方法，而且椭圆曲线分解过程在数域筛分解过程中占用了很大一部分时间。因此，提高椭圆曲线分解法的速度将有效地缩短大整数分解的时间。基于椭圆曲线的素性测试和整数分解算法，是目前的研究热点问题之一。一方面，该问题的深入研究有利于推动现代数论，特别是计算数论，自身的发展。另一方面，鉴于RSA公钥密码系统安全性所面临的挑战，基于椭圆曲线的公钥密码学得到了飞速的发展，其中一大部分也是基于大整数分解的困难性的，进而利用椭圆曲线的工具更利于分析这些系统的安全性。因此，对于椭圆曲线素性测定和整数分解算法的研究具有重要的理论和实际应用意义。（2) 国内外研究现状及发展动态对于素性测定，最有名的是Fermat 测试算法 , Miller-Rabin 测试 , G-K 椭圆曲线算法 , ECPP 测试。目前已知的整数分解方法基本上可以划分为两大类，一类称为同余式的组合法，如二次筛法、数域筛法、连分式法等，另一类称为光滑阶群法，如分解算法、分解算法、分解算法、椭圆曲线分解算法等。虽然已有人提出了在理论上多项式时间内素性测定算法，但还没有进入应用阶段。刘如玉，周锦君1999年对椭圆曲线整数分解法进行研究，对其做了一些改进，并在机上实现了这一改进的算法，分解了一个位的十进制整数（两个位素数之积）。刘祥伟，吴永2006年阐述了代数几何中关于椭圆曲线的定义及相应的运算法则，依据p-1算法给出了基于椭圆曲线的因子分解算法的原理与实现方式，同时对此算法程序在运行过程中所涉及的若干子程序（算法）作了全面的分析。2010年于飞根据超奇异椭圆曲线有理点个数与素数的关系，提出一个具有多项式时间复杂度的素性检验的概率型算法。 根据超奇异椭圆曲线有理点个数与素数的关系，提出一个具有多项式时间复杂度的素性检验的概率型算法。对于给定的整数N , 如果N3( mod 4) 或者N1( mod 3)，该算法具有多项式时间O( log )。在广义黎曼假设成立的情况下, 对于所有整数都具有这一时间复杂度。目前实现椭圆曲线分解算法的最好的是由Zimmermann 和Dodson推出的GMP-ECM软件。该软件能够分解较大的大整数。但是数学家仍希望进一步改进该软件，使得时间复杂度更低，提高效率。且不断有数学家在此软件的基础上提出新的算饭和新的软件，推进了椭圆曲线算法的发展，也加速了软件的快速更新。2011年ROMAIN COSSET在椭圆曲线算法的基础上了提出了超椭圆曲线算法HECM，该算法是将椭圆曲线算法中亏格为1的椭圆曲线推广到亏格为2的超椭圆曲线，从而推出了超椭圆曲线算法。ROMAIN COSSET证明了该超椭圆曲线代替椭圆曲线来分解整数或进行素性判定的可行性，虽然在理论上超椭圆曲线分解算法比椭圆曲线分解算法ECM要慢；但ROMAIN COSSET 提出了在Kummer 平面上利用特殊的超椭圆曲线分解大整数，降低了时间复杂度，并在MP-ECM软件的基础上实现了HECM算法，验证了该算法要比ECM算法快很多。ROMAIN COSSET推进椭圆曲线算法迈进了新的领域。Daniel J. Bernstein, Peter Birkner, Tanja Lange, and Christiane Peters对GMP-ECM方案进一步改进的基础上提出了一个更好的算法，称之为GMP-EECM算法, 该算法比GMP-ECM算法更快更有效。GMP-ECM算法主要是在GMP-ECM算法基础上做了在以下几个方面的改进：（1）用Edwards曲