Teoría de Números
“Curso de Introducción a la Criptografía”
by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto
$\mathbb{Z}$
Definición: $\mathbb{Z}$ es el conjunto (infinito) de los enteros
$\mathbb{Z} = \{\dotsc, -3,-2,-1,0,1,2,3,\dotsc\}$
Operaciones sobre $\mathbb{Z}$
$+$, $-$, $\times$, $\text{div}$
$a, b \in \mathbb{Z}$ y $b \neq 0$ entonces:
$\begin{aligned} a \text{ div } b &= \lfloor a/b\rfloor = q \leftarrow \text{cociente }q\text{, dividendo }a\text{, divisor }b\\ a \bmod b &= a - b\lfloor a/b\rfloor = a - qb = r \leftarrow \text{resto } r\;(0 \leq r < b) \end{aligned}$
o sea:
$\begin{aligned} a &= qb + r \\ a &= (a \text{ div } b)b + (a \bmod b) \end{aligned}$
Hechos
Decimos que $c$ es un divisor común a $a$ y a $b$ si $c|a$ y $c|b$
El máximo común divisor de $a$ y $b$ es
$d = \text{mcd}(a,b)$
si $d$ es el valor máximo que cumple $d|a$ y $d|b$
Hecho: Teorema fundamental de la aritmética
Todo entero $n$ se puede factorizar (descomponerse) en el producto de potencias de números primos:
$n = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$ con $(e_i \geq 0)$
y esta descomposición es única
Definiciones
Decimos que $a$ y $b$ son coprimos si $\text{mcd(a,b)} = 1$
Decimos que $p$ es un número primo si solo es divisible por $1$ y por $p$
$\mathbb{Z}_n$
Definición: $\mathbb{Z}_n$ es el conjunto (finito) de enteros módulo $n$
$\mathbb{Z}_n = \{0,1,2,3,\dotsc,n-1\}$
Operaciones sobre $\mathbb{Z}_n$
$+$, $-$, $\times$, $\text{div}$
$+$, $-$, $\times$ equivalentes a las definidas/conocidas en $\mathbb{Z}$
$\text{suma: } (a+b) \bmod n$
$\text{resta: } (a-b) \bmod n$
$\text{mult: } (a\times b) \bmod n$
$\text{div: } (a \text{ div } b) \bmod n$
la división no estará bien definda para todo $b$: hace falta que $b$ tenga "inverso $\pmod n$"
$\text{inverso: } b^{-1} \bmod n$
$b$ tiene inverso $\pmod n$
sii $b$ y $n$ son comprimos
el cálculo del inverso módulo $n$ es eficiente mediante el algoritmo de Euclides (para $\text{mcd}$) ampliado
congruente
$a \equiv b \pmod n$
$a$ es congruente módulo $n$ con $b$ sii:
$a \bmod n = b \bmod n$
ó $n|(a-b)$
Ejemplo:
$173 \equiv 3 \pmod{10}$ ó $10|(173-3)$
$73 \equiv 173 \pmod{10}$ ó $10|(73-173)$
$73 \not\equiv 2 \pmod{10}$
$\mathbb{Z}_p^*$
Definición: siendo $p$ un número primo, $\mathbb{Z}_p^*$ es el subconjunto de elementos de $\mathbb{Z}_p$ que son invertibles módulo $p$
$\mathbb{Z}_p^* = \{1,2,3,\dotsc,p-1\}$
(o sea, todo $\mathbb{Z}_p$ menos el $0$;
esto es el grupo multiplicativo de $\mathbb{Z}_p$)
Ejemplo:
$\mathbb{Z}_{5}^* = \{1,2,3,4\}$
en cambio:
$\mathbb{Z}_{5} = \{0,1,2,3,4\}$
Operaciones sobre $\mathbb{Z}_p^*$
(con $p$ primo)
$\times$, $\text{div}$
$\times$ equivalente a la definida/conocida en $\mathbb{Z}_n$
Para la división, lo que haremos primero es invertir el divisor, y después multiplicar
$\begin{aligned} a \text{ div } b &\equiv a{b}^{-1} \pmod p \end{aligned}$
$b$ siempre tiene inversa por definición (ya que hemos eliminado el $0$)
Nota: $+$, $-$, están "mal definidos" ahora (pero no los usaremos)
Teorema "pequeño" de Fermat
el siglo XVII Fermat vió que
si multiplicaba "$p$ veces" cualquier número entero $a$ por sí mismo, el resultado
era divisible por $p$ con la condición que $p$ fuese un número primo.
Es decir que:
$a^p \equiv a \pmod p$
e.g. para $a = 2$
$\begin{aligned} \mathbb{Z}_{3}^{*} \implies &2^{3} = 8 = 3·2+2 \equiv 2 \pmod{3} \\ \mathbb{Z}_{5}^{*} \implies &2^{5} = 32 = 5·6+2 \equiv 2 \pmod{5} \\ \mathbb{Z}_{7}^{*} \implies &2^{7} = 128 = 7·18+2 \equiv 2 \pmod{7} \\ & \vdots \end{aligned}$
Test de primalidad de Fermat
A partir del teorema pequeño de Fermat, podemos deducir un algoritmo para probar si un número primo o no.
Sea $n$ un entero, para saber si es primo tomamos un conjunto suficientemente grande de números y probamos si el teorema pequeño de Fermat se cumple:
$\begin{aligned} 2^{n} & \overset{?}{\equiv} 2 \pmod n & \qquad \vdots \\ 3^{n} & \overset{?}{\equiv} 3 \pmod n & a^{n} & \overset{?}{\equiv} a \pmod n \\ 4^{n} & \overset{?}{\equiv} 4 \pmod n \end{aligned}$
Test de primalidad de …
El problema es que hay números no primos que son "válidos" según el test
para cualquier valor de $a$:
son los "mentirosos" de Fermat o números de Carmichael
Aunque la probabilitat de topar con un número "mentiroso" de Fermat es baja
(muy baja), para obtener números primos de forma fiable hay algoritmos
que los refinan y son más robustos, como el
test de primalidad de Rabin-Miller
Generalización del TP de Fermat
\[ \begin{aligned} a^{p} & \equiv a \pmod p \\ a^{p-1} & \equiv 1 \pmod p \\ (a^{p-1})^{t} & \equiv 1^t \pmod p \\ (a^{p-1})^{t} & \equiv 1 \pmod p \\ a^{t(p-1)} & \equiv 1 \pmod p \\ a^{t(p-1)}a^r & \equiv a^r \pmod p \\ a^{t(p-1)+r} & \equiv a^r \pmod p \\ \end{aligned} \]
$a^{x} \equiv a^{y} \pmod p $ si $ x \equiv y \pmod{p-1}$
$\mathbb{Z}_n^*$
Definición: $\mathbb{Z}_n^*$ es $\mathbb{Z}_n$ excluyendo los $n$ no invertibles
$\mathbb{Z}_n^* = \{a \in \mathbb{Z}_n \; | \; a$ invertible $\}$
$\mathbb{Z}_n^* = \{a \in \mathbb{Z}_n \; | \; \text{mcd}(a,n) = 1\}$
$\mathbb{Z}_n^* = \{a \in \mathbb{Z}_n \; | \; a$ y $n$ coprimos $\}$
(esto se denomina grupo multiplicativo de $\mathbb{Z}_n$)
Ejemplo:
$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$
en cambio:
$\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$
Operaciones sobre $\mathbb{Z}_n^*$
$\times$, $\text{div}$
$\times$ equivalente a la definida/conocida en $\mathbb{Z}_n$
Para la división, lo que haremos primero es invertir el divisor, y luego multiplicar
$\begin{aligned} a \text{ div } b &\equiv a{b}^{-1} \pmod p \end{aligned}$
$b$ siempre tiene inversa por definición
(versión generalizada del caso anterior $\mathbb{Z}_p^*$)
Nota: $+$, $-$, están "mal definidos" ahora (pero no los usaremos)
Definición: $\; \phi(n)$
Función "phi" de Euler o función Totient de Euler
$\phi(n)$ es la cantidad de valores
coprimos con $n$
Por tanto: $\phi(n) = |\mathbb{Z}_n^*|$
(traducido: $\phi(n)$ es el número de elementos de $\mathbb{Z}_n^*$)
Cálculo: $\; \phi(n)$
Para $n = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$
$\phi(n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})$
Para calcular $\phi(n)$ hace falta la factorización de $n$
Casos particulares:
Sii $p$ primo: $\phi(p)=p-1$
Sii $p$ y $q$ primos: $\phi(pq)=(p-1)(q-1)$
Ejemplos
$\begin{aligned} |\mathbb{Z}_{17}^*| &= |\{1,2,3,4,5, \dotsc,15,16\}| = \phi(17) = (17-1) = 16 \\ |\mathbb{Z}_{16}^*| &= |\{1,3,5,7,9,11,13,15\}| = \phi(16) = 16(1-1/2) = 16/2 = 8 \\ |\mathbb{Z}_{15}^*| &= |\{1,2,4,7,8,11,13,14\}| = \phi(15) = (5-1)(3-1) = 8 \end{aligned}$
Teorema de Euler
Euler un siglo después generalizó el
teorema "pequeño" de Fermat
\[ a^{\phi(n)} \equiv 1 \pmod{n} \]
Teorema de Euler:
extiende el pequeño de Fermat
Teniendo en cuenta que $\phi(p) = p-1$ (para $p$ primo), podemos particularizar el teorema de Euler:
$\begin{aligned} a^{\phi(p)} &\equiv 1 \pmod p \\ a^{p-1} &\equiv 1 \pmod p \\ a^p &\equiv a \pmod p \\ \end{aligned} $
Por tanto, el teorema pequeño de Fermat es un caso particular del teorema de Euler para valores de $n$ primos
Generalización del T de Euler
\[ \begin{aligned} a^{\phi(n)} & \equiv 1 \pmod n \\ (a^{\phi(n)})^{t} & \equiv 1^t \pmod n \\ (a^{\phi(n)})^{t} & \equiv 1 \pmod n \\ a^{t\phi(n)} & \equiv 1 \pmod n \\ a^{t\phi(n)}a^r & \equiv a^r \pmod n \\ a^{t\phi(n)+r} & \equiv a^r \pmod n \\ \end{aligned} \]
$a^{x} \equiv a^{y} \pmod n$ si $x \equiv y \pmod{\phi(n)}$
$\mathbb{Z}_n^*$ cíclicos
DSA $\rightarrow$
DH $\rightarrow$
para uso en criptografia nos bastan los $\mathbb{Z}_p^*$ cíclicos (con $p$ primos)
Definición: Orden $\text{ord}(a)$
el orden de un $a \in \mathbb{Z}_n^*$ es el menor valor de $t$ que:
$a^t \equiv 1 \pmod n$
Como que $a^{\phi(n)} \equiv 1 \pmod n$, entonces:
$t \leq \phi(n)$
y por tanto:
$t|\phi(n)$
Ejemplo: $\;a \in \mathbb{Z}_{21}^*$
| $a$ | $1$ | $2$ | $4$ | $5$ | $8$ | $10$ | $11$ | $13$ | $16$ | $17$ | $19$ | $20$ |
| $\text{ord}(a)$ | $1$ | $6$ | $3$ | $6$ | $2$ | $6$ | $6$ | $2$ | $3$ | $6$ | $6$ | $2$ |
Fijémonos que $\phi(21)=(3-1)(7-1)=12$
y que $\text{ord}(a)|12 \quad \forall a \in \mathbb{Z}_{21}^*$
Generador $\alpha$
Decimos que $\alpha$ es un generador de $\mathbb{Z}_n^*$ si:
$\text{ord}(\alpha) = |\mathbb{Z}_n^*| = \phi(n)$
sii $\mathbb{Z}_n^*$ tiene al menos un generador, decimos que $\mathbb{Z}_n^*$ es cíclico
e.g. el anterior grupo $\mathbb{Z}_{21}^*$ no era cíclico ya que ningún $a$ tenía
orden $12$ ($\phi(21) = 12$)
Ejemplo: $\;a \in \mathbb{Z}_{9}^*$
| $a$ | $1$ | $2$ | $4$ | $5$ | $7$ | $8$ |
| $\text{ord}(a)$ | $1$ | $6$ | $3$ | $6$ | $3$ | $2$ |
Fijémonos que $\phi(9)=9(1-1/3)=6$
y que $\text{ord}(a)|6 \quad \forall a \in \mathbb{Z}_{9}^*$
como que hay al menos un elemento con orden $6$ (hay dos, el $2$ y el $5$), tenemos generadores y por tanto, $\mathbb{Z}_{9}^*$ es cíclico
Para $\mathbb{Z}_{n}^*$ cíclico con generador $\alpha$
se cumple que:
$\mathbb{Z}_{n}^* = \{\alpha^i \pmod n \; | \; 0 \leq i < \phi(n)\}$
tenemos el conjunto original (simplemente ordenado de forma diferente)
Hecho: $\;\mathbb{Z}_{n}^*$ es cíclico…
…sii $n = 2,4,p^k, 2p^k$ para todo primo $p \geq 3$
Ejemplo: $\;\mathbb{Z}_{9}^*$
Recordemos que son generadores $2$ y $5$
$\mathbb{Z}_{9}^* = \{1,2,4,5,7,8\}$
$2^i \pmod 9 = \{2,4,8,7,5,1\} \; | \; 1 \leq i \leq \phi(9)=6$
$5^i \pmod 9 = \{5,7,8,4,2,1\} \; | \; 1 \leq i \leq \phi(9)=6$
Ejemplo: $\mathbb{Z}_{11}^*$
Son generadores $2$, $6$, $7$ i $8$
$\mathbb{Z}_{11}^* = \{1,2,3,4,5,6,7,8,9,10\}$
$\phi(11)=10$
$2^i \pmod{11} = \{2,4,8,5,10,9,7,3,6,1\} \; | \; 1 \leq i \leq 10$
$6^i \pmod{11} = \{6,3,7,9,10,5,8,4,2,1\} \; | \; 1 \leq i \leq 10$
$7^i \pmod{11} = \{7,5,2,3,10,4,6,9,8,1\} \; | \; 1 \leq i \leq 10$
$8^i \pmod{11} = \{8,9,6,4,10,3,2,5,7,1\} \; | \; 1 \leq i \leq 10$
(Contra)Ejemplo: $\mathbb{Z}_{11}^*$
No son generadores $1$, $3$, $4$, $5$, $9$ y $10$
$\mathbb{Z}_{11}^* = \{1,2,3,4,5,6,7,8,9,10\}$
$1^i \pmod{11} = \{1,1,1,1,1,1,1,1,1,1\} \; | \; 1 \leq i \leq 10$
$3^i \pmod{11} = \{3,9,5,4,1,3,9,5,4,1\} \; | \; 1 \leq i \leq 10$
$4^i \pmod{11} = \{4, 5, 9, 3, 1, 4, 5, 9, 3, 1\} \; | \; 1 \leq i \leq 10$
$5^i \pmod{11} = \{5, 3, 4, 9, 1, 5, 3, 4, 9, 1\} \; | \; 1 \leq i \leq 10$
$9^i \pmod{11} = \{9, 4, 3, 5, 1, 9, 4, 3, 5, 1\} \; | \; 1 \leq i \leq 10$
$10^i \pmod{11} = \{10, 1, 10, 1, 10, 1, 10, 1,10, 1\} \; | \; 1 \leq i \leq 10$
Hecho: número de generadores
El número de generadores de $\mathbb{Z}_{n}^*$ es $\phi(\phi(n))$
Es por eso que lo que se hace es escoger primos con una gran cantidad de generadores como los
de la forma $p = 2q+1$
(para $q$ también primo), dado que
$\begin{aligned} \phi(\phi(p)) & = \phi(p-1) = \phi(2q) = \\ & = \phi(2)\phi(q) = 1·(q-1) = q-1 \end{aligned}$
La mitad de los elementos son generadores, ya que $q/p \approx 1/2$
En la práctica se busca un primo $q$, y luego se mira si $2q+1$ es también primo
Selección del generador $\alpha$ …
…para el caso $\mathbb{Z}_{p}^*$ que es el que aplica a DH y DSA se
usa $p = 2q+1$ con $q$ también primo
entonces, coge un $2 \leq \alpha < p-1$ aleatorio:
$\alpha^{q} \equiv -1 \pmod p$
si no es cierto, hace falta buscar otro $\alpha$
(en uno o dos intentos encontraremos un generador)