為了完成這學期密碼學的大作業（我們選的是調研 modular e-th root 的相關問題），最近讀了這篇結論有趣的 Breaking RSA Generically Is Equivalent to Factoring，在這裡分享給大家。

textbook RSA

破解 RSA 系統究竟有多困難？有人猜測它的難度與質因數分解相等，的確假如能在多項式時間內知道 n=pq 的分解，就能在多項式時間內求出私鑰 d 。但如何證明破解 RSA 能規約成質因數分解，仍是一個 open problem。

破解 RSA 的一個等價問題是求出密文的 e 次方根。所以這篇 Aggarwal 和 Maurer 發表於2009年的文章就證明瞭這個方向的一個較弱命題：如果存在一個在多項式時間求解 modular e-th root 的 generic ring algorithm，那麼就能在多項式時間內找到合數 n 的質因子。

文章的主要結論（實際上，這個定理比上一段所說的命題更強一點）
定理中 assumption 的定義. 從 RSA assumption 推到 Factoring assumption 仍是 open problem

1. 何為 Generic ring algorithm

簡單來講，一個 generic ring algorithm (後簡稱 GRA) 中的每一步，要麼是某個交換環的分式域 （這篇文章裏是模 n 的多項式環 mathbb{Z}_n[x] 的分式域）中兩個元素的運算（加，減，乘，除），要麼是判斷兩個環元素是否相等的條件語句。為了避免除法，我們可以將分式域中的每一個元素用一對多項式（分子，分母） (P(x), Q(x)) (P(x),Q(x)in mathbb{Z}_n[x]) 來表示。這樣演算法的每一步可以表示成

((P_i,Q_i),(P_i,Q_i),circ_i)=egin{cases} (P_iQ_i+P_iQ_i, Q_iQ_i), & ext{if } circ_i ext{ is }+\ (P_iQ_i-P_iQ_i, Q_iQ_i), & ext{if } circ_i ext{ is }-\ (P_iP_i, Q_iQ_i), & ext{if } circ_i ext{ is } imes\ (P_iQ_I, P_iQ_i), & ext{if } circ_i ext{ is }div\ mathbb{I}((P_i,Q_i)=(P_i,Q_i)),& ext{if } circ_i ext{ is }= end{cases}

我們將一個一般意義上的 (probabilistic) GRA 看做若干 deterministic GRA 依概率的組合，而對於每個 deterministic GRA，可以將每一步運算看做節點，用一棵樹來表示（如下圖所示）。演算法輸入數據首先作用於根結點，最後經過葉子節點的運算後輸出。我們把這棵樹上的每一條從根節點出發，不重複經過節點，並含有 L 次四則運算的路徑稱為一個 L-step straight line program (以後簡稱為 SLP)。簡單來說，一個 SLP 就是不包含條件判斷語句的 GRA。

deterministic GRA 的樹表示

一個 GRA 以 (x,1)~ (xin mathbb{Z}_n) 為輸入，以 (P(x),Q(x)) 為輸出，如果 P(x)^e-xcdot Q(x)^e=0 ，則演算法成功求出 x 的 e 次方根。

一些常用的操作（例如用二進位表示十進位數，然後XOR）仍然不能由域運算實現，因此 GRA 是一個比 probabilistic algorithm 小的集合。

2. 數學知識

對於多項式 P(x)in mathbb{Z}_n[x] ，我們令 u_n(P)=frac{|{xin mathbb{Z}_n ~|~ P(x)=_n0}|}{n}

為 P 的根所佔的比例，令 eta_n(P)=frac{|{xin mathbb{Z}_n ~|~ gcd(P(x),n) otin {1,n}}|}{n} 為 P 的值與 n 有非平凡 gcd (即 gcd(P(x),n) 蘊含了 n 的因子) 的比例。關於 u_n(P), eta_n(P) 的值，我們有如下兩個Lemma:

Lemma 1: For any P(x)inmathbb{Z}_n[x] , if u_n(P)in[delta,1-delta], then eta_n(P)ge delta^{3/2} .

Lemma 2: Let p be a prime. A random monic polynomial f(x)in mathbb{Z}p[x] of degree d is irreducible inmathbb{Z}_p[x] with probability at least 1/2d and has a root in mathbb{Z}_p with probability at least 1/2 .

當 n 為質數時，mathbb{Z}_n[x]為歐氏整區，其上的多項式也可以通過輾轉相除法求出最大公約式。而當 n 是合數時，輾轉相除法可能會失敗，返回一個最高次係數與 n 有非平凡公因子的餘式。而判斷輾轉相除法是否會失敗，可以通過比較在不同 mathbb{Z}_p[x] 上（ p 為 n 的質因子）求得的 gcd 最高次數是否相等。此處給出如下命題：

瞭解這些數學知識後，我們就可以真正開始定理的證明瞭！

整篇文章的思路比較簡單，首先通過樹表示上的路徑，將modular eth root 的 GRA 轉化為 SLP 或 n 的質因數分解，然後通過輾轉相除法將 SLP 轉化為 n 的質因數分解。( 如果你不追究細節的話，可以跳過下面兩節不看了)

3. Step 1: GRA Rightarrow SLP or Factoring

對於一個 GRA G，令輸入 x 遵循 mathbb{Z}_n 的均勻分佈，令lambda_n(G) 為 G 成功輸出 x 的 e 次方根的概率。

證明的第一步，就是驗證能通過一個概率演算法，將一個在 mathbb{Z}_n[x] 中能高概率成功求解 modular e-th root 的 GRA 以 (1-epsilon) 的概率轉化為一個高概率求解 modular e-th root 的 SLP，或者輸出 n 的質因數。

第一步證明的結論

現在來簡述這一步的證明思路：

對於步數不大於 L 的 GRA G，我們考慮它對應的樹，對於其代表相等判斷的節點 v 和輸入 (P_v(x),Q_v(x)) (P_v(x), Q_v(x)) ，假如 u_n(P_v(x)cdot Q_v(x)- P_v(x)cdot Q_v(x)) in [delta, 1-delta] (這裡 delta 可以視作一個小量)，則稱這樣的 v 為 non-extreme vertex (反之，則稱為 extreme vertex)。

將 GRA 轉化為（因數分解 或 SLP）的演算法是這樣進行的：從樹的根結點開始向下走，當我們遇到一個 non-extreme vertex 時，根據 Lemma 1 可以得知，反覆 M 次隨機 sample xin mathbb{Z}_n 並求 gcd(n,P_v(x)cdot Q_v(x)- P_v(x)cdot Q_v(x)) ，得到一個 n 的質因數的概率不小於 1-(1-delta^{3/2})^M .

而當我們遇到一個 extreme vertex 時，可以通過隨機 sample xin mathbb{Z}_n 並計算 mathbb{I}(P_v(x)cdot Q_v(x)= P_v(x)cdot Q_v(x)) 估計這一步之後最有可能走入哪一個分支，並繼續這個分支的下一個運算。倘若在到達葉節點時仍未遇到 non-extreme vertex，我們就得到了一個求解 modular e-th root 的 SLP。此時，由於至少有 (1-delta L) 比例的輸入經過我們選擇的每一個分支，SLP 成功輸出 e-th root 的概率至少為 lambda_n(G)-delta L .

選取參數 delta=epsilon/2L,~ M=lceil frac{L^{3/2} }{ (epsilon / 2)^{5/2}} ceil ，我們就能滿足引理中的條件。演算法的詳細描述如下：

證明第一部分結論所用的演算法

4. Step 2: SLP Rightarrow Factoring

第二步的結論

第二步是證明一個求解 modular e-th root 且成功概率不小於 mu 的 L-step SLP 能在多項式時間內，以不小於 mu/(8(L)+log(e)) 的成功概率輸出 n=pq 的質因子。假設SLP的輸出是 (P(x),Q(x)) ，令 f(x)=P(x)^e-xcdot Q(x)^e ，則 frac{|{xin mathbb{Z}_n,f(x)=0}|}{n}ge mu . 基於 SLP 的質數分解演算法如下：

其中，H(P(x), Q(x)) 表示用輾轉相除法求 gcd(P(x), Q(x)) 失敗時，所得餘式的首項

根據第二部分的 Proposition 1，當egin{equation*}deg(gcd_p(h(x),z(x))) eq deg(gcd_q(h(x),z(x)))end{equation*} 或者 deg(gcd_p(h(x),h(x))) eq deg(gcd_q(h(x),h(x))) 時，演算法就會成功。因此，我們只需要 lower bound 這兩種情況發生的概率。

又由於 Lemma 2， h(x) 同時在 mathbb{Z}_p[x] 有根 s ，並在 mathbb{Z}_q[x] 中不可約的概率至少為 frac{1}{2d}cdot frac{1}{2}=frac{1}{4d} . 在下面的討論中，假設 h(x) 滿足這兩種性質。此時分為兩種情況：

  • (x-s)^2|h(x) ~ in~ mathbb{Z}_p[x] : 易知 (x-s)|gcd_p(h(x),h(x)) ，但由於 h(x) 在mathbb{Z}_q[x] 中不可約， deg(gcd_q(h(x),h(x)))=0 eq deg(gcd_p(h(x),h(x))) . 演算法的第 6 行返回 n 的非平凡因子。

  • (x-s)^2 ot| ~h(x) ~ in~ mathbb{Z}_p[x] : 假設 h(x)=(x-s)h_1(x) ，則由於 r(x) 選取的任意性， Pr((x-s)|z(x))=Pr(z(s)=0 mod p)ge Pr(f(r(s))=0 mod n)ge mu . 而另一方面，由於h(x)在 mathbb{Z}_q[x]中不可約， f(r(x)) 在有限域 mathbb{Z}_q[x]/h(x) 中的次數至多為 2^Le+1 ， Pr(f(r(x))=0 mod q)le frac{deg(f)}{q^d}le frac{2^Le+1}{q^d} 選取 d=L+lceil log(e) ceil ，這個概率不會大於 1/2 . 因此 Pr(deg(gcd_q(z(x),h(x)))=0)=1-Pr(f(r(x))=0 mod q)ge 1/2 即，以不小於1/2的概率，第5行的輾轉相除法會失敗。

綜上所述，演算法第 5,6 行輸出 n 的質因子的概率不小於 frac{1}{4d}cdotfrac{mu}{2}=frac{mu}{8(L+lceil log(e) ceil)} .

結合 Step 1 與 Step 2 的結果：假設某個 GRA 破解 RSA 的成功概率至少是 mu_n ，令第一步結論中的 epsilon=frac{mu}{4} ，我們就在 poly(L,mu_n,log(e)) 時間內，以不小於 frac{mu_n}{16(L+lceil log(e) ceil)} 的概率求出 n 的質因子。對整個演算法時間複雜度的分析，這裡就不給出了。

5. Remarks

可以發現，第 2 步的演算法和證明對於任意非常值且能進行取模運算（最高次係數不是 p, q 的倍數）的多項式都成立。

這篇文章並沒有指出破解 RSA 與 factorization 的難度相比如何，但至少證明瞭，不通過 factoring 破解 RSA 的多項式時間演算法至少是 non generic 的（也就是說，一定會用到 bit manipulation 等域運算以外的操作）。

對這篇文章的介紹就到這裡啦，很多地方講得不嚴謹，有興趣的話建議直接閱讀原文

寫文章單純是為了督促和記錄學習，個人覺得把學到的東西講出來（一定程度上）有助於梳理思路，所以如果發現有理解上的偏差，歡迎指出。以後的文章大概都會是這種比較簡單無聊的畫風，大佬們姑且隨便看看就行啦 2333

推薦閱讀：

相關文章