Crittosistema di Rabin

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

Generazione delle chiavi[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

La funzione di cifratura è:

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

Decifrazione[modifica | modifica wikitesto]

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

Sicurezza del sistema di Rabin[modifica | modifica wikitesto]