论文复现：A Matrix Extension of the RSA Cryptosystem

Matrix RSA论文复现+H&NCTF相关题目复现

RSA相关

Theorem 1. Euler’s Theorem. Let $a \in \mathbb{Z}$ and $n\in\mathbb{N}$. If$\gcd(a, n)=1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$.
Lemma 1. Let $x, y, a, b \in\mathbb{Z}^{+}$ such that $\gcd(a, b)=1$. If $x\equiv y \pmod{a}$ and $x\equiv y \pmod{b}$,then $x\equiv y \pmod{ab}$.
Theorem 2. Let $n = pq$ where p and q are distinct prime integers, let $m \in\{0,1, 2,…,n − 1\},e, d \in\mathbb{Z}$ such that $ed\equiv 1 \pmod{\phi(n)}$, and let $c \equiv m^e \pmod{n}$. Then $c^{d}\equiv m \pmod{n}$

证明就不多赘述了。

矩阵RSA

文章中的方法对RSA系统进行修改，将明文存储在$2\times 2$的矩阵中，依旧利用整数n=pq，矩阵M代替原来的标量值m，并且不依赖于$\varphi(n)=(p-1)(q-1)$而是依赖于值$(p^{2}-1)(p^{2}-p)(q^{2}-1)(q^{2}-q)$

前置过程

下面给出一般线性群的一般定义：

Definition 1. The General Linear Group of order $s$, denoted $GL_{s}(\mathbb{Z}_{n})$, is the monoid of invertible $s \times s$ matrices containing elements from $\mathbb{Z}_{n}$ with respect to multiplication such that the determinants of the matrices and $n$ are relatively prime.

单位矩阵I属于$GL_{s}(\mathbb{Z}_{n})$，矩阵乘法满足结合律，矩阵行列式与n互质即$GL_{s}(\mathbb{Z}_{n})$中每一个元素都有乘法逆元，所以构成一个群。

文章中提到一个灵感来源于文献[1]的方法，它为所有方阵提出了这种方法，并提及了一般线性群的使用。文献[1]提出的指数模运算被定义为： $g=\prod_{k=0}^{s-1}(p^{s}-p^{k})+\prod_{k=0}^{s-1}(q^{s}-q^{k})$
其中s是一般线性群在$\mathbb{Z}_{p}$和$\mathbb{Z}_{q}$上的阶；
进一步地，文献[1]声称 $g=\prod_{k=0}^{s-1}(p^{s}-p^{k})$ 是s阶一般线性群的阶。
选一个例子，文献[1]取$p=43, q=47$。加密模数为$n=pq=2021$，而指数模运算为 $𝑔=(𝑝^{2}−𝑝)(𝑝^{2}−1)+(𝑞^{2}−𝑞)(𝑞^{2}−1)=8111184$，加密指数被选为e=17，满足gcd(e, g)=1，解密指数被找到为d=954257。
当我们使用矩阵A(mod n)对于一个正整数n时，A的每一项都属于$\mathbb{Z}_{n}$。
以 $𝑀=\begin{bmatrix} 13&1\\20&7 \end{bmatrix}$ 为例，矩阵对应于明文math。那么，根据文献[1]提出的方法，密文为 $C\equiv M^{e}\equiv \begin{bmatrix} 1473&884\\1512&211 \end{bmatrix}\pmod{n}.$ 然而，解密这个矩阵时，我们得到 $C^{d}\equiv\begin{bmatrix} 791&1460\\906&115 \end{bmatrix}\pmod{n}.$
显然这个矩阵并不是原始矩阵M。
代码过程如下：

sage: import gmpy2
sage: p=47
sage: q=43
sage: n=p*q
sage: g=(p^2-p)*(p^2-1)+(q^2-q)*(q^2-1)
sage: g
8111184
sage: e=17
sage: gcd(e,g)
1
sage: d = inverse(e, g)
sage: d = int(gmpy2.invert(e,g))
sage: d
954257
sage: M = [[13,1],[20,7]]
sage: M = matrix(Zmod(n),M)
sage: C=M^e
sage: C
[1473  884]
[1512  211]
sage: C^d
[ 791 1460]
[ 906  115]

猜想

显然，在s=1的情况下上述提出的模数定义并不能正确简化为欧拉函数，文章中修改指数模运算为： $g=\prod_{k=0}^{s-1}(p^{s}-p^{k})\cdot\prod_{k=0}^{s-1}(q^{s}-q^{k})$ 为方便讨论，固定取s=2得到 $𝑔=(𝑝^{2}−𝑝)(𝑝^{2}−1)(𝑞^{2}−𝑞)(𝑞^{2}−1)$

Theorem 3. The order of the General Linear Group $GL_2(Z_p)$ is given by $|GL_{2}(Z_{p})| = (p^{2} − 1)(p^{2} − p),$where p is a prime integer.

$Proof$. Let $S = \left\{\begin{bmatrix}a&b\\c&d\end{bmatrix}:a,b,c,d\in\mathbb{Z}_{p}\right\}$，注意到$GL_{2}(\mathbb{Z}_{p})\subset S$，所以尝试从所有可能中减去不属于该群的矩阵来计算总矩阵数量。
Let $A\subset S$，A中每一元素都有p种选择，即$|S|=p^{4}$。
要使A不属于$GL_{2}(Z_p)$，则$det(A)\equiv 0\pmod{p}$，即$ad\equiv bc\pmod{p}$。
若$ad\equiv bc\equiv 0\pmod{p}$：当$bc ≡ 0 \pmod{p}$时有$2p-1$种方式使其成立，ad同理，因此有$(2p-1)^{2}$种方法使$ad\equiv bc\equiv 0\pmod{p}$。
若$ad\equiv bc\not\equiv 0\pmod{p}$：当$bc ≡ i \pmod{p},i\in \{1,2,\dots,p-1\}=\mathbb{Z}^{*}_{p}$时有$p-1$种方式使其成立，ad同理，同时$i$也有$p-1$种可能，因此有$(p-1)^{3}$种不同方式使得$ad\equiv bc\equiv 0\pmod{p}$。
因为零和非零bc的选择是不相交的，我们得出$k = (2p - 1)^2 + (p - 1)^3$，代入得 $∣GL_2(\mathbb{Z}_p)∣=p^4−((2p−1)^2+(p−1)^3)$ 简化后得出 $∣GL_2(\mathbb{Z}_p)∣=(p^2−1)(p^2−p)$

有了所有素数p的$GL_2(\mathbb{Z}_p)$的阶，就能够构建一个类似于RSA密码系统中的$\varphi(n)$的模数$g=(p^{2}-1)(p^{2}-p)(q^{2}-1)(q^{2}-q)$，其中p和q是前述n的素因数，我们得到了类似于定理2的结果。
为了做到这一点，我们还需要关于群阶的Lagrange定理：

Theorem 4. Lagrange’s Theorem. Let $H$ be a subgroup of a finite group $G$. Then $|H|$ divides $|G|$.We also require the following lemma.
Lemma 2. Let $n = pq$ where $p$ and $q$ are distinct prime integers. If $M\in GL_2(\mathbb{Z}_n)$, then $M \in GL_2(\mathbb{Z}_p)$ and $M \in GL_2(\mathbb{Z}_q)$.

$Proof$. 设 $n=pq$，利用反证法证明，假设$M\not\in GL_2(\mathbb{Z}_n)$。
根据一般线性群的定义，$\gcd(\det(M),p)\ne1$。
由于$p$是素数，我们有 $\gcd(\det(M),p)=p$，即$p|\det(M)$。
因为$p|n$。那么$\gcd(\det(M),n)\geq p>1$，与$M\not\in GL_2(\mathbb{Z}_n)$相矛盾。
因此得出结论，如果$M\in GL_2(\mathbb{Z}_n)$，则$M\in GL_2(\mathbb{Z}_p)$。同理$M\in GL_{2}(\mathbb{Z}_{q})$。

其实从$\det(M)$与$n=pq$互质就能得到$\det(M)$分别与$p,q$互质。
代码验证：

sage: import gmpy2
sage: p = 123321123456776543211232123321232142376734682734268374682734628374268374683469827516948569347825698471568991   #prime
sage: e=17
sage: M = [[13,1],[20,7]]
sage: gp=(p^2-p)*(p^2-1)
sage: d = int(gmpy2.invert(e,gp))
sage: gcd(e,gp)
1
sage: M = matrix(Zmod(p),M)
sage: C=M^e
sage: C^d
[13  1]
[20  7]
sage: M==C^d
True

符合。
该文章文章使用M表示明文矩阵，C表示密文矩阵，而e和d分别表示加密和解密指数。利用$ed≡1 \pmod{g}$来从$C≡M^{e}\pmod{n}$中还原明文$M≡C^{d} \pmod{n}$。

Theorem 5. Let $n = pq$ where p and q are distinct prime numbers, let $M\in GL_2(\mathbb{Z}_n)$ be a matrix made up of nonnegative integers less than n, let $g_{p} = |GL_2(\mathbb{Z}_{p})|= (p^2−1)(p^2−p)$ and $g_q = |GL_2(\mathbb{Z}_{q})|=(q^{2}−1)(q^{2}-q)$ and define $g=g_{p}g_{q}$ . Further let $e, d \in \mathbb{Z}^{+}$ such that $ed\equiv \pmod{g}$, and let $C\equiv M^{e}\pmod{n}$. Then $C^{d}\equiv M\pmod{g}$.

$Proof.$假设已经定义了上述所有变量和矩阵，有$C^{d}\equiv M^{ed}\equiv M\pmod{n}$。
因为$ed\equiv 1\pmod{g}$，根据同余定义，存在整数 k 使得$ed = 1 + kg$。从而$M^{ed} ≡ M^{1+kg} \pmod{n}$，因此$M^{ed} ≡ M^{1+kg} ≡ M \cdot (M^{g_{p}})^{g_{q} \cdot k} \pmod{p}$
由于$g_p$定义为$GL_2(ℤ_p)$的阶，而$M$的循环子群$\langle M\rangle$是$GL_2(ℤ_p)$的子群，根据拉格朗日定理，$|\langle M\rangle|$ 必然整除$g_p$。这意味着存在整数j使得$g_p = j \cdot |\langle M\rangle|$，于是$C^{d} \equiv M^{e} \equiv M\cdot M^{g_{p}\cdot g_{q}\cdot k}\equiv M \cdot ((M^{j \cdot | \langle M\rangle |})^{g_{q}})^{k} \equiv M \cdot (M^{j \cdot | \langle M\rangle | \cdot g_{q} \cdot k}) \equiv M \cdot I^{j \cdot g_{q} \cdot k} ≡ M \pmod{p}$。
同理可以证明$C^d \equiv M \pmod{p}$。
由引理1我们得到$C^d \equiv M \pmod{n}$。

Example

文章中选择了$p=503,q=499$也就是$n=250997$，$e=241$作为公钥对。 $\begin{align} g_{p}=(p^{2}-p)(p^{2}-1)\\g_{q}=(q^{2}-q)(q^{2}-1) \end{align}$ 则

$\begin{align} g=g_{p}g_{q}=3953076248524019904000 \end{align}$

计算私钥$d=1016973972649332921361$
文章中发送方将消息转化为四条子消息放入矩阵M中如下： $M=\begin{bmatrix}31825&162015\\71801&160825\end{bmatrix}$ 发送方加密C $C\equiv M^{e}\equiv\begin{bmatrix}31825&162015\\71801&160825\end{bmatrix}^{241}\equiv\begin{bmatrix}153377&104497\\76449&55902\end{bmatrix}\pmod{n}$ 接收方解密M $M\equiv C^{d}\equiv\begin{bmatrix}153377&104497\\76449&55902\end{bmatrix}^{1016973972649332921361}\equiv\begin{bmatrix}31825&162015\\71801&160825\end{bmatrix}\pmod{n}$

代码验证：

import gmpy2
from sage.all import *
  
p = 503
q = 499
n = p*q
e = 241
gp = (p**2-p)*(p**2-1)
gq = (q**2-q)*(q**2-1)
g = gp*gq
  
d = gmpy2.invert(e,g)
  
M = matrix(Zmod(n),[[31825,162015],[71801,160825]])
C = M**e
print(M == C**d)
"""
True

Counterexample

文章还例举了一个$|M|=0$的反例。
选择$p=43,q=47,n=pq,e=17,M=\begin{bmatrix}21&22\\21&22\end{bmatrix}$，计算$g=1593215311564$
注意到$21+22=43=p$
计算密文C $C\equiv M^{e}\equiv\begin{bmatrix} 1634&172\\1634&172 \end{bmatrix}\pmod{n}$ 尝试解密： $C^{d}\equiv\begin{bmatrix} 1634&172\\1634&172 \end{bmatrix}\pmod{n}$
显然这个解密方法是错误的。
代码验证：

import gmpy2
from sage.all import *
from Crypto.Util.number import *
p = 43
q = 47
n = p*q
e = 17
gp = (p**2-p)*(p**2-1)
gq = (q**2-q)*(q**2-1)
g = gp*gq
  
d = gmpy2.invert(e,g)
  
M = matrix(Zmod(n),[[21,22],[21,22]])
C = M**e
print(M == C**d)
print(C**d)
"""
False 
[1290 774]
[1290 774]

第一次复现论文找了篇简单的试试水【思索】

例题

H&NCTF MatrixRSA，这篇论文正是在复现中发现的。

题目：

from Crypto.Util.number import *
import os

flag = b"H&NCTF{??????????????}" + os.urandom(73)

p = getPrime(56)
q = getPrime(56)
n = p * q

part = [bytes_to_long(flag[13*i:13*(i+1)]) for i in range(9)]

M = Matrix(Zmod(n),[
    [part[3*i+j] for j in range(3)] for i in range(3)
])

e = 65537
C = M ** e
print(f"n = {n}")
print(f"C = {list(C)}")

"""
n = 3923490775575970082729688460890203
C = [(1419745904325460721019899475870191, 2134514837568225691829001907289833, 3332081654357483038861367332497335), (3254631729141395759002362491926143, 3250208857960841513899196820302274, 1434051158630647158098636495711534), (2819200914668344580736577444355697, 2521674659019518795372093086263363, 2850623959410175705367927817534010)]
"""

解析：

这个题看了出题者的记录似乎是没出好而有了非预期
出题者本意是想让用Matrix的三阶矩阵群的阶为$p(p^{2}-1)(p^2+p+1)$
结果phi取虚数$(p^{2}-1)(q^{2}-1)$也可以。
在复现了这篇论文后，理解到该一般线性群的最大阶为g，然而大部分矩阵的阶都达不到最大阶而是这个阶的因子，所以只需要包含实际矩阵的阶就可以了，经过测试发现$(p^{2}-1)(q^{2}-1)$恰好为M的阶

sage: M^((p**2-1)*(q**2-1))
[1 0 0]
[0 1 0]
[0 0 1]

翻群里发现鸡块师傅现身为他人解惑：可以参考GL(n,Fp)群阶的研究 | Tover’s Blog

exp

import gmpy2
from sage.all import *
from Crypto.Util.number import *
n = 3923490775575970082729688460890203
C = [(1419745904325460721019899475870191, 2134514837568225691829001907289833, 3332081654357483038861367332497335), (3254631729141395759002362491926143, 3250208857960841513899196820302274, 1434051158630647158098636495711534), (2819200914668344580736577444355697, 2521674659019518795372093086263363, 2850623959410175705367927817534010)]
e=65537
#print(factor(n))
p = 56891773340056609
q = 68964114585148667
C = Matrix(Zmod(n), C)
gp = (p**2-p)*(p**2-1)
gq = (q**2-q)*(q**2-1)
g = gp * gq
d = gmpy2.invert(e, g)

M=C**d%n

m = b''.join(long_to_bytes(int(y)) for x in M for y in x)

print(m)
"""
b"H&NCTF{58bff5c1-4d5f-4010-a84c-8fbe0c0f50e8}hj\xa5\x1d'\x92\xa9\x1as\xb5\xd2\x9c\xba=bI\xa5\xb52{\x9c-\xff\xb1\x9dZ\x06\x82v\x11\xaa:t%\xd0\xa6\xb0\xa7wJE\x0f_o\xd6\xf7x3\n\xf44\x01\xee\xd4\r\x08&\x19N\xed\x03\x1b\xfeJ\xc1.\xe7\xecR\xe1\xee\xe4\xbe"

[1] S. Aboud et al, An Efficient RSA Public Key Encryption Scheme, Fifth International Conference on Information Technology: New Generations, (2008), 127-130

论文复现：A Matrix Extension of the RSA Cryptosystem

http://example.com/2024/07/02/论文复现：A Matrix Extension of the RSA Cryptosystem/

作者

AlLvia

发布于

2024年7月2日

许可协议

羊城杯2024复现上一篇

XYCTF-Crypto方向部分wp 下一篇