Notxor tiene un blog

Defenestrando la vida

Generando un número primo grande

Notxor
2022-07-23

El título de este artículo podría haber sido algoritmo de cifrado RSA palote palote. En el artículo anterior comencé a hablar sobre cifrado mediante RSA y expliqué cómo funciona el algoritmo, en este abundo un poco más y comienzo la implementación en código. Voy a llegar hasta el momento de la generación de un número primo grande (muy grande), los algoritmos que he empleado y algunas otras cosas «laterales» que he considerado interesante explicar. Si te gustan los números primos sigue leyendo... y si no, pues sigue leyendo, que siempre se aprende algo.

Debo también explicar, que como últimamente le estaba dando al Tcl/Tk1 pensé en realizarlo sin necesidad de forzar a mis neuronas más de la cuenta cambiando de lenguaje. Si programas en otros lenguajes no debería ser muy difícil seguir el código escrito. En cada función he añadido comentarios con una breve explicación de lo que hace, qué es cada parámetro y que devuelve. Como puesto así, a cachos, es posible que no dé una idea general de cómo funciona, lo pondré todo junto, en un sólo listado, al final del artículo, por si alguien tiene la curiosidad de probarlo. El dividirlo, durante la explicación, en pequeños fragmentos, es porque es más fácil de encontrar el código al que hago referencia. Pero vamos al tajo.

Conseguir un generador de números primos de cualquier tamaño es el objetivo. Mi forma de trabajar es el habitual: unos pocos tests y a cumplirlos:

test esPrimo3 { "Tres es primo" }     -body { es-primo 3 }    -result 1
test esPrimo5 { "Cinco es primo" }    -body { es-primo 5 }    -result 1
test esPrimo8 { "Ocho no es primo" }  -body { es-primo 8 }    -result 0
test esPrimo9 { "Nueve no es primo"}  -body { es-primo 9 }    -result 0
test esPrimo11 { "Once es primo" }    -body { es-primo 11 }   -result 1
test esPrimo977 { "977 es primo" }    -body { es-primo 977 }  -result 1
test esPrimo978 { "978 no es primo" } -body { es-primo 978 }  -result 0
test esPrimo1999 { "1999 es primo" }  -body { es-primo 1999 } -result 1
test esPrimo2915 { "2915 no" }        -body { es-primo 2915 } -result 0
test esPrimo3571 { "3571 es primo" }  -body { es-primo 3571 } -result 1

La lista de tests de números primos, y compuestos, puede ser tan larga como quieras. Pongo estos sólo como muestra.

Por supuesto, de momento fallarán todos los tests porque ni siquiera existe la función es-primo, pero podemos ver que dicha función necesitará un parámetro numérico y deberá devolver 1 si el parámetro es un número primo y 0 si el parámetro en un número compuesto.

El primer procedimiento que creo será es-primo:

proc es-primo num {
    return 0
}

Evidentemente fallará en la mitad de los tests de los números que sean primos, pero al menos me he quitado la ristra de errores que dicen que no existe el procedimiento llamado.

Otro hecho, aunque este puramente subjetivo, es la desazón que me produce el que algún test falle. Independientemente de que sepa el motivo, o falte algo por implementar y esté seguro de que es lo esperado... el desasosiego se apodera de mí. Hay que picar código hasta conseguir pasarlos todos. Pero primero hay que saber qué escribir y aquí me tropecé con el problema de la primalidad.

El problema de primalidad

Pensaba que a estas alturas las cosas estarían mejor resueltas, pero encontré que el problema de la primalidad2, aún tiene algunas aristas que pulir. Me gustaría, por aquello de la seguridad, tener la certeza de estar empleando un par de números primos para la tarea. Saber la primalidad en números pequeños es bastante sencillo, pero los que necesito son enormes y es más complicado asegurarnos. Encontré dos formas de determinar la primalidad que podían servirme. Podría hacer algo de historia, porque este problema viene ya desde la Antigua Grecia y hay algoritmos de todo tipo para determinar si un número es primo. Pero por no enrollarme demasiado hablaré de los dos métodos más aceptados a estas alturas:

  • Algoritmos con certeza
    • Algoritmo de Lucas-Lehmer
    • Algoritmo AKS
  • Algoritmos probabilísticos
    • Algoritmo Miller-Rabin

Primero probé con algoritmos seguros, concretamente el de Lucas-Lehmer me pareció bastante sencillo de implementar.

Algoritmo de Lucas-Lehmer

Lo podéis encontrar en la wikipedia, no voy a entrar en más explicaciones ni darle más a las matemáticas. A continuación pongo la implementación del algoritmo, tal y como la escribí:

proc lucas-lehmer num {
    set s 4
    set m [expr {(2 ** $num) - 1}]
    for {set j 2} {$j <= ($num - 1)} {incr j} {
        set sj $s
        set s [expr {(($sj ** 2) - 2) % $m}]
        if {$sj == 0} {return 1}
    }
    return 0
}

Sencillo de entender y escribir, va probando si hay algún \(2 \leq x \leq n-1\) que divida de forma exacta a \(n\), pero nos encontramos con un problema de ejecución:

% rsa::generar-primo 8
exponent too large

Vale, si el número es muy grande, que para lo que necesitamos 8 bytes es pequeño, no funciona... la solución pasa por implementar una exponenciación más resultona y que funcione con números grandes.

Para eso implementé una función de exponenciación rápida... también podéis mirar el algoritmo y las explicaciones en la wikipedia3

proc exp-rapida {base exp} {
    set res 1
    for {set i 1} {$i <= $exp} {incr 1} {
        set res [expr {$res * $exp}]
    }
    return $res
}

Es rápida porque no debe hacer todos los cálculos, pero aún así es lenta. Al final el tiempo empleado entre unas cosas y otras hace que este algoritmo sea impracticable. Para números primos de 8 bytes se podía pasar, tranquilamente, una hora calculando. Utilizarlo para números de \(2^8\) bits hubiera sido morir en el intento.

Estuve mirando también el algoritmo AKS, que menciono antes, pero es mucho más lioso. Había seis pasos, cada uno de ellos lento, con muchos bucles y, he de confesar que a ojo, me pareció aún lento aún que el Lucas-Lehmer.

Algoritmo de Miller-Rabin

La otra opción era implementar uno probabilístico... y escogí el algoritmo de Miller-Rabin por dos motivos:

  1. Sin tener mucha idea de por qué, aunque leí unas parrafadas enormes con justificaciones matemáticas, es el más utilizado en criptografía.
  2. Siendo un algoritmo probabilístico, parece estar diseñado para reducir al máximo la existencia de falsos positivos. Es decir, que si falla en su respuesta, posiblemente esté descartando algún número primo considerándolo compuesto, pero al final, las operaciones del algoritmo RSA se realizarán con una seguridad razonable asumiendo que los números utilizados son primos.

El inconveniente: algunos tests fallan algunas veces, especialmente con números pequeños y no es raro que rechace el 5 y el 11 considerándolos como compuestos. La precisión del algoritmo depende también del número de iteraciones que utilizas y yo lo hice dependiente del tamaño del número que queremos probar.

El algoritmo funciona de la siguiente forma:

  • Dado un número \(n > 1\) y el número de veces \(k\) que queremos probarlo
  • Se definen \(r\) y \(s\) tal que \(r\) es impar y \((n - 1)=r \cdot 2^s\)
  • Para \(1 \leq j \leq k\) hacer:
    1. \(a \leftarrow x\) siendo \(x\) un entero aleatorio entre \([n, n-2]\)
    2. \(y \leftarrow a^r \; mod \, n\)
    3. Si \((y \neq 1) \land (y \neq n - 1)\) entonces:
      1. \(j \leftarrow 1\)
      2. Mientras \(j \leq (s - 1) \land y \neq (n-1)\) hacer:
        1. \(y \leftarrow y^2 \; mod \, n\)
        2. Si \(y = 1\) entonces devolver compuesto
        3. \(j \leftarrow j + 1\)
      3. Si \(y \neq (n-1)\) entonces devolver compuesto
  • devolver posible primo

El algoritmo también presenta cierta sencillez, aunque no deja de ser un bucle dentro de un bucle. Lo he implementado de la siguiente manera:

  # ######################################################################
# 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 2 + [entero-entre 1 [expr {$n - 1}]]]
    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
}

He sacado el bucle interno a otra función auxiliar pero básicamente es lo mismo. Hay que recordar que con esta función, la probabilidad de falso positivo es \((\frac{1}{4})^k\). A mayor \(k\) es más pequeña la probabilidad de que sea un falso primo.

He hecho depender el número de pruebas del tamaño del número. Para saber el número de bits de un número utilizo la siguiente función:

# ######################################################################
# 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
}

Antes se llamaba al test de primalidad directamente. Sin embargo, al incluir la necesidad de añadir el número de veces que debe hacer la prueba, se ha optado por poner una función es-primo intermedia entre las funciones de generar-primo y la de test, miller-rabin.

Esta función se llama desde el siguiente código:

# ######################################################################
# 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 {
    set veces 0
    while { 1 } {
        incr veces
        set p [aleatorio $s]
        if {($p % 2) == 0} {
            continue
        } else {
            # if { [lucas-lehmer $p] } 
            if { [es-primo $p] } {
                break
            }
        }
    }
    return [list $veces $p]
}

Como he explicado antes generar-primo primariamente llamaba al algoritmo Lucas-Lehmer. Pero primero tenía que generar el número que hay que contrastar. El parámetro que se le pasa a esta función indicará el tamaño en bytes del número que queremos obtener con aleatorio... y aquí me encontré también con la dificultad de generar números aleatorios.

Generación de números aleatorios

Primero pongo la función que escribí para obtener un número aleatorio y luego me explico mejor:

# ######################################################################
# 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[binary encode hex $byte]
    }
    close $f
    # convierto la cadena hexadecimal en un número decimal (big %ll)
    set n [format %lld 0x$cadena]
    return $n
}

Podría haber utilizado la función habitual del lenguaje, que según la notación de Tcl es ::tcl::mathfunc::rand. Sin embargo, quería algo menos predecible que un número pseudoaleatorio. Una opción sería utilizar la API que ofrecen algunos organismos como www.random.org para la generación de números aleatorios. Sin embargo, he utilizado otro método: leer del dispositivo /dev/random4, básicamente porque lo tengo a mano.

Siguiendo la filosofía de Unix, se utiliza como cualquier fichero: se abre el fichero, se lee de él y se cierra. Aquí tropiezo con el tipo de datos que devuelve y la idiosincrasia del lenguaje que estoy utilizando. En Tcl todo es una cadena, no hay tipos. Por tanto, tengo que convertir el contenido binario leído en una cadena. Lo que hago es leer uno a uno los bytes que me dice el parámetro, convierto el binario obtenido en una cadena que lo expresa en hexadecimal y cuando termino de leer bytes, cierro el archivos y convierto la cadena hexadecimal formada en un número decimal utilizando la función format. Por defecto, si se llama sin parámetro devolverá un número aleatorio de 8 bytes.

Otra de las funciones aleatorias que necesita el código es entero-entre. Esta función la llama la función auxiliar (el bucle interno, si lo prefieres llamar así). En este caso, puesto que ya tenía hecha la función de aleatorio, lo que hace es obtener un número aleatorio de 8 bytes mediante dicha función y hacer un simple cálculo.

# ######################################################################
# 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}])
}

El cálculo consiste en obtener un número entre 0 y 0xffffffffffffffff y hacer una regla de tres.

De momento, con todo lo explicado hasta aquí, ya consigo hacer el primer paso del algoritmo RSA, que es conseguir números primos muy altos. El siguiente paso será, después de probar que efectivamente el código es seguro, generar las dos claves que necesitamos.

De momento, me pondré con una refactorización para eliminar todo el código inútil que hay. El código que muestro al final del artículo está aún sin refactorizar. Por ejemplo, para hacer pruebas me puse a contar también el número de intentos de encontrar un número primo al azar. Y la función que debería devolver un número primo, devuelve una lista con el número de intentos y el número primo juntos.

Pruebas

Por ejemplo, buscando primos de 16 bytes me puse a contar la cantidad de veces que hay que tirar el dado para que nos devuelva un número primo. Me hice un script sencillito cuya salida era algo parecido a:

Intentos:  198 -- Primo: 42257895601817581841334192879244172861
Intentos:  149 -- Primo: 268013252449733683657437157911978100873
Intentos:  138 -- Primo: 118450050774604994062315721188627087679
Intentos:    1 -- Primo: 249880285931983262494435137763895968483
Intentos:   36 -- Primo: 8008379698234226130537034850572345927
Intentos:   51 -- Primo: 32904817994662091085344712101414460091
Intentos:    1 -- Primo: 298689198394747193867273799433969986389
Intentos:   44 -- Primo: 219365110495942244274573360479389771271
Intentos:   80 -- Primo: 285990911941440299303524155960171686387
Intentos:  291 -- Primo: 338447441262384199035015634515322563473
...

Mostré esta salida a un amigo y le llamaron la atención los dos unos que hay. ¿Es difícil acertar a la primera? ¿Cómo de difícil? ¿Estamos obteniendo verdaderos números primos? Pues nada, ya tuvimos una tarde entretenida haciendo pruebas y más pruebas.

Para resumir, y no irme por las ramas explicativas, para saber si era difícil acertar a la primera, hice otro script, también sencillito, que me calculara la media del tiempo empleado en cada intento y la media de intentos necesarios para encontrar un número primo. El cálculo se repetía 100 veces para cada familia de números primos. No fue más amplia, porque los tiempos empleados para los primos de 32 y 64 bits se convertían en prohibitivos. Para calcular los 100 correspondientes a los 64 bits, sólo tenéis que hacer un simple cálculo y sabréis que tardó más de hora y media en hacerlo.

bytes seg. intentos
8 0.0611 37.39
16 0.5663 72.08
32 4.7169 177.66
64 47.1604 352.71
  • bytes: Tamaño en bytes del número primo generado
  • seg.: Tiempo medio de cálculo en segundos
  • intentos: Número medio de intentos antes de encontrar al azar un número primo.

Las conclusiones de estas pruebas son que algunas veces se han encontrado número primos a la primera, cosas del azar, pero ha sido en raras ocasiones. Podríamos considerar que la media de intentos, aunque haga falta un muestreo más alto, sería una estimación la densidad de números primos entre el conjunto de números de ese tamaño. Por último, que la generación de claves seguras puede llevar algunos minutos de proceso.

Conclusión

De momento el proyecto sigue adelante y más fácilmente de lo esperado (sí, esperaba más complicación). Aún utilizando un algoritmo probabilístico para obtener los primos el proceso es lento, pero seguro. Como dije antes la probabilidad matemática de obtener un falso positivo es \((\frac{1}{4})^k\). Utilizo la fórmula \(2 \cdot num-bits\). En números como los que se utilizarán en las claves ese error será de \((\frac{1}{4})^{1024} = 3,09434604738 \cdot 10^{-617}\).

Después de la refactorización, continuaré con la implementación del algoritmo RSA. Sigan atentos a sus pantallas...

Código fuente completo

A continuación se muestra todo el código del paquete tal y como se encuentra en esta fase del desarrollo. Omito las pruebas unitarias que he ido haciendo, porque harían muy largo este apartado y son triviales. Al finalizar la serie de artículos publicaré todo el código.

# 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

    # ######################################################################
    # 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: exp-rapida
    #   Calcula el resultado de una exponenciación.
    # Parámetros:
    #   `base` la base del cálculo
    #   `exp` el exponente del cálculo
    # Devuelve:
    #   El resultado de la operación
    #
    proc exp-rapida {base exp} {
        set res 1
        for {set i 1} {$i <= $exp} {incr 1} {
            set res [expr {$res * $exp}]
        }
        return $res
    }

    # ######################################################################
    # Procedimiento: lucas-lehmer
    #   Realiza el tests de primalidad con el algoritmo Lucas-Lehmer
    # Parámetros:
    #   `num` El número que debe ser probado
    # Devuelve:
    #   `0` significa que `num` es compuesto
    #   `1` significa que `num` es primo
    #
    proc lucas-lehmer num {
        set s 4
        set m [expr {[exp-rapida 2 $num] - 1}]
        for {set j 2} {$j <= ($num - 1)} {incr j} {
            set sj $s
            set s [expr {(($sj ** 2) - 2) % $m}]
            if {$sj == 0} {return 1}
        }
        return 0
    }

    # ######################################################################
    # 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[binary encode hex $byte]
        }
        close $f
        # convierto la cadena hexadecimal en un número decimal (big %ll)
        set n [format %lld 0x$cadena]
        return $n
    }

    # ######################################################################
    # 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: 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 2 + [entero-entre 1 [expr {$n - 1}]]]
        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 {
        set veces 0
        while { 1 } {
            incr veces
            set p [aleatorio $s]
            if {($p % 2) == 0} {
                continue
            } else {
                # if { [lucas-lehmer $p] } 
                if { [es-primo $p] } {
                    break
                }
            }
        }
        return [list $veces $p]
    }
}

Footnotes:

1

Lo pronuncian tíkel tikey yo lo deletreaba antes, pero ahora me hace gracia el nombre tal como lo pronuncian los programadores anglosajones, como D. Richard Hipp el padre de Sqlite o Fossil.

2

Es decir, el determinar con certeza si un número es primo o no.

3

Ya disculparéis que no ponga el enlace.

4

Si alguien quiere copiar el código en Windows no le funcionará. Habría que buscar otra fuente de números aleatorios razonablemente segura.

Categoría: criptografia

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.