Tema 3: Criptografía de clave privada
Teoría de códigos y criptografía
Grado en Matemática Aplicada
Tema 3: Criptografía de clave privada
Generalidades
El cifrado de César
Criptosistema afín
Cifrados de sustitución
Criptosistema de Vigenère
Criptosistema de Hill
Permutando, que es udogreni
Enigma
Códigos actuales
Tema 3: Criptografía de clave privada
Generalidades
Alice (A) y Bob (B) quieren establecer un canal seguro de
comunicación. Eve (E) es el adversario y quiere interceptar y
leer los mensajes del canal.
Mensajes: números enteros en cierta base (normalmente 2 o
congruencia mod N) conocida por todos. Alice y Bob crean
un criptosistema (aplicación biyectiva). Usaremos letras
minúsculas para lo que sólo conocen Alice y Bob y con
mayúsculas lo que es conocido también por Eve. Así,
tenemos que:
Alice quiere mandar un mensaje m a Bob.
Alice y Bob comparten una clave secreta k.
Alice tiene una aplicación de cifrado F (·, ·) y puede
calcular en tiempo polinomial F (k, m) = M .
Bob dispone de una aplicación de descifrado G(·, ·) y
puede calcular en tiempo polinomial G(k, M ) = m.
Eve conoce F (·, ·), G(·, ·) y M , pero sin conocer k no
puede calcular m (requeriría tiempo exponencial).
Tema 3: Criptografía de clave privada
Generalidades
Sistema criptográ co
Un sistema criptográ co de clave privada es un par de
funciones F : K × M → C , G : K × C → M, con K: claves
posibles, M: mensajes posibles, C : mensajes cifrados posibles.
Además, si F (k, m) = M , entonces G(k, F (k, m)) = m.
El que Eve conozca F y G parece pérdida de seguridad pero
en la práctica todo sistema se ve comprometido y retado.
Tradicionalmente, se asumen los Principios de Kerckhos
para el sistema:
1 Si no es teóricamente irrompible, debe serlo en la
práctica.
2 La efectividad no debe depender de que su diseño sea
secreto.
3 La clave debe ser fácilmente memorizable (sin escribirla).
4 Los mensajes cifrados darán resultados alfanuméricos.
5 Debe ser operable por una única persona y fácil de usar.
Tema 3: Criptografía de clave privada
Generalidades
Ejemplo
Asignar a cada letra un número empezando en 0 (Z/Z27 en
español y Z/Z26 en inglés por la Ñ).
A B ... Z
0 1 . . . 26
Mensaje: elemento de (Z/ZN )r , donde N y r varían en cada
criptosistema.
Ejemplo
Usar caracteres ASCII para enumerar mensajes. Cada
caracter se sustituye por su número binario. El entero
decimal es el resultante del mensaje. Por ejemplo:
(1010101 1101110 0100000 1101101 1100101 1101110
1110011 1100001 1101010 1100101 0101110)2 7→
85110321091011101159710610146
Tema 3: Criptografía de clave privada
Generalidades
En los mensajes obviaremos espacios, signos de puntuación y
lo representaremos en grupos de 5 letras (es lo habitual en
criptografía). Por ejemplo,
This is our most desperate hour. Help me, Obi-Wan Kenobi.
You're my only hope.
sería
THISI SOURM OSTDE SPERA TEHOU RHELP WANKE
NOBIY OUREM YONLY HOPE
Tema 3: Criptografía de clave privada
El cifrado de César
Es del s. I a.C. en honor a Julio César. Se usó durante la
guerra de las Galias. Se transforma el mensaje mediante el
desplazamiento de caracteres:
Criptosistema César
Sean K = M = C = Z/ZN . El criptosistema César está
de nido por F (k, m) = k + m, G(k, M ) = M − k .
El tradicional cifrado César es con k=3 y alfabeto latino.
m A B C D E F G H I J K L M N
M D E F G H I J K L M N Ñ O P
m Ñ O P Q R S T U V W X Y Z
M Q R S T U V W X Y Z A B C
m =THISI SOURM OSTDE SPERA TEHOU RHELP
WANKE NOBIY OUREM YONLY HOPE
F (3, m) =WKLVL VRXUP RVWGH VSHUD WHKRX
UKHOS PHREL ZDQNH QRELB RXUHP KRSH
Tema 3: Criptografía de clave privada
El cifrado de César
Nos podemos encontrar con el problema de descifrar el
siguiente mensaje cifrado con un criptosistema César:
QMKCR GKCQG RGQRF CNCMN JCLMM LCAYL GKYEG
LCYLQ RFGLE MDUFM BMRFC RFGLE QLMML CAYLG
KYEGL CYJYL RSPGL E
Notemos que el espacio de claves tiene tamaño |K| = N . Es
factible generar por ordenador las N claves posibles y mirar
cuál devuelve algo coherente. Este ataque se llama fuerza
bruta.
El sistema de César se puede complicar también si usamos
una función afín.
Tema 3: Criptografía de clave privada
Criptosistema afín
Criptosistema afín
Un criptosistema afín viene de nido por
K = (Z/ZN )∗ × (Z/ZN ), M = C = Z/ZN , F (k, m) = am + b,
G(k, M ) = a−1 (M − b), donde k = (a, b) ∈ K es la clave.
Ejemplo
N = 26, k = (11, 4). Para cifrar C = 2, tenemos
F (k, C) = F (k, 2) = 11 · 2 + 4 = 26 = 0 = A. Para nuestro
mensaje
m =THISI SOURM OSTDE SPERA TEHOU RHELP
WANKE NOBIY OUREM YONLY HOPE
F ((11, 4), m) = FDOUO UCQJG CUFLW UNWJE FWDCQ
JDWVN MERKW RCPOI CQJWG ICRVI DCNW
El espacio de claves en el sistema afín tiene tamaño
|K| = |(Z/ZN )∗ × (Z/ZN )| = φ(N ) · N
Este número no suele ser muy grande y se puede generar
todas las claves posibles e inspeccionar.
Tema 3: Criptografía de clave privada
Cifrados de sustitución
Los que hemos visto antes son de sustitución. Otros
ejemplos:
El disco cifrador de Alberti (genovés s. XV)
con dos discos concéntricos. Disco exterior:
20 caracteres latinos (sin H,J,Ñ,K,U,W,Y)
y los números 1, 2, 3, 4. Disco interior:
caracteres latinos y además &, H, K, Y .
Para cifrar se sustituye cada caracter del
disco exterior por el del interior. Además se
permite cambiar de posición en medio del
texto tras cifrar una longitud o al aparecer un símbolo.
El escarabajo
de oro es uno de los cuentos más famosos
de Edgar Allan Poe. El protagonista
debe descifrar el mensaje de la imagen.
Tema 3: Criptografía de clave privada
Cifrados de sustitución
En La aventura de los bailarines, uno de los
relatos de El retorno de Sherlock Holmes,
Sherlock atrapa a un criminal descifrando
varios mensajes de este tipo. Para ello se hace un análisis de
frecuencias. Holmes juega el papel de adversario y se ve
como la seguridad del sistema disminuye al aumentar la
cantidad de texto cifrado con el mismo procedimiento.
Criptosistema sustitución
Sea A un alfabeto de N signos identi cado con Z/ZN . Un
criptosistema de sustitución está de nido por M=C=A y
K = SA una permutación de A. Además, F (σ, m) = σ(m),
G(σ, M ) = σ −1 (M ).
Tamaño del espacio de claves: |K| = |SA | = |SN | = N ! Si
N = 256, tenemos 256! ≈ 21684 (enorme). No se puede hacer
por fuerza bruta. Veremos que los criptosistemas de
sustitución serán susceptibles de un ataque estadístico.
Tema 3: Criptografía de clave privada
Criptosistema de Vigenère
Del s. XVII al XIX se consideró infranqueable y no era para
tanto. El nombre se debe a Blaise de Vigenère (1523-1596).
Usa el mismo método que César con la diferencia de que el
desplazamiento viene indicado por el valor numérico
asociado a uno de los caracteres de una clave que se escribe
cíclicamente bajo el mensaje.
Ejemplo
Mensaje (m): ENUNLUGARDELAMANCHADECUYONOMBRE...
Clave (k): CERVANTESCERVANTESCERVANTESCER...
Numéricamente tendríamos:
Mensaje(m):04 13 21 13 11 21 06 00 18 03 04 11 00 ...
Clave(k): 02 04 18 22 00 13 20 04 19 02 04 18 22 ...
Cifrado(M): 06 17 12 08 11 07 26 04 10 05 08 12 22 ...
Mensaje completo cifrado: GQMIL HZEKF ICVMN GGZCH
VXULI...
Tema 3: Criptografía de clave privada
Criptosistema de Vigenère
Criptosistema de Vigenère
Sea K = M = C = (Z/Z26)r . Se de ne el criptosistema de
Vigenère de longitud r y clave k = (k1 , . . . , kr ) como el par de
funciones F (k, m) = k + m, G(k, M ) = M − k , donde los
bloques son mensajes de la forma m = (m1 , . . . , mr )
Una misma letra se puede cifrar de maneras diferentes
dependiendo de qué letra de la clave le toque para cifrarse
en cada momento.
Se creía que este criptosistema era seguro, pero es posible
atacarlo con el método Kasiski (averiguar longitud de la
clave, r, y resolver r cifrados de César).
Mejora posible: cifrado en modo CBC que es cambiando la
clave en bloques sucesivos. Si el mensaje es m = m1 m2 m3 . . . ,
M1 = F (k, m1 ), M2 = F (M1 , m2 ), M3 = F (M2 , m3 ), . . . Para el
descifrado:
m1 = G(k, M1 ), m2 = G(m1 , M2 ), m3 = G(m2 , M3 ), . . .
Tema 3: Criptografía de clave privada
Criptosistema de Hill
Vigenère generaliza a César y veremos ahora la
generalización del cifrado afín usando una dimensión más
alta.
Criptosistema de Hill
El criptosistema de Hill es el de nido por
k = A ∈ K = GL(n, Z/Z26), m ∈ (Z/Z26)n = M = C,
F (k, m) = Am, G(k, M ) = A−1 M
Ejemplo
11 6
Si n = 2, k = , cuyo determinante es una unidad
9 7
enZ/Z26. Entonces nuestro mensaje
m =THISI SOURM OSTDE SPERA TEHOU RHELP
WANKE NOBIY OUREM YONLY HOPE se cifra como
M =RMOQO QOGZD OQRFD QJDZF RDMOG ZMDTJ
TFVFD VOZOV OGZDD VOVTV MOJD
Tema 3: Criptografía de clave privada
Criptosistema de Hill
El criptosistema es difícil de romper conociendo solo el texto
cifrado, pero es fácil si es posible inferir algún trozo del texto
con un sistema de ecuaciones. Es posible generalizar un poco
este criptosistema:
Criptosistema de Hill generalizado
Sean k = (A, b) ∈ GL(n, Z/Z26) × (Z/Z26)n ,
m ∈ (Z/Z26)n = M = C , F (k, m) = Am + b,
G(k, M ) = A−1 (M − b)
Tema 3: Criptografía de clave privada
Permutando, que es udogreni
El cifrado de permutaciones en forma de escítala espartana
es el más antiguo (s. V a. C.). La escítala era un par de
varas de madera de grosor jado por emisor y receptor. Para
cifrar un mensaje se enrollaba una piel o papiro alrededor.
Para descifrarlo, el receptor tenía que volver a enrollar el
papiro en la otra escítala. Por ej. ATACALASTERMOPILAS
se codi caba como ALRLTAMAASOSCTP-AEI-. Hemos
añadido un par de signos para hacerlo de longitud 20
(debilidad de este cifrado de permutaciones). Este es un ej.
del cifrado de trasposición, caso particular del cifrado de
permutación, que consiste en aplicar una permutación a
bloques del texto m. Se usaban permutaciones de pocos
elementos (7 por ej.).
Criptosistema de permutación
Un criptosistema de permutación de r letras del alfabeto A
viene dado por M = Ar = C , K = Sr ,
F (σ, (m1 , . . . , mr )) = (mσ−1 (1) , . . . , mσ−1 (r) ),
G(σ, (c1 , . . . , cr )) = (cσ(1) , . . . , cσ(r) )
Tema 3: Criptografía de clave privada
Permutando, que es udogreni
Ejemplo
Para
m =THISI SOURM OSTDE SPERA TEHOU RHELP
WANKE NOBIY OUREM YONLY HOPEX XXX
ha sido necesario añadir 4 símbolos para que su longitud
fueramúltiplo de 9. Con la permutación
1 2 3 4 5 6 7 8 9
σ= tenemos que la inversa
7 1 8 5 9 2 3 4 6
es:
−1 7 1 8 5 9 2 3 4 6
σ = =
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
2 6 7 8 4 9 1 3 5
El cifrado de m sería
M = HSOUS RTIIO ESPTE MSDAO UREHR THLOB
IMWEP ENOBI EYAKN UYONE LORMH YOE
Tema 3: Criptografía de clave privada
Enigma
La máquina Enigma, creada
por Arthur Scherbius en 1918 y patentada
en 1928, fue un hito en la criptografía.
Era una evolución de otros modelos
que intentaban automatizar el cifrar
y descifrar mensajes de contenido militar.
Consistía en tres rotores que eran
permutaciones de las letras que actuaban
consecutivamente. Además hay un receptor
que hace que el proceso de cifrado y
descifrado sea el mismo. La clave de cifrado
consiste en 3 letras con la posición inicial de
los 3 rotores que se podían escoger libremente dando logar a
263 claves. Los modelos militares eran más complejos:
Cinco rotores de los que se eligen 3 y funcionan en
cierto orden.
Anillos para modi car el movimiento de 2º y 3º rotor.
Steckerbrett: tablero de clavijas cada una asociada a una
letra si se conectaban dos por cable se intercambiaban
en el cifrado.
Tema 3: Criptografía de clave privada
Enigma
Ejemplo
Rotor ABCDEF GHIJKLM N OP QRST U V W XY Z
I EKM F LGDQV ZN T OW Y HXU SP AIBRCJ
II AJDKSIRU XBLHW T M CQGZN P Y F V OE
III BDF HJLCP RT XV ZN Y EIW GAKM U SQO
Ref lector Y RU HQSLDP XN GOKM IEBF ZCW V JAT
Al pulsar E se movía el rotor III:
Rotor ABCDEF GHIJKLM N OP QRST U V W XY Z
I EKM F LGDQV ZN T OW Y HXU SP AIBRCJ
II AJDKSIRU XBLHW T M CQGZN P Y F V OE
III DF HJLCP RT XV ZN Y EIW GAKM U SQOB
Ref lector Y RU HQSLDP XN GOKM IEBF ZCW V JAT
A continuación ciframos la letra E así:
E 7→ L 7→ H 7→ R ↔ B 7→ K 7→ L 7→ Z , donde ↔ es la
permutación del re ector. Para la siguiente letra, digamos N,
volvía a avanzar el rotor III. Cuando el rotor daba la vuelta
completa, el segundo rotor se movía, luego el siguiente. El
re ector es invariante.
Tema 3: Criptografía de clave privada
Códigos actuales
Tenemos dos tipos:
CÓDIGOS DE FLUJO (RC4 es el más conocido)
Están asociados a una función que es un generador de
claves, K(·). Ésta genera una clave para cifrar a partir de
nuestra clave privada k, y esta clave K(k) es que se usa en el
cifrado. La función debe estar bien escogida para que la
longitud de K(k) sea grande, que tenga caracter aleatorio
pasando unos test de modo que sea indistinguible de una
cadena aleatoria de números y que la complejidad del
algoritmo para hallar K(k) sea polinomial.
CÓDIGOS DE BLOQUE
Rompen el mensaje en bloques de un tamaño pre jado. Por
ej. de 64 bits (DES) y 128 bits (AES). La clave para cifrar se
aplica a cada bloque por separado. El cifrado se realiza varias
veces.
Tema 3: Criptografía de clave privada
Códigos actuales
Veamos un ej. de un código en bloque: cifrado de Feistel
(base del DES, donde se aplica Feistel 16 veces). Fiajmos
(públicamente) una función F (·, ·) que toma como entrada la
clave de cifrado k y un bloque de texto que sea la mitad del
total a cifrar. Operamos como sigue:
Dividimos el mensaje en dos mitades m = [ℓ | r]
Hallamos F (k, r)
Calculamos M = [r | ℓ ⊕ F (k, r)]
No parece gran cosa porque la primera mitad del texto
cifrado es la segunda mitad del original, pero al realizar una
nueva codi cación ya todo resto del texto original
desaparece. Fue ideado por Feistel e investigadores de IBM
en los 70 para aplicarlo de forma iterada.
Para el descifrado, Bob recibe M = [r | ℓ ⊕ F (k, r)] = [L | R] y
calculada F (k, r) (Bob conoce r pues r = L), puede
recuperar m = [R ⊕ F (k, L) | L].
Tema 3: Criptografía de clave privada
Códigos actuales
Ejemplo
Aplicar dos rondas de Fesitel sobre el mensaje
011110100001
1 2 3
con función de nida por la permutación σ=
2 1 3
1ª ronda
m = [ℓ | r], con ℓ = 011110, r = 100001
F (r) = 010001
ℓ ⊕ F (r) = 011110 ⊕ 010001 = 001111. Por tanto,
M = [r | ℓ ⊕ F (r)] = [100001 | 001111]
2ª ronda
m′ = [ℓ′ | r′ ], con ℓ′ = 100001, r′ = 001111
F (r′ ) = 001111
ℓ′ ⊕ F (r′ ) = 100001 ⊕ 001111 = 101110. Por tanto,
M ′ = [r′ | ℓ′ ⊕ F (r′ )] = [001111 | 101110]
La respuesta sería 001111101110.
Tema 3: Criptografía de clave privada
