背景

大家好，我是石頭哥。

RSA 算法大家肯定都聽說過了，它是一種常見的非對(duì)稱加密算法，常用來對(duì)一些在網(wǎng)絡(luò)上傳輸?shù)拿舾行畔⑦M(jìn)行加密。

但具體流程不知道大家清楚不?本文將概述 RSA 算法的流程，并用一個(gè)簡(jiǎn)單示例進(jìn)行闡述，最后講解了一種意想不到的“旁門左道”的破解方式。

RSA 算法流程

具體算法流程如下：

找到互質(zhì)的兩個(gè)數(shù)， p 和 q， 計(jì)算 N = p*q

確定一個(gè)數(shù) e， 使得 e 與 (p-1)(q-1) 互質(zhì)， 此時(shí)公鑰為 (N, e)， 告訴給對(duì)方

確定私鑰 d， 使得 e*d-1能夠被(p-1)(q-1)整除

消息傳輸方傳輸消息 M， 加密密文C為:

消息接受方通過收到密文消息 C， 解密消息 M:

RSA算法依賴于歐拉定理，一個(gè)簡(jiǎn)化版本為大致為 a 和 p 互質(zhì)，那么有:

即a 的 p-1 次方 對(duì) p 取余為1，(a 的 p-1次方減去1可以整除 p)

歐拉定理的證明比較復(fù)雜，可以參考下文末的參考資料。

舉個(gè)例子

還是用個(gè)簡(jiǎn)單示例來說明：

N = pq， 取倆素?cái)?shù) p=11, q = 3, N = p * q = 33， 取 e 與 (p-1)(q-1) = 20 互質(zhì)的數(shù) e = 3， 然后通過

確定私鑰， 即取一個(gè) d 使得 3*d -1 能 20 被整除， 假設(shè)取 d=7 或者d=67。(3*7-1=20 當(dāng)然能被20整除， 3*67-1=200 也能被20整除)

因此 public key 為 (N=33, e=3)， private key 為 d=7 或者d=67。

假設(shè)加密消息M=8， 通過加密算法，得到密文 C=8^3 % 33 = 17。

再來看解密， 由，得到明文 M = 17^7 % 33 = 8 或者 M=17^67 % 33=8， 是不是很神奇? (這里^ 表示多少次方，后文中的有的表示異或)

來， 安利一個(gè)計(jì)算器的工具， bc 命令， 支持任意精度的計(jì)算， 其實(shí) Mac簡(jiǎn)單的計(jì)算就可以通過前面介紹的 Alfred 可以方便得完成。

linux計(jì)算器

RSA 破解

如果需要破解 RSA 的話，就是需要找到 p 和 q， 使得 pq=33， 如果知道了 p 和 q 就能通過公鑰 N 和 e 反推出私鑰 d 了。

當(dāng)然上面所述的案例較簡(jiǎn)單，當(dāng) N 很大時(shí)，就特別困難了。大數(shù)分解在歷史以來就一直是數(shù)學(xué)上的難題。

曾經(jīng)有人花了五個(gè)月時(shí)間分解了這個(gè)數(shù)39505874583265144526419767800614481996020776460304936454139376051579355626529450683609727842468219535093544305870490251995655335710209799226484977949442955603(159位數(shù))， RSA-155 (512 bits) [from wikipedia]。

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

計(jì)時(shí)攻擊(Timing Attack)

計(jì)時(shí)攻擊是邊信道攻擊(或稱"側(cè)信道攻擊"，Side Channel Attack，簡(jiǎn)稱 SCA) 的一種， 主要是一種利用不同的輸入會(huì)有不同的執(zhí)行時(shí)間這個(gè)特點(diǎn)進(jìn)行的。

剛開始看到這個(gè)，我還是大為震驚的。憑直覺想，感覺要實(shí)際應(yīng)用起來干擾項(xiàng)太多了，是不是可以直接忽略?

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

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

MessageDigest.isEqual計(jì)時(shí)攻擊

參考資料:

[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)

[費(fèi)馬小定理](https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86)