一次合同方程式を解く
はじめに
CTFで暗号の問題をやっているとよく出くわす概念に合同式があるのですが方程式の形で与えられることは少ない上に、解こうとしても特殊な場合(解きやすい)が多く、一般化について考えたことがありませんでした。というわけで今回は一次合同方程式を考察し、そのソルバを実装して実際にCTFで出た問題を解くところまでやろうと思います。
高校レベルの整数論以外の前提知識として不定方程式が可解であることとこれの解の導出(拡張Euclid互除法)がありますが、実装に関しては後者だけ知っていれば問題ありません。
一次合同方程式
今回扱うのはの形の合同方程式になります。整数に対し、をで割った余りがとなるを求めるというものです。まず最初に方程式が解けるかどうかを考察し、次にその解の個数と求め方を示します。
解の存在
次の2通りに分けて可解かどうかを調べます。なお、はの最大公約数を示します。
以下ではと定義します。
まず1. の場合ですが、が互いに素であることからに解が存在します(拡張Euclid互除法とその理論背景を参照)。これらをとおきます。つまり、です。これの両辺にを乗じて変形するととなるため、とおくことでとなります。よってを法としてこれと合同な数は全て解となります。
続いて2. の場合ですが、がの倍数である時とそうでない時を考えます。後者の場合にとなるの存在を仮定するととなる整数が存在します。しかし左辺がの倍数であるのに対し、左辺はの倍数でないとしたので矛盾します。よってがの倍数でない時は解は存在しません。
前者の場合は1. 同様にの解が存在しすると、とおくことでがを満たすことから解が存在することがわかります。
以上よりがの倍数であるなら解は存在することになります。
解の個数
では続いてを法として解の数が幾つあるかを考えます。存在性と同様、2つの場合に分けて考えます。
の場合、求められた解をを法としてとおきます。ここでもう1つの解が存在するとしてとします。それぞれであることから2式の差をとるととなります。は互いに素であることからとなるが存在し、したがってとなります。このをとおいて先程の2式の差をとった式の両辺にかけるととなることからであるため解は結局1つになります。
の可解(がの倍数)の場合、より、となる整数が存在します。これの両辺をで割るととなります。はいずれもの倍数なのでこの式の分数部分は全て整数です。したがってが成り立ちます。なお、が成り立つようなはこの手順を逆に辿ることでが成り立つこともわかります。したがってこの2つの問題は法を無視して整数全体を見ると同一の解を持つことからの解をを法とするように拡張すればの解となります。
が解け、を法として解が1つになることは1. の場合をこの問題に適用できることから明らかです。この解をとします。これを法がの場合に拡張するととなる範囲で整数を用いて表すことができます。このの範囲はであることから解の数は個になります。
以上よりの解は存在する場合は個になります。
実装
↑の2つをそのまま実装します。なお、外部でEuclid互除法と拡張Euclid互除法は実装済みとします(それぞれgcd(a, b)
とext_gcd(a, b)
)
# 可解性 def is_solvable(a, b, n): g = gcd(a, n) return (b % g) == 0 # 解が1つの場合 def solve_one(a, b, n): x_0, _ = ext_gcd(a, n) return (x_0 * b) % n # 全ての解をリストにして返す def solve(a, b, n): a, b = a % n, b % n if not is_solvable(a, b, n): return [] ret = [] g = gcd(a, n) _a, _b, _n = a // g, b // g, n // g _x = solve_one(_a, _b, _n) for i in range(g): ret.append(_x + _n * i) return ret if __name__ == "__main__": print(solve(4, 8, 12)) # [2, 5, 8, 11]
Contrail CTF document_rescueのWriteup
これが解けると何が嬉しいのかというとなんとCTFで使えます。実はこれは半分本当で先日のCTFで出た問題が解けなかったので復習のために勉強してこの記事が生えたという経緯があります。詳しくは↓のWriteup記事の反省欄に書いたのでそちらを参照して欲しいのですが、ここでは先日行われたContrail CTFで出てきたdocument_resuceというCryptoの問題を今回のソルバを利用して解こうと思います。
この問題ではPDFをCFBモードで暗号化しています。その際の暗号化関数は線形合同法を利用しており、具体的には事前に用意された未知の鍵を用いて暗号文ブロックと平文ブロックに対しとしています。CFBモードなので最初のブロックのためのIVが与えられていますがこちらも鍵ファイル中に含まれているので不明です。以降この鍵をと表し、IVをとします。
ここでPDFはマジックナンバーが%PDF
であることからある程度平文を予測できると考えられます。ソースコードを見ると頭8文字は%PDF-9.9
としていたため次のような関係式が成り立ちます。
但し、は%PDF
の16進表記では%-9.9
のそれです、pythonを使うとint.from_bytes(b, "big")
の結果になります。これだけの情報ではを特定するのは難しいのですがPDFのファイル終端が%EOF
であることを利用できないか考えます。実際はパディングされているため平文の最終ブロックは確定しないのですが%EOF, EOF\x00, OF\x00\x00, F\x00\x00\x00
の4つのうちいずれかになります。平文の最終ブロックをとおき、暗号文の末尾2ブロックはとすると合同方程式が追加で得られます。改めて3つの式を並べると次のようになります。この3つの式を利用してを求めることを考えます。
このうち2つ目と3つ目の式の差をとるととなります。これはを求める合同方程式のため、上のソルバを使って解くことが出来ます。実際の解の数はであることから2つ存在し、の候補が4つあることから掛け合わせて8通り考えることになります。このようにして求まった各に対して2つ目の式、あるいは3つ目の式を利用するとが求まります。よって各を1つ目の式に代入するとを求める合同方程式になることから同じくソルバを使って解くことができます。
この実行結果は最終的に11通り存在することからこれら全てのパラメータで復号を試みます。どのPDFも手元のビュアーでは読めなかったのですが、バイナリエディタで中身を見ると1つだけGreat! You have awesome programming skill and knowledge of CFB-mode encryption! Then let's find and use a tool to fix this corrupted header and try to see this PDF file's content :)
という文字が現れるPDFが現れたためオンラインの修復ツールに投げたところ無事にPDFが開けてフラグが出てきました。
フラグはctrctf{f1l3_5truc7ur3_1nf0rm471on_4lw4ys_help_u}
でした。
使用したコードはこちらです↓
from math import ceil, floor def gcd(a, b): if b == 0: return a return gcd(b, a % b) def ext_gcd(a, b): if b == 1: return 0, 1 q = a // b r = a % b next = ext_gcd(b, r) return next[1], next[0] - q * next[1] def is_solvable(a, b, n): g = gcd(a, n) return (b % g) == 0 def solve_one(a, b, n): x_0, _ = ext_gcd(a, n) return (x_0 * b) % n def solve(a, b, n): a, b = a % n, b % n if not is_solvable(a, b, n): return [] ret = [] g = gcd(a, n) _a, _b, _n = a // g, b // g, n // g _x = solve_one(_a, _b, _n) for i in range(g): ret.append(_x + _n * i) return ret def to_num(b): return int.from_bytes(b, "big") def decrypt(a, b, x): with open("flag.www", "rb") as f: cipher_raw = f.read() m = pow(2, 32) c = [] index = 0 while index + 4 <= len(cipher_raw): c.append(int.from_bytes(cipher_raw[index:index + 4], "big")) index += 4 plain = [] for i, _c in enumerate(c): if i != 0: plain.append(((c[i-1] * a + b) % m) ^ c[i]) else: plain.append(((a * x + b) % m) ^ c[i]) # print(plain[0].to_bytes(4, "big")) # print(plain[1].to_bytes(4, "big")) # print(plain[-1].to_bytes(4, "big")) f = open("flag-{}-{}-{}.pdf".format(a, b, x), "wb") for p in plain: f.write(p.to_bytes(4, "big")) f.close() if __name__ == '__main__': with open("flag.www", "rb") as f: cipher_raw = f.read() c = [] index = 0 while index + 4 <= len(cipher_raw): c.append(int.from_bytes(cipher_raw[index:index + 4], "big")) index += 4 plain = list(map(to_num, [b"%PDF", b"-9.9"])) hooter_candidates = list( map(to_num, [b"%EOF", b"EOF\x00", b"OF\x00\x00", b"F\x00\x00\x00"])) m = pow(2, 32) coef1 = (c[0] - c[-2]) % m g = gcd(coef1, m) print(g) abx_list = [] for hooter in hooter_candidates: coef2 = ((plain[1] ^ c[1]) - (hooter ^ c[-1])) % m a_list = solve(coef1, coef2, m) for a in a_list: b = ((plain[1] ^ c[1]) - (c[0] * a)) % m x_list = solve(a, (plain[0]^c[0]) - b, m) for x in x_list: print("[+]: a, b, x -> %d %d %d" % (a, b, x)) decrypt(a, b, x)
実行結果は次のようになります。ちなみにフラグが出てきた値はa, b, x = 2109834763, 3764688820, 268435455
でした。
[+]: a, b, x -> 2134452074 854811907 92870375 [+]: a, b, x -> 2134452074 854811907 2240354023 [+]: a, b, x -> 4281935722 3002295555 92870375 [+]: a, b, x -> 4281935722 3002295555 2240354023 [+]: a, b, x -> 2109834763 3764688820 268435455 [+]: a, b, x -> 4257318411 1617205172 268435455 [+]: a, b, x -> 1049060107 1850361012 1270779903 [+]: a, b, x -> 3196543755 3997844660 1270779903 [+]: a, b, x -> 1202086667 2673427636 2381221887 [+]: a, b, x -> 3349570315 525943988 2381221887
あとがき
当日持っている整数論の知識で解けなくて物凄く悔しい思いをしたのでこのように解くことができて嬉しい一方で、z3のような優秀なソルバで解いてるWriteupが多く、そちらも習得しなくてはならないという気持ちにもなりました。弊チームに最近優秀な暗号担当が生えしばらく触れていませんでしたが、まだまだCrypto問題から学べることは多いので担当の低レイヤーを疎かにしない程度に頑張ろうと思います。
前回の復習記事ではあるものの、CTF関連の記事が続いているので次回も近いうちに真面目な記事が書けると嬉しいです。
参考文献
- 初等整数論講義/第1章/一次合同式 - Wikisource: 合同方程式に関する理論の参考文献
- ContrailCTFで僕が出した問題の想定解法と裏話(今後MyInstructionsを追加します) - Battle for my life: document_rescueの作問者Writeup、z3を使用
- ContrailCTF 2019のwriteup - Szarny.io: document_rescueを同じく整数論的に解いているWriteup、私のものより少ない候補で試していたので数字の出処が気になる