凯撒密码

凯撒密码作为一种最为古老的对称加密体制，在古罗马的时候都已经很流行，他的基本思想是：通过把字母移动一定的位数来实现加密和解密。例如，如果密匙是把明文字母的位数向后移动三位，那么明文字母B就变成了密文的E，依次类推，X将变成A，Y变成B，Z变成C，由此可见，位数就是凯撒密码加密和解密的密钥。　　　它是一种代换密码。据说恺撒是率先使用加密函的古代将领之一，因此这种加密方法被称为恺撒密码。

在密码学中，恺撒密码（或称恺撒加密、恺撒变换、变换加密）是一种最简单且最广为人知的加密技术。它是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。例如，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。这个加密方法是以恺撒的名字命名的，当年恺撒曾用此方法与其将军们进行联系。恺撒密码通常被作为其他更复杂的加密方法中的一个步骤，例如维吉尼亚密码。恺撒密码还在现代的ROT13系统中被应用。但是和所有的利用字母表进行替换的加密技术一样，恺撒密码非常容易被破解，而且在实际应用中也无法保证通信安全。例子 恺撒密码的替换方法

恺撒密码原理密码的使用最早可以追溯到古罗马时期，《高卢战记》有描述恺撒曾经使用密码来传递信息，即所谓的“恺撒密码”，它是一种替代密码，通过将字母按顺序推后起3位起到加密作用，如将字母A换作字母D，将字母B换作字母E。因据说恺撒是率先使用加密函的古代将领之一，因此这种加密方法被称为恺撒密码。这是一种简单的加密方法，这种密码的密度是很低的，只需简单地统计字频就可以破译。现今又叫“移位密码”，只不过移动的为数不一定是3位而已。

密码术可以大致别分为两种，即易位和替换，当然也有两者结合的更复杂的方法。在易位中字母不变，位置改变；替换中字母改变，位置不变。　　将替换密码用于军事用途的第一个文件记载是恺撒著的《高卢记》。恺撒描述了他如何将密信送到正处在被围困、濒临投降的西塞罗。其中罗马字母被替换成希腊字母使得敌人根本无法看懂信息。

苏托尼厄斯在公元二世纪写的《恺撒传》中对恺撒用过的其中一种替换密码作了详细的描写。恺撒只是简单地把信息中的每一个字母用字母表中的该字母后的第三个字母代替。这种密码替换通常叫做恺撒移位密码，或简单的说，恺撒密码。　　尽管苏托尼厄斯仅提到三个位置的恺撒移位，但显然从1到25个位置的移位我们都可以使用， 因此，为了使密码有更高的安全性，单字母替换密码就出现了。

如：　　明码表 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　　明文 F O R E S T

密文 Y G K T L Z　　只需重排密码表二十六个字母的顺序，允许密码表是明码表的任意一种重排，密钥就会增加到四千亿亿亿多种，我们就有超过4×1027种密码表。破解就变得很困难。

如何破解包括恺撒密码在内的单字母替换密码？　　方法：字母频度分析

尽管我们不知道是谁发现了字母频度的差异可以用于破解密码。但是9世纪的科学家阿尔·金迪在《关于破译加密信息的手稿》对该技术做了最早的描述。　　“如果我们知道一条加密信息所使用的语言，那么破译这条加密信息的方法就是找出同样的语言写的一篇其他文章，大约一页纸长，然后我们计算其中每个字母的出现频率。我们将频率最高的字母标为1号，频率排第2的标为2号，第三标为3号，依次类推，直到数完样品文章中所有字母。然后我们观察需要破译的密文，同样分类出所有的字母，找出频率最高的字母，并全部用样本文章中最高频率的字母替换。第二高频的字母用样本中2号代替，第三则用3号替换，直到密文中所有字母均已被样本中的字母替换。”

以英文为例，首先我们以一篇或几篇一定长度的普通文章，建立字母表中每个字母的频度表。　　在分析密文中的字母频率，将其对照即可破解。

虽然设密者后来针对频率分析技术对以前的设密方法做了些改进，比如说引进空符号等，目的是为了打破正常的字母出现频率。但是小的改进已经无法掩盖单字母替换法的巨大缺陷了。到16世纪，最好的密码破译师已经能够破译当时大多数的加密信息。　　局限性：

短文可能严重偏离标准频率，加入文章少于100个字母，那么对它的解密就会比较困难。　　而且不是所有文章都适用标准频度：

1969年，法国作家乔治斯·佩雷克写了一部200页的小说《逃亡》，其中没有一个含有字母e的单词。更令人称奇的是英国小说家和拼论家吉尔伯特·阿代尔成功地将《逃亡》翻译成英文，而且其中也没有一个字母e。阿代尔将这部译著命名为《真空》。如果这本书用单密码表进行加密，那么频度分析破解它会受到很大的困难。　　一套新的密码系统由法国外交家维热纳尔（Blaise de Vigenère）于16世纪末确立。其密码不再用一个密码表来加密，而是使用了26个不同的密码表。这种密码表最大的优点在于能够克制频度分析，从而提供更好的安全保障。

凯撒密码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]。

对于每组查询，输出一行，表示根据密码表中的规则，加密后的密文数字，如果在无法在密码表中查找到该单词，输出 -1。　　7 A aaab 10 A aaac 20 A aaad 30 Q aaac A aaac 40 Q aaaa Q aaac

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，当然这不是一成不变的，这时应该就被破解了。

我们看到一个密码怎样判断是凯撒密码呢？这又要扯到频率分析去（在这里不介绍，在后面在说），没有经过移位的明文和移过的密文是有区别的，这样就可以区分凯撒密码和栅栏密码了（栅栏密码参照下一章）。　　没有移位的栅栏密码元音比较多，这是语言本身的性质绝定，像英语和汉语拼音的元音出现频率就比较高。

维吉尼亚密码很明显，凯撒密码的密度是很低的，只需简单地统计字频就可以破译。于是人们在单一恺撒密码的基础上扩展出多表密码，称为“维吉尼亚”密码。它是由16世纪法国亨利三世王朝的布莱瑟·维吉尼亚发明的，其特点是将26个恺撒密表合成一个，见下表：　　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

A -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　　B -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 A

C-C D E F G H I J K L M N O P Q R S T U V W X Y Z A B　　D- D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

E- E F G H I J K L M N O P Q R S T U V W X Y Z A B C D　　F- F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

G- G H I J K L M N O P Q R S T U V W X Y Z A B C D E F　　H- H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

I- I J K L M N O P Q R S T U V W X Y Z A B C D E F G H　　J- J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

K- K L M N O P Q R S T U V W X Y Z A B C D E F G H I J　　L -L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

M- M N O P Q R S T U V W X Y Z A B C D E F G H I J K L　　N- N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

O- O P Q R S T U V W X Y Z A B C D E F G H I J K L M N　　P- P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

Q- Q R S T U V W X Y Z A B C D E F G H I J K L M N O P　　R- R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

S- S 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　　T- 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

U- 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 T　　V- V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

W- W X Y Z A B C D E F G H I J K L M N O P Q R S T U V　　X- X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

Y- Y Z A B C D E F G H I J K L M N O P Q R S T U V W X　　Z- Z 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

维吉尼亚密码（类似于今天我们所说的置换密码）引入了“密钥”的概念，即根据密钥来决定用哪一行的密表来进行替换，以此来对抗字频统计。假如以上面第一行代表明文字母，左面第一列代表密钥字母，对如下明文加密：　　TO BE OR NOT TO BE THAT IS THE QUESTION

当选定RELATIONS作为密钥时，加密过程是：明文一个字母为T，第一个密钥字母为R，因此可以找到在R行中代替T的为K，依此类推，得出对应关系如下：　　密钥：RELAT IONSR ELATI ONSRE LATIO NSREL

明文：TOBEO RNOTT OBETH ATIST HEQUE STION　　密文：KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY

历史上以维吉尼亚密表为基础又演变出很多种加密方法，其基本元素无非是密表与密钥，并一直沿用到二战以后的初级电子密码机上。

历史溯源恺撒曾经使用这种密码与其将军们联系 根据苏维托尼乌斯的记载，恺撒曾用此方法对重要的军事信息进行加密：

“

如果需要保密，信中便用暗号，也即是改变字母顺序，使局外人无法组成一个单词。如果想要读懂和理解它们的意思，得用第4个字母置换第一个字母，即以D代A，余此类推。

”

—苏维托尼乌斯，罗马十二帝王传

同样，奥古斯都也使用过类似方式，只不过他是把字母向右移动一位，而且末尾不折回。　　

“

每当他用密语写作时，他都用B代表A，C代表B，其余的字母也依同样的规则；他用AA代表X。

”

—苏维托尼乌斯，罗马十二帝王传

另外，有证据表明，恺撒曾经使用过更为复杂的密码系统：

“

文法学家普罗布斯曾经写过一份独具创新的手稿，研究恺撒书信中包含有秘密信息的字母。

”

—格利乌斯，阿提卡之夜

公元前51年初，深冬。高卢，毕布拉克德（现法国境内伯夫雷山），凯撒的营帐。深夜，罗马共和国高卢行省长它儒略.凯撒，正在一张羊皮上写着什么。他的身影被跳动的灯火映在帐篷上，高大而摇曳。他的脸略嫌狭长，但棱角分明，专注的神色中透着与生俱来的自负。他在写他的“随记”，也就是后来流传于世的《高卢战记》。戎马生涯的凯撒本没有余暇来写什么随记，但是过去的几年中，与他在高卢的显赫战绩相比，政治上的事态发展可不那么如意。罗马执政宫克拉苏斯在同帕尔提亚人（在今土库曼斯坦南部和伊朗东北部）的作战中被俘。熔化了的台液灌进了他的喉咙……这个当年残酷镇压斯巴达克斯起义的刽子手，如今向他嗜如生命的黄金铸在了一起，这对凯撒来说是一件好事——少了一个政敌，但更是一件坏事——罗马“三巨头”之间的平衡被打破了，活着的两巨头，他和庞培，不得不面临决斗。凯撒从来没有看得起过克拉苏斯。这个只会献媚的小人死不足惜，但庞培绝不能小看，不然的话凯撒当年也不会把自己的女儿尤丽姬嫁给庞培。要知道，庞培比凯撒还要大8岁。现在，尤丽娅已经去世，他们之间除了你死我活己无任何瓜葛。庞培以罗马唯一执政官的地位优势，正在元老院里向他发动强大的政治攻势……他必须宣传自己，他必须向元老院陈述自己的功绩，但同时又必须表现出一种谦逊、客观的态度，不能带有任何自吹自擂的痕迹。为此，他在这部随记中，处处用第三人称称呼自己，通篇都用异常平静、简洁的笔调叙说战事的经过。　　这时他正写到卷五，说的是公元前54年，他的爱将西塞罗突然遭到维尔纳人的围攻，情况紧急，“于是，他以极大的酬报说服了一个高卢骑兵，送一封信去给西塞罗。送去的信是用希腊文写的，免得它被敌人截住后得知我军的计划……”写到这时，他停了一下，似在考虑更好的措词。一丝狡猾的微笑从脸上掠过，他继续写了下去……时间无情地飞驰，转眼就过了近2000年，凯撒的《高卢战记》以其翔实的叙事、清纯的文风，成为研究罗马历史、拉丁文学和军事史不可或缺的学术资料。1979年，中国商务印书馆将《高卢战记》译成中文，作为“汉译世界学术名著丛书”中的一种出版，译者任炳湘先生打开这本中文译本，翻到第124页，我们看到了上面引述的那桩派人送信给西塞罗的事。然而，治学严谨的译者在这里发现了问题，他注道：“言下之意，似乎高卢人个懂希腊语，即令书信被截去，也不会泄露自己的计划。但在本书卷一25节中曾说到在厄尔维几人营中发现用希腊文写的统计数字，又说高卢人无论公私文件都用希腊文书写，似乎有矛盾。”对此，译者的推测是：“也许上面两节指的是高卢人用希腊字母书写自己的语言，这一节所说的是真正的希腊文。”译者的质疑可说是切中要害，然而译者的推测却仍让人疑云难消。敌营中就没有一人认识真正的希腊文？他们就不能去找一个希腊人来识这封信（如果他们截住了这封信的话）?足智多谋的凯撒会不考虑这些明摆着的可能而铤而走险？是不是可以有另外的解释?确实有另外一种解释：如果记让一位密码学家来进行推测，他会毫不犹豫地认为——凯撒送去的这封信是用密码写的！因为任何一本讲述密码学历史的著作，都会提到凯撒对军事密码学的贡献。凯撒在其军事行动中使用了密码，这在密码学界已不是密码。

现在已经无法弄清恺撒密码在当时有多大的效果，但是有理由相信它是安全的。因为恺撒大部分敌人都是目不识丁的，而其余的则可能将这些消息当作是某个未知的外语。即使有某个敌人获取了恺撒的加密信息，根据现有的记载，当时也没有任何技术能够解决这一最基本、最简单的替换密码。现存最早的破解方法记载在公元9世纪阿拉伯的阿尔·肯迪的有关发现频率分析的著作中。

特定恺撒密码名称根据偏移量的不同，还存在若干特定的恺撒密码名称：　　偏移量为10：Avocat(A→K) 偏移量为13：ROT13偏移量为-5：Cassis (K 6） 偏移量为-6：Cassette (K 7）

凯撒系统此系统因罗马时代的发明人Julius Caesar（盖乌斯·尤利乌斯·恺撒）得名。传说被恺撒大帝使用过。　　恺撒系统的密码是自己选的一个单词。

例如，选用mountain，写出以下的字母序列：mountaibcdefghjklpqrsvwxyz。　　看出来了吗？就是在正常字母序列中抽掉你的密码mountain。由于mountain中有两个n，把第二个去掉。

然后，把正常字母序列写在这个序列下面：　　Mountaibcdefghjklpqrsvwxyz.......密文字母序

Abcdefghijklmnopqrstuvwxyz.......明文字母序　　在加密的时候，用上面那个序列里的字母代替原文中的字母写成密文。例如，m代替a，o代替b。解密时方向相反。所以，加密heishere的结果是：btcqbkpt。

如果你的文本中有数字，那么不妨写一个36字符的序列，并把数字加在你的密码中。　　评价：这种方法比简单移位系统安全，可以在你的日记中使用。但是，如果加密的文字有（大约）400字符以上，那么攻击者手工花费1天时间即可破解，因为英文和其它语言中每个字母都有一定的使用频率，破解者根据这些频率就可以破译。