Transposition

出自KMU Wiki

所有密碼學中的加密演算法都是以列兩原則為基礎：取代(substitution)與置換(transposition)。取代指的是明文(原始訊息，密文則為編碼過的訊息)中的每一個元素(一個位元、一個字母、一組位元、或是一組字母)都被對應到另一個元素。而置換密碼(permutation cipher)，又稱換位密碼（transposition cipher)：指的是明文的字母保持相同，但將明文中的元素順序重新排列。加密的基本要求是不流失任何資訊，絕大部分的生產系統都會引用好幾回的取代與置換。

在本世紀之前，大多數密碼系統都基於字元置換或字元換位元（稱為置換密碼和換位元密碼）。最著名的傳統密碼可能就是凱撒密碼，通常認為這是最先發明的加密演算法之一。在凱撒密碼中，透過將每個字母按照字母表向下旋轉固定次數來將明文訊息轉換成密文。當使用一個字元的旋轉時，將把字母 "A" 加密成 "B"，把 "B" 加密成 "C"，把 "Z" 加密成 "A"。例如，旋轉一個字元之後，字串 "HELLO WORLD" 將變成 "IFMMP XPSME"。在該演算法中，有 25 個金鑰（在使用英文的情況下）可以確定每個字元旋轉的字母數。如果攻擊者知道使用的密碼，那麼嘗試 25 個可能的解碼來尋找金鑰並不會花多長時間。大多數情況下，只有一種解碼有意義。
凱撒密碼是 置換密碼 的一個特殊情況。最簡單的置換密碼是字母表上 26 個字母的置換。在沒有電腦的社會中，很明顯，蠻力攻擊不可行。儘管如此，如果有足夠的密文，這樣的密碼往往不難攻破。關鍵是計算密文中每個字母出現的案例。既然 E 是英語中最常用的字母，那麼給定一個足夠大的密文，該純文字中最常出現的字母很可能就是 E。如果不是，那可能是 A、I 或 O。傳統密碼專家只用十幾個密碼字母就能很快地進行這種統計攻擊。

置換密碼可以隨意變得更複雜，希望這可以從密文中除去可導致簡單分析的元素。例如，可以使用這樣的密碼︰同一密文根據上下文不同而代表不同明文字母，以使對密文的統計分析難以進行。可以使一個密文位元映射成多個明文位元的組合。還可以「級聯」加密，以便一個位元的加密取決於前一位元的解密。

置換是傳統密碼中的主要原始方法，但是置換字元的實際位置是另一種原始方法。大多數現代密碼演算法建置在這些相同的基本準則之上。它們的區別在於︰現代演算法執行的置換和換位要多得多。當然，傳統演算法要由手動應用。即使是相當簡單的密碼和相當短的訊息，加密和解密一條訊息也很費時間。然後出現了電腦（在電腦的首要使用中密表將碼術用得很多）。電腦可以使用經過大量置換次序處理的更複雜演算法，同時加密和解密速度還比人工快許多。以那種方式，現代密碼遠遠超出了傳統密碼。