randrangeの実装をソース読んでみたんですけど（後メルセンヌツイスタのソースも）
randrange(N)はNのビット数以下の乱数をメルセンヌツイスタからもらってもしそれがNより大きいなら取り直すってことやってるんすよ。
今、 $2^{31} < 3133731337 < 2^{32}$
なので、 $3133731337 < メルセンヌ　< 2^{32}$ のときはその値が破棄されてしまうと。output.texに書かれてるのは $メルセンヌ　< 3133731337$ となった時だけです。

つまるところ、我々が入手したデータは穴抜けのデータであり、メルセンヌツイスタの内部情報を参考記事のように簡単には復元できないと。
悲しい。

ということで、メルセンヌツイスタの動作から、穴抜け部分の復元を図ります。
3つの内部状態から新たな内部状態１つを作るので、３つわかってれば復元できます。
このプログラムを考えてたら終わってました。
つうか確率で失敗するのでやる気出ませんでした。
だって $1/4$ くらいでとりなおしがはっせいするんだぜ？運ゲーじゃーん。
まあでもたぶんこの方針だよなあ。

3.harc4
rc4でしたっけ。ストリーム暗号のやつ。
調べてもどんなアルゴなのか出てこないこと多すぎない？
もう次からさっさとソース読みます。

from Crypto.Cipher import ARC4

これの中身見てから再挑戦しよ。

4.shellcode writer
見た記憶がない。やってないとおもわれ。

まあWriteupまちですね。

今回は
・うるせえいいからぐぐれ
・なけりゃソースよめ
の二つができたのでエンジニアっぽいしよしとします。

有名なライブラリとかモジュールって結構読みやすいので、今までなんで忌避してたんだろうって感じです。
エラーメッセージの分岐おおすぎるのがうざいだけであとは超きれい。

レインボーテーブルがわかったので実装してみよっかな。
そしたらまた記事書きますね。
ではまた。

2019-09-30

第0回 RSAへのAttack ～RSAってなに～

Crypto RSAまとめ Cryptoまとめ duck

どうも。duckです。
RSAへのAttackの記事を書くことにしました。

今回の流れ
・RSA暗号の仕組み
・Attackの成功条件
・Attackする場所

RSA暗号の仕組み

公開: $N,e,C$
秘密: $p,q,d$

暗号化
(0)暗号化したい平文mを準備する。
(1)素数 $p,q$ を用意する。( $N=pq$ とおく)
(2) ${\phi(N)}=(p-1)(q-1)$ と互いに素な自然数 $e$ を用意する。
(3) $ed \equiv 1 \pmod {\phi(N)}$ となるdを計算する。
(4) $C \equiv m^e \pmod N$ が暗号文となる。

復号
$C ^ d \bmod N$ を計算するとそれが平文となる。
つまり $m \equiv C ^ d \pmod N$

順に仕組みをみていく。
(0)平文 $ｍ$ の数字化
CTFではpythonのライブラリのCrypto.Util.numberの中の関数
bytes_to_longを用いられることが多い。

(1)素数 $p,q$ の生成
CTFではpythonのライブラリのCrypto.Util.numberの中の関数
getPrime(ビット数)関数が用いられることが多い。
もしくは、秘匿されたファイルから読みだされていることもある。

(2) $e$ の選択
一般的に $e=65537$ (素数)が選ばれることが多い。
$e$ は素数であるから ${\phi(N)}$ が $e$ の倍数でない限り ${\phi(N)}$ と $e$ は互いに素となる。

(3) $d$ の計算
拡張ユークリッドの互除法を用いる。
参考:CTFで使う数学前編 - CTFと共に生きる

(4)特になし。

復号できる理由
本質：オイラーの定理に基づく。
参考：CTFで使う数学後編 - CTFと共に生きる

$ed \equiv 1 \pmod {\phi(N)}$ より、ある整数 $k$ を用いて
$ed=k{\phi(N)}+1$ と書ける。

よって
$C ^d \equiv {(m ^e)}^d \equiv m ^{ed} \equiv m ^ {k{\phi(N)}+1} \equiv m \times {(m ^ k) }^ {\phi(N)} \pmod N$
オイラーの定理により ${(m ^ k) }^ {\phi(N)} \equiv 1 \pmod N$ だから
$C ^ d \equiv m \pmod N$

公開情報 $N,e,C$ のみから平文 $m$ を求めるのが目標である。
現実では適切なパラメータ設定が行われていると考えられるため、公開情報 $N,e,C$ のみから平文 $m$ を求めることはできない。
しかしCTFでは不適切なパラメータが設定されているので、そこをついて平文 $m$ の入手を目指すこととなる。

もう少し具体的に攻撃が成立する条件を見てみよう。

Attackの成功条件

(a) $d$ がわかる。
(b) ${\phi(N)}$ がわかる。
(c) $p$ または $q$ がわかる。
(d)なぜかいきなり $m$ がわかる。

理由
(a) $C ^ d \equiv m \pmod N$ から $m$ がわかる。
(b) ${\phi(N)}$ ,公開情報の $e$ から(3)を実行し $d$ が得られる。以下(a)と同様。
(c) ${\phi(N)}$ が計算できるため。以下(b)と同様。
(d)そりゃそうだろ。

これらのどれかをめざす。
Attackの成功条件がわかったところで、どこを見ればいいのかを教える。
具体的な攻撃手法については次回以降まとめていく。

Attackする場所

青文字は解くときに特に注意している部分である。
それ以外は最後に紹介する参考サイトのほうが見やすいのでそちらを見ることを推奨する。~~（じゃあなんで書いた）~~
(イ)素数 $p,q$ の生成
　－素数 $p,q$ が小さすぎる
　　具体的には $N$ のbit数が~300bit程度だと素因数分解が可能。(c)に帰着。
　　 $N$ のbit数は最低でも1024bit以上がふつう。
　－特殊な素数を使っている
　　フェルマー素数、メルセンヌ素数など有名な素数を使っている場合それを利用して素因数分解できる。(c)に帰着。
　　素数 $p,q$ が秘匿されたファイルから読みだされている場合は試す価値あり。
　－ $p,q$ の差 $p-q$ が小さすぎる
　　フェルマー法により素因数分解できる。(c)に帰着。
　　具体的には上位数十ビットが等しい場合などは試してみるといいだろう。
　－ $p,q$ の差 $p-q$ が大きすぎる、または $p,q$ のうち片方が極端に小さい
　　試し割法で素因数分解できる。(c)に帰着。
　　ふつうは $p,q$ のビット数は同じとするので、 $p,q$ のbit数が違うときは怪しいと思ったほうが良い。
　　素因数分解できない場合でもそこが突破口になりやすい。
(ロ) $e$ の選択
　－ $e$ が小さすぎる
　　中国剰余定理または実数上での $e$ 乗根を求めることで $m$ が直接求まる。(d)に帰着。
　　 $e=2,3$ ならまず間違いなくとける。
　－ $e$ が大きすぎる
　　Wieners attackにより $d$ が求まる。(a)に帰着。
　　具体的には[tex:N}と大差ないくらいの大きさだと怪しい。
　 $e \neq 65537$ のときは、注意すること。
(ハ)平文 $m$ の部分情報の漏洩
　 $m$ の一部分がわかる場合coppersmithの定理(CTFで使う数学後編 - CTFと共に生きる)により $m$ が直接求まる。
　ただし、一部分といっても大半がわからないと解けないことが多い。（ $m$ の半分以上がわかっているとか）(d)に帰着。

最初なのでお世話になっているサイトも紹介しておきます。

攻撃が成立するパラメータの不備がよくまとまっていて神
RSA暗号運用でやってはいけない n のこと #ssmjp
実際の攻撃方法を実装していて神
plain RSAに対する攻撃手法を実装してみる - ももいろテクノロジー

いつもありがとうございます！！！！

具体的な攻撃については次回からやっていきます。

2019-09-29

Bsides CTF 2019 Crypto Writeup(+1) Crypto道場六[9/100]

Crypto writeup duck Crypto道場

どうも。duckです。
1問解けたのでWriteup書きます。

1.BabyRSA
二つのファイルが配られた。
暗号化処理が書いてあるpythonファイルとflagや公開鍵などが書いてあるファイル。
data.txt
Dropbox - data.txt - Simplify your life
encrypt.py
Dropbox - encrypt.py - Simplify your life

まずは数式に書き起こす。ただし長い変数名は嫌いなので短くおく。
$s=\mathit{salt},m=\mathit{magic\_value},e=\mathit{ee},d=\mathit{ed},E=\mathit{enc},N_1=n_1,N_2=n_2,N=pq,C_1=c_1,C_2=c_2,C_3=c_3$ とする。

$s=m \oplus \mathit{FLAG}　\\ N_1=p_1 q_1,N_2=p_2 q_2 \\ C_1 \equiv m^{e_1} \pmod {N_1},C_2 \equiv m^{e_2} \pmod {N_2} \\ ed \equiv 1 \pmod {\phi(N)} \\ C_3 \equiv (p_1p_2)^d \pmod N \\ E = s^e \pmod N$

また、data.txtから
$\mathit{given}:C_1,C_2,C_3,N_1,N_2,e_1,e_2,E,N,d$ 。

$\mathit{FLAG} = s \oplus m$
であるから（ワンタイムパッド） $s,m$ を求めればよい。

(1) $s$ を求める。
$s \equiv E^d \pmod N$ より容易。

s=11295349226607404013471021010341147978232157635167255049065532106494114988908324617162496015788158425092740147662943160785286369117660955898007291303207104

(2) $m$ を求める。
やったことを書く。

(a)Wiener's Attackにより $e$ が求まる。
$d$ と $N$ の大きさがほとんど一緒であるので、Wiener's Attackが使えそうと判断。
codeは
rsa-wiener-attack/Arithmetic.py at master · pablocelayes/rsa-wiener-attack · GitHubのものを使わせてもらった。

e=230194238437088036834072549225817051199

(b) $N_1,N_2$ を素因数分解する。
$C_3 \equiv (p_1 p_2)^d \pmod N , ed \equiv 1 \pmod {\phi(N)}$ であるから
$p_1 p_2 \equiv {C_3}^e \pmod N$

よって
$p_1={\gcd(N_1,p_1 p_2)},q_1=N_1 \div p_1 \\ p_2={\gcd(N_2,p_1 p_2)},q_2=N_2 \div p_2$

通常であればここで ${\phi(N_1)},{\phi(N_2)}$ から
$e_i d_i \equiv 1 \pmod {\phi(N_i)}$ から $d_i$ ( $i=1,2$ )が求まり終了する。

しかし
$\gcd(e_1,{\phi(N_1)})=562 \\ \gcd(e_2,{\phi(N_2)})=166$

であり、互いに素ではない。
よって拡張ユークリッドの互除法により求められるのは
${C_1}' \equiv m ^ {562} \pmod {N_1} \\ {C_2}' \equiv m ^ {166} \pmod {N_2}$

どまりである。
これを $m$ について解くのは計算量的に困難。

(c)2乗なら解ける。
${\rm mod}N_i$ ではなく ${\rm mod}q_i,{\rm mod}p_i$ でなら $m$ が解けるのでは？と思いつく。
それさえ解ければ中国剰余定理で $m$ が求まるはず。（後述）
案の定
$\gcd(\phi{(q_1)},562) = 2$ , $\gcd(\phi{(q_2)},166) = 2$
であったので
$562*d_1 \equiv 2 \pmod {\phi(q_1)}$ , $166 * d_2 \equiv 2 \pmod {\phi(q_2)}$ となる $d_1,d_2$ を用いて
${{C_i}'}^{d_i} \equiv m^2 \pmod {q_i}$ と書ける。

幸運なことに $q_i \bmod 4 = 3$ であったため、 $m= \pm {{C_i}'} ^ {\frac {q_i + 1}{4}} \pmod {q_i}$ とすぐに $m$ が求まった。
（これに関してはそのうち $x^2 \equiv \pmod p$ の解き方としてそのうちまとめたい。オイラーの規準、平方剰余などがでてくるやつだ）

(d)中国式剰余定理で $m$ を求める。
$\gcd{(q_1,q_2)}=1$ であったから、
$x\equiv m \pmod {q_1} \\ x \equiv m \pmod {q_2}$

を両方満たす $x$ は中国式剰余定理ですぐ求まる。
ただ、 $m$ はそれぞれ二つずつ値の候補があったから４通りの候補が出た。

m=[130204528787507505773710923666654908063951342300341290679481831089048475661769804679434320541299854192944581837117095632601550663649704580455239831296388244795699081558529808425017950463304134904449847423117536416689316941082295460328322896891187718311773570823357440044019285149368069722662004114150614222139, 11295349226607404013471021010341147978232157635167255049065532106494114988908324616956647488198714894202591671750797554105930964810174872213148351201383613, 155328494801539469659088679666851276753591192017192346542864403340513541152283708502912394372206759224607578141814677435838429120228926266030995634784793810029010046854516342686756175376802934265799821368172545904638220345216445314249676172852240226067187570748506096577796912199512986620072139171057340043068, 25123966014031963885377756000196368689639849716851055863382572251465065490513903823478073830906905031662996304697581803236878456579221685575755803488405576528660191903390547732759235254646777593507609112310058553481009898249138762245970232608540706470308202516820407331331732981109727072282348205257927204542]

あとは４通りの $m$ について $\mathit{FLAG} = s \oplus m$ を計算し、正しい $\mathit{FLAG}$ を求めるだけだ。

flag:bsides_delhi{JuG1iNg_WiTh_RS4}

はやいとこWiener's Attackと $x^2 \equiv \pmod p$ を理解しないといけない。
解けなかったが、共通カギ暗号もまた出題されていたので、そちらも。

2019-09-17

CTFで使う数学　後編

Crypto duck Cryptoまとめ Crypto数学

どうも。duckです。
後編始めるよ。

ちょっと全体的に難易度が上がるから、前編にもまして証明が雑になるよ。
よくわからんって人はとりあえずcoppersmithの定理だけみておけばいいです。
頻出なんで。
じゃあやっていこうかー。

６．coppersmithの定理　頻度「４」
これ難しいからスルーしてたんだけどCTFで出会った回数が4回目になったときに学ぶ決心をした。
定理を使う条件さえ覚えていれば後はSagemath(数学ライブラリ)が計算してくれるのであんまり気負わず。

条件　・ $N$ は素因子が未知の合成数
　　　・ $N$ の素因子 $b$ が $b \leq N ^ \beta (0 < \beta \leq 1)$
　　　・ $f(x)$ は次数 $\delta$ の1変数モニック多項式（最高次係数が１）
定理： $f(x) \equiv 0 \pmod b (|x| \leq cN^{\frac{\beta^2}{\delta}})$ を満たす解 $x$ は簡単に求まる。

定理の使い方例
① $b \leq N ^ \beta$ から $\beta$ を求める。
② $(|x| \leq cN^{\frac{\beta^2}{\delta}})$ から（c=1とでもしておくとよい）簡単に求まる $x$ の範囲を求める。
③この範囲に求めたい値が含まれれば上の定理を使う。

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)

$X$ は解 $cN^{\frac{\beta^2}{\delta}}$ のこと。

この定理にまつわる自身の論文を快く提供してくださった同期Kに感謝します。
証明は1ミリもブログに書いてないけどな。すまんな。

７．平方剰余　頻度「１」
今のところで出会ったことがほとんどない。

定義： $x^2 \equiv a \pmod N$ となる $x$ が存在するとき $a$ は $N$ を法とする平方剰余であるという。

定理： $a$ が $N$ を法とする平方剰余かどうかは簡単にわかる。

端的に言うと $\mod N$ の世界で $\sqrt{a}$ が存在するかはすぐわかるということ。
証明は平方剰余の相互法則によるが、書かない。
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]

８．中国剰余定理　頻度「３」
まあまあでる。直接ではなくても間接的によくお世話になる。

定理：連立合同式
$x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \quad \vdots\\ x \equiv a_n \pmod {m_n}$
の解 $x$ は $\gcd(m_i,m_j)=1$ ならば $0 \leq x < m_1 m_2 \cdots m_n$ の中に唯一存在する。

答えとなる $x$ を構成することで証明とする。（唯一性の証明は省略）

$m_{ij}^{-1}$ とかいたらそれは $m_i$ の $j$ における逆数という意味で使う。

Garner 法
$x_1 \equiv a_1 \pmod {m_1}$ となる $x_1$ をとってくる。
$x_2 = x_1 + m_1 t_1$ とおき、 $x_2 \equiv a_2 \pmod {m_2}$ となるように $t_1$ を決める。
つまり $x_1 + m_1 t_1 \equiv a_2 \pmod {m_2}$ より $t_1=(a_2-x_1){m_{12}}^{-1}$ とする。
このとき $x_2 \equiv a_1 \pmod {m_1}$ かつ $x_2 \equiv a_2 \pmod {m_2}$
$x_3 = x_2 + m_1 m_2 t_2$ とおき、・・・以下繰り返し。

イメージとしては連立合同式の上から順番に満たすように $x_i$ を拡張していく感じ。

コード：

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暗号の復号計算を高速化するのに使われているが、それは”暗号まとめ”記事にまとめようと思う。

９．オイラーの定理　頻度「1」
フェルマーの定理の拡張。
まずオイラーのトーシェント関数の定義（ファイ関数ともいう）。

定義：自然数 $N$ と互いに素で1以上 $N$ 以下となるものの自然数の個数を $\varphi (N)$ で表す。

本題。

定理： $a,N$ が互いに素ならば $a ^{\varphi(N)} \equiv 1 \pmod N$

証明概略： $N$ と互いに素な数の集合 $A=\{r_1,r_2,\cdots,r_{\varphi(N)}\}(1 \leq r_i \leq N)$ と $B=\{ar_1,ar_2,\cdots,ar_{\varphi(N)}\}$ の集合は $N$ を法として等しい。
なぜならば $ar_i$ は $N$ と互いに素であるから $ar_i \bmod N = r_j$ ( $A$ の集合の要素のどれかと一致)であり $ar_i \not \equiv ar_j \pmod N$ 。(*)
よって $a ^ {\varphi(N)} r_1 r_2 \cdots r_{\varphi(N)} \equiv r_1 r_2 \cdots r_{\varphi(N)} \pmod N$ 。

(*)フェルマーの小定理5.1を参照(CTFで使う数学前編 - CTFと共に生きる)

コメント：
素数 $p$ に対し $\varphi(p)=p-1$ よりこれはフェルマーの定理の拡張である。
またRSAへの応用として $\phi(pq)=(p-1)(q-1)$ となることにも注意。（復号で使う）
トーシェント関数にはほかにも面白い性質があるがここに書くには余白が(ry)

二次合同式についても触れるつもりでしたが、またの機会に。多分そのうちしれっと追記します。
次は”数学を使わないで解けるCrypto問題”、”暗号方式を学ぶ”みたいなタイトルの記事を書きたいです。

2019-09-16

CSAWCTF 2019 Crypto Writeup(+2) Crypto道場五[8/100]

Crypto duck Crypto道場 writeup

どうも。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

起動画面。

f:id:falconctf:20190916113821p:plain — menu

メニュー：
1.RSAで暗号化されたFLAGの表示
2.RSAで暗号化されたfake_flagの表示
3.RSAもどきで暗号化されたfake_flagの表示
4.任意の平文入力をRSAで暗号化してくれる

ただ、1,2,3のうちどれか2回、コマンドを打つと強制終了する。4は無制限。
方針：使うコマンドは1,3一回ずつと4を三回。
(a)2と3と $N$ がわかれば $p$ がわかることを示す。
(b) $N$ を求める。
(c)2をブルートフォースし $p$ を求める。
(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

結局サーバーから返ってくるのは連立方程式

$C_1=m^{e_p} \bmod p = m^e \bmod p \\ C_2=m^{e_q} \bmod q \quad {\rm XOR} \quad fun$

の解 $C=C_2 + h * q$ になる。なぜこの $C$ が上記連立方程式の解になるのかは~~”CTFで使う数学後編”の記事に書くのでそちらを参照のこと。~~
→暗号方式まとめRSA編まで待って。

2を $C_f$ とおく。
$C_f= m^e \bmod p$
を満たすことは明らか。よって、
$C - C_f \equiv 0 \pmod p$ であり $C-C_f$ は $p$ の倍数である。
$N=pq$ ゆえ $\gcd (N,C-C_f)$ から $p$ が求まる。

(b) $N$ を求める。
4から三つのデータを取り、最大公約数を取ることで $N$ は求まる。
こちらからのinputとしては!,#,$を選んだ。
それぞれアスキーコードでは33,35,36に対応する。
数式：サーバーからのリターンを $R_{i}$ とする

$R_{33}={33}^{e} \bmod N \cdots ①\\ R_{35}={35}^{e} \bmod N \cdots ②\\ R_{36}={36}^{e} \bmod N \cdots ③$

（①－②）と（②－③）の最大公約数を取れば、それは $N$ の倍数となる。
小さい素数で割って、 $N$ を求めれば終了。

コード：

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)

$N$ のbit数が2048とわかっているので、乖離していた場合は取り直すべき。

コード：

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=""

これにて $p$ が求まった。

(d)復号する。
$p$ がわかったので $q$ , $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やろうかとか思ってた自分が恥ずかしい。世界は広い。

2019-09-12

CTFで使う数学　前編

Crypto Cryptoまとめ duck Crypto数学

どうも。duckです。
とあるCTF（後で書きます）の過去問解いてたんですが、あまりの数学のできなさに絶望したのでまとめます。
証明は適当につけたのであってるかわかりません。（オイ）
まあわかるっしょっていう条件は書いてなかったり厳密性を重視してなかったりするのでお気を付けくださいませ。
あと個人的にCTFで使う頻度（五段階評価）も書いておきます。まあまだ全然解いてないのであてにはならないですが。
じゃあこっから数学れっつごー。

１．合同式　頻度「５」
ないと死ぬ。Cryptoは整数論でできているのです。
いちいち説明する気にならないので
合同式の意味とよく使う６つの性質 | 高校数学の美しい物語ここらを見ていただければ。

そのうちまとめます。勉強会とか開いたら。（開くとは言っていない）

２．ユークリッドの互除法　頻度「３」

定理： $a,b \in \mathbb N$ の最大公約数は簡単に求められる

詳しいアルゴリズム書くのはめんどいからコード見て。これで $a,b$ の最大公約数が求まります。

def gcd(a,b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

定理の核： $\gcd (a,b) = \gcd (bk + r,b) = \gcd (r,b)$
ただし $a = bk + r(0 < r < a)$

コメント：最大公約数が簡単に計算できることくらいは知っておいたほうがよい。
アルゴリズムは調べれば出てくるし上のコードコピペしてもいいし、お好みで覚えて。

３．拡張ユークリッドの互除法　頻度「４」
RSA暗号に出てくるじゃん。つまり超重要。

定理1： $ax + by = \gcd (a,b)$ の整数解 $(x,y)は計算できる$

これはユークリッドの互除法から構成的に証明できるんだけど、めんどい。
汚いコードおいとくね。（拡張ユークリッドの互除法が入ってる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のコードと一緒に使わないと動かないよ。

暗号的には次の応用が重要。（先にいえ）