（计算数学专业论文）基于ecc快速算法及签名方案的研究.pdf

摘 要 本文给出e c c快速算法中计算标量乘法方面的两个改进算法，讨论了椭圆 曲线数字签名算法并进行实现和测试分析，随后对其验证算法进行较好的改进; 最后提出一种在椭圆曲 线上实现的基于消息 恢复的数字签名的新方案。 论文主要 内容安排如下: 第一章， 论述椭圆曲 线密码的研究现状。 第二章， 介绍有限域的表示， 椭圆曲线 ( e c )上点运算的基本概念，将一 些常见的公钥算法平行推广到椭圆曲线上，随后介绍了一套椭圆曲线公钥密码 ( e c c ) 的实现示例， 最后介绍了e c c中的 系统参数选取。 第 三 章 ，首 先 介 绍 利 用。 n h 来 加 快 基 域f 2 . 上 域 元 素 的 运 算 ; 随 后 讨 论 了 常见的主要快速标量乘法， 对其中的两个算法做出进一步讨论和改进: 一个利用 直接加倍的方 法来改 进k - u y 方法， 从而使得重复倍点 运算速度得到提高; 另一 个方法是利用滑动窗口 技术对n a f 方法的改进， 并给出窗口w = 4 时的试验， 对 比与其它方法的优劣。 第四章，结合前面的知识， 详细分 析并具体实现了 e c d s a算法:利用对 m o n t o g o m e r y方法的改 进来同时 计算两个标量乘法之和， 给出 一个新的 验证算 法并 给出 证明; 接下一节中， 在t s e n g 的 签名方案的启发 下， 提出一 种在椭圆曲 线上实现的基于消息恢复的数字签名的 新方案， 该方案恢复 信息同时又具备认证 功能， 并在此基础上提出了两个扩展方案: 一个有认证加密功能; 另一个是在处 理大信息时的推广。 最后， 在第五章给出本文的工作总结。 关键词:椭圆曲 线公 钥密 码， 有限 域，离 散 对数问 题， 标量乘法， 椭圆曲 线数字签名 信息恢复，认证加密 ab s t r a c t i n t h i s d i s s e rt a t i o n , w e p r e s e n t e d t w o i m p r o v e d a l g o r i t h m s w h i c h c a n c a l c u l a t e s c a l a r m u lt i p l i c a t i o n o n e l l i p t i c c u r v e . t h e n , w e a n a l y z e t h e d i g i t a l s i g n a t u r e a l g o r i t h m o f e l l i p t i c a n d i m p l e m e n t t h i s a l g o r i t h m s i m u l t a n e o u s l y . o n s e c o n d t h o u g h t s , w e o b t a i n e d s o m e c o n c l u s i o n s b y i n v e s t i g a t i n g t h e a l g o r i t h m . f i n a l l y , w e d e s i g n a n e w s i g n a t u r e s c h e m e w i t h m e s s a g e r e c o v e r y b a s e d o n e l l i p t i c c u r v e . t h e ma i n c o n t e n t s o f t h e d i s s e rt a t i o n a r e a s f o l l o ws : c h a p t e r o n e s u m m a r iz e s c u r r e n t s it u a t i o n s o f e l l ip t i c c u r v e c ry p t o l o g y . c h a p t e r t w o i n t r o d u c e s r e p r e s e n t a t i o n o f f i n it e f i e l d a n d c o n c e p t o f p o in t o p e r a t i o n o n e l l i p t i c c u r v e ， e x t e n d s s o m e p o p u l a r p u b l i c k e y c ry p t o s y s t e m t o e l l ip t i c c u r v e c ry p t o s y s t e m , a n d g i v e a n e x a m p l e a b o u t e l l i p t i c c u r v e p u b l i c k e y c i p h e r a l g o r i t h m . f i n a l ly , w e s t a t e s t h a t c h o o s i n g a n a p p r o p r i a t e p a r a m e t e r i n e l l ip t i c c u r v e p u b l i c k e y c ry p t o s y s t e m . c h a p t e r th r e e s t u d i e s a r it h m e t ic o p e r a t io n s o v e r f i n it e f i e l d凡 。 u s in g o n b ( o p t i m a l n o r m a l b a s e s ) a n d d i s c u s s s o m e m a j o r f a s t s c a l a r m u l t i p l i c a t i o n a l g o r i t h m s . t h e i m m e d i a t e p o i n t d o u b l i n g m e t h o d i s u s e d t o i m p r o v e k - a ry a l g o r i t h m a n d t h e s p e e d o f c o m p u t i n g t h e r e p e a t e d p o i n t d o u b l i n g c a n b e q u i c k e n . mo r e o v e r , t h e o p t i m i z i n g t e c h n iq u e s w h i c h a d o p t s l id i n g - w i n d o w i s a p p l i e d i n n a f a l g o r i t h m . w h e n t h e w i n d o w s w i d t h i s 4 , e x p e r i m e n t a t i o n a b o u t t h i s i m p r o v e d a l g o r i t h m w a s i m p l e m e n t e ff ic i e n t l y . b a s e d o n a b o v e c o n c l u s i o n s , c h a p t e r f o u r a n a l y z e s t h e d i g i t a l s i g n a t u r e a l g o r i t h m o f e l l i p t i c a n d i m p l e m e n t t h i s a l g o r i t h m场c o m p u t e r t e s t i n g s i m u l t a n e o u s l y . l a t e r , t h e a r ti c l e p r e s e n t s a n n e w c o m p u t a t i o n a l m e t h o d b a s e d o n mo n t g o m e r y m e t h o d w h i c h w a s d e v e l o p e d t o r e d u c e t h e c o m p u t a t i o n s f o r k p + 1 q i n v e r i f i c a t i o n p r o c e s s o f e c d s a. i n t h en e x t s e c t i o n , e l l i p t i c c u r v e w e d e s i g n e d a n e w s i g n a t u r e s c h e m e w i t h r e c o v e ry b a s e d o n t h i sh a d a p r o p e rt y t h a t t h e s i g n e r s k e y c a n s im u l t a n e o u s l y b e a u t h e n t i c a t e d i n v e r i f y i n g t h e s i g n a t u r e . mo r e o v e r , w e a l s o p r e s e n t t w o v a r i a n t s a b o u t t h e s c h e m e: o n e i s a n a u t h e n t i c a t e d e n c r y p t i o n s c h e m e t h a t o n l y a l l o w s a s p e c i f i e d r e c e i v e r t o v e r i f y a n d r e c o v e r t h e m e s s a g e ， t h e o t h e r i s e x t e n s i o n b a s e d o n t h e s e c o n d s c h e m e w h i c h c a n d e a l w i t h t h e l a r g e m e s s a g e c o mmu n i c a t i o n . c h a p t e r f i v e c o n c l u d e s t h e w o r k i n t h i s d i s s e r ta t i o n . k e y w o r d s : e l l i p t i c c u r v e p u b l i c k e y c r y p t o s y s t e m , fi n i t e f i e l d , d i s c r e t e l o g a r i t h m p r o b le m， s c a l a r m u l t i p l i c a t i o n , e l l i p t i c c u r v e d i g i t a l s i g n a t u r e , m e s s a g e w it h r e c o v e r y , a u t h e n t i c a t e d e n c r y p t i o n i i i 西北工业大学硕士学位论文 第一章 绪 论 1 . 1 引言 密码作为一种技术源远流长， 古已 有之。 1 9 4 9 年， s h a n n o n 的一篇“ 保密通 信的信息理论” 开创了现代密码学的先河， 使得密码学有了突飞猛进的发展。 随 着计算机科学的迅速发展和信息时代的到来，现代密码学的应用范围已 经从狭义 的 通信保密理论发展为包含了 诸如防篡改技术、防假冒 技术、安全协议的 制订、 身份验证、电子签名、 电子货币以及秘密分享方案等多方面内容的枝繁叶茂的学 科庄金融、财贸等领域有重要的应用。 密码体制分对称密码体制 ( 单钥) 和公钥密码体制 ( 双钥) 。 对称加密是指 在信息加密过程中， 对信息的加密和解密都使用相同的密钥。 交易双方的任何信 息都通过这把密钥加密后传给对方。 这种体制的缺点就是通信的秘密依 赖于双方 的相互信任， 当一个实体和很多实体进行通信时， 要维护大量的秘密密钥。 1 9 7 6 年， d i ff i e与h e l l m a n i ll 提出了 适用于网 络上 保密通信的 公钥密 码思 想: 在加密 过程中， 密钥被分为一对。 这对密钥中的任何一把密钥都可以作为公开密钥通过 非保密方式向 他人公开， 而另一把则作为私有密钥加以 保存。 这对密钥具有这样 两个特点: 其一， 当知道密钥对中的一个密钥时， 要检测出另一个密钥， 计算上 是不可实现的; 其二， 一个密钥用于对信息的加密， 相应的另一个密钥则用于对 加密信息的解密。通信的双方只要彼此知道对方的公钥，即可建立安全的 通信。 因此， 克服了 对称密码体制中的 两点不足。 目 前比 较流行的公钥密码体制主要有三类: 1 . 基于大 整数因 子 分解问 题 ( i f p ) 的 公 钥密 码体制。 这类公 钥密码 体制以 r s a为 代表。 r s a是由r v ie s t ,s h a m ir 和a d le m a n 2 1于1 9 7 7 年 提出 的， 是目 前 应 用最广泛的公钥密码体制。 2 .基于有限域离散对数问题 ( d l p )的公钥密码体制。这一类中最著名的 算法是美国国家标准局 ( n i s t ) 于1 9 9 4 年通过的数字签名标准 ( d s s )中使用 的 签名算法d s a ( d i g i t a l s i g n a t u r e a l g o r it h m ) . 3 基于有限域椭圆曲 线离散对数问 题 ( f c d l p ) 的密码体制。 1 9 8 5 年n e i l 西北工业大学硕士学位论文 第一章 绪 论 1 . 1 引言 密码作为一种技术源远流长， 古已 有之。 1 9 4 9 年， s h a n n o n 的一篇“ 保密通 信的信息理论” 开创了现代密码学的先河， 使得密码学有了突飞猛进的发展。 随 着计算机科学的迅速发展和信息时代的到来，现代密码学的应用范围已 经从狭义 的 通信保密理论发展为包含了 诸如防篡改技术、防假冒 技术、安全协议的 制订、 身份验证、电子签名、 电子货币以及秘密分享方案等多方面内容的枝繁叶茂的学 科庄金融、财贸等领域有重要的应用。 密码体制分对称密码体制 ( 单钥) 和公钥密码体制 ( 双钥) 。 对称加密是指 在信息加密过程中， 对信息的加密和解密都使用相同的密钥。 交易双方的任何信 息都通过这把密钥加密后传给对方。 这种体制的缺点就是通信的秘密依 赖于双方 的相互信任， 当一个实体和很多实体进行通信时， 要维护大量的秘密密钥。 1 9 7 6 年， d i ff i e与h e l l m a n i ll 提出了 适用于网 络上 保密通信的 公钥密 码思 想: 在加密 过程中， 密钥被分为一对。 这对密钥中的任何一把密钥都可以作为公开密钥通过 非保密方式向 他人公开， 而另一把则作为私有密钥加以 保存。 这对密钥具有这样 两个特点: 其一， 当知道密钥对中的一个密钥时， 要检测出另一个密钥， 计算上 是不可实现的; 其二， 一个密钥用于对信息的加密， 相应的另一个密钥则用于对 加密信息的解密。通信的双方只要彼此知道对方的公钥，即可建立安全的 通信。 因此， 克服了 对称密码体制中的 两点不足。 目 前比 较流行的公钥密码体制主要有三类: 1 . 基于大 整数因 子 分解问 题 ( i f p ) 的 公 钥密 码体制。 这类公 钥密码 体制以 r s a为 代表。 r s a是由r v ie s t ,s h a m ir 和a d le m a n 2 1于1 9 7 7 年 提出 的， 是目 前 应 用最广泛的公钥密码体制。 2 .基于有限域离散对数问题 ( d l p )的公钥密码体制。这一类中最著名的 算法是美国国家标准局 ( n i s t ) 于1 9 9 4 年通过的数字签名标准 ( d s s )中使用 的 签名算法d s a ( d i g i t a l s i g n a t u r e a l g o r it h m ) . 3 基于有限域椭圆曲 线离散对数问 题 ( f c d l p ) 的密码体制。 1 9 8 5 年n e i l 西北工业大学硕士学位论文 k o b l it z l l , v i c t o r m u l le r l4 1将 椭 圆 曲 线 应 用 到 密 码 学 中 ， 这 就 是 椭圆曲 线 上 的 密 码 体 制 e c c ( e l l ip ti c c u r v e c r y p t o s y s t e m ) . 经典的r s a , d s a , e l g a t n a 1 15 1 等公 钥密 码体 制的 密钥长 度一般为1 0 2 4 b i t . 但是， 随着密码理论研究的深入和计算机技术的飞速发展， 这一密钥长度已变得 越来越不安全了。e c c相对于经典公钥在算法效率上取得了突破性进展。椭圆 曲线加密方法与现行公用r s a方法相比，有以下优点: ( 1 )安全性能更高。 e c c和其他几种公钥系统相比， 其抗攻击性具有绝 对的优势。如 1 6 0位 e c c与 1 0 2 4 位r s a , d s a有相同的安全强度。而 2 1 0 位e c c则与2 0 4 8 b i t r s a , d s a具有相同的安全强度。 ( 2 ) 计算量小， 处理速度快。 由于e c c密钥操作长度相对小的缘故， e c c 加解密速度比r s a , d s a要快得多。 ( 3 ) 存储空间占 用小。 e c c的密钥尺寸和系统参数与r s a , d s a相比 要 小得多，意味着它所占的存贮空间要小得多。 这对于加密算法在i c卡上的应用 具有特别重要的意义。 ( 4 )带宽要求低。 当对长消息进行加解密时，三类密码系统有相同的带 宽要求， 但应用于短消息时e c c带宽要求却低得多。 而公钥加密系统多用于短 消息， 例如用于数字签名和用于对对称系统的会话密钥传递。 带宽要求低使e c c 在无线网络领域具有广泛的应用前景。 f c c是当今最好的一种数学公钥密码体系。由于 r s a的专利权己经失效， e c c的这些特点使它必将取代 r s a ，成为通用的公钥加密算法。比如一些工业 制造厂家 如爱立信、摩托罗拉等)已 经开始把 e c c技术应用到移动电话、i c 卡芯片上。s e t协议的制定者已 把它作为下一代s e t协议中缺省的公钥密码算 法。 关于e c c 的相应工业标准也己 经制定出来， 主要有i e e e p 1 3 6 3 , a n s i x 9 . 6 2 和a n s i x 9 . 6 3 。 所以 关于e c c 方方面面的 研究是大家共同的 热点。 1 .2 研究现状 十几 年来关于椭圆曲 线密码的 各类研究成果层出不穷。 总结起来其研究主要 有以下四个方面。 一、椭圆曲线密码的安全性 安全性是任何一个密码体制的核心问 题。 e c c是建立在求椭圆曲 线离散对 西北工业大学硕士学位论文 k o b l it z l l , v i c t o r m u l le r l4 1将 椭 圆 曲 线 应 用 到 密 码 学 中 ， 这 就 是 椭圆曲 线 上 的 密 码 体 制 e c c ( e l l ip ti c c u r v e c r y p t o s y s t e m ) . 经典的r s a , d s a , e l g a t n a 1 15 1 等公 钥密 码体 制的 密钥长 度一般为1 0 2 4 b i t . 但是， 随着密码理论研究的深入和计算机技术的飞速发展， 这一密钥长度已变得 越来越不安全了。e c c相对于经典公钥在算法效率上取得了突破性进展。椭圆 曲线加密方法与现行公用r s a方法相比，有以下优点: ( 1 )安全性能更高。 e c c和其他几种公钥系统相比， 其抗攻击性具有绝 对的优势。如 1 6 0位 e c c与 1 0 2 4 位r s a , d s a有相同的安全强度。而 2 1 0 位e c c则与2 0 4 8 b i t r s a , d s a具有相同的安全强度。 ( 2 ) 计算量小， 处理速度快。 由于e c c密钥操作长度相对小的缘故， e c c 加解密速度比r s a , d s a要快得多。 ( 3 ) 存储空间占 用小。 e c c的密钥尺寸和系统参数与r s a , d s a相比 要 小得多，意味着它所占的存贮空间要小得多。 这对于加密算法在i c卡上的应用 具有特别重要的意义。 ( 4 )带宽要求低。 当对长消息进行加解密时，三类密码系统有相同的带 宽要求， 但应用于短消息时e c c带宽要求却低得多。 而公钥加密系统多用于短 消息， 例如用于数字签名和用于对对称系统的会话密钥传递。 带宽要求低使e c c 在无线网络领域具有广泛的应用前景。 f c c是当今最好的一种数学公钥密码体系。由于 r s a的专利权己经失效， e c c的这些特点使它必将取代 r s a ，成为通用的公钥加密算法。比如一些工业 制造厂家 如爱立信、摩托罗拉等)已 经开始把 e c c技术应用到移动电话、i c 卡芯片上。s e t协议的制定者已 把它作为下一代s e t协议中缺省的公钥密码算 法。 关于e c c 的相应工业标准也己 经制定出来， 主要有i e e e p 1 3 6 3 , a n s i x 9 . 6 2 和a n s i x 9 . 6 3 。 所以 关于e c c 方方面面的 研究是大家共同的 热点。 1 .2 研究现状 十几 年来关于椭圆曲 线密码的 各类研究成果层出不穷。 总结起来其研究主要 有以下四个方面。 一、椭圆曲线密码的安全性 安全性是任何一个密码体制的核心问 题。 e c c是建立在求椭圆曲 线离散对 西北工业大学硕 f 学位论文 数困 难 ( e c d l p ) 基础之上的 ， 它的 安 全性依 赖于e c d l p 的 安全性。 1 .椭圆曲线上的离散对数问题 简单地讲 代数结构构成 离散对数问题就是乘方过程的求逆。 这个问题可以由各种不同的 最常见的类型有: 有限 域 上 离 散 对 数问 题( d l p ) : 给 定 有限 域凡 和g , h e 凡， 寻 找 一 个 整 数d 使 得 在 代 中 有 g d = h o 椭 圆 曲 线 离 散 对数问 题 ( e c d l p ) : 给 定 定 义 于 有限 域凡 上的 椭圆 曲 线e 和e 上 的 两 点 p , q e e ( 凡 ) i 寻 找 一 个 整 数 d 使 在e ( 凡 ) 上 有d p = q 2 .椭圆曲 线公钥密码的攻击现状 离散对数算法平移而来。 扫 线有限群上离散对数问 题的算法， 都是从一般群g上 而该类离散对 数问 题算 法可分为 两类: i n d e x c a l c u l u s 6 1 目 前， 对于所有椭圆曲 线有限群上离散对数问 题的算法， 都是从一般群 算法和碰撞搜索法. i n d e x c a l c u l u s 算法具有亚指数时间复杂度，是目 前解决一 般群g上离散对数问 题的最好算法， 但对e c d l p ，该算法无论从理论上还是从 实际上看， 都不可行; 碰撞搜索法具有纯指数时间复杂度， 这一类算法可以用于 求 解e c d l p ，目 前 最 好 的 碰 撞 搜 索 法 有: p o l la r d - r h o h l 算 法 和p o h l ig - h e l lm a n t8 i 算法。其中: ( 1 ) p o l ig - h e l lm a n 算 法 。 这 个 方 法 首 先 分 解 点p 的 阶 n ， 的 因 子 ， 那 么 问 题 就 归 约 为 从 1 模 的 n ， 因 子 恢 复 l 的 问 题 ， 这 个 可 由 中 国 剩 余 定 理 解 决 。 据 此 ， 为 了 选 取更困难的e c d l p实例， 必须选取一e c使其阶具有大的素因子或阶是素数。 ( 2 ) p o l l a r d r h o 算 法。 这个 算 法由p o l la r d 提出 ， 是b a b y - s t e p g i a n - s te p 算 法的 随 机 版。 运 行 时 间 为 汀 n n l 2 步 。 但 存 储 空 间 的 需 求 可 以 忽 略 。 随后，对p o l l a r d r h o 算法陆续有更好的改进。 ( 3 ) 并 行p o ll a r d r h o h o l 算 法。 o o r s c h o t 和w ie n e r 提出p o l la r d r h o 算 法 的 并 行 算 法， 在r 如果有 个处理器上运行需要 森 1 2 r 步 ， 也 就 是 加 速了 : 倍。 此 算 法 用 硬 件 来 实 现 : r = 3 3 0 0 0 0 0 个处理器， 那么解决一个n = 2 1 2 0 的e c d l p 大约需要3 2 天。 构 造这样的硬件大约需要1 亿美元。 而a n s i x 9 . 6 2 要求n 2 1 6 0 ， 所以， 以今天的技 西北工业大学硕士学位论文 术进行硬件攻击是不可能成功的。 ( 4 ) p o l la r d l a m e d a p q 算 法。 这 是p o ll a r d r h o 算 法的 另一 种 随 机 性 算 法。 此 算 法也可 并 行执行， 速度比 并 行r h o 算法稍慢。 但是加果已 知 对数值属于 o ,n - 1 的 子 区间 0 ,b , b l . 一 有 限 域f p 的 域 表 示 有 限 域凡由 整 数 集 合 0 , 1 , 2 , . . . p - 1 1 组 成 ， 每 个 这 样 的 整 数 可 以 用 一 个 恰 好 为t 二 l la g 2 p 的 二 进制 表示， 该 表 示由 整 数的 二 进 制 表示 及 在其 左 边 添加 适当 个 数 的0 组 成 f p 中 元 素 具 有 以 下 算 术 运 算 。 加 法 如 果 。 ,b e 凡， 则 。 十 b = r ， 其 中 ; 是 。 + b 被 p 除 所 得 的 剩 余 ， o s r s p - 1 . 乘 法 如 果 。 ,b e 凡， 则 。 -b = s ， 其 中 : 是 “ b 被 p 除 所 得 的 剩 余 ， o s s s p - 1 . 乘法 逆 令f , 表示f , 中 所 有 非 零 元 素的 集 合， 则 可 证明 至少 存 在一 个 元素 g e 凡， 使 得凡中 任 意 非 零 元 素 可以 表 示 成g 的 一 个 方 幕。 这 样的 一 个 元 素g 称 为 凡的 生 成 元 即 凡 一 g : 0 z i s p 一 2 1 , 。 一 扩 e 凡 的 乘 法 逆 是 生 一 : 一 一 : (一 ) (， 一 ) 。 a 二、 有限 域f 2, 域 表示 我 们 利 用 多 项 式 的 加、 乘 、 除 和 剩 余 来 构 造 有 限 域f 2 , 令f ( x ) 二 广十 f . - ,x “ 一 + 十 f x 十 f o ( f e f , 0 s i 二 一 1 ) 是凡 上 次 数 为 m 的 不可约多项式，即f ( x ) 不能分解为f 2 上两个次数小于m的多项式的积。 有限 域 西北工业大学硕士学位论文 第二章:椭圆曲线密码体制 本 章 主 要 介 绍 了 有 限 域 f , 和 f中 域 元 素 的 表 示 和 在 这 两 个 基 域 上 椭 圆 曲 线上点运算的 基本概念， 将两个常见的公钥算法平行推广到椭圆曲 线上， 稍后通 过介 绍了 一 套 椭圆曲 线公 钥 密 码 ( e c c ) 的 实 现 示 例来 说明 它的 应 用， 最后 介绍了 e c c中的系统参数选取。 2 . 1 域元素表示 本 节 将 给 出 有 限 域 乓 的 元 素 表 示 。 其 中 ， r 一 p , p 是 素 数 ， 或 q 二 2 m , m l . 一 有 限 域f p 的 域 表 示 有 限 域凡由 整 数 集 合 0 , 1 , 2 , . . . p - 1 1 组 成 ， 每 个 这 样 的 整 数 可 以 用 一 个 恰 好 为t 二 l la g 2 p 的 二 进制 表示， 该 表 示由 整 数的 二 进 制 表示 及 在其 左 边 添加 适当 个 数 的0 组 成 f p 中 元 素 具 有 以 下 算 术 运 算 。 加 法 如 果 。 ,b e 凡， 则 。 十 b = r ， 其 中 ; 是 。 + b 被 p 除 所 得 的 剩 余 ， o s r s p - 1 . 乘 法 如 果 。 ,b e 凡， 则 。 -b = s ， 其 中 : 是 “ b 被 p 除 所 得 的 剩 余 ， o s s s p - 1 . 乘法 逆 令f , 表示f , 中 所 有 非 零 元 素的 集 合， 则 可 证明 至少 存 在一 个 元素 g e 凡， 使 得凡中 任 意 非 零 元 素 可以 表 示 成g 的 一 个 方 幕。 这 样的 一 个 元 素g 称 为 凡的 生 成 元 即 凡 一 g : 0 z i s p 一 2 1 , 。 一 扩 e 凡 的 乘 法 逆 是 生 一 : 一 一 : (一 ) (， 一 ) 。 a 二、 有限 域f 2, 域 表示 我 们 利 用 多 项 式 的 加、 乘 、 除 和 剩 余 来 构 造 有 限 域f 2 , 令f ( x ) 二 广十 f . - ,x “ 一 + 十 f x 十 f o ( f e f , 0 s i 二 一 1 ) 是凡 上 次 数 为 m 的 不可约多项式，即f ( x ) 不能分解为f 2 上两个次数小于m的多项式的积。 有限 域 西北工业大学硕十学位论文 f , 由 上 f 2 所 有 次 数 小 于 m 的 多 项 式 组 成 ， 即 凡二 am-lx 十 a m - =x - ， 十 二 + a lx 十 a o : a i e 0 ,1 1 域元素( a , - ,x m - + a , - 2 x m - 2 + 二 a ,x + a , ) 通常 用长 度为m的 二进制串( a m - l . - a ,a o ) 表 示 ， 使 得凡二 ( a m - la . - 2 . . . a ,a a ) : a , e 0 , 1 1 1 因 此， f . 中 的 元 素 可以 用所 有 长 度 为m的 二 进 制串 的 集合来 表示。 域元素的加 域加法 、乘运算如下: ( a . - , . . . a , a o ) + ( b m - : 一 叭 ) 二 ( c . _ 1 。 二 c c o ) 其中乌 二 a 十 执 m o d 2 ，即 域 加 法是 按 分量 方 式 进行的。 域乘法( a . , . . . a ,a o ) ( b . - , . . .b ib o ) 二 ( . - r r o ) 其 中 多 项 式 ( m 一 “ 一 十 ._2x， 十 ( a m - x m - + a m - 2 x - z + 一 a ,x + a o ) 卜 所得的剩余。 . r ix + r o ) 是多项式 (b m _ ,x m - + b - 2 x - 2 + . . .b lx + b o ) 在f 2 上被f ( x ) 除 这 种 表 示 f 2 . 的 方 法 称 为 多 项 式 基 表 示 。 注 意 到 f 2 , 恰 好 包 含2 个 元 素 乘法逆 素g 任 f 2 . ， 令f 2. 表 示 f 2 中 所 有 非 零 元 素 的 集 合 ， 则 可 证 明 至 少 存 在 一 个 元 使 得f 2, 中 任 意 非 零 元 素 可以 表 示 成g 的 一 个 方 幕。 这 样 的 一 个 元 素 g 称 为 f 2,. 的 生 成 元 。 即 f 2 . 一 g i : 0 r i s 2 一 2 1 , “ 一 9 i e f r 的 乘 法 逆 是 生 二 。 一 一 : (一). .ac，一 ，) 。 更 一 般 地 ， 域 f r 可以 表 示 成 f 2 上 一 个 维 数 为 m 的 向 量 空 间 ， 也 即 f 2 中 存 在 一 个 由 m 个 元 素 a . , a , , a m - , 组 成 的 集 合， 使 得 每 个“ e 凡可 唯 一 写 成 如 下 形 式， 即 a - a u a n + a ,a , + - - - + a m - ,a ， 一 其 中a ; e 0 , 1 a 可以 将。 表 示 成向 量0 , 1 向 量( a a , a l , , a m - z + a m - ,) 。 域 元 素 的 加 法由 元 素 的向 量表示按位异或来进行。 一 般 地， f z a 在f上 有 很多 不同 的 基 f z 在 基 域f z 上 的 一 组 正 规 基 是 形 如 西北工业大学硕士学位论文 y , y 2 , 尸, . 厂 的 一 组 基 ， 其 中 刀 任 只 . 。 理 论 上 证 明 这 样 的 基 总 存 在 。 给 定 任 意 元 素 a e f r , ， 可 以 记 。 一 菩 o ， 其 中 “ ; e 10 ,11 , o s i s m 一 。 由 于 平 方 在 凡 中 是 一 个 线 性 运 算 ， 有。 2 二 蒸 o , -万 a 百一 ” r 指 标 用 模 m 约 简 因 此 ， f 2 ,. 用 正 规 基 表 示 时 ， 平 方 一 个 元 素 可 以 通 过 向 量 表 示 的一个简单循环移位来完成，这是在硬件中非常容易实现的运算。 2 .2 椭圆曲线上的基本概念 本节主要介绍有关椭圆曲 线的基本概念和运算。 关于椭圆曲 线理论更系统 的 叙 述 可 参 阅 s ilv e r m a n 24 1 的 书 令 凡 表 示 q 个 元 素 的 有 限 域 ， q 一 厂， p 是 素 数 ， r a l , 令 e ( 乓 ) 表 示 定 义 在乓 上 的 一 个 椭 圆 曲 线 。 定 理1 ( h a s s e 定 理 ) 令 e ( f , ) 是 定 义 在 有 限 域f q 上 的 椭 圆 曲 线 ， e ( f q ) 的 点 数 用 # e (f q ) 表 示 ， 则i # e (f , ) 一 、 一 华晒。 定理 详细 证明 可 参阅 参 考 文 献2 5 的 v . 1 . 推 论对 任 意 卜 卜 2 而 , t - 0 (m o d p ) ， 存 在 凡 上 的 椭 圆 曲 线 e ， 使 得 # e ( f 9 ) = q + 1 一 t 。 如 果# e ( f p ) = p 十 1 ,曲 线 就 称为 是 超 奇 异 的 ， 否 则 称 为 是 非 超 奇 异 的 。 定 理2 e ( 凡 ) “z ,h ee z r , ， 其 中 n 2 卜 1 , n d 。 一 1 . 那 .2 .1 凡 上 的 椭圆 曲 线 令 p 3 是 一 个 素 数 ， a ,b 任 凡 满 足 4 a 3 十 2 7 b 2 0 0 ， 由 参 数 。 和 6 定 义 的 凡 上 的 一 个 椭 圆 曲 线 是 方 程y 2 s x l 十 a x + b 的 所 有 解( x , y ) ， 二 任 凡， y e 凡连 同 一 个 称为“ 无 穷 远点 ” ( 记为 o ) 的 元 素 组 成 的 点 集 合e ( 乓 ) 的 点 数 用# e ( 凡 ) 表 示 。 由 h a s s e 定 理 可 知 ， 十 卜 2 扣 # e ( f , ) ， + 1 + 2 万， 点 集 合 ( f , ) 对 应卜 西北工业大学硕士学位论文 y , y 2 , 尸, . 厂 的 一 组 基 ， 其 中 刀 任 只 . 。 理 论 上 证 明 这 样 的 基 总 存 在 。 给 定 任 意 元 素 a e f r , ， 可 以 记 。 一 菩 o ， 其 中 “ ; e 10 ,11 , o s i s m 一 。 由 于 平 方 在 凡 中 是 一 个 线 性 运 算 ， 有。 2 二 蒸 o , -万 a 百一 ” r 指 标 用 模 m 约 简 因 此 ， f 2 ,. 用 正 规 基 表 示 时 ， 平 方 一 个 元 素 可 以 通 过 向 量 表 示 的一个简单循环移位来完成，这是在硬件中非常容易实现的运算。 2 .2 椭圆曲线上的基本概念 本节主要介绍有关椭圆曲 线的基本概念和运算。 关于椭圆曲 线理论更系统 的 叙 述 可 参 阅 s ilv e r m a n 24 1 的 书 令 凡 表 示 q 个 元 素 的 有 限 域 ， q 一 厂， p 是 素 数 ， r a l , 令 e ( 乓 ) 表 示 定 义 在乓 上 的 一 个 椭 圆 曲 线 。 定 理1 ( h a s s e 定 理 ) 令 e ( f , ) 是 定 义 在 有 限 域f q 上 的 椭 圆 曲 线 ， e ( f q ) 的 点 数 用 # e (f q ) 表 示 ， 则i # e (f , ) 一 、 一 华晒。 定理 详细 证明 可 参阅 参 考 文 献2 5 的 v . 1 . 推 论对 任 意 卜 卜 2 而 , t - 0 (m o d p ) ， 存 在 凡 上 的 椭 圆 曲 线 e ， 使 得 # e ( f 9 ) = q + 1 一 t 。 如 果# e ( f p ) = p 十 1 ,曲 线 就 称为 是 超 奇 异 的 ， 否 则 称 为 是 非 超 奇 异 的 。 定 理2 e ( 凡 ) “z ,h ee z r , ， 其 中 n 2 卜 1 , n d 。 一 1 . 那 .2 .1 凡 上 的 椭圆 曲 线 令 p 3 是 一 个 素 数 ， a ,b 任 凡 满 足 4 a 3 十 2 7 b 2 0 0 ， 由 参 数 。 和 6 定 义 的 凡 上 的 一 个 椭 圆 曲 线 是 方 程y 2 s x l 十 a x + b 的 所 有 解( x , y ) ， 二 任 凡， y e 凡连 同 一 个 称为“ 无 穷 远点 ” ( 记为 o ) 的 元 素 组 成 的 点 集 合e ( 乓 ) 的 点 数 用# e ( 凡 ) 表 示 。 由 h a s s e 定 理 可 知 ， 十 卜 2 扣 # e ( f , ) ， + 1 + 2 万， 点 集 合 ( f , ) 对 应卜 西北工业大学硕士学位论文 y , y 2 , 尸, . 厂 的 一 组 基 ， 其 中 刀 任 只 . 。 理 论 上 证 明 这 样 的 基 总 存 在 。 给 定 任 意 元 素 a e f r , ， 可 以 记 。 一 菩 o ， 其 中 “ ; e 10 ,11 , o s i s m 一 。 由 于 平 方 在 凡 中 是 一 个 线 性 运 算 ， 有。 2 二 蒸 o , -万 a 百一 ” r 指 标 用 模 m 约 简 因 此 ， f 2 ,. 用 正 规 基 表 示 时 ， 平 方 一 个 元 素 可 以 通 过 向 量 表 示 的一个简单循环移位来完成，这是在硬件中非常容易实现的运算。 2 .2 椭圆曲线上的基本概念 本节主要介绍有关椭圆曲 线的基本概念和运算。 关于椭圆曲 线理论更系统 的 叙 述 可 参 阅 s ilv e r m a n 24 1 的 书 令 凡 表 示 q 个 元 素 的 有 限 域 ， q 一 厂， p 是 素 数 ， r a l , 令 e ( 乓 ) 表 示 定 义 在乓 上 的 一 个 椭 圆 曲 线 。 定 理1 ( h a s s e 定 理 ) 令 e ( f , ) 是 定 义 在 有 限 域f q 上 的 椭 圆 曲 线 ， e ( f q ) 的 点 数 用 # e (f q ) 表 示 ， 则i # e (f , ) 一 、 一 华晒。 定理 详细 证明 可 参阅 参 考 文 献2 5 的 v . 1 . 推 论对 任 意 卜 卜 2 而 , t - 0 (m o d p ) ， 存 在 凡 上 的 椭 圆 曲 线 e ， 使 得 # e ( f 9 ) = q + 1 一 t 。 如 果# e ( f p ) = p 十 1 ,曲 线 就 称为 是 超 奇 异 的 ， 否 则 称 为 是 非 超 奇 异 的 。 定 理2 e ( 凡 ) “z ,h ee z r , ， 其 中 n 2 卜 1 , n d 。 一 1 . 那