• 在写这篇文章之前，我大部分接触的都是CTF密码学方向，很大一部分都在学习密码分析学，这就导致我最先入门的不是密码编码学，而是密码分析学。
  • 而且CTF密码学方向，其实是密码学理论、密码分析技术和工程实践在竞赛场景中的综合应用。但是CTF密码学方向与实际的密码学工程应用还是稍微有差别的。
  • 我写这篇文章，是为了构建属于自己的密码学知识体系，因为这几年来打CTF都是以做赛题、复现赛题为切入点，从而学习密码学知识，这使得我脑子里面的密码学知识还是很零散，做不到成体系学到后期明显感到基础不足，所以打算以CTF题目为主继续学习新的密码学知识，同时以学习密码学基础知识和数学知识为辅，夯实我的密码学基础。（纯热爱，无功利）

密码学总体介绍

密码学的定义

  • 密码学Cryptology：是一门研究信息安全保护及其相关理论与技术的学科。它主要通过数学理论、计算方法和密码算法，实现对信息的机密性、完整性、真实性以及不可否认性等安全属性的保护。
  • 从发展历程来看，密码学最初主要研究如何通过特定的编码和变换方式隐藏信息，使未经授权的人无法理解通信内容。随着计算机科学、舒徐和信息技术的发展，密码学逐渐从传统的加密技术发展成为一门综合性的学科，研究范围从单纯的信息加密扩展道了身份认证、数字签名、密钥交换、零知识证明、多方安全计算以及后量子密码等领域。
  • 现代密码学不仅研究如何设计安全的密码算法，还研究如何证明密码系统的安全性、如何分析和攻击密码系统，以及如何将密码算法安全地应用于实际计算机系统。
  • 因此，密码学并不只是研究某种加密算法，而是包含数学理论、密码构造、安全分析和工程实现等多个方面的完整知识体系。

密码学的总体分类

  • 密码学，英文名词为Cryptology是这个学科的总称，但是从传统的密码学的学科划分来看，密码学通常还划分为两个主要部分：
    • 密码编码学Cryptography：研究密码算法、密码原语和密码协议的设计与构造。
    • 密码分析学Cryptanalysis：研究密码算法和密码协议的安全性，寻找其中的弱点和漏洞。
  • 随着现代密码学的发展，密码学涉及的理论和工程内容越来越丰富，为了更加系统地组织知识，我对密码学划分为四个主要部分（不是很严谨的划分，会有交叉关系），下面一张思维导图是密码学总体的概览包括四个主要部分中更细的划分：
    • 密码学理论与数学基础
    • 密码编码学
    • 密码分析学
    • 密码工程与实现

密码学(Cryptology)v2.0

密码学各分支之间的关系

  • 密码学的四个主要部分并不是相互独立，它们之间存在紧密的联系：
    • 密码学理论与数学基础提供构造和分析密码系统所需要的数学工具与理论依据。
    • 密码编码学利用这些数学理论设计密码算法、密码原语和密码协议。
    • 密码分析学研究这些密码构造的安全性，寻找其中的弱点和潜在漏洞。
    • 密码工程与实现将密码算法和协议应用到真实计算机系统中，并解决实际运行中的安全性和效率问题。
    • 上面的四个部分共同构成一个完整的密码学研究体系。
  • 举例1：RSA加密
分类 对应知识
理论与数学基础 初等数论、模运算、欧拉函数、欧几里得算法等
密码编码学 RSA密钥生成、加密、解密、数字签名
密码分析学 Wiener攻击、Boneh-Durfee攻击、Coppersmith攻击
密码工程与实现 RSA软件实现、密钥管理、填充方案、常数时间实现
  • 举例2：格密码
分类 对应知识
理论与数学基础 格理论、线性代数、概率论
密码编码学 LWE、NTRU、ML-KEM
密码分析学 LLL、BKZ、SVP、CVP、LWE求解
密码工程与实现 格密码算法优化、后量子密码库实现
  • 所以，我们在学习某一个具体的密码体系，往往需要同时涉及这四个方面。

总结

  • 密码学是一门以数学理论和计算方法为基础，研究信息安全保护、密码系统构造、安全性分析及工程实现的综合性学科。
  • 从整体上看，可以将密码学划分为四个主要部分：
    • 密码学理论与数学基础：研究密码学所依赖的数学理论、计算理论和安全模型。
    • 密码编码学：研究密码算法、密码原语和密码协议的设计与构造。
    • 密码分析学：研究密码算法和协议的安全性，分析其中的弱点和漏洞。
    • 密码工程与实现：研究密码算法和协议在真实计算机系统中的实现、优化和部署。
  • 这四个部分共同构成密码学的知识体系。

密码学相关概念与名词

  • 在具体了解密码学历史之前，先要了解几个英文单词：
    • 代码code：现在基本上就是指编程语言的这种代码，而在过去code即代码的意思，这个字本来是指秘密通讯的方法，所谓代码就是用一个字，或数字、符号，来取代某个字或词组。
      • 例如：情报人员都有一个代号codename，用来代替真实姓名以隐藏身份的名称。
      • 例如：要传达拂晓攻击这个命令给战场指挥官时，使用Jupiter朱庇特这个代码codeword来替代，这样约定好后拦截到消息的敌人则会一头雾水。
    • 密码cipher：是比code作用面更基层的方法，更替一个个字母，而不是一整个词。
      • 例如：使用B代替A，C代替B以此类推的规律，拂晓攻击英文为Attack at dawn，使用密码作用到每一个字母就变成Buubdl bu ebxo了。
    • 代码破解者codebreaker，密码破解者cipherbreaker。
    • 明文plaintext：加密前的信息。
    • 密文ciphertext：加密后的信息。

隐写术

  • 在人类历史上，经常会出现掩饰信息存在性的保密通讯法，该方法称为隐匿法steganography。steganography这个单词源自希腊文steganos和graphein两个单词，前者意为掩蔽的，后者则是书写。自希罗多德时代起，两千年来隐匿法的应用以千奇白怪的形式遍及世界各地。

  • 隐匿法发展的时间这门长，表示它显然是相当的安全，不过隐匿法有一个致命的弱点，万一敌人搜查到隐匿文字的载体，并发现信息，那么秘密通讯的内容马上就要曝光，也就是说一旦信息被拦截到，所有安全措施都会前功尽弃。

  • 接下来介绍一些隐写术使用的历史，以及现在科技时代的隐写术。

  • 秘密书信：希罗多德讲过一些最早的秘密书信的故事，主要是希腊和波斯在公元前5世纪时的冲突。

    • 波斯国因为某些事情与希腊和斯巴达两国积怨，波斯打算派人攻打两国。
    • 波斯国军队的集结行动被一名为狄马拉图斯的希腊人所瞧见，他是被希腊流放到波斯国的一个城市苏萨。
    • 狄马拉图斯虽被流放，但是还心系希腊，于是就将一副可对折的木制写字板上的蜡瓜下来，把波斯要攻打希腊和斯巴达这件事写在木头上，再用一层蜡把这则信息盖住。这样以来，这些木板看似一片空白，沿路上的士兵就不会找它们的麻烦。
    • 不过这个木板到达目的地时没人猜到其中的奥秘，是克利欧明斯的女儿戈尔戈瞧出端倪，之后把蜡刮了发现消息，并转告给希腊人。

image-20261030194135072

  • 剃发传信：希罗多德还讲述了一个发生在波斯战争背景下的故事。
    • 希斯泰尤斯为了鼓动米里图斯的亚里斯达哥拉斯反叛波斯国王，决定送一封信。
    • 希斯泰尤斯把信差的头发剃光，在信差头皮上刺写秘密信息。
    • 等到信差头发重新长出来后，希斯泰尤斯便将信拆派往目的地。
    • 接收者再次剃掉信差头发，获得信中的内容。
  • 其他隐写：
    • 古代中国人把信息写在柔细的丝布上，揉成小球，覆上蜡，再让信差吞进这粒蜡球。
    • 16世纪的意大利科学家乔凡泥·波塔解说了再煮熟的鸡蛋里藏匿信息的方法：用一盎司明矾和一品脱醋所混成的液体当作墨水写在蛋壳上。这种溶剂会穿透富含气孔的蛋壳，而在硬化的蛋白表层上留下信息，你得剥掉蛋壳才看得到。
    • 使用隐形墨水写信也是隐匿法的一种，早在公元1世纪，老普林尼就解释道：thithymallus植物的汁液可以用作隐形墨水。它的汁液干掉就会变透明，但稍微加热就会焦掉而变成棕色。
  • 现代数字隐写：
    • 将秘密信息隐藏在 JPEG 图片中、将秘密信息隐藏在 WAV 音频中、将秘密信息隐藏在 MP4 视频中、将秘密信息隐藏在普通文本中。
    • 网络协议隐写，网络协议本身也作为隐写载体。
    • 人工智能与生成式隐写，利用语言模型生成文本，让文本在满足语义和语言自然性的同时携带秘密信息。

置换与代换

  • 由于隐匿法的局限性和容错低，所以在隐匿法发展的同时还出现了密码法。密码法这一词源于希腊文kryptos，隐藏的意思。密码法的目标不是将信息本身隐藏起来，而是隐藏信息的意义。它的过程就是：加密encryption，把信息转译成无法理解的文字或符号。
  • 密码法和隐匿法虽然没什么关联，但是却可以合并使用，以强化安全性。不过密码法是秘密通讯两门技术中较强的一个，因为它有防止信息落入敌手的能力。
  • 事实上密码法本身又可以分为两种类型：
    • 位移法数学上称之为置换：将信息里的字母调动顺序，这个方法不适用于非常简短的信息，因为可以很容易穷举出来。
    • 替代法数学上称之为代换：将信息里的字母用别的字母代替，更或者用其他符号代替。

置换法

  • 对于置换法而言，加密信息时若将字母随意搬家，它的安全度一定非常高，因为即使是短短的句子，拦截道它的敌人也没办法解译出来。
  • 置换法本质就是在制造回文谜，可以制造困难度非常高的回文谜，但是这样字母重组毫无章法，那么不仅是敌人，就连原收信人也没办法解读。
  • 所以字母的重组必须遵循发信人与收信人预先约定好的规则，这样置换法才有实际效用。
  • 栅栏密码：是一种通过置换法，对字母进行重新排列的一个密码法。
    • 最常见的就是栅栏数为2的栅栏密码，也就是将信息内容的奇数位字母排成一排，偶数位字母写在另一排，再把偶数位字母接道奇数位字母后面。收信人只需要执行逆过程就可以恢复原信息。
    • 例如：THY SECRET IS THY PRISONER;IF THO。
1
2
3
4
5
T*Y *E*R*T *S *H* P*I*O*E*;I* T*O
*H* S*C*E* I* T*Y *R*S*N*R;*F *H*
TYERTSHPIOEITO 
HSCEITYRSNRFH
TYERTSHPIOEITOHSCEITYRSNRFH

  • 调换密码：将字母两两对调顺序，也就是将第一个字母和第二个字母互调，第三个字母和第四个字母互调，以此类推。

  • 密码棒：历史上第一件军用密码装置，公元前5世纪的斯巴达密码棒。密码棒就是采用了另一种形式的置换法。

    • 密码棒是一根木棒，缠绕上一条皮革或羊皮纸，发信人在密码棒上横向写下信息，再解下这条皮带。
    • 展开皮带后，皮带上的长串字母没有任何意义，借此方法即可搅乱信息的内容。
    • 有时候信差会把它当作腰带，有字母的那一面向内藏，系在腰上，也就算是隐匿法的一种。

image-20261030204641168

代换法

  • 代换法：原始信息的每个字母都用另一个字母取代，可以说是跟置换法互补的一种方法。

  • 历史上代换法的使用：

    • 在公元4世纪，婆罗门学者跋舍耶那所写的《爱欲经》就曾提到用代换法加密信息：

      • 此书是鼓励妇女学习64种技艺，其中第45项则是秘密书信，帮助妇女隐瞒她们的暧昧关系。

      • 其中一项建议的方法是：先将字母随意配对，再用配对字母取代信息里面的原始字母。如果将这套用道罗马字母，我们可以为字母进行如下的配对：A<->V、D<->X、H<->B、I<->G、K<->J、M<->C、O<->Q、S<->N、U<->E、W<->F、Y<->P、Z<->T

      • 这样一来，发信人可以把meet at midnight，改写成CUUZ VZ CGXSGIBZ。

    • 凯撒加密：代换法在军事上的首次运用就是凯撒大帝，就是将当前字母改写成它后面几位的字母，这个代换规则是有规律的，凯撒常用的是移位3位的代换规则，这种称为凯撒密码法。

    • 代码代换：不论是《爱欲经》还是凯撒加密，都算是密码代换，而代码代换其实就是将某个单词用字母或者符号代替，比如assassinate行刺使用D代替等。

    • 单表代换：上面介绍的凯撒加密，其实都是用单个密码表对字母进行代换操作，但是随着时代的发展很容易被破解，于是就有了用虚元(没有意义的符号)，或者说用σ\sigma符号表示下一个符号代表两个字母，这样一个复杂但是有规律的代换。

    • 还有一些其他的单表代换密码，比如：同音代换法、纳瓦霍密码

    • 多表代换：下面要介绍的维吉尼亚密码就是多表代换，多表代换其实就是使用多个密码表对字母进行代换，这个代换比较复杂，但是也是有一定规律的。维吉尼亚密码就是典型的多表代换密码。

置换和代换的区分：置换法是字母的内涵不变，位置变了；代换法是字母的内涵变了，位置不变。

区别一个密码是代换还是置换，主要判断它是不是置换，置换其实就是把字母打乱顺序。主要就是假设如果穷举出全部的字母排列，是不是有其中一个排列是原文，如果是就是置换，如果不是就是代换。例如：凯撒密码（举这个例子是因为我之前把凯撒密码当作置换，其实是代换只不过代换规则是有规律的），凯撒密码apple，将位移1，这样就替换成bqqmf，这样在穷举出所有字母的排列没有一个是正确答案apple，所以这个其实就是代换，而不是置换。

注意：上面介绍的密码都是用这类符号或字母、或两者混用，以一个密码字母代替一个明文的方法，通称为单套字母替代式密码。

两者综合

  • ADFGVX加密：

密码分析学

  • 密码分析学的起源主要就是阿拉伯人，当时阿拉伯那边的国家社会问题，对于一些官员的消息通信，都会进行加密通讯。
  • 密码分析学：在无从得知密钥的情况下解译信息的科学。密码分析学的催生需要一个高度文明，即数学、统计学和语言学科，都必须具备高度水平。
  • 词频分析法的历史：
    • 词频分析法这个技术最早见于公元9世纪科学家肯迪，词频分析主要就是根据一般使用的英文字母，字母的出现频率从高到底的排序，一般文章出现频率最高的单词是e，接着就是t，以此下去。这样再分析被加密后的文章字母出现的频率，这样就很可能分析出代换的关系。
    • 当时的阿拉伯有很多神学校，神学家在研究神学中《古兰经》所载穆罕默德的天启，想按照编年史进行编排就是统计每篇天启中字母的频率。有些字母出现的早，有些字母更晚才被创造。

image-20261030231223266

  • 卡希斯基测试：
  • 暴风雨攻击tempest attack：
  • 量子计算机破解RSA加密

柯克霍夫原则

  • 每种密码法都可视为一般加密法，称为算法，再加上钥匙的组合结果。钥匙是用来指定特定加密程序的演算细节。
  • 对于置换和代换的算法其实大家都知道，但是就是具体如何置换和代换是不太清楚的，所以置换和代换规则其实就相当于一个密钥。
  • 敌人研究拦截下来的加密信息时，也许可以八九不离十的猜对它的算法，却很难推测出它的钥匙。

荷兰语言学家，奥古斯特·柯克霍夫提出了一个密码学的原则，即柯克霍夫原则：

即使密码系统的任何细节已为人悉知，只要密钥未泄漏，它也应是安全的。

其为军用保密器所设计的这六个原则是：

  1. 即使如果做不到数学上的不可破解，系统也应该在实质程度上无法破解
  2. 系统内不应含任何机密无，即使落入敌人手中也不会造成困扰
  3. 密钥必须易于沟通和记忆，而不须写下；且双方可以容易改变密钥。
  4. 系统应可以用于电讯
  5. 系统应可以携带，不应需要两个人或以上才能使用
  6. 系统应容易使用，不应让用户的脑力过分操劳，也无需记得长串的规则。
  • 补充：密钥的空间还需要足够大，像凯撒密码中密钥只有25种可能就不行，密钥需要空间需要足够大，才能使得系统无法在有限的世纪枚举出所有密钥。这样就不会被爆破。

密码机械

  • 最早的密码机械是密码盘：p138
  • Enigma密码机：
  • Type X密码机
  • SIGABA密码机

计算机加密

  • Diff-Hemen密钥交换：一种密钥交换协议，根据离散对数求解的困难性创造出来的加密算法。
  • RSA非对称加密：一种公钥密码算法，依据是大整数分解的困难性创造出来的加密算法。
  • 最佳隐私PGP,Pretty Good privacy：是一套用于保护信息安全的密码学系统，最早使用了IDEA+RSA与数字签名。
  • 加密通话PGPfone：
    • 是由 PGP 的创始人Phil Zimmermann于1995年推出的一款加密语音通信软件。
    • 它的核心目标是：让两个人能够通过普通计算机和通信线路，进行实时加密通话，防止第三方窃听。
  • 认证机构CA：
    • 中文也称为证书颁发机构，是公钥基础设施中的核心组成部分。
    • 它的主要作用是：通过数字证书，将一个实体的身份与其公钥建立可信的绑定关系。
  • 公钥基础设施PKI：公钥基础设施，是一套围绕公钥、数字证书和信任关系建立的基础设施。
  • 受托的第三者TTP：可信第三方，是通信双方之外，被双方信任并承担特定安全职责的第三方实体。

量子密码

  • 量子密码学是一种基于量子力学的加密方式，与传统依赖数学难题的密码不同，它利用量子态的不可测定性和不可克隆性保障信息安全。
  • 发送方和接收方通过量子比特qubit生成共享密钥，任何窃听行为都会改变量子态，从而被立即发现，实现理论上的绝对安全。

后量子密码

  • 后量子密码，也称抗量子密码，是为应对量子计算机对现有密码算法的威胁而设计的新型密码技术。
  • 传统公钥算法RSA、Diffie-Hellman、椭圆曲线加密依赖大整数分解或离散对数问题，其安全性在量子计算机和Shor算法面前将不复存在 。
  • 后量子密码通过基于量子难解的数学问题构建加密、签名和密钥交换机制，确保在量子攻击下仍安全

其他概念

  • 随机密钥：是指通过随机数生成过程产生的密钥，而不是由人为指定、固定规则或可预测的数据直接构造出来的密钥。
  • 一次一密One-Time-Pad,OPT：是一种理论上绝对安全的加密方法，由美国密码学家沃纳·韦纳斯于1917年提出，后经过香农在1949年证明其满足信息论上的完美保密性。
  • 放射线测定器随机生成密钥：是一种利用放射性衰变的物理随机性来产生不可预测的随机数，进而生成高安全性密钥的技术。
  • 密钥交换协议：密钥交换吸引是密码学中用于在不安全信道上安全地协商出一个共享密钥的协议，其核心目标是在通信双方之间建立一个秘密密钥，以便后续使用对称加密算法进行安全通信。
  • 噪声Noise：在密码学中，噪声是指在加密、数据传输或密码协议过程中有意或无意引入的随机性、不确定性或干扰，其目的是混淆信息、增加破解难度，从而提高习题的安全性。这个与我们所描述声音的那种噪声含义是不同的，但是其实两者都有干扰功能。噪声可以是：
    • 随机填充：防止频率分析等密码分析攻击，比如古典密码的一些虚元。
    • 随机扰动：在密文中加入不可预测的数值或比特翻转。
    • 量子噪声：量子比特与环境相互作用产生的退相干。

密码编码学历史

  • 公元前5世纪：斯巴达密码棒出现；蜡版藏信、剃头刺字。

  • 公元前1世纪：恺撒移位密码

  • 公元1-10世纪：单表替代、虚元、同音替代、命名法

  • 公元15世纪：阿尔伯蒂密码盘、多表替代思想

  • 公元16世纪：维吉尼亚密码出现

  • 公元17世纪：路易十四“大密码”

  • 公元19世纪：电报、摩斯电码、书稿密码

  • 1918年：一次性密码本；Enigma 专利

  • 1920年到1945年：Enigma、Type X、SIGABA、Lorenz；纳瓦霍语密码

  • 1945年到1970年：计算机加密、DES

  • 1976年到1977年：Diffie-Hellman-Merkle 钥匙交换；RSA公钥加密算法

  • 1984年：量子密码的构想提出

  • 1991年：PGP邮箱加密软件问世， RSA + IDEA 混合加密、数字签名，强加密进入民间

密码分析学历史

  • 公元9世纪：肯迪提出频率分析， 统计字母出现频率，单表替代从此可被系统破解；密码分析学诞生

  • 公元15世纪：

    • 索罗、巴布、韦达等人先后都进行了密码破译，这使得职业的破译者出现。1586年菲利普斯破玛丽女王密码。
    • 频率分析、虚元剔除、上下文猜测等密码破译方法问世以及被使用。

  • 公元17世纪：黑房厅的出现，专门进行拆信、抄录、破译、再将信封好送回邮局，这使得破译工作变得工业化。

  • 1854年和1893年：巴贝奇、卡西斯基通过找出重复字符串，推断钥匙长度，分组做频率分析等方法破解维吉尼亚密码。

  • 1890年到1893年：巴泽里从反复出现的数字串猜出les ennemis，再逐字扩展，从而破解了大密码

  • 1917年：英国40号房破齐玛曼电报，促使美国参战

  • 1918年：邦梵破破解出ADFGVX密码，使得德军春季攻势失去突然性

  • 1932年：瑞杰斯基利用重复加密的信息钥匙，用字母环链把钥匙空间从101610^{16}缩减到105456105456种转子设定，从而了破解Enigma机

  • 1939年到1945年：

    • 在英国的布莱切利园，聚集了众多密码学家，对密码进行破译和研究，在这里图灵发明了用于破解Enigma机名为bomb的机器。
    • 第一台电子计算机Colossus破解了Lorenz。
    • 美国破解了紫色密码。

  • 1952年到1953年：文屈斯、查德威克利用频率、结构、模式分析失传文字，证明它是古希腊语，并破解了线形文字B

  • 1969年到1974年：GCHQ秘密发明公开钥匙加密，艾利斯提出概念，考克斯想出 RSA 式方案，威廉森想出钥匙交换，这件事1997年才公之于众。

  • 1994年：RSA-129被破解，Shor算法提出

  • 1996年：Grover算法使得量子搜索可以加速破解DES等穷举型密码

  • 1990年至今：侧信道密码分析、TEMPEST、病毒和木马、后门，以及量子密码，攻击点从算法转向实施与人员，量子密码让窃听必然被发现