CTF、RSA暗号解読問題。大きな数の桁数をPythonでカウントする
サイバーセキュリティプログラミング ―Pythonで学ぶハッカーの思考
- 作者: Justin Seitz,青木一史,新井悠,一瀬小夜,岩村誠,川古谷裕平,星澤裕二
- 出版社/メーカー: オライリージャパン
- 発売日: 2015/10/24
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (11件) を見る
RSA暗号の強度はモジュロのとする数(2つの素数の積)の桁数によって変わる
これの2問目を勉強中。もう数日経過。
SECCON Beginners CTF 2018 Write-up
RSA暗号の仕組みが大枠については理解できてきた。
この記事がよかった
上記記事から引用すると、 「現在(2003 年かな?)のRSA暗号では素数と素数を掛け合わせた後(法とする数)が 310 桁以上にもなる数を用いています。」
「2003 年の年末時点では素数と素数を掛けた数が 174 桁の数が、100 台の業務用コンピュータで協調計算させて 3 ヶ月で素因数分解できることが実証されています」
つまりまとめると、
状況このサイトの引用の引用をすると、わかります。
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桁、これなら解ける!と判断すればいいわけですね。