An Entity of Type: Procedure101023820, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance in the cryptographic community, but is a candidate for "post-quantum cryptography", as it is immune to attacks using Shor's algorithm and – more generally – measuring coset states using Fourier sampling. Variants of this cryptosystem exist, using different types of codes. Most of them were proven less secure; they were broken by .

Property Value
dbo:abstract
  • Das McEliece-Kryptosystem ist ein asymmetrischer Verschlüsselungsalgorithmus. Es wurde 1978 vom Kryptographen Robert J. McEliece vorgestellt. Das Verfahren wird nur selten praktisch eingesetzt, da die Schlüssel große Matrizen sind; die Beschreibung eines Schlüssels mit einem Sicherheitsniveau von 128 Bit benötigt in der Größenordnung von 1 MB, über tausendmal mehr als vergleichbare RSA-Schlüssel. Jedoch ist selbst unter Verwendung von Quantencomputern kein effizienter Algorithmus bekannt, der das McEliece-Kryptosystem brechen kann, was es zu einem vielversprechenden Kandidaten für Post-Quanten-Kryptographie macht. (de)
  • Le cryptosystème de McEliece est un schéma de chiffrement asymétrique, inventé en 1978 par Robert McEliece. Ce système, reposant sur un problème difficile de la théorie des codes, n'a pas rencontré de véritable soutien dans la communauté cryptographique[réf. nécessaire], entre autres car la clé de chiffrement est particulièrement grande et que le message chiffré est deux fois plus long que l'original. Pourtant, le cryptosystème de McEliece possède des propriétés intéressantes : la sécurité croît beaucoup plus rapidement avec la taille des clés que pour le système RSA, et le chiffrement est plus rapide. Un autre avantage est de reposer sur un problème très différent des algorithmes asymétriques usuels. Cela signifie qu'une percée théorique dans le domaine de la factorisation, réalisable par des algorithmes quantiques, qui ruinerait RSA, n'affecterait en rien ce système. Cette avantage lui permet d'être sélectionné par le NIST comme candidat à la standardisation des algorithmes de chiffrement post-quantique. Des attaques efficaces ont été publiées contre le cryptosystème de McEliece, ainsi que contre de nombreuses variantes. Cependant, des améliorations ont été proposées afin d'éviter ces attaques. Il est rarement utilisé en pratique du fait de la grande taille des clefs, mais a été utilisé pour le chiffrement dans Entropy, une alternative à Freenet. (fr)
  • In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance in the cryptographic community, but is a candidate for "post-quantum cryptography", as it is immune to attacks using Shor's algorithm and – more generally – measuring coset states using Fourier sampling. The algorithm is based on the hardness of decoding a general linear code (which is known to be NP-hard). For a description of the private key, an error-correcting code is selected for which an efficient decoding algorithm is known, and which is able to correct errors. The original algorithm uses binary Goppa codes (subfield codes of geometric Goppa codes of a genus-0 curve over finite fields of characteristic 2); these codes can be efficiently decoded, thanks to an algorithm due to Patterson. The public key is derived from the private key by disguising the selected code as a general linear code. For this, the code's generator matrix is perturbated by two randomly selected invertible matrices and (see below). Variants of this cryptosystem exist, using different types of codes. Most of them were proven less secure; they were broken by . McEliece with Goppa codes has resisted cryptanalysis so far. The most effective attacks known use information-set decoding algorithms. A 2008 paper describes both an attack and a fix. Another paper shows that for quantum computing, key sizes must be increased by a factor of four due to improvements in information set decoding. The McEliece cryptosystem has some advantages over, for example, RSA. The encryption and decryption are faster. For a long time, it was thought that McEliece could not be used to produce signatures. However, a signature scheme can be constructed based on the Niederreiter scheme, the dual variant of the McEliece scheme. One of the main disadvantages of McEliece is that the private and public keys are large matrices. For a standard selection of parameters, the public key is 512 kilobits long. (en)
  • 암호학에서 매켈리스 암호체계는 로버트 매켈리스가 1978년에 제안한 이다. 그러나 실제로 사용하는 경우는 거의 없다. 이 알고리즘은 오류 정정 부호의 일종인 를 사용한다. 큰 행렬을 개인 키와 공개 키로 사용해야 하는데, 이것이 이 암호 방식의 가장 큰 단점이다. 공개키는 거의 비트 정도로 매우 길다. 매켈리스 암호체계는 키의 크기가 지나치게 크다는 점 이외에도 여러 단점이 있다. 암호문은 평문의 2배로 불어나기 때문에, 효율적이지 못하다. 매켈리스 암호체계를 깨뜨리려는 시도는 오랫동안 있었지만, 아직 성공적인 공격방법은 발견되지 않았다. 그러나, 매켈리스 암호체계는 이미 안전하지 않다고 알려진 배낭 문제와 유사한 문제에 기반하고 있기 때문에 안전성에 대한 우려가 있다. (ko)
  • Algorytm McEliece'a – asymetryczny algorytm szyfrowania, opracowany w 1978 roku przez , który oparty jest na trudności dekodowania kodów liniowych. W przypadku tego algorytmu zastosowane zostały . Ze względu na kilka niedociągnięć, jak duża długość klucza (219 bitów), duża długość szyfrogramu, algorytm nie przyjął się. (pl)
  • マックエリス暗号(McEliece_cryptosystem)は、暗号理論において,公開鍵暗号方式の一つであり,1978年にロバート・マックエリス()によって提案された。 この暗号方式は,最初の確率的な暗号方式であり,一つの平文から異なる暗号文が生成される.この暗号方式は暗号コミュニティにおいてあまり注目を浴びてこなかったが,を用いた攻撃で破ることができないため,の候補の一つとなっている. この暗号方式は,線形符号の復号困難性(これはNP困難であることが知られている)に基づいている.復号に用いられる秘密鍵は,効率的に復号可能で 個のエラーを訂正可能な誤り訂正符号である.マックエリスによるオリジナルの方式は,二元ゴッパ符号(標数が2である有限体上の種数0の曲線で定義されるゴッパ符号)を用いている.この符号はPattersonによるアルゴリズムにより,効率的に復号できる. 暗号化に用いる公開鍵は,秘密鍵である符号を一般的な線形符号に「偽装」することで得られる.このために,符号の生成行列 を,二つのランダムに選ばれた可逆行列 と によって攪乱する.(具体的な方法については下を参照のこと.) この暗号化方式には,別の符号を用いた複数のバリエーションが存在するが,多くは安全性が低く,構造的攻撃によって破ることができる. ゴッパ符号を用いたマックエリス暗号は現在のところ解読されていない.最も効率の良い攻撃方法として知られているのは アルゴリズムを用いるものである.2008年の論文には,攻撃手法と修正方法が示されている. 別の論文では,量子コンピュータに対して安全にするためには,鍵サイズを4倍に延ばす必要があることが示されている.これは, 量子コンピュータによって information set decoding が効率化できるからである. マックエリス暗号の利点 --- 例えばRSA暗号などと比較して --- として,暗号化と復号が速いことが挙げられる. 長い間,マックエリス暗号で デジタル署名 は生成できないだろうと考えられてきた.しかし,マックエリス暗号の双対版である暗号を用いると署名方式を構築することができる.マックエリス暗号の一番大きな欠点は,公開鍵と秘密鍵が大きな行列であることである.標準的なパラメータにおいては,公開鍵は512KB(キロバイト)である. (ja)
  • Het McEliece cryptosysteem is een asymmetrisch versleutelingsalgoritme dat in 1978 door Robert McEliece is ontwikkeld.Het algoritme is nooit populair geworden binnen de cryptografische wereld, maar is mogelijk een goede kandidaat voor versleuteling van berichten wanneer de kwantumcomputer zijn intrede heeft gedaan, omdat het beschermd is tegen aanvallen die gebruikmaken van het algoritme van Shor. Het originele algoritme maakt gebruik van binaire Goppa codes. Dit zijn lineaire codes met een bepaalde eigenschap zodat ze goed herkenbaar zijn, met behulp van bijvoorbeeld het algoritme van Patterson. Een Goppa code is een vorm van een foutherstellende code. Deze eigenschap wordt ingezet bij McEliece cryptografie. De verzender van het bericht voegt na de versleuteling met de publieke sleutel een aantal random fouten toe aan zijn bericht. Door het gebruik van Goppa codes is de ontvanger in staat om met zijn private sleutel de fouten te herstellen en het bericht te ontcijferen. Zie hiervoor ook coderingstheorie.Een eenvoudig voorbeeld van een foutherstellende code is de Hamming-code. Deze code is slechts in staat om één fout in de code te herstellen, of om maximaal twee fouten te detecteren. Goppa codes zijn in staat om meerdere fouten te herstellen. Een algemene lineaire code is vrijwel niet te kraken, en het algoritme van McEliece vermomt de Goppa code met behulp van twee andere matrices tot een 'gewone' lineaire code. Dit zorgt ervoor dat het McEliece-systeem moeilijk te kraken is. Het McEliece-cryptosysteem is het eerste public-key versleutelingsschema dat gebruikmaakt van willekeurigheid in het versleutelingsproces. Er bestaan andere varianten van het systeem, die gebruikmaken van andere type codes. De meeste hiervan zijn minder veilig gebleken: ze werden gekraakt met behulp van 'structural decoding'. Het kraken van een McEliece-systeem dat gebruikmaakt van Goppa codes is veel lastiger. De meest effectieve bekende aanvallen gebruiken informatieset-ontcijfering (een algoritme voor het ontcijferen van lineaire codes). Een recent geslaagde aanval en oplossing tegen deze aanval is beschreven door Bernstein, Lange and Peters. Het McEliece cryptosysteem heeft een aantal voordelen ten opzichte van andere versleutelsystemen, bijvoorbeeld RSA. Het versleutelen en ontcijferen gaat veel sneller (voor een vergelijking, zie het eBATS vergelijkingsproject) en met het groeien van de sleutelgrootte, gaat het veiligheidsniveau steeds sneller omhoog. Lange tijd werd gedacht dat McEliece niet gebruikt kon worden voor het maken van een digitale handtekening. Maar het blijkt dat een handtekening geconstrueerd kan worden op basis van een -systeem, de duale variant van het McEliece-systeem.Omdat zowel de persoonlijke als de publieke sleutel bestaan uit zeer grote matrices - de persoonlijke sleutel bijvoorbeeld heeft een lengte van 219 bits - wordt het McEliece-cryptosysteem in de praktijk zelden gebruik. Een uitzonderlijke geval dat wel gebruikmaakt van McEliece-versleuteling is Entropy, een applicatie die op Freenet (P2P) lijkt. (nl)
  • McEliece — криптосистема с открытыми ключами на основе теории алгебраического кодирования, разработанная в 1978 году . Это была первая схема, использующая в процессе шифрования. Алгоритм не получил широко признания в криптографии, но в то же время является кандидатом для постквантовой криптографии, так как устойчив к атаке с использованием Алгоритма Шора. Алгоритм основан на сложности декодирования полных линейных кодов (общая задача декодирования является NP-сложной). Для описания закрытого ключа выбран код исправляющий ошибки, для которого известен эффективный алгоритм декодирования и который может исправить ошибок. Алгоритм использует двоичные коды Гоппа, которые легко декодируются благодаря алгоритму Петерсона. Открытый ключ получается при помощи маскировки выбранного кода как полного линейного. Для этого порождающая матрица сначала умножается справа на , а затем на невырожденную матрицу слева (см. ). Существует несколько вариантов криптосистемы, использующих различные типы кодов. Большинство из них оказываются менее защищенными. Отдельного рассмотрения заслуживает вопрос выбора параметров криптосистемы. До сих пор McElice с кодами Гоппы не поддается криптоанализу. Наиболее известные атаки используют алгоритм . Последние работы описывают как атаки на систему, так и её защиту. В других работах показано, что для квантовых вычислений размер ключа должен быть увеличен на четыре порядка из-за усовершенствования декодирования множества данных. Криптосистема имеет несколько преимуществ, например, над RSA. Шифрование и дешифрование проходит быстрее и с ростом длины ключа степень защиты данных растет гораздо быстрее. Долгое время считалось, что McEliece не может быть использована для ЭЦП. Однако оказалось возможным построить схему для ЭЦП на основе криптосистемы Нидеррайтера (модификация МcEliece). Поскольку в зависимости от используемых кодов, эти две криптосистемы выражают одну и ту же кодовую задачу, на сегодняшний день, можно утверждать, что McEliece применим в задачах аутентификации. Из-за McEliece используется редко. Одно из исключений — использование McElice для шифрования в Freenet-подобной сети ENTROPY. (ru)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 735452 (xsd:integer)
dbo:wikiPageLength
  • 14541 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1061434367 (xsd:integer)
dbo:wikiPageWikiLink
dbp:date
  • May 2016 (en)
dbp:reason
  • 524 (xsd:integer)
dbp:wikiPageUsesTemplate
dct:subject
rdf:type
rdfs:comment
  • Das McEliece-Kryptosystem ist ein asymmetrischer Verschlüsselungsalgorithmus. Es wurde 1978 vom Kryptographen Robert J. McEliece vorgestellt. Das Verfahren wird nur selten praktisch eingesetzt, da die Schlüssel große Matrizen sind; die Beschreibung eines Schlüssels mit einem Sicherheitsniveau von 128 Bit benötigt in der Größenordnung von 1 MB, über tausendmal mehr als vergleichbare RSA-Schlüssel. Jedoch ist selbst unter Verwendung von Quantencomputern kein effizienter Algorithmus bekannt, der das McEliece-Kryptosystem brechen kann, was es zu einem vielversprechenden Kandidaten für Post-Quanten-Kryptographie macht. (de)
  • 암호학에서 매켈리스 암호체계는 로버트 매켈리스가 1978년에 제안한 이다. 그러나 실제로 사용하는 경우는 거의 없다. 이 알고리즘은 오류 정정 부호의 일종인 를 사용한다. 큰 행렬을 개인 키와 공개 키로 사용해야 하는데, 이것이 이 암호 방식의 가장 큰 단점이다. 공개키는 거의 비트 정도로 매우 길다. 매켈리스 암호체계는 키의 크기가 지나치게 크다는 점 이외에도 여러 단점이 있다. 암호문은 평문의 2배로 불어나기 때문에, 효율적이지 못하다. 매켈리스 암호체계를 깨뜨리려는 시도는 오랫동안 있었지만, 아직 성공적인 공격방법은 발견되지 않았다. 그러나, 매켈리스 암호체계는 이미 안전하지 않다고 알려진 배낭 문제와 유사한 문제에 기반하고 있기 때문에 안전성에 대한 우려가 있다. (ko)
  • Algorytm McEliece'a – asymetryczny algorytm szyfrowania, opracowany w 1978 roku przez , który oparty jest na trudności dekodowania kodów liniowych. W przypadku tego algorytmu zastosowane zostały . Ze względu na kilka niedociągnięć, jak duża długość klucza (219 bitów), duża długość szyfrogramu, algorytm nie przyjął się. (pl)
  • Le cryptosystème de McEliece est un schéma de chiffrement asymétrique, inventé en 1978 par Robert McEliece. Ce système, reposant sur un problème difficile de la théorie des codes, n'a pas rencontré de véritable soutien dans la communauté cryptographique[réf. nécessaire], entre autres car la clé de chiffrement est particulièrement grande et que le message chiffré est deux fois plus long que l'original. Pourtant, le cryptosystème de McEliece possède des propriétés intéressantes : la sécurité croît beaucoup plus rapidement avec la taille des clés que pour le système RSA, et le chiffrement est plus rapide. (fr)
  • In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance in the cryptographic community, but is a candidate for "post-quantum cryptography", as it is immune to attacks using Shor's algorithm and – more generally – measuring coset states using Fourier sampling. Variants of this cryptosystem exist, using different types of codes. Most of them were proven less secure; they were broken by . (en)
  • マックエリス暗号(McEliece_cryptosystem)は、暗号理論において,公開鍵暗号方式の一つであり,1978年にロバート・マックエリス()によって提案された。 この暗号方式は,最初の確率的な暗号方式であり,一つの平文から異なる暗号文が生成される.この暗号方式は暗号コミュニティにおいてあまり注目を浴びてこなかったが,を用いた攻撃で破ることができないため,の候補の一つとなっている. この暗号方式は,線形符号の復号困難性(これはNP困難であることが知られている)に基づいている.復号に用いられる秘密鍵は,効率的に復号可能で 個のエラーを訂正可能な誤り訂正符号である.マックエリスによるオリジナルの方式は,二元ゴッパ符号(標数が2である有限体上の種数0の曲線で定義されるゴッパ符号)を用いている.この符号はPattersonによるアルゴリズムにより,効率的に復号できる. 暗号化に用いる公開鍵は,秘密鍵である符号を一般的な線形符号に「偽装」することで得られる.このために,符号の生成行列 を,二つのランダムに選ばれた可逆行列 と によって攪乱する.(具体的な方法については下を参照のこと.) この暗号化方式には,別の符号を用いた複数のバリエーションが存在するが,多くは安全性が低く,構造的攻撃によって破ることができる. (ja)
  • Het McEliece cryptosysteem is een asymmetrisch versleutelingsalgoritme dat in 1978 door Robert McEliece is ontwikkeld.Het algoritme is nooit populair geworden binnen de cryptografische wereld, maar is mogelijk een goede kandidaat voor versleuteling van berichten wanneer de kwantumcomputer zijn intrede heeft gedaan, omdat het beschermd is tegen aanvallen die gebruikmaken van het algoritme van Shor. (nl)
  • McEliece — криптосистема с открытыми ключами на основе теории алгебраического кодирования, разработанная в 1978 году . Это была первая схема, использующая в процессе шифрования. Алгоритм не получил широко признания в криптографии, но в то же время является кандидатом для постквантовой криптографии, так как устойчив к атаке с использованием Алгоритма Шора. Алгоритм основан на сложности декодирования полных линейных кодов (общая задача декодирования является NP-сложной). Из-за McEliece используется редко. Одно из исключений — использование McElice для шифрования в Freenet-подобной сети ENTROPY. (ru)
rdfs:label
  • McEliece-Kryptosystem (de)
  • McEliece cryptosystem (en)
  • Cryptosystème de McEliece (fr)
  • マックエリス暗号 (ja)
  • 매켈리스 암호체계 (ko)
  • Algorytm McEliece’a (pl)
  • McEliece-cryptosysteem (nl)
  • McEliece (ru)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License