Challenge
題目:server.py
Solution
這題有三個選項,給你做三個動作的機會,很明顯每個選項都有用
- info
- get flag
- encrypt
選擇 info 會傳公鑰 (n,e)
給你
選擇 get flag 就是把 flag encrypt 給你
選擇 encrypt 就是請你輸入明文,他幫你做他的 RSA encrypt
而 encrypt 的方式如下:
def encrypt(self, plain):
if self.mode == self.MODE_CTR:
n, d = self.key
blocksize = 16
cipher = b''
for i in range(0, len(plain), blocksize):
x = self.nonce
y = pow(x, d, n)
z = (y + bytes_to_long(plain[i:i+blocksize])) % n
cipher += z.to_bytes(128, 'big')
self.nonce += 2020 # 2020 happy new year
return cipher
else:
raise NotImplementedError
他並沒有直接加密你的明文,而是把 Nonce 加密起來後加上你的 16 bytes 明文
只是 Nonce 會以 CTR 的形式,不斷的加上 2020。
不過,也因為有 encrypt 的功能所以出現一個問題 ….
如果請他幫忙 encrypt 00
,那就可以得到他的 Encrypted nonce
了
對 … 直接解開就好了 …
得到 nonce
後,我們把 flag 每 128 bytes 切開,可以知道:
FLAG1 : pow( nonce + 2020, d, n) + flag1
FLAG2 : pow( nonce + 4040, d, n) + flag2
FLAG3 : pow( nonce + 6060, d, n) + flag2
解 RSA 時,有個演算法 Coppersmith ,提供我們找出失去的明文:
當我們知道明文的 high bits ,可以輕鬆的找回低位的部分 (miss_part)
$$C = (M + miss_part )^e\ %\ N$$
剛好符合我們的問題,我們遺失的事 - flag
將他的給的 FLAGs 帶入 Coppersmith 就可以解出這些遺失的 flag
FLAG{dIdyousolVEITWIthCoppERsmith}
Script : solve.sage