若尔当标准型与矩阵离散对数问题

想写这篇好久了，一直没空，考完期末水一下

第一部分：若尔当标准型概述

参考资料：《高等代数（第五版）》（北京大学数学系前代数小组 编）:P213-P219,P236-P239

定义：形为

的矩阵称为若尔当块，其中$\lambda_0$为复数.由若干个若尔当块组成的准对角矩阵

称为若尔当形矩阵，其中$\lambda_1,\lambda_2,\cdots,\lambda_s$为复数，有一些可以相同.

例如矩阵

为若尔当形矩阵（同时它也是一个若尔当块）.

下面给出的是跟若尔当形矩阵相关的一个重要结论，也是后面通过若尔当形矩阵解决矩阵离散对数问题的重要理论支撑.

定理：每个$n$阶复矩阵$\pmb{A}$一定与一个若尔当形矩阵相似.这个若尔当形矩阵除去其中若尔当块的排列顺序外由$\pmb{A}$唯一确定，我们称该若尔当形矩阵为$\pmb{A}$的若尔当标准型.而若尔当标准型中主对角线上元素为$\pmb{A}$的所有特征值.

由上述定理我们可以知道：对于复矩阵$\pmb{A}$的若尔当标准型$\pmb{J}$，必存在一可逆矩阵$\pmb{P}$，使得$\pmb{J}=\pmb{P}^{-1}\pmb{A}\pmb{P}$.

实际上，对于上面的若尔当形矩阵：

其转置$\pmb{A}^T$也可被称为若尔当形矩阵，例如对于矩阵

矩阵$\pmb{A}^T=\left(\begin{matrix}1&1&0\\0&1&1\\0&0&1\end{matrix}\right)$也是若尔当形矩阵.

下面介绍一种求矩阵的若尔当标准型的方法——通过矩阵的特征值求出其若尔当标准型：

第一步：对于一矩阵$\pmb{A}_{n×n}$，求出其特征值$\lambda_1,\lambda_2,\cdots,\lambda_s$；

第二步：求出每个特征值的几何重数（相等特征值只需求一次，表示该特征值对应的若尔当块的个数），其中对于特征值$\lambda_i$，几何重数为$n-r(\lambda_i\pmb{I}-\pmb{A})$

第三步：求每个特征值对应的若尔当块的最大阶数，即找到特征值$\lambda_i$对应的一个值$k_i$，使得$k_i$为满足$r[(\lambda_i\pmb{I}-\pmb{A})^{k_i}]=r[(\lambda_i\pmb{I}-\pmb{A})^{k_i+1}]$的最小正整数

举个例子，对矩阵$\pmb{A}=\left(\begin{matrix}9&0&-36\\6&0&-27\\0&1&0\end{matrix}\right)$，求其对应的若尔当标准型：

第一步，求矩阵$\pmb{A}$对应的特征值，即解方程$det(\lambda \pmb{I}-A)=0$，解得唯一解$\lambda=3$；

第二步，对唯一特征值$\lambda=3$，有$3\pmb{I}-\pmb{A}=\left(\begin{matrix}-6&0&36\-6&3&27\\0&-1&3\end{matrix}\right)\sim\left(\begin{matrix}1&0&-6\\0&1&-3\\0&0&0\end{matrix}\right)$，所以其几何重数为$3-r(3\pmb{I}-\pmb{A})=1$，所以特征值$\lambda=3$对应的若尔当块的个数为$1$；

第三步：对$3\pmb{I}-\pmb{A}$有$r[(3\pmb{I}-\pmb{A})^1]=2,r[(3\pmb{I}-\pmb{A})^2]=1,r[(3\pmb{I}-\pmb{A})^3]=0,r[(3\pmb{I}-\pmb{A})^4]=0$，所以该特征值对应的若尔当块的最大阶数为$3$，所以$\lambda=3$对应的一个三阶的若尔当块$\pmb{J}(3,3)=\left(\begin{matrix}3&1&0\\0&3&1\\0&0&3\end{matrix}\right)$或者$\pmb{J}(3,3)=\left(\begin{matrix}3&0&0\\1&3&0\\0&1&3\end{matrix}\right)$，所以矩阵$\pmb{A}=\left(\begin{matrix}9&0&-36\\6&0&-27\\0&1&0\end{matrix}\right)$对应的若尔当标准型为$\left(\begin{matrix}3&1&0\\0&3&1\\0&0&3\end{matrix}\right)$或者$\left(\begin{matrix}3&0&0\\1&3&0\\0&1&3\end{matrix}\right)$.

由于本文主要讨论的是通过若尔当标准型求解矩阵的离散对数问题，所以就不再深入介绍若尔当标准型了。

在这一部分的最后，我们介绍sage中求方阵的若尔当标准型的方法，这个在后面也会用到：

在sage中有函数jordan_form()，其作用是返回self的若尔当标准型，其函数原型为jordan_form(subdivide=True,transformation=False)，其接收三个参数，分别为一个方阵self，一个布尔型变量subdivide（默认为True），一个布尔型变量transformation（默认为False）。

若subdivide=True，则返回的矩阵中会根据若尔当块进行分块标出.

若transformation=True，则会返回一个矩阵组(J,P)，其中J为self的若尔当标准型，而P为使得$self=\pmb{P}\pmb{J}\pmb{P}^{-1}$成立的方阵；若transformation=False，则只会返回self的若尔当标准型J.

例：求矩阵$\pmb{A}=\left(\begin{matrix}9&0&-36\\6&0&-27\\0&1&0\end{matrix}\right)$的若尔当标准型$\pmb{J}$并求矩阵$\pmb{P}$使得$\pmb{P}^{-1}\pmb{A}\pmb{P}=\pmb{J}$

sage代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sage: A = [[9,0,-36],[6,0,-27],[0,1,0]]
sage: J,P = matrix(A).jordan_form(subdivide = False,transformation = True)
sage: J
[3 1 0]
[0 3 1]
[0 0 3]
sage: P
[36  6  1]
[18  6  0]
[ 6  0  0]
sage: P^-1 * matrix(A) * P
[3 1 0]
[0 3 1]
[0 0 3]

可以得出矩阵$\pmb{A}=\left(\begin{matrix}9&0&-36\\6&0&-27\\0&1&0\end{matrix}\right)$的若尔当标准型为$\pmb{J}=\left(\begin{matrix}3&1&0\\0&3&1\\0&0&3\end{matrix}\right)$，且有矩阵$\pmb{P}=\left(\begin{matrix}36&6&1\\18&6&0\\6&0&0\end{matrix}\right)$使得$\pmb{P}^{-1}\pmb{A}\pmb{P}=\pmb{J}$.

第二部分：利用若尔当标准型解决矩阵离散对数问题

在解决矩阵离散对数问题之前，我们先要了解何谓矩阵离散对数：在有限域$GF(p)$（$p$为质数）中，已知$n$阶矩阵$\pmb{G}$和$\pmb{H}$，满足$\pmb{G}^x=\pmb{H}$，求其中$x$的问题即为矩阵的离散对数问题.

由上面的部分我们可以知道，对于矩阵$\pmb{G}$，存在一个可逆矩阵$\pmb{P}$使得$\pmb{G}=\pmb{P}\pmb{J}\pmb{P}^{-1}$，其中矩阵$\pmb{J}$为$\pmb{G}$对应的若尔当标准型，那么我们可以知道：

其中：

（$\pmb{J}_1,\pmb{J}_2,\cdots,\pmb{J}_s$均为若尔当块）

由于$\pmb{J}$为准对角矩阵，我们有：

对于任意若尔当块

而若尔当块可以分为两部分：

所以

而我们很容易可以知道：

所以$\pmb{J}(\lambda,k)^n=\left(\begin{matrix}n\\0\end{matrix}\right)\pmb{\Lambda}^n+\left(\begin{matrix}n\\1\end{matrix}\right)\pmb{\Lambda}^{n-1}\pmb{E}+\cdots+\left(\begin{matrix}n\\k-1\end{matrix}\right)\pmb{\Lambda}^{n-k+1}\pmb{E}^{k-1}$

可得：

对于一般的矩阵离散对数问题，即给出有限域$GF(p)$下两个矩阵$\pmb{G}$和$\pmb{H}$，求满足$\pmb{G}^x=\pmb{H}$的整数$x$，我们可以直接对比两个矩阵进行求解即可，大致步骤如下：

先求$\pmb{G}$的若尔当标准型$\pmb{J}$并求可逆矩阵$\pmb{P}$使得$\pmb{P}^{-1}\pmb{G}\pmb{P}=\pmb{J}$，由于$\pmb{H}=\pmb{G}^x=(\pmb{P}\pmb{J}\pmb{P}^{-1})^x=\pmb{P}\pmb{J}^{x}\pmb{P}^{-1}$，所以有$\pmb{P}^{-1}\pmb{H}\pmb{P}=\pmb{J}^x$，取矩阵$\pmb{J}$其中一个阶数大于等于$2$的若尔当块$\pmb{J}(\lambda,k)$，在矩阵$\pmb{P}^{-1}\pmb{H}\pmb{P}$取该若尔当块对应区域中最后两行的最后一个元素，实际上就是$\pmb{J}(\lambda,k)^x$最后两行中的$\lambda^x$与$x\lambda^{x-1}$（由上面的矩阵可以得知），从而有：

由于我们知道该若尔当块对应的特征值$\lambda$，所以我们就可以通过乘上一个$\lambda$求出我们需要的$x$.

举个例子，当$p=31$时，在$GF(p)$下有矩阵$\pmb{G}=\left(\begin{matrix}17&0&6\\0&3&0\\9&0&18\end{matrix}\right)$，且有$\pmb{H}=\pmb{G}^x=\left(\begin{matrix}25&0&3\\0&28&0\\20&0&10\end{matrix}\right)$，求$x$.

先求出$\pmb{G}$的若尔当标准型$\pmb{J}$及使得$\pmb{P}^{-1}\pmb{G}\pmb{P}=\pmb{J}$成立的矩阵$\pmb{P}$如下（此处为了减少篇幅使用sage求两个矩阵）：

通过$\pmb{P}$求出$\pmb{J}^x=\pmb{P}^{-1}\pmb{H}\pmb{P}=\left(\begin{matrix}28&0&0\\0&2&16\\0&0&2\end{matrix}\right)$，由于$\pmb{J}$中有一个$2$阶的若尔当块$\left(\begin{matrix}2&1\\0&2\end{matrix}\right)$，其对应的$\pmb{G}$的特征值为$\lambda=2$，所以取$\pmb{J}^x$中对应的块$\left(\begin{matrix}2&16\\0&2\end{matrix}\right)$，有:

两边同乘一个$\lambda=2$可得$x\equiv16\pmod{31}$.

此类矩阵离散对数问题的求解代码模板如下（假设若尔当形矩阵$\pmb{J}$最右下角一个若尔当块阶数大于$2$）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import*
from sage.all import*

G = []
H = []

p = 
n = 	#矩阵的阶数

M_G = matrix(GF(p),G)
M_H = matrix(GF(p),H)

J, P = M_G.jordan_form(subdivide = False,transformation = True)

lambda0 = J[n-1][n-1]
M_H_trans = P**-1 * M_H * P

x = lambda0 * M_H_trans[n-2][n-1] * inverse(int(M_H_trans[n-1][n-1]),p) % p

print(x)

还有一种类型的矩阵离散对数问题，即为给出$GF(p)$下的矩阵$\pmb{G}$及一个初始向量$\pmb{v}$，且给出$\pmb{y}=\pmb{G}^x\pmb{v}$，求$x$.对于这种类型的矩阵离散对数的求解大致步骤如下：

设$\pmb{v}=\left(v_1,v_2,\cdots,v_n\right)^T,\pmb{y}=\left(y_1,y_2,\cdots,y_n\right)^T$，求出矩阵$\pmb{G}$的若尔当标准型$\pmb{J}$并求可逆矩阵$\pmb{P}$使得$\pmb{P}^{-1}\pmb{G}\pmb{P}=\pmb{J}$.为方便解释，在这里我们假定$\pmb{G}$的若尔当标准型$\pmb{P}$的最右下角的若尔当块阶数大于等于$2$（实际上，一个矩阵的若尔当标准型可以通过若尔当块的顺序来变成该矩阵的另外一个若尔当标准型）.

所以有：

设$\pmb{t}=\pmb{P}^{-1}\pmb{v}，\pmb{z}=\pmb{P}^{-1}\pmb{y}$，就可以得到：$\pmb{P}\pmb{J}^x\pmb{t}=\pmb{P}\pmb{z}$，而由于矩阵$\pmb{P}$可逆，则有$\pmb{J}^x\pmb{t}=\pmb{z}$.

由于我们已知$\pmb{v}$及$\pmb{y}$，所以我们可以通过$\pmb{P}$求出$\pmb{t}$及$\pmb{z}$，在这里我们设$\pmb{t}=\left(t_1,t_2,\cdots,t_n\right)^T,\pmb{z}=\left(z_1,z_2,\cdots,z_n\right)^T$，由于上面我们假设了$\pmb{J}$最右下角的若尔当块的阶数大于等于$2$，在这里我们假设它对应的特征值为$\lambda$，就可以得出若尔当标准型$\pmb{J}$最后两行对应的线性关系为：

我们可以知道$\lambda^{x}\equiv\frac{z_n}{t_n}\pmod{p}$，代入第一行的式子可以得到：

整理可得：

这样我们就可以求出我们要求的$x$了.

例如，当$p=31$时，在$GF(p)$下有矩阵$\pmb{G}=\left(\begin{matrix}17&0&6\\0&3&0\\9&0&18\end{matrix}\right)$，且有$\pmb{v}=(1,2,3)^T$，有$\pmb{G}^x\pmb{v}=\pmb{y}=(13,30,25)^T$，求$x$.

这个矩阵$\pmb{G}$的若尔当标准型$\pmb{J}$和对应的矩阵$\pmb{P}$在上面已经求出，所以这里我们直接搬下来用：

所以有$\pmb{t}=\pmb{P}^{-1}\pmb{v}=(2,21,27)^T，\pmb{z}=\pmb{P}^{-1}\pmb{y}=(30,20,23)^T$，而矩阵$\pmb{J}$的最右下角的若尔当块对应的特征值$\lambda=2$，所以有：

所以可以得出要求的$x = 21$.

此类矩阵离散对数问题的求解代码模板如下（假设若尔当形矩阵$\pmb{J}$最右下角一个若尔当块阶数大于$2$）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import*
from sage.all import*

G = []
V = []
Y = []

p = 31
n = 3

M_G = matrix(GF(p),G)
v = matrix(GF(p),V)
y = matrix(GF(p),Y)

J, P = M_G.jordan_form(subdivide = False,transformation = True)
t = P**-1 * v
z = P**-1 * y
lambda0 = J[n-1][n-1]

x = lambda0 * (t[n-1][0]*z[n-2][0] - t[n-2][0]*z[n-1][0]) * inverse(int(t[n-1][0]*z[n-1][0]),p) % p

print(x)

还有一种特殊情况就是$\pmb{G}^x=\pmb{H}$中$\pmb{G}$的若尔当标准型为对角矩阵.这种情况实际上只需要求出$\pmb{G}$的标准型$\pmb{J}$与其对应的$\pmb{P}$之后，通过$\pmb{P}^{-1}\pmb{H}\pmb{P}$求出$\pmb{J}^x$，再通过求解整数的离散对数问题的方法求解就行（实际上应该只有这一种方法）.

下面通过一道题展示一下矩阵离散对数在密码学上的应用：

[XYCTF2024]fakeRSA

加密代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *

flag = b'XYCTF{******}'
n = ZZ(bytes_to_long(flag))
p = getPrime(int(320))
print(p)

G = Zmod(p)

def function(X, Y, Z):
    def part(a, b, c):
        return vector([9 * a - 36 * c, 6 * a - 27 * c, b])
    def parts(n):
        Gx.<a, b, c> = G[]
        if n == 0: return vector([a, b, c])
        mid = parts(n // 2)
        result = mid(*mid)
        if n % 2 == 0: return result
        else: return part(*result)
    return parts(n)(X, Y, Z)

print(function(69, 48, 52))
#输出数据略

由代码可以看出function的作用是在$GF(p)$中对向量$(X,Y,Z)^T$进行$n$次变换$(X’,Y’,Z’)^T=(9X-36Z,6X-27Z,Y)^T$后得到输出的向量，写出变换的矩阵形式如下：

设原向量为$(x_1,x_2,x_3)^T$，最终向量为$(y_1,y_2,y_3)^T$，则有：

通过上面介绍的方法求解即可得出$n$，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import*
from sage.all import*

G = [[9,0,-36],[6,0,-27],[0,1,0]]
V = [[69],[48],[52]]
Y = ...	#题目中输出的向量

p = 1849790472911267366045392456893126092698743308291512220657006129900961168811898822553602045875909
n = 3

M_G = matrix(GF(p),G)
v = matrix(GF(p),V)
y = matrix(GF(p),Y)

J, P = M_G.jordan_form(subdivide = False,transformation = True)
t = P**-1 * v
z = P**-1 * y
lambda0 = J[n-1][n-1]

x = lambda0 * (t[n-1][0]*z[n-2][0] - t[n-2][0]*z[n-1][0]) * inverse(int(t[n-1][0]*z[n-1][0]),p) % p

print(long_to_bytes(int(x)))

运行可得结果：XYCTF{y0u_finally_f0und_t3h_s3cr3ts!!}