《椭圆曲线超优对的研究与实现》由会员分享，可在线阅读，更多相关《椭圆曲线超优对的研究与实现（68页珍藏版）》请在金锄头文库上搜索。
1、中山大学 硕士学位论文 椭圆曲线超优对的研究与实现 姓名：林锐斌 申请学位级别：硕士 专业：计算机应用技术 指导教师：陈晓峰;张方国 20100607 中山大学硕士学位论文椭圆曲线超优对的研究与实现 论文题目：椭圆曲线超优对的研究与实现 专业：计算机应用技术 硕士生：林锐斌 指导教师：陈晓峰副教授张方国教授 摘要 双线性对是近几年发展起来的用来构造密码协议的一个重要工具。基于双线 性对的特殊性质，诸多有趣的密码协议被构造出来。这些协议利用其他基本数学 工具是难以构造的。实现这些密码协议的有效性取决于双线性对的计算效率。为 了提高双线性对的计算效率，减少M i l l e r 链所需要的迭代次数
2、是最重要的方法之 一。超优对是一种双线性对，其M i l l e r 链所需要的迭代次数是目前最少的一种。 本文研究了超优对的原理及其实现，主要的研究成果包括： ( 1 ) 对两种基于椭圆曲线构造的双线性对T a t e 对和广义A t e 对进行了系统的 整理，详细讨论了构造这两类双线性对所需的条件，以及用于计算双线性对的 M i l l e r 算法； ( 2 ) 重点讨论了超优对的实现。结合双线性对T a t e 对和广义A t e 对，利用椭 圆曲线上的非平凡自同构给出了两类超优对的构造，并给出实际例子说明其有效 计算性： ( 3 ) 编写代码实现双线性对T a t e 对、广义A t
3、 e 对以及上述两类超优对的计算， 通过实际统计数据比较超优对与T a t e 对、广义A t e 对的计算效率，从而更有力 地说明超优对的计算效率优于T a t e 对、广义A t e 。 关键字：椭圆曲线，M i l l e r 算法，非平凡子同构，超优对 中山大学硕士学位论文 椭圆曲线超优对的研究与实现 T i t l e ：R e s e a r c ho nS u p e r - o p t i m a lP a i r i n g so fE l l i p t i cC u r v e sa n dI m p l e m e n t M a j o r ：C o m p u t
4、e rA p p l i c a t i o nT e c h n o l o g y N a m e ：L i nR u i b i n S u p e r v i s o r ：A s s o c i a t eP r o f e s s o rC h e nX i a o f e n g ，P r o f e s s o rZ h a n gF a n g g u o A b s t r a c t B i l i n e a rP a i r i n g sa l eo n eo ft h em o s ti m p o r t a n tt o o l sf o rc o n s t
5、 r u c t i o no f c r y p t o g r a p h i cp r o t o c o l si nr e c e n ty e a r s M a n yi n t e r e s t i n gc r y p t o g r a p h i cp r o t o c o l s b a s e do np a i r i n g sh a v eb e e np r o p o s e d ，w h i c hc a n n o tb ea c h i e v e du s i n go t h e r m a t h e m a t i c a l p r i
6、m i t i v e s T h ee f f i c i e n c y o fi m p l e m e n t i n gt h e s ep r o t o c o l si s d e t e r m i n e db yt h ee f f i c i e n c yo fp a i r i n gc o n p u t a t i o n s A n do n eo fm o s ti m p o r t a n t m e t h o d st oi m p r o v et h ee f f i c i e n c yo fp a i r i n gc o n p u t
7、a t i o n si st or e d u c et h el e n g t ho f M i l l e rl o o p S u p e r - o p t i m a lb i l i n e a rp a i r i n g sa r eo n eo ft h ep a i r i n g sw h i c hh a v et h e l e a s tl e n g t hS Of a r W ef o c u so nt h et h e o r ya n di m p l e m e n to fs u p e r - o p t i m a lb i l i n e a
8、 rp a i r i n g s ，a n d t h em a i nr e s u l t sa r el i s t e da sf o l l o w s ： F i r s t l y ，t h i sp a p e rs u n q t m a r i z e st h et h e o r yo ft w ok i n d so fb i l i n e a rp a i r i n g sb a s e d o ne l l i p t i cc u r v e s ：T a r ep a i r i n ga n dg e n e r a l i z e dA t ep a
9、 i r i n g W ed i s c u s sc o n d i t i o n s f o rc o n s t r u c t i n gT a t ep a i r i n ga n dg e n e r a l i z e dA t ep a i r i n g ，a n di n t r o d u c et h eM i l l e r a l g o r i t h mw h i c hi su s e dt oi m p l e m e n tt h ep a i r i n g s S e c o n d l y ，t h em o s ti m p o r t a
10、n tr e s u l to ft h i sp a p e r ，w ep r o p o s et w ok i n d so f s u p e r - o p t i m a lb i l i n e a rp a i r i n g sb a s e do nT a t ep a i r i n g ，g e n e r a l i z e dA t ep a i r i n ga n d e f f i c i e n te n d o m o r p h i s m so ne l l i p t i cc u r v e s E x a m p l ei sa l s og
11、i v e nf o re x p l a i nt h e i r e f f i c i e n tc o m p u t a t i o n W h a t Sm o r e ，ap r o g r a mi sw r i t t e nf o rc o m p u t i n gT a t ep a i r i n g ，g e n e r a l i z e dA t e p a i r i n ga n dt h e s et w os u p e r - o p t i m a lb i l i n e a rp a i r i n g s W i t hr e s u l to
12、 ft h ep r o g r a m ，a c o n c l u s i o ni sg i v e nt h a tt h ee f f i c i e n c yo fc o m p u t i n gs u p e r - o p t i m a lb i l i n e a rp a i r i n g s i sb e t t e rt h a nt h a to fT a t ep a i r i n ga n dg e n e r a l i z e dA t ep a i r i n g K e yW o r d s ：E l l i p t i cC u r v e ，
13、M i l l e rA l g o r i t h m , e n d o m o r p h i s m s ，S u p e r - o p t i m a l B i l i n e a rP a i r i n g I I 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名 日期：矽，口年多月 学位论文使用授权声明 本人完全了
14、解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者虢研玩纸 日期：哞多月7 日 习汨 F广、 前月 旅吖 名驯 鹕 渺 【b C E师期 m b r T _ r 中山大学硕士学位论文椭圆曲线超优对的研究与实现 第1 章绪论 1 1 研究背景与意义 随着计算机科学、通信和网络技术的迅速发展，人们为了更好的利用丰富 的网络资源，开始尝试把一些现
15、实中如付款、投票、签名等习以为常的行为在 网络上实现，从而发展出网上付款、网络投票和数字签名等需要在网络上进行 信息传输的工具。然而，我们在利用网络进行创新和实现繁荣的同时，也遇到 了严竣的、不可忽视的信息安全问题。公钥密码学正是应这种需求而产生的。 公钥密码学起源于1 9 7 6 年D i f f i e 和H e l l m a n 发表的著名论文密码学的新 方向【。文献中证明了两个相距遥远的用户在没有秘密安全信道，并且彼此 不需要预先见面的情况下能达成一个公共的密钥，使发方和收方之间不需要传 递密钥的情况下进行保密通信。该论文在密码学中掀起一场变革。 受D i 伍e 和H e l l m
16、 a n 的启迪，各种公钥密码体制的实现方案不断被提出。 R i v e s t 、S h a m i r 和A d l e m a n 于1 9 7 8 年提出了第一个公开的公钥密码体制【2 1 ( 基 于大数分解问题的R S A 密码体制) ，并且给出了第一个数字签名算法，成功地 让现实生活中的签名能够电子化、网络化。自此，公钥密码学在近三十多年中 取得了蓬勃发剧3 1 。 1 9 8 5 年，K o b l i t z t 4 1 和M i l l e r 5 1 分别提出基于椭圆曲线离散对数问题的公钥 密码体制，它是用椭圆曲线中的有限群代替基于有限域上离散对数问题公钥密 码中的有限循环群所得到的一类密码体制。椭圆曲线密码学的诱人之处在于安 全性相同的前提下，可使用较短的密钥。椭圆曲线密码学是公钥密码学中的一 大热门领域，且在公钥密码学的各方面都有着重要的应用前景【6 一。 近年来基于椭圆曲线构造的双线性对在公钥密码学中有着重要的应用。 19 9 4 年，M e n e z e s ，O k a m o t o 与V a n s
