HKCERT 2024
Almost DSA
import os
from Crypto.Util.number import getPrime as get_prime
from Crypto.Util.number import isPrime as is_prime
import secrets
import hashlib
# Computes the inverse of a mod prime p
def inverse(a, p):
return pow(a, p-2, p)
def hash(m):
h = hashlib.sha256(m).digest()
return int.from_bytes(h, 'big')
def generate_parameters():
# FIPS 186-4 specifies that p and q can be of (2048, 256) bits
while True:
q = get_prime(256)
r = secrets.randbits(2048-256)
p = r*q + 1
if p.bit_length() != 2048: continue
if not is_prime(p): continue
break
h = 1
while True:
h += 1
g = pow(h, (p-1)//q, p)
if g == 1: continue
break
return p, q, g
def sign(params, x, m):
p, q, g = params
k = secrets.randbelow(q)
r = pow(g, k, p) % q
s = inverse(k, q) * (hash(m) + x*r) % q
return (r, s)
def verify(params, y, m, sig):
p, q, g = params
r, s = sig
assert 0 < r < p
assert 0 < s < p
w = inverse(s, q)
u1 = hash(m) * w % q
u2 = r * w % q
v = pow(g, u1, p) * pow(y, u2, p) % p % q
assert v == r
def main():
# The parameters were generated by generate_parameters(), which will take some time to generate.
# With that reason, we will use a fixed one instead of a random one.
p = 17484281359996796703320753329289113133879315487679543624741105110874484027222384531803606958810995970161525595158267517181794414300756262340838882222415769778596720783078367872913954804658072233160036557319401158197234539657653635114116129319712841746177858547689703847179830876938850791424742190500438426350633498257950965188623233005750174576134802300600490139756306854032656842920490457629968890761814183283863329460516285392831741363925618264196019954486854731951282830652117210758060426483125525221398218382779387124491329788662015827601101640859700613929375036792053877746675842421482667089024073397901135900307
q = 113298192013516195145250438847099037276290008150762924677454979772524099733149
g = 2240914810379680126339108531401169275595161144670883986559069211999660898639987625873945546061830376966978596453328760234030133281772778843957617704660733666090807506024220142764237508766050356212712228439682713526208998745633642827205871276203625236122884797705545378063530457025121059332887929777555045770309256917282489323413372739717067924463128766609878574952525765509768641958927377639405729673058327662319958260422021309804322093360414034030331866591802559201326691178841972572277227570498592419367302032451643108376739154217604459747574970395332109358575481017157712896404133971465638098583730000464599930248
print(f'{p = }')
print(f'{q = }')
print(f'{g = }')
x = secrets.randbelow(q)
y = pow(g, x, p)
print(f'{y = }')
m = b'gib flag'
r = int(input('r = '))
s = int(input('s = '))
verify((p, q, g), y, m, (r, s))
flag = os.getenv('FLAG', 'hkcert24{***REDACTED***}')
print(flag)
if __name__ == '__main__':
main()
To solve, send r=1 and s=q.
RSA LCG (0)
import os
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime
class LCG:
def __init__(self, bits, a=None, c=None, seed=None):
self.seed = seed
if self.seed is None: self.seed = secrets.randbits(bits) | 1
self.a = a
if self.a is None: self.a = secrets.randbits(bits) | 1
self.c = c
if self.c is None: self.c = secrets.randbits(bits)
self.bits = bits
self.m = 2**bits
def next(self):
self.seed = (self.seed * self.a + self.c) % self.m
return self.seed
def __repr__(self):
return f'LCG(bits={self.bits}, a={self.a}, c={self.c})'
def get_prime(lcg, bits):
while True:
p = 0
for i in range(bits//lcg.bits):
p <<= lcg.bits
p |= lcg.next()
if p.bit_length() != bits: continue
if not is_prime(p): continue
return p
if __name__ == '__main__':
FLAG = os.environb.get(b'FLAG', b'hkcert24{***REDACTED***}')
seed = secrets.randbits(16) | 1
lcg = LCG(bits=128, seed=seed)
print(f'{lcg = }')
ps = [get_prime(lcg, bits=1024) for _ in range(4)]
n = reduce(mul, ps)
e = 0x10001
m = int.from_bytes(FLAG, 'big')
c = pow(m, e, n)
print(f'{n = }')
print(f'{e = }')
print(f'{c = }')
lcg = LCG(bits=128, a=181525535962623036141846439269075744717, c=115518761677956575882056543847720910703)
n = 481114791694785858695050549695538734046971417176843978882044871919616727765643820034066591387776993303130591599679964348353329376559922076715381691496791199317834852972956556186543750873476577029492255903246050392214315442941266567737558736141253495436298490003513325026207840446389886295321748490024615821174562383476857761918630446488869812894422048853097952363719756297344014883459670109643440173428469002028435568608888993928248402297380061528970024946401518041243564217741744613525402813984605478699738311132717493610790718032712239270654974446116711995328572373804563487208899590643981315012517538379075118546604524143430683964513429268368997878214614073305169449253802788601323508855536854500946367628892634824935231007194546528797696281628426050519984306590514055620223093615738335974270220301535497863462980632453977776013292134758089648072661829571370276168813518517058289217357255320627263734650032320305279867840420886394855960116879598125383109784504746667833173574005936871719063288584361794901458463052848937392072728849939635133710409996428462876274835371522565826839423046726308001047859782566419852401917763502007196004524754115471117969452116174478677547559057917128250716516531170082878464757039874318490906158689
e = 65537
c = 345977789156696385683581168846000378215844867611205467179181525756923773343997491856273352579925123046597359189866939437231366570263052567113535467666353517443555775669947203980735918360811410985879753948221470545729133552842244535778330182549296248222039054438197983267418429814674564210947108838042963108251861548375535326969960093796185009763176002544709169063466256285182205803310470811843866647483609768051301160908646352263376778439044867189801653416628219979460525679135210530110143121851284249580066642389243748128010268277263972367956550837364650977683324140767090284085773301486622501777068017859676285398384937589784505599555747372780238872296757407155242584567297352399943303106161556729208284654934208601533197169169514879515899747537955886064112109885660797961038075757520138954391314283382301755474526387505278386817416193439304304484679228240909612236945218009947246430065957288065358434877715856330476675541582153869420244176864467086961698529560004535449279996657026744930241841052475481816491735959706500890907139027990119800255632071177694111432383236909734940374926954075681464953536382583119130818187839809617068848876572944726598351264384270260481762978383770917542259594389267566490962365207501538561114532291
For this one, the seed is only 16 bits and you can brute force it.
from Crypto.Util.number import isPrime as is_prime
from tqdm import trange
class LCG:
def __init__(self, bits, a=None, c=None, seed=None):
self.seed = seed
self.a = a
self.c = c
self.bits = bits
self.m = 2**bits
def next(self):
self.seed = (self.seed * self.a + self.c) % self.m
return self.seed
def get_prime(lcg, bits):
while True:
p = 0
for _ in range(bits//lcg.bits):
p <<= lcg.bits
p |= lcg.next()
if p.bit_length() != bits: continue
if not is_prime(p): continue
return p
lcg = LCG(bits=128, a=181525535962623036141846439269075744717, c=115518761677956575882056543847720910703, seed=1)
n = 481114791694785858695050549695538734046971417176843978882044871919616727765643820034066591387776993303130591599679964348353329376559922076715381691496791199317834852972956556186543750873476577029492255903246050392214315442941266567737558736141253495436298490003513325026207840446389886295321748490024615821174562383476857761918630446488869812894422048853097952363719756297344014883459670109643440173428469002028435568608888993928248402297380061528970024946401518041243564217741744613525402813984605478699738311132717493610790718032712239270654974446116711995328572373804563487208899590643981315012517538379075118546604524143430683964513429268368997878214614073305169449253802788601323508855536854500946367628892634824935231007194546528797696281628426050519984306590514055620223093615738335974270220301535497863462980632453977776013292134758089648072661829571370276168813518517058289217357255320627263734650032320305279867840420886394855960116879598125383109784504746667833173574005936871719063288584361794901458463052848937392072728849939635133710409996428462876274835371522565826839423046726308001047859782566419852401917763502007196004524754115471117969452116174478677547559057917128250716516531170082878464757039874318490906158689
c = 345977789156696385683581168846000378215844867611205467179181525756923773343997491856273352579925123046597359189866939437231366570263052567113535467666353517443555775669947203980735918360811410985879753948221470545729133552842244535778330182549296248222039054438197983267418429814674564210947108838042963108251861548375535326969960093796185009763176002544709169063466256285182205803310470811843866647483609768051301160908646352263376778439044867189801653416628219979460525679135210530110143121851284249580066642389243748128010268277263972367956550837364650977683324140767090284085773301486622501777068017859676285398384937589784505599555747372780238872296757407155242584567297352399943303106161556729208284654934208601533197169169514879515899747537955886064112109885660797961038075757520138954391314283382301755474526387505278386817416193439304304484679228240909612236945218009947246430065957288065358434877715856330476675541582153869420244176864467086961698529560004535449279996657026744930241841052475481816491735959706500890907139027990119800255632071177694111432383236909734940374926954075681464953536382583119130818187839809617068848876572944726598351264384270260481762978383770917542259594389267566490962365207501538561114532291
#for seed in trange(1, 2**16, 2):
for seed in trange(58725, 2**16, 2): # skip
lcg.seed = seed
p = get_prime(lcg, bits=1024)
if n%p == 0:
break
flag = pow(c, pow(65537, -1, p-1), p)
print(bytes.fromhex(f'{flag:x}'))
# hkcert24{0k4y_th1s_1s_n0t_ev3n_vu1n3r4b1e_b3c4u5e_0f_1cgs}
RSA LCG (1)
import os
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime
class LCG:
def __init__(self, bits, a=None, c=None, seed=None):
self.seed = seed
if self.seed is None: self.seed = secrets.randbits(bits) | 1
self.a = a
if self.a is None: self.a = secrets.randbits(bits) | 1
self.c = c
if self.c is None: self.c = secrets.randbits(bits)
self.bits = bits
self.m = 2**bits
def next(self):
self.seed = (self.seed * self.a + self.c) % self.m
return self.seed
def __repr__(self):
return f'LCG(bits={self.bits}, a={self.a}, c={self.c})'
def get_prime(lcg, bits):
while True:
p = 0
for i in range(bits//lcg.bits):
p <<= lcg.bits
p |= lcg.next()
if p.bit_length() != bits: continue
if not is_prime(p): continue
return p
if __name__ == '__main__':
FLAG = os.environb.get(b'FLAG', b'hkcert24{***REDACTED***}')
lcg = LCG(bits=256, c=0)
print(f'{lcg = }')
ps = [get_prime(lcg, bits=1024) for _ in range(4)]
n = reduce(mul, ps)
e = 0x10001
m = int.from_bytes(FLAG, 'big')
c = pow(m, e, n)
print(f'{n = }')
print(f'{e = }')
print(f'{c = }')
lcg = LCG(bits=256, a=102197201962123846389438942955101245465045811321520032783251514372432272871077, c=0)
n = 712650313276602240132329097304430048400352751513310575526412992129597422070848111072491134888258819603174150809317988369755331029009864211216547294646211646094933573124257136163629116984386416188859789467395164897001085191528084740453428500956450177548977865861466055171717564208692444769495508512419622780024874941844495178742341131675818700155796280310646897103229083027529919187454771613414875490462993045875936234591157744167214046734190302287427367403568860249349359776931200150301621481939428066984857258770478004853926288162003818241246878159630318266155498887714140614580751646422502723648142074111613225912644502226694307736726087673647398291980857229829977354067820423709011783907277562489549103977052076140881547728240425069463175586173317054911517453708001448687312406872942899280723472709421452062317503252258181984837591194705354256671714708896675155493168030996749797654707148117051477506855802867089687545890519363621855230477269747205380531049996041867129632051572747028441506474146062043427303954298727328531350438208765938027973006421501568307421856483699068172998763428694958905673708416275143602068221058898394079378423785058886143156065469790907727616640696078658243794470631540358286862899496224884600294835441
e = 65537
c = 445308155915029567991204642441037106636274278969323594266962964897048528466773947276913391974222302661172087064465526779062356615268434642959161607080766074334140739062421641878296527210809334178619685030176261525389226557543594953035919061416292966585184462770190073132725325830890587610808224156896611989260754435566640011008330800266408350415234832430226789140062590779004940578475055195767146347394381212157930691103929079825296986828415158506003438261121628407171546274414046568037336522095223978532053246031668840069046046390952201058199981492454288495640857942797704964843287034359460079316661425483842570190113998195387780579545809621808801626313837113473885818945052873823360056317079785841069224993435527933283918571286444280017102781865312454024328849395335083566145607543834607504822081522250923714391873652357185101163374950977150829214936039230387625706376713934778873385375582488086205462961139042991664546797362021066081938999660281537596860879414252495949608351649066648594254272314188241185715920283526637402373027396529855631498571685297193020517033784357794223831020791070397249992230576960345185544552280142788704673413055403847038488791910041421887897364099871208624646292906015164161354890370666964030412257423
In this one c=0.
So each lcg output is just a**x * s for some x.
We can also write p1 * p2 * p3 * p4 ≡ n (mod m)
The lower 256 bits of each prime is just some lcg output, so:
(a**x1 * s) * (a**x2 * s) * (a**x3 * s) * (a**x4 * s) ≡ n (mod m)
a**(x1+x2+x3+x4) * s**4 ≡ n (mod m)
let t = x1+x2+x3+x4
s**4 ≡ n * a**(-t)
Now you can brute t and solve for s with modular 4th root.
In fact, you seem to be able to solve some of the primes with t less than the real t and a seed different to the real seed:
class LCG:
def __init__(self, bits, a=None, c=None, seed=None):
self.seed = seed
self.a = a
self.c = c
self.bits = bits
self.m = 2**bits
def next(self):
self.seed = (self.seed * self.a + self.c) % self.m
return self.seed
def get_prime(lcg, bits):
while True:
p = 0
for _ in range(bits//lcg.bits):
p <<= lcg.bits
p |= lcg.next()
if p.bit_length() != bits: continue
if not is_prime(p): continue
return p
n = 712650313276602240132329097304430048400352751513310575526412992129597422070848111072491134888258819603174150809317988369755331029009864211216547294646211646094933573124257136163629116984386416188859789467395164897001085191528084740453428500956450177548977865861466055171717564208692444769495508512419622780024874941844495178742341131675818700155796280310646897103229083027529919187454771613414875490462993045875936234591157744167214046734190302287427367403568860249349359776931200150301621481939428066984857258770478004853926288162003818241246878159630318266155498887714140614580751646422502723648142074111613225912644502226694307736726087673647398291980857229829977354067820423709011783907277562489549103977052076140881547728240425069463175586173317054911517453708001448687312406872942899280723472709421452062317503252258181984837591194705354256671714708896675155493168030996749797654707148117051477506855802867089687545890519363621855230477269747205380531049996041867129632051572747028441506474146062043427303954298727328531350438208765938027973006421501568307421856483699068172998763428694958905673708416275143602068221058898394079378423785058886143156065469790907727616640696078658243794470631540358286862899496224884600294835441
c = 445308155915029567991204642441037106636274278969323594266962964897048528466773947276913391974222302661172087064465526779062356615268434642959161607080766074334140739062421641878296527210809334178619685030176261525389226557543594953035919061416292966585184462770190073132725325830890587610808224156896611989260754435566640011008330800266408350415234832430226789140062590779004940578475055195767146347394381212157930691103929079825296986828415158506003438261121628407171546274414046568037336522095223978532053246031668840069046046390952201058199981492454288495640857942797704964843287034359460079316661425483842570190113998195387780579545809621808801626313837113473885818945052873823360056317079785841069224993435527933283918571286444280017102781865312454024328849395335083566145607543834607504822081522250923714391873652357185101163374950977150829214936039230387625706376713934778873385375582488086205462961139042991664546797362021066081938999660281537596860879414252495949608351649066648594254272314188241185715920283526637402373027396529855631498571685297193020517033784357794223831020791070397249992230576960345185544552280142788704673413055403847038488791910041421887897364099871208624646292906015164161354890370666964030412257423
a = 102197201962123846389438942955101245465045811321520032783251514372432272871077
m = 2**256
t = 0
while True:
t += 4
for seed in Zmod(m)(n * pow(a, -t, m)).nth_root(4, all=True):
lcg = LCG(bits=256, seed=int(seed), a=a, c=0)
p = get_prime(lcg, bits=1024)
if n%p != 0:
continue
flag = pow(c, pow(65537, -1, p-1), p)
flag = bytes.fromhex(f'{int(flag):x}')
print(f'{t = }\n{seed = }\n{p = }\n{flag = }\n')
# hkcert24{c0mpu71n9_subs3qu3nc3s_0f_g30m3tr1c_s3qu3nc3s_1s_fun}
RSA LCG (2)
import os
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime
class LCG:
def __init__(self, bits, a=None, c=None, seed=None):
self.seed = seed
if self.seed is None: self.seed = secrets.randbits(bits) | 1
self.a = a
if self.a is None: self.a = secrets.randbits(bits) | 1
self.c = c
if self.c is None: self.c = secrets.randbits(bits)
self.bits = bits
self.m = 2**bits
def next(self):
self.seed = (self.seed * self.a + self.c) % self.m
return self.seed
def __repr__(self):
return f'LCG(bits={self.bits}, a={self.a}, c={self.c})'
def get_prime(lcg, bits):
while True:
p = 0
for i in range(bits//lcg.bits):
p <<= lcg.bits
p |= lcg.next()
if p.bit_length() != bits: continue
if not is_prime(p): continue
return p
if __name__ == '__main__':
FLAG = os.environb.get(b'FLAG', b'hkcert24{***REDACTED***}')
lcg = LCG(bits=256, a=1)
print(f'{lcg = }')
ps = [get_prime(lcg, bits=1024) for _ in range(4)]
n = reduce(mul, ps)
e = 0x10001
m = int.from_bytes(FLAG, 'big')
c = pow(m, e, n)
print(f'{n = }')
print(f'{e = }')
print(f'{c = }')
lcg = LCG(bits=256, a=1, c=14258939715516539295587731120991968901228171455016001595761489750577784177213)
n = 279784521303926518544200383491171400996467006054806060652945044514173580730320793076951350168517896308345078513333979433742090849938580604359515861344088875721354836410510396140219655796215325682295239294661185563708496490830500773420871847769568879274978173218440545663363350310752698066412613793738234395676975963986090446949443295350235071286869321557833967521199446244573020803085515110891641843096725596572980675877230459500589604078432572911282759481893882548258867802789628543364574694501159808895930747113406016718685856976531978713324829507636743778130758650283045513372598798114943752532619142439604369129493324057181519512588183783756314385380800844831034863151900295735342816476791991454383732133474515109758087482912794282007801160780475284011802960270750792620686906175026995623082009841402872948756740311519047998978234628057595438481437871594714428834059691733188294695393205472914443179153321670750219104306769911019089432918102588905808629421158434486927928786793524017503900505368724824170796339023214910404096208544407500008089429770878575702088992309354303731919302687039737672125268143820658069899761163750521000478474705014645224845757836226858836333259628284972467671764606702417658922805838428375959908059533
e = 65537
c = 12668023009781840908542456747150790958366008947388222673139950309896560492008423201703814113959062916216738813414905779255815616125482715748800637882572776464413794672305560913420843604427904075596817771292191713968187201485479797042112384390953800170012145372635694385419895184449315436204936393181245447065007450494691263361925589404791904565458416407877820052394996905208559706702586674504665164085593562932792149402776674399837342851449263354042894145700586851308674806581185881411576045932596814585050689676622481653401541955765009732517013919996864475158687111703292317464104677422251199063539026204584634157266215824371162154934075299210675220082034930924899581928745732959112210135371763739653442724659470938281648056607023621212384635978368358089470066114660978000389704285586405309891824263306072117253963803228130111794609335559502199299483268104278641029669532263556375348912538425414244341532656162870453118645106346455731193356791582571147804331894783849241501307040707035938949680381788534081674899875606974239354654393310878542209938345878740320797711262798440736790479007006147569066845667894663218494368548456732889916013895067014484182872120996578247736683746861794081478555452926231507488557048374863197550101866
In this one a=1.
So each lcg output is just s + x*c for some x.
import secrets
class LCG:
def __init__(self, bits, a=None, c=None, seed=None):
self.seed = seed
if self.seed is None: self.seed = secrets.randbits(bits) | 1
self.a = a
if self.a is None: self.a = secrets.randbits(bits) | 1
self.c = c
if self.c is None: self.c = secrets.randbits(bits)
self.bits = bits
self.m = 2**bits
def next(self):
self.seed = (self.seed * self.a + self.c) % self.m
return self.seed
def get_prime(lcg, bits):
i = 0
while True:
i += 1
p = 0
for _ in range(bits//lcg.bits):
p <<= lcg.bits
p |= lcg.next()
if p.bit_length() != bits: continue
if not is_prime(p): continue
return p, i
c = 14258939715516539295587731120991968901228171455016001595761489750577784177213
a = 1
m = 2**256
s = secrets.randbits(256) | 1
print(f'{s = }')
lcg = LCG(bits=256, seed=s, a=1, c=c)
p1, i1 = get_prime(lcg, bits=1024)
p2, i2 = get_prime(lcg, bits=1024)
p3, i3 = get_prime(lcg, bits=1024)
p4, i4 = get_prime(lcg, bits=1024)
n = p1*p2*p3*p4
# each LCG output is some (s + x*c) % m
x1 = i1 - 1
x2 = i1 + i2 - 1
x3 = i1 + i2 + i3 - 1
x4 = i1 + i2 + i3 + i4 - 1
print(f'{x1 = }\n{x2 = }\n{x3 = }\n{x4 = }\n')
assert p1 == (s + (x1*4+4)*c) % m + \
((s + (x1*4+3)*c) % m) * 2**256 + \
((s + (x1*4+2)*c) % m) * 2**512 + \
((s + (x1*4+1)*c) % m) * 2**768
# the mod m's are annoying so let's get rid of them
# replace each with - k*m
k1 = ((s + (x1*4+1)*c) - ((s + (x1*4+1)*c) % m)) // m
k2 = ((s + (x2*4+1)*c) - ((s + (x2*4+1)*c) % m)) // m
k3 = ((s + (x3*4+1)*c) - ((s + (x3*4+1)*c) % m)) // m
k4 = ((s + (x4*4+1)*c) - ((s + (x4*4+1)*c) % m)) // m
print(f'{k1 = }\n{k2 = }\n{k3 = }\n{k4 = }\n')
assert (s + (x1*4+1)*c) % m == s + (x1*4+1)*c - k1*m
# k might be different for consecutive lcg outputs,
# but through testing, only by a maximum difference of 1
# so use some new variables j that are either 0 or 1
j1_2 = ((s + (x1*4+2)*c) - ((s + (x1*4+2)*c) % m)) // m - k1
j1_3 = ((s + (x1*4+3)*c) - ((s + (x1*4+3)*c) % m)) // m - k1
j1_4 = ((s + (x1*4+4)*c) - ((s + (x1*4+4)*c) % m)) // m - k1
#print(f'{j1_2 = }\n{j1_3 = }\n{j1_4 = }\n')
assert (s + (x1*4+2)*c) % m == (s + (x1*4+2)*c) - (k1 + j1_2)*m
j2_2 = ((s + (x2*4+2)*c) - ((s + (x2*4+2)*c) % m)) // m - k2
j2_3 = ((s + (x2*4+3)*c) - ((s + (x2*4+3)*c) % m)) // m - k2
j2_4 = ((s + (x2*4+4)*c) - ((s + (x2*4+4)*c) % m)) // m - k2
#print(f'{j2_2 = }\n{j2_3 = }\n{j2_4 = }\n')
j3_2 = ((s + (x3*4+2)*c) - ((s + (x3*4+2)*c) % m)) // m - k3
j3_3 = ((s + (x3*4+3)*c) - ((s + (x3*4+3)*c) % m)) // m - k3
j3_4 = ((s + (x3*4+4)*c) - ((s + (x3*4+4)*c) % m)) // m - k3
#print(f'{j3_2 = }\n{j3_3 = }\n{j3_4 = }\n')
j4_2 = ((s + (x4*4+2)*c) - ((s + (x4*4+2)*c) % m)) // m - k4
j4_3 = ((s + (x4*4+3)*c) - ((s + (x4*4+3)*c) % m)) // m - k4
j4_4 = ((s + (x4*4+4)*c) - ((s + (x4*4+4)*c) % m)) // m - k4
#print(f'{j4_2 = }\n{j4_3 = }\n{j4_4 = }\n')
# now sub all these variables into our expression for p
assert p1 == (s + (x1*4+4)*c) - (k1+j1_4)*m + \
((s + (x1*4+3)*c) - (k1+j1_3)*m) * 2**256 + \
((s + (x1*4+2)*c) - (k1+j1_2)*m) * 2**512 + \
((s + (x1*4+1)*c) - k1*m) * 2**768
# factor:
q = 2**768 + 2**512 + 2**256 + 1
r = c*(2**768 + 2*2**512 + 3*2**256 + 4)
assert p1 == q*(s + 4*x1*c - k1*m) + m*(-j1_2*2**512 - j1_3*2**256 - j1_4) + r
assert p2 == q*(s + 4*x2*c - k2*m) + m*(-j2_2*2**512 - j2_3*2**256 - j2_4) + r
assert p3 == q*(s + 4*x3*c - k3*m) + m*(-j3_2*2**512 - j3_3*2**256 - j3_4) + r
assert p4 == q*(s + 4*x4*c - k4*m) + m*(-j4_2*2**512 - j4_3*2**256 - j4_4) + r
# Well now what…
# if you create an equation by multiplying all p’s in ZZ, you’re going to get a non-linear equation…
# if you create an equation by multiplying all p’s in Zmod(q), all your unknowns will just disappear…
# Mystiz actually works in Zmod(q**2)! It results in a nice linear equation we can perform LLL on!
PR.<s,k1,k2,k3,k4,x1,x2,x3,x4> = PolynomialRing(Zmod(q**2))
p1 = q*(s + 4*x1*c - k1*m) + m*(-j1_2*2**512 - j1_3*2**256 - j1_4) + r
p2 = q*(s + 4*x2*c - k2*m) + m*(-j2_2*2**512 - j2_3*2**256 - j2_4) + r
p3 = q*(s + 4*x3*c - k3*m) + m*(-j3_2*2**512 - j3_3*2**256 - j3_4) + r
p4 = q*(s + 4*x4*c - k4*m) + m*(-j4_2*2**512 - j4_3*2**256 - j4_4) + r
f = p1*p2*p3*p4 - n
M = (
identity_matrix(QQ, 10)
.augment(vector(f.coefficients()))
.stack(vector([0]*10 + [q**2]))
)
M[:, 0] /= m
M = M.LLL()
M[:, 0] *= m
for row in M:
seed = abs(row[0])
if row[-1] != 0 or abs(row[-2]) != 1 or seed % 2 != 1:
continue
p, _ = get_prime(LCG(a=1, c=c, seed=seed, bits=256), bits=1024)
print(n%p == 0)
final solver:
from itertools import product
from tqdm import tqdm
class LCG:
def __init__(self, bits, a=None, c=None, seed=None):
self.seed = seed
self.a = a
self.c = c
self.bits = bits
self.m = 2**bits
def next(self):
self.seed = (self.seed * self.a + self.c) % self.m
return self.seed
def get_prime(lcg, bits):
while True:
p = 0
for _ in range(bits//lcg.bits):
p <<= lcg.bits
p |= lcg.next()
if p.bit_length() != bits: continue
if not is_prime(p): continue
return p
c = 14258939715516539295587731120991968901228171455016001595761489750577784177213
m = 2**256
n = 279784521303926518544200383491171400996467006054806060652945044514173580730320793076951350168517896308345078513333979433742090849938580604359515861344088875721354836410510396140219655796215325682295239294661185563708496490830500773420871847769568879274978173218440545663363350310752698066412613793738234395676975963986090446949443295350235071286869321557833967521199446244573020803085515110891641843096725596572980675877230459500589604078432572911282759481893882548258867802789628543364574694501159808895930747113406016718685856976531978713324829507636743778130758650283045513372598798114943752532619142439604369129493324057181519512588183783756314385380800844831034863151900295735342816476791991454383732133474515109758087482912794282007801160780475284011802960270750792620686906175026995623082009841402872948756740311519047998978234628057595438481437871594714428834059691733188294695393205472914443179153321670750219104306769911019089432918102588905808629421158434486927928786793524017503900505368724824170796339023214910404096208544407500008089429770878575702088992309354303731919302687039737672125268143820658069899761163750521000478474705014645224845757836226858836333259628284972467671764606702417658922805838428375959908059533
e = 65537
ct = 12668023009781840908542456747150790958366008947388222673139950309896560492008423201703814113959062916216738813414905779255815616125482715748800637882572776464413794672305560913420843604427904075596817771292191713968187201485479797042112384390953800170012145372635694385419895184449315436204936393181245447065007450494691263361925589404791904565458416407877820052394996905208559706702586674504665164085593562932792149402776674399837342851449263354042894145700586851308674806581185881411576045932596814585050689676622481653401541955765009732517013919996864475158687111703292317464104677422251199063539026204584634157266215824371162154934075299210675220082034930924899581928745732959112210135371763739653442724659470938281648056607023621212384635978368358089470066114660978000389704285586405309891824263306072117253963803228130111794609335559502199299483268104278641029669532263556375348912538425414244341532656162870453118645106346455731193356791582571147804331894783849241501307040707035938949680381788534081674899875606974239354654393310878542209938345878740320797711262798440736790479007006147569066845667894663218494368548456732889916013895067014484182872120996578247736683746861794081478555452926231507488557048374863197550101866
q = 2**768 + 2**512 + 2**256 + 1
r = c*(2**768 + 2*2**512 + 3*2**256 + 4)
for it in tqdm(product([0, 1], repeat=12), total=int(2**12)):
j1_2, j1_3, j1_4, j2_2, j2_3, j2_4, j3_2, j3_3, j3_4, j4_2, j4_3, j4_4 = it
PR.<s,k1,k2,k3,k4,x1,x2,x3,x4> = PolynomialRing(Zmod(q**2))
p1 = q*(s + 4*x1*c - k1*m) + m*(-j1_2*2**512 - j1_3*2**256 - j1_4) + r
p2 = q*(s + 4*x2*c - k2*m) + m*(-j2_2*2**512 - j2_3*2**256 - j2_4) + r
p3 = q*(s + 4*x3*c - k3*m) + m*(-j3_2*2**512 - j3_3*2**256 - j3_4) + r
p4 = q*(s + 4*x4*c - k4*m) + m*(-j4_2*2**512 - j4_3*2**256 - j4_4) + r
f = p1*p2*p3*p4 - n
coeffs = f.coefficients()
M = (
identity_matrix(QQ, 10)
.augment(vector(coeffs))
.stack(vector([0]*10 + [q**2]))
)
M[:, 0] /= 2**256
M = M.LLL()
M[:, 0] *= 2**256
for row in M:
seed = abs(row[0])
if row[-1] != 0 or abs(row[-2]) != 1 or seed % 2 != 1:
continue
p = get_prime(LCG(a=1, c=c, seed=seed, bits=256), bits=1024)
print(f'{p = }')
print(n%p == 0)
flag = bytes.fromhex(f'{int(pow(ct, pow(65537, -1, p-1), p)):x}')
print(f'{flag = }')
# hkcert24{surpr1s3_lll4t71c3_r3duc710n_t1m3}
RSA LCG (3)
import os
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime
class LCG:
def __init__(self, bits, a=None, c=None, seed=None):
self.seed = seed
if self.seed is None: self.seed = secrets.randbits(bits) | 1
self.a = a
if self.a is None: self.a = secrets.randbits(bits) | 1
self.c = c
if self.c is None: self.c = secrets.randbits(bits)
self.bits = bits
self.m = 2**bits
def next(self):
self.seed = (self.seed * self.a + self.c) % self.m
return self.seed
def __repr__(self):
return f'LCG(bits={self.bits}, a={self.a}, c={self.c})'
def get_prime(lcg, bits):
while True:
p = 0
for i in range(bits//lcg.bits):
p <<= lcg.bits
p |= lcg.next()
if p.bit_length() != bits: continue
if not is_prime(p): continue
return p
if __name__ == '__main__':
FLAG = os.environb.get(b'FLAG', b'hkcert24{***REDACTED***}')
seed = secrets.randbits(128)<<128 | 1
lcg = LCG(bits=256, seed=seed)
print(f'{lcg = }')
ps = [get_prime(lcg, bits=1024) for _ in range(4)]
n = reduce(mul, ps)
e = 0x10001
m = int.from_bytes(FLAG, 'big')
c = pow(m, e, n)
print(f'{n = }')
print(f'{e = }')
print(f'{c = }')
lcg = LCG(bits=256, a=14766004292360945258404852367497617471774948936126805425073927394403062559771, c=101392444572529008969348961056906071660419768871029068095780498478077435335658)
n = 310104949044058363811425892282439667555795850923698164575500719920877363952490328278993741848588550303907803963138208625777769116407165079299045658359072735954939955634899149028890186203432587177185672614983999894171325785452784795686085757918290966774324125319406224747711723917236527562556229579589022628862590296281590323788478820477333016394079937231878378358046269624402362566235154381484471820688582120004595351405438024178098190005187895688879764539037795309008703147966413618274215850034115978270168263624156747737483336047033398686990065931568589053366201551840168657333564635190953575770912434947264202860664609208924668470174089395139643640441218757659152083626042918967413234744394606549606305861281752161107561439760204185976944782327736965087510398008449771008025699947582049442588729371212204993669594933838721600502189158688622194652824336960901728311819450912079584032482610919375366829986623070788751982011540521220055895553821778224253746970625666841786339189340344498152279172317609743104777470108401770109956350920020610131660906732383196598286142112787914912796448301345111823730145040316068582039211121377301361760688564938322941885358577303167411970251703604232966219027983536858119778300500933101751641899457
e = 65537
c = 103062216319994633883021726707255505833894115982244229797744500400724941059411346264133479322957473182662752018633592486294774530211270693527482730004815628242002327808204776228223444383519632042858531074466552102288702530352869324049976713089889252600765238196110451324303956172732401402047005544975223308718486936799382134071405038584109821524691964342940757473561547043393942877521141027936710682878315017107714350048208655766169663561363722598270709129397838087810818396682268983758680728353233325680608113581239966748966828100455121487936700949018790286804701500925964419202040562160087415752569883786048654250026952720505649274955681447219364518875892085854376617187428517680579374255991868541726338897567149638047885985817814723274557132684796698662679779677729590702208805883768828626340945484760552452520907126473183457061321026569739763527385628295340908066618403473190885048961117252304808518351740671498261396384433967551138018727839531240932197016466713851341150888734655103395641340466366445201973820121462512449662479632578237405866465926851495594436176622348441495580476338358402531879195673909374090632193981789951544889982768669254824649367936539308980191669227919352771464458152027996758074065744620552247585183945
In this one the seed is created as seed = secrets.randbits(128)<<128 | 1
It means that the seed mod 2^128 is just 1!
So do a meet-in-the-middle attack mod 2^128, to recover x1, x2, x3, x4.
Then you form an equation g mod 2^256.
Currently, the beta version of sage is good at solving this, just do .roots(multiplicities=False).
If you don’t have it yet, then lsb pruning is also fun/instructive:
from tqdm import trange, tqdm
a = 14766004292360945258404852367497617471774948936126805425073927394403062559771
c = 101392444572529008969348961056906071660419768871029068095780498478077435335658
n = 310104949044058363811425892282439667555795850923698164575500719920877363952490328278993741848588550303907803963138208625777769116407165079299045658359072735954939955634899149028890186203432587177185672614983999894171325785452784795686085757918290966774324125319406224747711723917236527562556229579589022628862590296281590323788478820477333016394079937231878378358046269624402362566235154381484471820688582120004595351405438024178098190005187895688879764539037795309008703147966413618274215850034115978270168263624156747737483336047033398686990065931568589053366201551840168657333564635190953575770912434947264202860664609208924668470174089395139643640441218757659152083626042918967413234744394606549606305861281752161107561439760204185976944782327736965087510398008449771008025699947582049442588729371212204993669594933838721600502189158688622194652824336960901728311819450912079584032482610919375366829986623070788751982011540521220055895553821778224253746970625666841786339189340344498152279172317609743104777470108401770109956350920020610131660906732383196598286142112787914912796448301345111823730145040316068582039211121377301361760688564938322941885358577303167411970251703604232966219027983536858119778300500933101751641899457
e = 65537
ct = 103062216319994633883021726707255505833894115982244229797744500400724941059411346264133479322957473182662752018633592486294774530211270693527482730004815628242002327808204776228223444383519632042858531074466552102288702530352869324049976713089889252600765238196110451324303956172732401402047005544975223308718486936799382134071405038584109821524691964342940757473561547043393942877521141027936710682878315017107714350048208655766169663561363722598270709129397838087810818396682268983758680728353233325680608113581239966748966828100455121487936700949018790286804701500925964419202040562160087415752569883786048654250026952720505649274955681447219364518875892085854376617187428517680579374255991868541726338897567149638047885985817814723274557132684796698662679779677729590702208805883768828626340945484760552452520907126473183457061321026569739763527385628295340908066618403473190885048961117252304808518351740671498261396384433967551138018727839531240932197016466713851341150888734655103395641340466366445201973820121462512449662479632578237405866465926851495594436176622348441495580476338358402531879195673909374090632193981789951544889982768669254824649367936539308980191669227919352771464458152027996758074065744620552247585183945
class LCG:
def __init__(self, bits, a=None, c=None, seed=None):
self.seed = seed
self.a = a
self.c = c
self.bits = bits
self.m = 2**bits
self.counter = 0
def next(self):
self.seed = (self.seed * self.a + self.c) % self.m
self.counter += 1
return self.seed
def get_prime(lcg, bits):
while True:
p = 0
for _ in range(bits//lcg.bits):
p <<= lcg.bits
p |= lcg.next()
if p.bit_length() != bits: continue
if not is_prime(p): continue
return p
def get_chunk(lcg, bits):
p = 0
for _ in range(bits//lcg.bits):
p <<= lcg.bits
p |= lcg.next()
return p
lcg = LCG(bits=256, seed=1, a=a, c=c)
MAX = 3200
m = 2**128
pp = [get_chunk(lcg, 1024) % m for _ in range(MAX)] # possible prime lsbs
def mitm():
lookup = {}
for x2 in trange(MAX):
for x1 in range(x2):
lookup[pp[x1] * pp[x2] % m] = (x1, x2)
for x4 in trange(MAX):
for x3 in range(x4):
t = n * pow(pp[x3] * pp[x4], -1, m) % m
if t in lookup:
x1, x2 = lookup[t]
return (x1, x2, x3, x4)
x1, x2, x3, x4 = mitm()
#x1, x2, x3, x4 = [2848, 3158, 595, 1597]
print(x1, x2, x3, x4)
x1, x2, x3, x4 = (4*(x1+1), 4*(x2+1), 4*(x3+1), 4*(x4+1))
m = 2**256 # now work mod 2**256
PR.<s> = PolynomialRing(Zmod(m))
def f(x):
return (pow(a, x, m) * s + c * sum([pow(a, i, m) for i in range(x)]))
g = f(x1) * f(x2) * f(x3) * f(x4) - n
g = g.change_ring(ZZ)
sol = {0}
for i in range(256):
cur_sol = set()
for rr in sol:
for b in [0, 1]:
r = b*2**i + rr
M = 2**(i+1)
if 0 != g(r) % M:
continue
cur_sol.add(r)
sol = cur_sol
for seed in tqdm(sol):
if seed % 2**128 != 1:
continue
if seed.bit_length() != 256:
continue
lcg = LCG(bits=256, seed=seed, a=a, c=c)
p = get_prime(lcg, 1024)
if n % p == 0:
break
flag = pow(ct, pow(e, -1, p-1), p)
print(bytes.fromhex(f'{flag:x}'))
# hkcert24{i5_th1s_y3t_4n0th3r_l33tc0d3_f0ur_sum_qu3s71on?}
Mask-mask-RSA
from Crypto.Util.number import getPrime, bytes_to_long
FLAG = b'flag{this_is_a_test_flag}'
def mask_expr(expr):
global e, n
assert '**' not in expr, "My computer is weak, I can't handle this insane calculation"
assert len(expr) <= 4, "Too long!"
assert all([c in r'pq+-*/%' for c in expr]), "Don't try to break me"
res = eval(expr)
return str(pow(res, e, n))[::2]
if __name__ == '__main__':
e = 65537
p, q = 1, 1
while p == q:
while (p-1) % e == 0:
p = getPrime(513)
while (q-1) % e == 0:
q = getPrime(513)
m = bytes_to_long(FLAG)
n = p * q
c = pow(m, e, n)
print(f'{c = }')
for _ in range(6):
expr = input('Input your expression in terms of p, q and r: ')
print(mask_expr(expr))
A variation on https://github.com/OfficialCyberSpace/CSCTF-2024/tree/main/crypto/mask-rsa with e changed from 3 to 65537.
Mystiz’s solver:
from pwn import *
from math import gcd
from Crypto.Util.number import isPrime as is_prime
def attempt(id):
e = 65537
log.info(f'attempt #{id}')
r = process(['python3', 'chall.py'])
#r = remote('localhost', 28134)
r.recvuntil(b'c = ')
c0 = int(r.recvline().decode())
r.sendline(b'p')
r.sendline(b'q')
r.sendline(b'p+q')
r.recvuntil(b'Input your expression in terms of p, q and r: ')
s1 = int(r.recvline().decode()) # a := p^e mod n
r.recvuntil(b'Input your expression in terms of p, q and r: ')
s2 = int(r.recvline().decode()) # b := q^e mod n
r.recvuntil(b'Input your expression in terms of p, q and r: ')
s3 = int(r.recvline().decode()) # c := (p^e + q^e) mod n
# s1 and s2 are of different lengths
if set([len(str(s1)), len(str(s2))]) != set([154, 155]):
r.close()
return False
# Require that a + b = c
if len(str(s3)) != 155:
r.close()
return False
if len(str(s1)) < len(str(s2)):
# p < q
s1, s2 = s2, s1
r.sendline(b'q-p')
r.sendline(b'p+p')
r.sendline(b'-q%p')
else:
# p > q
r.sendline(b'p-q')
r.sendline(b'q+q')
r.sendline(b'-p%q')
# Nonetheless, we have p > q now.
r.recvuntil(b'Input your expression in terms of p, q and r: ')
s4 = int(r.recvline().decode()) # s4 := (p^e - q^e) mod n
r.recvuntil(b'Input your expression in terms of p, q and r: ')
s5 = int(r.recvline().decode()) # s5 := (2^e q^e) mod n
r.recvuntil(b'Input your expression in terms of p, q and r: ')
s6 = int(r.recvline().decode()) # s6 := (-p^e - 2^e q^e) mod n
if len(str(s4)) != 154:
r.close()
return False
if len(str(s5)) != 155:
r.close()
return False
if len(str(s6)) != 154:
r.close()
return False
_a = [None for _ in range(309)]
_b = [None for _ in range(309)]
_s = [None for _ in range(309)] # a+b
_d = [None for _ in range(309)] # a-b
_c = [None for _ in range(309)] # c
_f = [None for _ in range(309)] # c-a
for i in range(155): _a[2*i+0] = int(str(s1)[i])
for i in range(154): _b[2*i+1] = int(str(s2)[i]); _b[0] = 0
for i in range(155): _s[2*i+0] = int(str(s3)[i])
for i in range(154): _d[2*i+1] = int(str(s4)[i]); _d[0] = 0
for i in range(155): _c[2*i+0] = int(str(s5)[i])
for i in range(154): _f[2*i+1] = int(str(s6)[i]); _f[0] = 0
assert _a[0] == 1
a = b = s = d = 0
for i in range(308, 0, -2):
# Fill in the i-th digit
a += _a[i] * 10**(308-i)
s += _s[i] * 10**(308-i)
b = (s - a) % 10**(308-i+1)
d = (a - b) % 10**(308-i+1)
# Fill in the (i-1)-th digit
b += _b[i-1] * 10**(308-i+1)
d += _d[i-1] * 10**(308-i+1)
a = (b + d) % 10**(308-i+2)
s = (a + b) % 10**(308-i+2)
a += _a[0] * 10**308
s += _s[0] * 10**308
c = f = 0
for i in range(308, 0, -2):
# Fill in the i-th digit
c += _c[i] * 10**(308-i)
f = (c - a) % 10**(308-i+1)
# Fill in the (i-1)-th digit
f += _f[i-1] * 10**(308-i+1)
c = (f + a) % 10**(308-i+2)
c += _c[0] * 10**308
f += _f[0] * 10**308
# a = p^e mod n
# b = q^e mod n
# Sanity check
assert int(str(a)[::2]) == s1
assert int(str(b)[::2]) == s2
assert int(str(s)[::2]) == s3
assert int(str(d)[::2]) == s4
assert a + b == s
assert a - b == d
assert c - a == f
# a = p^65537 mod n
# b = q^65537 mod n
# c = 2^65537 * q^65537 mod n
q = gcd(b, c)
for k in range(2, 10**6):
while q % k == 0:
q //= k
assert q.bit_length() == 513
assert is_prime(q)
dq = pow(e, -1, q-1)
p = pow(a, dq, q) + q
assert p.bit_length() == 513
assert is_prime(p)
n = p * q
# Sanity check, the real one
assert int(str(pow(p, e, n))[::2]) == s1
assert int(str(pow(q, e, n))[::2]) == s2
assert int(str(pow(p+q, e, n))[::2]) == s3
assert int(str(pow(p-q, e, n))[::2]) == s4
assert int(str(pow(2*q, e, n))[::2]) == s5
assert int(str(pow(2*q-p, e, n))[::2]) == s6
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
m0 = pow(c0, d, n)
flag = int.to_bytes(m0, (m0.bit_length()+7)//8, 'big')
print(f'{flag = }')
return True
def main():
id = 0
while not attempt(id):
id += 1
if __name__ == '__main__':
main()