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 $p\equiv 3(\mathrm{mod}4)$ e $q\equiv 3(\mathrm{mod}4)$
• Calcolare $n=pq$

A questo punto

• $(p,q)$ è la chiave privata
• $n$ è la chiave pubblica

Funzione di cifratura

La funzione di cifratura è:

$f_A:{\mathbb{Z}}_n\to {\mathbb{Z}}_n,f_A(M)=C\equiv M^2(\mathrm{mod}n)$

Decifrazione

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

1. Si calcolano
   1. $m_p\equiv C^{\frac{p+1}{4}}(\mathrm{mod}p)$
   2. $m_q\equiv C^{\frac{q+1}{4}}(\mathrm{mod}q)$

Allora $\pm m_p(\mathrm{mod}p)$ e $\pm m_q(\mathrm{mod}q)$ sono le radici quadrate di $C$ in ${\mathbb{Z}}_p$ e ${\mathbb{Z}}_q$ rispettivamente.

1. Con l'algoritmo di Euclide si calcolano due interi $a,b$ tali che $ap+bq=1$
2. Con il Teorema cinese del resto si computano
   1. $M_1=ap{m}_q+bq{m}_p$
   2. $M_2=ap{m}_q-bq{m}_p$
   3. $M_3=-ap{m}_q+bq{m}_p$
   4. $M_4=-ap{m}_q-bq{m}_p$
3. Uno tra $M_1$, $M_2$, $M_3$, $M_4$ è $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.

Voci correlate

• Impronta di Rabin
• Test di Miller-Rabin