TEORIA DE NÙMEROS

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 encomputador 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

Página 238

Capítulo 7: Teoría de losNúmeros

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) .
a-b=k∗n
– Esto podemos expresarloasí:
a≡nb
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

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 encriptografí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

© Jorge Ramió Aguirre

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

Madrid (España) 2006

Página 241

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

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 + amod 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

Página 242

Capítulo 7: Teoría de los NúmerosPropiedades 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

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

Página 244

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

Homomorfismo de los enteros
Enteros

Enteros mod n

a1 , a2

(a1 mod n), (a2 mod n)

es lo mismo que

Esta operación ...

op (y posterior reducción mod n)
(a1 op a2) mod...