# ###########################################################################################################
# Chiffrement RSA complet
# ###########################################################################################################
#
# Ce programme :
#    - choisit automatiquement les nombres premiers p et q (en appliquant un test de primalité)
#    - calcule automatiquement n, phi et la clé publique e
#    - calcule automatiquement la clé privée d (en appliquant l'algorithme d'Euclide étendu)
#    - la clé publique (n,e) et la clé privée (n,d) sont enregistrées dans 2 tuples
#    - chiffre un message avec la clé publique (n,e)
#    - déchiffre le message avec la clé privée (n,d)
#    - utilise des clés publique (n,e) et privée (n,d) différentes à chaque lancement
#
# Mars 2025
# nsi.gecif.net
# ###########################################################################################################

from random import *

# ---------------------------------------------------------------------
#   Déclaration des fonctions
# ---------------------------------------------------------------------

# Fonction premier(n): elle renvoie True si l'entier n est un nombre premier
def premier(n):
    if n<2: # cas particulier du 1
        return False
    elif n==2: # cas particulier du 2
        return True
    elif n%2==0: # les nombres pairs
        return False
    else: # n est impair et supérieur à 2 : est-il premier ?
        a=3
        while True:
            if a>=n**0.5+1:
                return True
            if n%a==0:
                return False
            a=a+2

def euclide_etendu(a,b): # applique l'algorithme d'Euclide étendu pour calculer la clé privée d
    if a==0:
        return (b,0,1)
    else:
        g,x1,y1 = euclide_etendu(b%a,a)
        x=y1-(b//a)*x1
        y=x1
        return (g,x,y)

def chiffrer(message,publique): # converit message en liste_chiffree
    # le paramètre "publique" est un tuple à 2 éléments contenant la clé publique (n,e) :
    n=publique[0]
    e=publique[1]
    liste_chiffree=[]
    for c in message:
        liste_chiffree.append(ord(c)**e%n) # chiffre avec la clé publique (n,e)
    return liste_chiffree

def dechiffrer(liste_chiffree,privee): # liste_chiffree vers message
    # le paramètre "privee" est un tuple à 2 éléments contenant la clé privée (n,d) :
    n=privee[0]
    d=privee[1]
    message=''
    for i in liste_chiffree:
        message+=chr(i**d%n) # déchiffre avec la clé privée (n,d)
    return message

# ---------------------------------------------------------------------
#   Programme principal :
# ---------------------------------------------------------------------

# Remplit une liste de nombre premiers dans un intervalle donné :
liste=[]
for i in range(100,1000):
    if premier(i):
        liste.append(i)

# Choisit au hasard une valeur pour p et q en mélangeant la liste :
shuffle(liste)
p=liste[0]
q=liste[1]

# Calcul automatique de n et phi :
n=p*q
phi=(p-1)*(q-1)

# Calcul automatique de e et d (avec e premier et d positif) :
for e in liste:
    d=euclide_etendu(e,phi)[1]
    if phi%e!=0 and e!=p and e!=q and d>0:
        break

# Affichage les entiers choisis :
print("Valeurs choisies par le programme :")
print("p = %d" % p)
print("q = %d" % q)
print("n = %d" % n)
print("phi = %d" % phi)
print("e = %d" % e)
print("d = %d\n" % d)

# Enregistre les clés dans 2 tuples :
cle_publique=(n,e)
cle_privee=(n,d)

# Affichage des clés pour le chiffrement RSA :
print("Clé publique :",cle_publique)
print("Clé privée :",cle_privee)

# Affichage du mesage en clair, chiffré, puis déchiffré :
message='Gecif.net est génial !'
print('\nMessage en clair avant chiffrement : %s' % message)
liste_ch=chiffrer(message,cle_publique)
print('Message chiffré : %s' % liste_ch)
message_dech=dechiffrer(liste_ch,cle_privee)
print('Message déchiffré : %s' % message_dech)