自製隨機 RSA
考慮以下加密方案，其中 RSA 用於加密明文m，然後我們選擇隨機r併計算：
$$ A = r + m^e \bmod N $$ 和$$ B = r^e \bmod N $$所以密文是一對：$$ (A,B) $$為了恢復m我們計算：$$ m = (B^d - A)^d \bmod N $$恕我直言，該方案沒有隨機加密，因為這種填充方法是錯誤的，但我不知道為什麼。誰能給我一點提示？
- Spartacus：也許我想出了解決方案，因為上面描述的密碼系統不是CCA 安全的，對手A可以攔截**(A,B)併計算新的密文$$ C = 2B\bmod N = 2^er^e \bmod N $$由於他正在執行 CCA 攻擊，因此他可以訪問解密預言機，並且因為：$$ C\neq B $$預言機輸出$$ RSA^{-1}(C) = 2^{ed}r^{ed}\bmod N = 2r\bmod N $$所以他可以簡單地將r恢復為計算明文的一半，併計算r - A**他獲得了消息的確定性加密。這樣對嗎？
- Artjom-B：你忘記了什麼 $ 2^eB\bmod N=2^er^e\bmod N $ . 我不認為這是完整的，因為解密 oracle 會解密 $ (A,C) $ 並不是 $ C $ 獨自的。
- 斯巴達克斯：也許是真的，但根據定義，我不能用原始挑戰密文 A 查詢解密預言機。如果有可能，我們獲得 CCA 安全密碼系統的機會為零
- SEJPM：提示 1：這個方案甚至不是 IND-CPA 安全的。提示 2：Henrick 所說的。提示 3：給定 $ (A,B,m,e,N) $ ，你能以某種方式恢復嗎 $ r $ ，可能以某種方式使用 A 和 m ？
好的，讓我們證明該方案不是 IND-CPA 安全的：
- 敵手A輸出兩條消息 $ m_0,m_1 $ .
- 一個統一的位 $ b $ 被選中 $ b \leftarrow {0,1} $ 然後是挑戰密文 $ C $ 計算如下：
$$ A = r + m_b^e \bmod N $$ $$ B = r^e \bmod N. $$ 3. 這對 $ (A,B) $ 輸出給對手A。 4. 在猜測值之前 $ b $ 敵手A仍然可以訪問公鑰，因此他可以計算以下兩種確定性加密 $ m_0 $ 和 $ m_1 $ 如下：
$$ C_0 = m_0^e \bmod N $$ $$ C_1 = m_1^e \bmod N $$. 5. 現在他可以計算r的兩個可能的明文值如下
$$ P_r^1 = A - C_0 $$ $$ P_r^2 = A - C_1. $$ 6. A 還不知道使用了兩個可能的計算明文值中的哪一個，但他有正確的密文和公鑰，所以他計算
$$ C_r^1 = (P_r^1)^e \bmod N $$ $$ C_r^2 = (P_r^2)^e \bmod N. $$ 7. 現在他可以簡單地比較密文如下：如果 $ C_r^1 = B $ 然後使用 $ P_r^1 $ , 否則使用 $ P_r^2 $ . 8. 讓 $ P_r^k $ 成為選定的值。現在對手可以簡單地計算挑戰密文的確定性加密 $ C $ :
$$ C_d = A - P_r^k \bmod N. $$ 9. 現在很容易猜出 $ b $ ： 如果 $ C_d = C_0 $ 然後 $ b’=0 $ ， 別的 $ b’=1 $ .
所以A輸出的機率 $ b’=b $ 等於 $ 1 $ ; 加密方案不是 IND-CPA 安全的。