datasheet

可重组多功能大数运算器的小规模硬件实现

2008-05-04来源: 中华电子网 关键字:实现算法  模幂乘  运算器  ALU  硬件实现  移位寄存器  公钥密码算法  实现方法

  随着各种加解密算法密钥长度的逐步增加,在一些具有安全性需求的芯片设计中,大规格数据运算的硬件实现已成为硬件设计的主要考虑因素和设计难点.比如RSA等基于大数分解的公钥密码算法,虽然目前密钥长度已达1024位,但是仍然不能避免将被破解的厄运,致使密钥还需进一步增加.这种运算规格的增长不仅使加解密运算速度降低,而且增加了硬件实现的难度.

  目前国内外对大数值运算器的研究,主要集中在大数模幂乘运算的实现上,其数学表达式为S=ABmodN.大数模幂乘一般用模平方和模乘来实现;对于一个指数B,模平方的次数是固定的,而模乘的次数是可以优化的.因此可在以下两方面考虑运算加速:(1)减少模乘次数;(2)提高大数模乘速度.针对第一种方案提出的加速算法有m进制方法、加法链法、Yacobi法;针对第二种方案有估商型系列算法和Montgomery系列算法_.以上各种方案或者需要预计算,占用较大的存储空间,或者需要设置专门的乘法单元,都是在牺牲规模的前提下提高运算速度.在对规模要求严格的安全芯片中,以上方法不再适用.而且,它们也并未涉及其他运算(如加、减、乘、除等四则运算)的大规格实现方法

  根据保密终端安全芯片CSTU(China secureterminal unit,国家密码委员会审批项目,产品型号SSX11)对运算速度要求不高(主频20 MHz)、对规模要求严格的设计需求,提出了一种小规模的大数值运算器设计方法.基于加法操作,在扫描链的配合下,全部用逻辑电路实现了包括加减乘除及模乘、模幂乘等多种运算功能,各功能支持的运算规格从8位一直扩展到2048位.经综合验证,在20MHz的主频下,设计规模只有13887门,完全适用于CSTU安全体系的面积优先的设计要求.

  1 CSTU 安全芯片体系结构简介

  随着人们对安全需求的不断增加,采用固定或单一加解密算法的产品已经无法满足人们的需求,目前的安全产品需要经常更换加解密算法甚至改变整个安全策略.适应这种需求常用的方法是在基本运算器之上,使用软件编程的方式灵活的实现算法的转换.但是面对不断升级的软件破解技术的挑战,以及软件方式的低速率性,各种加解密算法也由软件实现向硬件电路实现过渡.为解决这一矛盾.可支持多种加解密算法的硬件安全产品就应运而生,其中基于可重组方式设计的安全芯片无疑又具有领先优势.

  CSTU保密终端安全芯片采用了可重组设计思想,综合分析了当前大量使用的DES,AES,IDEA,RSA,MD5等十余种加解密算法的实现过程,支持对称、公钥、摘要密码算法及用户隐秘算法,提供这些算法实现所需的IP平台,不同的用户可以根据自己的需要在平台上进行二次开发,形成自己定义的安全算法及策略.

  CSTU安全芯片可用于保密电话、安全卡证或移动安全终端等产品中,这些产品的共同特点是对规模要求比较严格,对公钥密码算法的速度要求不高.为提供对公钥密码算法和数字签名算法的支持,大数运算器成为CSTU安全体系中关键的核心IP.根据实际需求,本设计在满足硬件规模尽可能小同时支持尽可能多的运算功能和多种规格的数据运算的条件下,最终保证整个系统的灵活性.

  2 算法分析

  2.1 模幂乘算法分析

  模幂乘运算采用平方乘算法,将模幂乘运算转化为模乘和模平方运算实现.

  平方-乘算法:一般地,求S=ABmodN,其中A

  

  

  

  观察算法,由于指数B化为二进制后的长度不确定,多数情况下高位会存在很多个0.如果完全按照该算法实现,指数B从最高位起开始运算,在第一个1出现以前,虽进行了多次运算,但D的值一直为1;当B出现第一个1后才进入有效的模乘运算.在具体实现时,设计专门的电路从高到低扫描指数B的每一位,当在找到第一个1之前,不做任何运算,找到第一个1时,使D=A,以后根据每次扫描的6[i]值,调用模乘实现运算.

  经过对多种公钥加解密算法的分析——如RSA算法,通常公钥的有效位较短,而私钥有效位较长.加密中的模幂乘运算,指数有效位很少,所以上面的改进可大大减少模乘次数,加快加密过程.以目前常用的私钥和模数1 024 bit,公钥128bit情况为例,采用上述改进可减少896次不必要的模乘.解密过程使用中国余数定理(CRT),可有效降低解密指数的长度,整个算法的执行效率得到进一步提高.

  2.2 模乘及模加的实现方法

  模乘采用改进的Blakley加法型算法,原理与平方-乘算法类似,核心是将模乘转化为模加实现.如通常S=(A×B)modN,A

  将B表示成二进制:

  

  

  

  由上式可知,可以像平方一乘算法一样,将模乘转化为模加实现.

  一般模加运算表示为S=(A+B)modN,观察以上模乘及模幂乘算法原理描述,可知在其调用的模加运算中,因为A

  

  因此考虑在运算中同时计算(A+B)和(A+B-N)两个结果,运算完成后通过判断加法器与减法器的进位输出(CO)与借位输出(BO).决定哪个为本次模加的正确结果.同上,A,B,N均为l位的二进制数,若CO=1,则说明(A+B)为l+1位二进制数,必大于l位的N;若CO=0,则(A+B)和N同为l位,当BO=1时(A+B)

  

  从而可以在一次运算中完成加法和求模过程,使模加的运算速度提高1倍.

  2.3 其他功能实现

  经过对多种公钥加解密算法及签名算法的分析,为提高芯片整体灵活性本设计还给出了对乘法、除法、求模、模加法逆、开方几种常用运算的支持.同样选择基于加减运算的算法实现,充分考虑算法对扫描链等已有逻辑资源的服用,设计出符合产品运算速度的面积最小化的系统.表1列出系统实现的其他功能模块采用的算法名称、详细算法及相关文献.

  

  

  

  3 设计实现

  以一个可以完成32位规格加、减、模加、增减量、移位等基本功能的ALU为基本运算单元,在扫描链逻辑的控制下,可以完成乘、除、开方、模乘、模幂乘等多种复杂运算.设计结构如图1所示.大数值运算器的外接口信号分以下三类.(1)控制:功能,规格以及源、目的指示;(2)数据:来自体RAM的源操作数,运算结果到RAM的反馈;(3)状态:运算结束,对体系相应状态寄存器的控制信号.

  

  

  

  基本运算单元(ALU):可在单周期内完成32位加减、增(减)量、模加、左右移一位功能,其核心结构如图2所示,由输入选通控制MUX-IN,32位加法器ADD,32位减法器SUB,移位逻辑SF和输出选通控制MUX-OUT组成.

  

  

  

  各功能在ALU中的具体实现方式见表2:

  功能控制逻辑:完成各个功能的控制,可分为简单功能和复杂功能两类不同的控制.

  1)简单功能:32位规格以上的加减、模加、增(减)量、移位功能.功能实现通过多周期迭代调用ALU相应功能实现,多次调用间保持进/借位传递.

  2)复杂功能:模乘、模幂乘、乘除、开方功能.根据算法原理设计状态机,根据扫描链逻辑的配合信号,通过调用简单功能实现运算.

  扫描链逻辑:当功能控制逻辑在完成复杂功能时,驱动扫描链逻辑动作.核心电路为32位的移位寄存器,扫描链逻辑可完成:待扫描数据的自动装载和切换;扫描数据高位0的自动去除,即自动找到第一个1,并给出标识信号;在使能信号的控制下从高到低自动扫描数据,给出扫描结果;扫描结束给出结束信号.

  

  

  

  4 测试及结论

  本文提出了一种用于可重组安全芯片的,面积优先、多功能、可重组的大数值运算器的实现方法设计支持的所有功能及规格如表3所示.所有模块均在ModelSim环境下通过了逻辑仿真,并在Xilinx公司的Virtex-Ⅱ系列FPGA产品XC2V6000上经过实际功能验证.

  

  

  

  使用Synopsys公司Design Compiler综合工具,在台基电(TSMC)0.25μm工艺和安全芯片要求的20Hz时钟主频下的综合结果为13 887门.设计的结果与近年的几个大数值运算器的对比见表4.可见本设计虽然运算速度稍慢,但设计规模同比大大降低,完全符合CSTU保密终端安全芯片对面积优先的设计要求,速度也在设计允许范围内.

  

关键字:实现算法  模幂乘  运算器  ALU  硬件实现  移位寄存器  公钥密码算法  实现方法

编辑:孙树宾 引用地址:http://www.eeworld.com.cn/gykz/2008/0504/article_860.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:陶瓷扬声器系统的放大器设计
下一篇:基于光电技术的脉搏测量方法

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利

推荐阅读

采用AVR单片机汇编语言实现AES加密算法及其优化

    AES是美国高级加密标准算法,将在未来几十年里代替DES在各个领域中得到广泛应用。本文在研究分析AES加密算法原理的基础上,着重说明算法的实现步骤,并结合AVR汇编语言完整地实现AES加密和解密。根据AES原理,提出几种列变化的优化算法,并根据实验结果分析和比较它们的优缺点。     随着对称密码的发展,DES数据加密标准算法由于密钥长度较小(56位),已经不适应当今分布式开放网络对数据加密安全性的要求,因此1997年NIST公开征集新的数据加密标准,即AES[1]。经过三轮的筛选,比利时Joan Daeman和Vincent Rijmen提交的Rijndael算法被提议
发表于 2018-03-19
采用AVR单片机汇编语言实现AES加密算法及其优化

采用ARM9微控制器实现上层控制算法解析方案

  引言  在很多嵌入式控制系统中,系统既要完成大量的信息采集和复杂的算法,又要实现精确的控制功能。采用运行有嵌入式Linux操作系统的ARM9微控制器完成信号采集及实现上层控制算法,并向DSP芯片发送上层算法得到控制参数,DSP芯片根据获得的参数和下层控制算法实现精确、可靠的闭环控制。  1 多机系统组成  该多机控制系统以ARM9微控制器s3c2440为核心,采用I2C总线挂载多个DSP芯片TMS320F28015作为协控制器,构成整个控制系统的核心。  1.1 S3C2440及TMS320F28015简介  Samsung公司的处理器S3C2440是内部集成了ARM公司ARM920T处理器内核的32位微控制器,资源丰富
发表于 2018-02-19
采用ARM9微控制器实现上层控制算法解析方案

单片机实现数字滤波的算法

    单片机主要作用是控制外围的器件,并实现一定的通信和数据处理。但在某些特定场合,不可避免地要用到数学运算,尽管单片机并不擅长实现算法和进行复杂的运算。下面主要是介绍如何用单片机实现数字滤波。    在单片机进行数据采集时,会遇到数据的随机误差,随机误差是由随机干扰引起的,其特点是在相同条件下测量同一量时,其大小和符号会现无规则的变化而无法预测,但多次测量的结果符合统计规律。为克服随机干扰引起的误差,硬件上可采用滤波技术,软件上可采用软件算法实现数字滤波。滤波算法往往是系统测控算法的一个重要组成部分,实时性很强。    采用数字滤波算法克服随机干扰
发表于 2017-11-18

单片机采用RLE算法实现液晶屏显示图片

由于需要用到液晶屏(320*240)显示图片,而且图片的数量比较多(好几百张),并且图片要求保存到16M的SPI FLASH里面,显然如果不处理 16M的FLASH明显是放不下去。后来同事说可以用压缩算法RLE,并且用C#给我做了个小的软件,压缩图片得到RLE压缩后的数据。点击打开链接  ---------- 详细的RLE算法可以参考次连接http://blog.csdn.net/orbit/article/details/7062218这个算法的缺点是  如果图片颜色复杂就不好,所以颜色尽量单调些。1、RLE算法小工具的使用2、我使用的RLE和上面连接的区别(改进)3、单片机里面实现的方法1、RLE算法小工具
发表于 2017-09-11
单片机采用RLE算法实现液晶屏显示图片

音频信号采集与AGC算法的DSP实现

实现方法具有实现简便、程序可移植行强、处理速度快等优点,特别是TI公司TMS320C54X系列在音频处理方面有很好的性价比,能够解决复杂的算法设计和满足系统的实时性要求,在许多领域得到广泛应用。在DSP的基础上对音频信号做AGC算法处理可以使输出电平保持在一定范围内,能够解决不同节目音频不均衡等问题。  音频信号采集  TI公司DSP芯片TMS320V  C5402具有独特的6总线哈佛结构,使其能够6条流水线同时工作,工作频率达到100MHz。利用VC5402的2个多通道缓冲串行口(McBSP0和McBSP1)来实现与AIC23的无缝连接。VC5402的多通道带缓冲的串行口在标准串口的基础上加了一个2K的缓冲区。每次串口发送数据时,CPU
发表于 2017-09-05
音频信号采集与AGC算法的DSP实现

通过这个神奇的算法,就能实现提供医疗级可穿戴产品方案

监测。CT404SG1模块基于TI AFE4404,包括AFE、MCU、G-sensor,iCareTech公司TrueSpO2/TrueHR专利算法且内置在模块中。它的尺寸仅为6mmx6mmx1.6mm功耗极低,PD/LED配置灵活,而且具有医疗级别的测量精度。大联大友尚借此还进一步推出了具备基于反射式血糖测量模块的,TI AFE4404的混合信号模块---ICT404SG1的个人健康智能手环解决方案。该方案具有连续脉率测量和连续血氧监测功能,可实现Led反射式血氧饱和度(SpO2)和脉率(PR)测量。其C+专利血氧心率算法提供了医疗级测量结果;凭借着大容量电池和超低功耗,该方案具有超长工作时间;通过蓝牙,配合云卫康手机APP
发表于 2017-04-19
通过这个神奇的算法,就能实现提供医疗级可穿戴产品方案

小广播

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2018 EEWORLD.com.cn, Inc. All rights reserved
pt type="text/javascript" src="//v3.jiathis.com/code/jia.js?uid=2113614" charset="utf-8">