Criptosistema RSA

El criptosistema de clave publica RSA es un algoritmo asimétrico basado en bloques, que utiliza una clave publica y otra privada. La seguridad de este algoritmo radica en que no se puede factorizar, rapidamente, un numero grande en factores primos, es decir el algoritmo esta basado el problema matematico llamado problema de la factorizacion entera, el cual es de alta complejidad computacional. La formulación del RSA es similar al criptosistema propuesto por Cocks-Ellis.


ALGORITMO

a)Generacion de Claves

(1) Alicia genera, aleatoriamente y del mismo tamaño, dos números primos
grandes y diferentes p y q, respectivamente.

(2) n = pq.

(3) Á = (p − 1)(q − 1).

(4) Seleccionar, aleatoriamente, un n´umero entero e tal que mcd(e, Á) = 1,
con 1 < e < Á.

(5) Usar el algoritmo de Euclides extendido para hallar el número entero d
tal que ed=1(mod Á), donde 1 < d < Á.

(6) La clave pública de Alicia es (n,e) y la clave privada es d.

b)Encriptación

(1) Bob recibe la clave pública de Alicia (n, e).

(2) Representa el mensaje en texto plano m, como un número entero en el
intervalo [0, n − 1].

(3) Computar c = m^e(mod n).

(4) Remitir el texto cifrado c a Alicia.

c)Desencriptación

(1) Para recuperar m, Alicia usa la transformación m = c^d(mod n).

(Este algoritmo se encuentra en el libro : Aplicación a la Criptografía, de Jose R.Melquiades y Teresa Bracamonte)



EJEMPLO

a)Para encriptar



b)Para desencriptar



CODIGO EN C++

El siguiente código es la implementación que hice del algoritmo mostrado .
Se necesita las siguientes funciones :

alg_euc() (Algoritmo de Euclides, puedes ver el código aqui )
Inverso_Zn() (Inverso en Zn, puedes ver el código aqui)
Exponenciacion_Zn() (Exponenciacion en Zn,puedes ver el código aqui)

/*Autor : Carlos Perez Sarmiento
  Universidad Nacional de Trujillo*/
#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;
using std::string;

string alfabeto("abcdefghijklmnopqrstuvwxyz");

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

int get_pos(string str,char elemento)
{
  for(int i=0;i<str.size();i++)
    if(str.at(i)==elemento)
      return i;
   return -1;   
}

string  validar_mensaje(string texto_plano)
{
  string texto_plano_valido="";
  
// eliminamos los espacios del texto plano
  for(int i=0;i<texto_plano.size();i++)
     if(texto_plano.at(i)!=' ')
       texto_plano_valido+=texto_plano.at(i);
          
 // completamos con x al final para que sea potencia de 2
   int tam=texto_plano_valido.size();
   if(tam%2!=0)
    texto_plano_valido+="x";
   

  return texto_plano_valido;      
}


void encriptar()
{
     long int p,q,n,fi,e,d;
     string mensaje,mensaje_valido;
     char mensaje_aux[300];
       cout<<" 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 2 cifras) ,
          ademas deben de ser primos */
         do
         {p=rand()%50+50;
         }while(!es_primo(p));
         
         do
         {q=rand()%50+50;
         }while(!es_primo(q));
         p=2357;
         q=2551;
         cout<<" p : "<<p<<"\n q : "<<q;
         
    /* 2) Calculamos el valor de n */
         n=p*q;
         cout<<"\n n : "<<n;
    
    
    /* 3) Calculamos el valor de fi */
         fi=(p-1)*(q-1);
         cout<<"\n fi : "<<fi;     
    
    /* 4) Seleccionamos aleatoriamente un entero 'e' tal que mcd(e,fi)=1 y 1 < e < fi */
       do{
       e=rand()%(fi-2)+2;
       }while(alg_euc(e,fi)!=1);
       cout<<"\n e : "<<e;
       
    /* 5) Usar el algoritmo de euclides extendido para hallar un entero 'd' tal que 
           ed = 1 (mod fi) donde 1 < d < fi (en otras palabras, hallar el inverso de 'e') */  
         d=Inverso_Zn(e,fi);    
         cout<<"\n d : "<<d;  
    
     /*  6) La clave publica es (n,e) y la clave privada es d */
         cout<<"\n\n clave publica : ("<<n<<" , "<<e<<")";
         cout<<"\n clave privada : "<<d<<endl<<endl;
     
    /////////////////////////////////////////////////// 

     cout<<" Mensaje a encriptar : ";
     fflush(stdin);
     gets(mensaje_aux);
     mensaje=mensaje_aux;
       cout<<" mensaje : "<<mensaje<<endl;    
     mensaje_valido=validar_mensaje(mensaje);
       cout<<" mensaje valido : "<<mensaje_valido<<endl;
     
     // representamos numericamente el mensaje     
       cout<<" mensaje en numeros : ";
     long int mensaje_int[mensaje_valido.size()]; /*posiciones de los caracteres en el alfabeto del mensaje*/
     long int mensaje_cifrado[mensaje_valido.size()/2]; 
     
     for(int i=0;i<mensaje_valido.size();i++)
       mensaje_int[i]=get_pos(alfabeto,mensaje_valido.at(i));
     for(int i=0;i<mensaje_valido.size();i++)
       cout<<mensaje_int[i]<<" ";
     cout<<endl;
     cout<<" mensaje en numeros 2: ";
     
     // agrupamos de 2 en 2 el mensaje numerico
      for(int i=0;i<(mensaje_valido.size()/2);i++)
        mensaje_cifrado[i]=mensaje_int[i*2]*100+mensaje_int[i*2+1];
     for(int i=0;i<(mensaje_valido.size()/2);i++)
        cout<<mensaje_cifrado[i]<<" ";
      cout<<endl;
      
      cout<<" mensaje cifrado : ";
      // elevamos al cuadrado el mensaje_cifrado
      for(int i=0;i<(mensaje_valido.size()/2);i++)
        mensaje_cifrado[i]=Exponenciacion_Zn(mensaje_cifrado[i],e,n);
      for(int i=0;i<(mensaje_valido.size()/2);i++)
        cout<<mensaje_cifrado[i]<<" ";
      cout<<endl;      
}

void desencriptar()
{
     cout<<"\n DESENCRIPTAR :\n\n";
     long int d,n,tam;
     cout<<" Ingrese clave privada (d) :";
     cin>>d;     
     cout<<" Ingrese clave n (p*q) :";
     cin>>n;      
     cout<<" longitud del mensaje cifrado:";
     cin>>tam;
     
     long int mensaje_cifrado[tam];
     long int mensaje_int[tam*2];
     string mensaje="";
     
     cout<<" Mensaje cifrado: \n";
     for(int i=0;i<tam;i++)
     { cout<<"  ["<<i+1<<"] = ";cin>>mensaje_cifrado[i];}
     cout<<endl;
     
     // elevamos el mensaje a la potencia d (mod n)
      cout<<" mensaje cifrado a la potencia 'd':";
      for(int i=0;i<tam;i++)
          mensaje_cifrado[i]=Exponenciacion_Zn(mensaje_cifrado[i],d,n);
      for(int i=0;i<tam;i++)
          cout<<mensaje_cifrado[i]<<" ";
      cout<<endl;        
      
      
     // hallamos el mensaje en numeros
     //cout<<" mensaje en numeros: ";
     for(int i=0;i<tam;i++)
       {mensaje_int[i*2]=mensaje_cifrado[i]/100;
        mensaje_int[i*2+1]=mensaje_cifrado[i]%100;
       } 
     for(int i=0;i<(tam*2);i++)
         cout<<mensaje_int[i]<<" ";
     cout<<endl;
  
  
     // hallamos el mensaje
     cout<<" mensaje : ";
     for(int i=0;i<(tam*2);i++)
       mensaje+=alfabeto.at(mensaje_int[i]%26);
     cout<<mensaje;  
     
}


int main(int argc, char *argv[])
{
     int op;
    cout<<"\n\n         ALGORITMO RSA\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;
}