仿射密碼
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 |
仿射密碼是一種替換密碼。它是一個字母對一個字母的。
它的加密函數是,其中
- 和互質。
- 是字母的數目。
解碼函數是,其中是在群的乘法逆元。
仿射密碼 為 單表加密的一種,字母系統中所有字母都藉一簡單數學方程加密,對應至數值,或轉回字母。 其仍有所有替代密碼之弱處。所有字母皆藉由方程 加密, 為移動大小。
介紹
[编辑]於仿射加密中,大小為 之字母系統首先對應至 範圍內之數值, 接著使用模算數來將原文件中之字母轉換為對應加密文件中的數字。 單一字母的加密函數為
取餘 為字母系統大小且 和 為密碼關鍵值。 之值必須使得 與 互質. 解密方程為
之乘法逆元素僅存在於 與 互質條件下。 由此,沒有 的限制,可能無法解密。 易知解密方程逆於加密方程。
弱處
[编辑]因爲仿射密碼仍爲單字母表密碼, 其依舊保留了該類別加密之弱處。當 ,仿射加密為 凱撒密碼 ,因該加密方程可簡化為線性移動。 考慮加密英文。(即: ),不計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);
參見
[编辑]- 仿射變換
- 凱撒密碼:的特殊情況
- Atbash code
- ROT13
參考文獻
[编辑]- ^ Kozdron, Michael. Affine Ciphers (PDF). [22 April 2014]. (原始内容存档 (PDF)于2016-04-09).
外部链接
[编辑]
|