仿射密碼

說明

實作仿射密碼，這是一種源自中東的古老加密系統。

仿射密碼是一種單表替換密碼。 每個字元會對應到它的數值，接著用數學函式加密，然後轉換成對應其新數值的字母。 雖然所有單表替換密碼都很弱，但仿射密碼比埃特巴什密碼強得多，因為它的金鑰數量多得多。

加密

加密函式為：

E(x) = (ai + b) mod m

其中：

• i是字母的索引，範圍從0到字母表長度減 1。
• m是字母表的長度。 對羅馬字母表來說，m是26。
• a和b是構成加密金鑰的整數。

為了讓自動解密成功，a和m必須_互質_，也就是說，它們唯一的公因數是1（更多資訊請見關於互質整數的維基百科文章）。 如果a與m不互質，你的程式應該指出這是錯誤。 否則就應該用提供的金鑰進行加密或解密。

就這個練習而言，數字是有效的輸入，但不會被加密。 空格和標點符號則會被排除。 密文會以固定長度分組輸出，各組之間以空格分隔，傳統的每組大小是5個字母。 這樣做是為了讓人更難根據單字邊界猜出加密後的文字。

解密

解密函式為：

D(y) = (a^-1)(y - b) mod m

其中：

• y是加密字母的數值，也就是y = E(x)
• 請注意，a^-1是a mod m的模乘法反元素（MMI）
• 模乘法反元素只有在a和m互質時才存在。

a的 MMI 是滿足「ax除以m後的餘數為1」的x：

ax mod m = 1

關於如何求出模乘法反元素以及它的意義，更多資訊請見相關的維基百科文章。

一般範例

• 使用金鑰a = 5、b = 7加密"test"會得到"ybty"
• 使用金鑰a = 5、b = 7解密"ybty"會得到"test"
• 使用錯誤的金鑰a = 11、b = 7解密"ybty"會得到"lqul"
• 使用金鑰a = 19、b = 13解密"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx"會得到"thequickbrownfoxjumpsoverthelazydog"
• 使用金鑰a = 18、b = 13加密"test"會是錯誤，因為18和26不互質

求模乘法反元素（MMI）的範例

求a = 15的 MMI：

• (15 * x) mod 26 = 1
• (15 * 7) mod 26 = 1，即105 mod 26 = 1
• 7是15 mod 26的 MMI

---

出處

Wikipedia