密码学初探:信息的艺术——区块链技术引卷之十一

              本文重点:密码学初探:信息的艺术——区块链技术引卷之十一

                通证通研究院FENBUSHIDIGITAL联合出品文:宋双杰,CFA;孙含儒特别顾问:沈波;Rin;JX  导读  密码学(Cryptography),是一门将信息进行加密处理与传递,以及分析加密信息的学科。

              根据以RSA为代表的公钥加密体系的出现,可以将密码学的发展过程分为古典密码学与现代密码学两部分。 古典密码学以“置换法”与“替换法”为基础,多应用事与情报领域;现代密码学则建立在数学、计算机与通信科学的基础上,除了加密信息之外,数字签名、数据完整性、身份认证等也是现代密码学的研究课题。   摘要  置换法依照一定的规则,改变原始信息中的字母排列顺序;替换法将原始信息中的字母按照一定的规则替换成其他字母。

              置换法与替换法的安全性较差,古阿拉伯的学者们开创了破译加密信息的科学——密码分析学,通过频率分析的方法破解替换式加密法。   在长达一千多年的时间里,古典密码学以置换法与替换法为基础不断演进。

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

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

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

                风险提示:量子计算技术的潜在威胁  目录  1隐匿法  2加密法  3持续千年的智力竞赛:加密与解密  4古典密码学的圣杯  5攻克“恩尼格玛”  正文  密码学(Cryptography),是一门将信息进行加密处理与传递,以及分析加密信息的学科。 “密码学”一词的词源来自古语“”(Krypts)和“书写”(Graphein),意为“秘密书写”,其历史几乎与人类有文字记载的文明一样悠久。

              古希伯来学者在公元前六世纪左右就掌握了“单字母表替换式加密法”,在之后的两千五百多年里,古典密码学在替换式加密法的基础之上不断发展演进。 古典密码学多应用于军事与情报领域,而微型计算机与现代密码学的发展能够保护普通人的日常通信免受第三方的窥探。 现代密码学建立在数学、计算机科学与通信科学的基础上,除了信息的加密与解密之外,数字签名、数据完整性、身份认证等也是现代密码学的研究课题。

              今天人们日常生活中的网络支付、电子商务、电子货币等都是密码学这一人类两千多年来智慧结晶的应用。   密码学的概念与人们平时登陆网站、使用银行账户的“密码”并不相同。 这些用于身份认证的“密码”,更准确的翻译是“通行词”或“通行码”(password),它是现代密码学的诸多应用之一,请读者注意区分两者的区别。   受限于篇幅,有关密码学以及密码学在区块链中应用的内容将分两篇专题介绍。   1隐匿法  隐匿法的历史非常久远,可以追溯到公元前5世纪古希腊与波斯帝国的战争年代。 公元前480年,波斯舰队在“万王之王”薛西斯一世的率领下秘密集结,准备对希腊发起进攻,然而这一秘密行动被一位遭到流放、居住在波斯的希腊人狄马图拉斯发现了。 他将波斯军队准备进攻希腊的消息写在木板上,并用一层蜡将文字遮住,成功骗过了路途中的波斯卫兵,将信息传回了希腊。 希腊城邦联合起来,抵御住了波斯人的突袭。

              而遭遇挫败之后,曾经盛极一时的波斯阿契美尼德王朝也开始走向衰退。   尽管简单地“将信息起来”与我们今天熟知的密码学相差甚远,被称为“隐匿法”的秘密书写方式却标志着人们开始探索信息保密的方式。   2加密法  隐匿法仅仅将信息藏匿起来,一旦藏匿的方式暴露,或是负责传达信息的信使叛变,也无从保证。 加密法则注重信息本身的含义,信息的发出方与接收方事先约定,将信息按照一定的规则进行转译(encipher),接收方在收到后遵循约定的规则就可以还原原始信息,而即使信息被第三方截获,如果不知道转译规则,也无法还原出原始信息。   加密法的出现标志着古典密码学的开端。

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

                置换法依照一定的规则,改变原始信息中的字母排列顺序。 公元前5世纪,斯巴达军队采用一种名为“密码棒”(Scytale)的工具对信息进行加密。

              发信人将长条形的羊皮纸带缠绕在一根木棒上,将信息横向书写,最后将羊皮纸解下。 收信人将信纸缠绕在同样直径的木棒上,就能够还原信息。

              而羊皮纸上的文字看起来是无意义的,并且用尺寸不相同的木棒也无法还原出原始信息。   但只要了解这种密码的加密方式,就能很容易地解读密文。

              从密文的第一个字母开始,每数到它之后的第N个字母,记下该字母。

              记录到密文结尾后,再从第二个字母开始重复这样的操作,以此类推,很快就可以还原明文信息。 其中N取决于木棒的直径,写下N个字母后,纸带正好绕木棒一圈,选择不同的N,同样的明文经过加密得到的密文也不相同。

              发信人和收信人要事先约定好同样的N,收信人才能还原密文。 同时N不能被第三方知晓,才能保证加密通信的安全。

              这里的N称为密钥,是加密通信的参与方共同享有的秘密知识(secretaryknowledge),用于加密和解密信息。

                替换法将原始信息中的字母按照一定的规则替换成其他字母。

              据传,凯撒大帝使用替换式加密法写作书信。 凯撒大帝将信息中的每个字母后移三位,例如A替换成D,Y替换成B,这种加密法称为凯撒挪移式加密法(Caesarcipher)。

              在这个例子中,密文相比明文,每个字母都被后移了3位,密钥可以用3表示。

              密钥可能的取值范围为1~25的自然数(密钥为0时,密文与原文相同),称为密钥空间。

              明文里所有可能出现的字母的集合称为明文空间,密文里可能出现的字母集合称为密文空间,替换法中的密钥可以表示为明文空间到密文空间的一个映射,在古典密码学中又称为密码表。

              密文空间可以与明文空间相同,例如凯撒密码中,密文的字母仍然是26个拉丁字母。 密文空间也可以是明文空间的超集,例如在密文中混入一些无效字符,以干扰试图破译密码的行动。

              密文空间还可以与明文空间完全不相关,例如在柯南道尔所著的福尔摩斯系列的《跳舞的人》(theAdventureofDancingMen)中,罪犯用26种形态各异的跳舞的小人来替换英文字母。

                公元8世纪,阿拉伯哈里发帝国的第二个世袭王朝——阿拔斯王朝在巴格达定都,其建立之初的一百年是伊斯兰文明的黄金时代。

              据记载,阿拔斯王朝的官员们使用替换式加密法保护机密的行政事务、税收数据,相信这能够帮助他们建立一个廉洁、高效的政府。 巴士拉的语言学家卡里尔(Al-Khalil)撰写了《加密信息手册》(BookofCryptographicMessages),使用排列组合对阿拉伯语单词的加密法进行分析。 此外,阿拉伯的学者们还开创了破译加密信息的科学——密码分析学(Cryptanalysis)。

                3持续千年的智力竞赛:加密与解密  古典密码学多用于军事、政治、外交领域重要情报的传递,希望刺探这些秘密的人自然不在少数。

              阿拉伯学者们在统计语言学资料时发现,在样本容量较大,有意义的阿拉伯语文本中,每个字母出现的频率是不一样的。

              字母a和字母l在阿拉伯语中出现频率最高(这里用阿拉伯语字母的拉丁转写表示),因为“al”是阿拉伯语中的定冠词,相当于英语的“the”,此外,元音的出现频率也比较高。 这些成果很快被运用到密文分析中。

                之前介绍的替换式加密法中,明文中的所有字母都遵循同一套规则(密钥)进行替换,这样的加密法称为单字母表替换式加密法。

              公元9世纪,阿拉伯科学家肯迪(Al-Kindi)在《解译加密信息》(ManuscriptfortheDecipheringCryptographicMessages)一书中阐述了对这种加密法的解译方式。

              如果能确定原文所使用的语言,首先列举出密文中出现的所有字母(或字符),统计它们各自出现的频率并排序,对照该语言中字母出现的频率顺序,就可以开始尝试对密文进行分析,这种方法称为频率分析法。 频率分析还可统计某种语言中特定的字母组合出现的频率,如英文中的“ee”,以及某个字母前后特定字母出现的频率,如英文中字母“q”之后一定跟随”u”等。 直到数百年后,中世纪的欧洲学者才掌握这一方法,并且决定了两位女王的命运。

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