Daily AlpacaHack: size limit Writeup

size limit

authored by jp3bgy

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

#!/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}')

今回秘密鍵$d$が公開されているので、pow(c, d, N)関数を用いることで復号できます。

from Crypto.Util.number import long_to_bytes

N = 65667982563395257456152578363358687414628050739860770903063206052667362178166666380390723634587933595241827767873104710537142458025201334420236653463444534018710274020834864080096247524541536313609304410859158429347482458882414275205742819080566766561312731091051276328620677195262137013588957713118640118673
e = 65537
c = 58443816925218320329602359198394095572237417576497896076618137604965419783093911328796166409276903249508047338019341719597113848471431947372873538253571717690982768328452282012361099369599755904288363602972252305949989677897650696581947849811037791349546750246816657184156675665729104603485387966759433211643
d = 14647215605104168233120807948419630020096019740227424951721591560155202409637919482865428659999792686501442518131270040719470657054982576354654918600616933355973824403026082055356501271036719280033851192012142309772828216012662939598631302504166489383155079998940570839539052860822636744356963005556392864865

m = pow(c, d, N)
flag = long_to_bytes(m)
print(flag)
# b'\x01\xf7\xb0\xaa\xec\x8f\xbe.\xf8\xa0\xb5\xfa`^\x8aA\xd7N\xa9\xf8qqyj\x90\xce\xd4_\xc58\x15\xb1\t\x1e)\xec\x98\xda\x9b8\xbd_\xc2\x01;\xa2\x91\xe7\xafI\xe9\xa4D\xf1\xfa\xf2\x82\xc5c"\x0c~C:\x90\x99\xeb\xab\xd4\x86\xe7\x01\x1e\xa3\xb4\x9a>\xfeY\x94\xc7EP\x08A\xd1\x12\xa7\xfb\xbf\xe0\x10*\xc5\xcfN0Al\x92!~]^\xed\x02\x1c\xb3\x8ab\xbb\x9d\xcf\xae\xc9\xbe\x8e\x8a\x98:-\xe1N3\xe6\xa8\xef\x12'

おや。うまく復号できませんね。失敗する理由は、フラグ長が131バイト = 1048ビット > 1024ビットとなっているためです。

解法

$m = N + \alpha$としましょう。これを暗号化すると、以下のように表せます。

c \equiv m^e \pmod N

一方で、

m \equiv N + \alpha\mod N \equiv \alpha \pmod 
N

と表せるため、$m = N + \alpha$と$m = \alpha$を暗号化した結果は同じ暗号文$c$となってしまいます。

今回は、これを利用して解いてみましょう。

今、求めたい平文$m$を考えると、

m = m' + \alpha N

と表せます。
$m$について考察すると、バイト長が131バイトであるかつprefixがTSGCTF{から始まるという条件を満たす整数であるといえます。この範囲の下限を$T$とすると、

m \geq T

となる最小の整数$\alpha$を探せばよいことがわかります。

m = m' + \alpha N \geq T\\

より、

\alpha N \geq T - m'\\

となるので、

\alpha \geq \frac{T-m'}{N}

を満たす$\alpha$を探したいと言い換えることができます。

よって、以下の手順でフラグを取得することができます。

1. m_prime = pow(c, d, N)を計算する
2. prefixがTSGLIVE{かつ131バイトを作成する
3. 上記の式に従って、$\alpha$を求め、mを求める

from Crypto.Util.number import long_to_bytes, bytes_to_long

N = 65667982563395257456152578363358687414628050739860770903063206052667362178166666380390723634587933595241827767873104710537142458025201334420236653463444534018710274020834864080096247524541536313609304410859158429347482458882414275205742819080566766561312731091051276328620677195262137013588957713118640118673
e = 65537
c = 58443816925218320329602359198394095572237417576497896076618137604965419783093911328796166409276903249508047338019341719597113848471431947372873538253571717690982768328452282012361099369599755904288363602972252305949989677897650696581947849811037791349546750246816657184156675665729104603485387966759433211643
d = 14647215605104168233120807948419630020096019740227424951721591560155202409637919482865428659999792686501442518131270040719470657054982576354654918600616933355973824403026082055356501271036719280033851192012142309772828216012662939598631302504166489383155079998940570839539052860822636744356963005556392864865

prefix = b"TSGLIVE{"
flag_length = 131
m_prime = pow(c, d, N)
T = bytes_to_long(prefix + b"\x00" * (flag_length - len(prefix)))

m = m_prime + ((T - m_prime)//N + 1) * N
print(long_to_bytes(m).decode())

flag: TSGLIVE{Tttthhhhhiiiiiiisssss iiiiiiiiiisssss aaaaaaaaaaaaaa tooooooooooooooooooooo looooooooooooooooong fllllaaaaaaaaaaaaaaaaaag!}

おまけ

minaminaoさんのWriteupによると、総当たりで行けるらしいです。
https://github.com/minaminao/ctf-writeups/tree/main/daily-alpacahack/2025-12/07_size-limit

from Crypto.Util.number import long_to_bytes

N = 65667982563395257456152578363358687414628050739860770903063206052667362178166666380390723634587933595241827767873104710537142458025201334420236653463444534018710274020834864080096247524541536313609304410859158429347482458882414275205742819080566766561312731091051276328620677195262137013588957713118640118673
e = 65537
c = 58443816925218320329602359198394095572237417576497896076618137604965419783093911328796166409276903249508047338019341719597113848471431947372873538253571717690982768328452282012361099369599755904288363602972252305949989677897650696581947849811037791349546750246816657184156675665729104603485387966759433211643
d = 14647215605104168233120807948419630020096019740227424951721591560155202409637919482865428659999792686501442518131270040719470657054982576354654918600616933355973824403026082055356501271036719280033851192012142309772828216012662939598631302504166489383155079998940570839539052860822636744356963005556392864865

m = pow(c, d, N)

for _ in range(1 << 25):
    m += N
    x = long_to_bytes(m)
    if b"TSGLIVE" in x:
        print(x)
        break