[plaidctf] Crypto 100




def encrypt(m, N):
    L = numbits(m)
    random.seed()
    r = random.randint(2, N-1)
    x = pow(r, 2, N)
    y = x
    l = 0
    for k in range(0, L):
        l = l << 1
        l |= y & 1
        y = pow(y, 2, N)
    return (m ^ l, y, L)

以上的扣這個是問題的主要部份. 問題的根本建構在 Finite Field上, 隨機挑選一個數字之後, 接續的做次方運算得到下一個數字. 根據要加密文件的 bit 數量, 得到一連串的數字(Sn), 並且只取每個數字的最後一個 bit 來跟本文做 xor 運算而得到密文. 最後會給我們{密文,最後加密數字,本文長度}

舉一個簡單的例子:
  • 給一個 GF(11)的 Finite Field (也就是{0,1,2,3,4,5,6,7,8,9,10})
  • 開始的隨機數字為3.
  • 本文的binary為11010
根據以上條件, 我們可以得到預計要加密的數字串為{3,9,4,5,3}, 取最後一個 bit 得到的加密 key 值為11011. 所以跟本文做 xor 可以得到密文為 00001, 最後加密數字為 9, 而本文長度為 5.


    如果要直接破解這個問題, 問題本身就變成要破解 FF 的平方根問題, 這個問題理論上可以做出來, 網路上也可以找到很多 paper, 然而這個問題並不是要我們朝這個方向進行... 這題官方已經提供給我們一個網站, 像他提供{密文,最後加密數字,本文長度}就會幫我們解密. 但是官方卻限制最後加密數字不能跟題目的一樣. 所以要想辦法繞過這個限制.

    繞過的方法, 就是利用 FF 的特性, 我們只要 shift 一格就可以繞過檢查. 原本的加密數字串為{S0,S1,S2,...,SL-1}, 並且提供給我們 SL當作是最後加密數字, 我們只需要多加密一次變成加密數字串為 {S1,S2,S3,....,SL} 最後加密數字為 SL+1, 並且請官方幫我們解密, 我們就可以得到 shift一格的解密文字.
  • 本文為 m, 原本的加密鑰為 k, 則密文為 c = m xor k, 其中最後加密數字為 A
  • A' = pow(A, 2, N)
  • 送給網站{c, A, L}, 則會給我們假本文 m'= c xor k', 其中 k' = k >> 1 + b, b 是多餘的一個 bit.
  • 同樣的 A'' = pow(A', 2, N) 做上面一樣的操作就可以得到 m''
  • 最後拿 m' xor m'' 就會得到 K = k' xor k''. 我們可以利用他來猜測可能的 k 值.
原因在於 K 的值就是 {k1 xor k2, k2 xor k3, ..., }, 只需要猜測四次 (k0跟k1) 就可以得到所有 k 的可能性. 這比去做 FF 的平方根或者重建整個 FF 的速度還要快.

沒有留言:

張貼留言