Cifrado Vigenere

P=C=K=(Z26)m

K=(k1,k2,……..,km)

ek=(x1,x2,….,xm)=(x1+k1,x2+k2,….xm+km)dk=(y1,y2,…ym)=(y1-k1,y2-k2,….ym-km)

Tabla de equivalencias:A>0,B>1,…..Z>26 (idioma ingles – Z>27 para castellano)

Ejemplo

P=thiscryptosystemisnotsecureK=cipher, m=6

Si cifro las primeras letras:19 7 8 18 2 17 24 15 192 8 15 7 4 17 2 8 15______________________________________________21 15 23 25 6 8 0 23 8

C=vpxzgiaxi….

¿Cuántos valores posibles de claves hay?

26m

Cifrado polialfabético

X1

X2.

Xi.

Xn

k1K2...

km

Y1Y2.

Yi.

yn

P K C

Método Kasiski(Friedrich Kasiski 1863)

OBJETO: Sirve para estimar el largo de la clave– Se basa en observar que dos segmentos idénticos

del texto claro, serán transformados al mismo texto cifrado siempre que la distancia entre segmentos sea una d, tal que d = 0 mod m. Siendo m la long. de la clave.

– El test busca dentro del texto cifrado pares de segmentos idénticos de un largo de por lo menos tres y guarda la distancia entre posiciones de los dos segmentos. El largo de la clave podría ser el m.c.d. de los di (es una suposición).

Indice de coincidencia (Wolfe Friedman 1920)

OBJETO: Sirve para estimar el largo de la clave– Es la probabilidad de que dos elementos de un texto,

tomados al azar, sean idénticos.– Si fi es la frecuencia de apariciones de la letra xi, se

puede escribir:P(a)=fa.(fa-1)/n.(n-1)Ic= (Σfi(fi-1))/n(n-1) 0<=i<=25

Información obtenida a partir del Ic

• Ic ˜ Σpi2 = 0.065 (para el inglés)

• Si el string de datos tiene frecuencia de apariciones totalmente aleatoriaIc ˜ 26.(1/26)2 = 1/26 = 0.038

• Como el texto cifrado (por un encriptadormonoalfabético) mantiene el mismo Ic que para el texto en claro se divide el texto encriptado en Vigenere en tantos subtextos como el largo de la clave supuesto. Luego para cada subtexto se puede calcular su Ic y si los valores fueron estimados correctamente el Ic de cada uno de ellos tendrá un valor cercano a 0.065.

Indice de Coincidencia Mutuo

OBJETO: Sirve para estimar la clave• Es la probabilidad de que un elemento elegido al azar

del texto ‘x’ sea idéntico a otro del texto ‘y’ también elegido al azar.

• MIc(x,y)= (Σfi.fi’)/n.n’ 0<=i<=25

0.04313

0.03912

0.04511

0.03810

0.0349

0.0348

0.0397

0.0366

0.0335

0.0444

0.0343

0.0322

0.0391

0.0650

VALOR ESPERADO PARA MicCORRIMIENTO RELATIVO

MIc esperados

Armado de la máscara de la clave

• Se utiliza una variación del indice Mic (por corrimiento relativo ‘g’).MIc(x,yg)= (Σfi.fi-g’)/n.n’ 0<=i,g<=25

• Esto se calcula tomando los subtextos de a pares y encriptando al segundo con un valor de g posible. El valor de g que haga que que Mic(x, yg)=0.065 da la distancia entre claves utilizadas en esos subtextos.

• Entonces,Kx- Ky = g

• Finalmente se deberan calcular todos los MIc necesarios para establecer todas las ecuaciones necesarias para resolver el sistema y establecer la máscara para la clave

Ejemplo

• Se parte de la hipótesis de m=5• Se computan los 260 valores MIc(yi,yj

g), donde 1 = i < j = 5, 0 = g = 25.

• Para cada par (i,j) se buscan los valoresMIc cercanos a 0.065. Si existe un único valor se estima que el g utilizado corresponde al corrimiento relativo entre ese par.

Tabla

54

53

43

52

42

32

51

41

31

.028 .027 .028 ……….068 ……………03621

Valor Mic para 0 = g = 25ji

Ecuaciones

• Incógnitas: k1,k2,k3,k4,k5k1 – k2 = 9 k1 – k5 = 16k2 – k3 = 13K2 – k5 = 7K3 – k5 = 20K4 – k5 = 11

MASCARA = (K1,K1+17,K1+4,K1+21,K1+10)La clave será algún corrimiento cíclico de AREVK

Bibliografía

• Douglas R. Stinson, “Cryptography, Theory and Practice”

• David Kahn, “The Codebreakers”