Para poder entender como es que Kasiski rompió un algoritmo polialfabético, es necesario conocer como trabaja primeramente un algoritmo monoalfabético, después un algoritmo polialfabético y finalmete como logró kasiski romper uno de ellos.

[ Cifrado Cesar | Cifrado de Vigenere | Kasiski | Kerckhoff ]

 Para empezar, Cesar fue uno de los primeros que utilizó la criptografía, en su caso, una muy simple pero que funcionó para enviar mensajes seguros en los que describía ordenes para sus comandantes y generales en la guerra de Galias.

El algoritmo que utilizó fue hacer un corrimiento de 3 letras a la derecha sobre el mismo alfabeto que utilizaba, se describe matemáticamente de la siguiente forma:

 Un ejemplo es cuando queremos cifrar el texto "Vuelva a Roma", al que llamamos P(K), el resultado cifrado es C ().

 Con un poco de atención, la manera de romperlo con una máquina con la que trabajamos diariamente es intentar cada no de los 26 cambios posibles y el que de éstos cheque con un texto en inglés legible, se utiliza. Sin embargo, ¿qué tan sencillo es identificar de manera automática el inglés? o ¿de qué manera la computadora reconocería un "texto inglés legible"?. Evidentemente requerimos de un criterio que es un tanto complejo para describir por medio de algoritmos.

Debido a que los cifrados de simple sustitución y corrimiento usan un solo mapeo de texto plano a texto cifrado, la distribución de frecuencias de cada letra se preserva en la encriptación, por lo cual siguen siendo vulnerables a un análisis e frecuencias

Por ejemplo, se sabe que en un texto de 1000 letras de varios alfabetos en inglés, generan la siguiente tabla de ocurrencias:

K DKVO DYVN LI KX SNSYD, PEVV YP CYEXN KXN PEBI, CSQXSPISXQ XYDRSXQ

 Si observamos adecuadamente, nos podemos dar cuenta que haciendo un corrimiento de 10 en el alfabeto, las frecuencias de ambas tablas coinciden en la mayoría de sus letras.

 Si ahora aplicamos esta substitución al mensaje, conseguimos:

C(K) = K DKVO DYVN LI KX SNSYD, PEVV YP CYEXN KXN PEBI, CSQXSPISXQ XYDRSXQ
P(K) = A TA L E TOLD BY AN IDIOT, FULL OF SOUND AND FURY, SIGNIFIYING NOTHIN

 Esto se conoce como análisis de frecuencias y ha sido muy útil para romper algoritmos de cifrado muy débiles

 En el siglo XVI, durante el reinado de Henri III, el francés Blaise de Vigenere propone una tabla que consta de una serie de corrimientos del alfabeto. En este cifrado se tiene una llave K formada por una secuencia de letras K = k1...kd donde cada k provee la cantidad de corrimiento en el alfabeto, matemáticamente,

Para cifrar         c= fi(a) = (a + ki) mod n
Para descifrar   a= fi-1(c) = (c - ki) mod n

Finalmente todo se resume en la siguiente tabla.

 

          A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

      A   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

      B   B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

      C   C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

      D   D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

      E   E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

      F   F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

      G   G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

      H   H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

      I   I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

      J   J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

      K   K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

      L   L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

      M   M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

      N   N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

      O   O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

      P   P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

      Q   Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

      R   R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

      S   S T U V W X Y Z A B C D E F G H I J K L M N O P Q R 

      T   T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

      U   U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

      V   V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

      W   W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

      X   X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

      Y   Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

      Z   Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

 En la tabla se interpreta el lado izquierdo o vertical como la letra de la llave K a utilizar, la parte superior se interpreta como el texto a cifrar (a) y el resultado de la intersección de renglón y columna, como el texto cifrado (c). Básicamente es un sistema de coordenadas.

Ejemplo No. 1:

Se desea cifrar el mensaje M utilizando como llave la palabra MIEDO. Como es de observarse, la longitud de la llave es 5, por lo tanto el texto M se divide en bloques de tamaño 5 y después se procede a cifrar de acuerdo a las intersecciones de la tabla.

M = MISION IMPOSIBLE

C = YQWLCZQQSCEQFOS

Puesto que el procedimiento que se siguió fue:

M = 12, entonces M+M = 24, que equivale a Y
I = 8, entonces I+I = 16, que equivale a Q
S = 18 Y E = 4, entonces S+E = 22, que equivale a W
I = 8 Y D = 3, ENTONCES I+D = 11, que equivale a I
O = 14, entonces O+O = 28 mod 26 = 2, que equivale a C

Y así sucesivamente

Ejemplo No. 2:

Se desea descifrar el cifrado C utilizando como llave la palabra AIRE. Como es de observarse, la longitud de la llave es 4, por lo tanto el texto C se divide en bloques de tamaño 4 y después se procede a descifrar de acuerdo a las intersecciones de la tabla.

M = SBRVCZRJTJISOENERA

M = STARTCRAFT BROOD WARS

Puesto que el procedimiento que se siguió fue:

S = 18 y A = 0, entonces S-A = 18, que equivale a S
B = 1 y I = 8, entonces B-I = -7mod(26), que equivale a T
R = 17, entonces R-R = 0, que equivale a A

 El método fue ideado por un oficial del ejército polaco llamado Kasiski en 1863 con el motivo de romper el cifrado de Vigenere, después de ser considerado irrompible por 300 años.

Se basa en la suposición de que la repetición de una cadena de dos o más caracteres a lo largo del criptograma (texto cifrado) se corresponderán con la misma cadena en el texto plano, por lo que la longitud entre las cadenas será un múltiplo de la longitud de la llave K.

Una vez encontrada la longitud n de la llave K, se divide el texto cifrado en bloques de tamaño n y se realiza un análisis de frecuencias por cada bloque, lo cual es más sencillo que realizarlo a todo el criptograma completo.

Por ejemplo

Texto cifrado : KSMEHZBBLKSMEMPOGAJXSEJCSFLZSY

Si elegimos el factor mas grande (9), se divide el criptograma.

Localización  : 012345678   901234567   890123456 789
Texto cifrado : KSMEHZBBL KSMEMPOGA JXSEJCSFL ZSY

Por lo tanto el texto descifrado queda como:

Texto plano : TO BE OR NOT TO BE THAT IS THE QUESTION

 Este método que Kerckhoff propuso es muy parecido al de kasiski, puesto que utiliza el mismo método para encontrar la longitud de la llave K. La diferencia radica entonces en el siguiente proceso para descifrar los bloques del criptograma

Una vez separado por bloques, el criptograma es ordenado por columnas respetando la longitud del bloque y realiza un análisis de frecuencias en cada columna y un análisis lógico para construir la llave y mas tarde descifrar el criptograma

Siguiendo el ejemplo anterior, se coloca el criptograma en n columnas:

Texto cifrado :

Se realiza un análisis de frecuencias por columna, es decir, K,K,J y Z, S,S,X y Z, M,M,S y Y, E,E y E y así sucesivamente

Un ejemplo mas robusto del análisis de kasiski es el que realizó un alemán llamado Klaus Pommerening el 14 de Agosto de 1997, su correo es Pommerening@imsd.uni-mainz.de

      00    05    10    15    20    25    30    35    40    45
0000  AOWBK NLRMG EAMYC ZSFJO IYYVS HYQPY KSONE MDUKE MVEMP JBBOA
0050  YUHCB HZPYW MOOKQ VZEAH RMVVP JOWHR JRMWK MHCMM OHFSE GOWZK
0100  IKCRV LAQDX MWRMH XGTHX MXNBY RTAHJ UALRA PCOBJ TCYJA BBMDU
0150  HCQNY NGKLA WYNRJ BRVRZ IDXTV LPUEL AIMIK MKAQT MVBCB WVYUX
0200  KQXYZ NFPGL CHOSO NTMCM JPMLR JIKPO RBSIA OZZZC YPOBJ ZNNJP
0250  UBKCO WAHOO JUWOB CLQAW CYTKM HFPGL KMGKH AHTYG VKBSK LRVOQ
0300  VOEQW EALTM HKOBN CMVKO BJUPA XFAVK NKJAB VKNXX IJVOP YWMWQ
0350  MZRFB UEVYU ZOORB SIAOV VLNUK EMVYY VMSNT UHIWZ WSYPG KAAIY
0400  NQKLZ ZZMGK OYXAO KJBZV LAQZQ AIRMV UKVJO CUKCW YEALJ ZCVKJ
0450  GJOVV WMVCO ZZZPY WMWQM ZUKRE IWIPX BAHZV NHJSJ ZNSXP YHRMG
0500  KUOMY PUELA IZAMC AEWOD QCHEW OAQZQ OETHG ZHAWU NRIAA QYKWX
0550  EJVUF UZSBL RNYDX QZMNY AONYT AUDXA WYHUH OBOYN QJFVH SVGZH
0600  RVOFQ JISVZ JGJME VEHGD XSVKF UKXMV LXQEO NWYNK VOMWV YUZON
0650  JUPAX FANYN VJPOR BSIAO XIYYA JETJT FQKUZ ZZMGK UOMYK IZGAW
0700  KNRJP AIOFU KFAHV MVXKD BMDUK XOMYN KVOXH YPYWM WQMZU EOYVZ
0750  FUJAB YMGDV BGVZJ WNCWY VMHZO MOYVU WKYLR MDJPV JOCUK QELKM
0800  AJBOS YXQMC AQTYA SABBY ZICOB XMZUK POOUM HEAUE WQUDX TVZCG
0850  JJMVP MHJAB VZSUM CAQTY AJPRV ZINUO NYLMQ KLVHS VUKCW YPAQJ
0900  ABVLM GKUOM YKIZG AVLZU VIJVZ OGJMO WVAKH CUEYN MXPBQ YZVJP
0950  QHYVG JBORB SIAOZ HYZUV PASMF UKFOW QKIZG ASMMK ZAUEW YNJAB
1000  VWEYK GNVRM VUAAQ XQHXK GVZHU VIJOY ZPJBB OOQPE OBLKM DVONV
1050  KNUJA BBMDU HCQNY PQJBA HZMIB HWVTH UGCTV ZDIKG OWAMV GKBBK
1100  KMEAB HQISG ODHZY UWOBR ZJAJE TJTFU K 

Texto repetido       Indice                 Diferencia

MDUHCQNY            147 1057               910 = 2·5·7·13
YWMWQMZ             345  464  737          119 = 7·17
                                           273 = 3·7·13
ZPYWM                56  462               406 = 2·7·29
UKEMV                37  373               336 = 2·2·2·2·3·7
PJBBO                44 1031               987 = 3·7·47
MDUK                 35  721               686 = 2·7·7·7
RMVU                427 1008               581 = 7·83
VLAQ                104  419               315 = 3·3·5·7
...

Si observamos la diferencia que generó cada texto, vemos que el periodo 7 es el mas repetido y por lo tanto se elige.

Otros links

Investigó Oswaldo Herrera [ correo ]