(Classe 5a) - Sistemi e Reti

In letteratura, molte descrizioni delle relazioni matematiche sulle chiavi RSA presentano i due numeri D ed E in ordine opposto, individuando inoltre (E, N) come chiave pubblica, e (D, N) come chiave privata. A noi piace rimettere le due lettere in ordine alfabetico, come lo sono P e Q, e far notare che l’uso delle due chiavi come pubblica o privata è del tutto convenzionale.

Per essere più didattici nelle definizioni, facciamo notare che il prodotto (P-1)*(Q-1) si chiama Funzione di Eulero di N = Ø(N), e conta i numeri interi coprimi a N e minori di N. Vale infatti che: Ø(N) = Ø(P*Q) = Ø(P)*Ø(Q) = (P-1)*(Q-1), dato che i numeri coprimi a un numero primo X (P e Q lo sono) e inferiori ad esso, sono tutti i numeri che lo precedono, in numero quindi di X-1. Come vedremo anche nel seguito, si ha ad esempio che: Ø(33) = Ø(3)*Ø(11)=2*10=20.

Il fatto che D (ed E) siano coprimi rispetto a Ø(N) si esprime in modo compatto con: (D, Ø) = 1 o MCD(D, Ø) = 1, in cui si afferma che il Massimo Comun Divisore dei due numeri è 1.

Inoltre, l’algoritmo per ricavare E da D (o viceversa), dato un N = P*Q, è dato dalla soluzione della cosiddetta Equazione diofantea lineare, cioè a coefficienti interi, D*E – Ø(N)*y = 1, ossia D*E ≡ 1 mod N, che si enuncia come: “D*E è congruo a 1 mod N”. Questa Equazione è particolare per il valore finale = 1 (in genere le Equazioni diofantee lineari si esprimono come: Ax + By = C), e prende perciò anche il nome di Identità di Bézout, che ha soluzioni solo se A e B sono primi tra loro: (A, B) = 1. Come vedremo nell’esempio seguente, la soluzione algebrica E = (Ø(N)*y + 1) / D è immediata per y=1, ma in generale l’Equazione può essere risolta, se una soluzione esiste anche per y diversi, solo con algoritmi non banali reperibili in letteratura.