椭圆曲线上的点构成的加法群.doc

论有限域GF(2m)上椭圆曲线的点构成加法群摘 要椭圆曲线理论是代数几何、数论等多个数学分支的一个结合点，一直被认为是纯理论学科。1985年，V.Miller和N.Koblitz各自独立地提出椭圆曲线密码体制。目前，椭圆曲线密码体制在理论和实践上都取得了很大的进展，使用椭圆曲线来构建密码系统的方法研究也取得了比较满意的效果。本文以基础定义开始，以细致的背景如有限域、群概念研究来介绍有限域GF(2m)上椭圆曲线的点构成加法群。 关键词 椭圆曲线；有限域；GF(2m) ；加法群引 言椭圆曲线密码学（ECC, Elliptic curve cryptography）是基于椭圆曲线数学的一种公钥密码的方法。椭圆曲线在密码学中的使用是在 1985年由Neal Koblitz和Victor Miller分别独立提出的。ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥比如RSA提供相当的或更高等级的安全。对椭圆曲线来说最流行的有限域是以素数为模的整数域(参见 模运算)GF(p)，或是特征为2的伽罗华域GF(2m)。後者在专门的硬件实现上计算更为有效，而前者通常在通用处理器上更为有效。专利的问题也是相关的。一些其他素数的伽罗华域的大小和能力也已经提出了，但被密码专家认为有一点问题。给定一条椭圆曲线E以及一个域GF(q)，我们考虑具有(x, y)形式有理数点E(q)的阿贝尔群，其中x和y都在GF(q)中并且定义在这条曲线上的群运算+在文章椭圆曲线中描述。我们然後定义第二个运算* | ZE(q)-E(q)：如果P是E(q)上的某个点，那么我们定义2*P=P+P, 3*P=2*P+P=P+P+P等等。注意给定整数 j和k，j*(k*P)=(j*k)*P=k*(j*P)。椭圆曲线离散对数问题(ECDLP)就是给定点P和Q，确定整数k使k*P=Q。1. 有限域简介有限域最简单的有限域是整数环Z 模一个素数p得到的余环Z/(p),由p个元素0,1,p-1组成,按模p相加和相乘。集合F=a，b，对F的元素定义了两种运算：“+”和“*”，并满足以下3个条件：F1：F的元素关于运算“+”构成交换群，设其单位元素为0。 F2：F0的元素关于运算“*”构成交换群。即F中元素排除元素0后，关于*法构成交换群。 F3：分配率成立，即对于任意元素a，b，cF， 恒有a*(b+c)=(b+c)*a=a*b+a*c p是素数时，可证F0，1，2，p-1，在modp意义下，关于求和运算“+”，及乘积“*”，构成了域。F域的元素数目有限时称为有限域。 有限域元素的数目称为有限域的阶。对于有限域，其元素的数目必然是素数的幂。而这个对应的素数成为有限域的特征。在编码和密码理论里面2n阶有限域被广泛使用，具有非常重要的意义。2. 椭圆曲线2.1椭圆曲线定义椭圆曲线就是亏格为1的代数曲线。 一条光滑的椭圆曲线可以放在射影平面里看，它的(仿射)标准方程是y2=x(x-1)(x-t)， 这里t是任意不等于0和1的参数。 作为实曲面看，椭圆曲线就是带有一个洞的闭曲面环面。环面可以通过同向粘合正方形的两对对边得到，其拓扑亏格为1。 椭圆曲线和椭圆函数,椭圆积分等内容密切相关，这里不再详述。 著名的费马大定理的证明也与此有关。总之，椭圆曲线是代数几何中最重要的一类研究对象。 2.2具体介绍椭圆曲线上的点全体构成一个加法群， 点与点之间的“加法”运算，如图所示。 正因为椭圆曲线存在加法结构，所以它包含了很多重要的数论信息。椭圆曲线和它的雅可比簇是同构的，所以它上面的“加法”结构实际上来自于它的雅可比簇的自然加法结构。 椭圆曲线上的有理点的个数也是人们关心的重要问题，这个问题和著名的Mordell-Weil定理有关。 Mordell-Weil定理是说：椭圆曲线上有理点构成的群是有限生成的。 另一方面，椭圆曲线上的整点只有有限多个，这个定理被称为Siegel定理。 通过以下实例，可以更好的理解上述两个定理： 椭圆曲线y2=x3+17上，仅有16个整点:(-2,3),(-1,4),(2,5),(4,9),(8,23),(43,282),(52,375),(5234,378661)。以及它们关于x轴的对称点，而其上所有的有理点可以由(-2,3),(2,5)通过群上的加法生成。 Bezout定理告诉我们， 两条光滑椭圆曲线相交于9个点（切点重复计算）。 进一步，如果有第三条光滑椭圆曲线经过其中的8个交点，那它必定经过第九个点。这是古典代数几何中的一个重要的结论。欧拉对此问题也有过考虑。 作为推广，X.诺特（Noether）曾经得到了更一般的代数曲线交点的类似结论。 这个问题和代数曲面上秩2向量丛的半稳定性有着深刻的内在联系。 谈胜利利用秩2向量丛的Bogomolov不等式， 将此问题推广到最一般的情形。 2.3特殊的情形由于椭圆曲线在射影平面中是三次曲线，所以它可以退化为许多特殊的情形： （1）三条直线； （2）一条直线和一条二次曲线（即圆锥曲线，比如椭圆，双曲线） 将这些退化情形放到上述的结论中， 我们就得到了许许多多著名的射影几何中的著名定理，比如帕斯卡定理等等。3. 加法群的概念群（group）是一个数学概念，群论是一门数学学科。群论是伽罗瓦为了解决他那个时代的几个首要的数学问题之一而创造的，那个问题是：什么时候可以用二次公式的某个推广来找到一个多项式的根. 定义:设G是一个非空集合，*是它的一个（二元）代数运算，如果满足以下条件：1. 封闭性：群内任意两个元素或两个以上的元素（相同的或不同的）的结合（积）都是该集合的一个元素。即若a和b是G中的元素，则它们的乘积a*b也是G中的元素。 2. 结合律：虽然群元素不一定要求满足交换律，但必须满足结合律，即对G中任意元素a,b,c都有 (a*b)*c=a*(b*c)； 3. 单位元素：集合G内存在一个单位元素e，它和集合中任何一个元素的积都等于该元素本身，即对于G中每个元素a都有 e*a=a； 4. 逆元素：对G中每个元素a在G中都有元素a（-1），叫做a的左逆元，使 a（-1）*a=e； 元素的集合如果满足上述四个条件就称为群。4. GF(2m) 上的椭圆曲线加法群的实现 GF(2m)上的椭圆曲线 GF2m上由参数a,bF2m，b0定义的一个非超奇异椭圆曲线E(F2m)是方程 y2+xy=x3+ax2+b (5) 的解集合(x,y)，其中x,yGF(2m)，连同（一个额外的“无穷远点构成的点集合）。 E(F2m)的加法规则如下： (1) += (2) 任给(x,y) E(F2m)，则(x,y) =(x,y) (3) 任给(x,y) E(F2m)，则(x,y)+(x,x+y)= ， 即点(x,y)的逆为(x,x+y). (4) 两个相异且不互逆的点的加法规则： 令(x1,y1),(x2,y2) E(F2m)且有x1x2则(x1,y1) +(x2,y2)=(x3,y3)，其中 x3=2+x1+x2+a； y3=(x1+x3)+x3+y1. 其中 = (y2+y1)/(x2+x1) (5) 倍点规则 令(x1,y1) E(F2m)，其中x10。则 2(x1,y1)=(x3,y3)，其中 x3= 2+ +a, y3=x12+( +1)x3, 这里 =(x1+y1/x1) 易见，群E(F2m)为Abel群，也即P+Q=Q+P对E(F2m)中所有的点都成立,即有限域GF(2m)上椭圆曲线的点构成加法群。5.总结文中数学背景和简单的有限域GF(2m)上椭圆曲线的点构成加法群理论，虽然涉及的数学理论知识很多且杂，但都还只是是椭圆编码理论中的基础部分，对于本理论的进一步发展及运用都还需更多的学习和研究。而且针对于椭圆密码理论运用于安全保密性编码等方面，远远强于有限域上的离散对数的密码体制，但其实际运用还有待发展和推广。参考文献1 杨波.现代密码学.清华大学出版社，2003.2 王建，蒋安