Mini-RSA

Crypto - Easy

Description: Decrypting RSA just got a bit more interesting! Don’t forget, you can always simplify 'e'!

Given: p, q, e, c

Directly trying to decrypt using these values results in an error:

from Crypto.Util.number import inverse
from Crypto.Util.number import long_to_bytes

p = 13013195056445077675245767987987229724588379930923318266833492046660374216223334270611792324721132438307229159984813414250922197169316235737830919431103659
q = 12930920340230371085700418586571062330546634389230084495106445639925420450591673769061692508272948388121114376587634872733055494744188467315949429674451947
e = 100
c = 110886661313947816173908115981658339620571560526918289660960169252288610286791854093943168159755480182507940709690550773331393090271095840939446837160952597445303632714973330299193541279697398541542792961783509392552656152310579707871010170438249002720983123078577661000629914516027258039187727198233299377218

n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

ValueError: base is not invertible for the given modulus

This is probably because e isn't prime and isn't coprime with phi

Implement the algo in this blog:

from Crypto.Util.number import inverse, GCD
from Crypto.Util.number import long_to_bytes

p = 13013195056445077675245767987987229724588379930923318266833492046660374216223334270611792324721132438307229159984813414250922197169316235737830919431103659
q = 12930920340230371085700418586571062330546634389230084495106445639925420450591673769061692508272948388121114376587634872733055494744188467315949429674451947
e = 100
c = 110886661313947816173908115981658339620571560526918289660960169252288610286791854093943168159755480182507940709690550773331393090271095840939446837160952597445303632714973330299193541279697398541542792961783509392552656152310579707871010170438249002720983123078577661000629914516027258039187727198233299377218

n = p * q
phi = (p - 1) * (q - 1)
max = 100

k = 1
while GCD(e, phi//k) != 1:
    k = k * GCD(e, phi//k)

d = inverse(e, phi//k)
g = pow(c, d, n)
for a in range(1, max):
    r = pow(a, phi//k, n)
    m = (r * g) % n
    print(long_to_bytes(m))

This prints possible plaintexts, including the flag