[硕士论文精品]椭圆曲线数字签名算法的fpga实现

皇王型堇盔堂堡主堡塞摘要椭圆曲线数字签名算法ECDSA是数字签名算法DSA的椭圆曲线对等。它先后成为ANSI，IEEE，NIST和ISO的标准，而且其它的一些组织正在考虑成为其标准。不象普通的离散对数问题和因数分解问题，椭圆曲线离散对数问题没有已知的亚指数算法，所以使用椭圆曲线的算法在密钥的位强度是足够高的。土，乒一，一本文从实际应用出发，研究了椭圆曲线数字签名算法的FPGA的实现以基本的数论理论、抽象代数和复杂度理论为依据，结合信息论、密码学的一些知识以及一些具体的相关算法，确定了ECDSA的硬件实现方案按照层次化、模块化的设计思想，采用硬件描述语言DL作为设计输入进行ECDSA的硬件设计；在每个设计层次和每个模块都进行了仿真验证，得以保证底层设计的正确性。在确保每个模块的设计正确后，完成对电路的顶层设计，进行总体的仿真。再通过逻辑综合，经过布局、布线，完成时序后仿真。设计主要采用MENTER公司的功能强大的FPGAADVANTAGE作为开发工具，进行了各个层次、各个模块的设计输入、仿真以及逻辑综合，完成了电路的前端设汁；然后选用XINLINX公司的FPGA的VERTEX系列的XCVL000，用XINLINX公司的A1LIANCESERIES工具，进行布局布线，然后再进行时序仿真，生成配置文件。由于FPGA器件具有现场可编程的特点，所以可以通过修改源程序的参数，就可以实现对不同位数的ECDSA的实现。，皿一本设计获得了良好的指标产生签名只需要十几个毫秒，验证签名需要二十几个毫秒。在我国安全领域，具有自主知识产权的加解密产品基本上还是处于空自状态，所以研究开发具有自主知识产权的椭圆曲线数字签名算法对于提高我国信息安全水平有较大的实用价值和现实意义。关键词ECDSA，匦勇FPGA、，、一阁溶擘抡皇王型垫盔堂塑主造塞一ABSTRACTTHEELLIDTICCURVEDIGITALSIGNATUREALGORITHMECDSAISTHEELLIPTICCURVEANALOGUEOFTHEDIGITALSIGNATUREALGORITHMDSAITWASACCEPTEDIN1999ASANANSISTANDARD，ANDWASACCEPTEDIN2000ASIEEEANDNISTSTANDARDSUNLIKETHEORDINARYDISCRETELOGARITHMPROBLEMANDTHEINTEGERFACTORIZATIONPROBLEM，NOSUBEXPONENTIALTIMEISKNOWNFORTHEELLIPTICCURVEDISCRETE109ARITHMPROBLEMFORTHISREASON，THESTRENGTHPER。KEYBITISSUBSTANTIALLYGREATERINANALGORITHMTHATUSESELLIPTICCURVESINTHISARTICLE，WESTUDYTHEIMPLEMETATIONOFFPGAFORELLIPTICCURVEDIGITALSIGNATUREALGORITHMBASEDONNUMBERTHESIS、ABSTRACTALGEBRAANDCOMPLEXTHESIS，INTEGRATEDINFORMATIONTHEORY、CRYPTOGRAPHYANDSOMESPECIFICRELEVANTALGORITHM，WEASCERTAINTHEIMPLEMENTATIONOFECDSAFOR,HARDWAREPROJECTACCORDINGTOTHEDESIGNIDEAOFHIBERARCHYANDINODULARIZATIONWEADOPTVERYHIGHSPEEDICHARDWAREDESCRIPTIONLANGUAGEVHDLASDESIGNINPUTANDSIMULATETHEDESIGNINEVERYLEVELANDEVERYMODELFORTHECORRECTOFTHEFUNDAMENTALDESIGNAFTERFINISHTHETOPDESIGN，WEPERFORMTHEWHOLESIMULATIONTHEN，WECARRYOUTTHETIMINGSIMULATIONAFTERTHELOGICSYNTHESANDLAYOUTMOSTLY，THISDESIGNEMPLOYSMENTORCORPORATIONSOFTWARE“FPGAADVANTAGE”ASEXPLOITATIONTOOLTOPERFORMDESIGNINPUT、SIMULATIONAND109ICTHESISWITHEVERYLEVELANDEVERYMODELTOFINISHTHEFOREDESIGN1HEN，CHOICESTHEXILINXCORPORATIONPRODUCTXCVL000OFTHEVERTEXSERIESANDEMPLOYITSTOOL“ALLICANCESERIES”TOIMPLEMENTLAYOUTANDTIMINGSIMULATIONINVIRTUEOFFPGAPRODUCTHASTHECHARACTERISTICOFFIELDPROGRAMMABLE，WECANPERFORMTHEECDSAIMPLEMENTATIONWITHDIFFERENTBITSACCORDINGTOMODIFICATIONTHEPARAMETEROFTHESOURCECODEMTHISPROJECTCANACHIVEGOODINDEXITCOSTSLESSTHAN15MILLISECONDINSIGNATUREPROCESSANDLESSTHAN30MILLISECONDINVERIFYPROCESSINSECURITYFIELDOFOURCOUNTRY，THEPRODUCTOFENCRYPTIONANDDECRYPTIONWHICHPOSSESSESINDENPENCEININTELLGENCEPROPERTYISINBLANDSTATESOTOSTUDYANDRESEARCHTHEE11IPTICCURVEDIGITALSIGNATURHASTHEGREATAPPLIEDVALUEANDREALISTICMEANINGFORENHANCINGINFORMATIONSECURITYLEVELOFOURCOUNTRYKEYWORDSECDSA，DSA，VHDL，FPGA，SIMULATION附件三独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标没和致谢的地方外，论文中不包含其他入融经发表豌撰写过豹研究威采，穗不包含为获褥电子科技大学或其它教育杌构媳学位或I菱麓I嚣馒怒遘戆耢辩。与凌一嗣羔箨静嗣漆对本疆究爨徽鹣任秘炎麸均已在论文中作了明确的说明并表示谢意。签名魏当生圣日期矽弓年1月相关于论文使焉授权酶说明本学像论文作者完全了解邀子科技大学有关保留、使籍学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印馋和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复剑手段保存、汇编擎位论文。保密的学位论文在解密鼷应遵守此规定签名熬当一熟导师签名型1墨乏玉鑫期炒；年月77舀皇至型垫盔兰塑主堡塞一第一章绪论11课题的提出及研究的意义当今社会已进入信息化时代，计算机网络已逐渐应用于社会各个领域，伴随着国民经济信息化进程的推进和电子商务等网络新业务的兴起，社会对计算机网络的依赖程度越来越高。计算机网络和信息系统的应用给人们带来了前所未有的方便，大大地提高了劳动生产率，给社会带来了无限的商机与财富。然而，社会对计算机网络的高度依赖同时也蕴藏着巨大的风险。网络攻击、网络欺诈、9网络犯罪将会给社会带来巨大的经济损失和秩序动荡，甚致会使整个人类社会陷入危机。因此，网络安全是一个必须解决的问题，已引起了全球社会的极大关注。网络安全从本质上来讲就是网络上的信息安全。信息安全技术是F涉及信息论、计算机科学和密码学等多方面知识的综合性学科。它的主要任务是研究计算机系统和通信网络内信息的保护方法以实现系统内信息的安全、保密、真实和完整。信息安全的核心是密码技术。数字签名提供了用来验证信息内容和发件人身份的方法，所以数字签名技术是实现信息安全的核心技术之一。研究更有效率的数字签名方案，是实现信息安全的重要手段之一。数字签名方案用于提供手写体签名或其它签名的数字副銮。数字签名是依赖于只有签名者才知道的一些秘密签名者的私钥的数字。此外，该数字包含在所签消息的内容中，并且必须是可以验证的。现今所使用的数字签名方案可以分为以下几种1整数因子分解IFINTEGERFACTORIZATION方案，其安全性基于对整数因子分解的不可实现性。其代表为RSARSA是一种公开密钥算法，既能用于加密，也能用于数字签名，以它的三个发明者RONRIVEST，ADISHAMIR和LEONARDADLEMAN的名字命名。2离散对数DLDISCRETELOGARITHM方案，其安全性基于对有限域的离散对数问题DLPDISCRETELOGARITHMPROBLEM的不可实现性。其代表为数字签名算法DSADIGITALSIGNATUREALGORITHM。3椭圆曲线ECELLIPTICCURVE方案，其安全性基于椭圆曲线离散对数一皇王銎堇盔兰堡主迨壅，问题ECDLPELLIPTICCURVEDISCRETELOGARITHMPROBLEM的不可实现性。其代表为椭圆曲线数字签名算法ECDSAELLIPTICCURVEDIGI蔓焦SIGNATUREALGORITHM。因为椭圆曲线离散对数问题ECDLP是比离散对数问题DLP困难得多，椭圆曲线系统中每个密钥位的强度在本质上要比传统的离散对数系统大得多，这体现ECDSA比RSA的每BIT安全性能更高。图11为ECDSA与RSA和DSA的安全性的比较。ECDSA所用的参数要比DL系统所用的参数少。该系统的优点是参数小、速度快以及密钥和证书都较小。这些优点在处理能力、存储空间、带宽和能源受限的环境中尤其重要。60005000密4000钥辱3000BITS20001000图11ECDSA、RSA、DSA抗攻击性比较12课题研究的国内外现状1E36椭圆曲线数字签名算法是国际标准组织ISOINTERNATIONALSTANDARDSORGANIZATION、美国国家标准研究所ANSIAMERICANNATIONALSTANDARDSINSTITUTE、电子和电器工程师协会IEEEINSTITUTEOFELECTRICALANDELECTRONICSENGINEERS、联邦信息处理标准PIPSFEDERALINFORMATION2皇至型垫丕堂堡主鲨銮PROCESSSTANDARDS的标准，并正为其它的标准化组织作为标准。在国际上，CERTICOM对于椭圆曲线数字签名算法研究的比较成熟，已有产品面世。但是在国内市场上，由于国家商用密码管理上实行专控，不准使用进口技术和产品。目前，除了由武汉大学青年教授陈建华成功开发出一套椭圆曲线加密软件，没有其它厂商或单位成功开发出基于ECCELLIPTICCURVECRYPTOGRAPHY椭圆曲线密码算法的加密产品，现有的产品大多是基于RSA或DESDESDATAENCRYPTIONSTANDARD，是一种对称密钥算法的算法。ECC必将取代RSA，因为它更适合信息产业发展的需要。13课题研究的主要内容本课题研究的内容为中物院电子工程研究所对于椭圆曲线数字签名算法研究的一部分主要研究其签名和验证签名的硬件实现部分，用以加速椭圆曲线数字签名算法的实现。由于椭圆曲线数字签名算法已经成为众多标准组织的标准，而且相关理论也非常成熟，所以本课题研究的主要内容为选择适合于硬件实现的算法，在时间和面积之间取得折中，然后采用结构化、层次化的设计技术，用硬件描述语言VHDL作为设计方法，逐步通过编译、仿真、综合、后仿真等设计流程，完成ECDSA的硬件设计。课题的主要研究内容如下1深入理解ECDSA的相关数学原理以及课题背景。2熟悉并理解与ECDSA相关的算法，选择适合于ECDSA硬件实现的算法。3将设计层次化、模块化，分别完成各个层次、模块的设计和仿真，以保证底层设计的正确性。4成顶层设计，通过总体仿真。5选择适合于本设计的器件，通过逻辑综合，产生相应的网表文件，然后采用器件提供者的相应的软件，完成布局布线，生成后仿真文件，并通过时序后仿真，验证设计的时序的正确性。3皇王型量盔堂堕主丝塞一第二章ECDSA的相关原理椭圆曲线数字签名算法ECDSA的原理涉及数论、抽象代数以及密码学的一些知识，下面分别予以介绍。21有限域有限域由集合F上具有二元操作的F元素的有限集组成，二元操作指满足某一算法的加法和乘法。有限域的阶是域中元素的数量。当且仅当Q为素数次方时存在Q阶有限域。如果Q为素数次方，则本质上只有一个Q阶有限域，这个域记为F。如果QP“，P是一个素数，M为一个正整数，则P称为FQ的特征，M则称为FA的扩展度。大部分的国际标准指定将椭圆曲线密码学技术限定在奇素数阶Q；P或2的幂Q2M之内A211有限域FD令P为一素数，称为素数域的有限域FP，由具有下面算法操作特性的整数集O，L，2，P1组成一加法如果A，BF。，则ABR，这里10为AB被P整除的余数，且OSRSPI，称为P的加法模。一乘法如果A，BEF。，则ABS，这里J为AB被P整除的余数，且0SSP一1，称为P的乘法模。逆如果A为有限域F。中的非零元素，A模P的逆记为A1，则存在唯的元CA一，使ACIMODP成立。212有限域E。有限域E4，称为特征双有限域或二元有限域，可以看作由0，L两个元素组成的F上的ID维向量空间A也就是在E”中存在M个元素AO，AL，A。，满足AE”能用以下的形式唯一写出AAOAOALOI口，一LA，I，口，O，14皇王型塾盔堂堡主堡塞集A。，A1，一，A。称最上E”的一个基。给出这样一个基，域元素A能够表征为T62串A。A。OM_1。域元素的加法可以通过向量表达式位异或运算进行。乘法律则依赖于基的选择。只”有很多不同的基。有一些基可以比其他基带来在最”上算法效率更高的软件和硬件实现。ANSIX962准许两种基多项式基和正规基，不同的基对应的算法操作不同。2121多项式基多项式厂力X”厶_L工”1工2ZX五O，1，IO，1，2，M1是一个在F2上度为M的不可约多项式。也就是说，FX不能被分解为度小于M的两个多项式之积，这样的多项式FX定义F2上的多项式基表征，FX称为不可约多项式。一域元素有限域F”是由在F2上所有度小于M的多项式组成E“口。1X。1口1XAOAL0，L域元素URNIX”1口LXAO通常表示为长度为M的位串口“ALAO，使E”AALAO口O，1这样，E”的元素能够表征为所有长度为M的二进制位串。乘法单元L表征为位串0001，加法单元0表征为位串0000。二域运算下面为不可约多项式，砷使用多项式基定义的F2”算术运算一加法若口口LQ，BK一。B,BOYG最”的元素，则A6CC，LCICO，C。QB,MOD2。域加是通过逐位相加来实现。一乘法着口口。AL，B6_。6160为E”的元素，则AXB，1FIFO，这里多项式一LZ“RLXRO为当多项式5皇王型垫盔堂堡主堕塞一一。X“QXFAO屯IX”16LX在E上除，力的余。一乘逆若口。口。为F2“的一非零元素，A的逆表示为A1，存在一个唯一的元素C81，使AXCLMODFX。三选择不可约多项式F2上的三项式是形如X”矿1的多项式，其中LKM一1。F2上的五项式是形如X”JBZB并1的多项式，其中LKL屯岛M1。ANSIX962在选择域只”上的不可约多碗式指定以下规则1对于不可约三项式X。矿1，选择尽可能小的K值。2对于不可约五项式X”XK3XK2XKL41，遵循以下几条1选择尽可能B的K3值；2对于选定的屯值，选择尽可能小的七2值；3对于选定的七2值，选择尽可能小的K值。2122正规基E”在基域F2上的的一组正规基是形如，2，掣，21，五”，理MI论上证明这样的基总是存在的。给定任何元素口EF2“，可以表示为口口，卢，O其中口，0,1。F2”用正规基表示时，对一个元素进行运算可以通过向量表示的一个简单循环移位来完成，这是在硬件中非常容易实现的运算，但在进行乘法运算时则很是烦琐。22有限域上的椭圆曲线221F口上的椭圆曲线令P3为素数，F。上的椭圆曲线由形如等式21定义Y2矿AXBMODPA,BE21并且口、B满足铂327B20椭圆曲线的点集E由所有满足等式21的点力，X，YE组成，这些点包括被称之为无穷点的特殊点D。6皇王型堇盔堂堡主迨塞对于椭圆曲线上的两点相加给出椭圆曲线上的第三点，有一条规则，称之为弦切律。伴随这种加法操作，ER的点形成了一个用D点作为标记的群，正是这个群被用来构造椭圆曲线密码系统。加法律最好用几何解释。令PXL，Y1，QX2，Y2是椭圆曲线E上两个截然不同的点，则P和Q的和，记为RX3，Y3，定义如下首先通过点P和Q作一条直线；这条直线与椭圆曲线交于第三点；则点R就是这个点关于X一轴的映射，如图21所示，图中的椭圆曲线由两个部分组成，象椭圆的图形和无穷曲线。PYLQX2，Y277J厂2160且N4孑。7伴随因子HEFQN；其中，E表示椭圆曲线上的点的个数。2ECDSA密钥对ECDSA的公钥是基点的随机倍数；而私钥则是用来生成这个倍数的整数。成员A必须在密钥生成之前得到域参数有效的保证。为了生成ECDSA的密钥对，每一个成员A都要做如下操作1在区间【1抄1】中选择一个随机或伪随机整数D。2计算QDO。3A的公钥是Q；私钥是D。3生成ECDSA签名为了签署消息NL，具有域参数DQ，FR，A，B，G，N，H及相关密钥对D，Q的成员A做如下操作1选择一个随机或伪随机整数K满足1SKSNL。2计算KGXL,Y1且将XI转换成整数鬲。3计算RXLMODN，如果R0则回到第一步。4计算KIMODRL。5计算SHAM，且将该位串转换成整数E。6计算SK“EDRMODRL。如果S0则回到第L步。7A对消息M的签名为R，S。4验证ECDSA签名要验证A在消息上的签名为R，S，B取得A域参数DQ，FR，A，B，G，NH的可信副本和相关公钥Q，推荐B也验证D和Q的有效性，然后B做以下的操作1验证R和S是区间INI】内的数。14皇至型垫盔堂塑主鲨塞2计算SHAM，并将该位串转换成整数E。3计算WSROODN。4计算ULEWROODN和U2州ROODM5计算XULGU2Q。6如果XO则拒绝签名；否则转换X的X1坐标为整数N，并计算V五ROODNO7当且仅当VR时接受签名。5验证签名的依据如果消息M上的签名R，S真正是由A生成的，则由SK1EDRMODN得KS_LEDRMODN邗TEWRDULUDMODN。因而ULGU2QUL十U2DGK6，同时也需要VR。252椭圆曲线数字签名算法的安全性ECDSA的安全目标是对于选择明文攻击在现有的基础上是不可伪造的，对一个合法成员A发动此类攻击的攻击目标是在获取A在攻击者所选择的消息集不包括M上的签名之后，能获取A在某一单条消息上的有效签名。在离散对数问题是困难的而且所使用的哈希函数是随机函数的前提下，POINTCHEVAL和STERN已经证明了对于选择明文攻击，ECDSA在现有的情况下是不可伪造的。BROWN已经证明了在基本群为普通群而且所使用的哈希函数是在抗碰撞的前提下，ECDSA本身是安全的。15皇三型垫奎兰堡主丝兰第三章ECDSA的设计方法及硬件实现方案31ECDSA的设计方法传统的电路设计方法都是自底向上的，即首先确定可用的元器件，然后根据这些器件进行逻辑设计，完成各模块后进行连接，最后形成系统。基于EDA技术的所谓自顶向下的TOPTODOWN设计方法正好相反，其步骤就是采用完全独立于目标器件芯片物理结构的硬件描述语言，在系统的基本功能或行为级上对设计的产品进行描述和定义，结合多层次的仿真技术，在确保设计的可行性与正确性的前提下，完成功能确认。然后利用EDA工具的逻辑综合功能，把功能描述转化成某一具体目标芯片的网表文件，输出给该器件厂商的布局布线适配器，进行逻辑映射及布局布线，在利用产生的仿真文件进行包括功能和时序的验证，以确保实际系统的性能。即系统的结构构成方式与系统的行为或算法方式相混的描述称为混合层次描述，由于硬件描述语言具有这种描述能力，设计者就可以在抽象度相当高的层次上描述系统的基本结构，自顶向下设计方法的优越性表现在1由于顶层的功能描述可以完全独立于目标器件的结构，在设计的最初阶段，设计人员可不受芯片结构的约束，集中精力对产品进行最适应市场的设计，从而避免了传统设计方法中的再设计风险，缩短了产品的上市周期。2现代成果的再利用得到保证。现代的电子应用系统以及电子产品的开发与生产正向模块化发展，或者说向软硬核组合的方向发展。对于以往成功的设计成果稍做修改、组合就能投入再利用，从而产生新的或派生的设计模块，同时还可以以一种IP核的方式进行存档。3由于采用的是结构化开发手段，一旦主系统基本功能结构得到确认，即可实现多人多任务的并行工作方式，使系统的设计规模和效率大幅度提高。4在选择实现系统的目标器件的类型、规模、硬件结构等方面具有更大的自由度。16皇王型垫盔堂堡主堡苎本设计采用硬件描述语言VHDL为基本的设计手段，下面将VHDL作一些介绍。311VHDL的发展历史VHDL是超高速集成电路硬件描述语言VERYHIGHSPEEDICHARDWAREDESCRIPTIONLANGUAGE的英文缩写，它是一种数字硬件系统设计和描述的标准语言。与常用的电路原理图输入方式不同，VHDL是以类似于一般程序编程的方式对电路进行行为或结构的描述和定义。VHDL的开发始于美国国防部1981年的超高速集成电路计划，其目的是为了给出一种与工艺无关的、支持大规模系统设计的标准方法和手段。在1985年IEEE也开始了VHDL的标准化工作。1987年12月，VHDL被正式确定为IEEE1076标准。同时美国国防部也规定VHDL为国防部标准，要求所有涉及数字专用集成电路的项目必须以VHDL语言设计和归档。按照IEEE的规定，VHDL应每5年修订一次，不断更新。1992年，美国政府又选定VHDL作为联邦信息处理标准，该标准是测定计算机及通信能力的一个指标。在这几年中，电子设计自动化EDA开发厂商分别推出了以VHDL为基础的产品，支持对VHDL的仿真和综合。现在VHDL被视为数字电路设计的新方法，与高层设计相提并论。312高层设计今天，电子系统的特点是日益复杂，电路规模不断增大，各种新型器件新工艺大量涌现，微型化、保密化，各系统都有独特的专用集成电路，但又要求设计周期短、成本低，而且有可移植性，便于采用最新的工艺方法来实现。面对电子系统的这些特点，传统的设计方法已难以满足要求，而一种新的设计方法高层设计已逐渐进入了实用阶段，它得到了VHDL等高级描述语言以及系统仿真、综合优化等工具的支持。VHDL的描述能力覆盖了下至具体逻辑门的描述，上至系统级的行为描述，这种宽范围的描述能力使VHDL成为了高层设计的核心。313VHDL的优点VHDL具有以下优点1如上所述，VHDL的宽范围描述能力支持高层设计，将设计人员的工作17一皇至型垫盔兰堡主笙塞一_一重心提高到了系统功能的实现与调试，而花费较少的精力于物理实现。2VHDL与工艺独立，方便了工艺转换。3VHDL可以表达精确的延时信息与定时要求，从而有了模拟真实硬件的能力。4VHDL是工业和国防标准，各大EDA开发厂商，如MENTORGRAPHICS。VIEWLOGICSYSTEMS，SYNOPSIS以及CADENCEDESIGNSYSTEMS，都推出了以VHDL为基础的设计环境，使用户不再受限于任何一家的EDA产品。作为共同的标准语言，YLIDL提供了一个设计成果交流、复用、保存的有效手段，也方便不同小组协同完成大系统的设计任务。32FPGA的发展、特点及设计流程现场可编程门阵列FIELDPROGRAMMABLEGATEARRAYFPGA是80年代中期出现的一类新型用户可编程器件。与以往的可编程器件不同，FPGA采用类似于掩膜编程门阵列的通用结构，因而具有更高的集成度、更强的逻辑实现能力和更好的设计灵活性。FPGA自1985年由美国XILINX公司首家推出后，受到世界范围内电子设计工程师的普遍欢迎，并因此得到迅速发展。目前，FPGA器件的供应商主要有XILINX、ALTERA、ACTEL、QUICKLOGIC等公司，他们的产品都各有特点，设计者应根据设计要求选择合适的器件。321可编程SIC的发展概况可编程专用集成电路ASICAPPLICATIONSPECIFICINTEGRATEDCIRCUIT是指由用户编程实现所需功能的专用集成电路，按照结构的复杂程度不同大致可分为以下几类1简单可编程逻辑器件SIMPLEPROGRAMMBLELOGICDEVICESPLD2复杂可编程逻辑器件COMPLEXPROGRAMMABLELOGICDEVICECPLD3现场可编程门阵列FPGA。简单可编程逻辑器件主要指早期开发的可编程逻辑器件PROGRAIMNABLELOGICDEVICEPLD，它们经典地由“与阵列”及“或阵列”组成，能够有效地实现以“积之和”为形式的布尔逻辑函数。当“与”及“或”两个阵列都是可编18皇至型堇丕堂堡主笙壅一程时，这个器件称之为可编程逻辑阵列PROGRAMMABLELOGICARRAYPLA，其变型是可编程只读存储器PROGRAMMABLEREADONLYMEMORYPROM、可编程阵列逻辑PROGRAMMABLEARRAYLOGICPAL和通用阵列逻辑GENERALARRAYLOGICGAL，前者具有固定的与阵列和可编程的或阵列，后两者具有可编程的与阵列和固定的或阵列。早期的PLD结构简单，具有成本低、速度高、设计简便等优点，但其规模较小，通常只有数百门，难于实现复杂的逻辑。为了增加PLD的密度，扩充其功能，一些厂家对PLD的结构进行了改进，使PLD逐渐向复杂可编程逻辑器件过渡。它们一般都具有可重编程特性，实现工艺有EPROM技术、闪速EPROM技术和E2PROM技术。在互连特性上，CPLD采取连续互连方式，即用固定长度的金属线实现逻辑单元之间的互连。CPLD能够实现较大规模的电路集成。FPGA是与传统的PLD不同的一类可编程器件。它具有类似于半定锖,JFJ阵列的通用结构，即由逻辑功能块排列阵列组成，并由可编程的互连资源连接这些逻辑功能块来实现所需的设计。FPGA与掩膜编程门阵列的不同之处在于它由用户现场编程完成逻辑块之间的互连，而后者需由IC工厂通过掩膜完成互连。因此，在某种意义上说，FPGA是将门阵列的通用结构与PLD现场可编程特性结合于一体的种新型器件，具有集成度高、通用性好、设计灵活、编程方便、产品上市快等多方面的优点。322FPGA的基本结构FPGA的发展非常迅速，形成了各种不同的结构，按逻辑功能块的大小分类，FPGA可分为细粒度FPGA和粗粒度FPGA。细粒度FPGA的逻辑功能块较小，资源可以充分利用，但连线很开关多，速度慢；租粒度FPGA的逻辑功能块规模大，功能强，但资源不能充分利用。从逻辑功能块的结构上分类，可分为分段互连型FPGA和连续互连型FPGA两类。分段互连型FPGA中具有多种不同长度的金属线各金属线段之间通过开关矩阵或反熔丝编程连接，走线灵活方便，但走线延时无法预测；连续互连型FPGA是利用相同长度的金属，连接与距离远近无关，布线延时是固定的和可预测的。根据编程方式，FPGA可分为一次编程型和可重复编程型两类。一次编程型采用反熔丝开关元件，具有体积小、集成度高、互连线特性阻抗低、寄生电容小和19皇兰型堇奎堂堡圭堕奎一高速度的特点，此外还具有加密位、防拷贝、抗辐射、抗干扰、不需外接PROM或EPROM的特点，但只能一次编程，比较适合于定型产品及大批量应用。可重复编程型FPGA采用SPAM开关元件或快闪EPROM控制的开关元件，配置数据存储在SRAM或快闪EPROM中。SRAM型FPGA的突出优点是可反复编程，系统上电时，给FPGA加载不同的配置数据就可完成不同的硬件功能，甚至在系统运行中改变配置，实现系统功能的动态重构，功耗也较SRAM型高。S23FPGA设计流程典型的FPGA设计流程包括5个基本步骤设计输入、功能仿真、设计实现、时序仿真和芯片构造。设计输入是指以图形或文本方式描述输出特定应用所需的逻辑功能。随着FPGA开发工具的普及，设计输入的方法也跟着丰富起来，除了普遍使用的原理图编辑器以外，还有ABEL、VHDL、VERILOGHDL等多种硬件描述语言。当FPGA设计的复杂度与密度达到万门以上时，采用硬件描述语言如VHDL可将设计的抽象层次提高，提高设计人员的工作效率。在设计输入完成后，通常要进行功能仿真，通过软件模拟对设计进行验证，以保证输入的设计在逻辑上正确无误。若有问题，则要返回到设计输入进行修改。通过功能仿真的设计可转入设计实现。首先由专门的网表转换软件将输入的设计变换成特定FPGA厂家所能接受的网表格式，然后进行工艺映射和布局布线。设计实现是FPGA设计的核心部分，现在各FPGA供应商提供的开发系统中均包含有版图自动设计工具，借助于这些工具，设计者只需按照要求进行一些功能指定和参数选择，系统便可自动完成网表转换、逻辑分割、布局布线，甚至自动生成配置FPGA芯片的结构代码。布局布线完成以后，可利用专门的软件来提起有关的器件延迟、连线延迟等时序参数，并在此基础上进行设计后仿真一时序仿真，以验证经过布局布线的设计在时序关系上是否满足要求。经时序仿真表明正确无误后可对FPGA编程，完成芯片构造。33EODSA的设计方案20皇王型垫奎堂堡主丝奎一椭圆曲线通常定义在FP域和E”域，由于E”域的加运算与通常所定义的加法运算有所不同，是逐位进行的，而没有进位，这一特点特别适合于硬件实现，对应于硬件结构即为逐位异或，而椭圆曲线的运算由模加、模乘、平方以及乘逆组成，实际上都分解为加法运算，因此，选用最“域对于提高系统的速度具有很大的意义；一般地，在有限域中的元素可以在两种基下表征正归基和多项式基。正归基对于平方运算特别地方便，只要通过一次移位即可，在时间上也只需一个时钟周期，但是对于乘法运算却十分的繁琐；而使用多项式基进行平方运算时，采用适当的算法，也可以用一个时钟周期完成，在资源上不超过M所选用的基的度个异或门，进行乘法运算时，有一个适合于硬件的算法，原理上特别简单，实现起来也很方便。由于用多项式基表征有限域中的元素具有以上优点，所以本课题选用多项式基。通过对ECDSA的实现的分析，采用模块化、层次化的设计思想，将其分为三大部分1椭圆曲线点乘，即LP的计算。这一部分是整个算法实现的关键部分，而且算法的实现的效率也主要由这一部分决定。这一部分的实现是在椭圆曲线上进行，运算单元主要是由异或门所组成，包括平方、模乘以及乘逆运算。2在FD域的运算，这一部分的加法运算要考虑进位，但是选用适当的器件，同样可以取得较高的速度；运算单元主要由加法单元所组成，有模乘和模逆两种运算。3安全散列函数，即SHA。这一部分实现起来逻辑上比较简单，但如果采用算法不当或编程不注意，往往需要耗费很多逻辑资源，在这里采用一些技巧，可以使资源得到很大的节约。以上三部分的结构框图如图31所示在每一个模块的设计实现时，又分为更小单元，每个单元都是采用VHDL进行设计输入，然后通过各个层次的仿真，最后在顶层设计时，通过控制单元，将各个模块连在一起，实现总的设计。2L皇三型垫查堂堡主堡兰图31ECDSA的硬件实现框图34EOOSA的开发平台本课题的前端设计，包括设计输入、编译、仿真以及综合都是在MENTOR的功能强大的FPGAADVANTAGE下完成的，它包括HDLDESIGNERSERIES输入及项目管理，MODELSIM仿真和LEONARDOSPECTRUM综合三个软件。在后端设计时，用XILINXALLIANCESERIES进行工艺映射和布局布线，它包括DESIGNMANAGER和FLOWENGEER。一皇王型垫盔堂堡主笙壅一第四章ECDSA的硬件实现在前面几章里，对ECDSA的相关原理、设计方法，以及硬件实现所涉及到的一些相关问题进行了分析，在这些基础之上就可以进行硬件设计。本章将具体介绍BCDSA的硬件设计以及相应的算法。在ECDSA的硬件设计中，采用了层次化、模块化的方法，在设计时对整个的椭圆曲线数字签名算法进行了多层次功能模块的划分，然后进行每个模块、每一层次的设计，完成后结合总体要求，再将这些模块组合起来就可以得到符合设计要求的ECDSA。对予各个层次上韵每个模块都需要进行仿真验证，以判断设计是否达到了要求。设计时只有通过对各个层次上的每个功能模块反复进行仿真、修改、再仿真，才能得到正确的设计结果。层次化、模块化的设计使整个设计工作更加容易实现，同时程序的维护性、纠错性都能相对提高。在进行ECDSA的硬件设计时，采用的是硬件描述语言VHDL作为设计输入方式。41椭圆曲线点乘即计算KP由于在椭圆曲线数字签名算法中的实现效率由计算椭圆曲线点乘的运算速度所决定，所以这一部分的实现在整个算法的实现中起着至关重要的作用。在计算椭圆曲线点乘KP的算法中，主要由在二元域的加、乘、平方以及乘逆组成。元域的运算规则已在前面作了介绍。由于在仿射坐标系下，在一般统计情况下，计算KP，要进行M次点加，M2次倍加。进行一次点加、倍加所需的运算见表41表41点加、倍加所需的运算次数点加倍加运算次数运算次数模乘2模乘3模平方1模平方1乘逆1乘逆1皇量型垫丕兰堡圭堡兰由上表可以看出，在仿射坐标下，不管是进行点加还是倍加运算，都要进行次乘逆运算，而进行一次乘逆运算等于数次的模乘运算。因此，在仿射坐标系下，完成KP的计算要以很长的时间为代价。为了避免多次的乘逆运算，下面讨论在射影坐标系下进行KP的运算。在射影坐标系下计算KP，比较常见的有两种算法一种为倍加一加点乘算法；另一种为蒙哥马利MONTGOMERY点乘算法。这两种算法的不同之处在于倍加一加算法既要进行相加运算，又要进行倍加运算；丽蒙哥马利点乘算法，只是对两个点，PL和P2的X一坐标进行运算。在这里，椭圆曲线由方程Y2砂X3甜26定义。表42，43分别列出了这两种算法。在这两个算法中，都设定K的二II进制表征为KY七F2其中七F，0。丽表42在射影坐标下的蒙哥马利点乘算法蒙哥马利点乘X，YKPPLP，P22PXL，ZBX2，Z2CONV_PROJECFIVEX，YFORI12DOWNTO0DOIFKI1THEN，P1XP1P2X，P2X2P2X，1，Z0MADDXL，ZL，X2，Z2，XP2，Z2MDOUBLEX2，Z2ELSE，卑P2XPIXP2X，P卜X2PTX，X2，Z2MADDX1，ZI，X2，Z2，XT，ZIMDOUBLEXT，Z0END难ENDFOR；RETURNCOMPUTE_XYXL，ZL，X2，Z2，X，YCONY_PROJEETIVEX，YXLX；ZLLX2X4BZ22X2RETURNXLZI，X2，Z2MADDXT，ZI，2Z2，XXLXLZX2ZLXXIZ2X2212；ZLIZ2X2ZI2MDOUBLECX2，Z2LETURNX224BZ24，Z2X22ZFLCOMPUTE_XYX1，ZL，X2，Z2，X，YXKXIZI，YKXTZLXX2Z2X2YT，ZLX，XY；RETURNXK，YK皇三型垫盔堂堡主笙苎表43在射影坐标下的倍加一加点乘算法倍加力X，Y，KADDX2，Y2，Z2，X1，Y1，Z1，Y,ZCONV_PROJECTIVEX，Y，IFPL；0THENRETURNPO，FXO，YO，Z0X，YZ产POPIFXI，YI，ZI0THENFORII2DOWNTO0DORETURNXO，YO，ZOX，YJZDOUBLEGYZP2PFELSEIFPOPLTHENRETURNOIFKILTHENPPPOELSEIFXO，YOZO一O1，YX，ZTXY，ZADD磁，YO，ZOXYZTHENRETURN0ENDIFPELSEIFPOPITHENLETUNL2POFENDFORTELSEIFXO,YO，Z0L，YL，Z1THENX，YCONYAFINEX，YZ；X2，Y2，Z2DOUBLEXO，YO，ZOLFETUL22X，Y；ELSERETURLLP2POPLUOXOZL2DOUBLEYZSOYOZL3PIFPOTHENRETURILOUIXL蔚IFX，YZOTHEN1ETULLLO；WUOUTELSEP0LLUFLL2P，SLYL牙Z2XZ2RSOSLX2XB1HZ24LZOWUZ2X2YZVRXLLYLY24Z2UX2Z2LZLENDIF；TRZ2RETURN，Y2,Z2X2AZ22TRW3Y2TX2VL2CONV_PMJECTIVEX,YEND征RETUMXX，YY,Z1；RETURLLX2，Y2,Z2从表42、43可以计算出E”域的点乘的复杂度，见表44电子科技大学硕士论文表44在E“域的点乘的复杂度复杂度蒙哥马利平均倍加一加平均平方5N1_137M117乘法61IRL10LO5FN13乘逆11由表44可以看出，使用蒙哥马利点乘算法的复杂度大大低于倍加点加算法，所以在椭圆曲线点乘算法中，采用蒙哥马利点乘算法。下面分别讨论平方运算、模乘运算以及乘逆运算在只”域的具体实现。411平方运算在前面已经讨论过，在使用多项式基进行平方运算时，可以在一个时钟周期完成，而且所使用的资源不超过M个异或门。现在详细讨论该算法的数学原理以及其相应实现在这里，使用的是三项式基厂G工4工1其中，M191，K9。MI令爿GQX为E“的任意元素。GG吼工42GMOD，G；口0口。工2口XMLO2AM1X2M2MODFX。MI_一2令_2B。AIX2叫；F口“M其中，包2A，当I为偶数时即IO，2，4，2M2；BL0，当I为奇数时即II，3，5，2M一3；M2I令QBLX。MODFXJO，虬罢一L勤为偶数；，蜘下M3，蚋奇数2M2色2以ZMODFX；当M为偶数时；，电子科技大学硕士论文2M3C。2BTX。MODFX当M为奇数时；了IO口G玩XMODFX；当M为偶数时；“MI12M一2GGBIXMODFXSO2CB2。_2X2“MODFX当M为奇数时；T一三一MIML则岛2BLXKWBMX“芝叫K6，；TO10，FL若当M为偶数时，K2争；即C0萋岛一十KK；当M为奇数时，6卅O；即M以一LOBM2X”2B2M一2工2”一2CIK“工”“6。2X”262。一2X2M一2；由于选用的多项式为辨191，K9。即M、K都为奇数，K，2，62。都等于0，现在令C2芝岛一2CO鱼。X”1COB。1X1MI6F一K。XK。X“LO。T一O。一M3C2荟W2QX”2B。3X1矿一1矿。荟6FX。KTXKX“1以。，6肿声“；MXKX以。MX包G4P啮岛XK咚一。62柚XM2纠6卅XKX“K，矿LOLUB,时3X362MLX础一16抓卜L工科一十62“T工科1B轩KTLX62俨2X卅262五X五62舻2X2卜2；1I为偶数QI包；IN，11XLN；C若YI1，SSX；D若SN，则SSN；3返回S；这种算法，主要是由移位、加减运算以及比较电路所组成。而比较电路所耗费的资源与加法器所耗费的资源相当。为了节省资源，将比较器转换为减法器，其具体实现为将输入信号以及在电路中所定义的中间信号的位数增加一位，即它们的位数为“如十L”位，其最高位定义为符号位，输入信号都是简单的在其最高位补0；在比较A与B的大小时，就将A减去B实质上就是A加上B的补码，若和数的最高位为1，则AB；现在，电路只由寄存器以及加减法电路所组成，而通过观察该算法，还可以做一些改进，使其电路只由加法电路就可以完成，改进的算法如下算法4改进的在F口域的模乘算法输入192位X，Y；192位模值N；输出XXYMODN421初始化XL一0X；ILL0N若“O1，则令SXL；否则S202令I从L到ML循环AXLXXXL；BXLXT一；若XLM11，贝UXL1LNL；C若YI1，则SSXL；DSS刀；若SM1L，则SSNL；3返回S；其中，拧表示NL的补码。算法的基本原理为在作比较运算比较数是否大于模数时，不进行比较，而直接将该数加上模数的补码，若输出为负数即当符号位为1时，则重新加上模数；否则，直接输出结果。由改进的模乘算法可知，整个的算法逻辑实现只由加法运算所组成，在平均时间上与算法3的比较见表45表45算法3与算法4的逻辑运算比较裔算法3算法4加法运算05M次35M次减法运算M次无比较运算2M次无总次数35M次35M次由表45，在改进的算法中，只由加法运算所组成，在逻辑上只需要一个加法运算器。而在算法3中，则需要加法器、减法器以及比较器。采用改进的模乘算法在时间上与原模乘算法的时间是一样的，因此，采用改进的模乘算法可以在相同时间实现模乘运算，而在逻辑资源上只用了193BITS的加法器，将比较器以及减法器都省略掉了。改进的模乘算法的设计输入还是采用YLTDL语言，其实体描述如下ENTITYMULPRIIS43皇王型垫查堂堡主笙苎一PORTCLK，RESET，STARTINSTD_LOGICA。BINSTD_LOGIC_VECTOR191DOWNTO0；NINSTDLOGIC_VECTOR191DOWNTO0；DONEOUTSTD_LOGIC；QOUTSTD_LOGICVECTOR191DOWNTO0；ENDMUL_PRI；其中，输入端口的A、B是待求模乘的被乘数和乘数，输入端口N为所选择的椭圆曲线的阶数，在这里作为模值。输出端口Q为模乘的结果。模乘MUL_PRI模块的逻辑符号如图4一11所示。图4一LL在艮域模乘运算的逻辑符号待分析完成在FP域中的乘逆运算之后，再通过联合仿真测试，来同时完成在素数域中的模乘和乘逆的仿真验证。422FO域的乘逆运算在FO域中进行乘逆运算，即计算出满足等式AXXLMOD小49的X的值，与扩展的欧几里德算法在计算满足等式41的X、Y值以及A与B的最大公约数GCDA,B的原理是相同的，只是在等式4一1，A与B是互素的，即它们的最大公约数为1，而且只需计算出X值。但是，在扩展的欧几里德算法中，需要进行除法运算，众所周知，进行除法运算是非常的耗费硬件资源。因此，在这里采用一种扩展的欧几里德算法的变形，尽管其增加了迭代次数，但是消除了除