# I found this super cool function on stack overflow \o/ https://stackoverflow.com/questions/2267362/how-to-convert-an-integer-to-a-string-in-any-base defnumberToBase(n, b): if n == 0: return [0] digits = [] while n: digits.append(int(n % b)) n //= b return digits[::-1]
assertlen(flag) <= 45
flag = int.from_bytes(flag, 'big')
base = int(input("Give me a base! "))
if base < 2: print("Base is too small") quit() if base > 256: print("Base is too big") quit()
print(f'Here you go! {sum(numberToBase(flag, base))}')
context(os='linux', arch='amd64', log_level='debug') m = 0 n = 1 for i in trange(2,256): p = remote('basic-sums.chal-kalmarc.tf', 2256) p.sendlineafter(b'Give me a base! ',str(i).encode()) p.recvuntil(b'go! ') m0 = int(p.recvline()) n0 = i-1 m = crt([m,m0],[n,n0]) n = lcm(n,n0) p.close() print(long_to_bytes(int(m))) # b'kalmar{At_least_it_wasnt_lattices_right???!?}'
# FROM python:3 import random withopen("flag.txt","rb") as f: flag=f.read() for i inrange(2**64): print(random.getrandbits(32)+flag[random.getrandbits(32)%len(flag)]) input()
defgetPrimes(bits, k): p = getPrime(bits) a = random.randint(0, p-1) b = random.randint(0, p-1) l = LCG(p, a, b) return [gmpy2.next_prime(l.next()) for _ inrange(k)]
p, q = getPrimes(1024, 2) n = p*q e = 65537 m = bytes_to_long(flag) c = pow(m, e, n) print(n, c) ''' p = 170302223332374952785269454020752010235000449292324018706323228421794605831609342383813680059406887437726391567716617403068082252456126724116360291722050578106527815908837796377811535800753042840119867579793401648981916062128752925574017615120362457848369672169913701701169754804744410516724429370808383640129 a = 95647398016998994323232737206171888899957187357027939982909965407086383339418183844601496450055752805846840966207033179756334909869395071918100649183599056695688702272113280126999439574017728476367307673524762493771576155949866442317616306832252931038932232342396406623324967479959770751756551238647385191314 b = 122891504335833588148026640678812283515533067572514249355105863367413556242876686249628488512479399795117688641973272470884323873621143234628351006002398994272892177228185516130875243250912554684234982558913267007466946601210297176541861279902930860851219732696973412096603548467720104727887907369470758901838 n = 5593134172275186875590245131682192688778392004699750710462210806902340747682378400226605648011816039948262008066066650657006955703136928662067931212033472838067050429624395919771757949640517085036958623280188133965150285410609475158882527926240531113060812228408346482328419754802280082212250908375099979058307437751229421708615341486221424596128137575042934928922615832987202762651904056934292682021963290271144473446994958975487980146329697970484311863524622696562094720833240915154181032649358743041246023013296745195478603299127094103448698060367648192905729866897074234681844252549934531893172709301411995941527 c = 2185680728108057860427602387168654320024588536620246138642042133525937248576850574716324994222027251548743663286125769988360677327713281974075574656905916643746842819251899233266706138267250441832133068661277187507427787343897863339824140927640373352305007520681800240743854093190786046280731148485148774188448658663250731076739737801267702682463265663725900621375689684459894544169879873344003810307496162858318574830487480360419897453892053456993436452783099460908947258094434884954726862549670168954554640433833484822078996925040310316609425805351183165668893199137911145057639657709936762866208635582348932189646 '''
from secrets import flag, get_random_emojiiiiii from Crypto.Util.number import *
defgenarate_emojiiiiii_prime(nbits, base=0): whileTrue: p = getPrime(base // 32 * 32) if base >= 3else0 for i inrange(nbits // 8 // 4 - base // 32): p = (p << 32) + get_random_emojiiiiii() # 猜一猜 if isPrime(p): return p
m = bytes_to_long(flag.encode( ) + "".join([long_to_bytes(get_random_emojiiiiii()).decode() for _ inrange(5)]).encode()) p = genarate_emojiiiiii_prime(512, 224) q = genarate_emojiiiiii_prime(512)
n = p * q e = "💯" c = pow(m, bytes_to_long(e.encode()), n)
print("p0 =", long_to_bytes(p % 2 ** 256).decode()) print("n =", n) print("c =", c) # p0 = 😘😾😂😋😶😾😳😷 # n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579 # c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
# sage from Crypto.Util.number import * from tqdm import trange
e = bytes_to_long("💯".encode()) p0 = bytes_to_long("😘😾😂😋😶😾😳😷".encode()) n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579 PR.<x> = PolynomialRing(Zmod(n)) for i in trange(0xf09f9880,0xf09f998f): p00 = i*2^256 + p0 f = x*2^288+p00 f = f.monic() roots = f.small_roots(X = 2**224,beta=0.4,epsilon=0.02) if roots: p = int(roots[0])*2^288 + p00 q = n // p print(f"{p = }") print(f"{q = }") break
然后就是e与ϕ不互素,上板子即可
# sage from sage.allimport * from sage.parallel.multiprocessing_sage import parallel_iter # TODO import itertools from tqdm import tqdm from Crypto.Util.number import * import string
defnth_p(y, n, p, k=1): assert is_pseudoprime(p) print('[LOG] Solving pi = %s^%d' % (hex(p), k)) try: xs = Zmod(p**k)(y).nth_root(n, all=True) except: xs = GF(p**k)(y).nth_root(n, all=True) xs = list(set(xs)) xs = [Integer(x) for x in xs] return xs
defnthRSA_p(c, e, p, k=1): assert is_pseudoprime(p) P = Integer(pow(p, k)) phi = euler_phi(P)
rs = [] ei = e whileTrue: r = gcd(phi, ei) if r == 1: break rs += [r] ei //= r r = product(rs) dr = (e // r).inverse_mod(phi) cr = pow(c, dr, P) return nth_p(cr, r, p, k)
defnthRSA_n(c, e, ps, ks=None, checker=None, ret1=False): # ps: p, q, ... assertisinstance(ps, list) if ks == None: ks = [1] * len(ps) else: assertlen(ps) == len(ks) ms = [] for i inrange(len(ps)): mp = nthRSA_p(c, e, ps[i], ks[i]) ms += [mp] total = product([len(x) for x in ms]) print('[Log] Doing crt.\nComplexity = %d: %s' % (total, str([len(x) for x in ms])))
res = [] Ps = [ps[i]**ks[i] for i inrange(len(ps))] for msi in tqdm(itertools.product(*ms), total=total): m = crt(list(msi), Ps) if checker == None: res += [m] continue if checker(m): ifnot ret1: res += [m] continue return m return res
defgenHeaderChecker(hd): ifisinstance(hd, str): hd = hd.encode() assertisinstance(hd, bytes) defcheckHeader(m): try: flag = long_to_bytes(int(m)) if hd in flag: print(flag) returnTrue returnFalse except: returnFalse return checkHeader
defgenStrChecker(dict, n=65537): defcheckStr(m): try: flag = long_to_bytes(int(m)).decode() for fi in flag[:n]: ifnot fi indict: returnFalse print(flag) returnTrue except: returnFalse return checkStr
p = 12424840247075830662687097292458444573014198016321428995092662043898159667123240573630892907827505266982898641483333170032514244713840745287869771915696311 q = 12602471198163266643743702664647336358595911975665358584258749238146841559843060594842063473155049870396568542257767865369797827796765830093256146584311989 e = bytes_to_long("💯".encode()) n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579 c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
ps = [p, q] checker = genHeaderChecker('TGCTF') res = nthRSA_n(c, e, ps, checker=checker) for r in res: flag = long_to_bytes(int(r)) print(flag.decode()) # TGCTF{🙇🏮🤟_🫡🫡🫡_🚩🚩🚩}😃😖😘😨😢