# algorithme RSA

from random import *

def nombre_premier(n,k):  # trouver un nombre premier N à n chiffres avec k tests
    s = 0
    while s == 0:
        N = 0
        while (N%10 in [0,2,4,5,6,8]) or sum(int(c) for c in str(N))%3 == 0:
            N = randint(10**(n-1),10**n-1)
        s = 1
        for i in range(k):
            A = randint(2,N-1)
            if pow(A,N-1,N) != 1:
                s = 0
    return(N)

# calcul du nombre N produit de deux grands nombres premiers P et Q, ainsi que de phi(N)

n = 50
k = 30
P = nombre_premier(n,k)
Q = nombre_premier(n,k)
N = P * Q
phi = (P-1)*(Q-1)
print("P =",P)
print("Q =",Q)
print("N =     ",N)
print("phi(N) =",phi,"\n")

# fonctions gcd et extended_gcd

def gcd(a, b):
    if a==0:
        return b
    return gcd(b % a, a)
    
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x, y = extended_gcd(b % a, a)
    return gcd, y - (b // a) * x, x

# nombre C généré par Bob, rendu public
C = randint(2,N-1)
while gcd(C,phi) != 1:
    C = randint(2,N-1)

# calcul du nombre correspondant D par Bob, maintenu secret
G, U, V = extended_gcd(C,phi)
D = U % phi

# message d'Alice
X = randint(1,N-1)
print("Message X:",X)

# calcul du message chiffré envoyé par Alice
Y = pow(X,C,N)
print("Message Y:",Y)

# calcul effectué par Bob pour déchiffrer le message d'Alice
Z = pow(Y,D,N)
print("Message Z:",Z)
print("Correspondance:", Z == X)