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