仿射密碼：修订间差异

删除的内容添加的内容

行内

2015年3月13日 (五) 11:57的版本

A	0	5	5	F
B	1	22	22	W
C	2	39	13	N
D	3	56	4	E
E	4	73	21	V
F	5	90	12	M
G	6	107	3	D
H	7	124	20	U
I	8	141	11	L
J	9	158	2	C
K	10	175	19	T
L	11	192	10	K
M	12	209	1	B
N	13	226	18	S
O	14	243	9	J
P	15	260	0	A
Q	16	277	17	R
R	17	294	8	I
S	18	311	25	Z
T	19	328	16	Q
U	20	345	7	H
V	21	362	24	Y
W	22	379	15	P
X	23	396	6	G
Y	24	413	23	X
Z	25	430	14	O

展示 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=aa^{-1}\mod {m}.

$a$ 之乘法逆元素僅存在於 $a$ 與 $m$ 互質條件下。由此，沒有 $a$ 的限制，可能無法解密。易知解密方程逆於加密方程。

{\begin{aligned}{\mbox{D}}({\mbox{E}}(x))&=a^{-1}({\mbox{E}}(x)-b)\mod {m}\\&=a^{-1}(((ax+b)\mod {m})-b)\mod {m}\\&=a^{-1}(ax+b-b)\mod {m}\\&=a^{-1}ax\mod {m}\\&=x\mod {m}.\end{aligned}}

弱處

Since the affine cipher is still a monoalphabetic substitution cipher, 其依舊保留了該類別加密之弱處。當 $a=1$ ，仿射加密為 Caesar cipher ，因該加密方程可簡化為線性移動。考慮加密英文。(i.e. $m=26$ )，不計26易凱薩密碼，總共有286非易仿射密碼。此數值是由於小於26之數中有12數與26互質。 ( $a$ 的可能值). Each value of $a$ 可有26互異之加法移動( $b$ 之值); 因此，共有 12*26 或 312 可能之關鍵值。 This lack of variety renders the system as highly insecure when considered in light of Kerckhoffs' Principle.

此密碼之首要弱處為，如密碼學家可發現(如 frequency analysis, 暴力解, 臆測或任何其他方法) 加密文件兩字元之原文，則關鍵值可透過解一方程組得到。 Since we know $a$ and $m$ are relatively prime this can be used to rapidly discard many "偽" keys in an automated system.

仿射密碼中同種的轉換使用於 linear congruential generator，為虛擬隨機數產生器其中一種。此產生器不為安全加密虛擬隨機數產生器，因仿射密碼不安全。

範例

在以下一加密一解密的例子中，字母為從Ａ至Ｚ，且在表格中都有對應值。

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

加密

在加密範例中，,^[1] 使用前述表格中各字母對應之數值可知欲加密的原文件為 "AFFINE CIPHER" ， $a$ 對應5, $b$ 對應 8, 而 $m$ 對應 26 （因共使用26字母）。只有 $a$ 之值has a restriction since it has to be coprime with 26. $a$ 的所有可能值有 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 與 25。若 $a$ 不等於 1， $b$ 之值可隨機選定， as long as since this is the shift of the cipher. 所以，此加密範例的函數為 $y=E(x)=(5x+8){\pmod {26}}$ . 加密訊息的首步即為寫出每個字母的數字值。

plaintext:	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的餘數。以下表格為加密的首四步驟。

plaintext:	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。伊始之時，寫下加密文件中對應各字母之數值，如以下表格所示：

ciphertext:	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的餘數。以下表格顯示兩者計算後的結果。 {| class="wikitable" border="1" |- | ciphertext: | 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 程式語言，以下代碼可用於加密羅馬字母Ａ至Ｚ。

#Prints a transposition table for an affine cipher.
#a must be coprime to m=26.
def affine(a, b):
    for i in range(26):
        print chr(i+65) + ": " + chr(((a*i+b)%26)+65)

#An example call
affine(5, 8)

Or in 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:

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.

In 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);