【浅谈系列】Hill cipher 的密钥空间

3 minute read

Published:

当你学习古典密码时,有考虑过 Hill cipher 的密钥空间大小吗?

由于五月回校毕设答辩,答辩完就和同学到处玩,然后暑假沉迷 Steam 加上考驾照,于是博客一直未更新,今年的 CryptoCTF 也忘了报名,后悔莫及

研一开学后发现碎片时间较多,鲜少有完整的闲暇时间,因此博客迟迟未更。中秋国庆假期国科大离京有诸多限制,只能呆在学校及附近,终于有空更新博客了。

本文来自应用密码学第一次作业里的一题。Hill cipher 虽说作为古典密码并没有什么安全性,但它的密钥空间有多大,有多少人在学习时考虑过这个问题呢?

仔细想来我当初学习 Hill cipher 时也并没有在意,只是将其当作一个无趣而没用的古典密码,看了一眼就跳过了。林东岱老师布置这道题作为第一次作业,我觉得是很妙的。

0. 参考资料

1. 问题阐述

Hill cipher 是一类古典密码,基本思想是将 $t$ 个明文字母通过线性变换转换为 $t$ 个密文字母:

\[\begin{align} & M = m_1 m_2 ... m_t \\ & E_k(M) = c_1 c_2 ... c_t \\ & c_1 = k_{11}m_1 + ... + k_{1t}m_t \\ & c_2 = k_{21}m_1 + ... + k_{2t}m_t \\ & ...... \\ & c_t = k_{t1}m_1 + ... + k_{tt}m_t \end{align}\]

因此对于长度为 $t$ 的明文,加密矩阵可以视为一个 $t$ 维的方阵,且这个加密必须可以解密,因此就要求该方阵可以求逆矩阵。试求出对于长度为 $t$ 的明文,Hill cipher 的密钥空间大小。

2. 数学基础

对题目进行简单分析可知,密钥空间大小,就是存在多少个满足条件的可用于加密的矩阵。而这些矩阵需要满足的条件只有一个,就是可以求出逆矩阵。那在 $\mathbb{Z_m}$ 上,有多少个 $t$ 维可逆矩阵呢?这就是我们要解决的问题。

首先给出相关数学知识。默认读者已有近世代数基础,基本概念不再赘述。

  • 【定义 1】 有序基

    这个概念不是很重要,学过线性代数的其实一直在用,只不过有的本科老师没提过这个概念。详见 参考资料

  • 【定义 2】 The General Linear Group 一般线性群

    定义:如果 $V$ 是域 $K$ 上的一个 $m$ 维向量空间,那么一般线性群 $\text{GL}(V)$ 就是 $V$ 上所有非奇异线性变换构成的群。

    如果某人选择一组 $V$ 上的有序基 ${ e_1,…,e_m }$,那么每个 $T \in \text{GL}(V)$ 确定了一个矩阵 $A = [\alpha_{ij}]$。

    而 $T \mapsto A$ 同构于 $\text{GL}(V) \rightarrow \text{GL}(m, K)$,其中 $\text{GL}(m, K)$ 是所有 $K$ 上 $m$ 维非奇异矩阵构成的乘法群。

    当 $K = \text{GF}(q)$,我们可以将 $\text{GL}(m,K)$ 写作 $\text{GL}(m,q)$。

  • 【引理 1】 假设 $m = p^n, \; n \in \mathbb{Z}^{+}, \; p \; is \; prime$。令 $A \in M_{d \times d}(\mathbb{Z_m}), \; d \in \mathbb{Z}^{+}$。用 $p$ 除 $A$,令矩阵 $B$ 为余数,矩阵 $C$ 为商,可得 $A = pC + B$。那么 $A$ 在 $\mathbb{Z_{p^n}}$ 上可逆当且仅当 $B$ 在 $\mathbb{Z_p}$ 上可逆。

    证明如下:

    各符号定义如引理中所述。可以注意到 $B$ 中元素在 $\mathbb{Z_p}$ 上,$C$ 中元素在 $\mathbb{Z_{p^{n-1}}}$ 上。

    根据引理中的定义,可知 $A \equiv B \pmod p$。因此由本科所学线性代数相关知识可得,$det \, A \equiv det \, B \pmod p$。因此,$gcd(det \, A,p) \equiv gcd(det \, B,p)$。

    于是,有 \(\begin{align} & A \; is \; invertible \; mod \; p^n \\ & \iff gcd(det \, A,p^n)=1 \iff gcd(det \, A,p) = 1 \\ & \iff gcd(det \, B,p)=1 \iff B \; is \; invertible \; mod \;p \end{align}\)

    得证。

  • 【引理 2】 定义 $\phi: M_{d \times d}(\mathbb{Z_m}) \longrightarrow \bigoplus_{i=1}^z M_{d \times d} (\mathbb{Z_{p_i^{n_i}}})$,于是 $\phi(A) = \bigoplus \phi_i(A)$,其中 $\phi_i(A) = A \pmod {p_i^{n_i}}$。于是 $\phi$ 是一个环同构。

    证明如下:

    设 $A$ 和 $B$ 为 $M_{d \times d}(\mathbb{Z_m})$ 上的矩阵。

    令 $\phi(A) = (A^{(1)}, … ,A^{(z)})$,$\phi(B) = (B^{(1)}, … ,B^{(z)})$。于是有:

    \[\begin{align} & \phi(A)\phi(B) \\ &= (A^{(1)}, ... ,A^{(z)})(B^{(1)}, ... ,B^{(z)}) \\ &= (A^{(1)}B^{(1)}, ... ,A^{(z)}B^{(z)}) \\ &= ((AB)^{(1)}, ... ,(AB)^{(z)}) \\ &= \phi(AB) \\ \end{align}\]

    于是 $\phi$ 是环同构的,得证。

  • 【引理 3】 $\phi$ 如上一条引理所定义。那么 $\mathbb{Z_m}$ 上的矩阵 $A$ 可逆当且仅当 $\phi(A)$ 可逆。

    由环同构易证。

3. 推导证明

本文的推导证明主要参考了论文 On the Keyspace of the Hill Cipher - Jeff Overbey。推导过程由特殊到一般,从有限域 $\mathbb{Z_p}$ 出发,到一般的 $\mathbb{Z_m}$,最终得到 Hill cipher 密钥空间的大小。

  • 【推导 1】 $\mid \text{GL}(t,\; \mathbb{Z_p}) \mid = \prod_{i=0}^{t-1}(p^t-p^i), \; p \; is \; prime$

    推导证明如下:

    既然只要求矩阵为可逆矩阵,那我们就一列列地来构造满足条件的矩阵。

    首先是第一列,第一列除了不能所有元素全为 $0$ 以外并没有什么要求,因此有 $p^t-1$ 种选择;在确定了第一列的基础上我们来构造第二列,因为要满足可逆,因此第二列不能与第一列线性相关,而与第一列线性相关的情况在 $\text{GF}(p)$ 上有 $p$ 种可能,因此第二列可能的选择有 $p^t-p$ 种;同理,第三列不能被第一二列线性表出,第四列不能被前三列线性表出。

    以此类推,可以得到为了构造可逆矩阵每一列所拥有的选择数量。将每一列可选数量相乘,就可以得到所有可逆矩阵的数量。

    即为在有限域 $\text{GF}(p)$ 上一般线性群的阶 $\mid \text{GL}(t,\; \mathbb{Z_p}) \mid = \prod_{i=0}^{t-1}(p^t-p^i)$,于是得证。

  • 【推导 2】 $\mid \text{GL}(t, \mathbb{Z_{p^n}}) \mid = p^{(n-1)t^2} \prod_{i=0}^{t-1}(p^t-p^i), \; p \; is \; prime$

    推导证明如下:

    在第一条推导的基础上,第二条就很容易证明了。根据 数学基础 部分给出的第一条引理,我们可以知道,这次的阶与 $B$ 和 $C$ 相关。

    而两者相互独立,因此 $A$ 的个数应该由两者个数相乘得到。根据引理,要求 $B$ 可逆,因此适用于推导一,$B$ 有 $\prod_{i=0}^{t-1}(p^t-p^i)$ 个;而 $C$ 可任意选取,且每个元素均在 $\mathbb{Z_{p^{n-1}}}$ 上,因此有 $p^{(n-1)t^2}$ 个。两者相乘即可得证。

  • 【推导 3】 $\mid \text{GL}(t,\; \mathbb{Z_m}) \mid = \prod_i (p_i^{(n_i-1)t^2} \prod_{k=0}^{t-1}(p_i^t-p_i^k)), \; for \; any \; integer \; m\geq 2, \; m = \prod_i p_i^{n_i}$

    推导证明如下:

    根据引理二和三易证。因为环同构,矩阵 $A$ 可逆等价于 $\phi(A)$ 可逆,因此把 $\phi(A)$ 的每一部分满足条件的个数累乘就可以得到最终结果。

4. 最终结论

对于长度为 $t$,且位于 $\mathbb{Z_m}$(其中 $m = \prod_i p_i^{n_i},\; p_i \; is \; prime$)的明文,Hill cipher 的密钥空间大小为:

\[\mid \text{GL}(t,\; \mathbb{Z_m}) \mid = \prod_i (p_i^{(n_i-1)t^2} \prod_{k=0}^{t-1}(p_i^t-p_i^k)), \; for \; any \; integer \; m\geq 2, \; m = \prod_i p_i^{n_i}\]

声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.