使用 GCD 的仿射明文攻擊！= 1

我正在嘗試破解仿射密碼，但是在破解時我找不到數字的倒數，因為 GCD 不是 1。這是我的明文，這是我的密文：

PLAIN:  072097 108108
CIPHER: 024328 164193

這是我的功能：

E(x) = ax + b (MOD 256256)

給出：

E(072097) = 072097a + b (MOD 256256) = 024328
E(108108) = 108108a + b (MOD 256256) = 164193

因此，如果我們減去這些，我們會得到：

139865 = 36012a (MOD 256256)
a = 139865 / 36012 (MOD 256256)
a = 139865 * 36012^-1 (MOD 256256)

現在 GCD(256256, 36012) = 4。所以沒有倒數，因為 GCD 不是一。

我確信可以破解此文本，但我只是不知道該怎麼做，因為沒有 36012 和 256256 的倒數。

有人知道如何破解這個或得到 36012 的倒數嗎？

您的算術似乎犯了一個錯誤：

$$ 108108 - 72097 = 36011 \ne 36012. $$ 號碼 $ 36011 $ 是可逆的模 $ 256256 $ ，因此你可以找到 $ a $ 和 $ b $ 以直截了當的方式。

更一般地說，您最終可能會遇到密文的差異 $ d_c $ 以及明文的區別 $ d_p $ 可能具有相同的公因數 $ g $ 與模 $ m $ . 在這種情況下，您可以做的是將差值和模數除以這個公因子以獲得 $ d’_c = d_c / g $ , $ d’_p = d_p / g $ 和 $ m’ = m / g $ ，並解決減少的遞歸 $ d’_c \equiv a d’_p \pmod{m’} $ . 這會給你的價值 $ a $ 模組 $ m’ $ ，這將對應於 $ g $ 不同的可能值 $ a $ 模組 $ m $ , 相差倍數 $ m’ $ . 如果 $ g $ 相對較小，這對於大多數用途而言幾乎與獲得唯一解決方案一樣好，因為例如要解密任何其他密文，您可以嘗試所有可能的解決方案並查看哪個結果最有意義。

引用自：https://crypto.stackexchange.com/questions/43927