Criptografía

Christian Chávez
Erick Altamirano

Universidad Yachay Tech 2023

Contenido

1. Conceptos Básicos de Criptografía
2. Cifrado Monográfico
3. Cifrado por Bloques
4. Cifrado Exponencial
5. Sistemas de Clave Pública

Preliminares

• Texto plano. El mensaje (leible) que será transmitido.
• Texto cifrado. El mensaje codificado (secreto).
• Clave: lo que te permite cifrar o descifrar.
• Alfabeto: Sistema de símbolos (letras, números, etc.).

Cifrados Monográficos

Cifrados Monográficos

Cifrado de Julio César: desplaza las letras del alfabeto por un número fijo de posiciones.

Cifrado y Decifrado

• A cada letra $\ell$ se le asigna un valor $n$ entre $0$ y $26$
• Desplazar cada valor por $3$ significa $$n \mapsto n + 3 \!\!\! \mod 27$$
• Para recuperar el mensaje, $$n \mapsto n - 3 \!\!\! \mod 27$$

Asigne un valor entero a cada letra

Recorra $3$ cada valor

Ejemplo

Cifrados monográficos más sofisticados

• Por agrupación
• Transformaciones afines
• Transposición
• $\cdots$

Cifrados monográficos más sofisticados

Cifrados monográficos más sofisticados

$$ n \mapsto a n + b \!\!\! \mod 27 $$

Cifrados monográficos más sofisticados

Requerimos que $(a,27) = 1$ para poder descifrar con

$$ n \mapsto a^{-1}(n-b) \!\!\! \mod 27 $$

Cifrados monográficos más sofisticados

Cifrado en bloques

Cifrado en bloques

• Tomamos el equivalente numérico de un texto plano y lo dividimos en grupos de $n$ letras, que tratamos como un vector $P$ de $\mathbb{R}^n$
• Luego multiplicamos cada vector $P$ por una matriz $A$ de tamaño $n\times n$ y tomamos residuos módulo $k$.

Cifrado en bloques

• Es decir, los vectores cifrados son de la forma $$C \equiv A P \pmod{k}$$
• donde $k$ es el tamaño del alfabeto

Cifrado en bloques

$A$ debe ...

• tener componentes en $\mathbb{Z}_k$
• ser invertible y además $(\det A, k)=1$

Ejemplo

Consideremos la matriz $ A = \begin{bmatrix} 7 & 11\\ 3 & 2 \end{bmatrix} $ con componentes en $\mathbb{Z}_{27}$ y $$(\det A, 27) = (8,27)=1$$

Ejemplo

• Dividimos el texto plano en grupos de $n=2$ letras
• y lo transformamos en su equivalente numérico

YA $\to$ $\begin{bmatrix} 24\\0 \end{bmatrix}\quad$ CH $\to$ $\begin{bmatrix} 2\\7 \end{bmatrix}\quad$ AY $\to$ $\begin{bmatrix} 0\\24 \end{bmatrix}$

Ejemplo

• Aplicamos la transformación $C \equiv A P \pmod{27}$
• Por facilidad, ponemos los vectores $C$ como columnas de una matriz y la multiplicamos por $A$

Ejemplo

• Utilizando el alfabeto encontramos el texto cifrado
$$ \mathrm{GR}\ \mathrm{KT} \ \mathrm{UU} $$
• Un texto plano que difiera por una única letra del original puede tener asociado un texto cifrado muy diferente

Decifrado

• Hallamos $A^{-1}$ y aplicamos la transformación inversa $$P \equiv A^{-1} C \pmod{27}$$
• La matriz $A^{-1}$ existe pues $(\det A, 27) = 1$

Decifrado

• En el ejemplo anterior, $$ \begin{align*} A^{-1} &= (\det A)^{-1} \begin{bmatrix} 2 & -11\\ -3 & 7 \end{bmatrix}\\ &=17 \begin{bmatrix} 2 & -11\\ -3 & 7 \end{bmatrix}\\ &\equiv \begin{bmatrix} 7 & 25\\ 3 & 11 \end{bmatrix} \pmod {27} \end{align*} $$

Observaciones

• Como en el caso de cifrado de caracteres, una forma más general de cifrar por bloques, es aplicando a los vectores una transformación afín de la forma $$ C \equiv AP + B \pmod{27}$$

Observaciones

• El cifrado de Hill fue el primer cifrado de sustitución poligráfico basado en álgebra lineal,
• aunque es suceptible al criptoanálisis.
• Pero podemos aumentar su seguridad tomando $n$ suficientemente grande.

Cifrados Exponenciales

Cifrados Exponenciales

• Son relativamente resistentes al criptoanálisis
• Ciframos y deciframos mensajes utilizando exponenciación modular

Consideremos el siguiente alfabeto

Cifrado

1. Dividimos al texto plano en grupos de $2n$ letras
2. Tratamos a cada bloque $P$ como un único entero
3. Escogemos un primo $p$ tal que $ 2626 < p < 262626$ Recordar: nuestro alfabeto es de tamaño $k=27$
4. Escogemos un entero $e$ tal que $(e,p-1) = 1$
5. Calculamos los bloques cifrados $C \equiv P^e \pmod{p}$

Cifrado

• El texto cifrado es la lista enteros $C$
• No se convierte a letras
• La clave de cifrado es $e$
• Calcular $C \equiv P^e \pmod{p}$ requiere esfuerzo, pero no es nada difícil para una computadora de hoy en día

Algoritmo para calcular $P^e\pmod{p}$

1. Encontramos la representación de $e$ en base $2$, digamos $e=(r_k r_{k-1} \cdots r_0)_2$
2. Calculamos $P, P^2, P^4, \ldots, P^{2^k}$ reduciendo $\text{mod} \,p$
3. Escribimos $P^e$ como el producto $$P^{r_{k}2^k}P^{r_{k-1}2^{k-1}} \cdots P^{r_0 2^0}$$
4. Simplificamos y tomamos residuos módulo $p$

Ejemplo 1: Calculemos $2743^{21}\pmod{2897}$

1. La representación de $21$ en base $2$ es $(1,0,1,0,1)_2$
2. Calculamos $$ \begin{align*} 2743 &\equiv 2743 &&\pmod{2897}\\ 2743^2 &\equiv 540&&\pmod {2897} \\ 2743^4 &\equiv 1900&&\pmod {2897} \\ 2743^8 &\equiv 338&&\pmod {2897} \\ 2743^{16} &\equiv 1261&&\pmod {2897} \end{align*} $$

Ejemplo 1: Calculemos $2743^{21}\pmod{2897}$

3. Como $$21=1\cdot 2^4 + 0\cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0,$$ tenemos

$$ \begin{align*} 2743^{21} &\equiv 2743^{ 2^4} \cdot 2743^{ 2^2} \cdot 2743^{ 2^0} \pmod{2897}\\ &\equiv 1261 \cdot 1900 \cdot 2743 \pmod{2897}\\ &\equiv 81 \cdot 2743 \pmod{2897}\\ &\equiv 2011 \pmod{2897} \end{align*} $$

Ejemplo 2

$$ \mathrm{ ''GENERALIZAR\>\> ES\>\> SIEMPRE }$$ $$ \mathrm{EQUIVOCARSE'' } $$

Ejemplo 2

• Convertimos las letras del texto en su equivalente numérico y formamos bloques de longitud cuatro obteniendo $$ \begin{array}{llllllll}0604 & 1304 & 1800 & 1108 & 2600 & 1804 & 1919 & 0804 \\ 1216 & 1804 & 0417 & 2108 & 2215 & 0200 & 1819 & 0424\end{array} $$ donde adicionamos al final los dos dígitos $24$, correspondientes a la letra \(\mathrm{X}\), para que todos los bloques tengan cuatro dígitos.

Ejemplo 2

• Aplicamos la transformación $P^{17} \pmod{2707}$ a cada bloque $P$
• Después de algún trabajo obtenemos, usando el algoritmo anterior, el texto cifrado que es \[\begin{array}{cccccccc}0185 & 2343 & 1853 & 0912 & 1316 & 2524 & 2645 & 1781 \\ 2653 & 2524 & 1325 & 2111 & 1615 & 0084 & 1543 & 0504\end{array}\]
• Recordar: el texto cifrado lo dejamos en valores numéricos, no lo convertimos a letras

Decifrado

• Aplicamos $P\equiv C^d\pmod{p}$ donde $d=e^{-1} \pmod{p-1}$.

Observaciones

• Para que un criptoanalista descifre un mensaje se necesita un gran tiempo de computación.
• Aún conociendo el primo $p$, se necesitan años para determinar $e$, cuando $p > 100$.

Sistemas de Clave Pública