数论与群论密码学-09-离散对数密码系统

离散对数密码系统

离散对数密码系统建立在以下原则上:

\(G\) 为某个抽象乘法群。
寻找一个 \(G\) 在计算机中的实现,其符合:
1. 有可高效快速计算 \(a^n\) 的算法。
2. 计算 \(log_a(b)\) 在技术上要复杂许多,并且不可在合理的时间完成。

以下给出数个离散对数密码系统。

Diffie-Hellman 密钥交换

严格来说,该系统并非一个密码系统。它仅为通信双方 \(A\), \(B\) 协商确立一个不可为第三方所知的密钥 1

后文记 \(g \in \mathbb{F}_p^\times\) 为一具有较高的阶 \(p\) 的元素。

通信协议如下:
1. \(A\) 随机选取一数 \(a\),计算 \(P_A = g^a\) 做为其公钥,并将其发送至 \(B\)
2. \(B\) 完成类似的步骤,称其公钥为 \(P_B\)
3. \(A\), \(B\) 分别计算 \(P_B^a = P_A^b = g^{ab} = S_{AB}\)。这便是 \(A\), \(B\) 所分享的密钥。

注意:
1. 若我们可以在 \(\mathbb{F}_p^\times\) 中求解以 \(g\) 为底的离散对数问题(DLP),则 \(S_{AB}\) 是可计算的。因为我们可分别由 \(P_A\), \(P_B\) 求得 \(a\), \(b\),而底数 \(g\) 也是公开的。
2. 所谓 Diffie-Hellman 问题(DHP)指的是,如上述从 \(g\), \(P_A\), \(P_B\) 中计算 \(S_{AB}\)
3. 根据 Diffie-Hellman 假设(DHA),DHP 不可在合理的时间内做出解答。
4. 有强烈的证据表明,求解 DHP 等价于求解 DLP。即:DHP 与 DLP 是一样难的。

Massey-Omura 密码系统

同 RSA 密码系统一样,Massey-Omura 密码系统建立的也是一个单向的信道。该系统的明文及密文空间皆为 \(m\in\mathbb{F}_p^\times = (\mathbb{Z}/p\mathbb{Z})^\times\).

以下为 Massey-Omura 密码系统的协议:

  1. \(A\) 选择满足 \(gcd(e_A, p-1) = 1\) 的数 \(e_A\),并计算符合 \(d_Ae_A \equiv 1 \pmod{p-1}\)\(d_A\).
  2. 类似地,\(B\) 选择/计算 \(e_B, d_B\).
    以上各数皆由 \(A\)\(B\) 所保密。
  3. \(A\) 发送至 \(B\)\(M := m^{e_A}\).
  4. \(B\) 发送至 \(A\)\(M' := \underbrace{(m^{e_A})^{e_B}}_{M^{e_B}}\).
  5. \(A\) 发送至 \(B\)\(M'' := M'^{d_A} = m^{e_b}\).
  6. \(B\) 计算 \((M'')^{d_B} = m\).

其中

\[ \begin{aligned} (M'')^{d_B} &= (M'^{d_A})^{d_B} \\ &= (m^{e_Ae_Bd_A})^{d_B} \\ &= (m^{e_B})^{d_B} \\ &= (m^{e_B})^{d_B} \\ &= m \end{aligned} \]

第二至三行的根据是:如果 \((e_Ad_A) = n \equiv 1 \pmod{p-1}\),那么在 \(\mathbb{F}_p^\times\)\(x^n = x\).

仿照我们在 RSA 密码系统中做的比喻,我们可以这么理解 Massey-Omura 密码系统:当 \(A\)\(B\) 发送信息时,\(A\) 先往信息上加一把锁,锁的钥匙只有 \(A\) 自己持有。 \(B\) 收到消息时,由于他并解不开 \(A\) 设下的锁,于是 \(B\) 往信息上加上自己的锁并把共有上了两把锁的信息发还给 \(A\)。此时 \(A\) 解开自己的锁后将信息再次发送给 \(B\)。这时的信息上只有 \(B\) 的锁了,而 \(B\) 可以解开自己设下的锁而得到信息。注意全过程中信息上至少有一把锁,保证了任何监听信道的第三方都无法解开信息。

注意:
1. 在 RSA 中,\(A\) 是被动接收方,例如银行,其公开其公钥并愿意接收任何人发送的信息。而在 Massey-Omura 中,\(A\) 是主动发信方,因此需要事先通过别的方法确认收信的 \(B\) 真的是 \(A\) 期望的送达对象。
2. DLP 应该对于 \((m, m^{e_A})\) 不可解。

ElGamal 密码系统

\(p\) 为素数,于是 \(\mathbb{F}_p^\times\) 形成一个域,并且有 \(g\in\mathbb{F}_p^\times\) 为一个有高阶的数。

以下为 ElGamal 密码系统的协议:
1. \(B\) 秘密地选择数 \(b\), \(0 < b < p-1\),并计算 \(g_B = g^b\)。于是 \(B\)\((p, g, g_B)\) 作为其公钥公开。
2. \(A\) 秘密地选择数 \(k\),并计算 \((M_1, M_2) := (g^k, mg_B^k)\),其中 \(m\) 为信息明文。 \(A\) 将该元组发送给 \(B\).
3. \(B\) 计算 \(m = M_2M_1^{-b}\)

其中负指数的定义为 \(x^{-k} := x^{ord(x)-k} = x^{n-k}\),于是有 \(g_B^km(g^k)^{-b} = g^{bk}mg^{-bk} = m\)

注意,有猜想认为破解 ElGamal 密码系统和求解 DLP 是一样困难的。

数字签名标准(Digital Signature Standard, DSS)

DSS 又称作 数字签名算法(Digital Signature Algorithm, DSA)

目标:为 \(A\)\(B\) 发送的消息 \(m\) 签名,使得 \(B\) 可以确认消息确实由 \(A\) 发出并且未被篡改。

向长度为 \(k\) 的消息 \(m\) 上附上长度为 \(l\) 的“指纹”,其中 \(l << k\).

函数 \(h: \Sigma^k \to \Sigma^l\) 被称为哈希函数,如果有:
0. 对于任何 \(x\in\Sigma^k\), \(h(x)\) 可以被轻易地计算。
1. \(k\) 具有碰撞抗性,即很难找到两个数 \(x_1, x_2, x1 \ne x_2\),使得 \(h(x_1) = h(x_2)\).
2. \(k\) 具有原像抗性,即给定 \(y\in\Sigma^l\),很难找到数 \(x\in\Sigma^k\),使得 \(h(x) = y\).

协议:
1. \(A\) 选择一个 160 比特的素数 \(q\) (使用随机数生成器和素数检测算法)
2. \(A\) 选择一个 512 至 1024 比特(\(512+64n, n\in[0, 8]\))的素数 \(p\) 使其满足 \(p \equiv 1 \pmod q\),因此有 \(q \mid p-1\).
3. \(A\) 选择阶为 \(q\) 的元素 \(g\in\mathbb{F}_p^\times\)。由于有 \(q \mid p-1 = \#\mathbb{F}_p^\times\),这样的元素一定存在。
方法为:随机生成数 \(g_0\) 并计算 \(g_0^{(p-1)/q} = g\)。若 \(g \ne 1\) 那么根据 P3 \(g\) 的阶为 \(ord(q)\),因为有 \((g_0^{\frac{p-1}{q}})^q = 1\).
4. \(A\) 选择随机数 \(a\) 使得 \(1 < a < q\),并计算 \(y = g^a\in\mathbb{F}_p^\times\)
5. \(A\)\((q, p, g, y)\) 作为其公钥公开。

签名协议:
\(A\) 要为消息 \(m\in\mathbb{F}_p^\times\) 签名,
1. \(A\) 将一公开的哈希函数应用于 \(m\): \(h = h(m) \in [1, q]\).
2. \(A\) 选择随机数 \(k \in [1, q]\) 并计算 \[ g_1 = g^k \bmod p\\ r = g_1 \bmod q \] 3. \(A\) 求解同余方程 \(sk \equiv h + ar \pmod q\) 得到 \(s \in [0, q]\),于是有 \(k = s^{-1}(h+ar) \pmod q\).
4. \(A\)\((r, g)\) 作为签名发送给 \(B\).

验证协议:
1. \(B\) 将同样的哈希函数应用于收到的信息 \(m'\) : \(h' = h(m') \in [1, q]\).
2. \(B\) 计算 \[ u_1 \equiv s^{-1}h' \pmod q\\ u_2 \equiv s^{-1} r \pmod q\\ g_1' = g^{u_1}y^{u_1} \bmod p \] 3. 若 \(g_1' \equiv r \pmod q\),那么签名是有效的。

注意,若确实有 \(m' = m\),应有 \(h' = h\)。那么 \[ u_1 \equiv s^{-1}h \pmod q\\ u_2 \equiv s^{-1}r \pmod q \] 于是有 \[ g_1' = g^{u_1}y^{u_2} \bmod p = g^{s^{-1}h}y^{s^{-1}r} = g^{s^{-1}h}g^{as^{-1}r} = g^{s^{-1}h + s^{-1}ra} = g^k\\ r \equiv g_1 \pmod q \equiv g_k \pmod q \equiv g_1' \pmod q \]

其中哈希函数的意义在于确保消息没有被篡改。注意由于哈希函数是公开的,其本身并不能作为签名。

注意,DSS 的优势在于,即使签名仅有 160 比特,其安全性取决于在 \(\mathbb{F}_p^\times\) (600 比特) 中求解 \(<g>\) 的离散对数的困难程度。


  1. 当然,早些时候我们提到过的,密钥交换系统与密码系统在本质上其实是一样的↩︎