Estudiando el algoritmo RSA

Todos tenemos una idea de cómo funciona el cifrado asimétrico RSA, que se basa en unos números primos muy largos para generar una clave pública, con la que cualquiera puede cifrar un documento dirigido a ti, y una clave privada, con la que sólo tú puedes descifrarlo. Pero a mí siempre se me ha resistido la comprensión última, las tuercas y tornillos del algoritmo, sobre todo porque mi conocimiento de la Teoría de los Números deja mucho que desear. Por eso he decidido hacer un auto-cursillo sobre este tema, con la esperanza de haber captado, si no los fundamentos profundos, al menos la mecánica detallada del procedimiento. También espero que ese estudio le sirva a alguien que vaya igual de despistado en este asunto. A los que estáis más puestos en esta materia os ruego benevolencia, incluso alguna colaboración o, si os aburre, que miréis para otro lado.

Me ha servido bastante la explicación que he encontrado en Clay Mathematics Institute, pero cualquiera de las que hay por ahí serviría igualmente, si se mira con atención.

Para facilitar la comprensión he confeccionado una versión de juguete, que usa números primos pequeños, con lo que no se consigue fortaleza alguna, pero quizá se vea más claro el intríngulis.

Para empezar, se codifican los caracteres del mensaje en claro mediante una tabla como ésta:

* 0  1  2  3  4  5  6  7  8  9

0 XX XX XX XX XX XX XX XX XX XX
1 SP A  B  C  D  E  F  G  H  I

3 T  U  V  W  X  Y  Z  a  b  c
2 J  K  L  M  N  O  P  Q  R  S
4 d  e  f  g  h  i  j  k  l  m

7 !  @  #  $  %  ^  &  *  -  +
5 n  o  p  q  r  s  t  u  v  w
6 x  y  z  .  ,  :  ;  '  "  `
8 (  )  [  ]  {  }  ?  /  <  >

9 0  1  2  3  4  5  6  7  8  9

en la que cada carácter se representa por el par de números de su fila y su columna. Por ejemplo, la palabra KRIPTOPOLIS se codificaría por el número

K R I P T O P O L I S = 21 28 19 26 30 25 26 25 22 19 29

KRIPTOPOLIS = 2128192630252625221929

Supongo que también podría usarse una tabla en la que tengan cabida los acentos y la Ñ, aprovechando los caracteres no utilizados, pero esto ahora no nos preocupa.

El siguiente paso es generar dos números primos p y q, tan grandes como sea posible, aunque en nuestra versión de juguete nos limitaremos a dos primos diminutos:

p = 439
q = 449

N = p*q = 197111

Después se fabrica número m a partir de los primos:

m = (p – 1) * (q – 1) = 196224

cuya utilidad se verá luego.

Este número se descompone en sus factores primos

m = 196224 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 3 * 7 * 73

Ahora necesitamos un número e que no tenga ningún factor común con m, es decir, que sea primo con respecto a él. En esto hay que tener cierto arte, porque luego tendremos que calcular otro número que va a depender de éste. Pongamos que construimos un número de esta forma:

e = 5 * 11 * 19 = 1045

Llegamos a la parte final de esta tarea, y es obtener otro núnero d que, junto con e, cumpla esta curiosa propiedad:

e * d - 1  = múltiplo de m
es decir:

e * d =  m * y + 1
e * d – 1  = m  *  y

d = (m * y  + 1)/e

Para calcular d hay que ir dando valores enteros a y desde 1 en adelante, hasta que el resultado sea entero, de aquí la importancia de elegir “bien” el número e anterior. Para esta operación puede servirnos una hoja de cálculo, como la que se ve en la figura. En nuestro caso, el primer valor entero de d aparece para y = 31

y = 31

d = 5821

Ya tenemos la tarea hecha, salvo el cifrado, claro. Ahora podemos presentar N y e como clave pública, con la que cualquiera podrá mandarnos un mensaje cifrado, mediante la operación

c = x^e modulo N

donde x es el mensaje convertido en un número por el procedimiento antes descrito

Por nuestra parte, con la clave privada -guardada a buen recaudo- que es básicamente el número d, sólo tenemos que descifrar mediante la operación

x = c^d modulo N

y ya está.

Para aplicar este algoritmo se necesita una herramienta que maneje enteros de longitud arbitrariamente larga, incluso para nuestra versión de juguete. Mediante Python, que no es demasiado eficiente, los cálculos son:

Imaginemos que nuestro mensaje es una sola letra, la K de KRIPTOPOLIS, cuyo código es el 21, según la tabla. La operación de cifrado será:

Cifrado

c = 21^e modulo N

c = 21^1045 modulo 197111 =  63202

Si tuviéramos un número par de dígitos se podría presentar como 63 20 etc, es decir .J (punto jota, etc)

Para descifrar sólo tenemos que calcular:

Descifrado

x = c^d modulo N

x =63202^5821 modulo 197111 = 21 = K

Ahora viene la pregunta fundamental: ¿Cómo es posible que la operación de descifrado deshaga lo que hace la de cifrado, siendo tan distintas? Y la respuesta es: Debido al Pequeño Teorema de Fermat: Si a no es divisible por p, siendo p primo, entonces a^(p-1) - 1 es divisible por p

=====================================================================

REEDICIÓN

En realidad la explicación se basa en el Teorema de Euler-Fermat , tal como trato de explicarlo en

Entender RSA (y II)

=====================================================================

La fortaleza del sistema, como ya sabéis, radica en que la factorización de un número N grande requiere mucho tiempo de computación, pero algunos opinan que los avances en hardware y, sobre todo los cálculos con GPUs en paralelo, van a traer pronto la muerte de RSA. La gente malpensada cree que alguna Agencia ya lo ha conseguido.

Imágenes: 

Fuente: http://www.kriptopolis.com

	Descargar fuente en Delphi
	Descargar ejecutable
	Descargar última versión de la unit de la Biblioteca,DFFLibV14_11May2015. (Necesario recompilar el programa).

Otro código fuente sobre el algoritmo RSA