Implementación del algoritmo de encriptación RSA en Java (parte 1)

Retomando un poco la temática principal inicial de este blog: la programación en Java, y más aún tocando temas tan excitantes como la criptografía, la siguiente entrada pretende que aprendas varias cosillas:

• Lo básico acerca del algoritmo de encriptación RSA
• Ejemplos de programación en Java
• Conocer algunas funciones y clases interesantes del API J2SE
• Aprender a crear un front-end en Swing
• Y algunas cosillas más…

Así que la información que pondré a continuación, no solamente enseñará a los estudiantes y aficionados a “implementar el algoritmo RSA en Java”, sino que les ayudará a comprender mucho mejor otros temas muy comunes en la “programación de aprendizaje”.

Al grano… ¿qué es RSA?

No tiene mucho sentido extenderme en este tema, que en realidad no es realmente lo que me preocupa enseñar en esta entrada, pero dado que la temática sobre la cual correrá nuestra aplicación es RSA, es necesario que estén enterados acerca del mismo. Bastante información hay ya en la red, y al final pondré las fuentes de información que recomiendo, de momento podemos comenzar con un extracto de texto tomado de la Wikipedia:

El sistema criptográfico con clave pública RSA es un algoritmo asimétrico cifrador de bloques, que utiliza una clave pública, la cual se distribuye (en forma autenticada preferentemente), y otra privada, la cual es guardada en secreto por su propietario. Una clave es un número de gran tamaño, que una persona puede conceptualizar como un mensaje digital, como un archivo binario o como una cadena de bits o bytes. Cuando se envía un mensaje, el emisor busca la clave pública de cifrado del receptor y una vez que dicho mensaje llega al receptor, éste se ocupa de descifrarlo usando su clave oculta. Los mensajes enviados usando el algoritmo RSA se representan mediante números y el funcionamiento se basa en el producto de dos números primos grandes (mayores que 10100) elegidos al azar para conformar la clave de descifrado.

Profundicemos entonces en el tema de RSA…

¿Cómo se generan las claves RSA?

Supongamos que “Mauricio” desea permitir que “Horacio” le envíe un mensaje cifrado sobre un canal inseguro. Lo primero que ha de hacer es generar los pares de claves pública (n,e) y privada (n,d):

• Elegimos dos números grandes para p y q (entre más grandes es más segura la encriptación, pero es más demorado el proceso de encriptar/desencriptar) que sean diferentes y totalmente independientes el uno del otro. Calculamos n=p*q
• Calculamos la función de Totient de n: totient(n)=(p-1)*(q-1)
• Elegimos un entero e, de tal forma que 1 < e < totient(n) y además que sea coprimo con totient(n)
• Calculamos un d, de tal forma que d*e=1 mod totient(n)
• La clave pública será entonces (n,e) y la privada (n,d)
• En dicho caso “Mauricio” puede compartir su clave pública con “Horacio” y guardar celosamente la privada.

Encriptando datos

Ahora supongamos que el profesor “Horacio” desea mandarle un mensaje a “Mauricio”… lo único que tendrá que hacer es consultar la clave pública de “Mauricio”, dividir el mensaje que quiere enviarle, asignarle un alfabeto numérico a cada trozo y calcular para cada división: c=n^e mod n

Desencriptando

Con el mensaje que le ha llegado a “Mauricio”, lo que tiene que hacer es dividirlo y usar su clave privada para calcular: n=c^d mod n

Implementar el algoritmo RSA en Java

He dividido el programa en dos clases: la primera maneja toda la lógica del algoritmo RSA, mientras que la segunda es simplemente la que muestra los resultados. A continuación colocaré la totalidad del código fuente del programa hecho en Java. Luego explicaré paso a paso lo que considere importante y/o interesante.

Primera clase: RSA.java

/*
 * RSA.java
 *
 * Creado 24 de octubre de 2007, 12:02 PM
 *
 */
import java.math.BigInteger;
import java.util.*;
import java.io.*;

/**
 *
 * @author Algunas personas
 */
public class RSA {

    int tamPrimo;
    BigInteger n, q, p;
    BigInteger totient;
    BigInteger e, d;

    /** Constructor de la clase RSA */
    public RSA(int tamPrimo) {
        this.tamPrimo = tamPrimo;
        generaPrimos();             //Genera p y q
        generaClaves();             //Genera e y d
    }
    
    public void generaPrimos()
    {
        p = new BigInteger(tamPrimo, 10, new Random());
        do q = new BigInteger(tamPrimo, 10, new Random());
            while(q.compareTo(p)==0);
    }
    
    public void generaClaves()
    {
        // n = p * q
        n = p.multiply(q);
        // toltient = (p-1)*(q-1)
        totient = p.subtract(BigInteger.valueOf(1));
        totient = totient.multiply(q.subtract(BigInteger.valueOf(1)));
        // Elegimos un e coprimo de y menor que n
        do e = new BigInteger(2 * tamPrimo, new Random());
            while((e.compareTo(totient) != -1) ||
		 (e.gcd(totient).compareTo(BigInteger.valueOf(1)) != 0));
        // d = e^1 mod totient
        d = e.modInverse(totient);
    }
    
    /**
     * Encripta el texto usando la clave pública
     *
     * @param   mensaje     Ristra que contiene el mensaje a encriptar
     * @return   El mensaje cifrado como un vector de BigIntegers
     */
    public BigInteger[] encripta(String mensaje)
    {
        int i;
        byte[] temp = new byte[1];
        byte[] digitos = mensaje.getBytes();
        BigInteger[] bigdigitos = new BigInteger[digitos.length];
        
        for(i=0; i<bigdigitos.length;i++){
            temp[0] = digitos[i];
            bigdigitos[i] = new BigInteger(temp);
        }
        
        BigInteger[] encriptado = new BigInteger[bigdigitos.length];
        
        for(i=0; i<bigdigitos.length; i++)
            encriptado[i] = bigdigitos[i].modPow(e,n);
        
        return(encriptado);
    }
    
    /**
     * Desencripta el texto cifrado usando la clave privada
     *
     * @param   encriptado       Array de objetos BigInteger que contiene el texto cifrado
     *                           que será desencriptado
     * @return  The decrypted plaintext
     */
    public String desencripta(BigInteger[] encriptado) {
        BigInteger[] desencriptado = new BigInteger[encriptado.length];
        
        for(int i=0; i<desencriptado.length; i++)
            desencriptado[i] = encriptado[i].modPow(d,n);
        
        char[] charArray = new char[desencriptado.length];
        
        for(int i=0; i<charArray.length; i++)
            charArray[i] = (char) (desencriptado[i].intValue());
        
        return(new String(charArray));
    }
    
    public BigInteger damep() {return(p);}
    public BigInteger dameq() {return(q);}
    public BigInteger dametotient() {return(totient);}
    public BigInteger damen() {return(n);}
    public BigInteger damee() {return(e);}
    public BigInteger damed() {return(d);}
}

Segunda clase: Main.java (contiene el método main)

import java.io.*;
import java.math.BigInteger;
/**
 *
 * @author Algunas personas
 */
public class Main {
    
    /**
     * @param argumentos de la línea de comandos
     */
    public static void main(String[] args) throws IOException {
        if(args.length != 1) {
            System.out.println("Sintaxis: java RSA [tamaño de los primos]");
            System.out.println("por ejemplo: java RSA 512");
            args = new String[1];
            args[0]="1024";
        }
        int tamPrimo = Integer.parseInt(args[0]);
        RSA rsa = new RSA(tamPrimo);

        System.out.println("Tam Clave: ["+ tamPrimo + "]n");

        System.out.println("p: [" + rsa.damep().toString(16).toUpperCase() + "]");
        System.out.println("q: [" + rsa.dameq().toString(16).toUpperCase() + "]n");

        System.out.println("Clave publica (n,e)");
        System.out.println("n: [" + rsa.damen().toString(16).toUpperCase() + "]");
        System.out.println("e: [" + rsa.damee().toString(16).toUpperCase() + "]n");

        System.out.println("Clave publica (n,d)");
        System.out.println("n: [" + rsa.damen().toString(16).toUpperCase() + "]");
        System.out.println("d: [" + rsa.damed().toString(16).toUpperCase() + "]n");

        System.out.println("Texto a encriptar: ");
        String textoPlano = ( new BufferedReader(new
                        InputStreamReader(System.in))).readLine();
        
        BigInteger[] textoCifrado = rsa.encripta(textoPlano);
        
        System.out.println("nTexto encriptado: [");
        for(int i=0; i<textoCifrado.length; i++) {
            System.out.print(textoCifrado[i].toString(16).toUpperCase());
            if(i != textoCifrado.length-1)
                System.out.println("");
        }
        System.out.println("]n");
        
        String recuperarTextoPlano = rsa.desencripta(textoCifrado);
        System.out.println("Texto desencritado: ["+ recuperarTextoPlano +"]");
    }
    
}

Cosas interesantes por notar

• Lo primero es ver que usamos una clase del paquete java.math: BigInteger. Esta clase escrita por Josh Bloch y Michael McCloskey, que nos permitirá hacer operaciones con números enteros demasiado grandes, y nos provee funciones análogas a todos los operadores primitivos de enteros.
  • De aquí mismo, es interesante resaltar las funciones: compareTo , subtract, multiply, gcd , modPow, modInverse que sirven para comparar, restar, multiplicar, común divisor, módulo del exponente, y el módulo del exponente inverso, respectivamente.
• Además la función toString(int), que convertirá el valor de un objeto BigInteger, a su valor equivalente a la representación String de este BigInteger en la raíz dada. Y posteriormente, ya siendo un objeto String lo que se maneja, se usa la función toUpperCase para convertir el texto en mayúsculas.
• En el método generaPrimos de la clase RSA.java, generamos los primos p y q.

Probando el programa

Para ejecutar el programa ejecutaremos el comando: java Main tamanioPrimo, por ejemplo:

java Main 1024

Y luego insertaremos el texto a encriptar!

Eso es todo en esta primera parte… en la próxima haremos un front-end en Swing, basándonos en la aplicación actual.

Descargas y enlaces

• Código fuente de la aplicación (simple)
• Código fuente de la aplicación (+proyecto en NetBeans)
• Bases de este artículo

33 Comentarios | deja el tuyo