密码学原理
密码学原理
南京大学2025-2026秋季课程
参考教材：现代密码学：原理和协议 (乔纳森·卡茨 (Jonathan Katz) etc.)
第一章 古典密码学概述
密码学形式化定义的一些概念如密钥空间，明文空间，密文空间，密钥生成函数等，古典密码如凯撒密码的密钥空间极小，部分变种有极大的密钥空间，但是破译方案仍然存在，书中作者认为古典密码学建立在“设计方案，破解方案”的无聊循环中。
第二章 完善保密加密
定义：（来自克劳德.香农）
$$
Pr(M=m|C=c)=Pr(M=m)
$$
作为敌方截获密文之后并不能获得任何与明文的概率分布相关的信息，
换句话说：你看到了密文，但是你不能根据密文进一步缩小它对应的明文空间！
等价定义：
$$
Pr(C=c|M=m)=Pr(C=c)
$$
完美不可区分性：
$$
Pr(C=c|M=m_{0})=Pr(C=c|M=m_{1})
$$
一次一密
对称密钥密码学
3.1 计算安全
本章引入概率，渐进分析等概念，目的就是：前一章介绍的完善保密加密是理论不可攻破，对密钥空间的要求过高，因此实际生活中用的都是满足计算安全的加密方案，也就是在一个很长的时间内，敌手能够以极低的概率攻破，一个方案是$(t,\epsilon)$的当且仅当它在最多$t$时间内最多以$\epsilon$概率被攻破，在分析时，敌手破译的运行时间是安全参数$n$的多项式函数，攻破概率是该多项式函数的倒数，在这种情况下，该计算安全加密方案是可行的。
可忽略性：函数$f(n)$是可忽略的，当且仅当对于所有多项式$p(n)$而言，存在一个整数$N$,当$n>N$时，$f(n)<\frac{1}{p(n)}$成立。
3.1.3 规约证明
简单解释一下：规约证明的发明是基于很多公钥加密算法的核心数学原理都是一些解决数学难问题的，比如$RSA$加密算法是基于大素数分解的问题，那么如果有朝一日大素数分解的难题被解决了，那么$RSA$公钥加密算法也就不安全了。
3.2 定义计算安全的加密
安全的基本定义
*定义的属性
3.3 伪随机性
如何验证遵循某种分布的字符串是伪随机的？当且仅当，任何多项式时间内的算法无法区分它与一个真正的随机字符串，但是这个伪随机字符串实际上是由确定性的算法生成的。
伪随机字符串发生器：接受一个真正随机的种子，然后对其进行扩展
3.4 构造安全加密方案
下面使用伪随机发生器构造一个类似一次一密的加密方案（其实就是在选择密钥$k$的时候，并不直接随机生成一个长度与明文相同的，而是选择一个长度较短的密钥$k$，然后使用伪随机发生器将其补充为长度与明文相同后与明文做异或得到密文）。
如果在这个过程中使用的是伪随机发生器，那么这个加密方案是不可区分的。
证明：（使用规约，加入存在一个算法$A^{‘}$，作为攻击者，能够区分出一个密钥是真的随机还是由伪随机发生器生成，这种优势是不可忽略的，那么上面的伪随机发生器的假设就不成立）
3.4.3 流密码和多个加密
流密码指：生成变长伪随机串，从而构造加密方案的方法
窃听者存在多次不可区分加密：在单次加密的情况下将消息变成消息向量，单次加密安全不等于多次加密安全。
定理：如果一个加密方案$(Gen,Enc,Dec)$中加密方案是密钥和明文消息的确认定性函数，则这个加密方案不具备窃听者存在多次加密不可区分性。
