title: Crittosistema di Rabin
text: # 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:
  
  * Si calcolano
     * $m_{p}\equiv C^{\frac {p+1}{4}}{\pmod {p}}\,$
     * $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.
  
  * Con l'algoritmo di Euclide si calcolano due interi $a,b$ tali che $ap+bq=1$
  * Con il Teorema cinese del resto si computano
     * $M_{1}=apm_{q}+bqm_{p}$
     * $M_{2}=apm_{q}-bqm_{p}$
     * $M_{3}=-apm_{q}+bqm_{p}$
     * $M_{4}=-apm_{q}-bqm_{p}$
  * 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.
  
  