SECCON Beginners 2018 おつかれさまでした。
初心者向けのCTF演習のCrypto問題のWriteUpです。さっくり書き故、誤字脱字あると思いますがご容赦。
一応蛇足も加えておきます。
2018/10/8 追記
文字の誤字脱字多かったため修正
Factoring
N = 6300099813268620937のとき、p+qの値はいくつでしょう。
いくつか解法があります。一応、今回のワークショップ内で話になっていた暗号方式がRSAであったことを踏まえてフェルマー法による解法。
# フェルマー法
import math
"""
# よく使う場面
- Nを素因数分解する必要がある
- Nがふたつの素数の積(= p*q)であることが既知
- pとqのビット数が同じ(または非常に近い)と予想される
# 蛇足
- スタンダードなRSAの公開鍵Nの素因数分解が必要ならまずフェルマー法をやってみる
"""
def is_square(n):
# 平方数を48で割った余りは0, 1, 4, 9, 16, 25, 33, 36のいずれか(平方剰余)
if not n % 48 in (0, 1, 4, 9, 16, 25, 33, 36):
return False
# nの平方根の近似整数を取得
x = math.floor(pow(n, 0.5))
return x*x == n
def fermat_method(n):
# nの平方根の近似整数を取得
sqrt = math.floor(pow(n, 0.5))
b = sqrt*sqrt - n
# 条件がTrueになるとき, b2は平方数
# -> m*m = a*a - nが成り立ち、nの素因数分解完了
while not is_square(b):
sqrt += 1
b = sqrt*sqrt - n
return sqrt - math.floor(pow(b, 0.5))
if __name__ == '__main__':
N = 6300099813268620937
p = fermat_method(N)
if p:
print(p, N/p, p + N/p)
else:
print("%d is prime" % N)
今回のこの程度のサイズのNであれば試し割り算でも計算できそうですね。
Go Fast (98)
2^4805 mod 97の値を計算してください。(2の4805乗)
一番簡単な方法はこちら
print(pow(2,4805,97))
……が、一応ワークショップで紹介されていたフェルマーの小定理を使った例も残しておきます。
# フェルマー法
import math
"""
# フェルマーの小定理
> pが素数であれば、a^(p-1) mod p == 1
# 蛇足
n == q * (p-1) + rのとき
a^n == a^(q*(p-1)+r)
== (a^(p-1))^q * a^r
となる(中学生レベル)
"""
# フェルマーの小定理を用いてa^n % p を求める
def fermat_little(a, n, p):
# 今はpが素数であることを前提とする
# if not is_prime(p):
# return False
# この処理では必ず1が表示される
# q = n // (p-1)
# print(pow(n, q*(p-1), p))
r = n % (p-1)
return pow(a, r, p)
if __name__ == '__main__':
a, n, p = 2, 4805, 97
print(fermat_little(a, n, p))
SimpleRSA (10)
p = 256745764655464715289043834762721676979
q = 200871874067534114215487430360232242973
e = 65537
C = 27530772477056816049880105308464106546033634204256035445852769149755729787021
もう少し問題文を書いてくれても良いのでは……？初心者には問題を読み解くのが少し苦しいと思いました。
ワークショップでRSAをやっていたこととタイトルから、おそらくp,q,eを用いてflagをRSAで暗号化してCを得たのであろうと推測。
p, q, eがあれば秘密鍵を生成できるので、秘密鍵を生成して暗号文Cを復号しましょう。
from Crypto.Util import number
"""
# RSA暗号
公開鍵(誰に見られても問題ない)
- N
- e
暗号化
送りたい文字列Mに対して暗号文Cを
C = M ^ e mod N
で求める
秘密鍵(自分だけの情報、知られるとアウト)
(- p, q) <- そもそも捨てる、知られると秘密鍵を生成できる(今回はこの例)
- d <- 知られると復号できる
- Φ(N) <- 知られると(p-1)(q-1) == Φ(N), N = p*qの等式からp+qが求まり
2次方程式の解と係数の関係に基づいてp,qが求められる
秘密鍵の作り方
公開鍵eを決定したのち
e * d == 1 mod Φ(N)
を満たすdを求める
復号
暗号文Cに対応する平文Mは以下を満たす
M == C ^ d mod N
"""
# オイラーのφ関数はN = p*qのとき(p-1)(q-1)
def totient(p, q):
return (p-1)*(q-1)
# 秘密鍵dによる復号
def decrypt(C, d, N):
return pow(C, d, N)
# 与えられたパラメータ
p = 256745764655464715289043834762721676979
q = 200871874067534114215487430360232242973
e = 65537
C = 27530772477056816049880105308464106546033634204256035445852769149755729787021
N = p*q
phi = totient(p, q)
# ed = 1 mod Φ(N) を満たすdを求める
d = number.inverse(e, phi)
# 復号
m = decrypt(C, d, N)
# 最後に、バイト文字列に戻す(過去1敗)
print(number.long_to_bytes(m))
ちなみに
e = 65537
とあるが、これはeは公開鍵(誰でも読み取っていい)なので計算の効率の良い2進数10000000000000001(=65537)を取ってきているから。RSA暗号でよく使われる値。
Find primes
問題では、とあるスクリプトとテキストファイルが配布されていた
スクリプト
計19個の素数
p = [p1, ... , p10]
q = [q1, ... , q9, pi] : (iは1...10のランダムな整数)
を用いて公開鍵e, N1, N2, ..., N10を作り、flagをRSAで暗号化して暗号文を出力
テキストファイル
スクリプトを走らせた結果得られた10個の暗号文とそれに用いた10個の公開鍵Nが入っていた。(伝われ)
この問題では用いられる素数p1,...q9は1024bitであるため力業で解を得るのは難しく、また秘密鍵も得られていないため容易には解けない。
そこで、肝となるのがqの中に含まれる素数piである。
これによって、pとqの組み合わせで生まれる10個のNの中に最大公約数が1でない要素の組み合わせが存在しているはず。
具体的には以下
pi にはp1が選ばれたと仮定
N1 = p1 * q1, N2 = p2 * q2, ..., N9 = p9 * q9, N10 = p10 * p1 とする
このとき、N1とN10の最大公約数はp1( != 1 )となる。( = p1は計算可能)
したがって(e, N1)で暗号化された平文はp1とN1/p1で復号可能！
from Crypto.Util import number
from itertools import combinations
"""
# RSAの脆弱性
有名なものとして
- p, qのどちらかが小さい
- p, qが同じくらいのサイズ
- 異なるeで同じ平文を暗号化
- 素数を使いまわした異なるNで同じ平文を暗号化
などがある。
今回は最後の脆弱性を抱えた問題。
GCD(N1, N2) => g != 1のとき、gは素数であり秘密鍵pに等しい。(N1, N2はp*q)
なのでもう片方の秘密鍵qはN1/pで求まる。(N2/pでも良い)
"""
# オイラーのφ関数はN = p*qのとき(p-1)(q-1)
def totient(p, q):
return (p-1)*(q-1)
# 秘密鍵dによる復号
def decrypt(C, d, N):
return pow(C, d, N)
# パラメータ
e = 65537
# 桁数多いので数値は省略(テキストファイルの中身そのもの)
params = [
(n1, c1),
(n2, c2),
...
(n10, c10)
]
for param1, param2 in combinations(params, 2):
p = number.GCD(param1[0], param2[0])
# pは1でない == param1[0]とparam2[0]に共通因子がある => 共通因子pは秘密鍵の素数
if p != 1:
q = param1[0]/p
C = param1[1]
# こちらでも良い
# q = param2[0]/p
# C = param2[1]
break
if p == 1:
print('no answer')
else:
# SimpleRSAと同じ処理
N = p*q
phi = totient(p, q)
d = number.inverse(e, phi)
m = decrypt(C, d, N)
print(number.long_to_bytes(m))
雑感
SimpleRSAとFind Primesは初心者には難しい内容だと感じました。SimpleRSAはRSAによる暗号化の流れを把握していれば方針は立つと思います。
Cryptoは数学の知識とコーディング力、そして脆弱性に関する知識の3つが大事だなと改めて思いました。