密码学的基本概念

2023年7月31日发(作者：)

密码学的基本概念

第一节 什么是密码学

密码学（在西欧语文中，源于希腊语kryptós“隐藏的”，和gráphein“书写”）是研究如何隐密地传递信息的学科。在现代特别指对信息以及其传输的数学性研究，常被认为是数学和计算机科学的分支，和信息论也密切相关。著名的密码学者Ron Rivest解释道：“密码学是关于如何在敌人存在的环境中通讯”，自工程学的角度，这相当于密码学与纯数学的异同。密码学是信息安全等相关议题，如认证、访问控制的核心。密码学的首要目的是隐藏信息的涵义，并不是隐藏信息的存在。密码学也促进了计算机科学，特别是在于电脑与网络安全所使用的技术，如访问控制与信息的机密性。密码学已被应用在日常生活：包括自动柜员机的芯片卡、电脑使用者存取密码、电子商务等等。

第二节 密码学的发展史

中国古代秘密通信的手段，已有一些近于密码的雏形。古中国周朝兵书《六韬•龙韬》也记载了密码学的运用，其中的《阴符》和《阴书》便记载了周武王问姜子牙关于征战时与主将通讯的方式：

太公曰：“主与将，有阴符，凡八等。有大胜克敌之符，长一尺。破军擒将之符，长九寸。降城得邑之符，长八寸。却敌报远之符，长七寸。警众坚守之符，长六寸。请粮益兵之符，长五寸。败军亡将之符，长四寸。失利亡士之符，长三寸。诸奉使行符，稽留，若符事闻，泄告者，皆诛之。八符者，主将秘闻，所以阴通言语，不泄中外相知之术。敌虽圣智，莫之能识。”

武王问太公曰：“… 符不能明；相去辽远，言语不通。为之奈何？”

太公曰：“诸有阴事大虑，当用书，不用符。主以书遗将，将以书问主。书皆一合而再离，三发而一知。再离者，分书为三部。三发而一知者，言三人，人操一分，相参而不相知情也。此谓阴书。敌虽圣智，莫之能识。”

阴符是以八等长度的符来表达不同的消息和指令，可算是密码学中的替代法（substitution），把信息转变成敌人看不懂的符号。至于阴书则运用了移位法，把书一分为三，分三人传递，要把三份书重新拼合才能获得还原的信息。

宋曾公亮、丁度等编撰《武经总要》“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密本体制的特点。

1871年，由上海大北水线电报公司选用6899个汉字，代以四码数字，成为中国最初的商用明码本，同时也设计了由明码本改编为密本及进行加乱的方法。在此基础上，逐步发展为各种比较复杂的密码。

在欧洲，西洋“史学之父”希罗多德（Herodotus）的《历史》（The Histories）当中记载了一些最早的秘密书信故事。公元前5世纪，希腊城邦为对抗奴役和侵略，与波斯发生多次冲突和战争。于公元前480年，波斯秘密结了强大的军队，准备对雅典（Athens）和斯巴达（Sparta）发动一次突袭。希腊人狄马拉图斯（Demaratus）在波斯的苏萨城（Susa）里看到了这次集结，便利用了一层蜡把木板上的字遮盖住，送往并告知了希腊人波斯的图谋。最后，波斯海军覆没于雅典附近的沙拉米斯湾（Salamis Bay）。

由于古时多数人并不识字，最早的秘密书写的形式只用到纸笔或等同物品，随着识字率提高，就开始需要真正的密码学了。最古典的两个加密技巧是：

转位式（Transposition cipher）：将字母顺序重新排列，例如‘help me’变成‘ehpl

em’；与替换式（Substitution cipher）：有系统地将一组字母换成其他字母或符号，例如‘fly at once’变成‘gmz bu podf’（每个字母用下一个字母取代）。 这两种单纯的方式都不足以提供足够的机密性。凯撒密码是最经典的替代法，据传由古罗马帝国的皇帝凯撒所发明，用在与远方将领的通讯上，每个字母被往后位移三格字母所取代。

二十世纪初，产生了最初的可以实用的机械式和电动式密码机，同时出现了商业密码机公司和市场。60年代后，电子密码机得到较快的发展和广泛的应用，使密码的发展进入了一个新的阶段。

密码破译是随着密码的使用而逐步产生和发展的。1412年，波斯人卡勒卡尚迪所编的百科全书中载有破译简单代替密码的方法。到16世纪末期，欧洲一些国家设有专职的破译人员，以破译截获的密信。密码破译技术有了相当的发展。1863年普鲁士人卡西斯基所著《密码和破译技术》，以及1883年法国人克尔克霍夫所著《军事密码学》等著作，都对密码学的理论和方法做过一些论述和探讨。1949年美国人香农发表了《秘密体制的通信理论》一文，应用信息论的原理分析了密码学中的一些基本问题。

图1-1 密码学的传统模型

自19世纪以来，由于电报特别是无线电报的广泛使用，为密码通信和第三者的截收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分激烈的隐蔽战线。

1917年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942年，美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，从而能以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。在保卫英伦三岛和其他许多著名的历史事件中，密码破译的成功都起到了极其重要的作用，这些事例也从反面说明了密码保密的重要地位和意义。

当今世界各主要国家的政府都十分重视密码工作，有的设立庞大机构，拨出巨额经费，集中数以万计的专家和科技人员，投入大量高速的电子计算机和其他先进设备进行工作。与此同时，各民间企业和学术界也对密码日益重视，不少数学家、计算机学家和其他有关学科的专家也投身于密码学的研究行列，更加速了密码学的发展。

第三节 密码学中的基本术语

密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换，随着通信技术的发展，对语音、图像、数据等都可实施加、脱密变换。

透过加密可以提供下列三种安全服务：

机密性(confidentiality)：不论是在传输或储存设备之中，都可以利用加密隐藏资讯。

完整性(integrity)：不论是在传输或储存设备之中，都可以利用加密确认资讯的完整性。

可说明性(accountability)：加密可以用来确认资讯的来源，且可让资讯的来源无法否认资讯的出处。 图1-2 传统加密和解密方法的简化模型

进行明密变换的法则，称为密码的体制。指示这种变换的参数，称为密钥，也称为金钥。它们是密码编制的重要组成部分。密码体制的基本类型可以分为四种：错乱－－按照规定的图形和线路，改变明文字母或数码等的位置成为密文；代替－－用一个或多个代替表将明文字母或数码等代替为密文；密本－－用预先编定的字母或数字密码组，代替一定的词组单词等变明文为密文；加乱－－用有限元素组成的一串序列作为乱数，按规定的算法，同明文序列相结合变成密文。以上四种密码体制，既可单独使用，也可混合使用，以编制出各种复杂度很高的实用密码。

20世纪70年代以来，一些学者提出了公开密钥体制，即运用单向函数的数学原理，以实现加、脱密密钥的分离。加密密钥是公开的，脱密密钥是保密的。这种新的密码体制，引起了密码学界的广泛注意和探讨。

利用文字和密码的规律，在一定条件下，采取各种技术手段，通过对截取密文的分析，以求得明文，还原密码编制，即破译密码。破译不同强度的密码，对条件的要求也不相同，甚至很不相同。密码破解通常有两种方式：分析破解法和暴力破解法。

分析破解法即当演算法受到攻击时，分析师会找寻将原文转成密文的演算法缺点，且在没有密钥的情况下还原资讯的原文。若是具有这类弱点的演算法，也就不能称为牢靠的演算法，当然也就不能使用。例如2005~2006年山东大学数学与系统科学学院教授、资讯安全实验室主任——王小云领导的研究团队成功地破解了国际上广泛应用的两大密码演算法MD5和SHA-1。王小云及她的团队在2005年将该成果发表為4篇论文，被公认为近年来国际密码学最出色的成果之一。

暴力破解法也是一种最基本的破解法，前提是可以看懂或辨明明文。理论上可以尝试所有可能的密钥，直到找到真正的密钥，一般来说所尝试的密钥数大约是可能密钥总数的一半。其破解所需成本与金钥大小成正比，金钥长度愈长愈不易经由暴力攻击法破解。

图1-3 全面搜索金钥所花费的平均时间

第四节 对称加密与非对称加密

1、对称加密

采用单钥密码系统的加密方法，同一个密钥可以同时用作信息的加密和解密，这种加密方法称为对称加密，也称为单密钥加密。由于其速度，对称性加密通常在消息发送方需要加密大量数据时使用。

所谓对称，就是采用这种加密方法的双方使用方式用同样的密钥进行加密和解密。密钥是控制加密及解密过程的指令。算法是一组规则，规定如何进行加密和解密。

因此对称式加密本身不是安全的。

常用的对称加密有：

DES、IDEA、RC2、RC4、SKIPJACK、RC5、AES算法等。

2、非对称加密

1976年，美国学者Dime和Henman为解决信息公开传送和密钥管理问题，提出一种新的密钥交换协议，允许在不安全的媒体上的通讯双方交换信息，安全地达成一致的密钥，这就是“公开密钥系统”。相对于“对称加密算法”这种方法也叫做“非对称加密算法”。

与对称加密算法不同，非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。

非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。甲方只能用其专用密钥解密由其公用密钥加密后的任何信息。

非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要，但加密和解密花费时间长、速度慢，它不适合于对文件加密而只适用于对少量数据进行加密。

第五节 现代密码学的发展

二十世纪早期的密码学本质上主要考虑语言学上的模式。从此之后重心转移，现在密码学使用大量的数学，包括信息论、计算复杂性理论、统计学、组合学、抽象代数以及数论。密码学同时也是工程学的分支，但却是与别不同，因为它必须面对有智能且恶意的对手，大部分其他的工程仅需处理无恶意的自然力量。检视密码学问题与量子物理间的关连也是目前热门的研究。

现代的研究主要在分组密码（block cipher）与序列密码（stream cipher）及其应用。

分组密码在某种意义上是阿伯提的多字符加密法的现代化。分组密码取用明文的一个区块和钥匙，输出相同大小的密文区块。由于信息通常比单一区块还长，因此有了各种方式将连续的区块编织在一起。DES和AES是美国联邦政府核定的分组密码标准（AES将取代DES）。尽管将从标准上废除，DES依然很流行（3DES变形仍然相当安全），被使用在非常多的应用上，从自动交易机、电子邮件到远端存取。也有许多其他的区块加密被发明、释出，品质与应用上各有不同，其中不乏被破解者。

序列密码，相对于区块加密，制造一段任意长的钥匙原料，与明文依位元或字符结合，有点类似一次一密密码本（one-time pad）。输出的串流根据加密时的内部状态而定。在一些流密码上由钥匙控制状态的变化。RC4是相当有名的序列密码。

2023年7月31日发(作者：)

密码学的基本概念

第一节 什么是密码学

密码学（在西欧语文中，源于希腊语kryptós“隐藏的”，和gráphein“书写”）是研究如何隐密地传递信息的学科。在现代特别指对信息以及其传输的数学性研究，常被认为是数学和计算机科学的分支，和信息论也密切相关。著名的密码学者Ron Rivest解释道：“密码学是关于如何在敌人存在的环境中通讯”，自工程学的角度，这相当于密码学与纯数学的异同。密码学是信息安全等相关议题，如认证、访问控制的核心。密码学的首要目的是隐藏信息的涵义，并不是隐藏信息的存在。密码学也促进了计算机科学，特别是在于电脑与网络安全所使用的技术，如访问控制与信息的机密性。密码学已被应用在日常生活：包括自动柜员机的芯片卡、电脑使用者存取密码、电子商务等等。

第二节 密码学的发展史

中国古代秘密通信的手段，已有一些近于密码的雏形。古中国周朝兵书《六韬•龙韬》也记载了密码学的运用，其中的《阴符》和《阴书》便记载了周武王问姜子牙关于征战时与主将通讯的方式：

太公曰：“主与将，有阴符，凡八等。有大胜克敌之符，长一尺。破军擒将之符，长九寸。降城得邑之符，长八寸。却敌报远之符，长七寸。警众坚守之符，长六寸。请粮益兵之符，长五寸。败军亡将之符，长四寸。失利亡士之符，长三寸。诸奉使行符，稽留，若符事闻，泄告者，皆诛之。八符者，主将秘闻，所以阴通言语，不泄中外相知之术。敌虽圣智，莫之能识。”

武王问太公曰：“… 符不能明；相去辽远，言语不通。为之奈何？”

太公曰：“诸有阴事大虑，当用书，不用符。主以书遗将，将以书问主。书皆一合而再离，三发而一知。再离者，分书为三部。三发而一知者，言三人，人操一分，相参而不相知情也。此谓阴书。敌虽圣智，莫之能识。”

阴符是以八等长度的符来表达不同的消息和指令，可算是密码学中的替代法（substitution），把信息转变成敌人看不懂的符号。至于阴书则运用了移位法，把书一分为三，分三人传递，要把三份书重新拼合才能获得还原的信息。

宋曾公亮、丁度等编撰《武经总要》“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密本体制的特点。

1871年，由上海大北水线电报公司选用6899个汉字，代以四码数字，成为中国最初的商用明码本，同时也设计了由明码本改编为密本及进行加乱的方法。在此基础上，逐步发展为各种比较复杂的密码。

在欧洲，西洋“史学之父”希罗多德（Herodotus）的《历史》（The Histories）当中记载了一些最早的秘密书信故事。公元前5世纪，希腊城邦为对抗奴役和侵略，与波斯发生多次冲突和战争。于公元前480年，波斯秘密结了强大的军队，准备对雅典（Athens）和斯巴达（Sparta）发动一次突袭。希腊人狄马拉图斯（Demaratus）在波斯的苏萨城（Susa）里看到了这次集结，便利用了一层蜡把木板上的字遮盖住，送往并告知了希腊人波斯的图谋。最后，波斯海军覆没于雅典附近的沙拉米斯湾（Salamis Bay）。

由于古时多数人并不识字，最早的秘密书写的形式只用到纸笔或等同物品，随着识字率提高，就开始需要真正的密码学了。最古典的两个加密技巧是：

转位式（Transposition cipher）：将字母顺序重新排列，例如‘help me’变成‘ehpl

em’；与替换式（Substitution cipher）：有系统地将一组字母换成其他字母或符号，例如‘fly at once’变成‘gmz bu podf’（每个字母用下一个字母取代）。 这两种单纯的方式都不足以提供足够的机密性。凯撒密码是最经典的替代法，据传由古罗马帝国的皇帝凯撒所发明，用在与远方将领的通讯上，每个字母被往后位移三格字母所取代。

二十世纪初，产生了最初的可以实用的机械式和电动式密码机，同时出现了商业密码机公司和市场。60年代后，电子密码机得到较快的发展和广泛的应用，使密码的发展进入了一个新的阶段。

密码破译是随着密码的使用而逐步产生和发展的。1412年，波斯人卡勒卡尚迪所编的百科全书中载有破译简单代替密码的方法。到16世纪末期，欧洲一些国家设有专职的破译人员，以破译截获的密信。密码破译技术有了相当的发展。1863年普鲁士人卡西斯基所著《密码和破译技术》，以及1883年法国人克尔克霍夫所著《军事密码学》等著作，都对密码学的理论和方法做过一些论述和探讨。1949年美国人香农发表了《秘密体制的通信理论》一文，应用信息论的原理分析了密码学中的一些基本问题。

图1-1 密码学的传统模型

自19世纪以来，由于电报特别是无线电报的广泛使用，为密码通信和第三者的截收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分激烈的隐蔽战线。

1917年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942年，美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，从而能以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。在保卫英伦三岛和其他许多著名的历史事件中，密码破译的成功都起到了极其重要的作用，这些事例也从反面说明了密码保密的重要地位和意义。

当今世界各主要国家的政府都十分重视密码工作，有的设立庞大机构，拨出巨额经费，集中数以万计的专家和科技人员，投入大量高速的电子计算机和其他先进设备进行工作。与此同时，各民间企业和学术界也对密码日益重视，不少数学家、计算机学家和其他有关学科的专家也投身于密码学的研究行列，更加速了密码学的发展。

第三节 密码学中的基本术语

密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换，随着通信技术的发展，对语音、图像、数据等都可实施加、脱密变换。

透过加密可以提供下列三种安全服务：

机密性(confidentiality)：不论是在传输或储存设备之中，都可以利用加密隐藏资讯。

完整性(integrity)：不论是在传输或储存设备之中，都可以利用加密确认资讯的完整性。

可说明性(accountability)：加密可以用来确认资讯的来源，且可让资讯的来源无法否认资讯的出处。 图1-2 传统加密和解密方法的简化模型

进行明密变换的法则，称为密码的体制。指示这种变换的参数，称为密钥，也称为金钥。它们是密码编制的重要组成部分。密码体制的基本类型可以分为四种：错乱－－按照规定的图形和线路，改变明文字母或数码等的位置成为密文；代替－－用一个或多个代替表将明文字母或数码等代替为密文；密本－－用预先编定的字母或数字密码组，代替一定的词组单词等变明文为密文；加乱－－用有限元素组成的一串序列作为乱数，按规定的算法，同明文序列相结合变成密文。以上四种密码体制，既可单独使用，也可混合使用，以编制出各种复杂度很高的实用密码。

20世纪70年代以来，一些学者提出了公开密钥体制，即运用单向函数的数学原理，以实现加、脱密密钥的分离。加密密钥是公开的，脱密密钥是保密的。这种新的密码体制，引起了密码学界的广泛注意和探讨。

利用文字和密码的规律，在一定条件下，采取各种技术手段，通过对截取密文的分析，以求得明文，还原密码编制，即破译密码。破译不同强度的密码，对条件的要求也不相同，甚至很不相同。密码破解通常有两种方式：分析破解法和暴力破解法。

分析破解法即当演算法受到攻击时，分析师会找寻将原文转成密文的演算法缺点，且在没有密钥的情况下还原资讯的原文。若是具有这类弱点的演算法，也就不能称为牢靠的演算法，当然也就不能使用。例如2005~2006年山东大学数学与系统科学学院教授、资讯安全实验室主任——王小云领导的研究团队成功地破解了国际上广泛应用的两大密码演算法MD5和SHA-1。王小云及她的团队在2005年将该成果发表為4篇论文，被公认为近年来国际密码学最出色的成果之一。

暴力破解法也是一种最基本的破解法，前提是可以看懂或辨明明文。理论上可以尝试所有可能的密钥，直到找到真正的密钥，一般来说所尝试的密钥数大约是可能密钥总数的一半。其破解所需成本与金钥大小成正比，金钥长度愈长愈不易经由暴力攻击法破解。

图1-3 全面搜索金钥所花费的平均时间

第四节 对称加密与非对称加密

1、对称加密

采用单钥密码系统的加密方法，同一个密钥可以同时用作信息的加密和解密，这种加密方法称为对称加密，也称为单密钥加密。由于其速度，对称性加密通常在消息发送方需要加密大量数据时使用。

所谓对称，就是采用这种加密方法的双方使用方式用同样的密钥进行加密和解密。密钥是控制加密及解密过程的指令。算法是一组规则，规定如何进行加密和解密。

因此对称式加密本身不是安全的。

常用的对称加密有：

DES、IDEA、RC2、RC4、SKIPJACK、RC5、AES算法等。

2、非对称加密

1976年，美国学者Dime和Henman为解决信息公开传送和密钥管理问题，提出一种新的密钥交换协议，允许在不安全的媒体上的通讯双方交换信息，安全地达成一致的密钥，这就是“公开密钥系统”。相对于“对称加密算法”这种方法也叫做“非对称加密算法”。

与对称加密算法不同，非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。

非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。甲方只能用其专用密钥解密由其公用密钥加密后的任何信息。

非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要，但加密和解密花费时间长、速度慢，它不适合于对文件加密而只适用于对少量数据进行加密。

第五节 现代密码学的发展

二十世纪早期的密码学本质上主要考虑语言学上的模式。从此之后重心转移，现在密码学使用大量的数学，包括信息论、计算复杂性理论、统计学、组合学、抽象代数以及数论。密码学同时也是工程学的分支，但却是与别不同，因为它必须面对有智能且恶意的对手，大部分其他的工程仅需处理无恶意的自然力量。检视密码学问题与量子物理间的关连也是目前热门的研究。

现代的研究主要在分组密码（block cipher）与序列密码（stream cipher）及其应用。

分组密码在某种意义上是阿伯提的多字符加密法的现代化。分组密码取用明文的一个区块和钥匙，输出相同大小的密文区块。由于信息通常比单一区块还长，因此有了各种方式将连续的区块编织在一起。DES和AES是美国联邦政府核定的分组密码标准（AES将取代DES）。尽管将从标准上废除，DES依然很流行（3DES变形仍然相当安全），被使用在非常多的应用上，从自动交易机、电子邮件到远端存取。也有许多其他的区块加密被发明、释出，品质与应用上各有不同，其中不乏被破解者。

序列密码，相对于区块加密，制造一段任意长的钥匙原料，与明文依位元或字符结合，有点类似一次一密密码本（one-time pad）。输出的串流根据加密时的内部状态而定。在一些流密码上由钥匙控制状态的变化。RC4是相当有名的序列密码。