第0回 RSAへのAttack ~RSAってなに~
どうも。duckです。
RSAへのAttackの記事を書くことにしました。
今回の流れ
・RSA暗号の仕組み
・Attackの成功条件
・Attackする場所
RSA暗号の仕組み
公開:
秘密:
暗号化
(0)暗号化したい平文mを準備する。
(1)素数を用意する。(とおく)
(2)と互いに素な自然数を用意する。
(3)となるdを計算する。
(4)が暗号文となる。
復号
を計算するとそれが平文となる。
つまり
順に仕組みをみていく。
(0)平文の数字化
CTFではpythonのライブラリのCrypto.Util.numberの中の関数
bytes_to_longを用いられることが多い。
(1)素数の生成
CTFではpythonのライブラリのCrypto.Util.numberの中の関数
getPrime(ビット数)関数が用いられることが多い。
もしくは、秘匿されたファイルから読みだされていることもある。
(2)の選択
一般的に(素数)が選ばれることが多い。
は素数であるからがの倍数でない限りとは互いに素となる。
(3)の計算
拡張ユークリッドの互除法を用いる。
参考:CTFで使う数学 前編 - CTFと共に生きる
(4)特になし。
復号できる理由
本質:オイラーの定理に基づく。
参考:CTFで使う数学 後編 - CTFと共に生きる
より、ある整数を用いて
と書ける。
よって
オイラーの定理によりだから
公開情報のみから平文を求めるのが目標である。
現実では適切なパラメータ設定が行われていると考えられるため、公開情報のみから平文を求めることはできない。
しかしCTFでは不適切なパラメータが設定されているので、そこをついて平文の入手を目指すこととなる。
もう少し具体的に攻撃が成立する条件を見てみよう。
Attackの成功条件
(a)がわかる。(b)がわかる。
(c)またはがわかる。
(d)なぜかいきなりがわかる。
理由
(a) からがわかる。
(b),公開情報のから(3)を実行しが得られる。以下(a)と同様。
(c)が計算できるため。以下(b)と同様。
(d)そりゃそうだろ。
これらのどれかをめざす。
Attackの成功条件がわかったところで、どこを見ればいいのかを教える。
具体的な攻撃手法については次回以降まとめていく。
Attackする場所
青文字は解くときに特に注意している部分である。それ以外は最後に紹介する参考サイトのほうが見やすいのでそちらを見ることを推奨する。
(イ)素数の生成
-素数が小さすぎる
具体的にはのbit数が~300bit程度だと素因数分解が可能。(c)に帰着。
のbit数は最低でも1024bit以上がふつう。
-特殊な素数を使っている
フェルマー素数、メルセンヌ素数など有名な素数を使っている場合それを利用して素因数分解できる。(c)に帰着。
素数が秘匿されたファイルから読みだされている場合は試す価値あり。
-の差が小さすぎる
フェルマー法により素因数分解できる。(c)に帰着。
具体的には上位数十ビットが等しい場合などは試してみるといいだろう。
-の差が大きすぎる、またはのうち片方が極端に小さい
試し割法で素因数分解できる。(c)に帰着。
ふつうはのビット数は同じとするので、のbit数が違うときは怪しいと思ったほうが良い。
素因数分解できない場合でもそこが突破口になりやすい。
(ロ)の選択
-が小さすぎる
中国剰余定理または実数上での乗根を求めることでが直接求まる。(d)に帰着。
ならまず間違いなくとける。
-が大きすぎる
Wieners attackによりが求まる。(a)に帰着。
具体的には[tex:N}と大差ないくらいの大きさだと怪しい。
のときは、注意すること。
(ハ)平文の部分情報の漏洩
の一部分がわかる場合coppersmithの定理(CTFで使う数学 後編 - CTFと共に生きる)によりが直接求まる。
ただし、一部分といっても大半がわからないと解けないことが多い。(の半分以上がわかっているとか)(d)に帰着。
最初なのでお世話になっているサイトも紹介しておきます。
攻撃が成立するパラメータの不備がよくまとまっていて神
RSA暗号運用でやってはいけない n のこと #ssmjp
実際の攻撃方法を実装していて神
plain RSAに対する攻撃手法を実装してみる - ももいろテクノロジー
いつもありがとうございます!!!!
具体的な攻撃については次回からやっていきます。
Bsides CTF 2019 Crypto Writeup(+1) Crypto道場六[9/100]
どうも。duckです。
1問解けたのでWriteup書きます。
1.BabyRSA
二つのファイルが配られた。
暗号化処理が書いてあるpythonファイルとflagや公開鍵などが書いてあるファイル。
data.txt
Dropbox - data.txt - Simplify your life
encrypt.py
Dropbox - encrypt.py - Simplify your life
まずは数式に書き起こす。ただし長い変数名は嫌いなので短くおく。
とする。
また、data.txtから
。
であるから(ワンタイムパッド)を求めればよい。
(1)を求める。
より容易。
s=11295349226607404013471021010341147978232157635167255049065532106494114988908324617162496015788158425092740147662943160785286369117660955898007291303207104
(2)を求める。
やったことを書く。
(a)Wiener's Attackによりが求まる。
との大きさがほとんど一緒であるので、Wiener's Attackが使えそうと判断。
codeは
rsa-wiener-attack/Arithmetic.py at master · pablocelayes/rsa-wiener-attack · GitHubのものを使わせてもらった。
e=230194238437088036834072549225817051199
(b)を素因数分解する。
であるから
よって
通常であればここでから
から()が求まり終了する。
しかし
であり、互いに素ではない。
よって拡張ユークリッドの互除法により求められるのは
どまりである。
これをについて解くのは計算量的に困難。
(c)2乗なら解ける。
ではなくでならが解けるのでは?と思いつく。
それさえ解ければ中国剰余定理でが求まるはず。(後述)
案の定
,
であったので
,となるを用いて
と書ける。
幸運なことにであったため、とすぐにが求まった。
(これに関してはそのうちの解き方としてそのうちまとめたい。オイラーの規準、平方剰余などがでてくるやつだ)
(d)中国式剰余定理でを求める。
であったから、
を両方満たすは中国式剰余定理ですぐ求まる。
ただ、はそれぞれ二つずつ値の候補があったから4通りの候補が出た。
m=[130204528787507505773710923666654908063951342300341290679481831089048475661769804679434320541299854192944581837117095632601550663649704580455239831296388244795699081558529808425017950463304134904449847423117536416689316941082295460328322896891187718311773570823357440044019285149368069722662004114150614222139, 11295349226607404013471021010341147978232157635167255049065532106494114988908324616956647488198714894202591671750797554105930964810174872213148351201383613, 155328494801539469659088679666851276753591192017192346542864403340513541152283708502912394372206759224607578141814677435838429120228926266030995634784793810029010046854516342686756175376802934265799821368172545904638220345216445314249676172852240226067187570748506096577796912199512986620072139171057340043068, 25123966014031963885377756000196368689639849716851055863382572251465065490513903823478073830906905031662996304697581803236878456579221685575755803488405576528660191903390547732759235254646777593507609112310058553481009898249138762245970232608540706470308202516820407331331732981109727072282348205257927204542]
あとは4通りのについてを計算し、正しいを求めるだけだ。
flag:bsides_delhi{JuG1iNg_WiTh_RS4}
はやいとこWiener's Attackとを理解しないといけない。
解けなかったが、共通カギ暗号もまた出題されていたので、そちらも。
CTFで使う数学 後編
どうも。duckです。
後編始めるよ。
ちょっと全体的に難易度が上がるから、前編にもまして証明が雑になるよ。
よくわからんって人はとりあえずcoppersmithの定理だけみておけばいいです。
頻出なんで。
じゃあやっていこうかー。
6.coppersmithの定理 頻度「4」
これ難しいからスルーしてたんだけどCTFで出会った回数が4回目になったときに学ぶ決心をした。
定理を使う条件さえ覚えていれば後はSagemath(数学ライブラリ)が計算してくれるのであんまり気負わず。
定理の使い方例
①からを求める。
②から(c=1とでもしておくとよい)簡単に求まるの範囲を求める。
③この範囲に求めたい値が含まれれば上の定理を使う。
sagemathコード例
sage: N = 1279012345679004320987654321 sage: K = Zmod(N) sage: PR.<x> = PolynomialRing(K) sage: f = x^2 + 78523430 sage: f.small_roots()
small_roots()関数がcoppersmithの定理の計算を勝手にやってくれて、答えの集合の配列を返す。
数字は適当なので気にしないで。ちなみにsmall_roots()は引数も持たせられる。
f.small_roots(X=2^kbits, beta=1/3)
は解のこと。
この定理にまつわる自身の論文を快く提供してくださった同期Kに感謝します。
証明は1ミリもブログに書いてないけどな。すまんな。
7.平方剰余 頻度「1」
今のところで出会ったことがほとんどない。
端的に言うとの世界でが存在するかはすぐわかるということ。
証明は平方剰余の相互法則によるが、書かない。
sagemathでの使い方を述べるにとどめる。
#kronecker(a,N) #1なら平方剰余 sage: kronecker(2,7) 1 #-1なら平方非剰余 sage: kronecker(3,7) -1 #あるNでの平方剰余が全部知りたいとき sage: quadratic_residues(7) [0, 1, 2, 4]
8.中国剰余定理 頻度「3」
まあまあでる。直接ではなくても間接的によくお世話になる。
答えとなるを構成することで証明とする。(唯一性の証明は省略)
とかいたらそれはのにおける逆数という意味で使う。
となるをとってくる。
とおき、となるようにを決める。
つまりよりとする。
このときかつ
とおき、・・・以下繰り返し。
コード:
def inverse(a,N): return extend_gcd(a,N)[0] % N def chinese(a_list,m_list): n=len(a_list) x=a_list[0] m=m_list[0] i = 1 while i < n: x=x+(a_list[i] - x) * inverse(m,m_list[i]) * m m*=m_list[i] i+=1 return x % m
gcd,extend_gcdは自分で定義した関数。詳しくは前編参照。
CTFで使う数学 前編 - CTFと共に生きる
重要な例としてRSA暗号の復号計算を高速化するのに使われているが、それは”暗号まとめ”記事にまとめようと思う。
9.オイラーの定理 頻度「1」
フェルマーの定理の拡張。
まずオイラーのトーシェント関数の定義(ファイ関数ともいう)。
なぜならばはと互いに素であるから(の集合の要素のどれかと一致)であり。(*)
よって。
コメント:
素数に対しよりこれはフェルマーの定理の拡張である。
またRSAへの応用としてとなることにも注意。(復号で使う)
トーシェント関数にはほかにも面白い性質があるがここに書くには余白が(ry)
二次合同式についても触れるつもりでしたが、またの機会に。多分そのうちしれっと追記します。
次は”数学を使わないで解けるCrypto問題”、”暗号方式を学ぶ”みたいなタイトルの記事を書きたいです。
CSAWCTF 2019 Crypto Writeup(+2) Crypto道場五[8/100]
どうも。duckです。
csawCTFはCrypto問題多かったですね。
とりあえず解けた二つ(Crypto400 Fault BoxとCrypto300 SuperCurve)だけwriteup書きます。
1.Crypto300 SuperCurve
楕円曲線暗号です。
配られたファイルはこちら。ローカルで動くので解けなかった方はぜひ。
server.py
Dropbox - server.py - Simplify your life
supercurve.py
Dropbox - supercurve.py - Simplify your life
単純にsecretkeyを見つければFLAGを返してくれる。
パラメータが素人目に見ても残念なのであっさりブルートフォースできた。
for secret in range(curve.order): # (13815, 1298)はサーバーからのpub if curve.mult(secret, base) == (13815, 1298): print(secret)
getしたsecretkeyをサーバーにぶん投げればおしまい。
flag{use_good_params}
あまりにあんまりなのでこれを機に楕円曲線暗号について勉強しようかな。きっとそれが運営の狙いに違いない。
2.Crypto400 Fault Box
上が3分で解けたのと引き換えにこっちは16時間かかりました。
知識が足りんかったね。
配られたファイルをローカルで動くように加工しておいたものはこちら。
server.py
Dropbox - server.py - Simplify your life
起動画面。
メニュー:
1.RSAで暗号化されたFLAGの表示
2.RSAで暗号化されたfake_flagの表示
3.RSAもどきで暗号化されたfake_flagの表示
4.任意の平文入力をRSAで暗号化してくれる
ただ、1,2,3のうちどれか2回、コマンドを打つと強制終了する。4は無制限。
方針:使うコマンドは1,3一回ずつと4を三回。
(a)2と3とがわかればがわかることを示す。
(b)を求める。
(c)2をブルートフォースしを求める。
(d)復号する。
(a)
まず3のencrypto部分を抜き出す。ただし変数名を一部変えている。(p→mとした。self.pと紛らわしいため)
def TEST_CRT_encrypt(self, m, fun=0): ep = inverse(self.d, self.p-1) eq = inverse(self.d, self.q-1) qinv = inverse(self.q, self.p) c1 = pow(m, ep, self.p) c2 = pow(m, eq, self.q) ^ fun h = (qinv * (c1 - c2)) % self.p c = c2 + h*self.q return c
結局サーバーから返ってくるのは連立方程式
→暗号方式まとめRSA編まで待って。
2をとおく。
を満たすことは明らか。よって、
でありはの倍数である。
ゆえからが求まる。
(b)を求める。
4から三つのデータを取り、最大公約数を取ることでは求まる。
こちらからのinputとしては!,#,$を選んだ。
それぞれアスキーコードでは33,35,36に対応する。
数式:サーバーからのリターンをとする
小さい素数で割って、を求めれば終了。
コード:
def gcd(a,b): while b != 0: r = a % b a = b b = r return a e=65537 a33=0x4FC26FA362C01A29D736A0BCEAB5BE9C1862C88ADDECD9E7B6F82E5714CC6C8089963C1239B4DB9B9D1A5D1D9D4A7338EDC23129CDF387108FC76BC9501FA29C77BEEFC86515F206AA0F2962959ED2DBDC6EBCB172C20DBE7E6D359570094DC552691FAC046BD4EEA07AC48A09B4D849861F063E66CCF61D54937CE4D09EF5C617C606B3D30AD6D798653E2CF7675AA0701888B6B10641DE349C22192E8F3A95A871C004A17F5191F1F3E07BE1699BB94166254A1746EB4DBF3B7FB120C6B9E906B41E6971C335CE55F5A56EB755F7ED373070F084EA01CA509D2EDF4A324A9CDA53EAB49AF839C6C1EDD3542D8D4B3876D95BA0E3D8396003100711316F64 a35=0x39AC520C665B84FEC4E9E74992A53E77EBECB3A7E356D2CACB7A4E3A4192BC4CF9C41FEB27E97A7F101B01FDB37FD3D64AFFD943F96B0329F8C99180EC8157E83BAC86E1E3E4761540FF82FB4884E1992D32211C50EF5621A22F092C7700F17DF6C59E122860E0973C23F197B3AA767D76B8EADA6B3A73CA87DEDED3C3C066FF4CDE0542626C49CB7AD34BF2F77EAC4F2F85690CFA046E8083E2A4A517C187D19BF10BE0D84646F0B2E8C51DCAE729CB410BA97F85F7175C7BEA7CBEED681B27CACFC15A64FF2D8AF0A9CB6FBE95EC2D61D3A3D70572FCC5333B836FF36CE2608FE45716F15B78A353606BBD2B4EFD2285A1BDB0C39C200A42F2DC1C8F6C38D a36=0x1755F0E5CD015A5DCC76E285D9B25D8360567461AFCF63976B6F1ECFFCCF7114FCB8FB7E5CFD74C37CE2B21078E56AA764439F98B41CC913FB59077AFDF0723B6E5694B1A8D990F91A617B0C448227EAD04145FE41277A9C2183B58F92AEB582CA1BC7A276F09C4B3ACE0E2AA892F8C483647AA7D4D18BBF84AC06DDF3FD671A69AB9E4F7A9E2F194F621ACF2886EB032C31B54170FDD35A0032F512BB31CE820F07BCD9734B2B71B63BB44E5E063C1A326E5560EB60CD41973DD918E766D14F2C3E0EEE609214FF6CDB9369CDB66EBCB252E7DB491520A1CB83C1CAB48285654D8C8F8ADAF809D34CD1F4AEFDC9031ABB40A1850A27E439387354D438CE1C3 pow33=pow(33,e) pow35=pow(35,e) pow36=pow(36,e) N=gcd(pow35 - a35 - pow33 + a33,pow36 - pow35 - a36 + a35) prime_list=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101] for prime in prime_list: while N % prime == 0: N = N // prime print(prime) print(hex(N)) print(len(str(hex(N)))*4)
のbit数が2048とわかっているので、乖離していた場合は取り直すべき。
(c)2をブルートフォースしを求める。
残念ながら2はサーバーから取れないので、自分で作る。
幸い平文の形はほとんどわかっているため大したことない。
コード:
N=0x4f4834ffa488e1c782f91942a71544b8aea3d28d86408d54a625315538e455d3ecfe69cf9b8bf3ddaa65ac65604270bd38af00f0f2f1efeb6f818ae87832dde30ed9468b3e85501f36fc6ea2140eae996152394dc7e697441192ecb258207b75af50d436856efe68b38198199b057487e339bb70eedd95ea0efa208e4a4982848c7c09668d021c80e5a932becb81c8101efe71a0a270124923272588b292cc32b032d01956c609d1470fab26855547081d9a7a4972eb0e3af918f5063147b30f4ec3791ec9c6e9be0bc8cda591725a17ceef60e648ed692456bec1a4b0367fe5c18020e9e09fa80084c1bc0931644a933bea3990ca9f830377af5e4c8f92777 e=0x10001 C=0x38CB3043F98E1F6D09A1A1D5D81322E785737C306B717365DC6FD9F8340366A191D6B9255E8363B8259894BD20886F43A26D14CC701659A170F76B039DF4E6F7D51BA8DFCA050CDB1DDD19B3ABDE9B7E7DE4EF44498BAAD25DEF46167583864AA4CDE729BA8924939C9FD960EEF68A6AFF0808B5D42B18B63E63CAFF6AACA179AA0E0E7D2D19A2CB99F568770CE70BE8D1FC14770C08079DC0E6001C3650CA9BC94F62CEF917A4534A4257DD29CAA893654358A52939B6CA73D803D6738A323FAFDC5CD15853415627825CE5983D807CFD35446468232CCB8A7DC8EDC4996A9600590F23C5A76F2B9339270B548E13240E5C9F43736F4491EDAA20424CCA538 li=["0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"] #fake_flagに対して総当たりする BF="" for i in li: BF+=i for j in li: BF+=j for k in li: BF+=k fake_flag="fake_flag{00000000000000000000000000000"+BF+"}" m=s2n(fake_flag) Cf=pow(m,e,N) if gcd(Cf-C,N) != 1: print("p:{%d}" % gcd(Cf-C,N)) print("Cf:{%x}" % Cf) BF=BF[0:2] BF=BF[0] BF=""
これにてが求まった。
(d)復号する。
がわかったので,ももとまる。ゆえに復号可能。
コード:
def extend_gcd(a,b): k_list=[] while b != gcd(a,b): r = a % b k_list.append((a - r) // b) a = b b = r k_list.reverse() y = 1 x = 0 for k in k_list: temp_y = y y = x - k * temp_y x = temp_y return [x,y] N=0x4f4834ffa488e1c782f91942a71544b8aea3d28d86408d54a625315538e455d3ecfe69cf9b8bf3ddaa65ac65604270bd38af00f0f2f1efeb6f818ae87832dde30ed9468b3e85501f36fc6ea2140eae996152394dc7e697441192ecb258207b75af50d436856efe68b38198199b057487e339bb70eedd95ea0efa208e4a4982848c7c09668d021c80e5a932becb81c8101efe71a0a270124923272588b292cc32b032d01956c609d1470fab26855547081d9a7a4972eb0e3af918f5063147b30f4ec3791ec9c6e9be0bc8cda591725a17ceef60e648ed692456bec1a4b0367fe5c18020e9e09fa80084c1bc0931644a933bea3990ca9f830377af5e4c8f92777 p=146121412489499472018936606208560315649851850426210311487767280785113784146895230548028829336346860550793966332799881971944233778584359574153755251587931570761602782385240314394277542506686618532791786610113830452217010923218599464860941149784418258798996522026079976590154467841339783864766395145168554744133 q=N//p e=0x10001 phi=(p-1)*(q-1) C=0x37480606FE2F01C9C09D173E841AB32158ADBD156077B6D0A27F2FBC5AB5EA071B19769DB8FAD69DB4857967BC97A9A5E66F2E965235656550B6780A13BAAB236CD6E7C56E09E3F8F34642885725A8B27FE810B085451FB726FE064DED15A65AAC1958D11E8AF4FAB98ADD0F31286B75FB01C9B2F85E15CB2FE22140747CFBA317C7E3AFC9E0A02CBD78C110AC503D8E94ED3E60C359B56EB1D9D29091EF1C81C21267517A5BAABEF7A688436E8726782CC28D5C40E1F42D879BEFD06A935AFA5C55A92EF0A62A92F459BF97A8B784ADF3A0FE1FBD44B4FFDC95A7E40765CCA8ADDE6CB0F9E62F4013D804ED835D65B78C09F90C9A00B8354FB22F9C21115CC d=extend_gcd(e,phi)[0] print(n2s(pow(C,d,N)))
flag{ooo000_f4ul7y_4nd_pr3d1c74bl3_000ooo}
共通カギ暗号、楕円曲線暗号、RSAパディングについて理解が甘いので調べてまとめます。
あとはコードが渡されないエスパー問題もよくわからんのでWriteup読みます。
いやあもうCryptoいけんじゃね?Webやろうかとか思ってた自分が恥ずかしい。世界は広い。
CTFで使う数学 前編
どうも。duckです。
とあるCTF(後で書きます)の過去問解いてたんですが、あまりの数学のできなさに絶望したのでまとめます。
証明は適当につけたのであってるかわかりません。(オイ)
まあわかるっしょっていう条件は書いてなかったり厳密性を重視してなかったりするのでお気を付けくださいませ。
あと個人的にCTFで使う頻度(五段階評価)も書いておきます。まあまだ全然解いてないのであてにはならないですが。
じゃあこっから数学れっつごー。
1.合同式 頻度「5」
ないと死ぬ。Cryptoは整数論でできているのです。
いちいち説明する気にならないので
合同式の意味とよく使う6つの性質 | 高校数学の美しい物語ここらを見ていただければ。
そのうちまとめます。勉強会とか開いたら。(開くとは言っていない)
2.ユークリッドの互除法 頻度「3」
def gcd(a,b): while b != 0: r = a % b a = b b = r return a
ただし
ここでかつでを考えると、が最大公約数であることに反する。
コメント:最大公約数が簡単に計算できることくらいは知っておいたほうがよい。
アルゴリズムは調べれば出てくるし上のコードコピペしてもいいし、お好みで覚えて。
3.拡張ユークリッドの互除法 頻度「4」
RSA暗号に出てくるじゃん。つまり超重要。
汚いコードおいとくね。(拡張ユークリッドの互除法が入ってるpythonモジュールなくない?)
def extend_gcd(a,b): k_list=[] while b != gcd(a,b): r = a % b k_list.append((a - r) // b) a = b b = r k_list.reverse() y = 1 x = 0 for k in k_list: temp_y = y y = x - k * temp_y x = temp_y return [x,y]
ちなみに上のgcdのコードと一緒に使わないと動かないよ。
暗号的には次の応用が重要。(先にいえ)
の整数解は計算できる。
。
最右辺と最左辺に対してをとれば定理2を得る。
コメント:RSAに出てくることもさることながら、この定理の便利なところは逆数が求まるところですね。
上記のを生かす問題がめちゃあります。
4.のときをとして使っていい 頻度「2」
数式でそれっぽく書くとこう。
コメント:を知りたいけどが秘密鍵でわからんって時に使えます。
はが公開鍵なので求められること多し。
言われりゃ当然なんだけど結構盲点。
5.フェルマーの小定理 頻度「2」
今のところそんなに見てないけどもっと活躍してもいい気がする。
証明ついでに整数論の常識として知っておくとよさそう(忘れてたがw)なものを証明しておく。
5.1 互いに素なら割ったら余りはバラバラ
は互いに素だからだがこれはに矛盾。
これを用いたフェルマーの小定理の証明
両辺でわる。
もういっこ
5.2 素数pの二項係数は1じゃなかったらの倍数
であるがは素数でよりの倍数。
後編は、オイラーの定理、平方剰余、coppersmith'sの定理、型の二次合同式の解(だっけ?)などを予定してます。
まあちょっと難易度は上がるけどcoppersmith'sの定理とかは頻出なので、よければ後編もお付き合いください。
N1CTF 2019 Crypto Writeup(+1) Crypto道場四[6/100]
どうも。duckです。
N1CTFも解いてました。
Cryptoが2題あったなか1題だけ解けた(悔しい)のでWriteup書きます。
Part3-BabyRSA
なんでPart3なんだとかツッコミはいろいろあるけど解いていきましょう。
配られたファイルはこちら。
暗号化
Dropbox - BabyRSA.py - Simplify your life
暗号文
Dropbox - flag.enc - Simplify your life
短いので暗号化のpythonファイルははっちゃいます。
#!/usr/bin/env python2 # -*- coding: utf-8 -*- from Crypto.Util import number import random from secret import flag N = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629 e = 0x10001 m = number.bytes_to_long(flag) with open('flag.enc', 'w') as f: while m: padding = random.randint(0, 2**1000) ** 2 message = padding << 1 + m % 2 cipher = pow(message, e, N) f.write(hex(cipher)+'\n') m /= 2
平文bitを下から順に1bitずつパディング入れながら暗号化してるだけですね。
Nがめちゃでかいのと、パディングもめちゃでかいのでこれどーすんのって感じです。
Crypto問題は困ったら(というかいつもだいたい)紙に起こしてみるようにしてます。
ということで数式になおしちゃうぞ☆。
とおく。
なので結局
です。
重要なのがmは0or1ということです。
んんん?
mが0の時は大変なことが起きますね。
はい。平方剰余です。
平方剰余の相互法則がありますから
を満たすが存在するかはすぐに判定できます。
つまり今回はが平方剰余であるかどうかを調べるとが0か1か判定できます。
計算にはSagemathを使いました。
コードはどっかに消えてしまったので見つかれば載せます。
すべてのchipherに対して平方剰余だったら0平方剰余でなかったら1を出力する用にfor文回すとかだったと思います。
下位ビットから求まっていくことに注意すれば解けました。
flag:N1CTF{You_can_leak_the_jacobi_symbol_from_RSA}
フラッグのjacobiはヤコビ記号のことです。平方剰余の時に出てきます。
ついでにいうとヤコビ記号の拡張としてルジャンドル記号もいます。たしか。
TMCTF2019 Writeup Wildcard 100
どうも。duckです。
TMCTFやりました。
ぱっと見Cryptoがなくてテンション下がりましたが1題解けたのでWriteup書きます。
・Wildcard 100
配られたのは3と6の手書き画像が3万個くらいあるファイル。
Dropbox - data.zip - Simplify your life
こんなん。
問題文によると、
1.3と6の画像を分ける。
2.そのあとそれぞれのユニークなファイルを数える。
3.flagはTMCTF{3の画像の数_6の画像の数}
としろとのことなのでやりました。
MISCとかに近い感じですね。
1.3と6を分ける
人力で分けるのはつらすぎるので、問題文に書いてある通りクラスタリングアルゴリズムを使います。
まあ端的に言えば機械学習です。
いい感じのサイトを見つけたのでコードを使わせていただく。
scikit-learnで国旗画像をクラスタリングして似ているものを探す │ Web備忘録
modifyしたやつ。
import os import shutil import numpy as np from PIL import Image from skimage import data from sklearn.cluster import KMeans # 1. RGBに変換して保存する for path in os.listdir('./data'): img = Image.open(f'./data/{path}') img = img.convert('RGB') img.save(f'./convert/{path}') # 2. 3次元配列の画像データを2次元配列のデータに変換 array=np.array([path for path in os.listdir('./convert')]) feature = np.array([data.imread('./convert/'+path) for path in array]) feature = feature.reshape(len(feature), -1).astype(np.float64) # 3. 学習(2種類のグループにクラスタリングする) model = KMeans(n_clusters=2).fit(feature) # 4. 学習結果のラベル labels = model.labels_ # 5. 学習結果(クラスタリング結果の表示 + ラベルごとにフォルダ分け) for label, path in zip(labels, os.listdir('./convert')): os.makedirs(f"./cluster/{label}", exist_ok=True) shutil.copyfile(f"./data/{path}",f"./cluster/{label}/{path}") print(label, path)
ちなみにこれサーキットラーンっていうライブラリ使ってます。
あとはてテンサーフローとかも有名ですよね。
まあそれはさておき、これで3と6のデータをよりわけることができましたとさ。
3が16768個で6が17254個でした。
はじめてやったけど教師なし学習ってこんなにきれいに分けられるのね。少しビビった。
2.ユニークなファイルを数える
どうすんだこれ。
バイナリで比較すりゃいいかと思って↓のコード書いた。
import numpy as np def openread(path): a = open(path,"rb") img = a.read() a.close() return img path='./0' array=np.array([openread(path) for path in os.listdir(path)]) set = set(array) print(len(set))
結果的にはこれでできてなかった。
phoenixによると、バイナリが違うのに画像として同じファイルが3の画像に一個あったらしいので
それを考慮して
flag:TMCTF{14962_347}
正直作問ミスかと思いました。phoenixがいてよかった。
引き続きN1CTFのWriteupも書かなきゃ。(終了まであと2時間あるけど諦め体制)