（微电子学与固体电子学专业论文）算法空间中离散对数逻辑研究与shank算法ip设计.pdf

摘要 摘要 目前，e l o a m a l 公钥密码体制是继r s a 公钥密码体制之后的又一个公钥密码 体制，此公钥密码体制是建立在求离散对数的困难性上的。另外基于离散对数的 困难性的应用还包括密钥交换和数字签名等领域，因此离散对数问题引起了广泛 的研究，一方面是在信息安全领域中基于离散对数困难性的加密系统等的研究和 发展，而另一方面求解离散对数的算法也有了广泛的研究。求解离散对数的算法 目前主要有四种，s h a n k 算法、分解整数的p o l l a r dh e l l m a n 算法、p o l l a r dp 算法 和指数演算的方法。其中分解整数的p o l l a r d _ h e l l m a n 算法、p o l l a r dp 算法和指 数演算的方法是建立在大数因式分解基础上，大数因式分解本身就是数学上的一 个困难问题，因此在电路上也不容易实现。s h a n k 算法是求解离散对数算法中比 较快速且要求较少存储资源的一种算法。 随着集成电路工艺的发展，i c 规模越来越大，复杂度越来越高，同时，片上 系统( s o c ) 的兴起使电子工业对设计的可重用性表现出高度的兴趣。i p 是指集 成电路设计中所采用具有独立知识产权的可重用的功能模块，其英文名称为 “i n t e l l e c t u a lp r o p e r t y ”。集成电路设计中利用i p 资源可以缩短相应的设计周期， 同时也可以提高一次流片的成品率。尤其是在要求实现片上系统( s o c ) 的今天， 充分利用i p 核可以使系统级芯片的功能更为强大。 本文分析了s h a n k 算法的流程和资源需求，运用自顶向下的设计流程，采用 j r 可重组逻辑技术，提出了一种比较优化的算法i p 模型，并将此模型转换为软 i p 核，并最后对s h a n k 算法口核进行仿真验汪。 关键词：离散对数，s h a n k 算法，衅，可重组逻辑 n o w a d a y s ，e l g a m a lp u b l i ck e yc i p h e rs y s t e mi sa n o t h e rc i p h e rs y s t e mc o m e s a f t e rr s ap u b l i ck e yc i p h e rs y s t e m ，t h i sc i p h e rs y s t e mi sb a s e do nt h ed i f f i c u l t yo f s o l v i n gd i s c r e t el o g a r i t h m a p p l i c a t i o n sb a s e d o nt h ed i f f i c u l t yo fd i s c r e t el o g a r i t h m i n c l u d es u c hf i e l d sa sk e ye x c h a n g ea n dd i g i t a ls i g n a t u r e ，s ot h er e s e a r c ho nt h ea r e a o fd i s c r e t el o g a r i t h mi se x t e n s i v e o no n eh a n d ，e n c o d i n gs y s t e m sb a s e do nt h e d i f f i c u l t yo fd i s c r e t el o g a r i t h mi ni n f o r m a t i o ns a f e t yf i e l da r ei n v e s t i g a t e d ，o na n o t h e r h a n d ，a l g o r i t h m so fs o l v i n gd i s c r e t el o g a r i t h ma r ew i d e l ys t u d i e d t h e r ea l em a i n l y f o u rk i n d so fd i f f e r e n ta l g o r i t h m ss o l v i n gt h ed i s c r e t el o g a r i t h m ：s h a n ka l g o r i t h m ， p o l l a r d _ h e l l m a na l g o r i t h m ，p o l l a r dpa l g o r i t h m ，a n de x p o n e n ta l g o r i t h m a m o n g t h e m ，p o l l a r d _ h e l m a na l g o r i t h mu s e dt od e c o m p o s ei n t e g e r ，p o l l a r dpa l g n f i t h m ，a n d e x p o n e n ta l g o r i t h ma r eb a s e do nt h ef a c t o r i z a t i o no fg r e a tn u m b e r , w h i l ef a c t o r i z a t i o n i t s e l fi sad i f f i c u l tp r o b l e mi nm a t h s h a r ka l g o r i t h mi sam u c hm o r ef a s ta n d r e s o u r c e s a v i n gm e t h o di na l lt h ea l g o r i t h m si n t e n d e dt os o l v ed i s c r e t el o g a r i t h m w i t ht h ed e v e l o p m e n to fi n t e g r a t ec i r c u i tt e c h n o l o g y , t h ei cs c a l eb e c o m e sm o r e a n dm o r el a r g ea n dc o m p l i c a t e d w i t ht h ee m e 画n go fs y s t e mo nc h i p ( s o c ) t h e e l e c t r o n i ci n d u s t r ys h o w sg r e a ti n t e r e s ti nt h er e u s a b i l i t yo fad e s i g n i ni cd e s i g n ，t h e u s a g eo fi pr e s o u r c ec a l ls h o r t e nt h ed e s i g nc i r c l e ，a n da l s oc a nr a i s et h ec h a n c eo f o n e - t i m et a p eo u t a n dc a nm a k et h ef u n c t i o no ft h es y s t e mc h i pe v e nm o r es t r o n g t h i s p a p e ra n a l y z e dt h e r e s o u r c e r e q u i r e m e n t so ft h es h a n ka l g o r i t h m a t o p d o w nd e s i g nf l o wi sc h o s e n ，w i t ht h et h ee m p h a s i so i lr e c o n f i g u r a b l el o g i c t e c h n o l o g yao p t i m i z e di pm o d e li sp u tf o r w a r d ，a n dt h e nt u r n e di n t os o f t w a r ei p c o r e a tt h ee n do ft h ep a p e r , t h er e s u l t so fs i m u l a t i o na n dv e r i f i c a t i o no ft h ep r o p o s e d s h a n ka l g o r i t h na r ep r e s e n t e d k e yw o r d ：d i s c r e t e l o g a r i t h m ，s h a n k a l g o r i t h m ，i n t e l l e c t u a l p m p e r t y ，t h e r e c o n f i g u r a b l el o g i ct e c h n o l o g y 第一章引言 第一章引言 目前，e i g a m a l 公钥密码体制是继r s a 公钥密码体制之后的又一个公钥密码 体制，此公钥密码体制是建立在求离散对数的困难性上的。另外基于离散对数的 困难性的应用还包括密钥交换和数宇签名等领域，因此离散对数问题引起了广泛 的研究，一方面是在信息安全领域中基于离散对数困难性的加密系统等的研究和 发展，而另一方面求解离散对数的算法也有了广泛的研究。 目前求解离散对数的算法主要有四种，s h a n k 算法、分解整数的 p o l l a r dh e l l m a n 算法、p o l l a r dp 算法和指数演算的方法。其中分解整数的 p o l l a r dh e l l m a n 算法、p o l l a r dp 算法和指数演算的方法是建立在大数因式分解基 础上，大数因式分解本身就是数学上的一个困难问题，因此在电路上也不容易实 现。s h a n k 算法是求解离散对数算法中比较快速且要求较少存储资源的一种算 法。本文分析了s h a n k 算法的流程和资源需求，提出了一种比较优化的算法i p 模型，并将此模型转换为软i p 核。 1 1 课题研究的现状 1 2 1 离散对数的算法 目前，应用在密码学中的数学困难问题有两个，一个是大数的因式分解，其 中r s a 公钥密码体制就是建立在大数的因式分解的困难性上，第二个就是离散 对数。所谓离散对数即是在有限域g f ( p ) 上的一种运算，尽管目前求离散对数的 算法有几种，但是这些算法多是建立在大数的因式分解的基础上的，而大数的因 式分解在数学上本身就是一个困难问题，所以用另一个困难问题来求解离散对 数，在电路实现上基本是不可能的，所以目前比较容易实现的方法就是用遍历查 找的方法，但是这种方法需要大量的存储资源而且速度比较慢。s h a n k 算法是求 解离散对数算法中比较快速且要求较少存储资源的一种算法，就这一点将会在 3 3 节具体的说明。 第一章引言 1 2 2 集成电路设计与i p 核 随着集成电路工艺的发展，i c 规模越来越大，复杂度越来越高，同时，竞争 的加剧要求对市场具有快速的反应能力，缩短产品的开发周期。但设计能力的提 高却严重滞后于半导体工艺的发展，两者的平均增长率分别为2 8 和5 8 。为 解决这一矛盾，必须提高设计人员的设计能力。其中，设计数据和知识的重用是 解决问题的关键。设计重用具有重要的价值。早期数字电子中的标准组件、p c b 标准硬件单元等都采用了重用方法。片上系统( s o c ) 的兴起使电子工业对设计 的可重用性表现出高度的兴趣。口是指集成电路设计中所采用具有独立知识产权 的可重用的功能模块，其英文名称为“i n t e l l e c t u a lp r o p e r t y ”。集成电路设计中利用 i p 资源可以缩短相应的设计周期，同时也可以提高次流片的成品率。尤其是在 要求实现片上系统( s o c ) 的今天，充分利用i p 核可以使系统级芯片的功能更为 强大。 i p 核模块有行为、结构和物理三个不同程度的设计，对应有主要描述功能行 为的“软i p 核”、完成结构描述的“固i p 核”和基于物理描述并经过工艺验证 的“硬i p 核”三个层次。 硬i p 核是基于某种半导体工艺的物理设计，已有固有的物理拓扑布局，并 已经通过工艺验证，它提供给用户的形式是电路物理结构掩模版图和全套的工艺 文件，也因此硬口核具有较低的灵活性。 软i p 核通常是以某种h d l 文本提交给用户，它经过行为级设计和功能验、正， 其中不包含有任何的具体的物理信息。据此用户可以综合出正确的门电路网表， 并可以进行后续结构设计，具有最大的灵活性，可以很容易的借助e d a 综合工 具与其它外部电路结合成一体，根据各种不同的半导体工艺，设计成具有不同性 能的芯片。因此软i p 核适合应用于数字系统中。鉴于此，本文分析了s h a n k 算 法的流程和资源需求，提出了一种比较优化的算法i p 模型，并将此模型转换为 软i p 核。 i p 核的设计有其自身的特征，由于i p 核是作为s o c 设计所需的基本元素， 因此在设计1 p 核时要充分考虑到口核的可重用、可再定向、可配置和可升级。 本文在设计s h a n k 算法i p 时尽量考虑到i p 核所具有的特征，使其标准化。 第一章引言 1 4 论文的内容介绍 本论文的内容安排如下： 第1 章：引言。介绍了研究课题的背景、国内外现状和研究工作的主要内容、 论文创新以及论文的结构划分。 第2 章：s h a n k 算法i p 设计的相关知识。介绍了本论文中对s h a n k 算法i p 设计中所用到的相关的思想和i p 设计的相关知识。 第3 章：s h a n k 算法介绍和资源分析。介绍了s h a n k 算法流程和所用资源 的分析。 第4 章：模乘运算模块的设计。介绍了s h a n k 算法中的模乘操作模块的设计， 用m o n t g o m e r y 改进算法实现。 第5 章：体系结构的设计。介绍了s h a n k 算法i p 的总体体系结构及各个子 模块的结构设计。 第6 章：i p 的仿真与验证。对s h a n k 算法i p 用v e r i l o g h d l 实现，并进行 仿真和验证。 第7 章：总结与展望。阐述了本论文主要完成的工作，并指出了研究工作的 不足之处和进一步工作的设想。 第= 章s h a n k 算法l p 设计的相关知识 第二章s h a n k 算法i p 设计的相关知识 2 1i p 核设计的硬件描述语言 数字逻辑系统的设计是一个把思想( 即算法) 转化为实际数字逻辑电路的过 程，包括行为、结构和物理三个领域。行为指系统的功能；结构指系统的逻辑组 成；物理指系统具体实现的几何特征与物理特性。根据抽象级别的不同，数字系 统又划分为若干层次，一般自顶向下包括系统级、行为功能级( 或称算法级) 、寄 存器传输级( r t l ) 、逻辑级、电路级等。 硬件描述语言h d l ( h a r d w a r ed e s c r i p t i o nl a n g u a g e ) 是一种形式化方法描述 数字电路和系统的语言。数字电路系统的设计者利用这种语言可以从上层到下层 从抽象到具体从系统级到电路级，逐层的描述自己的思想，用一系列分层次的模 块来表示极其复杂的数字系统。然后利用e d a 工具逐层的进行仿真验证，再把 其中需要变为具体物理电路的模块组合经综合工具转换成为门电路网表，接下去 苒通过布局布线工具把网表文件转换成具体的电路结构。在制成物理器件前，还 可以用v e r i l o gh d l 语言的门级模型( 原语组件) 来代替基本组件。因其逻辑功 能和延时特性与物理组件完全一致，所以在仿真工具的支持下能验证复杂数字系 统的正确性，使投片的成功率达到1 0 0 。据统计，目前在美国硅谷约有9 0 以 上的a s i c 和f p g a 已采用硬件语言描述的方法进行。 硬件描述语言的发展至今已有2 0 多年的历史，并成功的应用于设计的各个 阶段：建模、仿真、验证和综合等。到2 0 世纪8 0 年代，己出现了上百种硬件描 述语言，它们对设计自动化曾起到了极大的促进和推动作用。但是这些语言一般 各自面向特定的设计领域和层次，而且众多的语言使用户无所适从。因此急需一 种面向设计的多领域多层次并得到普遍认同的标准硬件描述语言。进入2 0 世纪 8 0 年代后期，硬件描述语言向着标准化的方法发展。最终，v h d l 和v e r i l o gh d l 语言适应了这种趋势的发展，先后成为了i e e e 的标准。 把硬件描述语言用于自动综合只有1 0 多年的历史。最近七八年来，用综合 工具把可综合风格的h d l 模块转换成具体电路发展十分迅速，大大提高了复杂 数字系统的设计生产率。在美国和日本等先进的电子工业国，v e r i l o gh d l 语言 第二章s h a n k 算法i p 设计的相关知识 已经成为了设计数字系统的基础。 v e r i l o gh d l 和v h d l 语言都是用于逻辑设计的硬件描述语言，并且都成为 了i e e e 标准。v h d l 的英文全称是v h s i ch a r dd e s c r i p t i o nl a n g u a g e ，而v h s i c 的英文全称是v e r yh i g hs p e e di n t e g r a t e dc i r c u i t ，意为超高速集成电路，故v h d l 的中文泽为超高速集成电路描述语言。v h d l 是美国军方组织开发的，在1 9 8 7 年成为了i e e e 标准。v e r i l o gh d l 语言则是由一个普通的民间公司的私有财产 转化而来，在1 9 9 5 年才正式成为了i e e e 的标准。 v h d l 和v e r i l o gh d l 作为硬件描述语言，其共同点在于：能形式化地抽象 表示电路的行为和结构：支持逻辑设计中层次与范围的插述；可借用高级语言的 精巧结构来简化电路行为的描述；具有电路仿真与验证机制以保证设计的正确 性；支持电路描述由高层到低层的综合转换；硬件描述语言与实现工艺无关；便 于理解和设计重用。 v h d l 和v e r i l o g h d l 又各自有其自己的特点。v e r i l o g h d l 语言最大的优点 是它是一种非常容易掌握的硬件描述语言，而掌握v h d l 语言设计技术就比较 困难；目前版本的v e r l i o gh d l 和v h d l 在行为级的抽象建模的覆盖范围方面也 有所不同。v e r i l o g h d l 在系统抽象方面比v h d l 略差些，而在门级开关电路描 述方面比v h d l 强得多。攀于v e d l o gh d l 语言的优点，本文的s h a n k 算法口 的设计采用v e r i l o gh d l 语言进行设计。采用v e f i l o gh d l 语言对数字系统进行 设计需要注意以下几点： ( 1 ) 采用t o p d o w n 的结构化设计方法。这样设计的结构和层次都非常清 晰，易于修改和调试。 ( 2 ) 注意设计源代码的风格对电路的影响。同样的功能用不同的描述，可能 产生不同的结果。因此在描述电路时，应认真考虑电路的描述方法。 ( 3 ) 虽然v e r i l o gh d l 语言与实现工艺无关，但是在某些设计中，由于特定 结构的要求，有些描述可能无法实现，致使在综合的过程中产生不必要 的错误。 ( 4 ) 在描述时要分清哪些是用来综合的程序，哪些是仅仅是用来仿真的程序。 第二章s h a n k 算法i p 设计的相关知识 2 。2 自项向下设计方法与设计流程 数字系统的设计方法主要有二种，分别是鲁底上( d o w m - - t o p ) 的方法、自 顶下c r o p - - d o w n ) 方法和这两种方法集合的方法。其中自底向_ h ( d o w n t o p l 的方法的基本思路是从系统的需求出发，根据已存在的硬件基本单元划分设计的 最低层的单元模块。目前d o w n - - t o p 设计的方法只能运用于简单i c 的设计，而 不能满足复杂的a s i c 和s o c 芯片的设计要求。t o p - - d o w n 的设计方法首先从 整体上规划整个系统的功能和性能，然后对系统进行划分，分解为规模较小、功 能较简单的局部模块，直到划分得到已存在的硬件基本单元。t o p - - d o w n 的设 计方法是目前数字系统设计的主要方法。下面对这种方法及设计流程进行详细的 介绍。 所谓自顶向下设计方法，就是设计者首先从整体上规划整个系统的功能和胜 能，然后对系统进行划分，分解为规模较小、功能较简单的局部模块，并确立它 们之间的相互连接关系，这种划分过程可以不断的进行下去，直到划分得到的单 元可以映射到物理实现，凼而它是面向系统的设计技术，是设计师可以将更多的 精力和时间花费到从高层次上对系统进行功能定义和设计。 自顶向下的设计方法是随着硬件描述语言和e d a 工具同步发展起来的。硬 件描述语言可以在各个抽象层次上对电子系统进行描述，而借助e d a 设计工具， 可以自动实现从高层次到低层次的转换，这使得自顶向下的设计过程得以实现。 采用自顶向下的设计方法的优点是：由于整个设计是从系统顶层开始的，结合模 拟手段，可以从一开始就掌握所实现系统的性能状况，结合应用领域的具体要求， 可以调整设计方案，进行性能优化或折衷取舍；随着设计层次向下进行，系统性 能参数将得到进一步的细化和确认，并随时可以根据需要加以调整，从而保证了 设计的正确性，缩短了设计周期，设计规模越大，这种设计方法的优势越明显。 随则e d a 工具的快速发展，这种方法在数字系统的设计中应用越来越广泛。 自顶向下设计的流程可分为三个大的阶段，如图2l 所示。各个阶段之间 并没有绝对的界限。 第二章s h a n k 算法i p 设计的相关知识 景 统 设 计 阶 段 综 合 优 化 阶 段 综 合 实 现 阶 段 设计；：成 图2 1 自顶向下技术设计流程 ( 一) 系统设计 。 系统设计阶段最为重要，它包括系统功能分析、体系结构设计、系统描述与 功能仿真四个步骤。 ( 1 ) 系统功能分析 系统功能分析的一个目的是在系统设计之前搞清楚系统的需求，确定系统所 要完成的功能、系统的输入输出、输入输出之间的关系以及系统的时序要求。另 外一个目的就是系统的模块划分。在系统分析时，应根据功能的耦合程度，将系 统划分为不同的功能模块，每一个功能都映像到一个模块，同时还需要确定模块 之间相互关系，这是模块化设计的基本需要。 ( 2 ) 体系结构设计 7 第二章s h a n k 算法i p 设计的相关知识 体系结构设计是整个设计的关键，以后的所有的工作都依赖于所设计的体系 结构来进行的， 体系结构设计的旨要任务就是数据通路的设汁。系统的控制建立在数据通路 的基础之上，不同的数据通路对应了不同的控制通路。数据通路的设计包括处理 数据类型分析、处理单元的划分以及处理单元之间的关联程度等。控制通路是数 据通路上数据传输的控制单元，用于协调数据处理单元之间关系。控制通路的设 计主要包括数据的调度、数据的处理算法和正确的时序安排等。数据通路与控制 通路的设计并不是截然分开的，有时在确定好数据通路后，由于时序或数据的调 度等问题，而不得不重新修改控制通路。所以，数据与控制通路的设计，往往要 经过多次反复，才能达到最优的效果。 ( 3 ) 系统描述 v e r i l o g 语言和v h d l 语言都支持不同的描述方法。所以可采用这两种语言 对系统进行描述。 ( 4 ) 系统功能仿真 系统的功能仿真是验证系统功能正确性的重要手段，很多e d a 设计软件都 支持语言级的系统仿真。 在语言级的系统仿真时，要求设计者使用v e f i l o g 或v h d l 语言来编写系统 的测试基准程序。测试基准程序在高层次设计中占有非常重要的地位，不仅在系 统功能仿真时被用来作为功能验证的基准，而且在门级仿真与时序仿真时都要以 此为基准。测试基准程序用于模拟系统的工作环境。在该程序中，产生系统工作 所需要的所有输入信号，同时对多系统产生的输出信号进行判断，给出正确和错 误信息。 ( 二) 综合优化 该阶段主要的工作是系统的综合优化门级( g a t el e v e l ) 方阵。 f 1 ) 系统的综合优化 系统的综合优化分为两个步骤：第一步是将语言翻译成为门电路，第二步是 门级优化。系统优化的目的就足花费最小的硬件资源满足最大的时序要求。所以， 系统优化就是在系统的速度( s p e e d ) 和面积( a r e a ) 之间找到个最佳方案。 系统优化的关键在于系统的约束条件( c o n s t r a i n t s ) 的设定，系统的约束条件将 第二章s h a n k 算法f p 没计的相关知识 使系统的优化按照设计者所期望的目标进行。 ( 2 ) 门级仿真 现在一般的高层综合工具，都能够提取出系统的门级v e r i l o g 语言文件，该 文件内不仅包含了完成系统功能所需的组件，而且也包含了电路的一些日寸序信 息。将该程序与前面所提到的测试基准程序链接到一起，就可以进行门级的时序 仿真。如果对仿真的结果不满意，就必须修改综合优化条件或修改系统结构等。 ( 三) 系统实现 在一般的a s i c 设计中，系统实现的工作一般是设计者将综合后的网表 ( n o f l i s t ) 和设计的时序要求交给i c 生产厂家来进行。系统实现的主要是布局 布线( p 1 a c c a n dr o u z e ) 。布线时所遇到的最大的问题是布通率，一般情况下在布 局布线时要加入一定的人工干预，例如改变引脚的位置、特殊功能块的安排等。 在完成布局布线之后，要进行系统的后仿真( p o s ts i m u l a t i o n ) 。这是整个设计的 最后一道障碍，主要对系统的速度、时序关系作最后的验证。 自顶向下设计技术是个多方面知识的综合的技术，设计者必须站在系统的高 度来看待一个设计，同时还要对电路设计、e d a 工具、微电子等相关知识有一 定的掌握，才可能谈得上进行自顶向下设计。系统仿真及综合只是对系统实现的 手段，要成功完成一个复杂系统的设计，不仅要熟练掌握先进设计工具的使用， 更重要的是对系统本身的正确理解与设计。 2 3 i p 核的设计原则 i p 核的设计有其自身的特征，由于i p 核是作为s o c 设计所需的基本元素， 因此在设计i p 核时要充分考虑到i p 核的可重用、可再定向、可配置和可升级。 芯片的设计中要考虑的几个原则分别是同步原则、面积速度互换原则和硬件原 则。因此作为s o c 设计中的i p 核元素也必须具有以下的设计原则。 ( 1 ) 同步原则 同步电路的特点是电路的核心逻辑用各种各样的触发器实现；电路的主要信 号都是由某个时钟沿驱动触发器产生出来的；同步时序电路可以很好的避免毛 刺。 同步时序电路的核心就是时钟，时钟沿驱动d f f ( 触发器) 控制数据的产生， 第二章s h a n k 算法i p 设计的相关知识 是同步时序电路的主要表现形式。所以时钟的质量和稳定性直接决定着同步时序 电路的性能。另外，同步时序电路要求对输入的信号进行同步化，同步化的主要 怍用是使本级时钟的姓理沿获得相对丁数据的最& 有效处理时间，从而获得了更 长的时间余量。如果输入数据和本级芯片的处理时间同频，并且建立、保持时间 匹配，则可以直接用本级芯片的主时钟对输入数据寄存器采样，完成同步化。 f 2 ) 面积与速度的平衡与互换原则 在这里，“面积”指的是一个设计所消耗的等价逻辑门数。对于f p g a 可以用 所消耗的触发器( f f ) 和查找表( l u t ) 来衡量，“速度”是指在芯片上稳定运行 所能达到的最高频率。 面积和速度的互换是芯片设计的一个重要思想。面积和速度是对立统一的矛 盾体。理论上，一个设计如果时序余量较大，所能跑的频率远远高于设计的要求 那么就能通过功能模块复用减少整个设计消耗的芯片面积，这就是速度的优势来 换取面积的节约，这样设计的方法有并串转换的方法：反之，如果一个设计的时 序要求很高，普通设计方法达不到设计频率，那么一般可通过将数据流串并转换， 并行复制多个操作模块，以提高系统的处理速度。设计的过程中有许多方法可以 实现面积和速度的互换，例如流水线设计技术和串并转换的方法就是用面积的消 耗来换取速度的提高。例如用三个并行的最高处理速度为1 5 0 m b s 的模块，实现 4 5 0 m b s 的数据处理的实现过程如图2 2 所示。 宙二写x 1 i 堕1 竺5 0 望a l b 堡s 茎卜竖! ! ! 韭 并 并 出 转 ! ! 选1 爿箜塾堡鳖p 业 转 换 换 二l s o m b a 图2 2 “面积换速度，原理图 ( 3 ) 硬件原则 硬件原则指是采用硬件描述语言( h d l ) 进行程序编写时，程序的最终结果 能够很好的达到硬件电路的性能，包括面积和速度两个方面。 v h d l 和v e r i l o gh d l 作为h d l 语言，是分层次的，如系统级( s y s t e m ) 、 第二章s h a n k 算法i p 设计的相关知识 算法级( a i g o r t h m ) 、寄存器传输级( r t l ) 、逻辑级( h 百c ) 、门级( g a t e ) 及 电路开关级( s w i t c h ) 等。系统级和算法级与c 语言相似，可用的语法和表现形 式也更丰富。自r t l 级以后，h d l 语言的功能就越来越侧重于硬件电路的描述， 可用的语法和表现形式的局限性也就越大。程序设计中，不能片面的追求代码的 整洁、简短，而应该根据所需设计实现的硬件电路的要求对该电路硬件部分的结 构与链接进行详细的分析，然后用适当的h d l 语句表达出来即可。 评价一个设计的代码水平的高低，仅仅是说这个设计由硬件向h d l 代码这 种表现形式的转换是否流畅、合理。而一个设计的最终性能，在更大程度上取决 于设计工程师所构想的硬件实现方案的效率及合理性。 2 4 流水线设计技术 在上一节中我们提到了i p 设计原则中的面积与速度的平衡与互换原则，其 中运用流水线设计技术就可以用面积的消耗来换取速度的提高。流水线 ( p i p e 1 i n e ) 的设计方法已经在高性能、需要经常进行大规模运算的系统中得到 广泛的应用，如c p u ( 中央处理器) 等。 流水线设计的概念：所谓流水线设计实际上是把规模较大、层次较多的组合 逻辑电路分为几级，在每一级插入寄存器组并暂存中间数据。k 级的流水线就是 从组合逻辑的输入到输出恰好有k 个寄存器( 分为k 级，每一级都有一个寄存 器组) ，上一级的输出是下一级的输入而又无反馈的电路。下面我们举例说明流 水线技术，图2 3 表示如何把组合逻辑转换为相同逻辑功能的流水线设计。 图2 3 组合逻辑设计转化为流水线设计 这个组合逻辑包括两级：第一级的延迟是t 1 和t 3 两个中的最大值；第二级 的延迟等于t 2 的延迟。为了通过这个组合逻辑得到稳定的计算结果输出，需要 r l 第二章s h a n k 算法i p 设计的相关知识 等待的传播延迟为 m “( t i ，t 3 ) + t 2 个时间单位。在从输入到输出的每一级 插入寄存器后，流水线设计的第一级寄存器所具有的总的延时为t 1 与t 3 时延 的最大值加上寄存器的r 。( 触发日寸问) 。同样，第二级寄存器延迟为t 2 的时延 加上t c 。采用流水线设计为取得稳定的输出总体计算周期为： m 职( m a x ( t 1 ，t 3 ) + t c 0 ，( t 2 + t ) ) 流水线设计需要两个时钟周期来获取第一个计算结果，而只需要一个时钟周 期来获取随后的计算结果。开始时用来获取第一个计算结果的两个时钊，周期被称 为流水线设计的首次延时( 1 a t e n c y ) 。对于c p l d 来说，器件的延迟如t 1 、1 2 和t 3 相对于触发器的t 。o 要长的多，并且寄存器的建立时间t s 。也比器件的延时 要小得多。只有在上述关于硬件时延的假设为真的情况下，流水线设计才能获得 比同等功能的组合逻辑设计更高的性能。 采用流水线设计的优势在于它能提高吞吐量( t h r o u g h p u t ) 。假设t 1 、t 2 和 t 3 具有同样的传递延迟b d ，对于组合逻辑设计而言，总的延迟为2 + l d ；对于 流水线设计来说，计算周期为( l d + t 。) 。前面提及得首次延迟( 1 a t c n c y ) 的概 念实际上就是将( 从输入到输出) 最长的路径进行初始化所需要的时间总量；吞 吐延迟则是执行一次重复性操作所需要的时间总量。在组合逻辑设计中，首次延 迟和吞吐延迟同为2 + t p d 。与之相比，在流水线设计中，首次延迟是2 t ( t p d + t 。) ， 而吞吐延迟是t 口d + t 。如果硬件能提供快速的t c 。，则流水线设计相对于同样 功能的组合逻辑设计能提供更大的吞吐量。 由以上的例子可以看出，流水线设计在性能上的提高是以消耗较多的寄存器 资源为代价的。 2 4 可重组逻辑设计技术 可重组逻辑发计技术的思想主要是源于计算机对可重构体系结构的研究，可 重构体系结构是介于可编程体系结构d s p 和专用集成电路a s i c 之间的一种体 系结构，这中体系结构融合了二者的优点，即能够根据不同的应用需求，改变自 身的体系结构，以便与具体的应用需求相匹配。目前可重构体系结构已经在很多 加密芯片中应用。 同样可重组逻辑设计技术的思想可以表述为，在逻辑电路中设置某些可被不 第二章s h a n k 算法i p 设计的相关知识 同逻辑函数重复使用的部件，并在可重用部件的内部和重用部件之间的连接网络 之中设置某些指令界面可见的可控节点，通过改变这些可控节点的控制编码，可 以改变重用部件的内部结构或相互之间的连接关系，从而实现不同的操作，匹配 不同的逻辑函数。这样利用可重组逻辑思想设计的电路就具有很大的灵活性，也 具有更大的应用性，下面用一个简单的例子来说明可重组逻辑技术的思想。 例2 1 】实现不同逻辑函数的可重组逻辑电路，电路图见图2 4 。 占 图2 4 实现不同逻辑函数的可重组逻辑举例 如图2 4 所示的电路中，a n d 2 表示2 输入与门，a n d 3 表示3 输入与门， o r 2 表示2 输入或门，n o t 表示非门，a 、b 、c 、d 是4 个输入变量，f 是输 出变量。我们在上述电路中设置了2 个可控节点，其控制信号分别记为c t r l l 和c t r l 2 。通过对c t r l l 和c t r l 2 赋以不同的值，就可以改变上述电路的逻 辑功能，实现不同的逻辑函数。下表给出了当c i r l l 和c t r l 2 取不同的值的 时候，上述电路所实现的函数关系。 表2 一l 图2 4 所示可重组逻辑实现的功能 c t r l lc t r l 2函数关系 d0f = 0 ol f = d 10 f = a b c 笙三童! ! ! 些茎鲨堡兰茎堕塑茎塑塑 图2 - - 5 实现不同连接关系的可重组电路 如图2 - - 5 所示，图中共有3 个部件a 、b 、c ，a 和b 的输出经过m u x 选 通后进入c 部件，作为c 部件的输入，其中m u x 就是一个可控节点，通过对 这个可控节点的控制就可以实现两种不同的连接关系，分别如图2 - 6 和图2 - 7 所 示。 图2 - 6 连接关系一 2 。5s h a n k 算法i p 的设计流程 b c 图2 7 连接关系二 前几节中，我们描述了i p 设计的基本流程和所用到的硬件描述语言，也描 述了一些电路设计的方法。本文在对s h a n k 算法i p 进行设计之前对s h a n k 算法 进行资源分析，然后采用自顶向f 的设计方法和流程，使用v e r i l o g 语言借助 1 4 第二章s h a n k 算法m 设计的相关知识 于多种e d a 工具完成s h a n k 算法坤核的设计、综合及仿真验证。 s h a n k 算法口核设计的流程如下： ( 1 ) 对s h a n k 算法流程进行分析，得出实现算法所需要的资源，并得出资源 和速度的关系； ( 2 ) 对s h a n k 算法i p 核进行顶层功能和结构的定义和划分，并得出各个模块 之间的链接、数据和时序关系： ( 3 ) 用行为级v e f i l o gh d l 描述整个i p 核，并用m o d e l s i m 软件进行行为级仿 真，以验证i p 的可实现性； ( 4 ) 用可综合的v e r i l o gh d l 重新描述各个分模块，在m o d e l s i m 软件上调试 各个模块，仿真基本时序： ( 5 ) 在x i l l i x 工具上综合各个模块，用m o d e l s i m 软件进行时序验证： ( 6 ) 对整个设计进行电路综合和优化，所得到的网表信息中含有电路中信号 的延时信息，摄后再做带延时信息的仿真验证。 第三章s h a n k 算法介绍和资源分析 第三章s h a n k 算法介绍和资源分析 3 1 离散对数 在介绍离散对数概念之前，我们先要了解有限域的一些基本理论。 3 1 1 有限域的概念 【域】f 是至少含有两个元素的集合，对f 定义了两种运算“+ ”和“聿，并且满足 以下三个条件的代数系统 f ，+ ，称为域。 ( 1 ) f 的元素关于“+ ”构成阿贝尔群，设其单位为0 。即对于n ，b f ，交换律 成立，满足口+ b ；b + a 。 ( 2 ) f 0 ) 关于运算“丰”构成阿贝尔群。即对于d ，b c f 且。，b ；0 ，交换律成立， 满足a ；6 = b ，a 。 ( 3 ) 对于4 ，b ，f ，分配律成立。即 ( 口十b ) + c = 4 c 十b + c 若域f 的元素有限个，则称之为有限域或伽罗瓦( g a i o i s ) 域。其中阿贝尔群表 示交换群，f 、 o ) 表示集合f 除去 0 ) 元素后的元素。 我们通常用域g f ( p ) 表示元素为 0 ，1 ，2 - - p i ( 其中p 为素数) 的域 则在此域上可以定义两种运算，“+ ”和“”，他们的运算规则为： ( 1 ) 对于口，b g f ( p ) ，口+ 6 = 0 + b ) m o d p ； ( 2 ) 对于口，b g f ( p ) ，口+ b = x b ) m o d p 另外，我们还可以在域g f p ) 定义出另外一种扩展的运算“幂”，即对于 n ，x g ，0 ) ，幂函数可以表示为： 第三章s h a n k 算法介绍和资源分析 a 。；口 d 十+ 口 ，( ( ( “n a ) m o d p ) a ) m o d p ) x a ) m o d p ；r dx ax 。a ) m o d p = a m o d p 3 1 2 费尔玛( f e r m a t ) 定理 【定理1 1 若p 是素数，且g c d ( 公约数) ( d ，p ) = 1 ，则口川= l m o d p ，这时 h p 1 称n 是口的乘法周期。 【定理2 】若j 口是素数，且g c d ( 公约数) ( 口，p ) = 1 ，则口sn m o d p 。 其中定理2 可以由定理1 推理得出，即a9 ；a + 口”= a m o d p 。 3 1 3 离散对数的概念 - z ：v 是一个大素数，n 是 0 ，1 ，2 p 一1 ) 中与p 互素的数，或称为口是域 g e ( p ) 上的本原元元素，计算幂函数，0 ) = d m o d p 并不困难。令 工= b o + 6 1 2 + 6 2 2 2 + - + 6 n 1 2 “一1 则 n r ；口+ 2 啦2 ：k 2 “。( 口) “( 日2 ) 6 tx ( 口2 2 ) “”( d2 ”) ” 且 广2 ： 所以先计算 a = 口x a 这样就可以很容易的计算出a 1 ； g y ( p ) 上已知z 计算口。= y ，反之，已知y 求x ，则x 用l o g ，y 表示，也称 墨三兰! ! ! 唑簦鳖坌塑塑壅塑坌堑 之为求离散对数。 由此，我们可以得出离散对数的概念。 晴散对数j 在n a f ( p ) ( 其中p 是一个大素数) ，口z = t 或a f ( p 、上的本原元 ( n 和p 互素) ，对于任意的在域6 - f ( p ) 上的y ，寻找唯- n n 数x ( o g z 5p 一1 、 n n y = n 。m o d p ，则把整数z 记为l o g 。y ，并称之为离散对数。 3 2 s h a n k 算法 s h a n k 算法是一种速度快，而且需要的存储也比较少的算法，基本思想如下， 运算在g f 0 ) 上进行。 1 、选d 。压 x ；q d + r ，0 sr d ，qs ；。i ， r d 。i 2 、建立一表格0 ，l o g 。且) ，l o a = 0 ，1 ，2 d i ： 按顺序排列，以便于 检索： 3 、由于假定y = 口；n 州”，所以 y ( a 。y = e 1 q d + 口“；a 7 y ( a 。) 9 = y ( a ”4 ) 4 j 1 - n y ( a ”。) 9 ，q2 0 ，1 ，2 ，直到结果中等于表中某个，r ：l o g 。x x = q d + r 。s h a n k 算法如下其中 ，= l o g 。y s 1 选择d 一以，一0 ，y 一1 ： s 2 ( y ，l o g 。y ) 进入表格； s 3 若r = d 一