查看“︁仿射密碼”︁的源代码

<div class="thumb tright">
<div align="center;" class="thumbinner">
{|bgcolor="#ffffff" class="wikitable"
|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
|}
<div class="thumbcaption" style="width:100px;">展示 17x+5 的仿射密碼。首先字母被轉換成介於0到25的數字，下一步對每個套用 17x+5，結果再取除26後的餘數，最後再轉回字母。</div>
</div>
</div>

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

它的加密函數是<math>e(x)=ax+b\pmod{m}</math>，其中

* <math>a</math>和<math>m</math>[[互質]]。
* <math>m</math>是字母的數目。

解碼函數是<math>d(x)=a^{-1}(x-b)\pmod{m}</math>，其中<math>a^{-1}</math>是<math>a</math>在<math>\mathbb{Z}_{m}</math>群的[[乘法逆元]]。

'''仿射密碼''' 為 [[單表加密]]的一種，字母系統中所有字母都藉一簡單數學方程加密，對應至數值，或轉回字母。 其仍有所有替代密碼之弱處。所有字母皆藉由方程 <math>(ax+b)\mod(26)</math>加密， <math>b</math> 為移動大小。

==介紹==
於仿射加密中，大小為 <math>m</math> 之字母系統首先對應至 <math>0 .. m-1</math>範圍內之數值， 接著使用[[模算數]]來將原文件中之字母轉換為對應加密文件中的數字。
單一字母的加密函數為 
:<math>\mbox{E}(x)=(ax+b)\mod{m},</math>
取餘 <math>m</math> 為字母系統大小且 <math>a</math> 和 <math>b</math> 為密碼關鍵值。 <math>a</math> 之值必須使得 <math>a</math> 與 <math>m</math> [[互質]]. 解密方程為
:<math>\mbox{D}(x)=a^{-1}(x-b)\mod{m},</math>
此處 <math>a^{-1}</math>為 <math>a</math> [[模算數|取模]] <math>m</math>之[[模反元素]] of I.e., 滿足等式 
:<math>1 = a a^{-1}\mod{m}.</math>
<math>a</math>之乘法逆元素僅存在於 <math>a</math> 與 <math>m</math>互質條件下。 由此，沒有 <math>a</math> 的限制，可能無法解密。
易知解密方程逆於加密方程。
:<math>
\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}</math>

==弱處==
因爲仿射密碼仍爲單字母表密碼，其依舊保留了該類別加密之弱處。當 <math>a=1</math>，仿射加密為[[凱撒密碼]]，因該加密方程可簡化為線性移動。

考慮加密英文。（即： <math>m=26</math>），不計26易凱薩密碼，總共有286非易仿射密碼。此數值是由於小於26之數中有12數與26互質。（<math>a</math>的可能值）。<math>a</math> 的每個值可有26互異之加法移動（<math>b</math> 之值）；因此，共有 12*26 或 312 可能之關鍵值。因为密码缺少复杂性，根据[[柯克霍夫原則]]，这套系统是不安全的。

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

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

==範例==
在以下一加密一解密的例子中，字母為從Ａ至Ｚ，且在表格中都有對應值。
{| class="wikitable" border="1"
|-
! 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
|}

===加密===
在加密範例中，<ref>{{cite web | url=//www.math.cornell.edu/~kozdron/Teaching/Cornell/135Summer06/Handouts/affine.pdf | title=Aﬃne Ciphers | accessdate=22 April 2014 | author=Kozdron, Michael | archive-date=2016-04-09 | archive-url=https://web.archive.org/web/20160409141219/http://www.math.cornell.edu/~kozdron/Teaching/Cornell/135Summer06/Handouts/affine.pdf | dead-url=no }}</ref> 使用前述表格中各字母對應之數值可知欲加密的原文件為 "AFFINE CIPHER" ，<math>a</math> 對應5, <math>b</math> 對應 8, 而 <math>m</math> 對應 26 （因共使用26字母）。其中<math>a</math>之值必須與<math>m</math>的值26互質，所以其所有可能值包含1、3、5、7、9、11、15、17、19、21、23、25。若<math>a \neq 1 </math>，則<math>b</math>之值可隨機選定（因為b只讓密文值平移而已）。所以，此加密範例的函數為 <math> y=E(x)=(5x+8)\pmod{26}</math>.  加密訊息的首步即為寫出每個字母的數字值。
{| class="wikitable" border="1"
|-
|原始文件:
| 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各值並解等式的第一部份， <math>(5x+8)</math>。 得出各字母對應<math>(5x+8)</math>的值後，取其對26的餘數。以下表格為加密的首四步驟。
{| class="wikitable" border="1"
|-
|原始文件:
| 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
|-
| <math>5x+8</math>
| 8
| 33
| 33
| 48
| 73
| 28
| 18
| 48
| 83
| 43
| 28
| 93
|-
| <math>(5x+8)\pmod{26}</math>
| 8
| 7
| 7
| 22
| 21
| 2
| 18
| 22
| 5
| 17
| 2
| 15
|}

加密訊息的最後一部，為查表求得對應字母的數值。 在此範例中，加密文本應為 IHHWVCSWFRCP。 以下表格顯示仿射加密一訊息的完整表格。
{| class="wikitable" border="1"
|-
|原始文件:
| 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
|-
| <math>5x+8</math>
| 8
| 33
| 33
| 48
| 73
| 28
| 18
| 48
| 83
| 43
| 28
| 93
|-
| <math>(5x+8)\pmod{26}</math>
| 8
| 7
| 7
| 22
| 21
| 2
| 18
| 22
| 5
| 17
| 2
| 15
|-
| 加密文件:
| I
| H
| H
| W
| V
| C
| S
| W
| F
| R
| C
| P
|}

===解密===
於此解密範例中，欲解密之加密文件來自加密範例 。其解密方程為 <math>\mbox{D}(y)=21(y-8)\mbox{ mod }26</math>，經過計算， <math>a^{-1}</math> 為 21, <math>b</math> 為8, <math>m</math> 為 26。伊始之時，寫下加密文件中對應各字母之數值，如以下表格所示：
{| class="wikitable" border="1"
|-
| 密文:
| 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
|}

下一步，計算 <math>21(y-8)</math>，再取結果除以26的餘數。以下表格顯示兩者計算後的結果。

{| class="wikitable" border="1"
|-
| 密文:
| 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。  以下為完成解密後的表格：
{| class="wikitable" border="1"
|-
|加密文件：
| 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
|}

===全數字母加密===
為求加解密更快速，可加密全數字母以將原文件之字母一對一對應至加密文件。此範例中，一對一映射如下：
{| class="wikitable" border="1"
|-
! 原文件中字母
! 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]] 程式語言，以下代碼可用於加密羅馬字母Ａ至Ｚ。 <syntaxhighlight lang="python">
# 列印仿射密碼的字母表。
# a必須與m互質
def affine(a, b):
    for i in range(26):
        print chr(i+65) + ": " + chr(((a*i+b)%26)+65)

# 調用函數的例子
affine(5, 8)
</syntaxhighlight>
或者以[[Java]]作例:
<syntaxhighlight lang="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)
</syntaxhighlight>

或於 [[Pascal語言|Pascal]]:
<syntaxhighlight lang="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.
</syntaxhighlight>

在 [[PHP]]的實現:
<syntaxhighlight lang="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);
</syntaxhighlight>

==參見==
* [[仿射變換]]
* [[凱撒密碼]]：<math>a=1</math>的特殊情況
* [[Atbash|Atbash code]]
* [[ROT13]]

==參考文獻==
{{Reflist}}

==外部链接==
* [http://nextprime.sitecloud.cytanium.com/cipher/affine.html 在线仿射密码计算器]{{dead link|date=2017年11月 |bot=InternetArchiveBot |fix-attempted=yes }} {{en icon}}

{{Cryptography navbox|classical}}

[[Category:古典密码]]