Download Sistemas basados en la Teoría de Números - DSIC

Criptografía de clave pública
Sistemas basados en la Teoría de Números
Departamento de Sistemas Informáticos y Computación
DSIC - UPV
http://www.dsic.upv.es
– p.1/20
Criptografı́a de clave pública
Sistemas basados en la Teoría de Números
• Cifrado exponencial de clave pública
• El sistema RSA
• Implementación de RSA. Exponenciación modular
• Implementación de RSA. Test de primalidad
• Residuos cuadráticos. El sistema de Rabin
• Logaritmos discretos. El sistema de ElGamal
DSIC - UPV
http://www.dsic.upv.es
– p.2/20
Cifrado exponencial de clave pública
Fundamentos matemáticos
• Teorema de Lagrange: Sea (G, ⊕) un grupo finito y (G0 , ⊕) un
subgrupo de (G, ⊕), entonces card(G0 )|card(G)
• Dado (G, ⊕) un grupo finito y a ∈ G, siendo a(k) = a ⊕ a ⊕ . . . ⊕ a,
{z
}
|
con < a > denotamos el subgrupo generado por a
< a >= {a(i) : i ≥ 1}
k
• Se define el orden de un elemento a ∈ G (ord(a)) como el menor
t > 0 tal que a(t) = e
• Teorema: Para cualquier grupo finito (G, ⊕) y a ∈ G se cumple
que ord(a) = card(< a >)
• Corolario: Dado a ∈ (G, ⊕) con ord(a) = t, entonces se cumple
que a(i) = a(j) ↔ i ≡ j (mod t)
Es consistente con el corolario definir a(0) = e y a(i) = a(i mod t) ,
para todo i ≥ 0
DSIC - UPV
http://www.dsic.upv.es
– p.3/20
Cifrado exponencial de clave pública
Fundamentos matemáticos
• Corolario: Si (G, ⊕) es un grupo finito con identidad e, entonces,
para todo a ∈ G se cumple que a(|G|) = e
Denotamos con Z∗n el grupo multiplicativo de los elementos invertibles
de Zn (recordatorio: |Z∗n | = φ(n))
• Teorema de Euler: ∀n ≥ 1, ∀a ∈ Z∗n : aφ(n) = e
• Teorema de Fermat: ∀p primo, ∀a ∈ Z∗p : ap−1 ≡ 1 (mod p)
Consecuencia: Z∗p = Zp − {0}, por lo tanto ap ≡ a (mod p)
• Dado a ∈ Z∗n , si ord(a) = card(Z∗n ) entonces < a >= Z∗n y
llamamos al grupo Z∗n cíclico
• Teorema: Z∗n es cíclico para los valores de n = {2, 4, pe , 2pe },
donde p es primo impar y e un entero positivo
• Teorema: Si p es primo impar y e ≥ 1, entonces x2 ≡ 1 (mod pe )
tiene como soluciones 1 y −1
DSIC - UPV
http://www.dsic.upv.es
– p.4/20
Cifrado exponencial de clave pública
Fundamentos matemáticos
• Teorema Chino del resto: Sean n1 , n2 , . . . , nk primos dos a dos,
entonces el conjunto de ecuaciones:
x ≡ ai
(mod ni )
tiene una única solución modulo n = n1 n2 . . . nk


(mcd(mi , ni ) = 1
k
mi = n/ni
X
x=
ai mi yi donde
mi ≡ 0 (mod nj ), i 6= j)

y = m−1 mod n
i=1
i
i
i
• Corolario: Sean n1 , n2 , . . . , nk primos dos a dos, sea
n = n1 n2 . . . nk , entonces:
x ≡ a (mod ni ) : i = 1..k ⇐⇒ x ≡ a (mod n)
DSIC - UPV
http://www.dsic.upv.es
– p.5/20
El sistema RSA
• Generación de claves
1. Seleccionar aleatoriamente dos números primos p y q
grandes (del orden de 100 cifras c.u.)
2. n = pq
3. Seleccionar un número impar e tal que mcd(e, φ(n)) = 1
4. Calcular d = e−1 mod φ(n)
5. Clave pública: (n, e); Clave privada: (d, p, q)
• Cifrado
◦ El dominio es Zn , para todo x ∈ Zn , ekpb (x) = xe mod n
• Descifrado
◦ Dado y ∈ Zn , dkpr (y) = y d mod n
La seguridad de RSA recae en el problema de factorizar un número.
No abordable si n tiene más de 200 cifras
DSIC - UPV
http://www.dsic.upv.es
– p.6/20
Implementación de RSA
Exponenciación modular
• Potencia módulo n por cuadrados sucesivos: Se basa en:
a2c mod n = (ac )2 mod n
a2c+1 mod n = ((ac )2 a) mod n
ExpModular(a,b,n)
c = 0;
d = 1;
< b1 , b2 , . . . , bk > representación binária de b
for(i = k; i ≥ 0; i − −){
c = 2c;
d = (dd) mod n;
if (bi == 1){
c + +;
d = (da) mod n;
}
}
devolver(d);
DSIC - UPV
http://www.dsic.upv.es
– p.7/20
Implementación de RSA
Densidad de números primos:
• π(n): no de números primos menores que n (π(10) = 4)
π(n)
x→∞ n/ ln n
• π(n) aproximado por lim
= 1, así, π(n) ≈ n/ ln n
• Números de 100 cifras comprendidos en el intervalo [1099 , 10100 ]
• Si n ∈ [1099 , 10100 ], entonces: π(n) ≈
10100
ln 10100
−
1099
ln 1099
• Si n ∈ [1099 , 10100 ], entonces el número de enteros impares es:
10100 −1099
2
• La probabilidad de que un impar en el intervalo [1099 , 10100 ] sea
primo es: 0.00868
• el promedio de extracciones para obtener un número primo:
1
0.00868 ≈ 115
DSIC - UPV
http://www.dsic.upv.es
– p.8/20
Implementación de RSA
Test de primalidad
• Dividir n por 2, 3, . . . , bn1/2 c, si no obtenemos divisor, entonces n
es primo
n decimal → β = blog nc no de bits
El número de divisiones se aproxima a 10β/2
Coste exponencial con la longitud en número de bits de n
DSIC - UPV
http://www.dsic.upv.es
– p.9/20
Implementación de RSA
Pseudoprimalidad (I)
• Fermat: si n primo, entonces ∀a ∈ Z∗n : an−1 ≡ 1 (mod p)
Si ∃a ∈ Z∗n tal que no lo cumpla, entonces n es compuesto
Aproximación: probar con a = 2
Pseudoprimo(n)
if (ExpModular(2, n − 1, n)6= 1){
devolver(F also); /* seguro compuesto
else
devolver(Cierto); /* prob. primo */
*/
n < 10000: El test falla para 22 valores (341,561,645,1105,...)
n ≈ 1050 : probabilidad de fallo en el test: 10−6
n ≈ 10100 : probabilidad de fallo en el test: 10−13
• El fallo no se elimina probando con más valores en Z∗n
• no s de Charmichael: no s compuestos psudoprimos para todo
valor en Z∗n (561,1105,1729, ...). Sólo hay 255 no s de
Charmichael menores que 108
DSIC - UPV
http://www.dsic.upv.es
– p.10/20
Implementación de RSA
Pseudoprimalidad (II)
• Teorema: Si p es primo impar y e ≥ 1, entonces x2 ≡ 1 (mod pe )
tiene como soluciones 1 y −1
• Corolario: Si existe una raiz no trivial de 1 módulo n, entonces n
es compuesto
• Miller-Rabin: Detecta números primos no detectados por el test
pseudoprimo
◦ Realiza más de una exponenciación modular para valores
aleatorios
◦ Mientras calcula la exponenciación modular, detecta si existe
alguna raiz no trivial de 1 módulo n
• Miller-Rabin detecta no s de Charmichael (p.e: n = 561, a = 7:
a280 = 67 (mod n) y a560 = 1 (mod n)
DSIC - UPV
http://www.dsic.upv.es
– p.11/20
Implementación de RSA
• Algoritmos:
Miller-Rabin(n,s)
for(i = 1;
}
i ≤ s; i + +){
a = rand(1, n − 1);
if(Testigo(a,n)) devolver(F also); /* compuesto */
devolver(Cierto);
/* muy prob. primo */
Testigo(a,
n)
< b1 , b2 , . . . , bk > representación binária de n − 1
for(d = 1,i = k; i ≥ 0; i − −){
x = d;
d = (dd) mod n;
if (d == 1 and x 6= 1 and x 6= −1)
devolver(Cierto); /* por el corolario */
if (bi == 1) d = (da) mod n;
}
if(d 6= 1) devolver(Cierto); /* por el teorema */
devolver(F also);
DSIC - UPV
http://www.dsic.upv.es
– p.12/20
Implementación de RSA
Parámetros del sistema
• La talla del módulo ha de ser de 1024 bits (309 cifras decimales)
• Longitud de p y q similares (512 bits)
• La diferencia entre p y q ha de ser grande (podrían buscarse
alrededorde la raiz del módulo)
• p y q han de ser primos seguros
◦ (p − 1) y (q − 1) con factores primos grandes
◦ mcd(p − 1, q − 1) pequeño
• Normalmente, escoger un valor primo grande r tal que p = 2r + 1
y q = 2p + 1 sean primos
• Ataques:
◦ Factorizar n
◦ Calcular φ(n) y resolver
DSIC - UPV
(
n = pq
φ(n) = (p − 1)(q − 1)
http://www.dsic.upv.es
– p.13/20
El sistema de Rabin
Residuos cuadráticos y raices cuadradas módulo n
• Se dice que a es un residuo cuadrático módulo n si existe algún x
tal que x2 ≡ a (mod n). Un tal x es una raiz cuadrada de a
módulo n
• El problema de calcular raices cuadradas módulo n es difícil si n
es compuesto y se desconoce su descomposición en factores
primos
La seguridad del sistema de Rabin recae en el problema de factorizar
un número. No abordable si n tiene más de 200 cifras
DSIC - UPV
http://www.dsic.upv.es
– p.14/20
El sistema de Rabin
• Generación de claves
1. Seleccionar aleatoriamente dos números primos p y q
grandes de talla similar y tales que p ≡ q ≡ 4 (mod 4)
2. n = pq
3. Clave pública: n; Clave privada: (p, q)
• Cifrado
◦ El dominio es Zn , para todo x ∈ Zn , ekp (x) = x2 mod n
• Descifrado
◦ Dado y ∈ Zn , obtener las 4 raices módulo n. Una de ellas
corresponde a x
DSIC - UPV
http://www.dsic.upv.es
– p.15/20
Implementación del sistema de Rabin
Cálculo de las raices cuadradas de c módulo n = pq cuando p ≡ q ≡ 3
(mod 4)
/* mcd(p, q) = 1 */
1. Utilizar el algoritmo de Euclides extendido para obtener a y b tales
que ap + bq = 1
2. Calcular r = c(p+1)/4 mod p
3. Calcular s = c(q+1)/4 mod q
4. Calcular m1 = (aps + bqr) mod n
5. Calcular m2 = (aps − bqr) mod n
Las cuatro raices de c son m1 , −m1 mod n, m2 y −m2 mod n,
DSIC - UPV
http://www.dsic.upv.es
– p.16/20
El sistema de Rabin
Ejemplo:
Sea n = 77 (p = 7, q = 11) y el mensaje x = 9 (y = x2 mod 77 = 4)
1. (Alg. de Euclides extendido) ap + bq = 1 ⇒ a = −3 y b = 2
2. r = 4(7+1)/4 mod 7 = 42 mod 7 = 2
3. s = 4(11+1)/4 mod 11 = 43 mod 11 = 9
4. m1 = (aps + bqr) mod 77 = −189 + 44 mod 77 = 9
5. m2 = (aps − bqr) mod 77 = −189 − 44 mod 77 = 75

m1 = 9 ⇐=



m = 75
2
La solución está entre:

−m1 mod 77 = 68



−m2 mod 77 = 2
DSIC - UPV
http://www.dsic.upv.es
– p.17/20
El sistema de ElGamal
Logaritmos discretos
• Sea G un grupo cíclico de orden n y α un generador de G.
Para β ∈ G, el logaritmo discreto de β en base α (log α β) es el
único entero x ∈ Zn tal que αx = β
ejemplo: log5 35 = 32 en Z∗97 , ya que 532 ≡ 35 (mod 97)
• Si p es primo, entonces Z∗p = Zp − {0} es un grupo cíclico
El problema del logaritmo discreto: Dado un número primo p, un
generador α de Z∗p y β ∈ Z∗p , encontrar un entero x tal que αx ≡ β
(mod p)
DSIC - UPV
http://www.dsic.upv.es
– p.18/20
El sistema de ElGamal
• Generación de claves
1. Escoger un número primo p, un generador α de Z∗p y un
número 0 < a < p − 2
2. Computar β = αa mod p
3. Clave pública: (α, β, p); Clave privada: a
• Cifrado
◦ El dominio es x ∈ Zp
◦ Escoger un número aleatorio k ∈ Zp−1
◦ Computar y1 = αk mod p y y2 = xβ mod p
◦ e(x) = (y1 , y2 )
• Descifrado
◦ d(y1 , y2 ) = y2 (y1a )−1 mod p
DSIC - UPV
http://www.dsic.upv.es
– p.19/20
Implementación del sistema de ElGamal
El mensaje se oculta multiplicandolo por β k . El valor αk se comunica,
permitiendo recuperar β k si se conoce la clave privada (a).
Ejemplo:
Generación de claves:
Sea p = 2579, α = 2, a = 765 y β = 2765 mod 2579 = 949; El valor de a
permanece secreto.
Cifrado:
Sea x = 1299; se escoge aleatoriamente un valor k (p.e. 853)
e(x) = (2853 mod 2579, 1299 · 949853 mod 2579) = (435, 2396)
Descifrado:
d(435, 2396) = 2396(453765 )−1 mod 2579 = 1299
DSIC - UPV
http://www.dsic.upv.es
– p.20/20