SItema 05

Tema 5
Teoría de los Números
Seguridad Informática y Criptografía
Ultima actualización: 03/03/03

Archivo con 67 diapositivas
Material Docente de Jorge Ramió Aguirre

v 3.1
Libre Distribución Universidad Politécnica de Madrid
Este archivo forma parte de un curso sobre Seguridad Informática y Criptografía. Se autoriza la
reproducción en computador e impresión en papel sólo con fines docentes o personales, respetando
en todo caso los créditos del autor. Queda prohibida su venta, excepto a través del Departamento de
Publicaciones de la Escuela Universitaria de Informática, Universidad Politécnica de Madrid, España.
Curso de Seguridad Informática y Criptografía © JRA

Conceptos básicos de congruencia
• Es la base matemática (matemáticas discretas) en

la que se sustentan las operaciones de cifra.
• 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
anb
a  b mod n
Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva 2
© Jorge Ramió Aguirre Madrid (España) 2003

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án muy importantes en criptografía.

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

Propiedades de las operaciones en Zn (1)
• Propiedad Asociativa:
a + (b + c) mod n  (a + b) + c mod n
• Propiedad Conmutativa: Se usará el signo =
a + b mod n  b + a mod n en vez de 
(algo propio de los
a  b mod n  b  a mod n
Campos de Galois)
• Propiedad Distributiva:
a  (b+c) mod n  ((a  b) + (a  c)) mod n
a  (b+c) mod n = ((a  b) + (a  c)) mod n

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:  Ambos importantes en
a + (-a) mod n = 0 criptografía 
a  (a-1) mod n = 1 (si a  0) 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

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

Homomorfismo de los enteros
Enteros Enteros mod n

a1, a2 (a 1 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 (a1 mod n) op (a2 mod n) mod n

Un ejemplo de homomorfismo
8893
88 93mod
mod13
13  Ejemplo: una calculadora capaz de
trabajar sólo con tres dígitos ...
8.184 mod
8.184 mod13
13
Solución por
Resultado:77
Resultado: homomorfismo:
88  93 mod 13
[(88) mod 13  (93) mod 13 mod 13
Se desbordaría
la memoria de
 10  2 mod 13
nuestro sistema 20 mod 13 Resultado: 7
se llega a lo mismo, pero...
Ahora ya no
se desborda ... y hemos usado siempre números de 3
dígitos. En este caso la operación máxima
la memoria  sería 1212 = 144, es decir tres dígitos.

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)
Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva
10
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) (a > b > r  0)
porque:
Si b > r entonces b = d2  r + r’
(con r un entero y r’ un resto)
11
Divisibilidad con algoritmo de Euclides
mcd (148, 40) 148 = 22  37 mcd (385, 78)
148 = 3  40 + 28 40 = 23  5 385 = 4  78+ 73
40 = 1  28 + 12
Factor común
78 = 1  73 + 5
22 = 4
28 = 2  12 + 4 73 = 14  5 + 3
12 = 3  4 + 0 5 = 1 3 + 2
No hay
mcd (148, 40) = 4 factor común 3 = 1 2 + 1
385 = 5  7  11 2=21+0
Será importante
en criptografía  78 = 2  3  13 mcd (385, 78) = 1
12
Inversión de una operación de cifra
• En criptografía deberá estar permitido invertir una

operación para recuperar un cifrado  descifrar.
• Si bien la cifra es una función, en lenguaje coloquial
la operación de cifrado sería una “multiplicación” y la
operación de descifrado una “división”.
• 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 ...
13
Inversos en un cuerpo
Si a  x mod n = 1
x será el inverso multiplicativo (a-1) de a en el módulo n
 No siempre existen los inversos multiplicativos. En

realidad lo raro es que existan.
 Por ejemplo, en Z = 2 no existirán inversos pues la
única solución para ax mod 2 = 1, con a, x = {0, 1},
sería x = 1 para a = 1, una solución trivial. El cero
nunca será solución del inverso multiplicativo.

14
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 41 mod 9 = 4 42 mod 9 = 8 43 mod 9 = 3
L
U
C
Ú
N
44 mod 9 = 7 45 mod 9 = 2 46 mod 9 = 6
I I
Ó C 47 mod 9 = 1 48 mod 9 = 5 Si mcd (a,n)  1
N A

15
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.

16
Inversos aditivos y multiplicativos
(A+B) mod 5 (AB) mod 5
B + 0 1 2 3 4 B  0 1 2 3 4
A 0 0 1 2 3 4 A 0 0 0 0 0 0
1 1 2 3 4 0 1 0 1 2 3 4
0+0 = 0
2 2 3 4 0 1 11 = 1 2 0 2 4 1 3
3 3 4 0 1 2 Es trivial 3 0 3 1 4 2
4 4 0 1 2 3 4 0 4 3 2 1
o En la operación suma siempre existirá el inverso o valor identidad
de la adición (0) para cualquier resto del cuerpo.
o En la operación producto, de existir un inverso o valor de identidad
de la multiplicación (1) éste es único. La condición para ello es que
el número y el módulo sean primos entre sí. Por ejemplo para n = 4,
el resto 2 no tendrá inverso multiplicativo, en cambio el resto 3 sí.
17
Conjunto reducido de restos CRR
• El conjunto reducido de restos, conocido como

CRR de n, es el subconjunto {0, 1, ... ni, ... n-1} de
restos primos con el grupo n.
• Si n es primo, todos los restos serán primos con él.
• Como el cero no es una solución, entonces:
CRR = {1, ..., ni, ... n-1} / mcd (ni, n) = 1
Ejemplo: CRR mod 8 = {1, 3, 5, 7}
CRR mod 5 = {1, 2, 3, 4}
18
Utilidad del CRR
¿Qué utilidad tiene esto en criptografía?

El conocimiento del CRR permitirá aplicar un algoritmo
para el cálculo del inverso multiplicativo de un número x
dentro de un cuerpo o grupo n a través de la función (n),
denominada Función de Euler o Indicador de Euler.
Será muy importante tanto en los sistemas
simétricos que trabajan en un módulo (con
excepción del DES) como en los sistemas
asimétricos. En ambos casos la cifra y las
claves están relacionadas con el CRR.
19
Función de Euler (n)
• Función (n) de Euler
• Entregará el número de elementos del CRR.
• Podremos representar cualquier número n de estas
cuatro formas:
– a) n es un número primo.
– b) n se representa como n = pk con p primo y k entero.
– c) n es el producto n = pq con p y q primos.
– d) n es un número cualquiera (genérico).
t
Veamos cada
n = p1e1  p2e2  ...  ptet =  piei uno de ellos
i=1
20
Función (n) de Euler (n = p)
Caso 1: n es un número primo

Si n es primo, (n) será igual a CCR menos el 0.
(n) = n - 1 Se usará en sistemas ElGamal y DSS
Si n es primo, entonces CRR = CCR - 1 ya que todos

los restos de n, excepto el cero, serán primos entre sí.
Ejemplo CRR(7) = {1,2,3,4,5,6} seis elementos
(7) = n - 1 = 7-1 = 6
(11) = 11-1 = 10; (23) = 23-1 = 22

21
Función (n) de Euler (n = pk)
Caso 2: n = pk (con p primo y k un entero)
(n) = (pk) = pk - pk-1 (pk) = pk-1(p-1)

De los pk elementos del CCR, restaremos todos los
múltiplos 1p, 2p, 3p, ...(pk-1-1)p y el cero.
Ejemplo CRR(16) = {1,3,5,7,9,11,13,15} ocho elementos

 (16) = (24) = 24-1(2-1) = 231 = 8
(125) = (53) = 53-1(5-1) = 524 = 254 = 100

22
Función (n) de Euler (n = pq) (1)
Caso 3: n = pq (con p y q primos)
(n) = (pq) = (p)(q) = (p-1)(q-1)

De los pq elementos del CCR, restaremos todos los
múltiplos de p = 1p, 2p, ... (q - 1)p, todos los
múltiplos de q = 1q, 2q, ... (p - 1)q y el cero.
(pq) = pq - (q-1) + (p-1) +1 = pq - q - p + 1
(p-1)(q-1)
23
Función (n) de Euler (n = pq) (2)
Ejemplo CRR(15) = {1,2,4,7,8,11,13,14} ocho elementos

 (15) = (35) = (3-1)(5-1) = 24 = 8
(143) = (1113) = (11-1)(13-1) = 1012 = 120
Será una de las funciones más utilizadas ya

que es la base del sistema RSA que durante
muchos años ha sido un estándar de hecho.

24
Función (n) de Euler (n = genérico)
Caso 4: n = p1e1p2e2 ... ptet (pi son primos)

t
(n) =  piei-1 (pi - 1)

Ejemplo i=1
(demostración no inmediata)
CRR(20) = {1, 3, 7, 9, 11, 13, 17, 19} ocho elementos

 (20) = (22 5) = 22-1(2-1)51-1(5-1) = 21114 = 8
(360) = (23 325) = 23-1(2-1)32-1(3-1)51-1(5-1) = 96

25
Teorema de Euler
Dice que si mcd (a,n) = 1  a(n) mod n = 1
Ahora igualamos ax mod n = 1 y a(n) mod n = 1
 a(n)  a-1 mod n = x mod n

 x = a(n)-1 mod n
El valor x será el inverso de a en el cuerpo n

Nota: Observe que se ha dividido por a en el cálculo anterior.
Esto se puede hacer porque mcd (a, n) = 1 y por lo tanto hay
un único valor inverso en el cuerpo n que lo permite.
26
Cálculo de inversos con Teorema Euler
Ejemplo
¿Cuál es el inverso de 4 en módulo 9?  inv (4, 9)
Pregunta: ¿Existe a  x mod n = 4  x mod 9 = 1?
Como mcd (4, 9) = 1  Sí ... aunque 4 y 9 no son primos.
(9) = 6  x = 46-1 mod 9 = 7  74 = 28 mod 9 = 1
Resulta obvio que: inv (4, 9) = 7 e inv (7, 9) = 4

27
Teorema de Euler para n = pq
Si el factor a es primo relativo con n y n es el

producto de 2 primos, seguirá cumpliéndose el
Teorema de Euler también en dichos primos.
Por ejemplo:
Si n = pq  (n) = (p-1)(q-1) En el capítulo
dedicado a la
 a / mcd {a, (p,q)} = 1 cifra con clave
pública RSA,
se cumple que: relacionaremos
a(n) mod p = 1 este tema con el
Teorema del
a mod q = 1
(n)
Resto Chino.
28
Ejemplo Teorema de Euler para n = pq
Sea n = pq = 711 = 77
(n) = (p - 1)(q - 1) = (7 - 1)(11 - 1) = 610 = 60
Si k = 1, 2, 3, ...
Para a = k7 a(n) mod n = k760 mod 77 = 56
Para a = k11 a(n) mod n = k1160 mod 77 = 22
Para  a  k7,11 a(n) mod n = a60 mod 77 = 1
Y se cumple que:
Para  a  k7,11 a(n) mod p = a60 mod 7 = 1
a(n) mod q = a60 mod 11 = 1
En caso contrario: a(n) mod p = 0
a(n) mod q = 0
29
Teorema de Fermat
Si el cuerpo de trabajo n es un primo p
mcd (a, p) = 1  a(p) mod p = 1
Entonces a  x mod p = 1 y a(n) mod p = 1
Además, en este caso (p) = p-1 por lo que igualando las

dos ecuaciones de arriba tenemos:
 a(p)  a-1 mod p = x mod p
 x = ap-2 mod p
Luego x será e inverso de a en el primo p.

30
¿Qué hacemos si no se conoce (n)?
• Calcular ai mod n cuando los valores de i y a son
grandes, se hace tedioso pues hay que utilizar la
propiedad de la reducibilidad repetidas veces.
• Si no conocemos (n) o no queremos usar el
teorema de Euler/Fermat, siempre podremos
encontrar el inverso de a en el cuerpo n usando el
Algoritmo Extendido de Euclides
Es el método más rápido y práctico

31
Algoritmo Extendido de Euclides AEE
Si mcd (a, n) = 1  a  x mod n = 1  x = inv (a, n)

Luego podemos escribir:
n = C1a + r1 a > r1 Sivolvemos
Si volvemoshacia
hacia
a = C2r1+ r2 r1> r2 atrásdesde
atrás desdeeste
este
valor,obtenemos
valor, obtenemos
r1 = C3r2+ r3 r2> r3
elelinverso
inversode
deaaenen
... ...
elelcuerpo
cuerpon.n.
rn-2 = Cnrn-1 + 1 rn-1> 1
rn-1 = Cn+11 + 0
Concluye el algoritmo
32
Tabla de restos del AEE
Ordenando por restos desde el valor 1 se llega a una expresión

del tipo (k1  n + k2  a) mod n = 1, en donde el inverso de a en
n lo dará el coeficiente k2 puesto que k1  n mod n = 0.
C1 C2 C3 C4 ... Cn-1 Cn Cn+1

n a r1 r2 r3 ... rn-2 rn-1 1
Vuelta hacia atrás
(k1  n + k2  a) mod n = 1
Tabla de restos

33
Cálculo de inversos con el AEE
Encontrar el inv (9, 25) por el método de restos de Euclides.
a) 25 = 29 + 7 7 = 25 - 29 7 = 25 - 29
b) 9 = 17 + 2 2 = 9 - 17 2 = 9 - 1(25 - 29) = 39 -125
c) 7 = 32 + 1 1 = 7 - 32 1 = (25 - 29) - 3(39 -125)
d) 2 = 21 + 0 restos 1 = 425 - 119 mod 25
Tabla de Restos Elinv

El inv(9,25)
(9,25)==-11
-11
2 1 3 2 -11++25
-11 25==14
14
25 9 7 2 1 0 inv(9,
inv (9,25)
25)==14
14

34
Algoritmo para el cálculo de inversos
Para encontrar x = inv (A, B)
x = inv (A, B)
Hacer (g0, g1, u0, u1, v0, v1, i) = (B, A, 1, 0, 0, 1, 1)
x = inv (9, 25)
Mientras gi  0 hacer
i yi gi ui vi
Hacer yi+1 = parte entera (gi-1/gi)
Hacer gi+1 = gi-1 - yi+1 gi 0 - 25 1 0
Hacer ui+1 = ui-1 - yi+1 ui 1 - 9 0 1
Hacer vi+1 = vi-1 - yi+1 vi 2 2 7 1 -2
Hacer i = i+1 3 1 2 -1 3
x = inv (9, 25) = -11+25 = 14
Si (vi-1 < 0)
4 3 1 4 -11
Hacer vi-1 = vi-1 + B
Hacer x = vi-1 Ejemplo 5 2 0 -9 25

35
Características de inversos en n = 27
Para el alfabeto castellano con mayúsculas (n = 27) tenemos:
x inv (x, 27) x inv (x, 27) x inv (x, 27)
1 1 10 19 19 10
2 14 11 5 20 23
4 7 13 25 22 16
5 11 14 2 23 20
7 4 16 22 25 13
8 17 17 8 26 26
27 = 33 luego no existe inverso para a = 3, 6, 9, 12, 15, 18, 21, 24.
inv (x, n) = a  inv (a, n) = x Inversos en sistemas de

cifra clásicos orientados a
inv (1, n) = 1 alfabetos de 27 caracteres.

36
¿Habrá inversos si mcd (a, n)  1?
• ¿Pueden existir inversos?
• No, pero...
• Si a  x mod n = b con b  1 y mcd (a, n) = m, siendo
m divisor de b, habrá m soluciones válidas.
Esto no nos sirve en criptografía ... 
6x mod 10 = 4 mcd (6, 10) = 2
No existe inv (6, 10) pero ... habrá 2 soluciones válidas
x1 = 4  64 mod 10 = 24 mod 10 = 4
x2 = 9  69 mod 10 = 54 mod 10 = 4 ?
37
Teorema del Resto Chino TRC
Si n = d1d2d3 ... dt con di = piei (p primo)

El sistema de ecuaciones:
x mod di = xi (i = 1, 2, 3, ... t)
tiene una solución común en [0, n-1
t
desarrollo
x =  (n/di)yixi mod n
i=1
con yi = inv [(n/di), di

38
Ejemplo de aplicación del TRC (1)
Encontrar x de forma que : 12  x mod 3.960 = 36
Tenemos la ecuación genérica: a  xi mod di = b
n = 3.960  n = 2332511 = d1d2d3d4 = 89511
a = 12
b = 36 Como n  d4, existirán 4 soluciones de xi
ax1 mod d1 = b mod d1 12x1 mod 8 = 36 mod 8 = 4
ax4 mod d4 = b mod4 ecuaciones
d4 12x
en x 4
mod 11 = 36 mod 11 = 3
Resolviendo para xi
39
x1 = 1 x2 = 0
4 ecuaciones en x
x3 = 3 x4 = 3
12x1 mod 8 = 4  4x1 mod 8 = 4  x1 = 1
12x2 mod 9 = 0  3x2 mod 9 = 0  x2 = 0
12x3 mod 5 = 1  2x3 mod 5 = 1  x3 = 3
12x4 mod 11 = 3  1x4 mod 11 = 3  x4 = 3

40
Resolvemos ahora la
y1 = 7 y2 = 8
ecuación auxiliar del
Teorema Resto Chino y3 = 3 y4 = 7
yi = inv [(n/di), di
y1 = inv [(n/d1), d1  y1 = inv[(3960/8),8 = inv (495,8)
y2 = inv [(n/d2), d2  y2 = inv[(3960/9),9 = inv (440,9)
y3 = inv [(n/d3), d3  y3 = inv[(3960/5),5 = inv (792,5)
y4 = inv[(n/d4), d4  y4 = inv[(3960/11),11 = inv(360,11)

41
Aplicando ecuación del Resto
x1 = 1 x2 = 0 Chino para el caso 12  x mod
3.960 = 36 con d1 = 8, d2 = 9, d3 = 5,
x3 = 3 x4 = 3 d4 = 11:
y1 = 7 y2 = 8 tt
xx==(n/d
(n/d)y
ii
)yx x mod n
i i i imod n
y3 = 3 y4 = 7 i=1
i=1
x = [(n/d1)y1x1 + (n/d2)y2x2 + (n/d3)y3x3 + (n/d4)y4x4
x = [49571 + 44080 + 79233 + 36073 mod 3.960
x = [3.465 + 0 + 7.128 + 7.560 mod 3.960 = 2.313

42
¿Todo marcha bien en este ejemplo?
¿Es la solución de 12x mod 3.960 = 36 única?
NO
¿Qué ha sucedido?
Puesto que mcd (a, n) = mcd (12, 3.960) = 12, ya hemos visto
en una diapositiva anterior que habrá 12 soluciones válidas.
x1 = 3; x2 = 333; x3 = 663; x4 = 993 ..... x8 = 2.313 ...

xi = 3 + (i-1)330 mod 3.960 ... hasta llegar a x12 = 3.633
Observe que x = 2.313, uno de los valores solución,
fue el resultado encontrado en el ejercicio anterior.
43
Otros casos de aplicación del TRC
¿Qué sucede ahora con: 12x mod 3.960 = 35

12x mod 3.960 = 35? mcd (a, n) = 12 no es un
divisor de b = 35, luego
aquí no existe solución.
Teníamos que
3.960 = 2332511 Encuentre x como ejercicio
49x mod 3.960 = 1

¿Qué sucede ahora con: Sí existirá x, en este caso es el
inverso de 49, y será único ya que
49x mod 3.960 = 1?
49 = 77 no tiene factores en n.
44
¿Sólo sirve para esto el TRC?
Calcular el inverso de 49 en el cuerpo 3.960 por medio
del Teorema del Resto Chino es algo tedioso .......... 
ya lo habrá comprobado .
No obstante, ya habrá comprobado que en este caso el
inverso de 49 en el cuerpo 3.960 es x = 889.
¿Para qué sirve entonces este algoritmo?

Entre otras cosas, cuando veamos el sistema de cifra
RSA y el tema dedicado a Protocolos Criptográficos,
encontraremos una interesante aplicación del Teorema.

45
Raíz primitiva o generador g de grupo p
• Un generador o raíz primitiva de un número primo
p n es aquel que, elevado a todos los restos del
cuerpo y reducido módulo n, genera todo el grupo.
Así, g es un generador si:  1  a  p-1
ga mod p = b (con 1  b  p-1, todos los b )
Sea p = 3  CCR = {1,2} (el cero no es solución)
Resto 1: no generará nada porque 1k mod p = 1
Resto 2: 21 mod 3 = 2; 22 mod 3 = 1
Luego el 2 es un generador del cuerpo n = 3

46
¿Cuántas raíces hay en un grupo?
• Existen muchos números dentro del CRR que son
generadores del cuerpo ... pero
• Su búsqueda no es fácil ... ¿alguna solución?
• Conociendo la factorización de p-1 (q1, q2, ..., qn)
con qi los factores primos de p-1, diremos que un
número g será generador en p si  qi: Ejemplo
g(p-1)/qi mod p  1 En cambio...

Si algún resultado es igual a 1, g no será generador.
47
Búsqueda de raíces primitivas (1)
BÚSQUEDA DE RAÍCES EN EL CUERPO Z13*
Como p = 13  p-1 = 12 = 223 Generadores en Z13

Luego: q1 = 2 q2 = 3
Si se cumple g(p-1)/qi mod p  1  qi g: 2,
entonces g será un generador de p
2(13-1)/2 mod 13 = 26 mod 13 = 12 Resto 2

2(13-1)/3 mod 13 = 24 mod 13 = 3 El resto 2 es generador
3(13-1)/2 mod 13 = 36 mod 13 = 1 Resto 3
3(13-1)/3 mod 13 = 34 mod 13 = 3 El resto 3 no es generador
48
Generadores en Z13 g: 2, 6, 7,
4(13-1)/2 mod 13 = 46 mod 13 = 1 Resto 4

5(13-1)/2 mod 13 = 56 mod 13 = 12 Resto 5
6(13 -1)/2 mod 13 = 66 mod 13 = 12 Resto 6
7(13-1)/2 mod 13 = 76 mod 13 = 12 Resto 7
49
Generadores en Z13 g: 2, 6, 7, 11
8(13-1)/2 mod 13 = 86 mod 13 = 12 Resto 8

9(13-1)/2 mod 13 = 96 mod 13 = 1 Resto 9
10(13-1)/2 mod 13 = 106 mod 13 = 1 Resto 10
11(13-1)/2 mod 13 = 116 mod 13 = 12 Resto 11
50
Generadores en Z13 g: 2, 6, 7, 11
12(13-1)/2 mod 13 = 126 mod 13 = 1 Resto 12

Latasa
La tasade
degeneradores
generadoresenenelelgrupo
grupopp
aproximadamente==(p-1)/(p-1).
seráaproximadamente
será (p-1)/(p-1).
Porlo
Por lotanto
tantopor
porlo
logeneral
generalelel30%
30%de
delos
los
 =  (12)/12
elementosdel
elementos delConjunto
ConjuntoReducido
Reducidode de
Restosde
Restos deppserá
seráun
ungenerador
generadoren enp.p.  = 4/12 = 1/3

51
Generadores en cuerpos de primos seguros
Un número primo p se dice que es un primo seguro o primo
fuerte si: p = 2p’ + 1 (con p’ también primo).
Por ejemplo:
Si p’ = 11, luego p = 211 + 1 = 23 (es primo y es seguro)
En este caso la tasa de números generadores del cuerpo será
mayor que en el caso anterior (con p = 13 era del 30%).
Probabilidad: pseguro = (p-1)/p-1  ½
Casi la mitad de los números del
Comprobación
grupo serán generadores en p.

52
Comprobación de generadores en p = 2p’+1
p’ = 11; 2p’ = 22; p = 2p’ + 1 = 23 primo seguro

Como 2p’ = p - 1 existirán:
(p’) = p’- 1 elementos de orden (p’) en el CRR
(11) = 10 = {1,2,3,4,5,6,7,8,9,10}
(2p’) = [p’- 1 elementos de orden (p-1) en el CRR
(22) = 10 = {1,3,5,7,9,13,15,17,19,21}
 = (p’- 1)/(p-1) = (p’- 1)/2p’  ½
Sigue

53
Comprobación de generadores en p = 2p’+1
Usando la ecuación g(p-1)/qi mod p

En este caso con q1 = 2 y q2 = 11
g(23-1)/2 mod 23 = g11 mod 23
g(23-1)/11 mod 23 = g2 mod 23
Encontramos los siguientes 10 generadores en p = 23

{5, 7, 10, 11, 14, 15, 17, 19, 20, 21}
Prácticamente la mitad de los valores de CRR que en
este caso es igual a 23 – 1 = 22.

54
Utilidad de la raíz primitiva en criptografía
¿Para qué sirve conocer la raíz primitiva de p?
• La utilidad de este concepto en
criptografía lo veremos cuando ?
se estudien los sistemas de clave
pública y, en particular, el
protocolo de intercambio de
claves de Diffie y Hellman.
• También se recurrirá a esta
propiedad de los primos cuando
estudiemos la firma digital
según estándar DSS (ElGamal).
55
La exponenciación en la cifra asimétrica
 Una de las más interesantes aplicaciones de la
matemática discreta en criptografía es la cifra
asimétrica en la que la operación básica es una
exponenciación AB mod n, en donde n es un
primo o un producto de primos grandes.
 Esta operación se realizará en el intercambio de
clave y en la firma digital.
 ¿Cómo hacer estos cálculos de forma rápida y
eficiente, sin tener que aplicar la reducibilidad?
Tenemos una solución aplicando un algoritmo
de exponenciación rápida.
56
Un método de exponenciación rápida
• En xy mod n se representa el exponente y en binario.
j
• Se calculan los productos x2 con j = 0 hasta n-1, siendo n
el número de bits que representan el valor y en binario.
• Sólo se toman en cuenta los productos en los que en la
posición j del valor y en binario aparece un 1.
Ejemplo
Calcular z = 1237 mod 221 = 207

1237 es un número de 40 dígitos:
8505622499821102144576131684114829934592
57
Ejemplo de exponenciación rápida
Calcular z = 1237 mod 221 = 207 122 mod 221
1442 mod 221
3710 = 1001012 x = 12 j 0 1 2 3 4 5
interesante
j 12 144 183 118 1 1
Bits 5 4 3 2 1 0
x mod 221
2
z = 121831 mod 221 = 207

En vez de 36 multiplicaciones y sus reducciones módulo
221 en cada paso ... 72 operaciones...
Hemos realizado cinco multiplicaciones (para j = 0 el valor
es x) con sus reducciones módulo 221, más dos al final y su
correspondiente reducción. Un ahorro superior al 80% .
58
Algoritmo de exponenciación rápida
Hallar x = AB mod n Ejemplo: calcule 1983 mod 91 = 24
• Obtener representación 8310 = 10100112 = b6b5b4b3b2b1b0
binaria del exponente B x=1
de k bits: i=6 b6=1 x = 1219 mod 91 = 19 x = 19
B2  bk-1bk-2...bi...b1b0 i=5 b5=0 x = 192 mod 91 = 88 x = 88
• Hacer x = 1 i=4 b4=1 x = 882 19 mod 91 = 80 x = 80
• Para i = k-1, ..., 0 hacer i=3 b3=0 x = 802 mod 91 = 30 x = 30
x = x2 mod n i=2 b2=0 x = 302 mod 91 = 81 x = 81
Si (bi = 1) entonces i=1 b1=1 x = 812 19 mod 91 = 80 x = 80
x = xA mod n i=0 b0=1 x = 802 19 mod 91 = 24 x = 24
1983 = 1,369458509879505101557376746718e+106 (calculadora Windows)
59
Cálculos en campos de Galois (GF)
• Cuando trabajamos en un cuerpo primo p, sabemos que se
asegura la existencia de un único inverso multiplicativo.
En este caso se dice que estamos trabajando en Campos
de Galois GF(p).
• Algunos usos en criptografía:
– Sistemas de clave pública cuando la operación de
cifra es C = Me mod p (cifrador ElGamal) o bien RSA
usando el Teorema del Resto Chino para descifrar.
– Aplicaciones en GF(qn), polinomios módulo q y de
grado n: a(x) = an-1xn-1 + an-2xn-2 + ... + a1x + a0:
Cifrador de flujo A5, RIJNDAEL, curvas elípticas.
60
Campos de Galois del tipo GF(qn)
a(x) = an-1xn-1 + an-2xn-2 + ... + a1x + a0

• Es un polinomio de grado n-1 o menor.
• Los elementos ai son parte del CCR del módulo q.
• Cada elemento a(x) es un resto módulo p(x), siendo
p(x) un polinomio irreducible de grado n (que no puede
ser factorizado en polinomios de grado menor que n).
• GF(2n) es interesante porque CCR(2) = {0, 1}  bits.
• GF(23)  8 elementos o restos polinómicos que son:
0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1, los 8 restos de un
polinomio de grado n-1 (n = 3).
61
Suma en campos de Galois GF(2n) 
Si el módulo de trabajo es 2 (con restos = bits 0 y 1), las

operaciones suma y resta serán un OR Exclusivo:
0  1 mod 2 = 1 1  0 mod 2 = 1
CG(22)
0  0 mod 2 = 0 1  1 mod 2 = 0
 0 1 x x+1 Como los resultados deberán
0 0 1 x x+1 pertenecer al cuerpo, aplicaremos
1 1 0 x+1 x Reducción por Coeficientes:
x x x+1 0 1
x+1 x+1 x 1 0
Por ejemplo:
x + (x +1) = 2x + 1 mod 2 = 1
Restos: 0, 1, x, x+1 1 + 1 = 2 mod 2 = 0

62
Producto en campos de Galois GF(2n) 
La operación multiplicación puede entregar elementos

que no pertenezcan al cuerpo, potencias iguales o
mayores que n  Reducción por Exponente.
CG(22) Sea el polinomio irreducible de
 0 1 x x+1
grado n = 2, p(x) = x2 + x + 1
Luego: x2 = x + 1
0 0 0 0 0
1 0 1 x x+1 Por ejemplo:
x 0 x x+1 1 (x + 1)(x + 1) = x2 + 2x + 1
x+1 0 x+1 1 x (x + 1)(x + 1) = (x + 1) + 2x +1
Restos: 0, 1, x, x+1 (x + 1)(x + 1) = 3x + 2 mod 2 = x

63
Operaciones con campos de Galois en AES
 La suma y multiplicación de polinomios dentro de un
cuerpo binario descritas en las dispositivas anteriores,
conforman las operaciones básicas del algoritmo de
cifra Advanced Encryption Algorithm AES, que con
el nombre RIJNDAEL es el estándar mundial desde
finales de 2001, desplazando al ya viejo DES.
 En este caso, se trabaja con 8 bits por lo que las
operaciones se realizan en GF(28). En el capítulo 10
sobre sistemas de cifra con clave secreta encontrará
ejemplos de suma y multiplicación polinómica dentro
de este cuerpo binario.
Fin del Tema 5
64
Cuestiones y ejercicios (1 de 3)
1. ¿Qué significa para la criptografía el homomorfismo de los enteros?
2. Si una función de cifra multiplica el mensaje por el valor a dentro
del cuerpo n, para qué nos sirve conocer el inverso de a en n?
3. En un cuerpo de cifra n, ¿existen siempre los inversos aditivos y los
inversos multiplicativos? ¿Debe cumplirse alguna condición?
4. Si en un cuerpo n el inverso de a es a –1, ¿es ese valor único?
5. Cifraremos en un cuerpo n = 131. ¿Cuál es el conjunto completo de
restos? ¿Cuál es el conjunto reducido de restos?
6. Para cifrar un mensaje M = 104 debemos elegir el cuerpo de cifra
entre el valor n = 127 y n = 133, ¿cuál de los dos usaría y por qué?
7. ¿Qué nos dice la función (n) de Euler?
8. ¿Qué papel cumple el algoritmo extendido de Euclides en la
criptografía? ¿Por qué es importante? ¿En qué se basa?
65
9. Si en el cuerpo n = 37 el inv (21, 37) = 30, ¿cuál es el inv (30, 37)?
10. Usando el algoritmo extendido de Euclides calcule los siguientes
inversos: inv (7, 19); inv (21, 52), inv (11, 33), inv (41, 43).
11. ¿Cuántas soluciones xi hay a la expresión 8x mod 20 = 12?
Explique lo que sucede. ¿Tiene esto interés en criptografía?
12. ¿Qué viene a significar el Teorema del Resto Chino? Aunque aún
no lo ha estudiado, ¿le ve alguna utilidad en criptografía?
13. Calcule inv (49, 390) usando el Teorema del Resto Chino.
14. Defina lo que es una raíz primitiva o generador de un cuerpo. ¿Es
necesario que ese cuerpo sea un primo?
15. ¿Cuántos generadores podemos esperar en el cuerpo n = 17? Y si
ahora n = 7, ¿cuántos generadores habrá? Compruébelo calculando
todos los exponentes del conjunto completo de restos de n = 7.
66
16. ¿Cómo se define un primo seguro? ¿Cuántos generadores tiene?
17. A partir de los valores p’ = 13, p’ = 17, p’ = 19 y p’ = 23 queremos
obtener un primo seguro, ¿con cuál o cuáles de ellos lo logramos?
18. Usando el algoritmo de exponenciación rápida calcule los siguientes
valores: 2332 mod 51; 100125 mod 201; 1.000100.000 mod 2.500.
19. Compruebe los resultados con la calculadora de Windows. ¿Qué
sucede para números muy grandes como el último?
20. ¿Cuántas operaciones básicas se han hecho en cada caso y en
cuánto se ha optimizado el cálculo?
21. En GF(2n) reduzca por coeficientes 5x5 + x4 + 2x3 + 3x2 + 6x + 2.
22. Reduzca (x3 + 1)(x2 + x +1) por exponente en GF(2n) usando como
polinomio primitivo p(x) = x4 + x + 1, es decir x4 = x + 1.

67

SItema 05

Cargado por

Copyright:

Formatos disponibles

SItema 05

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

SItema 05

Cargado por

Copyright:

Formatos disponibles

Tema 5

Teoría de los Números

Seguridad Informática y Criptografía

Ultima actualización: 03/03/03

Material Docente de Jorge Ramió Aguirre

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

• Es la base matemática (matemáticas discretas) en

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

¿Es 18 congruente con 3 módulo 5?

Esta operación en Zn se expresará así:

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

Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva 4

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

Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva 5

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

a  (a-1) mod n = 1 (si a  0) No siempre existe

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

CCR (6) = {0, 1, 2, 3, 4, 5} = {12, 7, 20, 9, 16, 35}

Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva 7

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

Enteros Enteros mod n

Esta operación ... esta otra

op (y posterior reducción mod n) op

Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva 8

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

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

mcd (148, 40) 148 = 22  37 mcd (385, 78)

148 = 3  40 + 28 40 = 23  5 385 = 4  78+ 73

• En criptografía deberá estar permitido invertir una

 No siempre existen los inversos multiplicativos. En

Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva

Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva

¿Y si no hay primalidad entre a y n?

• El conjunto reducido de restos, conocido como

¿Qué utilidad tiene esto en criptografía?

Caso 1: n es un número primo

(n) = n - 1 Se usará en sistemas ElGamal y DSS

Si n es primo, entonces CRR = CCR - 1 ya que todos

Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva

Caso 2: n = pk (con p primo y k un entero)

(n) = (pk) = pk - pk-1 (pk) = pk-1(p-1)

Ejemplo CRR(16) = {1,3,5,7,9,11,13,15} ocho elementos

Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva

Caso 3: n = pq (con p y q primos)

(n) = (pq) = (p)(q) = (p-1)(q-1)

Ejemplo CRR(15) = {1,2,4,7,8,11,13,14} ocho elementos

Será una de las funciones más utilizadas ya

Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva

Caso 4: n = p1e1p2e2 ... ptet (pi son primos)

(n) =  piei-1 (pi - 1)

CRR(20) = {1, 3, 7, 9, 11, 13, 17, 19} ocho elementos

Seguridad Informática y Criptografía. Tema 5: Teoría de los Números Diapositiva

 a(n)  a-1 mod n = x mod n

El valor x será el inverso de a en el cuerpo n

¿Cuál es el inverso de 4 en módulo 9?  inv (4, 9)

Pregunta: ¿Existe a  x mod n = 4  x mod 9 = 1?

Como mcd (4, 9) = 1  Sí ... aunque 4 y 9 no son primos.

(9) = 6  x = 46-1 mod 9 = 7  74 = 28 mod 9 = 1

Resulta obvio que: inv (4, 9) = 7 e inv (7, 9) = 4