Mawa Town

Mawaという人が作る小さな町でMawaTownです。技術と音楽が好き。

CTF、RSA暗号解読問題。大きな数の桁数をPythonでカウントする

サイバーセキュリティプログラミング ―Pythonで学ぶハッカーの思考

サイバーセキュリティプログラミング ―Pythonで学ぶハッカーの思考

RSA暗号の強度はモジュロのとする数(2つの素数の積)の桁数によって変わる

これの2問目を勉強中。もう数日経過。

SECCON Beginners CTF 2018 Write-up

RSA暗号の仕組みが大枠については理解できてきた。

この記事がよかった

解読法と素因数分解 – まいとう情報通信研究会

上記記事から引用すると、 「現在(2003 年かな?)のRSA暗号では素数素数を掛け合わせた後(法とする数)が 310 桁以上にもなる数を用いています。」

「2003 年の年末時点では素数素数を掛けた数が 174 桁の数が、100 台の業務用コンピュータで協調計算させて 3 ヶ月で素因数分解できることが実証されています」

つまりまとめると、

  • 2003年時点で、174桁の素数の積はすでに危険 
  • 2003年時点で、310桁の素数の積は実用的
  • こんかいのCTF4bは77桁でmsieveで2分で計算できる

状況このサイトの引用の引用をすると、わかります。

Electronic Journal: ●「RSA暗号は因数分解の原理使用」(EJ第4661号)

         スパコン 千倍高速コン 量子コンピュータ
因数分解/2百桁 約10年    約3日       数分
因数分解/1万桁 約千億年   約1億年   数時間~数日
                ──竹内茂樹著の前掲書より

これらが事実だとすると、量子コンピュータが実用段階に入るまではRSA暗号は単純に桁数を1万桁くらいまで増やせばいいこともわかります。なるほど・・・

CTFでの対策

以上の調査から、CTFで出てくるRSA暗号は正攻法で溶ける場合は、100桁以下で出題されそうだということがわかるので、その際の判断基準になる素数の積の桁数をpythonでちょっと測るという方法をメモしておきます。

#直感的にわかりやすい方法
>>> s = str("97139961312384239075080721131188244842051515305572003521287545456189235939577")
>>> list(s)
['9', '7', '1', '3', '9', '9', '6', '1', '3', '1', '2', '3', '8', '4', '2', '3', '9', '0', '7', '5', '0', '8', '0', '7', '2', '1', '1', '3', '1', '1', '8', '8', '2', '4', '4', '8', '4', '2', '0', '5', '1', '5', '1', '5', '3', '0', '5', '5', '7', '2', '0', '0', '3', '5', '2', '1', '2', '8', '7', '5', '4', '5', '4', '5', '6', '1', '8', '9', '2', '3', '5', '9', '3', '9', '5', '7', '7']
>>> sl = list(s)
>>> len(sl)
77

#単純に文字列にlenをかけてもでました・・・苦笑
>>> len(s)
77

77桁、これなら解ける!と判断すればいいわけですね。