跳转到内容

仿射密码

维基百科,自由的百科全书
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). 

外部链接