Codificar y descodificar cadenas con el algoritmo RSA

Notxor

2022-07-28

Esta es la tercera y última entrega sobre el algoritmo RSA para cifrado y descifrado de mensajes. Si te has perdido los anteriores, lo mismo te vendría bien echarles un ojo, porque en el primero explico cómo funciona el algoritmo RSA, con un poco de matemáticas por medio, y en el segundo hablo sobre unos de los cálculos más complejos que hay que realizar en el paso de generación de las claves. Si te has perdido los anteriores porque no te interesaba el tema, no sé que haces leyendo éste. En el presente artículo hablo sobre el resto de la generación de las claves, creando un fichero para la llave pública y otro para la llave privada y un par de funciones de cifrado y descifrado que serán las que hagan la magia. El código completo lo puedes encontrar al final del texto.

Podréis observar que en el código hay varias funciones de exponenciación. Al trabajar con números tan grandes el operador habitual ** no funcionaba por desbordamiento. Sin embargo, parece que los operadores habituales (+ - / *) siguen adelante en TCL con los números grandes. Busqué algunos algoritmos que hicieran esa operación de forma rápida y después de probar varias alternativas, me di cuenta que en realidad no lo necesitaba, porque lo que realmente era necesario ya estaba incluido en el código de las pruebas de primalidad. Lo que necesitaba era el exponente modular. En fin, torpe que soy.

Generar la clave

En el título del apartado hablo en singular, aunque en realidad el proceso generará dos archivos, uno terminado en -pub.key y otro en -priv.key que contendrán las claves que necesitamos, el primero la pública y el segundo la privada.

proc generar-clave {t} {
    puts "Generando clave aleatoria de [expr {16 * $t}] bits"

    # 1. generar dos números primos
    set p [generar-primo $t]
    while { 1 } {
        set q [generar-primo $t]
        if {$p != $q} break
    }
    dict set key "p" $p
    dict set key "q" $q

    # 2. Calcular el módulo
    set n [expr {$p * $q}]
    set t [num-bits $n]
    dict set key "n" $n
    dict set key "t" $t

    # 3. Calcular `phi(n)`
    #
    set phiN [mcm [expr {$p - 1}] [expr {$q - 1}]]
    dict set key "phi(n)" $phiN

    # 4. Calcular el exponente
    #    `e` ¿65537?
    #
    set e [aleatorio [expr {$t / 8}]]
    dict set key "e" $e

    # 5. Calcular el exponente `d`
    #
    set d [modinverso $e  $phiN]
    dict set key "d" $d

    return $key
}

La función que genera la clave sigue paso a paso el algoritmo. Se puede mejorar el proceso, especialmente metiéndole comprobaciones de que los pasos se completan satisfactoriamente dentro de las especificaciones establecidas, como se ha hecho en el primer paso al generar los números primos. El primer número se genera aleatoriamente con el tamaño pedido¹. El segundo se pide en bucle y se comprueba que no sea idéntico al primero. La probabilidad de esto ocurra es muy pequeña, infinitesimal, dado el tamaño de los números. Sin embargo, haciendo pruebas con números pequeños, ya me ha ocurrido que eran idénticos².

Obtenidos dos números primos grandes, completamente aleatorios. El siguiente paso es calcular el módulo. Este paso se podría juntar con el primero y comprobar, además de que los dos números primos son de tamaño ligeramente diferente, y que el módulo, sea igual o superior al tamaño que le estamos pidiendo, es decir 16 * t.

Para el tercer paso, calcular \(\lambda (n) = \phi (n)\) debemos calcular el mínimo común múltiplo de \((p - 1) \cdot (q - 1)\). Y aquí también me he tropezado con un montón de algoritmos, todos muy lentos con números tan grandes, para calcular el mcm. El único que resultó suficientemente rápido fue explotar la relación que existe entre el MCM y el mínimo común divisor (MCD).

proc mcd {a b} {
    while {$a != $b} {
        if {$a > $b} {
            set a [expr {$a - $b}]
        } else {
            set b [expr {$b - $a}]
        }
    }
    return $a
}

proc mcm {a b} {
    return [expr {$a * $b / [mcd $a $b]}]
}

Resultó que el algoritmo de cálculo del MCD es bastante más rápido que el del MCM, y puesto que sabemos que:

\[mcm(a,b) = \frac{a \cdot b}{mcd(a,b)}\]

salía más a cuenta calcular mcd primero y en base a él el mcm, que es lo que hace el código. Para calcular el primer exponente, no hay mucho que hacer. El algoritmo sólo nos pide un número entre 1 y \(\phi(n)\). Pero, puesto que elijo un número aleatorio de tamaño \(t/8\), no necesito compararlo con \(\phi(n)\) pues siempre será, matemáticamente menor. También me he encontrado mucha literatura que parece tener cierta predilección y sugería el uso sistemático de 65537 (y múltiplos de él) como exponente e y calcular el d en base a él. He estado curioseando algunas claves que tengo por el disco duro y efectivamente algunas parecen confirmarlo, pero otras no. En todo caso, no encuentro una explicación para ello y prefiero que la aleatoriedad trabaje.

Por último, para calcular el segundo exponente necesitaremos la función modinverso, que calcula el módulo inverso:

proc modinverso { e phi } {
    set m0 $phi
    set y 0
    set x 1

    try {
        if {$phi == 1} {return 0}
        while {$e > 1} {
            set q [expr {$e / $phi}]
            set t $phi

            set phi [expr {$e % $phi}]
            set e $t
            set t $y

            set y [expr {$x - $q * $y}]
            set x $t
        }
        if {$x < 0} {
            set x [expr {$x + $m0}]
        }
        return $x
    } on error {} {
        return -1
    }
}

Como se puede observar, el código de cálculo está dentro de una cláusula try. Esto es porque no siempre existe un d, dados un e y un \(\phi\). Cuando esto ocurre termina produciéndose una división por 0 y se genera el consiguiente error. En esos casos, la función devolverá -1. Cuando esto ocurre hay que volver a seleccionar otro exponente e y repetir el cálculo.

Es decir, como no siempre dado un exponente podemos calcular su módulo inverso, en algunas ocasiones nos encontraremos que debemos repetir los cálculos, como veremos a continuación. De momento, nos basta con saber que todos estos datos calculados son devueltos en un diccionario de nombre key.

Generar los ficheros de claves

Hasta ahora hemos visto cómo realizar todos los cálculos para obtener un diccionario con los datos necesarios para cifrar-descifrar cadenas. Todo este proceso resultará más largo cuanto más grande sea el tamaño de clave, pero, sólo necesitan hacerse una vez. Los datos que se han calculado pueden guardarse y utilizarse para el cifrado y descifrado sin necesidad de repetirlo todo cada vez.

Finalmente, se utiliza una función que una vez realizados los cálculos los guarda en archivos. Concretamente dos, uno contendrá la clave pública y otra la clave privada. Necesita el tamaño en bytes del tamaño de cada número primo y una cadena con el nombre que queremos para la clave y que se usará como base para el nombre de los archivos de clave. Esta función es:

proc obtener-claves {t nombre} {
    set key [generar-clave $t]

    set tam [expr {$t + 1}]
    while {[dict get $key "d"] == -1 | [dict get $key "t"] < (16 * $t)} {
        if {[dict get $key "d"] == -1} {
            puts "Clave indefinida."
        } else {
            puts "Clave incompleta."
            set tam [expr {$tam + 1}]
        }
        set key [generar-clave $tam]
    }

    # Escribir clave pública
    set fpub "$nombre-pub.key"
    set f [open $fpub w]
    puts $f "n:[dict get $key n]\ne:[dict get $key e]"
    close $f
    # Escribir clave privada
    set fpriv "$nombre-priv.key"
    set f [open $fpriv w]
    foreach {k v} $key {
        puts $f "$k:$v"
    }
    close $f
    return $key
}

Vemos que lo primero que hace esa función es generar una clave. Con esa clave puede ocurrir, sin haber puesto comprobaciones hasta ahora, que aleatoriamente se hayan generado un par de números primos no tan grandes como se desea o que no se haya podido calcular d, el segundo exponente, por los motivos que comenté antes. Se podría acelerar los cálculos repitiendo sólo aquellos necesarios con anterioridad y no generando una nueva clave por completo. Pero dejo eso para una posterior refactorización y mejora del código.

Realizados todos los cálculos e incluso generando un par de ficheros con las claves... ¿funciona?

Cifrar y descifrar cadenas

Para cifrar y descifrar cadenas, necesitamos las claves correspondientes, obtenidas en los pasos anteriores. Sin embargo, como ya guardamos las claves en ficheros mediante la función obtener-claves, lo que nos hace falta es leerlas desde donde las guardamos:

proc leer-fichero-clave {nombre} {
    try {
        set f [open $nombre r]
        set datos [split [read $f] "\n:"]
        close $f
    }

    foreach {k v} [lrange $datos 0 [expr {[llength $datos] - 2}]] {
        dict set key $k $v
    }
    return $key
}

Es una función muy sencilla: se le proporciona un nombre de fichero y lo lee. Espera encontrar una lista de parámetros con un formato muy simple, en cada línea un par nombre:valor. Por ejemplo, una clave privada tendrá los siguientes valores:

p:2496806461475996779639
q:747147072320567882239
n:1865481637842867751904719692788458184931721
t:141
phi(n):310913606307144625316912623209110270044974
e:73470389151338783283577819257589238878901
d:202567603045917330908610474508371510582647

mientras que su par, la clave pública será:

n:1865481637842867751904719692788458184931721
e:73470389151338783283577819257589238878901

Lo que hace es leer todo el contenido de golpe, dividiendo el resultado en una lista de pares que luego se convierten en un diccionario. Quizá la parte más oscura del código anterior es que se elimina la línea en blanco que genera la escritura, convertida en una cadena vacía, {}, generada en la lectura, mediante un lrange. Sería recomendable algún tipo de código, como algún encabezado de fichero, que nos permita asegurar que es un fichero de clave bien formado.

El código para cifrar y descifrar consiste en dos pequeñas funciones que hacen el cálculo \(c = m^e \; (mod \, n)\) para cifrar y \(m \equiv c^d \; (mod \, n)\) para descifrar:

proc rsa-encript {cadena key} {
    # Convertir la cadena de entrada en un número
    set num [cad-a-num $cadena]
    set n [dict get $key n]
    set e [dict get $key e]
    if {$num < $n} {
        set resultado [expmod $num $e $n]
    } else {
        error "«$cadena» es demasiado largo para la clave especificada."
    }
    return $resultado
}

proc rsa-decript { num key } {
    set n [dict get $key n]
    set d [dict get $key d]
    return [num-a-cad [expmod $num $d $n]]
}

A la primera le proporcionamos una cadena y una clave. Convierte la cadena a un número que lo representa. Eso se hace mediante la función:

proc cad-a-num {cadena} {
    return [format %lld 0x[binary encode hex $cadena]]
}

Ésta, lo que hace es convertir la cadena en bytes hexadecimales con binary y luego pasarlo a número decimal con el que poder operar con format.

Antes de cifrar se comprueba que el módulo sea mayor que el número que se debería cifrar, pues si no es así no se cumpliría la equivalencia de exponentes para el descifrado. Por ello, si ocurriera eso, se lanza un error. En caso contrario devuelve el valor cifrado.

El paso contrario es equivalente, pero a la inversa, se introduce un número y una clave y devuelve una cadena formada con el resultado del cálculo, mediante la función num-a-cad

proc num-a-cad {num} {
    return [binary decode hex [format %llx $num]]
}

que realiza las operaciones inversas de cad-a-num, convierte el número a formato hexadecimal mediante format y el resultado en una cadena mediante binary. Si el número hexadecimal está bien formado y corresponde a valores de caracteres, la cadena quedará bien formada.

Como ejemplo:

> tclsh
% lappend auto_path ../src
/usr/lib64/tcl/tcl8.6 /usr/lib64/tcl /usr/lib /usr/share/tcl ../src
% package require rsa
1.0
% set key [rsa::obtener-claves 8 corto-inseguro]
Generando clave aleatoria de 128 bits
Clave indefinida.
Generando clave aleatoria de 144 bits
Clave indefinida.
Generando clave aleatoria de 144 bits
p 2496806461475996779639 q 747147072320567882239 n 1865481637842867751904719692788458184931721 t 141 phi(n) 310913606307144625316912623209110270044974 e 73470389151338783283577819257589238878901 d 202567603045917330908610474508371510582647
% set c [rsa::rsa-encript "hola" $key]
1084245477992884776922019206560106173451692
% rsa::rsa-decript $c $key
hola
%

Se puede ver que se ha generado la clave, se ha cifrado la cadena "hola" y se ha vuelto a descifrar. Para observar el mismo proceso desde la carga de ficheros podríamos hacer la simulación completa, empezando por el cifrado:

> tclsh
% lappend auto_path ../src
/usr/lib64/tcl/tcl8.6 /usr/lib64/tcl /usr/lib /usr/share/tcl ../src
% package require rsa
1.0
% set key [rsa::leer-fichero-clave "corto-inseguro-pub.key"]
n 1865481637842867751904719692788458184931721 e 73470389151338783283577819257589238878901
% set c [rsa::rsa-encript "hola" $key]
1084245477992884776922019206560106173451692
% set conerror [rsa::rsa-encript "Hola mundo del cifrado!" $key]
«Hola mundo del cifrado!» es demasiado largo para la clave especificada.
% puts $conerror
can't read "conerror": no such variable
% 
...
% set key [rsa::leer-fichero-clave corto-inseguro-priv.key]
p 2496806461475996779639 q 747147072320567882239 n 1865481637842867751904719692788458184931721 t 141 phi(n) 310913606307144625316912623209110270044974 e 73470389151338783283577819257589238878901 d 202567603045917330908610474508371510582647
% rsa::rsa-decript $c $key
hola
%

Se puede observar que la clave privada incluye también los datos de la pública, por lo que se puede cifrar y descifrar sólo cargando la clave privada. Sin embargo, con la clave pública sólo es posible el cifrado y debemos cargar la privada para el descifrado.

Conclusiones

El algoritmo está funcionando, ¿qué faltaría? Pues faltan todas las acciones correspondientes a la conformación correcta de claves, para intercambio con otras aplicaciones. El módulo sólo es capaz de utilizar las claves obtenidas con un formato muy básico, crudo. Haría falta tener en cuenta el tema de los tamaños y cómo las herramientas de cifrado serias, realizan operaciones de relleno para no dar pistas de los tamaños empleados, para no facilitar el cálculo inverso de claves. Pero en general, estoy satisfecho con el resultado y ha sido más sencillo de implementar de lo que me esperaba.

Me estoy planteando, por seguir con la serie sobre criptografía con hacer un par de cosas más: algún algoritmo de cifrado simétrico y alguno de hash. Para firma digital también se utiliza RSA, así que no tendría mucho más que explicar, salvo el protocolo de firmado. Amenazo con volver.

Código

El código completo está a continuación. Necesita un refactorizado y muchas pruebas para determinar su efectividad. Pero teóricamente todas las premisas del algoritmo se cumplen. Una de las cosas que debería hacerse es limitar la cantidad de funciones accesibles desde el exterior, en el bloque namespace export. Hay también alguna función que se hizo para incorporar algún otro algoritmo de cálculo y que se ha quedado en el código como código muerto. Habría que hacer limpieza.

He metido comentarios en todas las funciones para que se pueda hacer uno la idea de lo que hace, los parámetros que necesita y lo que devuelve.

# Paquete que proporciona el archivo
package provide rsa 1.0

# Creamos un `namespace` para evitar choques de nombre
namespace eval ::rsa {

    # Rutinas que se exportan para trabajar con ellas
    namespace export num-bits es-primo generar-primo\
        exp-rapida obtener-claves mcm modinverso pow expmod\
        rsa-encript rsa-decript leer-fichero-clave

    # ######################################################################
    # Procedimiento: num-bits
    #   Devuelve el número de bits empleados para representar un número entero
    # Parámetros:
    #   `valor` representa el número del que queremos saber el tamaño
    # Devuelve:
    #   La cantidad de bits empleados en la representación del número
    #
    proc num-bits valor {
        set bits -1
        set p 0
        while {$valor >= $p} {
            set p [expr {(1 << [incr bits])}]
        }
        return $bits
    }

    # ######################################################################
    # Procedimiento: aleatorio
    #   Devuelve un número aleatorio (biginteger) utilizando el dispositivo
    #   `/dev/random` de Unix (Esto no funcionará en güindón)
    # Parámetros:
    #   `nbytes` determina el número de bytes que se leen del dispositivo
    #   y, por tanto, el tamaño del número devuelto
    # Devuelve:
    #   Un número, entero, aleatorio dentro del rango establecido
    #
    proc aleatorio {{nbytes 8}} {
        set cadena ""
        # Leo `nbytes` del dispositivo `/dev/random`
        set f [open /dev/random rb]
        for {set b 0} {$b < $nbytes} {incr b} {
            set byte [read $f 1]
            # cada byte se convierte a una cadena hexadecimal y se
            #      concatena en `cadena`
            set cadena $cadena[byte-a-hex $byte]
        }
        close $f
        # convierto la cadena hexadecimal en un número decimal (big %ll)
        return [format %lld 0x$cadena]
    }

    # ######################################################################
    # Procedimiento: entero-entre
    #   Devuelve un entero aleatorio entre los valores mínimo y máximo. El
    #   número aleatorio, devuelto por [aleatorio 8] al ser de 8 bytes,
    #   tendrá un rango entre 0 y 18446744073709551615
    # Parámetros:
    #   `min` El valor mínimo que debe devolver
    #   `max` El valor máximo que debe devolver
    # Devuelve:
    #   Un entero `n` tal que 'min <= n <= max'
    #
    proc entero-entre {min max} {
        set dec [aleatorio 8]
        # el número máximo que se puede obetener aleatoriamente por el
        # código anterior es 18446744073709551615
        return round([expr {(($dec/18446744073709551615.0) * ($max - $min)) + $min}])
    }

    # ######################################################################
    # Procedimiento: byte-a-hex
    #   Convierte un `byte` a una cadena hexadecimal
    # Parámetros:
    #   `byte` valor binario que convierte en cadena
    # Devuelve:
    #   Una cadena con la expresión en hexadecimal del byte proporcionado
    #
    proc byte-a-hex {byte} {
        return [binary encode hex $byte]
    }

    # ######################################################################
    # Procedimiento: cad-a-num
    #   Convierte una cadena a una expresión numérica resultante de tratar
    #   sus caracteres mediante los números que los representan.
    # Parámetros:
    #   `cadena` Es una cadena de texto.
    # Devuelve:
    #   El valor numérico que la representa.
    #
    proc cad-a-num {cadena} {
        return [format %lld 0x[binary encode hex $cadena]]
    }

    # ######################################################################
    # Procedimiento: num-a-cad
    #   Toma un número para convertirlo en cadena.
    # Parámetros:
    #   `num` Un número que expresa los caracteres de una cadena
    # Devuelve:
    #   Una cadena
    #
    proc num-a-cad {num} {
        return [binary decode hex [format %llx $num]]
    }

    # ######################################################################
    # Procedimiento: expmod
    #   Exponenciación modular. Calcula el residuo cuando una base se eleva
    #   a un exponente y se divide por el módulo. Se utiliza para acelerar
    #   el cálculo con grandes números.
    #   (Algoritmo sacado de la wikipedia)
    # Parámetros:
    #   `base` el número base
    #   `exp`  el exponente
    #   `mod`  el módulo
    # Devuelve:
    #   El resultado de la exponenciación
    #
    proc expmod {base exp mod} {
        set x 1
        set y $base
        while {$exp > 0} {
            if {($exp % 2) == 1} {set x [expr {($x * $y) % $mod}]}
            set y [expr {($y * $y) % $mod}]
            set exp [expr {$exp >> 1}]
        }
        return [expr {$x % $mod}]
    }

    # ######################################################################
    # Procedimiento: mr-test
    #   Proc. auxiliar del test de «Miller-Rabin» sobre primalidad, sacando
    #   el bucle de dentro del bucle principal.
    # Parámetros:
    #   `d` llega como el entero inmediatamente inferior del número testado
    #   `n` el número testado
    # Devuelve:
    #   0 significa que `n` es compuesto
    #   1 significa que `n` es primo
    #
    proc mr-test {d n} {
        set a [expr [entero-entre 1 [expr {$n - 1}]] + 2]
        set x [expmod $a $d $n]
        if {$x == 1 || $x == ($n - 1) } {return 1}
        while {$d != ($n - 1)} {
            set x [expr {($x * $x) % $n}]
            set d [expr {$d * 2}]
            if {$x == 1} {
                return 0
            } elseif {$x == ($n - 1)} {
                return 1
            }
        }
        return 0
    }

    # ######################################################################
    # Procedimiento: miller-rabin
    #   Algoritmo de primalidad probabilístico pero altamente utilizado en
    #   criptografía. Está diseñado para evitar los falsos positivos.
    #   (Algoritmo sacado de la wikipedia, aunque adaptado)
    # Parámetros:
    #   `n` El número cuya primalidad deseamos probar
    #   `k` El número de pruebas que queremos hacer
    # Devuelve:
    #   0 significa que el número `n` es compuesto
    #   1 significa que el número `n` es primo
    #
    proc miller-rabin { n k } {
        set d [expr {$n - 1}]
        while { ($d % 2) == 0 } {
            set d [expr {$d >> 1}]
        }
        for {set i 0} {$i < $k} {incr i} {
            if {[mr-test $d $n] == 0} {
                return 0
            }
        }
        return 1
    }

    # ######################################################################
    # Procedimiento: es-primo
    #   Determina si un número es primo.
    # Parámetros:
    #   `num` El número cuya primalidad será testeada
    # Devuelve:
    #   0 si el número `num` es compuesto
    #   1 si el número `num` es primo
    #
    proc es-primo num {
        # la variable `k` podría ajustarse por parámetro.
        # de momento la calculo en base a la cantidad de bits de `num`, de
        # esta manera habrá un muestreo proporcional al tamaño del número
        set k [expr {2 * [num-bits $num]}]
        if {$k < 8} {set k 8}
        # hacer la prueba `k` veces
        set primo [miller-rabin $num $k]
        return $primo
    }

    # ######################################################################
    # Procedimiento: generar-primo
    #   Devuelve un número primo del tamaño en bytes especificado
    # Parámetros:
    #   `s` es el tamaño en bytes del número deseado
    # Devuelve:
    #   Un número primo
    #
    proc generar-primo s {
        while { 1 } {
            set p [aleatorio $s]
            if {($p % 2) == 0} {
                continue
            } else {
                if { [es-primo $p] } {
                    break
                }
            }
        }
        return $p
    }

    # ######################################################################
    # Procedimiento: pow
    #   Calcula la potencia de la base `b` calculando sólo las cifras «1»
    #   (o significativas) del exponente `e` expresado como binario.
    # Parámetros:
    #   `b` Base del cálculo
    #   `e` Exponente del cálculo
    # Devuelve:
    #   Devuelve el cálculo b^e
    #
    proc pow { b e } {
        set r 1
        while {$e > 0} {
            if {$e & 1} {
                set r [expr {$r * $b}]
            }
            set b [expr {$b * $b}]
            set e [expr {$e >> 1}]
        }
        return $r
    }

    # ######################################################################
    # Procedimiento: mcd (máximo común divisor)
    #   Calcula el m.c.d. de dos números
    # Parámetros:
    #   `a` Uno de los números
    #   `b` El otro número
    # Devuelve:
    #   El máximo común divisor de los dos números
    #
    proc mcd {a b} {
        while {$a != $b} {
            if {$a > $b} {
                set a [expr {$a - $b}]
            } else {
                set b [expr {$b - $a}]
            }
        }
        return $a
    }

    # ######################################################################
    # Procedimiento: mcm (mínimo común múltiplo)
    #   Calcula el m.c.m. de dos números sabiendo la relación que hay con
    #   el máximo común divisor, que es bastante más rápido de calcular:
    #                 a x b
    #   mcm(a, b) = ---------
    #               mcd(a, b)
    # Parámetros:
    #   `a` Uno de los números a calcular
    #   `b` El otro número
    # Devuelve:
    #   El mínimo común múltiplo de dos números
    #
    proc mcm {a b} {
        return [expr {$a * $b / [mcd $a $b]}]
    }

    # ######################################################################
    # Procedimiento: modinverso
    #   Calcula el inverso de un módulo. Dado un exponente y un módulo
    #   encuentra otro exponente congruente con ellos. Si no existe un
    #   número congruente termina lanzando un error `divide by cero`. En
    #   ese caso devuelve un `-1`.
    # Parámetros:
    #   `e` Exponente calculado con anterioridad
    #   `phi` el phi(n) calculado
    # Devuelve:
    #   El segundo exponente para el cálculo del RSA
    #
    proc modinverso { e phi } {
        set m0 $phi
        set y 0
        set x 1

        try {
            if {$phi == 1} {return 0}
            while {$e > 1} {
                set q [expr {$e / $phi}]
                set t $phi

                set phi [expr {$e % $phi}]
                set e $t
                set t $y

                set y [expr {$x - $q * $y}]
                set x $t
            }
            if {$x < 0} {
                set x [expr {$x + $m0}]
            }
            return $x
        } on error {} {
            return -1
        }
    }

    # ######################################################################
    # Procedimiento: generar-clave
    #   Genera una clave completa con un tamaño `t` en bytes.
    # Parámetros:
    #   `t` Tamaño mínimo en bytes de la clave
    # Devuelve:
    #   Un diccionario con los datos de la clave generada
    #
    proc generar-clave {t} {
        puts "Generando clave aleatoria de [expr {16 * $t}] bits"

        # 1. generar dos números primos
        set p [generar-primo $t]
        while { 1 } {
            set q [generar-primo $t]
            if {$p != $q} break
        }
        dict set key "p" $p
        dict set key "q" $q

        # 2. Calcular el módulo
        set n [expr {$p * $q}]
        set t [num-bits $n]
        dict set key "n" $n
        dict set key "t" $t

        # 3. Calcular `phi(n)`
        #
        set phiN [mcm [expr {$p - 1}] [expr {$q - 1}]]
        dict set key "phi(n)" $phiN

        # 4. Calcular el exponente
        #    `e` ¿65537?
        #
        set e [aleatorio [expr {$t / 8}]]
        dict set key "e" $e

        # 5. Calcular el exponente `d`
        #
        set d [modinverso $e  $phiN]
        dict set key "d" $d

        return $key
    }

    # ######################################################################
    # Procedimiento: rsa-encript
    #   Cifra una cadena dada con los datos proporcionados por una clave.
    # Parámetros:
    #   `cadena` es la cadena de texto que queremos cifrar.
    #   `key` es un diccionario que debe tener al menos dos elementos:
    #         `n` es el módulo de cifrado-descifrado RSA.
    #         `e` es el exponente de cifrado RSA.
    # Devuelve:
    #   Un número que representa la cadena codificada.
    #
    proc rsa-encript {cadena key} {
        # Convertir la cadena de entrada en un número
        set num [cad-a-num $cadena]
        set n [dict get $key n]
        set e [dict get $key e]
        if {$num < $n} {
            set resultado [expmod $num $e $n]
        } else {
            error "«$cadena» es demasiado largo para la clave especificada."
        }
        return $resultado
    }

    # ######################################################################
    # Procedimiento: rsa-decript
    #   Descifra un número que contiene un mensaje cifrado mediante RSA.
    # Parámetros:
    #   `num` el número que hay que descifrar
    #   `key` un diccionario que debe contener al menos dos elementos:
    #         `n` es el módulo de cifrado-descifrado RSA.
    #         `d` es el exponente de descifrado RSA.
    # Devuelve:
    #   La cadena descifrada.
    #
    proc rsa-decript { num key } {
        set n [dict get $key n]
        set d [dict get $key d]
        return [num-a-cad [expmod $num $d $n]]
    }

    # ######################################################################
    # Procedimiento: obtener-claves
    #   Obtiene un par de ficheros con la clave pública y la clave privada.
    # Parámetros:
    #   `t` es el tamaño de la clave.
    #   `nombre` una cadena de texto que será el nombre utilizado para las
    #            claves generadas.
    # Devuelve:
    #   Nada
    #
    proc obtener-claves {t nombre} {
        set key [generar-clave $t]

        set tam [expr {$t + 1}]
        while {[dict get $key "d"] == -1 | [dict get $key "t"] < (16 * $t)} {
            if {[dict get $key "d"] == -1} {
                puts "Clave indefinida."
            } else {
                puts "Clave incompleta."
                set tam [expr {$tam + 1}]
            }
            set key [generar-clave $tam]
        }

        # Escribir clave pública
        set fpub "$nombre-pub.key"
        set f [open $fpub w]
        puts $f "n:[dict get $key n]\ne:[dict get $key e]"
        close $f
        # Escribir clave privada
        set fpriv "$nombre-priv.key"
        set f [open $fpriv w]
        foreach {k v} $key {
            puts $f "$k:$v"
        }
        close $f
        return $key
    }

    # ######################################################################
    # Procedimiento: leer-fichero-claves
    #   Lee el fichero de claves dado en el argumento `nombre`
    # Parámetros:
    #   `nombre` debe ser un nombre de archivo.
    # Devuelve:
    #   un diccionario con los valores de la clave encontrados en el fichero.
    #
    proc leer-fichero-clave {nombre} {
        try {
            set f [open $nombre r]
            set datos [split [read $f] "\n:"]
            close $f
        }

        foreach {k v} [lrange $datos 0 [expr {[llength $datos] - 2}]] {
            dict set key $k $v
        }
        return $key
    }
}

Footnotes:

Hay que recordar aquí, que el tamaño de la clave será el cuadrado del tamaño que entra en la función, pues \(n=p \cdot q\) y cada número primo, tanto p como q tendrán el tamaño t.

Aunque sólo sucedió en una ocasión y para tamaño de clave pequeño. Pero no está de más asegurarnos que son distintos.

Comentarios

Debido a algunos ataques mailintencionados a través de la herramienta de comentarios, he decidido no proporcionar dicha opción en el Blog. Si alguien quiere comentar algo, me puede encontrar en esta cuenta de Mastodon, también en esta otra cuenta de Mastodon y en Diaspora con el nick de Notxor.

Si usas habitualmente XMPP (si no, te recomiendo que lo hagas), puedes encontrar también un pequeño grupo en el siguiente enlace: notxor-tiene-un-blog@salas.suchat.org

Disculpen las molestias.

Notxor tiene un blog

Defenestrando la vida