Rsa
哪些攻擊可能針對原始/教科書 RSA？
PKCS#1 標準為簽名生成/驗證（ EMSA-PSS和EMSA-PKCS1-v1_5）和加密/解密（EME-OAEP和不太安全的EME-PKCS1-v1_5 ）定義了多種填充方案。
如果沒有應用填充機制，即如果在明文或散列上使用原始 RSA，則可能對簽名生成/驗證和加密/解密進行哪些攻擊？
這描述了一些針對教科書 RSA（也稱為原始 RSA）的攻擊，其中公共函式 $ x\mapsto y=x^e\bmod N $ 或私人功能 $ y\mapsto x=y^d\bmod N $ 直接應用於整數 $ m $ 代表消息。根據標准假設，公鑰 $ (N,e) $ 是已知的。
加密/解密
根據標准假設，密文 $ c\gets m^e\bmod N $ 是已知的。
- 教科書 RSA 中的確定性允許攻擊者（給定密文）搜尋相應的明文。
- 確定性也導致流量分析。可以區分是否發送了相同的加密消息，以及消息何時更改。這可能會洩露資訊。例如，如果攻擊者看到 $ E(\text{stay put}) $ , $ E(\text{stay put}) $ , $ E(\text{stay put}) $ , $ E(\text{stay put}) $ , 最後 $ E(\text{attack}) $ ，攻擊者會知道某些事情發生了變化。
- $ e $ th 根攻擊：針對短消息 $ m $ 和低 $ e $ （例如 $ e=3 $ )，可能會發生 $ m^e<n $ 使得密文 $ c=m^e $ , 則可以實現解密函式為 $ e $ -th根提取。這種攻擊有擴展 $ \log_2(m) $ 略高於 $ \log_2(n)/e $ .
- 廣播攻擊：當相同的消息被加密發送到至少 $ e $ 不同的通訊者，它可以（很有可能）在不知道任何私鑰的情況下被恢復。
- 中路遇襲；這是對上述 1 的改進，它允許比蠻力更快地搜尋明文；如果消息被假定為可寫為 $ m=a\cdot b $ 和 $ \max(a,b)\le u $ 和 $ \min(a,b)\le v $ ，努力是 $ \mathcal O(u) $ 有記憶 $ \mathcal O(v) $ 為常數 $ N $ .
- Jacobi 洩漏：如果 $ c=m^e\bmod N $ ， 然後 $ \big({c\over N}\big)=\big({m\over N}\big) $ . 換句話說，明文的雅可比符號 $ m $ 相對於 $ N $ 從密文中洩露 $ c $ . 這可能是在 RSA 之上建構的某些（相當複雜的）協議中的問題，或/和某些消息結構 $ m $ ; 例如 $ m=4r^2+b $ 和 $ r $ 一個 500 位的隨機密鑰， $ b $ 一位秘密和 1024 位 $ N $ : 當觀察到 $ \big({c\over N}\big)=-1 $ , 可以肯定地知道 $ b=1 $ .
簽名生成/驗證
根據標准假設，簽名驗證 $ s $ 計算 $ s^e\bmod N $ 並且要麼檢查 $ m $ ，或檢查這是一個明智的 $ m $ .
- Eve 可以隨機選擇一個 $ s $ , 計算 $ m=s^e\bmod N $ ，並假裝 $ s $ 是簽名 $ m $ . 稍微試錯，她可以選擇一些 $ m $ ，例如，讓它像
OK顯示為 C 字元串一樣列印，並帶有預期的 $ 2^{24} $ 嘗試。- 攻擊者可以組合簽名來創建新的簽名。例如 - 給定一個簽名 $ 2 $ （IE， $ 2^d\bmod{N} $ ) - 可以為 $ 4 $ ( $ 2^d\cdot 2^d\equiv 4^d\bmod{N} $ ).
- 假設 Alice 使用她的 RSA 私鑰實現了一個簽名服務。特別是，任何人都可以向 Alice 發送消息，她會檢查消息內容以確保其中沒有太糟糕的內容。如果資訊還不錯，她就會簽名。讓 $ m_b $ 是一個壞消息。夏娃可以發送 $ km_b $ 對於一些常數 $ k $ 給愛麗絲。自從 $ km_b $ 還不錯，愛麗絲會籤的。給夏娃 $ (km_b)^d\bmod{N} $ . Eve 也可以獲得一個有效的簽名 $ k $ 來自愛麗絲，因為它還不錯 $ k^d\bmod{N} $ . 使用這兩個，Eve 現在可以得到一個有效的簽名 $ m_b $ ，愛麗絲以前從未簽名過的東西，通過乘以第二個簽名的倒數。
- Eve 知道一些消息的簽名；例如簽名 $ 0 $ 是 $ 0 $ , 的簽名 $ 1 $ 是 $ 1 $ , 的簽名 $ n-1 $ 是 $ n-1 $ , 的簽名 $ k^e\bmod N $ 是 $ k $ 為了 $ 0\le k<N $ . 這本身可能很麻煩，也可能有助於攻擊 1 和 2。
更多的攻擊在 Dan Boneh 的RSA 密碼系統的二十年攻擊（在AMS 的通知，1999 年；或者這個其他版本的更多參考資料）中進行了描述。