上回书咱们说到非对称加密算法的扛把子RSA。这里就来翻一翻RSA瓤子里的东西。这样各位看官可以了解为啥素数规律和RSA有直接的关联。
--RSA的一些数论基础--
1、互质：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。（质数就是素数，还记得不？）
2、欧拉函数φ(n)：任意给定正整数n，求出在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）
3、欧拉定理：a^(φ(m))同余1(modm)(a与m互质)，这个定理是后面RSA公钥私钥互为加解密的基础，但解释起来很烧脑，还有一堆推论，都是数学游戏，这里就不展开了。
--RSA的运算过程--
前面咱有唠过对称加密算法和非对称加密算法的很大不同，就是对称加密算法对密钥不讲究，而非对称加密算法的密钥讲究的很。RSA作为一种典型的非对称加密算法，密钥不是随便找的，是要经过一系列烧脑的操作才能整出一对合格的密钥（公钥、私钥），两者之间有很强的关联性，所以一旦从数学的角度掌握了素数规律，拥有公钥很可能就可以用比以前穷举法更低的成本推算出私钥。为啥？首先看看RSA密钥对的生成方法。
第一步，随机选择两个不相等的质数p和q。
比如选择61和53。（实际应用中，这两个质数越大，就越难破解。）
第二步，计算p和q的乘积n。
如上：61和53相乘。n=61×53=
第三步，计算n的欧拉函数φ(n)。
根据上面偷懒没细说的一个推论，φ(n)=(p-1)(q-1)=60x52=
第四步，随机选择一个整数e，条件是1eφ(n)，且e与φ(n)互质。
咱们在1到之间，随机选择17吧（实际应用中，常常选择，比较安全）
第五步，计算e对于φ(n)的模反元素d。
所谓模反元素就是指有一个整数d，可以使得e*d被φ(n)除的余数为1。
数学表达是
e*d≡1(modφ(n))
这个式子等价于
ed-1=kφ(n)
于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。
ex+φ(n)y=1
已知e=17,φ(n)=，
17x+y=1
这个方程可以用扩展欧几里得算法求解，咱就不列具体过程了。总之，算出一组整数解为(x,y)=(,-15)，即d=。
第六步，将n和e封装成公钥，n和d封装成私钥。
在上面的例子中，n=，e=17，d=，所以公钥就是(,17)，私钥就是（,）。对的，非对称加密算法的密钥就是长这么任性！在实际的例子中，公钥大多是以X.证书规定的数据结构来存放的：
私钥通常以PEM文件方式携带：
--RSA算法破解分析--
1、能破吗？怎么破？
分析一下，有没有可能在已知RSA密钥的n和e的情况下，推导出d呢？
所以结论是：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。
可以看到，RSA算法的密钥对是非常关键的。由于公钥是公开的，RSA破解的风险主要在于私钥的安全性，而安全性又分存储安全性（要藏好）和算法安全性两方面（要抗破解）。公钥、私钥之间如果n可以被很快的因数分解（每个n只有一种分解可能性），d就可以被很快算出来，也就意味着私钥被破解了。所以RSA的算法命门在于大数的因数分解。实际上大整数的因数分解是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科是这么描述的：
举例而言，你可以对进行因数分解（61×53），但是你没法对下面这个整数进行因数分解
/p>
它等于这样两个质数（素数）的乘积：
之所以举这个例子，因为这大概是人类成功分解过的最大整数（个十进制位，个二进制位）。比它更大的因数分解，还没有被报道过的案例。而目前主流的RSA密钥长度是，被认为以当今世界上最先进的计算机也是无法在合理的时间内暴力破解的（以后量子计算机成熟后就说不好了）。
另外，大伙可能会觉得奇怪：这都讲到密钥了，怎么不顺着往下说RSA的加密、解密过程呢？其实RSA的加解密算法比较直观，本身是公开的。所以算法层面没什么好保护的，加密算法的保护主要在密钥保护上面。
而密钥的保护除了密钥本身的传递、保存的保护之外，最重要的是防止破解。这就呼应到上面的黎曼猜想的证明了。之所以黎曼猜想被证实有这么大的影响，最主要的也是因为证明的过程中可能会引发数学基础的大地震，导致RSA的基础：素数分布的规律被找到，这令大数（值很大的数）的因数分解变得比原来成本更低，从而使黑客获取公钥后比以前更快速的破解私钥。
2、算法破了怎么用？
RSA算法的长期广泛使用导致整个信息产业对其依赖性特别强。算法如果可以被以能接受的成本破解（数学家叫多项式时间复杂性），那影响的范围实在太广了。黑客可以攻入银行的安全系统，盗取以RSA保护的信息，篡改或制造签名保护的信息…举个简单的例子，一个SSL网站的数字证书（含公钥）是公开可获取的。黑客可以获取数字证书后进行算法破解，获取私钥。之后便用私钥解密基于HTTPS通信的数据，如果这个网站涉及巨额交易，之后的事情就很可能很大条了…还有更危险的事情就是用非对称加密算法保护的数据，一旦被破解，这些业务系统恐怕就要裸奔了！
--黎曼猜想被证明导致的RSA密码体系风险有多大--
其实从目前的情况看起来，我们还不能完全确认阿蒂亚对黎曼猜想的证明是完全严谨的，而且他展示的证明论文也非常庞杂，目前还处于同僚论证的阶段。业内已经有多位砖家对老先生的论文表示质疑。先不说这位迈克尔·阿蒂亚爵士是否真正攻破了这个旷世难题（老人家年龄大了，最近已有过几次失手，所以有人质疑他这次又在吹牛皮），假设成功的证明了黎曼猜想，则大概率能够给素数分布提供很多启示，甚至直接的规律，比方说我们可以用黎曼猜想来估计了素数定理的误差项，估计相邻素数之间的间隙等等，但是我们要知道RSA位的密钥长度是个二进制位，换算成十进制的话密钥是超过10的几百次方的超级大数。有学者计算过，即便在素数有规律可循的情况下，暴力破解RSA位的成本依然是天文数字。
即使我们可以通过黎曼猜想来获取到某个素数公式，我们也很难用它来快速破解RSA算法。为了破解RSA算法，我们需要的不是素数公式，我们需要分解质因数，而有了素数公式只能让分解因数这个本身耗费巨量算力的事情变得成本低了一些。现在业界常用的RSA算法的加密密钥的大小是位，根据素数定理，这个大小范围内素数大约占了所有整数的几千分之一。我们或许可以用给定区间内的所有素数来给破解RSA的算法提速数以万倍，但是本身成本仍然是天文数字（就好比成本从十亿年降到一亿年没啥区别）。如果有一天这个破解成本结合计算机运算速度的提升变得可以接受，却很容易就被RSA密钥长度的翻倍（提高到位）搞定，因为当从密钥长度增加到从位，暴力破解的碰撞成本会被提高数百亿倍。
--多说几句--
是不是有种看了场分钟的球赛0比0的感觉？！当然，话又说回来，RSA算法树大招风。有多少黑客、学者、各路英雄都盯着RSA。无论是谁，只要能以可以接受的成本攻破RSA，即可在世界范围内扬名立万。当年山东大学王小云教授通过碰撞法攻破了SHA1和MD5算法就受到了广泛的
