破解N位RSA模數

Question

這與我的previous post有關，我的唯一選擇是擁有一個RSA算法，它似乎相對較弱。讓我們假設我想用一個36位模（34359738368到68719476735）編碼一個35位數（從0到34359738367）。

參照http://en.wikipedia.org/wiki/RSA我可以看到，我的n在34359738368之間，最高達到68719476735個隨機總數（形式爲p-1 * q-1）。我隨機選擇一個d和e。我編碼一個數字並在UI上顯示。

出於參數的目的，讓我們假設用戶可以看到多達1000個這樣的輸出。他可以使用像Polla's或類似的任何算法來破解我的d，e或n，從而開始預測新的數字嗎？如果是這樣會有多難？ （通過僅僅知道說1000組輸入/輸出）

作爲一個例子（考慮6個輸出作爲輸入/輸出格式樣品），

1. 10001621865,31116156015
2. 10001621866,33031668326
3. 10001621867,37351399313
4. 10001621868,06071714212
5. 10001621869,01188523761
6. 10001621870,18341011998

有人能告訴我我的n，d，e是什麼嗎？ （N之間34359738368高達68719476735）

我只是想知道它是多麼可破解，所以如果你可以給我任何信息有多長時間，有多快，有多少人看到輸出，可以使用什麼算法等等。它會很棒。

PS：用戶看不到像標準RSA算法那樣的「e」。他只能看到輸入輸出集。

信息添加 我試圖從數據庫到用戶呈現連續的用戶ID。因爲它是順序的，我不希望用戶通過執行一些註冊來猜測另一個用戶的ID。爲了避免這種情況，我必須將其編碼爲< = 12位數字。這個問題有很多限制，在this question中有解釋。

另外n，d和e的值對用戶是未知的。用戶可以看到的最大數量是幾個輸入輸出樣本（通過重複註冊）

接受由Accipitridae發佈的答案，因爲「Jacobi」算法可用於在幾秒鐘內解決此問題。不知道n，e或p。

Answer 1

攻擊者可以猜測n和e mod（p-1）的因子p。每個猜測可以通過消息m來檢查，計算m^e mod p然後與c mod p進行比較，其中c是相應的密文。由於p和e mod（p-1）每個可能是20位，這意味着該方案的安全性不會超過40位。

但40位只是一個非常粗略的上限。 攻擊者可以做得更好。例如，他可以猜測一個因子p。然後他計算消息和密文的雅可比符號。如果消息m是二次餘數mod p，那麼密文必須是二次餘數mod p，反之亦然。因此，如果這個關係不滿足消息/密文對，他可以拒絕p的猜測。或者攻擊者可以計算消息和密文之間的離散對數。這爲e mod提供了一個更快的候選（p-1）。

這應該提供20-30位的安全級別，因此需要幾秒鐘才能中斷。如果你將你的樣本數量擴展到20我可能會嘗試一些基準。

更新：由於您沒有給我20個樣本來進行實驗，我必須自己生成它們。用以下樣本

m = 10001621865 c = 31116156015 
m = 10001621866 c = 33031668326 
m = 10001621867 c = 37351399313 
m = 10001621868 c = 6071714212 
m = 10001621869 c = 1188523761 
m = 10001621870 c = 18341011998 
m = 10001621871 c = 7620400191 
m = 10001621872 c = 36106912203 
m = 10001621873 c = 37615263725 
m = 10001621874 c = 7795237418 
m = 10001621875 c = 34774459868 
m = 10001621876 c = 4555747045 
m = 10001621877 c = 33123599635 
m = 10001621878 c = 34836418207 
m = 10001621879 c = 33962453633 
m = 10001621880 c = 6258371439 
m = 10001621881 c = 7500991556 
m = 10001621882 c = 5071836635 
m = 10001621883 c = 911495880 
m = 10001621884 c = 39558568485 

作爲輸入，上述算法找到的因素201821和206153中 20ms的。如上所述，這並不需要知道e，儘管你對e = 65537的選擇很容易猜到，也可以被利用。

RSA的優勢在於它基於大分解因子的難度。在這裏你可以消除這個困難，剩下的就是RSA的所有弱點（即數學關係）。根據RSA構建分組密碼是一個可怕的想法。我真的不明白爲什麼你不想像我之前提出的那樣使用Luby-Rackoff結構。

Answer 2

RSA很容易受到選擇密文攻擊。也就是說，如果我們想破解密文y，我們可以使用其中一個密文 - 明文對來破解它。

如何打破它：

選擇一個x0和y0，其中x0和y0是，已經提供了明文，密文對。

y1 = y0 * y mod n y1是向用戶提供的滿足該標準的1000個密文中的另一個。 X1是Y1的解密，這也給出，這意味着：

X1 = Y1^d模N（這已經給我們，我們已經知道了X1）

X1 =（Y0 * Y ）^ d模N X1 = Y0^d * Y^d模NΞX0 * X

X1 * X0^-1 = X

x是y的解密。

這當然取決於y0 * y mod n是否會產生我們已經擁有的另一個密文，並且由於我們只有1000個這樣的對需要使用，所以破解不太可能但不是不可行。你只需要非常仔細地選擇你的配對。

我還想補充一點，您正在使用的n的大小允許一個保理啓發式來快速找到n的素因式分解。另外，RSA很容易受到時間攻擊，但這很容易受挫。

附加信息：不知道n，d或e，根本沒有信息提供，這意味着猜測n，d或e的組合與猜測明文本身一樣好。爲了找到n和e，至少有4359738367個n的猜測組合以及e可能的所有組合。即使有1000個密文 - 明文對能夠破解n和e，也不容易。

Answer 3

這是一個可怕的想法，36位RSA ??爲什麼不簡單地使用塊或流密碼？這樣你就可以以更安全的方式獲得1：1映射。

我推薦的另一種解決方案是使用SHA散列作爲UID，並將每個用戶的序號作爲單獨的列存儲在數據庫中。