El criptosistema de Rabin es
una técnica criptográfica asimétrica cuya seguridad, al igual que RSA, se basa en
la complejidad de la factorización. Sin embargo, la ventaja del criptosistema
de Rabin es que se ha demostrado que la complejidad del problema en el que se
basa es tan duro como la factorización de enteros, cosa que se desconoce si es
cierto en el caso del RSA simple. El inconveniente que tiene es que cada salida
de la función de Rabin puede ser generado por 4 posibles entradas, y si cada
salida es un texto cifrado se requiere un tiempo extra en el descifrado para
identificar cual de las 4 posibles entradas era el correcto texto en claro. El
algoritmo se publicó en enero de 1979 por Michael O. Rabin.
El sistema de llave asimétrica
de Rabin se basa en el problema de calcular raíces cuadradas módulo un número
compuesto. Este problema se ha demostrado que es equivalente al de la factorización
de dicho número.
ALGORITMO DE RABIN
GENERACIÓN DE LLAVES
Escogemos dos
números primos, p y q, ambos congruentes con 3 módulo 4.Estos primos son la
clave privada.
La clave pública es su producto, n=p*q.
CIFRAR MENSAJE
- Cabe aclarar que para cifrar el mensaje este debe de estar en forma de cadena de bits con una longitud de 16 bits , en el caso de que falten se cogen las ultimas cifras de la cadena para completar los 16 bits.
- Se realiza una conversión de binario a decimal de la cadena ingresada (m) .
- Para codificar un mensaje , simplemente se calcula:
DESCIFRAR MENSAJE
Para desencriptar el mensaje
solo se deben obtener las 4 raíces de:
C (mod n)
Una de las raíces convertida a binario hará referencia al
mensaje cifrado.
EJEMPLO APLICATIVO:
Generando llaves:
Sea:
- p=277
- q=331
Entonces n= p*q = 91687
- Clave
Publica=(p=277,q=331)
- Clave
Privada=(n=91687)
Cifrando:
Cadena Ingresada: 1001111001 , como no cumple con la cantidad maxima de 16 caracteres se cogen las ultimas 6 cifras para completar, obteniendo nuestra nueva cadena:1001111001111001.
Pasando a decimal nuestra cadena, obteniendo m= 40569.
Ahora procedemos a cifrar: aplicando :
C=405692 mod 91687 = 62111
Descifrando:
Para descifrar el mensaje
lo único que debemos hacer es aplicar la raíz cuadrada de C(mod n) , en este ejemplo
obtendríamos:
m1 = 69654 = >
10001000000010110
m2 = 22033 =
> 101011000010001
m3 = 40569 =
> 1001111001111001
m4 = 51118 =
> 1100011110101110
Podemos observar que la raíz
m3 corresponde al mensaje antes de cifrar.
Implementación
Se hace recordar que en la implementacion hace uso de algoritmos que ya hemos visto con anterioridad , por lo que recomendamos se pase por el siguiente post:
Clase Rabin:
Se hace recordar que en la implementacion hace uso de algoritmos que ya hemos visto con anterioridad , por lo que recomendamos se pase por el siguiente post:
public class Rabin {
private String mensaje;
private long n, q, p;
private String cifrado;
private String CadenaCompleta;
private int m,c;
public int getM() {
return m;
}
public int getC() {
return c;
}
public String getCadenaCompleta() {
return CadenaCompleta;
}
public String getMensaje() {
return mensaje;
}
public long getN() {
return n;
}
public long getQ() {
return q;
}
public long getP() {
return p;
}
public String getCifrado() {
return cifrado;
}
public void setMensaje(String mensaje) {
this.mensaje = mensaje;
}
public boolean primo(int n)
{
for(int i=2;i< n;i++)
{
if(n%i==0)
{
return false;
}
}
return true;
}
public void GenerarPrimos()
{
Boolean resP,resQ;
do
{
p = (int)(Math.random()*(1000-100+1)+100);
q = (int)(Math.random()*(1000-100+1)+100);
resP=primo((int) p);
resQ=primo((int) q);
}while((p< q)||(p==q)||(resP==false)||(resQ==false)||((p-3)%4!=0)||((q-3)%4!=0));
System.out.println("P:"+p);
System.out.println("Q:"+q);
}
public void GenerarKey()
{
GenerarPrimos();
n=p*q;
System.out.println("n: "+n);
}
public String CompletarCadena()
{
String nuevo_mensaje,aux;
int tam=mensaje.length();
int diferencia=tam-(16-tam);
System.out.println("diferencia: "+diferencia);
if(tam< 16)
{
aux=mensaje.substring(diferencia,tam);
nuevo_mensaje=mensaje+aux;
}
else
{
nuevo_mensaje=mensaje;
}
return nuevo_mensaje;
}
public String Encriptar()
{
//Completando Cadena en el caso de que no cumplan los 16 bits
CadenaCompleta=CompletarCadena();
//Pasando la cadena a decimal para poder encriptar
Binario objBinario= new Binario();
m=objBinario.BinarioDecimal(CadenaCompleta);
//Encriptando
Exponenciacion expo= new Exponenciacion();
c=expo.CalcularExp(m, 2, (int) n);
//Pasando a Binario el mensaje cifrado
cifrado=objBinario.decimalABinario(c);
return cifrado;
}
public String[] Desencriptar(int m,int c)
{
RaizCompuesta obj = new RaizCompuesta();
int raices[]=new int[4];
Binario objBinario= new Binario();
String Descifrado[]= new String[4];
raices=obj.CalcularRaizCompuesta(m,c);
if(raices==null)
{
JOptionPane.showMessageDialog(null, "NO EXISTEN RAICES");
}
else
{
Descifrado[0]=objBinario.decimalABinario(raices[0]);
Descifrado[1]=objBinario.decimalABinario(raices[1]);
Descifrado[2]=objBinario.decimalABinario(raices[2]);
Descifrado[3]=objBinario.decimalABinario(raices[3]);
}
return Descifrado;
}
}
Clase Binario:
public class Binario {
int decimal;
public int BinarioDecimal(String numero)
{
decimal= Integer.parseInt(numero,2);
return decimal;
}
public String decimalABinario(int numeroDecimal){
int temp = numeroDecimal;
String resultado="";
while (temp != 0){
if(temp % 2 == 0)
{
resultado="0"+resultado;
}
else
{
resultado="1"+resultado;
}
temp = temp/2;
}
return resultado;
}
}
Resultados:
