PDF de programación - Capítulo 7 Teoría de los Números

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 7

Teoría de los Números

Seguridad Informática y Criptografía

Ultima actualización del archivo: 01/03/06
Este archivo tiene: 75 diapositivas

v 4.1

Material Docente de
Libre Distribución

Dr. Jorge Ramió Aguirre
Universidad Politécnica de Madrid

Este archivo forma parte de un curso completo sobre Seguridad Informática y Criptografía. Se autoriza el uso,
reproducción en computador y su impresión en papel, sólo con fines docentes y/o personales, respetando los
créditos del autor. Queda prohibida su comercialización, excepto la edición en venta en el Departamento de
Publicaciones de la Escuela Universitaria de Informática de la Universidad Politécnica de Madrid, España.

Curso de Seguridad Informática y Criptografía © JRA

Capítulo 7: Teoría de los Números

Página 238

Matemática discreta y congruencia

• La congruencia es la base en la que se sustentan las

operaciones de cifra en matemática discreta.

• Concepto de congruencia:

– Sean dos números enteros a y b: se dice que a es

congruente con b en el módulo o cuerpo n (Zn) si y sólo
si existe algún entero k que divide de forma exacta la
diferencia (a - b) .

– Esto podemos expresarlo así:

a - b = k ∗ n

a ≡ n b

a ≡ b mod n

Desde esta página Web podrá realizar diversos cálculos en
matemática discreta:

http://www.numbertheory.org/php/php.html



© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 7: Teoría de los Números

Página 239

Operaciones de congruencia en Zn

¿Es 18 congruente con 3 módulo 5?

¿18 ≡ 3 mod 5?

Sí, porque: 18-3 = 15 = k∗5 con k = 3

¿Cómo se usará esto en criptografía?
Esta operación en Zn se expresará así:

18 mod 5 = 3

El valor 3 será el resto o residuo.
El conjunto de números que forman los restos dentro de
un cuerpo Zn será muy importante en criptografía.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Página 240

Propiedades de la congruencia en Zn

• Propiedad Reflexiva:

a ≡ a mod n ∀ a ∈ Z

• Propiedad Simétrica:

a ≡ b mod n ⇒ b ≡ a mod n ∀ a,b ∈ Z

• Propiedad Transitiva:

Si a ≡ b mod n y b ≡ c mod n

⇒ a ≡ c mod n ∀ a,b,c ∈ Z

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 7: Teoría de los Números

Página 241

Propiedades de las operaciones en Zn (1)

• Propiedad Asociativa:

a + (b + c) mod n ≡ (a + b) + c mod n

• Propiedad Conmutativa:

a + b mod n ≡ b + a mod n
a ∗ b mod n ≡ b ∗ a mod n

• Propiedad Distributiva:

Normalmente usaremos
el signo = en vez de ≡ que
denotaba congruencia.
Esto es algo propio de los
Campos de Galois que
veremos más adelante.

a ∗ (b+c) mod n ≡ ((a ∗ b) + (a ∗ c)) mod n
a ∗ (b+c) mod n = ((a ∗ b) + (a ∗ c)) mod n

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Página 242

Propiedades de las operaciones en Zn (2)
• Existencia de Identidad:

a + 0 mod n = 0 + a mod n = a mod n = a
a ∗ 1 mod n = 1 ∗ a mod n = a mod n = a

• Existencia de Inversos:



a + (-a) mod n = 0
a ∗ (a-1) mod n = 1 (si a ≠ 0)

Ambos serán
muy importantes
en criptografía

No siempre existe

• Reducibilidad:



(a + b) mod n = [(a mod n) + (b mod n)] mod n
(a ∗ b) mod n = [(a mod n) ∗ (b mod n)] mod n

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 7: Teoría de los Números

Página 243

Conjunto completo de restos CCR

Para cualquier entero positivo n, el conjunto
completo de restos será CCR = {0, 1, 2, ... n-1},
es decir:
∀ a ∈ Z ∃ ! ri ∈ CCR / a ≡ ri mod n
CCR (11) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
CCR (6) = {0, 1, 2, 3, 4, 5} = {12, 7, 20, 9, 16, 35}
El segundo conjunto es equivalente: 12 → 0, 7 → 1...
Normalmente se trabajará en la zona canónica: 0 – n-1

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Página 244

Homomorfismo de los enteros

Enteros
a1, a2

Enteros mod n
(a1 mod n), (a2 mod n)

es lo mismo que

Esta operación ...

esta otra

op (y posterior reducción mod n) op

(a1 op a2) mod n
Esto nos permitirá trabajar con números muy grandes

(a1 mod n) op (a2 mod n) mod n

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 7: Teoría de los Números

Página 245

Un ejemplo de homomorfismo



88 ∗ 93 mod 13
8.184 mod 13
Resultado: 7

Se desbordaría
la memoria de
nuestro sistema

Ahora ya no
se desborda
la memoria



☺

Ejemplo: una calculadora capaz de
trabajar sólo con tres dígitos ...
Solución por homomorfismo:
88 ∗ 93 mod 13
[(88) mod 13 ∗ (93) mod 13] mod 13

10 ∗ 2 mod 13
20 mod 13 Resultado: 7

se llega a lo mismo, pero...
... y hemos usado siempre números de 3
dígitos. En este caso la operación máxima
sería 12∗12 = 144, es decir tres dígitos.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Página 246

Divisibilidad de los números

En criptografía muchas veces nos interesará encontrar el
máximo común denominador mcd entre dos números a y b.
Para la existencia de inversos en un cuerpo n, la base a y el
módulo n deberán ser primos entre sí. ⇒ mcd (a, n) = 1
Algoritmo de Euclides:

– a) Si x divide a a y b ⇒ a = x ∗ a’ y b = x ∗ b’
– b) Por lo tanto: a - k ∗ b = x ∗ a’ - k ∗ x ∗ b’

a - k ∗ b = x (a’ - k ∗ b’)

– c) Entonces se concluye que x divide a (a - k ∗ b)

© Jorge Ramió Aguirre Madrid (España) 2006

http://es.geocities.com/eucliteam/



Capítulo 7: Teoría de los Números

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 7: Teoría de los Números

Página 247

El máximo común denominador mcd

Como hemos llegado a que x divide a (a – k ∗ b) esto nos
permitirá encontrar el mcd (a, b):

Si a > b entonces a = d1 ∗ b + r
(con di un entero y r un resto)

Luego mcd (a, b) = mcd (b ,r)
porque:

(a > b > r ≥ 0)

Si b > r entonces b = d2 ∗ r + r’
(con r un entero y r’ un resto)

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Página 248

Divisibilidad con algoritmo de Euclides

mcd (148, 40)
148 = 3 ∗ 40 + 28
40 = 1 ∗ 28 + 12
28 = 2 ∗ 12 + 4
12 = 3 ∗ 4 + 0
mcd (148, 40) = 4

Esta condición
será importante en
criptografía.



148 = 22 ∗ 37
40 = 23 ∗ 5

Factor común
22 = 4

No hay
factor común
385 = 5 ∗ 7 ∗ 11
78 = 2 ∗ 3 ∗ 13

mcd (385, 78)
385 = 4 ∗ 78+ 73
78 = 1 ∗ 73 + 5
73 = 14 ∗ 5 + 3
5 = 1∗ 3 + 2
3 = 1∗ 2 + 1
2 = 2 ∗ 1 + 0

mcd (385, 78) = 1

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 7: Teoría de los Números

Página 249

Inversión de una operación de cifra

• En criptografía deberá estar permitido invertir una

operación para recuperar un cifrado ⇒ descifrar.

• Aunque la cifra es una función, en lenguaje coloquial la

operación de cifrado podría interpretarse como una
“multiplicación” y la operación de descifrado como una
“división”, si bien hablaremos en este caso de una
multiplicación por el inverso.

• La analogía anterior sólo será válida en el cuerpo de los

enteros Zn con inverso.

• Luego, si en una operación de cifra la función es el valor a
dentro de un cuerpo n, deberemos encontrar el inverso a-1
mod n para descifrar; en otras palabras ...

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Página 250

Inversos en Zn
Si a ∗ x ≡ 1 mod n

se dice que x es el inverso multiplicativo de a en Zn y se

denotará por a-1.

• No siempre existen el inverso de un elemento en Zn.
Por ejemplo, si n = 6, en Z6 no existe el inverso del
2, pues la ecuación 2∗x ≡ 1 mod 6 no tiene solución.

• Si n es un número primo p, entonces todos los

elementos de Zp salvo el cero tienen inverso. Por
ejemplo, en Z5 se tiene que:
1-1 mod 5 = 1; 2-1 mod 5 = 3, 3-1 mod 5 = 2; 4-1 mod 5 = 4.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 7: Teoría de los Números

Página 251

Existencia del inverso por primalidad

∃ inverso a-1 en mod n

ssi mcd (a, n) = 1

Si mcd (a,n) = 1, el resultado de a∗i mod n (para i todos los
restos de n) serán valores distintos dentro del cuerpo n.

mcd (a, n) = 1 ⇒ ∃ x ! 0 < x < n / a ∗ x mod n = 1

Sea: a = 4 y n = 9. Valores de i = {1, 2, 3, 4, 5, 6, 7, 8}

S
O
L
U
C
I
Ó
N

Ú
N
I
C
A

4∗1 mod 9 = 4
4∗2 mod 9 = 8 4∗3 mod 9 = 3
4∗4 mod 9 = 7 4∗5 mod 9 = 2 4∗6 mod 9 = 6
4∗7 mod 9 = 1

4∗8 mod 9 = 5

Si mcd (a,n) ≠ 1

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Página 252

Inexistencia de inverso (no primalidad)

¿Y si no hay primalidad entre a y n?

Si mcd (a, n) ≠ 1
No existe ningún x que 0 < x < n / a ∗ x mod n = 1
Sea: a = 3 y n = 6 Valores de i = {1, 2, 3, 4, 5}

3∗1 mod 6 = 3 3∗2 mod 6 = 0 3∗3 mod 6 = 3
3∗4 mod 6 = 0 3∗5 mod 6 = 3



No existe el inverso para ningún resto del cuerpo.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 7: Teoría de los Números

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 7: Teoría de los Números

Página 253

Inversos aditivo y multiplicativo

(A+B) mod 5
B + 0 1 2 3 4
0 1 2 3 4
A 0
1
1 2 3 4 0
2 3 4 0 1
2
3 4 0 1 2
3
4
4 0 1 2 3

(A∗B) mod 5
B ∗ 0 1 2 3 4
0 0 0 0 0
A 0
1
0 1 2 3 4
0 2 4 1 3
2
0 3 1 4 2
3
4
0 4 3 2 1

0+0 = 0
1∗