Rsa

當公鑰和私鑰都是秘密的時,Shor 的算法能否破壞 RSA?

  • February 9, 2021

如果 RSA 要創建一個公私密鑰對並在純測試 P 上執行加密以創建密文 C,那麼給定 P 和 C 是否可以使用 Shor 算法來查找公鑰和私鑰?您同時擁有純文字和密文,但都沒有密鑰。

如果公鑰和私鑰都是秘密的,那麼使用 RSA 似乎毫無意義的事實已經出現了幾次,所以讓我解釋一下。我想使用 RSA,因為它的屬性是,如果純文字 P 用密鑰 K1 加密,結果用密鑰 K2 加密,假設 K1 和 K2 具有相同的模數基數,這將產生與加密 P 相同的密文K2 然後 K1。

如果有另一個更安全的加密方案具有此屬性,那麼我將非常有興趣了解它。否則,我將需要使用 RSA,這就是為什麼我要詢問 RSA 對抗量子電腦的能力。

此外,模組庫也將是眾所周知的。唯一的秘密資訊是密鑰對中的指數。

目的

有人問密鑰交換性的價值是什麼。它允許一方使用另一方(只有乙方知道)的密鑰 K 加密一個秘密文本 P(只有甲方知道)。這是如何:

令 P = 純文字(只有當事方 Alice 知道)

讓 C = 密文(只有當事方 Alice 知道)

讓 K = 密鑰(只有當事方 Bob 知道)

讓 U = 中間密鑰(只有當事方 Alice 知道)

Alice 用 U 加密 P 並將其發送給 Bob。Bob 用 K 對其進行加密並將其發送回 Alice。A 刪除初始加密(使用 U 的解密對)得到 C。

C 與 P 在沒有中間密鑰的情況下使用 K 加密是相同的,因為密鑰可以交換。

示意圖:

在此處輸入圖像描述

愛麗絲和鮑勃只能看到他們“身邊”的東西(密鑰和文本)。等號牆代表了這種分離。箭頭表示從一個地方傳輸到另一個地方的文本,與箭頭相交的密鑰表示通過它們的文本的加密。我希望這是對這個過程的一個清晰的解釋。我不熟悉繪製這類示意圖的任何傳統方式。我有人可以指導我獲取一些有關如何繪製的資訊,我很樂意學習它並以這種格式重寫我的原理圖。

實際上,如果 RSA 以一種確定的方式使用(以及公共指數 $ e $ 相對較小),有人可以恢復價值 $ N $ .

我們知道 $ P^e = C \bmod N $ ; 這相當於 $ P^e - C = kN $ 對於某個整數 $ k $ ; 如果 $ e $ 很小,那麼 Shor 的算法可能能夠分解 $ P^e - C $ ; 讓你恢復 $ N $ . 或者,如果您有來自同一個密鑰的兩個明文/密文,那麼您需要做的就是 $ \gcd(P_1^e - C_1, P_2^e - C_2) $ ,這可以在傳統電腦上完成。

現在,對於公鑰加密,我們從不使用確定性加密。但是,為了生成簽名,我們有時會這樣做;這實際上可能適用於那裡。

我也會贊同 Maarten 的評論,即如果您真的打算對公鑰保密,那麼有更實用的對稱算法(更不用說抗量子計算了)。

引用自:https://crypto.stackexchange.com/questions/37012