凱撒密碼:代換密碼-中文百科頻道

概念

凱撒密碼最早由古羅馬軍事統帥蓋烏斯·尤利烏斯·凱撒在軍隊中用來傳遞加密信息，故稱凱撒密碼。這是一種位移加密方式，隻對26個字母進行位移替換加密，規則簡單，容易破解。

在密碼學中，凱撒密碼（或稱恺撒加密、恺撒變換、變換加密）是一種最簡單且最廣為人知的加密技術。它是一種替換加密的技術。這個加密方法是以恺撒的名字命名的，當年恺撒曾用此方法與其将軍們進行聯系。恺撒密碼通常被作為其他更複雜的加密方法中的一個步驟，例如維吉尼亞密碼。恺撒密碼還在現代的ROT13系統中被應用。但是和所有的利用字母表進行替換的加密技術一樣，恺撒密碼非常容易被破解，而且在實際應用中也無法保證通信安全。

凱撒密碼II

在人類曆史上，對信息保護的需求與對信息本身的需求一樣久遠。第一個用于加密和解密文本的編碼方式是凱撒密碼。由于原始的凱撒密碼較簡單，較易被破解。随着考古的進展，人們發現了升級版的凱撒密碼II。

凱撒密碼II通過查詢動态密碼表，把凱撒單詞加密成一些密文數字。

如果請你使用現有動态密碼表，加密一些單詞。你要處理m個操作，操作分成兩種：

A string integer:增加一條凱撒單詞string到凱撒密文數字integer的映射規則，如果先前已經有關于這個string的規則，那麼用該規則替換原規則。

Q string:查詢單詞string所對應的最新密文數字。

第一行一個整數m（1≤m≤1,000,000），表示有m個操作。

單詞僅有長度不超過8位的小寫字母組成，單詞總數不超過100,000個。

密文數字的範圍是[0..1,000,000,000]。

凱撒密表

古羅馬随筆作家修托尼厄斯在他的作品中披露，凱撒常用一種“密表”給他的朋友寫信。這裡所說的密表，在密碼學上稱為“凱撒密表”。用現代的眼光看，凱撒密表是一種相當簡單的加密變換，就是把明文中的每一個字母用它在字母表上位置後面的第三個字母代替。古羅馬文字就是現在所稱的拉丁文，其字母就是我們從英語中熟知的那26個拉丁字母。因此，凱撒密表就是用D代a，用E代b，……，用z代w，（注意！）用A代x，用B代y，C代z。這些代替規則也可用一張表格來表示（所以叫“密表”）。

那麼，在公元前54年，凱撒就是用這種密碼給西塞羅寫信的嗎?有趣的是，密碼界對這—點卻持否定态度，因為密碼學曆史上還記載着凱撒使用的另一種加密方法：把明文的拉丁字母逐個代之以相應的希臘字母，這種方法看來更貼近凱撒在《高盧戰記》中的記叙。

顯然，哪一個拉丁字母應該代之以哪—個希臘字母，事先都有約定，凱撒知道，西塞羅也知道，不然的話，西塞羅收到密信後，也會不知所雲。當阿裡巴巴站在那四十一名大盜的山洞大門口，準備打開大門時，他必須知道一個咒語：“芝麻開門”。當我們站在密碼學的大門，準備邁入時，必須要知道的則是—些基本概念。為此，讓我們先把密碼通信的幾個要素總結如下。

在軍事通信上，必須考慮要傳送的秘密信息在傳送的途中被除發信者和收信者以外的第三者（特别是敵人）截獲的可能性使載送信息的載體（如文本、無線電被等）即使在被截獲的情況下也不會讓截獲者得知其中信息内容的通信方法或技術，稱為保密通信。密碼通信就是一種保密通信，它是把表達信息的意思明确的文字符号，用通信雙方事先所約定的變換規則，變換為另一串莫名其妙的符号，以此作為通信的文本發送給收信者，當這樣的文本傳送到收信者手中時，收信者—時也不能識别其中所代表的意思，這時就要根據事先約定的變換規則，把它恢複成原來的意思明确的文字，然後閱讀。

這樣，如果這個文本在通信途中被第三者截獲，由于第三者—般不知道那變換規則，因此他就不能得知在這一串符号背後所隐藏的信息。當然，為了戰争的目的，他會千方百計地努力弄到這個變換規則。一種努力就是對已經截獲的密文進行分析，有時結合從其他途徑獲得的有關信息，試圖找出這個變換規則。

在密碼學中，我們要傳送的以通用語言明确表達的文字内容稱為明文，由明文經變換而形成的用于密碼通信的那一串符号稱為密文，把明文按約定的變換規則變換為密文的過程稱為加密，收信者用約定的變換規則把密文恢複為明文的過程稱為解密。敵方主要圍繞所截獲密文進行分析以找出密碼變換規則的過程，稱為破譯。

明密對照表

明文：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個位置的移位我們都可以使用，因此，為了使密碼有更高的安全性，單字母替換密碼就出現了。

如何破解包括恺撒密碼在内的單字母替換密碼？

方法：字母頻度分析

盡管我們不知道是誰發現了字母頻度的差異可以用于破解密碼。但是9世紀的科學家阿爾·金迪在《關于破譯加密信息的手稿》對該技術做了最早的描述。

“如果我們知道一條加密信息所使用的語言，那麼破譯這條加密信息的方法就是找出同樣的語言寫的一篇其他文章，大約一頁紙長，然後我們計算其中每個字母的出現頻率。我們将頻率最高的字母标為1号，頻率排第2的标為2号，第三标為3号，依次類推，直到數完樣品文章中所有字母。然後我們觀察需要破譯的密文，同樣分類出所有的字母，找出頻率最高的字母，并全部用樣本文章中最高頻率的字母替換。第二高頻的字母用樣本中2号代替，第三則用3号替換，直到密文中所有字母均已被樣本中的字母替換。”

以英文為例，首先我們以一篇或幾篇一定長度的普通文章，建立字母表中每個字母的頻度表。

在分析密文中的字母頻率，将其對照即可破解。

雖然設密者後來針對頻率分析技術對以前的設密方法做了些改進，比如說引進空符号等，目的是為了打破正常的字母出現頻率。但是小的改進已經無法掩蓋單字母替換法的巨大缺陷了。到16世紀，最好的密碼破譯師已經能夠破譯當時大多數的加密信息。

局限性：

短文可能嚴重偏離标準頻率，假如文章少于100個字母，那麼對它的解密就會比較困難。而且不是所有文章都适用标準頻度：

1969年，法國作家喬治斯·佩雷克寫了一部200頁的小說《逃亡》，其中沒有一個含有字母e的單詞。更令人稱奇的是英國小說家和評論家吉爾伯特·阿代爾成功地将《逃亡》翻譯成英文，而且其中也沒有一個字母e。阿代爾将這部譯著命名為《真空》。如果這本書用單密碼表進行加密，那麼頻度分析破解它會受到很大的困難。

一套新的密碼系統由法國外交家維熱納爾（Blaise de Vigenère）于16世紀末确立。其密碼不再用一個密碼表來加密，而是使用了26個不同的密碼表。這種密碼表最大的優點在于能夠克制頻度分析，從而提供更好的安全保障。

曆史溯源

恺撒曾經使用這種密碼與其将軍們聯系根據蘇維托尼烏斯的記載，恺撒曾用此方法對重要的軍事信息進行加密：公元前51年初，深冬。高盧，畢布拉克德（現法國境内伯夫雷山），凱撒的營帳。深夜，羅馬共和國高盧行省長它儒略.凱撒，正在一張羊皮上寫着什麼。他的身影被跳動的燈火映在帳篷上，高大而搖曳。他的臉略嫌狹長，但棱角分明，專注的神色中透着與生俱來的自負。他在寫他的“随記”，也就是後來流傳于世的《高盧戰記》。戎馬生涯的凱撒本沒有餘暇來寫什麼随記，但是過去的幾年中，與他在高盧的顯赫戰績相比，政治上的事态發展可不那麼如意。

羅馬執政宮克拉蘇斯在同帕爾提亞人（在今土庫曼斯坦南部和伊朗東北部）的作戰中被俘。熔化了的台液灌進了他的喉嚨……這個當年殘酷鎮壓斯巴達克斯起義的劊子手，如今向他嗜如生命的黃金鑄在了一起，這對凱撒來說是一件好事——少了一個政敵，但更是一件壞事——羅馬“三巨頭”之間的平衡被打破了，活着的兩巨頭，他和龐培，不得不面臨決鬥。凱撒從來沒有看得起過克拉蘇斯。

這個隻會獻媚的小人死不足惜，但龐培絕不能小看，不然的話凱撒當年也不會把自己的女兒尤麗姬嫁給龐培。要知道，龐培比凱撒還要大8歲。尤麗娅已經去世，他們之間除了你死我活己無任何瓜葛。龐培以羅馬唯一執政官的地位優勢，正在元老院裡向他發動強大的政治攻勢……他必須宣傳自己，他必須向元老院陳述自己的功績，但同時又必須表現出一種謙遜、客觀的态度，不能帶有任何自吹自擂的痕迹。為此，他在這部随記中，處處用第三人稱稱呼自己，通篇都用異常平靜、簡潔的筆調叙說戰事的經過。

這時他正寫到卷五，說的是公元前54年，他的愛将西塞羅突然遭到維爾納人的圍攻，情況緊急，“于是，他以極大的酬報說服了一個高盧騎兵，送一封信去給西塞羅。送去的信是用希臘文寫的，免得它被敵人截住後得知我軍的計劃……”寫到這時，他停了一下，似在考慮更好的措詞。一絲狡猾的微笑從臉上掠過，他繼續寫了下去……時間無情地飛馳，轉眼就過了近2000年，凱撒的《高盧戰記》以其翔實的叙事、清純的文風，成為研究羅馬曆史、拉丁文學和軍事史不可或缺的學術資料。

1979年，中國商務印書館将《高盧戰記》譯成中文，作為“漢譯世界學術名著叢書”中的一種出版，譯者任炳湘先生打開這本中文譯本，翻到第124頁，我們看到了上面引述的那樁派人送信給西塞羅的事。然而，治學嚴謹的譯者在這裡發現了問題，他注道：“言下之意，似乎高盧人個懂希臘語，即令書信被截去，也不會洩露自己的計劃。但在本書卷一25節中曾說到在厄爾維幾人營中發現用希臘文寫的統計數字，又說高盧人無論公私文件都用希臘文書寫，似乎有矛盾。”對此，譯者的推測是：“也許上面兩節指的是高盧人用希臘字母書寫自己的語言，這一節所說的是真正的希臘文。”

譯者的質疑可說是切中要害，然而譯者的推測卻仍讓人疑雲難消。敵營中就沒有一人認識真正的希臘文？他們就不能去找一個希臘人來識這封信（如果他們截住了這封信的話）?足智多謀的凱撒會不考慮這些明擺着的可能而铤而走險？是不是可以有另外的解釋?确實有另外一種解釋：如果記讓一位密碼學家來進行推測，他會毫不猶豫地認為——凱撒送去的這封信是用密碼寫的！因為任何一本講述密碼學曆史的著作，都會提到凱撒對軍事密碼學的貢獻。凱撒在其軍事行動中使用了密碼，這在密碼學界已不是密碼。

科學已經無法弄清恺撒密碼在當時有多大的效果，但是有理由相信它是安全的。因為恺撒大部分敵人都是目不識丁的，而其餘的則可能将這些消息當作是某個未知的外語。即使有某個敵人獲取了恺撒的加密信息，根據現有的記載，當時也沒有任何技術能夠解決這一最基本、最簡單的替換密碼。現存最早的破解方法記載在公元9世紀阿拉伯的阿爾·肯迪的有關發現頻率分析的著作中。