Come funziona il cifrario di McEliece
Episodio I. Bob genera le due chiavi (pubblica e privata) del cifrario di McEliece
- Bob sceglie un [n,k]q – codice lineare C capace di correggere t errori e per cui si dispone di un algoritmo rapido di decodifica
- Bob sceglie una matrice G a coefficienti in GF(q) con k righe ed n colonne e tale da generare il codice C
- Bob sceglie una matrice di permutazione P a coefficienti in GF(q) con n righe ed n colonne
- Bob sceglie una matrice invertibile S a coefficienti in GF(q) con k righe e k colonne
- Bob calcola G’ = S x G x P. Il risultato è una matrice G’ a coefficienti in GF(q) con k righe ed n colonne
- La chiave pubblica è la coppia (G’,t)
- La chiave privata è la terna (S,G,P)
Episodio II. La chiave pubblica di Bob viene pubblicata su Internet
- Bob salva la chiave pubblica e quella privata su una pennetta USB.
- Bob si reca di persona presso una Certification Authority, ovvero un’azienda che è autorizzata per legge a pubblicare le chiavi pubbliche del cifrario di McEliece su Internet.
- La Certification Authority controlla che Bob abbia generato correttamente le due chiavi (pubblica e privata).
- La Certification Authority controlla che le chiavi generate da Bob siano sicure, ovvero che sia difficilissimo risalire alla chiave privata conoscendo soltanto la chiave pubblica. In altre parole, la Certification Authority si mette nei panni di un eventuale hacker e prova a calcolare S, G e P conoscendo soltanto G’ e t.
- Se le chiavi di Bob superano i test di correttezza e di sicurezza (vedi i due punti precedenti), allora Bob riceve dalla Certification Authority un certificato (chiamato X.509) contenente tutti i dettagli relativi alla sua chiave privata.
- La Certification Authority pubblica il certificato di Bob su Internet.
Episodio III. Alice invia un messaggio cifrato a Bob
- Alice sceglie il messaggio m da inviare a Bob. Il messaggio è un vettore m in GF(q)n
- Alice sceglie in modo casuale un vettore e in GF(q)n con peso al più t
- Alice calcola il messaggio cifrato y = m x G’ + e. Il risultato è un vettore y in GF(q)n
- Alice invia il vettore y a Bob
Episodio IV. Bob decifra il messaggio di Alice
- Bob calcola l’inversa della matrice P. Il risultato è una matrice P-1 a coefficienti in GF(q) con n righe ed n colonne
- Bob calcola y x P-1 = [m x G’ + e] x P-1 = [m x (S x G x P) + e] x P-1 = (m x S x G) + (e x P-1)
- Bob applica l’algoritmo di decodifica del codice C a (m x S x G). Il risultato è il vettore m x S in GF(q)n
- Bob calcola l’inversa della matrice S. Il risultato è una matrice S-1 a coefficienti in GF(q) con k righe ed k colonne
- Bob calcola m x S x S-1. Il risultato è il messaggio m di Alice!