替換密碼演算法

A. 替代密碼的替代密碼的分類

根據密碼演算法加解密時使用替換表多少的不同，替代密碼又可分為單表替代密碼和多表替代密碼。
單表替代密碼的密碼演算法加解密時使用一個固定的替換表。單表替代密碼又可分為一般單表替代密碼、移位密碼、仿射密碼、密鑰短語密碼。
多表替代密碼的密碼演算法加解密時使用多個替換表。 多表替代密碼有弗吉尼亞密碼、希爾(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加，這使軟
硬體實現都非常簡單。但是，這種密碼體制雖然理論上是不可破譯的，然而
在實際應用中，真正的一次一密系統卻受到很大的限制，其主要原因在於該
密碼體制要求：
① 密鑰是真正的隨機序列；
② 密鑰長度大於等於明文長度；
③ 每個密鑰只用一次（一次一密）。
這樣，分發和存儲這樣的隨機密鑰序列，並確保密鑰的安全都是很因難
的；另外，如何生成真正的隨機序列也是一個現實問題。因此，人們轉而尋
求實際上不對攻破的密碼系統。
⒋Playfair密碼
Playfair密碼是一種著名的雙字母單表替代密碼，實際上Playfair密碼屬於一種多字母替代密碼，它將明文中的雙字母作為一個單元對待，並將這些單元轉換為密文字母組合。替代時基於一個5×5的字母矩陣。字母矩陣構造方法同密鑰短語密碼類似，即選用一個英文短語或單詞串作為密鑰，去掉其中重復的字母得到一個無重復字母的字元串，然後再將字母表中剩下的字母依次從左到右、從上往下填入矩陣中，字母I，j占同一個位置。

B. 希爾密碼原理

希爾密碼（Hill Cipher）是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。每個字母當作26進制數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果MOD26。

中文名
希爾密碼
外文名
Hill Cipher
原理
基本矩陣論
類別
替換密碼
提出者
Lester S. Hill
快速
導航
產生原因

原理

安全性分析

例子
簡介
希爾密碼是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。
每個字母當作26進制數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果模26。
注意用作加密的矩陣（即密匙）在必須是可逆的，否則就不可能解碼。只有矩陣的行列式和26互質，才是可逆的。
產生原因
隨著科技的日新月異和人們對信用卡、計算機的依賴性的加強，密碼學顯得愈來愈重要。密碼學是一門關於加密和解密、密文和明文的學科。若將原本的符號代換成另一種符號，即可稱之為廣義的密碼。狹義的密碼主要是為了保密，是一種防止竊文者得知內容而設的另一種符號文字，也是一般人所熟知的密碼。
使用信用卡、網路賬號及密碼、電子信箱、電子簽名等都需要密碼。為了方便記憶，許多人用生日、電話號碼、門牌號碼記做密碼，但是這樣安全性較差。
為了使密碼更加復雜，更難解密，產生了許多不同形式的密碼。密碼的函數特性是明文對密碼為一對一或一對多的關系，即明文是密碼的函數。傳統密碼中有一種叫移位法，移位法基本型態是加法加密系統C=P+s(mod m)。一般來說，我們以1表示A，2表示B，……，25表示Y，26表示Z，以此類推。由於s=0時相當於未加密，而0≤s≤m-1（s≥m都可用0≤s≤m-1取代），因此，整個系統只有m-1種變化。換言之，只要試過m-1次，機密的信息就會泄漏出去。
由此看來，日常生活中的密碼和傳統的密碼的可靠性較差，我們有必要尋求一種容易將字母的自然頻度隱蔽或均勻化，從而有利於統計分析的安全可靠的加密方法。希爾密碼能基本滿足這一要求。
原理
希爾加密演算法的基本思想是，將d個明文字母通過線性變換將它們轉換為d個密文字母。解密只要作一次逆變換就可以了，密鑰就是變換矩陣本身。[1]
希爾密碼是多字母代換密碼的一種。多字母代換密碼可以利用矩陣變換方便地描述，有時又稱為矩陣變換密碼。令明文字母表為Z，若採用L個字母為單位進行代換，則多碼代換是映射f：Z→Z。若映射是線性的，則f是線性變換，可以用Z上的L×L矩陣K表示。若是滿秩的，則變換為一一映射，且存在有逆變換K。將L個字母的數字表示為Z上的L維矢量m，相應的密文矢量c，且mK=c，以K作為解密矩陣，可由c恢復出相應的明文c·K=m。
在軍事通訊中，常將字元（信息）與數字對應（為方便起見，我們將字元和數字按原有的順序對應，事實上這種對應規則是極易被破解的）：
abcde…x y z
12345…242526
如信息「NOSLEEPPING」對應著一組編碼14,15,19,12,5,5,16,16,9,14,7。但如果按這種方式直接傳輸出去，則很容易被敵方破譯。於是必須採取加密措施，即用一個約定的加密矩陣K乘以原信號B，傳輸信號為C=KB（加密），收到信號的一方再將信號還原（破譯）為B=KC。

C. 凱撒密碼為一種替換密碼，此題的加密過程為先進行base64編碼，再進行移

在密碼學中，愷撒密碼（或稱愷撒加密、愷撒變換、變換加密）是一種最簡單且最廣為人知的加密技術。它是一種替換加密的技術，明文中的所有字母都在字母表上向後（或向前）按照一個固定數目進行偏移後被替換成密文。
愷撒密碼的加密、解密方法還能夠通過同餘的數學方法進行計算。首先將字母用數字代替，A=0，B=1，...，Z=25。此時偏移量為n的加密方法即為： E(x) = (x + n) mod 26.
解密就是：
D(x) = (x - n) mod 26.
顯而易見，一旦確定了某兩個字母的對應關系（即n的值），這種移位密碼很容易被破解。
因此，為了使密碼有更高的安全性，單字母替換密碼就出現了。
明碼表: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
密碼表:T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
但是這種加密方式依然可以破解，根據字母使用頻度表，分析密文中的字母頻率，將其對照即可破解。
不僅如此，凱撒加密對加密數據也是有要求的，一般情況下，它只支持對基本的英文字母進行加密，如果對中文等亞太地區的文字進行加密，結果可想而知，你的隱私將毫無保留的出現在眾人面前。有人說，我們可以擴展這個演算法，使它支持所有的文字，這么做是可行的，如果採用同餘式的方式實現，代碼幾乎不怎麼需要改動，只要字元集本身是Unicode就可以了。但是這種加密的安全性很難滿足應用的要求。如果採用單字母替換的方式，程序將需要構建兩個巨大的字元數組去保存他們的映射關系，而且擴展性也不好，當然也是不可行的。這樣看來，凱撒加密豈不是一無是處了，其實對於一般的應用，凱撒加密還是足以應付的，只要我們對它稍作改進。

D. 為什麼說加法密碼、乘法密碼、仿射密碼、置換密碼、Hill密碼以及Vigenere密碼

加法密碼就是真典密碼學中的愷撒密碼格式是：密文=(明文+密鑰)mod26,剩法密碼是愷撒密碼發展出來，格式是：密文=明文x實鑰mon26；置換密碼就是在簡單的縱行換位密碼中，明文以固定的寬度水平的寫在一張圖表紙上，密文按垂直方向讀出，解密就是密文按相同的寬度垂直的寫在圖表紙上，然後水平的讀出明文。希爾密碼（Hill Cipher）是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。每個字母當作26進制數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果MOD26；Vigenere是愷撒密碼演變而來。使用一系列凱撒密碼組成密碼字母表的加密演算法，屬於多表密碼的一種簡單形式。
有興趣可以了解一下古典密碼學，這裡面都有。

E. 替換式密碼的諧音替換法

早期的加密中，為增加替換式密碼應付頻率分析攻擊的強度，有時會採用「諧音」來改變明文字母頻率。在這種加密演算法中，明文字母可以映射到多個密文符號。通常情況下，頻率最高的明文符號（如E）會比低使用頻率的字母（如X）有更多的諧音符號，使頻率分布更為平坦，讓分析更困難。
但亦因此，只是字母之間互相替換就會造成不夠分配，從而有了好幾種不同的解決方法。其中最簡單的方式可以算是用1-0共10個數字作為某些字母的替換。另一種方法則是將現有的字母分開成原字母配以簡單的變化、大寫、小寫、上下倒轉的字母、鏡像文字（左右倒轉）等。雖然更為藝術化，卻不代表一定更安全，其中一些諧音替換法全部使用新發明的奇特符號來代表字母。
一種有趣的變化名為命名密碼法（英語：nomenclator）。此加密法有許多不同的版本，之間的區別來自其前綴。而該前綴來自宣讀來訪貴賓稱號的公職人員名字。這種密碼結合一個小型密碼本（英語：Codebook）組成一個大型的諧音替換表。在此密碼中，常用單詞會按密碼本加密，餘下字母則按另一本密碼本加密，兩者符號最後在密文中混起來，以減低簡易替換密碼中被破解的風險。路易十四所使用的密碼是羅西諾爾家族（英語：Rossignols）創立的偉大密碼，該密碼直至法國王室廢止後百年才被破解。
15世紀早期至18世紀後期，命名密碼是外交文件及間諜最常使用的加密，然而其中大多數仍然使用加密性能較差的命名密碼。雖然由十六世紀中葉開始政府情報機構的密碼分析員就破解部分命名密碼法，但使用者通常的反應僅僅是加大諧音替換表。十八世紀後期，諧音替換系統開始消亡之時，一些命名密碼已有高達5萬個符號。
然而，並非所有命名密碼法都已被破解。直到今天，仍然不時有新的命名密碼被破解的新聞。
比爾密碼是另一個諧音替換法的例子。這個故事指在1819年至1821年期間由一個加密文本來隱藏美國獨立宣言中所述的寶藏。在這里，每個密文字元由一個數字替換。數字代表著獨立宣言中第幾個字的第一個字母。獨立宣言中許多字的首字母都是一樣的，而密文數字能是其中任何一個，例如正文中第二和第六個字都是「I」開頭，即「I」既可以是2，又可以是6。而解讀僅僅就是把密文中的數字（如代數X），放到獨立宣言中查找（第X個字的首字母）。
斯塔爾則描述了另一個諧音替換密碼，其密碼是第一次嘗試在電腦的資料庫上加密。在斯塔爾的方法中，無論是明文還是密文都是以二進制字元串存儲，因此諧音的數量可以非常大，使得頻率分析比平常更為困難。
書本式加密（英語：Book cipher）與散列板都是諧音替換密碼的一種。

F. 替換式密碼的多表替換加密

在1467年，多表替換密碼由萊昂·巴蒂斯塔·阿爾伯蒂以圓碟的形式首次描述。約翰尼斯·特里特米烏斯所著的《隱寫術》（古希臘文：Steganographia）中介紹了一種表格（古希臘文：tableau）（見下；15世紀已完成但很久以後才出版）。1563年，喬瓦尼·巴蒂斯塔·德拉波爾塔（英語：Giovanni_Battista_della_Porta）在《書寫中的隱蔽字元》（古希臘文：De FurtivisLiterarum Notis）描述了一個更復雜的混合字母版本。
在一個多表替換密碼中，會使用多個字母作為密碼。為了加快加密或解密速度，所有的字母通常寫在一張表格上，密碼學上稱作tableau。這種表格通常是26×26，因為這樣才能放下全部26個英文字母。填充表格及選擇下次使用的字母的方法，就是不同多字母替換密碼之間的定義。多字母替換密碼比單字母更難打破，因為其替換可能性多，密文要較長才可。
其中最著名的一種為吉奧萬·巴蒂斯塔·貝拉索於1585年推出的維吉尼亞密碼。它於1863年之前一直未被破解。法國人稱它作「不能破譯的密碼」（法語：le chiffre indéchiffrable）。（此密碼曾被誤以為由布萊斯·德·維吉尼亞所創，所以才叫作維吉尼亞密碼。）
維吉尼亞密碼中，表格的第一行只需直接填上26個字母，然後以握帆空下每一行的字母都是向左偏移一格。（這叫作表格橫移，數學上每一列同餘26。）要用這種密碼需要使用一個關鍵字來作為密鑰。關鍵字每次用完就再次重復。假設關鍵字是「CAT」，明文的第一個字由「C」加密，第二個字由「A」加密，第三個則由「T」加密，然後再回到C加密，一直重復。然後按照右邊的密碼表加密，例如BALL用CAT作關鍵字時會加密至DAEN，可見即使是同一個「L」亦會加密至另一個字母。現實中，維吉尼亞密碼的關鍵字非常長。
1863年，弗里德里希·卡西斯基（英語：FriedrichKasiski）少校發明了一種方法（在克里米亞戰爭前已由查爾斯·巴貝奇秘密並獨立地發明），使得可以計算維吉尼亞密碼中關鍵字的長度。這種方法需要較長的密文，因為其運作依靠找出常見的字（如THE）使用相同關鍵字（如ABC）的數量，因此段瞎，極短的密文難以用此辦法找出。
因此，即使在轎兆今天，如果在表格中使用混合表加密，或關鍵字是隨機的，維吉尼亞密碼理論上亦難以破解。但由於實際上很難用到這些方法，維吉尼亞密碼的使用越來越少。
其他著名的多字母替換加密包括：
格蘭示菲特密碼 - 與維吉尼亞密碼相似，但由於整個密碼只使用10個單元，因此關鍵字長度有限，很容易被破解。博福特密碼 - 這實際上就是維吉尼亞密碼，除「tabula」改為向後偏移一格，數學上是等式為：密文=鍵－明文。博福特密碼屬於對等加密，即加密演算法與解密演算法相同。自動密鑰密碼 - 它的密鑰開頭是一個關鍵詞，之後則是明文的重復，以避免周期函數。運動密鑰密碼，關鍵詞從某些文章或名句中取出，因此可以非常長。
現代的流密碼中可以看出，現代的多表替換加密都努力改進流密鑰，使其盡可能的長及不可預知。