Nombre: RSA
Plataforma: HP-49G
Descripción: Implementación sencilla para la HP del algoritmo de encriptación RSA
Fecha: Octubre de 1999
Tamaño: 1226 bytes.
Autor: José Manuel Alarcón Aguín
Ingeniería Mecánica
E.T.S. Ingenieros Industriales
Vigo (España)
mail to me jalarcon@uvigo.es

Nota Inicial:
Se trata de la implantación en la HP-49G del conocido algoritmo de encriptación/ desencriptación RSA. Este algoritmo se ha escrito con fines meramente educativos, como más tarde se explica en este documento.
Este conjunto de programas solamente se pueden utilizar en una HP-49G o superior ya que emplea algunas funciones específicas de esta máquina. En cualquier caso si alguno de ellos detecta que se está intentado usar en una máquina diferente a una HP-49 dejará de funcionar indicando dicho motivo.
Junto con el propio programa y esta explicación del algoritmo se ha incluido el código fuente totalmente comentado para una más fácil comprensión.
Disfrútalo y si tienes algún comentario o sugerencia ya sabes a donde puedes escribirme :-)

Cifrado RSA:
RSA es uno de los algoritmos de clave pública más utilizados y sirve tanto para cifrar como para efectuar firmas digitales. Su nombre proviene de las iniciales de sus tres inventores: Ron Rivest, Adi Shamir y Leonard Adleman que lo definieron en 1978.

Generación de las claves:
Lo primero que se debe hacer para poder utilizar el RSA es generar un par de claves (una pública y otra privada) que servirán para encriptar y desencriptar los mensajes respectivamente. Estas dos claves irán acompañadas de un módulo que será necesario para efectúar operaciones en matemática discreta.
Lo primero que se debe hacer es generar un par de números primos iniciales a partir de los cuales se obtendrá el módulo para la encriptación. Estos dos primos ('p' y 'q', por ejemplo) se deben elegir de forma aleatoria y deben ser lo mayores posibles para que el algoritmo sea difícil de romper. Su producto 'm':

m = p x q

actuará de módulo en el proceso de encriptación y desencriptación.
A partir de estos dos números se obtendrá también la clave pública 'C1' para encriptar los mensajes. Esta clave 'C1' es también aleatoria y lo único que debe cumplir es que ha de ser primo relativo con respecto al producto (p-1) x (q-1).
Una vez obtenida la clave pública 'C1' la obtención de la clave privada 'C2' es directa ya que:

C1 x C2 = 1 mod ((p-1) x (q-1))

o sea, que 'C1' y 'C2' deben ser inversos en el anillo de módulo (p-1) x (q-1).

Por fin, la clave pública está formada por 'C1' y el módulo 'm', y la clave privada por 'C2' y el módulo 'm' que son los únicos valores del proceso de generación de claves que debemos conservar.
En la implementación de RSA que he hecho se pueden obtener las claves usando el programa 'GENKEYS' que es la etiqueta que aparece en segundo lugar en el directorio. Tras un periodo de tiempo más o menos largo (dependiendo del factor elegido y de una parte aleatoria) obtendremos en la pila un par de claves (pública y privada) elegidas al azar así como el módulo necesario para efectuar encriptación con las mismas.
Debemos conservarlas en alguna variable para poder usarlas posteriormente. Al resto de la gente sólo debemos facilitarle la clave privada y el módulo si queremos que nos envíen mensajes o si pretendemos enviarles una firma digital.

La tercera variable del directorio RSA que se crea al instalar el programa se llama 'FAC' y es la encargada de contener el "factor de tamaño de clave". Este factor controla el tamaño de las claves generadas por 'GENKEYS' y cuanto mayor sea más seguridad tendremos. Esto no quiere decir que podamos poner cualquier cosa. He comprobado que los valores de 'FAC' mayores a 10^11 hacen que la generación de claves sea un proceso excesivamente largo. Con este valor límite de 10^11 tendremos unos tiempos bastante razonables, sobre todo teniendo en cuenta que RSA no está pensado para encriptar grandes cantidades de texto sino más bien para frases cortas en formas digitales o en mensajes que guarden otro tipo de claves para utilizar en otros métodos de encriptación.
De todos modos usando 10^11 como valor para 'FAC' se obtiene módulos 'm' como por ejemplo:

5154228018862208512867

Este número la HP-49 tarda muchísimo tiempo en factorizarlo (me aburrí después de media hora de esperar) y cualquier otro generado con este valor de 'FAC' tardará más o menos el mismo tiempo.
Esto no implica en absoluto que el RSA para la HP-49 sea seguro para enviar mensajes muy confidenciales, ya que cualquiera con el suficiente interés y paciencia podría obtener la factorización de 'm' y por lo tanto 'p' y 'q', pudiendo averiguar enseguida el valor de las claves pública y privada y acabar así con la confidencialidad del mensaje. Lo dicho: Este programa está hecho con fines educativos aunque pueda ser usado de una manera práctica para mensajes de poca importancia.

El proceso de encriptación/desencriptación:
Una vez obtenidas las claves, el mensaje se divide en bloques tales que su valor numérico sea siempre inferior al módulo de encriptación 'm'. Esto implicaría, en el caso de la HP, un gran trabajo extra y números excesivamente grandes para manejar, y por lo tanto se ha optado por la más sencilla solución (aunque no correcta desde el punto de vista teórico) de simplemente dividir el mensaje en sus correspondientes códigos ASCII.
Para cifrar se aplica a cada bloque (en esta caso a cada código ASCII) la expresión:

Ei = Mi^C1 mod(m)

siendo 'Mi' el bloque de mensaje a cifrar y 'Ei' el resultado cifrado.
Para descrifrar se emplea la siguiente expresión:

Mi = Ei^C2 mod(m)

debido a una demostración que no voy a escribir aquí y que conlleva el uso del "pequeño teorema de Fermat", y del "teorema del resto chino" para demostrar la consistencia de RSA.
Se pueden intercambiar las claves en los procesos de cifrado y descifrado por ejemplo para la realización de firmas digitales. En los casos de aplicación reales se suele poner como clave pública la de menor longitud de manera que el proceso de cifrado o de comprobación de firmas sea mucho más rápido.
En una apliacción real y perfectamente realizada de RSA, el mensaje cifrado siempre ocupa algo más que el mensaje en claro ya que siempre se obtiene en cada bloque un dígito más que el bloque original. Sin embargo esto tiene una importancia muy baja ya que no suele representar más de un pequeño porcentaje de aumento. Sin embargo en el caso de la implementación que he hecho para la HP-49 este efecto es realmente importante. Dado que la división de los bloques la hago directamente con los caracteres del mensaje cada uno de ellos aumenta considerablemente al ser encriptado, y por lo tanto el mensaje cifrado alcanzará un tamaño varias veces mayor dependiendo del tamaño de las claves y el módulo (o sea del valor de 'FAC').

Ejemplo de aplicación:
Antes de nada debemos asegurarnos de que tenemos la calculadora en modo "Radianes" o sino contestar que sí cuando se nos pregunte si queremos ponerlo.
Para cifrar el texto "Secret stuff!" con la clave pública 4264723 con el módulo 40181463436921 podríamos en la pila lo siguiente:

3: "Secret Stuff!"
2: 4264723
1: 40181463436921

y tras pulsar 'RSA' obtendríamos la lista con los bloques cifrados:

{ 37789553811171 6897667489646 36892321337318 18010549703471 6897667489646 6993235818405 30383408828234 37789553811171 6993235818405 27290194209539 3839510730285 3839510730285 4982777788734 }

Esta es la lista que deberíamos pasar a quien quisiésemos hacer llegar nuestro mensaje cifrado. Esta persona, al recibirlo, lo desencriptaría utilizando su clave privada, que en este caso es 8337386909755, como vemos más larga que la pública. tendría que hacer así:

3: { 37789553811171 6897....}
2: 8337386909755
1: 40181463436921
(el módulo es el mismo que antes)

obteniendo en la pila el mensaje en claro de nuevo.

Si quisiésemos utilizar una firma digital podríamos en un mensaje, por ejemplo, nuestras iniciales y las encriptaríamos con nuestra clave privada. A continuación se lo enviaríamos a nuestro destinatario y éste al recibirlo lo desencriptaría con nuestra clave pública obteniendo nuestras iniciales. Si no hubiésemos enviado nosotros el mensaje, al desencriptar con nuestra clave pública no se obtendrían nuestras iniciales sino cualquier otra cosa ininteligible, de manera que si las obtiene puede estar seguro de que se trata de nosotros.

Licencia:
Este software es FREEWARE siempre y cuando se distribuya con todos los archivos originales, es decir, este texto en castellano y en inglés, los gráficos correspondientes, el binario del programa y el código fuente comentado.

© José Manuel Alarcón Aguín 1999