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

论有限域GF(2m)上椭圆曲线的点构成加法群摘要椭圆曲线理论是代数几何、数论等多个数学分支的一个结合点，一直被认为 是纯理论学科1985年，V.Miller和N.Koblitz各自独立地提出椭圆曲线密码 体制目前，椭圆曲线密码体制在理论和实践上都取得了很大的进展，使用椭圆 曲线来构建密码系统的方法研究也取得了比较满意的效果本文以基础定义开 始，以细致的背景如有限域、群概念研究来介绍有限域GF(2m)上椭圆曲线的点 构成加法群关键词 椭圆曲线；有限域；GF(2m)；加法群引言椭圆曲线密码学(ECC, Elliptic curve cryptography)是基于椭圆曲线数 学的一种公钥密码的方法椭圆曲线在密码学中的使用是在1985年由Neal Kobli tz和Vic tor Miller分别独立提出的ECC的主要优势是在某些情况下它 比其他的方法使用更小的密钥——比如RSA——提供相当的或更高等级的安全对椭圆曲线来说最流行的有限域是以素数为模的整数域(参见 模运算)$GF(p)$,或是特征为2的伽罗华域GF(2m)後者在专门的硬件 实现上计算更为有效，而前者通常在通用处理器上更为有效。

专利的问题也是相 关的一些其他素数的伽罗华域的大小和能力也已经提出了，但被密码专家认为 有一点问题给定一条椭圆曲线E以及一个域$GF(q)$,我们考虑具 有$(x,\; y)$形式有理数点$E(q)$的阿贝尔群，其中x 和y都在$GF(q)$中并且定义在这条曲线上的群运算"+"在文章椭圆 曲线中描述我们然後定义第二个运算"*" | ZX$E(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： F\{0}的元素关于运算“*”构成交换群即F中元素排除元素0 后，关于*法构成交换群•F3:分配率成立，即对于任意元素a，b， cWF,恒有 a* (b+c) = (b+c) *a=a *b+a *cp是素数时，可证F{0, 1，2,…，p-1}，在modp意义下，关于求和运算“ + ”， 及乘积“*”，构成了域F域的元素数目有限时称为有限域有限域元素的数目称为有限域的阶对于有限域，其元素的数目必然是素数 的幕而这个对应的素数成为有限域的特征在编码和密码理论里面2'n阶有限 域被广泛使用，具有非常重要的意义2. 椭圆曲线2.1椭圆曲线定义它的(仿射)标准方程是y"2=x(x-1)(x-1)，这里t是任意不等于0和1的参数作为实曲面看，椭圆曲线就是带有一个洞的闭曲面——环面环面可以通过 同向粘合正方形的两对对边得到，其拓扑亏格为1椭圆曲线和椭圆函数，椭圆积分等内容密切相关，这里不再详述著名的费 马大定理的证明也与此有关总之，椭圆曲线是代数几何中最重要的一类研究对 象2.2具体介绍椭圆曲线上的点全体构成一个加法群，点与点之间的“加法”运算，如图 所示正因为椭圆曲线存在加法结构，所以它包含了很多重要的数论信息。

椭 圆曲线和它的雅可比簇是同构的，所以它上面的“加法”结构实际上来自于它的 雅可比簇的自然加法结构椭圆曲线上的有理点的个数也是人们关心的重要问题，这个问题和著名的 Mordell-Weil 定理有关Mordell-Weil定理是说：椭圆曲线上有理点构成的群是有限生成的另一方面，椭圆曲线上的整点只有有限多个，这个定理被称为Siegel 定理通过以下实例，可以更好的理解上述两个定理：椭圆曲线y"2=x,+17上，仅有16个整点：(-2,3),(-1,4),(2,5),(4,9),(& 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,beF2m，b#0定义的一个非超奇异椭圆曲线E(F2m)是方程 y2+xy=x3+ax2+b (5)的解集合(x,y),其中x,y^GF(2m)，连同8 (—个额外的“无穷远点构成 的点集合)E(F2m)的加法规则如下：(1) 8 +8 = 8(2) 任给(x,y) e E(F2m)，贝U (x,y) © 8 =(x,y)(3) 任给(x,y) e E(F2m)，则(x,y) + (x,x+y)二 8 ,即点(x,y)的逆为(x,x+y).(4) 两个相异且不互逆的点的加法规则：令(xl,yl),(x2,y2) e E(F2m)且有 xlHx2则(xl,yl) +(x2,y2) = (x3,y3),其中x3=a 2+a +xl+x2+a；y3=a (xl+x3)+x3+yl.其中 a = (y2+yl)/(x2+xl)(5) 倍点规则令(xl,yl) eE(F2m)，其中 xlHO贝U2(xl,yl) = (x3,y3),其中x3= a 2+ a +a, y3=x12+(a +1)x3,这里a =(x1+y1/x1)易见，群E(F2m)为Abel群，也即P+Q=Q+P对E(F2m)中所有的点都成立，即 有限域GF(2m)上椭圆曲线的点构成加法群。

5. 总结文中数学背景和简单的有限域GF(2m)上椭圆曲线的点构成加法群理论，虽 然涉及的数学理论知识很多且杂，但都还只是是椭圆编码理论中的基础部分，对 于本理论的进一步发展及运用都还需更多的学习和研究而且针对于椭圆密码理 论运用于安全保密性编码等方面，远远强于有限域上的离散对数的密码体制，但 其实际运用还有待发展和推广参考文献[1] 杨波•现代密码学•清华大学出版社，2003.[2] 王建，蒋安平，盛世敏•椭圆曲线加密体制的双有限域算法及其FPGA 实现[J].北京大学学报，2008，44(6)： 871-875.[3] 彭长根，李祥.有限域GF(2~m)上椭圆曲线密码体制的运算分析.贵州大 学学报，2005.[4] 张焕国译•椭圆曲线密码学导论.电子工业出版社，2005.[5] 汪朝晖，陈建华•素域上椭圆曲线密码的高效实现[J].武汉大学学报(理 工版)，2004.。