（电路与系统专业论文）椭圆曲线加密算法的异步电路硬件实现.pdf

论文摘要 论文摘要b 8 5 6 8 2 自从出现了电子通信，通信的安全性就一直成为人们关心的焦点。保证安全 性最有效的方法就是对源数据进行替换，使得攻击者很难从现有数据中破译出原有 的信息。密码学经过多年的发展，公钥加密算法( p u b l i c k e y c r y p t o s y s t e m ，p k c ) 目前 正受到越来越多的人的青睐。当今电子银行和电子商务已经非常盛行，在这类交易 中经常需要用到数据加密并且需要数字签名来确认身份，这些功能都可以由公钥加 密算法来实现的，然而加密算法的运算复杂性却限制了其在更广泛的领域应用的可 能。 现代公钥加密算法主要基于以下三个数学难题：大整数分解难题、离散对数 难题和椭圆曲线上的离散对数阀题。几乎所有的研究都表明，基于椭圆曲线离散对 数难题的椭圆曲线加密算法( e l l i p t i cc u ec r y p t o s y s t e m ，e c c ) 在实现时所需占用的 资源是最少的。这是因为在相同的安全度下。椭圆曲线加密算法的密钥最短。因此 我们对此进行研究是有现实意义的。 本论文为椭圆加密算法的v l s i 实现提供了一种新的解决方案，并且用 v e r i l o g 语言对整个设计方案进行了硬件描述以验证该方案的正确性。在该设计中 最主要也是最耗时间的运算是基于椭圆曲线的有限域乘法运算l 一，为此我们设计 了专用的乘法器来提高运算速度，由仿真结果可知，该乘法器的性能要好于其他基 于迦罗华域的通用乘法器。本设计中还运用了新的结构来实现e c c 的点加和倍点 运算的调度，使得他比传统的d o u b l e - a n d - a d d 算法所使用更少的迭代周期。 此外，异步逻辑的使用是本设计的另一个亮点。由于没有全局时钟，异步芯 片的功耗大大降低，时钟偏移的问题也随之消失，因此芯片的性能大大提高。 关键词：椭圆加密系统密码学 低功耗设计异步电路设计模乘 有限域整数基多项式基 a b s t r a c t a b s t r a c t s i n c et h ea d v e n to fe l e c t r o n i cc o m m u n i c a t i o n st h e r eh a sb e e nan e e dt os e c u l i n f o r m a t i o nf r o mt h ep r y i n ge y e so fa l la d v e r s a r y t h em o s te f f e c t i v ew a vt od ot h i sh a s b e e nt h r o u g hs o m ef o n t io fe n c r y p f i o nt os c r a m b l e 也eo r i g i n a lm e s s a g es ot h a ti ti s e x c e e d i n g l yh a r dt ou n s c r a m b l ei n t oi t so r i g i n a lc o n t e n t s w i t ht h ed e v e l o p m e n to ft h e e n c r y p t i o nt e c i m e l e g yo ft h e s ey e a r s ，t h eu s eo fp u b l i c - k e yc r y p t o s y s t e m ( p k c ) h a s r e c e i v e dc o n s i d e r a b l ea t t e n t i o n t h e ya r eb e n e f i c i a li nd a t ae n c r y p t i o na sw e l la sd i g i t a l s i g n a t u r et h a tp l a y a l le s s e n t i a lr o l ei ne t e e t r o n i cb a n k i n ga n df i n a n c i a lt r a n s a c t i o n s t h e c o m p u t a t i o n a lc o s to fe n e r y p t i o ni s ab a r r i e rt ow i d e ra p p l i c a t i o no fav a r i e t yo fd a t a s e c u r i t yp r o t o c o l s c u r r e n tp u b l i ck e y a i g o r i t h mi sb a s e do nt h r e ea r i t h m e t i cd i f f i c u l t i e s ：i n t e g e r f a c t o r i z a t i o n ，d i s c r e t el o g a r i t h ma n de l t i p t i eg u l - v eb a s e ds c h e m e s v i r t u a l l ya l lr e s e a r c h o ne l l i p t i cc u r v ec r y p t o s y s t e mo i c c ) w h i c hi sb a s e do n e l l i p t i c c u r v el o g a r i t h m s c h e m e sp m v i d e se v i d e n c et o s u g g e s tt h a te c c c a np r o v i d eaf a m i l yo fe n e r y p t i o n a l g o r i t h m st h a tr e q u i r ef e w e rc o m p u t a t i o n a lr e s o u r c e sf o ri m p l e m e n t a t i o nt h a td oc u r r e n t w i d e l yu s e dm e t h o d s t h i se f f i c i e n c yi so b t a i n e ds i n c ee c c a l l o w sm u c hs h o r t e rk e y l e n g t h sf o rc q u i v u l e a a tl e v e l so f s e c u r i t y i nt h i s p a p e r , w ep r o p o s en e wm e t h o d sf o rc a l c u l a t i n gf a s tv l s ia r i t h m e t i c a l g o r i t h m sf o rs e c l n 世d a t ae n c r y p t i o na n dd e c r y p t i o ni nt h ee c c ，a n da l s ov e r i f yt h e p r o o f - o f - c o n c e p t sb yn u m e r i c a le x p r e s s i o n sa n dt h r 0 1 【g ht h eu s eo fv e r i l o gh d l w e h a v e d e v e l o p e daf a s tf i n i t ef i e l dm u l t i p l i e rt h a tu t i l i z e san e wc o n e tw i t ha ni m p r o v e d i n t e m a ls t r u c t u r e ，a sw e l la sn o v e lf a s ta l g o r i t h mf o rc a l c u l a t i n gk p ，w h i c hi st h em o s t t i m e - c o n s u m i n go p e r a t i o ni nt h ee c c d a t ac n e r y p t i o ns c h e m e t h ep r o p o s e dm u l t i p l i e r f e a t u r e sah i g h e rt h r o u g h p u tp e rc o s tr a t i nt h a na n yo t h e ro r d i n a r yg a l o i sf i e l d ( g n m u l t i p l i e rt h a tc a l lb eu s e di nt h el a r g ep r i n l cf i n i t e6 e l d t h ed e v e l o p e da l g o r i t h mf o r p o i n tm u l t i p l i c a t i o nd e c r e a s e st h es t e p sm q u l r e df o ri t e r a t i o nb y h a l lc o m p a r e dt ot h a to f t h et r a d i t i o n a ld o u b l e - a n d - a d da l g o r i t h m t h eu s e o f a s y n c h r o n o u sl o g i ci sa n o t h e rh i g h l i g h t w i t h o u tg l o b a lc l o c kn e t w o r k , t h ep o w e r c o n s u m p t i o n o ft h ew h o l e c h i pd e c r e a s e d ，c l o c ks k e w i sa l s oa v o i d e d s ot h i s f e a t u r ec a nm a k ea b i g c o n t r i b u t i o nt ot h e c h i pp e r f o r m a n c e k e yw o r d s ：e l l i p t i cc u r v e ，e n c r y p t i o n ，n o m a lb a s i s ，p o l y n o m i a lb a s i s ，a s y n c h r o n o u s ， f i n i t ef i e l d s ，m o d u l a rr e d u c t i o n 前言 日l j舌 密码学从其诞生至今已经有几千年的历史。在当今的信息时代，大量的敏感 信息通过公共通信设施或计算机网络来进行交换，这些信息的秘密性和真实性是人 们迫切需要的，同时参与通信的各方的身份也必须进行实时验证，这对密码学的发 展提出了新的要求。 当前最流行的公钥加密算法在1 9 7 6 年由d i f f i e 和h e l l m a n 首次提出。他们 发表的“密码学的新方向”一文首次证明了在发送端和接收端无密钥传输的保密信 息是可能的，从而开创了公钥密码学的新纪元。目前的公钥密码系统主要依赖下面 三种数学难题：大整数因子分解问题、离散对数问题、椭圆曲线上的离散对数问 题。本文所讨论的公钥系统是建立在椭圆曲线离教对数闯题上的密码系统，称为椭 圆曲线密码系统e c c ( e l f i p f i cc u r v ec r y p t o s y s t e m ) 。与另外两种公钥加密系统相 比，e c c 具有密钥长度短、加解密速度快。盟主士簋强接要求低以及需要通信时对 带宽要求低等特点。所以近年来e c c 被广泛应用于商用密码领域。 殖着半导体制造工艺的发展，作为目前数字集成电路主流的同步电路在设计 过程中遇到越来越多的挑战，其中最主要的是功耗问题和时钟偏移问题。异步电路 由于没有全局时钟，所以在解决上述问题中有着同步电路所不具备的优势。 本文深入研究了椭圆加密算法，并用异步电路的方法进行v l s i 实现。e c c 的核心运算涉及宽比特有限域上的加法、乘法、平方、除法、求模以及这些运算的 复杂组合。对于m 为素数的g f ( 2 “) 域的e c c 的实现研究，目前国际上公开报导 的文献非常少，本文对e c c 加密算法的硬件实现提供了一种有效的方案。 本文e c c 加密算法的实现基于非超级奇异曲线和g f ( 2 2 6 3 ) 域。该椭圆加密 系统的密钥长度为2 6 3 位，整个芯片完成参数读入、e c c 运算、计算结果输出， 而密钥的产生在片外进行。为了降低计算的复杂度，整个运算在投影坐标系 ( p r o j e c t i v ec o o r d i n a t e s ) 下进行，将复杂的群运算转化成宽比特整数的加法、乘法、 平方运算。整个系统用v o r i l o g 语言进行描述，并且在c s m c 0 6 u m 的工艺库上进 行了逻辑综合，完成了门级时序仿真。其仿真结果表明，采用这样的体系结构设计 出的电路完全可以满足一秒钟十次e c c 运算的计算量；与此同时，控制模块、运 算模块以及移位寄存器组等一共约三万门的规模是完全可以接受的。 本文分为以下六个部分： 第一章主要介绍了椭圆曲线加密算法的相关知识。本章首先介绍了密码学的 历史与现状，分析了公钥密码学在当今各领域的重要地位；然后比较详细地讨论了 椭圆加密算法所基于的数学模型，包括有限域及其运算规则、椭圆曲线和定义在椭 圆曲线上的加法运算；第三节还给出了e c c 加密算法的两个应用实例d i f f i e h d l m a n 密钥交换协议和e 1 g a m a l 密码体制；最后一节对e c c 的安全性进行了简 要的分析。 前言 第二章主要介绍了异步电路设计方法。这一章分析了当前集成电路设计中所 面临的难题，而异步电路由于其自身的特点可以对这些问题提供一些可行的解决方 案。文中详细讨论了异步逻辑最常用也是最有代表性的一些单元及其特点。 第三章主要介绍了异步e c c 芯片的系统结构。本章分别分析了异步e c c 芯 片中所用到的运算模块、存储模块和控制模块的体系结构，特别着重分析了核心模 块乘法器的结构。最后一节还对整个芯片的运算复杂度进行了分析，其结果表明该 体系结构还是可以满足设计要求的。 第四章主要介绍了异步e c c 各模块的电路实现。本章主要介绍了本设计中 所用到的几类异步电路专有的电路结构，包括c e l e m e n t 流水线、不同类型寄存器 组的门控时钟以及与运算模块配套的匹配延迟电路。这些电路与专用运算模块相配 合，使得系统可以正常工作。 第五章主要介绍了整个项目实现的过程以及仿真结果。本章的前半部分主要 介绍了芯片用v c r i l o g h d l 语言实现的全过程，给出了顶层的模块之间的接1 2 1 以及 各信号线的含义。本章的后半部分主要介绍了对系统进行仿真的情况，包括功能仿 真以及在c s m c 0 6 u m 工艺库上综合后进行时序仿真的结果。 第六章主要介绍了关于芯片测试方面的内容，特别着重分析了基于f p g a 的可重用测试系统的搭建。 蔓二兰塑璺! 堕兰堡堕尘 第一章椭圆加密算法简介 1 1 、密码学的历史及其现状 1 1 1 、密码学的发展阶段 密码学是一门古老而又年轻的科学，它用于保护军事和外交通信可追溯到几 千年前。在当今的信息时代，大量的敏感信息通过公共通信设施和计算机网络来进 行交换，而这些信息的秘密性和真实性是人们迫切需要的。因此，现代密码学对于 军事、政治和外交、商业的价值越来越重要。明文信息可以用两种办法之一来隐 藏：一是信息隐蔽，隐藏信息的存在，二是利用密码学方法通过对文本信息的不同 转换而实现信息的对外不可读。 密码学的发展历史大致可划分为三个阶段： 第一个阶段为从古代到1 9 4 9 年。这一时期可看作是科学密码学的前夜时期， 这段时期的密码技术可以说是一种艺术，而不是一种科学，密码学专家常常是凭借 着直觉和信念来进行密码设计和分析，而不是推理证明。例如，最早应用替代的恺 撒密码。 第二个阶段为从1 9 4 9 年到1 9 7 5 年。1 9 4 9 年s h a n n o n 发表的“保密系统的信 息理论”一文为对称密码系统建立了理论基础，从此密码学成为一门科学，人们将 此阶段使用的加密方法称为传统加密方法，其安全性依赖于密钥的秘密性，而不是 算法的秘密性，也就是说，使得基于密文和加解密算法的知识去解密一段信息在实 现上不可能。 1 9 7 7 年美国国家标准局正式公布实施了美国的数据加密标准( d e s ) ，公开它 的加密算法，并批准用于非机密单位和商业上的保密通信。密码学的神秘面纱从此 被揭开。 第三个阶段从1 9 7 6 年至今。1 9 7 6 年d i m e 和h e l h n a n 的“密码学的新方向” 一文导致了密码学上的一场革命。他们首次证明了在发送端和接收端无密钥传输的 保密信息是可能的，从而开创了公钥密码学的新纪元。 在密码学的发展过程中，数学和计算机科学作出了卓越的贡献。数学中许多 分支如数论、概率统计、近似代数信息论、椭圆曲线理论、算法复杂性理论、自动 机理论、编码理论等都可以在其中找墅4 各自的位置。它的踪影遍及数学许多分支， 而且还推动了并行算法的研究，从而成为近年来非常引人入胜的领域。 随着计算机网络不断渗透到各个领域，密码学的应用也随之扩大。数字签 名、身份鉴别等都是由密码学派生出来的新技术和应用。 第一章椭圆加密算法简介 1 1 2 、公钥密码学 公钥密码学是整个密码学发展历史中最伟大的一次革命，也可以说是唯一的 一次革命。从密码学产生至今，几乎所有的密码系统都是基于替换这些初等方法， 在过去的几千年中，算法的实现主要是通过手工计算来完成。随着转轮加密解密 机器的出现，传统密码学有了很大进展，利用电子机械转轮可以开发出极其复杂的 加密系统，利用计算机甚至可以设计出更加复杂的系统，最著名的例子是l u c i f e r 在i b m 实现数据加密标准( d e s ) 时所设计的系统。转轮机器和d e s 是密码学发展 的重要标志，但是它们都是基于替换和置换这些初等方法之上。 公钥密码学与其前的密码学完全不同，它的出现使密码学的研究发生了巨大 的变化。与传统加密系统不同的是，使用这种方法的加密系统，不仅公开加密算法 本身，也公开了加密用的密钥。首先，公钥算法是基于数学函数而不是基于替换和 置换，更重要的是，与只使用一个密钥的传统对称密码不同，公钥密码学是非对称 的，它使用两个独立的密钥。我们将会看到，使用两个密钥在消息的秘密性、密钥 分配和认证领域有着重要意义。 目前的公钥密码系统主要依赖下面三种数学难题： 大整数因子分解问题 离散对数问题 椭圆曲线上的离散对数问题 这三种难题基于同一个数学理论，即给定一个单向的方程，它的正向运算相 对比较简单，但反向运算复杂度却很高。这一理论用在密码学中，正向运算相当于 正常的加解密过程，而反向运算为破译过程。 第一类公钥系统是由r i v e t ，s h a m i r ，a d e l m a n 提出的，简称r s a 系统，它的 安全性是基于大整数因子分解的困难性，而大整数因子分解问题是数学上的著名难 题，用来确保r s a 算法的安全性。r s a 系统是公钥系统中最具有典型意义的方 法，自提出以来就一直是人们研究的焦点。对于密码破译者来说，在这种系统中， 已知密文而想得出明文就必须进行大整数的因子分解。 从上述介绍中不难看出，r s a 方法的优点主要在于原理简单，易于使用。但 是，随着分解大整数方法的进步及完善、计算机速度的提高以及计算机网络的发展 ( 可以使用成千上万台机器同时进行大整数分解) ，作为r s a 加解密安全保障的大 整数要求越来越大。为了保证r s a 的安全需要1 0 2 4 位以上的字长，显然，密钥长 度的增加导致了其加解密的速度大为降低，硬件实现也交得越来越难以忍受，这对 使用r s a 的应用带来了很重的负担，对进行大量安全交易的电子商务更是如此， 从而使得其应用范围越来越受到制约。 第二类公钥系统的安全性依赖与离散对数问题( d i s c m el o g a r i t h mp r o b l e m ， 简称d l p 问题) 的计算困难性。设g 为一个有限a b e l 加法群，假定g 为g 的某 个元，a 为任意的整数，如果己知g 及a g ，如何求出整a 来的问题在数学上称为离 散对数问题。一般说来，当群g 选择得当，且整数a 充分大时，求解此类问题是 非常困难的。离散对数问题又可细分为两类，一类为某个有限域上的离散对数问 题，一类为椭圆曲线上的离散对数问题。两者比较，后一类问题求解更为困难些。 第一章椭圆加密算法简介 基于这一判断，人们通过对群g 作出不同的选择时，构造了各种不同的公钥系 统，比如m a s s e y - o m u r a 公钥系统，e 1 c - a m a l 公钥系统等等。 第三类公钥系统是建立在椭圆曲线离散对数问题上的密码系统，称为椭圆曲 线密码系统。众所周知，定义在某一代数域上椭圆曲线上的有理点在适当的定义了 零元素和运算规则后，构成了一个有限秩的a b e l 群。设g f ( p ) 为一个有限域，则 o f ( p ) 上的一条椭圆曲线e 上的有理点构成一个有限群e p ，这个有限群的阶可经由 某些特别方法计算出来，设已知属于e p 的点g 和a g ，从g 和a g 求出a 来是非常困 难的，此种问题称为椭圆曲线离散对数问题，它较通常的离散对数问题更为困难。 椭圆曲线加密算法e c c ( e l l i p t i ec u r v ec r y p t o s y s t e m ) 是由n e a lk o b l i t 和v i e t o r m i l l e r 于1 9 8 5 年首次提出，从那时起e c c 的安全性和实现效率就被众多的数学家 和密码学家所广泛研究。所得的结果表明，较之r s a 算法，e c c 具有密钥长度 短、加解密速度快、对计算环境要求低、通信时对带宽要求低等特点。近年来， e c c 被广泛应用于商用密码领域，这可由e c c 被许多著名的国际标准组织所采纳 所佐证，下面列出了一些涉及椭圆曲线密码系统加密、签名、密钥管理等方面的若 干国际标准： 髓ep 1 3 6 3 a n s ix 9 i s o ，i e c m t f a t mf o r u m f p s1 8 6 - 2 加密、签名、密钥协商机制 椭圆曲线数字签名算法及椭圆曲线密钥协商和传输协议 椭圆曲线e l g a m a l 体制签名 椭圆曲线d h 密钥交换协议 异步传输安全机制 美国政府用于保证其电子商务活动中的机密性和完整性 由于公钥加密系统已逐渐成为加密系统的主流，有些人对公钥密码系统产生 了一些误解。 一种误解是，从密码分析的角度看，公钥密码比传统的密码更安全。例如， g a r d e n e r 在s c i e n t i f i ca m e r i c a n 上发表的一篇著名的文章中就提出了这样一种观 点。事实上，任何加密方法的安全性依赖于密钥的长度和破译密文所需要的计算 量。从抵御密码分析的角度看，原则上不能说传统密码优于公钥密码，也不能说公 钥密码优予传统密码。 第二种误解是，公钥密码是一种通用的方法，所以传统密码已经过时。其实 正相反，由于现有的公钥密码所需的计算量大，所以取缔传统密码似乎不太可能。 就象公钥密码的发明者之一所说的，“公钥密码仅限于用在密钥管理和签名这类应 用中，这几乎是已被广泛接受的事实。” 1 1 3 、公钥密码系统及其应用 在实际应用中，对称密码系统与公钥密码系统经常有两种结合方式：电子信 封和交换会话密钥。 第一章椭圆加密算法简介 电子信封，指使用对称密码系统对明文加密，然后用公钥系统对对称密码的 密钥加密，最后将明文加密结果和密钥加密结果，一起传给接收者：接收者接到数 据后，先通过公钥系统解密出对称密码的密钥，再用对称密码系统解出明文。 交换会话密钥，指在实际通信之前，通信双方先使用公钥系统，共享一个随 机的对称密码的密钥。然后，再用这个密钥，通过对称密码系统进行实质的数据交 换。 这两种结合方式，都能够有效的发挥两种密码系统的优势，达到两全其美的 效果。 公钥密码学在实际应用中主要是用作数据加密( c 卿i o n ) 和数字签名( d i 西诅l s i g n a t u r e ) 。这两者在秘钥对的使用上是不一样的。对于加密来说，发送方利用接收 方的公钥来加密，接收方用自己的私钥来解密并读出明文。对于数字签名，签名者 使用私钥，而接收者使用公钥来验证签名。 图1 1 1 表示加密和解密的过程，其步骤如下： 1 ) 接收方b 产生公钥、私钥对； 2 ) b 将公钥存放在公共目录中； 3 ) 发送方a 从公共目录中取得b 的公钥； 4 ) a 使用b 的公钥对数据进行加密并传送出去； 5 ) b 使用自己的私钥解出明文。 图1 1d a t ae n c r y p t i o n 相对于数据加密，数字签名稍微复杂一些，因为它多了一个提取数据的过程 ( h a s h i n g ) ，也就是在大量数据中提取一些有代表性的数据，这个过程是有专用算法 来实现的。图1 2 表示了整个数字签名的过程，其步骤如下： 1 ) 发送方a 产生公钥、私钥对； 2 ) a 将公钥存放在公共目录中： 3 ) a 对原文进行提取得到h a s h ； 4 ) a 使用自己的私钥对h a s h 进行加密； 5 ) 加密后的h a s h 和源数据进行叠加； 6 ) a 将运算后得到的数据发送给b ； 7 ) b 接收到数据后首先要把已加密的部分分离出来； 8 ) b 对源数据进行一次提取过程； 9 ) b 使用a 的公钥对已加密的h a s h 进行解密： l o ) b 将自己产生的h a s h 和解开的h a s h 进行比较。 只有用a 的私钥进行加密的h a s h 才能匹配，这样就可以验证a 的签名。 4 第一章椭圆加密算法简介 1 2 、公钥密码学的数学基础 1 2 i 、整数和取模 整数取模其实就是该操作数对模数( m o d u l u s ) 进行除法取余数的过程，例如： 1 1m o d8 = 3 。当两个数对同一个模数m 取模相等时，这两个数称为模m 相等 ( c o n g r u e n tm o d u l om ) ，可以表示为4 i b ( m o d m ) 。 1 2 2 、二进制有限域( b i n a r y f i n i t ef i e l d s ) 有限域又称迦罗华域( f i n i t ef i e l do rg a l o i sf i e l d ) 包含有限多的元素和一些代数 运算，如加法、减法、乘法、除法( a d d i t i o n , s u b l r a c t i o r l m u l t i p l i c a t i o n ，d i v i s i o nb y n o n z e r oe l e m e n t s ) 等等，同时代数运算律如交换律、结合律和分配律( c o m m u t a t i v e a s s o c i a t i v e , d i s t r i b u t i v e ) 仍然有效。有限域的阶数表示该有限域所包含的元素的数 目，当q 为大于l 的整数，并且q 为基的素数次方，则该有限域的阶数可以确定。 对于给定阶的有限域可以各不相同，然而它们的代数结构( a l g e b r a i cs t r u c t u r e ) 是相同的。在密码学中，有两种有限域是通常被用到的。 当q 是一个素数p ，则有限域6 f ( p ) 被称为素数有限域，它主要是由模 数p 来表示。 当q = 2 。，则有限域g f ( 2 ”) 被称为二进制有限域。本设计的所有运算都 是在这个域中展开的。 下面我们将详细讨论二进制有限域的性质。 第一章椭圆加密算法简介 1 2 3 、有限域上的多项式 对于正整数m 来说，二进制有限域g f ( 2 ”) 由2 ”个位长为m 的二进制数组 成。例如，g f ( 2 3 ) = o o o ，0 0 1 ，o l o ，0 1 1 , 1 0 0 , 1 0 1 ，1 1 0 ，1 1 1 ，m 称为有限域的阶次。当 m = l 时，g f ( 2 ) 只有两个元素 o ，1 ) ，模数为2 。 有限域上的运算可以用下面的方法来实现。 加法 当m l 时，定义在g f ( 2 “) 域上的加法运算在实现时为按位相加模2 ( b i t w i s e a d d i t i o nm o d u l o 2 1 ，也就相当于按位异或( b i t w i s ex o r ) ，没有进位。 例如：( 1 1 0 0 1 ) + ( 1 0 1 0 0 ) = ( 0 1 1 0 1 ) 。 乘法 有限域g f ( 2 ”) 上的乘法运算有很多中方法来实现，而乘法规则的确定和基 ( b a s i sr c p r e s 锄叫o n ) 的选择密切相关。通常有两种基：多项式基和常规基( p o l y n o m i a l b a s i sr e p r e s e n t a t i o n sa n dn o r m a lb a s i sr e p r e s e n t a t i o n s ) 。本设计中e c c 的乘法运算是 在多项式基中完成的。因此下面我们也只讨论基于多项式的乘法运算。 在多项式基中，g f ( 2 “) 域中每一个元素都可以用一个阶次小于m 的多项式 来表示。还有更加简化的表示方法。可以用位流( 口卅人a 2 a ) 来代替多项式 a m _ i t ”1 + a + 4 2 t 2 + 口l t 十a o 。在有限域的乘法中，除了两个乘数之外还有一个重要 的参数，m 阶的不可约二进制多项式( i r r e d u c i b l eb i n a r yp o l y n o m i a l ) p ( t ) 。一般情况 下，p ( t ) 是一个三项式( t r i n o m i a l ) 或五项式( p e n t a n o m i a l ) ，也就是说除了最高位和最 低位，中间只有一位或三位的系数为l ，其余都为0 。有限域的乘法就是两个乘数 多项式相乘再对p ( t ) 求模得出的结果。 1 3 、椭圆曲线 1 3 1 、椭圆曲线 简单的说，椭圆曲线并不是椭圆，之所以称之为椭圆曲线是因为它们是用三 次方程来表示的，并且该方程与计算椭圆周长的方程相似。e c c 加密体制的椭圆 曲线可分为两类：超级奇异曲线( s u p 口s i n g u l a rc u r v e ) 和非超级奇异曲线( n o n - s u p e r s i n g u l a rc u r v e ) 。其中，后者具有更高的安全性。最高项为三次方的非超级奇 异曲线可定义如下：y 2 + 砂= x 3 + a x 2 + 6 。 第一章椭圆加密算法简介 我们在椭圆曲线上定义加法运算。简单地说，可如下定义加法运算：若椭圆 曲线上的三个点在一条直线上，则它们的和为0 ( 称为无穷远点或零点的元素) 。从 这个定义出发我们可以定义椭圆曲线加法的运算规则： 1 ) 0 是加法的单位元。这样有o = 一o ；对椭圆曲线上的任何一点p ，有p + 0 = p 。 2 ) 一条垂直的线与椭圆曲线相交于两点，这两点具有相同的x 坐标，设为 p l ( x ，y ) 和p 2 ( x ，- y ) 。这条直线与曲线也在无穷远点相交，因此p i + p 2 = 0 且 p = - - p 2 ，因此一个点的负元是具有相同x 坐标和相反的y 坐标的点。 3 ) 要计算x 坐标不相同的两点q 和r 之和，则在q 和r 间作一条直线并找 出第三个交点p 1 ，显然存在有唯一的交点p l ( 除非这条直线在q 或r 处与 该椭圆曲线相切，此时我们取m = q 或p i = r ) ，因此o “h p l = o ，从而 q r = 一p l 。 4 ) 要计算q 的两倍，则作一条切线并找出另一交点s ，那么q + q - 2 q ；一s 。 上述加法满足普通加法的性质，如交换律和结合律。我们定义正整数k 乘以 椭圆曲线上的点p 为k 个p 之和，因此有2 p = p + p ，3 p = 2 p + p 。 图1 3 给出了上述加法运算在椭圆曲线上的表示情况，左边为v + o ，右边为 2 p ，这样我们可以很直观地看出加法的结果在椭圆曲线上的位置。 y !澎 ： n 盼 。，| | j ： ，+ 口 y h ? j 厅 1 。r f 。 。 一 屺 ，弋 ； ： 图1 3 e l l i p t i cc u r v e 1 3 2 、椭圆曲线加密算法 对于非超级奇异曲线，根据几何方法可以得出椭圆曲线上的点加运算，其中 已知p 和q 为椭圆曲线上的两点，p = ( x l ，y 0 ，q = o 【2 ，y 2 ) ，我们需要求出下面的结 果r = p + q - 气x a ，y 0 。 当p q 时( 点加) ： 第一章椭圆加密算法简介 x 3 = 牙+ a + 五+ 工2 + a y 3 = t ( x l + 屯) + 屯+ m a ：! ! 丝 工i + 屯 当p = q 时( 倍点) ： 黾= 矛+ z + 口 y 3 = 砰+ 也+ 而 五- - - - x t + 丝 。 而 从上述的计算公式中我们可以看出，不论是点加还是倍点，都有一次除法运 算，当计算p + q 时，除法运算是通过求逆运算来实现的，在g f ( 2 “) 域上，求逆 运算是2 “一1 次幂的运算，非常复杂。 上述运算是在仿射坐标系( a m n ec o o r d i n a t e s ) - f 完成的，为了避免除法运算， 我们可以在投影坐标系( p r o j e c 曲ec o o r d i i l a t e s ) 下完成该运算。设p ；( x 1 ，y l ，z o ， q = ( x 2 ，y 2 ，盈) ，其中p ，q 0 ，求r _ p 刊q = ( x 3 ，y 3 ，墨) 。 当p q 时： x 3 = a d 乃= c d + a 2 ( 甄+ 嘲) 2 3 = a 3 z i z 2 a 2 x 2 z i + 。2 b 2 y 2 z l + y l z 2 c = a + 口 d = a 2 + i ：2 ) + z l z 2 b c 当p = q 时： x 3 = a b y ，= 0 爿+ 占( 奸+ y l z l + 彳) z 3 。a 3 a = 毛 b = b z 卜| 在投影坐标系下，完成一次点加运算需要1 3 次乘法、1 次平方、7 次加法， 完成一次倍点需要7 次乘法、5 次平方、4 次加法。 本论文的核心内容就是讨论投影坐标系下点加运算的硬件实现。下面几节简 要介绍了基于椭圆曲线核心运算的加密解密协议。 第一章椭圆加密算法简介 1 3 3 、d i f f i e h e l l m a n 密钥交换协议 在e c c 密钥交换协议中，考虑方程q = i c p ，其中q ，p e p ( a ，b ) 且k 3 ) ，由于最近出现 了攻击只上的e c d l p 的方法，导致只中对n 的要求越来越严，比如，在2 0 0 0 年，g a u d r yh e s s 和s m a r t 等人通过改进的w e i l 下降方法，使得对于只上的 e c d l p ，当1 1 不是素数时，计算变得有效，基于这个理由，只作为基本域更好。 2 如果选取作基域，如何选取p 。一般说来，为了算法实现的效率，p 可 取成m e r s e n n e 素数或拟m e r s e n n e 素数。所谓拟m e r s e n n e 素数，即p = + b ，其 中a ，b 都是小整数。我们可以取其中一种，也可以选择随机素数p 。 l o 第一章椭圆加密算法简介 3 曲线的选择。这是e c c 的关键所在。“好的”曲线才具有高度安全性。大 量的研究表明，特殊的椭圆曲线是有安全隐患的，因此，为了抗击各种攻击方法， 我们的曲线至少要满足： 1 ) e 。不是超椭圆曲线( 口，0 ) ，这里的口，为f r o b e n i u s 映射的迹 2 ) e 。不是反常椭圆曲线( 口。1 ) 3 ) e ，的阶( 记为l e ，j ) 包含有大的素因子( 如要求大于2 2 “) 4 ) 陋。l 不能整除p 一1 ，这里的l k 2 0 上述的对曲线的限制主要是由目前已知的攻击方法所决定的。这些攻击方法 有： p o l l i g - h e l l m a n 方法 p o l l a r d 的r h o 方法 w e i l 对和t a t e 对方法 s e m c a v - s a t o h - a r a k i s m a r t 方法 m o v 方法 最近出现的g a r d r y ，h e s s 和s m a r t 等人的方法 这里，p o l l i g - h e l l m a n 方法和p o l l a r d - r h o 方法对于一般有限a b e l 群上的离散 对数问题都是有效的，但计算复杂度为指数级的；即o ( p ) ，其中，p 为i e v l 最大 素因子。 其他方法都只对特殊的椭圆曲线有效。比如m o v 方法只对超椭圆曲线有效。 在避免采用上述特殊的曲线后，为防范p o l l i g - h e l l m a n 方法和p o l l a r d - r h o 方法 的攻击，我们首先应有能力计算e ，的阶旧小最好将陋，i 选为素数。 4 阶的计算。对于1 e 。l 的计算有许多方法。如，设4 。为f r o b e n i u s 映射的迹， 对于任意的q e ，由于i e v i = p + l - a ，可知( p + o q = a p q ，从上式出发，我们 可以用b s g s 方法计算出来，由于l a ，l 2 p “2 ；可知计算复杂度为o ( p “4 ”) ，当 p 2 ”时，这一方法失效。 1 9 8 5 年s c h o o f 找到了计算i e 。i 的多项式算法，s c h o o f 方法的出发点为如下的 公式：声2 一口。庐+ p = o ，这时为f r o b e n i u s 映射。通过约化，利用除多项式的性 质，s c h o o f 实现了他的算法，但是这一方法在实际计算中效率极低。其算法的复 杂度为o ( 1 0 9 8p ) ，从1 9 8 8 年至今，a t k i n ，e l k i s 等人改进了s c h o o f 算法，他们通 过分析e 。上的同种映射，利用模多项式的性质，得出的方法称之为s e a 方法， s e a 方法的概率复杂度为o ( 1 0 9 6p ) ，因此，较之s c h o o f 方法更为有效，m o r a i n 等 人利用这一方法，加之其他的改进措施，曾计算出p = 1 0 ”的e 的阶来。 我们通过改进s e a 方法，结合b s g s 方法，对于计算l e 。i 作了许多工作，比 如，当p 为1 6 0 位时，我们在p 翻n t i u m h i4 5 0 计算机上联网计算出旧。i 来，所费时 间为十多分钟，当然如果使用更多的技巧，还可以大大提高效率。 第一章椭圆加密算法简介 基于算阶方面的工作，我们选择的椭圆曲线具有如下的特点： a 全随机的素数p 和椭圆曲线 b 1 耳l 为素数 小结 本章首先介绍了密码学的历史与现状，分析了公钥密码学在当今各领域的重 要地位；然后比较详细地讨论了椭圆加密算法所基于的数学模型，包括有限域及其 运算规则、椭圆曲线和定义在椭圆曲线上的加法运算；第三节还给出了e c c 加密 算法的两个应用实例d i f f i e h e l l m a n 密钥交换协议和e 1 g a m a l 密码体制：最后一节 对e c c 的安全性进行了简要的分析。 第二章异步电路设计方法简介 第二章异步电路设计方法简介 2 1 、前集成电路设计中存在的一些问题 随着半导体制造工艺的发展，集成电路朝着规模更大、速度更快的方向发 展。但与此同时，集成电路的设计中也出现了一系列急需解决的问题，包括由于电 路规模的增大所引起的功耗的增大：全局时钟引起的时钟偏移；工艺尺寸减小导致 连线延迟在系统延迟中所占比例的增大。下面我们将详细讨论这些问题。 2 1 i 、集成电路的功耗问题 在过去，集成电路设计者最关心的电路参数是面积、速度、性能、成本和可 靠性，然后才是电路的功耗的问题。然而近年来情况发生了很大的变化，电路的功 耗已经和面积、速度一样，成为设计者考虑的首要因素。与之相对应超大规模集 成电路和系统的设计重点也渐渐地由高速度转向低功耗设计，低功耗设计方法成为 现在超大规模集成电路设计中一个热门的课题。这种局面的形成是由以下几个因素 所决定的： a 便携式电子器件的广泛应用 便携式电子器件近几年得到了迅猛的发展，已经深入到人们的日常生活中， 例如便携式个人电脑、手机、p d a 、手掌游戏机、便携式数字相机和摄像机、便 携式媒体播放机等等。这些电子产品性能的迅速提高给人们的生活带来了极大的方 便，然而作为这些便携式器件的供电设备的电源，它的发展速度远远不及电子系统 的发展速度。所以为了使得电池的使用时间尽可能的长，电路的低功耗设计就显得 尤为重要。 b 芯片的散热问题 众所周知，芯片设计领域有一条著名的摩尔定律( m o