# 4096
> I heard 4096 bit RSA is secure, so I encrypted the flag with it.
Given 2 files source.py and output.txt
**output.txt**
```5063044818262689349546481067052560277152768583825797461048343533234972879239682659155894702765781959079059082984180815182574418440572589398433071983557250741951706997461200682654263844788610562573902643381085125976082911294476910155786547493524567231063893110746852349278093493676517767429281515526243583180149919787431112177379704118607502476646097739215044375652078206758127750408292353473677676942875580799403593608239135605307923598655237414878299381511822118457743459711574878291024456900481855007946459091382645700364836778416412720674300534200173875498954894297558726799070654115564322285197448853366633464568677410728501877583102809033848558601197433765401159269846371331652281165634000155777927063299110580323061291654757690658347384655841929618150310860319222676939967572620107832276316304925998118139293762311660071240329782138957362770088691273787358830040621104775963704507191818542565885405938633849553474747184699776816692963098840666843038183442042916232475516202316840679354482839093385626076296376333652878742150358231943536875543518175278329634124185393227633488627151178677901966478684565832316685226626428651627591996365040234526464928756930330004873367220895028105589453914590291325257828519729315640629897212089539145769625632189125456455778939633021487666539864477884226491831177051620671080345905237001384943044362508550274499601386018436774667054082051013986880044122234840762034425906802733285008515019104201964058459074727958015931524254616901569333808897189148422139163755426336008738228206905929505993240834181441728434782721945966055987934053102520300610949003828413057299830995512963516437591775582556040505553674525293788223483574494286570201177694289787659662521910225641898762643794474678297891552856073420478752076393386273627970575228665003851968484998550564390747988844710818619836079384152470450659391941581654509659766292902961171668168368723759124230712832393447719252348647172524453163783833358048230752476923663730556409340711188698221222770394308685941050292404627088273158846156984693358388590950279445736394513497524120008211955634017212917792675498853686681402944487402749561864649175474956913910853930952329280207751998559039169086898605565528308806524495500398924972480453453358088625940892246551961178561037313833306804342494449584581485895266308393917067830433039476096285467849735814999851855709235986958845331235439845410800486470278105793922000390078444089105955677711315740050638```
**source.py**
~~~pythonfrom Crypto.Util.number import getPrime, bytes_to_longfrom private import flag
def prod(lst):	ret = 1	for num in lst:		ret *= num	return ret
m = bytes_to_long(flag)primes = [getPrime(32) for _ in range(128)]n = prod(primes)e = 65537print(n)print(pow(m, e, n))~~~
From the code above, we know that this is classic RSA task. And the first line of output.txt is **n** and the second line is **c**. After doing some google search, i've found that this is multi prime RSA task and ive found solver script as well in [Here](https://gist.github.com/jackz314/09cf253d3451f169c2dbb6bbfed73782). We just need to find the factor **n** using ~~sage from valorant~~ sagemath
~~~python➜  4096 git:(master) ✗ sage┌────────────────────────────────────────────────────────────────────┐│ SageMath version 9.0, Release Date: 2020-01-01                     ││ Using Python 3.8.10. Type "help()" for help.                       │└────────────────────────────────────────────────────────────────────┘sage: list(factor(50630448182.....97293)) [(2148630611, 1), (2157385673, 1), (2216411683, 1), (2223202649, 1), (2230630973, 1), ...... (4276173893, 1)]~~~
then copy the list of factor into solver script.
**solver.py**
~~~python#!/usr/bin/env python2.7
primes = [2148630611, 2157385673, 2216411683, 2223202649, 2230630973, 2240170147, 2278427881, 2293226687, 2322142411, 2365186141, 2371079143, 2388797093, 2424270803, 2436598001, 2444333767, 2459187103, 2491570349, 2510750149, 2525697263, 2572542211, 2575495753, 2602521199, 2636069911, 2647129697, 2657405087, 2661720221, 2672301743, 2682518317, 2695978183, 2703629041, 2707095227, 2710524571, 2719924183, 2724658201, 2733527227, 2746638019, 2752963847, 2753147143, 2772696307, 2824169389, 2841115943, 2854321391, 2858807113, 2932152359, 2944722127, 2944751701, 2949007619, 2959325459, 2963383867, 3012495907, 3013564231, 3035438359, 3056689019, 3057815377, 3083881387, 3130133681, 3174322859, 3177943303, 3180301633, 3200434847, 3228764447, 3238771411, 3278196319, 3279018511, 3285444073, 3291377941, 3303691121, 3319529377, 3335574511, 3346647649, 3359249393, 3380851417, 3398567593, 3411506629, 3417563069, 3453863503, 3464370241, 3487902133, 3488338697, 3522596999, 3539958743, 3589083991, 3623581037, 3625437121, 3638373857, 3646337561, 3648309311, 3684423151, 3686523713, 3716991893, 3721186793, 3760232953, 3789253133, 3789746923, 3811207403, 3833706949, 3833824031, 3854175641, 3860554891, 3861767519, 3865448239, 3923208001, 3941016503, 3943871257, 3959814431, 3961738709, 3978832967, 3986329331, 3991834969, 3994425601, 4006267823, 4045323871, 4056085883, 4073647147, 4091945483, 4098491081, 4135004413, 4140261491, 4141964923, 4152726959, 4198942673, 4205028467, 4218138251, 4227099257, 4235456317, 4252196909, 4270521797, 4276173893]e = 65537c = 15640629897212089539145769625632189125456455778939633021487666539864477884226491831177051620671080345905237001384943044362508550274499601386018436774667054082051013986880044122234840762034425906802733285008515019104201964058459074727958015931524254616901569333808897189148422139163755426336008738228206905929505993240834181441728434782721945966055987934053102520300610949003828413057299830995512963516437591775582556040505553674525293788223483574494286570201177694289787659662521910225641898762643794474678297891552856073420478752076393386273627970575228665003851968484998550564390747988844710818619836079384152470450659391941581654509659766292902961171668168368723759124230712832393447719252348647172524453163783833358048230752476923663730556409340711188698221222770394308685941050292404627088273158846156984693358388590950279445736394513497524120008211955634017212917792675498853686681402944487402749561864649175474956913910853930952329280207751998559039169086898605565528308806524495500398924972480453453358088625940892246551961178561037313833306804342494449584581485895266308393917067830433039476096285467849735814999851855709235986958845331235439845410800486470278105793922000390078444089105955677711315740050638n = 50630448182626893495464810670525602771527685838257974610483435332349728792396826591558947027657819590790590829841808151825744184405725893984330719835572507419517069974612006826542638447886105625739026433810851259760829112944769101557865474935245672310638931107468523492780934936765177674292815155262435831801499197874311121773797041186075024766460977392150443756520782067581277504082923534736776769428755807994035936082391356053079235986552374148782993815118221184577434597115748782910244569004818550079464590913826457003648367784164127206743005342001738754989548942975587267990706541155643222851974488533666334645686774107285018775831028090338485586011974337654011592698463713316522811656340001557779270632991105803230612916547576906583473846558419296181503108603192226769399675726201078322763163049259981181392937623116600712403297821389573627700886912737873588300406211047759637045071918185425658854059386338495534747471846997768166929630988406668430381834420429162324755162023168406793544828390933856260762963763336528787421503582319435368755435181752783296341241853932276334886271511786779019664786845658323166852266264286516275919963650402345264649287569303300048733672208950281055894539145902913252578285197293
def egcd(a, b):    if a == 0:        return (b, 0, 1)    else:        g, y, x = egcd(b % a, a)        return (g, x - (b // a) * y, y)
def modinv(a, m):    g, x, y = egcd(a, m)    if g != 1:        raise Exception('modular inverse does not exist')    else:        return x % m
ts = []xs = []ds = []
for i in range(len(primes)):    ds.append(modinv(e, primes[i]-1))
m = primes[0]
for i in range(1, len(primes)):    ts.append(modinv(m, primes[i]))    m = m * primes[i]
for i in range(len(primes)):    xs.append(pow((c%primes[i]), ds[i], primes[i]))
x = xs[0]m = primes[0]
for i in range(1, len(primes)):    x = x + m * ((xs[i] - x % primes[i]) * (ts[i-1] % primes[i]))    m = m * primes[i]
print hex(x%n)[2:-1].decode("hex")~~~
**FLAG:** corctf{to0_m4ny_pr1m3s55_63aeea37a6b3b22f}
**BONUS**: SAGE

