small ant-eating rabbits

problem

You thought it was Rivest-Shamir-Adleman, but it was me, Rabin!

#!/usr/bin/env python3

from Crypto.Util.number import *
from SECRET import FLAG

def get(num):
    while True:
        p = getPrime(num)
        if p % 4 == 3:
            return p

p,q = get(512),get(512)
n = p*q

m = bytes_to_long(FLAG)
e = 2
c = pow(m,e,n)

print(f"e = {e}\nn = {n}\nc = {c}")

nc eth007.me 42099

sample outputs:

e = 2
n = 136762088700205784893984420325079113985982624450774351393794751756555765566974409001224588597491831786403339609029293912729153032344979929616582899970285316423789679744930099572981940901084519656719834065601578348516697207625337400957727713594011284162290847287907878125286054301373187647391555968208476322037
c = 73702707879144707423816439646387584517363844494220143898044812190922429054425236483166119574760994918745273087431242828976190835215504937191703240903080161775017106246302023245935055533081541213888916660854671920741548538753323188970393301748296138223547430037612427123530166759179097022977340687696946806177

e = 2
n = 170142059295441555912422397113615345157111806157117425474382791195106782233666480512037587233059420083664633920273279561004431462366271735654806935114327971663722194363433939492198290235055150282439951876926851251352394301204911274894944684291914005623702971600908650582411322234395198493220679215186080186317
c = 118950259898062836821778215496023422310771142724458219618063361759234432246152374112493199884266246479302936688317687858252121387382660537999578105839266032275946698367713693125617206329668179189159532162276656500206400092110977953391491421348575355920555784559980883970846483415001561602087613155606748822298

e = 2
n = 89122595133981132614767941813442938227804872212739390357889692852661742260720455386631427644435514622971361346894873445651201210373983622659399056487998633806890197276693999883760250496164469880680083443980456756788171832162199969740971336511378463784894546956482473037904841546983053812261564736618343609337
c = 20585700759358504082988834503726953438777621357785028305064499907763331492646740508987857037923729268613087830721352776134372489276445411511083037714481381901387527052362393725756080956097838037849430713377145734080014892411897267663571552963090755950261606529478660151087687450387915128376871532567659935684

e = 2
n = 91595356828271295680196917041206909680700932152108416858504920429117619384744056395987928535233308170265521327441773226295125142289438087814373460973627145133936294934941191079121823765252727416570138612088798789092501786847041013785962407512483383483652318455059762035250102248649729814181550231982467732549
c = 87248404619129527495142732588481268005597026302873615796687208662883968425179770011797174494627008622234294390555223185864751490551822864580162547089542145646576481319647610244619300884271323518934458446536037530245504581288070240351316490106786848031209829526245815973409885998199718899621262859373451882039

solution

this is the rabin cryptosystem where c = (m**2) % n

we can solve a system of modular equations using the Chinese Remainder Theorem

import socket
import libnum


HOST = "eth007.me"
PORT = 42099


def get_pair() -> tuple[int, int]:
    with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
        s.connect((HOST, PORT))
        data = s.recv(2048).decode('ascii')
        n = None
        c = None
        for line in data.splitlines(False):
            if line.startswith("n = "):
                n = int(line[4:])
            if line.startswith("c = "):
                c = int(line[4:])
        return n, c


remote = True
buncha_n = []
buncha_c = []
for _ in range(20):
    add_n, add_c = get_pair()
    if add_n is None or add_c is None:
        continue
    print(add_c, add_n)
    buncha_n.append(add_n)
    buncha_c.append(add_c)
    print(f"Got pair #{_+1}")


msquared = libnum.solve_crt(
    tuple(buncha_c),
    tuple(buncha_n)
)

print(msquared)

this gets us our m**2 of 4264818727870941534795252586064804803783264207700426630363121855538449149268153611125689806182739871654665209944210683231827731765178801238535609212404313744540781781278852975938016354694814730786846228466493151550581648159688925487075909630289515346380093127982677914002170072911131499734079874680846246620935625991256367717625623454985137950691775996596993805633476470195935474756688093079993772970809038601

we can take the sqrt of that using math.isqrt and then using pycryptodome’s long_to_bytes get the flag

>>> from Crypto.Util.number import *
>>> from math import isqrt
>>> long_to_bytes(isqrt(4264818727870941534795252586064804803783264207700426630363121855538449149268153611125689806182739871654665209944210683231827731765178801238535609212404313744540781781278852975938016354694814730786846228466493
151550581648159688925487075909630289515346380093127982677914002170072911131499734079874680846246620935625991256367717625623454985137950691775996596993805633476470195935474756688093079993772970809038601))
b'ictf{hAstaD_str1k3s_aGa!n18230842989032184879028542848403284098329048218985284104801}'