Inicio » Contenidos
Archivos de la categoría: Contenidos
¿Cómo construir cuerpos finitos?
Ya sabéis que los anillos $(\mathbb{Z}_p,+,\cdot)$, con $p$ primo, son cuerpos finitos (tienen $p$ elementos). Sin embargo, no son los únicos cuerpos finitos. Veamos ahora cómo construir más. Para ello vamos a utilizar el último resultado que hemos probado en las clases de teoría: si $A$ es un anillo conmutativo e $I$ es un ideal de $A$ entonces $I$ es ideal maximal si y sólo si $A/I$ es cuerpo.
Sea $p$ cualquier número primo y consideremos el anillo de polinomios con coeficientes en $\mathbb{Z}_p$, $A=\mathbb{Z}_p[x]$. Consideremos también un polinomio irreducible $f(x)\in \mathbb{Z}_p[x]$ (irreducible significa que no puede escribirse como producto de dos polinomios en $\mathbb{Z}_p[x]$ no constantes). Sea el ideal $I$ de $\mathbb{Z}_p[x]$ generado por $f(x)$, es decir, $I=\langle f(x) \rangle=A f(x)=\mathbb{Z}_p[x]f(x)$ (cuyos elementos son exactamente los múltiplos de $f(x)$, es decir, los polinomios de la forma $h(x)f(x)$ con $h(x)\in \mathbb{Z}_p[x]$.
Puede demostrarse que $I$ es un ideal maximal de $\mathbb{Z}_p[x]$ (esta prueba la veréis en cuarto) y, por tanto, aplicando la caracterización de los ideales maximales antes mencionada, el anillo cociente $\mathbb{Z}_p[x]/I$ es un cuerpo.
Veamos que este cuerpo tiene una cantidad finita de elementos. Si $h(x)+I$ es un elemento cualquiera de $\mathbb{Z}_p[x]/I$ entonces, dividiendo $h(x)$ entre $f(x)$, se tiene que existen dos polinomios únicos $q(x)$ (cociente) y $r(x)$ (resto) tales que $h(x)=q(x)f(x)+r(x)$, donde o bien $r(x)$ es el polinomio nulo, o bien es un polinomio no nulo de grado estrictamente menor que el grado de $f(x)$. (El ‘Algoritmo de la División’ también es válido para polinomios con coeficientes en cualquier cuerpo). Tomando clases módulo el ideal $I$ tenemos que
$$h(x)+I=(q(x)+I)(f(x)+I)+(r(x)+I)=r(x)+I$$
porque $f(x)+I=0+I$ al ser $f(x)\in I$. Si llamamos $d$ al grado de $f(x)$, como el grado de $r(x)$ es menor que $d$ (en caso de no ser el polinomio nulo), se tiene que
$$r(x)=a_0+a_1x+\cdots+a_{d-1}x^{d-1}$$
para ciertos elementos $a_0,\ldots, a_{d-1}\in \mathbb{Z}_p$. Luego:
$$h(x)+I=(a_0+I)(1+I)+(a_1+I)(x+I)+\cdots + (a_{d-1}+I)(x^{d-1}+I).$$
Fijémonos en que, si $a,b\in \mathbb{Z}_p$ (es decir, son polinomios constantes) entonces $a+I=b+I$ si y sólo si $a-b\in I$ si y sólo si $a-b$ es un múltiplo del polinomio $f(x)$. Y esto ocurre si y sólo si $a-b=0$ (es decir, $a=b$), pues $a-b$ es un polinomio constante y $f(x)$ es un polinomio de grado $d\geq 1$. Por tanto, para cada coeficiente $a_i+I$ hay tantas posibilidades distintas como elementos $a_i$ en $\mathbb{Z}_p$ (es decir, $p$ posibilidades).
Con esto, acabamos de probar que todo elemento $h(x)+I$ del cuerpo $\mathbb{Z}_p[x]/I$ puede expresarse como combinación lineal (con coeficientes de la forma $a_i+I$, con $a_i$ constante en $\mathbb{Z}_p$) de las siguientes $d$ clases: $1+I, x+I, x^2+I,\ldots, x^{d-1}+I$. Como cada uno de los coeficientes $a_i+I$ puede tomar sólo $p$ valores (los correspondientes a los $p$ elementos de $\mathbb{Z}_p$) se tiene que hay, como mucho, $p^d$ elementos en $\mathbb{Z}_p[x]/I$. De hecho, puede justificarse fácilmente (no entramos aquí en esto) que estos $p^d$ elementos son todos distintos. Por tanto, concluimos que el cuerpo $\mathbb{Z}_p[x]/I$ tiene, exactamente, $p^d$ elementos (donde $d$ es el grado del polinomio irreducible $f(x)$).
Para construir cuerpos finitos de esta manera podemos tomar cualquier polinomio irreducible $f(x)$ de $\mathbb{Z}_p[x]$. Puede demostrarse que si $f_1(x)$ y $f_2(x)$ son dos polinomios irreducibles de $\mathbb{Z}_p[x]$ del mismo grado entonces los respectivos cuerpos $\mathbb{Z}_p[x]/\langle f_1(x)\rangle$ y $\mathbb{Z}_p[x]/\langle f_2(x)\rangle$ son isomorfos. Como consecuencia de esto (y de otros hechos relevantes) se deduce que, para cada número primo $p$ y para cada número natural $d$ existe, salvo isomorfismo, un único cuerpo con $p^d$ elementos. Este cuerpo se denomina cuerpo de Galois de cardinal $p^d$ y suele denotarse por $GF(p^d)$ (en inglés “Galois field”). (Para polinomios de grado 1 se obtienen los conocidos cuerpos $GF(p)=\mathbb{Z}_p$ con $p$ primo).
Y hay más: puede demostrarse que estos son todos los cuerpos finitos que existen (salvo isomorfismo). No hay más. Cualquier cuerpo finito debe ser isomorfo a uno de los grupos de Galois $GF(p^d)$.
Aplicaciones de la teoría de anillos
Describimos someramente, a continuación, una de las aplicaciones más básicas del Álgebra Conmutativa: resolución de sistemas de ecuaciones polinómicas.
Si $A$ es un anillo y $x$ es una indeterminada, denotemos por $A[x]$ al conjunto de expresiones formales del tipo $$a_0+a_1x+\cdots+a_nx^n,$$ donde $a_i\in A$ para todo $i$ y $n$ es un número entero no negativo. Una expresión de este tipo se denomina polinomio con coeficientes en $A$ e indeterminada $x$. Ya habéis trabajado con polinomios en Educación Secundaria y en Bachillerato; la única diferencia es que los coeficientes que usábais eran números reales y aquí se permiten coeficientes en cualquier anillo $A$. También habéis visto que dos polinomios se pueden sumar y multiplicar. En el caso más general que nos ocupa, la suma y el producto de polinomios se definen igual. Es sencillo probar que $(A[x],+,\cdot)$ tiene estructura de anillo.
Podemos considerar también polinomios en más indeterminadas. Si $x_1,…,x_n$ es un conjunto de indeterminadas, se denomina monomio en $x_1,…,x_n$ a cualquier expresión del tipo $x_1^{\alpha_1}\cdots x_n^{\alpha_n}$, donde los exponentes $\alpha_i$ son enteros no negativos. Dicho de otro modo, un monomio es un producto de potencias de las indeterminadas. Se denomina polinomio en $x_1,\ldots,x_n$ con coeficientes en $A$ a cualquier combinación lineal de monomios con coeficientes en $A$. El conjunto de todos estos polinomios se denota por $A[x_1,\ldots,x_n]$. Por ejemplo, si consideramos dos indeterminadas $x,y$, las expresiones $0$, $3$, $2+5x+yxy^2$ y $x^2y-7xy^5-12x^7$ son ejemplos de polinomios en $\mathbb{Z}[x,y]$. De manera totalmente análoga (y natural) al caso de $A[x]$, se definen la suma y el producto de polinomios en $A[x_1,\ldots,x_n]$. Además, $(A[x_1,\ldots,x_n],+,\cdot)$ también tiene estructura de anillo (denominado anillo de polinomios en las indeterminadas $x_1,\ldots,x_n$).
Vamos a centrarnos en anillos de polinomios con coeficientes en un cuerpo $K$. Es decir, anillos del tipo $K[x_1,\ldots,x_n]$. Vamos a considerar, como ejemplo, $K=\mathbb{C}$ (el cuerpo de los números complejos) y vamos a tomar dos indeterminadas $x,y$.
Vamos a considerar el siguiente sistema de ecuaciones con coeficientes en $\mathbb{C}$: $$f:=xy^2-2x-y^2+2=0,$$ $$g:=x^2y-x^2+y+1=0.$$ Nuestro objetivo va a ser resolver dicho sistema de ecuaciones, es decir, encontrar todos los pares de números complejos $(x,y)$ que satisfacen estas dos ecuaciones.
Esto no parece fácil, a simple vista. Veremos (someramente, sin detalles) que determinados resultados de álgebra conmutativa nos van a permitir resolver este sistema.
Fijémonos en que los primeros miembros de las ecuaciones, $f$ y $g$, son polinomios con dos indeterminadas ($x,y$) y coeficientes en $\mathbb{C}$. Es decir, $f,g\in \mathbb{C}[x,y]$. Lo que buscamos al resolver el sistema de ecuaciones es el conjunto de ceros comunes a $f$ y a $g$, entendiéndose como cero de un polinomio $h\in \mathbb{C}[x,y]$ un punto $(a,b)\in \mathbb{C}\times \mathbb{C}$ en el que se anula $h$ (es decir, tal que $h(a,b)=0$).
Introduzcamos un poco de notación: si $S$ es un conjunto de polinomios en $\mathbb{C}[x,y]$, denotaremos por $V(S)$ al conjunto de todos los puntos $(a,b)\in \mathbb{C}\times \mathbb{C}$ tales que $h(a,b)=0$ para todo $h\in S$. Dicho de otro modo, $V(S)$ es el conjunto de ceros comunes a todos los polinomios de $S$. En nuestro ejemplo, lo que buscamos es el conjunto $V(\{f,g\})$.
La primera observación importante es la siguiente: si $\langle f,g\rangle$ es el ideal de $\mathbb{C}[x,y]$ generado por $f$ y $g$ entonces $V(\{f,g\})=V(\langle f, g\rangle)$. Dicho de otro modo, el conjunto de ceros comunes a $f$ y a $g$ es exactamente el mismo que el conjunto de ceros comunes a todos los polinomios pertenecientes al ideal que generan $f$ y $g$. Veamos esto:
Si $(a,b)\in V(\{f,g\})$ y $h$ es un polinomio perteneciente al ideal $\langle f,g\rangle$ entonces $h(a,b)=0$. En efecto: sabemos (lo hemos visto en teoría) que los elementos de $\langle f,g\rangle$ son exactamente todas las combinaciones lineales $f$ y $g$ con coeficientes en en anillo (que, en este caso, es $\mathbb{C}[x,y]$. Por tanto, existen dos polinomios $h_1,h_2\in \mathbb{C}[x,y]$ tales que $h=h_1f+h_2g$. Evaluando $h$ en $(a,b)$ se tiene que $h(a,b)=h_1(a,b)f(a,b)+h_2(a,b)g(a,b)=0$, donde la última igualdad es consecuencia del hecho de que $(a,b)\in V(\{f,g\})$ (es decir, de que $(a,b)$ sea un cero común a $f$ y a $g$). Esto prueba la inclusión $V(\{f,g\})\subseteq V(\langle f, g\rangle)$.
La otra inclusión es clara, ya que tanto $f$ como $g$ pertenecen al ideal $\langle f, g\rangle$.
Por tanto, el conjunto de soluciones del sistema de ecuaciones anterior no depende de las ecuaciones específicas $f=0$ y $g=0$ sino más bien del ideal generado por $f$ y $g$. Así pues, si logramos encontrar un sistema de generadores de $\langle f,g\rangle$ que sea mejor (en el sentido de que las ecuaciones que determinen se puedan resolver fácilmente) habremos ganado.
Hay técnicas de Álgebra Conmutativa Computacional que permiten hacer esto. Dado un ideal de un anillo de polinomios, usando la Teoría de bases de Groebner (de la cual no es pertinente dar más detalles aquí), puede calcularse un conjunto de generadores del ideal «más fácil». En el caso que nos ocupa, puede verse que el conjunto de polinomios $$\{y^3-y^2-2 y+2, x y^2+2 x-y^2+2, x^2+x y^2-2 x+y^2-1\}$$ constituye un sistema generador alternativo del ideal $\langle f,g\rangle$, es decir, $$\langle f,g\rangle=\langle y^3-y^2-2 y+2, x y^2+2 x-y^2+2, x^2+x y^2-2 x+y^2-1 \rangle.$$ Como, por lo dicho antes, $$V(\{f,g\})=V(\langle f,g\rangle)=V(\langle y^3-y^2-2 y+2, x y^2+2 x-y^2+2, x^2+x y^2-2 x+y^2-1 \rangle),$$ resulta que nuestro sistema de ecuaciones inicial es equivalente al sistema siguiente: $$y^3-y^2-2 y+2=0,$$ $$x y^2+2 x-y^2+2=0,$$ $$x^2+x y^2-2 x+y^2-1=0.$$
Observemos que la primera ecuación sólo depende de $y$ (no depende de $x$). Podemos, por tanto, resolver esta ecuación en $y$ (que tiene una sola incógnita) y calcular todos los valores de $y$ posibles en las soluciones. Sustituyendo estos valores en las dos ecuaciones siguientes pueden calcularse los valores de $x$ correspondientes. De esta manera, seremos capaces de resolver el sistema. Si hacemos esto veremos que las soluciones de nuestro sistema son las siguientes: $$ (1,1),(i, \sqrt{2}),(-i, \sqrt{2}),(i,-\sqrt{2}),(-i,-\sqrt{2}).$$
Proofs from the book
Proofs from the book es un libro de demostraciones matemáticas de Martin Aigner y Günter M. Ziegler. Está dedicado al matemático Paul Erdős, que a menudo se refería a «El Libro» donde Dios guardaba las demostraciones más elegantes de cada teorema matemático. Durante una conferencia en 1985, Erdős dijo que un matemático «no tiene que creer en Dios, pero debería creer en El Libro».
Para los interesados en los fundamentos de las matemáticas:
“Matemáticas. La pérdida de la certidumbre” de Morris Kline.
De «Introduction to Mathematical Philosophy»(Bertrand Russell)
«Mathematics is a study which, when we start from its most familiar portions, may be pursued in either of two opposite directions. The more familiar direction is constructive, towards gradually increasing complexity: from integers to fractions, real numbers, complex numbers; from addition and multiplication to differentiation and integration, and on to higher mathematics. The other direction, which is less familiar, proceeds, by analysing, to greater and greater abstractness and logical simplicity; instead of asking what can be defined and deduced from what is assumed to begin with, we ask instead what more general ideas and principles can be found, in terms of which what was our starting-point can be defined or deduced. It is the fact of pursuing this opposite direction that characterises mathematical philosophy as opposed to ordinary mathematics. But it should be understood that the distinction is one, not in the subject matter, but in the state of mind of the investigator. Early Greek geometers, passing from the empirical rules of Egyptian land-surveying to the general propositions by which those rules were found to be justifiable, and thence to Euclid’s axioms and postulates, were engaged in mathematical philosophy, according to the above definition; but when once the axioms and postulates had been reached, their deductive employment, as we find it in Euclid, belonged to mathematics in the ordinary sense. The distinction between mathematics and mathematical philosophy is one which depends upon the interest inspiring the research, and upon the stage which the research has reached; not upon the propositions with which the research is concerned.»
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 6)
¿Dónde radica la seguridad del criptosistema RSA?
Conocer la aplicación de descifrado $D$ equivale a conocer la clave privada $d$, que sólo posee Bob. Y esta clave secreta $d$ no puede conocerse a partir de $(n, e)$ sin el conocimiento de $r=\varphi(n)=(p-1)(p-1)$ (recuérdese que $d$ es un representante del inverso de la clase de $e$ módulo $r=(p-1)(q-1))$. Puede razonarse que conocer $r$ es igual de difícil que saber factorizar $n$ como producto de los primos $p$ y $q$. Si estos primos se han elegido suficientemente grandes (y satisfaciendo ciertas condiciones buenas), $n$ tendrá un valor tan grande que será imposible factorizarlo con los recursos computacionales existentes en este momento. Aquí radica la seguridad del criptosistema RSA. Si una supuesta espía Eve interceptara el mensaje que Alice le envía a Bob, le resultaría imposible averiguar la clave secreta $d$ (y, por tanto, descifrar el mensaje) aún sabiendo la clave pública $(n,e)$.
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 5)
Para probar que el proceso de descifrado anteriormente descrito es correcto, hay que demostrar que las aplicaciones de cifrado, C, y descifrado, D, son inversas una de la otra, es decir, $C\circ D=D\circ C=Id$, donde $Id: \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ es la aplicación identidad. Como, para todo $\overline{x}\in \mathbb{Z}_n$, $C(D(\overline{x}))=D(C(\overline{x}))=\overline{x}^{ed}$, es suficiente demostrar que $$x^{ed}\equiv x\; ({\rm mod}\; n)\;\mbox{para todo $x\in \mathbb{Z}$}.$$
Sea $x$ un entero arbitrario. Si $x$ es divisible por $n$ entonces la congruencia anterior es obvia. Por tanto, podemos asumir que $x$ no es divisible por $n$. Como $ed\equiv 1\; ({\rm mod}\; r)$, existe un entero $\lambda$ tal que $ed=1+\lambda r$. Luego $x^{ed}=x (x^r)^{\lambda}$.
Vamos a distinguir dos casos:
Caso 1: $x$ y $n$ son coprimos. En este caso, la clase $\overline{x}\in \mathbb{Z}_n$ tiene inverso multiplicativo en $\mathbb{Z}$ (por la Proposición 1.9 de los apuntes, que veremos). Además, en la Sección 1.10 del Capítulo 1, veremos también que el conjunto $U_n$ formado por los elementos de $\mathbb{Z}_n$ que tienen inverso multiplicativo es un grupo (con el producto) cuyo orden es $\varphi(n)=r$ (la función de Euler de $n$). Como $\overline{x}\in U_n$, por un corolario del Teorema de Lagrange (que veremos, previsiblemente, en la clase del jueves) el orden de $\overline{x}$ en $U_n$ es un divisor de $r=\varphi(n)$ y, por tanto: $\overline{x}^{r}=\overline{1}$, es decir, $x^{r}\equiv 1\; ({\rm mod}\; n)$. Así pues, $$x^{ed}=x (x^r)^{\lambda}\equiv x\; ({\rm mod}\; n).$$
Caso 2: $x$ y $n$ no son coprimos. En este caso, como $n=p q$, $x$ ha de ser divisible por uno de los dos primos $p$ y $q$, pero no por ambos (al no ser $n$ divisor de $x$). Supongamos, sin pérdida de generalidad, que $p$ divide a $x$ (se razonaría igual si $q$ divide a $x$) y, por tanto, $q$ es coprimo con $x$. Como consecuencia de esto último, la clase de $x$ en $\mathbb{Z}_q$ (que vamos a denotar también por $\overline{x}$; ¡que el abuso notacional no te confunda, por favor!) tiene inverso multiplicativo, luego pertenece a $U_{q}$. Como el grupo $U_q$ tiene orden $\varphi(q)=q-1$, razonando igual que antes se tiene que el orden de $\overline{x}$ en $U_q$ es un divisor de $q-1$ y, por tanto, $\overline{x}^{q-1}=\overline{1}$ en $\mathbb{Z_q}$. Luego $\overline{x}^r=(\overline{x}^{q-1})^{p-1}=\overline{1}$ en $\mathbb{Z}_q$. Por tanto, $x^{ed}=x (x^r)^{\lambda}\equiv x\; ({\rm mod}\; q)$, es decir, $x^{ed}-x$ es un múltiplo de $q$.
Por otro lado (continuando dentro del Caso 2), como $p$ divide a $x$ se cumple, obviamente, que $x^{ed}\equiv 0 \equiv x\; ({\rm mod}\; p)$, es decir, $x^{ed}-x$ es un múltiplo de $p$.
Así, hemos demostrado que $x^{ed}-x$ es, a la vez, múltiplo de $p$ y de $q$. Luego es múltiplo de $n=p q$, es decir, $$x^{ed}\equiv x\; ({\rm mod}\; n).$$
Con esto, acabamos de demostrar que las aplicaciones $C$ y $D$ son inversas una de la otra.
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 4)
Vamos a diseñar ahora una «función de cifrado», es decir, una función $$C:\mathbb{Z}_n\rightarrow \mathbb{Z}_n$$ tal que, si $\overline{m}$ es el mensaje que Alice quiere cifrar (recordad que Alice ha «preparado» el mensaje para transformarlo en una clase de congruencia módulo $n$), el resultado del cifrado será la imagen de $\overline{m}$ por esta función, es decir, $C(\overline{m})$. Este será el valor que Alice enviará a Bob.
La función de cifrado se define de la siguiente manera: $$C(\overline{x}):=\overline{x}^e$$ para todo $\overline{x}\in \mathbb{Z}_n$ (¡OJO! Aquí la «barrita» superior significa «clase módulo $n$»). Dicho de otro modo, para cifrar el mensaje $\overline{m}$, Alice calculará la clase de $\mathbb{Z}_n$ consistente en multiplicar la clase $\overline{m}$ consigo misma $e$ veces (con el producto en $\mathbb{Z}_n$, claro está).
Por ejemplo, consideremos las claves del anterior ejemplo e imaginemos que el mensaje que quiere cifrar Alice es $\overline{m}=\overline{12423}\in \mathbb{Z}_{25877}$. Entonces se tiene que $$C(\overline{m})=\overline{12423}^{e}=\overline{12423}^{1321}=\overline{14946}\in \mathbb{Z}_{25877}.$$ Este es el mensaje que Alice envía a Bob.
Vamos a diseñar ahora una «función de descifrado», es decir, una función $$D:\mathbb{Z}_n\rightarrow \mathbb{Z}_n$$ tal que, si Bob aplica esta función al mensaje $C(\overline{m})$ que le ha enviado Alice, obtiene el mensaje original $\overline{m}$. Dicho de otro modo, tal que $D(C(\overline{m}))=\overline{m}$. Un poco de reflexión nos hará concluir que, lo que queremos es que $C$ sea una función biyectiva y $D$ sea su inversa.
Esta función de descifrado $D$ se define de la siguiente manera: $$D(\overline{x}):=\overline{x}^d$$ para todo $\overline{x}\in \mathbb{Z}_n$.
En el caso de nuestro ejemplo, si aplicáis esta función de descifrado $D$ a $C(\overline{m})=\overline{14946}$ obtendréis $$D(C(\overline{m}))=D(\overline{14946})=\overline{14946}^{d}=\overline{14946}^{17881}=\overline{m}.$$
¿Por qué esto funciona? ¿Cómo se justifica? Lo veremos en el siguiente post.
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 3)
Ya hemos visto que la clave pública del criptosistema RSA consiste en un par $(n,e)$, donde $n$ es el producto de dos primos muy grandes, $p$ y $q$, y $e$ es un entero entre $1$ y $r-1$ coprimo con $r$, donde $r=\varphi(n)=\varphi(p q)=(p-1)(q-1)$. Veamos ahora cómo Bob determina una clave privada (que sólo conocerá él).
Consideramos la clase de $e$ en el conjunto de clases de congruencia módulo $r$, $\mathbb{Z}_r$ (recuérdese que $e$ es un entero entre $1$ y $r-1$; por tanto, se trata de una clase distinta de la del cero). Como es habitual, denotemos por $\overline{e}$ a esta clase. Consderamos ahora la operación producto en $\mathbb{Z}_r$. Como ya sabéis, no todo elemento de $\mathbb{Z}_r\setminus \{\overline{0}\}$ tiene inverso multiplicativo (es decir, no para toda clase $\overline{x}\neq \overline{0}$ existe otra clase $\overline{x}^{-1}$ tal que $\overline{x}\cdot \overline{x}=\overline{1}$). Pero, ¿cuáles son las clases de $\mathbb{Z}_r\setminus \{\overline{0}\}$ que tienen inverso multiplicativo? La respuesta la tenéis en la Proposición 1.9 de los apuntes (que veremos más adelante): tienen inverso exactamente aquellas clases $\overline{k}$, con $1\leq k\leq r-1$, tales que $k$ y $r$ son coprimos. Revisad ahora las condiciones que satisface $e$: ¡son exactamente estas! Por tanto, la clase de $e$ en $\mathbb{Z}_n$, $\overline{e}$, tiene inverso multiplicativo. Luego existe un entero $d$ tal que $1<d<r-1$ y $\overline{d}=\overline{e}^{-1}$ en $\mathbb{Z}_r$. Dicho de otro modo, $$ed\equiv 1\;({\rm mod}\; r).$$
Este entero $d$ es la clave privada de Bob.
Ahora repasemos:
- Para generar una clave pública, Bob elige dos primos muy grandes $p$ y $q$ y considera su producto $n=p q$. Después calcula $r:=\varphi(n)=(p-1)(q-1)$ y elige un entero $e$ tal que $1\leq e\leq r-1$ y ${\rm mcd}(e,r)=1$. La clave pública es el par $(n,e)$.
- Para generar una clave privada, Bob calcula el entero $d$ tal que $1\leq d\leq r-1$ y tal que su clase en $\mathbb{Z}_r$ sea el inverso multiplicativo de la clase de $e$, es decir, tal que $ed\equiv 1\;({\rm mod}\;r)$. La clave privada es este entero $d$.
En nuestro ejemplo «de juguete» anterior (recordad: $n=113\cdot 229=25877$ y $e=1321$), Bob podría tomar como clave privada $d:=17881$ (podéis verificar que la clase de $d$ es el inverso multiplicativo de la clase de $e$ módulo $r$).
La siguiente pregunta es: ¿cómo usará Alice la clave pública $(n,e)$ para cifrar mensajes, y cómo usará Bob su clave privada $d$ para descifrarlos?
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 2)
Recordemos que tenemos a Alice y a Bob, y que Alice quiere enviar un mensaje encriptado a Bob (usando una clave pública) para que Bob lo descifre (usando SU clave privada). Para ello, Bob considera dos números primos muy grandes $p$ y $q$ y los multiplica, formando un entero muy grande $n:=pq$. Este valor $n$ es conocido por Alice y por cualquier persona que quiera y/o pueda conocerlo (¡Ojo! el valor $n$ es público, pero NO lo son los factores $p$ y $q$), y forma parte de la clave pública necesaria para cifrar mensajes para enviar a Bob. Como más adelante recordaremos, la seguridad del sistema radica en que es computacionalmente muy difícil averiguar los factores primos $p$ y $q$ a partir de $n$ si éstos son muy grandes.
Veamos ahora cómo calcular la segunda parte de la clave pública. Para esto Bob (que es el único conocedor de los primos $p$ y $q$) calcula el siguiente valor: $$r:=\varphi(n)=(p-1)(q-1),$$ es decir, la función de Euler de $n$. Para él es muy fácil de calcular pues, como $n$ es el producto de dos primos $p$ y $q$, y ÉL CONOCE ESTOS PRIMOS, por una propiedad de la función de Euler sabe que $\varphi(n)=(p-1)(q-1)$ (véase https://es.wikipedia.org/wiki/Función_φ_de_Euler). Puede razonarse que la dificultad de calcular $r$ a partir únicamente de $n$ (que es muy grande) es similar a la dificultad de obtener los primos $p$ y $q$ sólo a partir de $n$. Una vez calculado este valor $r$, Bob elige arbitrariamente un número entero $e$ tal que $0<e<r$ y tal que ${\rm mcd}(e,r)=1$. El par formado por $(n,e)$ constituye la clave pública completa, y es la información que Bob da a conocer a Alice (y a quien quiera saberla) para que ésta pueda encriptar el mensaje que quiere transmitir a Bob.
Vamos a ver un ejemplo nada realista (con números primos «de risa») para que se entienda bien. Bob podría elegir los primos $p=113$ y $q=229$. El valor $n$ es igual a $113\cdot 229=25877$, y el valor $r$ es igual a $\varphi(113\cdot 229)=112\cdot 228=25536$. Bob elige como $e$ el valor $1321$ (que está entre $1$ y $r-1$ y es coprimo con $r$).
La clave pública sería el par $$(n=25877, e=1321).$$