RSA暗号解読問題を解く(前編)[CTF for Beginners 2018]"RSA is Power"
セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-
- 作者: 碓井利宣,竹迫良範,廣田一貴,保要隆明,前田優人,美濃圭佑,三村聡志,八木橋優,SECCON実行委員会
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/09/30
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (4件) を見る
経緯
この記事を元にCTF復習中 SECCON Beginners CTF 2018 Write-up
2問目
N = 97139961312384239075080721131188244842051515305572003521287545456189235939577 E = 65537 C = 77361455127455996572404451221401510145575776233122006907198858022042920987316
という3つの数字が並ぶ。わかったところまでメモる。
手順
1:Cは末尾が6。_%2
も(_%2)%2
も0なので2素数の積ではない。モジュロには不適。 Eは桁数が少ないのでRSA暗号のモジュロにするには不適(そもそも実際素数なので素数の積になりえない)なので、Eはたぶん公開鍵だろうなとあたりをつける。でNがモジュロだとあたりをつける。で素因数分解。このとき77桁なので、まあ素因数分解できるか
bit数を測る:桁数じゃなくてビット数をカウントして計算量を測る場合。
>>> s = "97139961312384239075080721131188244842051515305572003521287545456189235939577" >>> bin(int(s)) '0b1101011011000011010001010000101111000110001110110000000000011110000100101000011111100011100010110110101110011101101011100011011010111111001101011011101011110011100100011011001010011111001010011000110010101010110111011110000111011111101011100100100011111001' >>> len(bin(int(s))) 258 #258bit
2258 の情報量ということですね。
情報量のメモ。 ビット
参考まで
>>> len(bin(0)) 3 >>> len(bin(10)) 6 >>> len(bin(100)) 9 >>> len(bin(100000)) 19
$ ./msieve -e -p -q -v "97139961312384239075080721131188244842051515305572003521287545456189235939577" ぶわーっと始まる recovered 18 nontrivial dependencies p39 factor: 299681192390656691733849646142066664329 p39 factor: 324144336644773773047359441106332937713 elapsed time 00:02:49
で、素数の積となる組み合わせPとQは、299681192390656691733849646142066664329と324144336644773773047359441106332937713になるということころまでわかりました。
続きは次回