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，如需轉載請自行聯系原作者