Naive implementation of RSA in python

naive_rsa.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
Implementazione naif di RSA

Uso:
$ python naive_rsa.py
"""

from random import randint


ALICE = "Alice"
BOB = "Bob"


def gcd(a, b):
    """
    Ritorna il MCD di a e b.
    """
    if b == 0:
        return a

    return gcd(b, a % b)


def egcd(a, b):
    """
    Algoritmo di Euclide esteso
    https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
    Ritorna (g, x, y) t.c. a*x + b*y = g = gcd(x, y)
    """
    if a == 0:
        return (b, 0, 1)

    g, x, y = egcd(b % a, a)
    return (g, y - (b // a) * x, x)


def private_exponent(e, phi):
    """
    Calcola l'esponente privato dato quello pubblico e, e phi
    utilizzando l'algoritmo di Euclide esteso
    L'esponente privato, d, è l'inverso moltiplicativo di e modulo phi,
    cioè t.c.: d*e mod phi = 1
    """
    (g, x, y) = egcd(e, phi)
    return x % phi


def public_exponent(phi):
    """
    Ritorna un numero che non divida phi
    """

    for el in range(3, 57, 2):
        if gcd(el, phi) == 1:
            return el


def get_two_rnd_primes():
    """
    Ritorna due primi "a caso"
    Obligatory xkcd: https://xkcd.com/221/
    """
    PRIMES = [
            7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433,
            7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523,
            7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589,
            7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687,
            7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789,
            7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883,
            7901, 7907, 7919,
    ]

    maxindex = len(PRIMES) - 1
    first = PRIMES.pop(randint(0, maxindex))
    second = PRIMES[randint(0, maxindex-1)]

    return [first, second]


def say(who, msg):
    """
    Messaggi pubblici
    """
    if who == BOB:
        template = "\n{} {:-^60}> {}\n"
    else:
        template = "\n{} <{:-^59} {}\n"

    msg = " " + str(msg) + " "
    print(template.format(BOB, msg, ALICE))


def do(who, msg):
    """
    In privato
    """
    print("{} {}".format(who, msg))


def main():
    # Bob sceglie due primi a caso: p e q
    [p, q] = get_two_rnd_primes()
    do(BOB, "sceglie due numeri primi: p = %s e q = %s" % (p, q))

    # Bob calcola il modulo: n
    n = p * q
    do(BOB, 'calcola il modulo n = p*q = %s' % n)

    # Bob calcola il numero di Eulero (toziente): φ(n)
    # facile perché p e q sono primi
    phi = (p - 1) * (q - 1)
    do(BOB, 'calcola φ(n) = (p-1)*(q-1) = %s' % phi)

    # sceglie 1 < e < φ(n) t.c. gcd(e, φ(n)) = 1
    e = public_exponent(phi)
    do(BOB, 'sceglie 1 < e < φ(n) tale che MCD(e, φ(n)) = 1: e = %s' % e)
    do(BOB, 'ora ha la propria chiave pubblica: (e=%s, n=%s)' % (e, n))

    # calcola d (l'esponente privato) t.c. e*d = 1 mod φ(n)
    d = private_exponent(e, phi)
    do(BOB, 'calcola d < φ(n) tale che d*e = 1 mod φ(n): d = %s' % d)
    do(BOB, 'ora ha la propria chiave privata: (d=%s, n=%s)' % (d, n))

    # Bob invia la chiave pubblica ad Alice su un canale insicuro
    say(BOB, 'La mia chiave pubblica è {e=%s, n=%s}' % (e, n))

    # Il messaggio che Alice vuole mandare a Bob
    msg = 42
    do(ALICE, 'prepara il messaggio: "%s"' % msg)

    # Alice cifra usando la chiave pubblica (e, n) di Bob:
    # (msg^e mod n) è il messaggio cifrato
    # La funzione pow() calcola msg alla e modulo n
    encrypted = pow(msg, e, n)
    do(ALICE, 'cifra il messaggio "%s": msg^e mod n = %s^%s mod %s = %s' %
        (msg, msg, e, n, encrypted))

    # Alice invia il messaggio cifrato a Bob su un canale insicuro
    say(ALICE, encrypted)

    # Bob decifra encrypted usando la propria chiave privata (d, n):
    # (encrypted^d mod n) è il messaggio decifrato
    decrypted = pow(encrypted, d, n)
    do(BOB, 'decifra il messaggio "%s": msg^d mod n = %s^%s mod %s = %s' %
        (encrypted, encrypted, d, n, decrypted))


if __name__ == "__main__":
    main()