仿射密碼

维基百科,自由的百科全书
跳转至: 导航搜索
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},其中

  • am互質
  • 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 為字母系統大小且 ab 為密碼關鍵值。 a 之值必須使得 am 互質. 解密方程為

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

此處 a^{-1}a 取模 m模反元素 of I.e., 滿足等式

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

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


\begin{align}
\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{align}

弱處[编辑]

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至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" ,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 程式語言,以下代碼可用於加密羅馬字母A至Z。

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



參見[编辑]


外部链接[编辑]

  1. ^ Kozdron, Michael. Affine Ciphers. [22 April 2014].