SECCON Beginners 2018 おつかれさまでした。
初心者向けのCTF演習のCrypto問題のWriteUpです。さっくり書き故、誤字脱字あると思いますがご容赦。

一応蛇足も加えておきます。

2018/10/8 追記

文字の誤字脱字多かったため修正

Factoring

N = 6300099813268620937のとき、p+qの値はいくつでしょう。

いくつか解法があります。一応、今回のワークショップ内で話になっていた暗号方式がRSAであったことを踏まえてフェルマー法による解法。

fermat.py

# フェルマー法
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乗)

一番簡単な方法はこちら

easiest.py


print(pow(2,4805,97))

……が、一応ワークショップで紹介されていたフェルマーの小定理を使った例も残しておきます。

fermat_little.py

# フェルマー法
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を復号しましょう。

simple_rsa.py

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で復号可能！

atack_rsa.py


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つが大事だなと改めて思いました。