# RSA is easy #1

In this exercise we are given two files:

1. c – a file containing an RSA public key and an encrypted flag.
2. rsa.py – an RSA implementation:
import random
from my_math import next_prime

from flag import flag

def egcd(a, b):
x, y, u, v = 0, 1, 1, 0
while a != 0:
q, r = b//a, b % a
m, n = x-u*q, y-v*q
b, a, x, y, u, v = a, r, u, v, m, n
gcd = b
return gcd, x, y

def gen_keys(p, q):
e = 65537
n = p * q
phi = (p - 1) * (q - 1)
gcd, d, b = egcd(e, phi)
# Keys:((pub),  (priv))
return ((e, n), (d, n))

def enc(key, p):
e, n = key
cipher = [pow(ord(char), e, n) for char in p]
return cipher

def dec(pk, c):
key, n = pk
plain = [chr(pow(char, key, n)) for char in c]
return ''.join(plain)

p = next_prime(random.SystemRandom().getrandbits(512))
q = next_prime(random.SystemRandom().getrandbits(512))

flag_key=gen_keys(p, q)

print("Public key:")
print(flag_key)

flag_c=(enc(flag_key, flag))

print("Encrypted flag:")
print(flag_c)

As we can see, encryption is performed on each byte separately.
Given the public key, we can encrypt all possible byte values and create a mapping between encrypted bytes to plaintext bytes.
This mapping is then applied on the ciphertext and the flag is obtained.