p=q 時的拉賓密碼體制解密
當我意識到給 p 和 q 相同的值時，我目前正在嘗試實現 Rabin 密碼系統：
所以我的價值觀如下：
原始消息 = 20
p=11
q=11
加密消息 = 37
解密後我得到四個值
99, 99, 22, 22
這些值都不是我的原始資訊。為什麼會這樣，我怎樣才能得到原始消息？
我在此處找到的 wiki 文章之後實現了算法：https ://en.wikipedia.org/wiki/Rabin_cryptosystem
先感謝您！
Rabin 和 RSA 一樣，需要 $ p\ne q $ . 基本上，這是因為環 $ \mathbf{Z}{pq} $ （為了 $ p\ne q $ ） 和 $ \mathbf{Z}{p^2} $ 有根本區別。至關重要的是， $ \mathbf{Z}_{pq} $ 同構於 $ \mathbf{Z}_p \times \mathbf{Z}q $ ，並且您的解密算法取決於該屬性。另一方面， $ \mathbf{Z}{p^2} $ 不同構於 $ \mathbf{Z}_p^2 = \mathbf{Z}_p \times \mathbf{Z}_p $ ，所以你的解密算法不起作用。
正如 fkraiem 已經指出的那樣，拉賓的要求 $ p\neq q $ ，否則你的環與直接產品不同構 $ \mathbb{Z}_p \times \mathbb{Z}_q $ . 然後解密無法按照算法中的說明進行。
是的，我知道。那我該怎麼做呢？我是否必須再次考慮 p，在其餘計算中使用 1 和 11 作為 p 和 q？（對於這個例子） - Krachwas
首先，如果您創建了密鑰，那麼您已經知道分解。你永遠不必考慮任何事情。
重要的是要意識到，使用 $ p=q $ 非常不安全。很容易發現，一個數字是一個完美的正方形。然後每個人都可以解密。
但是，假設您使用不安全的，這就是您如何取回您的號碼 $ p^2 = n $ 和密文 $ c $ :
- 首先你計算平方根模 $ p $ ： 計算 $ x $ 英石 $ x^2 = c \mod p $ ，例如使用Tonelli-Shanks 算法
- 然後您可以將Hensel 提升與多項式一起使用 $ x^2 - c = 0 \mod p $ 得到解決方案 $ y^2 - c = 0 \mod p^2 $ .
但最後，您只想通過使用來解決您的問題 $ p, q $ 素數和 $ p\neq q $ ，如算法要求中所述。