⛳

AlpacaHack Round 12 (Crypto) writeup & upsolve

に公開
writeup
tech

概要

2025年7月6日に開催されたAlpacaHackのwriteupです。

諸用があり、１時間だけ参加でしたが1問解けたのは良いところ。

一方で、変な計算ミスで時間を浪費してしまったので、落ち着いて問題に取り組むのは課題と感じました。

ということで、以下writeup。

RSARSARSARSARSARSA

You don't have to say it again and again...

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

n,e,cが与えられる。
cは、flag({\rm bytes})を1337回繰り返したものを暗号化したものである。

方針）

  1. {\rm flag}({\rm bytes})をN倍していることから、乗法の準同型性を用いる
  2. eが比較的小さいため、Low Public-Exponent Attackを用いる
    問題と予想。
2.についての補足

正確には、{\rm flag}^e < p\times qであるため
assert len(flag) == 26 and flag.startswith("Alpaca{") and flag.endswith("}")
より、
((256)^{26})^{19}=3953 {\rm bit} < p\times q=(4095) {\rm bit}

具体的には、

c = (X\times {\rm flag})^e \mod N

であるため、x=X^{-e} \mod NとなるXを求め、

x\times c = x\times (X\times {\rm flag})^e \mod N\\ x\times c = x\times X^e \times ({\rm flag})^e \mod N\\ x\times c = {\rm flag}^e \mod N

を計算し、e乗根を計算すれば良い。

簡単のため、

m = bytes_to_long((flag * 2).encode())

の状況を考える。

{\rm flag}({\rm bytes})（26バイトの文字列）が二つ連続しているという状況は、{\rm flag}({\rm bytes})を26バイト左にシフトし更に{\rm flag}を足したものに等しい。
つまり、x={\rm bytes\_to\_long}({\rm flag}), y={\rm bytes\_to\_long}({\rm flag}*2)とした時、

y = (256^{26}+1)x

となる。

同様に、今回は、1337倍しているので

c = \left(\left(\sum_{i=0}^{1337} {256^{i}}\right){{\rm flag}}\right)^e \mod N

であるため、

x = \left(\sum_{i=0}^{1337} {256^{i}}\right)^{-e} \mod N\\ x\times c = ({\rm flag})^e \mod N

が求められ、x\times cのe乗根を計算することで、flagが得られる。

solve.py
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot

n = 434245275129793896913302623186216967500119715299127153234221039838158526818290666891561167619572507897277032319251523352710966722158326513857889678449160348496647427753832233179173745189495799707833020232209447520485615893168704144655033371807912826948460011240258726843346618328839282439390863464375320181495406806870462330735361196286553150480225927729088313551861682406252457739974850015509783430978939475350707211461876140420181118923743456062581297038004651412953310377554877499792225388059857865550418697212704277742826280689987165702071346542831836616149138379224837551040036947064990027047482745931141458056028719767845142490618375017582275824317241572815337810658684051187938258804346960781372035972758516593800419459342799854863845667715099378564373594732798224797622583907677749880918106223965727445907355069025939554400938193579295415911074889648122298896605189398591684277376327938718166279159875826993866460251900514487349848332991005775574378131897581182876147580659857596204121970624162722935263271888969020482566142620134100258216288390250174699829806817678453601913377347867137739622906815272561714188564065071077762169177825466514512198167566882661748389120146622447920498988341055543170346944366105037929197965527
e = 19
c = 78338816976998323261765735600063671710448529902850366859501110834174319629348492230679353792803618614020892663940158627385470036549819116375194598599193512981265682997072278631964394686243958989105159463105190885437258093111178664394786430767942639437287236999171486583513816766766869843448941665224796216610702708658300011987744401747551989248270799179750556330952646223694000679475842632497149402602469848595868051660228892506097962300820851000134370939783634534516434054009303981106884637932006844265722691022870174977860945699441650254771777451995160642261482879537396171107016491225773397809485749640163676209732235156461483660111845782227127763086286553520914359194795617080980736767821995556156173267185240945707717461037831992544868933876015548419376861213017988005848033349136839971120363078490938026883354839573512645985195570831018461470031329716026531550172207332072481279548470657090575709419245114386419567236219816237412255505882075283974654569995321334498673793010812162088796252555619242463561750801895032793870706949913548310632113206159695535952422316840587214237406730422405058644629458566515378607614900910335034732797410592671297941526063690060922625005949094383664832255082556088451940780657576420871470920836

x = ((256**26)**1337-1)//(256**26-1)

x_inv =  pow(x,-e,n)
m2 = (c*x_inv)%n

m, tf = iroot(m2, e)

if tf:
    print(long_to_bytes(m).decode())

その他

upsolveするよん。お楽しみに。

Discussion