Broken RSA

I tried to send you an important message with RSA, however I messed up my RSA implementation really badly. Can you still recover the flag?

output.txt

n = 27772857409875257529415990911214211975844307184430241451899407838750503024323367895540981606586709985980003435082116995888017731426634845808624796292507989171497629109450825818587383112280639037484593490692935998202437639626747133650990603333094513531505209954273004473567193235535061942991750932725808679249964667090723480397916715320876867803719301313440005075056481203859010490836599717523664197112053206745235908610484907715210436413015546671034478367679465233737115549451849810421017181842615880836253875862101545582922437858358265964489786463923280312860843031914516061327752183283528015684588796400861331354873
e = 16
ct = 11303174761894431146735697569489134747234975144162172162401674567273034831391936916397234068346115459134602443963604063679379285919302225719050193590179240191429612072131629779948379821039610415099784351073443218911356328815458050694493726951231241096695626477586428880220528001269746547018741237131741255022371957489462380305100634600499204435763201371188769446054925748151987175656677342779043435047048130599123081581036362712208692748034620245590448762406543804069935873123161582756799517226666835316588896306926659321054276507714414876684738121421124177324568084533020088172040422767194971217814466953837590498718

Solution

This WriteUp Solution is password protected by the flag of the challenge.

Flag:

Things here to notice are:

• n is prime
• $\phi$ is not coprime to e,so we do't have a unique decryption
• $(mx)^e \equiv c(mod \space n) \Rightarrow x^e \equiv c(mod \space n)$

So we need to find roots of unity for modulo n

solve.py

from Crypto.Util.number import *
from sage.all_cmdline import *
n = 27772857409875257529415990911214211975844307184430241451899407838750503024323367895540981606586709985980003435082116995888017731426634845808624796292507989171497629109450825818587383112280639037484593490692935998202437639626747133650990603333094513531505209954273004473567193235535061942991750932725808679249964667090723480397916715320876867803719301313440005075056481203859010490836599717523664197112053206745235908610484907715210436413015546671034478367679465233737115549451849810421017181842615880836253875862101545582922437858358265964489786463923280312860843031914516061327752183283528015684588796400861331354873
e = 16
ct = 11303174761894431146735697569489134747234975144162172162401674567273034831391936916397234068346115459134602443963604063679379285919302225719050193590179240191429612072131629779948379821039610415099784351073443218911356328815458050694493726951231241096695626477586428880220528001269746547018741237131741255022371957489462380305100634600499204435763201371188769446054925748151987175656677342779043435047048130599123081581036362712208692748034620245590448762406543804069935873123161582756799517226666835316588896306926659321054276507714414876684738121421124177324568084533020088172040422767194971217814466953837590498718

def roots_of_unity(e, phi, n):
    phi_coprime = phi
    while gcd(phi_coprime, e) != 1:
        phi_coprime //= gcd(phi_coprime, e)

    # we have gcd(phi,e) roots of unity but can be for any i so take upto 100
    roots = set(pow(i, phi_coprime, n) for i in range(1,100))
    
    assert all(pow(root, e, n) == 1 for root in roots)
    return roots, phi_coprime

phi = n - 1

roots, phi_coprime = roots_of_unity(e, phi, n)

d = inverse_mod(e, phi_coprime)
pt = pow(ct, d, n)
assert pow(pt, e, n) == ct

# Use the roots of unity to get all other possible plaintexts
pts = [(pt * root) % n for root in roots]
pts = [long_to_bytes(int(pt)) for pt in pts]
for pt in pts:
    try:
        print(pt.decode())
    except:
        pass

After running the script, we get the flag crypto{m0dul4r_squ4r3_r00t}