概念
愷撒密碼凱撒密碼II
在人類歷史上，對信息保護的需求與對信息本身的需求一樣久遠。第一個用於加密和解密文本的編碼方式是凱撒密碼。由於原始的凱撒密碼較簡單，較易被破解。隨著考古的進展，人們發現了升級版的凱撒密碼II。
凱撒密碼II通過查詢動態密碼錶，把凱撒單詞加密成一些密文數字。
如果請你使用現有動態密碼錶，加密一些單詞。你要處理m個操作，操作分成兩種：
Astringinteger:增加一條凱撒單詞string到凱撒密文數字integer的映射規則，如果先前已經有關於這個string的規則，那么用該規則替換原規則。
Qstring:查詢單詞string所對應的最新密文數字。
第一行一個整數m（1≤m≤1,000,000），表示有m個操作。
單詞僅有長度不超過8位的小寫字母組成，單詞總數不超過100,000個。
密文數字的範圍是[0..1,000,000,000]。
對於每組查詢，輸出一行，表示根據密碼錶中的規則，加密後的密文數字，如果在無法在密碼錶中查找到該單詞，輸出-1。
7Aaaab10Aaaac20Aaaad30QaaacAaaac40QaaaaQaaac
20
-1
40
凱撒密表
古羅馬隨筆作家修托尼厄斯在他的作品中披露，凱撒常用一種“密表”給他的朋友寫信。這裡所說的密表，在密碼學上稱為“凱撒密表”。用現代的眼光看，凱撒密表是一種相當簡單的加密變換，就是把明文中的每一個字母用它在字母表上位置後面的第三個字母代替。古羅馬文字就是現在所稱的拉丁文，其字母就是我們從英語中熟知的那26個拉丁字母。因此，凱撒密表就是用D代a，用E代b，……，用z代w，（注意！）用A代x，用B代y，C代z。這些代替規則也可用一張表格來表示（所以叫“密表”）。
例如，有這樣一個拉丁文例子
OmniaGalliaest
divisainPartestres
（高盧全境分為三部分）
用凱撒密表加密後，就成為密文
RPQLDJDOOLDHVW
GLYLVDLQSDUWHVWUHV
你看，不掌握其中奧妙，不知道凱撒密表，簡直不如所云。那么，在公元前54年，凱撒就是用這種密碼給西塞羅寫信的嗎?有趣的是，密碼界對這—點卻持否定態度，因為密碼學歷史上還記載著凱撒使用的另一種加密方法：把明文的拉丁字母逐個代之以相應的希臘字母，這種方法看來更貼近凱撒在《高盧戰記》中的記敘。顯然，哪一個拉丁字母應該代之以哪—個希臘字母，事先都有約定，凱撒知道，西塞羅也知道，不然的話，西塞羅收到密信後，也會不知所云。當阿里巴巴站在那四十一名大盜的山洞大門口，準備打開大門時，他必須知道一個咒語：“芝麻開門”。當我們站在密碼學的大門，準備邁入時，必須要知道的則是—些基本概念。為此，讓我們先把密碼通信的幾個要素總結如下。
在軍事通信上，必須考慮要傳送的秘密信息在傳送的途中被除發信者和收信者以外的第三者（特別是敵人）截獲的可能性使載送信息的載體（如文本、無線電被等）即使在被截獲的情況下也不會讓截獲者得知其中信息內容的通信方法或技術，稱為保密通信。密碼通信就是一種保密通信，它是把表達信息的意思明確的文字元號，用通信雙方事先所約定的變換規則，變換為另一串莫名其妙的符號，以此作為通信的文本傳送給收信者，當這樣的文本傳送到收信者手中時，收信者—時也不能識別其中所代表的意思，這時就要根據事先約定的變換規則，把它恢復成原來的意思明確的文字，然後閱讀。這樣，如果這個文本在通信途中被第三者截獲，由於第三者—般不知道那變換規則，因此他就不能得知在這一串符號背後所隱藏的信息。當然，為了戰爭的目的，他會千方百計地努力弄到這個變換規則。一種努力就是對已經截獲的密文進行分析，有時結合從其他途徑獲得的有關信息，試圖找出這個變換規則。
在密碼學中，我們要傳送的以通用語言明確表達的文字內容稱為明文，由明文經變換而形成的用於密碼通信的那一串符號稱為密文，把明文按約定的變換規則變換為密文的過程稱為加密，收信者用約定的變換規則把密文恢復為明文的過程稱為解密。敵方主要圍繞所截獲密文進行分析以找出密碼變換規則的過程，稱為破譯。
如在上一部分中，
OmniaGalliaestdivisainPartestres
就是一段明文，凱撒密表就是—種變換規則。這段明文經凱撒密表加密後，
就變成了密文
RPQLDJDOOLDHVWGLYLVDLQDUWHVWUHV。
收信者收到這段密文後，就要進行解密，解密也是用凱撒密表。在這個例子中，加密和解密都在用凱撒密表，但嚴格地說，加密時所用的變換與解密時所用的變換是兩個變換。這兩個變換間的關係是它們互為逆變換。也就是說，明文用其中一個變換進行加密產生密文後，若再用另一個變換對這密文進行解密，就會得到原來的明文。這種互逆的關係就如同我們所熟知的加法和減法互為逆運算的關係一樣：加上一個數後再減去同一個數，就等於不加也不減。
下面我們總結一下：
明密對照表：
明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文：TUVWXYZABCDEFGHIJKLMNOPQRS
註：廣義上的凱撒是位移的。
凱撒是沒有密匙的，即使沒有密匙也能將它破解出來，因為凱撒移位密碼只有25種密匙，最多就是將這25種可能性挨個檢測一下可以了，這就是我們所說的暴力破解法。也可在用軟體破解，不過我提倡用人工的。
推理的方法：
1，對於有空格的凱撒移位，單字母A和I是突破口，這無異相當於告訴了移動的位數，這樣很容易就被破解了。所以，如果我們要用凱撒密碼的話一定要去掉空格加大破解難度。
2，差數法。
有空格時，而又沒有單字母A和I時，這種方法很，如果我們令A=1,B=2,C=3......就是每個字母是字母的第幾個，經過移位後的單詞，每兩相鄰的字母之間的差值不變的。如the的差值為12,3（在這裡我是用後面的一個字母減前面的一個字母，當然你也可以用後面的一個字母減前面的一個字母），移動後兩個相鄰字母的差值也將會是12,3。
對於沒有空格的愷撒破解起來就比有空格的難一些，對於沒有空格的我們還要對密文進行分析，找出重複出現的字母串，然後對字母串進行猜測，例，如果有3個字母串，出現的次數比較高，我們就可以假設它為the因為3個字母串出現次最多的就是the，當然這不是一成不變的，這時應該就被破解了。
我們看到一個密碼怎樣判斷是凱撒密碼呢？這又要扯到頻率分析去（在這裡不介紹，在後面在說），沒有經過移位的明文和移過的密文是有區別的，這樣就可以區分凱撒密碼和柵欄密碼了（柵欄密碼參照下一章）。
沒有移位的柵欄密碼元音比較多，這是語言本身的性質絕定，像英語和漢語拼音的元音出現頻率就比較高。
原理
密碼的使用最早可以追溯到古羅馬時期，《高盧戰記》有描述愷撒曾經使用密碼來傳遞信息，即所謂的“愷撒密碼”，它是一種替代密碼，通過將字母按順序推後起3位起到加密作用，如將字母A換作字母D，將字母B換作字母E。因據說愷撒是率先使用加密函的古代將領之一，因此這種加密方法被稱為愷撒密碼。這是一種簡單的加密方法，這種密碼的密度是很低的，只需簡單地統計字頻就可以破譯。現今又叫“移位密碼”，只不過移動的位數不一定是3位而已。
密碼術可以大致分為兩種，即移位和替換，當然也有兩者結合的更複雜的方法。在移位中字母不變，位置改變；替換中字母改變，位置不變。
將替換密碼用於軍事用途的第一個檔案記載是愷撒著的《高盧記》。愷撒描述了他如何將密信送到正處在被圍困、瀕臨投降的西塞羅。其中羅馬字母被替換成希臘字母使得敵人根本無法看懂信息。
蘇托尼厄斯在公元二世紀寫的《愷撒傳》中對愷撒用過的其中一種替換密碼作了詳細的描寫。愷撒只是簡單地把信息中的每一個字母用字母表中的該字母后的第三個字母代替。這種密碼替換通常叫做愷撒移位密碼，或簡單的說，愷撒密碼。
儘管蘇托尼厄斯僅提到三個位置的愷撒移位，但顯然從1到25個位置的移位我們都可以使用，因此，為了使密碼有更高的安全性，單字母替換密碼就出現了。
如：
明碼錶ABCDEFGHIJKLMNOPQRSTUVWXYZ
密碼錶TUVWXYZABCDEFGHIJKLMNOPQRS
明文THEFAULT,DEARBRUTUS,LIESNOTINOURSTARSBUTINOURSELVES.
密文MAXYTNEM,WXTKUKNMNL,EBXLGHMBGHNKLMTKLUNMBGHNKLXEOXL.（空格是為了和上排對齊）
只需重排密碼錶二十六個字母的順序，允許密碼錶是明碼錶的任意一種重排，密鑰就會增加到四千億億億多種，我們就有超過4×1027種密碼錶。破解就變得很困難。
如何破解包括愷撒密碼在內的單字母替換密碼？
方法：字母頻度分析
儘管我們不知道是誰發現了字母頻度的差異可以用於破解密碼。但是9世紀的科學家阿爾·金迪在《關於破譯加密信息的手稿》對該技術做了最早的描述。
“如果我們知道一條加密信息所使用的語言，那么破譯這條加密信息的方法就是找出同樣的語言寫的一篇其他文章，大約一頁紙長，然後我們計算其中每個字母的出現頻率。我們將頻率最高的字母標為1號，頻率排第2的標為2號，第三標為3號，依次類推，直到數完樣品文章中所有字母。然後我們觀察需要破譯的密文，同樣分類出所有的字母，找出頻率最高的字母，並全部用樣本文章中最高頻率的字母替換。第二高頻的字母用樣本中2號代替，第三則用3號替換，直到密文中所有字母均已被樣本中的字母替換。”
以英文為例，首先我們以一篇或幾篇一定長度的普通文章，建立字母表中每個字母的頻度表。
在分析密文中的字母頻率，將其對照即可破解。
雖然設密者後來針對頻率分析技術對以前的設密方法做了些改進，比如說引進空符號等，目的是為了打破正常的字母出現頻率。但是小的改進已經無法掩蓋單字母替換法的巨大缺陷了。到16世紀，最好的密碼破譯師已經能夠破譯當時大多數的加密信息。
局限性：
短文可能嚴重偏離標準頻率，假如文章少於100個字母，那么對它的解密就會比較困難。
而且不是所有文章都適用標準頻度：
1969年，法國作家喬治斯·佩雷克寫了一部200頁的小說《逃亡》，其中沒有一個含有字母e的單詞。更令人稱奇的是英國小說家和評論家吉爾伯特·阿代爾成功地將《逃亡》翻譯成英文，而且其中也沒有一個字母e。阿代爾將這部譯著命名為《真空》。如果這本書用單密碼錶進行加密，那么頻度分析破解它會受到很大的困難。
一套新的密碼系統由法國外交家維熱納爾（BlaisedeVigenère）於16世紀末確立。其密碼不再用一個密碼錶來加密，而是使用了26個不同的密碼錶。這種密碼錶最大的優點在於能夠克制頻度分析，從而提供更好的安全保障。
維吉尼亞密碼
很明顯，凱撒密碼的密度是很低的，只需簡單地統計字頻就可以破譯。於是人們在單一愷撒密碼的基礎上擴展出多表密碼，稱為“維吉尼亞”密碼。它是由16世紀法國亨利三世王朝的布萊瑟·維吉尼亞發明的，其特點是將26個愷撒密表合成一個，見下表：
ABCDEFGHIJKLMNOPQRSTUVWXYZ
A-ABCDEFGHIJKLMNOPQRSTUVWXYZ
B-BCDEFGHIJKLMNOPQRSTUVWXYZA
C-CDEFGHIJKLMNOPQRSTUVWXYZAB
D-DEFGHIJKLMNOPQRSTUVWXYZABC
E-EFGHIJKLMNOPQRSTUVWXYZABCD
F-FGHIJKLMNOPQRSTUVWXYZABCDE
G-GHIJKLMNOPQRSTUVWXYZABCDEF
H-HIJKLMNOPQRSTUVWXYZABCDEFG
I-IJKLMNOPQRSTUVWXYZABCDEFGH
J-JKLMNOPQRSTUVWXYZABCDEFGHI
K-KLMNOPQRSTUVWXYZABCDEFGHIJ
L-LMNOPQRSTUVWXYZABCDEFGHIJK
M-MNOPQRSTUVWXYZABCDEFGHIJKL
N-NOPQRSTUVWXYZABCDEFGHIJKLM
O-OPQRSTUVWXYZABCDEFGHIJKLMN
P-PQRSTUVWXYZABCDEFGHIJKLMNO
Q-QRSTUVWXYZABCDEFGHIJKLMNOP
R-RSTUVWXYZABCDEFGHIJKLMNOPQ
S-STUVWXYZABCDEFGHIJKLMNOPQR
T-TUVWXYZABCDEFGHIJKLMNOPQRS
U-UVWXYZABCDEFGHIJKLMNOPQRST
V-VWXYZABCDEFGHIJKLMNOPQRSTU
W-WXYZABCDEFGHIJKLMNOPQRSTUV
X-XYZABCDEFGHIJKLMNOPQRSTUVW
Y-YZABCDEFGHIJKLMNOPQRSTUVWX
Z-ZABCDEFGHIJKLMNOPQRSTUVWXY
維吉尼亞密碼（類似於今天我們所說的置換密碼）引入了“密鑰”的概念，即根據密鑰來決定用哪一行的密表來進行替換，以此來對抗字頻統計。假如以上面第一行代表明文字母，左面第一列代表密鑰字母，對如下明文加密：
TOBEORNOTTOBETHATISTHEQUESTION
當選定RELATIONS作為密鑰時，加密過程是：明文一個字母為T，第一個密鑰字母為R，因此可以找到在R行中代替T的為K，依此類推，得出對應關係如下：
密鑰：RELATIONSRELATIONSRELATIONSREL
明文：TOBEORNOTTOBETHATISTHEQUESTION
密文：KSMEHZBBLKSMEMPOGAJXSEJCSFLZSY
歷史上以維吉尼亞密表為基礎又演變出很多種加密方法，其基本元素無非是密表與密鑰，並一直沿用到二戰以後的初級電子密碼機上。
歷史溯源
愷撒曾經使用這種密碼與其將軍們聯繫根據蘇維托尼烏斯的記載，愷撒曾用此方法對重要的軍事信息進行加密：公元前51年初，深冬。高盧，畢布拉克德（現法國境內伯夫雷山），凱撒的營帳。深夜，羅馬共和國高盧行省長它儒略.凱撒，正在一張羊皮上寫著什麼。他的身影被跳動的燈火映在帳篷上，高大而搖曳。他的臉略嫌狹長，但稜角分明，專注的神色中透著與生俱來的自負。他在寫他的“隨記”，也就是後來流傳於世的《高盧戰記》。戎馬生涯的凱撒本沒有餘暇來寫什麼隨記，但是過去的幾年中，與他在高盧的顯赫戰績相比，政治上的事態發展可不那么如意。羅馬執政宮克拉蘇斯在同帕爾提亞人（在今土庫曼斯坦南部和伊朗東北部）的作戰中被俘。熔化了的台液灌進了他的喉嚨……這個當年殘酷鎮壓斯巴達克斯起義的劊子手，如今向他嗜如生命的黃金鑄在了一起，這對凱撒來說是一件好事——少了一個政敵，但更是一件壞事——羅馬“三巨頭”之間的平衡被打破了，活著的兩巨頭，他和龐培，不得不面臨決鬥。凱撒從來沒有看得起過克拉蘇斯。這個只會獻媚的小人死不足惜，但龐培絕不能小看，不然的話凱撒當年也不會把自己的女兒尤麗姬嫁給龐培。要知道，龐培比凱撒還要大8歲。尤麗婭已經去世，他們之間除了你死我活己無任何瓜葛。龐培以羅馬唯一執政官的地位優勢，正在元老院裡向他發動強大的政治攻勢……他必須宣傳自己，他必須向元老院陳述自己的功績，但同時又必須表現出一種謙遜、客觀的態度，不能帶有任何自吹自擂的痕跡。為此，他在這部隨記中，處處用第三人稱稱呼自己，通篇都用異常平靜、簡潔的筆調敘說戰事的經過。
這時他正寫到卷五，說的是公元前54年，他的愛將西塞羅突然遭到維爾納人的圍攻，情況緊急，“於是，他以極大的酬報說服了一個高盧騎兵，送一封信去給西塞羅。送去的信是用希臘文寫的，免得它被敵人截住後得知我軍的計畫……”寫到這時，他停了一下，似在考慮更好的措詞。一絲狡猾的微笑從臉上掠過，他繼續寫了下去……時間無情地飛馳，轉眼就過了近2000年，凱撒的《高盧戰記》以其翔實的敘事、清純的文風，成為研究羅馬歷史、拉丁文學和軍事史不可或缺的學術資料。1979年，中國商務印書館將《高盧戰記》譯成中文，作為“漢譯世界學術名著叢書”中的一種出版，譯者任炳湘先生打開這本中文譯本，翻到第124頁，我們看到了上面引述的那樁派人送信給西塞羅的事。然而，治學嚴謹的譯者在這裡發現了問題，他注道：“言下之意，似乎高盧人個懂希臘語，即令書信被截去，也不會泄露自己的計畫。但在本書卷一25節中曾說到在厄爾維幾人營中發現用希臘文寫的統計數字，又說高盧人無論公私檔案都用希臘文書寫，似乎有矛盾。”對此，譯者的推測是：“也許上面兩節指的是高盧人用希臘字母書寫自己的語言，這一節所說的是真正的希臘文。”譯者的質疑可說是切中要害，然而譯者的推測卻仍讓人疑雲難消。敵營中就沒有一人認識真正的希臘文？他們就不能去找一個希臘人來識這封信（如果他們截住了這封信的話）?足智多謀的凱撒會不考慮這些明擺著的可能而鋌而走險？是不是可以有另外的解釋?確實有另外一種解釋：如果記讓一位密碼學家來進行推測，他會毫不猶豫地認為——凱撒送去的這封信是用密碼寫的！因為任何一本講述密碼學歷史的著作，都會提到凱撒對軍事密碼學的貢獻。凱撒在其軍事行動中使用了密碼，這在密碼學界已不是密碼。
科學已經無法弄清愷撒密碼在當時有多大的效果，但是有理由相信它是安全的。因為愷撒大部分敵人都是目不識丁的，而其餘的則可能將這些訊息當作是某個未知的外語。即使有某個敵人獲取了愷撒的加密信息，根據現有的記載，當時也沒有任何技術能夠解決這一最基本、最簡單的替換密碼。現存最早的破解方法記載在公元9世紀阿拉伯的阿爾·肯迪的有關發現頻率分析的著作中。
特定愷撒密碼名稱
根據偏移量的不同，還存在若干特定的愷撒密碼名稱：
偏移量為10：Avocat(A→K)偏移量為13：ROT13偏移量為-5：Cassis(K6）偏移量為-6：Cassette(K7）
凱撒系統
此系統因羅馬時代的發明人JuliusCaesar（蓋烏斯·尤利烏斯·愷撒）得名。傳說被愷撒大帝使用過。
愷撒系統的密碼是自己選的一個單詞。
例如，選用mountain，寫出以下的字母序列：mountaibcdefghjklpqrsvwxyz。
看出來了嗎？就是在正常字母序列中抽掉你的密碼mountain。由於mountain中有兩個n，把第二個去掉。
然後，把正常字母序列寫在這個序列下面：
在加密的時候，用上面那個序列里的字母代替原文中的字母寫成密文。例如，m代替a，o代替b。解密時方向相反。所以，加密heishere的結果是：btcqbkpt。
如果你的文本中有數字，那么不妨寫一個36字元的序列，並把數字加在你的密碼中。
評價：這種方法比簡單移位系統安全，可以在你的日記中使用。但是，如果加密的文字有（大約）400字元以上，那么攻擊者手工花費1天時間即可破解，因為英文和其它語言中每個字母都有一定的使用頻率，破解者根據這些頻率就可以破譯。
盤點密碼學相關知識
| 盤點密碼學相關知識，密碼學是研究編制密碼和破譯密碼的技術科學。 |
