[强网拟态决赛 2023] Crypto

Bad_rsa

题目描述：

from Crypto.Util.number import *

f = open('flag.txt','rb')
m = bytes_to_long(f.readline().strip())

p = getPrime(512)
q = getPrime(512)
e = getPrime(8)
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
leak = d & ((1<<265) - 1)

print(f'e = {e}')
print(f'leak = {leak}')
print(f'n = {n}')
c = pow(m,e,n)
print(f'c = {c}')

'''
e = 149
leak = 6001958312144157007304943931113872134090201010357773442954181100786589106572169
n = 88436063749749362190546240596734626745594171540325086418270903156390958817492063940459108934841028734921718351342152598224670602551497995639921650979296052943953491639892805985538785565357751736799561653032725751622522198746331856539251721033316195306373318196300612386897339425222615697620795751869751705629
c = 1206332017436789083799133504302957634035030644841294494992108068042941783794804420630684301945366528832108224264145563741764232409333108261614056154508904583078897178425071831580459193200987943565099780857889864631160747321901113496943710282498262354984634755751858251005566753245882185271726628553508627299
'''

题目分析：
d低位泄露
$$\begin{gathered} e?d=1+k?phi \\ 设s=p+q \\ 则有e?d=k?(n?s+1)+1 \\ 设d的低位为d_l(已知) \\ ?e?d_l\equiv k?(n?s+1)+1(\mathrm{mod}{2}^{265})① \\ 又p^2+s?p+n=p^2?p^2?p?q+n=0② \\ p?①?k?②=e{d}_{l}p\equiv kpn+kp+p?k{p}^2?kn(\mathrm{mod}{2}^{265}) \\ 如此此式子便只有p这个未知数了 \end{gathered}$$

解同余方程式:$e{d}_{l}p\equiv kpn+kp+p?k{p}^2?kn(\mathrm{mod}{2}^{265})$便能得到p的低265位$p_l$
此时高247位未知，而我们又知道以下结论：

p,q 512bit ---- 未知227bit , coppersmith定理可求解 （0.38 <= beta <= 0.44）
p,q 512bit ---- 未知248bit , coppersmith定理可求解 (0.40 <= beta <= 0.49, epsilon = 0.01)
p,q 512bit ---- 未知250bit , coppersmith定理可求解 (beta = 0.5, epsilon = 0.01 , p进行求解且p > q)
p,q1024bit — 未知554bit , coppersmith定理可求解 （0.38 <= beta <= 0.44）
p,q1024bit — 未知496bit , coppersmith定理可求解 (0.40 <= beta <= 0.49, epsilon = 0.01)
p,q1024bit ----未知500bit , coppersmith定理可求解 (beta = 0.5, epsilon = 0.01 , p进行求解且p > q)

所以copper时使用X = 2^428, beta = 0.4, epsilon = 0.01即可求解出完整p，之后便是常规rsa操作得flag

exp:

from tqdm import tqdm
def getFullP(low_p, n):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    p = x*2^265 + low_p
    root = (p-n).monic().small_roots(X = 2^248, beta = 0.4,epsilon = 0.01)
    if root:
        print(root[0])
        return p(root[0])
    return None
    
def phase4(low_d, n, c):
    maybe_p = []
    for k in range(1, 150):
        p = var('p')
        p0 = solve_mod([149*p*low_d  == p + k*(n*p - p^2 - n + p)], 2^265)
        maybe_p += [int(x[0]) for x in p0]
    print(maybe_p)
    
    for x in tqdm(maybe_p):
        P = getFullP(x, n)
        if P: break
    
    P = int(P)
    print(P)
        
    d = inverse_mod(149, (P-1)*(Q-1))
    print(long_to_bytes(int(pow(c,d,n))))

e = 149
low_d = 6001958312144157007304943931113872134090201010357773442954181100786589106572169
n = 88436063749749362190546240596734626745594171540325086418270903156390958817492063940459108934841028734921718351342152598224670602551497995639921650979296052943953491639892805985538785565357751736799561653032725751622522198746331856539251721033316195306373318196300612386897339425222615697620795751869751705629
c = 1206332017436789083799133504302957634035030644841294494992108068042941783794804420630684301945366528832108224264145563741764232409333108261614056154508904583078897178425071831580459193200987943565099780857889864631160747321901113496943710282498262354984634755751858251005566753245882185271726628553508627299

phase4(low_d, n, c)

# flag{827ccb0eea8a706c4c34a16891f84e7b}

Classlcal

题目描述：

p = ZQIUOMCEFZGVRGTBAAAAAJRTKENSNQ
c = WUJQYGCAHAAAAAGDPQXUXHIDTDLIRG

C = OKCZKNCSQ_ULYOKPKW,PL.UXIWX,YCLXZFGBM_SUJLSCOXZT.AIGFZRDCIX,

题目分析：
加密表现如下，其中p，c已知
$$\left(\begin{array}{ccccc}{k}_{11}& k_{12}& k_{13}& k_{14}& k_{15}\\ k_{21}& k_{22}& k_{23}& k_{24}& k_{25}\\ k_{31}& k_{32}& k_{13}& k_{34}& k_{15}\\ k_{41}& k_{42}& k_{43}& k_{44}& k_{45}\\ k_{51}& k_{52}& k_{53}& k_{54}& k_{55}\end{array}\right)\left(\begin{array}{c}{p}_1\\ p_2\\ p_3\\ p_4\\ p_5\end{array}\right)+K=\left(\begin{array}{c}{c}_1\\ c_2\\ c_3\\ c_4\\ c_5\end{array}\right)$$
一共6组，每组加密形式都是这样，密钥矩阵和K是固定的，我们的目标就是求出密钥矩阵和K，然后解C

我们用前五个明文减后五个明文，前五个密文减后五个密文即可消掉K
$$\begin{gathered} 化简一下： \\ k?P_1?K=C_1① \\ k?P_2?K=C_2② \\ k?P_3?K=C_3③ \\ k?P_4?K=C_4④ \\ k?P_5?K=C_5⑤ \\ k?P_6?K=C_6⑥ \\ 前一组减后一组： \\ k?(P_1?P_2)=(C_1?C_2) \\ k?(P_2?P_3)=(C_2?C_3) \\ k?(P_3?P_4)=(C_3?C_4) \\ k?(P_4?P_5)=(C_4?C_5) \\ k?(P_5?P_6)=(C_5?C_6) \end{gathered}$$
(注意P和p,C和c的差别，每个P由5个p组成，C由5个c组成)
得到：

${\left(\begin{array}{ccccc}{k}_{11}& k_{12}& k_{13}& k_{14}& k_{15}\\ k_{21}& k_{22}& k_{23}& k_{24}& k_{25}\\ k_{31}& k_{32}& k_{13}& k_{34}& k_{15}\\ k_{41}& k_{42}& k_{43}& k_{44}& k_{45}\\ k_{51}& k_{52}& k_{53}& k_{54}& k_{55}\end{array}\right)}_{5?5}{\left(\begin{array}{c}{P}_1?P_2\\ P_2?P_3\\ P_3?P_4\\ P_4?P_5\\ P_5?P_6\end{array}\right)}_{5?5}={\left(\begin{array}{c}{C}_1?C_2\\ C_2?C_3\\ C_3?C_4\\ C_4?C_5\\ C_5?C_6\end{array}\right)}_{5?5}$

其中P,C皆已知，那么密钥矩阵便能求出来，之后利用① 便能将K求出来
未知量全部求出，那么由所给的密文C便能求出flag了

先将字符串转换成对应的数字：

p = 'ZQIUOMCEFZGVRGTBAAAAAJRTKENSNQ'
c = 'WUJQYGCAHAAAAAGDPQXUXHIDTDLIRG'
C = 'OKCZKNCSQ_ULYOKPKW,PL.UXIWX,YCLXZFGBM_SUJLSCOXZT.AIGFZRDCIX,'
mapping_dict = {'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4, 'F': 5, 'G': 6, 'H': 7, 'I': 8, 'J': 9, 'K': 10, 'L': 11, 'M': 12, 'N': 13, 'O': 14, 'P': 15, 'Q': 16, 'R': 17, 'S': 18, 'T': 19, 'U': 20, 'V': 21, 'W': 22, 'X': 23, 'Y': 24, 'Z': 25, '_': 26, ',': 27, '.': 28}
pp = [mapping_dict[char] for char in p]
cc = [mapping_dict[char] for char in c]
CC = [mapping_dict[char] for char in C]
print(pp)
print(cc)
print(CC)

完整exp:

mapping_dict = {'A': 0, 'B': 1, 'C': 2, 'D': 3, 'E': 4, 'F': 5, 'G': 6, 'H': 7, 'I': 8, 'J': 9, 'K': 10, 'L': 11, 'M': 12, 'N': 13, 'O': 14, 'P': 15, 'Q': 16, 'R': 17, 'S': 18, 'T': 19, 'U': 20, 'V': 21, 'W': 22, 'X': 23, 'Y': 24, 'Z': 25, '_': 26, ',': 27, '.': 28}
pp = [25, 16, 8, 20, 14, 12, 2, 4, 5, 25, 6, 21, 17, 6, 19, 1, 0, 0, 0, 0, 0, 9, 17, 19, 10, 4, 13, 18, 13, 16]
cc = [22, 20, 9, 16, 24, 6, 2, 0, 7, 0, 0, 0, 0, 0, 6, 3, 15, 16, 23, 20, 23, 7, 8, 3, 19, 3, 11, 8, 17, 6]
CC = [14, 10, 2, 25, 10, 13, 2, 18, 16, 26, 20, 11, 24, 14, 10, 15, 10, 22, 27, 15, 11, 28, 20, 23, 8, 22, 23, 27, 24, 2, 11, 23, 25, 5, 6, 1, 12, 26, 18, 20, 9, 11, 18, 2, 14, 23, 25, 19, 28, 0, 8, 6, 5, 25, 17, 3, 2, 8, 23, 27]

temp1 = []
temp2 = []
for i in range(0,25,5):
    temp1.append([(cc[j] - cc[j+5])%29 for j in range(i,i + 5)])
    temp2.append([(pp[j] - pp[j+5])%29 for j in range(i,i + 5)])
    
# XA = B，求X【求key1】
B = matrix(Zmod(29),temp1).transpose()
A = matrix(Zmod(29),temp2).transpose()
key1 = A.solve_left(B)

#【求key2】
temp3 = matrix(Zmod(29),pp[:5]).transpose()
temp4 = (key1 * temp3).list()
temp5 = cc[:5]
key2 = [(temp5[i] - temp4[i]) % 29 for i in range(5)]

# key1 * P + key2 = C ,求P
m_list = []
for i in range(0,len(CC),5):
    tt = CC[i:i+5]
    ttt = [(tt[j] - key2[j]) % 29 for j in range(5)] 
    B = matrix(Zmod(29),ttt).transpose() # B = C - key2 = key1 * P = B
    # AX = B 求X 【求最终明文】
    P = x.solve_right(B).list()
    m_list.extend(P)

# 【明文数字转换成字母】
for i in m_list:
    for key, value in mapping_dict.items():
        if i == value:
            print(key,end = '')

# QUANTUM_CRYPTOGRAPHY_IS_AN_UNBREAKABLE_SYSTEM_OF_ENCRYPTION.