Encriptacion RSA

Encriptacion: (Cifrado, codificación). La encriptación es el proceso para volver ilegible información considera importante. La información una vez encriptada sólo puede leerse aplicándole una clave.

Se trata de una medida de seguridad que es usada para almacenar o transferir información delicada que no debería ser accesible a terceros. Pueden ser contraseñas, numeros de tarjetas de crédito, conversaciones privadas, etc.

Acabo de leer hace poco sobre un método para encriptar información que es muy interesante, se creo en 1978 y se llama RSA, siglas de sus creadores: Rivest, Shamir y Adleman; se basa en la dificultad de factorizar números grandes en números primos, por ejemplo, resulta fácil multiplicar 2 números primos para obtener un tercero pero es difícil a partir del tercero obtener sus 2 factores primos. De hecho este es el mejor método de encriptacion que existe y lo usan bancos, instituciones gubernamentales, etc. Un banco de Monterrey, N.L. que usa este sistema proporcinado por RSA, The Security Division of EMC es Banorte:

Token Banorte

La mayoría de los números primos que se utilizan en la encriptacion RSA son de 250 dígitos o mas, esto es para obtener mayor seguridad pues es mas tardado factorizar un numero primo entre mas grande sea. Teóricamente cifras primas de 250 dígitos requieren millones de años para factorizar.

Como funciona exactamente

Resulta que:

$c \equiv m^{e} \ mod \ n$
$m \equiv c^{d} \ mod \ n$

Si y solo si
$n=pq$, p y q son números primos
$1 < e < \phi (n)$ y $gcd(e, \phi (n))=1$, con $\phi (n)=(p-1)(q-1)$
Y d cumple con $de \equiv 1 \ mod  \ n$
m seria un mensaje numerico y c su contra parte cifrada.
e seria la clave publica para encriptar y d la llave privada para desencriptar.
Nota: phi(n) es la función de Euler.

Procedimiento

1. Se buscan dos numeros p y q que sean primos.
2. Se obtienen n multiplicando p y q, y phi(n) multiplicando (p-1) y (q-1).
3. Se busca un numero e que no tenga divisores comunes con phi(n), y que divida a phi(n)+1 sin dejar residuo.
4. Se encuentra d con la division phi(n)+1 entre e.
5. Ahora ya tenemos todo y la llave publica sera (e, n) mientras que la privada es (d), como el resto de los numeros (p, q, phi(n)) no los vamos a necesitar, pueden destruirse para mayor seguridad.

Ejemplo

Supongamos que elegimos:

$p=11, \ q=23$, dos números primos pequeños ideales para nuestro ejemplo.
Entonces calculamos n: $n=pq=253,$
Calculamos phi(n): $\phi (n)=(p-1)(q-1)=(11-1)(23-1)=220$
Y e: $$1 < e < \phi (n)=220 \ y \ gcd(e, 220)=1$$.
Un numero que lo cumple es 13: $$1 < 13 < \phi (n)=220 \ y \ gcd(13, 220)=1$$
Ahora d es la division de phi(n)+1 entre e: $\frac{221}{13} =17$. Observamos que se cumple: $(17)(13) \equiv 1 \ mod  \ 253$, o que es lo mismo, phi(n)+1 puede ser dividido por e con residuo 0.

Comprobación:


Con el mensaje: 11
$c=11^{13} \ mod \ 253=132$
$m=132^{17} \ mod \ 253=11$


Otro ejemplo

Otro ejemplo con mayor claridad seria el siguiente:

$p=3, \ q=11$
$n=33$
$\phi n=(3-1)(11-1)=20$
$e=7$ porque cumple con 1 < 7 < 20 y gcd(7, 20)=1
$d=\frac{\phi (n)+1}{e}=\frac{21}{7} =3$

Comprobación:

Con el mensaje m=2

$c=m^{e} \ mod \ n=2^{7} \ mod \ 33=128 \ mod \ 33=29$
$m=c^{d} \ mod \ n=29^{3} \ mod \ 33=24389 \ mod \ 33=2$

Podemos observar que si introducimos el mensaje m=2 se encripta en c=29 y se puede desencriptar con la llave privada d. Ahora con nuestras llaves es posible encriptar y desencriptar cualquier mensaje numérico por mas largo que sea.

Nota que si vas a realizar operaciones de exponenciacion muy grandes, deberás de utilizar el algoritmo de potenciacion binaria para ahorrar operaciones.

Algunas formas para convertir un texto a numero es aplicando una llave numérica por partes o simplemente convirtiéndolo a valores ASCII (aunque esto no es tan seguro).

Mas información


http://www.rsa.com/
http://www.tagoror.com/enciclopedia/es/wikipedia/f/fu/funcion_phi_de_euler.html
http://boards5.melodysoft.com/canalingenio/la-funcion-phi-de-euler-225.html
http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/rsa.html

Ahora les mostrare el pseudocodigo que estoy haciendo, no esta terminado pero me da la idea de lo que voy a hacer para implementarlo.

/*Pseudocodigo para cifrar, metodo RSA*/

#include < stdio.h >
#include < time.h >
#define p long 47
#define q long 13
long p, q, n, h, e, d, m;
char M[4000];
long a[3], b[3], m[3], res;

n();
h();
e();
d();
string();
ps();
encrypt();
decrypt();
show-string();

main()
{
  n();
  h();
  e();
  d();
  put-string();
  ps(M)
  encrypt(m);
  decrypt(c);
  ps(m);
  show-string(M);
  getch();
}

n()
{
  //Elegir 2 primos (p y q)
  n=p*q;
}

h()
{
  //Funcion phi Euler
  h=(p-1)*(q-1);
}

e()
{
  //e  long fac[3];
  e=(5*h)/8;
  fac[0]=e;
  fac[1]=h;
  gcd();
  while (fac[1]!=1&&)
    {
      e++;
      gcd();
    }
}

d()
{
  //Algoritmo euclideano extendido para calcular
  //el modulo multiplicativo inverso de: e (mod h)
  a[1]=1;
  b[1]=0;
  m[1]=e;
  a[2]=0;
  b[2]=1;
  m[2]=h;
  res=e-(h*m[2]);
  while (m[2]!=1)
    {
      //Correr los valores
      a[0]=a[1];
      a[1]=a[2];
      b[0]=b[1];
      b[1]=b[2];
      m[0]=m[1];
      m[1]=m[2];
      //Calcular ultimos valores
      a[2]=a[0]-(a[1]*res);
      b[2]=b[0]-(b[1]*res);
      m[2]=m[0]-(m[1]*res);
    }
  d=a[2];
}

string()
{
  printf("Introduce el mensaje que quieras encriptar:\n");
  scanf("%s", M);
}

ps(char x)
{
  //Convertir cadena a numeros o viceversa
  if (isalfa(x))
    {
      m=tonumber(x);
      return m;
    }
  else
    {
      M=toalfa(x);
      return M;
    }
}

long encrypt(long)
{
  c=pow(m, e) mod n;
  return c;
}

long decrypt(long)
{
  m=pow(c, d) mod n;
  return m;
}

show-string()
{
  printf("%s", M);
}

gcd()
{
  //Algoritmo euclidiano
  fac[0]=e;
  fac[1]=h;
  fac[2]=fac[0]%fac[1];
  while (fac[2]!=0)
    {
      fac[0]=fac[1];
      fac[1]=fac[2];
      fac[2]=fac[0]%fac[1];
    }
}





Seguiré mejorando el pseudocodigo y mejorare la información aquí presente. Pueden darse una vuelta de vez en cuando para ver el avance. También agregare mas enlaces con información por si tienen dudas de como conseguir todos los números para las claves, se supone  que se utilizan ciertos métodos de factorizacion como el algoritmo euclideano que aprendimos la clase pasada en el salon pero por falta de tiempo no la mostrare aquí.

Actualización 18 Mayo 2010: He corregido unas cosas importantes y agregue un ejemplo mas.
Actualización 21 Mayo 2010: Utilizar algoritmo de potenciacion binaria para ahorrar operaciones.