Fundamento algebraico del sistema de clave pública RSA

Damos por demostrados los siguientes resultados:

T1.Todo número entero pude descomponerse de forma única como producto de números primos.

T2. Sean $a$ y $b$ números enteros con $b\neq 0$. Entonces existen números enteros $q$ y $r$ con $0\leq r<|b|$ tales que

$$a=bq+r$$

T3. Para cualquier par de números enteros $a\neq0$ y $b\neq 0$ existe un $v$ (mc.d.) que se puede obtener como combinación lineal de estos

$$v=xa+tb;\ s,t\in Z$$

T4. Si $a\neq0$ y $b\neq0$ son primos entre si $(m.c.d.=1$) entonces

$$1=sa+tb;\ s,t\in Z$$

T5. Si $p$ es un número primo y divide al producto de otros dos, entonces divide al menos a uno de ellos.

T6. Si un número $a$ es primo con $b$ y $c$ también es primo con el producto $bc$ (Este resultado se puede generalizar a $n$ números $b_1,b_2,…\ b_n$)

 

 

1.Todo cuerpo es un dominio de integridad:

Si $a·b=0$ y $a\neq 0$  entonces  $\exists a^{-1}/a^{-1}·a=0\Rightarrow a=0$

Existen dominios de integridad, como $\mathbb{Z}$, que no son cuerpos, sin embargo, se puede afirmar que » todo dominio de integridad finito es un cuerpo»

Sea $a\in A$; $a\neq 0$ y definamos $a:A\longrightarrow A$ tal que $a(x)=a·x$. Es obviamente una aplicación inyectiva ya que  $a·x=a·y\Rightarrow ax-ay=0\Rightarrow a(x-y)=0$; pero como $a\neq 0$ y $A$ es un dominio de integridad, se tiene que $x-y=0$;  $x=y$. Como se trata de un conjunto finito, la aplicación es también exhaustiva con lo que debe existir $a^{-1}(1)$;  o sea que $a·a^{-1}=1)$,  con lo que queda demostrado que todo elemento tiene inverso, con lo que $A$ es un cuerpo.

2. Un elemento $a\in {Z}{_{n}}$ es invertible si y sólo si $a$ y $n$ son primos relativos:

Si $m.c.d.(a,n)=1$  se cumple que $\exists r,s\in \mathbb{Z} / 1=ar+ns$

$\overline{1}=\overline{ar+ns}$ $\Longrightarrow$ $\overline{1} = \overline{ar} + \overline{ns}  =  \overline{ar} = \overline{ns}$ con lo que $\overline{a}^{-1}=\overline{r}$

Los divisores de cero de $ {Z}{_{n}}$  son precisamente los elementos no inversibles  

Si $a$ es no invertible se tiene que $M.c.d.(a,n)=d$ $\Rightarrow{a·r=d}$    y    $n·s=d$
Con lo que se tiene $ar=ns=0$ siendo $a\neq0$ y $r\neq0$

3. ${Z}{_{n}}$ es un cuerpo si y sólo si $n$ es un número primo

Como resultado de todo lo anterior
${Z}{_{n}}$ es un cuerpo (el número mínimo de elementos que puede tener un cuerpo es 2.)

Función $\phi$ de Euler
Se define $\phi{(1)}=1$ y $\phi{(n)}=N$; siendo $N$ el número de elementos de ${Z}{_{n}}$ que son primos con $n$ (c9ntando el 1). Por ejemplo
$$\phi{(6)}=6$$
$$\phi{(9)}=6$$
$$\phi{(12)}=4$$

Si $p$ es primo se tienen que $\phi{(p)}=p-1$ que es el número de elementos de ${Z}{_{p}}$ quitando el 0.

Sea ${G}{_{n}}\subset{Z}{_{n}}$ el conjunto definido por todos los elementos $a\in{Z}{_{n}}$ que son primos relativos con $n$. Tal y como lo hemos definido, ${G}{_{n}}$ es un grupo de orden $\phi (n)$.

(Recordemos que si $G$ es un grupo finito de orden $k$ se tiene que $\ x^k=1$ $\forall x\in G$).

Teorema de Euler-Fermat
Si $a$ es un entero positivo y es primo non $n$, entonces $a^{\phi (n)}\equiv 1 \ (mod\ n)$.
Es una consecuencia inmediata del hecho de que $a\in{G}{_{n}}$.

FUNCIÓN UNIDIRECCIONAL CON TRAMPA EN EL CRIPTOSISTEMA RSA

Sean $p$, $q$ dos números primos y $n=p·q$. $\phi{(n)}$ la función de Euler y $e$ un número primo con $\phi{(n)}$; $m.c.d.(e, \phi{(n)})=1$.

Sea $d$ el inverso de $e$ en $Z_{\phi{(n)}}$ cuya existencia tenemos garantizada por ser $e$ primo con $\phi(n)$.

Definimos la función $E_{(e,n)}(x)=x^e\ (mod\ n$).

La función $D_{(d,n)}(y)=y^d\ (mod\ n)$ es la inversa de $E_{(e,n)}$
$$E_{(e,n)}^{-1} =D_{(e,n)}$$

$e·d=1\ mod(n)$ (por definición) $\Rightarrow \exists t\in Z /e·d-1=\dot{n}=t·\phi (n))$
$e·d=1+\phi{(n)}·t$

$D_{(d,n)}·E_{(e,n)}(x)=(x^e)^d\ (mod\ n)=(x^e)^d\ (mod\ n)=x^{1+\phi{(n)}·t}\ (mod\ t)=x^{\phi{(n)}·t}·x\ (mod\ n)$ (1).
Como n es un número primo se tiene que $m.c.d.(x,n)=1$ con lo que podemos aplicar el teorema de Euler -Fermat, siendo entonces $x^{\phi (n)} \equiv{1}\ mod\ (n)$ con lo que la igualdad anterior se transforma en
$$(1)=1^b·x\ (mod\ n)$$
por lo mismo $E_{(e,n)}D_{(d,n)}=I$ con lo que la funciones direccionales de encriptación $(E)$ y de desencriptación $(D)$ son una inversa de la otra.

El sistema de encriptación $(E)$ y de desencriptación $(D)$ sigue el siguiente proceso:

Se trabaja siempre con números, por lo cual se deben asignar a las letras del abecedario números, ya sea en base decimal o en binario. Se hacen asignaciones por bloques siguiendo determinadas reglas que ahora no vienen al caso.
Se determinan dos números primos $p$ y $q$ (secretos). Pongamos por ejemplo que son $p=3$ y $q=5$, se hace el producto $n=p·q=15$. Se define $\phi(n)=(p-1)(q-1)=2·4=8$. A continuación buscamos un número entero $e$ (público) que sea primo con $\phi(n)$, por ejemplo $e=3$ será $m.c.d.\ (3,8)=1$ y otro número $d$ (secreto) que sea $d=e^-1$ en $Z_{\phi(n)}$.
La clave pública de cifrado es entonces $(e,n)$

Supongamos que tenemos el siguiente mensaje: $M=7\ ,\ C=13$
El cifrado es $7^3\ (mod\ 15)\equiv{13}$
Y el descifrado $13^3\ (mod\ 15)\equiv{7}$

SECRETOS: $(\phi (n)$, d)
PÚBLICOS: $(e,n)$

De hecho, si supiéramos $\phi (n)$ no supondría ningún problema encontrar $(d)$. La dificultad real del criptoanalista estriba en encontrar $p$ y $q$ lo que , en términos matemáticos, se traduce en la posibilidad e factorizar un número como producto de dos factores primos, algo para o que de momento no existe un método (se entiende que hablamos siempre de números primos muy grandes)

PROBLEMAS QUE RESUELVE LA CLAVE PÚBLICA

1. Distribución de claves.

Dado un conjunto de usuarios $A,\ B,\ …$ debe existir una base de datos que contenga las claves de encriptación $E_{kA},\ E_{kB},\ …$ de cada uno de los usuarios
Supongamos que $A$ quiere enviar a $B$ un mensaje $m$

El fichero público proporciona a $A$ la clave $E_{k_{B}}$ de manera que
$$A:E_{k_{B}}(m)\longrightarrow\ B:D_{k_{B}}(E_{k_{B}}(m))=m$$

De esta forma , cada vez que alguien quiere enviar un mensaje solicita al centro de distribución la cave del destinatario y con esta encripta el mensaje. En principio existe siempre la posibilidad de que en el sistema se cuele un «extraño» que se haga pasar por $A$, situaciń que queda resuelta mediante el proceso de autenticación.
2. Autenticación.

Definición: Firma Digital: Un criptosistema tiene firma digital si para todo mensaje $m$ y toda clave $k$ se cumple
$$E_k (D_k(m))=m$$

La manera en que $A$ puede asegurar a $B$ que es realmente él quien envía el mensaje es primero utilizando la firma $s=Dk_A(m)$ y luego encriptando $c=Ek_B(s)$ con lo que
$$A\longrightarrow Ek_A(s)=c\\\\ B\longrightarrow Ek_B(s)=s$$

$s$ es un mensaje que no se puede entender, pero cuando $B$ pide al centro de claves la clave pública de $A$ se tienen que
$$Ek_A(s)=Ek_A(Dk_A(m))=m$$
ya puede leer el mensaje y sabe con seguridad que proviene de $A$ (recordemos que $E$ y $D$ son funciones inversas una de la otra).

Para todos los públicos
A caballo entre el final del bachillerato y el principio de carrera
Para matemáticos adictos a la cafeína.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *