Author：Hcamael

date： 2016-11-28 20:26:26

注：更多 HCTF 題目可以在此找到：https://github.com/hduisa/HCTF2016

今年犯懶了所以只出了3題RSA的密碼學題目, 出題思路來源于協會上一屆的學長 @Mystery Of Panda 關于RSA后門的畢業設計.

Crypto So Interesting

題目: https://github.com/Hcamael/ctf-library/tree/master/RSA1

payload: https://github.com/Hcamael/ctf-library/blob/master/RSA1/rsa1_payload.py

出題時預測的分數在300分左右, 不過看完選手的wp后發現這題出現了重大失誤, 現在來看, 這題只值150分左右, 但是實際情況只有23個隊解出了該題.

本題思路來源: 基于隱藏指數的RSA-HSDβ算法, 全稱為隱藏小私有指數δ的RSA后門密鑰生成算法.

該算法依賴于wiener小指數攻擊方法

后門生成流程:

hctf_rsa1

其中β是在2^(k-1) ± 2^(k/2)范圍內的素數, 轉置函數的作用是在β非常大的情況下, 返回值可以認為是PRP(Pseudo-Random Permutation). 轉置函數可以有好幾種形式, 我選取的是一種比較簡單的轉置函數.

從上面的流程可以看出這題非常的簡單, 要逆向也是很容易的, 所以該題為本屆HCTF密碼學的簽到題

逆向思路:

hctf_rsa1_2

從上圖可以看出本題只涉及到了wiener算法, 難度差不多是150左右

出題時本來是準備考兩種算法的, 一種是wiener算法, 一種是, payload中的divide_pq函數, 已知e, d, n質因數分解p和q(http://www.di-mgt.com.au/rsa_factorize_n.html)

原本設計著算出(?, δ)后, 根據(?, δ, n)分解出q和p, 但是出題失誤, 導致只需要wiener算法就能getflag

PS1: 不過還是出現了非預期, ROIS的dalao利用wiener算法分解出p和q, https://github.com/Hcamael/ctf-library/blob/master/RSA1/rsa_s.py

PS2: 基于隱藏指數的RSA后門生成算法除了本題涉及的還有RSA-HSPEβ和RSA-HSEβ

Crypto So Cool

題目: https://github.com/Hcamael/ctf-library/tree/master/RSA2 payload:

出題時預測的分數在400分左右, 實際情況只有7個隊解出了該題. 和預測差不多, 最后放了一波hint, 要不然可能會更少.

本題思路來源: 基于隱藏素數因子的RSA-HPβ算法

該后門算法依賴于Coppersmith partial information attack算法, sage實現該算法

后門生成流程: hctf_rsa2_1

該算法的核心在于把p的前半部分比特隱寫到n中

τ的長度為k/16比特

μ的長度為5k/16比特

λ的長度為5k/8比特

所以n的長度為k比特

p * (q xor random(k/8比特長度))的前3k/8比特的值是不變的

所以可以成功把τ, μ隱寫到n中

逆向思路:

hctf_rsa2_2

該題的難點主要在于Coppersmith partial information attack算法, 能在放hint前做出的隊伍都是在github上找到了該算法的腳本 https://github.com/Gao-Chuan/RSA-and-LLL-attacks

Crypto So Amazing

題目: https://github.com/Hcamael/ctf-library/tree/master/RSA3

payload:

出題時預測的分數在450分左右, 不過卻沒有能做出來, 我知道的幾個隊都是被上一題的腳本給坑了

本題思路來源: 基于有限域F(2^m)上橢圓曲線的RSA后門生成算法

流程圖懶得畫了, 上一題的后門算法看懂了, 這題去看代碼也不難, 主要是通過Diffie–Hellman key exchange算法生成私鑰作為種子生成偽隨機數, 私鑰很好求, 本題的難點跟上題一樣同樣在于Coppersmith partial information attack算法

上一題我故意改簡單了, 已知p的前640比特, 所以可以很容易通過https://github.com/Gao-Chuan/RSA-and-LLL-attacks這個腳本恢復出完整的p

但是這題已知p的前576bit, github上的那個腳本就跑不出來了

這部分是出題時無意間挖出的坑, 因為我并不知道github上的這個腳本, 在我預想中能做出rsa2的基本都是能做出rsa3的

這題還有一個坑點

hctf_rsa_keng2 hctf_rsa_keng1

sage和python 用相同的seed生成的隨機數不一樣, 所以在payload中我使用了python生成隨機數

總結

本屆HCTF的Crypto計劃的考點是Coppersmith partial information attack算法和Riemann's hypothesis and tests for primality算法, 不過無奈由于出題失誤第二個算法沒考成

RSA后門相關的論文可參考:

  • Crépeau C, Slakmon A. Simple backdoors for RSA key generation[J]. Topics in Cryptology—CT-RSA 2003, 2003, 2612: 403-416.
  • Young, A., Yung, M. A Space Efficient Backdoor in RSA and its Applications[J]. Preneel, B., Tavares, S. (eds.) SAC 2005, 2005, 3897: 128-143.
  • Tzung-Her Chen, Tsung-Hao Hung. A Comprehensive Study of Backdoors f or RSA Key Generation[R]. Cryptology and Information Security Conference, 2010.

Paper 本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.jmbmsq.com/128/