McEliece-cryptosysteem

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.