[强网拟态决赛 2023] Crypto

文章目录

- Bad_rsa
- Classlcal

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低位泄露
$phi\\ 设 s = p + q\\ 则有 e * d = k * (n - s + 1) + 1\\ 设d的低位为d_l(已知)\\ \Rightarrow e * d_l \equiv k * (n - s + 1) + 1 \pmod{2^{265}} ①\\ 又 p^2 + s * p + n = p^2 - p^2 - p * q + n = 0②\\ p * ① - k * ② = e d_lp \equiv kpn + kp + p - kp^2 - kn \pmod{2^{265}}\\ 如此此式子便只有p这个未知数了$

解同余方程式: $d_lp \equiv kpn + kp + p - kp^2 - kn \pmod{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已知
$\begin{pmatrix} 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{pmatrix} \begin{pmatrix} p_1\\p_{2}\\p_{3}\\p_{4}\\p_{5}\end{pmatrix}+K= \begin{pmatrix} c_{1}\\c_{2}\\c_{3}\\c_{4}\\c_{5} \end{pmatrix}$
一共6组，每组加密形式都是这样，密钥矩阵和K是固定的，我们的目标就是求出密钥矩阵和K，然后解C

我们用前五个明文减后五个明文，前五个密文减后五个密文即可消掉K
$化简一下：\\ 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)\\$
(注意P和p,C和c的差别，每个P由5个p组成，C由5个c组成)
得到：

$\begin{pmatrix} 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{pmatrix}_{5*5} \begin{pmatrix} P_1 - P_2\\ P_2 - P_3\\ P_3 - P_4\\ P_4 - P_5\\ P_5 - P_6 \end{pmatrix}_{5 * 5}= \begin{pmatrix} C_1 - C_2\\ C_2 - C_3\\ C_3 - C_4\\ C_4 - C_5\\ C_5 - C_6 \end{pmatrix}_{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.