替代密碼是指先建立一個替換表，加密時將需要加密的明文依次通過查表，替換為相應的字元，明文字元被逐個替換後，生成無任何意義的字元串，即密文，替代密碼的密鑰就是其替換表 。
基本介紹
- 中文名：替代密碼
- 外文名：Substitution Cipher
- 分類：單表替代密碼和多表替代密碼
- 作用：加密
定義,替代密碼的分類,單表替代密碼,多表替代密碼,
定義
替代是古典密碼中用到的最基本的處理技巧之一 。
替代密碼是指先建立一個替換表，加密時將需要加密的明文依次通過查表，替換為相應的字元，明文字元被逐個替換後，生成無任何意義的字元串，即密文，替代密碼的密鑰就是其替換表 。
替代密碼的分類
根據密碼算法加解密時使用替換表多少的不同，替代密碼又可分為單表替代密碼和多表替代密碼。
單表替代密碼的密碼算法加解密時使用一個固定的替換表。單表替代密碼又可分為一般單表替代密碼、移位密碼、仿射密碼、密鑰短語密碼。
多表替代密碼的密碼算法加解密時使用多個替換表。 多表替代密碼有維吉尼亞密碼、希爾(Hill)密碼、一次一密鑰密碼、Playfair密碼。
單表替代密碼
單表替代密碼對明文中的所有字母都使用一個固定的映射（明文字母表到密文字母表）。設A={a0, a1,…, an-1}為包含了n個字母的明文字母表；
B={b0, b1,…, bn-1} 為包含n個字母的密文字母表，單表替代密碼使用了A到B的映射關係：f：A→B， f ( ai )= bj
一般情況下，f 是一一映射，以保證加密的可逆性。加密變換過程就是將明文中的每一個字母替換為密文字母表的一個字母。而單表替代密碼的密鑰就是映射f或密文字母表。經常密文字母表與明文字母表的字元集是相同的，這時的密鑰就是映射f。下面給出幾種典型的單表替代密碼。
⒈一般單表替代密碼
一般單表替代密碼的原理是以26個英文字母集合上的一個置換π為密鑰，對明文訊息中的每個字母依次進行變換。可描述為：明文空間M和密文空間C都是26個英文字母的集合，密鑰空間K={π：Z26→Z26|π是置換}，是所有可能置換的集合。
對任意π∈K，定義:
加密變換：eπ(m)=π(m)=c
解密變換：dπ(c) = π-1(c)=m， π-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
q w e r t y u i o p a s d f g h j k l z x c v b n m
試用單表替代密碼以π為密鑰對明文訊息message加密，然後寫出逆置換 ，並對密文解密。
解：以π為密鑰用單表替代密碼對明文訊息message加密，所得
密文訊息為： π(m) π(e) π(s) π(s) π(a) π(g) π(e)=dtllqut
一般單表替代密碼算法特點：
▲密鑰空間K很大，|K|=26!=4×10^26 ，破譯者窮舉搜尋計算不可行，1微秒試一個密鑰，遍歷全部密鑰需要1013 年。
▲移位密碼體制是替換密碼體制的一個特例，它僅含26個置換做為密鑰空間。
密鑰π不便記憶。
▲針對一般替換密碼密鑰π不便記憶的問題，又衍生出了各種形式單表替代密碼。
⒉移位密碼
明文空間M、密文空間C都是和密鑰空間K滿足，即把26個英文字母與整數0，1，2，…，25一一對應。
加密變換，E={E:Z26→Z26, Ek (m) = m + k (mod26)| m∈M, k∈K }
解密變換，D={D:Z26→Z26, Dk (c) = c－k (mod26)| c∈C, k∈K }
解密後再把Z26中的元素轉換英文字母。
顯然，移位密碼是前面一般單表替代密碼的一個特例。當移位密碼的 密鑰k=3時，就是歷史上著名的凱撒密碼（Caesar）。根據其加密函式特 點，移位密碼也稱為加法密碼。
⒊仿射密碼
仿射密碼也是一般單表替代密碼的一個特例，是一種線性變換。仿射密碼的明文空間和密文空間與移位密碼相同，但密鑰空間為 K={(k1，k2)| k1，k2∈Z26，gcd(k1，26)=1}
對任意m∈M，c∈C，k = (k1，k2)∈K，定義加密變換為 c = Ek (m) = k1 m +k2 (mod 26)
相應解密變換為： m = Dk (c) = k1 (c－k2) (mod 26)
其中，K1 k1=1mod26 。很明顯，k1=1時即為移位密碼，而k2=1則稱為乘法密碼。
⒋密鑰短語密碼
選用一個英文短語或單詞串作為密鑰，去掉其中重複的字母得到一個無重複字母的字元串，然後再將字母表中的其它字母依次寫於此字母串後，就可構造出一個字母替代表。當選擇上面的密鑰進行加密時，若明文為“china”，則密文為“yfgmk”。顯然，不同的密鑰可以得到不同的替換表，對於明文為英文單詞或短語的情況時，密鑰短語密碼最多可能有26!=4×1026個不同的替換表。
多表替代密碼
單表替代密碼錶現出明文中單字母出現的頻率分布與密文中相同， 多表替代密碼使用從明文字母到密文字母的多個映射來隱藏單字母出現 的頻率分布，每個映射是簡單替代密碼中的一對一映射多表替代密碼將 明文字母劃分為長度相同的訊息單元，稱為明文分組，對明文成組地進 行替代，同一個字母有不同的密文，改變了單表替代密碼中密文的唯一 性，使密碼分析更加困難。
多表替代密碼的特點是使用了兩個或兩個以上的替代表。著名的維吉尼亞密碼和Hill密碼等均是多表替代密碼。
⒈維吉尼亞密碼
維吉尼亞密碼是最古老而且最著名的多表替代密碼體制之一，與位移密碼體制相似，但維吉尼亞密碼的密鑰是動態周期變化的。
該密碼體制有一個參數n。在加解密時，同樣把英文字母映射為0－25的數字再進行運算，並按n個字母一組進行變換。明文空間、密文空間及密鑰空間都是長度為n的英文字母串的集合，因此可表示
加密變換定義如下：
設密鑰 k=(k1,k2,…,kn), 明文m=(m1,m2,…,mn), 加密變換為：
Ek(m)=(c1,c2,…,cn),
其中ci(mi + ki)(mod26)，i =1,2,…,n
對密文 c=(c1,c2,…,cn), 解密變換為：
Dk(c)=(m1,m2,…,mn), 其中 mi=(ci －ki)(mod26)，i =1,2,…,n
⒉希爾（Hill）密碼
Hill密碼算法的基本思想是將n個明文字母通過線性變換，將它們轉換為n個密文字母。解密只需做一次逆變換即可。
⒊一次一密密碼（One Time Pad）
若替代碼的密鑰是一個隨機且不重複的字元序列，這種密碼則稱為一次一密密碼，因為它的密鑰只使用一次。該密碼體制是美國電話電報公司的Joseph Mauborgne在1917年為電報通信設計的一種密碼，所以又稱為Vernam密碼。Vernam密碼在對明文加密，前首先將明文編碼為（0，1）序列，然後再進行加密變換。
設m=(m1 m2 m3 … mi …)為明文,k=(k1 k2 k3 … ki …)為密鑰,其中mi,ki ∈(0,1), i≥1, 則加密變換為： c=(c1 c2 c3 … ci …) ,其中ci = mi Å ki , i≥1,
這裡為模2加法（或異或運算）
解密變換為：
m=(m1 m2 m3 … mi …) ,其中mi = ci Å ki , i≥1,
在套用Vernam密碼時，如果對不同的明文使用不同的隨機密鑰，這時Vernam密碼為一次一密密碼。由於每一密鑰序列都是等機率隨機產生的，敵手沒有任何信息用來對密文進行密碼分析。香農（Claude Shannon）從資訊理論的角度證明了這種密碼體制在理論上是不可破譯的。但如果重複使用同一個密鑰加密不同的明文，則這時的Vernam密碼就較為容易破譯。
若敵手獲得了一個密文c=(c1 c2 c3 … ci …) 和對應明文m=(m1 m2 m3 … mi …) 時，就很容易得出密鑰 k=(k1 k2 k3 … ki …) ，其中ki = ciÅ mi，i≥1。 故若重複使用密鑰，該密碼體制就很不安全。
實際上Vernam密碼屬於序列密碼，加密解密方法都使用模2加，這使軟
硬體實現都非常簡單。但是，這種密碼體制雖然理論上是不可破譯的，然而
在實際套用中，真正的一次一密系統卻受到很大的限制，其主要原因在於該
密碼體制要求：
① 密鑰是真正的隨機序列；
② 密鑰長度大於等於明文長度；
③ 每個密鑰只用一次（一次一密）。
這樣，分發和存儲這樣的隨機密鑰序列，並確保密鑰的安全都是很因難
的；另外，如何生成真正的隨機序列也是一個現實問題。因此，人們轉而尋
求實際上不對攻破的密碼系統。
