# algorithme pour établir une signature digitale

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 Alice, meintenu secret
C = randint(2,N-1)
while gcd(C,phi) != 1:
    C = randint(2,N-1)

# calcul du nombre correspondant D par Alice, rendu public
G, U, V = extended_gcd(C,phi)
D = U % phi

# message envoyé par Alice
X = randint(1,N-1)
print("Message X:",X)

# calcul du hash de X (effectué à nouveau par Alice)
H = pow(X,X,1001)
print("Hash de X:",H)

# calcul de la signature du message X (toujours effectué par Alice)
S = pow(H,C,N)
print("Signature S:",S)

# Alice envoie H et S à Bob

# vérification par Bob que le message X est bien envoyé par Alice
test = pow(S,D,N)
print("Vérification par Bob:",test == H)