Aritmetica modular

Seguridad Informática 2010

TEMA 1.1: Herramientas matemáticas para la criptografía

Aritmética modular
Definición Sea n ≥ 1, se dice que a es congruente con b módulo n y se escribe a ≡ b mod n si n|(a − b). Definición Un conjunto de números enteros tales que cualquier entero es congruente módulo n con exactamente un elemento del conjunto recibe el nombre de «conjunto completo de residuosmódulo n». Definición Zn es un conjunto completo de residuos módulo n. Por ejemplo: Zn = {0, 1, 2, ..., n − 2, n − 1} Definición a ∈ Zn es invertible ⇔ ∃b ∈ Zn tal que ab ≡ 1 mod n Teorema a ∈ Zn es invertible ⇔ (a, n) = 1
Ingeniería Técnica en Informática de Gestión 1

Seguridad Informática 2010

TEMA 1.1: Herramientas matemáticas para la criptografía

Algoritmo de Euclídes para calcular el MCDde a y b
Paso 1 Inicializar r0 = a y r1 = b Paso 2 Calcular la secuencia de ecuaciones r0 = q1 · r1 + r2 r1 = q2 · r2 + r3 . . rn−3 = qn−2 · rn−2 + rn−1 rn−2 = qn−1 · rn−1 + rn hasta que haya una iteración en la cual rn = 0 y rn−1 = 0. Paso 3 El Máximo Común Divisor de a y b es rn−1 NOTA Si M CD(a, b) = 1 entonces a y b son primos relativos.
Ingeniería Técnica en Informática de Gestión 2Seguridad Informática 2010

TEMA 1.1: Herramientas matemáticas para la criptografía

Algoritmo extendido de Euclídes para obtener a−1 mod N
Este algoritmo permite calcular la inversa modular x ≡ a−1 mod N tal que ax ≡ 1 mod N INICIALIZACIÓN: r0 = N, r1 = a, x0 = 1 q1 = r0/r1, r2 = r0 mod r1, x1 = −q1 ITERACIÓN: Mientras r2 = 0 calcular iterativamente r0 = r1, r1 = r2, q1 = r0/r1, r2 = r0 mod r1x2 = x0 − q1 · x1, x0 = x1, x1 = x2 SOLUCIÓN: Si r1 = 1 no existe la inversa Si x0 > 0 la inversa es x0 en caso contrario, la inversa es x0 + N

Ingeniería Técnica en Informática de Gestión

3

Seguridad Informática 2010

TEMA 1.1: Herramientas matemáticas para la criptografía

Algoritmo de exponenciación modular para y ≡ xm mod n
Los números que se manejan en la criptografía son muygrandes y se requiere disponer de algoritmos los manejen evitando desbordamientos (overflows). En el caso del cálculo de la exponenciación modular y ≡ xm mod n se dispone del siguiente algoritmo: INICIALIZACIÓN: y = 1, u = x mod n ITERACIÓN: Iterar hasta que m = 0 1. Si m mod 2 = 1 entonces y = (y ∗ u) mod n 2. m = m/2 3. u = (u ∗ u) mod n SOLUCIÓN: y ≡ xm mod n

Ingeniería Técnica en Informáticade Gestión

4

Seguridad Informática 2010

TEMA 1.1: Herramientas matemáticas para la criptografía

La función Totient de Euler
De acuerdo al Teorema fundamental de la aritmética, cualquier entero m > 1 se puede factorizar como un producto de potencias de números primos de acuerdo a n m=
i=1

pei i

donde pi son los distintos factores primos y ei > 0 sus correspondientes exponentes,siendo n el número de factores primos. En estas condiciones, se define la función Totient de Euler φ(n) tal que
n

φ(n) =
i=1

(pei − pei−1) i i

es el número de enteros positivos menores que m primos relativos con m.
Ingeniería Técnica en Informática de Gestión 5

Seguridad Informática 2010

TEMA 1.1: Herramientas matemáticas para la criptografía

Teorema de Euler
Sean N y avalores enteros con a primo relativo con respecto de N. Bajo estas condiciones, si φ(N ) es la función Totient de Euler, entonces se verifica que aφ(N ) ≡ 1 mod N

Teorema de Fermat
Si p es un número primo y a es un entero relativamente primo con p, entonces se verifica la congruencia ap−1 ≡ 1 mod p lo cual es un caso particular del Teorema de Euler, puesto que para un primo p la función Totient deEuler φ(p) está dada por φ(p) = p − 1.
Ingeniería Técnica en Informática de Gestión 6

Seguridad Informática 2010

TEMA 1.1: Herramientas matemáticas para la criptografía

Corolarios al Teorema de Fermat
1. Si p es primo, para cualquier entero de a se verifica que ap−1a ≡ a mod p 2. Si p es primo, para cualesquiera valores enteros de a y k se verifica que ak(p−1)a ≡ a mod p 3. Si p es...