仿射密码

展示 17x+5 的仿射密码。首先字母被转换成介于0到25的数字，下一步对每个套用 17x+5，结果再取除26后的余数，最后再转回字母。

仿射密码是一种替换密码。它是一个字母对一个字母的。

它的加密函数是$e(x)=ax+b\pmod{m}$，其中

- $a$和$m$互质。
- $m$是字母的数目。

解码函数是$d(x)=a^{-1}(x-b)\pmod{m}$，其中$a^{-1}$是$a$在$\mathbb{Z}_{m}$群的乘法逆元。

仿射密码 为 单表加密的一种，字母系统中所有字母都藉一简单数学方程加密，对应至数值，或转回字母。其仍有所有替代密码之弱处。所有字母皆借由方程 $(ax+b)\mod(26)$加密， $b$ 为移动大小。

## 介绍

于仿射加密中，大小为 $m$ 之字母系统首先对应至 $0 .. m-1$范围内之数值，接着使用模算数来将原文件中之字母转换为对应加密文件中的数字。

单一字母的加密函数为

$$\mbox{E}(x)=(ax+b)\mod{m},$$

取余 $m$ 为字母系统大小且 $a$ 和 $b$ 为密码关键值。$a$ 之值必须使得 $a$ 与 $m$ 互质. 解密方程为

$$\mbox{D}(x)=a^{-1}(x-b)\mod{m},$$

此处 $a^{-1}$为 $a$ 取模 $m$之模反元素 of I.e., 满足等式

$$1 = a a^{-1}\mod{m}.$$

$a$之乘法逆元素仅存在于 $a$ 与 $m$互质条件下。由此，没有 $a$ 的限制，可能无法解密。

易知解密方程逆于加密方程。

$$\begin{align} \mbox{D}(\mbox{E}(x)) &= a^{-1}(\mbox{E}(x)-b)\mod{m}\\ <pre> &= a^{-1}(((ax+b)\mod{m})-b)\mod{m} \\ &= a^{-1}(ax+b-b)\mod{m} \\ &= a^{-1}ax \mod{m}\\ &= x\mod{m}. </pre> \end{align}$$

## 弱处

因为仿射密码仍为单字母表密码，其依旧保留了该类别加密之弱处。当 $a=1$，仿射加密为凯撒密码，因该加密方程可简化为线性移动。

考虑加密英文。（即： $m=26$），不计26易凯萨密码，总共有286非易仿射密码。此数值是由于小于26之数中有12数与26互质。（$a$的可能值）。$a$ 的每个值可有26互异之加法移动（$b$ 之值）；因此，共有 12*26 或 312 可能之关键值。因为密码缺少复杂性，根据柯克霍夫原则，这套系统是不安全的。

此密码之首要弱处为，如果密码学家可发现(如 频率分析、暴力破解、臆测或任何其他方法）加密文件两字元之原文，则关键值可透过解一方程组得到。由于我们知道$a$及$m$互质，这个事实可被用于快速破解密码。

仿射密码中同种的转换使用于线性同余方法，为伪随机数生成器中的一种。此产生器不为密码学安全伪随机数生成器，因仿射加密不安全。

## 范例

在以下一加密一解密的例子中，字母为从Ａ至Ｚ，且在表格中都有对应值。

A｜B｜C｜D｜E｜F｜G｜H｜I｜J｜K｜L｜M｜N｜O｜P｜Q｜R｜S｜T｜U｜V｜W｜X｜Y｜Z

0｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10｜11｜12｜13｜14｜15｜16｜17｜18｜19｜20｜21｜22｜23｜24｜25

### 加密

在加密范例中，使用前述表格中各字母对应之数值可知欲加密的原文件为 "AFFINE CIPHER"，$a$ 对应5, $b$ 对应 8, 而 $m$ 对应 26 （因共使用26字母）。其中$a$之值必须与$m$的值26互质，所以其所有可能值包含1、3、5、7、9、11、15、17、19、21、23、25。若$a \neq 1$，则$b$之值可随机选定（因为b只让密文值平移而已）。所以，此加密范例的函数为 $y=E(x)=(5x+8)\pmod{26}$. 加密讯息的首步即为写出每个字母的数字值。

原始文件:｜A｜F｜F｜I｜N｜E｜C｜I｜P｜H｜E｜R

x:｜0｜5｜5｜8｜13｜4｜2｜8｜15｜7｜4｜17

现在，取x各值并解等式的第一部分， $(5x+8)$。得出各字母对应$(5x+8)$的值后，取其对26的余数。以下表格为加密的首四步骤。

原始文件:｜A｜F｜F｜I｜N｜E｜C｜I｜P｜H｜E｜R

x:｜0｜5｜5｜8｜13｜4｜2｜8｜15｜7｜4｜17

$5x+8$｜8｜33｜33｜48｜73｜28｜18｜48｜83｜43｜28｜93

$(5x+8)\pmod{26}$｜8｜7｜7｜22｜21｜2｜18｜22｜5｜17｜2｜15

加密讯息的最后一部，为查表求得对应字母的数值。在此范例中，加密文本应为 IHHWVCSWFRCP。以下表格显示仿射加密一讯息的完整表格。

原始文件:｜A｜F｜F｜I｜N｜E｜C｜I｜P｜H｜E｜R

x:｜0｜5｜5｜8｜13｜4｜2｜8｜15｜7｜4｜17

$5x+8$｜8｜33｜33｜48｜73｜28｜18｜48｜83｜43｜28｜93

$(5x+8)\pmod{26}$｜8｜7｜7｜22｜21｜2｜18｜22｜5｜17｜2｜15

加密文件:｜I｜H｜H｜W｜V｜C｜S｜W｜F｜R｜C｜P

### 解密

于此解密范例中，欲解密之加密文件来自加密范例。其解密方程为 $\mbox{D}(y)=21(y-8)\mbox{ mod }26$，经过计算， $a^{-1}$ 为 21, $b$ 为8, $m$ 为 26。伊始之时，写下加密文件中对应各字母之数值，如以下表格所示：

密文:｜I｜H｜H｜W｜V｜C｜S｜W｜F｜R｜C｜P

y:｜8｜7｜7｜22｜21｜2｜18｜22｜5｜17｜2｜15

下一步，计算 $21(y-8)$，再取结果除以26的余数。以下表格显示两者计算后的结果。

密文:｜I｜H｜H｜W｜V｜C｜S｜W｜F｜R｜C｜P

y:｜8｜7｜7｜22｜21｜2｜18｜22｜5｜17｜2｜15

21(y-8):｜0｜-21｜-21｜294｜273｜-126｜210｜294｜-63｜189｜-126｜147

(21(y-8)) mod 26:｜0｜5｜5｜8｜13｜4｜2｜8｜15｜7｜4｜17

解密的最后一部，借由表格将数值转回字母。解密的原始文件为 AFFINECIPHER。以下为完成解密后的表格：

加密文件：｜I｜H｜H｜W｜V｜C｜S｜W｜F｜R｜C｜P

y:｜8｜7｜7｜22｜21｜2｜18｜22｜5｜17｜2｜15

21(y-8):｜0｜-21｜-21｜294｜273｜-126｜210｜294｜-63｜189｜-126｜147

(21(y-8)) mod 26:｜0｜5｜5｜8｜13｜4｜2｜8｜15｜7｜4｜17

原文件:｜A｜F｜F｜I｜N｜E｜C｜I｜P｜H｜E｜R

### 全数字母加密

为求加解密更快速，可加密全数字母以将原文件之字母一对一对应至加密文件。此范例中，一对一映射如下：

原文件中字母｜A｜B｜C｜D｜E｜F｜G｜H｜I｜J｜K｜L｜M｜N｜O｜P｜Q｜R｜S｜T｜U｜V｜W｜X｜Y｜Z

原文件中数字｜0｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10｜11｜12｜13｜14｜15｜16｜17｜18｜19｜20｜21｜22｜23｜24｜25

(5x+8)mod(26)｜8｜13｜18｜23｜2｜7｜12｜17｜22｜1｜6｜11｜16｜21｜0｜5｜10｜15｜20｜25｜4｜9｜14｜19｜24｜3

加密文件字母｜I｜N｜S｜X｜C｜H｜M｜R｜W｜B｜G｜L｜Q｜V｜A｜F｜K｜P｜U｜Z｜E｜J｜O｜T｜Y｜D

### 程式实例

用 Python 程式语言，以下代码可用于加密罗马字母Ａ至Ｚ。

```python
# 列印仿射密碼的字母表。
# a必須與m互質
def affine(a, b):
    for i in range(26):
        print chr(i+65) + ": " + chr(((a*i+b)%26)+65)

# 調用函數的例子
affine(5, 8)
```

或者以Java作例:

```Java
public void Affine(int a, int b){
	    for (int num = 0; num < 26; num++)
	      System.out.println(((char)('A'+num)) + ":" + ((char)('A'+(a*num + b)% 26)) );
	}
Affine(5,8)
```

或于 Pascal:

```pascal
Procedure Affine(a,b : Integer);
  begin
    for num := 0 to 25 do
      WriteLn(Chr(num+65) , ': ' , Chr(((a*num + b) mod 26) + 65);
  end;

begin
  Affine(5,8)
end.
```

在 PHP的实现:

```php
function affineCipher($a, $b) {
    for($i = 0; $i < 26; $i++) {
        echo chr($i + 65) . ' ' . chr(65 + ($a * $i + $b) % 26) . '<br>';
    }
}

affineCipher(5, 8);
```