Criptosistema Rabin

El criptosistema de Rabin és una tècnica criptográfica asimètrica la seguritat de la qual, de la mateixa manera que RSA, es basa en la complexitat de la factorización. No obstant, la ventaja del criptosistema de Rabin és que s'ha demostrat que la complexitat del problema en el que es basa és tan dur com la factorización de sancers, cosa que es desconeix si és cert en el cas del RSA simple. L'inconvenient que té és que cada eixida de la funció de Rabin pot ser generat per 4 possibles entrades, i si cada eixida és un text sifrat es requerix un temps extra en el dessifrat per a identificar com de les 4 possibles entrades era el correcte text en clar. l'algoritme es va publicar en giner de 1979 per Michael O. Rabin.

Descripció del Criptosistema RSA Versió de Rabin

Abans d'explicar el criptosistema de Rabin seria convenient aclarir el concepte de raïls en operacions modular. Es diu que la raïl d'un número és aquell que multiplicat per sí mateixa, dona eixe número. Puix be, en Aritmètica modular, açò seguix sent aixina. Pero clar, un número al quadrat en mòdul n pot ser que siga major que eixe n, per lo que en fer mòdul, es reduïx el seu valor. Per lo tant, un mateix número pot tindre vàries raïls. En l'àlgebra habitual, un número té 2 raïls reals (la positiva i la negativa), pero quan n és el producte de 2 cosins, existixen valors que tenen 4 raïls distintes. De fet, lo normal és que tinguen 4 raïls. I tindran 4 raïls tots els número que no tinguen com divisor a un dels dos cosins en els que es va generar n, en el cas de la qual tindran només 2.

Si es realisen càlculs s'observarà que existixen de l'orde de $O(p+q)$ valors en 2 raïls i de l'orde de $O(p\cdot q)$ valors en 4 raïls distintes.

Dit açò, centrem-nos ara en el criptosistema de Rabin: el criptosistema de Rabin és una bona alternativa al criptosistema RSA, encara que de la mateixa manera que RSA, basa la seua seguritat en la dificultat de factorizar. El criptosistema de Rabin funciona de la següent manera:

Cada usuari elegix una parella de primers $p$ i $q$cada u igual a 3 mòdul 4 i forma el producte $n=p\cdot q$. La clau pública serà $n$ i la clau privada $p$ i $q$ Funció de sifrat: $c=E(m)=m^2(\mathrm{mod}n)$ Funció de dessifrat: Donat un text sifrat c, es calculen les 4 raïls quadrades de c mod n. Una d'elles serà el propi m, una atra és n-m i les atres són les seues negatives. Per a trobar m deurà fer-se a partir de les atres 3 raïls. Si, com es va dir abans, els primers p i q són iguals a 3 mòdul 4 existixen fòrmules senzilles per a trobar les raïls, calculant prèviament per mig del TCR els valors per a $a$ i $b$ que satisfan l'equació: $a\cdot p+b\cdot q=1$

            $s=c^{((q+1)/4)}(\mathrm{mod}q)$
            $r=c^{((p+1)/4)}(\mathrm{mod}p)$
            $x=(a\cdot p\cdot s+b\cdot q\cdot r)(\mathrm{mod}n)$
            $y=(a\cdot p\cdot s-b\cdot q\cdot r)(\mathrm{mod}n)$
           

Les 4 raïls seran m1=x, m2=-x, m3=i i m4=-i

Per a distinguir el m que codifica el mensage de les atres raïls (els atres m), serà necessari incloure informació redundante.

Detalls del Criptosistema RSA Versió de Rabin

Per a distinguir el m que codifica el mensage de les atres raïls (els atres m), serà necessari incloure informació redundante.

És interessant el fet de que per al cas en que un primer p siga congruent a 1 mòdul 4 no es coneix cap algoritme polinomial determinista per a trobar les raïls quadrades de residus quadràtics mòdul p.

Per tant, el fet que p = 3 mod 4 i q = 3 mod 4 és vital per al correcte funcionament de l'algoritme de descripció, ya que existixen les fòrmules abans expostes.

Un atacant no sabria com de les quatre raïls és la correcta, pero el receptor tampoc. Açò es resol acordant certes regles de redundància en el mensage per a poder distinguir com de les quatre raïls correspon al mensage original.