数论与群论密码学-08-离散对数问题

上一章里我们讨论了基于素因数分解复杂度的 RSA 密码系统,同时也观察到了不良设计的密钥生成算法易受到的一些攻击。接下来我们将要讨论基于离散对数问题复杂度的一些密码系统,这一章首先讨论离散对数问题。

离散对数问题

\(b \in G = (\mathbb{Z}/m\mathbb{Z})^\times\),则记 \(<b> = \{b^n: n \in \mathbb{Z}\} = \{1, b, b^2, \cdots, b^{n-1}\}\),其中根据费马定理,有 \(b^n = 1\)

\(<b>\) 为群 \(G\) 中由 \(b\) 生成的循环子群。对于任意 \(y \in <b>\),称最小使得 \(b^n = y\) 的非负整数 \(n\) 为以 \(b\) 为底的 \(y\) 的离散对数,记为 \(n = DL_b(y)\)

离散对数问题即为给定 \(y \in <b>\), \(b \in G = (\mathbb{Z}/m\mathbb{Z})^\times\)\(DL_b(y)\).

注意求解该问题是十分困难的。

首先,称 \(<b>\) 中所有元素及其离散对数的表格为以 \(b\) 为底的对数表。显然地,若我们做出对数表,即可解离散对数问题。

然而,我们应注意到以 \(b\) 为底的对数表——等价地——循环子群 \(<b>\) 的大小。

\(b \in G = (\mathbb{Z}/m\mathbb{Z})^\times\) 的阶为使得 \(b^n = 1\) 的最小整数 \(n \ge 1\),记作 \(|b|\)\(ord(b)\).

我们将在更一般的群代数结构中表述离散对数问题,并且观察到 \((\mathbb{Z}/m\mathbb{Z})^\times\) 是一个群。

若集合 \(G\) 上有二元运算 \(\cdot\),其满足

  1. \(\cdot\) 有结合性,即 \(x \cdot (y \cdot z) = (x \cdot y) \cdot z\);

  2. \(\cdot\) 有单位元(幺元),即存在 \(e \in G\),使得对于任何元素 \(x \in G\),皆有 \(e \cdot x = x \cdot e = x\)。也记此幺元为 \(e_G, 1_G, 1\).

    某些群论文献会记此幺元为 \(0\)。由于其使用加法表示群的二元运算,因此借鉴整数的加法而使用 \(0\) 表示幺元是个自然的选择。尤其当该种文献随后引入另一以乘法表示的二元运算时,需要记其幺元为 \(1\).

  3. \(G\) 中每一元素都有唯一 \(\cdot\) 下的逆元,即 \(\forall x \in G, !\exists y \in G: xy = yx = 1\)。我们记 \(y\)\(x^{-1}\).

群元素的阶

\(G\) 为群,\(x \in G\),则定义 \(ord(x) = min\{n \ge 1: x^n = 1\} \in \mathbb{N} \cup \{\infty\}\),称之为 \(x\) 的阶。

循环群(循环子群)

\(G\) 为有限基的群,那么每个 \(b \in G\) 都有有限的阶(\(ord(b) \ne \infty\))。并且,若 \(<b> = \{b^k: k \in \mathbb{Z}\}\)\(b\) 生成的循环子群,那么有 \(<b> = \{b^0, b^1, \cdots, b^{n-1}\}\),其中 \(n = ord(b)\) 并且前记元素相异。因此 \(\big| <b> \big| = n = ord(b)\)

因此,若 \(G = (\mathbb{Z}/m\mathbb{Z})^\times\),那么对于任何 \(b \in G\),其对数表的大小为 \(ord(b)\).

\(b \in G\),由于 \(G\) 为群而对乘法封闭,则 \(b^0, b^1, \cdots b^n, \cdots \in G\)。由于 \(G\) 有限,前记元素必定有重复。因此对于某些 \(0 \le k < n\),有 \(b^n = b^k\)。由于 \(G\) 可逆(并记 \((b^k)^{-1}\)\(b^{-k}\)),有

\[ b^n b^{-k} = b^k b^{-k}\\ b^{n-k} = 1 \]

因此 \(ord(b) \le n-k\) 且有限。

显然有 \(S = \{b^0, b^1, \cdots b^{n-1}\} \subseteq <b>\)。为了证明另一个方向的包含关系,设 \(b^k \in <b>, k \in \mathbb{Z}\)。记 \(k = qn+r, 0 \le r < n\),其中 \(n = ord(b)\)。因此 \(b^n = 1\),于是有

\[ b^k = b^{qn+r} = b^{qn}b^r = (b^n)^qb^r = 1^qb^r = b^r \in S = \{b^0, b^1, \cdots, b^{n-1}\}\]

因此有 \(<b> \subseteq S\).

最后,证明 \(b^0, b^1, \cdots, b^{n-1}\) 相异。如果此不为真,则存在 \(0 \le m < k \le n-1\) 使得 \(b^m = b^k\). 于是有

\[ b^mb^{-m} = b^kb^{-m}\\ 1 = b^{k-m} \]

然而有 \(1 \le k-m < n\),与 \(n\) 的最小性相矛盾,因此有 \(S\) 的元素两两相异。

那么给定 \(b \in G\),其阶的大小可能是什么?

阶的基本性质

\(G\) 为基有限的阿贝尔群, \(x, y \in G\), \(n, m \in \mathbb{Z}\)。有
P0. \(ord(x) \le \infty\)
P1. \(x^n = 1 \iff ord(x) \mid n\)
P1'. \(x^n = x^m \iff n \equiv m \pmod{ord(x)}\)
P2. \(ord(x^n) = \frac{d}{(n, d)}\),其中 \(d = ord(x)\), \((n, d) = gcd(n, d)\)
P3. \(ord(x) \mid \#G\)
P4. \(ord(xy) \mid lcm(ord(x), ord(y))\)。更多地,当 \(gcd(ord(x), ord(y)) = 1\) 时,两式相等。
P5. 若 \(G = G_1 \times \cdots \times G_r\) 是一个乘积群,则 \(ord((x_1, \cdots, x_r)) = lem(ord(x_1), \cdots, ord(x_r))\)

以上除 P4 以外的所有性质即使当 \(G\) 为非阿贝尔群时都成立。

\(\big| G \big| = n\),则对于所有 \(x \in G\) 皆有 \(x^n = 1\)

根据 P3,有 \(ord(x) \mid n\)。根据 P1 有 \(x^n = 1\).

\((\mathbb{Z}/11\mathbb{Z})^\times\)\(b = 2\) 的对数表的大小

由于对于任何 \(b \in G = (\mathbb{Z}/11\mathbb{Z})^\times = \{1, \cdots, 10\}\)\(ord(b) \mid 10\),因此 \(ord(b) \in \{1, 2, 5, 10\}\).

于是根据

\[ b^2 \equiv 4 \not \equiv 1 \pmod{11} \implies ord(b) \ne 2, 1\\ b^5 \equiv 32 \equiv 10 \not \equiv 1 \pmod{11} \implies ord(b) \ne 5 \]

\(ord(b) = 10\)。因此 \(b\) 的对数表的大小是 10.

更多地,由于 \(\big| G \big| = 10 = ord(b) \stackrel{\text{Thm1}}{=} \big| <b> \big|\),因此有 \(G = <b>\).

这样一来,群 \(G\) 中的任何元素皆可表示为 \(b^n\), \(0 \le n < 11\)。于是可以根据 P2 求出任意元素的阶。列如,有 \(8 = 2^3 = b^3\),则 \(ord(8) = \frac{10}{(3, 10)} = 10\).

\(G = (\mathbb{Z}/m\mathbb{Z})^\times\)\(m\) 为合数,我们可以利用 P5 轻松地计算 \(G\) 中各元素的阶。

\((\mathbb{Z}/15\mathbb{Z})^\times\)\(b = 7\) 的对数表的大小

根据中国剩余定理第一版,有

\[ \psi : (\mathbb{Z}/15\mathbb{Z})^\times \xrightarrow{\sim} (\mathbb{Z}/3\mathbb{Z})^\times \times (\mathbb{Z}/5\mathbb{Z})^\times\\ \begin{aligned} \psi(7 \bmod 15) &= ((7 \bmod 3), (7 \bmod 5))\\ &= (1, 2) \end{aligned} \]

因此

\[ \begin{aligned} ord(7 \bmod 15) &= ord(\psi(7))\\ &= ord((1, 2))\\ &\stackrel{\text{P5}}{=} lam(\underbrace{ord(1 \bmod 3)}_{=1}, \underbrace{ord(2 \bmod 5)}_{=4})\\ &= 4 \end{aligned} \]

阶的基本性质的证明

给定 \(G\) 为一有限群

  • P0. \(ord(x) < \infty\) 为定理 1 的直接推论。

  • P1. \(x^n = 1 \iff ord(x) \mid n\)

    (\(\Leftarrow\)) 若 \(ord(x) \mid n\),则有 \(n = k \cdot ord(x), k\in\mathbb{Z}\)。那么 \(x^n = x^{k \cdot ord(x)} = (x^{ord(x)})^k = 1^k = 1\).

    (\(\Rightarrow\)) 若 \(x^n = 1\),则记 \(n = qd + r, 0 \le r < d\),其中 \(d = ord(x)\), 那么有

    \[ \begin{aligned} 1 = x^n = x^{qd + r} &= x^{qd} \cdot x^r\\ &= (x^d)^q \cdot x^r\\&= 1^q \cdot x^r\\ 1 &= x^r \end{aligned} \]

    根据 \(d\) 的最小性,有 \(r = 0\).

    于是有 \(n = qd\),则 \(ord(x) d \mid n\).

  • P1'. \(x^n = x^m \iff n \equiv m \pmod{ord(x)}\)

    \(d = ord(x)\)。有

    \[ \begin{aligned} x^n = x^m &\iff x^{n-m} = x^{m-m} = 1\\ &\stackrel{\text{P1}}{\iff} d \mid n-m\\ &\iff n \equiv m \pmod d \end{aligned} \]

  • P2. \(ord(x^n) = \frac{d}{(n, d)}\),其中 \(d = ord(x)\), \((n, d) = gcd(n, d)\)

    首先注意到由于 \(gcd(d, n) \mid n\),有 \(\frac{n}{(d, n)}\in\mathbb{Z}\)。于是

    \[(x^n)^{\frac{d}{(d, n)}} = x^{\frac{n \cdot d}{(d, n)}} = (x^d)^{\frac{n}{(d, n)}} = 1^{\frac{n}{(d, n)}} = 1\]

    因此根据 P1 有 \(d' = ord(x^n) \mid \frac{d}{(d, n)} = k\).

    特别地,有 \(d' \le k\).

    接下来证明 \(d' \ge k\).

    考虑 \(x^{d'n} = (x^n)^{d'} = 1\),因此在 \(x\) 上使用 P1,有 \[ d \mid d'n\\ \frac{d}{(d, n)} \mid \frac{d'n}{(d, n)} \]

    因为 \(gcd(\frac{d}{(d, n)}, \frac{n}{(d, n)}) = 1\),根据欧几里得定理有 \(k = \frac{d}{(d, n)} \mid d'\)。于是有 \(k \le d'\).

    于是有 \(k = d'\).

  • P3. \(ord(x) \mid \#G\)

    这里我们只给出 \(G\) 为交换群时的证明。

    \(G = \{x_1, \cdots, x_n\}\),其中 \(n = \#G\). 设 \(x \in G\),那么有 \(\{xx_1, \cdots, xx_n\} = G\)。于是有 \[ \begin{aligned} x_0 = x_1 \cdot\ldots\cdot x_n &= (xx_1)\cdots(xx_n)\\ &\text{$G$ 为阿贝尔群}\\ &= x^n (x_1 \cdot\ldots\cdot x_n)\\ &= x^nx_0 \end{aligned} \]

    因此上式两边同乘 \(x_0^{-1}\),可得 \(1 = x^n\)。根据 P1 于是有 \(ord(x) \mid n\).

  • P4. \(ord(x_1x_2) \mid lcm(ord(x_1), ord(x_2))\)。更多地,当 \(gcd(ord(x_1), ord(x_2)) = 1\) 时,两式相等。

    该性质仅在 \(G\) 为交换群时成立。

    由于 \(G\) 是交换群,有 \((x_1x_2)^n = x_1^nx_2^n, n \in \mathbb{Z}\).

    因此设 \(d_i = ord(x_i), \lambda = lcm(d_1, d_2)\). 于是有 \(d_{\{1, 2\}} \mid \lambda\).

    根据 P1 有 \(x_i^\lambda = 1\),因此 \((x_1x_2)^\lambda = x_1^\lambda x_2^\lambda = 1\).

    根据 P1 有 \(ord(x_1x_2) \mid \lambda\),因此第一个断言得证。

    若有 \(gcd(d_1, d_2) = 1\),则 \((x_1x_2)^{d_1} = x_1^{d_1}x_2^{d^1} = x_2^{d_1}\)

    根据 P2 有 \(ord(x_2^{d_1}) = \frac{d_2}{(d_1, d_2)} = d_2\),因此 \(ord((x_1x_2)^{d_1}) = d_2\)

    根据 P2 有 \(d_2 \mid ord(x_1x_2)\)。类似地,有 \(ord((x_1x_2)^{d_2}) = d_1\)\(d_1 \mid ord(x_1x_2)\)

    于是 \(\lambda = lcm(d_1, d_2) \mid (ord(x_1x_2))\)

    而前证 \(ord(x_1x_2) \mid \lambda\),因此 \(ord(x_1x_2) = lcm(ord(x_1), ord(x_2))\)

  • P5. 若 \(G = G_1 \times \cdots \times G_r\) 是一个乘积群,则 \(ord((x_1, \cdots, x_r)) = lem(ord(x_1), \cdots, ord(x_r))\)

    根据群 \(G\) 中乘法的定义,对于任何 \(n \in \mathbb{Z}\),有 \((x_1, \cdots, x_r)^n = (x_1^n, \cdots, x_r^n)\)

    因此有

    \[ \begin{aligned} (x_1, \cdots, x_r)^n = 1 &\iff x_{\{1, \cdots, r\}}^n = 1\\ &\stackrel{\text{P1}}{\iff} ord(x_{\{1, \cdots, r\}}) \mid n\\ &\iff lcm(ord(x_1), \cdots, ord(x_r)) \mid n \end{aligned} \]

    那么满足 \((x_1, \cdots, x_r)^n = 1\) 的最小的正整数 \(n = lcm(ord(x_1), \cdots, ord(x_r))\),因此 \(ord((x_1, \cdots, x_r)) = lcm(ord(x_1), \cdots, ord(x_r))\).

对数表的上限(阶的上限)

那么,对于任意 \(b \in (\mathbb{Z}/m\mathbb{Z})^\times\),以 \(b\) 为底的对数表,等价地, \(ord(b)\) 的上限几何?目前我们仅知道, \(ord(b) \mid \phi(m)\).

\(G\) 被称为循环群,若 \(\exists x \in G, G = <x>\)。由于 \(G\) 中任意元素皆可表达为这样的 \(x\) 的次方,我们称这样的 \(x\) 称为 \(G\) 的生成元。

注意:
1. 若 \(G\) 为有限群且 \(x \in G\),那么有 \[G = <x> \iff \big| G \big| = \big| <x> \big| \stackrel{\text{Thm1}}{=} ord(x)\] 2. 若 \(G\)\(n\) 阶循环群,那么 \(G\)\(\phi(n)\) 个生成元。

\(G = <x>\),则 \[ \begin{aligned} G &\stackrel{\text{Thm1}}{=} \{1, x, \cdots, x^{n-1}\}\\ &= \{x^k : 0 \le k \le m-1\} \end{aligned} \]

那么 \(x\) 是生成元 \(\stackrel{\text{上注1}}{\iff} ord(x^k) = \big| G \big|\).

根据 P2, \(ord(x^k) = \frac{n}{(k, n)} = 1 \iff gcd(k , n) = 1\).

因此,\(G\) 的生成元的集合为 \(\{ x^k : 0 \le k \le m-1, gcd(m, k) = 1\}\),且生成元的数量为 \(\phi(n)\).

\(p\) 为素数,那么 \((\mathbb{Z}/p\mathbb{Z})^\times\) 是一个循环群,并且有 \(\phi(p-1)\) 个生成元。

该定理的证明使用了计数的论证方法,因此不是建设性的。另外其也使用了当且仅当 \(p\) 为素数时 \(\mathbb{F}_p := \mathbb{Z}/p\mathbb{Z}\) 为一个域的性质(加法乘法皆有逆元)。

\(p\) 为素数,那么 \((\mathbb{Z}/p\mathbb{Z})^\times\) 中有阶为 \(n\) 的元素,当且仅当 \(n \mid p-1\).

(\(\Leftarrow\)): 若 \(ord(x) = n\),则根据 P3 有 \(n \mid \#(\mathbb{Z}/p\mathbb{Z})^\times = \phi(p) = p-1\).

(\(\Rightarrow\)): 若 \(n \mid p-1\),则 $ 。根据定理 3,有 \(\exists x_0 \in (\mathbb{Z}/p\mathbb{Z})^\times, ord(x_0) = p-1\)。那么 \(x = x_0^{\frac{p-1}{n}}\) 的阶为 \(n\):

\[ord(x^{\frac{p-1}{n}}) = \frac{p-1}{\frac{p-1}{n}, p-1)} = \frac{p-1}{\frac{p-1}{n}} = n\]

注意,该从理给出了关于当 \(m=p\) 为素数时对数表大小的问题的解答。当 \(m\) 不为素数的情况比较复杂,然而我们并不需要。