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 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 2¹⁹ 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:

1. een algoritme om de persoonlijke en de publieke sleutel te genereren
2. een versleutelalgoritme voor het bericht
3. een ontcijferingsalgoritme.

Alle gebruikers van een McEliece-omgeving delen een verzameling van gemeenschappelijke veiligheidsparameters: $n$, $t$, $k$. Hierbij geven $n$ en $k$ de grootte aan van de gebruikte matrices en is $t$ 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: $n=1024$, $t=38$, $k=644$. Recentere suggesties raden aan om voor de veiligheid nog grotere parameters te gebruiken, namelijk $n=4096$ en $k=3556$.

Het genereren van een sleutel

1. Alice selecteert een binaire $(n,k)$-lineaire code $C$ die in staat is $t$ fouten te corrigeren. Een Goppa codes is hier een goede keuze, want deze bevat een efficiënt ontcijferingsalgoritme.
2. Alice genereert een $k\times n$ generator-matrix $G$ voor de code $C$.
3. Alice selecteert een willekeurige $k\times k$ niet-singuliere matrix $S$ over het lichaam waar de code $C$ op gedefinieerd is. Bij de keuze van een Goppa code, wat gedefinieerd is over het lichaam $\mathbb {F} _{2^{n}}$, is dit een binaire matrix.
4. Alice selecteert een willekeurige $n\times n$ permutatiematrix P.
5. Alice berekent de $k\times n$ matrix ${\hat {G}}=SGP$
6. Alice haar publieke sleutel is $({\hat {G}},t)$; haar persoonlijke sleutel is $(S,G,P)$

Versleutelen van een bericht

Stel dat Bob een bericht m naar Alice wil sturen. Alice haar publieke sleutel is $({\hat {G}},t)$:

1. Bob codeert zijn bericht m als een binaire rij met lengte $k$.
2. Bob berekent de vector $c^{\prime }=m{\hat {G}}$.
3. Bob genereert een willekeurige $n$-bit vector $z$, die op zijn hoogst $t$ enen bevat (een vector met lengte $n$ en gewicht $t$). Daarmee brengt Bob maximaal $t$ fouten aan in zijn bericht.
4. Bob berekent de cijfercode als $c=c^{\prime }+z$. Met '+' als standaard vectoroptelling over het lichaam.

Ontcijferen van het bericht

Wanneer Alice $c$ ontvangt, voert ze de volgende stappen uit om het bericht te ontcijferen:

1. Alice berekent de inverse $P^{-1}$.
2. Alice berekent ${\hat {c}}=cP^{-1}$.
3. Alice gebruikt het decodeeralgoritme voor de code $C$ om ${\hat {c}}$ te decoderen tot ${\hat {m}}$.
4. Alice berekent $m={\hat {m}}S^{-1}$.

Bewijs van ontcijfering van het bericht

Bedenk eerst dat ${\hat {c}}=cP^{-1}=m{\hat {G}}P^{-1}+zP^{-1}=mSG+zP^{-1}$, en dat $P$ een permutatiematrix is, zodat $zP^{-1}$ hoogstens een Hamming waarde $t$ heeft. De Goppacode $G$ kan maximaal $t$ fouten corrigeren en het woord $mSG$ is op ten hoogste $t$ afstand van $cP^{-1}$. Daarom wordt het woord ${\hat {m}}=mS$ correct teruggevonden. Vermenigvuldigen met de inverse van $S$ geeft $m={\hat {m}}S^{-1}=mSS^{-1}$, oftewel het originele tekstbericht.

Aanvallen op McEliece

Een aanvaller die de publieke sleutel $({\hat {G}},t)$ kent, wil een onderschept gecodeerd bericht $y\in \mathbb {F} _{2}^{n}$ ontcijferen. Hij kan dit doen door te proberen $G$ 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 $G,S$ en $P$. 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

Referenties en bronvermelding

Referenties

Bronnen

• (en) Menezes, A.J., Oorschot, P.C. van, Vanstone, S.A., (1997) Handbook of Applied Cryptography, Boca Raton Florida: CRC Press, ISBN 0-8493-8523-7
• (en) Canteaut, A., Sendrier, N., (1998) Cryptanalysis of the Original McEliece Cryptosystem. Springer Berlin / Heidelberg ISBN 978-3-540-65109-3
• (en) Bernstein, D.J., (2008), Bernstein, D.J., (2008), List decoding for binary Goppa codes, University of Illinois, Chicago