Algoritmo di Rabin

Algoritmo di Rabin

Questo algoritmo è stato proposto da Michael Rabin nel 1979 e, come per la crittografia RSA, si basa sul Problema della Fattorizzazione degli Interi.

Generazione delle chiavi

Siano p e q due numeri primi sufficientemente grandi, e sia n = pq il loro prodotto. La chiave pubblica è costituita da n, mentre quella privata è costituita dalla coppia p e q.

Cifratura

Dato un messaggio m < n, il messaggio cifrato C è calcolato nel modo seguente:

(1)

\begin{align} c = m^2\:mod\:n \end{align}

Esistono quattro messaggi distinti m₁, m₂, m₃, m₄ che producono lo stesso valore di c, ovvero:

(2)

\begin{align} c = m_1^2\:mod\:n = m_2^2\:mod\:n = m_3^2\:mod\:n = m_4^2\:mod\:n \end{align}

Quindi, in fase di decifrazione devono essere calcolati i quattro possibili valori del messaggio e deve essere scelto quello corretto

Decifratura

Dato un messaggio cifrato c, si calcolano i quattro messaggi m₁, m₂, m₃, m₄ candidati nel modo seguente:

(3)

\begin{align} r = c^{\frac{(p+1)}{4}} mod p \end{align}

(4)

\begin{align} s = c^{\frac{(q+1)}{4}} mod q \end{align}

Si calcolano due valori a e b tali che $a\:p + b\:q = 1$ tramite l'algoritmo esteso di Euclide. Si procede calcolando i due valori seguenti:

(5)

\begin{align} x = (a\:p\:s + b\:q\:r)\:mod\:n \end{align}

(6)

\begin{align} y = (a\:p\:s - b\:q\:r)\:mod\:n \end{align}

I quattro valori sono: m₁ = x, m₂ = -x, m₃ = y, m₄ = -y

Implementazione

Nell'implementazione, per semplificare i calcoli, viene consigliato di scegliere in numeri primi p e q in modo tale che

(7)

\begin{align} p\:mod\:4 = q\:mod\:4 = 3 \end{align}

in modo tale che per calcolare i valori r (3) e s (4), si elevi il valore di c ad un numero intero.

Per poter scegliere qual'è il messaggio corretto, si suggerisce di inserire qualche forma di ridondanza nei dati. Ad esempio, in [1] si consiglia di replicare gli ultimi 64 bit di dati. In questo modo è possibile capire in modo semplice quale messaggio corrisponde all'originale.

Sicurezza

La sicurezza dell'Algoritmo di Rabin risiede nel problema della fattorizzazione dei numeri interi. Si è dimostrato che la robustezza dell'algoritmo è equivalente alla fattorizzazione. Per l'algoritmo RSA invece si suppone che sia equivalente alla fattorizzazione, ma tale equivalenza non è stata dimostrata.

Algoritmi

	Fattorizzazione Interi	Logaritmo Discreto	Curve Ellittiche
Cifratura	RSA, Rabin	ElGamal, DHIES

Bibliography

1. Menezes, van Oorschot, Vanstone, "Handbook of Applied Cryptography", CRC Press, ISBN: 0-8493-8523-7, Sito web: http://www.cacr.math.uwaterloo.ca/hac/