Apri il menu principale

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.

CifraturaModifica

Generazione delle chiaviModifica

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 cifraturaModifica

La funzione di cifratura è:

 

DecifrazioneModifica

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

  1. Si calcolano
    1.  
    2.  

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
    1.  
    2.  
    3.  
    4.  
  3. Uno tra  ,  ,  ,   è  

Dettagli e casi particolariModifica

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 RabinModifica

Voci correlateModifica