本文旨在深入浅出地讲解密码编码学，面向懂基本二进制运算的受众。

理论

古典密码

单表替换密码

简单代替密码通过把26个英文字母随机打乱生成查找表。它很容易破译，因为明文中不同字母的出现频率信息被原封不动地保留在密文中。

机械加密

多表替换能一定程度上掩盖频率信息。最著名的转轮装置是恩尼格马(Enigma)，它在第二次世界大战期间由德国人使用。它的破解（由图灵等人完成）并非源于密码学原理的正面突破，而是利用了其机械设计缺陷（如一个字母永远不会加密成它自己）和操作流程上的漏洞。

消息形式

古典密码对字符操作；数字时代的消息格式不再局限于英语文本，计算机加密用于操作二进制序列。

计算机密码

对称密码

形式化定义：输入消息M(message)和密钥K(key)到加密函数enc(encrypt)，得到密文C(ciphertext)；运行解密函数dec(decrypt)还原明文P(plaintext)=M。函数如下：

C=enc(M,K)
P=dec(C,K)

通信协议要求双方通过安全信道协商好K，然后通过不必安全的信道传输C。

理论上不可破的密码

存在一种密码，使得无论算力多么大，无论对手得到多少密文，都无法还原明文。

一次一密乱码本

密钥生成：把密钥K选取为与消息M相同长度的真随机数。
加密函数：C=xor(M,K)。
解密函数：P=xor(C,K)。其中xor为二进制异或

一次性密码本（One-Time Pad）的主要局限在于密钥管理。它要求密钥与消息等长且不可复用，这实际上并未解决安全通信的根本问题，而是将“安全传递消息”的难题转化为了“安全传递等长密钥”的难题。

在现实世界里，密钥管理是密码学领域最困难的部分。设计安全的密钥算法和协议是不容易的，但你可以依靠大量的学术研究。相对来说，对密钥进行保密更加困难。

除了一次一密之外的密码系统在唯密文攻击中都是可破的，方法是蛮力攻击。

计算上安全的密码

分组密码算法可以很容易地用软件实现，因为它可以避免耗时的位操作，并且它易于处理计算机界定大小的数据分组。另一方面，序列密码更适合用硬件实现，因为使用硅材料可以非常有效地实现它。

分组密码AES的分组长度为128位，密钥长度分为128、192、256位共三个等级；是现代对称加密的主流选择，尤其是在现代CPU配备了AES-NI指令用于硬件加速的情况下。在AES标准颁布后才发展起来的序列密码ChaCha20是在没有硬件加速的设备上做对称加密的另一主流选择。

从分组密码的视角看单字母替换密码，单字母替换密码可以视为分组长度为一个字符的短分组密码，秘钥空间为26的阶乘，且易受频率分析攻击。AES的128位分组长度很好地隐藏了频率信息。

分组密码的设计

设计一个分组密码很容易。如果把64位分组密码看成是一个64位数的置换，显然几乎所有这样的置换都是安全的。困难的是设计一个分组密码不仅要安全，而且要容易描述和简单实现。
如果有一个巨大的存储器来存储48X32的S盒，那么设计一个分组密码很容易。如果把DES迭代128轮，那么想要设计一个不安全的DES变形将十分困难。如果密钥长度为512位，实际上就不用关心这些密钥是否有互补特性。
实际上，设计分组密码非常困难的原因，是该密码要具有尽可能小的密钥、尽可能小的存储空间以及尽可能快的运行速度

能不能像单字母替换密码那样存储一个双射表来实现一个分组长度128位的密码呢？不能，因为地球没有这么多的硅原子。

这正是为什么分组密码（如AES）需要被设计成一个紧凑的算法，而不是一个巨大的查找表。算法本身（代码和S盒等）可能只有几KB大小，但它能有效地模拟出一个从2^128个输入到2^128个输出的、看起来完全随机的置换，而无需真正存储这个天文数字般的映射表。

分组密码算法的设计就是用较少的存储空间创建这样大的表。
技巧是在一个密码中以不同的组合方式多次混合扩散和混乱（用更小的表），这称为乘积密码(product cipher)

有没有不需要安全传输密钥的密码

在现代对称加密中，通信双方都不需要存储完整的查找表，且加密映射和解密映射均由同一个密钥K定义。有没有办法让加密映射和解密映射由不同的密钥定义，且知道发加密密钥的人无法推导出解密密钥呢？

经典非对称密码

形式化定义：输入消息M(message)和公钥Kpub到加密函数enc(encrypt)，得到密文C(ciphertext)；输入密文C和私钥Kpri到解密函数dec(decrypt)还原明文P(plaintext)=M。函数如下：

C=enc(M,Kpub)
P=dec(C,Kpri)

通信协议只要求将Kpri保密，且允许公开地分发Kpub，然后通过不必安全的信道传输C。且根据Kpub计算出Kpri是一个数学难题。

公开密钥密码与对称密码是两种不同的东西，它们解决不同的问题。对称密码适合加密数据，它速度极快并且对选择密文攻击不敏感；公开密钥密码可以做对称密码所不能做的事情，它最擅长密钥分配。

1976年后，提出了多种公开密钥算法，其中许多是不安全的。而那些被视为安全的算法，有许多却不实用，要么密钥太大，要么密文远大于明文。

背包密码系统

尽管这个算法后来发现是不安全的，但由于它证明了如何将NP完全问题用于公开密钥密码学，所以很值得研究。

普通背包问题（困难）：背包问题描述起来很简单。给定一堆物品，每个重量不同，能否将这些物品中的几件放入一个背包中使之等于一个给定的重量?更公式化的描述:给定一系列值M1，M2，…，Mn 和一个和S，计算Bi，使之满足:;
S=B1M1+B2M2+…+BnMn

Merkle-Hellman背包算法的思想是将消息编码为背包问题的解。明文分组长度等于堆中物品个数，且明文位与B的值相对应，密文是计算得到的和值。Bi的值可为0或1，1表示这个物品在背包中，0表示不在。一般来说，解决这个问题所需的时间似乎会随着堆中物品个数的增加呈指数增长。

如果重量的序列是一个超递增序列(Superincreasing sequence)那么相应的背包问题易求解。

Merkle-Hellman算法就是利用了这个性质。私人密钥是一个超递增背包问题的重量序列。公开密钥是有相同解的普通背包问题的重量序列。Merkle和Hellman设计了一种方法可将超递增背包问题转化为普通的背包问题，他们用模运算来完成此变化。

RSA

RSA是原理最直观、容易理解的公钥密码算法之一。

密钥生成：随机生成等长的素数p、q，计算模数n=p*q，可将e选取为固定的65537且不影响安全性；用扩展欧几里得算法找到d使得e*d = 1 mod (p-1)(q-1)。销毁p、q。
公钥是e、n，私钥是d。
加密函数：C=M^e mod n
解密函数：P=C^d mod n

初等数论能证明上述等式成立，本文不讲具体数学证明。

对RSA的最有力的攻击是对N分解质因数，这至今是一个指数复杂度的问题。那为什么我们能快速找到两个大素数呢？因为“检测一个大数是否为素数”要比“找出大数的一个素因子”要快得多。一台普通计算机很快就能生成两个大素数，且很快计算出n、e、d，但基于分解n计算出私钥d对于超级计算机也是个难题。

RSA的私钥d几乎与模数n一样长，且私钥空间不稠密，密钥管理不便。

将RSA与对称密码混合的模型是用对称算法加密长消息，然后用公钥加密对称密钥；接收方用私钥解密得到对称密钥进而还原消息。更现代的非对称密码的模型是双方共同计算出同一个大数，然后双方用同一个大数确定性派生出对称密钥。

Diffie-Hellman算法

DH只能用于密钥协商，但它是理解更现代公钥密码的阶梯。

选择一个大的索菲·热尔曼素数n和一个小的生成元g，然后：

Alice选取一个大的随机整数x，并发送给Bob:X=g^x mod n。
Bob选取一个大的随机整数y，并发送给Alice:Y=g^y mod n。
Alice 计算 k=Y^x mod n。
Bob 计算 k'=X^y mod n。

k和k'都等于g^(xy) mod n。即使线路上的窃听者也不可能计算出这个值，他们只知道n、g、X和Y。除非他们计算离散对数，恢复x、y，否则无济于事。因此k是Alice 和 Bob 独立计算的秘密密钥。

用颜料混合协议做类比：

Alice选取一个随机颜料x，将它与n个单位的公开基底颜料g混合成X寄给Bob
Bob选取一个随机颜料y，将它与n个单位的公开基底颜料g混合成Y寄给Alice
Alice再取同样的颜料x与Y混合得到k
Bob再取同样的颜料y与X混合得到k'

k和k'都等于xyg的固定单位的混合色颜料。安全性基于窃听者即使知道n、g也无法从混合色X中提取出x，如果窃听者有一台颜料分离提纯装置可以从混合色颜料中“除去”g就能攻破颜料混合协议，但DH算法在特定有限域是安全的。

如果x是Alice的长期固定私钥，那X是Alice的长期固定公钥。

ElGamal

ElGamal用了与DH几乎一样的思想来实现加密

密钥生成：要产生一对密钥，首先选择索菲·热尔曼素数p，两个随机数g和x，g和x都小于p，然后计算:
y=g^x mod p

公开密钥是y、g和p，私人密钥是x。g和p可由一组用户共享。

加密函数：选择与p-1互素的随机数k。然后计算:
a=g^k mod p
b=M * y^k mod p
a和b是密文对。注意，密文的大小是明文的两倍。

解密函数：计算a^x的模p乘法逆元然后乘以b

M= b/a^x (mod p)

证明：因为a^x=g^(kx) mod p以及b/a^x≡My^k/a^x≡Mg^(xk)/g(kx)=M mod p都成立，除了y是密钥的一部分以及通过乘以y加密外，它和Diffie-Hellman密钥交换几乎一样。

在GF(p)上寻找离散对数的复杂性实质上与对同样大小的一个整数"进行因子分解的复杂性一样，"是两个大致等长的素数的乘积

计算离散对数与因子分解有紧密的关系。如果你能解决离散对数问题，那么你就能解决因子分解问题。(逆命题的正确性还未被证明)。

ElGamal的私钥短但公钥和密文依然长。

rsa能加密小于模数N的自然数，ElGamal能加密小于模数p的自然数，aes单次能加密128位的分组，他们的定义域都是整数环——自然数域的子集。更现代的公钥加密算法定义在椭圆曲线域。

椭圆曲线密码

在相同的加密强度（安全级别）下，椭圆曲线加密（Elliptic Curve Cryptography, ECC）所需的密钥长度是所有主流非对称算法中最短的。有限域GF(2^n)上的椭圆曲线特别有趣，它们提供了一个更快的具有更小密钥长度的公开密钥密码系统。很多公开密钥算法，如Diffie-Hellman、EIGamal和Schnorr可以在有限域上用椭圆曲线实现。

它将 ElGamal 的思想从整数环上的乘法运算，巧妙地“搬”到了椭圆曲线上的点运算。椭圆曲线域只需定义点的加法和逆元两种基本运算，然后通过加法定义倍乘、通过逆元定义减法。

椭圆曲线密钥生成通常需要先选择一条特定的曲线参数和曲线上的基点G。

密钥生成

Alice使用她的私钥 d 计算出公钥点 Q = d * G并发布公钥。

无论用于密钥协商还是加密，都需要Bob选择一个一次性的、随机的秘密数字 k，计算C1 = k * G

ECDH

Alice计算：S = d * C1

Bob计算：S = k * Q

双方计算结果是完全一样的，都等于d*k*G，他们可以基于这个共同计算结果派生出一样的对称密钥。Alice通过椭圆曲线域的倍乘运算难以反向求d的特性把私钥掩盖，k也可以视为Bob的临时私钥。

椭圆曲线加密

加密方额外计算：C2 = M + S

解密：M = C2 - S（点的减法就是加上一个点的逆元）

此处比ElGamal多出的麻烦在于椭圆曲线中的M需要被编码为曲线上的点，本文不讲怎么进行这个编码。

量子计算机对传统密码的影响

对称密码的安全性不依赖于任何有“捷径”的数学难题。它的安全性主要来自于穷举搜索的巨大复杂性。

量子Grover算法将对称密钥的有效安全强度减半。对称密码在量子时代依然可用，只需选择足够长的密钥。
量子Shor算法能够在多项式时间内高效地解决大整数分解和离散对数问题。

一旦有了足够规模的容错量子计算机，上述传统非对称密码都不安全。

后量子密码

后量子密码在经典图灵计算机上运行，且能抵抗量子计算机攻击；只不过密钥和密文扩展普遍比传统非对称密码大。

kyber

kyber安全性基于格理论中的带模学习误差问题（Module-Learning With Errors, M-LWE）。

密钥生成

生成公共矩阵 A：
- 首先，系统会生成一个公开的、随机的“种子” ρ (rho)。
- 使用这个种子 ρ 通过一个可扩展输出函数（如SHAKE-128）可以确定性地生成一个巨大的、所有人都认可的公共矩阵 A。
- 关键点：我们不需要存储或传输整个矩阵 A，只需要存储和传输小小的种子 ρ 就行了。任何人拿到 ρ 都能自己重新生成出完全一样的 A。
生成Alice的秘密 s 和误差 e：
- Alice在自己的电脑上生成一个随机数，并用它派生出她的秘密向量 **s 和一个误差向量 e**。
- 这些向量里的多项式系数都非常小，这是保证解密正确性的关键。它们是从一个中心二项分布中采样的。
计算公开向量 t：
- Alice使用公共矩阵 A、她的秘密 s 和误差 e，进行核心计算：
  t = A * s + e
- 这个计算过程是在多项式环上进行的，包含大量的多项式乘法和加法。为了加速，实际实现中会使用一种叫NTT（数论变换）的技术。
组合成公钥和私钥：
- 公钥 (Public Key, pk)：就是计算结果 t 和用于生成 A 的种子 ρ。所以 pk = (t, ρ)。Alice可以把这个公钥告诉任何人。
- 私钥 (Secret Key, sk)：就是Alice的秘密向量 s。sk = s。Alice必须绝对保密。

加密函数

Bob也生成一个自己的一次性的、临时的秘密向量 r，以及两个小的误差向量 **e1 和一个误差多项式 e2**。这些也都是“小”的多项式。
计算密文的两个部分 u 和 v：
- 第一部分 u：Bob用 A 的转置 A^T 和自己的临时秘密 r 计算出一个密文组件：;
  
  u = A^T * r + e1;
  
  这部分的作用类似于一个临时的“公钥”，用于混淆消息。
- 第二部分 v：Bob用Alice的公开向量 t、自己的临时秘密 r、误差 e2 以及他想加密的消息 m（m 会先被编码成一个多项式）来计算：;
  
  v = t^T * r + e2 + encode(m);
  
  这部分是真正承载加密信息的地方。

解密函数

计算result = v - u^T * s
得到结果是编码后的消息加上一堆误差项 (e^T * r + e2 - e1^T * s)。因为 s, e, r, e1, e2 里面的所有系数都非常小，所以它们乘积和加减的结果（也就是总噪声）也非常小。所以，result 的值会非常接近 encode(m)。Alice只需要对 result 的系数进行一个简单的“取整”操作，就能消除掉这点微小的噪声，完美地恢复出 encode(m)，然后再解码得到原始消息 m。

McEliece算法

McEliece算法很早就被提出。

它存在着多个问题：公开密钥太庞大，数据扩展太大，密文长度是明文的两倍。在进入量子计算时代后焕发新生，但在后量子密码竞赛中的整体表现依然不如Kyber。

标准与应用

密钥长度

热力学局限性

根据热力学第二定律，表示信息需要一定的能量。通过改变一个系统的状态来记录一个比特位，需要的能量不小于kT。

穷尽全宇宙的能量，最多能让一个229位的计数器穷举其状态位。故对256位秘钥的对称密码做穷举破解是不可能的。全宇宙只有10^80个原子，2^256即使在全宇宙范围内也是个很大的数。

公钥密码长度

特性	RSA (用于混合加密)	ElGamal (经典)	ECC (ECIES)	Kyber (PQC 标准)
安全基础	大整数分解难题	离散对数难题 (DLP)	椭圆曲线离散对数 (ECDLP)	格上的带模学习误差 (M-LWE)
所需参数大小	模数 n ≈ 3072/7680/15360位	模数 p ≈ 3072/7680/15360位	曲线阶 n ≈ 256/384/521位	Kyber-512/768/1024
---	---	---	---	---
非压缩公钥长度	`= (n, e)`	`= (p, g, y)`	65/97/133字节 (非压缩)	800/1184/1568字节
私钥长度	=n	32/48/64字节	=n	1632/2400/3168字节且均可基于64字节的种子派生
密钥封装长度	=n	=p	33/49/67字节	768/1088/1568字节

现代混合密码方案

用于存储的长期加密，建议优先试用：AES256 + x448级联Kyber1024
如果遇到性能问题，可以降为：AES192 + Curve25519级联Kyber768
如果需要最短的私钥且不需抗量子，使用：AES128 + Curve25519

椭圆曲线参数选择

如果你正在开发一个新的应用，需要进行密钥交换或数字签名，Curve25519 是毫无疑问的首选。它更快、更安全、更容易正确使用。如果需要更高的安全级别，可以选择 x448。
secp256k1 的地位非常特殊。它凭借在加密货币领域的巨大成功，成为了经受过最高强度现实攻击考验（价值数万亿美元的资产由它保护）的曲线。但它的安全性高度依赖于少数几个经过千锤百炼的开源库（如 libsecp256k1），不建议非专家自行实现。
P-521 则更像是一个“遗产”或特定领域的选择，在新的通用项目中已经很少被考虑。

这是四条标准椭圆曲线核心参数的简洁列表。

Curve25519 (X25519)

方程: $y^{2} = x^{3} + 486662 x^{2} + x$ (蒙哥马利曲线)
素数 p: $2^{255} - 19$
基点 Gx: 9
阶 n: $\approx 2^{252}$
协因子 h: 8

x448 (Curve448)

方程: $y^{2} = x^{3} + 156326 x^{2} + x$ (蒙哥马利形式)
素数 p: $2^{448} - 2^{224} - 1$
基点 Gx: 5
阶 n: $\approx 2^{446}$
协因子 h: 4

secp256k1

方程: $y^{2} = x^{3} + 7$
素数 p: $2^{256} - 2^{32} - 977$
基点 Gx: 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
基点 Gy: 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
阶 n: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
协因子 h: 1

P-521 (secp521r1)

方程: $y^{2} = x^{3} - 3 x + b$
素数 p: $2^{521} - 1$
系数 b: 一个十六进制表示有131位的巨大常数
基点 Gx: 0x00C6...BD66 (一个巨大的常数)
基点 Gy: 0x0118...F650 (一个巨大的常数)
阶 n: 0x01FF...C140 (一个接近 $2^{521}$ 的素数)
协因子 h: 1

分组密码模式与常用加密软件

民用密码分析学界至今没找到比穷举密钥更好的破解aes单个分组的办法，但用同一个密钥加密长于1个分组的消息时，选择不同的模式可能会泄露一些信息有助于密码分析。

对比一次一密乱码本与AES的CTR模式，主流对称加密就是将大秘密变成小秘密。

对称加密成品

cryptomator

保险库格式

v8对文件内容和文件名都使用了 AES-256-SIV 模式。
** v7 及更早**
- 文件内容加密: 使用 AES-256-CTR (Counter Mode)。
- 文件名加密: 使用 AES-256-CBC (Cipher Block Chaining) 并配合密文窃取（Ciphertext stealing）。
- 文件完整性: 通过单独计算的 HMAC-SHA256 来实现

适合网盘存储场景

VeraCrypt

用XTS模式，不提供完整性校验

适合需快速随机访问明文和合理否认性的场景

使用建议：将只读挂载与作为可移动介质挂载设为默认挂载选项

操作系统自带加密

适合不想安装额外软件的场景

ubuntu的LUKS

用XTS模式

BitLocker

从 Windows 10 版本 1511 开始，对于新加密的驱动器，BitLocker 的默认加密模式是 XTS-AES。
在 Windows 10 版本 1511 之前，或者为了兼容更早的 Windows 版本（如 Windows 7），BitLocker 使用的是 AES-CBC (Cipher Block Chaining) 模式。

openssl和git-crypto

默认AES-256-CBC模式

适合简单的密码解密场景

非对称加密成品

适合需要让加密设备不能解密的场景

gnupg和git-secret

v2.4不支持后量子密码，v2.5支持后量子密码但不支持导出私钥。

模式：

CFB (历史)
OCB(现代AEAD)

PGP

PGP将可能是接近军事级加密的最佳捷径。

PGP 公司后来几经转手，最终被赛门铁克 (Symantec) 收购，其商业版本 PGP Desktop 仍在维护，但影响力已大不如前。

Signal

同时使用 X25519 和 Kyber-1024 进行密钥交换

软件加密实现细节

自行编写代码实现密码算法的全部细节难以使软件抵抗侧信道攻击，故加密需求应优先使用成品软件，次优选择被广泛审计的库。