HITB GSEC CTF 2017 Crypto881: Hack in the Card I – II Writeup

這次有關 RSA 的題目都是比較經典的。題目分成兩部分:

  • 第一部份提供 oscilloscope 測量的電壓 (Voltage),明顯是 power attack;
  • 第二部分 public key 所用的 \(n\) 跟第一部份相同。由於我們得到這個 \(n\) 對應的其中一對密鑰 \(e’, d’\),我們可以因式分解 \(n = pq\),繼而得到這部分的 \(e\) 所對應的 \(d\)。

第一部分

RSA 加密或者解密時都需要算出形如 \(a^k (\text{mod}n)\) 的表達式。眾所周知,沒有人會用 \(\mathcal{O}(k)\) 的算法來計算它 - 我們可以用 \(\mathcal{O}(\text{log }k)\) 把結果算出來:

計算單數的 \(k\) 時,以上算法會比計算雙數時多出一個乘法運算。有什麼分別?下圖是 oscilloscope 對於 0 和 1 的 waveform:

圖片來源:https://en.wikipedia.org/wiki/Power_analysis

由上圖所見,0 和 1 在 oscilloscope 裡分別是「高低」和「高高低」,所以我們可以把題目給定的波形轉成由 0 和 1 組成的序列。

另外,考慮上述的算法是怎樣算出 \(2^{11} (\text{mod} 37)\) 的:

記住次序是 top-down 的,所以我們得到 0-1 序列後需要把它的次序倒轉,才會得到 \(d\) 的二進制表達式。

得到了 \(d\) 後,解密是非常簡單的:

第二部分

這部分的 \(n\) 是跟第一部份的一樣。由於我們已經有一組 \((e’, d’\)),我們可以用算法找出 \(n\) 的因式分解。

得出 \(n = pq\) 後,對於 \(e\) 有 \(d \equiv e^{-1} (\text{mod}(p-1)(q-1))\)。我們用 extended Euclidean’s algorithm 即可得出 \(d\)。解密得到 flag:

 


發表迴響