CAN304 W4

zz-w / 2023-05-14 / 原文

CAN304 W4

The public-key revolution

对称加密 (symmetric cryptograph) 带来了一系列安全问题：

如何安全地共享密钥？(The key-distribution problem)
多个人如何共享密钥 (每两人一个？)(The key-management problem)？
假设两个没有先前关系的用户想要安全地通信，他们什么时候会共享密钥?（Lack of support for "open systems"）

非对称加密 (asymmetric cryptography)：一方生成一对密钥 - 公钥pk 和私钥 sk，公钥被广泛传播，私钥是保密的。

Key ideas:

Some problems exhibit asymmetry‒ Easy to compute, but hard to invert
Use this asymmetry to enable two parties to agree on a sharedsecret key using public discussion
一些问题表现出非对称性 - 易于计算，但难以反转 (invert)
利用这种不对称性，双方可以通过公开讨论就共享密钥达成一致

Factoring problem：计算两个数字的乘积很容易；但根据乘积分解数字很难
Discrete-logarithm problem: 离散对数问题

Fix cyclic group 𝐺 of order 𝑚, and generator 𝑔

Dlog problem in 𝐺:
Given 𝑔 and an element ℎ in 𝐺, find 𝑥 such that 𝑔^x= ℎ
Dlog assumption in 𝐺:
Solving the discrete log problem in 𝐺 is hard
Diffie-Hellman problems:
Fix group 𝐺 with generator 𝑔
- Computational Diffie-Hellman (CDH) problem:
  
  Given 𝑔, 𝑔^x, 𝑔^y, compute 𝑔^xy
- Decisional Diffie-Hellman (DDH) problem:
  
  Given 𝑔, 𝑔^x, 𝑔^y, distinguish the correct 𝑔^xy from a uniform element of 𝐺

Public-key encryption

Public-key encryption (PKE)

public-key encryption scheme 由三种算法组成：

Gen：key-generation algorithm，生成公钥 pk 和私钥 sk
Enc：根据输入 pk 和 message m，输出密文 c 的加密算法
Dec：根据输入 sk 和密文 c，输出 message m 或 ⊥ (error) 的解密算法

Hybrid encryption

使用对称加密对 m 进行加密，然后用非对称加密对密钥 k 进行加密。解密时先用私钥解密 k，再用 k 解密密文。(由于 m 会很长，直接用非对称加密计算量会很大)

Dlog-based PKE: ElGamal encryption

Dlog problem：给定 𝑔 和 group 𝐺 中的一个元素 ℎ，找到 x 使得 𝑔^x = h。

Gen
- 初始化 group 参数 G，q，g；选择 uniform $x \in Z_q$ (Z_q = {1, 2, ..., q-1})，计算 h = 𝑔^x
- Public key is ℎ, private key is 𝑥
Enc_pk(m), where $m \in G$
- 选择 uniform $y \in Z_q$
- The ciphertext is $ (𝑐_1, \ 𝑐_2) = (𝑔^y, \ ℎ^y ⋅ 𝑚)$
Dec_sk(c₁, c₂)
- 解密输出 $\frac{c_2} {c_1^x} =\frac{h^y*m} {g^{xy}} = \frac{g^{xy}*m} {g^{xy}} = m$

RSA encryption

Factoring problem

Chosen-plaintext attack (CPA) 选择明文攻击

攻击类型：Ciphertext-only attack -> Known-plaintext attack -> Chosen-plaintext attack -> Chosen-ciphertext attack，强度依次增加。

假如攻击者知道一些 plaintext-ciphertext pairs，例如 (m₁, c₁) 和 (m₂, c₂)。现在有一个密文 c₃，如果 $c_1 \sdot c_2 = c_3$，那么 $m_1 \sdot m_2 = m_3$。

注意：我们不是向普通RSA展示真正的CPA攻击；我们只是说明普通RSA没有CPA安全性！

因此，Plain RSA is not CPA-secure，不过这个问题可以通过 PKCS 解决。

PKCS: Public-Key Cryptography Standard (PKCS) 公钥加密标准(PKCS)

idea：add random padding
- 要加密 𝑚，随机选择一个 𝑟，把 r 添加到 m 里
- $c = [(r|m)^e mod N]$
Issues:
- No proof of CPA-security (unless 𝑚 is very short)
- Chosen-plaintext attacks known if 𝑟 is too short
- Chosen-ciphertext attacks known

Digital signature

Digital signature 和 MACs 的区别：

Public verifiability
- “任何人”都可以验证 signature，而只有密钥持有者才能验证 MAC 的 tag
Transferability
- 可以将 signature 转发给其他人
Non-repudiation
- 签名者不能（轻易地）否认签发的签名 (可以使用 pk 的公共副本验证签名)
- 而 MAC 无法提供此功能 (无法访问密钥，无法验证 tag)，而且无法确定是谁发出的签名 (有密钥的都可以发)

Signature schemes

签名方案由三种 PPT 算法（Gen、Sign、Vrfy）定义：

Gen：输入 1ⁿ (指定密钥长度)，输出 pk 和 sk
Sign：将私钥 sk 和 message $m \in \{0, 1\}^*$，输出 signature $\sigma$

\[\sigma \leftarrow Sign_{sk} (m) \]
Vrfy：输入公钥 pk，message m 和 signature $\sigma$，输出 0 或 1 (拒绝和接受)

Hash-and-sign paradigm

给定：

一个 signature scheme Π=(Gen, Sign, Vrfy) 来签名长度为 n 的短 message
Hash function $H: \{0,1\}^* \rightarrow \{0,1\}^n$

构建一个可以适用于任意长度 message 的 signature scheme Π‘ =(Gen’, Sign‘, Vrfy’)：

$Sign_{sk}' (m) = Sign_{sk}(H(m))$
$Vrfy_{pk}' (m, \sigma) = Vrfy_{pk}(H(m), \sigma)$

RSA-based signatures （基于大数因子分解）

Attacks

sign specific messages
- 假如给定 m=1，可以得到 $\sigma=1$，因为 $\sigma = [1^d mod N] = 1$ ，即当m=1时，不管d为何值，签名的值都为1。
sign “random” messages
- 选择随机的 $\sigma$，设置 $m = [\sigma ^e mod N]$ ，意思是即使我不能控制m的值，但是我得到了m的合法签名$\sigma$。在大量数据的情况下，我总能得到一部分有用的m的签名。
combine two signatures to obtain a third
- 签名 $\sigma_1,\ \sigma_2$ 是合法的签名，它们分别对应于 $m_1, \ m_2$
- 那么 $\sigma' = \sigma_1 \sigma_2 \ mod \ N$ 是合法的签名，它对应于 $m' = m_1 m_2 \ mod \ N$。因为 $(\sigma_1 \sigma_2)^e = \sigma_1^e \sigma_2^e = m_1 m_2 \ mod \ N$