Description: What is RSA? Really Spicy Applesauce? Ridiculously Smart Alpaca? Random Squirrel Alliance? Nope, not at all. Just some dudes who made a cool public-key cryptosystem!

from Crypto.Util.number import getStrongPrime, getPrime, bytes_to_long as b2l
FLAG = open('flag.txt', 'r').read().strip()
OUT = open('output.txt', 'w')
l = len(FLAG)
flag1, flag2, flag3 = FLAG[:l//3], FLAG[l//3:2*l//3], FLAG[2*l//3:]
# PART 1
e = 0x10001
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
ct = pow(b2l(flag1.encode()), e, n)
OUT.write(f'*** PART 1 ***\ne: {e}\np: {p}\nq: {q}\nct: {ct}')
# PART 2
e = 3
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
ct = pow(b2l(flag2.encode()), e, n)
OUT.write(f'\n\n*** PART 2 ***\ne: {e}\nn: {n}\nct: {ct}')
# PART 3
e = 65537
p = getPrime(24)
q = getPrime(24)
n = p*q
fl = round(len(flag3)/4)
f3_parts = [flag3[i:i+4] for i in range(0, len(flag3), 4)]
assert ''.join(f3_parts) == flag3
ct_parts = []
for part in f3_parts:
    pt = b2l(part.encode())
    assert pt < n
    ct = pow(pt, e, n)
    ct_parts.append(ct)
OUT.write(f'\n\n*** PART 3 ***\ne: {e}\nn: {n}\nct: {ct_parts}')

*** PART 1 ***
e: 65537
p: 152933908726088000025981821717328900253841375038873501148415965946834656401640031351528841350980891403699057384028031438869081577476655254545307973436745130347696405243778481262922512227444915738801835842194123487258255790292004204412236314558718035967575479232723997430178018130995420315759809636522091902529
q: 173403581892981708663967289381727914513043623656015065332774927693090954681172215632003125824638611519248812013286298011144213434368768979531792528759533473573346156338400142951284462417074992959330154930806611253683603690442142765076944118447174491399811297223146324861971722035746276165056022562961558299229
ct: 24900222896050719055946861973957246283663114493271057619080357155524140641110166671081924849912377863714741017586072836978357770860853088772671413685690588862677870057778743649753806625109141461870634890427341765490174013453580041222600439459744928592280825572907034701116518706347830413085865254963646096687533779205345001529893651672061316525244476464884343232361498032095529980932018530224029715267731845742371944443150142380656402289372470902457020777826323051802030062577945893807552316343833971210833255536637260838474638607847822451324479398241526919184038034180388382949827367896808363560947298749154349868503
*** PART 2 ***
e: 3
n: 17832697294201997154036617011957221780954165482288666773904510458098283881743910060438108775052144170769164876758249100567442926826366952851643073820832317493086415304740069439166953466125367940677570548218324219386987869433677168670642103353927101790341856159406926994785020050276564014860180970395749578442970075496442876475883003906961049702649859496118324912885388643549649071478725024867410660900848046927547400320456993982744075508818567475254504481562096763749301743619222457897353143558783627148704136084952125284873914605708215421331001883445600583624655438154001230490220705092656548338632165583188199066759
ct: 55717486909410107003108426413232346564412491530111436942121941739686926249314710854996834619
*** PART 3 ***
e: 65537
n: 107710970774233
ct: [18128889449669, 12202311999558, 10705744036504, 23864757944740]p

We Have provided encrypt.py and output files , from the output we can conclude that the flag is divided into 3 parts.

PART 1:

Part 1 is just basic rsa , we need to find the private key d and decrypt it.

phi=(p-1)*(q-1)

d=e^-1(mod)phi

from Crypto.Util.number import *
e= 65537
p= 152933908726088000025981821717328900253841375038873501148415965946834656401640031351528841350980891403699057384028031438869081577476655254545307973436745130347696405243778481262922512227444915738801835842194123487258255790292004204412236314558718035967575479232723997430178018130995420315759809636522091902529
q= 173403581892981708663967289381727914513043623656015065332774927693090954681172215632003125824638611519248812013286298011144213434368768979531792528759533473573346156338400142951284462417074992959330154930806611253683603690442142765076944118447174491399811297223146324861971722035746276165056022562961558299229
ct= 24900222896050719055946861973957246283663114493271057619080357155524140641110166671081924849912377863714741017586072836978357770860853088772671413685690588862677870057778743649753806625109141461870634890427341765490174013453580041222600439459744928592280825572907034701116518706347830413085865254963646096687533779205345001529893651672061316525244476464884343232361498032095529980932018530224029715267731845742371944443150142380656402289372470902457020777826323051802030062577945893807552316343833971210833255536637260838474638607847822451324479398241526919184038034180388382949827367896808363560947298749154349868503
phi=(p-1)*(q-1)
d=pow(e,-1,phi)
n=p*q
flag1=pow(ct,d,n)
print(long_to_bytes(flag1))

Part 1 output: flag{361862d

PART 2:

Here we only have the values of e,n,ct.

The Public key (e) is 3 , which makes the ciphertext vulnerable to cube root attack.

If you the cubed root of ct, and if that is smaller than the cubed root of n, then your plaintext message m is just the cubed root of c.

So no need to find the private key in this case. Solve script for part is given below,

#cube root attack 
from Crypto.Util.number import *
e= 3
n= 17832697294201997154036617011957221780954165482288666773904510458098283881743910060438108775052144170769164876758249100567442926826366952851643073820832317493086415304740069439166953466125367940677570548218324219386987869433677168670642103353927101790341856159406926994785020050276564014860180970395749578442970075496442876475883003906961049702649859496118324912885388643549649071478725024867410660900848046927547400320456993982744075508818567475254504481562096763749301743619222457897353143558783627148704136084952125284873914605708215421331001883445600583624655438154001230490220705092656548338632165583188199066759
ct= 55717486909410107003108426413232346564412491530111436942121941739686926249314710854996834619
def iroot(x, n):
    """Return (y, b) where y is the integer nth root of x and b is True if y is exact."""
    if x == 0:
        return x, True
    k = (x.bit_length() - 1) // n
    y = 1 << k
    for i in range(k - 1, -1, -1):
        z = y | 1 << i
        if z ** n <= x:
            y = z
    return y, x == y ** n
pt = iroot(ct,3)[0]
decrypted = long_to_bytes(pt)
print(decrypted)

Part 2 output: 054e2a9abe41c

PART 3:

Here we have the values of e, n and a list of values for ct,

e: 65537

n: 107710970774233

ct: [18128889449669, 12202311999558, 10705744036504, 23864757944740]

So the idea is to find the private key and iterate it through the list to get the plaintext.

Using http://factordb.com/ I found the factors of n and using p,q calculated phi and found the private key.

use the private key(d) to decrypt the ct one by one, solve script for part 3 is given below,

from Crypto.Util.number import *
e= 65537
n= 107710970774233
ct=[18128889449669, 12202311999558, 10705744036504, 23864757944740]
p=8885719  
q=12121807
phi=(p-1)*(q-1)
d=pow(e,-1,phi)
flag=''
for i in ct:
    f=pow(i,d,n)
    flag += long_to_bytes(f).decode()
    f=''
print(flag)

Finally concatenate all the 3 parts to get the flag,

flag{361862d054e2a9abe41cc315517cfa31}