Cryptographie basée sur les codes correcteurs d'erreurs · Plan 1 Codes6= Cryptographie 2 Notionsdethéoriedescodes 3 Fairedelacryptographieavecdescodes 4 Propositions,attaques,enjeux

Cryptographie basée sur les codes correcteurs d’erreurs

Alain Couvreur

INRIA & LIX, École Polytechnique — Gt Codes et Cryptographie

Journées du GdR IM 2016

A. Couvreur Cryptographie basée sur les codes GdR IM 2016 1 / 30

Plan

1 Codes 6= Cryptographie

2 Notions de théorie des codes

3 Faire de la cryptographie avec des codes

4 Propositions, attaques, enjeux


Codes 6= Cryptographie

1 Codes 6= Cryptographie



On les confond souvent

Problématiques classiques de la Théorie des codes :Comment communiquer efficacement via un canal bruité ?Comment stocker des données sur un support qui vieillira et sedégradera ?

Problématiques de la cryptographie : lorsque l’on communiquecomment se protéger des oreilles indiscrètes ?comment s’assurer que notre interlocuteur n’est pas un usurpateur ?

En résumé,en théorie des codes, on se protège contre le bruit ;en cryptographie on se protège contre les méchants.















Pourquoi les confond-on ?

La langue française (et probablement d’autres) n’aide pas... on parle de“message codé”,

on devrait dire message chiffré ;

“code secret”,

on devrait dire mot de passe ;

“décoder un message”,

on devrait dire décrypter.




La langue française (et probablement d’autres) n’aide pas... on parle de“message codé”, on devrait dire message chiffré ;“code secret”,

on devrait dire mot de passe ;

“décoder un message”,





La langue française (et probablement d’autres) n’aide pas... on parle de“message codé”, on devrait dire message chiffré ;“code secret”, on devrait dire mot de passe ;“décoder un message”,





La langue française (et probablement d’autres) n’aide pas... on parle de“message codé”, on devrait dire message chiffré ;“code secret”, on devrait dire mot de passe ;“décoder un message”, on devrait dire décrypter.



Le grand schtroumpf

dit toujourd qu’il ne faut pas

dire "schtroumpfer" mais

"schtroumpfer"

La langue française (et probablement d’autres) n’aide pas... on parle de“message codé”, on devrait dire message chiffré ;“code secret”, on devrait dire mot de passe ;“décoder un message”, on devrait dire décrypter.


Notions de théorie des codes

2 Notions de théorie des codes



Codes correcteurs d’erreurs

L’idée fondamentale : ajouter de la redondance à l’information.

Noise

Encoder Decoder

message c

ReceiverSender

Message m Encoded c⊕ e Decodedmessage m′

DéfinitionUn encodeur est une application linéaire injective : Fqk ↪→ Fqn .Un code correcteur est l’image d’une telle application, i.e. un sous-espacevectoriel C ⊆ Fqn .



Distance de Hamming

DéfinitionLa distance de Hamming sur Fqn est définie par

dH(x , y)def= |{i | xi 6= yi}|.

Par exemple dH((0, 1, 0, 1, 0, 1), (0, 1, 1, 1, 0, 0)) = 2.



Distance de Hamming

DéfinitionLa distance de Hamming sur Fqn est définie par

dH(x , y)def= |{i | xi 6= yi}|.

Par exemple dH((0, 1, 0, 1, 0, 1), (0, 1, 1, 1, 0, 0)) = 2.



Paramètres et décodeurs

À un code C ⊆ Fnq on associe :

sa longeur nsa dimension k . Le ratio k

n est appelé rendementsa distance minimale est

minx 6=y∈C

{dH(x , y)}.

Un algorithme de décodage t–correcteur prend en entrée y ∈ Fnq et

renvoiec ∈ C s’il existe un unique c ∈ C tel que dH(c , y) 6 t ;“ ?” sinon.



Paramètres et décodeurs

À un code C ⊆ Fnq on associe :

sa longeur nsa dimension k . Le ratio k

n est appelé rendementsa distance minimale est

minx 6=y∈C

{dH(x , y)}.

Un algorithme de décodage t–correcteur prend en entrée y ∈ Fnq et

renvoiec ∈ C s’il existe un unique c ∈ C tel que dH(c , y) 6 t ;“ ?” sinon.



Tous les codes sont bons mais...

TheorèmeSoit C ⊆ Fn

q un code aléatoire de longueur n et dimension k, alors

Proba(dminC 6 δn) = O(2−n),

où δ = 1− Hq(k

n

).

Autrement dit : “presque tous les codes ont une distance minimale linéaireen la longueur”. Mais...

Déterminer la distance minimale est un problème difficile ;On ne sait pas décoder un code aléatoire en temps polynomial.







où δ = 1− Hq(k

n

).


Déterminer la distance minimale est un problème difficile ;

On ne sait pas décoder un code aléatoire en temps polynomial.







où δ = 1− Hq(k

n

).


Déterminer la distance minimale est un problème difficile ;On ne sait pas décoder un code aléatoire en temps polynomial.



Les instances faciles

Les constructions algébriquesCodes de Reed–Muller ;Codes de Reed–Solomon ;Codes BCH ;Codes géométriques ;etc...

Les constructions “probabilistes”codes LDPC (codes de Gallager) ;Turbo-codes.



Codes de Reed–Solomon

DéfinitionSoient x1, . . . , xn des éléments distincts de Fq. Un code de Reed–Solomonest défini par

RSk(x)def= {(f (x1), . . . , f (xn)) | f ∈ Fq[X ]<k} .

Un code de Reed–Solomon estde dimension k ;et de distance minimale n − (k − 1).



Codes de Reed–Solomon

DéfinitionSoient x1, . . . , xn des éléments distincts de Fq. Un code de Reed–Solomonest défini par

RSk(x)def= {(f (x1), . . . , f (xn)) | f ∈ Fq[X ]<k} .

Un code de Reed–Solomon estde dimension k ;et de distance minimale n − (k − 1).



Décodage – L’algorithme de Berlekamp Welch

Soit c = (f (x1), . . . , f (xn)) ∈ RSk(x). Soit y = c + e avec dH(y , c) 6 t.y est connu ;on veut calculer c .

SoitE (X )

def=

∏i tels que ei 6=0

(X − xi )

On a :

∀i ∈ {1, . . . , n}, yiE (xi ) = f (xi )E (xi ).




Soit c = (f (x1), . . . , f (xn)) ∈ RSk(x). Soit y = c + e avec dH(y , c) 6 t.y est connu ;on veut calculer c .

SoitE (X )

def=

∏i tels que ei 6=0

(X − xi )

On a :

∀i ∈ {1, . . . , n}, yiE (xi ) = f (xi )E (xi ).




On a∀i ∈ {1, . . . , n}, yiE (xi ) = f (xi )E (xi ).

où :les xi , yi sont connus ;E , f sont inconnus mais on sait que deg E 6 t et deg f < k .

On pose N(X )def= f (X )E (X ) et on résout le système linéaire d’inconnues

E (de degré 6 t) et N (de degré < t + k) :

∀i ∈ {1, . . . , n}, yiE (xi ) = N(Xi ).

On ramène le problème du décodage à un problème d’algèbre linéaire.Cet algorithme permet de corriger jusqu’à n−k

2 erreurs.








∀i ∈ {1, . . . , n}, yiE (xi ) = N(Xi ).


2 erreurs.








∀i ∈ {1, . . . , n}, yiE (xi ) = N(Xi ).


2 erreurs.



Où sont-ils ?

Pour corriger des erreurs :Programme Voyager ;

CD, DVD, Blu Ray ;ADSL ;codes barres, QR codes ;etc...

Pour d’autres choses :Partage de secret (avec menteurs), calcul multi parti ;fonctions de hachage ;etc...



Où sont-ils ?

Pour corriger des erreurs :Programme Voyager ;CD, DVD, Blu Ray ;

ADSL ;codes barres, QR codes ;etc...




Où sont-ils ?

Pour corriger des erreurs :Programme Voyager ;CD, DVD, Blu Ray ;ADSL ;

codes barres, QR codes ;etc...




Où sont-ils ?

Pour corriger des erreurs :Programme Voyager ;CD, DVD, Blu Ray ;ADSL ;codes barres, QR codes ;

etc...




Où sont-ils ?

Pour corriger des erreurs :Programme Voyager ;CD, DVD, Blu Ray ;ADSL ;codes barres, QR codes ;etc...




Où sont-ils ?

Pour corriger des erreurs :Programme Voyager ;CD, DVD, Blu Ray ;ADSL ;codes barres, QR codes ;etc...



Faire de la cryptographie avec des codes

3 Faire de la cryptographie avec des codes



Le schéma de McEliece (1978)

Schéma de chiffrement à clé publique reposant sur la difficulté de décoderun code aléatoire.

On se donne une famille de triplets (C , t,A), oùC est un code [n, k]q de matrice génératrice G ;t ∈ N∗ ;A est algorithme “rapide” corrigeant jusqu’à t erreurs



Principe du schéma de McEliece

Fonctionnement :

Clé publique : (G , t) ;Clé secrète : A.Chiffrement : m ∈ Fk

qc = mG ∈ C

On génère e ∈ Fnq aléatoire tel que wH(e) 6 t ;

message chiffré :mchiffr

def= c + e

Déchiffrement : On applique A et on retrouve c puis m.




Fonctionnement :Clé publique : (G , t) ;

Clé secrète : A.Chiffrement : m ∈ Fk

qc = mG ∈ C



def= c + e





Fonctionnement :Clé publique : (G , t) ;Clé secrète : A.

Chiffrement : m ∈ Fkq

c = mG ∈ C



def= c + e





Fonctionnement :Clé publique : (G , t) ;Clé secrète : A.Chiffrement : m ∈ Fk

qc = mG ∈ C



def= c + e






qc = mG ∈ COn génère e ∈ Fn

q aléatoire tel que wH(e) 6 t ;


def= c + e







q aléatoire tel que wH(e) 6 t ;message chiffré :

mchiffrdef= c + e







q aléatoire tel que wH(e) 6 t ;message chiffré :

mchiffrdef= c + e




Avantages et inconvénients

Avantageschiffrement et déchiffrement rapides. Par exemple, [Canteaut Sendrier1998]

chiffrement ≈ 5 fois plus rapide que RSA 1024 (exposant public = 17)déchiffrement ≈ 150 fois plus rapide que RSA 1024.

Post quantique.

InconvénientsNécessite souvent de grandes tailles de clé La proposition historique(McEliece 1978) : 67ko key (pour une sécurité inférieure à RSA 1024).Mais des améliorations récentes (c.f. plus loin...)



Avantages et inconvénients

Avantageschiffrement et déchiffrement rapides. Par exemple, [Canteaut Sendrier1998]

chiffrement ≈ 5 fois plus rapide que RSA 1024 (exposant public = 17)déchiffrement ≈ 150 fois plus rapide que RSA 1024.

Post quantique.Inconvénients

Nécessite souvent de grandes tailles de clé La proposition historique(McEliece 1978) : 67ko key (pour une sécurité inférieure à RSA 1024).Mais des améliorations récentes (c.f. plus loin...)


Propositions, attaques, enjeux

4 Propositions, attaques, enjeux



Comment proposer une famille de codes

On doit avoirune large famille de codes (éviter les attaques par rechercheexhaustive) ;des codes de “grande” dimension (résister aux attaques sur les chiffrés)des codes dont la structure est masquable (pour résister aux attaquessur la clé).



Familles proposées

Codes de Goppa Binaires [McEliece, 1977](RS/F2m ∩ Fn

2)

Paramètres Clé Sécurité[1024, 524, 101]2 67ko 262

[2048, 1608, 48]2 412ko 296

Pas d’attaque structurelle connue à ce jour



Familles proposées

Codes de Goppa Binaires [McEliece, 1977](RS/F2m ∩ Fn

2)


[2048, 1608, 48]2 412ko 296

Pas d’attaque structurelle connue à ce jour



Familles proposées

Codes de Reed–Solomon Généralisés (GRS)[Niederreiter, 1986]


[Sidelnikov Shestakov, 1992]Attaque en O(n3)



Familles proposées

Codes de Reed–Solomon Généralisés (GRS)[Niederreiter, 1986]


[Sidelnikov Shestakov, 1992]Attaque en O(n3)



Familles proposées

Codes de Reed–Muller Binaires [Sidelnikov, 1994]

Paramètres Clé Sécurité[1024, 176, 128]2 22.5ko 272

[2048, 232, 256]2 59.4ko 293

[Minder Shokrollahi, 2007]Attaque sous-exponentielle.



Familles proposées

Codes de Reed–Muller Binaires [Sidelnikov, 1994]

Paramètres Clé Sécurité[1024, 176, 128]2 22.5ko 272

[2048, 232, 256]2 59.4ko 293

[Minder Shokrollahi, 2007]Attaque sous-exponentielle.



Familles proposées

Codes géométriques [Janwa Moreno, 1996]


Attaques Polynomiales[Faure Minder, 2008], genre 6 2[C-, Márquez–Corbella, Pellikaan, 2014],genre quelconque



Familles proposées

Codes géométriques [Janwa Moreno, 1996]


Attaques Polynomiales[Faure Minder, 2008], genre 6 2[C-, Márquez–Corbella, Pellikaan, 2014],genre quelconque



Familles proposées

Variantes avec clés compactes[Gaborit, 2005], codes BCH ;(∼ 1.5 ko, Sécurité : > 280)

[Berger, Cayrel, Gaborit, Otmani, 2009], codes alternantsquasi-cycliques ;(∼ 750 o, Sécurité : > 280)

[Misoczki, Baretto, 2009], codes alternants quasi-diadiques.(∼ 2.5 ko, Sécurité : > 280)

[Otmani, Tillich, Dallot, 2008][Faugère, Otmani, Perret, Tillich, 2010][Faugère, Perret, Otmani, Portzamparc,

Tillich 2015]



Familles proposées

Variantes avec clés compactes[Gaborit, 2005], codes BCH ;(∼ 1.5 ko, Sécurité : > 280)

[Berger, Cayrel, Gaborit, Otmani, 2009], codes alternantsquasi-cycliques ;(∼ 750 o, Sécurité : > 280)

[Misoczki, Baretto, 2009], codes alternants quasi-diadiques.(∼ 2.5 ko, Sécurité : > 280)

[Otmani, Tillich, Dallot, 2008][Faugère, Otmani, Perret, Tillich, 2010][Faugère, Perret, Otmani, Portzamparc,

Tillich 2015]



Familles proposées

Codes de Goppa q–aires [Bernstein, Lange, Peters, 2010]

Des clés de 78 à 200ko d’une sécurité > 2128.

Non cassé, mais...

[C. Otmani, Tillich, 2014] sous-corps d’indice 2[Faugere, Perret, de Portzamparc 2015] codes sur des corpsnon premiers de petite caractéristique



Familles proposées

Codes de Goppa q–aires [Bernstein, Lange, Peters, 2010]

Des clés de 78 à 200ko d’une sécurité > 2128.

Non cassé, mais...

[C. Otmani, Tillich, 2014] sous-corps d’indice 2[Faugere, Perret, de Portzamparc 2015] codes sur des corpsnon premiers de petite caractéristique



Conclusion

Les codes qui restent en course :Constructions algébriques :

Les codes de Goppa (RS/Fqm ∩ Fnq) avec m > 3 ;

Leurs généralisations géométriques.

Constructions probabilistes [Baretto, Misoczki, Tillich, Sendrier]Codes MDPC (quasi–cycliques) : clés ≈ 10000 bits pour 128 bits desécurité.



Conclusion

Les codes qui restent en course :Constructions algébriques :

Les codes de Goppa (RS/Fqm ∩ Fnq) avec m > 3 ;

Leurs généralisations géométriques.

Constructions probabilistes [Baretto, Misoczki, Tillich, Sendrier]Codes MDPC (quasi–cycliques) : clés ≈ 10000 bits pour 128 bits desécurité.



Merci !


Documents

Cryptographie basée sur les codes correcteurs d'erreurs · Plan 1 Codes6= Cryptographie 2 Notionsdethéoriedescodes 3 Fairedelacryptographieavecdescodes 4 Propositions,attaques,enjeux