Siguiente: Encriptamiento Un nivel arriba: Método de llave pública Anterior: Método de llave pública

Algoritmos básicos

Un resultado clásico de Teoría de Números es el:

Teorema Pequeño de Fermat. Si p es primo y $a\in I\!\!N$ no es divisible entre p, entonces $a^{p-1}\mbox{\rm mod }p=1$.

Sean p,q dos números primos, y sea $n=p\cdot q$ su producto. Por el teorema de Fermat, se tiene que para cualquier $x\not=0$,

$$x^{p-1}\mbox{\rm mod }p=1 \hspace{3em}\mbox{\rm y }\hspace{3em} x^{q-1}\mbox{\rm mod }q=1,$$

consecuentemente

$$x^{(p-1)(q-1)}\mbox{\rm mod }p=1 \hspace{3em}\mbox{\rm y }\hspace{3em} x^{(p-1)(q-1)}\mbox{\rm mod }q=1.$$

Es decir

$$p\left\vert (x^{(p-1)(q-1)}-1)\right. \hspace{3em}\mbox{\rm y }\hspace{3em} q\left\vert (x^{(p-1)(q-1)}-1)\right..$$

Así pues, $n\left\vert (x^{(p-1)(q-1)}-1)\right.$. Es decir, .

El teorema de Fermat puede plantearse de manera más general. Se dice que dos números enteros n y m son primos relativos si no tienen factores comunes, es decir, si $\mbox{\rm m.c.d.}(n,m)=1$.

La función de Euler es

$$\phi:n\mapsto \mbox{\rm card}\{m\leq n\vert m\mbox{\rm es primo relativo con }n\}.$$

Entre las propiedades más importantes de esta función están:

• Si p es primo, entonces $\phi(p) = p-1$.
• $\phi$ es multiplicativa, es decir, si m y n son primos relativos entonces $\phi(mn) = \phi(m) \phi(n)$.
• Si p es primo y $r\in I\!\!N$, entonces $\phi(p^r) = p^{r-1}(p-1)$.
• ${\displaystyle \limsup_{n\to +\infty} \frac{\phi(n)}{n}=1}$.
• ${\displaystyle \liminf_{n\to +\infty} \frac{\phi(n)\ln(\ln(n))}{n}=e^{-\gamma}}$, donde $\gamma=0.577215\ldots$ es la, así llamada, constante de Euler.

Teorema Pequeño de Fermat (bis). Si n es un entero no-nulo y $a\in I\!\!N$ es primo relativo con n, entonces $a^{\phi(n)}\mbox{\rm mod }n=1$.

Además, dado que la función ``módulo'' es un homomorfismo, se tiene

$$r\mbox{\rm mod }\phi(n)=s\ \Rightarrow\ a^r\mbox{\rm mod }n=a^s.$$

Consecuentemente, si e,d son enteros tales que $e\cdot d\mbox{\rm mod }(p-1)(q-1)=1$ se tiene que: $a^{ed}\mbox{\rm mod }n = a$.

Esta es la base del algoritmo de encriptamiento: Si a es el mensaje, se hace c=a^c su cifrado. Entonces, c^d=m.

 

La pareja (n,e) es la llave, que puede hacerse pública.

La llave secreta es (n,d).

Para calcular d sabiendo e, es necesario conocer la factorización de n como producto de los dos primos p y q.

Siguiente: Encriptamiento Un nivel arriba: Método de llave pública Anterior: Método de llave pública