Crittosistema di Rabin

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

Il crittosistema di Rabin è un sistema di cifratura a chiave pubblica sviluppato nel 1979 da Michael Oser Rabin che, come per il sistema RSA, basa la propria sicurezza sul fatto che il problema della fattorizzazione di interi è computazionalmente difficile.

Cifratura[modifica | modifica wikitesto]

Generazione delle chiavi[modifica | modifica wikitesto]

Ogni utente deve

  • Generare due numeri primi p e q tali che e
  • Calcolare

A questo punto

  • è la chiave privata
  • è la chiave pubblica

Funzione di cifratura[modifica | modifica wikitesto]

La funzione di cifratura è:

Decifrazione[modifica | modifica wikitesto]

La procedura per decifrare un dato messaggio cifrato richiede la conoscenza della chiave privata e l'esecuzione dei seguenti passaggi:

  1. Si calcolano

Allora e sono le radici quadrate di in e rispettivamente.

  1. Con l'algoritmo di Euclide si calcolano due interi tali che
  2. Con il Teorema cinese del resto si computano
  3. Uno tra , , , è

Dettagli e casi particolari[modifica | modifica wikitesto]

Per distinguere la m che codifica il messaggio delle altre radici (le altre m), sarà necessario includere informazioni aggiuntive.

È interessante il fatto che nel caso in cui il numero primo P è congruente a 1 modulo 4, nessun algoritmo polinomiale deterministico è noto per trovare le radici quadrate dei residui quadratici di P.

Pertanto, il fatto che P = 3 mod 4, e q = 3 mod 4 è fondamentale per il corretto funzionamento dell'algoritmo descritto, in quanto è la campo di esistenza delle equazioni precedenti.

Un utente malintenzionato non saprebbe quale delle quattro radici è corretta, ma non il destinantario. Ciò viene risolto concordando alcune regole di ridondanza, note fra mittente e destinatario, da includere nel messaggio per essere in grado di distinguere quale delle quattro radici corrisponde a quella del messaggio originale.

Sicurezza del sistema di Rabin[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]