密码学第一个笔记

第一节：课程概况#

密码学（Cryptography）是信息安全的重要基础工具。

信息安全可以从不同角度研究，其中一个重要区分是：

• 安全通信：信息处于传输过程中，在两个或多个实体之间交换，同时防止攻击者监听、篡改、伪造等。
• 安全存储：信息处于存储状态，例如保存在磁盘或其他存储介质中，防止信息被未授权读取、修改、删除或窃取。

大白话就是安全通信关注“运动中的数据（data in transit）”，安全存储关注“静止的数据（data at rest）”。

以最基本的对称密码通信模型为例：

A 和 B 共享一个秘密密钥K 。A 使用 K对消息进行加密，B 使用同一个K进行解密。

现代密码系统通常遵循一个重要原则：密码算法本身可以公开，系统的安全性主要依赖密钥K的保密。

攻击者可能知道算法、看到密文，甚至在更强的攻击模型中监听和操纵通信，但不能在正常安全假设下直接获得秘密密钥。

密钥有些情况下只能使用一次，例如一次性密码本（One-Time Pad）；现代密码系统通常允许一个密钥保护大量数据，但必须按照协议要求正确使用随机数、Nonce 等机制。

密码学主要解决密码学模型和攻击假设下的安全问题，不能直接解决软件漏洞、实现错误、系统配置问题、社会工程学等问题。

因此可以概括为：密码学是信息安全的重要基础，但不是信息安全的全部​

第二节：什么是密码学#

• 数字签名：是密码学中的一种安全机制，数字签名由被签署的消息和签名者的私钥共同生成，具有完整性，认证性，不可否认性。
• 匿名通信：B看不到A的某些信息（根据威胁模型而定），可相互通信。
• 安全多方计算：不用第三方权威机构进行统计计算，只用相互传递在不泄露数据的情况下计算出需要的值。
• 私有外包计算：A向B发加密信息，B不解密直接带入查询，查询出来的加密信息再交给A，由A进行解密，B不知道A发送和发出的加密信息内部是什么。
• 零知识证明：A知道秘密，B知道公开信息。B要在不泄露秘密的情况下，去询问A进行检验A是否真的知道信息，作弊者成功欺骗的概率可以无限趋近于0，例如：B公开信息（两个球，颜色不同）A能看到球的颜色，不知道秘密的都是色盲，B可以选择交换两个球的位置或不交换去问A球是否交换了检测A是否知道秘密。

描述概念三部曲：指定威胁模型，构造，证明

第三节： 信息论安全和一次性密码本#

密码的符号：K密钥，M明文，C密文，D解密算法，E加密算法。满足 D(K,E(K,M))=M 即为可解密。

大白话就是A是干加密的，E(K,M)=C。B是干解密的，D(K,C)=M，这俩合一块，能解密开，那就是可解密的。

一次性密码本：{0,1}ⁿ，它是所有 n 位二进制字符串的集合。K 为随机生成的、长度与 M 相同的一次性密钥，即 |K|=|M|，具有完善保密性。

异或（XOR）：符号为 ⊕ 。一一对应中，相同为0，不同为1。在这里加密：K⊕M=C，解密：K⊕C=M。对于固定的 K，M 与 C 的映射是双射，一一对应关系依照 K 决定。运算举例如 M：00100，K：10000，则 C 为 10100。

在现实中难以使用的原因是 K 长度要和 M 长度一样长，因此需要传输、存储和安全共享同样长度的密钥，而且密钥只能使用一次，密钥管理很麻烦。

完善保密性：核心就是攻击者看到密文后，不能因此获得关于明文的额外信息。形式化地说：Pr[M=m | C=c] = Pr[M=m]。等价地，对于任意两个明文 M0、M1 和任意密文 c，有 Pr[C=c | M=M0] = Pr[C=c | M=M1]，即攻击者无法仅根据密文判断原来的明文是 M0 还是 M1。完善保密性是一种信息论安全性质，不依赖攻击者的计算能力。

第四节：流密码和伪随机数生成器#

流密码：通常不直接使用与明文等长的完全随机密钥，而是使用一个较短的随机密钥作为种子，通过伪随机数生成器（PRG）扩展成较长的伪随机密钥流，再与明文进行 XOR。

伪随机数生成器（PRG）：把 n bit 的随机种子扩展成 m bit 的伪随机输出，其中 m＞n。

其中算法 G 是确定性的，并且通常是公开已知的；密钥/种子 K 保密。G(K) 不要求本身保密，攻击者甚至可以看到部分输出。

PRG 不具备 OTP 那样的信息论完美保密性，因为较短的 n bit 随机种子被扩展成了 m bit（m＞n）的输出，因此输出不可能覆盖所有可能的 m bit 字符串，而只能产生其中一部分。

判断 PRG 是否安全的一种方式是不可预测性（Unpredictability）：

大白话：攻击者即使已经知道 PRG 输出的一部分 G1(K)，也无法有效地预测剩余部分 G2(K)。例如在流密码中，如果攻击者知道某一部分明文 M1 和对应密文，就可能得到对应的 G1(K)，然后尝试预测后面的 G2(K)。如果 G2(K) 为 1 bit，那么攻击者的预测成功概率≤随机猜测的 1/2 高一点点，而且这个“一点点”会随着安全参数增大而趋近于 0，就是不可预测性。

例如，如果 PRG 输出存在固定前缀、明显规律等，使攻击者在看到 G1(K) 后能够以明显高于 1/2 的概率预测 G2(K)，那么该 PRG 就不满足不可预测性，因此不安全。

第五节：PRG的安全定义#

不可区分性：G输入K Bit，最多产生2的K次方种不同的输出，而整体随机空间R最多有2的n次方种不同的n Bit字符串，k小于n，若攻击者无法将G（A）和R进行有效区分，即为不可区分性。

统计测试：统计测试是一种输入{0,1}的n次方的算法，如果它认为输入和随机一样，就会输出1，反之输出0。优势（ADV）意思是查看统计测试对PRG输出和真正随机输出的判断结果相差多少，ADV=|统计测试对G（A）输出1的概率-统计测试对R输出1的概率|，区间是[0,1]，理想情况下，ADV越接近0越无法区分，ADV越大越容易区分。

统计测试常见方式：∣#0−#1∣≤10倍根号下n，意味着1和0在统计上没有偏离超过典型随机波动尺度（即为根号n）的10倍，我就暂时认为它没问题。

最大零游程（maximum zero-run），意味着如果一个PRG输出的比特串特别容易出现超长的0或1游程，那么它可能泄露了“我不是随机的”。

安全的伪随机数生成器：统计测试只是一个区分器的具体长相，对于任意一个高效的攻击者/区分器，它的ADV都应该是可忽略的（1/2000这种固定概率也算不可忽略的）。安全定义允许攻击者自己设计这个区分器，而且它甚至可以专门针对目标PRG的弱点设计，因此安全的PRG不是“通过几个统计测试”就算安全，而是应该通过任意高效区分器的检验。

补充：我们目前无法无条件证明严格意义上的安全PRG一定存在。经典结果是：不能简单认为P≠NP和PRG存在是等价关系。

Yao’82：简单来说就是不可预测性和不可区分性是充要的。

第六节：现实世界中的流密码#

RC4：原理可理解为 PRG。KSA：先用密钥把 256 张牌搅乱一次。PRGA：每次再搅两张牌 → 抽出一张 → 作为一个字节输出→ 继续搅 → 再抽下一张。即先 K → G(K) 扩展，后通过循环机制持续输出密钥流 Z。Z ⊕ M = C。循环机制可理解为“有规律的持续洗牌”。

问题一：RC4 输出的第二个字节不像真正随机数那么均匀，出现 0 的概率约为 1/128，而理想随机情况是 1/256。原因：输出初期存在统计偏差，可以粗略理解为“刚洗完牌还有痕迹”。应急办法：丢弃前 256 字节，从第 257 字节开始取。

问题二：RC4 的输出中，(0,0) 这个二字节组合可能存在统计偏差，即其概率可能偏离理想随机情况。(0,0) 即：00000000 00000000

如果观察的输出越长，能检查的连续二字节位置越多，因此整段输出中“至少出现一次 (0,0)”的概率也越大。

原因：1、(0,0) 本身可能存在 RC4 的统计偏差，2、输出越长，观察机会越多。

解决方法：不要继续使用 RC4，改用现代安全的加密方式。

CSS：（Content Scramble System）是早期 DVD 使用的一种流密码。加密方式：M⊕Z=C。

Z（伪随机密钥流）的生成过程是先有一个40Bit的key/seed，然后分成16Bit和24Bit，然后每组加上1Bit变成17和25，去分别交给LFSR（线性反馈移位寄存器），跑八次，最后生成出来的16Bit通过zi​=(xi​+yi​+ci​)mod256，获得Z。

seed：大白话就是一个种子，用来长出Z的果实的，说是抛砖引玉也行。

LFSR（线性反馈移位寄存器）：就是一个转换的，例子：0001，第一和第四异或=0⊕1=1，获得1，然后移位变成1000，然后第一和第四异或=1⊕0=1，获得1，然后…，如果全是0000的话，就X和Y都变成全0了，所以需要每组加上1Bit的1防止全0

mod256：意思就是每256一循环，比如（300）mod256=1carry+44

总问题：攻击者不用完整破40Bit，因为css拆成两个了，所以可以破较少的16Bit，最多只需2的16次方，然后就知道xi，因为攻击者知道一部分M，所以zi通过异或即可已知，yi​=zi​−xi​−ci​(mod256)即可把24bit的也破解了，最后再检查这串到底是不是一个合法的 25-bit LFSR 能生成的序列，是的话16Bit的就找对了。

问题 1：密钥太短

40Bit现在来说太小了，但是由于历史局限性，在之前他的优势是快速便捷的，而且貌似之前难以破解

问题 2：用了线性的 LFSR

LFSR 本身结构非常简单，输出受固定线性递推约束。

问题 3：两个 LFSR 的组合方式太弱

只是yi​=zi​−xi​−ci​(mod256)，简单的带进位的模 256 加法，容易反向计算

Salsa20：生成密钥流的方式是Salsa20(k;r)=H(k,(r,0))∥H(k,(r,1))∥H(k,(r,2))∥…，也就是每个部分都是K+r（nonce）+σ（固定常量）→H(k,r,0）→64Byte密钥流块。对于Salsa20-256：

K(秘密密钥) = 256 bit = 32 byte

r(nonce，区分一次密钥流使用) = 64 bit = 8 byte

i (区分第几个输出块)= 64 bit = 8 byte

σ(标识/固定常量) = 16 byte

功能不同，所以Bit的数量也不同

state：把上面的原料按照 Salsa20 规定的顺序塞进一个 16×32-bit 的“拼盘”里，1 word=32 bit=4 byte，

长这样：

1
│ σ │ K │ K │ K │
2
│ K │ σ │ r │ r │
3
│ i │ i │ σ │ K │
4
│ K │ K │ K │ σ │

进行 20 轮由模 加法、XOR 和循环左移组成的 ARX 混合；也就是 10 个 double-round，再进行Y=F(X)+X(mod2的32次方)，说白了就是每小格的最终值和原始值一相加，再保留低 32 位，就获得了宝贵的64Byte密钥流块，然后再把每个密钥流块都和上，就是KS，然后KS异或M=C。

第六节补充：ChaCha20 对战 Salsa20#

相同点大白话：ChaCha 的设计是 Salsa 的优化版本。两者都是 ARX 流密码，状态由 16 个 32-bit word 组成，每个输出块是 64 byte。两者都支持按输出块并行计算：不同 counter 对应的 64-byte 密钥流块可以分别计算；实际能否利用多核取决于实现，单个块内部的轮运算仍然是串行的。两者也都支持随机访问密钥流块：知道 key、nonce 和 counter，就可以直接计算第 i 个 64-byte 密钥流块，不必先算出所有前序块。

不同点大白话：Salsa20 的矩阵较乱，是这样的：

1
│ σ │ K │ K │ K │
2
│ K │ σ │ r │ r │
3
│ i │ i │ σ │ K │
4
│ K │ K │ K │ σ │

Salsa20 中，r是 64-bit nonce，i是 64-bit block counter。

而 ChaCha20 的很整齐：

1
│ σ │ σ │ σ │ σ │
2
│ K │ K │ K │ K │
3
│ K │ K │ K │ K │
4
│ i │ r │ r │ r │

ChaCha20-Poly1305（RFC 8439），i 是 32-bit block counter，r 是 96-bit nonce。（这只适用于 RFC 8439 的 ChaCha20-Poly1305）

轮函数结构优化：Salsa20 采用「列轮 + 行轮」的交替模式，先对矩阵的每一列执行 quarter-round 运算，再对每一行执行运算，循环移位参数为 7、9、13、18。ChaCha20 改为「列轮 + 对角轮（diagonal round）」的交替模式，完成列运算后，转而对四组对角线方向的状态元素执行 quarter-round，运算顺序和移位参数都做了针对性调整，循环移位参数为 16、12、8、7。

抗密码分析能力：已有减轮密码分析研究表明，在所考察的单比特差分攻击模型下，Ghafoori 等对 Salsa20/8 和 ChaCha7.25 分别给出了约 2^241.62 和 2^254.011 的时间复杂度；但由于两者的减轮数不同，该结果主要用于说明具体攻击模型下的复杂度差异，不能直接等同于两种算法整体安全性的高低。[1] GHAFOORI N, MIYAJI A, ITO R, et al. PNB based differential cryptanalysis of Salsa20 and ChaCha[J]. IEICE Transactions on Information and Systems, 2023, E106-D(9): 1407-1422. DOI<10>.1587/transinf.2022ICP0015.

第七节：什么是分组密码加AES分组密码#

分组密码：有固定K，M和C长度固定且一样、确定性计算且可逆

PRF的安全定义：伪随机函数（PRF）：就是将x通过K映射到y上，不要求双射，伪随机置换（PRP）<就是将把集合x中的> x映射到 X中的某个 y，且固定 K 下是双射/置换、可逆。PRP 与 PRF 是两个不同的区分游戏；定义域足够大时，安全 PRP 可当安全 PRF 用。攻击者通过x自适应选择询问PRF和真随机函数，如果攻击者无法通过结果区分输出的是真随机函数还是伪随机函数，则认为PRF是安全的。

AES：有128bit、192bit、256bit，三种密钥大小，密钥越大，密码安全性越强同时也变慢。AES和chacha20两者都有类似 4×4的状态矩阵，AES：4×4 个 byte，状态 128 bit。ChaCha20：4×4个 32-bit word，状态 512 bit。AES加密的时候先是M 和第0个轮密钥进行异或，然后每格在进行字节替换（就是有个替换表，把每格原本的换成新的）行移位（第0行不动，第1行往左移一位，2行左二位，3行左三位）列混合（就是把每列的四个面团混到一块面坨子，揉完之后再分成四份放回去），然后再次异或第1个轮密钥，循环次数和k大小有关，但是最后一步都是第n个轮密钥异或当前状态收尾，最后一步没有列混合，所以一共是做n+1次异或和n-1次完整轮（一套字节替换加行移位加列混合）（n为AES总轮数）。

分组和分块的区别：

第八节：多密钥安全性·CPA安全#

CPA安全：如果对于所有PPT对手A，CPAadv[A,E] 的值都可忽略不计，我们就称密码E对选择明文攻击是语义安全(semantically secure against chosen plaintext attack)的，简称为CPA安全(CPA secure) 的。

CPA攻击游戏：在一局游戏里挑战者在K随机抽k（k是一局一换的，一局内k不能换）和秘密比特b(就是决定挑战者加密左边或者右边，说白了就是抛个硬币，0朝上就是左，1朝上就是右（纯假设），方便后续统计计算对手是蒙的还是真能知道谁是谁)，PPT对手自适应地反复提交等长消息（m1, m2），挑战者负责把它加密再给他，对手不知道给的是哪个，对手判断那个是M1或者M2，然后输出1Bit，算”输出 1”的概率在 b=0 与 b=1下的差。若对所有 PPT 对手这个差都可忽略，就叫 CPA 安全。

CPA安全和现实的联系：最开始疑惑就是凭啥挑战者要给他加密，但事实现实中很常见，比如对手给挑战者发一封邮件，挑战者把它加密并放在磁盘里面了，然后哪天磁盘被泄露/攻破了，在结果上相当于加密再还给他了（这种就是选择明文攻击）。为了保证CPA安全，一种常见的做法是把每次的加密过程都加上唯一的nonce，这样即使是同一个K加密同一个M，攻击者也不会知道那个是M1那个是M2。

第九节：消息认证码#

MAC：消息认证码是基于发送方和接收方之间共享密钥的消息完整性系统,I=(S,V)，S为签名算法，可以具有随机性或确定性，V是验证算法，具有确定性，S和V的调用都需要K，因为如果不用K的话，攻击者可以把要传输的消息m截下来，换成自己的C消息m’，然后再根据算法伪造一个tag，也是可以通过V的验证的。每当算法V对某个消息-标签对(m,t)输出accept时,我们就称t是m在密钥k下的有效标签,或者说(m,t)是k下的有效对。MAC是通过在消息m中增加tag的方式提供不可篡改性，但是不提供保密性，比如系统的文件是明文的，但是要防止篡改，广告是明文的，但是也要防止篡改。

安全的MAC：能够发动使用选择消息攻击的自适应的PPT攻击者也不能创造出一个存在性MAC伪造，此MAC就是安全的。

选择消息攻击：攻击者用自己的任意的M去让MAC请求标签，然后获得信息-标签对(m,t)。

存在性MAC伪造：在不管m的意义的情况下，只要攻击者在一个新的m上，伪造出了能通过V验证的tag。

学习资料与参考资源#

本文相关知识主要参考以下课程与学习资料：

1. Stanford《Cryptography I》——Coursera 官方课程
   由斯坦福大学提供、Dan Boneh 主讲的密码学课程，涵盖对称加密、伪随机函数、消息认证、选择明文攻击、选择密文攻击及公钥密码学等内容，是系统学习现代密码学基础的重要资源。

2. Stanford《密码学 | Cryptography 1》中英字幕课程（Bilibili）
   便于中文学习者跟随课程视频理解概念、攻击模型与安全性分析。涉及关键定义、公式或证明时，建议结合课程原始材料进行核对。

3. 《Graduate Applied Cryptography》中文译本（GitHub）
   Dan Boneh 与 Victor Shoup 合著的《A Graduate Course in Applied Cryptography》的中文翻译项目，可作为课程学习的延伸参考，用于进一步查阅密码学构造、安全定义及相关证明。阅读时应注意译本与英文原版的版本、章节及术语差异。

以上资源分别用于课程学习、辅助理解与延伸阅读。