同余理論在仿射加密中的應用

摘 要： 本文介紹了數論中的同余理論在仿射加密中的應用。首先說明了字母與整數的對應，其次介紹了凱撒密碼這一簡單的加密方法，再次利用同余理論分析了通過明文中字母出現的頻率與英文字母本身出現的頻率的對應關系，介紹了對明文加密及對密文解密的方法，體現了數論的應用價值。

關鍵詞： 明文 密文 仿射加密 同余理論

在當今社會，信息無處不在。在一些情況下，傳遞信息的人希望他的信息只被特定的接收者知道要說明的內容，因而信息的加密顯得尤為重要。數論作為一門理論性的學科，在現實生活中顯示出了它的實用性。

一、了解相關概念

明文是一目了然的信息。把這些信息傳遞給某些人時，要先對明文進行“加密”處理，經加密處理的明文，稱之為密文。只有接收者掌握了一定的方法，才能由密文知道明文的信息。這個信息的傳遞包括兩個層面：第一，把明文寫成密文的方法；第二，解密的方法。

二、同余在仿射加密中的應用

首先建立明文與正整數的對應關系。一個文件總是由文字和其他符號組成的。如果用漢語拼音書寫漢字，那么，文件就可以用26個拉丁字母和一些符號表示，假設共N個，那么這些符號和N個正整數建立了一一對應的關系，例如：

那么，你真好（nizhenhao）對應的數字就是130825070413070014.

接著給出仿射加密方法。

例如：凱撒密碼作為一種最為古老的對稱加密體制，在古羅馬的時候已經很流行，它的基本思想是：通過把字母移動一定的位數實現加密和解密。明文中的所有字母都在字母表上向后（或向前）按照一個固定數目進行偏移后被替換成密文。例如，當偏移量是3的時候，設符號a，b，…，z分別與數字0，1，…，25對應，取n=26，a=1，b=3，d=1，對明文P中的每一個符號用公式E≡P+3（mod 26）加密。比如對于明文a有a→0→3→d，依此可得：

六點鐘（liudianzhong）被加密成olxgldqckrqj.

對于密文可用P≡E-3（mod 26）得到明文，例如g→6→3→d

由此可見，位數就是凱撒密碼加密和解密的密鑰。

再例，假如事先知道信息的每一個字母通過同余公式E≡P+k（mod 26），0≤E≤25進行變換，我們試對以下密文進行分析：

YFXMPCESPZCJTDFDPQFWQZCPYNTASPCTYRXPDDLRPD

首先我們要對密文中每個字母的出現字數進行統計，如下表所示：

“P”是出現頻率最高的字母，“C、D、F、T、Y”頻率較高。而我們知道“E”是英文信息中出現頻率最高的字母，可以猜測密文中的“P”表示明文中的“E”，則15≡4+k（mod 26），則k≡11（mod 26）。

因此，我們有同余公式E≡P+11（mod 26）及P≡E-11（mod 26），可得

嘗試破解密文得到：

NUMBERTHORYISUSEFULFORENCIPHERINGMESSAGES

通過明文的意思我們知道破解密碼正確。如果得到明文的字母混亂，則可以通過密文其他頻率較高字母的可能變換來解密。

一般的，對于仿射加密方法，只要知道兩對（不同的）相對應的明文與密文就可以求出解密方法。

參考文獻：

[1]馮克勤.數論與密碼.科學出版社，2007，3：61-76.

[2]紀建.數論與應用.清華大學出版社，2013，1：217-220.