Criptografía elemental

Definición de código criptográfico

Un código definido en K, M y C con un par de de algoritmos eficientes* (E,D) donde:

$E=K\times M\rightarrow C$

$D=K\times C\rightarrow M$

Además, debe cumplirse que:

$\forall \,m \in M, k\in K: D(k,E(k,m))=m$

*Eficiente aquí se refiere a que la ejecución de estos algoritmos debe producirse en tiempo polinomial.

El algoritmo E puede tener una componente aleatoria en su salida pero el algoritmo D siempre es determinista.

Ejemplo característico: Libreta de un sólo uso (One time pad)

El “tamaño” del mensaje m, la clave k y el cifrado c son iguales a n.

$M={\left\{0,1\right\}}^n, K={\left\{0,1\right\}}^n,C={\left\{0,1\right\}}^n$

El algoritmo de cifrado y de descifrado es la operación o-exclusiva (XOR).

Cifrado:

$c=k\oplus m$

Descifrado:

$m=k\oplus c$

Teoría de la seguridad en la información (Shanon 1949)

La idea intuitiva es que c no debe revelar información sobre m. Sin embargo la definición formal es más compleja como se verá a continuación.

Un código de cifrado tiene secreto perfecto si:

$\forall \,m_0,m_1\, con\, y\,\forall c\in C$

$Longitud(m_0)=Longitud(m_1)$

$P\left[ E\left(k,m_0\right)=c\right]=P\left[ E\left(k,m_1\right)=c\right]$

k es uniforme en el espacio K, esto es $k \xleftarrow{R} K$

Teorema: Para que un código posea “secreto perfecto”

$\mid K\mid\geq \mid M\mid$

Es decir, la longitud de k debe ser mayor o igual a la longitud de m, el código one time pad —en adelante OTP— cumple la condición el el límite.

Cifrador de flujo (Stream cipher)

Aquí la idea es remplazar la k aletoria de OTP un una pseudo-aleatoria. Un generador de claves pseudo-aleatorias o PRG (Pseudo Random Generator) es una funcion G que:

$G: \left \{ 0,1 \right \}^{s} \rightarrow \left \{ 0,1 \right \}^{n} ; s\ll n$

El algoritmo que genera esta función debe ser eficiente y su salida debe parecer aleatoria —más sobre esto después—. Esta nueva clave sustituirá a la k usanda en el OTP:

Cifrado:

$c=G\left(k\right)\oplus m$

Descifrado:

$m=G\left(k\right)\oplus c$

Tal y como indicó Shannon este tipo de cifrado no tiene secreto perfecto y por lo tanto habrá que definir lo que se considera un generador G seguro, mientras tanto veamos la definición de un generador G impredecible.

Para que un generador G sea impredecible no tiene que existir un algoritmo eficiente A que conocidos los i primeros bits generados permita calcular los n-i bits restantes.

$\exists i : G\left(k \right )\mid _{1,...i}\,\xrightarrow{algoritmo}G\left(k \right )\mid _{i+1,...n}$

Matemáticamente un generador es predecible si existe un algoritmo A tal que…

$\exists A\, y\, \exists \left [ 1\leqslant i\leqslant (n-1)\right ]: P\left [ A\left\{G\left(k \right )\mid _{1,...i} \right \}=G\left(k \right )\mid _{i+1} \right ]\geqslant \left ( 1/2 +\varepsilon \right )$

Con:

$k \xleftarrow{R} K$ y un $\varepsilon$ no despreciable.

Por lo tanto, un algoritmo será impredecible si no es predecible —¡vaya vuelta para contar esto!—.

Notas finales sobre qué es despreciable:

En la práctica:

$\varepsilon$ se considera no despreciable si $\varepsilon \geqslant \frac{1}{2^{30}}$ (1GB de datos) y se considera despreciable si $\varepsilon \geqslant \frac{1}{2^{80}}$

En teoría:

$\varepsilon$ es una función tal que $\varepsilon:Z^{\geq 0}\rightarrow R^{\geq 0}$

$\varepsilon$ se considera no despreciable si $\exists d:\varepsilon\left(\lambda \right )\geqslant 1/\lambda^{d}$ y se considera despreciable si $\forall d, \lambda\geqslant \lambda_d: \varepsilon \left(\lambda \right )\leqslant 1/\lambda^{d}$

—Ejemplo despreciable: $\varepsilon \left(\lambda \right )=1/2^{_{\lambda}}$

Para un d dado existe una $\lambda$ tal que satisface la ecuación.

—Ejemplo no despreciable: $\varepsilon \left(\lambda \right )=1/\lambda^{_{1000}}$

En el ejemplo se comprueba que si se toma una $\lambda$ mayor a 1000 la condición no se cumple.