Linear cryptanalysis (original) (raw)

About DBpedia

線形解読法（せんけいかいどくほう、英語: Linear cryptanalysis）とは、暗号化変換の線形近似式を発見することを基本とした一般化された暗号解読手法の一つである。この攻撃は、ブロック暗号およびストリーム暗号に適用される。線形攻撃法は、ブロック暗号にもっとも適用される攻撃法の二つのうちの一つである（もうひとつは、差分解読法である）。

Property Value
dbo:abstract La Criptoanàlisi lineal és una tècnica inventada per , investigador de Mitsubishi. Data de 1993 i va ser desenvolupada inicialment per trencar l'algorisme de xifratge simètric DES. Aquest tipus de Criptoanàlisi es basa en un concepte anterior al descobriment de Matsui: les expressions lineals probabilistiques. Aquestes últimes han estat estudiades per i A. Tardy-Cordfir en el marc d'un atac sobre FEAL. La Criptoanàlisi lineal és més eficaç que la Criptoanàlisi diferencial però menys pràctica per la senzilla i bona raó 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à o un altre. Llavors, Matsui millora el seu algorisme el 1994 i proposa una solució amb parelles. La complexitat amb una bona implementació és tanmateix inferior i de l'ordre de operacions DES. La Criptoanàlisi lineal consisteix a fer una aproximació lineal de l'algorisme de xifratge simplificant-lo. Augmentant el nombre de parelles disponibles, es millora la precisió de l'aproximació 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ètode, les taules de substitució presenten en efecte certes propietats lineals mentre que estaven precisament previstes per afegir una no-linealitat a DES. S'ha aplicat amb èxit sobre diversos algorismes com , FEAL o una versió simplificada de Serpent. Els algorismes més recents com AES (Rijndael) i d'altres encara són insensibles a un atac lineal. La complexitat de l'atac és en aquests casos àmpliament superior a la d'un . (ca) Die lineare Kryptoanalyse ist eine allgemeine Form der Kryptoanalyse, die auf der linearen Annäherung an den wahrscheinlichsten Schlüssel zum Brechen von Blockverschlüsselungsverfahren basiert. Diese Methode wurde 1992 von Mitsuru Matsui (einem der Entwickler des MISTY1-Verschlüsselungsalgorithmus) veröffentlicht. Diese Technik wurde erstmals bei der Untersuchung der FEAL-Verschlüsselung eingesetzt. Später veröffentlichte Matsui auch einen Angriff auf den Data Encryption Standard (DES), der schließlich zur ersten öffentlichen Publizierung einer experimentellen Kryptoanalyse wurde. Dieser Angriff ist in der Praxis kaum anwendbar, da er für einen 16-Runden-DES 247 bekannte Klartext-/Chiffrat-Paare benötigt. Andere Varianten der linearen Kryptoanalyse wurden sowohl für Block- als auch für Stromchiffren entwickelt. Daher wird bei neu entworfenen Algorithmen normalerweise ihre Sicherheit gegen die lineare Kryptoanalyse geprüft. Die lineare Kryptoanalyse ist eine der am häufigsten verwendeten Angriffsmöglichkeiten gegen Blockchiffren, die andere ist die differenzielle Kryptoanalyse. (de) In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being differential cryptanalysis. The discovery is attributed to Mitsuru Matsui, who first applied the technique to the FEAL cipher (Matsui and Yamagishi, 1992). Subsequently, Matsui published an attack on the Data Encryption Standard (DES), eventually leading to the first experimental cryptanalysis of the cipher reported in the open community (Matsui, 1993; 1994). The attack on DES is not generally practical, requiring 247 known plaintexts. A variety of refinements to the attack have been suggested, including using multiple linear approximations or incorporating non-linear expressions, leading to a generalized partitioning cryptanalysis. Evidence of security against linear cryptanalysis is usually expected of new cipher designs. (en) La cryptanalyse linéaire est une technique inventée par Mitsuru Matsui, chercheur chez Mitsubishi Electric. Elle date de 1993 et fut développée à l'origine pour casser l'algorithme de chiffrement symétrique DES. Ce type de cryptanalyse se base sur un concept antérieur à la découverte de Matsui : les expressions linéaires probabilistes. Ces dernières ont été étudiées par et Anne Tardy-Corfdir dans le cadre d'une attaque sur FEAL. La cryptanalyse linéaire est plus efficace que la cryptanalyse différentielle, mais moins pratique pour la simple et bonne raison que l'on part du principe que l'attaquant ne dispose pas de la boîte noire symbolisant l'algorithme de chiffrement, et qu'il ne peut pas soumettre ses propres textes. Dans le cas de DES, cette attaque nécessitait à l'origine couples (tous chiffrés avec la même clé) que l'attaquant a pu récupérer par un moyen ou un autre. Par la suite, Matsui améliore son algorithme en 1994 et propose une solution avec couples. La complexité avec une bonne implémentation est toutefois inférieure et de l'ordre de opérations DES. La cryptanalyse linéaire consiste à faire une approximation linéaire de l'algorithme de chiffrement en le simplifiant. En augmentant le nombre de couples disponibles, on améliore la précision de l'approximation et on peut en extraire la clé. Tous les nouveaux algorithmes de chiffrement doivent veiller à être résistants à ce type d'attaque. DES n'était pas conçu pour empêcher ce genre de méthode, les tables de substitution (S-Boxes) présentent en effet certaines propriétés linéaires, alors qu'elles étaient justement prévues pour ajouter une non-linéarité à DES. Elle a par la suite été appliquée avec succès sur plusieurs algorithmes comme LOKI, FEAL ou une version simplifiée de Serpent. Les algorithmes plus récents comme AES (Rijndael), IDEA, et bien d'autres encore, sont insensibles à une attaque linéaire. La complexité de l'attaque est dans ces cas largement supérieure à celle d'une recherche exhaustive. (fr) La crittanalisi lineare è una forma generale di crittanalisi basata sulla ricerca di approssimazioni affini al comportamento di un cifrario. Gli attacchi sono stati sviluppati per i cifrari a blocchi e quelli a flusso. La crittanalisi lineare è una delle due tecniche di attacco più utilizzate contro i cifrari a blocchi: l'altra è la crittanalisi differenziale. La scoperta della crittanalisi lineare è attribuita a Mitsuru Matsui, che per primo l'applicò al cifrario FEAL nel 1992. Successivamente Matsui pubblicò un attacco al DES, probabilmente il primo esperimento di crittanalisi del cifrario riportato da un accademico. L'attacco non è però generalmente praticabile, dato che richiede 243 testi in chiaro noti. Sono state suggerite una gran varietà di migliorie all'attacco, incluse l'uso di approssimazioni lineari multiple o l'incorporazione di espressioni non lineari. Dai nuovi cifrari in genere ci si attende che i loro sviluppatori pubblichino anche il livello di sicurezza contro la crittanalisi lineare. (it) 線形解読法（せんけいかいどくほう、英語: Linear cryptanalysis）とは、暗号化変換の線形近似式を発見することを基本とした一般化された暗号解読手法の一つである。この攻撃は、ブロック暗号およびストリーム暗号に適用される。線形攻撃法は、ブロック暗号にもっとも適用される攻撃法の二つのうちの一つである（もうひとつは、差分解読法である）。 (ja) 선형 공격(linear cryptanalysis)은 의 한 방법으로, 암호화 과정에서의 근사적 선형 관계식을 찾는 것을 목적으로 한다. 선형 공격은 (松井 充)의 논문에서 처음 공개되었으며, 해당 논문에서는 선형 공격으로 암호를 공격하는 방법을 제시했다. 선형 공격은 차분 공격과 함께 블록 암호를 공격하는 방법으로 널리 응용된다. (ko) В криптографии линейным криптоанализом называется метод криптоанализа, использующий линейные приближения для описания работы шифра. Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (яп. 松井 充 Мацуи Мицуру). Предложенный им в 1993 году (на конференции Eurocrypt '93) алгоритм был изначально направлен на вскрытие DES и FEAL. Впоследствии линейный криптоанализ был распространён и на другие алгоритмы. На сегодняшний день наряду с дифференциальным криптоанализом является одним из наиболее распространённых методов вскрытия блочных шифров. Также пригоден для атак на потоковые шифры. Открытие линейного криптоанализа послужило толчком к построению новых криптографических схем. (ru) Kryptoanaliza liniowa – wprowadzona przez , polega na aproksymacji szyfru za pomocą liniowej funkcji boolowskiej. Na podstawie tej aproksymacji, przy znajomości par tekst jawny - szyfrogram, możliwe jest znalezienie bitów klucza. (pl) В криптографії лінійним криптоаналізом називають метод криптоаналітичного розкриття, що використовує лінійні наближення для роботи шифру. Лінійний криптоаналіз був винайдений японським криптологом Міцуру Мацуі (яп. 松井 充 Мацуі Міцуру) . Запропонований ним у 1993 році (на конференції Eurocrypt '93) алгоритм був від самого початку спрямований на розкриття DES і FEAL. Згодом лінійний криптоаналіз був поширений і на інші алгоритми. На сьогодні разом з диференціальним криптоаналізом є одним з найбільш розповсюджених методів розкриття блочних шифрів. Розроблені атаки на блочні та потокові шифри. Відкриття лінійного криптоаналізу стало поштовхом до побудови нових криптографічних схем. (uk)
dbo:wikiPageExternalLink http://www.engr.mun.ca/~howard/Research/Papers/ldc_tutorial.html http://www.cs.rit.edu/~ib/Classes/CS482-705_Winter10-11/Slides/crypto_lc.pdf https://web.archive.org/web/20130928011123/http:/nsfsecurity.pr.erau.edu/crypto/lincrypt.html http://www.uclouvain.be/crypto/services/download/publications.pdf.be55706e161dc10a.34382e706466.pdf http://www.apprendre-en-ligne.net/crypto/bibliotheque/PDF/lincrypt.pdf
dbo:wikiPageID 59469 (xsd:integer)
dbo:wikiPageLength 6287 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1084899095 (xsd:integer)
dbo:wikiPageWikiLink dbr:Partitioning_cryptanalysis dbr:Cryptography dbr:Cryptanalysis dbr:Piling-up_lemma dbr:Substitution–permutation_network dbr:Brute-force_attack dbr:Data_Encryption_Standard dbr:Affine_transformation dbc:Cryptographic_attacks dbr:Differential_cryptanalysis dbr:S-box dbr:Absolute_difference dbr:Block_cipher dbr:Cipher dbr:Known-plaintext_attack dbr:Mitsuru_Matsui dbr:FEAL dbr:Stream_cipher
dbp:wikiPageUsesTemplate dbt:Reflist dbt:Short_description dbt:Cryptography_navbox
dct:subject dbc:Cryptographic_attacks
gold:hypernym dbr:Form
rdf:type yago:WikicatCryptographicAttacks yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Attack100972621 yago:Event100029378 yago:Operation100955060 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity
rdfs:comment 線形解読法（せんけいかいどくほう、英語: Linear cryptanalysis）とは、暗号化変換の線形近似式を発見することを基本とした一般化された暗号解読手法の一つである。この攻撃は、ブロック暗号およびストリーム暗号に適用される。線形攻撃法は、ブロック暗号にもっとも適用される攻撃法の二つのうちの一つである（もうひとつは、差分解読法である）。 (ja) 선형 공격(linear cryptanalysis)은 의 한 방법으로, 암호화 과정에서의 근사적 선형 관계식을 찾는 것을 목적으로 한다. 선형 공격은 (松井 充)의 논문에서 처음 공개되었으며, 해당 논문에서는 선형 공격으로 암호를 공격하는 방법을 제시했다. 선형 공격은 차분 공격과 함께 블록 암호를 공격하는 방법으로 널리 응용된다. (ko) Kryptoanaliza liniowa – wprowadzona przez , polega na aproksymacji szyfru za pomocą liniowej funkcji boolowskiej. Na podstawie tej aproksymacji, przy znajomości par tekst jawny - szyfrogram, możliwe jest znalezienie bitów klucza. (pl) La Criptoanàlisi lineal és una tècnica inventada per , investigador de Mitsubishi. Data de 1993 i va ser desenvolupada inicialment per trencar l'algorisme de xifratge simètric DES. Aquest tipus de Criptoanàlisi es basa en un concepte anterior al descobriment de Matsui: les expressions lineals probabilistiques. Aquestes últimes han estat estudiades per i A. Tardy-Cordfir en el marc d'un atac sobre FEAL. (ca) Die lineare Kryptoanalyse ist eine allgemeine Form der Kryptoanalyse, die auf der linearen Annäherung an den wahrscheinlichsten Schlüssel zum Brechen von Blockverschlüsselungsverfahren basiert. Diese Methode wurde 1992 von Mitsuru Matsui (einem der Entwickler des MISTY1-Verschlüsselungsalgorithmus) veröffentlicht. Andere Varianten der linearen Kryptoanalyse wurden sowohl für Block- als auch für Stromchiffren entwickelt. Daher wird bei neu entworfenen Algorithmen normalerweise ihre Sicherheit gegen die lineare Kryptoanalyse geprüft. (de) In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being differential cryptanalysis. (en) La cryptanalyse linéaire est une technique inventée par Mitsuru Matsui, chercheur chez Mitsubishi Electric. Elle date de 1993 et fut développée à l'origine pour casser l'algorithme de chiffrement symétrique DES. Ce type de cryptanalyse se base sur un concept antérieur à la découverte de Matsui : les expressions linéaires probabilistes. Ces dernières ont été étudiées par et Anne Tardy-Corfdir dans le cadre d'une attaque sur FEAL. (fr) La crittanalisi lineare è una forma generale di crittanalisi basata sulla ricerca di approssimazioni affini al comportamento di un cifrario. Gli attacchi sono stati sviluppati per i cifrari a blocchi e quelli a flusso. La crittanalisi lineare è una delle due tecniche di attacco più utilizzate contro i cifrari a blocchi: l'altra è la crittanalisi differenziale. Sono state suggerite una gran varietà di migliorie all'attacco, incluse l'uso di approssimazioni lineari multiple o l'incorporazione di espressioni non lineari. (it) В криптографії лінійним криптоаналізом називають метод криптоаналітичного розкриття, що використовує лінійні наближення для роботи шифру. Лінійний криптоаналіз був винайдений японським криптологом Міцуру Мацуі (яп. 松井 充 Мацуі Міцуру) . Запропонований ним у 1993 році (на конференції Eurocrypt '93) алгоритм був від самого початку спрямований на розкриття DES і FEAL. Згодом лінійний криптоаналіз був поширений і на інші алгоритми. На сьогодні разом з диференціальним криптоаналізом є одним з найбільш розповсюджених методів розкриття блочних шифрів. Розроблені атаки на блочні та потокові шифри. (uk) В криптографии линейным криптоанализом называется метод криптоанализа, использующий линейные приближения для описания работы шифра. Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (яп. 松井 充 Мацуи Мицуру). Предложенный им в 1993 году (на конференции Eurocrypt '93) алгоритм был изначально направлен на вскрытие DES и FEAL. Впоследствии линейный криптоанализ был распространён и на другие алгоритмы. На сегодняшний день наряду с дифференциальным криптоанализом является одним из наиболее распространённых методов вскрытия блочных шифров. Также пригоден для атак на потоковые шифры. (ru)
rdfs:label Criptoanàlisi lineal (ca) Lineare Kryptoanalyse (de) Cryptanalyse linéaire (fr) Crittanalisi lineare (it) Linear cryptanalysis (en) 선형 공격 (ko) 線形解読法 (ja) Kryptoanaliza liniowa (pl) Линейный криптоанализ (ru) Лінійний криптоаналіз (uk)
owl:sameAs freebase:Linear cryptanalysis yago-res:Linear cryptanalysis wikidata:Linear cryptanalysis dbpedia-ca:Linear cryptanalysis dbpedia-de:Linear cryptanalysis dbpedia-fr:Linear cryptanalysis dbpedia-he:Linear cryptanalysis dbpedia-it:Linear cryptanalysis dbpedia-ja:Linear cryptanalysis dbpedia-ko:Linear cryptanalysis dbpedia-pl:Linear cryptanalysis dbpedia-ru:Linear cryptanalysis dbpedia-simple:Linear cryptanalysis dbpedia-uk:Linear cryptanalysis https://global.dbpedia.org/id/kmaY
prov:wasDerivedFrom wikipedia-en:Linear_cryptanalysis?oldid=1084899095&ns=0
foaf:isPrimaryTopicOf wikipedia-en:Linear_cryptanalysis
is dbo:wikiPageDisambiguates of dbr:LC dbr:Linear_(disambiguation)
is dbo:wikiPageWikiLink of dbr:List_of_cryptographers dbr:M8_(cipher) dbr:MMB_(cipher) dbr:Partitioning_cryptanalysis dbr:Anubis_(cipher) dbr:List_of_important_publications_in_cryptography dbr:Rijndael_S-box dbr:DES-X dbr:DFC_(cipher) dbr:Decorrelation_theory dbr:Index_of_cryptography_articles dbr:International_Data_Encryption_Algorithm dbr:Interpolation_attack dbr:List_of_lemmas dbr:SXAL/MBAL dbr:Symmetric-key_algorithm dbr:Cryptography dbr:RSA_Award_for_Excellence_in_Mathematics dbr:Cryptanalysis dbr:The_Recruit dbr:Bent_function dbr:MISTY1 dbr:Key_schedule dbr:Piling-up_lemma dbr:Madryga dbr:Burt_Kaliski dbr:Data_Encryption_Standard dbr:Locally_decodable_code dbr:Differential-linear_attack dbr:Differential_cryptanalysis dbr:Fast_syndrome-based_hash dbr:Q_(cipher) dbr:S-box dbr:Block_cipher dbr:XSL_attack dbr:Boolean_function dbr:CIPHERUNICORN-A dbr:CIPHERUNICORN-E dbr:COCONUT98 dbr:Cipher_security_summary dbr:Mitsuru_Matsui dbr:Matt_Robshaw dbr:Serpent_(cipher) dbr:FEAL dbr:FROG dbr:LC dbr:Linear_(disambiguation) dbr:SC2000 dbr:NUSH dbr:Outline_of_cryptography dbr:SM4_(cipher)
is foaf:primaryTopic of wikipedia-en:Linear_cryptanalysis