Encrypted-P

2026/03/27の課題である encrypted-p に関するWriteUp

概要

PSAという暗号方式に関する性質を利用したCTF。 RSA暗号の秘密鍵の材料（素数 p）が間接的に漏洩することで、暗号が解読されてしまうという問題。 該当リンク

コード解説

このコードは「RSA暗号でFLAGを暗号化して、暗号文と公開鍵を出力する」というものです。 順を追って見ていきましょう。

1. 鍵の材料を作る

# FLAG(平文)を整数に変換
m = bytes_to_long(os.getenv("FLAG", "Alpaca{REDACTED}").encode())
# 512ビットの巨大な素数を2つ生成
p = getPrime(512)
q = getPrime(512)

RSAでは、まず2つの巨大な素数 p と q を用意します。 この2つは「秘密鍵の材料」であり、絶対に外部に漏らしてはいけません。

2. 公開鍵を作る

n = p * q       # p と q を掛け合わせた値（公開する）
e = 65537       # 暗号化に使う指数（公開する）

n と e のペアが「公開鍵」です。 n は誰でも知ることができますが、n を p と q に分解（素因数分解）するのは天文学的に難しい、というのがRSAの安全性の根拠です。

3. 暗号化する

c1 = pow(m, e, n)   # FLAG を暗号化
c2 = pow(p, e, n)   # ← ここが問題！ p を暗号化して公開している

c1 はFLAGの暗号文で、これ自体は普通のRSA暗号化です。 しかし c2 は 素数 p をRSAで暗号化したもの です。 一見「暗号化してるから安全では？」と思いますが、ここに致命的な脆弱性があります（後述）。

攻略手順

c2 = pow(p, e, n)
   = p^e mod n

p = gcd(c2, n)  # c2 と n の最大公約数を取れば p が求まる

from math import gcd
from Crypto.Util.number import long_to_bytes

# 与えられた値（問題の出力）
n = 128951281305588745177398666629581199631058485864966572111701156939267450500461527200369468573426631836231657529006961512763025035249904387307870700668785175314961077286667575866244736508708739350133249344265003181706608358459178127198312194766478590857197619309351373290212091866616979044480765203518287880231
e = 65537
c1 = 54584723810742525332842344311000852588602730106620353769829210613572823180653937528363454036086393048077676074759109894318976797773129779455362292423939574494740847776236268109008206494521359064552627895524641251831367406439093727541197347429866604384086035828634392203445282651867426691962843204295565063110
c2 = 1275053191052289311623571273789725721667869401026425104630717220610992153205486162391947489891617470912363657454340060212607860799074584462787330453990545702469206778960092594048128793161645208662908619530980792732439888903918520029492353921753829884907087387587329511678531595496711467707727494180922007863

# Step 1: c2 と n の最大公約数で p を復元
p = gcd(c2, n)
q = n // p

# Step 2: 秘密鍵 d を計算
#   φ(n) = (p-1)(q-1) を求め、e の逆元を取る
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# Step 3: FLAG を復号
m = pow(c1, d, n)
print(long_to_bytes(m).decode())

必要となる前提知識

RSA暗号とは

公開鍵暗号の一種で、インターネット通信（HTTPS）などで広く使われています。

公開鍵 を使って誰でも暗号化できる 秘密鍵 を持つ人だけが復号できる

Webエンジニアなら馴染みのある「SSH鍵」や「SSL証明書」も、この仕組みの上に成り立っています。

RSA鍵の作り方（ざっくり）

1. 巨大な素数 p と q をランダムに生成する
2. n = p × q を計算する（これが公開鍵の一部）
3. φ(n) = (p-1) × (q-1) を計算する（後述のオイラーのトーシェント関数）
4. e（通常 65537）を暗号化指数として選ぶ
5. d = e の逆元 mod φ(n) を計算する（これが秘密鍵）

公開するのは (n, e) だけ。p, q, d は秘密にします。

なぜ安全なのか

安全性は「n から p と q を求める（素因数分解する）のが現実的に不可能」という点に依存しています。 512ビットの素数同士の積は1024ビット（約300桁）になり、現在のコンピュータでは分解に天文学的な時間がかかります。

逆に言えば、p か q のどちらかが漏れた瞬間、q = n / p で即座にもう片方も判明し、秘密鍵 d が復元できてしまいます。 今回の問題はまさにこのケースです。

オイラーのトーシェント関数（φ）

何を表すのか

φ(n) は 「1 から n‑1 までの整数のうち、n と互いに素（共通の約数が 1 だけ）な数の個数」 を表します。

互いに素 とは、たとえば 8 と 15 は共通の約数が 1 だけなので互いに素です。 n = p·q（p と q は素数）のとき、φ(n) = (p‑1)·(q‑1) です。

なぜRSAに必要なのか

RSAの復号には「暗号化に使った e の逆元 d」が必要です。 この d を求める式が d = e⁻¹ mod φ(n) であり、φ(n) が分からないと d は計算できません。

なぜ φ(n) でうまくいくかというと、オイラーの定理という性質があるからです：

m^φ(n) ≡ 1 (mod n)

これは「任意の数 m を φ(n) 回掛けると、mod n の世界では 1 に戻る」という意味です。 Webエンジニア的に言えば、配列のインデックスが一周して先頭に戻るような感覚です。

この性質のおかげで、復号の計算が成り立ちます：

暗号化: c = m^e mod n
復号:   m = c^d mod n = m^(e·d) mod n

e·d ≡ 1 (mod φ(n)) なので e·d = 1 + k·φ(n) と書けて：

m^(e·d) = m^(1 + k·φ(n)) = m · (m^φ(n))^k = m · 1^k = m

元の平文 m に戻ります。つまり φ(n) は「ぐるっと一周して元に戻る周期」を教えてくれる関数です。

まとめると

• φ(n) = 復号鍵 d を作るための土台
• φ(n) を知るには p と q が必要 → だから p, q は秘密にする
• φ(n) が分かる ＝ 秘密鍵が作れる ＝ 暗号が解ける

gcd（最大公約数）

gcd(a, b) は「a と b の両方を割り切れる最大の整数」です。

gcd(12, 8) = 4
gcd(15, 9) = 3
gcd(7, 13) = 1  ← 互いに素

今回の攻略では gcd(c2, n) で p を取り出しています。 c2 は p^e mod n なので p の倍数であり、n も p × q なので p の倍数。 両方に共通する因数 p が gcd で求まる、という仕組みです。

まとめ

今回の問題は「RSAの秘密鍵の材料である素数 p を、暗号化して公開してしまった」というシナリオでした。

一見すると p を暗号化しているので安全に見えますが、p は n の因数であるという関係性から、gcd 一発で p が復元できてしまいます。暗号化しても、公開鍵 n との数学的な関係が残っている限り意味がない、ということです。

BACKUP

python playground

import os
from Crypto.Util.number import getPrime, bytes_to_long

m = bytes_to_long(os.getenv("FLAG", "Alpaca{REDACTED}").encode())
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
c1 = pow(m, e, n)
c2 = pow(p, e, n)

assert m < n

print(f"n = {n}")
print(f"e = {e}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")

n = 128951281305588745177398666629581199631058485864966572111701156939267450500461527200369468573426631836231657529006961512763025035249904387307870700668785175314961077286667575866244736508708739350133249344265003181706608358459178127198312194766478590857197619309351373290212091866616979044480765203518287880231
e = 65537
c1 = 54584723810742525332842344311000852588602730106620353769829210613572823180653937528363454036086393048077676074759109894318976797773129779455362292423939574494740847776236268109008206494521359064552627895524641251831367406439093727541197347429866604384086035828634392203445282651867426691962843204295565063110
c2 = 1275053191052289311623571273789725721667869401026425104630717220610992153205486162391947489891617470912363657454340060212607860799074584462787330453990545702469206778960092594048128793161645208662908619530980792732439888903918520029492353921753829884907087387587329511678531595496711467707727494180922007863