Fundamentos matemáticos del método RSA

Fundamentos matemáticos del método RSA – Hugo D.Scolnik Abril 2004.

1

Fundamentos matemáticos del método RSA

Dr.Hugo D.Scolnik Profesor Titular Regular

Departamento de Computación Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires


2

Nociones elementales de teoría de números: Usaremos la notación b/a (b divide a a) para significar que a = kb para algún entero k. Diremos que a es un múltiplo de b. Todo entero divide a 0. Si b no divide a a escribiremos b//a. Si b/a y b>0 diremos que b es un divisor de a. Todo entero a es divisible por 1 y a (se los llama divisores triviales). A los divisores no triviales de un entero (si existen) se los denomina factores. Números primos y compuestos Un entero a > 1 tal que sus únicos divisores son 1 y a se denomina primo. Ejercicio: demostrar que hay infinitos números primos. Los enteros que no son primos se denominan compuestos. El número 1 no es ni primo ni compuesto (lo mismo sucede con el 0 y los enteros negativos). El teorema de la división, restos y la equivalencia modular Dado un entero n, el conjunto Z de todos los enteros puede particionarse en dos subconjuntos: los que son múltiplos de n y los que no lo son. Gran parte de la teoría de números se basa en el refinamiento de esta partición obtenida clasificando a los enteros que no son múltiplos de n de acuerdo con el resto que se obtiene al dividirlos por n. Teorema 1 (de la división): Para cualquier entero a y cualquier entero positivo n existen enteros únicos q y r tales que 0≤ r <n y a = qn + r


3

Dado un número real x se define a la función parte entera [x] como al mayor entero que no supera a x. El valor q =[a/n] es el cociente de la división. El valor r = a mod n es el resto (o residuo) de la división. Por lo tanto, n/a si y solo si a mod n = 0. Por lo tanto, a = [a/n]n + (a mod n) (1) o a mod n = a – [a/n]n (2) Si a mod n = b mod n escribimos a ≡ b (mod n). Se dice en este caso que a es equivalente a b módulo n. Equivalentemente a ≡ b (mod n) si y solo si n / (b-a) . Escribiremos a ≈ b si a no es equivalente a b módulo n. Como a ≡ b (mod n) es una noción de equivalencia, el conjunto Z se particiona en n clases de equivalencia de acuerdo con sus restos al dividirlos por n. La clase de equivalencia módulo n que contiene a un entero a es:

[a]n = {a + kn : k∈Z}

Escribir entonces a∈[b]n equivale a a ≡ b (mod n). El conjunto de todas esas clases de equivalencia es Zn = {[a]n : 0 ≤ a ≤ n-1} (3) En general se usa la definición: Zn ={0,1,...,n-1} (4) que debe leerse como equivalente a (3) entendiendo que 0 representa [0]n, 1 representa [1]n, etc. Naturalmente hay que tener en cuenta a las clases de equivalencia subyacentes. Por ejemplo, una referencia a –1 en Zn debe entenderse como una referencia a [n-1]n dado que –1 ≡ n – 1 mod n.

Divisores comunes y máxmo común divisor (MCD) Si d es un divisor de a y también un divisor de b, entonces diremos que d es un divisor común de a y b. Por ejemplo, los divisores de 30 son: 1,2,3,5,6,10,15,y 30, así que los divisores comunes de 24 y 30 son 1,2,3, y 6. Una propiedad importante de los divisores comunes es que:


4

d / a y d / b implica d / (a +b) y d / (a – b) (5) Mas generalmente, tenemos que d / a y d / b implica d / (ax + by) (6) para cualquier par de enteros x,y. También, si a / b entonces a≤ b o b =0 ⇒ a / b y b / a ⇒ a = ± b (7) El máximo común divisor de dos enteros a y b que no son simultáneamente nulos es el mayor de sus divisores comunes, y se denota por MCD(a,b). Por ejemplo, MCD(24,30)=6, MCD(3,5)=1, MCD(0,9)=9. Si ab ≠ 0 entonces 1 ≤ MCD(a,b) ≤ min(a,b). Definimos MCD(0,0)=0 para tornar estándar las propiedades de la función MCD (ver (11) mas abajo) Propiedades de la función MCD: MCD (a,b) = MCD (b,a) (8) MCD (a,b) = MCD ( -a,b) (9) MCD (a,b) = MCD (a,b) (10) MCD (a,0) = a (11) MCD (a,ka) = a para cualquier k∈Z (12) Teorema 2: si a y b son enteros no simultáneamente nulos, entonces MCD (a,b) es el menor elemento positivo del conjunto {ax + by: x,y∈Z} de combinaciones lineales de a y b. Demostración: sea s el menor elemento positivo de dichas combinaciones. Por lo tanto, sea s = ax + by para algun x,y∈Z. Sea q=[a/s] . La ecuación (2) implica que a mod s = a – qs = a – q(ax + by) = a(1 – qx) + b(-qy) y por lo tanto a mod s también es una combinación lineal de a y b. Pero como a mod s < s tenemos que a mod s = 0 porque s era la menor combinación positiva de ese tipo. Por lo tanto, s / a y por un razonamiento similar s / b. O sea que s es un divisor común de a y b, y por lo tanto MCD (a,b)≥ s. La ecuación (6) implica que MCD (a,b) / s porque MCD (a,b) divide a a y b, y s es una combinación lineal de ambos. Pero MCD (a,b) / s y s > 0 lo que implica que MCD (a,b)≤ s. Por lo tanto MCD (a,b) = s. Corolario 2.1: Para cualquier par de enteros a y b si d /a y d / b entonces d / MCD (a,b)


5

Demostración: resulta de (6) porque MCD (a,b) es una combinación lineal de a y b por el Teorema 2. Corolario 2.2: Para cualquier par de enteros a y b y cualquier entero positivo n, MCD (an,bn) = nMCD (a,b)

Demostración: Si n = 0 el resultado es trivial. Si n > 0 entonces MCD (an,bn) es el menor entero positivo del conjunto {anx + bny} el cual es n veces el menor entero positivo del conjunto {ax + by}. Ejercicio: demostrar el siguiente Corolario 2.3: Para todos los enteros positivos n, a y b , si n / ab y MCD (a,n) = 1, entonces n / b. Primos relativos Dos enteros a, b se dice que son primos relativos si MCD (a,b) = 1. El siguiente teorema establece que si dos enteros son primos relativos con otro entero p, entonces su producto es primo relativo con p. Teorema 3: Para enteros cualesquiera a,b y p, si MCD (a,p) = 1 y MCD (b,p) = 1 , entonces MCD (ab,p) = 1. Demostración: Del Teorema 2 surge que existen enteros w,x,y,z tales que aw + px = 1 by + pz = 1 Multiplicando estas ecuaciones resulta ab(wy) + p(xby + zaw + pxz) = 1 Factorización única

Un hecho elemental pero importante acerca de la divisibilidad por primos es el siguiente Teorema 4: Para cualquier primo p y todos los enteros a,b , si p / ab entonces p / a o p / b.


6

Demostración: Supongamos que p / ab pero p // a y p // b. Por lo tanto, MCD (a,p) = 1 y MCD (b,p) = 1 puesto que los únicos divisores de p son 1 y p, y por hipótesis p no divide ni a a ni a b. El Teorema 3 implica que MCD (ab,p) = 1, lo que contradice la suposición de que p / ab puesto que p / ab implica MCD (ab,p) = p. Esta contradicción completa la demostración. Una consecuencia del Teorema 4 es que un entero tiene una única factorización en números primos. Ejercicio: demostrar el Teorema 5 (de la factorización única): un entero compuesto n puede escribirse de modo único como un producto de la forma n = p1

e1...pkek donde los pi son primos tales que p1 < p2 < ... < pk y los exponentes

son enteros positivos. El máximo común divisor En esta sección vamos a presentar el algoritmo de Euclides para calcular el MCD de dos enteros en forma eficiente y a analizar su complejidad computacional. Nos vamos a restringir a los enteros positivos (ver (10)). En principio podríamos calcular MCD (a,b) a partir de las factorizaciones en primos de ambos números, o sea:

a = p1

e1...pkek (13)

b = p1

f1...pkfk (14)

donde algunos exponentes pueden ser nulos para que podamos usar el mismo conjunto de primos para a y b. Entonces, MCD(a,b) = p1

min(e1,f1) ... pkmin(ek,fk) (15)

Como veremos luego, los mejores algoritmos para factorizar NO son polinomiales, o sea que el enfoque anterior para calcular MCD (a,b) no puede conducir a un método eficiente.

El algoritmo de Euclides se basa en el siguiente


7

Teorema 6 (de la recursión): para cualquier entero no negativo a y cualquier entero positivo b

MCD (a,b) = MCD (b, a mod b) Demostración: demostraremos que MCD (a,b) y MCD (b, a mod b) se dividen mutuamente, de modo tal que por (7) deben ser iguales dado que ambos son no negativos.

Veamos primero que MCD (a,b) / MCD (b, a mod b). Sea d =MCD(a,b), entonces d / a y d / b. Por (2), a mod b = a – q b donde q = [a/b]. Entonces a mod b es una combinación lineal de a y b y (6) implica que d / a mod b. Entonces, como d / b y d / a mod b, el Corolario 2.3 implica que d / MCD (b, a mod b) o, equivalentemente, que

MCD (a,b) / MCD (b, a mod b) (16) Demostrar que MCD (b, a mod b) / MCD (a,b) es casi lo mismo. Sea d=MCD (b,a mod b), entonces d / b y d / a mod b. Como a = q b + a mod b donde q =[a/b] tenemos que a es una combinación lineal de b y a mod b.

Por (6), concluímos que d / a, y como d / b, resulta que d / MCD (a,b) por el Corolario 2.3 o, equivalentemente, que

MCD (b, a mod b) / MCD (a,b) (17) Usando (7) para combinar las ecuaciones (16) y (17) resulta el teorema. El algoritmo de Euclides El siguiente algoritmo se describe en el libro “Elementos” (aproximadamente 300 años AC) aunque quizás sea anterior.

Sean a y b dos enteros arbitrarios no negativos Procedimiento Euclides (a,b) 1. Si b = 0 2. Entonces devolver a 3. de lo contrario devolver Euclides (b, a mod b) Ejemplo: sea calcular MCD (30,21) Euclides (30,21) = Euclides (21,9) = Euclides (9,3) = Euclides (3,0) = 3


8

O sea, hay tres llamadas recursivas al procedimiento Euclides. La correctitud del algoritmo surge del teorema 6 y del hecho de que si el procedimiento devuelve a en el paso 2, entonces b = 0, de modo tal que (11) implica que MCD (a,b) = MCD (a,0) = a. Notar que no puede ciclar indefinidamente puesto que el segundo argumento decrece estrictamente en cada llamada recursiva. La complejidad del algoritmo de Euclides Analizaremos el peor caso en función de los tamaños de a y b. Supondremos que sin pérdida de generalidad que a > b ≥ 0. Esto se justifica porque si b > a ≥ 0 entonces Euclides (a,b) inmediatamente hace la llamada recursiva Euclides (b,a). O sea que si el primer argumento es menor que el segundo, Euclides “gasta” una llamada recursiva para intercambiar a los mismos. Similarmente si a = b > 0, el procedimiento termina luego de una llamada recursiva puesto que a mod b = 0 El tiempo total de ejecución de Euclides es proporcional al número de llamadas recursivas que hace. Para analizarlo necesitamos los números de Fibonacci definidos por la siguiente recurrencia: F0 = 0 F1 = 1 Fi = Fi-1 + Fi-2 para i ≥ 2

Teorema 7: Si a > b ≥ 0 y el procedimiento Euclides (a,b) realiza k ≥1 llamadas recursivas, entonces a ≥ Fk+2 y b ≥ Fk+

Demostración: Por inducción sobre k. Sea k =1. Entonces b ≥ 1 = F2 y como a > b debe ser a ≥ 2 = F3. Como b > a mod b en cada llamada recursiva el primer argumento es estrictamente mayor que el segundo, o sea que la suposición a > b es válida para cada llamada recursiva. Supongamos que el teorema es cierto para k – 1 llamadas recursivas, y veremos que también lo es para k llamadas. Como k > 0 tenemos que b > 0 y Euclides (a,b) llama a Euclides (b, a mod b) recursivamente y este último hace a su vez k – 1 llamadas recursivas. La hipótesis inductiva implica que b ≥ Fk+1 a mod b ≥ Fk. Tenemos que

b + (a mod b) = b + (a – [a/b]b) ≤ a Como a > b > 0 implica que [a/b] ≥ 1. Por lo tanto a ≥ b + (a mod b) ≥ Fk+1 + Fk = Fk+2


9

Teorema 8 (Lamé): para cualquier entero k ≥ 1, si a > b ≥ 0 y b < Fk+1, entonces la invocación al procedimiento Euclides (a,b) realiza menos de k llamadas recursivas. Podemos mostrar ahora que la cota superior del teorema 8 es la mejor posible. Dos números de Fibonacci consecutivos constituyen el peor caso para el algoritmo de Euclides. Dado que Euclides (F3,F2) hace exactamente una llamada recursiva y como k ≥ 2, tenemos que Fk+1 mod Fk = Fk-1 y MCD(Fk+1,Fk) = MCD (Fk, Fk+1 mod Fk) = MCD (Fk,Fk-1) Por lo tanto el algoritmo Euclides (Fk+1,Fk) hace k –1 llamadas recursivas, llegando a la cota superior del Teorema 8.

El algoritmo de Euclides extendido El objetivo es extender el algoritmo que vimos para calcular coeficientes enteros x,y que satisfagan d = MCD (a,b) = ax + by (18) Notar que x,y pueden ser nulos o negativos. La utilidad de dicho algoritmo será para calcular inversas multiplicativas modulares. El procedimiento extendido tiene como entrada a un par arbitrario de enteros y devuelve una terna (d,x,y) que satisface (18). Procedimiento Euclides extendido (a,b) 1. Si b = 0 2. Retornar con (a,1,0) 3. de lo contrario, (d’,x’,y’) ← Euclides extendido (b,a mod b) 4. (d,x,y) ← (d’,y’,x’ – [a/b] y’) 5. retornar (d,x,y)

Veamos el cálculo de MCD (99,78)

a b [a/b] d x y 99 78 1 3 -11 14 78 21 3 3 3 -11


10

21 15 1 3 -2 3 15 6 2 3 1 -2 6 3 2 3 0 1 3 0 - 3 1 0

El paso 1. equivale al test “ b = 0” en Euclides. Si b = 0, el Euclides extendido devuelve d = a en el paso 2. junto con x = 1, y = 0, o sea que a = ax + by. Si b ≠ 0, el algoritmo calcula (d’,x’,y’) tal que d’ = MCD (b,a mod b) y d’ = bx’ + (a mod b ) y’ (19) Como en Euclides, tenemos en este caso que d = MCD (a,b) = d’ = MCD(b, a mod b). Para obtener x,y tales que d = ax + by comenzamos por reescribir (19) usando d = d’ y la ecuación (2): d = bx’ + (a – [a/b] b) y’ = ay’ + b(x’ – [a/b] y’) De este modo, eligiendo x = y’ , y = x’ – [a/b] y’ se satisface la ecuación d = ax + by, lo que demuestra la correctitud del algoritmo. Dado que el número de llamadas recursivas en los dos algoritmos es igual, los tiempos de procesamiento solo difieren en un factor constante Grupos finitos Un grupo (S,⊕) es un conjunto S con una operación binaria ⊕ para la cual se verifican las siguientes propiedades: 1. Cerrado: Para todo a,b ε S ⇒ a⊕b ε S 2. Identidad: Existe un elemento neutro e ε S tal que a ⊕ e = e ⊕ a = a ∀ a ∈ S 3. Asociatividad:∀ a,b,c ∈ S, (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c) 4. Inversa: ∀ a ∈ S ∃ un único elemento b ∈ S tal que a ⊗ b = b ⊗ a = e Si un grupo satisface la propiedad conmutativa a ⊗ b = b ⊗ a ∀ a,b ∈ S, se dice que es abeliano y si S < ∞ (donde S denota la cardinalidad de S) se dice que el grupo es finito. Podemos formar dos grupos abelianos finitos utilizando la suma y la multiplicación módulo n, donde n es un entero positivo, basados en las clases de equivalencia de los enteros módulo n. Para definir un grupo en Zn necesitamos operaciones


11

binarias convenientes que se obtienen redefiniendo las operaciones ordinarias de suma y multiplicación.Es simple definir las operaciones de suma y multiplicación en Zn porque la clase de equivalencia de dos enteros determina unívocamente la clase de equivalencia de su suma y su producto. Si a ≡ a’ (mod n ) y b ≡ b’ (mod n) entonces a + b ≡ a’ + b’ (mod n) ab ≡ a’b’ (mod n) De este modo definimos la suma y la multiplicación módulo n , denotadas por +n y . n mediante [a]n +n [b]n = [a + b]n [a]n .n [b]n = [ab]n y análogamente la substracción [a]n –n [b]n = [a –b]n Estos hechos justifican la práctica de usar el menor elemento positivo de cada clase de equivalencia como su representante cuando se realizan cálculos en Zn. La suma, la resta y la multiplicación se llevan a cabo como siempre con sus representantes , pero los resultados se expresan con el representante de su clase (o sea x → x mod n ). Usando esta definición de la suma módulo n definimos el grupo aditivo módulo n como (Zn ,+n) recordando que Zn= n. Teorema 12: (Zn ,+n) es un grupo abeliano finito. Demostración: queda como ejercicio. Usando la definición de multiplicación módulo n definimos el grupo multiplicativo módulo n como (Z*n ,.n) donde Z*n denota a los elementos de Zn que son primos relativos con n, o sea Z*n = { [a]n ∈ Zn : MCD(a,n) = 1} Para ver que este conjunto está bien definido notemos que para 0 ≤ a < n resulta que a ≡ (a + kn) (mod n) para todos los enteros k. Es fácil ver entonces que MCD(a,n) = 1 ⇒ MCD(a +kn,n) = 1 para todos los enteros k.. Como [a]n = {a + kn ; k ∈Z} resulta que Z*n está bien definido. Por ejemplo, Z*15 = {1,2,4,7,8,11,13,14}. La multiplicación módulo 15 es la operación del grupo; así 8.11 ≡ 13 (mod 15) y la identidad para este grupo es el 1. Teorema 13: (Z*n ,.n) es un grupo abeliano finito. Vimos en el teorema 6 que para a,b,p enteros tales que


12

MCD (a,p) = MCD (b,p) = 1 entonces MCD (ab,p) =1. Esto implica que (Z*n ,.n) es cerrado. La asociatividad y conmutatividad quedan como ejercicio. Veamos la existencia de inversas: sea a ∈ Z*n, (d,x,y) el resultado del algoritmo Euclides extendido (a,n). Entonces, d =1 porque a ∈ Z*n y ax + ny = 1 resulta que ax ≡ 1 (mod n) o sea que [x]n es una inversa multiplicativa de [a]n mod n (luego veremos que las inversas son únicas). De ahora en adelante vamos a denotar a las clases de equivalencia por sus elementos representativos y a las operaciones simplemente por + y . También las equivalencias módulo n serán interpretadas como ecuaciones en Zn. Por ejemplo. son equivalentes las expresiones: ax ≡ b (mod n) y [a]n .n [x]n = [b]n

También vamos a omitir la explicitación de las operaciones cuando las mismas sean evidentes a partir del contexto. Así (Zn ,+n) será Zn y (Z*n ,.n) será Z*n. La inversa multiplicativa de un elemento a se notará (a-1 mod n). La división en Z*n está definida por la ecuación a/b ≡ ab-1 (mod n). Por ejemplo, en Z*15 tenemos que 7-1 ≡ 13 (mod 15) porque 7.13 = 91 ≡ 1 (mod 15) de modo tal que 4/7 ≡ 4.13 ≡ 7 (mod 15). La cardinalidad de Z*n , o sea Z*nse denota por φ (n), conocida como la función de Euler, que satisface la ecuación φ (n) = n ∏ (1 – 1/p) (20) p<n donde p recorre todos los primos que dividen a n (incluyendo a n si n es primo). Intuitivamente comenzamos con la lista de los restos {0,1,...,n-1} y entonces para cada primo p que divide a n, borramos los múltiplos de p de dicha lista. Por ejemplo, como los divisores primos de 45 son 3 y 5, resulta φ (45) = 45(1 – 1/3)(1 – 1/5) = 45(2/3)(4/5) = 24. Consecuencia importante: si p es primo, Z*p = {1,2,...,p-1} y φ (p)= p-1 Si n es compuesto, entonces φ (n) < n – 1


13

Subgrupos

Si (S , ⊕) es un grupo, S’ ⊆ S, y (S’ ,⊕) también es un grupo, entonces se dice que (S’ ,⊕) es un subgrupo de (S , ⊕). Por ejemplo, los enteros pares forman un subgrupo de los enteros con la operación de suma. El siguiente teorema da una herramienta útil para reconocer subgrupos: Teorema 14 (un subconjunto cerrado de un grupo finito es un subgrupo): Si (S , ⊕) es un grupo finito y S’ es cualquier subconjunto de S tal que si a,b ∈ S’ ⇒ a ⊕ b ∈S’, entonces (S’ , ⊕) es un subgrupo de (S , ⊕). Demostración: queda como ejercicio. Teorema 15 (Lagrange): Si (S’ ,⊕) es un subgrupo de (S , ⊕), entonces S’ es un divisor de S. Un subgrupo S’ de un grupo S se dice propio si S’ ≠ S. El siguiente Corolario es útil en el test de Rabin-Miller para generar números pseudoprimos; Corolario 16: Si S’ es un subgrupo propio de S, S’≤ S/2 Subgrupo generado por un elemento: El teorema 14 da un modo interesante de generar subgrupos de grupos finitos: elegir un elemento a y tomar todos los elementos que puedan obtenerse de él con la operación de grupo. Sea a(k) = a ⊕ a ... ⊕ a (k veces) Por ejemplo, si tomamos a = 2 en Z6 resulta a (1) = 2, a (2) = 4, a (3) = 6 ≡ 0, a (4) = 2, ... En el grupo Zn tenemos que a(k) = ka mod n y en el grupo Z*n es a (k) = a k mod n. El subgrupo generado por a denotado por (a) o (a, ⊕) se define por (a) = { a (k) , k ≥ 1} Decimos que a genera (a) o que a es un generador de (a). Como S es finito, (a) es un subconjunto finito de S. La asociatividad de ⊕ implica que a (i) ⊕ a(j) = a (i+j) . (a) es cerrado, entonces por el Teorema 14 , (a) es un subgrupo de S.


14

Ejemplos: en Z6 (0) = 0, (1) = {0,1,2,3,4,5}, (2) = {0,2,4} El orden de a (en el grupo S) notado ord(a), es el menor i > 0 tal que a (i) = e Teorema 17: Para cualquier grupo finito (S , ⊕) y cualquier a ∈ S, el orden de un elemento es igual a la cardinalidad del subgrupo que genera, o sea ord(a) = (a). Demostración: Sea t = ord(a). Como a (t) = e, y a (t+k) = a(t) ⊕ a(k) = a (k) para k ≥ 1, si i > t entonces a (i) = a (j) para algún j < i. O sea que no aparecen nuevos elementos después de a (t), y (a) = { a (1) , ... , a (t) }. Para demostrar que (a)= t supongamos por contradicción que a (i) = a (j) para i,j satisfaciendo 1 ≤ i < j ≤ t Entonces a (i+k) = a (j+k) para k ≥ 0. Pero esto implica que a (i+ (t-j)) = a (j + (t-j)) = e, una contradicción porque i + (t-j) < t, pero t es el menor entero positivo tal que a (t) = e. Por lo tanto cada elemento de la sucesión a (1) , a (2) , ... , a (t) es distinto, y (a) = t. Corolario 18 : la sucesión a (i) es periódica con período t = ord (a), esto es a (i) = a (j) si y solo si i ≡ j (mod t). Corolario 19 : si (S , ⊕) es un grupo finito con identidad e, entonces ∀ a ∈ S , a (S) = e Demostración: El teorema de Lagrange implica que ord (a) / S, o sea que S ≡ 0 (mod t) , donde t = ord(a) Resolución de ecuaciones modulares: Vamos a considerar ahora la resolución de ecuaciones de la forma ax ≡ b (mod n) donde n > 0 (22) Suponemos que a,b, n son enteros dados y el problema es encontrar x que satisfaga (22) (puede haber 0,1 o varias soluciones). Dado que (a) = {a (x), x > 0} = { ax mod n: x > 0}, la ecuación (22) tiene solución si y solo si b ∈ (a). El teorema de Lagrange nos dice que (a) tiene que ser un divisor de n. El siguiente teorema da una caracterización precisa de (a).


15

Teorema 20: Para cualquier par de enteros positivos a,n, si d = MCD (a,n) entonces (a) = (d) = {0, d, 2d, ..., ((n/d –1)d} (23) y (a) = n/d Demostración: primero veremos que d ∈ (a). El procedimiento Euclides extendido (a,n) calcula enteros x’, y’ tales que d = ax’ + ny’. Por lo tanto, ax’ ≡ d (mod n), de modo tal que d ∈ (a). Entonces, todo múltiplo de d pertenece a (a) porque un múltiplo de un múltiplo de a es un múltiplo de a. O sea que (a) contiene a todo elemento en (d) lo que implica que (d) ⊆ (a). Veremos ahora que (a) ⊆ (d). Si m ∈ (a), entonces m =ax mod n para algún entero x, o sea que m = ax + ny para algún entero y. Sin embargo, d/a y d/n, así que d/m lo que implica que m ∈ (d). Combinando estos resultados resulta que (a) = (d). Para ver que (a)= n/d basta observar que hay exactamente n/d multiplos de d entre 0 y n - 1 inclusive. Corolario 21: La ecuación (22) es resoluble si y solo si MCD (a,n)/b Corolario 22: La ecuación (22) tiene d soluciones distintas módulo n donde d = MCD (a,n) o no tiene soluciones. Demostración: Si x es solución, entonces b ∈ (a). La sucesión ai (mod n) , i = 0 ,1, ... es periódica con período (a)= n/d por el Corolario 18. Si b ∈ (a) , entonces b aparece exactamente d veces en la sucesión ai mod n , i = 0 ,1, ... n - 1 porque los bloques de valores de (a) se repiten d veces cuando i varía entre 0 y n – 1. Los índices x de estas posiciones son las soluciones de la ecuación (22). Teorema 23: sea d = MCD (a,n) y supongamos que d = ax’ + ny’ para un par de enteros x’,y’ (por ejemplo dados por el procedimiento Euclides extendido). Si d/b, entonces (22) tiene como una solución al valor x0 = x’(b/d) mod n. Demostración: como ax’ ≡ d (mod n) tenemos que ax0 ≡ ax’(b/d) (mod n) ≡ d(b/d) (mod n) ≡ b (mod n) y por lo tanto x0 es una solución de ax ≡ b (mod n). Teorema 24: suponiendo que la ecuación ax ≡ b (mod n) es resoluble (esto es, d = MCD(a,n) / b) y que x0 es cualquier solución de la misma. Entonces esta ecuación tiene exactamente d soluciones distintas módulo n dadas por xi = x0 +i(n/d) para i = 1, 2, ... , d – 1.


16

Demostración: dado que n/d > 0 y 0 ≤ i(n/d) < n para i = 0 ,... , d – 1, los valores x0, x1 , ... , xd-1 son todos distintos módulo n. Por la periodicidad de la sucesión ai (mod n) (Corolario 18) si x0 es una solución de ax ≡ b (mod n) entonces todo xi es una solución. Por el Corolario 22 hay exactamente d soluciones de modo tal que ellas son x0, x1 , ... , xd-1 Hasta aquí hemos desarrollado los conceptos matemáticos necesarios para resolver la ecuación ax ≡ b (mod n). El siguiente algoritmo imprime todas las soluciones de la misma, donde a, b son enteros arbitrarios y n es un entero positivo arbitrario. Ecuaciones modulares (a,b,n) 1. (d,x’,y’) ← Euclides extendido (a,n) 2. si d/b 3. entonces x0 ← x’(b/d) mod n 4. para i ← 0, hasta d – 1 5. imprimir (x0 + i(n/d)) mod n 6. de lo contrario imprimir “ no hay soluciones” Sea por ejemplo la ecuación 14x ≡ 30 (mod 100) . llamando al procedimiento Euclides extendido obtenemos (d,x,y) = (2, -7, 1). Como 2/30 se ejecutan los pasos 3-5. En el paso 3 calculamos x0 = (-7)(15) mod 100 = 95. El loop de los pasos 4-5 imprime las dos soluciones 95 y 45. El paso 1 calcula d = MCD(a,n) y los valores x’, y’ tales que d = ax’ + ny’, o sea que x’ es una solución de la ecuación ax’ ≡ d (mod n). Si d//b entonces la ecuación ax ≡ b (mod n) no tiene solución por el Corolario 21. El paso 2 verifica si d/b, y si no el Paso 6 imprime que no hay solución. De lo contrario el Paso 3 calcula una solución x0 de la ecuación (22) de acuerdo con el Teorema 23. Dada una solución, el Teorema 24 establece que las otras d – 1 soluciones pueden ser obtenidas adicionando múltiplos de (n/d)( mod n). Por ello los pasos 4-5 imprimen las d soluciones distintas, comenzando con x0 y sumando (n/d) mod n. Los siguientes corolarios son casos de particular interés para la Criptografía: Corolario 25: para cualquier n > 1 , si MCD(a,n) = 1, entonces la ecuación ax ≡ b (mod n) tiene una única solución módulo n. El caso b =1 es muy importante, pues en ese caso estamos calculando la inversa de a módulo n.


17

Corolario 26: para cualquier n > 1, si MCD (a,n) = 1, la ecuación ax ≡ 1 (mod n) tiene una única solución módulo n. De lo contrario, o sea si MCD (a,n) ≠ 1, no existe ninguna solución. El Corolario 26 nos permite usar la notación (a-1 mod n) cuando a y n son primos relativos. Si MCD (a,n) = 1, entonces una solución de la ecuación ax ≡ 1 (mod n) es el entero x dado por el procedimiento Euclides extendido puesto que la ecuación MCD(a,n) = 1 = ax + ny implica que ax ≡ 1 (mod n). De este modo (a-1 mod n) puede calcularse eficientemente mediante el procedimiento Euclides extendido. El teorema chino del resto: Hace unos 2000 años, el matemático chino Sun-Tsu resolvió el problema de encontrar los enteros x que dan restos 2, 3 y 2 cuando se los divide por 3 ,5 y 7 respectivamente. Una solución es x = 23, y todas las soluciones son de la forma 23 + 105k, con k un entero arbitrario. El “teorema chino del resto” da una correspondencia entre un sistema de ecuaciones módulo un conjunto de números que son relativamente primos dos a dos (por ejemplo, 3 ,5 y 7), y una ecuación módulo su producto (por ejemplo, 105). Este teorema tiene dos aplicaciones principales: Sea el entero n = n1n2 ... nk donde los factores ni son primos relativos entre sí. En primer lugar, este teorema es “estructural”, en el sentido que describe a la estructura de Zn como esencialmente idéntica a la del producto cartesiano n n n1 2 kZ x Z x ... x Z

realizando la suma y la multiplicación de la i-ésima componente módulo ni . En segundo lugar, esta caracterización da lugar a algoritmos muy eficientes puesto que es mejor computar en cada subsistema niZ que hacerlo módulo n.

Teorema 27 (teorema chino del resto): Sea n = n1n2 ... nk donde los factores ni son primos relativos entre sí. Consideremos la correspondencia: a ↔ (a1 , ... , ak) (25) donde a ∈ Zn , ai ∈ niZ y ai = a (mod n)i para i =1 , ... , k.

La correspondencia (25) es una biyección entre Zn y el producto cartesiano n n n1 2 kZ x Z x ... x Z . Las operaciones realizadas en Zn pueden ser realizadas

equivalentemente en las k – uplas con las componentes individuales en el sistema apropiado. Esto es, si a ↔ (a1 , ... , ak) , b ↔ (b1 , ... , bk) entonces (a + b) (mod n) ↔ ((a1 + b1) (mod n1 ), ... , (ak + bk) (mod nk )) (26)


18

(a - b) (mod n) ↔ ((a1 - b1) (mod n1 ), ... , (ak - bk) (mod nk )) (27) (ab) (mod n) ↔ ((a1b1) (mod n1 ), ... , (akbk) (mod nk )) (28) Demostración: La transformación de una representación a otra es inmediata. Ir de a → (a1 , ... , ak) requiere solamente k divisiones. Al revés, o sea a ← (a1 , ... , ak) se realiza mediante la siguiente fórmula: sea mi = n/ni para i = 1 , ... , k. Notar que mi = n1n2 ... ni-1 ni+1 ... nk de modo tal que mi ≡ 0 (mod nj) para i ≠ j. Entonces, definiendo ci = mi (mi

-1 mod ni) para i = 1 , ... , k (29) tenemos que a ≡ (a1c1 + ... + akck) (mod n) (30) La ecuación (29) está bien definida porque mi y ni son relativamente primos (Teorema 6) y por lo tanto el Corolario 26 implica que mi (mi

-1 mod ni) está definido. Para verificar (30) notar que cj ≡ mj ≡ 0 (mod ni) si i ≠ j y que ci ≡ 1 (mod ni). De este modo tenemos la correspondencia ci ↔ (0 , 0 , ... , 1 , 0 , ... , 0) donde el 1 está en la i – ésima componente , o sea que ci tiene una “base” para su representación como en los espacios vectoriales. Para cada i tenemos entonces que a ≡ aici (mod ni) ≡ ai mi (mi

-1 mod ni) (mod ni) ≡ ai(mod ni) Dado que podemos transformar en ambos sentidos, la correspondencia es biunívoca. Las ecuaciones (26)– (28) resultan fácilmente a partir de x (mod ni )= (x mod ni )(mod ni ) para todo x, y para i = 1 , ... , k. Corolario 28: si n1 ,n2 , ... ,nk son primos relativos entre sí y n = n1n2 ... nk entonces para enteros a1, ... , ak el sistema de ecuaciones x ≡ ai (mod ni) para i = 1 , ... , k tiene una única solución módulo n para la incógnita x. Corolario 29: si n1 ,n2 , ... ,nk son primos relativos entre sí y n = n1n2 ... nk entonces para todos los enteros x , a x ≡ a (mod ni) para i = 1 , ... , k ⇔ x ≡ a (mod n) Veamos un ejemplo ilustrativo del Teorema 27. Sean las ecuaciones:


19

a ≡ 2 (mod 5) a ≡ 3 (mod 13) de modo tal que a1 = 2, n1 = m2 = 5 , a2 = 3, y n2 = m1 = 13, y queremos calcular a mod 65 dado que n = 65. Como 13-1 ≡ 2 (mod 5) y 5-1 ≡ 8 (mod 13) tenemos que c1 = 13(2 mod 5) = 26 c2 = 5 (8 mod 13) = 40 y a ≡ 2.26 + 3.40 (mod 65) ≡ 52 + 120 (mod 65) ≡ 42 (mod 65) Potencias de un elemento: Tal como consideramos los múltiplos de un elemento a módulo n es natural investigar las potencias de a∈Z*n módulo n. Comenzando con 0 tenemos que a0 mod n =1 y el i-ésimo valor es ai mod n. Por ejemplo las potencias de 3 módulo 7 son:

I 0 1 2 3 4 5 6 7 8 9 10 11 3i mod 7 1 3 2 6 4 5 1 3 2 6 4 5

En esta sección usaremos la notación (a) para el subgrupo de Z*n generado por a y sea ordn(a) el orden de a en Z*n .Ahora usamos la definición de la función de Euler ∅(n) para la cardinalidad de Z*n y traducimos el Corolario 19( si (S , ⊕) es un grupo finito con identidad e, entonces ∀ a ∈ S , a (S) = e) en la notación de Z*n para obtener el Teorema de Euler y si además lo especializamos al caso Z*p resulta el Teorema de Fermat: Teorema 30 (de Euler): para cualquier entero n > 1, a ∅(n) ≡ 1 (mod n) ∀ a ∈ Z*n Teorema 31 (llamado el pequeño teorema de Fermat): Si p es primo, a p-1 ≡ 1 (mod p) ∀ a ∈ Z*p Demostración: por la ecuación (21), ∅(p) = p – 1 si p es primo. Esto se aplica a todo elemento en Zp excepto el 0 puesto que 0 ∉ Z*p . Para todo a ∈ Zp tenemos que a p ≡ a (mod p) Si ordn(g) = Z*n resulta que todo elemento de Z*n es una potencia de g, y en ese caso decimos que g es un generador o raíz primitiva de Z*n


20

Por ejemplo, 3 es un generador módulo 7. Si Z*n posee un generador, decimos que el grupo Z*n es cíclico. Teorema 32: Los valores de n > 1 para los cuales Z*n es cíclico son 2, 4, pe y 2pe para todos los primos impares p y todos los enteros positivos e. Demostración: ver por ejemplo el libro I.Niven and H.Zuckerman, “An Introduction to the Theory of Numbers”, J.Wiley, fourth edition, 1980. Si g es un generador de Z*n y a es cualquier elemento de Z*n entonces existe un z tal que g z ≡ a (mod n). Este z se denomina el logaritmo discreto o índice de a módulo n con respecto a la base g y lo notaremos logn,g (a). Teorema 33 (del logaritmo discreto): Si g es un generador de Z*n entonces la ecuación g x ≡ g y (mod n) tiene solución si y solo si la ecuación x ≡ y (mod ∅(n)) la tiene. Demostración: supongamos primero que x ≡ y (mod ∅(n)). Entonces, x = y +k∅(n) para algún entero k. Por lo tanto, g x ≡ g y+k∅(n) (mod n) ≡ g y .(g ∅(n).k) (mod n) ≡ g y.(1k) (mod n) ≡ g y(mod n) donde utilizamos el Teorema 30 (g ∅(n).≡ 1 (mod n)). Recíprocamente, supongamos que g x ≡ g y (mod n). Como la sucesión de potencias de g genera todo elemento de (g), y (g)=∅(n), el Corolario 18 implica que la sucesión de potencias de g es periódica con período ∅(n). Por lo tanto, si g x ≡ g y (mod n) debe cumplirse que x ≡ y (mod ∅(n)). El tomar logaritmos discretos puede simplificar a veces el razonamiento acerca de las ecuaciones modulares, tal como lo muestra el siguiente: Teorema 34: si p es un primo impar y e ≥ 1, entonces la ecuación X 2 ≡ 1 (mod p e) (34) tiene solo dos soluciones: x =1 y x = -1. Demostración: sea n = pe . El teorema 32 implica que Z*n tiene un generador g. La ecuación (34) puede escribirse como


21

log ( ) log (1)2, ,( ) (mod ) (35)xn g n gg g n≡

Dado que logn,g (1) =0 , el Teorema 33 implica que la ecuación (35) es equivalente a

,2.log ( ) 0 (mod ( )) (36)n g x nφ≡

Para resolver esta ecuación para la incógnita log n,g (x) aplicamos los métodos vistos anteriormente. Haciendo

( 1) (2, ( )) (2, ( 1) ) 2ed MCD n MCD p pφ −= = − = Si d / 0 resulta del Teorema 24 que la ecuación (36) tiene exactamente d =2 soluciones. Entonces la ecuación (34) tiene exactamente dos soluciones que son obviamente x =1 y x = -1. Un número x es una raíz cuadrada no trivial de 1 módulo n si satisface la ecuación x 2 ≡ 1 (mod n) pero no es equivalente a las raíces “triviales” 1 y –1 (mod n). Por ejemplo, 6 es una raíz cuadrada no trivial de 1 módulo 35. El siguiente Corolario del Teorema 34 será usado para probar la correctitud del algoritmo de Rabin-Miller para testear primalidad. Corolario 35: si existe una raíz cuadrada no trivial de 1 módulo n, entonces n no es primo (ver más abajo el test de Rabin-Miller). Demostración: por el Teorema 34 n no es primo ni es potencia de un primo.

Calculando potencias mediante cuadrados sucesivos: Una operación fundamental en la teoría de números, y en el método RSA en particular, es la de elevar un número a una potencia módulo otro número. A esto se lo llama exponenciación modular. Más precisamente, buscamos una manera eficiente de calcular a b (mod n), donde a, b son enteros no negativos y n es un entero positivo. El método de los cuadrados sucesivos resuelve este problema en forma eficiente usando la representación binaria de b. Sea (b k, b k-1, ... , b 1, b 0) la representación binaria de b (contiene b k+1 bits, siendo b k el bit más significativo). Procedimiento Exponenciación modular (a,b,n) 1. c ← 0 2. d ← 1


22

3. sea (b k, b k-1, ... , b 1, b 0) la representación binaria de b 4. para i ← k hasta 0 5. do c ← 2c 6. d ← (d.d) (mod n) 7. si b i = 1 8. entonces c ← c + 1 9. d ← (d.a)(mod n) 10. devolver d

Cada exponente que se calcula es el duplo del exponente anterior o ese más uno. La representación binaria de b se lee de derecha a izquierda para controlar cuales operaciones se van a realizar. Cada iteración del loop utiliza las identidades:

2 2

2 1 2

(mod ) ( ) (mod ) ( 0)

(mod ) .( ) (mod ) ( 1)

c ci

c ci

a n a n caso b

a n a a n caso b+

= =

= =

La variable c no es realmente necesaria, pero la incluímos aquí por razones de claridad. El método siempre mantiene la identidad d = a c mod n y c se incrementa duplicandola o sumándole uno hasta que c = b. Si a, b , n son números con k bits, entonces el número total de operaciones aritméticas es O(k) y el número total de operaciones con bits es un O(k3) Ejemplo: sea a = 7, b = 560 = (1000110000), n = 561. La siguiente tabla muestra los resultados del algoritmo en cada paso:

I 9 8 7 6 5 4 3 2 1 0 b i 1 0 0 0 1 1 0 0 0 0 c 1 2 4 8 17 35 70 140 280 560 d 7 49 157 526 160 241 298 166 67 1

Por lo tanto, 7 560 (mod 561) = 1 Una explicación simple de estas ideas es la siguiente: supongamos que queremos calcular a8 (mod n). La forma usual es: (a.a.a.a.a.a.a.a) (mod n) que involucra 7 multiplicaciones y una reducción modular enorme. Esto es obviamente ineficiente desde cualquier punto de vista. Mejor es calcular

2 2 2(( (mod )) (mod )) (mod )a n n n


23

pues esto requiere tres multiplicaciones y tres reducciones modulares, pero de tamaño mucho menor.

El algoritmo RSA: Ya hemos visto los hechos fundamentales relativos a la criptografía de clave pública, así que en aquí nos concentraremos exclusivamente en los aspectos teóricos y algorítmicos del método RSA. El esquema básico es: 1. Seleccionar al azar dos números primos de “gran” longitud. 2. Calcular n =pq 3. Elegir un entero impar e primo relativo con ∅(n) = (p –1)(q – 1) 4. Calcular d tal que e.d (mod ∅(n)) = 1 (el Corolario 26 asegura que d existe y es

único). 5. Publicar el par P = (e,n) que es la clave pública del método RSA. 6. Mantener en secreto el par S = (d,n) que es la clave privada del método RSA. Para encriptar un mensaje M con la clave privada se calcula

dS(M) = M (mod n) (37)

y para desencriptarlo,

cP(S(M)) = (S(M)) (mod n) = M (38) Teorema 36 (correctitud de RSA): Las ecuaciones (37) y (38) definen transformaciones inversas de Zn que cumplen M = S(P(M)) = P(S(M)). Demostración: de las ecuaciones (37) y (38) resulta que

cdP(S(M)) = S(P(M)) = M (mod n) Como e y d son inversas multiplicativas módulo (n) = (p -1)(q - 1)φ

1 ( -1)( -1) para algún entero . ed k p q k= +

Pero entonces, si M 0 (mod p) ≠ tenemos por el Teorema 31 que:

1 ( 1) ( 1)( ) (mod ) (1) (mod ) (mod )ed p k q k qM M M p M p M p− − −≡ ≡ ≡


24

También

ed

ed

(mod ) si 0 (mod ). O sea,

M (mod ) para todo . Similarmente,

M (mod ) Por lo tanto, por el Corolario 29 del Teorema del resto

chino, (mod )

ed

ed

M M p M p

M p M

M q

M M n M

≡ ≡

≡

≡

≡ ∀

La seguridad de RSA depende en gran medida de la dificultad para factorizar números enteros muy grandes (actualmente se ha conseguido factorizar números de 150 dígitos en seis meses de trabajo usando cuatro supercomputadoras Cray. Por ello el método RSA de 1024 bits equivale a usar un n =pq del orden de 310 dígitos, enteros estos que hasta el momento no se han podido factorizar). Lo anterior no quiere decir que quebrar RSA sea equivalente al problema de factorizar enteros, o sea que podrían existir métodos de ataque que no involucren la factorización de n. Resta ahora estudiar el problema de la generación de números primos de gran tamaño. La densidad de los números primos: Los números primos son “bastante” frecuentes, así que es posible y razonable, desde el punto de vista computacional, testear enteros impares aleatorios para ver si son primos. La función de distribución de primos ∏(n) da el número total de primos que son menores o iguales que n. Por ejemplo, ∏(10) = 4 puesto que los primos menores o iguales a 10 son 2, 3, 5 y 7. El Teorema de los números primos da una aproximación útil a esta función. Teorema 37 (de los números primos):

( )

lim 1/ lnn

nn n→∞

Π =

Demostración: ver un libro sobre teoría de números (por ejemplo el ya citado o, E.Kranakis, Primality and Cryptography, Wiley-Teubner Series in Computer Science, 1986). La aproximación / ln n n es bastante buena aún para valores pequeños de n. Por ejemplo, para n = 10 9 tenemos que ∏(n) = 50.847.478 y

/ ln n n = 48.254.942, o sea un error de menos del 6%. Cabe aclarar que este n es muy pequeño tanto sea para la Teoría de Números como para la Criptografía. Podemos usar este teorema para calcular la probabilidad de que un número entero elegido al azar sea primo. Ella es obviamente 1/ ln . n O sea que debemos testear


25

aproximadamente ln n enteros elegidos al azar en las proximidades de n para encontrar un primo con la misma longitud que n. Por ejemplo, para encontrar un primo de 100 dígitos hay que testear aproximadamente ln 10 100 ≅ 230 números de 100 dígitos elegidos al azar. Naturalmente esta cifra se divide por dos pues solo testeamos a los enteros impares. Vamos a ver el problema de testear cuando un número entero impar “grande” es primo o no. Supongamos que n tiene la descomposición en factores primos 2,3,5,...,[ ]n Un enfoque simple al problema de testear la primalidad de n es dividirlo sucesivamente por los enteros hasta n

Este enfoque es exponencial en la longitud de n, así que sólo es factible para valores pequeños de n. Nuestro interés se concentra en determinar cuando un entero es primo , y resulta sorprendente que contestar esto es mucho más simple que calcular la descomposición en factores primos. Los test de pseudoprimalidad:

* {1,2,..., 1} . , n n nSea Z n Si n es primo entonces Z Z+ += − = Vamos a considerar primero un test de primalidad que “casi funciona” y que de hecho sirve para muchas aplicaciones prácticas. Luego, un refinamiento de este método permite eliminar el problema que el original tiene, tema que veremos más adelante. Diremos que n es un pseudoprimo de base a si n es compuesto y

1 1 (mod ) (40)na n− ≡ El Teorema 31 (de Fermat) nos dice que si n es primo entonces n satisface la ecuación (40) para todo elemento a ∈ Z*n .

O sea, que si podemos encontrar un *na Z∈ tal que n no satisface (40), entonces

n es compuesto. Sorprendentemente, lo recíproco “casi” es cierto, con lo cual tenemos un criterio “casi” perfecto de primalidad. Primero testeamos si n satisface (40) con a = 2. Si no, es compuesto. En caso afirmativo, podría ser primo (de hecho sabemos que o es primo o es un pseudoprimo de base 2) El siguiente procedimiento pretende testear de este modo la primalidad de n.


26

Pseudoprimo(n) 1. Si Exponenciación modular (2,n – 1,n) no es congruente con 1 (mod n) 2. entonces devolver COMPUESTO (con seguridad) 3. de lo contrario devolver PRIMO ( posiblemente) Este procedimiento puede tener errores, pero solo de un tipo. Esto es, si dice que n es compuesto, esto es definitivo. Si decimos que n es primo, podemos equivocarnos pues podría ser un pseudoprimo de base 2. La cuestión es: esto sucede con frecuencia ? Respuesta: es muy poco frecuente que suceda. Por ejemplo, si n = 10000 solo hay 22 valores menores que n para los que esto sucede (los primeros cuatro de ellos son 341, 561, 645 y 1105). Puede demostrarse que la probabilidad de que el error ocurra con n un número de k bits tiende a cero cuando k → ∞. Estimaciones más precisas (C.Pomerance, On the distribution of pseudoprimes, Mathematics of Computation, 37(156), pp. 587-593, 1981) muestran que un entero de 50 dígitos elegido al azar que es dado por primo por el procedimiento anterior, tiene una probabilidad menor que una en un millón de ser un pseudoprimo de base 2, y si fuera de 100 dígitos la probabilidad se reduce a 10 –13. Lamentablemente no podemos eliminar los posibles errores testeando con otra base, por ejemplo a =3 porque existen números n compuestos tales que la

ecuación (40) se cumple para todo *na Z∈ .Estos enteros n con dicha propiedad

son extremadamente raros, y se denominan números de Carmichael (los primeros tres son 561, 1105 y 1729). De hecho son tan poco frecuentes que solo hay 255 de ellos menores que 100.000.000 Veremos ahora como mejorar el test de primalidad de modo tal que no pueda ser “engañado” por los números de Carmichael. El test de primalidad de Rabin-Miller: Este test evita los problemas del procedimiento Pseudoprimo (n) mediante dos modificaciones: 1. Prueba diversos valores de a elegidos al azar en vez de un solo

valor.


27

2. Mientras calcula cada exponenciación modular, testea si se encuentra una raíz cuadrada no trivial de 1 módulo n. En caso afirmativo, el resultado para n es “COMPUESTO” (el Corolario 35 justifica esta decisión). A continuación incluímos el pseudocódigo para el test de Rabin-Miller. El dato de entrada n > 2 es el impar que queremos testear para ver si es primo, y s es el

número de valores de base *na Z∈ que se van a ensayar. Suponemos que

tenemos un procedimiento Azar (1, n – 1) que calcula enteros al azar a que satisfacen 1≤ a ≤ n –1. El código también usa un procedimiento llamado Testigo(a,n) que da el valor “VERDAD” si y solo si a es un “testigo” de que n es compuesto, o sea que es posible usar a para probar que n es compuesto. Este procedimiento es similar, pero más efectivo, que el procedimiento Pseudoprimo, que estaba basado en el test con a =2. Primero presentamos y justificamos Testigo, y luego veremos como se usa en el test de Rabin-Miller.

1 1 (mod ) (aqui entendemos como "nocongruente)na n− ≠ ≠

Testigo (a,n) 1. Sea (b k, b k-1, ... , b 1, b 0) la representación binaria de n – 1 2. d ← 1 3. Para i ← k hasta 0 4. do x ← d 5. d ← (d.d) mod n 6. si d = 1 y x ≠ 1 y x ≠ n – 1 7. entonces devolver “VERDADERO” 8. Si b i = 1 9. entonces d ← (d.a) mod n 10. Si d ≠ 1 11. entonces devolver “VERDADERO” 12. devolver “FALSO” Este pseudocódigo para Testigo se basa en el procedimiento Exponenciación modular. La línea 1 determina la representación binaria de n –1 que se usará para calcular a n-1. Las líneas 3-9 calculan d como a n-1 mod n, tal como en Exponenciación modular. Pero cada vez que se calcula un cuadrado en la línea 5 las líneas 6-7 controlan si se ha encontrado una raíz cuadrada no trivial de 1. Si es así, devuelve el valor “VERDADERO”. Las líneas 10-11 devuelven “VERDADERO” si el valor computado para a n-1 mod n es


28

distinto de 1, tal como el procedimiento Pseudoprimo devuelve “COMPUESTO” en ese caso. Veamos ahora que si Testigo (a,n) devuelve “VERDADERO” entonces podemos probar que n es compuesto usando a. Si Testigo (a,n) devuelve “VERDADERO” en la línea 11 entonces descubrió que d = an-1 mod n ≠ 1. Si n es primo, el teorema 31 (Fermat) nos dice que a n-1 ≡ 1 (mod p) ∀ a ∈ Z*n Por lo tanto n no puede ser primo. Si Testigo (a,n) devuelve “VERDADERO” en la línea 7, entonces encontró que x es una raíz cuadrada no trivial de 1 módulo n, o sea que x no es congruente con ± 1 módulo n aunque x2 ≡ 1 (mod n). El Corolario 35 establece que solo si n es compuesto existe una raíz cuadrada no trivial de 1 módulo n, con lo que queda demostrada la correctitud del procedimiento Testigo (a,n). Veamos ahora el Procedimiento Rabin-Miller (n,s) 1. Para j ← 1 hasta s 2. do a ← Azar (1,n – 1) 3. Si Testigo (a,n) 4. Entonces devolver “COMPUESTO” (con seguridad) 5. devolver “PRIMO” (casi seguro)

Este procedimiento es una búsqueda probabílistica de una prueba que n es compuesto. El loop principal (que comienza en la línea 1) elige s valores al azar de a en el intervalo [1,n – 1] en la línea 2. Si uno de esos valores de a es un “testigo” de que n es compuesto, entonces el procedimiento devuelve el valor “COMPUESTO” en la línea 4, y este resultado es siempre correcto debido a la demostración de correctitud del procedimiento Testigo (a,n). Si no se encuentra ningún testigo de que n es compuesto, entonces el procedimiento de Rabin-Miller asume que el número n es primo. Luego veremos que esto es esencialmente correcto si s es lo suficientemente grande, pero siempre existe una probabilidad (que se puede hacer tan pequeña como se quiera) de que existan testigos que el procedimiento no encontró. Veamos un ejemplo con el número de Carmichael 561. Supongamos que elegimos a = 7 como base. La tabla – que ya vimos – era:

I 9 8 7 6 5 4 3 2 1 0 b i 1 0 0 0 1 1 0 0 0 0 c 1 2 4 8 17 35 70 140 280 560 d 7 49 157 526 160 241 298 166 67 1


29

Testigo encuentra una raíz no trivial de 1 puesto que a 280 ≡ 67 (mod n) y a 560 ≡ 1 (mod n). Entonces a =7 es un testigo y el procedimiento Testigo(7,n) devuelve “VERDADERO” y Rabin-Miller “COMPUESTO”. Estimación del error en el procedimiento de Rabin-Miller: Como dijimos anteriormente, si el resultado del procedimiento es “PRIMO”, existe una probabilidad de error que depende de s y de la “suerte” en la elección de los valores de base a. Como el procedimiento de Rabin-Miller no se limita simplemente a verificar si se cumple la ecuación (40) tal como lo hace el procedimiento Pseudoprimo, es de esperar que el error probable sea mucho menor. El siguiente teorema precisa estas consideraciones. Teorema 38: si n es un número compuesto impar, entonces el número de testigos es por lo menos (n – 1)/2. Demostración: la haremos demostrando que la cardinalidad del conjunto de los números que no son testigos no es mayor que (n – 1)/2

Primero observemos que un “no testigo” pertenece a *nZ puesto que debe

satisfacer a n-1 ≡ 1 (mod n) aunque si MCD(a,n) = d > 1 entonces por el Corolario 21 no existen soluciones x de la ecuación modular ax ≡ 1 (mod n) (en particular x = a n –2 no es una solución). Por lo tanto cada

miembro de *n nZ Z− es un testigo. Para completar la demostración mostraremos

que los no testigos están contenidos en un subgrupo propio S de *nZ Por el

Corolario 16 tenemos que S≤ *nZ /2 . Como *

nZ ≤ n – 1 resulta que S≤ (n – 1)/2. Por lo tanto el número de “no testigos” es a lo sumo (n – 1)/2, de modo tal que el número de testigos es al menos (n – 1)/2. Veamos ahora como encontrar un subgrupo propio S que contenga a todos los “no testigos”. Dividimos a la demostración en dos casos:

Caso 1: existe x ∈ *nZ tal que

x n-1 ≠ 1 (mod n) (41)

Sea S = {s ∈ *nZ : s n-1 ≡ 1 (mod n)} . Como S es cerrado para la multiplicación

módulo n, es un subgrupo (Teorema 14). Notemos que todo “no testigo” a pertenece a S puesto que debe cumplir


30

a n-1≡1 (mod n). Como x ∈ *nZ – S , resulta que S es un subgrupo propio de *

nZ .

Caso 2: ∀ x ∈ *nZ

x n-1 ≡ 1 (mod n) (42) En este caso n no puede ser una potencia de un primo, pues supongamos que

n = pe con p primo impar y e > 1. El Teorema 32 implica que *nZ contiene un

elemento g tal que ordn(g) = *nZ =∅(n)= (p-1)pe-1. Pero entonces, la ecuación

(42) y el Teorema 33 del logaritmo discreto (tomando y =0) implican que n-1 ≡ 0 (mod ∅(n)) o sea que (p-1)pe-1/ pe –1. Esta condición falla para e > 1 puesto que el lado izquierdo es divisible por p pero el derecho no. Por lo tanto n no puede ser la potencia de un primo. Y como no lo es, lo podemos escribir como un producto n1n2 donde cada factor es mayor que 1 y son primos relativos entre sí. (puede haber muchas maneras de hacer esto, pero no importa para la demostración). Definamos t, u de modo tal que n – 1= 2t u donde t ≥ 1 y u es

impar. Para cualquier a ∈ *nZ consideremos la sucesión

2 2ˆ { , ,..., } (43)tu u ua a a a=

Donde cada elemento se calcula módulo n. Como 2t / n – 1 la representación binaria de n – 1 termina en t ceros y los elementos de (43) son los últimos t + 1 valores de d calculados por Testigo durante el cálculo de a n-1 mod n; o sea que las últimas t operaciones son cuadrados.

Ahora, encontremos el mayor j ∈{0,1,...,t} tal que existe v∈ *nZ tal que

2 1 (mod )j uv n≡ −

Que algún j existe surge del hecho que u es impar, con lo cual podemos tomar v = -1 , j =0. Dejamos v fijo para satisfacer dicha condición, y sea

* 2{ : 1 (mod )}j u

nB x Z x n= ∈ ≡ − Dado que B es cerrado bajo la multiplicación

módulo n, es un subgrupo de *nZ . Por lo tanto, B divide a *

nZ . Todo “no testigo” debe ser un miembro de B, porque la sucesión (43) producida por un “no testigo” debe estar compuesta de todos 1 o debe contener un –1 a lo sumo en la j-ésima posición, por la maximalidad de j. Vamos a usar ahora la existencia de v para demostrar que existe un


31

* 2 21. Como 1 (mod ) tenemos que -1 ( mod )

j ju unw Z B v n v n∈ − ≡ − ≡

* 2 21. Como 1 (mod ) tenemos que -1 ( mod )

j ju unw Z B v n v n∈ − ≡ − ≡

por el Corolario 29. Por el Corolario 28, existe un w que satisface simultáneamente a las ecuaciones:

1

2

21

22

(mod )

1 (mod ) y por lo tanto

1 (mod )

1 (mod )

j u

j u

w v n

w n

w n

w n

≡≡

≡ −

≡

conjuntamente con el Corolario 29, estas ecuaciones implican que

2 1 (mod ) (44)j uw n≠ ±

y por lo tanto

* * * *1

*

. Como tenemos que

De donde resulta que B es un subgrupo propio de . En cualquier caso vemos que la cantidad

de testigos de que n es compuesto es por lo menos (n - 1)/2

n n n n

n

w B v Z v Z w Z w Z B

Z

∉ ∈ ∈ ⇒ ∈ ⇒ ∈ −

Teorema 39: para cualquier entero impar n > 2 y cualquier entero positivo s, la probabilidad de que el procedimiento Rabin-Miller (n,s) erre es a lo sumo 2 –s Demostración: usando el Teorema 38, vemos que si n es compuesto, entonces cada ejecución del loop de las líneas 1-4 tiene una probabilidad de al menos ½ de descubrir un testigo x de que n es compuesto. El procedimiento solo comete un error si no encuentra un testigo de que n es compuesto en ninguna de las s iteraciones del loop principal. La probabilidad de que esa sucesión de “no encontrar” un testigo es a lo sumo 2 –s Nota: esta cota del error se puede mejorar. Por ejemplo, en los trabajos: I.B.Damgard and P.Landrock, “ Improved Bounds for the Rabin Primality Test”, Cryptography and Coding III,M.J.Ganley (ed), Oxford Clarendon Press, 1993, pp.117 – 128. I.B.Damgard, P.Landrock and C.Pomerance, “Average Case Error Estimates for the Strong Probable Prime Test”, Mathematics of Computation, vol.61, 203, Jul.1993, pp. 177-194.


32

se demuestra que aún la cota 4 –s es pesimista. Obviamente estas demostraciones deben entenderse en un sentido probabílistico, pues en la práctica se encuentran casos en que a pesar de fijar valores muy pequeños del error, aparecen números compuestos dados como primos.

Métodos de factorización: El objetivo de este apunte no incluye discutir en profundidad los métodos de factorización ni los ataques a RSA, pero de todos modos haremos algunos comentarios. Obviamente, si se pudiese factorizar n =p*q (que forma parte de la clave pública, y por lo tanto es conocido), se lograría quebrar RSA inmediatamente. El método más antiguo es el llamado de la criba de Erastótenes que sirve para encontrar todos los números primos en un intervalo dado (hasta n). Primero se hace un círculo al 2 y se marcan todos los que siguen de dos en dos ) o sea 4, 6, 8, ...). El próximo número no marcado es 3, se le hace un círculo, y se marcan los que siguen de 3 en 3, etc. Luego de llegar a la raíz cuadrada de n se hace un círculo a los enteros que quedaron sin marcar, y esos son los primos. De hecho este algoritmo hace algo más que encontrar primos: si un entero se marca más de una vez es porque tiene varios factores primos. Por ejemplo, a 30 se lo marca tres

veces. Una observación interesante es la siguiente, ilustrada con un ejemplo: supongamos que queremos factorizar 8051. Dado que puede escribirse como 8100 – 49 = 902 – 72 =(90 +7)*(90 – 7) = 83*97, encontramos fácilmente sus factores. Ahora, esto es general ? Sí, puesto que

2 21 1* ( ( )) ( ( ))

2 2a b a b a b= + − −

De hecho, esta idea se debe a Fermat, y si a y b están próximos a n como sucedía en el caso 8051, es bastante simple encontrar los cuadrados. Pero en los casos “difíciles” este algoritmo es peor que simplemente dividir por los primos menores que n . En la década de 1920, Maurice Kraitchik propuso la idea que es la base de los métodos modernos (aunque se remonta a Gauss y Seethoff). En vez de buscar u,v tales que n = u2 – v2, la idea es que la diferencia de los cuadrados sea congruente con n. Dicha congruencia puede tener soluciones “no interesantes” como u ≡ v (mod n) o u ≡ -v (mod n), o “interesantes” donde lo anterior no vale. Si n es impar y divisible al menos por dos primos distintos, entonces como mínimo la mitad de las


33

soluciones de u2 ≡ v2 (mod n) con uv coprimo con n son “interesantes”. Y para ellas, el MCD(u-v,n) debe ser necesariamente un factor no trivial de n. De hecho, n divide a u2 – v2 =(u –v)*(u + v) pero no divide a ninguno de sus factores, y por ello debe estar entre u –v y u + v. Veamos un ejemplo: sea n = 2041. El primer cuadrado mayor que n es 462 = 2116. Consideremos la sucesión Q(x) = x2 – n para x = 46, 47, .. Resulta: 75, 168, 263, 360, 459, 560, ... Hasta aquí no aparecieron cuadrados, así que el método de Fermat seguiría buscando. Pero Kraitchik tiene otra opción: encontrar varios valores de los números x tales que su producto con los correspondientes elementos de Q(x) sean un cuadrado. Porque si Q(x1)Q(x2)...Q(xk) = v2 y x1...xk = u, entonces

2 2 2 2 2 21 1 1

2 2

... ( )...( ) ( )... ( ) (mod ), o sea

encontramos una solucion a (mod )

k k ku x x x n x n Q x Q x v n

u v n

= ≡ − − = =

≡

Pero, cómo encontrar a los valores xi ? Kraitchik se dio cuenta que algunos de los números Q(x) pueden factorizarse rápidamente: 75 = 3.52 , 168 = 23.3.7 , 360 = 23.32.5 , 560 = 24.5.7 De estas factorizaciones se puede ver que el producto de los cuatro números es 210.34.54.72, un cuadrado ! De este modo tenemos que u2≡ v2 mod n, donde u = 46.47.49.51 ≡ 311 mod 2041, v = 25.32.52.7 ≡1416 mod 2041 Como 311 no es congruente con 1416 mod 2041, calculamos MCD(1416 – 311,2041) = 13, entonces 2041 = 13.157. Los métodos usados actualmente tienen su origen en las ideas que recién vimos. Ellos son: 1) La criba cuadrática (quadratic sieve). Es el más rápido para números de hasta

110 dígitos. 2) La criba cuadrática polinomial múltiple. Versión más rápida que la anterior. 3) El método NFS (Number Field Sieve). Es el más veloz para números con más

de 110 dígitos. Su tiempo asintótico se acerca a lo polinomial. Una referencia interesante es: Carl Pomerance, “A Tale of Two Sieves”, Notices of the American Mathematical Society, December 1996, pp.1473 – 1485.

Una idea del esfuerzo computacional requerido para quebrar RSA lo da la siguiente tabla:


34

No.de bits de n Años para factorizar suponiendo 1.000.000 de instrucciones por segundo.

512 30.000 768 200.000.000 1024 300.000.000.000 2048 300.000.000.000.000.000.000

La empresa RSA Data Security ofrece distintos desafíos relativos a la factorización (http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html) . El mayor número factorizado entre ellos ha sido: 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059 que tiene 174 dígitos y se logró el resultado el 3/12/2003 El “siguiente” desafío tiene un premio de 20.000 U$S y corresponde al número de 193 dígitos: 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609 La lista de los mayores primos conocidos se encuentra en el link http://primes.utm.edu/largest.html El mayor hasta hoy es: 220,996,011-1 que tiene 6.320.430 dígitos decimales y lo obtuvo Michael Shafer el 17/11/2003

Documents

Fundamentos matemáticos del método RSA