Maojui

AIS3 2020 EOF - RSACTR (Crypto, 321)

2020-01-18

Challenge

題目:server.py

Solution

這題有三個選項,給你做三個動作的機會,很明顯每個選項都有用

  1. info
  2. get flag
  3. 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