（基础数学专业论文）基于双线性对的密码体制研究.pdf

摘要 n e a ! k o b l i t z 在1 9 8 9 年提出了超椭圆曲线密码体制( h e c c ) 。与e c c 相比，h e c c 具有在比较小的基域上提供与e c c 同等级别的安全性的优势，因而超椭圆曲线密码体制 的相关理论在最近l o 年倍受密码学界的高度重视。 2 0 0 0 年j o u x 开创性地提出了基于双线性对的单轮三方d i f f i e - h e l l m a n 密钥协商协 议。近几年已经有很多基于椭圆曲线的双线性对的应用。双线性对的应用成了最近几年 研究的热门问题，但是还有很多具体问题没有很好的解决。在本论文中，作者主要做了 以下几方面的工作： ( 1 ) 利用m a p l e 实现椭圆曲线密码体制的加、解密。 ( 2 ) 给出了基于双线性对的消息恢复签名方案。 关键词超椭圆曲线超椭圆曲线密码体制双线性对消息恢复签名方案 a b s t r a c t i n1 9 8 9n e a lk o b l i t zf a s tp u tf o r w a r dt h et h e o r yo fh y p e r e l l i p t i cc u r y ec r y p t o s y s t e m s ( h e c c ) c o m p a r c dt oe c c ，t h eb a s e - f i e l do f h e c c i ss m a l l e rt h a nt h a to f e c cw i t ht h eg a m e l e v e lo fs e c u r i t y a n dt h e r e f o r e ，t h er e l a t i v et h e o r yo fh e c ca t t r a c t sm u c hi m p o r t a n ta t t e n t i o n i nt h el a s t1 0y e a r s j o u xi n i t i a l l yp r o p o s e dao n e r o u n dt h r e e - p a r td e f i l e h e l l m a nk e yc h a n g ep r o t o c 0 1 t h e r e h a sb e e nal o to fe f f i c i e n ti m p l e m e n t a t i o no fp a i r i n g so ne l l i p t i cc u r v e s t h ea p p l i c a t i o n so f p a i r i n g sa r cp o p u l a ri s s u e si nt h el a s ty e a r s ，b u tt h e r ea r em a n yi d i o g r a p h i cp r o b l e m sw h i c h a r e n o ts e t t l c dy e t i nt h i sd i s s e r t a t i o n t h em a i nw o r k so f t h ea u t l l o ri sf o l l o w s ： ( 1 ) t h ee n c r y p t i o na n dd e c e p t i o no f t h ee c c c o u l db ea c t u a l i z e di nm a p l e ( 2 ) a ne f f i c i e n ti d b a s e dd i g i t a ls i g n a t u r ew i t hm e s s a g er e c o v e r yi sp r o p o s e db a s e do n t h eb i l i n e a rp a r i n g k e yw o r d s ：h y p e r e l l i p t i cc b r v e ，h y p e r e l l i p t cc n r v ec r y p t o s y s t e m ，b i l i n e a rp a i r i n g , i d - b a s e d d i g i t a ls i g n a t u r ew i t hm e s s a g er e c o v e r y n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。除文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得海南师范大学或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名 学位论文著作权声明 f 了期： 洫2 ：厶l f 本硷文作者声明： 口 本论文全部成果均为本人和指导教师台作研究取得，本人和指导教师都有权 使用本成果学术内容( 有第三方约定者除外) 。 口 本论文为指导教师指导埘卜，本人独自完成。本人独自享官本论文的全部著作 权 学位论文作者签名 n期 挺 一燃名：将 细一幺上 1 1 抓钇9 i 一台r 学位论文版权使用授权书 本学位论文作者完龟了解海南师范大学有关保留、使用学位论文的规定，即： 海南师范大学有权保疆并向国家有关都fj 或机构送交学位论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权海南师范大学可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后使用本授权书) 学位论文作者签名：鱼复袅辈 f f期：2 鲫- 彳? 上 f _ j 矶力晦- 厶r ， 第一章绪论 1 1 超椭圆曲线密码体制的研究背景及其意义 作为椭圆曲线密码体制的推广，n e a l k o b l i t z 在1 9 8 9 年提出了超椭圆曲线密码体制 ( h e c c ) ( 我们知道，椭圆曲线就是亏格为l 的超椭圆曲线) ，它是基于有限域中超椭圆 曲线上j a e o b i a n 的离散对数问题( h c d l p ) 的计算困难性。与e c c 相比，h e c c 具有在比 较小的基域上提供与e c c 同等级别的安全性的优势，因而超椭圆曲线密码体制的相关理 论在最近1 0 年受到密码学界的高度重视。 与其它的公钥密码体制相比，超椭圆曲线密码体制有以下优点： ( 1 ) 在具有相同阶的超椭圆曲线上j a e o b i a n 与椭圆曲线上有理点群所建立的密码体 制提供相同强度安全性。h e c c 建立在h c d l p 基础之上，从计算复杂度的角度考虑， h c d l p 是一个n p c o a m 问题。1 。 ( 2 ) h e c c 的一个显著的优势就是：当提供和r s a 相同级别的安全性时，它可以使 用更短的密钥长度，从而可以使用更少的带宽。在密钥长度为8 0 1 0 0 之问所建立的h e c c 就足以抗击目前的密码攻击。 ( 3 ) 目前对低亏格( g 4 ) 的h e c c 的最有效攻击是指数时间型，对于亏格小于4 的一般超椭圆曲线还没有发现亚指数时间型的攻击。 ( 4 ) 设髟是特征为奇素数的有限域，对于k 上的j a c o b i a n 中的加法运算，康托 ( c a n t o r ) 提供了一种有效算法“1 。并i ；1k o b l i t z 在1 9 8 9 年把康托的算法推广到任意的有 限域上“1 。 ( 5 ) 实践证明：在相同安全级别上，h e c c 需要的基域比e c c 需要的基域还小。 ( 6 ) 在亏格g 4 的前提下，在相同的定义域上，亏格越大超椭圆曲线越多，所以选 取用于密码体制中的安全曲线的余地就越大。 ( 7 ) 研究h e c c 的一个重要的现实意义就是，可以把已经比较成熟的e c c 密码体 制的一些协议、方案推广到h e c c 上。并且可以把用于h e c c 上的一些普遍的技术和方 法用在e c c 上，从而推动e c c 的发展。 但是，超椭圆曲线密码体制也有缺点，最显著的是j a e o b i a n 的运算法则要比e c c 的 群运算法则复杂，且确定j a e o b i a n 的阶比较困难。从已有的h e c c 的实现来看，h e c c 的实现速度并不理想，但e h 于具有上述优点，所以仍有很大的研究必要。况且，只有在 海南师范大学硕士学位论文 对它作深入研究，才能发现更高效的算法，才能使得它早日走向成熟。 由于h e c c 可以提供更少的带宽，并且需要更小的基域，从而有许多e c c 所不具备 的优点。虽然目前h e c c 的实现不理想，但是可以相信，一旦有了有效的算法，h e c c 必将成为主流密码体制强有力的竞争对手，特别是带宽和内存受限的应用( 如智能卡) 。 1 2 超椭圆曲线密码体制的研究现状 最近几年，超椭圆曲线密码的相关文章尽管很多，但是仍然有很多问题没有解决。 下面就超椭圆曲线密码体制的研究现状作一综述。 超椭圆曲线密码体制基于超椭圆曲线一l j a c o b i a n 的离散对数的计算困难性，有限域 上超椭圆曲线上j a c o b i a n 是一个交换群。对于特征为奇素数的有限域k 上的j a c o b i a n 的 加法运算，康托( c a n t o r ) 提供了一种有效的算法”。并且k o b l i t z 在1 9 8 9 年把康托的算 法推广到任意的有限域上“1 。 本节下面提到的运算，都是指j a c o b i a n 的运算。 对于定义在任意特征上的亏格为2 的超椭圆曲线，h a r l e y “1 首次给出具体加法公式， 2 0 0 2 年h s u g i z a k i 等人把h a r l e y 的算法推广到偶特征的有限域上。对| 丁奇特征域上的亏 格为2 的超椭圆曲线，l a n g e 在2 0 0 2 给出了射影坐标下的的加法，倍乘算法公式”1 。 对于亏格为3 的超椭圆曲线，x f a n & y w a n g ”1 在2 0 0 4 年给出了摄影坐标下不用求逆 的算法。t w o l l i n g e r 在他的博士论文“3 1 中给出了j o b i a n 的加法运算。2 0 0 5 年m g o n d a 2 7 1 等人给出了提高算法。 超椭圆曲线密码体制的实现方面，很多人认为超椭圆曲线上除予类群的运算代价太 高，所以超椭圆陆线密码体制在2 0 0 3 年之前主要是处在理论阶段的研究。2 0 0 4 年开始陆 续出现了一些比较简单的加法运算( 如t w o l l i n g e r 、m g o n d a 等人给出的算法) 。在实现 速度上有了很大的改进，再加上超椭圆曲线密码体制自身的一些优点，使得e c c 有向 h e c c 发展的趋势。 当然，超椭圆曲线密码体制的实现还有很多需要进一步改进的地方。下面给出目前 在h e c c 研究中急需解决或比较备受关注的几个问题： 1 寻找有效算法计算超椭圆曲线上j a c o b i a n 的阶。 2 如何提高超椭圆曲线上j a c o b i a n 的基本运算的速度。 3 如何提高超椭圆曲线上j a c o b i a n 的标量乘法运算，从而提高整个超椭圆曲线密码 体制的实现速度。 第一章绪论 4 如何进一步提高明文潜入到超椭圆曲线上除子的方法。 5 针对j a c o b i a n 的攻击需要进一步研究，有助于提高超椭圆曲线密码体制的安全性。 6 超椭圆曲线密码体制的标准化实现。 1 3 基于双线性对的密码体制的研究现状 2 0 0 0 年j o u x “1 开创性地提出了基于双线性对的单轮三方d i f f i e h e l l m a n 密钥协商协 议，同年，r s a k a i ，k o h g i s h i 和m k a s a h a r a x 基于- 5 0 3 线性对的密码体制进行了初步研究” ”。2 0 0 4 年j o u x 给出了加强版的基于双线性对的单轮三方d i f f i e - h e l l m a n 密钥协商协议“1 。 2 0 0 1 年，p i o n t c h c v a l 和o k a m o t o 在文献 1 0 中给出了如何利用g a p d h 设计数字签名 方案。b o n e h 、l y 帅和s h a c h a m 利用超奇异的椭圆曲线上的w e i l 对设计了短签名方案1 。 自从s h a m i r - y - 1 9 8 4 年提出了基于身份( i d e n t i t y b a s e d ) 数字签名方案，基于身份的 加密方案一直没有解决，直到2 0 0 1 年b o n e h 和f r a n k l i n 给出了著名的基于身份的加密方案 t 2 l ，他们在2 0 0 3 年又给出了抗选择密文攻击的加密方案1 。此后，基于双线性对的密码 体制成了密码学上最热门的问题之一。最近，t a r e 对和w e i l 对已经被用在构建不同的密码 体制上了”z a 。t o 因此，很多人在研究如何提高双线性对的计算问题( 2 5 、 2 6 、 1 5 、 2 8 、 2 9 、e 3 0 、 3 1 、 3 2 、 3 3 、 3 4 、 3 5 ) 。 2 0 0 4 年，p s l m b a r r e t o 等人“”对于某些特殊类型的曲线( 主要是特征为2 和3 的超 椭圆曲线以及特征为p - - - 3 m o d 4 拘d u u r s m a - l e e 型曲线，= r x + d 。”) 提出了一种新 的双线性对，称为e t a 对。更确切地说，e t a 对的值是把t a t e 对的值升幂到某个常数。事实 证明：相对于t a r e 对的计算，e t a 对节省计算量。主要原因是e t a 对的计算过程只是t a t e 对 计算过程的一小部分。 e t a 对出现之后，e h e s s “6 1 等人把e t a 对简化为a t e 对，并且把a t e 对用于普通的椭圆曲 线上。 2 1 有限域 第二章超椭圆曲线的基本理论 关于有限域的详细知识，请参考文献 1 7 1 9 ，3 6 ，本论文以下部分只给m 有用的定 义和定理，其证明全部省略。 定义2 1 1 设限+ ，) 上是交换环，如果满足： ( 1 ) f 中至少含有两个元素0 和1 。 ( 2 ) f + = f 0 构成乘法群。 那么称( f ，+ ，) 是域。 具有有限个元素的域成为有限域。吒= 2 ，p z ( p 为素数) 是最简单的有限域。 设巧表示特征为p 且含有g 个元素的有限域，我们知道，吒可以看成b 上的向量空 间，设维数为d ，则g = p 8 。 定理2 1 1 设啄是含有g = p 4 个元素的有限域，令盯：n 卜o ，则盯是e 上的一 个自同态。 定理2 1 2 设巧是含有g = p d 个元素的有限域，那么的子域为巧( 其中| d ) 。 密码学上用的最广的两个有限域大素数有限域虬( p 为大素数) 和特征为2 的有 限域。 下面给出有限域中元素常见的表示方法； ( 1 ) 有限域贬t 的多项式基 对于任意给定的k 2 ，总存在吒上的k 次不可约多项式r e ( x ) ，则 吩- 兰b 【z 】( m ( z ) ) ，巴也可以看作m ( z ) 的一个根口添加到哆所得到的最小扩域。有限域 0 - 实际上是巧上的七维向量空间，设口是m ( z ) 在巴。上的一个根，则 一，口2 ，0 “) 在吒 卜线性无关，构成向量空间的组基。在多项式基表下，e 。中的元素可以看成次数小于 t 的多项式。 ( 2 ) 有限域贬t 的正则基 4 第二章超椭圆曲线的基本理论 元素口l 。称为上的正则元，如果口，口p ) - - - , 口，“在吒上线性无关。此时称 口，口，口矿“) 为上髟的一组正则基。 2 2 椭圆曲线 本节中我们只讨论大素数域上的椭圆曲线p 9 1 。 当p 是大素数，那么有限域k = e 上的椭圆曲线e 是由下面的方程确定的： y 2 = ，+ 似+ 6 ( 2 2 i ) 其中a , b k 且( ( 4 矿+ 2 7 b 2 ) m o d p 0 。易知e 在k 上的有理点连同无穷远点0 0 构成一个 加法交换群e 饭) ，其加法公式( 2 2 1 ) 如下： ( 1 ) 若p = ( 玉，m ) e e ，贝l j - p = ( 一，- ) 1 ) 且，+ ( 一户) = 。 ( 2 ) 若q = ( 而，儿) e 且q - p ，则p + q = ( x 3 ，y 3 ) 。其中 毛= k 2 一 一x 2 乃= i “一而) 一月 且 k = 儿一m 屯一玉 3 0 + 口 2 y l i f p q i f p = q m a p l e i “1 是功能强大的符号处理和数值分析工具，它是一种计算机代数系统。由于其 符号处理功能的强大，已经成为理论分析强有力的工具。作为强大的交互式计算软件， m a p l e 可以向控制台输入各种命令完成各种代数运算或数值运算。同时，对于复杂的运算， m a p l e 提供了强大的编程接口和工具包来帮助用户完成复杂的编程工作。相比c 语言， m a p l e i i 吾言更接近于平时说话的语法。同时，m a p l e 语言可以方便地转化成c 语言，这为 编程带来了方便，并且运行效率比较理想。 程) 葶c o o r d i n a t e 4 5 l 要确定椭圆曲线上的有理点，首先需要矿+ 甜+ 6 是模数p 的二次剩余。关于二次剩 余，将用到下面的定理“”。 海南师范大学硕i 学傍论文 定理2 2 1 ( 欧拉准则)设p 为素数，则对v 虻是模p 的二次剩余当且仪当 0 7 一2i l m o d p 由于”；h m o d p 时，月和珂同为模数p 的二次剩余或同为模数p 的二次非剩余。对 于有限域上求平方根运算，m a p l e 给出t r o o t s 0 命令。因此，对于方程( 2 2 1 ) 确定的椭圆 曲线e ，确定e 在k 上的有理点，结合定理2 2 1 可用m a p l e 编程实现，程序如下： 一c o o r d i n a t e ：= p r o c ( a ，b ，x ，p ) l o c a ln , y ，c ； n ：= ( x “3 + a + x + b ) m o dp ； i fi r e m ( n ，p ) = ot h e nc ：2 【x ，0 】； e l i f n “( ( p 1 ) 2 ) m o dp 。1t h e n c ：= 【x ，r o o t s ( y “2 一n ) m o dp 】； e l s e c ：= f ： f i ；c ：e n d ； 说明： ( 1 ) 输出f 表示方程2 2 1 没有y 的解。 ( 2 ) m 印i e 中r o o t s 命令输出多项式在有限域b 上所有根及对应根的重数。例如：若输 a r o o t s ( y 2 1 0 ) m o d1 3 ，则输出 7 ，1 ， 6 ，1 ，就是说y 2 = 1 0 在；3 中有2 个单根7 和 6 ；若输入r o o t s ( y n 3 + y n 2 y 1 ) m o d1 3 ，则输出 1 ，1 ， 1 2 ，2 ，就是说y 3 - y 2 - y - ! = 0 在珏i ，中有一个单根1 和一个二重根1 2 ( 3 ) 程序中表示点的坐标时用“ ”代替了“( ) ”。因为在m a p l e q b 0 被认为是 程序中连接整体的符合，所以无法输出。下面所有程序都是这样的。 利用i t h p r i m e ( k ) 可以求第k 个素数，比如： it h p r i m e ( 9 9 9 0 0 0 ) ； 1 5 4 6 9 3 1 3 即第9 9 9 0 0 0 个素数为1 5 4 6 9 3 1 3 。 例2 2 1设椭圆曲线e 是有限域k = f ( p = 1 5 4 6 9 3 1 3 ) 上方程y 2 = + j + 6 确定 的。求出e 上的趸一有理点。比如： 第二章超椭圆曲线的基本理论 c o o r d i n a t e ( i ，6 ，0 ，1 5 4 6 9 3 1 3 ) ； f c o o r d i n a t e ( 1 ，6 , 2 ，1 5 4 6 9 3 1 3 ) ； 【2 ，【4 ，1 】，【1 5 4 6 9 3 0 9 ，l 】 c o o r d i n a t e ( 1 ，6 ，1 8 ，1 5 4 6 9 3 1 3 ) ； 【1 8 ， 1 5 1 0 2 3 5 2 ，i i ， 3 6 6 9 6 1 ，1 】 也就是说e ( 峨m ) 中存在有理点( 2 ，4 ) ，( 2 ，1 5 4 6 9 3 0 9 ) 及( 1 8 ，1 5 1 0 2 3 5 2 ) ，( 1 8 ，3 6 6 9 6 1 ) 。 程序a d d p i o n t l 4 s 设毋= “，m ) 最= ( 而，咒) ，若一而，则由加法公式( 2 2 1 ) 可求出曷+ ：若= x 2 ， 要么咒= 儿( 即舅= 县) ；要么乃= 喁( 即墨= 一最，亦即暑+ b = m ) 。因此，根据加法 公式( 2 2 1 可用m a p l e 的i f i 目句编程求弓+ 最。程序如下： a d d p i o n t ：= p r o c ( x _ l ，yl ，x2 ，y 3 ，a p ) l o c a lk , x _ 3 ，y _ 3 ，q ； i f x i x 一2 t h e n k ：= ( y 二l 一) ，_ 2 ) ，( xl - x2 ) m o dp ； x 3 ：= ( k 2 - x _ l - x _ 2 ) m o dp ； y _ 3 ：_ k + ( x _ l - x _ 3 ) - y _ lm o dp ； q ：2 【x - 3 ，y - 3 】； e l i f y _ l = y _ 2t h e n k ：鼍3 + x _ l 2 + a ) ( 2 + y - 1 ) m o dp ； x3 ：2 ( k 2 一k l - x _ 2 ) m o dp ； y - 3 ：= k ( x _ l - x _ 3 ) - y _ lm o dp ； q ：= 【) _ 3 ，y _ 3 】； e l s eq ：= i n f i n i t y ； f i ；q ；e n d ； 例2 2 1 中月= ( 2 ，4 ) ，最= ( 2 ，1 5 4 6 9 3 0 9 ) ，弓= ( 1 8 ，3 6 6 9 6 1 ) 可用程序a d d p i o n t 求出 只+ ，丑+ b 及2 e , 。 a d d p i o n t ( 2 421 5 4 6 9 3 0 9 ，l ，1 5 4 6 9 3 1 3 ) ； 7 海南师范大学硕十学 口论文 a d d p i o n t ( 2 ，4 ，1 8 ，3 6 6 9 6 1 ，1 ，1 5 4 6 9 3 1 3 ) ； 【9 1 9 7 3 4 4 0 ，1 2 8 4 6 5 9 1 】 a d d p i o n t ( 2 ，4 ，2 ，4 ，】，15 4 6 9 3 13 ) ； 【5 5 5 9 2 8 3 ，6 3 4 4 8 5 即日+ 只= ，只+ 与= ( 9 1 9 7 3 4 4 0 ，1 2 8 4 6 5 9 1 ) ，2 e , = ( 5 5 5 9 2 8 3 ，6 3 4 4 8 5 ) 。 程序s c a l a r p r o d u c t p 】 设e 上点只= ( x ；，y ) ，其阶为 ，则2 e ，3 p , ，一2 ) 鼻的横坐标都不等于x 。且对仃 意t “2 ，”一1 1 ，都有嵋= ( r 1 ) 只+ 只。 因此，根据加法公式( 2 2 1 ) 可用m 印1 e 的f o r 循环结构求嵋( 数乘运算) ，程序如下： s c a l a r p r o d u c t ：= p r o c ( t ，x _ l ，y l ，a ，p ) l o c a li , k - i ，k i ，y i ，q ； f o r if r o m2 t o t d o i f i = 2 t h e n k - i ：= ( 3 + x _ l “2 + a ) ( 2 y - 1 ) m o dp ； x 一( 2 ) ：= ( k _ i 2 2 x 1 ) m o d p ； y - ( 2 ) ：= k _ i ( x _ l 一) - ( 2 ) ) - ) ，- lm o dp ； e l s ek i ：= ( y j i 一1 ) - y j i ) ) ，( x _ ( i - 1 ) - x 一1 ) m o dp ； x _ ( i ) ：= k _ i “2 - x j i 一1 ) 一x _ lm o dp ； y _ ( i ) ：= k - j + ( x _ 1 - x 一( i ) ) 一y _ lm o dp ； f i ；q ：= f x 一( i ) y _ ( j ) 1 ；o d ；q ；e n d ； 说明：如果输入的数，输出为 e r r o r , ( i ns c a l a r p r o d u c t ) n u m e r i ce x c e p t i o n ：d i v i s i o nb yz e r o 则表示输入的数字f 开( 其中”等于只点的阶数) 。若输入f 0 时有正确的输出，而输入r 0 + l 时，输出为上面的显示，则表示片点的阶为岛+ l 。 例2 2 2 对有限域e l 上的e ：y 2 = x 3 + 2 x + 4 ，由程序c o o r d i n a t e 可求出e 卜的所 有有理点 c o ，( o ，2 ) ，( o ，9 ) ，( 2 ，4 ) ，( 2 ，7 ) ，( 3 ，2 ) ，( 3 ，9 ) ，( 6 ，1 ) ，( 6 ，l o ) ，( 7 ，3 ) ，( 7 ，8 ) ，( 8 ，2 ) ， ( 8 ，9 ) ，( 1 0 ，1 ) ，( 1 0 ，1 0 ) 即# ( 正i ) = 1 7 为素数。e 上除。点之外的点，其阶均为1 7 ；亦即除o o 之外的点都是 第二章超椭圆曲线的基本理论 以厩i ) 的生成元。若p = ( o 2 ) ，求7 p ，1 6 p , 1 7 p 可用程序s c a l a r p r o d u c t 实现： s c a l a r p r o d u c t ( ? ，0 , 2 ，2 ，1 1 ) ； 【2 ，4 】 s c a l a r p r o d u c t ( 1 6 022 ，1 1 ) ； 【o ，9 】 s c a l a r p r o o u c t ( 1 7 ，0 , 2 ，2 ，1 1 ) ； e r r o r , ( i ns c a l a r p r o d u c t ) n u m e r i ce x c e p t i o n ：d i v i s i o nb yz e r o 即7 p = ( 2 ，4 ) ，1 6 p = ( o ，9 ) ，1 7 p = 。 程序0 r d r 4 l 我们知道：若e 上点片= ( ，m ) ，其阶为押，贝f j 2 7 , ，3 7 1 ，一2 ) 只的横坐标都不等丁 玉，且加一j 溜的横坐标等于西。因此程序s c a l a p r o d u c t 稍加修改就可以求基点墨= “，咒) 的阶数( 命名为程序0 r d ) 。 o r d ：= p r o c ( x1 , 3 1 ，a p ) l o c a li ，k - i ，x i , y _ i ； i ：= 2 ： w h i l ex j i 1 ) k ld o i f i = 2 t h e n k _ i ：= ( 3 x l 2 + a ) ( 2 y - 1 ) m o op ； x - ( 2 ) ：2 ( k - i 2 - 2 + x1 ) m o op ； y - e l s e k - i ：吣，_ ( - 1 ) 一y i ( 1 ) ) ( x - ( i - 1 ) - x1 ) m o o p ； x j j ) ：= ki 2 - x j i - 1 ) - x _ lm o o “ y j i ) ：= k - i + ( x l x j i ) ) 一y - lm o op ； f i ；i ：= i + l ；0 d ；i ；e n d ； 比如；对于例2 。2 。2 中的基点露= ( o ，2 ) ， 0 r d ( 0 ，2 ，2 ，1 1 ) ： 1 7 即露= ( o 2 ) 的阶为1 7 。同样对于例2 2 1 中的最= ( 2 ，4 ) ；则 9 海南师范大学硕士学位论文 o r d ( 2 ，4 ，l ，1 5 4 6 9 3 1 3 ) ； 5 1 5 6 7 7 即最= ( 2 ，4 ) 的阶) b 5 1 5 6 7 7 。 本文介绍m e n o z e s v a n s t o n e 于1 9 9 3 年提出的椭圆曲线密码方案 3 9 。设用户a 选择方 程( 2 2 1 ) 确定的椭圆曲线占，选择基点尸= ( x o ，) 的阶为”( 大整数) ，且e 的循环子群 上的离散对数问题是困难问题。然后选择私钥女【1 ，n 一1 】，计算q = k p = ( b r ，b 2 ) ， 把e ，p ，q 作为公钥公开。加、解密算法如下： 加密算法：设用户b 把明文m = ( x ，y ) e b 发送给用户a ，那么用户b ： ( 1 ) 找到用户a 的公钥e ，p ，o 。 ( 2 ) 随机选择f 1 ，”一1 】，计算：t q = ( z l ，w 2 ) ，y j = z 2 x m o d p ，y 2 = w 2 y m o d p ， 乃= t p m o d p ( 3 ) m 的密文为( m ，y 2 ，乃) 。 解密算法：设用户a 收到用户b 的密文，儿，乃) ，那么用户a ( 1 ) 计算- = ( z ；，嵋) 。 ( 2 ) 计算x 7 = m ( 乏) 一m o d p ，y t = 儿( 嵋) - 。m o d p 。 ( 3 ) 恢复出明文为m = ( x ，y ) 。 程序e n c r y p t ”1 在加密、解密中，最关键的是数乘运算的实现。前面已介绍了程序s c a l a r p r o d u c t ，因 此可以用m a p l e 实现加密。设明文m = ( x ，y ) ，基点p = ( x o ，) ，公钥q = k p = ( a ，b o ，h j m a p l e 实现加密，程序如下： e n c r y p t ：= p r o c ( t ，x ，y ，x _ o ，y _ o ，k l ，b _ 2 ，a ，p ) l o c a li ，j ，k - i ，t j ，y 1 ，y _ 2 ，y3 ，q ； f o r j f r o m2 t o td o i f j = 2t h e nt _ j ：= ( 3 b - l “2 + a ) “2 + b _ 2 ) m o dp ； z _ ( 2 ) ：= ( t _ j 2 2 + b _ 1 ) m o dp ； w 一( 2 ) ：= t _ i + ( b 一1 一z _ ( 2 ) ) 一b _ 2m o dp ； 1 0 第二章超椭圆曲线的基本理论 e l s et j ：= ( w - _ 0 一1 ) 一b _ 2 ) ( z ( j - 1 ) b _ 1 ) m o dp ； 互- o ) ：2 t j “2 一z _ o 1 ) - b - lm o dp ； w - ( i ) ：= t j + ( b - 1 z _ 0 ”一b - 2m o dp ； f i ；y _ l ：= ( 2 i _ 0 ) ) xm o d p ；y 一2 ：= ( w 一( j ”+ ym o d p ；o d ； f o r i f r o m 2 t o t d o i fi = 2t h e nk _ i ：= ( 3 + x _ o 2 + a ) l ( 2 + y0 ) m o d p ； c - ( 2 ) ：= ( k _ i 2 2 + x o ) r o o dp ； d - ( 2 ) ：= k _ i + ( x - 呐- - ( 2 y _ om o dp ； e l s eki ：= ( d _ ( i 1 ) - y - o ) ( c j i 1 ) 一xo ) m o d p ； 9 - ( i ) ：= 叠一i 2 - c ( i - 1 ) - xo m o d p ； d - ( i ) ：= k i ( x _ o c - ( i ) ) - y _ or o o dp ； f i ；y _ 3 ：= 【c j i ) ，d _ ( i ) 】；o d ； q ：= 【y _ l ，y 3 ，y _ 3 】；q ；e n d ； 说明：输入的参数中t 为加密时随机选择的整数，口为式( 2 2 1 ) 中工的系数。 例2 2 3设椭圆曲线e 是有限域k = e ( p = 4 1 5 1 4 2 2 6 3 ) 上方程y 2 = + x + 6 确 定的。用户a 选择的基点p = ( 2 ，4 ) ( 其中o r d ( p 产5 1 5 6 7 7 为素数) ，私钥k = 2 7 5 2 1 ，则用程 序s c a l a r p r o d u c t 口- 求公钥q = k p = ( 2 9 1 1 2 3 1 6 9 ，1 4 7 3 6 8 7 6 7 ) ，用户b 的明文消息m = ( 9 1 ) ， 随机选择整数，= 1 2 8 9 利用e n c r y p t 程序可得 e n c r y p t ( 1 2 8 9 ，9 , 1 ，2 ，4 ，2 9 11 2 3 1 6 9 ，1 4 7 3 6 8 7 6 7 ，l ，4 1 5 1 4 2 2 6 3 ) ； f 1 5 9 3 7 5 5 4 8 ，3 8 5 7 5 6 3 ，【1 7 7 9 4 1 8 0 3 ，2 3 0 9 0 5 0 6 2 即选择整数t = 1 2 8 9 时，m = ( 9 ，1 ) 的密文为 ( 1 5 9 3 7 5 5 4 8 ，3 8 5 7 5 6 3 ，( 1 7 7 9 4 1 8 0 3 ，2 3 0 9 0 5 0 6 2 ) ) 。 程序d e c r y p t i ” 若用户a 收到的密文为o ，。，儿，乃) ，其中乃；( ，) 。找出私钥i = 2 7 5 2 1 用m 印l e 实 现解密，程序如下： d e c r y p t ：= p r o c ( k ，y _ l ，y _ 2 ，z _ o ，w _ o ，a ，p ) l o c a li ，t _ i ，x ，y ，q ： f o rif r o m2t okd o i fi = 2t h e nti ：= ( 3 * zo 2 + a ) ( 2 , w 一0 ) m o dp ： 1 1 塑妻墅垫查兰堡! ：兰生丝苎 z 一( 2 ) ：= ( t _ i 4 2 - 2 z _ 0 ) m o dp ： w 一( 2 ) ：= t i ( z _ o z 一( 2 ) ) 一wom o dp ： e l s et _ i ：= ( l ( 卜1 ) 一w _ o ) ( z 一( i 一1 ) 一z _ o ) m o dp ： z 一( i ) ：= t i 2 - z 一( i 一1 ) 一z _ o m o dp ： w - ( i ) ：一j $ ( z _ o 一一( i ) ) 一w _ om o dp ： f i ：x ：= y i ( z 一( i ) ) m o dp ：y ：= y 一2 ( w 一( i ) ) m o dp ：o d ； q ：= x ，y ：0 ：e n d ： 比如解密例2 2 3 中密文：( 3 9 5 2 8 5 1 ，1 3 0 0 4 9 9 7 ，( 7 6 4 3 6 9 7 ，9 7 5 0 8 8 5 ) ) 。用户a 找出私钥 k = 2 7 5 2 l ，然后运行： d e c r y p t ( 2 7 5 2 1 ，1 5 9 3 7 5 5 4 8 ，3 8 5 7 5 6 3 ，1 7 7 9 4 1 8 0 3 ，2 3 0 9 0 5 0 6 2 ，1 ，4 1 5 1 4 2 2 6 3 ) ； 9 ，i 】 即锯密密文( 3 9 5 2 8 5 1 ，1 3 0 0 4 9 9 7 ，( 7 6 4 3 6 9 7 ，9 7 5 0 8 8 5 ) ) 恢复出明文是( 9 ，1 ) 。 2 3 超椭圆曲线 对于本节中的相关定理，其证明我们省去，详见文献 2 0 。 定义2 3 1设k 是一个域，露为彭的代数闭域。则域k 上亏格为g ( g 1 ) 的超椭 圆曲线c 是由下面的方程确定的曲线： c ：y 2 + 矗( y = ( 功 ( 2 3 1 ) 其中 ( x ) k f 】是次数最大为g 的多项式，f ( x ) e k x 】是首项系数为1 的，次数为 2 9 + 1 的多项式，并且不存在点p = ( x ，) k x k 一，同时满足方程( 2 3 i ) 及偏导数方程 2 y + ( x ) = 0 ， ( x ) y = f7 ( x ) 。 若存在点p = ( 工，) k x k 一，同时满足方程( 2 3 1 ) 及偏导数方程2 y + 矗( x ) = o ， 矗( x ) y = f ( j ) ，则称p 为c 的奇异点 f ：= p r o c ( y ) l o c a lx ，yx ： f o rxf r o m0t o6d o y _ x ：= m s o l v e ( y - 2 + x + y = x 5 + 5 x 4 + 6 x 2 + x + 3 ，7 ) ： p r i n t ( x ，yx ) e n dd o ： e n d ： 我们输入 f ( y