（电路与系统专业论文）密码算法SMS4的硬件实现研究[电路与系统专业优秀论文].pdf

浙江大学硕士论文 摘要 随着我国国民经济和社会信息化建设进程，信息安全问题越来越得到关注。 而密码技术作为信息安全技术的核心，对它的研究就变得重要而迫切。 本文主要介绍了国内官方公布的第一个商用密码算法，s m s 4 分组密码算法， 详细分析了该算法的架构。根据不同的加密模式提出了实现该算法的几种硬件架 构：全循环架构、循环展开架构、流水线架构、循环展开和流水线的结合架构。 在此基础上给出了几种f p g a 实现方案：( 1 ) 全循环实现；( 2 ) 高速流水线实现； ( 3 ) 高速引擎实现。 根据s m s 4 算法自身的特点( 3 2 轮的循环迭代) ，采用全循环实现。该方案， 占用面积小，前后加解密数据块之间没有相关性，能够应用于反馈加密模式， 如c b c 、c f b 、o f b 模式。但每组数据需进过3 2 轮的迭代算法，数据吞吐量小， 算法速度相对较慢。 在数字电路中为了加快数据的运行速度，流水线是最常见的方式。该方式使 得几组数据同时在运行，大大加快了运算速度。但占用面积比较大，差不多是全 循环实现的3 2 倍，因为整个实现包括3 2 个轮次的f e i s t e l 网络结构的加解密算 法模块；并且3 2 级流水线使得3 2 组数据同时在加解密运算，该方式无法实现 c b c 等反馈加密模式。 高速引擎实现，其实是内部流水线的一种方式，单个引擎分为3 级内部流水， 电路运行速度快，引擎数可灵活的配置，并且能配置成多引擎串行结构、多引擎 并行结构。该方法同全流水线方式一样不适合反馈加密模式。 本文对以上的方案进行了仿真分析和讨论。 【关键字】s m s 4 密码算法f p g a 流水线引擎 第1 页 浙江大学硕士论文 a b s t r a c t a sn a t i o n a le c o n o m ya n ds o c i e t yi n f o m l a t i o n a l ，i n f o n n a t i o ns e c u r i t yi sd r a w i n g m o r ea n dm o r ea t t e m i o n c r y p t o g r a p h yi sm ec n l c i a lt e c h n i q u ei nt l l ei n f o n a t i o n s e c u r i t yf i e l d ，s or e s e a r c ho n “b e c o m e se v e nm o r ei m p o n a n ta n de x i g e m s m s 4a l g 州岫i s 也ed o m e s t i ce n c r ) 甲t i o n 咖d a r dr c l e 嬲e df o rw l a nu s e t h e t l l e s i s a n a l y z e d t l l es t m c t l l r co fs m s 4a l g c t l l l ，a n d p r o p o s e ds e v e r a l h a r d w a r e - i m p l e m e n t a t i o nm e t h o d sa c c o r d i n gt od i 疵r e n te n c r y p t i o nm o d e s ，w l i c h a r e 削l - l o o p s t r u c t u r c ， 1 0 0 p - u n r 0 1 l i n g s t r u c t u r e ， p i p e l i i 伦d - s 仇l c t l l r e ，a n d 1 0 0 p u i l i d l l i n g & p i p e l i i l e d m i x e ds t m c t u r e t h ef p g ai i n p l e m e n 诅d o ni sa l s o i n 锄d u c e di i lt h i sp 印e r ：( 1 ) f l l l l 一l o o pi m p l e m e n t a t i o n ；( 2 ) p i p e l i n e di i n p l 锄e n 诅t i o n ； ( 3 ) h i g l l - s p e e de n g i n ei m p l e m e n t a t i o n i m p l e m e m a 埴o n1 ：s m s 4i sa3 2 一m l l l l di t e r a t i o na l g o 血l l i n ，s oaf u l l - l o o p s t n l c t i l r ei sp r o p o s e da st 1 1 ef j r s tm e t l l o d i tn o to n l yc o s t sl e s s c e l lc o n s 啪p t i o n ，b u t a l s oc a i lb eu s c di n l ef e e d b a c km o d e ，l i k ec b c ，c f b ，0 f b t h em a md i s a d v a n t a g e i st h a tf b re a c hd a 诅b 1 0 c k3 2r o u n d sc a l c u l a t i o na r en e e d e d ，w 扯c hl i m i t sm e t 1 1 】u g h p u ta 1 1 ds y s t e m 矗e q u e n c y i m p l e m e n t a t i o n2 ：t h es e c o n di n 劬o di sap i p e l i n e ds n u c t i l r e t w oc o n c r e t e w a y sa r ep r o p o s e da c c o r d i n gt od i n e r e h ts - b o xi m p l 锄e n t a t i o n s o n ei su s i n gl u t ， t l l eo m e ri su s i n gr o m p i p e l i n ei st h em o s tp o p u l a rt e c l l 血q u et o 油p r o v et l l e p e r f b 舯a n c ei nd i g i t a li cd e s i g n fm o r ct l l a no n ed a t ab l o c ka r ec a l c u l a t e dp a r a l l e l s i m l l l t a n e o u s l y ，w h i c hg r e a ya c c e l e r a t e st l l ec a l c u l a t i o ns p e e d h o w e v e r ，t l l i sm c 也o d c o s tt o om u c h 锄dc a l ln o tr e a l i z em o d e sl i k ec b c ，c f b ，0 f b i m p l e m e n t a t i o n3 ：i nt l l i sp a p e r ，a j li 1 1 i l e 卜r o 硼dp i p c l i n c d ，王l i 曲一s p e e de n g i n ei s p r o p o s e d 蛆e ra n a l y 痂培t l l ef 毫a t l l r c so ft l l i sa l g o r i t 量1 1 1 1 b yu s i n gp i p e l i n c do rp a r a l l e l m u l t i e n g i n e s ，i m u 曲p u ta l l d h a r d w a r ec o s tc a i lb ee a s i l ya 由u s t e da c c o r d i i l gt o d i 圩b r e n t 印p l i c a 廿o n s c 唧a r e dw i t l lt 1 1 e3 2 一s t a g ep i p e l i n e ds t 九l c t l l r e ，h a r d w a r ec o s t i sm u c hl o w e r u n d e rt 1 1 es 锄et h m u g h p u t s i m u l a t i o na i l ds y n t l l e s i sr e s u l t so f 血e s ei m p l e m e n t a t i o n sa r ea l s od i s c l l s s e di n t 如i st l l e s j s 【l c e y w o r d 】：s m s 4c r y p t o g r a p h yf p g ap i p e l i n ee n g i n e 第1 i 页 浙江大学硕士论文 第1 章绪论 第l 节研究背景 当前，随着我国国民经济和社会信息化建设进程，如金融信息化、电子商务、 电子政务的快速发展，急需解决经济、文化等重要领域信息系统的信息安全问题， 提高安全保护水平，增强信息安全积极防御与反应能力。信息安全技术主题将通 过对信息安全关键技术的攻关研究以及对急需的信息安全产品的研究开发，为我 国信息化建设的安全保障体系提供关键核心技术和平台，增强对国家信息基础设 施和重点信息资源的安全保障能力，基本满足党、政和国民经济建设主要部门的 信息安全需求。 信息安全中最核心的技术是密码技术，密码技术的研究和应用已经有几千年 的历史，但是作为一门科学却是2 0 世纪5 0 年代才开始的，互联网的广泛使用大 大推动了密码技术的研究和发展，不但涌现了各种各样的密码算法和密码体制， 还出现了馄饨密码技术、量子密码技术等各种新技术。 第2 节密码学概述 密码学是信息安全技术的核心，它主要由密码编码学和密码分析学两个分支 组成。密码编码学的主要任务是寻求产生安全性高的有效密码算法和协议，以满 足对消息进行加密或认证的要求。密码分析学的主要任务是破译密码或伪造认证 信息，实现窃取机密信息或进行诈骗破坏活动。这两个分支既相互对立又相互依 存，正是由于这种对立统一关系，才推动了密码学自身的发展。 1 2 1 密码学的发展概况 密码学是一门即古老又年轻的学科，其历史可以追溯到几千年以前。密码学 的发展大约可分为3 个阶段：古代加密方法、古典密码( c l a s s i c a lc f y p t o g r a p h y ) 和 近代密码( m o d e mc r y p t o g r a p h y ) 儿2 1 。 古代加密方法主要有古希腊墓碑的名文志、隐写术及古代的行帮暗语和一些 第1 页 浙江大学硕士论文 文字猜谜游戏等。这种加密方法通过原始的约定，把需要表达的信息限定在一定 的范围内流通，已体现出了密码学的若干要素，但只能限制在一定的范围内使用。 古典密码一般采用手工或机械变化的方式实现，它比古代加密方法更复杂， 但其密钥变化向量仍然比较小。古典密码时期的密码系统已经初步呈现出当代密 码系统的雏形。古典密码的加密方法一般是文字置换，使用手工或机械变换的方 式实现。 1 9 4 9 年，c e s h a n n o n 发表了“保密系统的信息论( c o m m u n i c a t i o nt h e o r yo f s e c r e c ys y s t e m s ) “， 1 9 7 6 年w d i f f i e 和m h e l l m a n 发表了“密码学的新方 向( n e wd i r e c t i o n si nc r y p t o g r a p h y ) ”。1 ，这两篇重要的论文和1 9 7 7 年美国 国家标准局( n a t i o n a lb u r e a uo fs t a n d a r d s ) 公布的数据加密标准d e s ( d a t a e n c r y p t i o ns t a n d a r d ) “3 ，标志着密码学的理论与技术的划时代变革，宣告了近 代密码学的开始。 随着计算机科学的蓬勃发展，社会已进入信息时代，电子计算机和通信网路 的广泛应用，特别是近年来电子商务的兴起，现代密码学的应用范围也在不断扩 张，已不仅仅局限与政治、军事以及外交等领域，其商用价值和社会价值也得到 了充分的肯定。 现代密码体制的研究基本沿着两个方向发展：一是以r s a 、e c c 为代表的公 开密钥密码体制；另一个是以d e s 、a e s 为代表的秘密密钥分组密码体制。公钥 密码体制和私钥密码体制各有其优缺点，因此在使用中大都采用这两种密码体制 相结合的方法。一般是在对密钥的传输中使用公钥加密体制，而在槽的加密过程 中使用私钥加密体制。这种结合不仅有效地保护了密钥，同时也保护了密文，效 率得到了很大的提高。 1 2 2 对称密码算法 对称算法( s y j l l l n e t r i ca l g o r “h m ) 有时又叫传统密码算法，就是加密密钥 能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加密解密密 钥是相同的。这些算法也叫秘密密钥算法或单密钥算法，它要求发送者和接收者 在安全通信之前，商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意 味着任何人都能对消息进行加密解密。只要通信需要保密，密钥就必须保密。 第2 页 浙江大学硕士论文 对称算法的加密和解密表示为： ( m ) = c d k ( c ) = m 其中m 表示明文，c 表示密文，e ( ) 表示加密函数，d ( ) 表示解密函数，k 表 示密钥。这些函数具有下面的特性( 如图1 1 ) ： d k ( e k ( m ) ) = m 囤11 ：使用对称算法的加密与解密 对称算法可分为两类。一次只对明文中的单个位( 有时对字节) 运算的算法 称为序列算法( s t r e a ma l g o r i t h m ) 或序列密码( s t r e a mc i p h e r ) 。另一类算法 是对明文的一组位进行运算，这些位组称为分组( b l o c k ) ，相应的算法称为分组 算法( b l o c ka l g o r i t h m ) 或分组密码( b l o c kc i p h e r ) 嘲。 1 2 3 公开密钥算法 公开密钥密码体制的思想是1 9 7 6 年由d i f “e 和h e l l m a n 提出的。它跟以前 的所有方法都截然不同：用作加密的密钥不同于用作解密的密钥，而且在合理的 长时间内，解密密钥不能根据加密密钥计算出来，这称为计算上不可行的。之所 以叫做公开密钥算法，是因为加密密钥能够公开，即陌生者能用加密密钥加密信 息，但只有用相应的解密密钥才能解密信息。在这些系统中，加密密钥叫做公开 密钥( p u b l i c k e y ，简称公钥) ，解密密钥叫做私人密钥( p r i v a t e k e y ，简称私 钥) 。 公开密钥密码体制主要有r s a 公钥密码体制、e l g a i i l a l 公钥密码体制、e c c 公钥密码体制。公钥密码体制提供的安全性取决与难于解决的数学问题，如r s a 公钥密码体制的安全性是基于大整数的素分解问题的难解性，e l g a m a l 公钥密码 第3 负 浙江大学硕士论文 体制的安全性是基于有限域上的离散对数问题的难解性，而e c c 公钥密码体制的 安全性则是基于椭圆曲线上的离散对数问题的难解性。 公钥密码体制的优点是加密密钥可以公开传播，缺点是运算数度较慢，譬如： 在硬件实现时，r s a 比d e s 慢大约1 0 0 0 倍，在软件实现时r s a 比d e s 慢大约1 0 0 倍”。 本文主要是对分组密码算法s m s 4 的研究，对公开密钥密码体制不再进行过 多的阐述。 第3 节国内外分组密码的研究现状 分组密码在许多密码系统中都是很重要的组成部分，目前在商业领域也是比 较重要而流行的一种加密机制，它广泛地应用于数据的保密传输、加密存储等领 域。用分组密码作为基本地加密部件，可以通过各种方式实现资料地保密性，如 构成随机数发生器、流密码、认证码和哈希函数。同时，分组密码在消息认证技 术、数据完整性机制、实体认证协议及数字签名方案中可以作为核心组件。 1 3 1 分组密码的研究意义嘲 分组密码算法具有数度快、易于标准化和便于软硬件实现等特点，通常是信 息网络安全中实现数据加密、数字签名、认证及密钥管理的核心体制，它在计算 机通信和信息系统安全领域有着广泛的应用。之所以受到广泛关注并且成为密码 学研究的热点课题之一，主要由于以下原因： 1 加密算法标准化的需要 标准化是工业社会的一个基本概念，它意味着生产规模化、生产过程的程序 化等。为了实现非相关团体之间的保密通信，加密体制的标准化是必要的。分组 密码由于器固有的特点，已经成为加密信息标准化进程的首选体制。1 9 7 7 年美 国国家标准局颁布了联邦信息处理标准d e s ，此后，d e s 作为数据加密的工业标 准，得到了i b m 等计算机制造商的大力支持，并陆续被其它组织机构采纳。但由 于d e s 的安全性问题，1 9 9 7 年4 月，美国a n s i 发起征集a e s ( a d v a n c e de n c r y p t i o n s t a n d a r d ) 的活动，并成立了a e s 工作小组。此次活动的目的是确定一个非保密 的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密 第4 页 浙江大学硕士论文 标准。并与2 0 0 0 年1 0 月n i s t 宣布r i j n d a e l 作为新的a e s 。 2 加密算法本土化的需要 信息安全的最大特点之一是自主性，因而其核心技术密码学的研究与开 发应当是一种本土性的科学。分组密码算法的安全性主要是依赖非线性s 盒的设 计，而大多数密码算法都不公布s 盒的设计依据，所以很有可能存在陷门。贸然 使用这些密码算法可能会带来不可预测的后果。因此，最明智的方法就是依靠自 己的力量并汲取现有的先进经验进行研究、设计和开发。 3 多级安全的需要 在区域通信系统中，用户较多，他们的地位、作用都不相同，所流通的信息 的重要性也不可能完全相同，因此他们要求得到的安全保护等级也不应该相同。 由此可见，研究多级安全密码算法非常必要。迭代分组密码是分组密码的典型代 表，其数学思想简单而灵巧。特别是在相同的轮函数下，迭代次数的不同即代表 了安全强度的不同级别。 4 网络安全通信的需要 随着网络技术应用与发展逐步渗透到许多关键部门，特别是政府、军事机构， 及电子商务的兴起与广泛应用，各种安全需求日渐复杂。 1 3 2 分组密码研究与进展 1 数据加密标准d e s 1 9 7 2 年，美国国家标准局( n b s ) ，拟定了一个旨在保护计算机和通信数据的 计划。作为该计划的一部分，他们想开发一个单独的标准密码算法。1 9 7 3 年， n b s 发布了公开征集标准密码算法。1 9 7 5 年，首次公布d e s 算法描述，并且进行 公开讨论，于1 9 9 7 年正式批准为无密级应用的加密标准。以后每隔5 年美国国 家安全( n s a ) 做出评估，并重新确定是否继续将其作为机加密标准。最近一次 评估是在1 9 9 4 年，并决定在1 9 9 8 年1 2 月以后不再作为加密标准。 2 a e s ( a d v a n c e de n c r y p t i o ns t a n d a r d ) 叫 1 9 9 7 年4 月1 5 日，美国国家标准技术研究所( n i s t ) 发起征集a e s ( a d v a n c e d e n c r y p t i o ns t a n d a r d ) 算法的活动，并专门成立了a e s 工作组。目的是为了确 定一个非保密的、公开披露的、全球免费使用的分组密码算法，用于保护2 1 世 第5 页 浙江大学硕士论文 纪政府的敏感信息。1 9 9 7 年9 月1 2 日在联邦登记处( f r ) 公布了征集a e s 候选 算法的通告。a e s 的要求是比三重d e s 快而且至少和三重d e s 一样安全，分组长 度为1 2 8 比特，密钥长度为1 2 8 、1 9 2 、2 5 6 比特。1 9 9 8 年8 月2 0 日n i s t 召开 了第一次a e s 候选会议，并公布了满足候选要求的1 5 个a e s 候选算法。后来， n i s t 又从这1 5 个算法中筛选出5 个a e s 候选算法。2 0 0 0 年1 0 月n i s t 宣布 r i j n d a e l 作为新的a e s 。r i j n d a e l 由比利时的j o a nd a e m e n 和v i n c e n tr i j m e n 设计，算法的原形是s q u a r e 算法，它的设计策略是宽轨迹策略。 3 n e s s i e ( n e we u r o p e a ns c h e m e sf o rs i g n a t u r e s ， i n t e g r i t y ， a n d e n c r y d t i o n ) 继美国征集a e s 结束之后，欧洲也开始进行称为n e s s i e 的密码大计划，其 主要目的是为了推出一系列安全的密码模块；另一个目的是保持欧洲在密码研究 领域的领先地位，并增强密码在欧洲工业中的作用。与a e s 相比，n e s s i e 涉及 的范围更广，不仅征集了分组密码，而且还征集序列密码、公钥密码、数字签名、 消息认证码以及杂凑函数。整个运作过程也是公开透明的，2 0 0 0 年3 月公布了 征集通告，2 0 0 0 年1 1 月1 3 1 4 曰召开第1 次n e s s i e 会议，并公布了征集到 的所有算法。 4 s m s 4 算法“ s m s 4 是无线局域网产品使用的分组对称密码算法，是国内官方公布的第一个 商用密码算法。s m s 4 是一个分组对称密码算法，分组长度和密钥长度为1 2 8 比 特。加密算法与密钥扩展算法都采用3 2 轮非线性迭代结构。其中非线性变换中 所使用的s 盒是一个具有很好密码学特性的、由8 比特输入产生8 比特输出的置 换。但是不存在永远安全的密码算法。s m s 4 的设计非常灵活，其中所采用的s 盒可以灵活地被替换，以应对突发性的安全威胁。 1 3 3 研究目的与意义 信息在社会中的地位和作用越来越重要，信息已成为社会发展的重要战略资 源，社会的信息化已经成为当今世界发展的潮流和核心。同时信息的安全问题也 成为人们关注的焦点。信息的安全问题主要由安全协议和密码算法组成，而密码 算法是信息安全的基础和核心技术，一个好的安全系统如果不依赖与好的密码算 第6 负 浙江大学硕士论文 法，将是不可想象的，而信息安全的自主性特点决定了密码算法的研究和开发必 须本土化，因为只有这样才能完全消除密码算法是否存在陷门的忧虑，才能放心 的用来维护本国关键信息的安全。 2 0 0 6 年1 月6 日，国家商用密码管理办公室发布了第7 号公告，规定无线局 域网产品须采用下列经批准的密码算法【l l 】： 1 、对称密码算法：s m s 4 ； 2 、签名算法：e c d s a ；其中，e c d s a 和e c d h 密码算法须采用我局指定的 椭圆曲线和参数。 3 、密钥协商算法：e c d h ； 4 、杂凑算法：s h a 2 5 6 ； 5 、随机数生成算法：自行选择。 其中，e c d s a 和e c d h 密码算法须采用我局指定的椭圆曲线和参数。 目前，密码产品中密码算法的实现，正逐渐由软件实现向硬件实现过渡。国 外一些厂商纷纷推出专用的加解密芯片，广泛应用与军事和商用领域。硬件加密 产品正越来越受到重视。硬件实现较软件实现而言，主要有以下两方面的优势： ( 1 ) 首先，硬件实现比软件实现的速度快，加密算法含有特定函数的复杂运 算，经过特殊设计的硬件实现有速度上的优势； ( 2 ) 其次，硬件实现比软件实现安全，对运行在没有物理保护的普通计算机 上的某个加密算法，机密算法和密钥文件可能会被非法拷贝，其算法或密钥有可 能完全被暴露，攻击者可以用各种跟踪工具研究、分析算法而使用者可能完全不 知道，硬件加密设备可以将算法和密钥安全的封装起来，攻击者无法获取密钥， 从而避免类似的事情发生【1 2 】 1 3 】。 考虑到信息安全的重要性和密码算法本土化的迫切要求，对分组加密算法 s m s 4 的硬件实现进行深讨和研究具有较大的理论意义和实践意义。 第4 节论文章节安排 全文分为六章，各章主要内容如下： 第一章介绍了本文的研究背景，随着我国国民经济和社会信息化建设进程， 急需解决经济、文化等重要领域信息系统的信息安全，而密码技术是信息安全技 第7 页 浙江大学硕士论文 术的核心技术。肯定了密码技术在当前现代化建设中的重要地位。 第二章介绍了f p g a 的基本原理和设计流程，因为f p g a 设计的灵活性，在实 验室阶段得到广泛的应用。本文的s m s 4 密码算法就是基于x i l i n x 公司的f p g a 工具开发的。 第三章介绍了分组密码算法s m s 4 的算法原理，详细分析了它的算法结构， 及密钥扩展算法。 第四章介绍了分组密码算法的两种加密模式：反馈模式和无反馈模式，以及 分析了s m s 4 密码算法的几种实现的架构，主要有全循环架构，解循环架构，流 水线架构( 包括普通、内部流水线架构) 等。并分析了各种架构适合的加解密 模式。 第五章给出了s m s 4 密码算法的几种设计与实现，分别为全循环实现，流水 线实现，高数引擎实现。并给出了各种实现的仿真结果图，以及性能分析。并对 对几种实现方式之间做一比较。 第六章给出了论文的总结和今后s 鹇4 算法的研究展望。 第8 贞 浙江丈学硕士论文 第2 章f p g a 概述 这一章主要介绍f p g a 的基本原理、特点、及其设计流程。因为f p g a 设计的 设计周期短、灵活性等特点，在实验室阶段得到广泛的应用。本文所讨论的分组 密码算法s m s 4 的实现就是基于x i l i n x 公司的f p g a 开发的。 第1 节f p g a 简介n 叼 随着微电子技术与工艺的发展，数字集成电路发展到了今天的专用集成电路 ( a s i c ) 。a s i c 的出现降低了产品的生产成本，提高了系统的可靠性，减少了 产品的物理尺寸，推动了社会的数字化进程。但是，a s i c 囡其设计周期长，改 版投资大，灵活性差等缺陷制约着它的应用范围。而可编程逻辑器件f p g a 以其 灵活的设计特点在很多方面得到了广泛的应用，根据需要，在实验室就能设计、 更改大规模数字逻辑，研制自己的a s i c 并马上投入使用。 2 1 1f p g a 的基本原理 简化的f p g a 的结构由4 部分组成：输入输出模块、二维逻辑阵列模块、连 线资源和内嵌存储器结构，如图2 1 所示。i 0 模块是芯片与外界的接口； c o f i g u m b l el o g i c 是可编程的主体，可以根据设计灵活地改变连接与配置，完成 不同的逻辑功能；连线资源连接所有的i ，0 模块和可编程逻辑模块；内嵌存储器 结构是可以在芯片内部存储数据。 图21 ：f p g a 的结构原理图 第9 页 浙江大学硕士论文 2 1 2f p g a 的特点 f p g a 既继承了a s i c 的大规模、高集成度、高可靠性的优点，又克服了普 通a s i c 设计周期长、投资大、灵活性差的缺点。当代f p g a 具有以下主要的特 点。 2 1 2 1 规模越来越大 随着超大规模集成电路工艺的不断提高，单一芯片内部可以容纳上百万个晶 体管，f p g a 芯片的规模也越来越大。单片逻辑门数已愈千万，如) ( i l i l l ) 【v i n e x - 4 x c 4 v1 5 0 已经达到1 5 0 0 万门的规模。随着芯片的规模越来越大，所能实现的功 能也越强。 2 1 2 2 开发过程投资小 f p g a 芯片在出厂前都做过百分之百的测试，具有高可靠性的特点。而且 f p g a 设计灵活，发现错误时可直接更改设计，减少了投片风险，节省了许多潜 在的花费。现在a s i c 的设计流程中就包括f p g a 的验证阶段，即通过了f p g a 的验证才拿去流片。 2 1 2 3f p g a 设计周期短 f p g a 可以反复地编程、擦除。每次更改设计都可以马上在f p g a 上实现， 省了流片的时间，能以最快的速度占领市场。 2 1 2 4 开发工具智能化 f p g a 的开发工具功能强大，应用各种工具可以完成从输入、综合、实现到 配置芯片等一系列功能。还有很多工具可以完成对设计的仿真、优化、约束、在 线调试等功能。 第1 0 页 浙江大学硕士论文 2 1 2 5 内嵌c p u 或d s p 内核 支持软硬件的协同设计，可以作为片上可编程系统的硬件平台。 第2 节f p g a 的设计流程 一个完整的f p g a 设计流程包括电路设计与输入、功能仿真、综合、综合后 仿真、实现、布线后仿真和下板调试等主要步骤。 本文所采取的主要设计流程为：v e r i l o g 代码的编写：代码输入) ( i l i n x 公司的 开发平台i s e7 1 i ；仿真工具采用m o d e lt e c h 公司的m o d e l s i ms ev 6 0 a ；综合工具 采用s y n o p s y s 的s y n p l 母p r ov 8 1 ；系统的下载对象为x i l i n xx c 4 v l x l o o 。 第3 节x n xv - n e x 4 的逻辑结构司 v i n e x - 4 主要由可配置逻辑块( c l b ，c o n f i g u r a b l el o g i cb 1 0 c k ) 、可编程输 入输出模块( 1 0 b ，i 印u t 0 u t p u tb l o c k s ) 、数字时钟管理器( d c m ，d i g i t a lc l o c k m a i l a g e r ) 、块存储器( b l o c kr 咖) 等基本模块构成。 2 3 1 可配置模块c l b n e x _ 4 系列器件的c l b 资源比传统的x i l i l l ) 【器件c l b 资源多了一倍，即 每个c l b 模块由4 个相同的s l i c e 和附加逻辑构成，用于实现组合逻辑和时序逻 辑。每个s l i c e 由两个4 输入函数发生器、进位逻辑、算术逻辑、存储逻辑和函 数复用器组成。 在c l b 细分后的s i j c e 模块中，4 输入函数发生器可以用于实现4 输入查找表( l u t ) 分布式 鼬i m 或1 6 位基于查找表的移位寄存器( s r l l 6 ) ，如 图2 2 。时序逻辑可配置为d 触发器。进位逻辑包括两条快速进位链，用于 提高c l b 模块的算术处理速度。每个c l b 模块既可以配置为分布式r a m ，也 可以配置为分布式r o m 。 第1 1 页 浙江大学硕士论文 图22 ：x 川n x v i r t e x 的s c e 结构 2 3 2 存储器体系结构 v i n e x 系列器件的存储器主要由分布式存储器结构和块存储器结构组成。 2 3 2 1 分布式存储器结构 分布式存储器( d i s 硒b u t c ds e l e c t r a m ) 是由c l b 中的查找表( l u t ) 实现 的。每个c l b 有8 个l u t ，可以构成8 个1 6 x 1 或1 2 8 x 1 ，6 4 x 2 的存储器，通 常用来构成小容量的片内存储器。 2 3 2 2 块存储器结构 块存储器( b 1 0 c k r a m ) 是f p g a 内部的专用存储器模块，通常沿芯片的垂 直边排列。v i n e x 4 器件的块存储器结构为每块1 8 k b ，器件型号不同块的个数也 不同，最动可提供1 6 8 块共3 0 m b 的块存储器。可以配置成单端口b 1 0 c k r a m 或完全的双端口b 1 0 c k r a m ，可提供大约3 3 n s 的访问时间。 第】2 页 浙江大学硕士论文 第3 章s m s 4 算法介绍l l l l s m s 4 是国家密码管理办公室于2 0 0 6 年1 月2 5 日公布的使用于无线局域网 产品的分组密码算法。之所以称s m s 4 为分组密码，是因为s m s 4 是对一组位进 行加解密运算，而不像流密码那样只对一位运算。图3 1 显示了s m s 4 的基本输 入输出框图。 d a t e x k 图3 1 ：s m s 4 基本框图 s m s 4 算法的分组长度为1 2 8 比特，密钥长度为1 2 8 比特。加密算法与密钥 扩展算法都采用3 2 轮非线性迭代结构。解密算法与加密算法的结构相同，只是 轮密钥的使用顺序相反，解密轮密钥是加密轮密钥的逆序。 介绍一种s m s 4 的简单用法，张三和李四共享一个密钥。张三用加密模块把 明文x 解密成密文y 通过网络传送给李四，李四接收到密文y 后用解密模块恢复 明文x ，如图3 2 所示。 张三 李四 图32 ：s m s 4 算法应用 第l3 页 浙江大学硕士论文 第1 节术语说明 3 1 1 字与字节 用互表示e 比特的向量集，乏2 中的元素称为字，芝中的元素称为字节。 3 1 2s 盒 s 盒为固定的8 比特输入8 比特输出的置换，记为s b o x ( ) 。 3 1 3 基本运算 在s m s 4 算法中采用了以下基本运算 o 3 2 比特异或； j3 2 比特循环左移j 位。 3 1 4 密钥及密钥参量 加密密钥长度位1 2 8 比特，表示为删= ( m ，埘k ，麟：，膨e ) ，其中 埘墨( f - 0 ，1 ，3 1 ) 为字。 轮密钥表示为( 吨，喝，心，) ，其中r t ( f _ o ，l ，3 1 ) 为字。轮密钥由加密密 钥生成。 似= ( 雕。，喁，雕：，胀，) 为系统参数，删= ( c 置。，c k ，傩，。) 为固定参 数，用于密钥扩展算法，其中取( f = o ，3 ) 、呱( f = 0 ，3 1 ) 为字。 第2 节轮函数f 该算法采用非线性迭代结构，以字为单位进行加密运算，称一次迭代运算为 轮变换。设输入为( 凰，置，五，置) ( 乏2 ) 4 ，轮密钥为屑e 乏2 ，则轮函数f 为： 第1 4 页 浙江大学硕士论文 f ( ，五，五，墨，础) = 0 丁( 墨0 五0 玛or ) ( 3 1 ) 3 2 1 合成置换t 合成置换t 是字到字的可逆变换，由非线性变换r 和线性变换三复合而成， 即r ( ) = 上( f ( ) ) 。 非线性变换f 由4 个并行的s 盒构成。设输入为爿= ( ，q ，啦，吗) ( 乏) 4 ，输 出为b = ( 6 0 ，岛，6 2 ，岛) ( z ；) 4 ，则： ( 6 0 ，6 l ，岛) = f ( 彳) = ( 肋甜) ，勋舛( q ) ，册耐( 口：) ，勋鲋( 口3 ) )( 3 2 ) 非线性变换f 的输出是线性变化三的输入。设输入为口乏2 ，输出为c 乏2 ， 则： c = 三( b ) = 曰0 ( 口 2 ) 0 ( 曰 l o ) o ( b 1 8 ) o ( b 2 4 )( 3 3 ) 3 2 2s 盒 表3 1 就是s 盒置换，s 盒的资料均采用1 6 进制表示。 表31 ：s 盒置换 0123456789abcdef od 69 0e 9f e c ce 13 db 71 6b 61 4c 22 8f b2 c0 5 12 b6 79 a7 62 ab e0 4c 3 a a 4 4 1 32 64 98 60 69 9 29 c4 25 0f 49 le f 9 87 a3 35 4o b4 3e dc fa c6 2 3e 4b 31 ca 9c 90 8e 89 58 0d f9 4f a 7 58 f3 fa 6 44 70 7a 7f cf 37 31 7b a8 35 93 c1 9e 68 54 fa 8 56 86 b8 1b 27 l6 4d a8 bf 8e bo f4 b7 05 69 d3 5 6l e2 40 e5 e6 35 8d 1a 22 52 27 c3 b0 12 17 88 7 7d 40 04 65 79 fd 32 7 5 24 c3 60 2e 7a 0c 4c 89 e 8e ab f8 ad 24 0c 73 8b 5a 3f 7f 2 c ef 96 11 5a 1 9 e oa e5 da 49 b3 41 a5 5a d9 33 23 0f 58 cb 1 e 3 第15 页 浙江大学硕士论文 al df 6e 22 e 8 2 6 6c a6 0c o2 9 2 3a b 0 d5 34 eb f bd 5d b3 74 5d ef d8 e2 f0 3f f6 a7 26 db c 5 b 5 1 c8 d1 ba f9 2b bd db c7 f1 1d 95 c4 11 f1 05 ad 8 do ac 13 l8 8a 5c d7 bb d2 d7 4d o1 2b 8e 5b 4b 0 e8 96 99 74 a0 c9 67 77 e6 5b 9f l0 9c 56 ec 68 4 fa 8f o7 de c 3 a d c4 d2 07 9e e5 f3 ed 7c b3 94 8 例：输入e f ，则经s 盒后的值为表中第e 行和第f 列的值，s b o x ( e f ) = 8 4 。 第3 节加懈密算法 定义反序变换r 为： r ( 4 ，4 ，4 ，坞) = ( 4 ，4 ，4 ，厶) ，4 乏2 ，f _ o ，l ，2 ，3 。 设明文输入为( 凰，置，五，五) e ( 乏2 ) 4 ，密文输出为( ，巧，e ，e ) ( 乏2 ) 4 ，轮 密钥为r t 霉2 ，f _ o ，1 ，2 ，3 1 。则本算法的加密变换为： + 。= f ( 五，z 。z 。墨。r 墨) = 置。丁( 置+ ，o 五+ 2o 置+ 3o 瞳) ，f - 0 ，1 ，3 1 。 ( k ，k ，k ，艺) = r ( 五：，五，置。，墨，) = ( 以，也。，置，玛：) ( 3 4 ) 本算法的解密变换与加密变换结构相同，不同的仅是轮密钥的使用顺序。 加密时轮密钥的使用顺序为：( 心，南，心，) 解密时轮密钥的使用顺序为：( r 屯。，r k ，心) 图3 3 为s m s 4 加解密算法的整体框图。1 2 8 比特的明( 密) 文输入经初始变 换分成四个字节，分别为x 0 、x 1 、x 2 、x 3 。该结构是轮循环的，称为f e i s t e l 【1 7 】 结构密码。下一轮的输入是上一轮的输出，每一轮都相应的有一个轮密钥，这样 经过3 2 轮迭代输出密文【1 8 】。 第1 6 页 浙江大学硕士论文 圈33 ：s m s 4 算法框图 图3 4 为s m s 4 算法的单个轮次的加密图示。x 1 、x 2 、x 3 以及r k 0 相异或， 异或的结果分成4 个b e t y 分别作为4 个s 盒的输入，参见公式( 2 2 ) ，经s 盒变 换后再进过线性变换l ，所得的结果与x o 异或得x 4 。 图3 4 ：s m s 4 的f e j s t e l 网络 第1 7 页 浙江大学硕士论文 第4 节密钥扩展算法 s m s 4 加密算法的轮密钥由加密密钥通过密钥扩展算法生成，密钥扩展算法 跟加解密算法的结构基本相同，也是经过3 2 轮迭代后生成3 2 个子密钥，以下 简要介绍密钥扩展算法： 加密密钥删= ( 删o ，似1 ，麟2 ，删3 ) ，心，z 知= o ，1 ，2 ，3 ： 设足，z 尹，f = o ，1 ，3 5 ，轮密钥为庸，z 尹，f = o ，1 ，3 1 ，则轮密钥生成方法为： 首先，( ，墨，足2 ，恐) = ( 艘oo 觥o ， lo 麟l ， 掰20 脒2 ， 3o 联，) 然后，对f - 0 ，l ，2 ，3 1 ，t 。= 足l + 4 = 蟛o r ( k + l o k j + 2 0 e + 3 0 傩，) 。 说明： ( 1 ) r 变换与加密算法轮函数中的t 基本相同，只是其中的线性变换l 修改 为：三( b ) = 丑o ( 曰 1 3 ) o ( b s m 删+ s 嘲 总而言之解循环模式可以增加算法的速度，不过速度提升的幅度不是很大，并 且速度的提升是以面积的成倍增长为代价的 表4 1 ：解循环效率比较 结构所需的时间 所占资源 全循环迭代 3 2 t m u x + 3 2 t f + 3 2 t r e gs m u x + s f + s ”g 解2 级循环 1 6 t m u x + 3 2 t f + 1 6 t | c gs 。+ 2 s f s r c g 解4 级循环 8 t m u x + 3 2 t f + 8 k g s m “+ 4 s f + s r e g 第2 3 页 浙江大学硕士论文 4 2 - 3 流水线结构 图