（计算机应用技术专业论文）基于fpga的加密算法的研究与实现.pdf

江苏大学硕士研究生毕业论文 摘要 在几乎所有现代通讯和计算机网络领域中，安全问题都起着非常重要的作 用。随着网络应用的迅速发展，对安全的要求也逐渐加强。目前影响最大的三类 公钥密码是r s a 公钥密码、e l g 锄a l 公钥密码和椭圆曲线公钥密码。但超椭圆 曲线密码是比椭圆曲线密码更难攻破的密码体制，且可以在更小的基域上达到与 椭圆曲线密码相同的安全程度。虽然超椭圆曲线密码体制在理论上已经基本成 熟，但由于它的计算复杂性大，所以在具体实现上还需要进一步研究。实现超椭 圆曲线密码系统，对于增强信息系统的安全性和研究更高强度的加密系统都有着 重要的理论意义和较高的应用价值，相信超椭圆曲线密码系统将会有更好的应用 前景。 对于密码系统，我们希望它占用的空间更少，实现的时间更短，安全性更 高。论文研究超椭圆曲线密码中的加密算法，对主要算法进行实现比较并提出 软硬协调思想实现超椭圆曲线密码系统就是为了达到这个目标。 论文先介绍了超椭圆曲线密码系统中有限域上的两个核心运算有限域 乘法运算和有限域求逆运算。对有限域乘法运算的全串行算法和串并混合算法 在f p g a 上用v h d l 语言进行了实现，并对它们的结果进行对比，重点在于对 并行度不同的串并混合算法进行实现比较，找到面积和速度的最佳结合点。通 过对算法的实现和比较，发现理论上面积和速度协调性较好的8 位串并混合算 法在实际中协调性并不是很好，最终得出结论，在所做实验的四种情况中，面 积和速度协调性较好的算法是4 位串并混合算法。随后论文对有限域求逆运算 的三种算法在f p g a 上用v h d l 语言进行实现比较，找到单独实现有限域求逆 运算较好的算法( m i m a 域求逆算法) 和可以与域乘法运算相结合的算法( 使 用域乘法求逆的算法) ，为软硬协调实现超椭圆曲线系统思想的提出打下基础。 论文然后提出了软硬协调的方法实现超椭圆曲线系统的思想，并对整个系统 进行了软硬件部分的划分。通过分析，将标量乘算法，除子算法和多项式环算法 划分到软件部分，并对其中的标量乘运算进行了详细的分析介绍，将有限域算法 归于硬件部分并对其进行了简单描述。在最后对全文进行总结，提出进一步需要 开展的工作。 关键词：超椭圆曲线：密码：f p g a ，有限域；标量乘；软硬协调设计 江苏大学硕士研究生毕业论文 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文 的全部内容或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密 口在 年解密后适用本授权书。 不保密团 学位论文作者签名： 琊辑导师签名：三烨 签字日期：2 0 0 8 年6 月7 日签字日期：2 0 0 8 年6 月7 日 江苏大学硕士研究生毕业论文 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：衡藉 日期：2 0 0 8 年6 月7 日 江苏大学硕士研究生毕业论文 1 1 研究背景与目的 第一章绪论 随着计算机和网络技术的高速发展和广泛应用，社会的信息化程度越来越 高，但社会对计算机和网络系统的依赖性也越来越大。若计算机和网络系统的 安全受到危害，则会危及国家的安全，引起社会的混乱，从而造成重大损失。 因此，确保计算机和网络系统的安全已成为世人关注的社会问题，并成为计算 机科学技术的热点领域。 众所周知，确保信息系统的安全是一个系统工程，必须从整体考虑，从底 层着手，综合采取措施，才能比较有效的确保信息系统的安全。硬件结构的安 全和操作系统的安全是信息系统安全的基础，而密码等则是关键技术。 密码技术是一门古老的技术，大概自人类社会出现战争便产生了密码。密 码的发展经历了由简单到复杂、有古典到近代的发展历程，并且在它发展的各 个阶段，都为确保信息安全发挥了重要作用。 1 9 4 9 年香浓发表了题为保密系统的通信理论这一著名论文，该论文把 密码置于坚实的数学基础之上，标志着密码学作为一门科学的形成。1 9 7 6 年 w - d i 硒e 和m e h e l l m a l l 提出了公钥密码的概念，从此开创了一个密码新时代。 公钥密码从根本上克服了传统密码在密钥分配上的困难，特别适合计算机网络 应用，而且很容易实现数字签名，因而特别受到重视。目前，公钥密码已得到 了广泛应用。 在国际上研究比较充分而且公认比较安全的公钥密码有，基于大整数因子 分解困难性的r s a 密码，基于离散对数问题困难性的e l g a l n a l 密码，以及基 于椭圆曲线离散对数问题困难性的椭圆曲线密码( e c c ) 等。 椭圆曲线密码是n e a lk o b l i t z 和c t o fm i l j 嚣于1 9 8 5 年提出来的，目前己 成为除r s a 密码之外呼声最高的公钥密码之一。它可以提供同r s a 密码体制 同样的功能。然而它的安全性建立在椭圆曲线离散对数问题( e c d l p ) 的困难 性之上。现在求解e c d l p 的最好算法具有全指数时间复杂度，与此不同，整 数因子分解问题却有亚指数时白j 算法。这意味着要达到期望的安全程度，椭圆 曲线密码可以使用较r s a 密码更短的密钥。因此，工程实现加解密速度较快， 并且可节省能源、带宽和存储空间。一些国际标准化组织已把椭圆曲线密码作 为新的信息安全标准。 作为椭圆曲线密码的一个推广，n e a lk o b l 沱在1 9 8 9 年提出了超椭圆曲线 江苏大学硕士研究生毕业论文 密码( h e c c ) 体制，它可以用更短的操作数达到与椭圆曲线密码同等的安全 程度。超椭圆曲线密码是基于有限域上超椭圆曲线的j a c o b i 姐群上的离散对数 问题的计算困难性。与椭圆曲线密码相比，超椭圆曲线密码所用的基域更小， 可以使用更短的密钥，且目前对低亏格( g g 4 1 口3 卜( ，一码一6 3 2 ) 口3 4 2 岛卜一日一6 3 ( m o d 口3 ) 6 江苏大学硕士研究生毕业论文 5 r e t l l m 讲1 ，( 吒，如) 根据c 锄t o r 算法很容易得到除子倍加算法，见算法2 2 算法2 2 除子倍加算法 i 印u t ：r e d u c o dd = 讲v ( 口，6 ) o i l t p u t ：同u c e d 讲v ( 口：6 ) = d + d 1 p e r f i o 肌e x t d e dg c dt oc o m p u t e d = g c ：d ( 口，2 6 + 日) = 而口+ 墨( 2 6 + ) 2 口3 卜口2 d 2 3 岛卜( 口6 + 岛( 6 2 + ，) ) d ( m o d 吩) 4 w h i l ed e 甙吩) g 4 1 口3 卜( ，一如一岛2 ) 口3 4 2 岛卜一日一岛( m o d 吩) 5 r e t u m 西，( 口3 ，反) 算法中的1 到3 步是复合步骤，第4 步是规约。在这个算法里，所有的多项 式环都是凹( 2 ”) 【“】，曲线的亏格决定了整个算法实现的难度。曲线的亏格越大， 多项式环的次数也越高，h ( ”) 和f ( “) 的次数也越高。尤其是f ( “) ，它的次数是 2 9 + l 。若g = 2 ，有限域卯( 2 ”) 中的刀取8 3 ，似) 的次数为5 ，则整个多项式 有8 3 6 = 4 9 8 个二进制位之多。实际上，也并不是亏格越大越好。已经有研究表 明，亏格g 4 的超椭圆曲线反而容易被攻破，因此，适合超椭圆曲线加密的曲 线亏格一般取2 或3 。文中为了便于实现，且便于与已有的论文结果进行比较， 选取g = 2 ，靠= 8 3 。 对于g = 2 的超椭圆曲线，c 锄t o r 算法中的第4 步可以简化成i f 语句。也就 是说，至多只需要进行一次规约即可。 。 有的论文提出，可以对c 锄t o r 算法进行改进，从而提高运算速度，如文献】 【1 2 】和等。但是这些改进基本上都是对c a l l t o r 算法进行展开，通过大量判断选 择语句对运算中可能出现的一些可能进行分类，对一些可以公用的部分进行提 取，甚至做一些合并等等。应该承认，这些改进的算法对于提高运算速度都有积 极作用。但是，对于硬件实现来说，这些改进的算法不但非常难以实现，而且可 升级性能太差。对于f p g a 实现，虽然能使速度加快，但会占用大量的芯片资源。 所以正如c l 觚c v 在文献【7 】中写到，它( 这类算法) 非常的不简单。” 从c a n t o r 算法可以看出，超椭圆曲线密码的除子加模块需要下面几个子模 块：环加法，环乘法，环除法，环g c d 和除子标准化等模块。这些子模块中又 包含有限域凹( 2 ”) 上的各种运算子模块一，： 7 江苏大学硕士研究生毕业论文 2 3 系统总体方案设计 由h c e l g 锄a l 加密算法可以看出，所发送的密文为( k ，s ) ，而k = 舾， s = 七q + m ，二者都有与整数七的运算，即标量乘运算。而s 的加法运算是很 容易的，所以我们将加密归结为标量乘运算。在超椭圆曲线密码系统中，标量 乘运算又是由除子加和除子倍加运算来实现的，这就需要实现c 锄t o r 算法。从 c a n t o r 算法可以看出，除子加和除子倍加运算是由多项式上的运算实现，其中 包括多项式环加法、环乘法、环除法和环g c d 等运算。最终，多项式环的运算 又由有限域中的各种域运算实现。所以，有限域运算是所有运算中最基础也是 最重要的运算。由此可知，系统总体方案设计框图如图2 1 所示。 栖( 标鼙乘算法) 上 - l 除子加、除子倍加( c a n t o r 算法) l 上 l 多项式的加法、乘法、乘方、除法、 i 求逆以及求最人公约数( g c d ) 运算 1 l 有限域中域元素的加法、 乘法、乘方、求逆运算 图2 1 系统总体方案设计框图 由上得知，实现超椭圆曲线密码系统的算法的底层算法是有限域上的算法。 在有限域的加法、乘法、乘方及求逆运算中，加法是很容易实现的，乘方可山 乘法运算代替，所以相对困难的就是乘法和求逆运算。实现乘法运算和求逆运 算都有几种算法，在本文的第五章将对这两种运算的各个算法的实现和比较进 行讨论。而在现实中，如果所有的运算都有硬件完成，将会占用大量的空间， 所以本文第六章将讨论使用软硬协调的方法实现超椭圆曲线密码系统。 2 4 小结 本章介绍了e l g 锄a l 加密和数字签名在超椭圆曲线上的模拟，并由所发送 的密文丌始逐层向下推导，由此引出c a i l t o r 算法，多项式运算，到最终的有限 江苏大学硕士研究生毕业论文 域上的运算，仔细分析了各个层次之间的关系，用框图表现出来，即系统总体 方案设计框图。由此框图可以明显看出各个层次之间的关系，并将超椭圆曲线 密码系统的基本框架清楚的表达出来，使得设计思路更加清晰，为以后的设计 实现提供了方便。 9 江苏大学硕士研究生毕业论文 第三章超椭圆曲线密码基础知识与系统概述 这一章介绍f p g a 实现超椭圆曲线密码的用到的一些基本知识。首先介绍 近世代数罩与超椭圆曲线密码系统相关的几个基本概念。然后详细说明超椭圆 曲线。最后讨论超椭圆曲线密码的定义及相关理论。 3 1 密码学基础 在介绍超椭圆曲线密码之前，首先介绍需要用到的几个数学概念。这些概 念都属于近世代数罩的内容。近世代数中对这些概念有详细的阐述，文中只是 从与本课题有关的方面进行简要的说明。具体的一些证明过程以及更深入的内 容可以参考近世代数方面的书籍【。4 】【15 】和【17 】等。 3 1 1 群 抽象代数中最简单的研究对象就是群。这个概念已深入现代数学了。许多 看似初等的问题仅仅是有关群基本事实的神秘表现。这一点在初等数论中表现 得尤为明显，许多结论都可以给出“初等的证明，但这样的证明却需要掌握 复杂并且容易混淆的知识。 定义3 1 给定一集合g = 如b ，) 和该集合上的运算o ，满足下列四条件的 代数系统 称为群： ( 1 ) 封闭性：若口，6 g ，则存在c g ，使口0 6 = c ( 2 ) 结合律成立：口，6 ，c g ，恒有( 口0 6 ) 圆c = 口 ( 6 圆c ) ( 3 ) 存在单位元素p ：即存在p g ，对v 口g ，恒有口o p = p o 口= 口 ( 4 ) 存在逆元素：对于v 口g ，恒有6 g 使口 6 = 6 0 口= p ，元素6 称为 口的逆元素，用口一表示，即6 = 口一。 若对v 口，6 g ，有口0 6 = 6 0 口，则称 为阿贝尔( a b e l i 觚) 群。 如g = l ，一1 ) 在乘法运算下构成群，而且是阿贝尔群。它满足以上四个条件： 击封闭性：( 1 ) ( 一1 ) = ( 一1 ) ( 1 ) = 一l ，( 1 ) 幸( 1 ) = l ，( 一1 ) 木( 一1 ) = l 。 3 结合律：显然成立。 a 单位元p _ 0 。 a 逆元存在。l 的逆元素就是l ，1 的逆元素就是1 。 另外，群还有以下性质： ( 1 ) 群中元素的个数称为群的阶，用 g 表示。一 l o 江苏大学硕士研究生毕业论文 ( 2 ) 群的单位元p 是唯一的。 ( 3 ) g 中每一个元素的逆元是唯一的。 ( 4 ) 是一群，日cg ， 也是一群，则称h 为g 的一个子群。 文中只考虑阿贝尔群，因为根据c 卸幻r 算法，在超椭圆曲线上定义的 j a c o b i 锄集合的元素和c 肌t o r 在这个集合上定义的加法操作构成了一个阿贝尔 群。 3 1 2 环 ! 环的概念是“数”的概念的推广，与群的概念相比，它可能还要更加直接一 些。一个环只是一个具有两个运算。和。的集合，并且具有一个特殊的元素o 。 其定义如下。 定义3 2 设尺为非空集合。r 和在r 上定义的两个运算，o 和o ，满足下 面的三个条件的代数系统构成环，记作 ： ( 1 ) 尺在。下构成阿贝尔群 ( 2 ) 结合律：对于v 口，6 ，c ，有口o ( 6 圆c ) = ( 口0 6 ) o c ( 3 ) 分配律：口o ( 6 0 c ) = ( 口圆6 ) o ( 口圆c ) 如果环满足对于v 口，6 ，c ，有以0 6 = 6 圆口，则构成可交换环。 若坏存在单位元p ，使口o p = p o 口= 口成立，则称环为有单位元的环。 构成j a c o b i 锄的除子是由多项式环构成的，多项式环是有单位元的可交换 环。因此，文中研究的范围仅限于有单位元的可交换环。所谓的多项式环就是形 如口。工”+ 吒一i x 剃+ + 口l j + 口o ，( 刀是整数) 的式子，其中q ( 0 f 刀) 是某个基环。 多项式环可以有除法和取模运算，可以有最大公约数运算。两个多项式相除， 总能得到商和余数，如果余数为零则表示可以整除。如果两个以上的多项式环可 以整除相同的某些多项式环，那么其中最大的多项式环称为多项式环的最大公约 数( g c d ) 。 h e c c 中用到的多项式环是系数为加罗瓦域的多项式坏。关于加罗瓦域的知 识将在下一小节进行介绍。 3 1 3 有限域 定义3 3 ，是至少含有两个元素的集合，对，定义了两种运算。和o ，并 且满足以下三个条件的代数系统 称为域。 ( 1 ) f 的元素关于运算。构成阿贝尔群，设其单位元为0 。 ( 2 ) f 除 o 以外关于运算0 构成阿贝尔群。 江苏大学硕士研究生毕业论文 ( 3 ) 对于口，6 c f ，分配律成立。即 ( 口0 6 ) 0 c = 口p c + 6 0 c c o ( 口0 6 ) = c o 口+ c 0 6 例如：实数的全体、复数的全体关于通常的加法、乘法都是域，分别称为实 数域和复数域。 若域f 的元素有限，则称之为有限域或加罗瓦( g a l o i s ) 域【1 8 】。 多项式 p ( 工) = 口o + 口i x + + 口i 石，口f f ， f = 0 ，l ，七 ( 3 1 ) 如果f 的元素个数为p ，则不同的多项式p ( 工) 个数为p “，即p ( x ) 和七+ l 位 p 进制数i 4 2 q 口。一一对应( q f江0 ，l ，p ) 。则p ) 和( 口o ，口l ，口口) 一 一对应。特别当f = 卯( 2 ) = o ，1 ) ，设 ( 功三d 届0 0 ( x ) = l 岛i o ( z ) = 石 另i o ( 功= 1 + 工 i ( x ) = 石2 a o i ( x ) = l + x 2 风l l ( x ) = 工+ x 2 p l l i ( z ) = l + z + 工2 这些多项式的乘积可得次方超过2 的多项式。若引进在卯( 2 ) 不可化约多项 式历( 工) = l + z + 夕，则m o d 朋( 石) ，上面的多项式除去( z ) 以外关于乘法构成 交换群。 表3 1 多项式模朋( 曲= 1 + x + x 3 的乘法结果 l 工 l + 石j r 2l + 石2工+ 工2 l + 工+ ， ll x l + 工 x 2l + x 2x + x 2l + x + ， 石工 工2x + # l + 工 l l + 工+ fl + 工2 l + 工l + 工 工+ 工2l + z 2l + 工+ ，x 2 l z x 2石2 l + j l + x + ，工+ x 2 工 l + 石2 l l + z 2 l + ， l x 2 z l + 工+ 工2 l + 工 z + 工2 工+ 工2z + 工2l + z + j c 2 i l + x 2 1 + 工 工 工2 l + 工+ x 21 + z + ，l + x 2 x l x + 工2x 2l + 工 1 2 江苏大学硕士研究生毕业论文 以( 1 + x 2 ) ( x + x 2 ) 为例，( 1 + 工2 ) ( x + j 2 ) = x + ，+ ，+ ，+ 工+ 1 1 x 4 + x 3 + 工2 + 工= j + l余数为l + 工 ， 所以，( 1 + x 2 ) ( 工+ j r 2 ) 耋l + 工m o d ( ，+ 工+ 1 ) 。其它同理可得。 可见 0 ，1 ，工，l + 薯工2 ，l + x 2 ，工+ ，1 + 工+ 了2 ) 在m o d ( ，+ 工+ 1 ) 的意义下，关于加 法和乘法构成有限域。由于此有限域共有8 个元素，故称其阶为2 3 = 8 。这样 的有限域可以表示为g f ( 2 4 ) 。 有限域上的各种运算举例如下： 二进制域只由下面1 6 个次数小于4 的多项式组成： 0 x2， j 3 + 工2 1 工2 + l工3 + 1，+ 石2 + l x工2 + 工 x 3 + 工，+ 工2 + 工 工+ l石2 + 工+ lz 3 + x + 1 ，+ x 2 + z + l 下面列出不可化约多项式厂( x ) = x 4 + x + 1 域e 上的一些算术运算： ( 1 ) 加法： ( ，+ 工2 + 1 ) + ( j 2 + 工+ 1 ) = ，+ 石。 ( 2 ) 减法： ( x 3 + x 2 + 1 ) 一( x 2 + 工+ 1 ) = ，+ j 。 ( 3 ) 乘法：( 一+ j 2 + 1 ) ( ，+ 工+ 1 ) = ，+ 1 。因为 ( ，+ 工2 + 1 ) ( x 2 + x + 1 ) = 工5 + j + l 且 ( ，+ 工+ 1 ) m o d ( 工4 + 石+ 1 ) = x 2 + l 。 ( 4 ) 求逆：( ，+ ，+ 1 ) 一1 = ，因为( 一+ x 2 + 1 ) 一x 2m o d ( x 4 + 工+ 1 ) = l 。 另外，关于有限域还有几个基本的原理，这些原理对于理解文中的有限域算 法也非常重要，下面简要介绍一下。 定理3 1设p ( x ) 是系数在卯( p ) 域的m 次不可化约多项式，则次方 肌一l ，系数在卵( p ) 上所有多项式关于m o dp ( x ) 构成一个阶为p ”的加罗瓦域 g f ( p ”) 。 推论：由于聊次不可化约多项式p ( 工) 满足p ( 朋) 兰0 m o dp ( 聊) ，所以有限域 乘法的到的，都可以通过加p ( 工) 进行规约。 3 1 4 公钥密码 d i 伍e h e l l m 锄在密码学新方向这篇文章中，提出了一种公钥密码的新 思想：每个用户有一加密用的密钥t ，还有一个解密用的密钥岛，将屯公开， 保密，而且t 的公开不至于妨碍到毛的安全忆可将各用户的t 集中成公钥文件， 江苏大学硕士研究生毕业论文 像电话本一样公丌发给所有用户。若b 欲与a 通信，查公钥文件得a 的加密用 公钥乞，用之加密得密文：c = 臣。，( m ) ，将c 寄给a ，a 用只有他自己才掌握 的解密密钥岛解密恢复明文朋：m = q ，( c ) ，任何第三者截获密文后，由于 不掌握解密密钥，也无法得知明文m 。由于屯屯，故公钥密码也称为“非 对称密码”。 在公钥密码体制中，密钥对的选择要保证从公钥求出私钥等价于要求解一个 困难的计算问题。构成常用公钥密码基础的困难问题有如下的数论问题： ( 1 ) 整数的因子分解问题，其困难性是r s a 公钥密码安全性的基础。 ( 2 ) 离散对数问题，其困难性是e l g 锄a l 公钥密码及其变体( 如数字签名算法) 安全性的基础。 ( 3 ) 椭圆曲线离散对数问题，其困难性是椭圆曲线公钥密码安全性的基础。 超椭圆曲线密码也是公钥密码的一种，它是以有限域上超椭圆曲线的 j a c o b i a n 群上的离散对数问题的计算困难性为基础的。由于其根本也是基于求 离散对数的困难性，所以我们可以通过下面的例子先理解基于离散对数的密码 体系( 此例子以e l g 锄a l 公钥密码为基本思想) 。 设p = 1 1 ，g = 7 ，在g f ( 1 i ) 上有：7 0 = l ，7 1 = 7 ，7 2 = 5 ，7 3 = 2 ，7 = 3 ， 7 5 = l o ，7 6 = 4 ，7 7 = 6 ，7 8 = 9 ，7 9 = 8 ，7 m = l ，g 是舒( 1 1 ) 上的本原元素。 设a 的私钥_ = 3 ，公钥y ，= 2 ：b 的私钥= 5 ，公钥儿= 1 0 。 假定a 欲将信息研= 6 保密寄给b 。a 取x = 7 ，a 计算： c - 暑2 7 m o d1l 三6 c i 暑g m o dll 三o k 暑( 1 0 ) 7m o d1 1 量l o 岛= 砌m o dl l 暑6 0 兰5 m o d l l a 将( 6 ，5 ) 作为密文寄给b 。b 收到后计算 x 暑( g ) 5m o d l l 三l o 一 k 一三( g ) 。0 - 5m o d l l 兰l o 班兰k 一1 c 2 兰5 0 m o d l l 暑6 故恢复朋兰6 。 3 2 超椭圆曲线密码 要讨论超椭圆曲线密码，必须先了解超椭圆曲线及其相关的一些知识。而 超椭圆曲线是椭圆曲线的推广，因此本节先概述椭圆曲线和椭圆曲线离散对数 1 4 江苏大学硕士研究生毕业论文 问题，在给出超椭圆曲线相关知识，最后引出超椭圆曲线密码。 3 2 1 椭圆曲线 椭圆曲线指的是由w c i e r s 觚s 方程： y 2 + 口i 砂+ 口3 y = x 3 + 口2 石2 + 口4 x + 口6 ( 3 2 ) 所确定的曲线。 为方便起见，令工= 工z ，y = y z ，代入w 萌e r s 仃a s s 方程，可得关于射影 平面 x ，y ，z ) 的方程： 】厂2 z ：x 3 + 珏y 2 z + 凇2 + c z 3 ( 3 3 ) z = 0 代入可得x = 0 有三重根，这意味着在无穷远交于3 点，用。表示无穷远 点。 心e r s t r 硒s 曲线称之为椭圆曲线，表示为c i 若p 、q 是c 上两点，如图3 1 所示，过p 、q 两点引一直线，交c 于第3 点p 幸q 。，过p q 引x 轴的垂直线， 交c 于点p + q 。设q 皇( x ，y ) ，则q = ( x ，- y ) 。q 和一q 的连线便是垂直于x 轴的 垂直线。它和c 交于第3 点即无穷远点。图3 1 中定义的p + q 就是椭圆曲线密 码定义的点加。 一 尹 i i r 。洲聃7 j 一j 一。匕 i 。， ：八、。 。 、p + q p ； 、， b ，2 一x 3 一缸+ 3 图3 1 椭圆曲线密码点加运算定义 3 2 2 椭圆曲线离散对数问题 若给定一条有限域f p 上的椭圆曲线，g 为e 上的一点e ( f p ) ，则e 上关于 g 的e c d l p 为：给定一点q ，求解整数r ，使得硒= q ( 硒为倍，即r 个g 相加) 。 对该系统的攻击依赖于在f p 上求解方程：g 卢qm o dp 或产l o g g qm q dp 。d l p 1 5 江苏大学硕士研究生毕业论文 求解是非常困难的，e c d l p 比有限域上的d l p 更难求解。在f p 上选择一条椭 圆曲线e 及一个具有较高阶的基点g e ( f p ) ，计算该点的倍乘而，相对来说较 容易，但己知g 和要求r 则是很困难。基于椭圆曲线密码的安全性最终归结为解 e c d l p 问题。当数据量足够大以致此问题无法解决e c d l p 时，认为该密码体制 是安全的。 3 2 3 超椭圆曲线 超椭圆曲线是一种特殊的代数曲线，可以看作是椭圆曲线的推广。其定义为： 定义3 4f 是有限域，f 是f 的代数闭包。f 上亏格为g 的超椭圆曲线( g 1 ) f 可以表示为以下形式： c ，2 + h 似) y = f ( “) i nf 【珥，】， ( 3 4 ) 其中觑“) ，是一个最高次数为g 的多项式，以“) f “】是个首项次数为 2 9 + l 的多项式，并且没有一对数( 珥v ) f f 同时满足方程y 2 + 日( “h = 日似) 和两个不同的等式2 v + h ( “) = 0 和日协) y 一日t ( “) = o 。可以看出，如果g = l ，则 方程3 4 就是椭圆曲线。对于超椭圆曲线密码的应用，方程中多项式的系数都是 有限域的元素。根据前面所述的多项式环的概念，日( “) 和f ( “) 都是多项式环 g ，( 2 ”) 【“ 的元素。 文中有限域采用g 尸( 2 ”) ，其中刀是个素数。这种有限域采用特征为2 的基 域，便于计算机的实现。当然，也可以采用g f ( 口) ，其中g 是个素数，但是这种 有限域最终还是要化成二进制在计算机罩进行表示。目前，两种方法的采用都有 研究，文中采用凹( 2 ”) 来表示，以便于硬件实现。 图3 2 给出了实数域上超椭圆曲线的一个例子。这个曲线是亏格为2 并满足 日( “) = o 。它定义为 g ： ，2 = “5 5 “3 + 4 “+ 3 = “( “一1 ) ( “+ 1 ) ( “一2 ) ( “+ 2 ) 曲线的图形如图3 2 。 为了下一部分的群运算得以顺利实现，现在让我们试着用与椭圆曲线上同样 的方法在超椭圆曲线上将两个点( 包括无穷电) 相加。假设只q c ，是连接尸，q 的直线。b e z o u t 定理证明与c 会有2 9 + 1 个交点，所以 n c = p q ，蜀，r ，r 川) 这个事实可以得到论证，我们使与c 2 相交，结果如图3 3 。c i 的亏格g = 2 ， 1 6 江苏大学硕士研究生毕业论文 所以我们得到2 9 + l = 5 个相交点。 幽3 2 ：实数域上超椭圆曲线c l ：，2 = 甜5 5 “3 + 4 “+ 3 = “似一1 ) ( “+ 1 ) ( ”一2 ) ( “+ 2 ) 图3 3 ：与超椭圆曲线c i ： ，2 = “5 5 之+ 4 ”，3 - 的交点 1 7 江苏大学硕士研究生毕业论文 如果g ：l ，即椭圆曲线的情形，我们只能得到唯一的第三个点，但是当g 2 时，我们可以得到多个点，并且没有规范的方法可以找到指定的一个。这意味着 解决的方法是使用点的列表而不是单一的一个点。理论上讲，每一个人都会选定 c 上的g 个点组成一个集合，并定义一个与这个集合相关的确定的方程。 下一小节将集中讨论这种关系并介绍除子的概念，我们将用除子来定义 j a c o b i 矾群上的加运算。 3 2 4 除子 对于椭圆曲线，点群的加法操作是用切割线定义的。那么对于超椭圆曲线是 否也能这样定义呢? 实际上不可以。因为超椭圆曲线的图像比较复杂，做切割线 并不能得到两个点的和。例如，方程y 2 + ，= 工5 一，+ 4 工，其图像如图3 4 所示。 设p ，q 是曲线上的任意两点，过p ，q 作切割线，则与曲线的交点可能多于一 个。这样，就不能利用椭圆曲线定义点加的方法来定义超椭圆曲线上的点加。于 是要有一种方法来定义超椭圆曲线上的阿贝尔群。要定义这个群，首先要定义除 子。 图3 4 方程y 2 + y = ，一一+ 4 工的图像 定义3 4 在超椭圆曲线上，满足恒等式 曰( “) 2 + 日( “) 曰( “) 三f ( 材) ( m o d 彳( “) )( 3 5 ) 江苏大学硕士研究生毕业论文 的彳( ”) 和口( “) 组成的g f ( 2 ”) 【”】多项式对d i v ( 么( “) ，b ( “) ) 称作超椭圆曲线的除 子。 除子也可以用另外的方法定义： 定义3 5 c 上的除子是一个有限形式和d = 尸m p 尸，这早m 尸是整数，且 只有有限个m 。是非零的，p 是超椭圆曲线上的点。d 的次数定义为 d e g d = 尸朋p 。 显然，定义3 5 不便于理解和实现。文中采用第一种定义方法。从定义3 4 可以看出，因为取模，彳( “) 和b ( “) 的次数可能很高但仍满足恒等式。所以，为 了定义一个群，还要有一个规约除子的概念。规约除子是指么( “) 次数不超过g ， 曰( “) 系数不超过彳0 ) 的除子。所有非规约除子都可以通过c 锄t o r 算法进行规约。 另外，为了简化c a l l t o r 算法中g c d 模块的运算，除子d i v ( 彳( “) ，b ( “) ) 中的 彳( “) 需要进行标准化，即把彳( “) 多项式的各项同除以最高项的系数，使得最高 项的系数为l 。根据恒等式3 5 ，由于是取模运算，所以彳( “) 系数的改变，不影 响b ( “) 的值，d i v ( 彳似) ，b ( “) ) 仍然是超椭圆曲线的除子。 3 2 5j a c o b i a n 群 所有规约除子的集合和除子加法构成j a c o b i 锄群，记作- ，( c ；乞) 。( c ；) 是一个阿贝尔群，它的单位元是d i v ( 1 ，o ) 。可以验证d i v ( 1 ，o ) 是，( c ；只。) 的单位元。 首先验证，d i v ( 1 ，o ) 是超椭圆曲线c 的规约除子。按照上面的定义，显然d i v ( 1 ，o ) 的次数小于等于g ，而且满足恒等式 b ( “) 2 + 月( “) b ( “) 三，( “) ( 1 i 】l o d 彳( 甜) )( 3 6 ) 上式中爿( “) = 1 ，b ( 掰) = 0 ，因为任何数都能被l 整除，所以恒等式两边相等， 恒等于0 。 下面将d i v ( 1 ，0 ) 代入c a n t o r 算法。于是， d = g c d ( 口l ，l ，勿+ ) = 而q + 如+ ( 岛+ 月) 显然，口，1 ，6 + 日的最大公约数是l ，即d 1 。s ，屯，邑可以分别选择o ，l ，0 。代入 算法2 1 的第2 步和第3 步： 口3 一口i d 2 = 口l 1 = 口i 岛+ 一0 幸q 幸o + l l 6 l + o 幸( 6 l o + ，) l ( i l 】l o d q ) = 岛 因为不需要规约，所以d i + 州l ，o ) = d i ，反过来同样成立。这样便验证了d i v ( 1 ，o ) 是_ ，( c ；c ) 的单位元。 1 9 江苏大学硕士研究生毕业论文 要证明所有规约除子的集合和除子加法构成j a c o b i 雒群还需要证明其它几 个条件成立，文献【7 】对此有详尽的证明过程，此处不再一一证明。给出上面的验 证过程，主要目的是使读者对c 删o r 算法的步骤有一个形象的了解，以便于理 解后面的具体实现过程。 ，( c ；c 。) 上的标量乘是指：d 是( c ；乞) ( 或，( c ；c ) 的一个n 阶子群) 的 一个生成元，任取脚 撑，( c ；f ) ( 或m n ) ，计算，国= d + d + + d ( m 个) 。 v j ( c ；只) 上的离散对数问题( h c d l p ) 是指：对定义在g f ( g ”) 阻】上的 ( c ；，) ，给出一个生成元d 和另外一个除子d ，求一整数肌，使得d ，o 。 3 2 6 安全超椭圆曲线 超椭圆曲线密码体制研究非常关心的一个问题是如何选择一条合适的曲线， 使得在它的j a c o b i a l l 群上建立的密码体制是安全的。并不是每条曲线都是安全 的。目前的研究表明，为了对抗已有的对离散对数的攻击方法，选取的超椭圆曲 线应该至少满足几个条件1 3 】： 第一，j a c o b i a n 的阶群，( c ；f 。) 含有一个大素数因子，这是为了防止s h 锄k s 的大步小步法和p o h l i 争h e l l m a n 方法【1 9 1 的攻击。目前要求这个大素数因子至少应 该有1 6 0 位【2 0 2 1 1 。 第二，群( c ；c 。) 或者撑( c ；c ) 的大素数因子不能整除( g ”) 一l ，这里的 七 ( 1 0 9 粤”) 2 。这是为了防止f r e y 和r u “2 2 1 利用t a t e 对推广的m o v 攻击【2 3 1 。 第三，大素数域g f ( p ) 上的超椭圆曲线的j a 0 0 b i 锄群中不能有p 阶子群。 第四，虽然通常认为亏格越大达到相同安全性采用的基域越小，但是g a u d d ， 的论文【2 4 】中讨论了关于大亏格超椭圆曲线易受攻击的问题。他指出，亏格大于4 的超椭圆曲线有一种快速的攻击方法，可以利用攻击离散对数的l 曲。方法进行 攻击。 另外，有一类称为超奇异曲线也不安全。研究表明，超奇异的椭圆曲线不适 合加密，这种观点也被引入了超椭圆曲线。关于如何避免超奇异的超椭圆曲线在 文献2 习有专门阐述。 综合以上，本文采用的超椭圆曲线其亏格等于2 ，日( 群) 的次数选1 ，用 d e g ( 日 ) ) = l 表示。日似) 的形式为( 甜) = j l l ”+ j i l d ；，似) 的形式为 f ( 甜) = 五掰5 + 五掰4 + 五甜3 + 五掰2 + 石掰+ 五。j ( c ；艺) 选择歹( c ；( ) ，除子的形式为 d i v ( “2 + 口i “+ ，6 l “+ 6 0 ) 。以上各系数均为g f ( 2 ”) 元素。 江苏大学硕士研究生毕业论文 3 2 7 超椭圆曲线密码 超椭圆曲线的加密首先要解决的一个问题就是找到一超椭圆曲线，将明文通 过编码嵌入到曲线上的点。然后，对这些点运用我们熟悉的加密运算。假设嵌入 的工作已经完成，下面的工作就是将我们熟悉的加密运算中的有限域用超椭圆曲 线上的j a c o b i 锄群置换。例如：对于上面说明的e l g 锄a l 密码系统，同样可在超 椭圆曲线上实现这个系统，假定明文所嵌入在曲线上的点。选一点g e ，彳 用户和曰用户分别选择一整数、，吼、保密，将g 、g 公开。若彳 向b 发送朋，则发送密文( 足g ，己+ 七( 口。g ) ) ，七是一个随机的整数。b 收到后先 根据七g 求得七g 。则己= 只+ 七( g ) 卜七g ，即a 欲向b 发送的明文。 3 3 超椭圆曲线密码系统 超椭圆曲线密码体制基本上可以看作是有限域乘法群上密码体制的模拟。由 于超椭圆曲线j a c o b i 觚群自身的特殊结构，使得超椭圆曲线密码体制与其它基于 离散对数系统的密码体制又有许多不同。 整个超椭圆曲线密码系统的安全性除了上述的曲线方程以外还决定于基域 的大小。换句话说就是g f ( 2 ”) 中n 的取值大小。人们公认的关于椭圆和超椭圆 曲线密码系统所需要的阿贝尔群的阶至少有2 啪。对于c 上的超椭圆曲线，至少 要满足g 幸1 0 9 2g 1 6 0 ，g 是超椭圆的亏格。因此需要的域c 的阶要大于等于2 。 文中选取刀= 8 3 ，规约多项式为厂( 工) = j 盯+ 工7 + ，+ z 2 + 1 。规约多项式一般有固 定的两种形式f ( 工) = ，+ + l 和，( z ) = ，+ 妒+ 驴+ + 一+ l ，规约多项式的选 择可以参考文献【2 6 】【2 7 】和【2 8 】等。 有关超椭圆曲线密码系统的设计可见第二章的总体设计以及第五、六章的具 体设计内容。 3 4 小结 本章依次介绍了密码学基础( 包括群、环、有限域这些近世代数的内容和 公钥密码的基本知识) ，超椭圆曲线密码( 包括超椭圆曲线、除子、j a c o b i 觚群 以及安全问题的讨论) 和超椭圆曲线密码系统的概况。要深入了解这些基础知 识需要阅读专门的文献。这里仅对与下一步研究工作密切相关的知识点进行介绍 并对一些知识进行了归纳、分析，使下一步的研究工作能够更好地把握住关键点。 2 l 江苏大学硕士研究生毕业论文 第四章f p g a 及开发工具简介 无论是用硬件实现超椭圆曲线密码系统的一些算法，还是论文第六章提出的 软硬协调实现超椭圆曲线密码思想的实现，都要用到相关的丌发工具，都要在一 定的丌发环境中完成。本章简要的介绍了所需的丌发工具和丌发环境，以方便后 面算法的具体实现和第六章思想的提出。 4 1f p g a 简介 现场可编程门阵列( f p g a ) 是近十年来加入到用户可编程技术行列中的器 件，可编程门阵列在器件的选择和内部的互连上提供了更大的自由度。f p g a 的结构类似于掩膜可编程门阵列( m 邪tp r 0 伊锄a b l eg a t e 慨m p g a ) 由逻辑 功能块排列成阵列组成，并有可编程的内部连线连接这些逻辑功能块来实现不 同的设计。 4 1 1f p g a 的特点 f p g a 是英文f i e l d p r o g r a m m a b l eg a t ea r r a y 的缩写，即现场可编程门阵 列，它是在p a l 、g a l 、e p l d 等可编程器件的基础上进一步发展的产物。它 是作为专用集成电路( a s i c ) 领域中的一种半定制电路而出现的，既解决了定 制电路的不足，又克服了原有可编程器件门电路数有限的缺点。 f p g a 的基本特点主要有： ( 1 ) 采用f p g a 设计a s i c 电路，用户不需要投片生产，就能得到合用的 芯片。 ( 2 ) f p g a 可做其它全定制或半定制a s i c 电路的中试样片。 ( 3 ) f p g a 内部有丰富的触发器和i o 引脚。 ( 4 ) f p g a 是a s i c 电路中设计周期最短、开发费用最低、风险最小的器 件之一。 ( 5 ) f p g a 采用高速c h m o s 工艺，功耗低，可以与c m o s 、t t l 电平兼 容。 可以说，f p g a 芯片是小批量系统提高系统集成度、可靠性的最佳选择之 一o f p g a 是由存放在片内i 认m 中的程序来设置其工作状态的，因此，工作时 需要对片内的r a m 进行编程。用户可以根据不同的配置模式，采用不同的编 图4 1f p g a 的基本结构图 在排成阵列的可编程逻辑单元之间存在稚线通道的f p g a 构成通道型 f p g a ，它们的主要结构特性如下： 江苏大学硕士研究生毕业论文 ( 1 ) 类似门阵列的连线通道和逻辑功能块结构：逻辑资源和通信资源明显 是分丌的和性质不同的，反映在c a d 系统中逻辑阵列上逻辑功能块的布局和功 能块之间的布线是作为设计的不同阶段来处理的。 ( 2 ) 支持双向和多资源的连线：双向连线在r a m 编程结构中是有问题的， 因为基本的丌关元件有高阻抗，并要求中自j 缓冲，但是在p c b 和门阵列设计方 式中，双向连线是最常用的，并在其中有效地支持基本元件，f p g a 设计者在结 构中包含它们以维持与以前技术之间的连贯性。 ( 3 ) 具有多输入的功能单元：提供具有许多输入的大的功能单元可以实现 完整的逻辑功能块，使得逻辑功能块比普通门阵列的功能更复杂，可以减少要求 的功能块数目，更重要的是也减少了设计布线要求的功能块问的连线。这对r a m 型f p g a 特别重要，因为连线通道会扩充面积和增加延时。 4 1 3s t r a t i x 系歹uf p g a s t r a t 仅系列是a l t e r a 公司于2 0 0 2 年2 月j 下式宣布推出的新一代可编程逻辑 器件。该系列采用1 5 v 内核，o 1 3 微米全铜工艺。芯片由q u 砌s i l 2 o 版本软件 支持。主要特点是： 内嵌三级存储单元，可配置为移位寄存器的5 1 2 b i t 小容量洲；4 k b i t 容量的标准r a m ( m 4 k ) ；5 1 2 k b i t 的大容量r a m ( m e g a r a m ) ，并自带 奇偶校验