php语言RSA加密及解密详解

RSA加密简介RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知...

RSA加密简介

RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制，这种加密模式被称为“非对称加密算法”。
在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。

公式和定理

互质关系：

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

1.任意两个质数构成互质关系，比如13和61;
2.一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10;
3.如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57;
4.1和任意一个自然数是都是互质关系，比如1和99;
5.p是大于1的整数，则p和p-1构成互质关系，比如57和56;
6.p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

欧拉函数：

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。φ(n) 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。

第一种情况
如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。 第二种情况
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。 第三种情况
如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、…、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。 第四种情况
如果n可以分解成两个互质的整数之积（n = p1 × p2），则　φ(n) = φ(p1p2) = φ(p1)φ(p2)；

模反元素：

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1，这时，b就叫做a的”模反元素”。

比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。

加密解密流程

乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的
甲方获取乙方的公钥，然后用它对信息加密
乙方得到加密后的信息，用私钥解密

加密解密步骤

第一步，随机选择两个不相等的质数p和q

例如：61和53（实际应用中，这两个质数越大，就越难破解）

第二步，计算p和q的乘积n

n = 61×53 = 3233
n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

第三步，计算n的欧拉函数φ(n)

根据公式：φ(n) = (p-1)(q-1)，计算出φ(3233)等于60×52，即3120。

第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质

在1到3120之间，随机选择了17（实际应用中，常常选择65537）

第五步，计算e对于φ(n)的模反元素d

所谓”模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1。ed ≡ 1 (mod φ(n)) 这个式子等价于ed - 1 = kφ(n)于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。
ex + φ(n)y = 1
已知 e=17, φ(n)=3120，
17x + 3120y = 1
这个方程可以用”扩展欧几里得算法”求解，此处省略具体过程。总之一组整数解为 (x,y)=(2753,-15)，即 d=2753

第六步，将n和e封装成公钥，n和d封装成私钥

以上例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）

RSA算法在web中的应用

通常我们做一个Web应用程序的时候都需要登录，登录就要输入用户名和登录密码，并且用户名和登录密码都是明文传输的，这样就有可能在中途被别人拦截，尤其是在网吧等场合。
所以，很多安全要求较高的网站都不会明文传输密码，它们会使用https来确保传输过程的安全，https是用证书来实现的，证书来自于证书颁发机构，当然了，你也可以自己造一张证书，但这样别人访问你的网站的时候还是会遇到麻烦，因为你自己造的证书不在用户浏览器的信任范围之内，你还得在用户浏览器上安装你的证书，来让用户浏览器相信你的网站，很多用户并不知道如何操作，就算会操作，也能也不乐意干；另一种选择是你向权威证书颁发机构申请一张证书，但这样有一定的门槛，还需要付费，也不是我们乐意干的事。

PHP进行RSA加密解密

生成RSA公钥和私钥密码
下载OpenSSL并进行安装，记住自己的安装路径即可,我安装到了（D:softOpenSSL-Win64）
CMD中进入到OpenSLL的bin目录下进行私钥和公钥的生成

//注意：生成的私钥公钥都在bin目录下面

D:softOpenSSL-Win64bin>openssl.exe

//生成私钥

OpenSSL> genrsa -out rsa_private_key.pem 1024

//查看私钥文件是否生成

D:softOpenSSL-Win64bin>dir rsa_private_*

//生成公钥

OpenSSL>rsa -in rsa_private_key.pem -pubout -out rsa_public_key.pem

//查看公钥文件是否生成

D:softOpenSSL-Win64bin>dir rsa_public*