（控制理论与控制工程专业论文）椭圆曲线密码（ecc）算法的fpga实现及优化设计.pdf

武汉理_ _ l = 人学硕士学位论文 摘要 随着计算机运算速度的迅速提高和i n t e r n e t 分布式计算能力的日益强大，经 典的公钥密码体制如r s a 、d i f f i e h e l l m a n 等在密钥长度为5 1 2 b i t 下已经越来越 不安全；虽然增加密钥长度能增加安全性，但是加、解密效率会越来越低，同 时对系统的要求也会提高。在这种情况下，椭圆曲线密码体制( e l l i p t i cc u r v e c r y p t o s y s t e m ，简称e c c ) “短密钥”的优势得到充分体现，其发展大有取代r s a 成为通用公钥密码体制之势。 本文结合椭圆曲线算法的数学基础对椭圆曲线密码体制进行深入的分析， 对椭圆曲线算法的f p g a 实现进行了具体的研究设计，为e c c 算法提供了实际 可行的硬件解决方案。 底层运算的实现中乘法器使用串并混合型结构以达到面积与速度的最佳匹 配。对比了两种模逆算法，从节约时间的角度选取了扩展的欧几里德方法。在 寻找适合硬件实现的高效算法的同时，充分考虑了e c c 算法的多样性，没有使 用针对单一曲线的快速算法。 上层运算中最重要的部分是k p 运算，结合底层有限域运算的特点对四种求 k p 的快速算法进行分析，最终选择了射影坐标下的m o n t g o m e r y 方法并给出了 其f p g a 实现算法。 在a l t e r a 公司的集成开发环境q u a r t u s i i 下，用v h d l 语言实现了椭圆曲线 算法的底层域运算及上层k p 运算。使用a n x ix 9 6 2 中椭圆曲线的例子对各个 运算模块进行测试，验证了它们的正确性。 测试结果表明：设计芯片能够有效地完成椭圆曲线加密体制完熬流程；在 2 0 m h z 的工作频率下，平均每次k p 运算的时间为1 5 1 5 m s 。该芯片可以支持 ms 2 5 6 的f 1 ，域上任意可变曲线的e c c 公钥密码算法，是一种系统参数可选择 的高速椭圆曲线密码芯片。 关键词：椭圆曲线，e c c ，密码系统，f p g a 武汉理工大学硕士学位论文 w i t ht h er a p i dd e v e l o p m e n to ft h ec o m p u t i n gs p e e do fc o m p u t e ra n dt h ep o w e r o fi n t e r n e td i s t r i b u t e dc a l c u l a t i n g , s o m ec l a s s i c a lc i p h e r s y s t e ms u c ha sr s a , d i f f i e h e l l m a n e t ca r em o r ea n dm o r ei n s e c u r ew h e nt h el e n g t ho fc r y p t o g r a p h i ck e y l e s st h a n5 1 2b i t t h o u 曲l e n g t h e nc r y p t o g r a p h i ck e ym a ye n h a n c es e c u f i t y e n c r y p t w i l lb em o r ea n dm o r ei n e f f i c i e n c y , i na d d i t i o nt h ed e m a n df o rs y s t e mi n c r e a s i n g l y h i g h e r h e n c e ，e l l i p t i cc u r v ec r y p t o s y s t e m ( e c c ) h a se x h i b i t si t sa d v a n t a g ef u l l yi n “s h o r tc r y p t o g r a p h i ck e y ”e c ct e n dt os u b s t i t u t er s aa st h eu n i v e r s a lp u b l i ck e y c r y p t o g r a p h i cs y s t e m 。 t h i st h e s i sa n a l y z e de l l i p t i cc u r v ec r y p t o s y s t e ma l o n gw i t ht h ea r i t h m e t i cb a s e o fe l l i p t i cc u r v ea n ds t u d i e dt h em a t e r i a la l g o r i t h m sf o rf p g ai m p l e m e n t a t i o no f e l l i p t i cc u r v ec r y p t o s y s t e mi nd e t a i l s 1w i l lp r e s e n taf e a s i b l es c h e m ef o rh a r d w a r e i m p l e m e n t a t i o no fe l l i p t i cc u r v ec r y p t o g r a p h i cs y s t e m am i x e dp a r a l l e l - s e r i a lm u l t i p l y i n gu n i ti sd e s i g n e d ，w h i c hm a k e st h ea r e aa n d t h ev e l o c i t yo ft h ec a l c u l a t i o no fm u l t i ! c l l i c a t i o nm a t c hb e s t e x t e n d e de u c l i d e a n a l g o r i t h mi ss e l e c t e dt or e a l i z ei n v e r s i o nf r o mt h es t a n d p o i n to fs a v i n gt i m e s o m e f a s ta l g o r i t h m si na l l u s i o nt og i v e ne l l i p t i cc u r v ea r ea b a n d o n e dc o n s i d e r i n gd i v e r s i t y o fe l l i p t i cc u r v ec r y p t o s y s t e m f o u rt y p e so ft h ep o i n tm u l t i p l i c a t i o na l g o r i t h m sa r ea n a l y z e di nt h i st h e s i s c o n s i d e r i n gt h ec h a r a c t e r i s t i c so fs u b j a c e n to p e r a t i o n ，i ti sc o n c l u d e dt h a tt h e m o n t g o m e r ya l g o r i t h mi se a s i l yi m p l e m e n t e dw i t hh g a t h r o u g ht h ec o m p l e t ed e s i g ne n v i r o n m e n to fq u a r t u si i ，s u b j a c e n to p e r a t i o na n d p o i n tm u l t i p l i c a t i o no fe l l i p t i cc u r v ec r y p t o s y s t e ma r er e a l i z e db yv h d l t h e s e m o d u l e sa r et e s t e db yt h ee x a m p l e so fe l l i p t i cc u r v ei na n x ix 9 6 2a n dt h e r e c o r r e c t n e s sw a sp r o v e d t e s tr e s u l t ss h o wt h a tt h ep r o c e s s o rc a nw o r ko u tt h ew h o l ef l o wo fe l l i p t i c c u r v ec r y p t o s y s t e me f f e c t i v e l y c o m p u t i n gk pn e e d s1 5 1 5 m so nt h ea v e r a g er e s u l t i no p e r a t i n gf r e q u e n c yi sa b o u t2 0 m h z t h i sp r o c e s s o rt h a th a sc h o i c ep a r a m e t e ra n d h i g hs p e e dc a l la p p l yt od i s c r e t i o n a le l l i p t i cc u r v eb a s e do nf i n i t ef i e l d 凡w i t hm l e s st h a n2 5 6 k e yw o r d s ：e l l i p t i cc u r v e ，e c c ，c r y p t o g r a p h y , f p g a i i 武汉理t 大学硕士学位论文 1 1 课题概述 1 1 1 课题的题目及来源 第1 章绪论 课题的题目：椭圆曲线密码( e c c ) 算法的f p g a 实现及优化设计 课题来源： 科研预研究 1 1 2 课题研究的背景 密码学的研究与应用已有几千年的历史，但作为一门科学是2 0 世纪5 0 年 代才开始的。目前密码技术已经从外交和军事领域走向公开，且已发展成为一 门结合数学、计算机科学、电子与通信、微电子等技术的交叉学科，使用密码 技术不仅可以保证信息的机密性，而且可以保证信息的完整性和确定性，防止 信息被篡改、伪造和假冒。 s h a n n o n 于1 9 4 9 年提出了保密通信系统模型【l 】，见图1 1 。在图1 1 中，明 文x 被发送之前，发送者和接收者之间使用的密钥k 需要事先商定，这个密钥 经商定后必须严加保密。一般说来，系统的保密性不依赖于加密体制或算法的 保密( k e r c k h o f f 原则) ，而只依赖于密钥。也就是说加密和解密算法是公开的， 密码分析者可以知道算法与密文，但由于他并不知道密钥，因此仍难于将密文 还原为明文。 图1 1s h a n n o n 保密通信模型 武汉理工大学硕士学位论文 加密算法和解密算法所使用的参数称为加密密钥和解密密钥，两者可以相 同，也可以不同。根据蜜钥的特点可将密码算法分为两类：对称( 私钥) 密码 算法和公钥密码算法口1 。 私钥密码体制从加密模式上可分为序列密码和分组密码两大类。在对称加 密嘉统中，加密和解密采用相同的密钥。因为加解密密钥相同，需要通信的双 商必须选择和保存他们共同的密钥，各方必须信任对方不会将密钥泄密出去， 妻样才可以实现数据的机密性和完整性【3 】。 公钥密码算法又称非对称密钥算法、双钥密码算法。在公钥密码算法中， 加密密钥不同于解密密钥，加密密钥可以公之与众，谁都可以使用；解密密钥 只有解密人自己知道，必须保密。加密密钥和解密密钥分别称为公开密钥( 简 称公钥) 和秘密密钥( 简称私钥) 。 私钥密码算法的优点是加解密速度快，其缺点是：密钥的分发和管理非常 复杂，不适何在大型网络中应用；无法对信息发送人的身份进行认证并检验信 息的完整性，因而不能用于数字签名。公钥密码算法很好地解决了这两方面的 问题，并正在产生许多新的思想和方案1 4 1 。公钥密码算法与对称密码算法相比有 其不可取代的优势，然而它的运算量却十分浩大。在公钥密码算法中所需要的 计算量比一般的加密算法如d e s 计算量多几个幂的数量级。因此，公开密钥一 般用在仅有少量数据需要传输的情况下，如数字签名，传送对称密钥算法中的 密钥等。 自从1 9 7 6 年d i f f i e 和h e l l m a n 提出了公钥密码的概念以来，出现了很多的 公钥密码系统，所有的这些系统的安全性都依赖于各自所基于的数学问题。近 来，其中一些公钥系统已经遭到了破译，另有一些则被证明是难以实现的。目 前只有3 种类型的系统被认为是安全和有效的。根据其依赖的数学问题，可将 这些系统分为f 5 l ： ( 1 ) 整数因数分解问题( i f p ) ：如r s a 和r a b i n w i l l i a m s 。 ( 2 ) 离散对数问题( d l p ) ：如美国政府数字签名算法( d s a ) ，d i f f i e h e l l m a n 和m q v 密钥交换方案，e 1 g a m a l 加密和签名方案，s c h n o r r 和n y b e r g r u e p p e l 签名方案。 ( 3 ) 椭圆曲线离散对数问题( e c d l p ) ：如椭圆曲线d s a ( e c d s a ) ，椭圆 曲线版本的d i f f i e - h e l l m a n 和m q v 密钥交换方案，e 1 g a m a l 加密和签名方案， s c h n o r r 和n y b e r g r u e p p e l 签名方案。 2 武汉理工大学硕士学位论文 以上问题都没有被证明是难解的，然而经过全世界数学和计算机科学家长 年的细致研究，并没有发现有效的快速算法去解决它们。通过越来越多的研究 和使用它们，使我们对其相应的密码系统的安全性有了更多的信心。 椭圆曲线密码系统( e c c ) 1 6 1 1 7 1 在1 9 8 5 年分别由v i c t o rm i l l e r 和n e a lk o b l i t z 独立提出。但在当时，他们都认为e c c 的概念仅是数学范畴的，而其实际实现 是不现实的。从1 9 8 5 年以来，e c c 受到全世界密码学家、数学家和计算机科学 家的密切关注。一方面，由于没有发现e c c 明显的漏洞，使人们充分相信其安 全性；另方面，在增加e c c 系统的实现效率上取得了长足的进步，到今日e c c 不仅可被实现，而且成为已知的效率最高的公钥密码系统。 e c c 相对于r s a 和d s a 等系统吸引人的最主要的原因是解决其数学问题 ( 即e c d l p ) 的已知的最好的算法也要用完全指数时问。与之相比，r s a 和 d s a 所基于的数学问题( 即因数分解i f p 和离散对数d l p 问题) 都有亚指数时 间算法。这意味着随着长度的增加，求解e c d l p 的难度比求解i f p 和d l p 的 难度增加得快得多。因此e c c 仅需要更小的密钥长度就可以提供跟r s a 和d s a 相当的安全性。 表1 1 具有相同安全强度的e c c 和r s a d s a 的密钥长度 r s a d s a 密钥长度( b i t s )e c c 密钥长度( b i t s ) 5 1 21 0 6 7 6 81 3 2 1 0 2 41 6 0 2 0 4 8 2 1 0 2 1 0 0 06 0 0 加密算法的安全性能一般通过该算法的抗攻击强度来反映。e c c 和其他几 种公钥系统相比，其抗攻击性具有绝对的优势。以当前应用最为广泛的公钥系 统r s a 为例，r s a 方法的优点主要在于原理简单，易于使用。但是，随着整数 因子分解方法的不断完善、计算帆速度的提高以及计算机网络的发展，作为r s a 加解密安全保障的大整数要求越来越大。要保证r s a 使用的安全性，就要相应 地增加其密钥的位数，目前一般认为r s a 需要1 0 2 4 位以上的字长才有安全保障。 但是，密钥长度的增加导致了其加解密的速度大大降低，硬件实现也变得越来 越困难，这对使用r s a 的应用带来了很重的负担，从而使得其应用范围越来越 受到制约。而椭圆曲线则具有较短的密钥长度，例如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 位r s a 、d s a 具有 相同的安全强度，这就意味着带宽要求更低，所占的存储空间更小。这些优点 在一些对于带宽、处理器能力、能量或存储有限制的应用中显得尤为重要。这 些应用包括：i c 卡、电子商务、w e b 服务器、移动电话和寻呼机等。表1 1 州给 出了在相同的安全条件下，e c c 和r s a d s a 的密钥长度。 1 1 3 课题研究的目的及意义 信息安全已成为人们在信息空间中生存与发展的重要保证条件，著名未来 学家托夫勒曾说过，在信息时代“谁掌握了信息，控制了网络，谁就将拥有整 个世界”。因此，密码学和信息安全技术在最近二十多年来，越来越受到人们的 重视，特别是“9 1 1 ”事件以来，信息安全业已成为各国政府和有关部门、企业、 机构的重要议事内容。 随着在有限域上的离散对数问题和因子分解上不断进步、计算机运算速度 的提高和计算机网络的发展，为了达到安全要求，大多数公钥密码体制的密钥 也越来越大，传统的软件加解密方式已经难以满足要求。要满足上百兆到上千 兆的加密速率，必须采用硬件实现。与软件加密相比，硬件加密具有加密速度 快、性能好等优势，并且便于物理保护，安全性好【9 】。因此，研究本课题有非常 迫切的现实意义。 与此同时，电子设计自动化技术( e d a ) 的发展使得电子工程师们在实验 室里就能设计出合适的a s i c 芯片，并且能立即投入实际应用之中。有人预言： “未来的v l s l 设计者是科学家而不是工程师”。意思是说未来的e d a 工具将高 度自动化，设计者重点是概念设计，而大部分工程实践中的技术问题都可以依 靠e d a 工具解决0 】。研究本课题还可以将c p l d f p g a 等e d a 器件以及v h d l 等e d a 工具应用于实际系统，从而掌握使用e d a 技术开发a s i c 的方法。 1 2e c c 芯片研究的现状 椭圆曲线密码算法( e c c ) 是一种非常复杂的数学算法，设计出能够完整实 现e c c 算法的专用集成电路芯片( a s i c ) 非常困难。当前，对e c c 的研究主 要集中在e c c 的实现方面，尤其是e c c 的芯片集成引人关注。 4 武汉理t 大学硕十学位论文 采用硬件方式实现e c c 的报道最早见于文献1 1 1 。文献【1 l 】构造了一块专门 用于执行有限域只。上乘法运算的v l s i 芯片，然后再利用一个高效的可编程控 制器实现了基于只。上的e c c 。利用这一芯片，加密速度大致可以达到4 0 k b s ， 换算为签名速度大约是1 3 0 次每秒。 2 0 0 1 年，德国的i n f i m e o m 公司推出了一款安全芯片，产品型号为 s l e 6 6 c 4 2 f 。它使用了一个1 6 位的安全控制器，具有数据加密标准( d e s ) 和 三重d e s 算法( 3 d e s ) 的对称n 解密功能和实现椭圆曲线数字签名算法的 ( e c d s a ) 的功能。对椭圆曲线数字签名算法，它只能对定义在f 。，m ；1 9 2 上 的椭圆曲线有效。在5 m h z 的工作频率下，完成一次签名的产生所需的时间是 2 8 5 m s ，完成一次签名验证所需的时问是5 4 0 m s 。在1 0 m h z 的工作频率下，完 成一次签名的产生所需要的时间是1 4 2 m s ，完成一次签名验证所需的时间是 2 7 0 m s 。 2 0 0 1 年，m o t o r o l a 公司推出了一款多功能安全处理器，型号为m p c i 8 0 。 这是一款功能上几乎做到了包罗万象的芯片，主要是为了实现网络安全( i p s e c ) 协议而为客户端用户所设计。该芯片具有实现d e s 、3 d e s 、r c 4 、d m 4 、m d 5 、 s h a 1 、r s a 、e c c 和随机数产生等算法功能。关于e c c 算法功能，m p c i 8 0 芯片可以同时兼容素数域曲线和特征2 域曲线。对素数域情况，只要求定义曲 线的素数域e 中的素数p 是一个规模在6 4 比特到5 1 2 比特之间的素数即可。对 特征2 域情况，也只要求定义曲线的有限域f 中的m 是一个规模在6 4 到5 1 2 之间的数即可。对两种情况下的椭圆曲线，芯片没有提供任何完整的密码算法 或密码协议的实现，只提供了标量乘法的计算功能和计算椭圆曲线上点加p + q 和计算倍点2 p 的功能 ”】。 我国密码芯片的设计和生产还远远滞后于系统和网络的发展需求，特别在 高速度密码芯片方面与发达国家还有十分明显的差距。国内对e c c 的芯片集成 的研究起步较晚，但近几年来的发展比较迅速，目前已经有正式的产品面世。 例如上海微科集成电路有限公司于2 0 0 4 年1 2 月1 5 宣布开发成功的r s a e c c 二合一密码算法协处理器芯片。该芯片最多可以完成2 5 6 比特的e c c 运算，每 秒至少可以完成1 0 0 次e c c 点乘运算。 武汉理工大学硕士学位论文 1 3 课题研究的内容 本课题的研究内容主要包括一下三个方面： ( 1 ) 深入研究e c c 体制及其快速算法。椭圆曲线密码算法中可以用硬件实现 的算法很多，但硬件实现必须考虑到面积问题，因为他们分别设计各自的运算 单元会使面积很大。因此，为了得到较快的加、解密速度和较小的芯片面积， 必须对这些基本算法进行优化。 ( 2 ) e c c 算法中的基本运算的硬件实现。以f p g a 为载体完成椭圆曲线上加 法、乘法、平方和求逆运算的功能。 ( 3 ) 芯片结构的优化。结合f p g a 器件本身特点以及所用算法的特点，对系 统各个运算部件和整个系统进行优化设计。 武汉理：人学硕士学1 1 ) = 论文 第2 章椭圆曲线公钥密码的理论基础 椭圆血线有丰富的数学结构，这使得它在公钥密码系统中有广泛的应用。 本章将结合椭圆曲线密码算法的数学基础对椭圆曲线密码体制进行分析，然后 对椭圆曲线算法硬件实现的载体f p g a 器件的设计流程进行介绍。 2 1 有限域 有限域是1 8 3 2 年g a l o i s 引进的，g a l o i s 为了探讨一元高次方程能否用四则 运算和开方求解，他创造了著名的g a l o i s 理论，在这个理论中他引进了群和域 这两个概念，有限域就是他作为域的例子而举出来的。自上个世纪八十年代以 来，人们已经利用有限域构造出多种公钥密码体制【1 3 l 。本节将介绍在公钥密码学 中经常用到的有限域e 和有限域只，【1 4 j 。 在本论文一下的论述中，q = p ，p 是素数，或q = 2 “，m 1 。 2 1 1 有限域只 有限域e 由整数集合 o ，1 ，2 ，p 一1 组成，每个这样的整数可以用一个 长度恰为f = f l o g ：p 1 ( 其中r x l 表示不小于x 的最小整数) 的二进制表示，该表 示由整数的二进制表示几在其左边添加适当个数的0 组成。只中元素具有以下 算术运算： 加法如果a ，b 只，则a + b = r ，其中r 是a + 6 被p 除所得的剩余， 0 ers p 一1 ： 乘法 如果口，b 巴，则日b = 5 ，其中s 是口b 被p 除所得的剩余， 0 sss p 一1 ： 令巧表示中所有非零元素，可证明在f p 中至少存在一个元素g ，使得 中任意非零元素可以表示成g 的方幂，这样的元素g 称为e 的生成元( 或本原 元) ，即 ，：= g ：0 s is p 一2 武汉理工大学硕士学位论文 口= g e 的乘法逆是 三；占? ；g ( 一j ) m d ( p 一1 一 a 2 1 2 有限域f 2 。 有限域只。包含2 ”个元素，这罩2 是只的特征，而m 是f 1 。在它的素域b 上的次数。 构造元素个数为素数方幂的有限域的方法有很多，其中最直观的方法是利 用多项式的加、乘、除和剩余来构造有限域f 。 令f ( x ) = x “+ ，m 1 x ”1 + + 厶z 2 + ，l 算+ f o ( l e ，0 s fs m 一1 ) 是巴上次 数为m 的不可约多项式，即，0 ) 不能分解为e 上两个次数小于m 的多项式的 积。有限域只由f 上所有次数小于m 的多项式组成，即 f 一盲 口卅_ 1 z ”- 1 + a m _ 2 x 4 2 + + 口l x + a o ：a i 0 ，1 域元素( a m _ i x ”1 + 口。一2 x ”2 + + n l z + 口o ) 通常用长度为m 的二进制串 ( 口。一1 口。一2 d 1 口o ) 表示，使得 只。= 0 a 。一2 口1 口o ) ：a f 0 ，1 因此，只中的元素可以用所有长度为m 的二进制串的集合来表示。 域元素的加、乘法运算如下： 域由口法 ( a m _ l a 。一2 n l n o ) + ( k 1 b 。一2 b i b o ) = ( c m - 1 c m _ 2 c l c o ) ，其中c 。= ( n 。+ 抚) m o d 2 ，即域加法是按分量方式进行的； 域乘法 ( 口。a 。一：口。4 。) ( k 一，k 一：b l b o ) 一( r 刖一，k 一：f i r o ) ，其中多项式 ( k - 1 x “- 1 + 一2 z “一2 + + ，1 z + ) 是多项式( 口，一1 工“_ 1 + 口。一2 x “一2 + + 以1 x + n o ) 乘 以( k 一。x “+ k 一：石”2 + + 岛z + ) 在，2 上被， ) 除所得的剩余。 这种表示f 。的方法称为多项式基表示法。这里的域乘法运算可以看作是模 f ( x ) 意义下的多项式乘法。 可以证明至少存在一个元素g f ，使得只，中任何一个非零元素都可以表 示成g 的一个方幂。这样的元素g 成为只。的生成元( 或本原元) 。即 f 二一 g ：0 s is2 ”一2 a = g ，二的乘法逆是 三鲁占。；g ( 一i ) - ，l 。d ( 2 ”一1 ) 武汉理工大学硕士学位论文 一般地，域只，可以表示成b 上一个维数为m 的向量空间，也即只，中存在 一个由m 个元素口。，a 。，口。组成的集合，使得每个a f 。可以唯一写成如下 形式，即 a = 口0 a 0 + a l l 】1 + + n 一l a m 一1 其中a f o ，1 。可以将a 表示成0 ，l 向量0 口，a l ，a r a _ 2 a 。) 。 c 。在f 2 上有很多不同的基。对于一个m 次不可约多项式厂 ) ，如果f ( x ) 的 m 个根成，芦1 - ，卢。在f 2 上线性无关，那么这研个根显然构成t 。在艺上的一 组基。作为， ) 的m 个共轭根，它们可以写成某一个根卢的幂次，即 卢。= 声，卢。= 卢2 ，卢：= 卢r ，p 。一。= 芦寸。通常把形如( 卢，卢2 ，卢。，卢2 ”1 ) 的基 称为正规基【1 6 1 。理论上已经证明这样的基总存在。 2 2 椭圆曲线 2 2 1 椭圆曲线的定义 椭圆曲线的研究来源于椭圆积分，如下式【1 7 1 ： 陲 o e ) 这里e 0 ) 是x 的二次多项式或四次多项式。这样的积分不能用初等函数来 表达，为此引入了所谓的椭圆函数。所谓椭圆曲线是指由韦尔斯特拉斯 ( w e i e r s t r a s s ) 方程( 如下式) 所确立的平面曲线： y 2 + a i x y + a 3 y 鲁x 3 + a 2 x 2 + a 4 x + 口6 ( 2 1 ) 若f 是一个域，其中a f f ，i = l 2 ，6 ，满足w e i e r s t r a s s 方程的数b ，y ) 称 为域f 上椭圆曲线e 的点。f 可以是有理数域，也可以是复数域，还可以是有 限域。除了曲线e 上的所有点外，还需要加上一个特殊的无穷远点d 。 令表示q 个元素的有限域，q = p ，p 是素数，z 1 ，令e ( ) 表示定义 在c 上的一个椭圆曲线。 定理2 1 ( h a s s e 定理) 令e ( ) 是定义在有限域上的椭圆曲线，e ( c ) 的点数用社e ( e ) 表示，则 l 撑( ) 一q qs2 4 q 定理2 2 对任意i t is2 矗，t * 0 m o d p ) ，存在e 上的椭圆曲线e ，使得 9 武汉理工大学硕士学位论文 # e ( 兄) ；q + 1 一t 。 2 2 2 椭圆曲线上的基本运算 ( 1 ) 只上的椭圆曲线 令p ，3 是一个素数，口，b e t 满足钇3 + 2 7 b 2 0 ( m o d p ) ，由参数a 和6 定 义的只上的一个椭圆曲线是方程 y 2 = x 3 + 甜+ b ( 2 2 ) 的所有解0 ，y ) ，z c ，y e c ，连同一个称为“无穷远点”( 记为o ) 的元素 组成的点集合。e ( l ) 的点数用舟占( 只) 表示。由h a s s e 定理可知 p + 1 2 x ps 撑e ( ，：) s p + 1 + 2 4 p 点集合e ( 疋) 对应下面的加法规则构成一个群。 在本节及以后表述中p ( x l ，y ，) 平r l q ( x ：，y ：) 表示e ( 只) 上的点，d 表示e 上的 无穷远点，表示p q 的连线。 1 1d + o o ； 2 ) o + p = p 并r e + o ；p ； 3 ) 如果p = ，y 1 ) o ，一p - ，- y 。) ，p + ( 一p ) 一o ( 即点0 ，y ) 的逆为 ，一y ) ) ； 4 ) 若尸和q 是满足而，z ：的点，则直线l = p q 与椭圆曲线有且仅有第三 个交点r ，定义尸+ q = 一r 。令一r 一 ，y ，) ，则有： 卜。a 2 - - x 1 - x 2( 2 3 ) l y 3 = z ( x 1 一z 3 ) 一y 1 其中a ：必。 茗2 一x 1 5 ) 若p ；a ，y ，* 0 ，令l 为椭圆曲线上点p 的切线，l 与椭圆曲线有且仅 有第二个交点r ，则p + a = 2 p = - r 。令一r = ，y ，) ，则有： j 而钌一2 x 1( 2 4 )、二斗 i y 3 ；z ( x 1 一x 3 ) 一y 1 其中a ：垡塑。 2 y 1 群e ( ) 是a b e l 群，即对e ( ) 中的所有点p 和a ，p + qa a + p 。如果 社e ( 疋) = p + 1 ，曲线就称为是奇异的，否则称为是非奇异的。 1 0 武汉理工人学硕士学位论文 ( 2 ) 上的椭圆曲线 f 2 ，上由参数n ，6 e 易，b * o 定义的一个非超奇异椭圆曲线e ( ) 是方程 y2 + x y = 工3 + 甜2 + b ( 2 5 ) 的解集合x ，y ) ，x f ，。，y 只，连同一个称为“无穷远点”( 记为0 ) 的元素 组成的点集合。( 一，) 的点数用撑( 只。) 表示。由h a s s e 定理可知 q + 1 2 目s 群e ( f 2 ，) s q + 1 + 2 4 q 其中口= 2 ”。进一步有：样( l ) 是偶数。 点集合e ( 只) 对应下面的加法规则构成一个群，即 1 ) o + o = o ； 2 ) o + p = p 并且p + o = p ； 3 ) 如果p = 。，m ) _ o ，一p = 0 l ，x 1 + y 1 ) ，p + ( 一p ) = o ( 即点0 ，y ) 的逆 为0 ，x + y ) ) ； 4 ) 若p 和q 是满足善。x ：的点，则直线l = p q 与椭圆曲线有且仅有第三 个交点r ，定义p + q 一r 。令一r 一，y ，) ，则有： i x s 。a 2 + a + j ，+ x ：+ 4(26)x i 二uj i ，3 一( x 1 + z 3 ) + 石3 + y 1 、 7 其中a 。丝! ! 。 石2 + 茗1 5 ) 若p q ，x ，0 ，令为椭圆曲线上点p 的切线，与椭圆曲线有且仅 有第二个交点r ，则p + q 2 p r 。令一r = o ，y ，) ，则有： j z 3 = a i + + 4 ( 2 7 ) l y 32 x 卜 + 1 ) x 3 其中a = z ，+ 丛。 4 群e ( f 2 ) 是a b e l 群，也即尸+ q q + p 对e ( t 。) 中的所有点p 和q 都成 立。 一次加法运算通常需要八次加法、两次乘法、一次平方、三次模域多项式 丁0 ) 的约简和一次求逆；一次倍点运算通常需要四次加法、两次乘法、两次平 方、四次模域多项式r ( u ) 的约简和一次求逆。椭圆曲线点加法的运算时间主要 耗费在乘法和求逆e 。 武汉理丁大学硕士学位论文 2 3 椭圆曲线密码系统简介 给定有限域和定义在有限域上的椭圆曲线e ( ) ，对于已知椭圆上的 点p ，求qz k p ( 舻称为椭圆曲线上的点乘，即k 个p 在椭圆曲线上的点乘运 算) 很容易，但是反过来在已知p 和q 的情况下求k 却非常困难。该问题被称为 椭圆曲线上的离散对数问题( e c d l p ) ，椭圆曲线公钥密码系统的安全性就是基 于椭圆曲线离散对数闯题的难解性。 2 3 1 系统的建立 椭圆曲线密码系统必须选用安全的椭圆曲线，否则整个系统都是不安全的。 所谓的安全曲线是指能抗各种已有攻击的曲线，目前对椭圆曲线攻击比较有效 的方法有m o v 攻击、s m a r t 方法、p o l l a r d p 方法等。为抵抗上述攻击，有限域 e 上的椭圆曲线e ( e ) 应满足： ( 1 ) 椭圆曲线群的阶( 即有限域内满足椭圆曲线的点数) 撑e ( e ) 有大于2 “ 且大于4 、肠的素数因子； ( 2 ) e ( e ) 不是超奇异曲线或反常曲线，这两类曲线在所有的椭圆曲线公钥 密码的标准中都被指定禁止使用。 构成一个椭圆曲线密码系统所需要的参数集称为椭圆曲线域参数，包括： 有限域只，椭圆曲线e ，基点g ( 椭圆曲线e 上的一个点) ，基点的阶尼( 使得 n p = 0 的最小正整数，最好是素数) ，椭圆曲线群的阶# f 4 f ，相关因子。o ) h 椭圆曲线的域参数是公开信息。 如果选择的有限域是素数域只，则椭圆曲线参数域是一个六元的参数组 p ，口，b ，g ，n ， ) 。其中p 决定有限域，口，b 决定椭圆曲线，g 表示基点，”是g 的阶，h 表示椭圆曲线群的阶与n 的商。 如果选择有限域是特征为2 的有限域l ，则椭圆曲线参数域是一个七元组 m ，f ( x ) ，口，b ，g ，n ，h ) ，其中：m 是有限域的尺寸，( x ) 是域中的多项式，n ，b 决定椭圆曲线，g 表示基点，r l 是g 的阶，h 表示椭圆曲线群的阶与，l 的商。 2 3 ，2 密钥的产生 系统建立以后，每个使用者( 简称实体) 执行以下计算： 壁坚望兰叁堂堡主堂堡丝苎 1 ) 在区间【1 ，”一1 】中随机选取一个整数d 2 ) 计算点a = d g ； 3 1 实体的公钥包含点q ； 4 ) 实体的私钥是整数d ； 2 - 3 3 椭圆曲线加密体制( e c e s ) 当实体b 发送信息m 给实体a 时，实体b 执行如下加密步骤： 1 ) 实体b 去查找公钥库p k d b ，查到a 的公钥q j ； 2 ) 将肘划分为较小的数据块，m = 枷1 ，m 2 ，m ) ，其中0 s s n ； 3 ) 在区间b n 一1 上选择- - 个随机数七； 4 ) 计算点置 ，y ，) ；k g ； 5 ) 计算点x ： ：，y ：) = k o a ，如果工：= 0 ，则回到第3 步： 6 ) 计算c = n q x 2 ； 7 ) 传送加密数据 ，y ，c ) 给a 。 实体a 接收到从b 发来的密文 ，y ，c ) 时，执行如下的解密步骤： 1 ) 使用他的私钥d 。，计算点x ：d 。x ，= d a ( k c ) = k ( d 。g ) = 七q 一；x z 2 1 通过计算扰= “i 1 ，恢复出数据m 。 2 3 4 椭圆曲线数字答名体制( e c d s a ) 当实体a 为实体b 签名信息m 时，a 执行下列步骤生成e c d s a 签名： 1 1 将信息m 表示成二进制串： 2 ) 使用一个h a s h 函数计算h a s h 值e 一( m ) ； 3 ) 在区间b ”一1 】内选取一个随机数k ； 4 ) 计算点瓴，y 1 ) = k g 并设r x l m o d n ； 5 1 利用私钥d ，计算s k 。忙+ r d ) m o d n ； 6 1a 传送给b 信息m 和它的签名( r ，s ) 。 注意当r ；0 或s 。0 则签名验证失败。可是，如果j j 是随机选取的，则r = 0 或s ；0 的概率非常之小可以忽略不计。 当实体b 验证a 对信息m 的签名( r ，5 ) 时，b 执行下列步骤对a 的签名进 行验证： 武汉理工大学硕士学位论文 1 1 查找a 的公钥q ： 2 1 如果r m o d n = ，则拒绝签名； 3 ) 计算值=0hash e 胃( m ) ； 4 ) 计算s m o d n ； 5 ) 计算“= s 1 e m o u r n 年口v = s 一1 r r o o d n ； 6 ) 计算点o l ，y 1 ) 一“g + v q ； 7 ) 接受a 对信息m 的签名当且仅当五m o d n ：，； 注意签名过程中h a s h 值e 模n 约简，因此，为保证安全，h a s h 函数日和n 的 选择应使得h m o d n 仍是一个密码安全的h a s h 函数。如果r ：0 ，则签名方程 s = k - 1 伯+ r d ) m o d n 就不包含私钥d 。出于安全需要，可以在生成签名的步骤( 4 ) 中强制，0 。 2 4 椭圆曲线密码算法实现的硬件基础 2 4 1f p g a 设计流程 现场可编程门阵列( f p g a ) 【1 q 是由掩膜可编程门阵列( m p g a ) 和可编程 逻辑器件二者演变而来的，并将它们的特性结合在起。因此f p g a 既有门阵 列的高逻辑密度和通用性，又有可编程器件的用户可编程特性。 f p g a 是9 0 年代才兴起的半定制集成电路，用户可以根据自己的需要在 f p g a 中设计自己的专用电路，用于完成特殊的功能。f p g a 基本的设计流程主 要包括电路设计与输入、功能仿真、设计综合、综合后仿真、布局布线、布线 后仿真和芯片测试等几个步骤。 电路设计与输入是根据工程师的设计方法将所设计的功能描述给e d a 软 件。设计输入主要有原理图输入和h d l 输入两种方式【”】，有些熟悉硬件设计的 工程师开始喜欢利用原理图进行设计，这种方法非常直观，但基于可移植性和 规范化方面的考虑，绝大部分深入f p g a 设计和a s i c 设计的工程师最终都将统 一到h d l 平台上来。 电路设计完成后，要用专用的仿真工具对设计进行功能仿真，验证电路功 能是否符合设计要求。功能仿真忽略了综合和布局布线导致的时延等因素，仅 仅从逻辑上进行仿真。这样可以及时发现设计中的错误，加快设计进度，提高 1 4 武汉理工大学硕士学位论文 设计的可靠性。 设计综合将h d l 语言生成用于布局布线的网表和相应的约束。综合效果直 接导致设计的性能和逻辑门的利用效率，因此，许多可编程逻辑器件开发商都 支持第三方综合和仿真工具。 综合完成后需要通过仿真来检查综合结果是否与设计要求一致。在仿真时， 把综合生成的延时文件反标到综合仿真模型中去，可估计延时带来的影响。 布局布线工具利用综合生成的网表，在f p g a 内部进行布局布线，并生成 可用于配置的比特流文件( 有了比特流文件就可下载到芯片里了1 。布局布线工 具与可编程逻辑器件工艺及其布线资源密切相关，一般由可编程逻辑器件开发 商直接提供。布线后必须通过时序仿真作进一步验证，发现并修正时序问题。 2 4 2v h d l 语言 硬件描述语言是e d a 技术的重要组成部分，v h d l2 0 1 是作为电子设计主流 的硬件描述语言。v h d l 的英文全名是v h s i c ( v e r yh i g hs p e e di n t e g r a t e d c i r c u i t ) h a r d w a r e d e s c r i p t i o n l a n g u a g e ，于1 9 8 3 年由美国国防部( d o d ) 发起 创建，由i e e e ( t h ei n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i c se n g i n e e r s ) 进一步发展 并在1 9 8 7 年作为“i e e e 标准1 0 7 6 ”发布。从此，v h d l 成为硬件描述语言的 业界标准之一。自i e e e 公布了v h d l 的标准版本( i e e es