Archieve📓：密码学基础回顾

Cipher

古典秘密通信的方式：秘密信件与火漆 (物理保密和身份认证)
古典密码的加密方式：替换与置换

eg: 凯撒密码,仿射密码,维吉尼亚密码

古典密码的加密操作，本质上是在一个有限的离散结构（如字母表、位置索引）上，施加一个由密钥决定的、可逆的确定性变换。(密钥=变换方式)

Classic Cipher and Enigma

在密码学史中，恩尼格玛密码机（德语：Enigma，又译哑谜机，或“谜”式密码机）是一种用于加密与解密文件的密码机。确切地说，恩尼格玛是对二战时期纳粹德国使用的一系列相似的转子机械加解密机器的统称，它包括了许多不同的型号，为密码学对称加密算法的流加密。

数学描述

恩尼格玛对每个字母的加密过程可以以数学的角度看作为一个组合过程。假设一台德国陆军/空军版 3 转子恩尼格玛密码机，P 表示接线板的连线（plugboard），U 表示反射器，L、M、R 表示左（left）、中（middle）、右（right）转子。那么加密后的信息 E 就可以表示成

$E = PRMLUL^{-1} M^{-1} R^{-1} P^{-1} E_0$

自从无线电和摩尔斯电码问世后，军事通讯进入了一个崭新的时代，但是无线电通讯完全是一个开放的系统，在己方接受电文的同时，对方也可“一览无遗”，因此人类历史上伴随战争出现的密码，也就立即与无线电结合，出现了无线电密码。直到第一次世界大战结束，所有无线电密码都是使用手工编码。毫无疑问，手工编码效率极其低下，同时由于受到手工编码与解码效率的限制，使得许多复杂的保密性强的加密方法无法在实际中应用，而简单的加密方法又很容易被破译，因此在军事通讯领域，急需一种安全可靠，而又简便有效的方法。

密钥的分级与生命周期

第一级：基础设置 (Grundlegende Einstellungen) - 通常每月更换

第二级：每日密钥 (Tagesschlüssel) - 每24小时更换

第三级：消息密钥 (Spruchschlüssel) - 每条消息更换

总结：一个操作员的一天

  1. 月初: 安装本月的转子和反射器。
  2. 每天凌晨: 根据密钥表设置当天的插接板和环设置。
  3. 发送第一条消息:
    • 随机想一个起始位置（如ABC）。
    • 用“每日起始位置”加密ABC两次，得到密文XYZ PQR。
    • 将转子调到ABC。
    • 发送 XYZ PQR + 加密后的正文。
  4. 发送第二条消息:
    • 重新随机想一个起始位置（如LFG）。
    • 重复上面的步骤。

这个分级策略设计得相当严密，但实际执行中，操作员的不规范操作（例如，选择AAA、LOL等有规律的随机密钥，或者在加密消息密钥时出现的漏洞）成为了盟军破解恩尼格玛的重要突破口。

Demo on Enigma-QtFrameWork

1
git clone https://github.com/CMoments/CryptoMathLab.git

启示：

  • 密码系统的柯克霍夫斯（Kerckhoffs）原则：
    密码体制的安全性仅应依赖于对密钥的保密，而不应依赖于对算法的保密。

  • 真正的随机密钥是安全的基础。
    恩尼格玛在理论上的强度，因密钥生成过程中的“人为随机”而大幅降低。

古典密码与近代密码是前计算机时代为小范围、可信任团体实现单纯保密而设计的工具。它无法解决在公开、敌对、大规模网络环境中所需的身份认证、完整性验证、不可否认性以及可证明的安全性和高效的密钥管理等核心问题。现代密码学是支撑数字世界信任体系的基石，没有它，就没有电子商务、在线银行、数字货币和安全的互联网通信。

Symmetric Cipher And Asymmetric Cipher

实现安全性的方式：
对称密钥密码算法是基于复杂的非线性变换与迭代运算实现算法安全性，而非对称密钥密码算法则一般是基于某个公认的数学难题来实现安全性的。

Symmetric

对称密码的特点

对称密码的核心特点是加密与解密使用同一把密钥。它具备：

  1. 效率高：运算速度快，适合加密大量数据。
  2. 安全性强：依赖复杂的非线性变换和迭代运算，实现混淆与扩散。
  3. 密钥管理挑战：通信双方必须预先安全地共享同一把密钥。

从DES到AES：

DES曾是全球标准，但其56位密钥和64位分组长度在算力飞速发展的时代逐渐暴露短板。1997年的公开破解挑战，证明了它已无法满足长期安全需求。

作为DES的继承者，AES在2001年被确立为新标准。它不仅是简单的“替代”，而是一次全面的升级：

  • 密钥更长：支持128、192、256位，可对抗穷举攻击。
  • 结构更优：采用SPN（代换-置换网络）结构，具有更强的扩散性。
  • 设计更开放：全球公开竞赛选拔，过程透明，凝聚了密码学界的集体智慧。

AES的诞生，标志着对称密码设计进入了更安全、更灵活、更经得起公开检验的现代时代。

DES( Data Encryption Standard )
由固定换位、密钥依赖、多次非线性变换而产生全面的混乱。解密算法和加密相同。
DES的整个体制是公开的，系统的安全性完全靠密钥的保密。(密钥!=变换方式)

DES补充材料

DES由美国IBM公司研制，是对早期称作Lucifer密码（密钥长度128bit）的一种发展和修改。
1975年被首次公布，1977年被正式批准为美国联邦信息处理标准(FIPS-46)，并规定每隔五年由美国国家安全局( National Security Agency，NSA)做出评估。

1997年1月28日，美国的RSA数据安全公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56位密钥加密的DES密文。
一位名叫Rocke Verser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为DESHALL的搜索行动，成千，上万的志愿者加入到计划中.
计划实施的第96天，即挑战赛计划公布的第140天，1997年6月17日晚_上10点39分，美国盐湖城Inetz公司的职员MichaelSanders成功地找到了密钥：
在计算机上显示了明文: "The unknown message is: Strong cryptography makes the world a safer place

EFF的价值250,000美元的DES破解机包括1,856个自定义的芯片，可以在数天内破解一个DES密钥—本图显示了使用数个Deep Crack芯片搭成的DES破解机

启示：

  • 密钥长度必须与时俱进，对抗算力增长
    DES的56比特密钥在其设计年代（1970年代）被认为是安全的，但摩尔定律使得算力呈指数级增长。1
    后续影响：直接催生了AES选拔，明确要求支持128、192、256比特的可变长密钥。现代密码学将128比特视为对称密钥的最低安全基准。

  • 密码算法必须公开，接受全球密码学界审查
    DES的设计细节（特别是S盒设计准则）曾被NSA要求保密，引发学界对其存在“后门”的猜疑。多年的公开分析最终证明其S盒设计非常优秀，能抵抗当时未知的差分分析。
    DES的公开分析过程确立了 “安全通过透明实现” 的现代密码学原则。这直接印证并强化了柯克霍夫斯原则——算法的安全性不应依赖于保密，而应依赖于经得起公开检验的数学强度和密钥保密。

  • 分组长度也需要足够大，防止碰撞与效率攻击
    DES的64位分组长度在数据量巨大时，可能面临生日攻击风险。现代分组密码（如AES）将分组长度提升至128位.

  • 标准化过程必须具有前瞻性和全球参与性
    DES由NSA主导，而AES的选拔由NIST公开进行，全球参与，过程透明。
    一个密码标准的安全性和可信度，与其制定过程的开放性、竞争性和学术共识直接相关。

任何密码算法的安全性都是相对于特定时代的计算能力而言的。 一个优秀的密码标准，必须具备公开透明、经得起检验的数学结构、足够且可扩展的参数，并预见到未来数十年的算力发展。

DES的谢幕，标志着密码学从早期的“安全通过隐匿”和固定设计，正式迈入了算法公开、参数可调、全球共研的现代密码学时代。

Asymmetric

把通信设置想象成一个带锁的信箱：

  • 公钥pk：就像是这个信箱的投递口。它的尺寸和形状是公开的。任何人（Bob）都知道如何通过这个投递口往里面扔信件（加密消息）。把这个投递口的规格告诉别人是安全的，因为它只允许投入，不允许取出。
  • 私钥sk：就像是打开信箱的物理钥匙。只有 Alice 一个人拥有这把钥匙。她用这把钥匙才能打开信箱，取出并阅读 Bob 投递进来的密文信件。

所以，Bob 拿到公钥pk，就像是他知道了 Alice 信箱投递口的精确尺寸，这样他就能准备一封能塞进去的信。
(加密密钥公开，解密密钥保密)

Computing

每一个密码学算法，都基于一个数学上难以解决的问题。
在数学上，这类问题对应的函数叫陷门函数。
而在计算理论中，这类问题必须属于NP但不属于P。

这个部分希望从计算理论的角度，介绍现代应用的公钥密码：签名，加密，密钥协商。
所需要的所有数学工具：大整数分解问题，离散对数问题，椭圆曲线离散对数问题，以及哈希函数

  • P：能在多项式时间内被确定性图灵机解决的问题。
  • NP：能在多项式时间内被非确定性图灵机解决，或能在多项式时间内验证一个解的问题。
  • NP-complete：NP 中最难的问题，如果其中一个有多项式时间算法，那么 NP = P。
  • BQP：能在多项式时间内被量子计算机以高概率解决的问题。

经典的、被认为 属于 NP 但不属于 P 问题的例子。这些问题是密码学、优化和理论计算机科学的核心。

经典的属于 NP 但不属于 P 问题的例子

1. 布尔可满足性问题（SAT）

  • 描述：给定一个布尔逻辑公式（由 AND, OR, NOT 和变量构成），问是否存在一组变量赋值，使得整个公式结果为真。
    硬件与芯片设计验证，软件包依赖管理，程序分析与漏洞挖掘，“状态机分析器”
    任何离散系统（包括计算机程序、数字电路、协议流程）都可以被建模为一个状态机，在一个由状态和转换构成的系统中，寻找一条满足特定条件的路径

2. 旅行商问题（TSP）

  • 描述：给定一系列城市和城市间的距离，问是否存在一条路径，访问每个城市恰好一次并返回起点，且总路程不超过一个给定值 K。

3. 图着色问题

  • 描述：给定一个图和一个数字 k，问是否可以用 k 种颜色给图的顶点着色，使得任何相邻顶点颜色不同。

4. 子集和问题

  • 描述：给定一个正整数集合 S 和一个目标值 T，问是否存在 S 的一个子集，其元素之和正好等于 T。
  • 为什么属于 NP：如果给你一个子集，你可以在多项式时间内将其元素相加，看是否等于 T。
  • 为什么被认为不属于 P：它是 NP-完全 问题。它是公钥密码学和比特币“找零”问题的基础。基于此问题的密码系统（如 Merkle-Hellman 背包密码）虽大多被破解，但该问题本身仍是 NP-完全性的经典例子。

5. 整数分解（判定问题形式）

  • 描述（判定问题形式）：给定整数 N 和 M，是否存在一个整数 f (1 < f < M)，使得 f 能整除 N？
  • 为什么属于 NP：如果给你一个因子 f，你可以在多项式时间内做除法验证。
  • 为什么被认为不属于 P：虽然其搜索版本（找出因子）在 BQP 内（量子计算机可解），但在经典计算下，它与分解问题同样困难，且不被认为是 NP-完全的。这是它与上述例子的关键区别。它是 RSA 密码系统 安全性的基础。

6. 离散对数问题

  • 描述（判定问题形式）：给定一个素数 p、一个生成元 g 和结果 y，是否存在一个整数 x 使得 g^x ≡ y (mod p)？
  • 为什么属于 NP：如果给你 x，你可以在多项式时间内通过模幂运算验证。
  • 为什么被认为不属于 P：在经典计算模型下没有已知的多项式时间算法。它是 Diffie-Hellman 密钥交换 和 数字签名算法（DSA） 安全性的基础。

局部最优的解决思路-机器学习

  1. 推理是简单的（P）：使用模型是高效的。
  2. 训练是困难的（NP-Hard）：从理论上讲，找到完美的模型是极其困难的。
  3. 实践是巧妙的：我们通过放弃理论上的“完美”（全局最优），拥抱实践中的“好用”（局部最优+泛化），用高效的近似算法（梯度下降）解决了理论上NP-Hard的问题。
  4. 验证和设计是更具挑战的（NP-Complete/Hard）：确保模型绝对安全或自动设计最优模型，是当前面临的最大计算挑战之一。

大整数分解问题-RSA算法

离散对数-DH/ECC算法

哈希函数

密码系统的分析方法

常见分组(对称)密码分析方法：
(1)差分密码分析
通过分析两个明文差值对密文差值的影响，来推断出某些密钥比特。
(2)线性密码分析
通过寻找给定密码算法的线性近似表达式，来破译密码算法。
(3)差分-线性密码分析
将差分密码分析和线性密码分析相结合，降低密码破译的计算复杂度。
(4)插值攻击
利用拉格朗日插值公式的思想，给出加解密算法的等价变换，以破译密码算法。
(5)密钥相关攻击
根据两个具有某种关系的密钥和相应的明文密文对，来对密码算法进行分析攻击。

密码系统的攻击方式

① 惟密文攻击（Ciphtext-only Attack）
在惟密文攻击中，密码分析者知道密码算法，但仅能根据截获的密文进行分析，以得出明文或密钥。由于密码分析者所能利用的数据资源仅为密文，这是对密码分析者最不利的情况。最易抵抗的攻击类型！

② 已知明文攻击（Plaintext-known Attack）
已知明文攻击是指密码分析者除了有截获的密文外，还有一些已知的“明文—密文对”来破译密码。密码分析者的任务目标是推出密文的某种解密算法，甚至从已知的明文被变换成密文的方式分析出密钥。

③ 选择明文攻击（Chosen Plaintext Attack）
选择明文攻击是指密码分析者不仅可得到一些“明文—密文对”，还可以选择被加密的明文，并获得相应的密文。这时密码分析者能够选择特定的明文数据块去加密，并比较明文和对应的密文，已分析和发现更多的与密钥相关的信息。
密码分析者的任务目标也是推出用来加密的密钥或某种算法，该算法可以对用该密钥加密的任何新的消息进行解密。

④ 选择密文攻击(Chosen Ciphertext Attack)
选择密文攻击是指密码分析者可以选择一些密文，并得到相应的明文。选择的密文可能与要破解的密文相关。密码分析者的任务目标是推出密钥。

Demo on SSH

https://github.com/settings/keys

  • 演示ssh协议的工作机制
  • 展示对称加密、签名、密钥协商的实际应用
  • 说明哈希算法对中间人攻击的防御——有KEM的地方一定会用哈希
  • github的工作方式(git clone)对ssh的封装
  • 引出密码算法的更多应用：软件分发、HTTPS(TLS/SSL)……

From PKE to KEM

  • 从一个信息传递工具变成了通信工具中的组件(综合考虑安全、效率等问题)
  • 从CPA-安全的密码系统到CCA-安全。(抵御选择密文攻击)

选择密文攻击：

这些例子的一个共同致命弱点是：它们无法检测密文是否被篡改。=> 这是一个保证消息完整性的问题，解决方案就是使用哈希函数处理输出密文，接收方验证哈希值。(不暴露E(m))

  • CPA安全的系统 只承诺：“如果你不碰密文，那么攻击者无法从密文中学到东西。”
  • CCA安全的系统 承诺了更多：“即使你恶意地篡改了密文，你不仅无法学到东西，而且我还会让这次解密失败（输出错误或随机值），从而不让你获得任何有用的信息。”

ML-KEM

量子安全：

  • Shor算法：能高效解决整数分解和离散对数问题（包括椭圆曲线上的），在量子计算机上运行时间为多项式级。这直接击溃了RSA、ECC等算法。
  • Grover算法：为搜索问题提供平方根加速，但对对称加密和哈希函数的影响是有限的（例如，将128位安全强度降为64位，我们可以通过将密钥长度增加到256位来轻松应对）。
  • 格密码（LWE, SIS等）的抵抗力：目前没有已知的量子算法能像Shor算法破解RSA那样，为格问题提供指数级加速。最好的量子算法（如格筛法）也只能提供一些多项式加速，其核心难度依然是指数级的。这就是为什么基于格的问题（如LWE、SIS）被认为是后量子安全的。

“最坏情况归约”的重要性

这是LWE/格密码一个极其强大的理论优势：

  • 传统密码学（RSA, ECC）：其安全性基于解决一个随机实例的困难性（例如，分解一个随机大整数）。
  • LWE/格密码：其安全性可以归约到解决格上某个问题的最坏情况实例的困难性。这意味着，如果能破解一个随机的LWE实例，那么你就能解决任意格上的一个最坏情况难题。

A Brief Introduction to Cyber Security

网络空间安全，涉及网络空间中的电子设备、电子信息系统、运行数据、系统应用中的安全问题。
密码学作为网络安全专业的重要工具，是其中一条重要的线索，连接起各个层面的业务安全。

无论在系统哪个层面，密码学都扮演着"安全语法"的角色：

  • 在基础设施层：TLS协议保护传输通道
  • 在系统层：数字签名验证软件完整性
  • 在数据层：加密算法保护静态和动态数据
  • 在身份层：证书和挑战-响应机制验证实体
  • 在业务层：不可否认性确保交易可审计