Apuntes2

1

´ n 2. El sistema RSA Leccio Los sistemas de cifrado los podemos clasificar en dos grandes grupos: a) Sistemas de clave privada, cuando la clave K se elige secretamente entre los comunicantes. Tambi´en se denominan sim´etricos. La funci´on de descifrado, dk se deduce f´acilmente de la funci´on de cifrado ek . ´blica, la funci´on de cifrado puede ser conob) Sistemas de clave pu cida por todos y escribirse en un directorio. Tambi´en se denominan asim´etricos.

El receptor es la u ´nica persona que conoce la regla para descifrar. En este caso el conocimiento de ek hace computacionalmente dif´ıcil obtener dk La idea de un sistema de clave p´ ublica se debe a W. Diffie y M.E. Hellman que lo publicaron en 1976. Multiuser cryptographic techniques, AFIPS Conference Proceedings, 45 (1976), 109-112. La realizaci´on de este sistema se debe a R. Rivest, A. Shamir y L. Adleman en 1977, por eso lo conocemos como el sistema RSA. A method for obtaining digital signatures and public key criptosystems. Communications of the ACM, 21 (1978), 120-126.

Blas Torrecillas

2

Resultados sobre congruencias ´ n Supongamos que a, m son enteros positivos si mcd(a, m) = 1 Definicio decimos que a y m son primos relativos. ´ n fi de Euler Dado m un entero positivo, definimos phi(m) La funcio como el n´ umero de enteros 1 ≤ a < m que son primos relativos con m. Coincide con el n´ umero de unidades en el anillo Zm . Teorema. El conjunto de todos los elementos invertibles, las unidades, de Zm es un grupo abeliano finito con respecto a la multiplicaci´on. Lo denotaremos U (Zm ). Teorema. La funci´on de Euler es multiplicativa, i.e. si m y n son enteros positivos primos relativos entonces φ(mn) = φ(m)φ(n). Demostraci´on. Se tiene el isomorfismos de anillos si m, n son primos relativos Zmn ∼ = Zm ×Zn . Entonces U (Zmn ) ∼ = U (Zm ×Zn ) ∼ = U (Zm )×U (Zn ). Teorema. Si p es un n´ umero primo y n un entero positivo φ(pn ) = pn−1 (p − 1) Demostraci´on. Basta observar que los u ´nicos elementos que no son primos con pn son los multiplos de p, que se pueden calcular multiplicando 1, 2, 3, ...., pn−1 por p. Por tanto φ(pn ) = pn − pn−1 . Teorema de Lagrange Definici´ on. Sea g ∈ G un elemento de un grupo G. El orden de g es el menor entero, si existe, n tal que g n = 1. Definici´ on. Un subconjunto S de un grupo G se llama subgrupo de G si S con la operaci´on del grupo G es un grupo. Teorema. (Lagrange). Si G es finito. El orden de cada subgrupo divide al orden del grupo.

Blas Torrecillas

3

Demostraci´on. Sea H un subgrupo de G. Establecemos una relaci´on de equivalencia en G. Dos elementos x, y ∈ G est´an relacionados cuando xy −1 ∈ H. Claramente xx−1 = e est´a en H, por tanto la relaci´on es reflexiva. Si x est´a relacionado con y, i.e. xy −1 ∈ H, su inverso (xy −1 )−1 tambi´en est´a en H. Como (xy −1 )−1 = (y −1 )−1 x−1 = yx−1 , se sigue que y est´a relacionado con x y la relaci´on es sim´etrica. Por u ´ltimo si x est´a relacionado con y e y est´a relacionado con z, se tiene que xy −1 ∈ H e yz −1 ∈ H. Multiplicando los dos elementos (xy −1 )(yz 1 ) = xz −1 obtenemos un elemento de H. Por tanto x est´a relacionado con z y la relaci´on es transitiva. En resumen hemos probado que se trata de una relaci´on de equivalencia. Toda relaci´on de equivalencia establece una partici´on en el conjunto, por tanto G se divide en clases de equivalencia. Cada clase de equivalencia est´a formada por elementos relacionados con un x ∈ G, es decir los elementos y ∈ G tales que xy −1 ∈ H. Tenemos xy −1 = h ∈ H, despejando y obtenemos y = h−1 x. La clase de equivalencia es por tanto el conjunto Hx = {hx, h ∈ H}. Consideremos la aplicaci´on H → Hx h 7→ hx. La aplicaci´on es inyectiva porque si hx = h0 x entonces h = h0 y es claramente sobreyectiva. Obtenemos una aplicaci´on biyectiva que prueba que todas las clases de equivalencia tienen el mismo cardinal, el orden de H. Como se trata de una partici´on, el orden de G es igual al orden de H por el n´ umero de clases de equivalencia. Luego el orden de H divide al orden de G. Teorema. El orden de cada elemento de un grupo finito divide al orden del grupo. Corolario 1. Teorema de Euler Si (b, m) = 1, entonces bφ(m) ≡ 1 (modm).

Blas Torrecillas

4

Corolario 2. Teorema de Fermat Supongamos Supongamos que p es primo y b ∈ Z. Entonces bp ≡ b (modp). Teorema Si p es primo, entonces Z∗p es un grupo c´ıclico.

Blas Torrecillas

5

´blica RSA Sistema de clave pu Algoritmo Generaci´on de claves para el sistema RSA Resumen: cada entidad crea un clave p´ ublica RSA y una correspondiente clave privada. Para esto cada entidad hace lo siguiente: 1. Generar aleatoriamente dos primos grandes (y distintos) p y q, aproximadamente del mismo tama˜ no. 2. Calcular n = pq y φ = φ(n) = (p − 1)(q − 1). 3. Seleccionar aleatoriamente un entero c, 1 < c < φ, tal que mcd(c, φ) = 1. 4. Usar el algoritmo extendido de Euclides para calcular el inverso de c m´odulo φ, i.e. un entero d tal que cd ≡ 1 (mod φ). 5. La clave p´ ublica de A es (n, c); la clave privada de A es d. ´ n Los enteros c y d en la generaci´on de clave RSA se denominan Definicio los exponentes de cifrado y descifrado respectivamente. Ejemplo La entidad A elige los primos p = 2357, q = 2551, y n = pq = 6012707 y φ = (p − 1)(q − 1) = 6007800. Elegimos c = 3674911 y usando el algoritmo de Euclides extendido encontramos el inverso d = 422191. clave p´ ublica de A es n = 6012707, c = 3674911 clave privada de A es d = 422191

Blas Torrecillas

6

El algoritmo de RSA Sea n = pq, donde p y q son primos. Sea P = C = Zn , y definamos K = {(n, p, q, c, d)|n = pq, p, q primos, cd ≡ 1 (mod ϕ(n))} Para K = (n, p, q, c, d), definimos eK (x) = xc mod n y dK (y) = y d mod n (x, y ∈ Zn ). Los valores n y c son p´ ublicos, y los valores de p, q, d son secretos. En primer lugar comprobaremos que el algoritmo funciona, i.e. que se verifica que dK (eK (x) = x. Efectivamente dK (eK (x)) = (xc )d = xcd = x1+tϕ(n) = x × xϕ(n) = x. Notemos que los c´alculos anteriores se han hecho en Zn . Ejemplo Sea el mensaje x = 5234673. El emisor lo cifra y = eK (x) = xc mod n = 52346733674911 mod 6012707 = 3650502 y lo env´ıa. El receptor lo descifra calculando x = dK (y) = y d mod n = 3650502422191 mod 6012707 = 5234673

Blas Torrecillas

7

´ Quien conoce que El emisor conoce el mensaje claro x El receptor conoce los primos p, q y la clave de descifrado d Todo el mundo conoce el entero n y la clave de cifrado c. Algoritmo C´alculo exponencial en Zn por cuadrados-multiplicaci´on repetidos. ENTRADA: a ∈ Zn , y un entero 0 ≤ k < n cuya representaci´on binaria P es k = ti=0 ki 2i . SALIDA: ak mod n. 1. Establecer b ← 1. Si k = 0 entonces devolver b. 2. Establecer A ← a. 3. Si k0 = 1 entonces b ← a. 4. Desde i = 1 a t hacer (a) Establecer A ← A2 mod n. (b) Si ki = 1 entonces b ← Ab mod n. 5. Devolver b.