MawaLog

一日一日、楽しく生きる。技術と音楽が好き。

RSA暗号解読問題を解く(前編)[CTF for Beginners 2018]"RSA is Power"

セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-

セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-

経緯

この記事を元に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

2:Nをmsieveで素因数分解すると2つの素数になる。

$ ./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になるということころまでわかりました。

続きは次回

k-mawa.hateblo.jp

参考記事

bias.hateblo.jp

SECCON Beginners CTF 2018 Write-up