背??景大家好，我是石头哥。大家一定听说过RSA算法。是一种常见的非对称加密算法，常用于对网络上传输的一些敏感信息进行加密。但是我不知道具体过程，你知道吗？本文将概述RSA算法的过程，用一个简单的例子进行讲解，最后讲解一个意想不到的“异端”破解方法。RSA算法过程具体算法过程如下：求两个互质数p和q，计算N=p*q确定一个数e，使得e和(p-1)(q-1)为互质，此时密钥为(N,e)，告诉对方确定私钥d，使得e*d-1可以被(p-1)(q-1)整除消息发送方发送消息M，加密后的密文C为：消息接受方收到密文消息C，解密消息M：RSA算法依赖于欧拉定理，简化版大致就是a和p互质，则有：即a的p-1次方取p的余数为1，（a的p-1次方减1可以整除p）欧拉定理的证明比较复杂，请参考参考资料在以下文本的末尾。我们用一个简单的例子来说明：N=pq，取两个素数p=11，q=3，N=p*q=33，取e和(p-1)(q-1)=20的素数e=3，然后通过确定私钥，即取一个d，使得3*d-1可以被20整除，假设d=7或者d=67。（3*7-1=20当然可以被20整除，3*67-1=200也可以被20整除。）因此，公钥为（N=33，e=3），私钥为d=7或d=67。假设密文M=8，通过加密算法，得到密文C=8^3%33=17。我们再来看解密。从中，我们可以得到明文M=17^7%33=8或者M=17^67%33=8，是不是很神奇？（这里^表示多少次幂，后文中有的表示异或）来，安利一个计算器工具，bc命令，支持任意精度计算。其实Mac上的简单计算，通过前面介绍的Alfred就可以轻松完成。Linux计算器RSA破解如果需要破解RSA，需要找到p和q，使得pq=33，如果知道p和q，就可以通过公钥N和e推导出私钥d。当然，上面介绍的情况都比较简单，但是当N很大的时候就特别难了。Factorizationoflargenumbershasbeenadifficultprobleminmathematicsthroughouthistory.曾经有人花了五个月时间分解了这个数39505874583265144526419767800614481996020776460304936454139376051579355626529450683609727842468219535093544305870490251995655335710209799226484977949442955603(159位数)，RSA-155(512bits)[fromwikipedia]。If这条路不行，有人会“侧身”走。斯坦福的几位研究人员花了两个小时破解了OpenSSL0.9.7的1024位RSA私钥（有兴趣的同学可以看看他们的论文RemoteTimingAttacksarePractical），使用的方法就是后文提到的定时攻击（或译为“定时攻击”）”）。定时攻击（TimingAttack）定时攻击是一种侧信道攻击（或称“边信道攻击”，SideChannelAttack，简称SCA），主要是利用不同的输入会有不同的执行时间的特点来进行的..当我第一次看到这个的时候，我还很震惊。直观上感觉实际应用的干扰项太多了。我可以忽略它吗？不过看到上面的论文有实际的成功案例，看到各大编程语言都打了补丁，还是很有必要这么做的，至少“政治上”是正确的。例如JDK1.6.0_17版本的ReleaseNotes中提到了MessageDigest.isEqual的bug修复，如下图：](http://www.cs.sjsu.edu/faculty/stamp/students/article.html)[远程定时攻击很实用](http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf)[费马小定理](https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86)
