kurenaif Valentine Problems - p_p_rsa

kurenaifさんがCryptoの問題をプレゼントしてくれました。ちょっと忙しかったので今から解きます。一応既に公式writeupが出ているはずですので、そちらを見た方が分かりやすい説も。

問題概要

問題リンク

problem.py

from Crypto.Util.number import *
from flag import *
import secrets

m = bytes_to_long(flag)

p = getPrime(256)
q = p # Oops!
N = p*q
e = 65537
print("e =", e)
print("N =", N)
print("c =", pow(m, e, N))

コメントの内容からも、普通のRSAながらも$p=q$というトンデモ制約が課せられています。

解説

RSAってそもそもどんなやつだっけ？

本来のRSAがどのように動作しているかをまずは復習しましょう。

• 大きな素数$p,q$を用意し、$N=p\times q$とする。この時点での「$N$から$p,q$を求めるのが難しい」というのがRSAの強さです。
• 暗号化する際には$c=m^e ({\rm mod} N)$とする。$e$は条件^[1]があるのですが、適当な数としてよく65,535が選ばれます。
• 復号化の際にはオイラーの小定理を活用します。

条件は割愛しますが、$\phi(N)$を$N$以下の$N$を割り切らない自然数の個数（オイラー関数）としたとき、$x^{\phi(N)}\equiv 1({\rm mod} N)$

• $ed\equiv 1\left({\rm mod}\phi(N)\right)$となる$d$は拡張ユークリッドの互除法から求めることが出来ます。この時、

• この$d$が分かると、$m \equiv c^d({\rm mod}N)$で復号が可能です。というのも、$m \equiv c^d \equiv (m^e)^d \equiv m^{ed} = m^{k\phi(N) + 1} ({\rm mod} N)$が成り立ち、先ほどのオイラーの小定理から$m^{\phi(N)}\equiv 1({\rm mod}N)$が成立するからです。

また、$p$、$q$は異なる素数であることから、$\phi(N)=(p-1)(q-1)$ということが広く知られており、これを用いて計算することが一般的です。

$p=q$だと何が起こるか

今回の問題の$p=q$の場合ですが、$p=q=N^{0.5}$であることから$p,q$を求めることがまず可能です。そこから$\phi(N)$も求まってしまい、結果的に$d$が計算出来て復号出来てしまいます。

注意しなくてはならない点がいくつかあります。

• 先程説明した$\phi(N)=(p-1)(q-1)$の話。今回は$p=q$で$p,q$は素数であることから、$N$を割り切る数は$N-p$個しかありません。オイラー関数をこれに置き換えておく必要があります。
• Pythonでsqrtをそのまま利用するとfloatで計算されるので有効数字が全く足らないと思います。僕は2分探索のコードを書いてしまいましたが、もしかしたらintのままsqrtを計算してくれるライブラリあるかもですね。

solve.py

e = 65537
N = 7504521114311153672308826977564891107288058227100173341193360340321176562970983694756086045753375611733443716948010092176135133045533366956059169702726409
c = 3120246791506259955679234385495683489853187127801200033777823093969698684663885288175101358075188702658492281935014546035799989917015048182861857825663454

left = 0
right = N
for _ in range(512):
    mid = (left + right) // 2
    if mid * mid > N:
        right = mid
    else:
        left = mid
assert left * left == N
p = q = left

def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a % b)
        y -= (a // b)*x
        return d, x, y
    return a, 1, 0

# 注意
g, d, _ = extgcd(e, N - p)
assert g == 1
assert e * d % (N - p) == 1

assert pow(pow(2, e, N), d, N) == 2
m = pow(c, d, N)
print(m.to_bytes(32, 'big'))

脚注

1. 条件は「$\phi(N)$と互いに素であること」「小さすぎず、かつ大きすぎないこと」です。前者はRSAの原理的に必須、後者は脆弱性になるため必要です。