wdream的题解

Problem: [鹤城杯 2021]Crazy_Rsa_Tech

# FLAG = bytes_to_long(pad(b"flag{??????}",64))
# def init_key():
#     p, q = getPrime(512), getPrime(512)
#     n = p*q
#     e = 9
#     while(GCD((p-1)*(q-1),e)!=1):
#         p, q = getPrime(512), getPrime(512)
#         n = p*q
#     d = inverse(e,(p-1)*(q-1))
#     return n,e,d

# n_list=list()
# c_list=list()
# for i in range(9):
#     N,e,d=init_key()
#     n_list.append(N)
#     c=pow(FLAG,e,N)
#     c_list.append(pow(FLAG,e,N))
#     assert(pow(c,d,N)==FLAG)
# print("n_list:",n_list)
# print("c_list:",c_list)
​
            
AI代码解释
            
                
            
        

p q都是512bit，n是1024bit，e = 9

后面的部分大致意思就是生成了9组模数n，一共用明文FLAG生成了9组密文c

所以已知c，e，n，记FLAG 为 m，记$N={\Pi }_{i=0}^8{n}_i$

$m^e\equiv c_i(\mathrm{mod}{n}_i)$可以使用CRT中国剩余定理

crt(c_list, n_list)得到最小非负整数解M，M满足$M\equiv m^e(\mathrm{mod}N)$

但是$m^e=m^9<N$所以$m^e=M=crt(c\_list,n\_list)$

再开e次根号得到m，也就是9次。

from Crypto.Util.number import long_to_bytes
n_list = [
]

c_list = [
]
e = 9
# CRT 合并
M = crt(c_list, n_list)
# 整数 9 次方根
m = M.nth_root(e)
print(long_to_bytes(int(m)))
​
            
AI代码解释
            
                
            
        

最后输出b'flag{H0w_Fun_13_HAstads_broadca5t_AtTack!}\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16'