《RSA公开密钥加密技术毕业论文》由会员分享，可在线阅读，更多相关《RSA公开密钥加密技术毕业论文（103页珍藏版）》请在金锄头文库上搜索。
1、. . .RSA公开密钥加密技术毕业论文目录摘要IAbstractII引言11 绪论21.1 模幂乘运算硬件IP研究进展及本文的主要工作21.1.1 模幂乘运算研究现状与存在的问题21.1.2 本文的主要工作31.2 相关技术的发展32 模幂乘硬核IP实现原理分析52.1 RSA算法基础52.2 Montgomery算法分析112.3 Montgomery算法在模幂乘IP设计中的应用112.4 模乘算法功能实现122.5 模幂乘算法功能实现153 模幂乘IP结构分析173.1 模幂乘主控模块实现173.2 模乘模块实现183.2.1 模乘的顶层模块183.2.2 模乘运算模块203.2.3 模
2、乘控制模块233.2.4 模乘存储模块244 前仿测试及FPGA测试的实验过程详述274.1 前仿测试274.1.1 测试说明274.1.2 预期结果与实际结果对比274.1.3 小结304.2 FPGA测试304.2.1 FPGA测试环境简介304.2.2 FPGA环境搭建过程315.1.1 测试准备及结果记录335.1.2 小结36结论38参 考 文 献39致谢42附录 高速模幂乘实现编码VHD描述43.参考资料.1 绪论1.1 模幂乘运算硬件IP研究进展及本文的主要工作RSA算法是由Rivest、Shamir与Adleman三人于1978年合作开发的，并以他们的名字命名的公开密钥算法。其
3、加密密钥是公开的，而解密密钥是的。它是基于一个非常简单的数论思想：“将两个素数乘起来是很容易的，但是分解该乘积是非常困难的”。因而，研究如何用硬件快速实现模幂乘运算有着重要的现实意义。密码技术是使信息系统达到安全的核心手段，用硬件来实现密码算法在性能和物理安全方面具有一定优势。无论是加密还是解密，发送方和接收方需要完成的运算是memodn，即大数模幂乘运算。很多加密算法都用到模幂乘运算，如Diffie-Hellman密钥交换算法，ElGamal数字签名及DSA数字签名等等。为此，开发高速的模幂乘运算硬件IP核是必要的。1.1.1 模幂乘运算研究现状与存在的问题在现在以及将来，信息安全将在计算机
4、和通信系统中起着重要作用。信息安全涉及法律、管理和技术等方面，在此仅讨论技术问题。从技术的角度讲，密码技术是使信息系统达到安全的核心手段。信息数据加密既可用硬件来实现，也可以通过软件来完成。虽然软件加密已经变得比较流行，但是硬件加密仍是商业和军事用途的主要选择。采用硬件的好处之一是速度，许多加密算法采用软件实现是无效率可言的，如DES、SHA1等，需要用专门的硬件来加以实现。之二是安全性，对运行在没有物理保护的一般的计算机上的某个加密算法，敌对方可以用各种跟踪工具修改算法而不让其他人知道。硬件加密设备可以安全地封装起来，可以避免对关键信息的任何非法访问。现实社会并没有处在理想社会，国家间仍然存
5、在着政治、军事和经济斗争；企业间仍然存在着技术和商业利益竞争；人与人之间存在着个人隐私。如果通过网络以明文方式传送不希望第三方（敌对方）知道的敏感信息，无论是通过无线还是有线传输，所传送的敏感信息很容易被第三方窃听。若把在公共信道上传送的信息以密文的方式传输，使窃听者难以获得有用信息，则可达到安全通信的目的。对于保护由地面通信线路、通信卫星和微波设备组成的通信网络中所传的信息，密码技术是唯一已知的实用方法。另一方面，信息技术包括技术的发展也使得在极大规模上的信息交流可以秘密进行。这些交流包括正常的有利于社会的活动，也有罪恶的计划。它们可以在更大规模上秘密地策划、组织、实施。而在过去，只要计划的
6、规模一大，通讯的规模也自然会大，因而就很难保住秘密。密码术有很长的历史。古代人在没有高速运算设备的条件下想尽了各种方法，也包含了许多巧妙的构思。早在公元前1900年，一个古埃及书写员就在一个铭文中使用了非标准的象形文字，这是人类最早的有记录的密码术。其后，古代人使用的密码术有如把字母表的顺序颠倒过来、进行字母替代，或者用错后一定数目的位置的字母替代前面的字母。其中有些密码术的构思也是十分巧妙的。1.1.2 本文的主要工作在开发高速模幂乘芯片的历史长河中。人们都在应用各种算法和技术去实现。本文的主要工作是研究及验证Montgomery算法原理，通过改进过后的免减Montgomery算法，开发设计
7、出256位、1024位、2048位规格的模幂乘运算电路，并利用仿真工作Modelsim、quartusII进行仿真验证。在电路设计过程中，详细描述电路结构及其电路中各个模块结构之间的关系。每个模块的端口信号，以及每个模块部主要逻辑和运算器件。在仿真过程中，详细例出各种规格数据的运行结果。包括前仿真测试和FPGA测试。1.2 相关技术的发展在计算机和通信网络飞速发展的今天，人们利用网络进行快捷、方便地交换信息，真有天涯若比邻的感觉，以至于人们把地球称为地球村。人们通过网络谈论个人私事、或传递商务信息、或下达军事和政府指令。它在方便人们生活的同时，也极大地提高了工作效率。现代密码术的划时代突破，是
8、威特菲尔德迪菲(Whitfield Diffie)和马丁海尔曼(Martin Hellman)有关公开密钥加密系统的构想，这是在1976年发表的。但威特菲尔德迪菲和马丁海尔曼提供的MH背包算法于1984年被破译，因而失去了实际意义。真正有生命力的公开密钥加密系统算法是由隆里维斯特(Ronald L. Rivest)、阿迪沙米尔(Adi Shamir)和雷奥纳德阿德尔曼(Leonard M.Adlemen)在威特菲尔德迪菲和马丁海尔曼的论文的启发下，在1977年发明的，这就是沿用至今的RSA算法。它是第一个既能用于数据加密也能用于数字签名的算法。2 模幂乘硬核IP实现原理分析2.1 RSA算法基
9、础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） 11
10、 x - 49 y = 1 49%11=5 -（b） 11 x - 5 y = 1 11%5 =1 -（c） x - 5 y = 1令y=0 代入（c）得x=1令x=1 代入（b）得y=2令y=2 代入（a）得x=9同理可使用递归算法求得任意 ax-by=1（a、b互质）的解。实际上通过分析归纳将递归算法转换成非递归算法就变成了大衍求一术：x=0,y=1WHILE a!=0i=yy=x-y*a/bx=ii=aa=b%ab=iIF x=0IF E%2=0C=C*C % NE=E/2ELSED=D*C % NE=E-1RETURN D继续分析会发现，要知道E 何时能整除 2，并不需要反复进行减一或
11、除二的操作，只需验证E 的二进制各位是0 还是1 就可以了，从左至右或从右至左验证都可以，从左至右会更简洁，设E=Sumi=0 to n(E*2*i)，0=E=1，则：D=1FOR i=n TO 0D=D*D % NIF E=1 D=D*C % NRETURN D这样，模幂运算就转化成了一系列的模乘运算。3) 模乘运算对于乘模运算 A*B%N，如果A、B都是1024位的大数，先计算A*B，再% N，就会产生2048位的中间结果，如果不采用动态存分配技术就必须将大数定义中的数组空间增加一倍，这样会造成大量的浪费，因为在绝大多数情况下不会用到那额外的一倍空间，而采用动态存分配技术会使大数存储失去连
12、续性而使运算过程中的循环操作变得非常繁琐。所以模乘运算的首要原则就是要避免直接计算A*B。设A=Sumi=0 to k(A*r*i)，r=0x10000000，0=Ar，则：C = A*B = Sumi=0 to n(A*B*r*i) %N可以用一个循环来处理：C=0;FOR i=n to 0C=C*rC=C+A*BRETURN C这样将一个多位乘法转换成了一系列单位乘法和加法，由于：a*b %n = (a%n * b%n) %na+b %n = (a%n + b%n) %n所以，对于求C=A*B %N，我们完全可以在求C的过程中完成：C=0;FOR i=n to 0C=C*r %NC=C+A
13、*B %NRETURN C这样产生的最大中间结果是A*B 或C*r，都不超过1056位，空间代价会小得多，但是时间代价却加大了，因为求模的过程由一次变成了多次。对于孤立的乘模运算而言这种时间换空间的交易还是值得的，但是对于反复循环的乘模运算，这种代价就无法承受，必须另寻出路。4) Montgomery模乘根据文献2证明，假设A=Sumi=0 to k(A*2*i)，0=A=1，则：C= A*B = Sumi=0 to k(A*B*2*i)可用循环处理为：C=0FOR i FROM k TO 0C=C*2C=C+A*BRETURN C若令 C= A*B*2*(-k)，则：C= Sumi=0 to
14、 k(A*B*2*(i-k)用循环处理即：C=0FOR i FROM 0 TO kC=C+A*BC=C/2RETURN C通过这一算法求A*B*2*(-k)是不精确的，因为在循环中每次除以2都可能有余数被舍弃了，但是可以通过这一算法求A*B*2*(-k) %N的精确值，方法是在对C除2之前，让C加上C0*N。由于在RSA中N是两个素数的积，总是奇数，所以当C是奇数时，C0=1，C+C0*N 就是偶数，而当C为偶数时C0=0，C+C0*N还是偶数，这样C/2 就不会有余数被舍弃。又因为C+N %N = C %N，所以在计算过程中加若干次N，并不会影响结果的正确性。可以将算法整理如下：C=0FOR i FROM 0 TO k
