問題
from Crypto.Util.number import getPrime, bytes_to_long
import flag
assert(len(flag.flag) == 131)
p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)
flag = bytes_to_long(flag.flag)
c = pow(flag, e, N)
print(f'N = {N}')
print(f'e = {e}')
print(f'c = {c}')
print(f'd = {d}')
与えられるデータ：
N = 65667982563395257456152578363358687414628050739860770903063206052667362178166666380390723634587933595241827767873104710537142458025201334420236653463444534018710274020834864080096247524541536313609304410859158429347482458882414275205742819080566766561312731091051276328620677195262137013588957713118640118673
e = 65537
c = 58443816925218320329602359198394095572237417576497896076618137604965419783093911328796166409276903249508047338019341719597113848471431947372873538253571717690982768328452282012361099369599755904288363602972252305949989677897650696581947849811037791349546750246816657184156675665729104603485387966759433211643
d = 14647215605104168233120807948419630020096019740227424951721591560155202409637919482865428659999792686501442518131270040719470657054982576354654918600616933355973824403026082055356501271036719280033851192012142309772828216012662939598631302504166489383155079998940570839539052860822636744356963005556392864865
解法
RSA暗号化されたフラグが与えられていて、秘密鍵 d も与えられている。普通に復号化すればいい。
あれ？ん？なんかうまくいかない。
フラグが131バイト（1048ビット）で、Nが1024ビット（2つの512ビット素数の積）という奇妙な設定がある。
フラグが N より大きいため、復号化時に複数の候補が生じる：
- $M = c^d \bmod N$ で得られる値
- 実際のフラグは $M + kN$ の形で存在する（$k$ は非負整数）
M = pow(c, d, N)
for k in range(1<<24):
cand = M + k*N
data = cand.to_bytes(131, "big")
if b"TSGLIVE{" in data:
print(data)
break
$k$ を 0 から増やしていき、得られたバイト列が TSGLIVE{ を含むかチェック。
文字制限を超えたRSA暗号化の脆弱性
RSA の基本
RSA では、暗号文 $c$ から平文 $m$ を得るには秘密鍵 $d$ を使って：
$$m \equiv c^d \pmod{N}$$
メッセージサイズ制限の重要性
通常、RSA では平文は $N$ より小さい値に制限される（$m < N$）。
この問題では、フラグが $N$ を超えるサイズで、通常のRSA運用の落とし穴を示している。
復号後、本来のメッセージは $M, M+N, M+2N, \ldots$ の中に存在する。