D0I:10.13374/j.issnl00I63.2006.12.044 第28卷第12期 北京科技大学学报 Vol.28 No.12 2006年12月 Journal of University of Science and Technology Beijing Dec.2006 可重组多功能大数运算器的小规模硬件实现 李蓬勃张晓彤王沁 北京科技大学信息工程学院，北京100083 摘要提出了一种面积优先的多功能、可重组的大数值运算器设计方法·基于简单的加法操作， 采用扫描链控制、迭代调用等方法对设计进行优化，实现了14种基本的大数运算功能。每种功能 支持的规格从8位至2048位，给安全芯片用户提供了极大的灵活性，显著减小了代码的开发周期 和成本.由于多种功能尽量复用相同的逻辑资源，本设计在满足体系运算速度的前提下，规模只有 13887门，完全满足安全芯片面积优先的设计约束. 关键词运算器：运算功能；安全芯片：硬件设计 分类号TP309.7;TP332.2 随着各种加解密算法密钥长度的逐步增加， 对规模要求严格的设计需求，提出了一种小规模 在一些具有安全性需求的芯片设计中，大规格数 的大数值运算器设计方法，基于加法操作，在扫 据运算的硬件实现已成为硬件设计的主要考虑因 描链的配合下，全部用逻辑电路实现了包括加减 素和设计难点，比如RSA等基于大数分解的公 乘除及模乘、模幂乘等多种运算功能，各功能支持 钥密码算法，虽然目前密钥长度已达1024位，但 的运算规格从8位一直扩展到2048位.经综合 是仍然不能避免将被破解的厄运，致使密钥还需 验证，在20Mz的主频下，设计规模只有13887 进一步增加.这种运算规格的增长不仅使加解密 门，完全适用于CSTU安全体系的面积优先的设 运算速度降低，而且增加了硬件实现的难度 计要求 目前国内外对大数值运算器的研究，主要集 中在大数模幂乘运算的实现上，其数学表达式为 1CSTU安全芯片体系结构简介 S=Amod N.大数模幂乘一般用模平方和模乘 随着人们对安全需求的不断增加，采用固定 来实现：对于一个指数B,模平方的次数是固定 或单一加解密算法的产品已经无法满足人们的需 的，而模乘的次数是可以优化的，因此可在以下 求，目前的安全产品需要经常更换加解密算法甚 两方面考虑运算加速：(1)减少模乘次数；(2)提 至改变整个安全策略，适应这种需求常用的方法 高大数模乘速度、针对第一种方案提出的加速算 是在基本运算器之上，使用软件编程的方式灵活 法有m进制方法、加法链法、Yacobi法：针对第二 的实现算法的转换.但是面对不断升级的软件破 种方案有估商型系列算法山和Montgomery系列 解技术的挑战，以及软件方式的低速率性，各种加 算法[.以上各种方案或者需要预计算，占用较 解密算法也由软件实现向硬件电路实现过渡，为 大的存储空间，或者需要设置专门的乘法单元，都 解决这一矛盾，可支持多种加解密算法的硬件安 是在牺牲规模的前提下提高运算速度，在对规模 全产品就应运而生，其中基于可重组方式设计的 要求严格的安全芯片中，以上方法不再适用.而 安全芯片无疑又具有领先优势 且，它们也并未涉及其他运算（如加、减、乘、除等 CSTU保密终端安全芯片采用了可重组设计 四则运算)的大规格实现方法 思想，综合分析了当前大量使用的DES,AES, 根据保密终端安全芯片CSTU(China secure IDEA,RSA,MD5等十余种加解密算法的实现过 terminal unit,国家密码委员会审批项目，产品型 程，支持对称、公钥、摘要密码算法及用户隐秘算 号SSX11)对运算速度要求不高（主频20Mz)、 法，提供这些算法实现所需的IP平台，不同的用 收稿日期：2005-12-06修回日期：2006-04-14 户可以根据自己的需要在平台上进行二次开发， 作者简介：李蓬勃(1980一)，男，硕士研究生；张晓彤(1968一)， 形成自己定义的安全算法及策略 男，副教授，博士 CSTU安全芯片可用于保密电话、安全卡证
可重组多功能大数运算器的小规模硬件实现 李蓬勃 张晓彤 王 沁 北京科技大学信息工程学院北京100083 摘 要 提出了一种面积优先的多功能、可重组的大数值运算器设计方法．基于简单的加法操作 采用扫描链控制、迭代调用等方法对设计进行优化实现了14种基本的大数运算功能．每种功能 支持的规格从8位至2048位给安全芯片用户提供了极大的灵活性显著减小了代码的开发周期 和成本．由于多种功能尽量复用相同的逻辑资源本设计在满足体系运算速度的前提下规模只有 13887门完全满足安全芯片面积优先的设计约束． 关键词 运算器；运算功能；安全芯片；硬件设计 分类号 TP309∙7；TP332∙2 收稿日期：20051206 修回日期：20060414 作者简介：李蓬勃（1980—）男硕士研究生；张晓彤（1968—） 男副教授博士 随着各种加解密算法密钥长度的逐步增加 在一些具有安全性需求的芯片设计中大规格数 据运算的硬件实现已成为硬件设计的主要考虑因 素和设计难点．比如 RSA 等基于大数分解的公 钥密码算法虽然目前密钥长度已达1024位但 是仍然不能避免将被破解的厄运致使密钥还需 进一步增加．这种运算规格的增长不仅使加解密 运算速度降低而且增加了硬件实现的难度． 目前国内外对大数值运算器的研究主要集 中在大数模幂乘运算的实现上其数学表达式为 S＝ A Bmod N．大数模幂乘一般用模平方和模乘 来实现；对于一个指数 B模平方的次数是固定 的而模乘的次数是可以优化的．因此可在以下 两方面考虑运算加速：（1） 减少模乘次数；（2） 提 高大数模乘速度．针对第一种方案提出的加速算 法有 m 进制方法、加法链法、Yacobi 法；针对第二 种方案有估商型系列算法［1］和 Montgomery 系列 算法［2］．以上各种方案或者需要预计算占用较 大的存储空间或者需要设置专门的乘法单元都 是在牺牲规模的前提下提高运算速度．在对规模 要求严格的安全芯片中以上方法不再适用．而 且它们也并未涉及其他运算（如加、减、乘、除等 四则运算）的大规格实现方法． 根据保密终端安全芯片 CSTU （China secure terminal unit国家密码委员会审批项目产品型 号 SSX11） 对运算速度要求不高（主频20MHz）、 对规模要求严格的设计需求提出了一种小规模 的大数值运算器设计方法．基于加法操作在扫 描链的配合下全部用逻辑电路实现了包括加减 乘除及模乘、模幂乘等多种运算功能各功能支持 的运算规格从8位一直扩展到2048位．经综合 验证在20MHz 的主频下设计规模只有13887 门完全适用于 CSTU 安全体系的面积优先的设 计要求． 1 CSTU 安全芯片体系结构简介 随着人们对安全需求的不断增加采用固定 或单一加解密算法的产品已经无法满足人们的需 求目前的安全产品需要经常更换加解密算法甚 至改变整个安全策略．适应这种需求常用的方法 是在基本运算器之上使用软件编程的方式灵活 的实现算法的转换．但是面对不断升级的软件破 解技术的挑战以及软件方式的低速率性各种加 解密算法也由软件实现向硬件电路实现过渡．为 解决这一矛盾可支持多种加解密算法的硬件安 全产品就应运而生其中基于可重组方式设计的 安全芯片无疑又具有领先优势． CSTU 保密终端安全芯片采用了可重组设计 思想综合分析了当前大量使用的 DESAES IDEARSAMD5等十余种加解密算法的实现过 程支持对称、公钥、摘要密码算法及用户隐秘算 法提供这些算法实现所需的 IP 平台不同的用 户可以根据自己的需要在平台上进行二次开发 形成自己定义的安全算法及策略． CSTU 安全芯片可用于保密电话、安全卡证 第28卷 第12期 2006年 12月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．28No．12 Dec．2006 DOI:10．13374／j．issn1001－053x．2006．12．044
Vol.28o.12 李蓬勃等：可重组多功能大数运算器的小规模硬件实现 .1203. 或移动安全终端等产品中，这些产品的共同特点 D的值一直为1；当B出现第一个1后才进入有 是对规模要求比较严格，对公钥密码算法的速度 效的模乘运算，在具体实现时，设计专门的电路 要求不高，为提供对公钥密码算法和数字签名算 从高到低扫描指数B的每一位，当在找到第一个 法的支持，大数运算器成为CSTU安全体系中关 1之前，不做任何运算，找到第一个1时，使D= 键的核心IP.根据实际需求，本设计在满足硬件 A,以后根据每次扫描的b[]值，调用模乘实现 规模尽可能小同时支持尽可能多的运算功能和多 运算 种规格的数据运算的条件下，最终保证整个系统 经过对多种公钥加解密算法的分析一如 的灵活性 R$A算法，通常公钥的有效位较短，而私钥有效 2算法分析 位较长，加密中的模幂乘运算，指数有效位很少， 所以上面的改进可大大减少模乘次数，加快加密 2.1模幂乘算法分析 过程.以目前常用的私钥和模数1024bit,公钥 模幂乘运算采用平方一乘算法③]，将模幂乘 128bit情况为例，采用上述改进可减少896次不 运算转化为模乘和模平方运算实现 必要的模乘，解密过程使用中国余数定理 平方乘算法：一般地，求S=A mod N,其中 (CRT),可有效降低解密指数的长度，整个算法的 A<N,B<N;将指数B表示为二进制，即 执行效率得到进一步提高 B=(b1-1b1-2…b1b0)2=2b:2, 2.2模乘及模加的实现方法 =0 模乘采用改进的Blakley加法型算法，原理与 b:∈{0,1{，=0,1,2，…，l-1. 平方乘算法类似，核心是将模乘转化为模加实 于是， 现.如通常S=(AXB)modN,A<N,B<N可 A=A-g 以按如下方式考虑， =0 将B表示成二进制： b:∈{0,1}，i=0,1,2,…,1-1 根据求模运算特性： B=(br-1br-g…b1b0)2=号6,2， (axb)mod n=(amod n)x (bmod n))mod n; b:∈10,1}，i=0,1,2,…,1-1. 于是， S=A"mod n= mod N= =0 mod N= =0 b:∈0,1f,=0,1,2,…,l-1: (4'mod N) mod N. S=(A×B)=modN= 号(b,2Am= 其中b:∈{0,1{，=0,1,2，…，1-1.则由上式可 (6;2iA)mod N)mod N= 得平方乘算法如下： Algorithm Square-Multi: (24 wy mod N. Begin D=1: 其中b:{0,1},=0,1,2,…,1-1 For i=l-1 downto 0 do 由上式可知，可以像平方乘算法一样，将模 D=(D*D)mod N; 乘转化为模加实现. If b[i]=1 then 一般模加运算表示为S=(A十B)modN,观 D=(D*A)mod N:} 察以上模乘及模幂乘算法原理描述，可知在其调 Return(D); 用的模加运算中，因为A<N且B<N,则(A十 End; B)2N,所以， 观察算法，由于指数B化为二进制后的长度 (A+B)mod N= 不确定，多数情况下高位会存在很多个0.如果完 A+B, O≤(A+B)<N 全按照该算法实现，指数B从最高位起开始运 A十B-N,N≤(A+B)<2N 算，在第一个1出现以前，虽进行了多次运算，但 因此考虑在运算中同时计算(A十B)和(A
或移动安全终端等产品中这些产品的共同特点 是对规模要求比较严格对公钥密码算法的速度 要求不高．为提供对公钥密码算法和数字签名算 法的支持大数运算器成为 CSTU 安全体系中关 键的核心 IP．根据实际需求本设计在满足硬件 规模尽可能小同时支持尽可能多的运算功能和多 种规格的数据运算的条件下最终保证整个系统 的灵活性． 2 算法分析 2∙1 模幂乘算法分析 模幂乘运算采用平方—乘算法［3］将模幂乘 运算转化为模乘和模平方运算实现． 平方—乘算法：一般地求 S＝ A Bmod N其中 A＜ NB＜ N；将指数 B 表示为二进制即 B＝（ bl—1bl—2…b1b0）2＝ ∑ l－1 i＝0 bi2i bi∈｛01｝i＝012…l—1． 于是 A B＝ A ∑ l－1 i＝0 b i2 i ＝ ∏ l－1 i＝0 A b i2 i bi∈｛01｝i＝012…l—1 根据求模运算特性： （ a×b）mod n＝（（ amod n）×（ bmod n））mod n； S＝ A Bmod n＝ ∏ l－1 i＝0 A b i2 i mod N＝ ∏ l－1 i＝0 （ A b i2 i mod N） mod N＝ ∏ l－1 i＝0 b i ≠0 （ A 2 i mod N） mod N． 其中 bi∈｛01｝i＝012…l—1．则由上式可 得平方—乘算法如下： Algorithm Square-Multi： Begin D∶＝1； For i∶＝ l—1downto0do ｛D∶＝（ D∗ D） mod N； If b ［ i］＝1then D∶＝（ D∗ A） mod N；｝ Return（ D）； End； 观察算法由于指数 B 化为二进制后的长度 不确定多数情况下高位会存在很多个0．如果完 全按照该算法实现指数 B 从最高位起开始运 算在第一个1出现以前虽进行了多次运算但 D 的值一直为1；当 B 出现第一个1后才进入有 效的模乘运算．在具体实现时设计专门的电路 从高到低扫描指数 B 的每一位当在找到第一个 1之前不做任何运算找到第一个1时使 D＝ A以后根据每次扫描的 b ［ i］值调用模乘实现 运算． 经过对多种公钥加解密算法的分析－－－如 RSA 算法通常公钥的有效位较短而私钥有效 位较长．加密中的模幂乘运算指数有效位很少 所以上面的改进可大大减少模乘次数加快加密 过程．以目前常用的私钥和模数1024bit公钥 128bit 情况为例采用上述改进可减少896次不 必要 的 模 乘．解 密 过 程 使 用 中 国 余 数 定 理 （CRT）可有效降低解密指数的长度整个算法的 执行效率得到进一步提高． 2∙2 模乘及模加的实现方法 模乘采用改进的 Blakley 加法型算法原理与 平方—乘算法类似核心是将模乘转化为模加实 现．如通常 S＝（ A×B）mod NA＜ NB＜ N 可 以按如下方式考虑． 将 B 表示成二进制： B＝（ bl—1bl—2…b1b0）2＝ ∑ l－1 i＝0 bi2i bi∈｛01｝i＝012…l—1． 于是 A×B＝ A× ∑ l－1 i＝0 bi2i＝ ∑ l－1 i＝0 （ bi2i A） bi∈｛01｝i＝012…l—1； S＝（ A×B）＝mod N＝ ∑ l－1 i＝0 （ bi2i A） mod N＝ ∑ l－1 i＝0 （ bi2i A）mod N） mod N＝ ∑ l－1 i＝0 b i ≠0 （（2i A）mod N） mod N． 其中 bi｛01｝i＝012…l—1． 由上式可知可以像平方—乘算法一样将模 乘转化为模加实现． 一般模加运算表示为 S＝（ A ＋B）mod N观 察以上模乘及模幂乘算法原理描述可知在其调 用的模加运算中因为 A ＜ N 且 B＜ N则（ A ＋ B）＜2N所以 （ A＋B）mod N＝ A＋B 0≤（ A＋B）＜ N A＋B— N N≤（ A＋B）＜2N 因此考虑在运算中同时计算（ A ＋ B）和（ A Vol．28No．12 李蓬勃等： 可重组多功能大数运算器的小规模硬件实现 ·1203·
,1204 北京科技大学学报 2006年第12期 +B一N)两个结果，运算完成后通过判断加法器 RAM 与减法器的进位输出(C0)与借位输出(B0),决 运算数据 运算结果 323232 定哪个为本次模加的正确结果，同上，A,B,N 功能 状态 基本运算单元 均为l位的二进制数，若C0=1,则说明(A十B) 扫措链逻 规格 寄存器 扫描 动 结束 为1十1位二进制数，必大于1位的N:若C0=0, 译码照动 信息 器 则(A十B)和N同为L位，当B0=1时(A十B) 目的 功能控制逐辑 结束信号 <N,当BO=0时N≤(A十B) 大数值运算馨 A十B, C0=0且B0=1 故(A+B)modN= 图1大数运算器内部结构图 、A十B一N,否则 Fig.1 Block diagram of the large number calculator 从而可以在一次运算中完成加法和求模过 程，使模加的运算速度提高1倍 结构如图2所示，由输入选通控制MUX-IN,32 2.3其他功能实现 位加法器ADD,32位减法器SUB,移位逻辑SF 经过对多种公钥加解密算法及签名算法的分 和输出选通控制MUX OUT组成， 析，为提高芯片整体灵活性本设计还给出了对乘 A B N 法、除法、求模、模加法逆、开方几种常用运算的支 MUX-IN 持，同样选择基于加减运算的算法实现，充分考 a b 虑算法对扫描链等已有逻辑资源的服用，设计出 ADD CI 符合产品运算速度的面积最小化的系统.表1列 SF SI 出系统实现的其他功能模块采用的算法名称、详 SUB 细算法及相关文献 e 表1系统实现的其他功能模块 MUX-OUT Table 1 Arithmetics of other functions FOUT 序号 模块名称 使用算法 参考文献 图2ALU核心结构图 1 乘法 加法式算法 [4] Fig-2 Kernel structure of ALU 除法 不恢复迭代算法 [4] 求模 不恢复迭代算法 [4] 各功能在ALU中的具体实现方式见表2： 4 开方 不恢复迭代算法 [5] 功能控制逻辑：完成各个功能的控制，可分为 5加减、模加、增减量、移位等功能 略 简单功能和复杂功能两类不同的控制 (1)简单功能：32位规格以上的加减、模加、 3 增（减）量、移位功能.功能实现通过多周期迭代 设计实现 调用ALU相应功能实现，多次调用间保持进/借 以一个可以完成32位规格加、减、模加、增减 位传递 量、移位等基本功能的ALU为基本运算单元，在 (②)复杂功能：模乘、模幂乘、乘除、开方功 扫描链逻辑的控制下，可以完成乘、除、开方、模 能，根据算法原理设计状态机，根据扫描链逻辑 乘、模幂乘等多种复杂运算，设计结构如图1所 的配合信号，通过调用简单功能实现运算 示.大数值运算器的外接口信号分以下三类. 扫描链逻辑：当功能控制逻辑在完成复杂功 (1)控制：功能，规格以及源、目的指示；(2)数据： 能时，驱动扫描链逻辑动作，核心电路为32位的 来自体RAM的源操作数，运算结果到RAM的反 移位寄存器，扫描链逻辑可完成：待扫描数据的自 馈：(3)状态：运算结束，对体系相应状态寄存器的 动装载和切换；扫描数据高位0的自动去除，即自 控制信号， 动找到第一个1，并给出标识信号；在使能信号的 基本运算单元(ALU):可在单周期内完成32 控制下从高到低自动扫描数据，给出扫描结果；扫 位加减、增（减）量、模加、左右移一位功能，其核心 描结束给出结束信号
＋B— N）两个结果运算完成后通过判断加法器 与减法器的进位输出（CO）与借位输出（BO）决 定哪个为本次模加的正确结果．同上ABN 均为 l 位的二进制数若 CO＝1则说明（ A ＋ B） 为 l＋1位二进制数必大于 l 位的 N；若 CO＝0 则（ A＋ B）和 N 同为 l 位当 BO＝1时（ A ＋ B） ＜ N当 BO＝0时 N≤（ A＋B）． 故（ A＋ B）mod N＝ A＋ B CO＝0且 BO＝1 A＋ B— N 否则 从而可以在一次运算中完成加法和求模过 程使模加的运算速度提高1倍． 2∙3 其他功能实现 经过对多种公钥加解密算法及签名算法的分 析为提高芯片整体灵活性本设计还给出了对乘 法、除法、求模、模加法逆、开方几种常用运算的支 持．同样选择基于加减运算的算法实现充分考 虑算法对扫描链等已有逻辑资源的服用设计出 符合产品运算速度的面积最小化的系统．表1列 出系统实现的其他功能模块采用的算法名称、详 细算法及相关文献． 表1 系统实现的其他功能模块 Table1 Arithmetics of other functions 序号 模块名称 使用算法 参考文献 1 乘法 加法式算法 ［4］ 2 除法 不恢复迭代算法 ［4］ 3 求模 不恢复迭代算法 ［4］ 4 开方 不恢复迭代算法 ［5］ 5 加减、模加、增减量、移位等功能 － 略 3 设计实现 以一个可以完成32位规格加、减、模加、增减 量、移位等基本功能的 ALU 为基本运算单元在 扫描链逻辑的控制下可以完成乘、除、开方、模 乘、模幂乘等多种复杂运算．设计结构如图1所 示．大数值运算器的外接口信号分以下三类． （1）控制：功能规格以及源、目的指示；（2）数据： 来自体 RAM 的源操作数运算结果到 RAM 的反 馈；（3）状态：运算结束对体系相应状态寄存器的 控制信号． 基本运算单元（ALU）：可在单周期内完成32 位加减、增（减）量、模加、左右移一位功能其核心 图1 大数运算器内部结构图 Fig．1 Block diagram of the large number calculator 结构如图2所示由输入选通控制 MUX—IN32 位加法器 ADD32位减法器 SUB移位逻辑 SF 和输出选通控制 MUX—OUT 组成． 图2 ALU 核心结构图 Fig．2 Kernel structure of ALU 各功能在 ALU 中的具体实现方式见表2： 功能控制逻辑：完成各个功能的控制可分为 简单功能和复杂功能两类不同的控制． （1） 简单功能：32位规格以上的加减、模加、 增（减）量、移位功能．功能实现通过多周期迭代 调用 ALU 相应功能实现多次调用间保持进／借 位传递． （2） 复杂功能：模乘、模幂乘、乘除、开方功 能．根据算法原理设计状态机根据扫描链逻辑 的配合信号通过调用简单功能实现运算． 扫描链逻辑：当功能控制逻辑在完成复杂功 能时驱动扫描链逻辑动作．核心电路为32位的 移位寄存器扫描链逻辑可完成：待扫描数据的自 动装载和切换；扫描数据高位0的自动去除即自 动找到第一个1并给出标识信号；在使能信号的 控制下从高到低自动扫描数据给出扫描结果；扫 描结束给出结束信号． ·1204· 北 京 科 技 大 学 学 报 2006年第12期
Vol.28 No.12 李蓬勃等：可重组多功能大数运算器的小规模硬件实现 .1205. 表2ALU各功能实现方式 Table 2 Implement of ALU's functions 功能 输入选通 加法器 减法器 输出选通 说明 加法 a=A,b=B CI=0 OUT=e 加法器完成运算 减法 a=A,6=0,c=B BI=0 OUT=f 减法器完成运算 增量 a=A,b=A,c=A CI=1 BI=0 OUT=f 0UT=(A十A十1)-A=A十1 减量 a=A,b=A,c=A CI=0 BI=1 OUT=f 0UT=(A+A)-A-1=A-1 模加 a=A:b=B,c=N CI=0 BI=0 OUT=e,f 输出由CO,B0共同决定 移位 a=A OUT=d 移位逻辑完成 4 测试及结论 法，设计支持的所有功能及规格如表3所示，所 有模块均在ModelSim环境下通过了逻辑仿真， 本文提出了一种用于可重组安全芯片的，面 并在Xilinx公司的Virtex?一Ⅱ系列FPGA产品 积优先、多功能、可重组的大数值运算器的实现方 XC2V6000上经过实际功能验证， 表3大数运算器功能规格列表 Table 3 Functions and specs of the large number calculator 功能 公式描述 支持规格 运算周期数（平均值） 加法 S=A十B 减法 S=A-B 增量 S=A十1 8位、16位、32位、64 减量 S=A-1 位、128位、256位、512 n/32 左移一位 S=A《1 位、1024位、2048位 右移一位 S=A>1 模加 S=(A十B)modN 模加逆 S=A-1,(A十A-)modN=0 n2/64 乘法 S=AXB n/16(n+n/2) 除法 S=A/B 32位、64位、128位、 n/32(n+n/2+1/2) 256位、512位、1024 开方 s=.A n/32(2n+n/4) 位、2048位（其中乘法 求模 S=Amod B 最大规格为1024位) n/32(m+1/2) 模乘 S=(AX B)mod N n/32(n十n/2) 模幂乘 S=Amod N n/32(n+n/2)(n+n/2) 使用Synopsys公司Design Compiler综合工 表4.可见本设计虽然运算速度稍慢，但设计规 具，在台基电(TSMC)0.25m工艺和安全芯片要 模同比大大降低，完全符合CSTU保密终端安全 求的20Hh时钟主频下的综合结果为13887门. 芯片对面积优先的设计要求，速度也在设计允许 设计的结果与近年的几个大数值运算器的对比见 范围内 表4不同大数运算器设计对比 Table 4 Contrast between different designs of larger number calculators 类别 主频/Mh 支持功能 位长 模幂乘运算周期数 规模/103门 文献[6] 150 模幂乘 512 2(n+4)(n+2) 109 文献[7] 200 模幂乘 1024 (n/2+2)(n/2+3) 187 文献[8] 50 模幂乘 1024 R-L:(n+34)(n+2) 156 L-R:(n+34)(1.5n+3) 92 本文 汤 加、减、乘、除、模加、模乘、模幂乘等共14种8至2048可选 n/32(n+n/2)(n+n/2) 13.9
表2 ALU 各功能实现方式 Table2 Implement of ALU’s functions 功能 输入选通 加法器 减法器 输出选通 说明 加法 a＝ Ab＝ B CI＝0 OUT＝e 加法器完成运算 减法 a＝ Ab＝0c＝ B BI＝0 OUT＝ f 减法器完成运算 增量 a＝ Ab＝ Ac＝ A CI＝1 BI＝0 OUT＝ f OUT＝（ A＋ A＋1）— A＝ A＋1 减量 a＝ Ab＝ Ac＝ A CI＝0 BI＝1 OUT＝ f OUT＝（ A＋ A）— A—1＝ A—1 模加 a＝ Ab＝ Bc＝ N CI＝0 BI＝0 OUT＝ef 输出由 COBO 共同决定 移位 a＝ A OUT＝ d 移位逻辑完成 4 测试及结论 本文提出了一种用于可重组安全芯片的面 积优先、多功能、可重组的大数值运算器的实现方 法．设计支持的所有功能及规格如表3所示．所 有模块均在 ModelSim 环境下通过了逻辑仿真 并在 Xilinx 公司的 Virtex—Ⅱ系列 FPGA 产品 XC2V6000上经过实际功能验证． 表3 大数运算器功能规格列表 Table3 Functions and specs of the large number calculator 功能 公式描述 支持规格 运算周期数（平均值） 加法 S＝ A＋ B 减法 S＝ A— B 增量 S＝ A＋1 减量 S＝ A—1 左移一位 S＝ A≪1 右移一位 S＝ A≫1 模加 S＝（ A＋ B）mod N 8 位、16 位、32 位、64 位、128位、256位、512 位、1024位、2048位 n／32 模加逆 S＝ A —1（ A＋ A —1）mod N＝0 乘法 S＝ A× B 除法 S＝ A／B 开方 S＝ A 求模 S＝ Amod B 模乘 S＝（ A× B）mod N 模幂乘 S＝ A Bmod N 32 位、64 位、128 位、 256 位、512 位、1024 位、2048 位 （其中乘法 最大规格为1024位） n 2／64 n／16（ n＋ n／2） n／32（ n＋ n／2＋1／2） n／32（2n＋ n／4） n／32（ n＋1／2） n／32（ n＋ n／2） n／32（ n＋ n／2）（ n＋ n／2） 使用 Synopsys 公司 Design Compiler 综合工 具在台基电（TSMC）0∙25μm 工艺和安全芯片要 求的20Hz 时钟主频下的综合结果为13887门． 设计的结果与近年的几个大数值运算器的对比见 表4．可见本设计虽然运算速度稍慢但设计规 模同比大大降低完全符合 CSTU 保密终端安全 芯片对面积优先的设计要求速度也在设计允许 范围内． 表4 不同大数运算器设计对比 Table4 Contrast between different designs of larger number calculators 类别 主频／MHz 支持功能 位长 模幂乘运算周期数 规模／103 门 文献［6］ 150 模幂乘 512 2（ n＋4）（ n＋2） 109 文献［7］ 200 模幂乘 1024 （ n／2＋2）（ n／2＋3） 187 文献［8］ 50 模幂乘 1024 R—L：（ n＋34）（ n＋2） 156 L—R：（ n＋34）（1∙5n＋3） 92 本文 20 加、减、乘、除、模加、模乘、模幂乘等共14种 8至2048可选 n／32（ n＋ n／2）（ n＋ n／2） 13∙9 Vol．28No．12 李蓬勃等： 可重组多功能大数运算器的小规模硬件实现 ·1205·
,1206 北京科技大学学报 2006年第12期 参考文献 and Processors.Texas:IEEE Computer Sociaty Press,1996: 538 [1]GroBschadl J.High-speed RSA hardware based on Barrett's modular reduction method/Proceedings of Cryptographic [6]Wu C H.Hong J H.Wu C W.RSA cryptosystem design Hardware and Embedded Systems(CHES 2000).Germany: based on the Chinese remainder theorem//Proceedings of Asia Springer-Verlag Press.2000:191 South Pacific Design Automation Conference 2001 (ASP-DAC [2]Walter C D.Montgomery's multiplication technique:How to 2001).New York:IEEE Press.2001:391 make it smaller and faster//Proceedings of Cryptographie [7]Melvor C.MeLoone M.Fast Montgomery modular multipli- Hardware and Embedded Systems(CHES 1999).Germany: cation and RSA eryptographie processor architecturesPro Springer-Verlag Press.1999:136 ceedings of 37th Asilomar Conference on Signals.Systems and [3]卢开澄.计算机密码学.北京：清华大学出版社，2003：220 Computers.New York:IEEE Press.2003:379 [4]李亚民。计算机组成与系统结构·北京：清华大学出版社， [8]Kwon T W.Two implementation methods of a 1024 bit RSA 2000:66 cryptoprocesor based on modified Montgomery algorithm [5]Li Y M.Chu W M.A New non-restoring square root al- Proceedings of the 2001 IEEE International Symposium on gorithm and its VLSI implementations//Proceedings of Inter- Circuits and Systems (ISCAS 2001).New York:IEEE Pre5s,2001:650 national Conference on Computer Design-VLSI in Computers Small-scale hardware implementation of reconfigurable multifunctional large number calculators LI Pengbo,ZHA NG Xiaotong,WANG Qin Information Engineering School.University of Science and Technology Beijing.Beijing 100083.China ABSTRACT An area first design method for multifunctional and reconfigurable large number calculators was brought forward.Based on the addition algorithm,the design was optimized by the method of scan chain control and iterative invoke and realized 14 kinds of large-number operations such as addition,sub- traction,multiplication,division,module addition,module multiplication,module exponential,etc.Every operation supported the data length from 8bits to 2048bits,which afforded security chip users'maneuver- ability,and reduced the time and cost of coding remarkably.Under the speed restriction of architecture, operations reused the same logic units as possible and the design just contained 13 887 gats,which could meet the requirement of area first design completely. KEY WORDS calculator;calculation function:security chip;hardware design
参 考 文 献 ［1］ GroBschadl J．High-speed RSA hardware based on Barrett’s modular reduction method ∥ Proceedings of Cryptographic Hardware and Embedded Systems （CHES 2000）．Germany： Springer-Verlag Press2000：191 ［2］ Walter C D．Montgomery’s multiplication technique：How to make it smaller and faster ∥ Proceedings of Cryptographic Hardware and Embedded Systems （CHES 1999）．Germany： Springer-Verlag Press1999：136 ［3］ 卢开澄．计算机密码学．北京：清华大学出版社2003：220 ［4］ 李亚民．计算机组成与系统结构．北京：清华大学出版社 2000：66 ［5］ Li Y MChu W M．A New non-restoring square root algorithm and its VLSI implementations∥Proceedings of International Conference on Computer Design—VLSI in Computers and Processors．Texas：IEEE Computer Sociaty Press1996： 538 ［6］ Wu C HHong J HWu C W．RSA cryptosystem design based on the Chinese remainder theorem∥Proceedings of Asia South Pacific Design Automation Conference2001（ASP—DAC 2001）．New York：IEEE Press2001：391 ［7］ McIvor CMcLoone M．Fast Montgomery modular multiplication and RSA cryptographic processor architectures ∥Proceedings of 37th Asilomar Conference on SignalsSystems and Computers．New York：IEEE Press2003：379 ［8］ Kwon T W．Two implementation methods of a1024bit RSA cryptoprocesor based on modified Montgomery algorithm ∥ Proceedings of the 2001 IEEE International Symposium on Circuits and Systems （ ISCAS 2001）． New York：IEEE Press2001：650 Smal-l scale hardware implementation of reconfigurable multifunctional large number calculators LI PengboZHA NG XiaotongWA NG Qin Information Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China ABSTRACT An area-first design method for multifunctional and reconfigurable large number calculators was brought forward．Based on the addition algorithmthe design was optimized by the method of scan chain control and iterative invoke and realized14kinds of large-number operations such as additionsubtractionmultiplicationdivisionmodule additionmodule multiplicationmodule exponentialetc．Every operation supported the data length from8bits to2048bitswhich afforded security chip users’maneuverabilityand reduced the time and cost of coding remarkably．Under the speed restriction of architecture operations reused the same logic units as possible and the design just contained 13887gatswhich could meet the requirement of area-first design completely． KEY WORDS calculator；calculation function；security chip；hardware design ·1206· 北 京 科 技 大 学 学 报 2006年第12期
