拉賓解密
所以在拉賓解密中，由於平方根，我們得到 4 個答案，其中一個是正確的，儘管我有時多次看到正確的結果，即 4 個平方根中的 2 個。這是正常的嗎？
拉賓解密（或者更確切地說，在選擇解決方案然後刪除填充之前的一步）正在求解方程 $ c=m^2\bmod(p;q) $ , 尋找 $ 0\le m<p;q $ 給定 $ c $ 和不同的大素數 $ p $ 和 $ q $ （通常是採取 $ p\equiv q\equiv3\mod 4 $ ).
這是由
求解 $ c\bmod p={m_p}^2\bmod p $ 和 $ 0\le m_p<p $ , 使用任一解決方案 $ m_p=0 $ 什麼時候 $ c\bmod p=0 $ ; 或 2 個解決方案 $ m_p\ne0 $ 和 $ p-m_p $ 否則（當 $ p\equiv3\mod 4 $ , 一個解決方案是 $ (c\bmod p)^{p+1}/4\bmod p $ , 另一個如下)
同模 $ q $ ，也給出一兩個解決方案。
通過CRT結合解決方案。通常的方法是採取一對 $ (m_p,m_q) $ 併計算
- $ q_\text{Inv}=q^{-1}\bmod p $
- $ m_0=(((m_p-m_q);q_\text{Inv})\bmod p);q+m_q $
- $ m_1=(-m_0)\bmod(p;q) $
- $ m_2=((((m_p+m_q);q_\text{Inv})\bmod p);q-m_q)\bmod(p;q) $
- $ m_3=(-m_2)\bmod(p;q) $
有 1、2 或 4 個不同的解決方案 $ m_i $ 如此計算，從不為 3（證明：兩個解只有在模數相等時才能相等 $ p $ 和模 $ q $ ，我們可以統計案例；1個解決方案發生在 $ c=0 $ , 2 解決方案當另一個 $ c $ 是這樣的 $ c\bmod p=0 $ 或者 $ c\bmod q=0 $ , 4 解決方案，否則）。
在實踐中，除非私鑰持有者犯錯，否則只會出現 1 或 4 個解決方案。那是因為參展 $ c $ （或者 $ m $ ) 有 2 個解立即導致因式分解，因為 $ \gcd(c,;p;q) $ 是其中之一 $ p $ 或者 $ q $ . 1 解決方案僅發生在偽造密文的情況下（很容易由活躍的對手或傻瓜造成）。