RSA 算法：您的朋友可以擁有的最大可能鎖是多少，以便他/她可以秘密地與您分享？
我在準備考試時發現了這個問題。問題是
Q)假設，你和你的朋友有幾個鎖，你們都想使用基於 RSA 的密碼系統安全地共享這些數字。您將私鑰用作 (5,27)，而您的朋友將公鑰用作 (13,27)。您的一位朋友只想與您分享確切數量的鎖。您的朋友可以擁有的最大可能鎖是多少，以便他/她可以秘密地與您分享？
問題的答案是 26。但我不明白答案是怎麼來的。那麼任何人都可以向我解釋這個問題和答案嗎？
警告：問題中有一些錯誤，因此可以合理地忽略它，請參閱第二部分。但首先讓我們試著回答它，就好像我們沒有註意到一樣。
在教科書 RSA 的幾個略有不同的定義之一中，
私鑰（用於密鑰持有者解密）是 $ (d,n) $
公鑰（用於任何人的加密）是 $ (e,n) $ ,
純文字 $ m $ 和密文 $ c $ 是區間中的整數 $ [0,n-1] $ ,
$ n $ , $ d $ 和 $ e $ 選擇這樣¹，為所有人 $ m $ 在所述區間內，我們可以計算
- $ c:=m^e\bmod n $ 用於加密，然後
- $ m’:=c^d\bmod n $ 用於解密，產生 $ m’=m $ .
在上述 $ \bmod $ 是一個有兩個參數的運算符，這樣 $ x\bmod n $ 是唯一定義的整數 $ y $ 和 $ 0\le y<n $ 和 $ x-y $ 的倍數 $ n $ . 什麼時候 $ x\ge0 $ 和 $ n>0 $ ， 那 $ y $ 是歐幾里得除法的餘數 $ x $ 經過 $ n $ . 間隔 $ [0,n-1] $ 在上面的RSA定義中是因為它是歐幾里得除法中餘數的區間。
該問題要求最大整數 $ m $ 它在加密然後解密時產生。給定的鍵表明 $ n=27 $ ; 因此答案（最多）是 $ m=n-1=27-1=26 $ . 驗證這一點是有意義的 $ m $ 為問題的正確加密和解密 $ d=5 $ 和 $ e=13 $ 通過上述 RSA 的定義。證明很簡單：我們有 $ m\equiv-1\pmod n $ ， 和 $ e $ 和 $ d $ 是奇數，因此 $ c\equiv(-1)^e\equiv-1\pmod n $ ， 因此 $ m’\equiv(-1)^d\equiv-1\pmod n $ ， 因此 $ m’=c=m=n-1 $ 因為這是唯一的整數 $ y $ 在 $ [0,n-1] $ 和 $ y\equiv-1\pmod n $ .
注：以上 $ y\equiv x\pmod n $ 方法： $ x-y $ 是非零的倍數 $ n $ . 在這種使用 $ \bmod $ 不是一個有兩個參數的運算符，如其左側的左括號所示；相當， $ \pmod n $ 符合條件的 $ \equiv $ 左邊的符號，是等價模 $ n $ .
這個問題至少有一個嚴重的問題：大多數整數 $ m $ 在區間 $ [0,26] $ 加密後無法正確破譯！如果有人願意嘗試，只有 $ 0 $ , $ 1 $ 和 $ 26 $ 這樣做（他們做任何奇怪的事 $ e $ 和 $ d $ 被選中）。此外，所有 $ m $ 倍數 $ 3 $ 加密相同 $ c=0 $ ，因此其中最多一個可以正確破譯。
問題不僅如此 $ e $ 和 $ d $ 不匹配 $ n $ . 問題是 RSA 對所有人都有效 $ m $ 在範圍內 $ [0,n-1] $ 這是必要的 $ n $ 是無平方的，即不能被任何素數的平方整除；否則，任何素數在因式分解中不得出現兩次 $ n $ . 但在這兒 $ 27 $ 可以被 $ 3^2 $ . 沒有那個無平方條件，對於奇數 $ n $ ，還是可以選擇的 $ e $ 和 $ d $ 這樣解密對大多數人都有效 $ m $ . 但在手頭的情況下， $ e $ 和 $ d $ 甚至不符合條件¹。一種可能性是該問題最初是針對 $ n=51 $ ，這使得 $ d=5 $ , $ e=13 $ 在職的; 然後不小心改成了 $ n=27 $ .
它比 $ (d,n) $ 和 $ (e,n) $ 問題中的參數對 RSA 無效：任何類似大小的 RSA 參數都不允許秘密共享任何內容。
只有滿足以下條件，RSA 才能安全 $ n $ 很難分解，這要求它是數百個十進制數字。因此，任何較小的運動 $ n $ 是關於 RSA 在面對有能力的對手時使用電腦時的不安全實例化。我的觀點是，在教學 RSA 範例中 $ n $ 應該足夠大，以至於手動分解它有一些困難。還應該強調的是，確定性 RSA 加密在小集合中使用明文（例如，小間隔，或類別卷上的名稱）是不安全的，因為可以嘗試所有明文來破譯。
此外，“基於 RSA 的密碼系統”的規定如此鬆散，以至於在第一部分中假設教科書 RSA 純屬猜測。那個問題陳述是錯誤的！
¹ 教科書 RSA 正確破譯所有明文整數的充要條件 $ m $ 在 $ [0,n-1] $ 什麼時候 $ n $ 是無平方的，並且至少對於所有這樣的 $ m $ 與 $ n $ 否則，是： $ e,d\equiv1\pmod{\lambda(n)} $ ， 在哪裡 $ \lambda $ 是卡邁克爾函式。它經常被教授幾個稍微不同的條件之一，這些條件是充分的但不是必要的。流行的包括 $ e,d\equiv1\pmod{\varphi(n)} $ ， 在哪裡 $ \varphi $ 歐拉 如此頻繁 $ d=e^{-1}\bmod{\varphi(n)} $ ，另外的意思 $ 0\le d<\varphi(n) $ ; $ e=d^{-1}\bmod{\varphi(n)} $ , 在原始 RSA 文章中使用； $ d=e^{-1}\bmod{\lambda(n)} $ ，產生最小的正有效 $ d $ 對於給定的 $ e $ .