【picoCTF】EVEN RSA CAN BE BROKEN??? - 偶数Nの性質を突いてRSA暗号を復号

問題概要

picoCTFの「EVEN RSA CAN BE BROKEN???」という問題の解説記事です。

• カテゴリ: Cryptography
• 難易度: Easy

問題文

解説

ステップ1: picoCTFのサーバーに接続

$ nc verbal-sleep.picoctf.net xxxxx
N: 19717589578836383613288380933302915055460046872338736531560971952640046688445811420337222036918341147335263071128959761369934032574988010574766426472259018
e: 65537
cyphertext: 103383222591393288699291000626233579128644528807366610545028605727542178516340706562756939242107082305732087684752037041734072285998617891769121977948199

※ポート番号は問題文に記載されているものを使用してください。

ステップ2: 提供されたencrypt.pyを確認

提供コード（重要な部分）

from Crypto.Util.number import bytes_to_long, inverse
from setup import get_primes

e = 65537

def gen_key(k):
    p,q = get_primes(k//2)
    N = p*q
    d = inverse(e, (p-1)*(q-1))
    return ((N,e), d)

def encrypt(pubkey, m):
    N,e = pubkey
    return pow(bytes_to_long(m.encode('utf-8')), e, N)

def main(flag):
    pubkey, _privkey = gen_key(1024)
    encrypted = encrypt(pubkey, flag)
    return (pubkey[0], encrypted)

このコードから、サーバーが出力している値は以下の通りです。

• N: RSAの法（modulus）。N = p * q
• e: 公開指数（ここでは固定で 65537）
• cyphertext: 平文（フラグ）を整数化して c = pow(m, e, N) を計算したもの

ステップ3: N が偶数であることに着目

• p または q が偶数
• 偶数の素数は 2 しか存在しない

ステップ4: p = 2として秘密鍵を復元

• phi = (p - 1) * (q - 1)（オイラーのトーシェント）
• d は「e の逆元（mod phi）」として求める

ステップ5: 復号してフラグを取得

ここは少し分かりづらいので、手順を細かく分けて整理します。

5-1. まずは値を手元にメモする

• N
• e
• cyphertext（ここでは c として扱います）

5-2. 復号スクリプトを作成して実行（ファイルを作る方法）

N = 19717589578836383613288380933302915055460046872338736531560971952640046688445811420337222036918341147335263071128959761369934032574988010574766426472259018
e = 65537
c = 103383222591393288699291000626233579128644528807366610545028605727542178516340706562756939242107082305732087684752037041734072285998617891769121977948199

p = 2
q = N // 2

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

m = pow(c, d, N)
pt = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(pt.decode())

実行します。

$ python3 decrypt.py

出力例

picoCTF{xxxxx}

※フラグはマスクしています。

5-3. 1回だけならCLIに直接流し込む方法（ワンライナー）

ファイルを作らずに、そのまま標準入力でPythonに渡す方法もあります。

$ python3 - <<'PY'
N = 19717589578836383613288380933302915055460046872338736531560971952640046688445811420337222036918341147335263071128959761369934032574988010574766426472259018
e = 65537
c = 103383222591393288699291000626233579128644528807366610545028605727542178516340706562756939242107082305732087684752037041734072285998617891769121977948199

p = 2
q = N // 2

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

m = pow(c, d, N)
pt = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(pt.decode())
PY

出力例

picoCTF{xxxxx}

※フラグはマスクしています。

使用したコマンドの軽い解説

nc

nc <ホスト> <ポート>

指定したホスト・ポートにTCP接続するコマンドです。 今回のように、接続すると値が表示されるタイプの問題でよく使います。

まとめ

▼ポイントは以下の通りです。

• RSAの N が偶数の場合、素因数に 2 が含まれる可能性が高い
• p = 2 と仮定すると q = N // 2 で簡単に分解できる
• phi を求めて d を復元すれば、復号してフラグを取り出せる