Criptosistema de Rabin

Este criptosistema es asimetrico cuya seguridad esta basada en la complejidad
del problema de la factorizacion y el problema de la raız cuadrada modulo
un numero compuesto n, tiene cierta similaridad con el RSA. El algoritmo de
este sistema criptografico fue publicado en enero de 1979 por el investigador
de origen israeli Michael Oser Rabin, quien junto con Dana Scott ganaron el
premio A. Turing por su trabajo sobre automatas no deterministas, el cual es
un concepto clave para la teorıa de complejidad computacional, en particular
para describir las clases de complejidad P y NP.

Codigo en C++

El siguiente algoritmo necesita las siguientes funciones :

Exponenciacion_Zn() (Exponenciacion en Zn,puedes ver el código aqui)

bool es_primo(int n)
{
  for(int i=2;i<n;i++)
    if(n%i==0)
     return false;
   
   return true;
}

bool es_valido(string mensaje)
{
  bool valido=true;
  //validamos que el mensaje sea binario
  for(int i=0;i<mensaje.size();i++)   
    if((mensaje.at(i)!='0')&&(mensaje.at(i)!='1'))
     valido=false;
   //verificamos que el tamaño del mensaje no sea mayor que 16  
  if(valido)
  {
    if(mensaje.size()<=16)
    return true;
    else
    return false;
  }   
  else
  return false;
}

string completar_16(string mensaje)
{
  int size=mensaje.size();
  int faltan;
 //mensaje a completar
 if(size<16)
 {
   faltan=16-size;
   if(size>=faltan) // extraemos
     mensaje+=mensaje.substr(size-faltan,faltan);   
   else  // repetimos
    {
     for(int i=0;i<(faltan/size);i++)
       mensaje+=mensaje.substr(0,size);
     if((faltan%size)!=0)
       mensaje+=mensaje.substr(0,faltan%size);
    }
 }
 return mensaje;
}

double bin_to_dec(string mensaje)
{
  double dec=0,bit,exp=0;
  
   for(int i=mensaje.size()-1;i>=0;i--)
    {
      if(mensaje.at(i)=='1')
      bit=1;
      else
      bit=0;
      
      dec+=bit*pow(2,exp);
      exp++;
    }
    return dec;
}

void encriptar()
{
     int p,q,n;
    string mensaje;
    char mensaje_aux[300];
       cout<<"\n\n ENCRIPTAR :\n\n";
    // Debemos seguir una serie de pasos para generar las claves publica y privada :
    
    /* 1) Generamos aleatoriamente dos enteros p y q (p y q pueden ser cualquier numero
         pero deben de ser del mismo tamaño , en este caso yo quiero que sean de 3 cifras) ,
          ademas deben de ser primos */
         do
         {p=rand()%900+100;
         }while(!es_primo(p));
         p=277;
         
         do
         {q=rand()%900+100;
         }while(!es_primo(q));
         q=331;
         
         cout<<" p : "<<p<<"\n q : "<<q;
         
    /*  2) Calculamos el valor de n */
         n=p*q;
         cout<<"\n n : "<<n;         
         
     /*  3) La clave publica es 'n' y la clave privada es (p,q) */
         cout<<"\n\n clave publica : "<<n;
         cout<<"\n clave privada : "<<p<<" , "<<q<<")"<<endl<<endl;         
         ////////////////////////////////////////////////
     
     // ingresamos el mensaje en binario
     /*validamos que la longitud del mensaje no sea mayor que 16 y que el mensaje sea binario*/
     do
     {    
     cout<<" Mensaje a encriptar : ";
     fflush(stdin);
     gets(mensaje_aux);
     mensaje=mensaje_aux;          
     }while(!es_valido(mensaje));    
     
     /* completamos el mensaje a 16 bits*/
     mensaje=completar_16(mensaje);
     cout<<" mensaje completado :"<<mensaje<<endl;
     
     /*convertimos el mensaje binario a decimal*/
     double dec=bin_to_dec(mensaje);
     cout<<" mensaje en decimal : "<<dec<<endl;
     
     /*hallamos el mensaje cifrado*/
     int cifrado=Exponenciacion_Zn(dec,2,n);
     cout<<" mensaje cifrado : "<<cifrado<<endl;
}

void desencriptar()
{


}


int main(int argc, char *argv[])
{
    int op;
    cout<<"\n\n         CRIPTOSISTEMA DE RABIN\n\n";      
          
    cout<<"    [1] -> ENCRIPTAR\n\n";
    cout<<"    [2] -> DESENCRIPTAR\n\n";
    cout<<" Seleccione una opcion:";
    cin>>op;
    if(op==1)
      encriptar();
    if(op==2)
      desencriptar();
    cout<<endl;    
    
    system("PAUSE");
    return EXIT_SUCCESS;
}