View
55
Download
3
Category
Preview:
Citation preview
OutlineTeorıa de NumerosProblemas basicos
CRIPTOGRAFIA DE CLAVE PUBLICA:ANTECEDENTES MATEMATICOS
Juan Manuel Garcıa Garcıa
29 de septiembre de 2010
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
Teorıa de NumerosEnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Problemas basicosProblema de la factorizacion de enterosProblema del logaritmo discreto
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Enteros
I El conjunto de enteros {. . . ,−3,−2,−1, 0, 1, 2, 3, . . . } esdenotado por el sımbolo Z.
I Sean a y b enteros. Entonces a divide a b si existe un entero ctal que b = ac. Si a divide a b es denotado por a|b.
I Si a y b son enteros con b ≥ 1 entonces la division ordinaria dea entre b nos da enteros q (cociente) y r (residuo) tales que
a = q · b + r
donde 0 ≤ r < b.
I El residuo de la division es denotado como a mod b y elcociente como a div b.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
I Un entero c es un denominador comun de los enteros a y b sic |a y c |b.
I Un entero no negativo d es el maximo comun denominador delos enteros a y b, denotado como gcd(a, b), si
1. d es un comun denominador de a y b2. siempre que c |a y c |b, entonces c |d
I Un entero no negativo d es el mınimo comun multiplo de losenteros a y b, denotado como lcm(a, b), si
1. a|d y b|d2. siempre que a|c y b|c , entonces d |c .
I Si a y b son enteros positivos, entonceslcm(a, b) = a · b/ gcd(a, b).
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Ejemplos
1. ¿Cual es el gcd(15, 10)?
2. ¿Cual es el lcm(15, 10)?
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Numeros primos
I Se dice que dos enteros a y b son primos relativos o coprimossi gcd(a, b) = 1.
I Se dice que un entero p ≥ 2 es primo si sus unicos divisorespositivos son 1 y p.
I (Teorema fundamental de la aritmetica) Todo entero n ≥ 2tiene una factorizacion unica como un producto de potenciasde primos:
n = pe11 pe2
2 . . . pekk
donde los pi son primos distintos y los ei son enteros positivos.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Funcion φ de Euler
I Para n ≥ 1, sea φ(n) el numero de enteros en el intervalo[1, n] que son primos relativos a n. La funcion φ esdenominada la funcion phi de Euler.
1. Si p es primo, entonces φ(p) = p − 1.2. Si gcd(m, n) = 1, entonces φ(m · n) = φ(m) · φ(n).
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Ejemplos
1. ¿Cual es el valor de φ(15)?
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Algoritmo de Euclides
Input: Dos enteros no negativos a y b con a ≥ b.Output: Maximo comun denominador de a y b.while b 6= 0 do
r ← a mod b;a← b; b ← r ;
endreturn a
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Algoritmo extendido de Euclides
Input: Dos enteros no negativos a y b con a ≥ b.Output: d = gcd(a, b) y enteros x ,y que satisfacen ax + by = d .if b=0 then
d ← a; x ← 1; y ← 0; return (d,x,y);endx2 ← 1; x1 ← 0; y2 ← 0; y1 ← 1;while b > 0 do
q ← ba/bc; r ← a− qb; x ← x2 − qx1; y ← y2 − qy1;a← b; b ← r ; x2 ← x1; x1 ← x ; y2 ← y1; y1 ← y ;
endd ← a; x ← x2; y ← y2;return (d,x,y)
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Congruencias modulares
Sea n un entero positivo.
I Si a y b son enteros, entonces se dice que a es congruente conb modulo n, escrito como a ≡ b (mod n), si n divide a(a− b).
I Ejemplo: 24 ≡ 9 (mod 5), dado que 24− 9 = 3 · 5.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Enteros modulo n
I Los enteros modulo n, denotados como Zn, es el conjunto deenteros {0, 1, 2, . . . , n − 1} donde la suma, resta ymultiplicacion en Zn se realizan modulo n.
I Sea a ∈ Zn. El inverso multiplicativo de a modulo n es unentero x ∈ Zn tal que a · x ≡ 1 (mod n). Si tal x existe esunica, se denota por a−1, y se dice que a es invertible.
I Sean a, b ∈ Zn. La division de a entre b modulo n es elproducto de a por b−1 modulo n, y esta definida solo si b esinvertible modulo n.
I Sea a ∈ Zn. Entonces a es invertible si y solo si gcd(a, n) = 1.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
El grupo multiplicativo de Zn es
Z∗n = {a ∈ Zn| gcd(a, n) = 1}.
En particular, si n es primo, entonces Z∗n = {a|1 ≤ a ≤ n − 1}.
I Teorema de Euler. Si a ∈ Z∗n, entonces aφ(n) ≡ 1 (mod n).
I Teorema de Fermat. Sea p un primo. Si gcd(a, p) = 1,entonces ap−1 ≡ 1 (mod p).
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Generadores de Z∗n
I Sea a ∈ Z∗n. El orden de a es el mınimo entero positivo t tal
que at ≡ 1 (mod n).
I Sea α ∈ Z∗n. Si el orden de α es φ(n), entonces se dice que α
es un generador de Z∗n.
I Si α es un generador entonces
Z∗n = {αi mod n|0 ≤ i ≤ φ(n)− 1}.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
EnterosNumeros primosAlgoritmos en enterosEnteros modulo nGrupo multiplicativo
Ejemplos
1. Z23 = {0, 1, 2, . . . , 22}.2. El inverso multiplicativo de 7 es 7−1 = 10.
3. ¿Cual es el inverso multiplicativo de 5?
4. Z∗23 = {1, 2, . . . , 22}.
5. 722 = 1 (mod 23)
6. 7 es un generador de Z∗23
7. 70 = 1, 71 = 7, 72 = 3, 73 = 21, 74 = 9, 75 = 17, 76 = 4,77 = 5, 78 = 12, 79 = 15, 710 = 13,...
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
Problema de la factorizacion de enterosProblema del logaritmo discreto
Problema de la factorizacion de enteros
El problema de la factorizacion de enteros es el siguiente:Dado un entero n, encontrar sus factores primos, esto es, hacer lafactorizacion
n = pe11 pe2
2 . . . pekk
donde los pi son primos distintos y cada ei ≥ 1.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
Problema de la factorizacion de enterosProblema del logaritmo discreto
Division de prueba
I Aplicar divisiones de prueba con primos pequenos hastaalguna cota b.
I Como caso extremo. se pueden intentar todos los primoshasta
√n.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
Problema de la factorizacion de enterosProblema del logaritmo discreto
Algoritmo de factorizacion ρ de Pollard
Input: Un entero compuesto n.Output: Un factor no trivial d de n.a← 2; b ← 2;for i = 1, 2, . . . do
a← a2 + 1 mod n; b ← b2 + 1 mod n; b ← b2 + 1 mod n;d ← gcd(a− b, n);if 1 < d < n then return d ;if d = n then Terminar algoritmo con fracaso.
end
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
Problema de la factorizacion de enterosProblema del logaritmo discreto
Records de factorizacion
I RSA-200 Challenge: 200 dıgitos decimales (663 bits).Factorizado entre diciembre de 2003 y mayo de 2005, usandoun cluster de 80 procesadores Opteron, BSI, Alemania.
I RSA-768 Challenge: 768 bits. Factorizado el 12 de diciembrede 2009, usando el equivalente a 2000 anos de computo deuna AMD Opteron de 2.2 GHz.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
Problema de la factorizacion de enterosProblema del logaritmo discreto
Problema del logaritmo discreto
El problema del logaritmo discreto (DLP) es el siguiente:Dado un primo p, un generador α de Z∗
p y un elemento β ∈ Z∗p
encontrar un entero x , 0 ≤ x ≤ p − 2, tal que
αx ≡ β (mod p).
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
Problema de la factorizacion de enterosProblema del logaritmo discreto
Busqueda exhaustiva
El algoritmo mas obvio para resolver el DLP es calcularsucesivamente α0, α1, α2,..., hasta obtener β.Este metodo toma O(n) multiplicaciones, donde n es el orden deα, y es por tanto muy ineficiente si n es grande.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
OutlineTeorıa de NumerosProblemas basicos
Problema de la factorizacion de enterosProblema del logaritmo discreto
Ejercicios:
1. Factorizar los enteros 4284179, 26164807, 61763557 y829348951.
2. Dado el grupo multiplicativo Zp donde p = 7919 y elgenerador es g = 7, encontrar los logaritmos dicretos de 9,1548 y 2367.
Juan Manuel Garcıa Garcıa CRIPTOGRAFIA DE CLAVE PUBLICA: ANTECEDENTES MATEMATICOS
Recommended