Tokyo Westerns CTF 2017 Crypto64: BabyDLP Writeup

題目提供了兩個常數 \(g, p\) 及一個 oracle,我們可以輸入 \(m\),它會算出 \(g^{m\oplus s} (\text{mod} p)\) 的值。我們需要利用這個 oracle 來得到 \(s\)。

這題很簡單,我們可以嘗試 \(m = 1\)、\(m = 2\)、\(m = 4\)、\(m = 8\) 等等。為什麼?

設 \(s = 2^n s_n + 2^{n-1} s_{n-1} + … + 2 s_1 + s_0\) (即 \(s_ns_{n-1}…s_1s_0\) 為 \(s\) 的二進制表達式)。

如果 \(s_k = 1\),那麼我們輸入 \(m = 2^k\) 的時候會得到 \(g^{s – 2^k} (\text{mod} p)\) 的值 - 而 \(g^{s – 2^k} \times g^{2^k} \equiv g^s (\text{mod} p)\)。

相反,如果 \(s_k = 0\),輸入 \(m = 2^k\) 則會得到 \(g^{s + 2^k} (\text{mod} p)\),乘上 \(g^{2^k}\) 之後也不會等於 \(g^s\)。

所以利用這點來找出 \(s\),也就是 flag - TWCTF{0f97c1c3ac2aedbd7fb8cd39d50f2b561d31f770} :

 


發表迴響