对高速模幂乘算法硬件研究与开发毕业设计.docx
- 文档编号:12761761
- 上传时间:2023-06-07
- 格式:DOCX
- 页数:150
- 大小:956.27KB
对高速模幂乘算法硬件研究与开发毕业设计.docx
《对高速模幂乘算法硬件研究与开发毕业设计.docx》由会员分享,可在线阅读,更多相关《对高速模幂乘算法硬件研究与开发毕业设计.docx(150页珍藏版)》请在冰点文库上搜索。
对高速模幂乘算法硬件研究与开发毕业设计
对高速模幂乘算法硬件研究与开发毕业设计
目 录
1绪论
1.1模幂乘运算硬件IP研究进展及本文的主要工作
RSA算法是由Rivest、Shamir与Adleman三人于1978年合作开发的,并以他们的名字命名的公开密钥算法。
其加密密钥是公开的,而解密密钥是保密的。
它是基于一个非常简单的数论思想:
“将两个素数乘起来是很容易的,但是分解该乘积是非常困难的”。
因而,研究如何用硬件快速实现模幂乘运算有着重要的现实意义。
密码技术是使信息系统达到安全的核心手段,用硬件来实现密码算法在性能和物理安全方面具有一定优势。
无论是加密还是解密,发送方和接收方需要完成的运算是 me mod n,即大数模幂乘运算。
很多加密算法都用到模幂乘运算,如Diffie-Hellman密钥交换算法,ElGamal数字签名及DSA数字签名等等。
为此,开发高速的模幂乘运算硬件IP核是必要的。
1.1.1模幂乘运算研究现状与存在的问题
在现在以及将来,信息安全将在计算机和通信系统中起着重要作用。
信息安全涉及法律、管理和技术等方面,在此仅讨论技术问题。
从技术的角度讲,密码技术是使信息系统达到安全的核心手段。
信息数据加密既可用硬件来实现,也可以通过软件来完成。
虽然软件加密已经变得比较流行,但是硬件加密仍是商业和军事用途的主要选择。
采用硬件的好处之一是速度,许多加密算法采用软件实现是无效率可言的,如DES、SHA1等,需要用专门的硬件来加以实现。
之二是安全性,对运行在没有物理保护的一般的计算机上的某个加密算法,敌对方可以用各种跟踪工具修改算法而不让其他人知道。
硬件加密设备可以安全地封装起来,可以避免对关键信息的任何非法访问。
现实社会并没有处在理想社会,国家间仍然存在着政治、军事和经济斗争;企业间仍然存在着技术和商业利益竞争;人与人之间存在着个人隐私。
如果通过网络以明文方式传送不希望第三方(敌对方)知道的敏感信息,无论是通过无线还是有线传输,所传送的敏感信息很容易被第三方窃听。
若把在公共信道上传送的信息以密文的方式传输,使窃听者难以获得有用信息,则可达到安全通信的目的。
对于保护由地面通信线路、通信卫星和微波设备组成的通信网络中所传的信息,密码技术是唯一已知的实用方法。
另一方面,信息技术包括保密技术的发展也使得在极大规模上的信息交流可以秘密进行。
这些交流包括正常的有利于社会的活动,也有罪恶的计划。
它们可以在更大规模上秘密地策划、组织、实施。
而在过去,只要计划的规模一大,通讯的规模也自然会大,因而就很难保住秘密。
密码术有很长的历史。
古代人在没有高速运算设备的条件下想尽了各种方法,也包含了许多巧妙的构思。
早在公元前1900年,一个古埃及书写员就在一个铭文中使用了非标准的象形文字,这是人类最早的有记录的密码术。
其后,古代人使用的密码术有如把字母表的顺序颠倒过来、进行字母替代,或者用错后一定数目的位置的字母替代前面的字母。
其中有些密码术的构思也是十分巧妙的。
1.1.2本文的主要工作
在开发高速模幂乘芯片的历史长河中。
人们都在应用各种算法和技术去实现。
本文的主要工作是研究及验证Montgomery算法原理,通过改进过后的免减Montgomery算法,开发设计出256位、1024位、2048位规格的模幂乘运算电路,并利用仿真工作Modelsim、quartusII进行仿真验证。
在电路设计过程中,详细描述电路结构及其电路中各个模块结构之间的关系。
每个模块的端口信号,以及每个模块内部主要逻辑和运算器件。
在仿真过程中,详细例出各种规格数据的运行结果。
包括前仿真测试和FPGA测试。
1.2相关技术的发展
在计算机和通信网络飞速发展的今天,人们利用网络进行快捷、方便地交换信息,真有天涯若比邻的感觉,以至于人们把地球称为地球村。
人们通过网络谈论个人私事、或传递商务信息、或下达军事和政府指令。
它在方便人们生活的同时,也极大地提高了工作效率。
现代密码术的划时代突破,是威特菲尔德•迪菲(WhitfieldDiffie)和马丁•海尔曼(MartinHellman)有关公开密钥加密系统的构想,这是在1976年发表的。
但威特菲尔德•迪菲和马丁•海尔曼提供的MH背包算法于1984年被破译,因而失去了实际意义。
真正有生命力的公开密钥加密系统算法是由隆•里维斯特(RonaldL.Rivest)、阿迪•沙米尔(AdiShamir)和雷奥纳德•阿德尔曼(LeonardM.Adlemen)在威特菲尔德•迪菲和马丁•海尔曼的论文的启发下,在1977年发明的,这就是沿用至今的RSA算法。
它是第一个既能用于数据加密也能用于数字签名的算法。
2模幂乘硬核IP实现原理分析
2.1RSA算法基础
1)欧几里得方程
在RSA算法中,往往要在已知A、N的情况下,求B,使得(A*B)%N=1。
即相当于求解B、M都是未知数的二元一次不定方程A*B-N*M=1的最小整数解。
而针对不定方程ax-by=c的最小整数解,古今中外都进行过详尽的研究,西方有著名的欧几里德算法,即辗转相除法,中国有秦九韶的“大衍求一术”。
事实上,二元一次不定方程有整数解的充要条件是c为a、b的最大公约数。
即当c=1时,a、b必须互质。
而在RSA算法里由于公钥d为素数,素数与任何正整数互质,所以可以通过欧几里德方程来求解私钥e。
欧几里德算法是一种递归算法,比较容易理解:
例如:
11x-49y=1,求x
(a)11x-49y=149%11=5->
(b)11x-5y=111%5=1->
(c)x-5y=1
令y=0代入(c)得x=1
令x=1代入(b)得y=2
令y=2代入(a)得x=9
同理可使用递归算法求得任意ax-by=1(a、b互质)的解。
实际上通过分析归纳将递归算法转换成非递归算法就变成了大衍求一术:
x=0,y=1
WHILEa!
=0
i=y
y=x-y*a/b
x=i
i=a
a=b%a
b=i
IFx<0x=x+b
2)模幂运算
模幂运算是RSA的核心算法,最直接地决定了RSA算法的性能。
针对快速模幂运算这一课题,西方现代数学家提出了大量的解决方案,通常都是先将幂模运算转化为乘模运算。
例如求D=C**15%N,由于:
a*b%n=(a%n)*(b%n)%n,所以:
C1=C*C%N=C**2%N
C2=C1*C%N=C**3%N
C3=C2*C2%N=C**6%N
C4=C3*C%N=C**7%N
C5=C4*C4%N=C**14%N
C6=C5*C%N=C**15%N
即:
对于E=15的幂模运算可分解为6个乘模运算,归纳分析以上方法可以发现对于任意E,都可采用以下算法计算D=C**E%N:
D=1
WHILEE>=0
IFE%2=0
C=C*C%N
E=E/2
ELSE
D=D*C%N
E=E-1
RETURND
继续分析会发现,要知道E何时能整除2,并不需要反复进行减一或除二的操作,只需验证E的二进制各位是0还是1就可以了,从左至右或从右至左验证都可以,从左至右会更简洁,设E=Sum[i=0ton](E*2**i),0<=E<=1,则:
D=1
FORi=nTO0
D=D*D%N
IFE=1D=D*C%N
RETURND
这样,模幂运算就转化成了一系列的模乘运算。
3)模乘运算
对于乘模运算A*B%N,如果A、B都是1024位的大数,先计算A*B,再%N,就会产生2048位的中间结果,如果不采用动态内存分配技术就必须将大数定义中的数组空间增加一倍,这样会造成大量的浪费,因为在绝大多数情况下不会用到那额外的一倍空间,而采用动态内存分配技术会使大数存储失去连续性而使运算过程中的循环操作变得非常繁琐。
所以模乘运算的首要原则就是要避免直接计算A*B。
设A=Sum[i=0tok](A*r**i),r=0x10000000,0<=A C=A*B=Sum[i=0ton](A*B*r**i)%N 可以用一个循环来处理: C=0; FORi=nto0 C=C*r C=C+A*B RETURNC 这样将一个多位乘法转换成了一系列单位乘法和加法,由于: a*b%n=(a%n*b%n)%n a+b%n=(a%n+b%n)%n 所以,对于求C=A*B%N,我们完全可以在求C的过程中完成: C=0; FORi=nto0 C=C*r%N C=C+A*B%N RETURNC 这样产生的最大中间结果是A*B或C*r,都不超过1056位,空间代价会小得多,但是时间代价却加大了,因为求模的过程由一次变成了多次。 对于孤立的乘模运算而言这种时间换空间的交易还是值得的,但是对于反复循环的乘模运算,这种代价就无法承受,必须另寻出路。 4)Montgomery模乘 根据文献[2]证明,假设A=Sum[i=0tok](A*2**i),0<=A<=1,则: C=A*B=Sum[i=0tok](A*B*2**i) 可用循环处理为: C=0 FORiFROMkTO0 C=C*2 C=C+A*B RETURNC 若令C'=A*B*2**(-k),则: C'=Sum[i=0tok](A*B*2**(i-k)) 用循环处理即: C'=0 FORiFROM0TOk C'=C'+A*B C'=C'/2 RETURNC' 通过这一算法求A*B*2**(-k)是不精确的,因为在循环中每次除以2都可能有余数被舍弃了,但是可以通过这一算法求A*B*2**(-k)%N的精确值,方法是在对C'除2之前,让C'加上C'[0]*N。 由于在RSA中N是两个素数的积,总是奇数,所以当C'是奇数时,C'[0]=1,C'+C'[0]*N就是偶数,而当C'为偶数时C'[0]=0,C'+C'[0]*N还是偶数,这样C'/2就不会有余数被舍弃。 又因为C'+N%N=C'%N,所以在计算过程中加若干次N,并不会影响结果的正确性。 可以将算法整理如下: C'=0 FORiFROM0TOk C'=C'+A*B C'=C'+C'[0]*N C'=C'/2 IFC'>=NC'=C'-N RETURNC' 由于在RSA中A、B总是小于N,又0<=A,C'[0]<=1,所以: C'=(C'+A*B+C'[0]*N)/2 C'<(C'+2N)/2 2C' C'<2N 既然C'总是小于2N,所以求C'%N就可以很简单地在结束循环后用一次减法来完成,即在求A*B*2**(-k)%N的过程中不用反复求模,达到了我们避免做除法的目的。 当然,这一算法求得的是A*B*2**(-k)%N,而不是我们最初需要的A*B%N。 但是利用A*B*2**(-k)我们同样可以求得A**E%N。 设R=2**k%N,R'=2**(-k)%N,E=Sum[i=0ton](E*2**i): A'=A*R%N X=A' FORiFROMnTO0 X=X*X*R'%N IFE=1X=X*A'*R'%N X=X*1*R'%N RETURNX 最初: X=A*R%N, 开始循环时: X=X*X*R'%N =A*R*A*R*R'%N =A**2*R%N 反复循环之后: X=A**E*R%N 最后: X=X*1*R'%N =A**E*R*R'%N =A**E%N 如此,我们最终实现了不含除法的模幂算法,这就是著名的蒙哥马利算法,而X*Y*R'%N则被称为“蒙哥马利模乘”。 以上讨论的是蒙哥马利模乘最简单,最容易理解的二进制形式。 蒙哥马利算法的核心思想在于将求A*B%N转化为不需要反复取模的A*B*R'%N,但是利用二进制算法求1024位的A*B*R'%N,需要循环1024次之多,我么必然希望找到更有效的计算A*B*R'%N的算法。 考虑将A表示为任意的r进制: A=Sum[i=0tok](A*r**i)0<=A<=r 我们需要得到的蒙哥马利乘积为: C'=A*B*R'%NR'=r**(-k) 则以下算法只能得到C'的近似值 C'=0 FORiFROM0TOk C'=C'+A*B C'=C'/r IFC'>=NC'=C'-N RETURNC' 因为在循环中每次C'=C'/r时,都可能有余数被舍弃。 假如我们能够找到一个系数q,使得(C'+A*B+q*N)%r=0,并将算法修改为: C'=0 FORiFROM0TOk C'=C'+A*B+q*N C'=C'/r IFC'>=NC'=C'-N RETURNC' 则C'的最终返回值就是A*B*R'%N的精确值,所以关键在于求q。 由于: (C'+A*B+q*N)%r=0 ==>(C'%r+A*B%r+q*N%r)%r=0 ==>(C'[0]+A*B[0]+q*N[0])%r=0 若令N[0]*N[0]'%r=1,q=(C'[0]+A*B[0])*(r-N[0]')%r,则: (C'[0]+A*B[0]+q*N[0])%r =(C'[0]+A*B[0]-(C'[0]+A*B[0])*N[0]'*N[0])%r)%r =0 于是我们可以得出r为任何值的蒙哥马利算法: m=r-N[0]' C'=0 FORiFROM0TOk q=(C'[0]+A*B[0])*m%r C'=(C'+A*B+q*N)/r IFC'>=NC'=C'-N RETURNC' 如果令r=0x100000000,则%r和/r运算都会变得非常容易,在1024位的运算中,循环次数k不大于32,整个运算过程中最大的中间变量C'=(C'+A*B+q*N)<2*r*N<1057位,算法效率就相当高了。 唯一的额外负担是需要计算N[0]',使N[0]*N[0]'%r=1,而这一问题前面已经用欧几里德算法解决过了,而且在模幂运算转化成反复模乘运算时,N是固定值,所以N[0]'只需要计算一次,负担并不大。 2.2Montgomery算法分析 根据2.1的第4小节,可知,选择与(模数)n互素的基数R。 为计算方便,它通常是机器字长的倍数;假如选择的模数n为64bit的数,那为R可以选择为0X10000000000000000,R为65bit的数据。 并且选择R-1及n,满足0 对于0≤m FunctionM(m) λ=(mmodR)n/modR;0≤λ≤R t=(m+λn)/R ift≥nthenreturn(t-n),elsereturnt 从上面的M(m)运算可以看出,因为λn≡mnn/≡-mmodR,故t为整数;同时tR≡mmodn,得t≡mR-1modn。 由于0≤m+λn≤Rn+Rn,M(m)的运算结果范围是0≤t<2n。 2.3Montgomery算法在模幂乘IP设计中的应用 Montgomery算法只给出满足0≤m 如果所取R>n,则可直接利用Montgomery算法M(AB)计算ABR-1modn,然后做适当的调整。 但在实际的硬件实现时R< 设n B= n= 则: Z=M(A,B)≡ABR-(s+1)modn的计算算法如下: FunctionM(A,B) Z0←0 Fori=0tosdo λi=(Zi+ai×b0)×n/LmodR Zi+1=Zi+ai×B+λi×n Zi+1=Zi+1/R Endfori式(2.1) 其中n/L=n/modR。 2.4模乘算法功能实现 1)模运算基础 (1)模p运算 给定一个正整数p,任意一个整数n,一定存在等式 n=kp+r 其中k、r是整数,且0≤r 对于正整数p和整数a,b,定义如下运算: 取模运算: amodp表示a除以p的余数。 模p加法: (a+b)modp,其结果是a+b算术和除以p的余数,也就是说,(a+b)=kp+r,则(a+b)modp=r。 模p减法: (a-b)modp,其结果是a-b算术差除以p的余数。 模p乘法: (a×b)modp,其结果是a×b算术乘法除以p的余数。 可以发现,模p运算和普通的四则运算有很多类似的规律,如下表2.1: 表2.1模四则运算法则 结合率 ((a+b)modp+c)modp=(a+(b+c)modp)modp ((a*b)modp*c)modp=(a*(b*c)modp)modp 交换率 (a+b)modp=(b+a)modp (a×b)modp=(b×a)modp 分配率 ((a+b)modp×c)modp=((a×c)modp+(b×c)modp)modp 简单的证明其中第一个公式: ((a+b)modp+c)modp=(a+(b+c)modp)modp 假设 a=k1*p+r1 b=k2*p+r2 c=k3*p+r3 a+b=(k1+k2)p+(r1+r2) 如果(r1+r2)>=p,则 (a+b)modp=(r1+r2)-p 否则 (a+b)modp=(r1+r2) 再和c进行模p和运算,得到 结果为r1+r2+r3的算术和除以p的余数。 对右侧进行计算可以得到同样的结果,得证。 (2)模P相等 如果两个数a、b满足amodp=bmodp,则称他们模p相等,记做a≡bmodp可以证明,此时a、b满足a=kp+b,其中k是某个整数。 对于模p相等和模p乘法来说,有一个和四则运算中迥然不同得规则。 在四则运算中,如果c是一个非0整数,则 ac=bc可以得出a=b但是在模p运算中,这种关系不存在,例如: (3x3)mod9=0 (6x3)mod9=0 因为: 3mod9=3 6mod9=6 根据定理(消去律): 如果gcd(c,p)=1,则ac≡bcmodp可以推出a≡bmodp 证明: 因为ac≡bcmodp 所以ac=bc+kp,也就是c(a-b)=kp 因为c和p没有除1以外的公因子,因此上式要成立必须满足下面两个条件中的一个 1)c能整除k 2)a=b 如果2不成立,则c|kp 因为c和p没有公因子,因此显然c|k,所以k=ck' 因此c(a-b)kp可以表示为c(a-b)=ck'p 因此a-b=k'p,得出a≡bmodp 如果a=b,则a≡bmodp成立,得证。 (3)欧拉定理 对于互质的整数a和n,有a^φ(n)≡1modn 证明: 首先证明下面这个命题: 对于集合Zn={x^1,x^2,...,x^φ(n)},考虑集合 S={ax^1modn,ax^2modn,...,ax^φ(n)modn} 则S=Zn 1)由于a,n互质,x^i也与n互质,则ax^i也一定于p互质,因此 任意x^i,ax^imodn必然是Zn的一个元素 2)对于Zn中两个元素x^i和x^j,如果x^i≠x^j 则ax^imodn≠ax^imodn,这个由a、p互质和消去律可以得出。 所以,很明显,S=Zn 既然这样,那么 (ax^1×ax^2×...×ax^φ(n))modn =(ax^1modn×ax^2modn×...×ax^φ(nmodn)modn =(x^1×x^2×...×x^φ(n)modn 考虑上面等式左边和右边 左边等于(a^φ(n)×(x^1×x^2×...×x^φ(n))modn)modn 右边等于x^1×x^2×...×x^φ(n))modn 而x^1×x^2×...×x^φ(n))modn和p互质 根据消去律,可以从等式两边约去,就得到: a^φ(n)≡1modn推论: 对于互质的数a、n,满足a^(φ(n)+1)≡amodn (4)费马定理 a是不能被质数p整除的正整数,则有a≡1modp 由于φ(p)=p-1,代入欧拉定理即可证明。 同样有推论: 对于不能被质数p整除的正整数a,有a≡amodp 2)模乘算法功能实现 设求B=M1*M2modn(M、n均为整数) (1)B1=M1*M2*R-1modn,(Montgomery算法实现) (2)B=B1*R2*R-1modn 根据本2.4节中[1]中的模运算结合率,可由 ((a*b)modp*c)modp=(a*(b*c)modp)modp, B=(M1*M2*R-1modn)*R2*R-1modn得到 B=M1*M2*R-1*R2*R-1modn=M1*M2modn 2.5模幂乘算法功能实现 设求A=Memodn(M、e、n均为整数,e>=3) 1)设s=1,求B=M*Mmodn 2)求A1=B*Mmodn,s=s-1, 3)判断s=e? 若s=e,则完成运算,否则跳到2步执行 图2.1模幂乘算法功能实现图 状态说明: 第0状态: 初始状态,等待模幂乘MMC_E使能信号 第2状态: 执行模乘运算B1=M1*M2*R-1modn;当模乘运算结束后,信号MMUL_OV有效,跳至状态3 第3状态: 将运算结果B1存入原M1所存的存储器中;并对信号DD进行判断,若DD为0,则跳至状态4,若DD为1,则跳至状态6 第4状态: 将R2存入原M2所存的存储器中;跳至状态2 第5状态: 将底数M存入原M2所
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高速 模幂乘 算法 硬件 研究 开发 毕业设计