title: McEliece-cryptosysteem
text: 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 Niederreiter-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.
  
  Definitieschema
  McEliece bestaat uit drie algoritmes:
   een algoritme om de persoonlijke en de publieke sleutel te genereren
   een versleutelalgoritme voor het bericht
   een ontcijferingsalgoritme.
  Alle gebruikers van een McEliece-omgeving delen een verzameling van gemeenschappelijke veiligheidsparameters: , , . Hierbij geven  en  de grootte aan van de gebruikte matrices en is  het aantal fouten dat maximaal toegevoegd kan worden. Het 'Handbook of Applied Cryptography' uit 1995 raadt aan om de volgende waarden van deze parameters te nemen: , , . Recentere suggesties raden aan om voor de veiligheid nog grotere parameters te gebruiken, namelijk  en .
  
  Het genereren van een sleutel
  Alice selecteert een binaire -lineaire code  die in staat is  fouten te corrigeren. Een Goppa codes is hier een goede keuze, want deze bevat een efficiënt ontcijferingsalgoritme.
  Alice genereert een  generator-matrix  voor de code .
  Alice selecteert een willekeurige  niet-singuliere matrix  over het lichaam waar de code  op gedefinieerd is. Bij de keuze van een Goppa code, wat gedefinieerd is over het lichaam , is dit een binaire matrix.
  Alice selecteert een willekeurige  permutatiematrix P.
  Alice berekent de  matrix 
  Alice haar publieke sleutel is ; haar persoonlijke sleutel is
  
  Versleutelen van een bericht
  Stel dat Bob een bericht m naar Alice wil sturen. Alice haar publieke sleutel is :
  Bob codeert zijn bericht m als een binaire rij met lengte .
  Bob berekent de vector .
  Bob genereert een willekeurige -bit vector , die op zijn hoogst  enen bevat (een vector met lengte  en gewicht ). Daarmee brengt Bob maximaal  fouten aan in zijn bericht.
  Bob berekent de cijfercode als . Met '+' als standaard vectoroptelling over het lichaam.
  
  Ontcijferen van het bericht
  Wanneer Alice  ontvangt, voert ze de volgende stappen uit om het bericht te ontcijferen:
  Alice berekent de inverse .
  Alice berekent .
  Alice gebruikt het decodeeralgoritme voor de code  om  te decoderen tot .
  Alice berekent .
  
  Bewijs van ontcijfering van het bericht 
  Bedenk eerst dat , en dat  een permutatiematrix is, zodat  hoogstens een Hamming waarde  heeft.
  De Goppacode  kan maximaal  fouten corrigeren en het woord  is op ten hoogste  afstand van . Daarom wordt het woord  correct teruggevonden.
  Vermenigvuldigen met de inverse van  geeft , oftewel het originele tekstbericht.
  
  Aanvallen op McEliece 
  Een aanvaller die de publieke sleutel  kent, wil een onderschept gecodeerd bericht  ontcijferen. Hij kan dit doen door te proberen  te achterhalen, en daarop Pattersons algoritme toe te passen. Maar bij grote waarden van n en t is dit vervelend werk. Er zijn gewoonweg te veel mogelijkheden voor  en .
  Een aanvaller die probeert het originele bericht m uit y te achterhalen zonder G te zoeken, oftewel één gecodeerd bericht per keer te kraken, heeft een grotere kans op succes. Robert McEliece realiseerde zich dit toen hij het cryptosysteem ontwikkelde. Een effectieve aanval staat bekend als ‘information set decoding’. McEliece noemde zelf een simpele vorm van zo'n aanval: Kies willekeurig k van de n coördinaten in de hoop dat geen van deze k coördinaten fout zijn, en onder deze aanname m uitrekenen. Maar wanneer k, n en t met zorg worden gekozen, dan is de kans om geen fouten aan te treffen in k coördinaten klein. In dat geval zijn er nog altijd vele herhalingen nodig, voordat de aanval slaagt.
  Gedurende de afgelopen jaren zijn er veel mogelijke aanvallen beschreven en verbeterd, maar tot voor kort was geen van hen toepasbaar vanwege de lange berekeningen. In 2008 waren Bernstein, Lange en Peters
   de eersten die een succesvolle aanval pleegden op een McEliece cryptosysteem, dat gebruikmaakte van de waarden voor de parameters die in 1978 waren gesuggereerd (n=1024, k=524, t=50). Dit deden ze door middel van
  'low-weight codewords'. In hun artikel suggereren ze ook een aantal verbeteringen voor het McEliece cryptosysteem, zodat het niet meer vatbaar is voor deze aanval. Zij stellen nieuwe waarden voor n, k en t voor, voor verschillende niveaus van beveiliging.
  
  Externe links
   The "Handbook of Applied Cryptography" chapter that deals with the McEliece cryptosystem. (PDF); Postscript version.
   Scientists Crack Elusive Code - Crypto System By Coding Theorists Robert J McEliece
  
  Cryptografie