跳转到内容

仿射密碼

维基百科,自由的百科全书
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後的餘數,最後再轉回字母。

仿射密碼是一種替換密碼。它是一個字母對一個字母的。

它的加密函數是,其中

  • 互質
  • 是字母的數目。

解碼函數是,其中群的乘法逆元

仿射密碼單表加密的一種,字母系統中所有字母都藉一簡單數學方程加密,對應至數值,或轉回字母。 其仍有所有替代密碼之弱處。所有字母皆藉由方程 加密, 為移動大小。

介紹

於仿射加密中,大小為 之字母系統首先對應至 範圍內之數值, 接著使用模算數來將原文件中之字母轉換為對應加密文件中的數字。 單一字母的加密函數為

取餘 為字母系統大小且 為密碼關鍵值。 之值必須使得 互質. 解密方程為

此處 取模 模反元素 of I.e., 滿足等式

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

弱處

因爲仿射密碼仍爲單字母表密碼, 其依舊保留了該類別加密之弱處。當 ,仿射加密為 凱撒密碼 ,因該加密方程可簡化為線性移動。 考慮加密英文。(即: ),不計26易凱薩密碼,總共有286非易仿射密碼。此數值是由於小於26之數中有12數與26互質。 (的可能值). 的每個值可有26互異之加法移動( 之值); 因此,共有 12*26 或 312 可能之關鍵值。 因为密码缺少复杂性,根据柯克霍夫原則,这套系统是不安全的。

此密碼之首要弱處為,如果密碼學家可發現(如 頻率分析, 暴力破解, 臆測或任何其他方法) 加密文件兩字元之原文,則關鍵值可透過解一方程組得到。 由於我們知道 互質,這個事實可被用於快速破解密碼。

仿射密碼中同種的轉換使用於線性同餘方法,為伪随机数生成器中的一種。此產生器不為密码学安全伪随机数生成器,因仿射加密不安全。

範例

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

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" , 對應5, 對應 8, 而 對應 26 (因共使用26字母)。其中之值必須與的值26互質,所以其所有可能值包含1、3、5、7、9、11、15、17、19、21、23、25。若,則之值可隨機選定(因為b只讓密文值平移而已)。所以,此加密範例的函數為 . 加密訊息的首步即為寫出每個字母的數字值。

原始文件: 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各值並解等式的第一部份, 。 得出各字母對應的值後,取其對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
8 33 33 48 73 28 18 48 83 43 28 93
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
8 33 33 48 73 28 18 48 83 43 28 93
8 7 7 22 21 2 18 22 5 17 2 15
加密文件: I H H W V C S W F R C P

解密

於此解密範例中,欲解密之加密文件來自加密範例 。其解密方程為 ,經過計算, 為 21, 為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

下一步,計算 ,再取結果除以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 程式語言,以下代碼可用於加密羅馬字母A至Z。

# 列印仿射密碼的字母表。
# 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作例:

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.

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

參見

參考文獻

  1. ^ Kozdron, Michael. Affine Ciphers (PDF). [22 April 2014]. (原始内容存档 (PDF)于2016-04-09). 

外部链接