Teoria de Nombres
“Curs d'Introducció a la criptografia”
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ó: $\mathbb{Z}$ és el conjunt (infinit) dels enters
$\mathbb{Z} = \{\dotsc, -3,-2,-1,0,1,2,3,\dotsc\}$
Operacions sobre $\mathbb{Z}$
$+$, $-$, $\times$, $\text{div}$
$a, b \in \mathbb{Z}$ i $b \neq 0$ llavors:
$\begin{aligned} a \text{ div } b &= \lfloor a/b\rfloor \leftarrow \text{quocient }q\text{, dividend }a\text{, divisor }b\\ a \bmod b &= a - b\lfloor a/b\rfloor \leftarrow \text{residu } r\;(0 \leq r < b) \end{aligned}$
o sigui:
$\begin{aligned} a &= qb + r \\ a &= (a \text{ div } b)b + (a \bmod b) \end{aligned}$
Fets
Diem que $c$ és un divisor comú a $a$ i a $b$ si $c|a$ i $c|b$
El màxim comú divisor d'$a$ i $b$ és
$d = \text{mcd}(a,b)$
si $d$ és el valor màxim que $d|a$ i $d|b$
Fet: Teorema fonamental de l'aritmètica
Tot enter $n$ pot factoritzar-se (descomposar-se) en el producte de potències de nombres primers:
$n = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$ amb $(e_i \geq 0)$
i aquesta descomposició és única
Definicions
Diem que $a$ i $b$ són coprimers si $\text{mcd(a,b)} = 1$
Diem que $p$ és un nombre primer si només és divisible per $1$ i per $p$
$\mathbb{Z}_n$
Definició: $\mathbb{Z}_n$ és el conjunt (finit) d'enters mòdul $n$
$\mathbb{Z}_n = \{0,1,2,3,\dotsc,n-1\}$
Operacions sobre $\mathbb{Z}_n$
$+$, $-$, $\times$, $\text{div}$
$+$, $-$, $\times$ equivalents a les definides/conegudes a $\mathbb{Z}$
Per la divisió, el que farem és primer invertir el divisor, i després multiplicar
$\begin{aligned} a \text{ div } b &\equiv a{b}^{-1} \pmod n \end{aligned}$
$b$ no sempre tindrà inversa: en cas de no tenir-ne, la divisió no estarà definida per $b$
congruent
$a \equiv b \pmod n$
$a$ és congruent mòdul $n$ amb $b$ sii:
$a \bmod n = b \bmod n$
ò $n|(a-b)$
Exemple:
$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ó: sent $p$ un nombre primer, $\mathbb{Z}_p^*$ és el subconjunt d'elements de $\mathbb{Z}_p$ que són invertibles mòdul $p$
$\mathbb{Z}_p^* = \{1,2,3,\dotsc,p-1\}$
(o sigui, tot $\mathbb{Z}_p$ menys el $0$;
això és el grup multiplicatiu de $\mathbb{Z}_p$)
Exemple:
$\mathbb{Z}_{5}^* = \{1,2,3,4\}$
en cambio:
$\mathbb{Z}_{5} = \{0,1,2,3,4\}$
Operacions sobre $\mathbb{Z}_p^*$
(amb $p$ primer)
$+$, $-$, $\times$, $\text{div}$
$+$, $-$, $\times$ equivalents a les definides/conegudes a $\mathbb{Z}_n$
Per la divisió, el que farem és primer invertir el divisor, i després multiplicar
$\begin{aligned} a \text{ div } b &\equiv a{b}^{-1} \pmod p \end{aligned}$
$b$ sempre té inversa per definició (ja que hem eliminat el $0$)
Teorema "petit" de Fermat
el segle XVII Fermat va veure que
si multiplicava "$p$ vegades" qualsevol número enter $a$ amb si mateix, el resultat
era divisible per $p$ a condició que $p$ fos un nombre primer.
És a dir que:
$a^p \equiv a \pmod p$
e.g. per $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 primalitat de Fermat
A partir del teorema petit de Fermat, podem deduir un algorisme per a provar si un nombre és primer o no.
Sigui $n$ un enter, per saber si és primer prenem un conjunt prou alt de nombres i provem si el teorema "petit" es compleix:
$\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 primalitat de ...
El problema és que hi ha nombres no primers que són "vàlids" segons el test
per qualsevol valor d'$a$:
són els "mentiders" de Fernat o nombres de Carmichael
Tot i que la probabilitat de topar amb un nombre "mentider" de Fermat és baixa
(molt baixa), per a obtenir nombres primers de forma fiable hi ha algorismes
que refinen aquest i són més robustos com el
test de primalitat de Rabin-Miller
Generalització 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ó: $\mathbb{Z}_n^*$ és $\mathbb{Z}_n$ excloent els $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$ i $n$ coprimers $\}$
(això se'n diu grup multiplicatiu de $\mathbb{Z}_n$)
Exemple:
$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$
en canvi:
$\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$
Operacions sobre $\mathbb{Z}_n^*$
$+$, $-$, $\times$, $\text{div}$
$+$, $-$, $\times$ equivalents a les definides/conegudes a $\mathbb{Z}_n$
Per la divisió, el que farem és primer invertir el divisor, i després multiplicar
$\begin{aligned} a \text{ div } b &\equiv a{b}^{-1} \pmod p \end{aligned}$
$b$ sempre té inversa per definició
(versió generalitzada del cas anterior $\mathbb{Z}_p^*$)
Definició: $\; \phi(n)$
Funció "phi" d'Euler o funció Totient d'Euler
$\phi(n)$ es el nombre de valors
coprimers amb $n$
Per tant: $\phi(n) = |\mathbb{Z}_n^*|$
(traduït: $\phi(n)$ és el nombre d'elements de $\mathbb{Z}_n^*$; la seva mida o
ordre)
Càlcul: $\; \phi(n)$
Per a $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})$
Per a calcular $\phi(n)$ cal conèixer la factorització d'$n$
Casos particulars:
Sii $p$ primer: $\phi(p)=p-1$
Sii $p$ i $q$ primers: $\phi(pq)=(p-1)(q-1)$
Exemples
$\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 d'Euler
Euler un segle després va generalitzar el
teorema "petit" de Fermat
\[ a^{\phi(n)} \equiv 1 \pmod{n} \]
Teorema d'Euler:
extén el petit de Fermat
Tenint en compte que $\phi(p) = p-1$ (per a $p$ primer), podem particularitzar el teorema d'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} $
Per tant, el teorema petit de Fermat és un cas particular del teorema d'Euler per a valors d'$n$ primers
Generalització del T d'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íclics
DSA $\rightarrow$
DH $\rightarrow$
per a criptografia en fem prou amb $\mathbb{Z}_p^*$ cíclics (amb $p$ primer)
Definició: Ordre $\text{ord}(a)$
l'ordre d'un $a \in \mathbb{Z}_n^*$ és el menor valor de $t$ que:
$a^t \equiv 1 \pmod n$
Com que $a^{\phi(n)} \equiv 1 \pmod n$, llavors:
$t \leq \phi(n)$
i per tant:
$t|\phi(n)$
Nota: no confondre l'ordre d'un element de $\mathbb{Z}_n^*$ amb l'ordre de $\mathbb{Z}_n^*$:
$|\mathbb{Z}_n^*| = \phi(n)$
Exemple: $\;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$ |
Fixem-nos que $\phi(21)=(3-1)(7-1)=12$
i que $\text{ord}(a)|12 \quad \forall a \in \mathbb{Z}_{21}^*$
Generador $\alpha$
Diem que $\alpha$ és un generador de $\mathbb{Z}_n^*$ si:
$\text{ord}(\alpha) = |\mathbb{Z}_n^*| = \phi(n)$
sii $\mathbb{Z}_n^*$ té al menys un generador, diem que $\mathbb{Z}_n^*$ és cíclic
e.g. l'anterior grup $\mathbb{Z}_{21}^*$ no era cíclic ja que cap $a$ tenia ordre $12$ ($\phi(21) = 12$)
Exemple: $\;a \in \mathbb{Z}_{9}^*$
| $a$ | $1$ | $2$ | $4$ | $5$ | $7$ | $8$ |
| $\text{ord}(a)$ | $1$ | $6$ | $3$ | $6$ | $3$ | $2$ |
Fixem-nos que $\phi(9)=9(1-1/3)=6$
i que $\text{ord}(a)|6 \quad \forall a \in \mathbb{Z}_{9}^*$
com que hi ha al menys un element amb ordre $6$ (n'hi ha dos, el $2$ i el $5$), tenim generadors i per tant, $\mathbb{Z}_{9}^*$ és cíclic
Per a $\mathbb{Z}_{n}^*$ cíclic amb generador $\alpha$
es compleix que:
$\mathbb{Z}_{n}^* = \{\alpha^i \pmod n \; | \; 0 \leq i < \phi(n)\}$
tenim el conjunt original (simplement ordenat diferent)
Fet: $\;\mathbb{Z}_{n}^*$ és cíclic…
…sii $n = 2,4,p^k, 2p^k$ per a tot primer $p \geq 3$
Exemple: $\;\mathbb{Z}_{9}^*$
Recordem que són generadors $2$ i $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$
Exemple: $\mathbb{Z}_{11}^*$
Són generadors $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)Exemple: $\mathbb{Z}_{11}^*$
No són generadors $1$, $3$, $4$, $5$ i $9$ i $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$
Fet: nombre de generadors
El nombre de generadors de $\mathbb{Z}_{n}^*$ és $\phi(\phi(n))$
Per això el que es fa és escollir primers amb un nombre gran de generadors com els
de la forma $p = 2q+1$
(per a $q$ també primer), donat que
$\begin{aligned} \phi(\phi(p)) & = \phi(p-1) = \phi(2q) = \\ & = \phi(2)\phi(q) = 1·(q-1) = q-1 \end{aligned}$
La meitat dels elements són generadors, ja que $q/p \approx 1/2$
A la pràctica és busca un primer $q$, i després es mira si $2q+1$ és també primer
Selecció del generador $\alpha$...
...pel cas $\mathbb{Z}_{p}^*$ que és el que aplica a DH i DSA es
fa servir $p = 2q+1$ amb $q$ també primer
llavors, agafa un $ 2 \leq \alpha < p-1$ aleatori:
$\alpha^{{p-1}/q} \not\equiv 1 \pmod p$
si és congruent $1$ cal buscar una altre $\alpha$
(amb un o dos intents trobarem el generador)