McEliece, kodebaseret kryptografi og matrixprodukt-koder

McEliece, code based cryptography and matrix-product codes

Bentzen-Petersen, Ida ; Melander, Camilla Lund

4. semester

Matematik, Kandidat

2016

2016-01-29

160

Dette projekt undersøger McEliece-kryptosystemet, et krypteringssystem baseret på fejlkorrigerende koder. En kendt ulempe ved systemet er den meget store offentlige nøgle. Vores mål er at gøre nøglen mindre ved at bruge matrixprodukt-koder (en måde at bygge nye koder ud fra mindre delkoder). Først forklarer vi McEliece-kryptosystemet og McElieces oprindelige brug af Goppa-koder. Vi sammenligner også med det ækvivalente system udviklet af Niederreiter og fokuserer derefter på McEliece, fordi de to systemer i praksis er ens. Derefter gennemgår vi to angrebstyper: beskedangreb (rettet mod at dekryptere en konkret besked) og nøgleangreb (rettet mod at finde den hemmelige nøgle). Eksempler viser, at det er beregningsmæssigt meget dyrt at bryde McEliece, selv med små kodeparametre. Nogle kodefamilier vurderes fortsat sikre mod kendte angreb, herunder irreducerbare binære Goppa-koder. For at reducere nøglestørrelsen ser vi på koder med en kvasi-cyklisk struktur og præsenterer den nødvendige teori. Vi introducerer også Gaborits variant af McEliece, som udnytter kvasi-cykliske koder og en særlig konstruktion af generator-matricen (en matrix, der beskriver koden) for at gøre nøglen mindre. I denne variant skjules generator-matricen kun med en permutationsmatrix (der omarrangerer positioner). Fordi varianten bruger underkoder af BCH-koder, er det vist, at den kan brydes. Selve idéen inspirerer dog en ny retning baseret på matrixprodukt-koder. Vi præsenterer matrixprodukt-koder og viser blandt andet, at minimumafstanden (et mål for, hvor mange fejl koden kan rette) kan beregnes præcist under visse betingelser. Vi giver også en afkodningsalgoritme, når delkoderne er indlejrede, og når den anvendte matrix er ikke-singulær kolonnevis (en teknisk betingelse, der sikrer, at beregninger kan vendes). Derudover viser vi, hvordan denne kodetype kan indgå i McEliece. Til sidst foreslår vi en ny variant af McEliece, der kombinerer matrixprodukt-koder med Gaborits idé om at begrænse permutationerne til små dele af kodeordet. Da en generator-matrix for en matrixprodukt-kode kan bygges af de små delkoders generator-matricer sammen med en matrix A, kan den offentlige nøgle gøres mindre ved kun at offentliggøre disse mindre matricer i stedet for én stor. Man kunne frygte, at varianten derfor også kan brydes som Gaborits, men vi peger på, at brug af irreducerbare binære indlejrede Goppa-koder kan gøre angreb vanskelige, fordi denne kodetype stadig regnes for robust mod kendte angreb. Som muligt fremtidigt arbejde foreslår vi at undersøge underfelts-underkoder til den nye variant, en idé som også er foreslået af Berger for Gaborits system.

This thesis studies the McEliece cryptosystem, an encryption scheme built on error-correcting codes. A well-known drawback is its very large public key. Our goal is to shrink this key by using matrix-product codes (a way to build new codes from smaller component codes). We first explain the McEliece scheme and McEliece’s original use of Goppa codes. We also compare it to the equivalent Niederreiter scheme and then focus on McEliece because the two are effectively the same. Next, we examine two attack types: message attacks (aimed at decrypting a specific message) and key attacks (aimed at recovering the secret key). Examples show that breaking McEliece is computationally very costly even for small code parameters. Some code families remain resistant to known attacks, in particular irreducible binary Goppa codes. To reduce key size, we consider codes with a quasi-cyclic structure and present the relevant theory. We introduce Gaborit’s variant of McEliece, which uses quasi-cyclic codes and a special way to build the generator matrix (a matrix that defines the code) to make the key smaller. In this variant, the generator matrix is hidden only by a permutation matrix (which rearranges positions). Because it uses subcodes of BCH codes, this variant has been shown to be breakable. Nevertheless, the core idea motivates a new approach based on matrix-product codes. We present matrix-product codes and show, among other things, that their minimum distance (a measure of how many errors the code can correct) can be computed exactly under certain conditions. We also give a decoding algorithm when the component codes are nested and when the mixing matrix is non-singular by columns (a technical condition that ensures computations can be inverted). We further illustrate how this code family can be used within McEliece. Finally, we propose a new McEliece variant that combines matrix-product codes with Gaborit’s idea of restricting permutations to small blocks of the codeword. Since a generator matrix for a matrix-product code can be assembled from the small component generator matrices together with a matrix A, the public key can be reduced by publishing only these smaller matrices instead of one huge matrix. One might worry that this variant could be broken like Gaborit’s; we suggest that using irreducible binary nested Goppa codes may make attacks impractical, as this code family is still considered robust against known attacks. For future work, we propose exploring subfield subcodes for the new variant, an idea also suggested by Berger for Gaborit’s scheme.

[Dette resumé er genereret ved hjælp af AI]

Download
Vis denne rapport i AAU Studenterprojekter