RSA密码算法

介绍：本篇文章主要介绍RSA密码算法的流程、基本定理及其实现难点说明。

一.RSA密码算法

1.安全基础

RSA公钥密码体制的理论基础是数论中的大整数因子分解的困难性，即求两个大素数的乘积，在计算机上很容易实现，但是，要将一个大整数分解成两个大素数的乘积，在计算机上很难实现。

2.算法流程

注：由于现代计算机计算性能的提高，要求n的比特长度不低于512，现在使用的RSA算法中一般使用的长度一般为512/1024/2048.每次加密过程中要求明文m小于n。

3.算法证明

4.欧拉定理

5.RSA实例

二.重难点说明

1.大素数选择

在RSA算法中，p、q是两个大素数，这样就涉及到选取大素数的问题。特别的，例如在1024位的RSA算法中，我们可以设计这两个大素数分别为512位（因为两个512bit长度数的乘积为2013或1024bit，而我们需要的是1024bit，故在设计p和q时可将最高的几位固定为1，这样乘积就为1024bit了）。可以通过下面的定理证明一个整数是否为素数，

2.公私钥产生

1）公钥产生 我们生成公钥e时，要求e与n的欧拉函数φ（n）互素，我们可以通过欧几里得算法验证互素与否。也可以通过构造一个一个素数e，因为e与非倍点的任何数都是互素的，故是符合要求的。

while(b!=0) { r = a % b; a = b; b = r; } //最终的a即为原a,b最大公约数

2）私钥产生 私钥d符合要求d = e^(-1)modφ(n)，求逆可以通过拓展欧几里得算法求得。

int exGcd(int a,int b,int &x,int &y) { if(b==0) { x = 1; y = 0; return a; } int r = exGcd(b,a%b,x,y); t = x; x = y; y = t-a/b*y; return r; }

3.加解密

1）加密 在加密过程中，加密者是不知道n的分解因子p、q，故无法使用中国剩余定理，只能通过常规的模幂运算。 2）解密 方法1：和加密流程一样，使用常规的模幂运算求解。 方法2：基于中国剩余定理（CRT）求解

m = c^d mod n，n = pq，这样就可以通过中国剩余定理将其变换为求解m，使得m = c^d mod p,且m = c^d mod q，这样就可以通过中国剩余 定理来求解。

中国剩余定理 通俗写法 拓展：拓展中国剩余定理

注：本文档部分参考自别的博客，侵删。