背景

大家好，我是石頭哥。

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整除)

因此 public key 為 (N=33, e=3)， private key 為 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 很大時，就特別困難了。大數分解在歷史以來就一直是數學上的難題。

曾經有人花了五個月時間分解了這個數39505874583265144526419767800614481996020776460304936454139376051579355626529450683609727842468219535093544305870490251995655335710209799226484977949442955603(159位數)， RSA-155 (512 bits) [from wikipedia]。

這條路走不通， 就有人走了"旁門左道"了， Stanford 的幾個研究者用了兩個小時破解了 OpenSSL 0.9.7 的 1024-bit 的 RSA 私鑰 (感興趣的同學可以看他們的論文Remote Timing Attacks are Practical)，用到的方法就是后面提到的時序攻擊(或譯為"計時攻擊")。

計時攻擊(Timing Attack)

計時攻擊是邊信道攻擊(或稱"側信道攻擊"，Side Channel Attack，簡稱 SCA) 的一種， 主要是一種利用不同的輸入會有不同的執行時間這個特點進行的。

剛開始看到這個，我還是大為震驚的。憑直覺想，感覺要實際應用起來干擾項太多了，是不是可以直接忽略?

不過，看到上述論文有實際攻破成功的案例，以及各大編程語言紛紛補丁來看，這樣做還是非常需要的，至少是“政治”正確的。

例如 JDK 1.6.0_17 中的Release Notes 中就提到了 MessageDigest.isEqual中的 bug 的修復，如下圖所示：

MessageDigest.isEqual計時攻擊

參考資料:

[Timing Attacks on RSA: Revealing Your Secrets through the Fourth Dimension](http://www.cs.sjsu.edu/faculty/stamp/students/article.html)

[Remote Timing Attacks are Practical](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)