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{\pmod {4}}\,$ e $q\equiv 3{\pmod {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}{\pmod {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}}{\pmod {p}}\,$
   2. $m_{q}\equiv C^{\frac {q+1}{4}}{\pmod {q}}\,$

Allora $\pm m_{p}{\pmod {p}}\,$ e $\pm m_{q}{\pmod {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}=apm_{q}+bqm_{p}$
   2. $M_{2}=apm_{q}-bqm_{p}$
   3. $M_{3}=-apm_{q}+bqm_{p}$
   4. $M_{4}=-apm_{q}-bqm_{p}$
3. Uno tra $M_{1}$, $M_{2}$, $M_{3}$, $M_{4}$ è $M$

Il calcolo delle radici quadrate

Dimostriamo la validità delle formule usate al passo 1 della decifrazione. Per la prima formula, vogliamo mostrare che $m_{p}^{2}\equiv C{\pmod {p}}$. Poiché $p\equiv 3{\pmod {4}},$ l'esponente ${\textstyle {\frac {1}{4}}(p+1)}$ è intero. Assumendo che $p$ non divida $C$ (altrimenti la formula è ovvia), notiamo che $C\equiv m_{p}^{2}{\pmod {pq}}$ implica $C\equiv m_{p}^{2}{\pmod {p}}$, quindi $C$ è un residuo quadratico modulo $p$. Ma allora $m_{p}^{2}\equiv C^{{\frac {1}{2}}(p+1)}\equiv C\cdot C^{{\frac {1}{2}}(p-1)}\equiv C\cdot 1{\pmod {p}}$, dove l'ultimo passaggio viene dal Criterio di Eulero.

Dettagli e casi particolari

Per distinguere la m che codifica il messaggio delle altre radici (le altre m), sarà necessario includere informazioni aggiuntive. 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.

È 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.

Sicurezza del sistema di Rabin

È stato dimostrato che qualunque algoritmo in grado di trovare uno dei possibili testi in chiaro per ogni crittogramma cifrato con Rabin può essere utilizzato per fattorizzare il modulo $n$. Pertanto, la decifrazione di un testo in chiaro casuale è difficile tanto quanto il problema della fattorizzazione degli interi. Si ritiene generalmente che non esista un algoritmo in tempo polinomiale per la fattorizzazione, il che implica che non esista un algoritmo efficiente per decifrare un valore cifrato con Rabin casuale senza la chiave privata $(p,q)$.

Il crittosistema di Rabin può subire un attacco con testo in chiaro scelto, poiché il processo di cifratura è deterministico. Un avversario, dato un crittogramma e un messaggio candidato, può facilmente determinare se il crittogramma codifica o meno quel messaggio, semplicemente verificando se la cifratura del messaggio candidato produce il crittogramma dato. Inoltre, non è sicuro contro un attacco con testo cifrato scelto (anche quando i messaggi di sfida vengono scelti in modo uniforme e casuale dallo spazio dei messaggi).

Voci correlate

• Impronta di Rabin
• Test di Miller-Rabin