RSA

Basic RSA

Description

Every CTF has RSA challenge.

Attachment: challenge.py

It is encouraged to have a basic understanding of RSA encryption before solving this!

Solution

Given the source code:

from Crypto.Util.number import bytes_to_long, getPrime

with open("flag.txt",'r') as f:
    flag = f.read().strip()
    
flag = bytes_to_long(flag.encode())

p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
c = pow(flag,e,n)

print(f'n={n}')
print(f'p={p}')
print(f'c={c}')

# n=15138047083336567387598404182117550531094679760081369569736673100835940614119297845724474328598653166682692035358124922093691226637190100662505454325397518583128761198861108433486661764566120192806515017361172003470479755673131103686416541000761949401411714006274727728179082530142674854344098633377634917375822347098405726105428537126400979220983824393630934242161943436579231485042987749145327379107056194186347264459118195219956940514076673315662396819409761346033025245958454058950121320337708219343872646349324376287708828282032716867999245556963140029186988131456310599586122979784177769970304120450653012512511
# p=138159122583150122539720672416651109965259423750397803915903094495596812603681284787472112426702597936630836894327906061362978462737525528215392644981478718358749052442979545783775891762536479603911896809757160718820241487029878002523604067015936695506547062698224984758721835069593092375144244144620366872961
# c=1453596642039151116086413588294421625111538325750688869393297447422986199873311576591406269261932213967119883516135438941788095024502918677407589460879677235723210412609001454986376121948201548608120904323444958939456420627636052032365803420545256681738481067122185206799862991406129261691011405505344276504766164166341017812076778442426876198929664548235013445421974512426707551989910605878929718470021555033308445317698061530848019576675720326051470316876972003948422471576781345019975660130395524998564859708066646547673944167524661953235771625088325779686474745263341018054771598275299015725925842283891824533202

Given the values of n, p and c, we need to find the remaining variable which is d in order to decrypt the cipher.

Below is the solution script:

from Cryptodome.Util.number import long_to_bytes, inverse

n = 15138047083336567387598404182117550531094679760081369569736673100835940614119297845724474328598653166682692035358124922093691226637190100662505454325397518583128761198861108433486661764566120192806515017361172003470479755673131103686416541000761949401411714006274727728179082530142674854344098633377634917375822347098405726105428537126400979220983824393630934242161943436579231485042987749145327379107056194186347264459118195219956940514076673315662396819409761346033025245958454058950121320337708219343872646349324376287708828282032716867999245556963140029186988131456310599586122979784177769970304120450653012512511
p = 138159122583150122539720672416651109965259423750397803915903094495596812603681284787472112426702597936630836894327906061362978462737525528215392644981478718358749052442979545783775891762536479603911896809757160718820241487029878002523604067015936695506547062698224984758721835069593092375144244144620366872961
c = 1453596642039151116086413588294421625111538325750688869393297447422986199873311576591406269261932213967119883516135438941788095024502918677407589460879677235723210412609001454986376121948201548608120904323444958939456420627636052032365803420545256681738481067122185206799862991406129261691011405505344276504766164166341017812076778442426876198929664548235013445421974512426707551989910605878929718470021555033308445317698061530848019576675720326051470316876972003948422471576781345019975660130395524998564859708066646547673944167524661953235771625088325779686474745263341018054771598275299015725925842283891824533202

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

print(f"Flag: {flag}")

Floor division is used to find q so that it will return an integer instead of float. long_to_bytes function is used to convert the decrypted message (long integer) into bytes (readable message).

Flag

GCTF2023{S1mpl3_RSA_n0_pr3ssur3}