VXCTF 2nd Crypto2000: Good Old Days 1-2 Writeup

這次我用的是旁門左道,如果想知道 intended solution 的話,請找 harrier。

第一個版本的 source code 如下,第二個版本大同小異,只是提供了更少的資料。

不過不要緊,我們要的資訊就只有 highlight 了的那些:

是的,就只需要 ciphertext 就夠了。

首先說明一下整個程序是怎樣運作:

Key generation:

  • 生成一個約 256 bits 的質數 \(p\)
  • 生成兩個亂數 \(2 \leq a, b < p\) 使得 \(a + b > p\)

加密 (\(m\rightarrow c\)):

  • 在 message 前後各自加上最多 1000 個字 (ASCII 不限)
  • 把所有字元一個一個字傳換成 ASCII code (\(m = m_1 m_2 … m_k\)、\(0 \leq m_i < 256\))
  • 逐個算出 \(c_i \equiv a m_i + b (\text{mod }p)\)

我的旁門左道的條件比較苛刻:

  1. 加入雜訊後的 plaintext 需要有 ASCII code 為 0x00, 0x01, 0x02, …,  0xFF
  2. \(p \leq 2a + b < 2p\)

如果第一個條件成立的話,我們可以枚舉 0x00、0x01 及 0x02 各自對應的 ciphertext。設它們為 \(c_0\)、\(c_1\) 及 \(c_2\),那麼\(c_0 \equiv b (\text{mod }p)\)、\(c_1 \equiv a + b (\text{mod }p)\)、\(c_2 \equiv 2a + b (\text{mod }p)\)。

由於 \(a < p\) 及 \(p < a + b < 2p\) ,我們有 \(c_0 = b\) 及 \(c_1 = a + b – p\)。

加上 \(p \leq 2a + b < 2p\) 這個條件的話,我們同時也有 \(c_2 = 2a + b – p\)。

對於每個枚舉的 \(c_0, c_1, c_2\),我們可以得出 \(a = c_2 – c_1\),\(b = c_0\) 及 \(p = c_0 + c_2 – 2 c_1\)。

然後我們要做的事就是看看\(3a + b (\text{mod }p)\)、\(4a + b (\text{mod }p)\)、…、\(255a + b (\text{mod }p)\) 在不在 ciphertext space 裡面。如果在的話,我們幾乎可以肯定 \(a, b, p\) 就是題目生成的那組。

最後就是寫一個 lookup table 找回對應的 plaintext。

 


發表迴響