非对称加密之-RSA加密

对一个大整数进行因数分解，在高等数学中叫做费马大定理，至今没有被破解RSA算法是最流行的公钥密码算法，使用长度可以变化的密钥。RSA是第一个既能用于数据加密也能用于数字签名的算法。

这是目前地球上最重要的加密算法

至此所有计算完成。将n和e封装成公钥，n和d封装成私钥。

回顾上面的密钥生成步骤，一共出现六个数字：

这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。那么有无可能在已知n和e的情况下，推导出d？

最终转换成->结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

第一步：首先生成秘钥对

第二步：公钥加密

第三步：私钥解密

几个全局变量解说：

关于加密填充方式：之前以为上面这些操作就能实现rsa加解密，以为万事大吉了，呵呵，这事还没完，悲剧还是发生了，Android这边加密过的数据，服务器端死活解密不了，，这造成了在android机上加密后无法在服务器上解密的原因，所以在实现的时候这个一定要注意

实现分段加密：搞定了填充方式之后又自信的认为万事大吉了，可是意外还是发生了，RSA非对称加密内容长度有限制，1024位key的最多只能加密127位数据，否则就会报错(javax.crypto.IllegalBlockSizeException:Datamustnotbelongerthan117bytes)，　RSA是常用的非对称加密算法。最近使用时却出现了“不正确的长度”的异常，研究发现是由于待加密的数据超长所致。RSA算法规定：待加密的字节数不能超过密钥的长度值除以8再减去11（即：KeySize/8-11），而加密后得到密文的字节数，正好是密钥的长度值除以8（即：KeySize/8）。

爱丽丝选择了61和53。（实际应用中，这两个质数越大，就越难破解。）

爱丽丝就把61和53相乘

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

爱丽丝算出φ(3233)等于60×52，即3120。

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

所谓模反元素就是指有一个整数d，可以使得ed被φ(n)除的余数为1。

这个式子等价于

于是找到模反元素d，实质上就是对下面这个二元一次方程求解。

已知e=17,φ(n)=3120，

至此所有计算完成

在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥就是(3233,17)，私钥就是（3233,2753）。

实际应用中公钥和私钥的数据都采用ASN.1格式表达

回顾上面的密钥生成步骤，一共出现六个数字：

这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。那么有无可能在已知n和e的情况下，推导出d？

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

可是大整数的因数分解，是一件非常困难的事情。目前除了暴力破解，还没有发现别的有效方法。维基百科这样写道

举例来说你可以对3233进行因数分解（61×53），但是你没法对下面这个整数进行因数分解。

它等于这样两个质数的乘积

事实上RSA加密的方式原理是一个高等数学中没有被解决的难题，所有没有可靠的RSA的破解方式