RSA implementation in native Python. This is only a toy implementation used to show how RSA works.

rsa.py

from collections import namedtuple
import typing

KeyPair = namedtuple('KeyPair', ['n', 'e', 'd'])


def inverse(x: int, y: int) -> int:
    a, b, u = 0, y, 1
    while x > 0:
        q = b // x
        x, a, b, u = b % x, u, x, a - q * u
    if b == 1:
        return a % y
    raise ValueError("must be coprimes")


def encrypt(msg: str, key: typing.Tuple[int, int]) -> str:
    result = ""
    n, e = key[0], key[1]
    for c in msg:
        o = ord(c)
        assert o < n, "O <= N"
        cc = pow(o, e, n)
        result += chr(cc)
    return result


def main():
    # Choose two different primes P and Q, where P != Q
    p = 11
    q = 19

    # N is then the product of P * Q
    n = p * q
    phi = (p - 1) * (q - 1)

    # Pick a relative prime (common greatest divisor is 1 for N and E) e to phi that suffices 1 < e < phi
    # The most easy solution is to pick a prime
    e = 7

    d = inverse(e, phi)

    key_pair = KeyPair(n, e, d)
    priv_key = (n, e)
    pub_key = (n, d)
    print("Public key: ({:d},{:d})".format(*priv_key))
    print("Private key: ({:d},{:d})".format(*pub_key))

    plain = "Hello"

    # Encrypt/decrypt plain text
    cypher = encrypt(plain, priv_key)
    print("Cipher:", cypher)
    print(encrypt(cypher, pub_key))



if __name__ == "__main__":
    main()