duckが送るBeginners CTF 2019 Go RSA（Crypto)の解説

どうもduckです。今日はGo RSAについて書くよ。
名前から見てわかる通り、公開鍵暗号の１種であるRSA暗号がわからないと解けない。
公開鍵暗号については↓を見るかググって。
公開鍵暗号方式とは？初心者でもわかる公開鍵暗号方…｜Udemy メディア

まずはざっくりRSAについて数式部分を書くよ。アタックするからには理解しておきたい。
平文を $m$ ,暗号文を $c$ ,公開鍵 $N,e$ ,秘密鍵 $d$ とする。
具体的なアルゴリズムの流れを見よう。
（１）受信側： $p,q$ (十分大きな素数)を選び $N=p*q$ とする。（任意）
（２）受信側： $\phi(N) = (p-1)*(q-1)$ を計算する。（ $\phi(N)$ はオイラーのトーシェント関数と呼ばれ、定義があるが今はこの形のみ知っていれば十分）
（３）受信側： $\phi(N)$ と互いに素な整数 $e$ をもってくる。（任意）
（４）受信側： $e * d \equiv 1 (mod \phi(N))$ となる $d$ を求める。（拡張ユークリッドの互除法を用いる）
（５）受信側：公開鍵 $N,e$ を公開。
（６）送信側： $c = m ^{e} (mod N)$ と暗号文を作成し、送り付ける。
（７）受信側： $m = c ^{d} (mod N)$ で復号でき平文をゲットできる。

通常RSAへのアタックは秘密鍵dを求め、暗号文を解読することが考えられる。
正しく運用されていれば安全であるが、以下のサイト（おすすめ）に挙げられるようなパラメータの設定ミスをすると解読されうる。
CTFではそう言った問題がでるのだろうか？（ちなみにCryptoのBitFlipではその中の脆弱性を突く問題が出た）

RSA暗号運用でやってはいけない n のこと #ssmjp from sonickun

www.slideshare.net

さて、では実際に問題を見よう。
Server: nc 133.242.17.175 1337と問題文に書かれている。
Linuxのnc(ネットキャット？)コマンドで接続しよう。

f:id:falconctf:20190528203001p:plain — GoRSA

まずEncypted　flag is~と書いてあるから、これを複合すればよいことがわかる。問題文でNを忘れたといっていたからNがわかれば解けそうと思っておく。
次に最後の行を見よう。The D was~と書いてある。おそらくこれが秘密鍵だろう。
真ん中部分はユーザー入力である。こちらが入れた数字に対し、謎の数字が返ってくるようだ。
Encyptedflag,D,ユーザー入力により返ってくる値は再接続のたびに変わるようだ。
つまり我々は、３回までのユーザー入力からヒントを得てNを計算すればよいのだろう。
頑張ろう。

ユーザー入力が何を返しているのかがよくわからないのでまずは実験してみる。
その結果、
(a)いつでも１に対しては１が返ってくる。
(b)同じ接続の中で同じ数字を入れると同じ値が返ってくる。
(c)1を除いた入力に対して、大体同じ桁数の値が返ってくる。
などの特徴があることが分かった。

(b)から乱数などは使われていなそうだし,(a)から何かのべき乗計算をしているのではないかと推測できる。
また(c)からmodを取っているのではという推測もたつ。

これらの推測と上で説明したRSAの式たちを見比べると
$m ^{e} (mod N)$ とかか？と勘繰る。
つまり
$（ユーザー入力）^{e} (mod N)$ が返ってきてそうである。

この仮定の下でNを求めに行こう。
我々が入手できるのは以下の３本の式をみたすinput,rの組である。
$r1 \equiv \mathit{input1} ^{e} (mod N)$
$r2 \equiv \mathit{input2} ^{e} (mod N)$
$r3 \equiv \mathit{input3} ^{e} (mod N)$
input1,2,3:ユーザー入力、r1,r2,r3:サーバーから返ってくる値

inputを操作してNを顕現させたい。
こういう任意で入力できる問題は大体小さい数字をinputとするとか、２のべきをinputとするとかだとうまくいくことが多い。
またmodで悩んだときは $=$ を使った形に直すとうまくいくことも多い。（特に数学よくわからないという人にお勧めする）
なんともひどい誘導だが以下のようにすればNが求まる。

inputとして2,3を与える。
$r1 \equiv 2 ^{e} (mod N)$
$r2 \equiv 3 ^{e} (mod N)$
これは適当な整数 $k,k'$ を用いて
$r1 = N * k + 2 ^ e$
$r2 = N * k' + 3 ^ e$
と書ける。 $2^e,3^e$ を移項すると
$r1 - 2 ^ e= N * k$
$r2 - 3 ^ e= N * k'$
となる。お分かりだろうか？これでNが求まるのだと。我々は勝利したのだと。
公約数を思い出してほしい。
$r1 - 2 ^ e$ と $r2 - 3 ^ e$ の約数に明らかにNがある！やったぜ。
追記：
書き忘れていましたが、RSAでは一般的に $e=65537$ が用いられることが一般的です。
それを使いましょう。

最大公約数はユークリッドの互除法というアルゴリズムで高速に求まる。
わからない人は学習指導要領が改定されて高校生でも知ってるからなんとか学んで。

一つだけ注意しておくと、場合によってはNの整数倍が出てきてしまうことだ。
具体的には $k$ と $k'$ が互いに素ではない場合である。

でてきたN で
$flag = (\mathit{encryptedflag}) ^{d} (mod N)$
をしてもうまくFLAGが出ないときは、違うペアで試してみるとよい。

まあ私もまだやってないんだけどな！！
おつかれさま！また明日！！！！！

追記：いままでずっとFLAG書くの忘れてた。この回のだけ残ってたので貼っておく。
ctf4b{f1nd_7he_p4ramet3rs}

コード

from Crypto.Util.number import long_to_bytes
import math

c=17085620552658351183335544500690226272875422158935145341165358891244918062440861767294934344129747923141668732715787177751203261627026230386846774546801758980449060209320668104704097944761232115359564279944744011306082649286738268431655969673959744882964166437946605686952999392726525064814877455046451725768410312677212123398538560508582810195854081569284454616942253143100785505524167586197713206797113052644900411469422688939261982981855377987421758621965591995651651907064794890066406751092949615529766196252331712555809200696136040227513088824530815886117265362591775970066168663851386432407675346081685681927303
r1=12308943287801278381602271020636811688003973209453971581897097872964067773128210282456593395262732270249597048332555708886509308319520920180598650511766799712167512259642431520797141790111692065487078128961600689554367757339155513577144978675218793446249701301839641500569661759646423276187542173318171335382960662774233945196912603079740368273195927210668950566249353140103271649493388077952820446391920593020564832067217333892843371485574515498385351718470670460084994536203053240439442202272531830723505883179658297522435407455008248311187789781960113589834827112974168260506676775743411648452439899496100115579052
r2=2266282824131486468448037400097649751436638343554890873042053537566051913016220134485956663087061113434331598112257987671237397919781153037511303664236178026024200716300256313054976795440759304679065940565652927875017851134819722783392228160931697899128129053901710489789174445944014043443083527638965765809070488225452982880922703011627801716957978130236512493237537609220292483693697781504935020101279551815050569381943159352285456791072657310654958418397051221153029472723065900747600963890428868830367126410421411370704517816919980344041449903545200031548407512798483005492350803089508282331827149736642020562720
d=1814452580735375349943862720618828918630139915423974587850653785462197560999774344107135368454555043491667375552314392616309506004814918478288708383302285286685970221339255810252747773103059121031264059575772453212207545840235008436247634620933941004726742219846507737410336486611203816257479343986488367114011777255284708000213494879044090517505540067938866432994071508106192379566964836729181005004378702445684759533988544066532056379172318125748705772688436663116204079306930926328994293354010739696046248305808409576809006078527713033315527061213274532299699148742370572758989921371532108833619290755313406817153

e=65537
N = math.gcd(r1-pow(2,e),r2-pow(3,e))
m = pow(c,d,N)
print(long_to_bytes(m))