Rsa
證明 RSA CCA 是可能的
我正在閱讀 William Stalling 的 Cryptography & Network Security - 第 7 版
對我來說，第一行暗示
$$ (M^e\bmod n)\times(2^e\bmod n)=((2M)^e\bmod n) $$ 這意味著如果我們要定義一個消息 $ X $ 這樣當解密時它給出 $ 2M $ 那麼我們應該考慮 $ X=(M^e\bmod n)\times(2^e\bmod n)=C\times(2^e \bmod n) $
然而，出於某種原因，這本書建議 $ X=(C\times2^e)\bmod n $ 而且我看不出它們是相同的表達方式。
作者忘記了幾個 $ \bmod n $ 一路上。特別是，方程 9.2 是錯誤的，應該是 $$ E(PU,M_1)\times E(PU,M_2)\bmod n=E(PU,(M_1\times M_2\bmod n)) $$ 此外，“注意”之後的內容在第一行是錯誤的，然後是從第二行到最後一行（結論是正確的）。
使用同餘模可以避免這種混亂 $ n $ ,等價關係 $ \mathbb Z $ 著名的 $ \equiv $ 和 $ \pmod n $ 在行尾。回想一下，對於 $ n,k\in\mathbb N^* $ , $ u,v\in\mathbb Z $
- 該聲明 $ u\equiv v\pmod n $ 方法 $ v-u $ 是的倍數 $ n $
- 該聲明 $ u=v\bmod n $ 另外意味著 $ 0\le u<n $ .
- 它擁有 $$ \begin{align} (u\bmod n)+v&\equiv u+v&\pmod n\ (u\bmod n)\times v&\equiv u\times v&\pmod n\ (u\bmod n)^k&\equiv u^k&\pmod n\ \end{align} $$
接著就，隨即 $ \equiv $ 符號，證明變為：
- 定義 $ X:=C\times2^e\bmod N $ 並將其送出解密，產生 $ Y:=X^d\bmod n $ .
- 它擁有 $ Y\equiv X^d\equiv(C\times2^e)^d\equiv C^d\times(2^e)^d\equiv C^d\times2\pmod n $ ，注意到 $ (2^e)^d\equiv2\pmod n $ 因為 $ 2 $ 被加密和解密。
- 自從 $ 0\le Y<n $ 它擁有 $ Y=2M\bmod n $ ，這讓我們找到 $ M $ 從 $ Y $ ： 如果 $ Y $ 就在那時 $ M:=Y/2 $ ， 否則 $ M:=(Y+n)/2 $ .