[crypto] RSARSARSARSARSARSA (AlpacaHack Round 12) writeup

---

• Source: AlpacaHack Round 12 (crypto)
• Author: Yu_212

---

RSA暗号で、mがflag*1337でe=19という問題。実行結果が与えられている。

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 = }")

mはflag*1337で明らかにnより大きいので、Low Public Exponent Attackは使えない。
しかしflagは26byteであることが分かっており、そのうちAlpaca{と}の8byteは既知。mの一部が分かっているので、Coppersmithで解けそう。

未知部分18byteを変数xと置いて頑張って立式する。詳しくはsolverを参照。

from Crypto.Util.number import *

n = 434245275129793896913302623186216967500119715299127153234221039838158526818290666891561167619572507897277032319251523352710966722158326513857889678449160348496647427753832233179173745189495799707833020232209447520485615893168704144655033371807912826948460011240258726843346618328839282439390863464375320181495406806870462330735361196286553150480225927729088313551861682406252457739974850015509783430978939475350707211461876140420181118923743456062581297038004651412953310377554877499792225388059857865550418697212704277742826280689987165702071346542831836616149138379224837551040036947064990027047482745931141458056028719767845142490618375017582275824317241572815337810658684051187938258804346960781372035972758516593800419459342799854863845667715099378564373594732798224797622583907677749880918106223965727445907355069025939554400938193579295415911074889648122298896605189398591684277376327938718166279159875826993866460251900514487349848332991005775574378131897581182876147580659857596204121970624162722935263271888969020482566142620134100258216288390250174699829806817678453601913377347867137739622906815272561714188564065071077762169177825466514512198167566882661748389120146622447920498988341055543170346944366105037929197965527
e = 19
c = 78338816976998323261765735600063671710448529902850366859501110834174319629348492230679353792803618614020892663940158627385470036549819116375194598599193512981265682997072278631964394686243958989105159463105190885437258093111178664394786430767942639437287236999171486583513816766766869843448941665224796216610702708658300011987744401747551989248270799179750556330952646223694000679475842632497149402602469848595868051660228892506097962300820851000134370939783634534516434054009303981106884637932006844265722691022870174977860945699441650254771777451995160642261482879537396171107016491225773397809485749640163676209732235156461483660111845782227127763086286553520914359194795617080980736767821995556156173267185240945707717461037831992544868933876015548419376861213017988005848033349136839971120363078490938026883354839573512645985195570831018461470031329716026531550172207332072481279548470657090575709419245114386419567236219816237412255505882075283974654569995321334498673793010812162088796252555619242463561750801895032793870706949913548310632113206159695535952422316840587214237406730422405058644629458566515378607614900910335034732797410592671297941526063690060922625005949094383664832255082556088451940780657576420871470920836

prefix = b"Alpaca{"
suffix = b"}"
k = 18 # 未知byte

PR.<x> = PolynomialRing(Zmod(n))

base = bytes_to_long((prefix + b"\x00"*k + suffix) * 1337)

coeff = 0
for rep in range(1337):
    # Alpaca{***}Alpaca{***}Alpaca{***}....の***部分の総和を求めたい
    pos = rep * 26 + len(suffix)
    coeff += pow(256, pos, n)

# coeff*x がbaseを1337回繰り返した値とflagを1337回繰り返した値の差分
# m = base + coeff * x
f = (base + coeff * x)**e - c
f = f.monic()

roots = f.small_roots(X=2**(8*k), epsilon=1/30)
flag = prefix + long_to_bytes(int(roots[0]), k) + suffix
print(flag)

flagが得られた。
Alpaca{cryptocryptocrypto}