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)Esistono quattro messaggi distinti m1, m2, m3, m4 che producono lo stesso valore di c, ovvero:
(2)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 m1, m2, m3, m4 candidati nel modo seguente:
(3)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)I quattro valori sono: m1 = x, m2 = -x, m3 = y, m4 = -y
Implementazione
Nell'implementazione, per semplificare i calcoli, viene consigliato di scegliere in numeri primi p e q in modo tale che
(7)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 |