RSA公开密钥加密技术论文.doc

RSA公开密钥加密技术毕业论文目　　录 摘　　要 I Abstract II 引　　言 1 1 绪论 2 1.1 模幂乘运算硬件IP研究进展及本文的主要工作 2 1.1.1 模幂乘运算研究现状与存在的问题 2 1.1.2 本文的主要工作 3 1.2 相关技术的发展 3 2 模幂乘硬核IP实现原理分析 5 2.1 RSA算法基础 5 2.2 Montgomery算法分析 11 2.3 Montgomery算法在模幂乘IP设计中的应用 11 2.4 模乘算法功能实现 12 2.5 模幂乘算法功能实现 15 3 模幂乘IP结构分析 17 3.1 模幂乘主控模块实现 17 3.2 模乘模块实现 18 3.2.1 模乘的顶层模块 18 3.2.2 模乘运算模块 20 3.2.3 模乘控制模块 23 3.2.4 模乘存储模块 24 4 前仿测试及FPGA测试的实验过程详述 27 4.1 前仿测试 27 4.1.1 测试说明 27 4.1.2 预期结果与实际结果对比 27 4.1.3 小结 30 4.2 FPGA测试 30 4.2.1 FPGA测试环境简介 30 4.2.2 FPGA环境搭建过程 31 5.1.1 测试准备及结果记录 33 5.1.2 小结 36 结　　论 38 参 考 文 献 39 致　　谢 42 附录 高速模幂乘实现编码VHD描述 43 绪论 模幂乘运算硬件IP研究进展及本文的主要工作 模幂乘运算研究现状与存在的问题 另一方面，信息技密1900年，一字母表的 本文的主要工作。 相关技术的发展 ?迪菲(Whitfield Diffie)和?海尔曼(Martin Hellman)有1976年?迪菲和?海尔曼提供的MH背包算法于1984年被破?里(Ronald L. Rivest)、阿迪?沙米尔(Adi Shamir)和雷?阿德尔曼(Leonard M.Adlemen)在威特菲尔德?迪菲和?海尔曼的1977年RSA算法。。 欧几里得方程在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 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 x0 x=x+b模幂运算模幂运算是RSA 的核心算法，最直接地决定了RSA 算法的性能。针对快速模幂运算这一课题，西方现代数学家提出了大量的解决方案，通常都是先将幂模运算转化为乘模运算。例如求D=C**15 % N，由于：a*b % n = (a % n)*(b % n) % n，所以：C1 =C*C % N =C**2 % NC2 =C1*C % N =C**3 % NC3 =C2*C2 % N =C**6 % NC4 =C3*C % N =C**7 % NC5 =C4*C4 % N =C**14 % NC6 =C5*C % N =C**15 % N即：对于E=15的幂模运算可分解为6 个乘模运算，归纳分析以上方法可以发现对于任意E，都可采用以下算法计算D=C**E % N：D=1WHILE E=0IF E%2=0C=C*C % NE=E/2ELSED=D*C % NE=E-1RETURN D继续分析会发现，要知道E 何时能整除 2，并不需要反复进行减一或除二的操作，只需验证E 的二进制各位是0 还是1 就可以了，从左至右或从右至左验证都可以，从左至右会更简洁，设E=Sum[i=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这样，模幂运算就转化成了一系列的模乘运算。模乘运算对于乘模运算 A*B%N，如果A