matrixRSA

初次复现

比赛的时候在哈尔滨🧊玩，队友太给力了，差点干进决赛了🐮，赛后复现一下

这是一道不难的 RSA，第一段是一个泄露 \(p\) 高位，\(512\) 位的 \(p\) 泄露了 \(412\) 位，绰绰有余，套板子即可

n = 132298777672085547096511087266255066285502135020124093900452138262993155381766816424955849796168059204379325075568094431259877923353664926875986223020472585645919414821322880213299188157427622804140996898685564075484754918339670099806186873974594139182324884620018780943630196754736972805036038798946726414009
p4 = 9707529668721508094878754383636813058761407528950189013789315732447048631740849315894253576415843631107370002912949379757275
e = 65537
pbits = 512

kbits=pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits,beta=0.4)

if roots:
    p = p4 + int(roots[0])
    q = n/p
    print ("n:",n)
    print ("p:",p)
    print ("q:",q)

第二段是一个论文题，论文链接在此

根据论文中的结论，这种基于矩阵的 RSA 在求 \(d\) 时， \(e\) 的逆元是在模 \(N\prime\) 意义下的，\(N \prime\) 的值为 \((p^h-1)(q^h-1)\)，其中 \(h\) 为矩阵的阶

但是，经过测试，实际上不管矩阵的阶是多少，\(N \prime\) 的值取 \((p^2-1)(q^2-1)\) 都可以得到正确的 \(d\)，而且目前看到的所有 wp，不管是各个师傅的，还是官方的，用的都是 \((p^2-1)(q^2-1)\)，但这道题里明明是一个三阶矩阵，按照论文中的结论应该用 \((p^3-1)(q^3-1)\) 才对，事实却是错的，至于原因，现在还没想清楚

d = pow(e,-1,(p**2-1)*(q**2-1))

C = Matrix(Zmod(n),[[..., ..., ...],
[..., ..., ...],
[..., ..., ...]])

M = C**int(d)
for MM in M:
    for MMM in MM:
        print(long_to_bytes(int(MMM)).decode(),end='')

探究正确模数

实际上，刚才上面引用的论文中，有提及前人已有的成果，这篇文章也是在此基础上总结，推测可以使用模数 \((p^h-1)(q^h-1)\)，而前人已有成果中，就有取 \[ g=\prod_{i=0}^{h-1}(p^h-p^i)\prod_{i=0}^{h-1}(q^h-q^i) \]

经过测试，使用这个 \(g\) 作为模数也是正确的，也就是在这题中取 \[ d = \mathrm{pow}(e,-1,(p^3-p^2)(p^3-p)(p^3-1)(q^3-q^2)(q^3-q)(q^3-1)) \] 也是可以得到正确的 \(d\) 的

而上面提到的这个结论，也就是上图中框出的 Andrew Pangia 提出的结论，论文链接在此，文章中对结论在 \(h=2\) 的情况时做了证明，下面做一个简单整理

证明过程

首先根据一般线性群的性质，有群 \(GF_2(\mathbb{Z_p})\) 的阶为 \[ g_p=(p^2-p)(p^2-1) \] 同理，群 \(GF_2(\mathbb{Z_q})\) 的阶为 \[ g_q=(q^2-q)(q^2-1) \] 采用的模数 \[ g=g_pg_q \] 即 \[ ed\equiv1\bmod g \] 即 \[ ed=1+kg,k\in\mathbb{Z} \] 故 \[ \begin{aligned} C^d&=M^{ed}\bmod n\\ &=M^{1+kg}\bmod n\\ &=M\cdot M^{kg_pg_q}\bmod p\\ &=M\cdot ((M^{g_p})^{g_q})^k\bmod p\\ \end{aligned} \] 由于明文矩阵 \(\langle M\rangle\) 是 \(GF_2(\mathbb{Z_q})\) 的子群，由拉格朗日定理，群 \(\langle M\rangle\) 的阶的是群 \(GF_2(\mathbb{Z_q})\) 的阶的因子，设为 \(x\)，即有 \[ g_p=jx,j\in\mathbb{Z} \] 故 \[ \begin{aligned} C^d&=M\cdot ((M^{g_p})^{g_q})^k\bmod p\\ &=M\cdot ((M^{jx})^{g_q})^k\bmod p\\ &=M\cdot ((M^{x})^{jg_q})^k\bmod p\\ &=M\cdot I^{jg_qk}\bmod p\\ &=M\bmod p\\ \end{aligned} \] 其中，\(I\) 为单位矩阵，因为 \(x\) 是群 \(\langle M\rangle\) 的阶

需要注意这里得到 \(M^x=I\) 需要在 \(\mathbb{Z_p}\) 下才能成立，这是一般线性群的定义要求的，这也是为什么上面从\(\bmod n\) 变成了\(\bmod p\)

同理，还可以得到 \[ C^d=M\bmod q\\ \] 故 \[ C^d=M\bmod n\\ \] 证明完毕

推广

可以看到，以上证明过程，与所涉及的一般线性群的阶的值 \(g_p,g_q\) 并无直接关系，因此可以将结论推广至高阶，即 \(h\) 阶的基于矩阵的 RSA 加密，在求 \(d\) 时所用的模数为 \[ \begin{aligned} g&=g_pg_q\\ &=\prod_{i=0}^{h-1}(p^h-p^i)\prod_{i=0}^{h-1}(q^h-q^i) \end{aligned} \] 同样，当 \(h\) 取 \(1\) 的时候，\(g\) 的值就是 \((p-1)(q-1)\)，也就是正常 RSA 的 \(\varphi\) 值，因为 \(h\) 取 \(1\) 的时候，是一个 \(1\times1\) 的矩阵，也就相当于没有矩阵，是一个正常的 RSA

新 wp

修改后的 wp 如下

gp = (p**3-p**2)*(p**3-p)*(p**3-1)
gq = (q**3-q**2)*(q**3-q)*(q**3-1)
d = pow(e,-1,gp*gq)

C = Matrix(Zmod(n),[[..., ..., ...],
[..., ..., ...],
[..., ..., ...]])

M = C**int(d)
for MM in M:
    for MMM in MM:
        print(long_to_bytes(int(MMM)).decode(),end='')