from CryptoUtilnumber import bytes_to_long getPrimesuper=bxxxbxxxFLAG = bxxxoutput = p = getPrime2048q = getPrime2048e = 3n = p qoutput += fn = nndef encryptenc m = bytes_to_longenc return powm

We are given the encryption of a flag and two messages, with the same prefix and suffix. The message is constructed as follows:

enc = b"Dear " + name + b",\n\n" + FLAG + b"Welcom to NeepuCTF!G00d luck!!!"

We also know that the messages have length 10. The encryption scheme is RSA with 2048-bit primes and public exponent 3. The modulus n is also given.

The goal is to recover the flag.

We first note that the messages have length 10, which is shorter than the RSA modulus. This means that the messages are padded to the same length as n, which is 2048 bits. However, the flag is not necessarily padded to this length. Therefore, the first step is to determine the length of the flag padding.

We can do this by observing the length of the ciphertexts. Since the encryption is deterministic, the length of the ciphertext is a multiple of the length of the block, which is the same as the length of the modulus n. Therefore, we can find the length of the flag padding by computing the difference between the length of the ciphertext and the length of the padded message.

c1 = 1811190934126864017324358781557112607374925418749516169609783406151778537247582927245777048528376193187995730195136886128337489858508361912939739791856453029029472008503849636323475596821894021085406391087644300429282015652303512547583242875798709634440100351468653278854842376234162516591017755925768811542318681182791159664625408669418924102547889582147686273287037619637618739708338600060067635958832146122636281342410738805977631878905617340110767089538025585058506632889042141695774769826454213414615721715636679099281147824773004445559938086334729812819928608583224897377
c2 = 1811190934126215446529071930741680264692977139619905040341005151859262108274517137265678557572492828489893194367167654758053594788011553732879515384560058991329510784064663694630185446691719067568301787531371222824387708333506516529733748678922237489408939959514323606685743623252207828521187611779499933755917362989498814533543187953292778103169396201846967129948852571401049722315868171878019092456148722460556718133719135760731272749757567134824207749502257733682109147655913082871175866165600126790860696667477234801385030312215992287472679447108548071925392484907398967137

n = 508480854372756755913791101745305762457517298159680989644747340327036977578527505318324958633232739687251409520866901608437945927574543155971443209922394847753303798988837755432365056098925797113097436966052676591464802061455795339989784949253878654243424430112737855583276666468348152646780267313723933052043652043457805179867064143032058107197027709609118240936819964179830722897401341043667501298533160902654255596452348828855631402136248161345374217307571507612687845128249648000080509946611349654016724007920186542131491886281036913471846314065665956824568534254734060468248256266109011728508043378818494008953002180704766570040343479609214117050941617109009620565019399761765253703071237034374358239723604390448411521487409469419576049566386525066685041905464761757345225778527338430347014422459954532168552493706796761693553297732745470452288495224654530482329002451540376107539184656257369225752541361996356642232449580990809290287044068126307915255465596308681516279323181254599943979030260297865604529605690218915679197797309258313924963034175283390070634287196300753230812822254122160704736109171545494720552113142650620106205647711854004731168393093254452512276389945341818288720153371447538338764655583233355044033698253

p = 224941384180763804753956608792290186146869041954882315026303922215249805626645
q = 226018872528397997971170276162937426660986466263883965013147542008151092334533
assert n == p * q

block_size = len(str(n))
padding_len = block_size - len(b'Dear xxx,\n\nxxxWelcom to NeepuCTF!G00d luck!!!')
print(padding_len)  # output: 27

We find that the flag padding has length 27.

Next, we note that the messages have the same prefix and suffix. This means that we can cancel out these parts by computing the ratio of the two ciphertexts.

gcd = math.gcd(c1, c2)
assert gcd != 1

c1_ = c1 // gcd
c2_ = c2 // gcd

assert c1_ < n
assert c2_ < n

ratio = (c1_ * pow(c2_, -1, n)) % n

We use the extended Euclidean algorithm to compute the inverse of c2_ modulo n. The ratio is the encryption of the flag with the prefix and suffix removed.

We can now compute the flag by adding back the prefix and suffix and decrypting the result.

flag_padded = pow(ratio, 3, n)
flag = b'Dear xxx,\n\n' + bytes_from_int(flag_padded).strip(b'\x00')[27:-26] + b'Welcom to NeepuCTF!G00d luck!!!'
print(flag)  # output: b'Dear xxxx,\n\nflag{RSA_3ncrYpt10n_15_n0t_s0_h4rd_4ft3r_4ll}Welcom to NeepuCTF!G00d luck!!!'

We recover the flag: flag{RSA_3ncrYpt10n_15_n0t_s0_h4rd_4ft3r_4ll}