Clase del 3 de octubre (2 horas)
En la clase de ayer probamos algunos resultados que se obtienen aplicando el Teorema de Lagrange:
- El orden de todo elemento de un grupo finito divide al orden del grupo.
- Si un grupo tiene orden primo entonces es cíclico.
- Un grupo finito no tiene subgrupos propios no triviales si y sólo si tiene orden primo.
Definimos el concepto de subgrupo normal de un grupo $G$ como aquél en el que las clases a izquierda y a derecha de cualquier elemento coinciden. Es decir, $n\leq G$ es normal en $G$ si $xN=Nx$ para todo $x\in G$. En particular, si $G$ es abeliano, todos sus subgrupos son normales. Observamos, como ejemplo, que el subgrupo $\{1,-1\}$ de $Q_8$ es un subgrupo normal.
Demostramos que, cuando $N$ es un subgrupo normal de un grupo $G$, el conjunto de sus clases a izquierda (o a derecha, porque son las mismas), denotado por $G/N$ en este caso, tiene estructura de grupo con la operación “producto de clases”. En particular, vimos que $(xN)(yN)=(xy)N$ (con lo cual el producto de clases es una clase y, por tanto, constituye una operación binaria interna en $G/N$), el elemento neutro es $1N=N$ (la clase del $1$) y el elemento inverso de una clase $xN$ es $x^{-1}N$, es decir, $(xN)^{-1}=x^{-1}N$. El grupo $G/N$ (con esta operación) se denomina grupo cociente de $G$ con $N$. Calculamos los elementos del grupo cociente $Q_8/H$, donde $H=\{1,-1\}$, construimos su tabla de Cayley, y vimos que $Q_8/H$ es isomorfo al 4-grupo de Klein comparando ambas tablas de Cayley. También vimos que el grupo cociente $\mathbb{Z}/n\mathbb{Z}$ (para todo entero $n$) coincide con el grupo de clases de congruencia módulo $n$ (con las operación suma).
Demostramos que, dados un subgrupo $H$ de un grupo $G$ y un elemento $g\in G$, el conjugado de $H$ con $g$, $H^g$, es un subgrupo de $G$. Además, si $H$ es finito, $H^g$ tiene el mismo orden que $H$.
Probamos un par de caracterizaciones de los subgrupos normales: un subgrupo $N$ de un grupo $G$ es normal si y sólo si $N^g=N$ para todo $g\in G$ si y sólo si $N^g\subseteq N$ para todo $g\in G$.
Finalmente, vimos en un ejercicio que la intersección de subgrupos normales es un subgrupo normal.
Clase del 30 de septiembre (1 hora)
En la clase de hoy hemos probado el Teorema de Lagrange, que afirma que, dado un grupo finito $G$ y un subgrupo $H$ de $G$, el orden de $G$ es igual al producto del orden de $H$ por su índice. Como consecuencia directa de este resultado se infiere que el orden de cualquier subgrupo de un grupo finito $G$ tiene que ser un divisor de $|G|$. También, dado un elemento $g\in G$, como $o(g)$ coincide con el orden del subgrupo generado por $g$, $\langle g \rangle$, se tiene como consecuencia que $o(g)$ es un divisor de $|G|$.
Hemos demostrado, como corolario del Teorema de Lagrange, la propiedad de “transitividad de índices” y también la fórmula que permite calcular el “cardinal” de $HK$, cuando $H$ y $K$ son sobgrupos de un grupo finito $G$.
Hay que tener en cuenta aquí que $HK$ no es necesariamente un subgrupo de $G$ (hemos visto un ejemplo de ello). Más adelante veremos un resultado que caracterizará aquellas situaciones en las que el producto de dos subgrupos es un subgrupo.
En la siguiente clase probaremos otras consecuencias del Teorema de Lagrange y, posteriormente, nos plantearemos la siguiente cuestión: dado un grupo $G$ y un subgrupo $H$ de $G$, ¿cuándo el conjunto de sus clases a derecha, $\{Hx\mid x\in G\}$, tiene estructura de grupo? Veremos que esto ocurre cuando $H$ pertenece a una clase muy importante de subgrupos: los subgrupos normales.
Clase del 26 de septiembre (2 horas)
Hemos comenzado la clase recordando un importante teorema que nos indica cuál es la estructura de los grupos cíclicos finitos. En particular, un grupo cíclico finito tiene un único subgrupo de orden $k$ para cada divisor $k$ del orden del grupo (y estos son exactamente sus subgrupos). Hemos visto, como ejemplo, todos los subgrupos de $\mathbb{Z}_6$; aquí lo “engorroso” es pasar de notación multiplicativa a notación aditiva, pero resulta muy fácil si se va con un poco de cuidado.
Hemos comenzado la sección sobre el Teorema de Lagrange. Hemos comenzado con un lema técnico, de demostración muy sencilla, pero que nos va a facilitar bastante la escritura de las demostraciones.
Después hemos definido el concepto de clases a derecha y a izquierda de un elemento módulo un subgrupo $H$ de un grupo $G$. Hemos visto que el conjunto de las clases a derecha forman una partición del grupo (análogamente con las clases a izquierda). También hemos visto que el cardinal del conjunto de las clases a izquierda coincide con el de las clases a derecha estableciendo una biyección entre ambos conjuntos. Esta biyección asigna, a cada clase a izquierda $xH$, la clase a derecha $Hx^{-1}$.
Si el conjunto de clases a izquierda (o a derecha) de un grupo $G$ módulo un subgrupo $H$ es finito, hemos definido el “índice de $H$ en $G$”, o “índice según $G$ de $H$”, como el número de tales clases. Se denota por $|G:H|$.
El objetivo del próximo lunes será enunciar y probar el Teorema de Lagrange, así como algunas consecuencias importantes. El Teorema de Lagrange afirma que, si $G$ es un grupo finito y $H$ es un subgrupo suyo entonces $$|G|=|H||G:H|.$$ En particular, el orden de todo subgrupo de $G$ debe ser necesariamente un divisor del orden de $G$. Por ejemplo, un grupo de orden $15$ puede tener subgrupos de ordenes $1$, $3$, $5$ y $15$, pero no puede tener subgrupos de orden $4$.
Con el objetivo de clarificar el concepto de clase a izquierda y a derecha módulo un subgrupo, vamos a incluir aquí un ejemplo (no mencionado en clase). Supongamos que $G$ es el grupo cuaternio de orden 8, $Q_8$, es decir, $$G=\{1, -1, i, -i-, j, -j, k, -k\}.$$
Vamos a considerar el subgrupo de $G$ generado por $i$, es decir, el subgrupo cíclico $$H:=\langle i \rangle.$$ Recordad que $i^2=-1$, $i^3=-i$ y $i^4=1$. Por tanto, $i$ es un elemento de orden 4. Así pues, por el teorema de estructura de los grupos cíclicos, se tiene que $$H=\{1,i,-1,-i\}.$$
Se trata, por tanto, de un subgrupo de orden 4. Aunque no lo hemos probado todavía, vamos a aplicar aquí el Teorema de Lagrange para conocer su índice en $G$. Por este teorema: $$|G|=|H||G:H|,$$
es decir: $8=4\cdot |G:H|$. Así pues, el índice de $H$ en $G$, $|G:H|$, es igual a 2. Esto significa que existen 2 clases a izquierda de $G$ módulo $H$ (y dos clases a derecha también). Veamos cuáles son las clases a izquierda. Sabemos que forman una PARTICIÓN de $G$. Una de las clases es, por supuesto, la clase del neutro (del $1$), que es $1H=H$. Por tanto, ya tenemos una clase: $$H=\{1, i, -1, -i\}.$$
Escojamos ahora un elemento que no esté en esta clase, como por ejemplo $j$, y calculemos la clase de $j$: $$jH=\{jh\mid h\in H\}=\{j\cdot 1, j \cdot i, j\cdot (-1), j\cdot (-i)\}=\{j, -k, -j,k\}.$$
Como, tal y como hemos visto, solo hay dos clases a izquierda (pues el índice era 2), ya las tenemos todas. Son las siguientes: $$H=\{1, i, -1, -i\}\;\;\mbox{ y }\;\;\; jH=\{j, -k, -j,k\}.$$
Obsérvese que, tal y como hemos mencionado en clase, se trata de clases de equivalencia. Las clases de $1, i, -1$ y $-i$ coinciden y son iguales a $H$, es decir, $$1H=iH=(-1)H=(-i)H=H.$$ También, las clases de $j$, $-k$, $-j$ y $k$ coinciden, es decir, $$jH=(-k)H=(-j)H=kH.$$
Obsérvese que el conjunto de las clases a izquierda de $G=Q_8$ módulo $H$, $\{H, jH\}$, constituye una partición de $G$.
Veamos ahora otro ejemplo. Sigamos con el mismo grupo $G=Q_8$ y consideremos el subgrupo $N$ generado por $-1$, es decir, $N:=\langle -1\rangle=\{1, -1\}$ (observad que $-1$ tiene orden 2 y, por tanto, $N$ posee solo dos elementos: $(-1)^0=1$ y $(-1)^1=-1$). Vamos a calcular, igual que antes, el índice de $N$ en $G$, usando el Teorema de Lagrange: $$|G|=|N||G:N|.$$
Por tanto: $8=2\cdot |G:N|$. Luego $|G:N|=4$. Así pues, existen 4 clases a izquierda de $G$ módulo $N$. Veamos cuáles son:
- Tenemos la clase del $1$, es decir, $1N=N=\{1, -1\}$.
- Elegimos un elemento que no esté en la clase anterior; por ejemplo, $i$. Calculemos la clase de $i$: $$iN=\{in\mid n\in N\}=\{i\cdot 1, i\cdot (-1)\}=\{i, -i\}.$$
- Elegimos un elemento de $G$ que no esté en ninguna de las clases anteriores; por ejemplo, $j$. Calculemos la clase de $j$: $$jN=\{jn\mid n\in N\}=\{j, -j\}.$$
- Elegimos un elemento de $G$ que no esté en ninguna de las clases anteriores; por ejemplo, $k$. Calculemos la clase de $k$: $$kN=\{kn\mid n\in N\}=\{k, -k\}.$$
Ya tenemos las 4 clases. Observamos que el conjunto de estas cuatro clases a izquierda forman una partición de $G$.
Si reproducís los cálculos anteriores para clases a derecha, observaréis que la clase a izquierda y a derecha módulo $H$ de cualquier elemento $x$ de $G$ coinciden (y lo mismo pasa con las clases módulo $N$), a pesar de que el grupo $G$ no es abeliano. ¡Ojo! Esto no pasa siempre. Cuando esto pasa (es decir, cuando las clases a izquierda y a derecha módulo un subgrupo coinciden) se dice que ese subgrupo es normal (y $Q_8$ tiene la peculiaridad de que todos sus subgrupos son normales, a pesar de no ser un grupo abeliano). Este concepto de subgrupo normal es muy importante y lo estudiaremos en la sección siguiente.
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).$$
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 1).
El sistema criptográfico RSA debe su nombre a sus inventores, Ronald Rivest, Adi Shamir y Leonard Adleman, que publicaron por primera vez el método en 1977. Se trata uno de los criptosistemas más utilizados hoy en día, presente como método de seguridad en transacciones bancarias, firma digital, etc. Permite intercambiar información de forma segura entre varios participantes. Cada participante tiene dos claves: una clave privada, que utiliza para descifrar los mensajes que recibe, y una clave pública, que utilizan los demás participantes cuando desean cifrar un mensaje dirigido a él. Estas dos claves son inversas entre sí, pero debe ser computacionalmente imposible deducir la clave privada a partir de la pública (y en eso radica la seguridad del sistema).
Vamos a considerar dos personajes, Alice y Bob. Alice quiere enviar un mensaje encriptado a Bob. Para ello, Bob debe generar una clave pública para comunicársela a Alice (y a cualquiera que quiera conocerla, pues no es secreta). Esta clave la utilizará Alice para encriptar el mensaje que quiere enviar a Bob. Para generar una clave pública, deben considerarse dos números primos $p$ y $q$ muy grandes (y con ciertas condiciones) y multiplicarlos. Su producto, $n:=pq$, constituye una parte de la clave pública del criptosistema (que todo el mundo conoce, o puede conocer).
Para poder aplicar toda la “maquinaria algebraica” que necesitamos, Alice transforma su mensaje en un elemento del conjunto de las clases de congruencia módulo $n$, $\mathbb{Z}_n$ (o lo divide en varios “submensajes” y transforma cada uno de ellos de esta manera); hay varias maneras de hacer esto, pero no vamos a entrar aquí en semejante disquisición. Por lo que a nosotros respecta, el mensaje se “prepara” de manera que se transforma en un elemento de $\mathbb{Z}_n$ (o en varios de ellos, si se parte en varios submensajes).
¿Cómo se genera la parte que falta de la clave pública? ¿Cómo genera Bob una clave privada? ¿Cómo se encripta un mensaje? ¿Cómo se descifra? ¿Por qué el método es seguro? Aquí entran en juego conceptos algebraicos que veremos en este curso. En próximos posts revelaremos el modo :).
Clase del 23 de septiembre (1 hora)
Hoy hemos demostrado, en primer lugar, que los subgrupos de $\mathbb{Z}$ son exactamente los de la forma $n\mathbb{Z}$, con $n\in \mathbb{Z}$.
También hemos probado un importante teorema sobre la estructura de un grupo cíclico finito. Afirma lo siguiente: si $G$ es un grupo cíclico finito generado por un cierto elemento $g$ de orden $n$ entonces el orden del grupo coincide con el orden del generador ($n$) y los elementos de $G$ son exactamente las $n$ primeras potencias de $g$ de exponente no negativo: $1=g^0, g=g^1, g^2,\ldots, g^{n-1}$. Además, para cada divisor $k$ de $|G|=n$, $G$ tiene un único subgrupo de orden $k$ (que está generado por $g^{n/k}$). Como consecuencia del Teorema de Lagrange (que veremos próximamente), el orden de cualquier subgrupo de un grupo finito debe ser un divisor del orden del grupo. Por tanto, los subgrupos anteriormente considerados son todos los subgrupos de $G$.
También hemos visto, como corolario, que si $G=\langle g \rangle$ es un grupo cíclico de orden $n$ entonces los conjuntos de generadores de $G$ de cardinal $1$ son los de la forma $\{g^m\}$, siendo $m$ coprimo con $n$. Dicho de otro modo: $G=\langle g^m\rangle$ si y sólo si ${\rm mcd}(n,m)=1$. Por tanto, el número de generadores de cardinal 1 de $G$ es $\varphi(n)$, es decir, la función de Euler de $n$.
Por ejemplo, si $G=\langle g \rangle$ es un grupo cíclico de orden $10$ entonces sus elementos son $\{1, g, g^2,\ldots, g^9\}$ y, además, $G$ tiene $\varphi(10)=4$ sistemas de generadores de cardinal 1, que son $\{g\}$, $\{g^3\}$, $\{g^7\}$ y $\{g^9\}$. Dicho de otro modo: $$G=\langle g \rangle=\langle g^3 \rangle= \langle g^7 \rangle=\langle g^9\rangle.$$
Planteo la siguiente pregunta: ¿cuáles son los sistemas de generadores de cardinal 1 de $\mathbb{Z}$?
Finalmente hemos demostrado que un grupo finito $G$ es cíclico si y sólo si posee un elemento de orden $|G|$.