如果 RSA 使用和和e和gcd(e,(N_))≠1gcd(和,φ(ñ))≠1gcd(e,phi(N))ne1但和和e很難分解 對手仍然有優勢ddd為了米d_≡m反對ñ米和d≡米反對ñm^{ed}equiv mmod N?
通常 RSA 使用加密指數 $ e $ 和 $ \gcd(e,\phi(N))=1 $ .
這個問題說明了為什麼會這樣：對於 $ \ne1 $ 可能不存在解密指數 $ d $ 因為其他 $ m’\ne m $ 可以與 $ m^e \equiv (m’)^e \bmod N $ .
但是，如果我們生產我們的 $ m $ 喜歡： $$ m = m_0^{e} \mod N $$ 或更一般的 $$ m = m_0^{e^{r_1}\cdot r_2} \mod N \tag{I} $$
我們總是可以（除了我們在這裡忽略的一些特殊情況）找到一個解密指數 $ d $ 為了 $ c \equiv m^e \mod N $ $$ d \equiv e^i \equiv e^{\phi(\phi(N))-1} \mod \phi(N) $$ 和 $$ c^d \equiv (m^{e})^d \equiv m^{\displaystyle e^1\cdot e^{{\phi(\phi(N))-1}}} \equiv m^{\displaystyle e^{{\phi(\phi(N))}}} \equiv m \mod N $$
當然這個消息 $ m $ 無法傳輸很多目標資訊。一些低位資訊可以通過產生隨機 $ m $ 直到第一個比特攜帶目標資訊。根本沒有效率，但這在這裡並不重要。
問題是對手找到解密指數會（更）容易嗎 $ d $ 對於這樣 $ e $ ?
如果 $ \gcd(e,\phi(N))\gg 1 $ 已知的因式分解 $ N $ 可以變得更容易，並因此破壞了 RSA 的安全性。
Q1：但是如果 $ \gcd(e,\phi(N))\gg 1 $ 不知道？為了確保我們選擇一個 $ e $ 這很難分解。
有一個對手仍然有很大的優勢，只是知道 $ \gcd \ne1 $ ?
它可能在很大程度上取決於選擇的因素。
我們在這裡假設（目標案例） $$ N = P \cdot Q $$ $$ P = 2 \cdot p_s \cdot p_b +1 $$ $$ Q = 2 \cdot q_s \cdot q_b +1 $$ $$ \phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b $$ $$ e = (2^2 \cdot p_b \cdot q_b) \cdot e_b > 2^{3000} \text{ (hard to factorize)} $$ $$ \gcd(e,\phi(N))=2^2\cdot p_b \cdot q_b = 2^2\cdot (2\cdot 3\cdot b_0+1) \cdot (2\cdot 3\cdot q_0+1) = B $$ $$ B > 2^{2000} \text{ (hard to factorize)} $$ $$ \phi(\phi(N)) = 2^3 \cdot 3^2 \cdot \phi(p_s) \cdot \phi(q_s) \cdot (q_0\cdot b_0) $$ $$ \phi(p_s) \cdot \phi(q_s) /4= S \approx 2^{200} \ll B $$ （在目標案例中 $ p_s,q_s $ 有表格 $ p_s = 2\cdot p_1\cdot p_2 \cdot p_3+1 $ )
（所有可變素因數都是唯一的）
$ e $ 必須是原根模的平方 $ p_s $ 和 $ q_s $ .
有了這個我們可以生產 $ S $ 不同的價值觀 $ m^{e^i} \bmod N $ . 取決於啟動 $ m $ 我們得到了 4 個這樣大小的不相交集（加上我們在這裡忽略的一些較小的特殊情況）。
附加因素 $ e_b $ 需要隱藏與 $ \phi(N) $ 和 $ B $ . 有了這個 $ e\gg N $ 這裡。
我們假設對手也知道 $ S $ 包括它的主要分解。
**Q2：**案例相關的問題也允許目標值 $ n\ne m $ 但生成像 $ (\text{I}) $ （並且已知有解決方案）：
對手能否找到 $ i $ 在 $ n\equiv m^{e^i} \bmod N $ 與已知 $ e,n,m,N,S $ 比…快 $ O(p_s + q_s) \approx O(\sqrt{S}) $ ?
這可以通過找到解決方案來實現 $ j,k $ 在 $ n^{\displaystyle p_s} \equiv (m^{\displaystyle {p_s}})^{e^j} \bmod N $ 和 $ n^{\displaystyle q_s} \equiv (m^{\displaystyle {q_s}})^{e^k} \bmod N $ 通過逐步測試。巨大的一步不能作為 $ \phi(N) $ 是未知的並且 $ e^{2^{50}} $ 沒有它太大而無法計算。還是可以更快地完成？
（玩具）-範例：
這裡 $ p_b,q_b < p_s,q_s $ 被使用。在目標案例中，它們將是 $ p_b,q_b \gg p_s,q_s $ （所有值都大得多）
$ N=P\cdot Q = 6565236619157488809896588016937 $
$ P = 2 \cdot p_s \cdot p_b +1 = 2500987802965403 $
$ Q = 2 \cdot q_s \cdot q_b +1 = 2625057431856779 $
$ p_b = 2 \cdot 3 \cdot p_0 = 2 \cdot 3 \cdot 4547= 27283 $
$ p_s = 2 \cdot p_1 \cdot p_2 \cdot p_3 + 1 = 2 \cdot 2579\cdot 2963\cdot 2999 + 1=45834178847 $
$ q_b = 2 \cdot 3 \cdot q_0 = 2 \cdot 3 \cdot 4007= 24043 $
$ q_s = 2 \cdot q_1 \cdot q_2 \cdot q_3 + 1 = 2 \cdot 2819\cdot 3023\cdot 3203 + 1=54590887823 $
$ \phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b = 6565236619157483683851353194756 $ $ \phi(\phi(N))=2^5\cdot3^2 \cdot p_0\cdot p_1\cdot p_2 \cdot p_3\cdot q_0\cdot q_1\cdot q_2\cdot q_3 $
$ \phi(\phi(N)) = 3282361465954844745126356151456 $
指數 $ e,d $ 只有一個額外的大因素使分解變得困難。 $ e = 3681846424601561452716738001396 = 2^2 \cdot p_b \cdot q_b \cdot 1403217197574083942221 $
$ d = 1568810657844451193145575929268 = 2^2 \cdot p_b \cdot q_b \cdot 597901661545558066493 $
這裡 $ B<S $ 但在目標案例中 $ B \gg S $ $ S = p_1\cdot p_2\cdot p_3\cdot q_1\cdot q_2\cdot q_3 = 625532128948867853353 $
$ B = 2^2 \cdot p_b \cdot q_b = 2^2 \cdot 27283 \cdot 24043=2623860676 $
對手會知道 $ N $ , $ e $ , $ S $ 包括因式分解 $ S $ . 但他不知道因式分解 $ N,e,B $ .
一種明顯的分解方法是：
r := rand(); m_0 := r^e mod n x := y := m_0 for (;;) x := x^2 * m_0 mod n y := y^2 * m_0 mod n y := y^2 * m_0 mod n if (gcd(x-y, n) != 1) gcd(x-y, n) is likely a nontrivial factor似乎使用的迭代次數可能與較大的主要因素中的較小者有關 $ p_s - 1, q_s - 1 $ . 因為您將它們指定為很小，所以這很有可能實用。