3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

【Crypto】SECCON Beginners 2018 WriteUp@東京都立産業技術高専

Last updated at Posted at 2018-10-06

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

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?