b'\n_START_ARTICLE_\nCriptoan\xc3\xa0lisi lineal\n_START_PARAGRAPH_\nLa Criptoan\xc3\xa0lisi lineal \xc3\xa9s una t\xc3\xa8cnica inventada per Mitsuru Matsui, investigador de Mitsubishi. Data de 1993 i va ser desenvolupada inicialment per trencar l\'algorisme de xifratge sim\xc3\xa8tric DES. Aquest tipus de Criptoan\xc3\xa0lisi es basa en un concepte anterior al descobriment de Matsui: les expressions lineals probabilistiques. Aquestes \xc3\xbaltimes han estat estudiades per Henri Gilbert i A. Tardy-Cordfir en el marc d\'un atac sobre FEAL. _NEWLINE_La Criptoan\xc3\xa0lisi lineal \xc3\xa9s m\xc3\xa9s efica\xc3\xa7 que la Criptoan\xc3\xa0lisi diferencial per\xc3\xb2 menys pr\xc3\xa0ctica per la senzilla i bona ra\xc3\xb3 que es parteix del principi que l\'agressor no disposa de la caixa negra simbolitzant l\'algorisme de xifratge i que no pot sotmetre els seus propis texts. En el cas de DES, aquest atac requeria inicialment  parelles (tots avaluats amb la mateixa clau) del que l\'agressor ha pogut recuperar per un mitj\xc3\xa0 o un altre. Llavors, Matsui millora el seu algorisme el 1994 i proposa una soluci\xc3\xb3 amb  parelles. La complexitat amb una bona implementaci\xc3\xb3 \xc3\xa9s tanmateix inferior i de l\'ordre de  operacions DES. _NEWLINE_La Criptoan\xc3\xa0lisi lineal consisteix a fer una aproximaci\xc3\xb3 lineal de l\'algorisme de xifratge simplificant-lo. Augmentant el nombre de parelles disponibles, es millora la precisi\xc3\xb3 de l\'aproximaci\xc3\xb3 i se\'n pot extreure la clau. Tots els nous algorismes de xifratge han de procurar ser resistents a aquest tipus d\'atac. DES no estava dissenyat per impedir aquest tipus de m\xc3\xa8tode, les taules de substituci\xc3\xb3 (caixes S) presenten en efecte certes propietats lineals mentre que estaven precisament previstes per afegir una no-linealitat a DES._NEWLINE_S\'ha aplicat amb \xc3\xa8xit sobre diversos algorismes com LOKI, FEAL o una versi\xc3\xb3 simplificada de Serpent. Els algorismes m\xc3\xa9s recents com AES(Rijndael) IDEA i d\'altres encara s\xc3\xb3n insensibles a un atac lineal. La complexitat de l\'atac \xc3\xa9s en aquests casos \xc3\xa0mpliament superior a la d\'un cerca exhaustiva.\n_START_SECTION_\nResultats\n_START_PARAGRAPH_\nEs veu que la primera equaci\xc3\xb3 \xc3\xa9s satisfeta 4 vegades sobre 8 mentre que l\'equaci\xc3\xb3 (2) no ho \xc3\xa9s m\xc3\xa9s que 2 sobre 8. L\'equaci\xc3\xb3 (1) \xc3\xa9s per tant una aproximaci\xc3\xb3 millor de la substituci\xc3\xb3 per\xc3\xb2 no \xc3\xa9s per for\xc3\xa7a la millor, un c\xc3\xa0lcul sobre totes les equacions possibles permet respondre a aquesta q\xc3\xbcesti\xc3\xb3. _NEWLINE_Es repeteix aquest tipus d\'estimaci\xc3\xb3 sobre diverses porcions de l\'algorisme de xifratge, aquesta etapa varia segons la seva arquitectura. Gr\xc3\xa0cies a aquestes aproximacions, s\'intenta trobar porcions de les claus intermedi\xc3\xa0ries (les subkeys).\n_START_SECTION_\nExemple\n_START_PARAGRAPH_\nEs considera ara un algorisme de xifratge molt senzill que pren 3 bits en entrada i subministra a 3 bits avaluats en sortida.\n_START_SECTION_\nNotaci\xc3\xb3\n_START_PARAGRAPH_\nSigui  la dada en clar de 3 bits. Sigui , el resultat final i xifrat de 3 bits. Siguin quatre claus intermedi\xc3\xa0ries  tretes de la clau principal i fetes servir per als tres etapes interm\xc3\xa8dies i el XOR final. Sigui , la funci\xc3\xb3 "substituci\xc3\xb3" amb la taula de substituci\xc3\xb3 n\xc2\xb0i. Sigui  la notaci\xc3\xb3 per al bit j de la clau i. Les tres taules s\xc3\xb3n similars a aquella descrita abans.\n_START_SECTION_\nRecuperaci\xc3\xb3 de les claus\n_START_PARAGRAPH_\nEs t\xc3\xa9 a m\xc3\xa0 una aproximaci\xc3\xb3 de les 3 primeres voltes de l\'algorisme de xifratge per\xc3\xb2 manca la clau de l\'\xc3\xbaltima volta, sigui  en el nostre cas. \xc3\x89s aqu\xc3\xad que intervenen els missatges avaluats a la nostra disposici\xc3\xb3. Es pren un missatge i s\'intenta desxifrar-lo provant totes les claus  possibles. S\'interessa m\xc3\xa9s particularment pels resultats al final del xifratge. M\xc3\xa9s precisament, es pren un missatge avaluat  i s\'efectua un XOR amb l\'\xc3\xbaltima clau : . Aix\xc3\xb2 correspon a la sortida de l\'\xc3\xbaltima taula de substituci\xc3\xb3. S\'efectua ara la substituci\xc3\xb3 inversa, la taula \xc3\xa9s coneguda: ._NEWLINE_Ara b\xc3\xa9 aquest valor correspon de fet al membre de l\'esquerra de la nostra equaci\xc3\xb3 lineal. Es t\xc3\xa9 aix\xc3\xad: . Es pot per tant tenir una estimaci\xc3\xb3 de la validesa de les claus provades comparant el valor exacte tornat per la substituci\xc3\xb3 inversa i l\'aproximaci\xc3\xb3 lineal sobre tots o una part dels bits. Amb un gran nombre de parells de missatges, es pot assolir m\xc3\xa9s precisi\xc3\xb3 de les estimacions. Per descobrir les altres claus interm\xc3\xa8dies, s\'ataca l\'algorisme pujant progressivament les voltes fins a arribar a la primera clau._NEWLINE_Sobre xifratges m\xc3\xa9s complexos com DES, no s\'interessa m\xc3\xa9s que per una part de les subclaus per tal de disminuir la complexitat de l\'atac. Un estudi m\xc3\xa9s profund permet determinar quins bits de l\'\xc3\xbaltima subclau tenen verdaderament una influ\xc3\xa8ncia sobre l\'aproximaci\xc3\xb3 lineal. En el seu exemple amb un DES de 8 rondes, Matsui indica que, malgrat la pres\xc3\xa8ncia de l\'\xc3\xbaltima clau (de 48 bits) en l\'equaci\xc3\xb3, sols 6 bits d\'aquesta \xc3\xbaltima clau influencien el terme on apareix._NEWLINE_S\'han desenvolupat altres t\xc3\xa8cniques diverses per millorar les prestacions d\'aquesta criptoan\xc3\xa0lisi.'