[AlpacaHack] size limit Writeup

ひとこと

たのしかった　実は私もRSAの自前実装をしたときにこの問題に一回出くわしたことがあったので興味が出た

問題

情報

ジャンル: Crypto
難易度: Medium
問題URL: https://alpacahack.com/challenges/size-limit

問題文

復号鍵も渡したんだし、これで誰でもメッセージを読めるよね！

注: この問題は TSG LIVE! CTF の過去問であり、フラグのフォーマットはTSGLIVE{...}です。フラグのフォーマットはフラグ提出フォームのプレースホルダーからも確認できます。

与えられたコード

problem.py

#!/usr/bin/python3

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}')

なにがまずいのか

平文$m$ (今回はflag)はかならず$n=pq$より小さくなる必要がありますが、$m$がassertより131byteということが分かります。つまり整数に直すと軽く見積もって$2^{131\cdot 8}=2^{1048}$程度となりますが、$p,q$は512bitなので$n$は1024bit、すなわち$n$はおおよそ$2^{1024}$で、$m>n$となってしまい、意図した平文が暗号化できていません。

平文の形

平文$m$はこんな感じで表せます。
$$m=kn+r~(0\leq r<n)$$
そして$r$は通常通りの復号をすると$r=c^d\bmod n$なので得られます。
問題は失われた商のほうです。ここはどうしようもないので総当たりします。

そのまえに探索範囲の見積もりだけ。
$m<2^{1048},n\geq2^{1024}$でしたよね。一回$r$は無視して($r<n$なので探索範囲の見積もりに利用したところであんまり変わらない)、
$$k\sim\left\lfloor\frac m n\right\rfloor<2^{1048-1023}=2^{25}$$

程度。$O(2^N)$のアルゴリズムに$N=25$をぶち込んでも宇宙崩壊、とはさすがにならないでしょう。

# from Crypto.Util.number import long_to_bytes
n = 65667982563395257456152578363358687414628050739860770903063206052667362178166666380390723634587933595241827767873104710537142458025201334420236653463444534018710274020834864080096247524541536313609304410859158429347482458882414275205742819080566766561312731091051276328620677195262137013588957713118640118673
e = 65537
c = 58443816925218320329602359198394095572237417576497896076618137604965419783093911328796166409276903249508047338019341719597113848471431947372873538253571717690982768328452282012361099369599755904288363602972252305949989677897650696581947849811037791349546750246816657184156675665729104603485387966759433211643
d = 14647215605104168233120807948419630020096019740227424951721591560155202409637919482865428659999792686501442518131270040719470657054982576354654918600616933355973824403026082055356501271036719280033851192012142309772828216012662939598631302504166489383155079998940570839539052860822636744356963005556392864865
r = pow(c, d, n)
for k in range(1, 10 ** 9): # 2 << 25とかでもOK
  m = k*n + r
  flg = m.to_bytes(131, "big") # 131byte確定なのでlong_to_bytes使わなくてよかった
  if flg.startswith(b"TSGLIVE{"): # 復号できたか判定
    print(flg, k)

これでflagをゲットできました。なお、$k$は$15128635$で、だいたい$2^{24}$くらいです。$[2^{23},2^{24}]$くらいでよかったかな?

おわりに

131byteという長さが分かっていたからよかったけど、長さが不明でなおかつ探索範囲が膨大であれば指数時間なので宇宙が崩壊します。RSA暗号って意外とそんな長いものを暗号化できなかったりする