Message Auth. Codes

MAC

MAC（消息验证码）是一对算法，包含一个签名算法和一个验证算法 I=(S,V)，定义在一个密钥空间、一个信息空间、一个标签空间上 (K,M,T)，签名算法 S(k,m) 会输出标签空间 T 中的一个标签 tag，验证算法 V(k,m,tag) 取密钥 k ，信息 m ，标签 tag，输出 yes 或 no。

分组密码：见《【DanBoneh】Block Ciphers》分组密码。

设计分组密码的两种基本技术：为了抵抗攻击者对密码系统的统计分析，香农提出混乱和扩散。

随机序列：

性质：不能可靠重复产生（用完全相同的输入操作两次，得到两个不相关的序列）

数学解释：概率服从均匀分布（①产生每个比特概率为 1/2 ②任意两个比特统计上相互独立）

计算机不能产生真正的随机序列，其本身只能产生伪随机序列。相同计算环境下，对于相同输入，计算机只能产生相同的输出。

电子密码本（ECB）不是语义安全的，永远不应被用来加密长于一个分组的信息。

分组密码：由两部分组成，加密算法E 和 解密算法D，它的输入和输出具有严格相同的位数。

3DES：分组大小为 64 位，使用 168 位长的密钥。n = 64 bits，k = 168 bits。

AES：n = 128 bits，k = 128，192，256 bits。密钥越长，密码工作速度越慢，越安全。

在流密码中，密钥不是完全随机的，而是一种伪随机密钥。

伪随机数发生器（PRG）：是一个本身没有随机性的完全确定的函数 G ，取一个种子为输入（种子具有随机性），用 {0,1}^s 表示所有长度为 s 的字符串，{0,1}^s 叫做种子空间，将 s 位种子映射到一个长得多的字符串 {0,1}ⁿ ，G：{0,1}^s→{0,1}ⁿ，n>>s。种子可能只有128位，但能扩展成一个长得多的字符串。

以种子为私钥 k ，使用发生器将种子扩张成长得多看起来随机的伪随机序列 G(k) ，将伪随机序列和明文异或，得到密文。c = E(K,m) = m⊕G(k)；m = D(K,c) = c⊕G(k)。

流密码是安全的，安全性依赖于使用的发生器，但其密钥比明文短得多，不是完美安全的。

密码由加密算法 E（经常是一个随机算法） 和解密算法 D（是确定算法） 组成。定义为一个三元组 （K, M, E），全体可能的密钥（密钥空间）记为 K ，全体可能的明文空间记为 M ，全体可能的密文空间记为 E。E：K×M→E ；D：K×E→M。

一致性方程：∀m∈M，k∈K，D(k,E(k,m)) = m。

Vernam密码（一次性密码本OTP）：它的明文空间与其密文空间一样，是全体 n 位二进制字符串的集合，M=E={0,1}ⁿ，K={0,1}ⁿ，密钥key=(与明文等长的随机字符串)。

c: = E(k,m) = k⊕m；m: = D(k,c) = k⊕c。

D(k,E(k,m)) = D(k,k⊕m) = k⊕k⊕m = m。

TLS（安全传输层协议）：由两部分组成。第一部分为握手协议（Handshake），Alice与Bob互相交谈，在握手的最后，双方分享一个密钥，Alice与Bob都知道这个密钥，但攻击者不知道会话密钥K，运用了公钥密码技术。第二部分为记录协议（Record），双方共享密钥时，如何使用密钥加以保护通信数据。

对称加密：以分组的形式保护流量的技术。在对称加密系统中，只有通信双方知道密钥K，他们使用加密算法 E 和解密算法 D 进行通信加密。加密算法以原信息和密钥为输入，产生密文；解密算法以密文和密钥为输入，输出原信息。算法是公开的，密钥是保密的。很多私有的算法一旦被逆向工程很容易破解。

一次密钥（one time key）每个密钥只加密一个信息。

标准符号

对于消息M（不管是明文还是密文）、密码算法A（不管它代表加密还是解密）、密钥K（不管它是加密密钥还是解密密钥），我们可以用M'=A(K,M)表示一个密码变换。

在对称密码体制种，我们可以认为K’=K；在公钥密码体制中，K’表示K的秘密部分或与K相匹配的部分。密文习惯记为${M}_K$。

用符号${M}_K$表示的完善加密

1. 不用密钥K（在对称密码体制中），或者不用与K相匹配的私钥（在公钥密码体制中），密文${M}_K$不提供任何求解明文消息M的密码分析方法。
2. 密文${M}_K$也许还有一些关于明文消息M的已知信息，不提供任何求解密钥K（在对称密码体制中）或与K相匹配的私钥（在公钥密码体制中）的密码分析方法。
3. （用于消息认证服务）如果没有密钥K，即使知道明文M，要想更改${M}_K$而不被接收者在解密阶段发现是不可能的。

具有这两个性质的完善加密是对现实世界中存在的加密算法的理想化。完善加密并不能防止协议含有安全缺陷。