Criptografía clásica. ¿Cómo romper cifrados monoalfabéticos y polialfabéticos? Análisis de frecuencias y método Kasiski

CRIPTOGRAFÍA CLÁSICA. ¿CÓMO ROMPER CIFRADOS MONOALFABÉTICOS y POLIALFABÉTICOS? ANÁLISIS DE FRECUENCIAS Y MÉTODO KASISKI. Marc García Arnau Estudiante de Telecom Paris (EN ST ) y de la Fa cultad de Infomuízica de la UPM. ¿QUÉ ES LA CRIPTOGRAFÍA? ¿CUÁNDO SURGIÓ? Es fasc in ante ver com o, a lo largo de los ti empos, el hombre ha ido progresando en el arte de controlar los secretos, y como su empeño por dominar la información, ha id o enmarañando los mecanismos para garantizar la con fi dencialidad la de la mism a. La información y su conocimie nt o son consustánciales al hombre ya la vida y, a veces, pueden tomarse comprometidas y p or e ll o, adquirir un gran valo r. La criptografía naci ó, entonces, de la necesidad de salvaguardar la con fi dencialidad de la información. En real idad, la propia raíz etimológica de la palabra criptografía nos da una idea de su utilida d. Del griego (kryptos), «oculto» y (graptos), «escrito», actualmente su defin ic ión podría perfectamente ser la de "arte de cifrar mensajes" o la de "ciencia que estudia los procesos de cifrado y descifrado de los mensajes". El resultado inmediato de cifrar un texto o documento es lo que conocemos por criptograma, y el criptoaná li si s, la cienci a, proceso, o arte, encargado del aná li sis de di chos criptogramas para desc ubrir su clave o su texto o ri gina l. Debemos remontarnos al an ti guo Egipto y a Mesopotami a, es decir, a los orígenes de la civ ili zación humana, para encontrar los primeros indicios de p ro tocriptografí a. Allí se dan ciertos hechos li gados a las escrituras jeroglífica y c un ei fo rme que pretend ia n transfo rm ar deliberadamente la escritur a. A partir de entonces, y a lo largo de los distintos pe ri odos de la histo ri a, se guardan referencias de curiosos e inge ni osos métodos de comunicación secreta con fi nes, habitua lm ente, mil üares o políticos. Como es el caso de la antigua China, donde de usaron métodos más bien est ega nográficos (ocultación de la información), para mantener la privacidad de la mi sm a. Así, se enviaban mensajeros que memo ri zaban los mensajes, o bien éstos se esclib ía n en papel o seda y, tras cubrirlos con una bola de cera, se in vitaba a los siempre dis pu estos mensajeros a esconde rl os en alg un a parte de su cue rp o ( ... ). O como cuando Hi s ti aeus envió un mensaje desde la corte persa a su ye rn o el ti rano Aristágoras de Mileto (G reci a) , para que se sublevara contra el emperador Ciro de Persia antes de que éste les atacase. Para e ll o, afeitó la cabeza de un siervo leal y le tatuó en eUa un mensaje. Eso sí, tuvo que esperar a que le creciera el pelo antes de dejarlo partir hacia Mileto . • RAM A DE E STU D IANTES DEL IEE E DE BARCELO A En el siglo V a. e., durante la guerras entre las polis griegas de Esparta y Atena , ya se usaron ciertos dispositi vos de cifrad o. Como es el ca o de la "escítala de los Lacedemonios", que podría clasificarse dentro de los ll amados métodos de transposición. Consistía en una cinta de papiro enro ll ada en un cilindro o bastón (cuyo di ámetro determina la cl ave), sobre la cual escribían el texto en cl aro ho ri zont al mente. Al desenro ll ar la cinta del bastón, las letras aparecían permutadas y constituí an un mensaje cifrado que, poste ri o rm ente, era enviado al receptor. És te, que di sponía de un a co pi a idéntica del bastón (es decir, conocía la clave) volvía a colocar la cinta y era capaz de leer el mensaje en cl aro. EL CIFRADO DE CESAR Y SU CRIPTOANÁLISIS. Por supuesto, no podíamos olvidar el prim er de los métodos de sustitución monoal fa bé ti ca, el conoc id o método de Cesar. Este método fue el empleado por J ulj o Cesar en sus ca mp añas durante el siglo 1 a. e. para transmitir info nn ación en secreto. Er a, como dec im os, un a sustitución que consistía en cifrar un mensaje empleando un alfabeto equivalente al o ri g in al, pero des pl azado en 3 letras. Es d ec ir, al c ifr ar por ejemplo las palabras GA LO S IRREDUCTIBL ES con este algoritm o, Cesar obtendrí a: JD ÑR VLUU H GXF WL EÑ HV El prim er criptoaná li sis aplica bl e sería el método de complementación al componente origina l, es deci r, probar las 27 permutaciones posibles obtenidas como resultado de desplazar un a posición cada vez las letras de una palabra del criptogram a. Por ejemplo, para JD ÑR V, anal iza nd o los 27 res ul tados es más que probable que encontremos un a ú ni ca palabra que tenga significado en español, con lo cual solo te nd ríamos que utilizar el mismo desplazamiento obtenido para descifrar el resto del text o. El segundo criptoaná li sis a pli ca bl e a este tipo de cifrado es el análisis de frecuencias. De un a fo rm a un tanto más el ega nte qu e el anterior, me di an te este método, es tu di amos la frecuencia rela ti va de aparición de las diferentes letras del texto cifrado, para compararlas con un a descripción estadística que hayamos obtenido del lenguaje, en el qu e sospechemos o sepamos que se encuentra el mensaje o ri ginal También se pu ede realizar un estudio sobre las 95 palabras más usadas, o sobre los digramas y trigramas que constituyen el inicio y terminación más frecuente de las palabras de un lenguaje. Por ejemplo, para un texto en español lo suficientemente representativo, se ha obtenido la siguiente distribución de frecuencias: r--- A 5' 1::.,1:5'1: B 5 1.5~1r e 15 4,5.5\J Análisis de Frecuencias o 15 4,S.5>'!i E 40 12, 12~ F 1 O.::HI$j> 18% 6 s 1,82~ ,'" H • 1.:ns:¡. I 21 6.36:2r 14% . J , 0,91%- '" l 24 1.27% AA B 2.,1.2% 10% . N 20 Ci,OSIS Ñ Q D,OQ::rr o 27 6, lar} f ? 2,12!1J' Q o 0,00\1 R 21 f3,36:! .. . 6% . • • • .. . 11 • , . ... ,. 1111 .U •• 111 .'. IIt.,t ,. S 31 9,33S] .lB COE fG U I J lMNIiOPDRS TUIIlI'fZ T 12 U 10 V ] O.9lÚ' X 1 0,30% Y ] 0,91%' c.i.. 1 O.3[]~ Figuras 1 Y 2.- Análisis de frecuencias del criptograma Este tipo de criptoanálisis es terriblemente efectivo para cifrado monoalfabético. Al emplearlo, se pone en evidencia la principal vulnerabilidad de este método pues, el hecho de sustituir unas letras por otras siguiendo siempre la misma congruencia lineal, hace que las propiedades estadísticas d(1l criptograma y del texto en claro sean exactamente las mismas. Simplemente hay que llevar a cabo un análisis estadístico de los símbolos del criptograma e intentar solaparlo o encajarlo con la distribución de los símbolos de nuestro idioma De esta forma, hallaremos el desplazamiento que fue aplicado al cifrar el texto original y podremos descifrar, inmediatamente, el resto del mensaje. Por ejemplo, si interceptamos el siguiente mensaje cifrado: DQR FLPFXHPWD DPWHV GH FULVWR WRGD ND JDÑLD HVWD RFXSDGA OHPRV XPD SHTXHQD DÑGHD GH LUUHGXFWLEÑHV JDÑRV TXH UHVLVWH DKRUD B VLHOSUH DÑ LPYDVRU El análisis de frecuencias de los símbolos de este criptograma es: 1 1 181 5 616 21 8 6 2 6 28 32 7107 6 1 ABCDEFGHI KLMNÑOPQRSTUVWXYZ Tablal.- Frecuencia de aparición de cada símbolo en el criptograma Si se observa atentamente esta tabla, que refleja el número de apariciones de cada letra en el texto cifrado, y se compara con el gráfico de frecuencias, se puede hallar rápidamente un encaje con otro alfabeto equivalente desplazado. Únicamente hay que tratar de hacer concordar 96 las letras más frecuentes en castellano con las más frecuentes en el criptograma. Así, sabiendo que una de las letras más utilizadas en español es la a, se le puede hacer corresponder laD, que es la más frecuente en nuestro texto cifrado. Cuatro posiciones a la derecha de la D, encontramos la H, también con un altísimo número de apariciones. Se puede entonces pensar que dichaH puede ser la sustituta de la letra e, también muy frecuente en nuestro idioma. En efecto, en el alfabeto español la a y la e distan exactamente cuatro lugares, con lo que se intuye que vamos por el buen camino. Se puede corroborar nuestra hipótesis procediendo de la misma manera con las letras menos frecuentes del lenguaje. Finalmente, concluimos que se trata de un cifrado monoalfabético con la siguiente correspondencia entre letras: Criptograma Frecuencia Texto claro A 1 X B 1 Y C -Z D 18 A E 1 B F 5 C G 6 D H 16 E 1 -F J 2 G K 1 H L 8 1 M -J N -K Ñ 6 L O 2 M P 6 N Q 2 Ñ R 8 O S 3 P T 2 Q U 7 R V 10 S W 7 T X 6 U Y 1 V Z -W Tabla2.- Correspondencia entre las letras del criptograma y las del texto en claro Es decir, el desplazamiento de este cifrado monoalfabético es 3. Para comprobarlo, aplicamos este cambio al mensaje cifrado y obtenemos: AÑo CINCUENTA ANTES DE CRISTO TODA lA GAllA ESTA OCUPADA MENOS UNA PEQUEÑA ALDEA DE IRREDUCTIBLES GALOS QUE RESISTE AHORA y SIEMPREALINVASOR MÉTODO KASISKI. CRIPTOANÁLISIS DE CIFRADOS POLIALFABÉTICOS. La sustitución polialfabética es una generalización de los sistemas de sustitución monoalfabeto. Este tipo de sustitución consiste en cifrar empleando una clave compuesta, es decir, de dos símbolos o más, que se usa cíclicamente. BURAN N°19 ABRIL 2003 Un buen ejemplo de cifrado poliaJfabético es el cifrado de Vigenére, que se sir ve de una tabla para facilitar las operacion es de cifrado y descifrado. Es intere ante resaJtar el h ec ho de que cada una de la fi las de esta tabla no on má que un cifrado de Ce aro La prime ra tiene un de plaza miento de O, la seg un da de 1, y así sucesivamente: A A CD E FG HI JK LM OP CRSTU VW XVZ El ElC E FG I J L MN PQ RS VWXVZA e CDEFGHIJ KLM NO PQRSTU VW XY ZAH D EF HI J KL llOP RS T YW 'IZASC E EF GH IJK LM O PC RSTUV K~Z A CD F FG I J K LMN OP Q RS TU VWX V2 AEl CD E G GH IJ K M NO PQRS TU VWXYZ4 El CD EF H H I JK Lt1 OP QRSTUVW)('IZABC DEFG I IJ LM r OPO T UVWKVZA C DE F H J J K MN OP QR S TU VWXVZA BCD EF GHI K K LHN OP Q RST YW )! '1 Z6El C DE FG I J L LH OP QRST UY KV ZA CDEFG HI JK M MN OP OR ST U VWXV 2AB CD E FG HIJK L N PQ RS TUV WXYZA BCD EF G IJ K LM OPQRS TU VW ~ YZ ~ BCDEFGHIJ KLH N PQRSTU WK~Z A CD EF HI J KLHN O o 5 T U VWX V 2 AB o U G I J L P R STUVW~YZABCD EFG H IJ K rH WPQ 5 s V\ K ZAeC DEFGHIJ KLM NO PQ R T TUVWX V2 AEl CD E FG HI JK LH OP QRS U U VWX~ ~ ABC D EFG HI J ' LMN D PO ST v VW M VZABCD E FGHIJK L MNO P QR S TU W W KV ZABC DE FG HI JK MN OP QRST UY X XV2 AEl CO E FG H IJK L MNO PQRST U VW y y ZA 8CD E FG H I JK L MN OP Of? STU V't/X Z ZAe CDEFG HIJ K MNOP QRS TU VWXY Figura 3.- Ta bl a de Vigenere A dif erencia de l os cifrad os mon oa lf abéticos, l os po li a lf abé ti cos no con se rvan la misma distribución de fr ec uencias del t ex to o ri ginal. Son más pr óx im os a un cifrador id ea l (como el de Ve mam ) ya que su distribución de sí mbolos se acerca más a una U nif orme. Sin e mb argo, pese a ser más seg ur a que la monoaJfabé ti ca, la sustitución po li alfabé ti ca no es inmune aJ criptoaná Li si . Ef ect i va mente, un o fi c iaJ prusiano ll amado Kasiski (1805 - 188 l), elaboró un método p ara haJJ ar el núm ero de aJfabetos en una sustitución po li aJfabética. El método se basa en la id ea de que en todos los idiomas a par ece n grupos de carac ter es con más frecuencia que o tr os. Es dec ir, por eje mplo en caste ll ano, existen ciertos di gramas y trigr amas que ti enen mucha más probabilidad de d arse que otros, en un texto, como so n: es, de, os, en, la, co n, etc. Si un t exto se ci fra con un n úme ro x de alfabetos de forma cíc li ca y, si un grupo de caracter es aparece un númer oyde veces en un texto, és te será cifrado aproximadamente y /n veces con el mismo aJfabeto. En re sumen, en un criptograma lo s uficie n temente ex ten so enco n traremo s, ine lu dibleme nte, repeticiones. P or ejem plo, supon ga mos que ciframos el sig ui ente alfabeto con la cl ave G/N (3 alfabetos ): DEseo FIANZA eo, 1. _ el ell'elNelN elN GI MF I III'ZLP¡'; HN I III'Z KT Se pued e ver como, separada por 9 espacios , aparece repetida la ca dena IWZ . Así pues, se pu ede ya ded ucir que • RAMA DE ESTUDIANTES DEL IEEE DE B ARCELONA los posibles periodos de nuestra clave serán l, 3 ó 9. Hay que decidir se por una de las aJ temativas, así que escogemos el 3 (la corr ec ta, por otro l ado ) para avanzar con el método. A continuación, lo que e de be h acer e r eo rd enar el t exto cifrado en un número de colu mnas igu aJ aJ periodo de clave upuesto correcto. Esta es la estrat eg ia ga nadora pues, tras hacer es to, el problema podrá ser tratado por co I u mnas indep end i en tes. Ca da u na de esa co l u mnas será J M F 1 \Y./ Z L P Ji S H Ji 1 \Y./ Z K T ... un simple cifrado mon oa lfabé ti co, de cript oaná lisis simpl e, co mo ya se ha visto en el apartado a nt e ri or. El pr oblema de d escif r ar un cri pt og rama qu e pr ese nt a ba un a d is tribu ción de fr ec uenci as co ns id er ableme nt e uni fo rm e ha qu eda do re du c id o a tr es an álisis fr ec uencial es ind epen die nt es, un o p ara ca da c olumn a. Es int er esa nt e r esa lt ar qu e, alg un as vece s, pu eden apar ece r repeticion es qu e so n fr ut o de la cas ualidad. Pero ju ega a nu es t ro f avo r el h ec ho de qu e es t as repeticion es cas ual es es tán di s tribuid as al aza r, mie ntr as qu e l as repeticion es útil es a nu es tr a ca u sa se dan ten az me nt e segú n la mi sma pa ut a. Paradó ji ca me nt e, el d oc um e nt o de 95 p ág in as qu e publi có Fr ederich W. K as iski no ca u só nin g ún int er és en su ép oca y d ec idió abandonar el c ript oa náli sis p ara de di ca r se a la a ntr opol ogía . REFERENCIAS [l] http ://s ta rb ase.cs. t rin co ll .e du /-c ry pt o /hi stori cal/ vi ge nere.htrnJ [2] Seg uridad y Protección de la In formación. J o s é Luís Moran t R amo n, ... ED. Ce nt ro de Estudios Ramón Areces, S.A. [3] h ttp :// ri n conquevedo.iespan a.es/ri n co nq uevedo/ Crip tografiaJintrodu cc ion.htm AUTOR Carda Arnau, Mar c. Ingenierio en I nf ormá Ti ca por la UPM. Ac - Tualm e nr e eS Tudia un más Ter en si STemas informáticos en la École Supérieure Nacional de Télécornrnunications . 97