快捷搜索:

科学知识

当前位置:betway必威官网手机版 > 科学知识 > 密码学初探,密码好玩的事

密码学初探,密码好玩的事

来源:http://www.abirdfarm.com 作者:betway必威官网手机版 时间:2019-11-22 20:21

信息时代,密码无处不在了,各种密码术也随处可见,为爱好者们津津乐道。而在此前很长一段时间,密码学作为一门行走在暗处的黑色艺术,一直不为大众所知,只在少数精英间流传。从凯撒的设计到二战时期美日间的较量,这个关于秘密通信的历史,精彩无比。有人设计密码,就有人破译密码,在这场智与智的较量中,遗下无数经典。让我们来了解几个最经典的密码,一起感受密码学里的艺术。

西蒙・辛格的《密码故事》生动有趣、引入入胜,但中文译本存在多处人名前后翻译不一致的现象,且原著中关于针孔加密法的示例也完全丢失,建议有条件的同学尽量阅读英文原著《The Code Book》。

图片 1

在无线电开始普及之后,各国政府先后投入精力开始研究加密和破译技术。加上随之而来的第一次世界大战,密码学在影响了战争结果的同时,也在这段时间飞速发展。让我们一起看看这段时间的一些经典成果。

说完了前面那些,想起个事,本系列依据内容主要来自《现代密码学》马春光编著。我就是学这本书的。

凯撒密码

作为一名杰出的军事领袖,尤里乌斯•凯撒深知指挥官对前方将领的命令对于一场战争的重要性,这些信息绝对不能让敌方知道,于是他设计了一种对重要的军事信息进行加密的方法,即使这些信息被截获,敌方也不一定能看懂——这就是著名的凯撒密码,也算是最早的密码实例。

在这种密码中,从A到W的每个字母在加密时用字母表中位于后三位的那个字母代替,字母XYZ分别被替换成ABC。凯撒在这里是将字母向右移动了三位(如下图)。比如,在三个移位的情况下,信息DOG(这种需要加密的信息统称“明文”)就变换成GRJ(这种经加密后产生的的信息统称“密文”);密文FDW对应的明文则是CAT。可以看到,加密、解密过程都是以字母移位的位数为参照的。这种在加密和解密的算法中依赖的参数则被称为——密钥。

图片 2

当然,移位的选择并不仅仅限制在三位,从1到25任何数的移位都能产生类似效果。只要通信双方事先约定好,这个选择就很任意。很明显的是,移位方法最多也只有25种,这成为凯撒密码的致命弱点。一般情况下,穷举25种移位方法,得到25组新编码,必有一种编码是真实的情报内容,由于其它24组多是是毫无意义的字母组合,所以凯撒密码很容易就能被破译。

但是凯撒在当时很成功的使用了这种密码,还在《高卢战记》中颇为得意的记录下了这个加密设计。究其原因,只能是他的敌人并没有意识到他在使用密码。

本文对于专用词汇的翻译不仅做了统一,索性和通用的翻译对齐,所以和中文译本里的译名可能有出入。共有上、中、下三篇,各篇链接及包含内容如下:

通证通研究院 × FENBUSHI DIGITAL 联合出品文:宋双杰,CFA;孙含儒特别顾问:沈波;Rin;JX

普莱费尔(Playfair)密码

在维热纳尔密码被破解之后,英国人查尔斯•惠斯通爵士开发了这种加密法。经他的朋友普莱费尔的大力提倡后,被英国政府部门和军队采用。它在1854到1855年的克里米亚战争和1899年的布尔战争中被广泛应用,直到1915年的一战时期才被破译。

普莱费尔加密法也是一种替换密码,不同的是它不仅比先前提到的维热纳尔加密法更加先进,同时它使用方便而且可以让英语字母的频率统计分析法再无用武之地。

在这种方法中,字母是成对而不是单个加密的。而密钥是一个5×5方阵(除J以外的25个字母随机排列)。加密之前,对明文信息要稍作如下处理:

用I代替J;
将要加密的信息所有字母排列成字母对形式:XX XX XX XX……
遇到同样字母组成的字母对,在中间插入Z
如果明文中字母个数是奇数,在最后补Z

实际操作时,密钥是依赖一个关键词确定产生的。比如选取关键词“rainbow”,把这个词的所含字母按序写到矩阵中之后,用25个字母中余下未出现的字母按字母表顺序补全矩阵的剩余位置,如下图(当然也可以将25个字母随机排列到矩阵中,但是这样并不利于记忆与操作)。

图片 3

当需要加密的信息用上述规则处理后,就可以按照一套既定的规则加密:

将密钥扩充成6行6列,第六行与第一行相同,第六列与第一列相同。

若两个字母在密钥中位于一行(列),每个字母替换为扩充后的密钥中位于它右侧(下方)的字母。

两个字母不同行不同列,则第一个字母替换成与它同行,列数与第二个字母相同的字母,第二个字母替换成与这三个字母形成矩形的字母。

图片 4

好了,古典密码就是古时候的密码,哈哈,逗你玩的,shannon的保密系统的通信理论发表前的都是古典密码,会在密码学简史中介绍这位牛人的。

改进后的加密法

在凯撒密码的缺点暴露后,有人便对它做出了改进:用一个按随机顺序排列的字母表来替代正常顺序的字母表。这种简单代换方法达26!种,这个看起来不大的数字,数量级达到了10 26 ,也就是说穷举法破译已经失效了。但是,这种方法并非无懈可击,当它对一段比较长的英文信息加密时,依然容易被破译。这是英语本身的统计特性决定的。

众所周知,英语具有统计特性。每个字母的使用频率不同且差别很大。一篇文章中字母出现的相对预期频率是可以通过统计大量英语文章确定出来的。比如,英语文章中 E 的出现频率最高,大约是 12.7% 这样子;而 J 的出现频率最低,只有 0.1% 左右。当使用上述的简单代换密码时,字母表中特定字母总是被同一个字母代替,导致密文中字母出现的频率也会出现同样的不平衡性,再加上破译者对发密方背景的了解,要确定密文中包含的信息依然不是一件困难的事。

一个好的解决办法是用多个密文符号来表示同一个字母。每个字母有不同数量的的密文符号替代,替代者的数量与每个字母在英语统计中的频率成正比。例如,字母 a 在书面英语大约占 8% 的比例,所以我们可以分配8个符号来表示它。明文中出现的字母 a 在密文中可以被这8个符号中任一个替换。这样一来,每个符号在密文中的频率都在 1% 左右。类似处理所有英文字母。这样设计出的一套字母替换表,打乱了密文中的英语统计特性。但由于每个密文符号只代表唯一的明文符号,也会带来风险:对于一个给定的密钥,破译者能汇编出一部已知的明文与密文相对应的词典。

好几个世纪以来,上述的几种加密法保证了信息的安全。不过自从频度分析这种方法被引进到欧洲后,密码破译者终于占据了上风。苏格兰玛丽女王的悲剧充分诠释了这种密码的弱点。

  • 上篇:单字母替换密码,多字母替换密码。
  • 中篇:加密的机械化,恩格玛机及其破解,象形文字和楔形文字的破解。
  • 下篇:公开密钥,PGP,量子密钥分发。

导读

破译Playfair

与先前所述的密码术相比,普莱费尔密码功能强大。但它并不是无懈可击,至少可以通过关键词发现法破译这种密码。

这种方法是由美国军方的大弗兰克•穆尔曼在一战时期开发的。他利用关键词的一些特征猜测关键词字母完成破译。穆尔曼知道关键词中每三个辅音字母很可能有两个元音字母,而关键词往往包含一些更为普通的字母。他还发现,如果密文中的某个字母大量和其他字母组合,那该字母很可能就是关键词的字母(因为关键词字母在明文中使用更频繁)。

穆尔曼通过分析密文,找出这些字母,它们很可能包含了大部分关键词字母,顺着这些字母继续下去,将密钥补充完整,反复尝试,就可能找出关键词了(除非运气很好,一般情况下工作量还是很大的)。

在电影《国家宝藏2》中,英国女王曾向美国内战中的南方同盟写过两封关于黄金城的密信,以期南方同盟获得巨额财富战胜北方政府。其中第二封信就是用普莱费尔密码加密的。主人公尼古拉斯凯奇的曾曾祖父为了保护了这个秘密,拒绝为南方同盟破译了这个密码被杀。两百年后凯奇依靠曾曾祖父留下的关键词(death)破解了这个普莱费尔密码,找到了黄金城的重要线索,最终解开了这个谜团。

学习古典密码学的意义:学习设计原理和分析方法

“不可破译”的密码

1586年,英国政府破译了苏格兰玛丽女王和同党谋反的密信,玛丽女王惨遭吊死。而她使用的就是字母替换这种单码加密法。这个事件也正式宣告上述密码已经全部失效。

同年,一位名叫维热纳尔的法国外交家出版了一本《密码理论》,介绍一种以他自己名字命名的新密码,而这本书一直无人问津。直到两百年后莫尔斯电码流行开来,为了防止电报员泄露信息和间谍窥探秘密,维热纳尔密码才被广泛应用。

维热纳尔密码一度被认为是无法破译的,以致让一些掌握这种密码的人洋洋自喜,不过很快,以建立了现代计算机的理论框架而闻名于世的怪才查尔斯•巴贝奇解决了这个难题。

事情起源于一个布里斯托尔的一个牙医赛瓦特。这个牙医其实对密码学知之甚少,1854年,他声称发明了一种新密码,并写信给《艺术协会杂志》企图获取专利。而他只不过是将维热纳尔密码重新包装了而已。巴贝奇写信揭露这个事实,赛维特却不愿承认,甚至为难巴贝奇让他破解这个密码。其实能否破解密码和密码是不是新创造的毫无关系,但这已足以激起巴贝奇的好奇心了。很快,他就成功破解了维热纳尔密码。

对于这样重要的成果,巴贝奇却没有发表它。这也符合他的性格:他一直是这种懒洋洋的态度。而更重要的原因恐怕是英国政府要求巴贝奇保密,从而让他们可以在这方面领先全世界9年——直到1863年卡西斯基也发现了破译方法并将它发表。

有趣的是,在美国的南北战争期间,南方联军仍然在使用黄铜密码盘生成维热纳尔密码,自始至终都只主要使用三个密钥,而那个时候这密码早就被破译了,所以北方政府在情报战上一直是笑而不语的。

单字母替换密码

隐文术:通过把信息隐藏起来的这种秘密通信称为 Steganography(隐文术),由希腊词 Steganos(意为「覆盖」)和 Graphein(意为「写」)派生而来。

希罗多德(Herodotus)以编年史的形式记载了公元前 5 世纪希腊和波斯之间的冲突,其中提到住在波斯的希腊人德马拉图斯(Demaratus)利用已上蜡的一副可折叠的刻写板,先将蜡刮去,再将波斯的阴谋刻写在木板的背面,然后再涂上蜡盖住消息,从而将信息秘密地传递给希腊人。得到警告的希腊人开始武装自己,并最终在波斯人进攻时佯装被包围,并诱使波斯船队进入海湾,运用策略打败了波斯。

希罗多德还讲述了希斯塔亚乌斯(Histaiaeus)的故事:希斯塔亚乌斯想鼓励米勒图斯(Miletus)的阿里斯塔哥拉斯(Aristagoras)反叛波斯国王,为了秘密地传达他的指示,希斯塔亚乌斯剃光了他的一个信使的头发,将信息写在其头皮上,再等信使的头发重新长起来,很明显这段历史时期发生的还不是什么紧急事件。这个信使显然不用携带任何异物,能够自由穿行,不会有麻烦。一旦到达目的地,他就剃光头发,指给联络人看。

中国古代将信息写在小块丝绸上,塞进一个小球里,再用蜡封上,然后让信使吞下这个蜡球。

16 世纪,意大利科学家乔瓦尼・波塔(Giovanni Porta)描述了如何将信息隐藏在一个煮熟的鸡蛋里:把少许明矾和一点醋混在一起制成一种墨水,再用这种墨水将信息写在鸡蛋壳表面。墨水溶液就会经蛋壳上的微孔渗透进去,在已凝固的鸡蛋白表面留下印迹,这样只能剥去蛋壳后才能读取。

早在公元 1 世纪普林尼(Pliny the Elder)就解释了体液如何用作隐形墨水。用体液写的字晾干后即变得透明,但轻轻地加热就能把液体烤焦,从而字迹就以棕色显现出来。许多有机液体都有这样的性质,因为它们富含碳因而很容易被烤焦。事实上,即使是现代间谍也很少知道在标准配备的隐形墨水用完之后还可以用自己的尿液来临时代替。

密码术:在隐文术发展的同时,还有另一种方法也在演化,那就是 Cryptography(密码术),从希腊词 Kryptos(意为「隐藏」)派生而来。密码术的目的不是隐藏信息本身,而是要隐藏它的意思,也就是一种加密的过程。

隐文术和密码术常常混合使用。例如,二战期间流行的微粒照片是一种隐文术。德军在拉丁美洲的间谍将一页文件缩小在直径不到 1 毫米的微型照片上,看上去就是一个点,再将这个点状照片贴在看似无关紧要的一封信的某个句号上面。这种微型照片在 1941 年第一次被美国联邦调查局发现后,德军间谍开始有所防范,在缩小之前,将照片中的信息打乱。

密码术分为两种,即移位和替换。在移位中,字母不变,位置改变;在替换中,字母改变,位置不变。

移位:在《S. 中使用的加密法》中提到的「栅栏加密法(Rail fence cipher)」就是移位加密法的一种。另一种移位形式是早在公元前 5 世纪就出现在斯巴达的称为「Scytale」的装置,外形是一根棱形木棍,外面缠绕着一条皮革或羊皮纸。发送人先沿着木棍纵向在条带上写上信息,然后再解开条带,那么从条带上就看到一些无意义的字母,信息已被打乱了,信使就可以带着这条皮带,如果再来点隐文术的手段,他可以将其伪装成腰带系在身上,而信息却写在反面。复原信息时,接收者只需简单地把条带绕在一根木棍上,其直径应和发送者使用的一般大。Scytale 如下图所示(图片来自 Scytale):

图片 5

替换:与移位并列的密码术是替换。关于替换加密的最早描述出现在《爱经》中,这是由婆罗门学者写于公元 4 世纪的一篇文章,但根据手迹来看,可追溯到公元前 4 世纪。《爱经》建议女人应学会 64 种技术,如做饭、穿衣、按摩和制备香水,还包括一些如咒术、象棋、装订和木工之类的不太常见的技术。第 45 种是密文术,其中介绍的一种方法就是先随机地将字母两两配对,然后将原始信息中的每一个字母用它的配对者来代替。这种形式的密文叫做替换密码。

恺撒移位密码:恺撒频率地使用密文,其中最著名的是简单地将信息中的每一个字母用字母表中的该字母后第三个字母代替,即密码表和明码表相比后移了 3 个位置。

密码的定义及密钥的重要性:一个密码是指任何形式的一种隐秘的替换,其中每个字母都被另一个字母或符号代替。每个不同的密码都代表着一种加密方法,包括算法和密钥两个元素,这两个元素描述了每种加密的精确细节。和算法相对立,密钥的重要性是密码术中永久的一项原则。对此,1883 年,荷兰语言学家奥古斯特(Auguste Kerckhoffs von Nieuwenhof)在其所著的《密码学》一书中作了权威性的陈述:一个密码系统的安全性不在于对加密算法进行保密,而仅在于对密钥的保密。称为科克霍夫原则(Kerckhoffs's principle)

除了对密钥保密外,一个安全的密码系统也必须有一个大范围的可供选择的密钥。在保证密钥数量的同时,密钥的简单性也很重要。因为密钥是发送者和接收者所共知的,密钥越简单,误解的机会就越小。可不通过随机地重排明码字母表来得到密码表,而是选择一个关键词或关键词组,先将其中的空格和重复字母去掉,然后将其作为密码表的前部分密码字母,至于后部分,先将明码字母表中在关键词组出现过的字母去掉,再按顺序接在其后。这种构建密码表的方法在《S. 中使用的加密法》的波雷费加密法和虚无加密法中都有应用。

以上所有替换密码都属于单字母替换密码(monoalphabetic substitution cipher)

尽管不知道是谁发现字母频率的差异可用于破译密码,但是 9 世纪的科学家阿尔・金迪(Al-Kindī)对该技术做了最早的描述。他被誉为「阿拉伯人的哲学家」,他最伟大的著作直到 1987 年才在伊斯坦布尔被发现,名为《关于破译加密信息的手稿》,书中含有对统计学及阿拉伯语法的详细讨论。阿尔・金迪的密码破译方法应用于英语可解释为:首先研究一篇或几篇一定长度的普通英文文章,建立字母表中每个字母的频度表(英语中 E 是最常见的字母,其次是 T、A 等等),然后检查待解决的密文,计算出其中每个字母的出现频率。如果密文中最普遍的字母是 J,那么它很可能就是用来替换 E 的字母;如果密文中第二高频的字母是 P,那么它可能是 T 的替换字母等等。阿尔・金迪的技术被称为「频度分析(frequency analysis)」,它表明了没有必要去检验数亿条有可能的密钥,相反,通过简单的分析密文中每个字符的出现频率就有可能揭示出一条被混乱的信息。

然而不可能无条件地应用阿尔・金迪的方法来破译密码,因为标准频率仅是个概数,不会精确地与每一篇文章的频率相符。1969 年法国作家乔治斯・佩雷克(Georges Perec)写了一本 200 页的小说《逃亡(La Disparition)》,其中没有一个含有字母 e 的单词。更令人称道的是英国小说和评论家吉尔伯特・阿代尔(Gilbert Adair)成功地将《逃亡》翻译成英文,而其中居然也没有一个字母 e。阿代尔将这本译著取名为《真空(A Void)》。由于英文字母中最常见的字母完全没有出现,因而如果将这整本书根据单字母替换密码而进行加密的话,那么天真地试图去解密它将会受到极大阻碍。

阿特巴士(atbash)加密法:在《旧约全书》中有几页文章通过阿特巴士法进行了加密,其原理是取一个字母,指出它位于字母表中正数第几位,再把它替换为从字母表倒数同样的位数后得到的字母。在英文中,例如字母 a 使用字母 z 代替,字母 b 则被 y 替换等等。阿特巴士(atbash)这个名称本身就是这种它所指的替换密码,因为其中 a 和 t 分别指希伯来字母表中的第一位字母 aleph 和倒数第一位字母 taw,而 ba 和 sh 则代表字母表中的第二位字母 beth 和倒数第二位 shin。

现知的第一本描述密码使用的欧洲书籍是于 13 世纪由英国圣方济会的修道士和博学家罗杰・培根(Roger Bacon)所写。该书名为《密文其实并不神奇》,讨论了七种将信息保密的方法,并提醒道:「不用隐秘的手法写一条密文的人是愚蠢的。」

14 世纪的杰弗里・乔叟(Geoffrey Chaucer)不仅在文学上有所成就,也是个天文学家和密码编码学家。在早期欧洲著名的几个有关密码的例子中,其中一个就是他的杰作。在他的《星球概述》一书中,他附加了题为《星球的赤道》的附录,对其中几段进行了加密,将明文中的字母用符号来代替,例如 b 变成了 δ,本质上相当于传统的单字母替换。

到了 15 世纪,欧洲的密码编码术已经是一种蒸蒸日上的行业了。作为文艺复兴的心脏,意大利的几个自治城邦之间的外交大使之间相互发送的信息,都由专门的密码机构完成,每个大使都有一个密码助理。

欧洲第一位伟大的密码破译家是乔瓦尼・索罗(Giovanni Soro),他在 1506 年被任命为威尼斯人的密码助理。索罗的名气响遍整个意大利,友好城邦都会将截获的信息送到威尼斯交给索罗破译。在欧洲其他地方,一些宫廷也开始雇用有能力的密码破译者,如费利波特・巴布,法国国王弗朗西斯一世的密码破译家。巴布因其非凡的的执着而著名,为了破解被截获的信息,他能日夜工作达数星期。但不幸的是,这使得国王有足够机会与巴布的妻子长时间私通。到了 16 世纪末,随着弗朗索瓦・韦达(François Viète)的加盟,法国人进一步加强了其破解密码的能力。韦达对破解西班牙的密码情有独钟。

对单字母替换密码的几个改进,但效果并不好:

  • 引入空符号:在密文中插入不使用的符号,其频率不定,用以干扰频度分析。
  • 有意拼错几个单词:同样用于干扰频度分析。
  • 引入代码:以单词为单位,将每个单词用另一个不同的单词或符号替换。有两大缺陷:密码表过于庞大,变成上百页的密码簿,编码困难;密码簿被截获后,重新编辑和分发密码簿非常痛苦。

玛丽女王与巴宾顿计划(Babington Plot):苏格兰玛丽女王被英国伊丽莎白女王囚禁多年,年轻的安东尼・巴宾顿(Anthony Babington)与其他天主教同道密谋营救玛丽女王、谋杀伊丽莎白女王并取而代之。巴宾顿与玛丽女王通过同为天主教徒的吉尔伯特・吉法德(Gilbert Gifford)互传密信,岂料吉法德是双重间谍,他同时为伊丽莎白女王的首席秘书弗朗西斯・沃尔辛厄姆爵士(Sir Francis Walsingham)效力,实际上正是沃尔辛厄姆派吉法德设法接近巴宾顿所在的组织。巴宾顿与玛丽女王的每条信息,都被吉法德拿给沃尔辛厄姆,由其专门负责伪造的手下拆开并复制,再用同样的邮票封好原信后交回吉法德。

巴宾顿使用的密码不是简单的单字母替换密码,而是一种代码与密码的组合,它包括 23 个用来替换字母表中字母的符号(不包括 j、v 和 w)和 35 个代表单词或词组的符号,另外还有四个空符号和一个类似 σ 的符号,它们表示其后所接的符号代表一个双字母(下图来自 Babington Plot):

图片 6

沃尔辛厄姆在伦敦建了一座密码学校,并雇用托马斯・菲利普斯(Thomas Phelippes)作为他的密码助理。菲利普斯破译了巴宾顿和玛丽女王之间的信,在最后阶段甚至根据沃尔辛厄姆的命令,在玛丽女王的信后伪造了一个附言,诱使巴宾顿报出所有参与者的名字。最终,巴宾顿和他的 6 个同伙都被抓捕并被砍头,玛丽女王也同样被送上了断头台。

苏格兰玛丽女王的密码清楚地说明了使用一个脆弱的密码有时比完全不用密码还糟糕。玛丽女王和巴宾顿之间毫无顾虑地直接交流计划,因为他们相信他们的通讯是安全的。而如果他们公开地通信,他们将以一种更谨慎的方法来提及他们的计划。而且,他们对其密码的信任使得他们特别轻易地接受了菲利普斯的伪作。发送者和接收者对他们密码的隐秘性是如此地相信,以至他们认为敌人是绝不可能模仿他们的密码来加入这一段伪造的密文进去。正确使用一个牢固的密码当然会有利于发送者和接收者,但错误使用一个脆弱的密码却会使人对安全性产生一种错觉。

密码学,是一门将信息进行加密处理与传递,以及分析加密信息的学科。根据以RSA为代表的公钥加密体系的出现,可以将密码学的发展过程分为古典密码学与现代密码学两部分。古典密码学以“置换法”与“替换法”为基础,多应用于军事与情报领域;现代密码学则建立在数学、计算机与通信科学的基础上,除了加密信息之外,数字签名、数据完整性、身份认证等也是现代密码学的研究课题。

希尔密码

普莱费尔密码特别之处在于一次加密多个字母。当密码学家了解这种加密法后,他们进一步开始尝试以三连字甚至更多字为单位的加密法。但是他们失败了,其中一个重要原因是维护三维(或以上)表是十分困难的。要成功设计这种加密法,需要引进专业的数学方法。

希尔密码诞生在1929年,是以其发明人Lester S. Hill来命名的。他是纽约亨特学院的数学教授,在1929年发表一篇论文提出了这种基于联立方程的加密算法。

希尔密码以每次加密m个明文字母块完成加密过程。首先需要对26个字母赋值,通常是a=0,b=1,…,z=25(希尔本人采取的是随机赋值)。块中的每个字母的数值一起用于生成一组新的数值。例如,m=3,需要加密的明文块的三个字母的数值(设为p1、p2和p3)通过下面的方程组转换成密文数值C1、C2和 C3。

图片 7

该加密法的密钥就是矩阵

图片 8

举个例子,现在对矩阵赋值如下:

图片 9

利用这个密钥和上面的方程,明文“now”首先转换成数字:13 14 22。将这些数值代入方程解得密文数值:23 20 4。再将这些数字转换成字母后,就得到密文“xue”了。

加密密钥是矩阵M,那么解密密钥就是 M -1 。这意味着要使解密可行,矩阵M必须是可逆的,因此密钥值并不能随意选取。从m=3的例子中归纳出用数学方法表达希尔密码的一般形式如下:

密钥为可逆矩阵

图片 10

将明文分块使得每块含有n个字母(最后不足位以z不足),用n×1的向量表示。例如第 i 块含有字符p1,p2,p3,…,pn:

图片 11

那么密文就由如下方程确定:

图片 12

希尔密码很好的防止了密文被攻击。而当密钥矩阵越大时,该加密法抗攻击能力就越强。但是用已知明文攻击法可以很容易地破译该密码。其攻击过程类似先前提到的汇编一部明文与密文的对应词典。即用已知明文和密文建立方程组,求解后寻找出密钥。

古典密码也是,俩门派:置换和代换,顾名思义,一个是换了个原来有的,一个是换了个原来没有的。学术点讲就是前者明文和密文空间一样,后者 不一样。你要是问我啥是明文空间和密文空间啊,我就呵呵。是M 和 C。m明文的集合,c密文的集合。对了明文有时候用p表示哦,plaintext。

维热纳尔密码的原理

维热纳尔密码又叫做维吉尼亚密码。它的加密过程是这样的:首先选择一个无重复字母的密钥词(比如 MATH ),重复密钥词直至它成为一个和明文信息一样长的字母序列,再利用下面这种方阵加密这条信息。为加密第一个字母 I,此时它下方对应的密钥词是 M,于是,加密 I 时由 M 对应的那行中读出 i 列下的字母即 U,类似的,得出所有密文:

信息 I L O V E Y O U
密钥 M A T H M A T H
密文 U L H C Q Y H B

图片 13

密码学初探,密码好玩的事。这无疑是一种高明的加密手段,维热纳尔密码用严格的轮换方式重复使用一串简单的代换密码,很好的伪装了基础语言中的字母频率。它还有很多变化,比如有一种可以允许密钥词中出现重复字母。每种变化都会产生一些新的特征,从而引发破译方式的变化。

查尔斯•巴贝奇是破译维热纳尔密码的第一人,他的思路是:在已知密码周期(即所使用的密码组件数目,显然,上述版本的维热纳尔密码周期就是密钥词长度)为 p 的情况下,将密文改写成 p 行,使得每一列按原来的密文顺序排列,例如,p=3,密文 c1c2c3c4c5c6c7c8c9… 就排列成:

c1 c4 c7…

c2 c5 c8…

c3 c6 c9…

这样排列后,每行都是使用同一简单代换密码所得出的,如此就可以对每一行都使用上一节提到过的统计分析了。事实上,对每一行而言,这种简单的代换密码正是凯撒密码。

所以对于维热纳尔密码的破译者来说,关键就在于确定周期 p,巴贝奇则用了一种精巧的方法:在密文中搜索重复的字符串,它意味着两个重复模式之间的距离可能等于周期的整数倍!

难题又被破解!再一次,密码编译者开始寻找新的方法,继续这场智的较量。

多字母替换密码

单字母替换密码在频度分析面前显得非常脆弱,迫切需要编出一种更强大的新密码。15 世纪佛罗伦萨的博学者里昂巴蒂斯特・阿尔伯提(Leon Battista Alberti)建议用两个或两个以上的密码表,在将信息译成密码时交替使用,以迷惑一些密码破译师,称为「阿尔伯提密码(Alberti cipher)」。

在阿尔伯提想法的基础上,布莱兹・德・维热纳尔(Blaise de Vigenère,又译作「布莱斯・德・维吉尼亚」)编出了一个系统的、更为有效的新密码,称为「维热纳尔密码(Vigenère cipher)」。其长处在于使用的是 26 个不同的密码表而不是单一的密码表来加密信息。加密的第一步是构造如下的维热纳尔方阵(图片来自 Tabula recta):

图片 14

然后选用一个关键词,对应明文的长度,一遍一遍地拼写关键词,直到明文中的每个字母都对应于关键词中的某个字母。然后将关键词字母所在行、明文字母所在列的字母作为密文字母,重复上述过程即完成加密过程。维热纳尔有两个优点:

  • 不惧怕频度分析。密文的相同字母可能对应不同的明文字母,同样地,明文的相同字母可能对应不同的密文字母,频度分析不再有效。
  • 具有数目众多的密钥。可使用字典中任一个单词,或单词组合,或者虚构的词作为关键词。

1586 年,维热纳尔出版了一本关于密文的书《密码理论》(同一年,托马斯・菲利普斯正在破解苏格兰玛丽女王的密码),但在接下来的两个世纪里,维热纳尔加密法并没有得到广泛的应用。由于其过于复杂,并不适用于需要速度和简便的军事通讯中。阿尔伯提密码和维热纳尔密码都属于「多字母替换密码(Polyalphabetic substitution cipher)」。

同音替换密码(Homophonic substitution):每个字母有不同数量的替代者,替代者的数量与每个字母的频率成正比。例如,字母 a 在书面英语中大约占到 8% 的比例,因此可以分配 8 个符号来代表它。明文中出现的每个字母 a 在密文中可以被 8 个符号中的任一个替换,因此在加密完成之后,每个符号将占到密文的 1%。同样,字母 b 在英语中大概占 2%,因此分配两个符号代表它,依此类推。

可根据英语中每个字母的特性找到破译同音替换密码的线索。例如,字母 q 的后面只能接一个字母就是 u。如果我们正在尝试破解一篇密文,我们知道字母 q 在英文中相对少见,因此很可能只有一个符号来代替它。我们也知道字母 u 在英语中大概占 3% 的比例,因此可能有三个符号可以用来替换它。因此如果我们发现密文中一个符号后面总是跟着三个特定的符号,那么我们有理由猜测这个符号代表的是 q,而其他三个符号表示 u。密文中的其他字母也可根据它们彼此之间的关系慢慢破译出来。

同音替换密码本质上是单字母替换密码,因为虽然一个明文字母可表示成多个符号,但每个符号只能表示一个字母。另外,一旦密码表被确定,那么在整个加密过程中它是保持不变的,尽管每个字母有几个加密选择。而多字母替换密码在加密时必须不断地在不同的密码表之间来回切换。

路易十四的大密码(Great Cipher):由一对父子发明:父亲安东尼・罗西格诺(Antoine Rossignol)和儿子博纳凡托・罗西格诺(Bonaventure Rossignol)。对他们能力一个最好的说明就是由他们名字形成的单词成为法国人的一个俚语,这是用来表示撬锁的一种装置,意在影射他们破解密码的能力。

罗西格诺父子发明的大密码在他们去世后就停止了使用,它的具体细节也很快失传,使得法国文档里的加密文件不能再被读懂。直到 19 世纪末,法国军事密码机构著名的专家埃提恩尼・巴泽利斯(Étienne Bazeries)才破译出大密码。在某一页出现多次的数字(124-22-125-46-345)经过巴泽利斯的分析被认为是代表 les-en-ne-mi-s,意为「les ennemis(敌人)」。由此衍生出的音节插到密文中,像填单词游戏一样更多的单词被猜出,又可以确定更多的音节,这些音节又可以推出其他的单词等等。也有特殊情况,有时一些数字代表的是单个字母而不是音节,有时一个数字既不代表一个音节,也不代表一个字母,它的存在仅仅是用来删除前面一个数字,部分编码表如下所示(图片来自 Great Cipher):

图片 15

到了 18 世纪,密码破译术已相当盛行,通常是政府的几组密码破译者一起工作。每个欧洲政权都拥有自己的密室——破解密码和收集情报的中枢。最有名的、也最有组织和效率的密室是维也纳的勘兹雷(Geheim Kabinets-Kanzlei)。密室的存在及电报的发展,使得单字母替换密码不再安全,密码编码者最终不得不采纳更复杂并且更安全的维热纳尔密码。

摩斯电码(Morse code)本身并不是某种形式的密码,因为对信息而言没有任何隐藏。点和短横仅仅是用来表示字母的一种便捷方法。摩斯电码事实上就是另一种形式的字母表(图片来自 Morse code):

图片 16

巴比奇破解维热纳尔密码:查尔斯・巴比奇(Charles Babbage)是一个性情古怪的天才,他最著名的成就是建立了现代计算机的理论框架。他成功地破解了维热纳尔密码,完成了一次自 9 世纪阿拉伯学者提出频度分析破解单字母替换密码以来,在密码破译学史上最伟大的突破。破解过程如下:

  • 寻找密文中的重复序列,查看每种重复序列的间隔字母数。
  • 计算所有间隔字母数的质因数,查看每个间隔数都有的质因数,即为关键词的长度 L(例如下图中可以确定关键词长度为 5)。
  • 将密文分成 L 个部分,第一部分为 1、L 1、2L 1、3L 1……第二部分为 2、L 2、2L 2、3L 2……每个部分都是根据一个单字母替换密码来加密的。
  • 对每个部分使用频度分析,并与标准频度分布对比,以确定每个部分所使用的密码表,即对应关键词的一个字母。
  • 将上述 L 个字母串起来即为加密所使用的关键词,使用此关键词做完整的密文解密,即可得到明文。

图片 17

巴比奇可能是在 1854 年成功地破解了维热纳尔密码。但他的发现却完全不为人所知,因为他从未发表它。这个发现直到 20 世纪当学者检查巴比奇丰富的笔记时才被公布于世。而与此同时,普鲁士军队的一位退役军官弗里德里克・威廉・卡西斯基(Friedrich Wilhelm Kasiski)也独立地发现了这种技术,他在 1863 年发表了他在密码破译学上的突破《加密和解密的艺术》,这个方法后来被称为卡西斯基测试(Kasiski examination),而巴比奇的贡献却很大程度上被忽略了。

在维多利亚时代,英国年轻的情侣禁止公开表白各自爱慕之心,甚至不敢互相通信,以防他们父母截住并偷看信的内容。这使得情侣之间通过报纸的个人信息专栏互相发送加密的信息。这些所谓的「激情栏(agony columns)」引起了许多密码破译师的好奇,查尔斯・巴比奇据悉就曾着迷于这种活动。他和他的朋友查尔斯・惠特斯通(Charles Wheatstone)以及巴伦里恩・波雷费(Lyon Playfair, 1st Baron Playfair)一起发明了一种灵巧的波雷费密码(Playfair cipher),也是《S. 中使用的加密法》其中一种加密法(维基百科上并没有提到巴比奇对此加密法有贡献)。有一次惠特斯通破解了《时代》杂志上一位牛津大学学生的留言,留言中暗示他的情人与他一起私奔。几天后惠特斯通插了一句留言,用同样的密码加密,建议这对情况不宜采取这样鲁莽的反叛行为。不久以后,杂志上出现了第三句留言,这次没有加密,是由那位女情人发来的:「亲爱的查理,不要再写了,我们的密码已经被发现了。」

针孔加密法(Pinprick encryption):古希腊历史学家埃涅阿斯(Aeneas Tacticus)提出一种秘密通讯的方法,先找到一篇无关紧要的文章,再在文章中一些特定的字母下面用针刺上小孔,这些字母可以拼成一段密文,接收者很容易识别。然而如果一个外人看到这一页,他可能会忽略这难以察觉的针孔,也就忽略了其中的密文。两千年后,英国写信的人使用了同样的方法以避免过多的邮政费用。在 19 世纪中期邮政系统革新之前,发送一封信大约是每 100 英里 1 先令,超过大部分人的财力。然而报纸可以免费邮寄,于是人们开始使用针孔在一张报纸的正面拼出一段信息,然后再通过邮局发送这份报纸,不需付一分钱。英文原著中对针孔加密法的描述及示例(图片来自 @BakaTakasugi):

图片 18

比尔密码(Beale ciphers):19 世纪美国西部的一个牛仔托马斯・比尔(Thomas Beale)聚焦了一大批财富,有一个藏有价值 2000 万美元珠宝的宝藏,并写了一套神秘的密文(即比尔密码)描述了这个宝藏的地点。关于这个故事以及那些密文都包含在 1885 年出版的一个小册子里。尽管只有 23 页,但是这本小册子还是困惑了几代的密码破译师,吸引了成百的觅宝者。

比尔密码共有三页,都是密密麻麻的数字,其中第二页在出版的小册子中已经给出破译方法及原文,使用的是书卷密码(Book cipher),其中一本书或者一篇文章本身就是密钥,姑且称这样的书或文章为钥文。密码编码者顺序地给钥文的每个单词编号,这样每个数字就可以用来代替关联单词的第一个字母。然后,通过将明文中的每个字母替换成上述的数字来加密一个信息。注意:由于钥文中的单词首字母可能重复,因此同一个字母可能使用不同的数字替换。比尔密码的第二页使用的是《独立宣言》作为钥文,而第一页和第三页至今仍未破译。

比尔密码之所以难以破译,是因为信息是一次性的,因为它们关系到如此贵重的一个宝藏,比尔或许准备为第一和第三页密码写一篇特别的一次性钥文。事实上,如果钥文真的由比尔亲笔所写,这也就解释了为什么搜寻已出版的文章而没有结果的原因。我们可以试想比尔写了一篇 2000 字的私人文章,可能就是关于捕猎野牛的事情,而这篇文章只有一份。只有这篇文章的持有者,即拥有了独一无二的钥文,才能够破译第一页和第三页比尔密文。为一个信息专门写一篇一次性的钥文要比使用一本出版的书作为钥文安全得多。但这需要发送者有时间写出钥文并能够传给接收者,而这个要求对于每日通讯来说是不可能的。

对 NSA 的调侃:美国国家安全局很少公开过什么事情,有人提议 NSA 不是用来指 National Security Agency(国家安全局),而是指「Never Say Anything(沉默主义者)」或「No Such Agency(没有这样的机构)」(在电影《Snowden)》中就出现过 No Such Agency 的调侃)。

以上。

摘要

其他的加密技术

到这里我们完成了对历史上几种最具代表性的加密系统的介绍,然而这也并非密码史的全部经典。还有不少精妙的加密法就不在此一一详述了。比如二战时期德军使用的Enigma加密法。它属于机械化的加密方法。Enigma加密法利用电机系统实现多码变换,这种系统叫做回转轮系统。回转轮是一个圆盘,它的两面都有电子接点,每个接点代表字母表中的一个字母。回转轮内部有连接各接点的电线,这种连接方式定义了简单单码替换方式。数个这样的回转轮和一个反射器组合起来就构成了强大的Enigma加密机。然而,这个加密法最终还是被英国政府联合波兰破解了。

置换密码就是列置换和周期置换两兄弟,倒序那个算捡来的吧。

置换法依照一定的规则,改变原始信息中的字母排列顺序;替换法将原始信息中的字母按照一定的规则替换成其他字母。置换法与替换法的安全性较差,古阿拉伯的学者们开创了破译加密信息的科学——密码分析学,通过频率分析的方法破解替换式加密法。

结语

密码学从最初的凯撒密码至今,走过了一个漫长的道路。计算机的超强计算能力,让上述经典的加密方法都已失效。但是先哲的思想并未失效,密码学也仍然在飞速发展,眼下它正朝着量子系统前进。一旦进入这种新的世界,密码学会发生什么变化,我们只能靠猜测了。但可以预见的是,这一定不是密码学故事的结束,而只是刚刚开始。

列置换:顾名思义,操作及输出都是以列为单位。将明文以密钥长度为列数形成矩阵,按照密钥的顺序进行列选出,然后一列一列的输出。

在长达一千多年的时间里,古典密码学以置换法与替换法为基础不断演进。以维吉尼亚密码为代表的多字母表替换式加密法轮流使用多个不同的替换式密码表,依次对明文中的字母进行加密。第二次世界大战时德军使用的“恩尼格玛”是一种基于复杂的多表替换加密原理的机械式密码机,但最终由于自身加密算法的缺陷,被图灵设计的“炸弹”攻克。

 

置换式与替换式加密法的弱点在于没能完全消除密文中有关明文的某些特征,保留了明文中的某些信息。奥古斯特·柯克霍夫在19世纪提出的柯克霍夫原则概括性地总结了加密算法应遵循的设计原则:即使加密系统的各个环节都是公开知识,只要密钥未被泄漏,加密系统都应该是安全的。

列置换密码(距阵置换密码)

加密算法的安全性问题本质在于:如何降低攻击者在了解加密算法,并拥有足够长的密文片段的前提下,猜测出正确密钥的可能性?1948年,香农创立了信息论,并在次年的一篇论文中从数学的角度讨论了加密系统,人们开始从科学的角度探究密码学的奥秘。

明文:ming chen jiu dian fa dong fan gong

风险提示:量子计算技术的潜在威胁

密钥:yu lan hua

目录

去掉密钥重复字母:yulanh,得出距阵列数为6;将明文按行填充距阵。

1 隐匿法

得到密钥字母顺序: 653142;

2 加密法

按列(依顺序)写出距阵中的字母。

3 持续千年的智力竞赛:加密与解密

密文:giffg hddn0 njngn cuaa0 inano meiog

4 古典密码学的圣杯

解密:加密的逆过程;

5 攻克“恩尼格玛”

 

正文

周期置换:其实就是在列置换的基础上,进行行输出。

密码学,是一门将信息进行加密处理与传递,以及分析加密信息的学科。“密码学”一词的词源来自古希腊语“”和“书写”,意为“秘密书写”,其历史几乎与人类有文字记载的文明一样悠久。古希伯来学者在公元前六世纪左右就掌握了“单字母表替换式加密法”,在之后的两千五百多年里,古典密码学在替换式加密法的基础之上不断发展演进。古典密码学多应用于军事与情报领域,而微型计算机与现代密码学的发展能够保护普通人的日常通信免受第三方的窥探。现代密码学建立在数学、计算机科学与通信科学的基础上,除了信息的加密与解密之外,数字签名、数据完整性、身份认证等也是现代密码学的研究课题。今天人们日常生活中的网络支付、电子商务、电子货币等都是密码学这一人类两千多年来智慧结晶的应用。

 

密码学的概念与人们平时登陆网站、使用银行账户的“密码”并不相同。这些用于身份认证的“密码”,更准确的翻译是“通行词”或“通行码”,它是现代密码学的诸多应用之一,请读者注意区分两者的区别。

周期置换密码

受限于篇幅,有关密码学以及密码学在区块链中应用的内容将分两篇专题介绍。

  明文:mingchen jiu dian fa dong fan gong

1

  加密密钥:3421(i=1,2,3,4的一个置换f (i) =3,4,2,1)

隐匿法

  加密:将明文分组(4个字母一组),然后根据规定顺序变换

隐匿法的历史非常久远,可以追溯到公元前5世纪古希腊与波斯帝国的战争年代。公元前480年,波斯舰队在“万王之王”薛西斯一世的率领下秘密集结,准备对希腊发起进攻,然而这一秘密行动被一位遭到流放、居住在波斯的希腊人狄马图拉斯发现了。他将波斯军队准备进攻希腊的消息写在木板上,并用一层蜡将文字遮住,成功骗过了路途中的波斯卫兵,将信息传回了希腊。希腊城邦联合起来,抵御住了波斯人的突袭。而遭遇挫败之后,曾经盛极一时的波斯阿契美尼德王朝也开始走向衰退。

                    ming chen jiud ianf adon gfan gong

尽管简单地“将信息起来”与我们今天熟知的密码学相差甚远,被称为“隐匿法”的秘密书写方式却标志着人们开始探索信息保密的方式。

                      ngim enhc udij nfai onda anfg ngog

2

  密文:ngimenhcudijnfaiondaanfgngog

加密法

  解密密钥:4312(3412的逆置换)

隐匿法仅仅将信息藏匿起来,一旦藏匿的方式暴露,或是负责传达信息的信使叛变,信息安全也无从保证。加密法则注重信息本身的含义,信息的发出方与接收方事先约定,将信息按照一定的规则进行转译,接收方在收到后遵循约定的规则就可以还原原始信息,而即使信息被第三方截获,如果不知道转译规则,也无法还原出原始信息。

 

加密法的出现标志着古典密码学的开端。在上面的例子中,未经加密的原始信息称为明文,按照特定的规则对明文进行转译后得到的信息称为密文,这个规则称为加密算法。古典密码学的加密算法大多是以字母、单词或是短语为基本单位,又可分为置换法和替换法两大类。

没啥说的,直接来代换密码:

置换法依照一定的规则,改变原始信息中的字母排列顺序。公元前5世纪,斯巴达军队采用一种名为“密码棒”的工具对信息进行加密。发信人将长条形的羊皮纸带缠绕在一根木棒上,将信息横向书写,最后将羊皮纸解下。收信人将信纸缠绕在同样直径的木棒上,就能够还原信息。而羊皮纸上的文字看起来是无意义的,并且用尺寸不相同的木棒也无法还原出原始信息。

也是两个流派,单表替换和多表替换。

但只要了解这种密码的加密方式,就能很容易地解读密文。从密文的第一个字母开始,每数到它之后的第N个字母,记下该字母。记录到密文结尾后,再从第二个字母开始重复这样的操作,以此类推,很快就可以还原明文信息。其中N取决于木棒的直径,写下N个字母后,纸带正好绕木棒一圈,选择不同的N,同样的明文经过加密得到的密文也不相同。发信人和收信人要事先约定好同样的N,收信人才能还原密文。同时N不能被第三方知晓,才能保证加密通信的安全。这里的N称为密钥,是加密通信的参与方共同享有的秘密知识,用于加密和解密信息。

单表代换密码:一个密文字母表。加法密码(著名的凯撒密码就是)乘法密码和仿射密码。

替换法将原始信息中的字母按照一定的规则替换成其他字母。据传,凯撒大帝使用替换式加密法写作书信。凯撒大帝将信息中的每个字母后移三位,例如A替换成D,Y替换成B,这种加密法称为凯撒挪移式加密法。在这个例子中,密文相比明文,每个字母都被后移了3位,密钥可以用3表示。密钥可能的取值范围为1~25的自然数,称为密钥空间。明文里所有可能出现的字母的集合称为明文空间,密文里可能出现的字母集合称为密文空间,替换法中的密钥可以表示为明文空间到密文空间的一个映射,在古典密码学中又称为密码表。密文空间可以与明文空间相同,例如凯撒密码中,密文的字母仍然是26个拉丁字母。密文空间也可以是明文空间的超集,例如在密文中混入一些无效字符,以干扰试图破译密码的行动。密文空间还可以与明文空间完全不相关,例如在柯南道尔所著的福尔摩斯系列的《跳舞的人》中,罪犯用26种形态各异的跳舞的小人来替换英文字母。

主要说下仿射密码

公元8世纪,阿拉伯哈里发帝国的第二个世袭王朝——阿拔斯王朝在巴格达定都,其建立之初的一百年是伊斯兰文明的黄金时代。据记载,阿拔斯王朝的官员们使用替换式加密法保护机密的行政事务、税收数据,相信这能够帮助他们建立一个廉洁、高效的政府。巴士拉的语言学家卡里尔撰写了《加密信息手册》,使用排列组合对阿拉伯语单词的加密法进行分析。此外,阿拉伯的学者们还开创了破译加密信息的科学——密码分析学。

f(mi)=ci=mj,j=k1i k2 mod n ,i,ki,k2{0,1,...,n-1}

3持续千年的智力竞赛:加密与解密

多表代换密码:多个密文字母表。Vigenere密码,Playfair密码和hill密码

古典密码学多用于军事、政治、外交领域重要情报的传递,希望刺探这些秘密的人自然不在少数。阿拉伯学者们在统计语言学资料时发现,在样本容量较大,有意义的阿拉伯语文本中,每个字母出现的频率是不一样的。字母a和字母l在阿拉伯语中出现频率最高,因为“al”是阿拉伯语中的定冠词,相当于英语的“the”,此外,元音的出现频率也比较高。这些成果很快被运用到密文分析中。

 

之前介绍的替换式加密法中,明文中的所有字母都遵循同一套规则进行替换,这样的加密法称为单字母表替换式加密法。公元9世纪,阿拉伯科学家肯迪在《解译加密信息》一书中阐述了对这种加密法的解译方式。如果能确定原文所使用的语言,首先列举出密文中出现的所有字母,统计它们各自出现的频率并排序,对照该语言中字母出现的频率顺序,就可以开始尝试对密文进行分析,这种方法称为频率分析法。频率分析还可统计某种语言中特定的字母组合出现的频率,如英文中的“ee”,以及某个字母前后特定字母出现的频率,如英文中字母“q”之后一定跟随”u”等。直到数百年后,中世纪的欧洲学者才掌握这一方法,并且决定了两位女王的命运。

主要说下Vigenere密码

1586年,英格兰政府对天主教的迫害日益加剧,安东尼·贝平顿与几位同党密谋策反,计划救出被伊丽莎白女王软禁的苏格兰女王、伊丽莎白女王的表妹、信仰天主教的玛丽女王,并暗杀伊丽莎白女王。贝平顿通过密使传递使用替换式加密法加密的书信,与玛丽女王商讨暗杀计划。贝平顿设计的更加复杂的替换式加密法使用23个符号替换除j、v、w之外的英文字母,4个不具有任何意义的混淆符号,表示下一个字母连续出现两次的“dowbleth”符号,以及若干个符号替换常用的单词,以尽量减少遭到频率分析法破译的可能。

Vigenere密码是周期代替密码

但可惜的是,贝平顿信任的密使其实是一位双面间谍,背地里将他与玛丽女王的密函交给伊丽莎白女王的国务大臣、间谍头子沃尔辛厄姆,后者先打开信封,抄写一份密文,再重新伪造封缄,并将密文交给密码学家托马斯·菲利普分析。菲利普通过频率分析法破译了密码,并在玛丽女王寄出的一封信件后附加了一段伪造的密文,诱使贝平顿说出参与计划的同伙的名字。暗杀计划暴露后,玛丽女王、贝平顿以及其密党都遭到处决。

当周期为1时,就是单表代替密码(加法密码)。

以上是一个过于信任加密方法的安全性,以致造成悲剧结局的例子。如何衡量加密通信安全与否是一个重要的问题,加密通信的过程可以划分为选择加密方式、约定密钥、加密明文、传输加密信息、还原明文几个步骤。古典密码学中,绝大多数加密方式都是替换法、置换法或者两者的结合,因此加密方式几乎不是秘密,试图对密文进行分析的人可以通过尝试所有可能的密钥进行解译,当某个密钥还原出的明文出现了有意义的单词,就说明找到了正确密钥。因此,密钥空间越大,意味着破译者需要尝试的密钥数就越多,密码就越安全。凯撒挪移式加密法只有25个可能的密钥,安全性非常差。

  用户钥:有限序列k =(k1,k2,…,kd)

奥古斯特·柯克霍夫在19世纪提出的柯克霍夫原则概括性地总结了加密算法应遵循的设计原则:即使加密系统的各个环节都是公开知识,只要密钥未被泄漏,加密系统都应该是安全的。换一个方式来说,加密系统的安全性应依赖于密钥的保密,而不是加密算法的保密。

工作钥:无限序列K=(K1,K2,…,Ki,…) ,是用户钥的

除此之外,加密算法自身可能也存在安全性漏洞,虽然密钥空间非常庞大,但破译者也能够通过分析密文的某些特征,缩小可能的密钥范围。明文的目的一般是传递某些信息,因而是有意义的,存在某些语言学或统计学上的特征,而密文则一定程度地保留了这些特征,如单字母表替换式加密法保留了不同字母出现的频率特征。为了消除这些频率特征,一些增强的替换式加密法被发明出来,但仍未能解决替换式加密法的缺陷。例如同音替换式加密法将出现频率较高的字母对应多个不同的密文,从而使密文中各个字母出现的频率相近,但字母组合的频率信息仍然没有完全消除,仍存在被破译的可能。法国国王路易十四用来加密机密文件的“大密码”采用替换字母对的方式,两个世纪以来都没有遭到破译。19世纪末,人们发现大密码的密文中出现的数字数量接近676,即两个字母组成的字母对可能的数量,从而猜到了其加密方式,并用频率分析破译了它。

周期性(周期为d)扩展,即

玛丽女王的例子还说明,信息传递的途径并非绝对安全。由于通信的双方需要事先约定同样的密钥,如果传递密钥的方式不安全,整个加密通信系统也形同虚设,信息安全保卫战就是“密钥保卫战”。

Ki=ki mod d ,i =1,2,3,…

早在15世纪初,文艺复兴时期的佛罗伦萨艺术家阿尔伯蒂已经认识到了单字母表加密法在频率分析法面前不堪一击,他提出了一套新的加密方法,即轮流使用多张密码表,依次对明文中的字母进行加密。这一方法由法国外交官维吉尼亚所发扬光大,发明了“维吉尼亚加密法”。维吉尼亚加密法采用26套不同的密码表,对应密钥为0~25的凯撒挪移式密码表,并以从A~Z的英文字母表示。加密的过程是,选择一个密钥单词,例如KEY,然后按照密钥单词中的字母顺序,依次对明文字母按照相应的密码表进行加密,第一个字母使用“K”对应的密码表替换,第二个字母使用“E”,第三个用“Y”,第四个再回到“K”,以此循环直至加密结束。这一类加密法称为多字母表替换式加密法,同样的明文字母可能会被加密成不同的密文,相同的密文字母不一定对应相同的明文,给破译者带来很大的干扰。维吉尼亚加密法的密钥空间几乎是无限的,一度被视为不可破译的,是一千年以来古典密码学的重大突破。

  明文:M=m1m2…mi…ml

但英国发明家查理`巴贝奇不认为破译维吉尼亚密码是一项不可能完成的任务。当人们开始了解维吉尼亚密码的加密算法,它的致命弱点也随之浮现。维吉尼亚密码用于加密的基础密码表只有26种,而且都是已知的凯撒密码表。维吉尼亚密码加密明文使用密码表的顺序是固定的,因此同一个明文单词,被加密成的密文仅有有限种可能。可能的密文种类数取决于密钥单词的长度。并且位置相差密钥单词长度的所有字母都是使用同一张密码表进行替换的。巴贝奇发现,维吉尼亚密码的密文每过一部分,就会出现重复的字母组合,这意味着两个可能:一,不同的明文片段被密钥单词的不同部分加密成了相同的密文;二、同样的明文片段恰好由密钥单词在同样的起始位置进行加密,形成了相同的密文。如果重复的字母组合足够长,第一种情形出现的可能性就远远小于第二种。第二种情况还揭露一个事实:密钥单词长度一定是重复的字母组合位置相差数的因子。巴贝奇记录下所有重复的密文字母组合位置之差,以及它们的所有因子,其中出现最多的因子就是密钥单词可能的长度。合位置之差,以及它们的所有因子,其中出现最多的因子就是密钥单词可能的长度。

密文:C=c1c2…ci…cl

知道了密钥单词长度这一重要信息,巴贝奇把密文分成N组分别由N个单字母表加密的片段。尽管这些零散的片段对应的明文是没有意义的,但只要这个片段出自完整的、有意义的信息,那么它的字母频率分布仍然遵守书写信息所使用语言的规律。使用频率分析法,维吉尼亚密码就可以被破译。加密者为了方便记忆,通常喜欢选取有意义的密钥单词,但这也使密码变得更加不安全。

工作钥:K=K1K2…Ki…Kl

4

加密:ci=mi+Kimod n,其中n为明文字母表的长度

古典密码学的圣杯

例:用户钥为cat,对明文“vigenere cipher”加密

维吉尼亚密码法看起来拥有庞大的密钥空间,如果使用26个英文字母的排列组合作为密钥单词,仅长度为6的密钥单词就有超过3亿种可能,为什么还是能够被破解呢?维吉尼亚密码法的缺陷就是循环使用固定的密码表对明文加密,一旦循环长度被破译者分析出来,整个加密算法就变的和单密码表加密无异。为了增强维吉尼亚密码的安全性,可以选用非常长的密钥单词,这样一来,密文中出现重复字母组合的可能性就降低了很多,并且使用同一套密码表加密的字母个数也随之减少,猜测密钥单词长度和频率分析法就失效了。

M:          v           i            g           e           n           e           r           e           c            i           p           h           e           r

将这个理论发挥到极致,就是著名的“一次一密”加密法,这种加密法广泛地运用在外交、军事等需要不计代价地保证通信秘密的场合。“一次一密”,即每发送一条信息,就更换一个新的密钥单词,密钥单词的长度和要发送信息的长度相当,而且是随机生成的,不包含任何有意义的单词。秘密通信的双方各持有一本密码本,每进行一次通信,就撕下密码本的一页,使用的密钥。从理论上来说,只要密码本没有泄露,即使破译者截获了某次通信的明文和密文,仍然无法破译下次通信的密文,“一次一密”是真正安全的加密方式,被誉为古典密码学的圣杯。

K:          c           a            t           c           a           t            c           a           t            c           a           t            c           a

第二次世界大战时,德军使用的“恩尼格玛”密码机是一种近似“一次一密”的加密机械。由于“一次一密“加密法需要对每一条信息使用随机的与明文等长度的密钥进行加密以保证安全性,因此就需要事先编纂一本密码本。而到了近代以后,战争期间情报部门每天需要处理海量的消息,使用这种密码本,不仅不容易查阅密钥,被敌人截获的可能性也高出不少。

C:          x            i            z           g           n           x           t           e           v            k          p           a           g           r

1918年,德国发明家亚瑟·雪毕伍斯发明了一种使用转子密码盘和机械结构的密码机,并分为商用和军用的版本。恩尼格玛使用键盘输入明文字母,输入信号经过三个编码器经过一系列别换,最终会点亮另一个键盘相应密文字母上的灯泡。最先接收输入信号的编码器每输入一个字母,就会转动一次,当它转动完一周,下一个编码器就会转动一次,以此类推,三个安装好的编码器一共有26×26×26种不同的状态,每一种状态对应一个密码表,在开始加密时,可以选择任意一种状态作为初始状态,用来加密明文的“密钥单词”也随着改变。除此之外,编码器位置可以互换,输入键盘和第一个编码器之间还有一个称为接线板的装置,可以互换六对字母的输入信号,有大约一千亿种不同的互换方式。恩尼格玛是历史上最为可靠的机械式密码机之一,但在英国传奇数学家阿兰·图灵和布莱切利公园的盟军密码工作者的努力下,德国军队使用的部分型号恩尼格玛密码机未能免遭被破解的命运,德军也为过于信任恩尼格玛的安全性付出了惨重的代价,恩尼格玛,是古典密码学最后的辉煌。未能免遭被破解的命运,德军也为过于信任恩尼格玛的安全性付出了惨重的代价,恩尼格玛,是古典密码学最后的辉煌。

 此例n=26;c:2,a:0,t:19

5

 

攻克“恩尼格玛”

代数密码:vernam密码

阿兰·图灵,今天人们以他的名字命名计算机科学领域的最高荣誉奖项。图灵建立了计算机器的通用模型“图灵机”,提出了“算法”的概念,还是第一个利用计算机器破解加密算法的人。

模2加运算,为什么提这个密码呢,因为他有个特点,就是加密和解密变换相同,称为对合运算。加密时是模2加,解密时也是与密钥模2加。著名的DES也是对合运算。

恩尼格玛密码机能够由操作员设置的部分包括三个编码器的位置、编码器的起始位置、接线板互换的字母设置,密钥空间超过10^16。德军情报部门会事先编制一本密码本,每天更换一次密钥。由于恩尼格玛曾有商用的版本,盟军对它的构造原理与加密方式有一定的了解,加上盟军缴获的几台密码机,恩尼格玛的加密算法可谓无处可遁,但不知道密钥的话,破译德军的加密情报仍然无从谈起。

 

密码分析学中,破译方尝试破解加密系统的行为称为攻击。根据柯克霍夫原则,假设加密系统除了密钥之外的一切都是公开信息,攻击实际上就是猜测密钥的行为。根据攻击者掌握的有关加密系统的信息量的多少,有以下攻击类型:

古典密码的统计分析:

惟密文攻击:攻击者只拥有关于密文的信息

单表代换密码中明文的统计特性在密文中仍然体现,容易被破译。加法和乘法知道一个密文对应的明文就完了,仿射强点,两个。

已知明文攻击:攻击者拥有某些明文片段和对应的密文片段的信息

统计字母出现频率就是一种统计分析方法。依照正常字母频率表逐个对照。

选择明文攻击:攻击者可以获得任意明文片段对应的密文信息

 

选择密文攻击:攻击者可以获得任意密文片段对应的明文信息

如果一个加密系统对已知明文攻击是安全的,那么即使攻击者截获了一些密文和对应的明文,仍然无法解译新的密文。单字母表和维吉尼亚加密法对于后三种攻击方式都不安全。如果明文是有意义的文本,它们对于惟密文攻击也是不安全的,通过频率分析法就能够轻松破解。“一次一密”,即密钥长度等于明文长度的多字母表替换式加密法是对所有攻击安全的。香农在“一次一密”法出现后30年创立了信息论,并从数学的角度证明了其安全性。而恩尼格玛的安全性介于一次一密和维吉尼亚加密法之间,下面将简要地说明图灵破解恩尼格玛的方法。

恩尼格玛的插线板最多可以对换六对字母的信号,一个对换过程可以表示为 三个编码器从左到右记为 , , ,相对初始状态的位置记为 , , ,则插线板与编码器对原始信号的共同作用可表示为

到这里为止,恩尼格玛的设计都还中规中矩。发报员在键盘上按下按键,字母会被转化为数字信号,经过处理后变成密文在密文键盘相应的位置点亮灯泡。那如果要解密怎么办呢?密码灯只能展示密文字母,而不能用做输入。收到加密信息的一方需要与加密使用相同的键盘输入密文解密,也就是要设计一种能够同时进行加密和解密的电路,对任意明文字母 以及对应的密文 = ( )满足:

雪比伍斯的方法是在三个编码器之后,再加上一块反射板,其作用是将最左边一块编码器的输出触点两两连接起来,将其输出信号反射回三个编码器,再穿过接线板,连接到密文灯泡。记反射板变换为 ,它由十三对不同字母的对换复合而成,满足

恩尼格玛在某个特定编码器状态下的加密过程就可以表示为

对于惟密文攻击,恩尼格玛几乎是牢不可破的。德军每天会更换密钥,每则密钥加密的明文数量有限。密钥的长度为17576,比大多数明文长度都要长,因而频率分析法对恩尼格玛也不起作用。但是对于已知明文攻击,反射板设计的危害就体现出来了。盟军缴获了德军的几台恩尼格玛密码机,并对一些已知的明文和密文进行对比,发现德军公文的格式较为固定,经常在固定的位置出现同样的单词。比如德军每天发送的天气预报中会出现wetter这一单词。图灵还发现,有时明文和密文之间会出现一种特殊的循环结构,这有助于识别编码器的状态信息。假设已知明文为wetter,对应的密文如下:

可以看出这样的循环是在 的作用下产生的,与接线板设置无关。图灵利用这一点,便可以不考虑接线板的接法,他使用三台相同的恩尼格玛密码机,随意设置第一台的编码器位置,记这个位置为 ,将第二台设置为 1,第三台设置为 3,并同步改变三台密码机的编码器设置。将第一台密码机的输出连接到第二台的输入,第二台的输出连接到第三台的输入,以此类推,从而模拟出同样的加密过程。如果编码器设置正确,就可以形成相同的循环回路。现在还不知道字母 被接线板替换成了哪个字母,图灵想到,连接两台密码机所有对应的字母触点,逐一尝试可能的编码器位置,只要有一个回路连通,就说明存在一个字母经过三台密码机被加密成它自身。这时的编码器位置虽然不一定是正确的,但只要使用筛选出的编码器位置还原明文,使用频率分析逐个检验就可以破解接线板的设置了。

图灵的设想成功地将搜寻密钥的工作简化了几个数量级,英国图表机械工厂根据图灵的设计建造出了拥有十二台密码机的解密机器“炸弹”,可以分析长度为十二的循环结构。到了1942年底,布莱切利公园一共拥有49台“炸弹”,最快在一小时内就可以找出德军的当日密钥,对盟军占据情报上的优势提供了极大的帮助。

要破解恩尼格玛,已知明文与密文的对应片段、三个编码器的内部线路都是不可缺少的。二战期间,英国皇家空军使用“栽培法”引诱德国海军发送包含特定信息的密文。英国空军在特定的地点布置水雷,故意让德军发送有关该地点坐标的情报,拦截下密文送往布莱切利公园,这也是一种选择明文攻击。

替换式加密算法与加密机械的弱点在于没能完全消除密文中有关明文的某些特征,保留了明文中的某些信息,例如单字母表替换式加密法保留了明文语言中字母的频率信息。有些则是设计上的缺陷,例如恩尼格玛。德军在二战后期增加了编码器的数量、接线板对换的字母对数量,却没意识到反射器才是根本缺陷。一些古典加密算法已经开始消除密文中反映的频率信息,如同音替换式加密法,但始终没能触及加密算法安全问题的本质:

如何降低攻击者在了解加密算法,并拥有足够长的密文片段的前提下,猜测出正确密钥的可能性?

1948年,克劳德·香农发表了著名的论文《通信的数学理论》,开创了一门新的学科:信息论。隔年,香农发表了《加密系统的通信理论》(Communication Theory of Secretary System),首先使用数学工具对加密系统进行分析。香农的理论使密码学得以成为真正的科学,也标志着现代密码学的开端。

参考文献:

[1] The Code Book, Simon Singh (1999)

[2] The Code Breakers, David Kahn (1996)

附注:

因一些原因,本文中的一些名词标注并不是十分精准,主要如:通证、数字通证、数字currency、货币、token、Crowdsale等,读者如有疑问,可来电来函共同探讨。

本文首发于微信公众号:分布式资本。文章内容属作者个人观点,不代表和讯网立场。投资者据此操作,风险请自担。

本文由betway必威官网手机版发布于科学知识,转载请注明出处:密码学初探,密码好玩的事

关键词:

上一篇:千里镜发掘B情势极化,原初重力波

下一篇:没有了