\(1.\) 对称加密
\(Alice\) 给 \(Bob\) 发送信息,用同一个密钥进行解密
对称加密的优点在于加密速度快,难以破解
问题在于,\(Alice,\ Bob\) 在网络上传输密钥的过程不安全
另一方面,若 \(n\ party\) 需要互相传输信息,若两两之间需要一个密钥,那么需要设计 \(C_{n}^{2}\) 个密钥;如果共享一个密钥,只要这个密钥被截获,大家的信息交流都不安全
\(2.\) 非对称加密
\(Alice\) 生成自己的公钥和私钥
\(Bob\) 给 \(Alice\) 发消息,利用 \(Alice\) 的公钥进行加密
\(Alice\) 收到消息后用自己的私钥进行解密
同理,\(Bob\) 自己也会生成公钥和私钥,以便于其他人和自己进行通信
但是,非对称加密的缺陷在于加密大数据的速度慢
\(3.\) 混合加密
非对称加密 \(\rightarrow\) 加密密钥
对称加密 \(\rightarrow\) 加密消息
\(4.\) 数字签名
信息传输过程中,敌手 \(Eve\) 也可以用 \(Alice\) 的公钥发消息,也就是说,\(Alice\) 无法确认信息来自 \(Bob\) 还是 \(Eve\)
\(4.1\) 数字签名
解决方法是 \(Bob\) 给 \(Alice\) 发消息的同时附上自己的数字签名,\(Alice\) 只要验证数字签名是否来自 \(Bob\) 即可
具体来讲,私钥为个人独有,所以\(Bob\) 用私钥加密自己的信息,附在密文后面,\(Alice\) 用 \(Bob\) 的公钥验签,即私钥签名-公钥验签
鉴于非对称加密耗时较久,考虑用哈希函数计算消息的摘要,对摘要进行签名
验证时 \(Alice\) 只需要用 \(Bob\) 的公钥解密摘要,便可以验证消息确实来自 \(Bob\)
\(Alice\) 用 \(Bob\) 的私钥解密密文得到明文,再对明文哈希,判断明文哈希与摘要是否一致,便可以验证消息是否被篡改
但是 \(Eve\) 可以冒充 \(Bob\) 给 \(Alice\) 发送自己的公钥,也就是说,\(Alice\) 无法确认手里的公钥是否是 \(Bob\) 的公钥
\(4.2\) 数字证书
引入可信第三方 \(CA(Certificate\ Authority)\)
\(Bob\) 花钱向 \(CA\) 申请数字证书,\(CA\) 用自己的私钥对证书颁发机构、有效期、公钥、持有者等信息进行签名,并把这些信息封装成数字证书
数字证书可以理解为 \(Bob\) 的公钥的数字签名
\(Alice\) 安装 \(CA\) 的数字证书,用 \(CA\) 的公钥验签,便可以验证消息确实来自 \(Bob\),随后得到 \(Bob\) 的公钥
\(4.3\) 盲签名
盲签名 签名者不知道消息内容的前提下进行数字签名,有如下性质
- 不可抵赖
- 不可追踪
考虑信息持有者 \(B\) 希望让 \(C\) 签名,但不希望 \(C\) 知晓消息内容,进行如下操作
- \(B\) 盲化消息,发送给 \(C\)
- \(C\) 签名,发送给 \(B\)
- \(B\) 去盲化
由于签名存在,所以不可抵赖;由于去盲化的消息与盲化消息不同,所以签名者不可追踪
\(5.\ RSA\) 加密
\(RSA\) 基于大整数分解问题
\(5.1\) 生成公钥和私钥
选取互质的大素数 \(p,\ q\),计算 \(n = pq,\ \phi(n) = (p - 1)\cdot (q - 1)\)
选取与 \(\phi(n)\) 互质的整数 \(e\),计算 \(e\) 在模 \(\phi(n)\) 意义下的逆元 \(d\),即 \(ed\equiv 1\ (mod\ \phi(n))\)
将 \(e,\ n\) 作为公钥,\(d,\ p,\ q\) 作为私钥
\(5.2\) 加密过程
将消息 \(M\) 映射到 \(\mathbb{Z_{n}}\),并且利用公钥 \(e,\ n\) 加密为 \(C\equiv M^{e}\ (mod\ n)\)
\(5.3\) 解密过程
计算 \(M = C^{d}\ mod\ n\)
\(5.4\) 正确性
考虑条件
以及如下同余式
若 \((M,\ n) = 1\),由欧拉定理 \(M^{\phi(n)}\equiv 1\ (mod\ n)\) 知道,\(M^{ed}\equiv M^{ed\ mod\ \phi(n)}\equiv M\ (mod\ n)\)
若 \((M,\ n)\neq 1\),因为 \(n\) 只有两个素因子 \(p,\ q\),所以 \(M\) 形如 \(sp,\ tq\),其中 \(s < q,\ t < p\),这意味着 \((sp,\ q) = 1,\ (tq,\ p) = 1\),不妨设 \(M = sp\)
通过验证
可以根据中国剩余定理得到
事实上,根据费马小定理,以及 \(M = sp\) 的形式
所以
同理可证 \(M = tq\) 的形式
所以,\(RSA\) 的正确性得到证明
\(6.\ ElGamal\) 加密
\(ElGamal\) 基于循环群上的离散对数问题
\(6.1\) 密钥生成
\(Alice\) 选取生成元 \(g\),生成一个 \(q\) 阶循环群 \(G\)
\(Alice\) 从 \(\left\{1,\ 2,..,\ q - 1 \right\}\) 中随机选择一个 \(x\)
计算 \(h = g^x\)
选择 \(h,\ G,\ q,\ g\) 为公钥,\(x\) 为私钥
\(6.2\) 加密
\(Bob\) 从 \(\left\{1,\ 2,..,\ q - 1 \right\}\) 中随机选择一个 \(y\),计算 \(c_{1} = g^{y}\)
\(Bob\) 计算共享秘密 \(s = h^y\)
\(Bob\) 将消息 \(m\) 映射到 \(G\) 上元素 \(m'\),计算 \(c_{2} = m'\cdot s\)
\(Bob\) 将 \((c_{1},\ c_{2}) = (g^y,\ m'\cdot (g^{x})^{y})\) 发送给 \(Alice\)
\(6.3\) 解密
\(Alice\) 利用密钥 \(x\) 计算共享秘密 \(s = c_{1}^{x} = (g^{y})^x\),以及 \(s^{-1} = (g^{y})^{-x}\)
进而计算出明文消息 \(m' = s^{-1}\cdot m'\cdot (g^{x})^{y} = (g^{y})^{-x}\cdot m'\cdot (g^{x})^{y}\)
\(6.4\) 特性
非确定加密,加密的密文取决于随机数 \(y\)