（微电子学与固体电子学专业论文）有限域快速多项式相乘运算核的研究.pdf

摘要 摘要 有限域上的乘积运算是许多加密系统和编码理论的一种基本运算。有限域乘 法的运算效率在很大程度上决定了整个系统的性能。运算速度对于很多密码系统 来说至关重要，在一些密码系统里，其最主要的运算量来源于计算大量的有限域 整系数多项式的乘积。因此提高有限域整系数多项式乘法的速度对于这类密码系 统来说很有应用价值。 本文采用基于数论变换的算法结构，完成了有限域快速多项式相乘运算核的 设计及f p g a 实现和测试验证，包括从算法设计、系统结构设计、各个子模块的 设计和实现、系统联调仿真到f p g a 的下裁实现和测试整个流程。研究设计了一 种具有自主知识产权的高速、高精度的有限域多项式相乘运算核。提出了一种可 行的、易于硬件实现的结构，具有无误差、速度快、设计复杂度低的优点。在 x i l i n x 公司的1 0 0 万门的v i r t e x l i 器件上实现，进行一次两个2 5 6 点的有限域多 项式相乘仅需6 5 4us 。和采用3 台p c 并行处理的软件实现方法相比，速度有2 倍的提高；和采用1 台p c 处理相比，速度有7 倍的提高。可直接应用于数字签 名运算中。 本文有特色的主要工作如下： 1 、利用f e r m a t 数变换( f n t ) 的循环卷积性质进行整系数多项式相乘， 提高了运算的精度和速度。本文还利用迭代和多项式拆分相乘的技 巧，将高次幂多项式相乘转化为低次幂多项式相乘再进行迭加，克 服了f n t 运算点数的限制。并采用乒乓r a m 的结构提高运算能力， 得到流水线结构。 2 、采用类似基4f f t 的快速算法实现6 4 点f n t 。所设讨的f n t 模块 可并行处理两组数据。并具有可扩展的性能，可根据具体的要求实 现多组数据并行处理。 3 、采用新码码制进行f n t 运算。其中涉及的乘法运算和模运算均被方 便地转化为移位运算和加减法运算，有利于硬件实现。 4 、采用带进位的模加器和保留进位加法( m c s a ) 的结构提高f n t 和 模乘的处理速度并节省硬件资源。 5 、 运算核采用v i r t e x l i 系列x c 2 v 1 0 0 0 4 f 9 2 5 6 实现，最高工作频率可达 到1 0 0 m h z ，完成一次运算所需的时间为6 5 4ps 。并将本运算核成 功地应用于有限域多项式幂运算中。 关键词：有限域，快速算法，多项式相乘，f n t ，模乘 a b s t r a c t a b s t r a c t f i n i t ef i e l d m u l t i p l i c a t i o n i st h eb a s i c a r i t h m e t i c o p e r a t i o n o f m a n y c r y p t o s y s t e ma n dc o d i n gt h e o r y , t h ep e r f o r m a n c eo ff i n i t ef i e l dm u l t i p l i c a t i o ni so f u n n o s ti m p o r t a n tw h i c hw i l li n f l u e n c et h ep e r f o r m a n c eo ft h ew h o l e s y s t e m t i m e s p e n d i n c r y p t o g r a p h i cf u n c t i o n s c a nb ec r i t i c a lf o rt h e a v a i l a b i l i t y o fs e r v i c e s s i n c et h em a j o rw o r ki st oc a l c u l a t ea l a r g eq u a n t i t yo ff i n i t e f i e l d p o l y n o m i a l m u l t i p l i c a t i o ni ns o m ec r y p t o g r a p h i cs y s t e m s ，a c c e l e r a t i n gp o l y n o m i a lm u l t i p l i c a t i o n i sv a l u a b l ef o rt h e s e c r y p t o g r a p h i cs y s t e m s i nt h i s t h e s i s ，t h ed e s i g na n df p g ai m p l e m e n t a t i o nr e s u l to faf i n i t ef i e l d p o l y n o m i a lm u l t i p l i e ri sp r e s e n t e d ，w h o s ea r i t h m e t i ca r c h i t e c t u r ei sb a s e do nt h e n u m b e rt h e o r e t i ct r a n s f o r m i ti n c l u d e ss y s t e ma l g o r i t h md e s i g n ，s y s t e ma r c h i t e c t u r e d e s i g n ，h a r d w a r ea r c h i t e c t u r ed e s i g n ，a n dh a r d w a r ei m p l e m e n t a t i o na n df u n c t i o n v e r i f i c a t i o n t h em u l t i p l i e r , w h i c hh a sb e e ni m p l e m e n t e do nt a r g e td e v i c e ：x i l i n x v i r t e x i is e r i e sf p g a ：x c 2 v 1 0 0 0 4 f 9 2 5 6 ，h a st h ec h a r a c t e ro f h i g ha c c u r a c y , h i g h s p e e da n dl o wc o m p l e x i t y i ts h o w st h a to n c ec o m p u t a t i o nt a k e s6 5 4ps c o m p a r i n g t os o f t w a r es o l u t i o n ，t h ep r o c e s s o rp r o v i d e su pt o7t i m e ss p e e d u pi nt h ee x e c u t i o no f t h ec o m p u t a t i o n ，m e e t st h ed e m a n do f t h e d i g i t a ls i g n a t u r ea n d a u t h e n t i c a t i o ns y s t e m t h e s ew o r k sa r ep r e s e n t e di nt h i st h e s i s ： 1 、t h em u l t i p l i c a t i o n f r e ef e r m a tn u m b e rt r a n s f o r m ( f n t ) w i t ht h e c y c l i c c o n v o l u t i o np r o p e r t yi su s e df o rc a l c u l a t i n gt h em u l t i p l i c a t i o no ft w op o l y n o m i a l st o i m p r o v es p e e da n da c c u r a c y 6 4p o i n t sf n t i su s e df o rc a l c u l a t i n gt h em u l t i p l i c a t i o n o ft w op o l y n o m i a l sw h o s ed e g r e e sa r eb o t hl e s st h a n3 2 t h e nb yu s i n gi t e r a t i o n t e c h n i q u e s ，t h em u l t i p l i c a t i o no ft w op o l y n o m i a lm u l t i p l i c a t i o nw h i c hd e g r e e sa r e b o t hl e s st h a n2 5 6c a nb ec a l c u l a t e d a n dp i n g - p o n gr a ms t r u c t u r ei su s e dt o i m p r o v e t h ee f f i c i e n c yo f t h e c o m p u t a t i o na n d t og a i np i p e l i n es t r u c t u r e 2 、4 - b a s e d6 4p o i n t sf n tw h i c hh a st h es i m i l a ra r c h i t e c t u r ew i t h4 - b a s e df f ti s p r e s e n t e d t h e a r c h i t e c t u r em a yh a n d l et w og r o u pd a t ai np a r a l l e l 3 、n e w c o d i n gs c h e m e i su t i l i z e df o rf n ta n dm u l t i p l i c a t i o n t h ed a t ai s t r a n s f o r m e df r o mg e n e r a lb i n a r yr e p r e s e n t a t i o nt o n e w c o d i n gr e p r e s e n t a t i o n t h e n t h ec o m p u t a t i o n sa r es u i t a b l ef o rh a r d w a r ei m p l e m e n t a t i o nw h e r eam u l t i p l i c a t i o n o p e r a t i o nm a y b ep e r f o r m e d b yc y c l i cs h i f t i n go p e r a t i o n sa n d a d d i t i o n s s u b t r a c t i o n s 4 、m o d u l a rc a r r i e ds a v ea d d e r ( m c s a ) i su s e dt oi m p r o v et h ec o m p u t a t i o ns p e e d o f f n ta n d m u l t i p l i c a t i o n 5 、t h ew h o l es t r u c t u r eh a sb e e ni m p l e m e n t e do nt a r g e td e v i c e ：x i l i n xv i r t e x i i s e r i e sf p g a ：x c 2 v 1 0 0 0 4 f 9 2 5 6 t h em a x i m u mc l o c kf r e q u e n c yc a na c h i e v ei o o m h z t h a tm e a n so n c ec o m p u t a t i o nt a k e s6 5 4us k e yw o r d s ：f i n i t ef i e l d ，f a s ta l g o r i t h m ，p o l y n o m i a lm u l t i p l i c a t i o n ， f n t , m o d u l a rm u l t i p l i c a t i o n 链硕士学位论文答辩委员会成员名单 姓名职称单位备注 杨平雄教授华东师范大学 主席 李刚副教授华东师范大学 石艳玲副教授华东师范大学 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究 成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经 发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在 文中作了明确说明并表示谢意。 作者签名：盘苤 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子舨和纸质版。有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名舞谚 导师签名： 季乏害步 日期：丞盘：i ：至日期：! ! 型：! ： 第一章绪论 第一章绪论 1 1 弓l 言 随着计算机技术、信息技术的迅速发展，信息已是当今社会的一种重要财 富。但当人们享受信息技术带来的巨大变革的同时，也承受着信息被篡改、泄 漏、伪造的威胁，以及计算机病毒及黑客入侵等安全问题。全世界由于信息系 统安全的脆弱性而导致的经济损失逐年上升，安全问题日益严重。信息安全的 风险制约着信息的有效使用，并对经济、国防乃至国家的安全带来了威胁。也 就是说信息安全对现代社会健康有序地发展，保障国家安全和社会稳定有着重 要作用，对信息革命的成败有着关键的影响。密码技术是信息安全技术的核心， 它是实现保密性、完整性、不可否认性的关键。 密码技术用于保护军事和外交通讯可追溯到几千年前。密码学的发展经历 了几个阶段：从古代到1 9 4 9 年，可看作是科学密码学的前夜时期，该时期的许 多密码系统的设计仅凭直观的技巧和经验，缺乏系统的理论和方法；1 9 4 9 年香 农( s h a n n o n ) 发表了“c o m m u n i c a t i o n t h e o r y o f s e c r e c y s y s t e m ( 保密系统的信 息理论) ”0 - - 文，为现代密码学奠定了理论基础，从此密码成为一门科学。同 时他也提出设计密码的观点，它们构成“私钥密码学”的理论基础。1 9 7 5 年 n b s ( 美国国家标准局) 公布了由i b m 公司的h f e i s t e l 设计的d e s ( d a t a e n c r y - p t i o ns t a n d a r d ) 加密算法，并于1 9 7 7 年将它批准为数据加密的联邦标准【3 】。 d e s 的公布和采用为标准是密码学发展史上的一个里程碑。密码学的另一个重 大事件发生在1 9 7 6 年，d i f f i e e 和h e l l m a n 发表了题为“n e wd i r e c t i o ni n c r y p t o g r a p h y ”( 密码学的新方向) 2 】一文，导致了密码学的一场革命，开创了 公钥密码的新体制。它使得从发送端到接收端进行保密通信不再需要密钥传送， 从而公钥密码学不仅可以用于保密，还可以用于认证。1 9 7 8 年出现第一个r s a 公钥加密和签名方案，它基于大整数素因子分解难解问题。1 9 8 5 年又出现一个 基于离散对数问题的e l g a m a i 公钥加密方案p j 。 公开密钥密码编码学的发展是整个密码编码学历史上的一次真正的革命。 公钥密码编码学与以前的所有方法都截然不同，一方面公开密钥算法基于数学 函数而不是替代和置换，更重要的是，公钥密码编码学是非对称的，它的主要 特点是将加密和解密能力分开，因而可以实现多个用户加密的消息只能由一个 用户解读，或只能由一个用户加密消息却能由多个用户解读。前一种方式可用 于保密通信，第二种方式可用于对消息的认证。它用到两个不同的密钥，一个 华东师范大学硕士学位论文一一有限域快速多项式相乘运算核的研究 第一章绪论 用于加密算法，一个用于解密算法。从公开密钥加密工作中获得的最重要的进 展是数字签名认证。 用户a 图1 1 公钥密码认证示意图 用户b 如图1 1 所示，用户a 产生一对密钥，个密钥( k 2 ) 用于加密，只有发送 方知道，即私有密钥。一个密钥( k 1 ) 用于解密，放在公开场合，即所谓的公开 密钥。用户a 用l ( 2 对消息m 加密后得到密文c ，再把c 发送给用户b 。b 收到 密文后用a 公布的公开密钥k l 来解密。其它所有人都无法伪造一个密文发送 给b 并声称是a 发送的。因为除了a 自己外，其它任何人都不知道a 的私有 密钥，也就无法伪造期望中的密文并称是a 发送的。这样就实现了对a 所发消 息的认证。 公钥加密的优点是：大型网络中每个用户需要的密钥数量少；对管理公钥 的可信第三方的信任程度要求不高而且是离线的；只有私钥是保密的，而且公 钥只要保证它的真实性。但公钥加密最显著的缺点是多数公钥加密运算复杂， 速度比私钥加密的速度要慢几个数量级。而且公钥加密方案的密钥长度比对称 加密的密钥要长，公钥加密方案也没有被证明是安全的。因此公开密钥一般使 用在仅有少量数据需要传输的情况下( 如数字签名、传送对称密钥算法中的密 钥等) 。 在现代加密体制中，消息在加密和传送之前是以数值的形式表现出来的。 加密过程是将输入值转换为输出值的数学运算过程。构建、分析和攻击这些密 码体制都需要数学工具，其中最重要的是数论，尤其是有关同余的理论。而随 着现代数字通信技术的发展，目前数字通信系统对数据传输速率的要求越来越 高，因此对加密系统的性能要求越来越高，需要快速又安全地实现这些系统。 许多完成身份认证、加密解密等的公钥密码体系都需要基于有限域上的运算， 如r s a 算法，d s a 算法，d i f f i e h e l l m a n 密钥交换算法，椭圆曲线加密算法， 椭圆曲线数字签名算法等。这些加密算法的所有性能都取决于其包括的有限域 华东师范大学硕士学位论文一一有限域快速多项式相乘运算核的研究 第一章绪论 运算的效率。因此提高有限域运算效率是必须解决的问题。 1 2 有限域发展现状 1 2 1 有限域发展概述 对有限域理论的研究最早可追溯到1 9 世纪pj 。数学家g a u s s 、a b e l 和g a l o i s 为了解决高次方程的解析解的问题而逐渐引出关于有限域的研究。特别是 g a l o i s 在1 8 2 8 年至1 8 3 1 年研究代数方程的可解性问题时，受复数概念的启发， 引出了g a l o i s 虚数的概念，这其实就是现在所说的有限域的元素。正是用这种 方法，他实际上提出了有限域理论特别是有限扩展域的理论。当时虽然还没有 抽象的群和域的名词，但g a l o i s 确实用到了群和域这些概念，因此他被认为是 近代抽象代数的创始人。所以有限域也被称为g a l o i s 域。1 9 0 1 年，d i c k s o n j 对此领域进行了进一步地、彻底深入地探索研究。g a l o i s ( 伽罗瓦) 域对近代数 学的发展产生了深远影响，它已渗透到数学的很多分支中。香农在1 9 4 8 年引进 了信息理论以及相关领域：代数编码理论 9 】，这对有限域领域提出了新的问题。 之后，有限域逐渐被用来解决各种工程技术问题。这些领域包括代数编码、加 密算法、随机数产生、数字信号处理和v l s i 测试等领域。随着现代数字通信 技术的发展和电子商务的安全性的需要，有限域在代数编码和加密算法应用中 变得越来越重要。 在许多加密系统和编码理论中，都要用到一个基本模块：有限域运算。在 数据的传输和存储的过程中，信道编码是必不可少的。纠错码一般都是定义在 有限环或有限域上的。其中r e e d s o l o m o n 纠错码是最常用的编码方式之一。它 可广泛应用于卫星通信、计算机网络、磁光存储器件中等，并已被e s a 、n a s a 规定为卫星通信的标准编码算法。而r e e d s o l o m o n 算法也是基于在有限域上的 运掣1 0 】。而对于加密算法如r s a 算法，d s a 算法，d i f f i e h e l l m a n 密钥交换算 法，椭圆曲线加密算法，椭圆曲线数字签名算法等，都需要基于有限域的运算。 随着现代数字通信技术的发展，目前数字通信系统对数据传输速率的要求越来 越高，因此对加密系统和编码系统的性能要求越来越高，需要快速又安全地实 现这些系统。既然有限域运算是这些系统的基础，提高有限域运算的速度成为 必须解决的关键问题。 12 2 有限域乘法运算研究现状 有限域中的算术运算包括加法、乘法、幂运算、除法运算等。根据有限域 在加密和编码中的应用，对有限域的研究大都集中在有限域乘法运算的研究上， 华东师范大学硕士学位论文一一有限城快连多项式相乘运算核的研究 3 第一章绪论 因为在有限域运算中，有限域乘法是最重要的一种运算，幂运算和除法运算都 可以通过乘法运算构建实现。而且有限域乘法也是最复杂和最耗费时间的运算， 简单、高速地实现有限域乘法很有必要。人们对如何提高有限域乘法的速度已 经做了很多研究和讨论。这些研究大都从两个方面着手解决：一是从算法角度 进行改进，采用更先进有效的算法来实现有限域乘法。二是从硬件实现角度进 一步提高速度，设计高效，简单的硬件电路来实现有艰域乘法。因此对有限域 的代数运算的硬件实现结构的研究引起很多研究人员的重视。 根据有限域运算应用的不同，有限域乘法可以根据有限域类型的不同分为 三类： l 、 g f ( 2 “) ( 为正整数) 上的乘法， 2 、g f ( p ) ( p 为大素数) 上的乘法， 3 、g f f p ”) ( p 为素数，n 为正整数) 上的乘法。 g f ( p ) ( p 为大素数) 上的乘法是利用余数制系统的数字信号处理应用的 基本模块。而现有的许多成熟的加密算法如椭圆曲线加密算法，r s a 算法以及 编码理论如r e e d - s o l o m o n 算法又都是基于有限域g f ( p ) 的情况或g f ( 2 ”) 的情 况。所以现有的研究多集中在这两种情况的乘法实现上。 关于g f ( 2 ”) 域的乘法器的研究，按照参加运算的数的形式来分有3 种【l i 】： 正规基( n o r m a l ) 、标准基( s t a n d a r d ) ( 或多项式基) 、和双基( d u a l ) 。按照结 构来分又可分为基于比特的全串行的结构、全并行的结构以及串并结合的混合 结构。双基乘法主要采用被乘数为双基表示，而乘数采用标准基表示，结果仍 用双基表示f 1 2 】。m a s s e y o m u r a 乘法中的乘数和被乘数都用正规基表示，乘积项 的每一个分量可用同一个函数表裂”州】。该乘法器对有限域元素的平方运算及 指数运算非常有效。这种方法实现的乘法器面积较小，但需要将有限域中的元素 用特殊的基表示，且与有限域中的本原多项式选择有关。而 s c o t t t a v a r e s 。p e p p a r d 乘法算法中则采用标准基来表示有限域中所有的元素【1 “。 b e r l e k a m p 位串法乘法器的乘数用对偶基表示，被乘数用标准基表示，乘积项用对 偶基表示，乘法器只需移位和异或运算。对于1 1 比较小的情况下，在制表存储量 许可的情况下，还可利用直接查表法实现，将有限域的每个元素用本原元的指 数表示，并在r o m 中存储每个元素的对数及反对数，有限域中任意2 个元素的 乘积可通过查表获得。其算法最简单、运算速度最快。 华东师范大学硕士学位论文一一有限域快速多项式相乘运算核的研究 第一章绪论 关于舒( p ) 域乘法器的研究，目前主要有先乘法后模简化和边乘法边模简 化二大类实现方式。从算法上主要有以下算法用于实现模乘：b a l k l e y 算法 1 6 】 将模乘转化为一系列加法进行计算。算法为使最终结果小于p ，每次计算都需 对累加中间结果进行模简化。m o n t g o m e r y 型算法是一种有效的进行模乘的算法 7 j ，其设计思想是借助一个新的特殊剩余系，将普通模乘转换为易计算的特殊 模乘。m o n t g o m e r y 算法不含除法，基本运算为字乘和字加。它通过剩余系转换 方法计算模乘，极大地提高了模乘计算速度，被广泛应用于各种软硬件实现中。 多年来，人们从高效率、低空间、高安全等角度对算法进行了各种改进【1 8 】 1 ”， 提出了不少改进方法。例如，清华大学微电子所采用m o n t g o m e r y 模乘的一种 高进制的变型算法c d s 设计出了一种新型的可作为协处理器使用模运算处理 器，运算数据的长度可变，范围从2 5 6 b 到2 0 4 9 b 。该处理器时钟频率可达6 0 m h z ， 在该工作频率下完成1 0 2 4 b 模幂的时问为5 7 m s 2 0 1 。在密码学领域，还有- g e e 特 殊的模乘：费马数( 形式为f = 2 6 + l ，b = 2 。，t 为自然数的数) 的模乘作为一种 特殊的运算在现代的加密算法中有着特殊的作用。对这种模乘的研究主要是采 用重编码技术，选择可以有效的表示算术模2 6 + 1 的编码来实现模乘【2 1 】；在结构 上采用基于保留进位模加器( m c s a ) 的新模乘结构实现高速数据运算 2 2 1 。 随着椭圆曲线加密算法、超椭圆曲线加密算法以及一些基于代数群理论的 加密算法的发展，g f ( p “) ( p 为大素数) 的情况逐渐得到重视。对卯( 尸”) ( p 为大素数) 上的乘法运算这一问题进行研究，现有文献大多从以下两个方面着 手解决【2 副：一是从能实现所需运算的快速算法角度减少乘法的次数，如快速傅 立叶变换( f f t ) 2 4 】和数论变换( n t t ) 2 5 1 的进一步发展。 f f t 变换的循环卷积性质可以用来有效地计算两个长离散序列的循环卷 积。采用f f t 进行卷积计算需要复数乘法运算，这需要大量的计算时间。另外， 用f f t 进行循环卷积运算会带来显著的舍入误差，会降低信噪比。当采用数字 电路处理数据时，有限的数据宽度使数据只能在有限的精度内有效，因此，不 失一般性，数据都可以看成是有一定上限的整数。在这样的数字领域，复数域 实际上可以用有限域代替，或者一个整数有限环，其上的加法和乘法都是模加 和模乘。这样的环里，采用类似离散傅立叶变换的变换，可以有效的进行循环 卷积运算，并且没有任何舍入误差。i “u t h 2 6 1 于1 9 6 9 年提出了这种有限域变换 的应用。p o l l a r d 2 7 】讨论了在有限域内具有循环卷积性质的这种变换，即数论变 换。并给出了在有限整数环内变换具有循环卷积性质的条件。s c h o n h a g e 和 s t r a s s e n 2 8 1 定义了模f e r m a t 数的、具有循环卷积性质的变换并讨论了变换在大 整数快速相乘的应用。n i c h o l s o n 2 9 提出了在任意环内有限傅立叶变换的代数理 华末师范大学硕士学位论文一一有限域快速多项式相乘运算核的研究 第一章绪论 论，并建立了类似快速f f t 的算法来计算这些变换。r a d e r 3 0 3 1 提出了在模 m e r s e r m e 数和模f e r m a t 数整数环上的有限域变换。他首次提出了数论变换在数 字信号处理的应用，阐明了该变换可以只用加法和移位进行计算。他还指出了 字长的限制并建议可以采用两维变换来克服这种限制。f e r m a t 数变换己被用于 快速数字卷积 3 2 、数字滤波 3 4 、多项式相乘、相关和自相关等领域。和 传统的f f t 方法相比，数论变换能产生精确的结果，计算无误差，可以用类似 f f t 的算法实现，能用移位代替乘法、更适合硬件实现。这对于一些需要高速、 没有误差的的计算非常合适。 二是发展并行结构和更快的数制系统获得更高的吞吐量，如多项式余数数 制系统( p r n s ) 3 7 1 3 8 1 ，将多项式相乘分解成多个多项式并行相乘，提高了吞 吐量，但也增加了数制系统转换的过程。这类方法适合不可约多项式形式为 x ”1 的情况。而且基本都是基于软件方法来实现，硬件实现方面还未见报道。 1 3 本论文的选题意义和研究内容 1 3 1 本论文的选题意义 卯( p “) 上的乘法在很多领域应用广泛，如利用卯”) 谱实现循环卷积 3 9 】 4 0 1 ，纠错系统4 0 和加密系统。特别地，在电子商务、网上银行、政府办公 等特别需要安全性的应用中，鉴别信息的来源显得非常重要，因此要经常验证 签名公式。例如，某公司收到另一个生意合作伙伴公司的很多带有数字签名的 报文，就需要逐个验证签名公式。这样，加快签名公式的验证速度对于提高整 个密码系统的运行效率就很重要。许多完成身份认证、加密解密等的密码体系 是基于有限域上的。在一些基于g a l o i s 域的数字签名方案中，最主要的计算量 来自于验证公式 月( x ) 。兰u ( x ) 矿( x ) 1 ( m o d x 9 一x 一1 ，p ) 。 由于多项式的幂次运算可以转化为多项式相乘和多项式平方，所以上述验 证公式的计算量可以归结为模型 a ( x ) b ( x ) m o dg ( x ) ，p ， 其中a ( x ) 和曰( z ) 表示次数不超过p 一1 的不确定多项式，丽g ( x ) 表示某个固 定的p 次多项式。 华东师范大学硕士学位论文一有限域快速多项式相乘运算核的研究 第一章绪论 这正是扩展域g f f p “) 上的多项式乘法，是有限域运算中最重要的一种运 算，也是最复杂和最耗费时间的运算。从系统设计的观点来看，有效的乘法结 构尤其重要，因为大多数先进的运算函数，如求幂和求逆运算都是基于乘法运 算。单纯使用软件来实现乘法运算，速度会非常慢，且安全性不高。因此提高 这种有限域乘法的运算速度成为必须解决的关键问题之一。 本论文的研究属于上海市科委集成电路设计创新项目一数字签名算法运 算i p 核( 项目编号：p d c 0 2 7 0 6 2 0 1 2 ) 的主要部分。主要研究内容为完成有限 域g f ( p ) 中的多项式相乘：a ( x ) - b ( x ) ；c ( x ) m o d p ( x ) ，p 。由于采用软件进行 运算速度慢，难以满足系统的性能要求，必须进一步采用硬件方法来实现。本 论文的工作可直接应用于该运算的硬件化，大大提高其运算速度和安全性，从 而提高整个运算系统的效率。 1 3 2 本论文的研究内容 本论文主要根据应用的要求，研究运算速度快、精度高、易于硬件实现的 有限域g f ( p “) 内多项式相乘运算核，使其速度与安全性等各项指标都得到明显 提高。重点针对精度高、速度快的有限域多项式相乘的运算核的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 ) 实现进行了研究。在算法选择上利用基于 f e r m a t 数变换的算法快速实现多项式相乘，采用预计算的多项式除法进行多项 式求模运算。在具体实现方面，采用t o p d o w n 的设计方法学，结合底层基本 有限域运算硬件电路的设计，在优化算法的同时，根据f p g a 的特点研究设计 高效的、适合f p g a 实现的硬件结构。并用高速的f p g a 实现，对运算核进行 测试验证。具体研究内容涉及算法选择、硬件结构选择、基本有限域运算硬件 结构优化、系统仿真、f p g a 实现验证。论文各章的具体内容如下： 第一章简单介绍了有限域的应用、发展概述以及有限域乘法运算的一些研 究现状。并阐述了选题的意义和论文内容。 第二章介绍了一些数学理论基础包括有限域、数论变换( n t t ) 和f e r m a t 数论变换( f n t ) 等基本概念。并分析比较了f n t 和f f t 各自的特点和优缺点， 最后选取了f n t 的快速算法实现多项式相乘。还详细介绍了如何利用快速f n t 计算两个多项式乘积的方法以及如何克服f n t 的不足，通过建立一个低次幂的 多项式相乘模块，进一步构造高次幂的多项式相乘。 第三章介绍了整个有限域快速多项式运算核的算法结构。建立低次幂的多 项式相乘模块，并通过调用低次幂的多项式相乘模块把高次幂的多项式相乘分 华东师范大学硕士学位论支一一有限域快速多项式相乘运算核的研究 第一章绪论 解成多个低次幂的多项式相乘的方法实现算法。其中包括选择新码进行数论变 换、利用数论变换的循环卷积性质进行多项式相乘、采用多项式除法预计算的 方法进行求模、乒乓r a m 结构实现流水线结构。 第四章为有限域快速多项式运算核的电路设计，包括基本的基于新码韵大 整数模加运算电路、模乘运算电路的设计，可扩展并行处理的基4f n t i f n t 模 块的设计，基于查找表的累加及求重模结构，控制部分和端口控制模块等。 第五章阐述了整个运算核的f p g a 实现验证过程，包括运算核的f p g a 实现 步骤、所消耗的资源及相关的测试。最后介绍了运算核应用于有限域多项式x 次幂运算的情况，该应用已通过上海集成电路设计研究中心( i c e ) 集成电路检 测实验室的测试。 第六章对整个论文进行了总结和讨论。 华东师范大学硕士学位论文一一有限域快速多项式相乘运算核的研究 第_ 7 - 章快速f e r m a t 教变换的算法 第二章快速f e r m a t 数变换的算法 2 1 有限域理论基础 为了对所要研究的问题有个清楚的认识，首先从应用角度对有限域的基本 理论做简要介绍。下面的介绍不涉及具体的数学证明过程。 2 1 1 有限域定义 取定p 是素数，那么整数集合 o 1 ，p - 1 ) 就组成了一个有限域，也称为伽 罗瓦域( g a l o i s 域) ，并用g f ( p ) 表示。伽罗瓦域g f ( p ) 中的元素具有以下算术 运算： 加法。如果口，b g f ( 尸) ，则a o b = r ，其中，是口+ 6 被p 除所得的剩余， 0 r 兰p 一1 。 乘法0 如果，b g f ( p ) ，则a 0 6 = s ，其中s 是d - 6 被p 除所得的剩余， 0 s p 一1 。 这里，伽罗瓦域g f ( p ) 对于加法和乘法是封闭的，即指g f ( 尸) 中的任何两 个元素加法和乘法( 按上面定义的加法和乘法) ，其结果仍为g f 妒) 中的元素。 2 1 2 有限域上的多项式和不可约多项式 伽罗瓦域上的运算大量地应用于现代密码学方面。整个数论运算都可在其 中进行，它给数一个限定范围，除法将不会有任何舍入误差。许多密码方面的 算法都基于g f ( p ) ，但为了使得算法更加复杂从而更不容易遭受攻击，密码算 法的设计者也经常使用伽罗瓦域g f ( p ) 上的多项式。 一个多项式爿( z ) = q 工，如果式中的系数qe g f ( p ) ，则此多项式为伽 i = o 罗瓦域g f ( p ) 上的多项式。 伽罗瓦域g f ( p ) 上的不可约多项式定义为：设p ( x ) 是g f ( p ) 上的n ( 1 ) 次 多项式，若p ( x ) 不能表示为p ( z ) = 4 ( x ) ob ( x ) ，式中4 ( x ) ，口( x ) 是g f ( p ) 上的次 华东师范大学硕士学位论文一一有限域 夹速多项式相乘运算核的研究 9 第二章快速f e r m a t 数变换的算法 数不低于1 次的多项式，则称p ( x ) 是g f ( 尸) 上的不可约多项式。此处 a ( x ) o b ( x ) 表示多项式a ( x ) 和b ( x ) 在模p 意义下的乘积，也即一( 功和占( 功先 做普通的多项式乘法，然后表示乘积的多项式的每个系数都要模p 。例如能够 验证，多项式x 一x l 就是g f ( p ) 上的不可约多项式。 2 1 3 重模运算 取定伽罗瓦域舒( 尸) 上的n 次不可约多项式p ( x ) ，现在约定下面遇到的 p ( x ) 总表示此处取好的不可约多项式p ( x ) 。g f ( p ) 上的任意多项式a ( x ) 关于 r o o d p ( z ) ，p 】做重模运算可以这样理解：先求爿( 工) + p ( x ) 的余式r ( x ) ，显然， r ( x ) 是一个次数不超过n 1 次的多项式，再让r ( 艽) 的每个系数对p 求余，设这 样所得到的多项式为“x ) ，则r ( x ) 就是a ( x ) 关于 m o d p ( x ) ，尸】做重模运算的最后 结果，即a ( x ) ；r ( x ) m o d p ( x ) ，p 。 2 1 4 扩展有限域 接下来引进完全剩余系的概念。设r ( x ) 是伽罗瓦域g f ( 尸) 上的次数不高于 m l 的某个多项式，则所有满足同余式a ( x ) = r ( x ) m o d p ( x ) ，p 的伽罗瓦域 g f ( p ) 上多项式a ( x ) 便构成了一个集合，也就是关于重模 m o d p ( x ) ，p 】的多项 式类( r ( x ) 。 因为伽罗瓦域g f ( p ) 上总共有p n 个次数不高于n 1 次的互异多项式，相应 地便有p “个关于重模 r o o d p ( x ) ，p 的多项式类。从每一类当中各取一个多项式， 可得p n 个多项式，这p “个多项式就构成了一个完全剩余系。通常用次数不高于 n 一1 的p 8 个多项式表示重模 m o d p ( x ) ，p 的完全剩余系。我们以g f ( p ) 表示该 完全剩余系，事实上，此时的口( 尸“) 也是一个有限域，成为扩展域。扩展域 g f ( p 一1 中的元素与伽罗瓦域g f ( 尹) 不同，他们已不再是整数，而是系数在 华东师范大学硕士学位论文一一有限域快速多项式相乘运算核的研究 第二章快速f e r m a t 数变换的算法 g f ( p ) 上，次数不高于n 一1 的g f ( p ) 上的多项式。 g f ( p “) 中的元素具有以下算术运算。设有g f 妒”) 上的两个元素 a ( x ) = a o + a l x + + a n _ i x 4 1 + + a n _ i x ”一 b ( 功= b o + 扫l x + + 吒一f z ”_ 1 + + 6 。一j z 8 - 1 则这两个元素a ( x ) 与b ( x ) 的加法和乘法分别定义为 加法a ( x ) 0 b ( x ) = c o + c i z + + c 。一i x “， 其中，c 。= a ，o b 。，即c 。是a 。+ b 。被p 除所得的最小非负剩余，0 c f p - 1 f = 0 n 一1 。 乘法一( z ) o b ( z ) = c o + c i 工+ + c 。一i x ”“ 其中，0 c s p - 1 ，i = 0 刀一1 。记c ( x ) = c o + c i x4 - + c 。一l x ”，贝0c ( x ) 满足同余式a ( x ) 1 3 ( x ) ；c ( x ) m o d p ( x ) ，p 】，此处a ( x ) - 日( x ) 表示普通的多项式乘 法。 2 2 数论变换、快速数论变换和f e r m a t 数变换( f n t ) 下面介绍本文采用的研究方法：数论变换。并将进一步介绍如何采用数论 变换的方法计算整系数多项式乘积运算。 1 9 7 1 年，p o l l a r d 2 7 1 在有限域上定义了数论变换。数论变换是以正整数m 为模的整数环z 。上定义的线性正交变换，所用的运算法则是数论中的同余运 算。整数环z m 是指整数集合 o ，l ，m 一1 。 定义2 1 1 设x i z r ( f _ 0 , 1 ，n 一1 ) ，如果作用在序列x o ，玉，x 上的一个 一l 变换五；x 。口“( m o d m )( i = o 1 ，n 一1 ) ，a a z ( 2 1 ) 不但具有如下形状之逆变换 一l x 。= n 。口”( r o o d m )( = o ，1 ，n 一1 ) ( 22 ) k = o 而且具有循环卷积性质。则称式( 2 1 ) 给出的变换为z u 上一个长为n 的数论变 华东师范大学硕士学位论文一一有限域快速多项式相乘运算核的研究 1 1 第二章快速f e r m a t 数变换的算法 换或一个z m 上的d f t ，或简记为n t t 。 要使数论变换具有快速计算的效果，通常需要满足三个条件： 1 、长度n 适合具有f f t 类型的快速计算，对二进制来说，n 最好为2 的方幂。 2 、由于需进行大量乘a 的运算，所以，选择数论变换中的a 之二进制表示的位 数越少越好。以a 是2 的方幂最理想。 3 、为了便于模m 的运算，选取m 之二进制表示的位数愈少愈好。 我们把和f f t 一样的