为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

基于DSP的数据加密技术综述

2019-01-14 19页 doc 64KB 15阅读

用户头像

is_266065

暂无简介

举报
基于DSP的数据加密技术综述基于DSP的数据加密技术综述 学号:                    专业:                    姓名:                    日期:    2014/6/18      目录 摘要:    3 Abstract:    3 一、引言    4 二、软件算法    5 2.1、RSA加密算法描述    5 2.2、Montgomery 模乘算法    6 2.3、实现RSA快速加密    6 2.3.1、 乘幂运算的快速实现    6 2.4、Montgomery 模乘算法改进...
基于DSP的数据加密技术综述
基于DSP的数据加密技术综述 学号:                    专业:                    姓名:                    日期:    2014/6/18      目录 摘要:    3 Abstract:    3 一、引言    4 二、软件算法    5 2.1、RSA加密算法描述    5 2.2、Montgomery 模乘算法    6 2.3、实现RSA快速加密    6 2.3.1、 乘幂运算的快速实现    6 2.4、Montgomery 模乘算法改进的RSA算法实现    7 2.4.1、改进的模乘算法    7 2.4.2、2 个CSA 加法器的Montgomery 模乘算法    7 2.4.3、 实现RSA 加密系统的结构图    9 三、硬件加密    10 3.1、 长整数模运算的快速实现    10 3.2、 TMS320C54X芯片的特点,及编程过程中应注意的地方    11 四、参考文献    12 五、课程总结    12 摘要: RSA是最早提出的公钥密码体制,其原理简单,安全性好,但由于其密钥较长才能保证一定的安全性,因而计算量大,如果用软件加密其速度太慢,用硬件实现可以大大提高RSA的速度。与此同时应用Montgomery 模乘算法来提高RSA的速度。在Montgomery 模乘算法改进的基础上, 提出了一种实现Montgomery 模乘算法的结构,该结构只需使用一个CSA (carry save adder) 加法器. 与目前使用两个CSA 加法器的模乘算法相比, 所提出的算法加快了RSA 加密处理器的实现, 并提高了整个加密系统的时间效率。DSP芯片系列提供了一种专用的乘法器,其完成一次乘法的时间只要一个周期,这使实现RSA的速度加快,怎样实现呢?那么就介绍一种适合DSP TMS320C54X 芯片,用汇编语言实现的一种快速的RSA,并实现了良好的加速算法。 Abstract: RSA is the earliest public key algorithm. Its theory is very simple and its security is very high,but it must use a long key to assure its security, so its computation is very large. Using hardware to implement data encryption is more faster than using softer. And use the modified Montgomery modular multiplication, Based on the modified Montgomery modular multiplication this paper proposed a new arch itec2tu re of u sing CSA (carry save adder ) for the implement at ion of Montgomery modular multiplication. Compared with the present algorithm using two CSA modular multiplication, the proposed algorithm only uses one CSA , so it speeds up the imp lamentation of RSA cryptoprocesser, and also imp roves the time .efficiency. There is a particular multiplier, which can compute a multiplication at a cycle, this means it can make RSA faster. How can it be done? then a kind of the design of fast RSA implementation base on DSP TMS320C54X chipset ,using assembler language is introduced. As a result, it gets a high speed. Key words: RSA; DSP; Fast Implementation; Modular Arithmetic Montgomery modular multiplication algorithm; CSA 一、引言 随着数字通信和电子商务,网络技术的高速发展和普及, 网络信息安全成为当今一个重要话题. 对数据安全的需求日益迫切,如何保证网络上信息安全成为一项重要的研究课题,而数据加密是保护信息的一种重要方法 为了保证信息安全,公开密钥体制得到广泛的认可, 而RSA 是其中一个重要的公开加密系统. 由于在RSA 加密算法中, 主要是模指数运算, 而模指数运算重复使用了模乘算法, 所以模乘算法是实现RSA 加密系统的关键所在, 如何提高模乘算法的效率, 影响到整个RSA 加密系统的工作效率. 而Montgomery 模乘算法在计算指数运算上效率较高, 而且易于实现.在RSA 加密处理器的硬件实现上, 有两种比较好的加密结构: 一种是基于硬件资源合理利用上的L2R ( left to right) 二进位方法; 一种是在实现速度较快基础上, 所需硬件资源较大的R2L ( right to left ) 二进位方法[ 1 ]. 本文在Montgomery 模乘算法优化的基础上, 使用L 2R 二进位方法, 并对Mon t2gom ery 模乘使用CSA 加法器[ 2 ]改进前后, RSA 加密处理器在处理时间上作相应的和比较. 但单纯由软件来加密虽然升级方便,但安全性和速度都与经过特殊设计的硬件加密无法相比,因此采用专用的芯片的PC安全卡,即利用专用的汇编语言实现算法并装载到卡上,再在专用的芯片上运行是一种性能高且成本低的解决。 TI公司推出的TMS320C54X系列的DSP具有性能适中,价格低廉和产品成熟等特点,并且其乘法指令执行快,并行性高,较适合于加密算法,因而采用TMS320C54X DSP作为PC安全卡的主CPU 二、软件算法 2.1、RSA加密算法描述 RSA 公钥算法是由MIT 的Rivest、Shamir 和Adleman 在1978 年提出来的。RSA 方案是唯一被广泛接受并实现的通用公开密钥密码算法,目前已成为公钥密码的国际。该算法的数学基础是初等数论中的欧拉( Euler) 定理,其安全性建立在大整数因子分解的困难性之上。RSA 作为公钥密码体制,利用了单向陷门函数的原理,如图1 所示。 图(1) RSA 算法归纳如下: ( 1) 选择2 个大素数p、q,为了保证安全,通常要求每个都 图1 RSA 利用单向陷门函数原理大于10100 ( 即超过100 位的十进制) ; ( 2) 计算n = p·q 和φ( n) = ( p - 1) ·( q - 1) ; ( 3) 选择一个与φ( n) 互素的数,令其为e; ( 4) 找到1 个d,使其满足 d = e-1 modφ( n) ; ( 5) 选好这些参数后,将明文划分成块,使得每个明文报文块长度满足M < n。加密M 时,计算: C = Me mod n        ( 1) 解密时计算: M = Cd mod n        ( 2) 由于模运算的对称性,可以证明,在确定的范围内,加密和解密函数是互逆的。为实现加密,需要公开{ e,n} ,为实现解密需要{ d,n} 。 2.2、Montgomery 模乘算法 RSA 加密系统主要是进行模指数运算. 假设N是2 个大的素数p 和q 的乘积, 而公开密钥e 可以根据e = d -1 mod (p - 1) (q - 1) 通过欧几里得乘法 逆元算法获得.加密时: ①明文M , 公开密钥(e, N ) (0< M
示法,设E为k位的,E=(Ek-1Ek-2………E0),将r位作为一组,令m=2r,算法如下: 1. 求出M2,M3,。。。。。。。Mm-1mod N 2. 令C:=1 3. 对于i=t-1,t-2,………..1,0 重复计算: (a) C:=Cm mod N(实际的运算是通过r次C:=C2mod N次运算得到的) (b) 若Ei≠0 则C:=C×MEi mod N 所得C即为所求 由上面的算法可看出平均计算量为: (1)预算M2。。。。。。。Mm-1: m-2=2r-2 (2)平方的次数: k (3)3(b)的执行乘的次数:(2r-1)×k/(2r×r)+2r-2 我们可以看出这三部分构成了该算法的主要运算量,只要能减少任一部分,则计算乘幂的时间还可以减少,注意到平方的计算次数只与E的位数k有关,没法再减少其计算量,下面引入的适应性M—ARY算法即固定性非零窗口滑动窗口算法(CLNW)就是在M—ARY基础上的改进算法,其目的是减少其他两个部分的计算量 2.4、Montgomery 模乘算法改进的RSA算法实现 2.4.1、改进的模乘算法 在Mon tgom ery 算法基础上, RSA 整个加密系统包括匹配、模指数和再匹配三部分。见下图 图(2) 加密系统 2.4.2、2 个CSA 加法器的Montgomery 模乘算法 1)目前使用2个CSA加法器的Mountgomery 模乘算法 : 算法1: 输入: A ,B ,N (modulus) 输出: P =(AB 2-n) mod N n: number of bits in A A i: ith bit of A S 0: the lowest bit of S 步骤1: P = 0; S = 0; C = 0; 步骤2: for i= 0 to n- 1 do 2a: (S , C) = S + C+ A iB 2b: (S , C) = S + C+ S 0N 2c: S = S ? 2; C= C?2 步骤3: P = S + C 步骤4: if (P > N ) P = P - N 步骤5: return (P ) 结果为REDC(A ,B ) = AB 2-(n+2)mod N . 2) 一个CSA 的Mon tgomery 模乘算法 由于目前采用的改进Mon tgom ery 模乘算法实现时, 使用了2 个CSA 加法器, 虽然每个加法可以在一个时钟周期完成, 但是随着加密数据长度n 的增加, 所需加法单元也会越来越大. 例如n = 1 024 bit 时, 也需要2 048个加法单元, 因此, 所使用的硬件资源仍然很大. 为了节省硬件资源, 同时加快模乘 算法, 本文对模乘算法做了相应的改进 算法2 输入: A ,B ,N (modulus) 输出: P = (A B 2-n) mod N n: m umber of bit s in A A i: ith bit of A S 0: the lowest bit of S C0: the lowest bit of C B 0: the lowest bit of B R : precomputed value of (B + N ) 步骤1: P = 0; S = 0; C= 0 步骤2 : for i= 0 to n- 1 do 2a: if (S0= C0) and not Ai then: L = 0 if (S 0≠C0) and notAi then: L = N if no t (S0 x or C0 x or B0) and A i then: L = B if (S0 x or C0 x or B0 ) and Ai then: L = R 2b: (S , C) = S + C+ L 2c: S = S ? 2; C= C?2 步骤3: P = S + C 步骤4: if (P > N ) P = P - N 步骤5: return (P ) 结果为REDC (A ,B ) = AB 2-(n+2) mod N . 算法一    图(3)      算法二 2.4.3、 实现RSA 加密系统的结构图 由于CPA 加法器是一种进位传播加法器, 如果进行高比特的加法, 不仅需要较多的硬件资源, 而且会有很大的时延, 因此不利于系统时钟频率的提高.为了保证整个加法能够在一个时钟周期完成, 提高Montgomery 模乘算法的时间和工作效率, 需使用CSA 加法器替代模乘算法中的CPA 加法器。在CPA 加法中, 执行1 024 bit 的加法需要32个时钟, 为了适应该加法结构, 输入的1 024 bit 寄 存器包括32 bit 的寄存器.使用32 bit 的CPA 加法器和移位寄存器, 减少了硬件资源. 同时, 移位寄存器也使32 bit I?O 接口成为可能. 基于L 2R 的实现Montgomery 算法的RSA 处理器的结构框架图如图4所示. 图(4) 三、硬件加密 3.1、 长整数模运算的快速实现 通常的长整数模运算都是用来完成的,因为PC机的加减法指令的执行速度比乘除法要快得多,利用加减法可以使指令的执行速度大幅度的提高,但对于C54X则不同,C54X芯片中的17bit*17bit专用乘法器使得其乘法指令的执行只需一个时钟周期,与加减指令的速度完全相同,这样就要考虑更多地用乘法来完成模运算 假设要做运算 R=T mod N      (3.1.1) 其中N为k位的长整数,T为2k位的长整数,设字长为m,则N共有n=k/m个字,T有2n个字,同时记X=2m 将T写为表达式:T=T1×2k+T0  (3.1.2) 并将T1表示为: T1=tn-1Xn-1+tn-2Xn-2+……….+t0      (3.1.3) 将式(3.1.2)和(3.1.3)代入式(3.1.1)即得 R=(tn-1×(X2n-1 mod N)+tn-2×(X2n-2mod N)+…….+t0×(Xnmod N)+T0)mod N      (3.1.4) 从(3.1.4)式可看出,可以预求n个Xn+I modN的值,分别记为: r0=Xnmod N r1=Xn+1mod N …………rn-1=X2n-1mod N 有R1=tn-1×rn-1+tn-2×rn-2+……..+t0×r0+T0          (3.1.5) 执行完式(3.1.5)之后,R1的k比特以上部分(记为R11)的位数不会超过  m+㏒n,对于C54X,m=16,只要选择的k<16*28=4096,R11的位数就不会超过24,这样,可以选择X=28重复式(3.1.5)的操作,这时的预表中只要如下三项即可: r10=2kmod N r11=2k+8mod N r12=2k+16mod N 记R11=(r12×X2+r11×X+r10) (3.1.6) 则可执行操作:      R2=r12×r12+r11×r11+r10×r10 (3.1.7) 执行完(3.1.7)后,R2的k比特位以上的部分(记为R21,低k比特的部分记为R20)的最大长度为10比特,这是对乘/累加的利用已达到最大限度,接下来必须进行加减法的操作,构造预表如下:r20=2kmod N r21=2k+1mod N ……..r29=2k+9mod N 这时可以执行如下操作: for I=1 to 10 do if R2i的第i位是1 then begin R20=R20+r2i If (R20>N) then R20=R20-N End 这样得到的结果R20就是最后的结果R 由上面的算法可见,整个模运算是由三步组成的,其中前两步是将加减法转换为乘/累加来做的,第三步的加法循环只有10次,这充分利用了C54X芯片的乘法优势,使模运算的速度有了很大的提高。完成一次模运算的时间为用减法完成模运算时间的38.5℅. 3.2、 TMS320C54X芯片的特点,及编程过程中应注意的地方 (1)芯片共有3条数据总线,1条程序总线,4条相应的地址总线,多条数据总线可同时读取多个数据,使得C54X具有功能强大的指令集。很多指令的效率很高。 (2)8个辅助寄存器使得程序编制更灵活。 (3)有2个40-bit累加器,1个17-bit×17-bit乘法器,可很方便的进行乘/累加运算,另外单指令周期的乘法指令使模运幂运算的速度大幅度提高。 (4)320C54X芯片采用了六级流水线机制,但没有解决流水线相关的问题,因此在编程时必须注意指令的连接关系,必要时要加上空操作,合理调配指令顺序,尽量减少指令的相关性,可大大提高程序的运行速度。 (5)许多指令都分为有符号数和无符号数两种,应根据所用数的类型选用指令。 (6)TMS32054X芯片的地址形成方式比较特殊,16位地址的高9位由DP给出,低7位由指令给出,这样使得直接寻址的指令的执行速度比较快,但必须先将DP设置为正确的值。因此在程序调试过程中,数据的存储位置尚未完全确定,最好避免利用DP寻址的指令,防止由于存储位置的变化引起程序运行错误。 四、参考文献 [1] 卢开澄. 计算机密码学 [M].北京:清华大学出版社,1998.81-96 [2] 周建江,戴明桢,等. TMS320C54X DSP 结构、原理及应用 [M].北京:北京航空航天大学出版社,2001.1-60 [3]阮飞. 当前我国信息安全领域面临的重大问题. 信息安全与通信保密, 2003( 12) [4]佟晓筠,王翥,郭长勇,等. 基于RSA 等算法软件加密技术的研究 与实现.微处理机,2003( 6) : [5]何彩燕,吴红.公钥制RSA 算法应用中要注意的几个问题. 现代计算机, 2004,178( 5) : [6] 尹勇,欧光军,关荣锋. DSP 集成开发环境CCS 开发指南. 北京: 北 京航空航天大学出版社,2003 五、课程总结 1、第一章 离散时间信号与系统 数字信号是由模拟信号经过采样得到离散时间信号,在经过量化和编码最终得到的。在采样的过程中,他的采样频率必须高于两倍信号的最高频率,则整个连续信号就可以完全用它的采样值来代表,而不会丢掉任何信息。任何一个时间离散信号都可以用单位脉冲序列信号及其移位的线性组合来描述他。单位阶跃信号和他的移位的线性组合可以用来描述一个离散时间的持续时间。 判断一个系统是否为线性系统: Linear system :  齐次性与叠加性 即      y1(n)=T[x1(n)] ,y2(n)=T[x2(n)] y (n)=T[ax1(n) +bx2(n)] = ay1(n) +by2(n) *加权信号和的响应=响应的加权和。 Time-invariant:  时不变特性  即    y(n-n0)=T[x(n-n0)] 所有 存在一个最小的正整数 ,满足: ,则称序列 是周期序列,周期为 。两个序列中只要有一个是无限长序列,则卷积之后是无限长序列,卷积是线性运算,长序列可以分成短序列再进行卷积,但必须看清起点在哪里。Z变换是分析离散信号与系统的一种有力的数学工具,他类似于拉普拉斯变换之对连续信号与系统。在离散时间系统分析中,从对系统数学模型的求解方法来讲,基本可以分为时域方法和变换域方法两类,时域法是直接分析时间变量的函数研究离散时间系统的时域特性。 第二章  离散傅里叶变换 离散傅里叶变换建立了有限长序列与离散频谱之间的联系,他在理论上具有重大意义。DFT隐含有周期性,周期为N, 有限N长序列x(n)的N点离散傅里叶变换(DFT)X(k)也可以定义为x(n)的周期延拓序列X((n))N的离散傅里叶级数(DFS) 的主值序列。周期序列的主周期序列指把周期序列截取主周期0——N-1得到的有限长序列。 循环卷积的计算方法,循环卷积与线性卷积的关系,用DFT计算线性卷积的方法。 设x1(n)( 0≤ n≤M-1),x2(n)(0 ≤n ≤N-1) 循环卷积:L取M、N中较长的一个(设M>N,则L=M)。较短的一个需要补0至L(两个序列的长度要求相等)。 循环卷积可以用DFT(FFT)实现; 用循环卷积实现线性卷积:L≥M+N-1 若不满足这个条件,则只在N-1 ≤n ≤M-1范围内两者相等。 DFS DFT 线性 线性 序列移位 循环移位 共轭对称性 共轭对称性 周期卷积 循环卷积     圆周卷积和线性卷积的对比 圆周卷积 线性卷积 针对FFT引出的一种表示方法 信号通过线性系统时,信号输出等于输入与系统单位冲激响应的卷积 两序列长度必须相等,不等时按要求补足零值点 两序列长度可以不等 如x1(n)为 N1点,x2(n)为 N2点 卷积结果长度与两信号长度相等皆为N 卷积结果长度为N=N1+N2-1     第三章 快速傅里叶变换 DFT在数字信号处理起着非常重要的作用,而这是与DFT存在着高效算法,即FFT。他不是一种新型变换,而是减少DFT计算量的一些高效算法。 FFT的运算量的计算,与DFT运算量的比较 N点的FFT的运算量为 复乘: CM=(N/2)M=(N/2) log2 N 复加: CA =N M=N log2 N N点的DFT的运算量为 复乘: CM =N2 复加: CA =N(N-1) 第四章 数字滤波网络 数字滤波器的功能本质上是将一组输入数字序列通过一定的运算后转变为另一组输出数字序列,其结构表示需要采用加法器,乘法器,延时器等。IIR滤波器的结构和信号流图:直接型;级联型;并联型。FIR数字滤波器的结构和信号流图:直接型;快速卷积型、频率采样型。FIR数字滤波器:非递归结构,无反馈,但在频率采样结构等某些结构中也包含有反馈的递归部分。级联型结构简化了滤波器发的实现方式,采用一些二阶节,通过适当的系数变换就可以实现整个系统,并且各级联形式子系统的零,极点就是整个系统的零,极点,所以调整子系统系数可以直接控制系统的传输特征。 第五章 滤波器设计原理 滤波器是一种具有一定传输特性的信号处理装置。从广义上讲,凡是有能力进行信号处理的装置都可以成为滤波器。但一般所讲的滤波器是一种选频器件,他对某些频率的信号衰减很小,允许信号通过,而对其他不需要的衰减很大,尽量阻止这些信号的通过。比较成熟的几种滤波器:Butterworth滤波器,Chebyshev滤波器。对滤波器的技术要求: 中心频率,通带带宽,通带插入损耗,通带波动,阻带衰减。 第六章 IIR 数字滤波器的设计 第八章 数字信号处理的实现及应用 自从数字信号处理器(Digital Signal Processor)问世以来,由于它具有高速、灵活、可编程、低功耗和便于接口等特点,已在图形、图像处理,语音、语言处理,通用信号处理,测量分析,通信等领域发挥越来越重要的作用。随着技术成本的降低,控制界已对此产生浓厚兴趣,已在不少场合得到成功应用。DSP在多媒体通信中的应用,多媒体包括文字、语言、图像、图形和数据等媒体。多媒体信息中绝大部分是视频数据和音频数据,儿数字化的音、视频数据的数据量是非常庞大的,只有采用先进的压缩编码算法对其进行压缩,节省储存空间,提高通信线路的传输效率,才能使高速的多媒体通信系统成为可能。作为处理数字信号的DSP技术,为人们快速的获取、分析和利用有效信息奠定了基础,必将进一步得到社会各界的普遍关注,由此可见,DSP技术在发展经济、推动社会进步方面的重要作用,是十分明显的。相信在不久的将来,随着制造技术和新材料技术的不断发展DSP技术将会出现一个飞跃,达到一个新的水平。
/
本文档为【基于DSP的数据加密技术综述】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索