RSA那些坑

1.背景

最近生产上出了两个因为RSA加解密导致的性能问题，一个是加密引起的，一个是解密引起的，都是大量线程在进行RSA操作时等锁，线程被block，请求都被堆在Weblogic队列里不能处理。为此，我就研究了一下RSA加解密在Java里的实现，发现加解密的问题都出现在同一个地方。因为RSA加解密使用的方法都是同一个，就是计算ae mod n，也就是模幂运算，在做这个运算的时候，为了防范攻击，需要加入随机因素，寻找一个blinding parameter，让攻击者无法破解私钥，就是在寻找这个blinding parameter的时候线程出现了堵塞。下面的内容会做详细阐述。

另外，两个问题出现的jdk版本不一样，第一个是1.6，第二个是1.7，都是同一个方法，但是底层实现不太一样。

2.问题描述

2.1 第一个问题:动态菜单签名

客户端的菜单不是写死在客户端的，是服务器下发的。客户端每次启动时，向服务端请求最新的动态菜单，通过向服务端发一个上次更新菜单的时间，来判断服务器是否有新的菜单。为了防止菜单下发后被篡改，对菜单url做了签名。菜单的内容是基本不变的，但是每个人过来都要做一次签名，结果有次对菜单做了较多改动，又赶上做了一次推送，大量用户打开App，把服务器搞挂了。因为Java提供的签名方法内部上锁了，大量线程在等待锁，请求又多，扛不住了。

<a href="http://s5.51cto.com/wyfs02/M01/85/33/wKiom1ecfDTAnG8BAAH-uEVxoAo931.png" target="_blank"></a>

这个问题没有深入往下研究，用缓存解决了。因为下发的菜单或者其他资源几本是不变的，所以只要按字符串为key做缓存就行了。比如把对url的签名，按url为key缓存。

1

2

3

4

5

6

7

<code>//先查缓存</code>

<code>String signature=memkv.unsafe_hget(“SIGN_LIST”, url);</code>

<code>//查不到则计算签名，放入缓存，缓存1800s</code>

<code>if</code><code>(signature==</code><code>null</code><code>) {</code>

<code> </code><code>signature = SignatureUtil.sign(url);</code>

<code> </code><code>memkv.unsafe_hset(“SIGN_LIST”, url, </code><code>1800</code><code>);</code>

<code>}</code>

2.2 第二个问题：上送报文RSA加密

应用开启了报文全加密，大部分加密都是通过与服务端协商一个对称密钥，然后使用非对称密钥加密后传送，后续的报文都是通过对称加密处理的。但是有部分报文直接用了RSA加密，对性能产生了影响，同样是等锁。一共最多1000个线程，900多个都在等这个锁。

<a href="http://s3.51cto.com/wyfs02/M01/85/33/wKioL1ecfcKBbxhsAABE7brk1eE823.png" target="_blank"></a>

这个问题没法用缓存解决了，因为每个人上送的信息都是不一样的，需要好好研究一下了。

3.问题分析

通过看代码和查资料，我发现RSA在实际应用中并不是简单的做大数运算，为了提高安全性防范各种攻击，在加解密过程中都需要添加一定的随机因素。随机因素有两方面，一个是为了让同一明文每次加密产生的密文都不一样，加密前先填充一部分随机数，这个不止RSA有，DES等对称加密也都有，称为padding。另一方面是RSA解密（加密与解密用的同一个方法）的时候在做模幂运算时加入随机数，似的做运算的时间不固定，让攻击者无法统计计算时间， 致盲攻击者，称为blinding。 上面出现的问题都是blinding引起的。

3.1 加密随机数(padding)

加密的时候，一般需要在明文上填充一部分随机数，这样每次产生的密文都不一样，这个过程称为padding，而且加密标准里有各种类型的padding标准，比如PCKS1。

比如明文是D，通过一些填充，形成一个0011xxxxxxx11D的待加密串，00是开头，两个11中间是随机数，而且这些随机数不能含有1。这样同一个D，每次产生的待加密串是不一样的，解密后，按照这个格式把D取出来就行了。加密和解密端要使用同样的padding格式。

以下过程依次为 原始明文 -&gt; padding后明文 -&gt; 密文 -&gt; padding后明文 -&gt; 原始明文 对明文D做第一次加密 D -&gt; 00112311D -&gt; 123456 -&gt; 00112311D -&gt; D 对明文D做第二次加密 D -&gt; 00117811D -&gt; 783719 -&gt; 00117811D -&gt; D

为什么要使用padding呢？这个比较容易理解，比如有一种攻击类型叫做短消息攻击，如果我已知加解密双方的明文空间是四个字节的字符串，那我就可以通过观察明文对应的密文把所有的对应关系枚举出来，不需要密钥我就能知道这个密文对应的明文了。如果同样的明文每次密文都不一样，就没法实现这种攻击了。

3.2 解密随机数(blinding)

这个需要先从一种特殊的攻击方式说起。

3.2.1 时序攻击

RSA的破解从理论上来讲是大数质数分解，可是就是有一些人另辟蹊径，搞出乱七八糟的破解方法。有一种攻击方法叫做时序攻击(timing attack)，根据你解密的时间长短就能破解你的RSA私钥。这是什么鬼呢？

举一个不恰当但是比较容易理解的例子：

A通过B提供的加密装置把报文加密后发给B，我们不关心加密是怎么搞的，因为时序攻击也不用关系加密端。 A给B发的密文是2048位的01串，B有一个私钥，也是2048位的01串，解密的时候把两个串and一下 （以下示例用四位表示） 密文0101 私钥0110 明文0100

问题的关键来了，进行and运算时如果有一个0，那么运算的时间为1ms，如果两个都是1，运算的时间是10ms（只是个假设）。

基于以上假设，A就可以破解B的私钥了。A先构造一个0001的密文，获取B解密的时间，如果是1ms左右，那么对应的位就是0，如果是10ms左右，对应的1，依次类推，就把整个私钥推断出来了。

如何防范这种攻击呢？

一种最简单有效的方法，每次过来一个密文，先用一个随机数与它and一下，然后在与私钥and，只要随机数是真正的随机数，那么是无法破解的。注意，是真正的随机数而不是伪随机数。

现在回到RSA，RSA解密的本质就是幂模运算，也就是x = a ^ b  mod  n ，其中a是明文，b是私钥，n是两个大质数(p-1)(q-1)的积。由于这些数都特别大，比如b可能有2048位，直接计算是不可行的。计算x的最经典的算法是蒙哥马利算法，用代码表示如下：

8

9

10

11

12

<code>int</code> <code>mod(</code><code>int</code> <code>a,</code><code>int</code> <code>b,</code><code>int</code> <code>n){  </code>

<code>    </code><code>int</code> <code>result = </code><code>1</code><code>;  </code>

<code>    </code><code>int</code> <code>base = a;  </code>

<code>    </code><code>while</code><code>(b&gt;</code><code>0</code><code>){  </code>

<code>     </code><code>if</code><code>(b &amp; </code><code>1</code><code>==</code><code>1</code><code>){  </code>

<code>         </code><code>result = (result*base) % n;  </code>

<code>      </code><code>}  </code>

<code>     </code><code>base = (base*base) %n;  </code>

<code>      </code><code>b&gt;&gt;=</code><code>1</code><code>;  </code>

<code>   </code><code>}  </code>

<code>   </code><code>return</code> <code>result;  </code>

这个算法从b的最低位循环到最高位，如果是1，需要进行两次模乘运算，如果是0的话则只需要一次。由于这个操作是比较耗时的，所以0和1对应的时间差别较大。攻击者可以通过观察不同输入对应的解密时间，通过分析统计推断出私钥。具体的分析方法也不难，不过我没怎么看懂。。。

而防范RSA时序攻击的方法也是在解密时加入随机因素，让攻击者无法获取准确的解密时间。

3.3 线程阻塞原因

3.3.1 关于随机数

真正意义上的随机数，是很难产生的，因为即使小到原子，它的规律也是有迹可循的。所以我们产生的随机数都是伪随机数，但是伪随机数的随机性也是不一样的，如果产生的随机数规律性很强，那就很容易被预测到，而如果产生的随机数被预测的难度特别大，那么我们就可以认为它是真随机数了，只有强度高的随机数用来加解密等操作上才是安全的。

目前大部分操作系统都会提供两种随机数的产生方式，以Linux为例，它提供了/dev/urandom和/dev/random两个特殊设备，可以从里面读取一定长度的随机数。/dev/random是blocking pseudo random number generator (阻塞式伪随机数产生器)，它是通过网络事件，键盘敲击事件等物理上随机的事件，收集一些随机bit到熵池来产生随机数。这个随机生成函数可能因为熵池为空而等待，所以需要大量随机数的情况下它会显得很慢，但诸如产生证书之类的操作需要这种强度的随机数。 而/dev/urandom就是unblocking，它不会阻塞，但是产生的随机数不够高，是以时间戳之类的种子来产生随机数。

其它操作系统的实现方式可能不同，但是本质都是一样的。总之，要想获得一个真随机数，不管用什么语言，都需要等。在Java里面，可以用SecureRandom产生随机数，而且可以在JVM参数里配置是使用/dev/random还是/dev/urandom，如果安全性要求改，就用/dev/random，但是性能是就会有折扣。

3.3.2 Java的Cipher类

Java的加解密库是通过spi的方式，底层有不同的provider实现，默认的是sun官方的，比较有名的第三方的是bouncy castle。而上层的统一接口就是Cipher。

使用方法：

<code>//获取Cipher示例，注意这个并不是单例的，它有线程安全问题</code>

<code>//第一个参数是算法以及填充之类的，第二个是Provider，比如BC就是bouncy castle</code>

<code>Cipher cipher = Cipher.getInstance(</code><code>"RSA/CBC/PCKS1"</code><code>, </code><code>"BC"</code><code>);</code>

<code>//必须初始化</code>

<code>cipher.init(Cipher.DECRYPT_MODE, privateKey);</code>

<code>//传入byte[]数组进行加解密</code>

<code>cipher.doFinal(miwen);</code>

我在看我们应用的代码时，发现全局竟然只有一个Cipher，这个是有问题的，它有线程安全问题，看代码以及多线程做实验都发现了，由于初始化一个Cipher比较慢，所以最好用ThreadLocal来解决它的线程安全问题。

3.3.3 getBlindingParameterPair函数

通过堵塞的线程堆栈来看，两个问题都出现在RsaCore的getBlindingParameterPair上，第一个行数是261，第二个是417，这是因为两个jdk不一样。

在jdk1.6里面，getBlindingParameterPair用的是随机数的方法，堵在了SecureRandom.nextBytes上，这个函数在底层是读的/dev/random，如果产生的随机数不够用，就要堵塞。

在jdk1.7_80这个版本里，getBlingdingParameterPair没有用随机数，而是通过计算得到了一个pair，具体代码如下：

13

14

<code>synchronized</code> <code>(</code><code>this</code><code>) {</code>

<code>  </code><code>if</code> <code>((!</code><code>this</code><code>.u.equals(BigInteger.ZERO)) &amp;&amp; (!</code><code>this</code><code>.v.equals(BigInteger.ZERO)))</code>

<code> </code><code>{</code>

<code>  </code><code>localBlindingRandomPair = </code><code>new</code> <code>RSACore.BlindingRandomPair(</code><code>this</code><code>.u, </code><code>this</code><code>.v);</code>

<code>  </code><code>if</code> <code>((</code><code>this</code><code>.u.compareTo(BigInteger.ONE)&lt;=</code><code>0</code><code>)||(</code><code>this</code><code>.v.compareTo(BigInteger.ONE)&lt;=</code><code>0</code><code>))</code>

<code>  </code><code>{</code>

<code>   </code><code>this</code><code>.u = BigInteger.ZERO;</code>

<code>   </code><code>this</code><code>.v = BigInteger.ZERO;</code>

<code>  </code><code>} </code><code>else</code> <code>{</code>

<code>   </code><code>this</code><code>.u = </code><code>this</code><code>.u.modPow(BIG_TWO, paramBigInteger3);</code>

<code>   </code><code>this</code><code>.v = </code><code>this</code><code>.v.modPow(BIG_TWO, paramBigInteger3);</code>

<code>  </code><code>}</code>

<code> </code><code>}</code>

在同步块里进行大数运算，为什么要上锁我没有深入研究，但是1.7确实比1.6快了。

上面都是用jdk自带的provider实现的，我又试了下把provider换乘bouncy castle，比1.6自带的快很多，但是比1.7的慢，用多个线程解密的时候发现也是堵在SecureRandom.nextBytes上，所以bouncy castle也是用的随机数。

<a href="http://s3.51cto.com/wyfs02/M01/85/35/wKiom1ecqinC_hF-AAA7x2YiB_E692.png" target="_blank"></a>

问题的原因就是jdk自带的RSA解密方法为了防范时序攻击导致的，但是也没有好的解决办法。在早期的jdk里，代码中有if(ENABLE_BLINDING)这个判断，所以是可以把blinding关掉的，但是新的已经没有选项了，都需要使用blinding，因为时序攻击确实是挺容易实施的。

4.问题解决方案

第一个问题用缓存解决了，每个菜单半个小时只做一次签名，与原来的每个请求都签名相比，性能好太多。

第二个问题除了锁的问题，Cipher类本身有线程安全问题，通过ThreadLocal解决线程安全问题。但是锁的问题不好解决，短期内通过使用计数器对线程进行保护，比如最多允许300个线程同时调用这个函数，多了直接拒绝，因为使用RSA加解密的交易并不多，出现拥堵估计是特殊情况。长期内还是把用RSA加密报文的方式彻底换掉，RSA只加密对称密钥。

总之，RSA作为一种低效的加密方法，用在加密大量数据上面是不合适的，即使是签名之类的地方，能尽量少用也要少用，否则对性能影响很大。

本文转自nxlhero 51CTO博客，原文链接：http://blog.51cto.com/nxlhero/1832127，如需转载请自行联系原作者