仿射密碼：如果數字在 mod n 上不可逆怎麼辦？

我目前正在解決一個簡單的密碼分析問題，我需要使用頻率分析來解密文本文件。文本已使用仿射密碼在 68 個字元的字母表上進行加密，其中包括大小寫英文字母、從 0 到 1 的數字以及這些字元：“. , ; : _ \n”，其中 _ 表示空格。

遍歷文本的頻率直方圖，出現頻率最高的字元是“，”，其次是“z”。據我所知，68 個字元的字母表中最常見的字元是空格，後跟“e”。

因此，我最終得到了這兩個等式：

$$ 66a + b = 63 \bmod 68 $$

$$ 4a + b = 25 \bmod 68 $$

這給了我：

$$ 62a = 38 \bmod 68 $$

$ a = 38 \cdot 62^{-1} \bmod 68 $

但是，62 不是可逆的 mod 68。我對密碼學很陌生，所以我很不確定是否有某種方法可以解決這個問題。

如果你把整個方程除以 2 你得到 $$ 31a\equiv 19\pmod {34} $$ 你可以解決得到 $ a\equiv 5\pmod{34} $ . 這提供了兩種可能性 $ a\pmod {68} $ : 5 或 39。對於這兩種可能性，您可以找到相應的 $ b $ （在這兩種情況下結果都是 5）並檢查哪個解決方案有效。

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