Daily AlpacaHack: one-p-rsa

one-p-rsa

authored by kanon

通常のRSAは2つの素数を使いますが、今回は一つだけのようです

from Crypto.Util.number import *
import os

flag = os.getenv("FLAG", "flag{example}").encode()
m = bytes_to_long(flag)

p = getPrime(512)
e = 65537
ct = pow(m, e, p)

print(f"{p = }")
print(f"{e = }")
print(f"{ct = }")

解法

RSAの暗号化は以下の式で定義されています。
$$
c \equiv m^e \pmod {pq}
$$
ただし、$p,q \in \mathbb{P}$とします。
今回は$p$のみなので、
$$
c \equiv m^e \pmod p
$$
と表すことができます。
つまり、今までのRSAと同じように
$$
ed \equiv 1 \pmod {\phi(p)}
$$
を満たす$d$を探してあげたらよいです。
ここで、$\phi(n)$は、$n$と互いに素である$1$以上$n$以下の自然数の個数を与える関数です。$n \in \mathbb{P}$のときは、$\phi(n) = n-1$となることが知られています。
よって、
$$
ed \equiv 1 \pmod {p-1}
$$
を満たす$d$を探し、復号の定義式
$$
m \equiv c^d \pmod p
$$
を与えてあげるとフラグが得られます。

from Crypto.Util.number import long_to_bytes

p = 7053006329937394640578809003529950424006540078407576710977610896377332570587931209266308841802166045389105874282224525157800335000482365019181031916131567
e = 65537
ct = 1207620648204721029719345249590236571809041832424398358565952316975026187064905972160827378199683620133257513725775137874934857698854513919128707181952938

d = pow(e, -1, p-1)
m = pow(ct, d, p)

print(long_to_bytes(m).decode())

Flag: Alpaca{which_rsa_do_you_like?}