Crittosistema di Rabin

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

Generazione delle chiavi

Ogni utente deve

• Generare due numeri primi p e q tali che ${\displaystyle p\equiv 3{\pmod {4}}\,}$ e ${\displaystyle q\equiv 3{\pmod {4}}\,}$
• Calcolare ${\displaystyle n=pq}$

A questo punto

• ${\displaystyle (p,q)}$ è la chiave privata
• ${\displaystyle n}$ è la chiave pubblica

Funzione di cifratura

La funzione di cifratura è:

${\displaystyle f_{A}:\mathbb {Z} _{n}\to \mathbb {Z} _{n},f_{A}(M)=C\equiv M^{2}{\pmod {n}}\,}$

Decifrazione

La procedura per decifrare un dato messaggio cifrato ${\displaystyle C}$ richiede la conoscenza della chiave privata ${\displaystyle (p,q)}$ e l'esecuzione dei seguenti passaggi:

1. Si calcolano
   1. ${\displaystyle m_{p}\equiv C^{\frac {p+1}{4}}{\pmod {p}}\,}$
   2. ${\displaystyle m_{q}\equiv C^{\frac {q+1}{4}}{\pmod {q}}\,}$

Allora ${\displaystyle \pm m_{p}{\pmod {p}}\,}$ e ${\displaystyle \pm m_{q}{\pmod {q}}\,}$ sono le radici quadrate di ${\displaystyle C}$ in ${\displaystyle \mathbb {Z} _{p}}$ e ${\displaystyle \mathbb {Z} _{q}}$ rispettivamente.

1. Con l'algoritmo di Euclide si calcolano due interi ${\displaystyle a,b}$ tali che ${\displaystyle ap+bq=1}$
2. Con il Teorema cinese del resto si computano
   1. ${\displaystyle M_{1}=apm_{q}+bqm_{p}}$
   2. ${\displaystyle M_{2}=apm_{q}-bqm_{p}}$
   3. ${\displaystyle M_{3}=-apm_{q}+bqm_{p}}$
   4. ${\displaystyle M_{4}=-apm_{q}-bqm_{p}}$
3. Uno tra ${\displaystyle M_{1}}$, ${\displaystyle M_{2}}$, ${\displaystyle M_{3}}$, ${\displaystyle M_{4}}$ è ${\displaystyle M}$

Dettagli e casi particolari

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

Voci correlate

• Impronta di Rabin
• Test di Miller-Rabin