公钥加密_PKE

RSA 加密

• 密钥生成：$N=pq,ed\equiv 1(\mathrm{mod}\varphi (N))$。$pk=(N,e),sk=d$。
• 加密：$c=m^e(\mathrm{mod}N)$。
• 解密：$m=c^d(\mathrm{mod}N)$。
• Textbook RSA 的不安全性：
  • 确定性：相同的明文生成相同的密文 $\to$ 不满足 IND-CPA。
  • 同态性：$Enc(m_1)\cdot Enc(m_2)=Enc(m_1\cdot m_2)$ $\to$ 易受延展性攻击。
  • 共模攻击：如果多人共享 $N$ 但 $e,d$ 不同，可能导致攻击。
• 修复：必须使用 Padding（如 OAEP）引入随机性。

补充

• 教科书式 RSA (Textbook RSA)：$c=m^e(\mathrm{mod}N)$。
  • 弱点：确定性加密（不满足 IND-CPA），保留了乘法同态性（易受篡改）。
• 典型攻击：
  1. 小指数攻击 (Small e)：如果 $e=3$ 且同个消息发给 3 个不同用户，可用中国剩余定理 (CRT) 直接求立方根恢复明文。
  2. 共模攻击 (Common Modulus)：如果多用户共享 $N$ 但 $e,d$ 不同，已知同一消息的两个密文可恢复明文。
• RSA-OAEP：通过填充 (Padding) 引入随机性，并在随机预言机模型下被证明是 CCA 安全 的。

ElGamal 加密

• 基于：离散对数困难 (DDH)。
• 构造：$pk=(G,q,g,h=g^x),sk=x$。
  • 加密：选随机数 $r$，计算 $c_1=g^r,c_2=m\cdot h^r$。
  • 解密：$m=c_2/(c_1^x)$。
• 特性：天然是随机化的（因为 $r$），满足 IND-CPA。

补充

• 构造：
  • 公钥 $y=g^x$，私钥 $x$。
  • 加密：$c_1=g^r,c_2=m\cdot y^r$。
• 安全性：
  • 这是一个 随机化 的加密方案（因为 $r$）。
  • 安全性归约到 DDH (判定 Diffie-Hellman) 假设。
  • 延展性：具有同态性质 $Enc(m_1)\cdot Enc(m_2)=Enc(m_1\cdot m_2)$，因此 不是 CCA 安全 的。

混合加密 (Hybrid Encryption)

• KEM (密钥封装) + DEM (数据封装)。
• 用公钥加密（RSA/ElGamal）传输一个短的对称密钥 $k$。
• 用对称密钥 $k$（AES）加密长消息。
• 效率高且安全。