现代密码学（五）公钥密码

发表于 更新于 分类于 阅读次数：
本文字数： 1.6k

介绍公钥密码学。

公钥密码理论

公钥算法主要有三类

  • 密钥分配
  • 公钥加密
  • 签名算法

DH密钥交换

  • 选定素数p和本原元a
  • A选定\(x_A\)，计算\(y_A=a^{x_A}\bmod p\)$
  • B选定\(x_B\)，计算\(y_B=a^{x_B}\bmod p\)$
  • 公开\(y_A\)和\(y_B\)$
  • A计算\(K=y_B^{x_A}\bmod p\)$
  • B计算\(K=y_A^{x_B}\bmod p\)$

RSA

算法流程

  • 选择两个大素数p和q
  • 计算\(N=p·q\)$
  • 随机选择加密密钥e，满足\(gcd(e, \phi(N)) = 1,\ e < N\)$
  • 求解解密密钥d，满足\(e·d\equiv1\bmod \phi(N)\)$
  • 公开\((N, e)\)，保存\((p,q,d)\)$

原理如下 \[ C = M^e\bmod N \\ D = C^d= (M^e)^d\bmod N \\ D = M^{(1+k\phi(N))}= M\bmod N \] RSA实际上是一种单表代换 \[ RSA: \mathbb{Z/nZ} \rightarrow \mathbb{Z/nZ},\ n=pq \] RSA的安全性取决于计算\(\phi(N)\)的困难性，但分解模未必是攻击RSA的最佳方法。

RSA需要计算大指数模幂，可以用中国剩余定理CRT来加速。 \[ M_1 = M\bmod p = (C\bmod p)^{d\bmod(p-1)} \\ M_2 = M\bmod q = (C\bmod q)^{d\bmod(q-1)} \]

对于方程组 \[ \begin{cases} M = M_1\bmod p \\ M = M_2\bmod q \end{cases} \] 有唯一解 \[ M = (q·u·M_1 + p·u'·M_2)\bmod N \\ p·u\equiv1\bmod q,\ q·u'\equiv1\bmod p \]

Rabin公钥密码体制

有两个困难数学问题

  • 二次剩余问题：给定奇合数n和整数a，难以判断a是n的二次剩余。
  • 模n的平方根问题：在n的分解未知情况下，难以求解n的平方根。

Rabin体制利用求解平方根的困难性构造了一种安全公钥体制。

首先选定两个形如4k+3的素数p和q，以n=pq作为公钥。

加密过程 \[ C = M^2 \bmod n,\ 0 \leq M < n \] 解密首先计算 \[ \begin{align} M_1 &= C^{\frac{(p+1)}{4}} \bmod p \\ M_2 &= p - C^{\frac{(p+1)}{4}} \bmod p \\ M_3 &= C^{\frac{(q+1)}{4}} \bmod q \\ M_4 &= q - C^{\frac{(p+1)}{4}} \bmod q \end{align} \] 利用中国剩余定理，可以得到四个解，必有一个与M相同。

Rabin体制的安全性等价于大整数分解，但是对选择密文攻击不安全。 \[ x_1^2\equiv x_2^2\equiv0\bmod n \\ \iff (x_1-x_2)(x_1+x_2)\equiv0\bmod n \] 与RSA相比，Rabin只需要一次乘法运算，但解密时更困难。

El Gamal

基于离散对数，但增加了消息长度（2倍）。

首先选定大素数p和本原元g，计算 \[ y_B = g^{x_B}\bmod p \] 发送者选择随机数k，计算消息密钥 \[ K = y_B^k\bmod p,\ 0\leq k\leq p-1 \] 之后计算密文对 \[ \begin{align} C_1 &= g^k\bmod p \\ C_2 &= M\cdot K\bmod p \end{align} \] 解密时先计算密钥再计算明文 \[ \begin{align} K &= C_1^{x_B}\bmod p = (g^k)^{x_B}\bmod p \\ M &= C_2\cdot K^{-1}\bmod p \end{align} \]

对于公钥密码的攻击

可以对RSA发动弱参数攻击

  • 共模攻击
  • 低加密指数攻击

可以对Rabin发动选择密文攻击