IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Generacion de numeros primos fuertes paracriptografıa
Juan Alfredo Salas Santillana
Escuela de Ciencia de la ComputacionUniversidad Catolica San Pablo
4 de julio de 2014
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Outline
1 Introduccion
2 Generadores de primos fuertesEl metodo original del rsaAlgoritmo de Williams/SchmidAlgoritmo de Gordon
3 Comparativas
4 Conclusiones
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Algunas definiciones
Numero primo: Es un entero mayor que 1 que tieneunicamente dos divisores distintos: el mismo y el 1
|Q| es el tamano en bits de Q.
Criba de Eratostenes: Algoritmo que permite hallar todos losnumeros primos menores que un numero natural dado n
Test de primalidad: Algoritmo que, dado un numero deentrada n, no consigue verificar la hipotesis de un teoremacuya conclusion es que n es compuesto.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Que es un primo fuerte
Un numero primo fuerte es aquel que cumple las siguientescaracterısticas:
|P| debe ser grande (Actualmente se propone 2048 bits omas).
El mayor factor de P − 1, llamado P ′ debe cumplir que |P ′|sea grande.
El mayor factor de P ′ − 1, llamado P ′′ debe cumplir que |P ′′|sea grande.
El mayor factor de P + 1, llamado P+ debe cumplir que |P+|sea grande.
Estas definiciones pueden variar en la diversa literatura, segun elautor.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Espiral de Ulam
La espiral de Ulam, descrita por el matematicopolaco-estadounidense Stanis law Marcin Ulam (1909-1984), es unaforma de representacion grafica de numeros primos que muestra unpatron.
Figura : Espiral de Ulam
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Test de primalidad Miller-Rabin
Dado n un primo mayor a 1 impar del cual queremos saber si esprimo o no. Sea m un valor impar tal que n − 1 = 2km y a tal que2 ≤ a ≤ n − 2, Cuando se cumple:
am ≡ ±1 mod n
o
a2rm ≡ −1 mod n
Para al menos un r entero tal que 1 ≤ r ≤ k − 1, se considera quen es un probable primo; en caso contrario n no puede ser primo.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Generador de primos aleatorios
Este algoritmo es una implementacion propia y hace uso delgenerador de aleatorios URAND del sistema operativo GNU/Linux.
1 Parsear a un entero el valor aleatorio obtenido de /dev/urandy almacenarlo en A.
2 Calcular
(A mod (END − START )) + START
donde END y START es el mayor y menor numero que sealmacena en la cantidad de bits indicada.
3 Sumar en una unidad A.
4 Enviar A al test de primalidad de Miller-Rabin.
5 Si A es compuesto regresar al paso 3.
6 Retornar A.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Pollard P-1
El algoritmo fue desarollado por J. M. Pollard en los 70, elmetodo basicamente usa alguna informacion acerca del ordende un elemento en el grupo Zp para encontrar un factor p deN
El Algoritmo hace uso del Teorema de Fermat el cual indica,Dado un primo p y un a ∈ Z tal que p - a entonces ap−1 ≡ 1mod p.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Pollard P-1
1 Seleccionar un limite superior para B (Usualmente 105 y 106)
2 Calcular m = lcm(B), Puede ser calculado mediante lamultiplicatoria de los primos generados mediante la Criba deEratostenes.
3 Seleccionar un entero aleatorio positivo entre 1 y n
4 Calcular d = gcd(a, n).Si d 6= 1, retornar d . (Este es un factor no trivial de n)
5 Calcular am mod n
6 Calcular e = gcd(am − 1, n)Si e = 1, ir a 1 e incrementar B.Si e = n, ir a 3 y cambiar a.Si e 6= 1 y e 6= n, retornar d . (Este es un factor no trivial de n)
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
El metodo original del rsaAlgoritmo de Williams/SchmidAlgoritmo de Gordon
Descripcion
El algoritmo planteado en el articulo original de RSA, tiene lacaracteristica de encontrar un numero P ′′ primo el cual sera elmenor factor de (P ′ − 1) que sera el menor factor de (P − 1).
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
El metodo original del rsaAlgoritmo de Williams/SchmidAlgoritmo de Gordon
Algoritmo
1 Encontrar un primo P ′′ con un tamano de bits elegido.
2 Calcular P ′ = A′′P ′′ + 1Para algun entero A′′, el cual debe ser encontrado probandolos valores {2, 4, 6, 8, ...}.
3 Calcular P = A′P ′ + 1A′ se obtiene de manera similar a A′′.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
El metodo original del rsaAlgoritmo de Williams/SchmidAlgoritmo de Gordon
Descripcion
En 1979, Williams y Schmid propusieron el siguiente algoritmo, esefectivo y altamente recomendado para generar primos fuertes.Este tambien calcula P+
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
El metodo original del rsaAlgoritmo de Williams/SchmidAlgoritmo de Gordon
Algoritmo
1 Encontrar dos primos P ′′ y P+ del tamano de bits elegido.
2 Calcular R = −(P ′′)−1 mod P+
Por tanto 0 < R < P+, La inversa de P ′′ en modulo P+ puedeser calculada mediante el algoritmo extendido de Euclides.
3 Encontrar el menor A tal que
P ′ = 2AP ′′P+ + 2RP ′′ + 1, y
P = 4AP ′′P+ + 4RP ′′ + 3
O encontrado P ′
P = 2P ′ + 1
Hasta que sean primos.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
El metodo original del rsaAlgoritmo de Williams/SchmidAlgoritmo de Gordon
Descripcion
En 1984, John Gordon propuso un nuevo algoritmo para generarprimos fuertes, este es un poco mas eficiente que el deWilliams/Schmid, debido a que no necesita calcular un P ′ fuerte.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
El metodo original del rsaAlgoritmo de Williams/SchmidAlgoritmo de Gordon
Algoritmo
1 Encontrar dos primos P ′′ y P+ del tamano de bits elegido.
2 Calcular el menor primo de la forma P ′ = A′′P ′′ + 1 paraalgun entero A′′
3 DejarP0 = ((P+)P
′−1 − (P ′)P+−1)(P ′P+)
Notar que esto por el teorema de Fermat implicaria queP0 ≡ 1 (mod P ′) y P0 ≡ −1 (mod p+)
4 Calcular el menor primo P de la siguiente manera
P = P0 + AP ′P+
para algun entero A.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Hardware usado
CPU: AMD A8-5545M APU with Radeon(tm) HD GraphicsNumero de nucleos: 4Velocidad del reloj: 1.7 GHz (Sin Overclocking)Cache L2: 4 MB
Memoria Ram: 6GB
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Metodologia usada
Es importante mencionar que el proceso se realizo en un solonucleo y no de manera paralela.
Los calculos se realizaron generando numeros de diferentestamanos de bits: 64, 128, 256, 512, 1024, 2048.
Para tener una mayor precision en el calculo, se genero 100numeros por cada generador y tamano de bits, luego de estose calculo la media aritmetica del tiempo total.
Para obtener una medida mas exacta el metodo de evaluacionse utilizara la funcion gettimeofday() que en Linux brinda laprecision de 10µs.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Tabla de tiempo de generacion
N. Bits No fuerte A. en RSA Williams Gordon’s
64b 0.0359229 0.161156 0.175932 0.118902128b 0.112868 0.238891 0.339435 0.282909256b 0.225215 0.535283 0.553583 0.515051512b 0.261919 0.881877 0.937849 0.907238
1024b 1.03088 2.69978 2.39081 4.003942048b 2.13455 12.6628 20.5621 17.402
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Grafica de tiempo de generacion
5
6
7
8
9
10
11
Time
Bit
s2x
No fuerteRSA Method
Williams/SchmidGordon’s
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa
IntroduccionGeneradores de primos fuertes
ComparativasConclusiones
Conclusiones
Debido a que de la fortaleza de los primos escogidos dependeuna mayor seguridad del sistema criptografico usado, esaltamente recomendable la utilizacion de alguno de losmetodos de generacion de primos indicados anteriormente.
Como se observa en las comparativas la generacion de primosno fuertes es mucho mas rapida, pero no cuentan con lasfortalezas indicadas. Tambien se observa que el Algoritmo deWilliams/Schmid es mas eficiente que el de Gordon y quecuenta con una fortaleza mayor que los otros algoritmosexpuestos.
Juan Alfredo Salas Santillana Generacion de numeros primos fuertes para criptografıa