AlpacaHack Round 12: RSARSARSARSARSARSA Upsolve

RSARSARSARSARSARSA

authored by yu212

何度も言わないでもわかるよ……

from math import gcd
import os
from Crypto.Util.number import getPrime, bytes_to_long

e = 19
while True:
    p = getPrime(2048)
    q = getPrime(2048)
    if gcd((p - 1) * (q - 1), e) == 1:
        break
n = p * q

flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}")
assert len(flag) == 26 and flag.startswith("Alpaca{") and flag.endswith("}")

m = bytes_to_long((flag * 1337).encode())
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

解法

ここで気になるのはflag * 1337というところです。
これがどういう関係になるのか実験をしてみましょう。

from Crypto.Util.number import bytes_to_long

flag = b"test"

print(hex(bytes_to_long(flag)))
print(hex(bytes_to_long(flag * 2)))
print(hex(bytes_to_long(flag * 3)))

hexにしてみたところ、以下のような出力が得られました。

0x74657374
0x7465737474657374
0x746573747465737474657374

今回、flagは26文字であることが確定しており、prefix(Alpaca{), suffix(})はすでに分かっていることから、
不明な文字数は18文字のみであるといえます。
つまり、平文$m$は既知部分$K$と未知部分$U$とすると、
$$
m = K + U
$$
となります。特に$U$は、未知18バイト$x$が線形に入るので、
$$
U = Cx
$$
と考えることができます。ただし、
$$
C = \sum_{i=0}^{1336} 256^{26i+1}
$$
とします。
すると、暗号文$c$は
$$
c \equiv m^e \equiv (K + Cx)^19 \pmod n
$$
となり、
$$
f(x) = (K + Cx)^19 - c \equiv 0 \pmod n
$$
と考えることができます。さて、$0 \leq x < 2^144$なので、小さい範囲の根となることがわかります。
以上の考えから、実装するとこのようになります。

from sage.all import *
import cuso
from Crypto.Util.number import bytes_to_long, long_to_bytes

n = 434245275129793896913302623186216967500119715299127153234221039838158526818290666891561167619572507897277032319251523352710966722158326513857889678449160348496647427753832233179173745189495799707833020232209447520485615893168704144655033371807912826948460011240258726843346618328839282439390863464375320181495406806870462330735361196286553150480225927729088313551861682406252457739974850015509783430978939475350707211461876140420181118923743456062581297038004651412953310377554877499792225388059857865550418697212704277742826280689987165702071346542831836616149138379224837551040036947064990027047482745931141458056028719767845142490618375017582275824317241572815337810658684051187938258804346960781372035972758516593800419459342799854863845667715099378564373594732798224797622583907677749880918106223965727445907355069025939554400938193579295415911074889648122298896605189398591684277376327938718166279159875826993866460251900514487349848332991005775574378131897581182876147580659857596204121970624162722935263271888969020482566142620134100258216288390250174699829806817678453601913377347867137739622906815272561714188564065071077762169177825466514512198167566882661748389120146622447920498988341055543170346944366105037929197965527
e = 19
c = 78338816976998323261765735600063671710448529902850366859501110834174319629348492230679353792803618614020892663940158627385470036549819116375194598599193512981265682997072278631964394686243958989105159463105190885437258093111178664394786430767942639437287236999171486583513816766766869843448941665224796216610702708658300011987744401747551989248270799179750556330952646223694000679475842632497149402602469848595868051660228892506097962300820851000134370939783634534516434054009303981106884637932006844265722691022870174977860945699441650254771777451995160642261482879537396171107016491225773397809485749640163676209732235156461483660111845782227127763086286553520914359194795617080980736767821995556156173267185240945707717461037831992544868933876015548419376861213017988005848033349136839971120363078490938026883354839573512645985195570831018461470031329716026531550172207332072481279548470657090575709419245114386419567236219816237412255505882075283974654569995321334498673793010812162088796252555619242463561750801895032793870706949913548310632113206159695535952422316840587214237406730422405058644629458566515378607614900910335034732797410592671297941526063690060922625005949094383664832255082556088451940780657576420871470920836

prefix = b"Alpaca{"
suffix = b"}"
unknown_len = 18
reps = 1337

block_len = len(prefix) + unknown_len + len(suffix)
assert block_len == 26

flag_guess = prefix + (b"\x00" * unknown_len) + suffix
repeated_flag_guess = flag_guess * reps
guess = Integer(bytes_to_long(repeated_flag_guess))

x = var("x")

coeff = Integer(0)
for i in range(reps):
    coeff += Integer(256) ** Integer(i * block_len + len(suffix))

m = guess + coeff * x
f = m**e - c
bounds = {x: (0, 2 ** (8 * unknown_len))}

roots = cuso.find_small_roots(
    relations=[f],
    bounds=bounds,
    modulus=n,
)

if not roots:
    raise RuntimeError("no roots found (try adjusting bounds/structure)")

x0 = Integer(roots[0][x]) if x in roots[0] else Integer(roots[0].get("x"))
flag = prefix + long_to_bytes(int(x0), unknown_len) + suffix
print(flag.decode())

Flag: Alpaca{cryptocryptocrypto}