数据安全与密码学基础期中学习报告

Lec1

什么是密码学？

密码学的英文是 cryptography，来源于希腊文中的隐藏和写；也就是说，密码学研究的是一种隐写术，目的是确保传输消息时的保密性

加密算法的语法

定义一个加密算法，至少要包含以下几个部分

1. 密钥生成函数 Gen() -> sk：随机的
2. 加密函数 Enc(sk, M) -> C：随机 / 确定的
3. 解密函数 Dec(sk, C) -> M：确定的

正确性

什么是正确性

形式化描述：解密密文一定可以得到原来的明文

$$\forall m\in M,Pr[Dec(Enc(sk, m))=m]=1$$

$$sk\leftarrow Gen()$$

安全性

攻击者的力量

1. 攻击者知道什么
2. 攻击者的计算能力

安全性是否依赖攻击者不知道加密算法

这个假设是非常不好、不合理的

因此现代密码学倾向于公开加密算法，让大家去攻击，寻找漏洞；假如都找不出漏洞，那么加密算法就是安全的

安全性依赖于攻击者无法攻破加密算法

现代密码学的想法，算法是完全公开的

现代密码学的基本原则：可证明安全 Provable Security

1. 安全定义
2. 数学假设
3. 规约算法：若给定的假设 X 是正确的，根据给定的定义，构造方案 Y 是安全的

在有安全定义的前提下，数学假设作为背书，规约算法进行绑定

Lec2

香农隐私 Shannon Privacy

攻击者无法获得先验信息以外的额外信息（1949，香农）

$$\forall t\in M,c\in C,Pr_{m\leftarrow D}[m=t]=Pr_{m\leftarrow D,sk\leftarrow Gen()}[m=t|Enc(sk,m)=c]$$

先验概率等于后验概率

完美隐私 Perfect Privacy

明文的分布是独立等可能的

$$\forall m_1,m_2\in M\forall c,Pr_{sk\leftarrow Gen()}[Enc(sk,m_1)=c]=Pr_{sk\leftarrow Gen()}[Enc(sk,m_2)=c]$$

香农隐私和完美隐私是等价的（证明略）

一次一密 One Time Pad

密码系统的组件

定义

$$M=\{0,1\}^n, K=\{0,1\}^n$$

$$sk=Gen()\in K$$

$$Enc(sk, m)=sk\oplus m$$

$$Dec(sk, c)=sk\oplus c$$

性质

算法是是完美安全的，但是有缺点：密钥太长

完美安全将安全性推到了极致，因此会牺牲效率和性能

完美隐私的局限性

若一个加密算法是完美安全的，则

$$|K|\ge|M|$$

Lec3

一次一密局限性过大，我们需要一个安全的，密钥短的加密算法；当然，为了提高性能，就要牺牲一定的安全性

计算安全

对攻击者的能力进行限制（如果攻击者的能力无限大，只有完美安全是安全的）

如何界定敌手

多项式时间 PPT 内解决问题

$$存在常数c，对任意问题X，图灵机M会在|X|^c时间内停下$$

我们只考虑允许多项式时间的敌手和确定性算法

算法设计

设计一个难题，作为数学假设

难题：一个多项式时间内无法解决的问题。也许有敌手可以解决，但是我们只考虑允许多项式时间的敌手，界定了敌手的范围。例如：停机问题，P=NP问题

使得 Enc 为简单的，Dec 为难的

即 $y=f(x)$ 简单，而 $x=f^{-1}(y)$难；被称为 One-Way Function

单向函数 One-Way Function

1. 易与计算

存在一个 PPT 算法 M 使得

$$M_f(x)=f(x)$$

2. 不易于反向求逆

$$\forall A\in PPT\exist negl,Pr_{x\leftarrow\{0,1\}^n}[A(f(x))=t:f(t)=f(x)]\le negl(n)$$

其中 n 为安全参数，negl 为一个大数的倒数，大在这里被定义为超多项式函数

超多项式：$f:\forall c\exist N,\forall n\ge N,f(n)\ge n^c$

弱化版本

$$\forall A\in PPT\exist poly,Pr_{x\leftarrow\{0,1\}^n}[A(f(x))=t:f(t)=f(x)]\le1-\frac{1}{poly}$$

保证不是无限接近于 1，但不一定无限接近于 0

Lec4

经过了上一讲的铺垫，现在考虑如何设计一个安全的，密钥短的加密算法

思路：将 sk 作为种子 seed，可以生成真正的密钥；即短字符串生成长字符串

Random Looking

由于原本的 sk 是一个真随机的字符串，需要让生成的长字符串“看上去像”真随机

不可能是真随机的，因为是短字符串生成的

1. 攻击者的时间
2. 问题规模

攻击者的时间越长，问题规模越大，越看上去像真随机的；这两者与前面提到的安全系数 n 类似

伪随机生成器 PRG

定义

$令 \{G_n\}_n:\{0,1\}^n\to \{0,1\}^{l(n)}，有$

1. $l(n)\gt n$
2. $\{X_n\}_n\approx \{Y_n\}_n；其中X_n为 G诱导出的分布，Y_n为\{0,1\}^n上的实分布$

长度扩展
保证安全：多项式时间内不可区分

安全游戏 / 区分器

挑战者 Ch，攻击者 A

1. Ch 告知 A：G 的运行原理和安全参数 n
2. Ch 任取：$x\in\{0,1\}^n,y\in\{0,1\}^{l(n)},b\in\{0,1\}$
   并当 b = 0 时，发送 G(x)；b = 1 时，发送 y 给 A
3. A 给出对 b 的猜测，猜对为 A 赢

A 疑似有 50% 概率赢

用下列函数衡量 A 的胜率，实际上可以衡量 G 的安全性

$$Adv(A)=Pr[\text{A wins}]-0.5$$

算法升级！

对 OTP 的升级

$$sk=Gen(1^n)\in \{0,1\}^n$$

$$Enc(sk, m)=G(sk)\oplus m$$

$$Dec(sk, c)=G(sk)\oplus c$$

同样可以用安全游戏衡量升级后的 OTP 的安全性（见下文）

流密码与窃听攻击

上述的加密算法一般被称为流密码（得名于比特流）

如果流密码的 G 是 PRG，那么该加密算法是窃听安全的

窃听攻击：敌手的能力较弱，只能窃听并观察到密文，没有其他能力

如果存在一个窃听攻击的敌手可以攻破加密算法，那么就可以利用这个敌手构造 R 消除伪随机性；但是伪随机性不可消除，因此该敌手不存在，证明如下

上课讲的安全游戏实际上就是具体化的区分器 D

Lec5

PRG 的扩展

定理：如果 PRG 能完成 1bit 的扩展，那么就能完成多项式 bit 的扩展

n + 1 $\to$ 2 * n

$$n_1=G(n)=n+b_1$$

$$n_2=G(n)=n+b_2$$

$$...$$

$$n_n=G(n)=n+b_n$$

$设G^\prime(x)=b_1+b_2+...+b_n$

则：$G^\prime $ 是 PRG $\lArr G $ 是 PRG

同理可以扩展到任意多项式

流密码的多次加密与安全性的加强

流密码如果使用 2+ 次，攻击者可以通过异或运算算出密钥异或后的值，这是我们不希望看到的

我们希望攻击者即使获取了多个密文也无法破译，因此我们对安全性的需求增加了

A 更加强大了

确定性算法无法满足需求

如果是一个确定性加密方式，则无法保证窃听攻击中的多次加密

因此我们要将其升级为随机算法

随机加密算法

定义

$$sk=KG(1^n)\in \{0,1\}^n$$

$$Enc(sk, m, r)=G(sk|| r)\oplus m,r$$

$$Dec(sk, c_1,c_2)=G(sk|| c_1)\oplus c_2$$

攻击者知道了一部分的密钥 r，因此很难规约到 PRG 的安全游戏

下面我们要考虑 r 被泄漏，sk 不泄漏的情况下（不泄漏无法解密），这个算法是否还是安全的；我们需要一个新的安全游戏来进行考量

假如我们有一个随机函数 F，就可以实现了

$|\{F\}|=2^{n*2^n}$，是一个非常大的数字，我们的算力不够，因此我们只能使用弱化的随机函数：伪随机函数

伪随机函数 PRF

PRG 是一个固定的函数（能够生成伪随机字符串的固定函数）；PRF 是一组函数的集合，或者说 PRF 是能够生成函数的函数

D 是一个多项式时间内的区分器

$$|Pr[D^{F_k(*)}(1^n)=1]-Pr[D^{f(*)}(1^n)=1]|\le negl(n)$$

无法在多项式时间内区分 PRF 生成的函数和纯随机函数，也就是：从 PRF 中选择的函数的分布与随机分布一样

Lec6

选择明文攻击 CPA

攻击者相对窃听攻击，有了新的力量：攻击者可以选择明文，通过加密算法进行加密得到相应的密文，得以尝试判断加密算法的一些特征以破解之

现实性

诚实方一定要为了攻击者加密他选择的明文吗？在现实世界中，诚实方很可能是被动的成为了攻击者的加密预言机；更近的例子是服务器收到的请求中，可能有恶意的，服务器很难分辨从而被动的成为了加密预言机

CPA 安全游戏

1. 运行 Gen 以生成密钥 sk
2. 敌手 A 可以访问预言机 Enc*()，生成 m0 和 m1 交给 Ch
3. Ch 随机选择 0 / 1，得到 b，通过 mb 计算出对应的密文给 A
4. 如果 A 猜对了 b，则 A 获胜；否则 A 失败

用下列函数衡量 A 的胜率，实际上可以衡量 CPA 的安全性

$$Adv(A)=Pr[\text{A wins}]-0.5$$

CPA 不可区分等价于

$$Adv(A)=Pr[PrivK^{cpa}_{A,\Pi}(n)=1]-0.5\le negl(n)$$

性质

单次加密的 CPA 安全即意味着多次加密的 CPA 安全（窃听安全不尽如此）；CPA 不可区分可以抵御多次加密

给定一个定长的 CPA 加密算法，可以构造一个 CPA 安全的任意长度的加密算法

构造 CPA 安全的加密算法

就像我们曾经用 PRG 抵御窃听攻击，我们可以用 PRF 抵御 CPA 攻击

基于 PRF 的 CPA 安全加密

1. $sk\leftarrow Gen(1^n)$
2. $sk,m,r\larr\{0,1\}^n.Enc(sk,m,r)=r+F_{sk}(r)\oplus m$
3. $Dec(sk,c_1,c_2)=F_{sk}(c_1)\oplus c_2$

直观的看上去确是安全的，因为密文 c1 + c2 对于敌手 A 来说是完全随机的
证明过程如下

Lec7

PRG 与 PRF 相互生成

PRF to PRG

$$G(x)=F_x(1)||...||F_x(l)$$

PRG to PRF

1. 通过 PRG 扩展一个指数级的字符串，再分块切割出 PRF（线性结构）

这种方法实际上是不好的，因为需要切割出第 k 个时，需要生成 (k - 1) 个垃圾块

2. 通过类似于生成树的方法生成一个 PRF（树状结构）

没有用的可以剪枝

高效的 CPA 安全的加密算法

原有的加密算法不够高效：密文至少是明文的长度的 2 倍；我们希望加密后的密文只比明文多 O(1) 的信息

PRF 的局限

PRF 是单向的，例如 $F_k(m)=c$ 是简单的，从 c 计算 m 是困难的；我们想要一个 c 到 m 也简单的算法，也就是一个置换

伪随机置换 PRP

$$F:\{0,1\}^*\times\{0,1\}^*\to\{0,1\}^*$$

同时在多项式时间里，可以计算 $F_k(x)$ 和 $F^{-1}_k(x)$

• PRP 一定是 PRF

如果 F 和一个随机置换是不可区分的，则 F 是一个强 PRP

在这里我们可以统一四个函数，下面四个函数是可以相互表示的
$OWF\lrArr PRG\lrArr PRF\lrArr PRP $

密码块链接模式 CBC-mode

类似于比特币区块链技术，但是比区块链早得多

将明文进行分块，第 i 块的加密结果作为第 (i + 1) 块的随机数 r，可以保证最后多出来的 r 是 O(1) 长的

在现实中并不使用前文所说的简单方法，而是将明文块置入 F，然而 PRF 是无法复原明文的，所以这里用的其实是 PRP

完整性

窃听攻击，CPA 攻击中的攻击者都是只能读的，假如攻击者可以篡改密文，我们就要考虑加密算法的完整性：我们可以识别攻击者对消息的修改而不是修复消息

消息鉴别码 MAC

通信双方先共享一个密钥 sk，当一方发送信息 m 时，将 sk 与 m 计算出 MAC t，将 m 和 t 一起发送；另一方接收到后，利用验证算法验证 m 是否被篡改

定义

1. $Gen(1^n)=sk;|sk|\ge n$
2. $Mac_{sk}( m)=t$
3. $b=Vrfy(m,t)$

$$\forall n\forall sk\larr Gen(1^n)\forall m,Vrfy(m,Mac_{sk}(m))=1$$

MAC 游戏

1. $Gen(1^n)=sk$
2. A 有权访问预言机 Mac，用 Q 表示 A 对预言机的询问的集合
3. A 获胜当且仅当 $Vrfy(m,t)=1,m\notin Q$

MAC是安全的，即在适应性选择消息攻击下，存在性不可伪造等价于

$$Pr[Mac-forge_{A,\Pi}(n)=1]\le negl(n)$$

MAC 的局限

MAC 无法抵御重放攻击（时间戳或序列号可以）