Line CTF 2022 X-Factor Writeup

题目背景

RSA 签名: $s \equiv m^d \pmod{n}$

RSA 验签: $m^\prime \equiv s^e \pmod{n}$, 检查$m^\prime = m$是否成立.

一般情况下要求对$m$的哈希值$H(m)$进行签名, 否则给定若干组$m_i$, 可以根据$m_i$的因子构造出新的消息$M$和伪造签名$S$.

假设$M = \prod{m_i^{\alpha_i}}$,$m_i$对应的签名为$s_i$,则有

$S \equiv M^d \pmod{n}$

$\quad \equiv (m_1^{\alpha_1}m_2^{\alpha_2}\cdots m_n^{\alpha_n})^d$

$\quad \equiv (m_1^{\alpha_1})^d(m_2^{\alpha_2})^d\cdots (m_n^{\alpha_n})^d$

$\quad \equiv (m_1^d)^{\alpha_1}(m_2^d)^{\alpha_2}\cdots (m_n^d)^{\alpha_n}$

$\quad \equiv s_1^{\alpha_1}s_2^{\alpha_2}\cdots s_n^{\alpha_n}$

Solution

题目给定了若干组RSA签名$(m_i, s_i)$, 给定$M$, 要求伪造其签名$S$.

考察$m_i$的质因子, 发现他们由下列质数组合而成

$P_i = {2, 61, 197, 811, 947, 970111, 2098711, 2854343, 9605087}$

考察$M$的质因子, 发现他们由下列质数组合而成

$P_m = {2, 197, 947, 2098711, 9605087}$

说明$M$或许可以用$m_i$的某种组合来表示.

我们这里构造一个线性空间, 将$p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$ 映射到向量$[\alpha_1, \alpha_2, \cdots, \alpha_n]^T$

于是可以将$m_i$按列向量排列为以下矩阵

$$A = \left[ \begin{matrix} 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 2& 0& 1\\ 1& 0& 0& 0& 1& 0& 1\\ 3& 0& 0& 1& 0& 0& 1\\ 1& 0& 1& 1& 0& 0& 0\\ 0& 0& 2& 1& 0& 1& 0\\ 0& 0& 1& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1& 0\\ \end{matrix} \right]$$

将$M$映射为以下向量

$$b = [1,0,1,0,1,0,1,0,1]^T$$

则$M$可以用$m_i$的组合表示可以变换为求解$Ax = b$

发现$rank(A) = rank(A|b)$说明这个方程可解.发现$A$不是方阵,我们可以通过左逆消去A.

$$A^+_{left} = (A^TA)^{-1}A^T$$

解得 $x = [-1,1,-1,2,-1,1,2]$, 所以

$$M \equiv m_1^{-1}m_2m_3^{-1}m_4^2m_5^{-1}m_6m_7^{2} \pmod{n}$$ $$S \equiv s_1^{-1}s_2s_3^{-1}s_4^2s_5^{-1}s_6s_7^{2} \pmod{n}$$

根据题目要求得到flag

from Crypto.Util.number import *
from primefac import primefac
from sympy import factorint

n = 0xa9e7da28ebecf1f88efe012b8502122d70b167bdcfa11fd24429c23f27f55ee2cc3dcd7f337d0e630985152e114830423bfaf83f4f15d2d05826bf511c343c1b13bef744ff2232fb91416484be4e130a007a9b432225c5ead5a1faf02fa1b1b53d1adc6e62236c798f76695bb59f737d2701fe42f1fbf57385c29de12e79c5b3 
e = 0x10001 

p = [0x945d86b04b2e7c7 , 0x5de2 , 0xa16b201cdd42ad70da249 , 0x6d993121ed46b , 0x726fa7a7 , 0x31e828d97a0874cff , 0x904a515 ]

c = [0x17bb21949d5a0f590c6126e26dc830b51d52b8d0eb4f2b69494a9f9a637edb1061bec153f0c1d9dd55b1ad0fd4d58c46e2df51d293cdaaf1f74d5eb2f230568304eebb327e30879163790f3f860ca2da53ee0c60c5e1b2c3964dbcf194c27697a830a88d53b6e0ae29c616e4f9826ec91f7d390fb42409593e1815dbe48f7ed4 , 0x3ea73715787028b52796061fb887a7d36fb1ba1f9734e9fd6cb6188e087da5bfc26c4bfe1b4f0cbfa0d693d4ac0494efa58888e8415964c124f7ef293a8ee2bc403cad6e9a201cdd442c102b30009a3b63fa61cdd7b31ce9da03507901b49a654e4bb2b03979aea0fab3731d4e564c3c30c75aa1d079594723b60248d9bdde50 , 0x9444e3fc71056d25489e5ce78c6c986c029f12b61f4f4b5cbd4a0ce6b999919d12c8872b8f2a8a7e91bd0f263a4ead8f2aa4f7e9fdb9096c2ea11f693f6aa73d6b9d5e351617d6f95849f9c73edabd6a6fde6cc2e4559e67b0e4a2ea8d6897b32675be6fc72a6172fd42a8a8e96adfc2b899015b73ff80d09c35909be0a6e13a , 0x2b7a1c4a1a9e9f9179ab7b05dd9e0089695f895864b52c73bfbc37af3008e5c187518b56b9e819cc2f9dfdffdfb86b7cc44222b66d3ea49db72c72eb50377c8e6eb6f6cbf62efab760e4a697cbfdcdc47d1adc183cc790d2e86490da0705717e5908ad1af85c58c9429e15ea7c83ccf7d86048571d50bd721e5b3a0912bed7c , 0xa7d5548d5e4339176a54ae1b3832d328e7c512be5252dabd05afa28cd92c7932b7d1c582dc26a0ce4f06b1e96814ee362ed475ddaf30dd37af0022441b36f08ec8c7c4135d6174167a43fa34f587abf806a4820e4f74708624518044f272e3e1215404e65b0219d42a706e5c295b9bf0ee8b7b7f9b6a75d76be64cf7c27dfaeb , 0x67832c41a913bcc79631780088784e46402a0a0820826e648d84f9cc14ac99f7d8c10cf48a6774388daabcc0546d4e1e8e345ee7fc60b249d95d953ad4d923ca3ac96492ba71c9085d40753cab256948d61aeee96e0fe6c9a0134b807734a32f26430b325df7b6c9f8ba445e7152c2bf86b4dfd4293a53a8d6f003bf8cf5dffd , 0x927a6ecd74bb7c7829741d290bc4a1fd844fa384ae3503b487ed51dbf9f79308bb11238f2ac389f8290e5bcebb0a4b9e09eda084f27add7b1995eeda57eb043deee72bfef97c3f90171b7b91785c2629ac9c31cbdcb25d081b8a1abc4d98c4a1fd9f074b583b5298b2b6cc38ca0832c2174c96f2c629afe74949d97918cbee4a ]
m = 0x686178656c696f6e

s = set()
t = [i for i in primefac(m)]
for i in t:
    s.add(i)
cc = 0 
for x in p:
    t = [i for i in primefac(x)]
    for i in t:
        s.add(i)

primelist = list(s)
primelist.sort()
print(primelist)
print([i for i in primefac(m)])
M = []
for x in p:
    l = factorint(x)
    vec = []
    for f in primelist:
        if f in l:
            vec.append(l[f])
        else:
            vec.append(0)
    print(vec)
    M.append(vec)

l = factorint(m)
ans = []

for f in primelist:
    if f in l:
        ans.append(l[f])
    else:
        ans.append(0)

v = Matrix(ans).transpose()
M = Matrix(M).transpose()
print(M)
print(v)
input()
print(M.rref())
input()
res = (M.transpose()*M).inverse()*M.transpose()*v

powers = res.column(0)
mm = 1 
s = 1 
for i in range(len(p)):
    print(powers[i])
    mm *= pow(p[i], powers[i], n)
    s *= pow(c[i], powers[i], n)

s %= n

assert mm == m
assert pow(s,e,n) == m

print(b'line{'+ long_to_bytes(int(s))[-16:].hex()+b'}')
# LINECTF{a049347a7db8226d496eb55c15b1d840}