Lipsum.dev

Groupes, logarithmes et confidentialité persistante

26 novembre 2020 — Cryptographie, Go

Le protocole TLS (anciennement SSL) permet de sécuriser les communications sur Internet — authentification, contrôle d’intégrité et confidentialité des échanges.

Ce protocole définit notamment un handshake au cours duquel client et serveur s’accordent sur le choix de la suite cryptographique à utiliser pour sécuriser la communication ultérieure et échangent des clefs cryptographiques.

La page SSL Labs permet de scanner un serveur et de déterminer les versions de TLS et des suites cryptographiques (cipher suites) supportées.

Voici un extrait du résultat pour lipsum.dev :

SSL Labs lipsum.dev

On constate en particulier que le format des suites cryptographiques a changé avec TLS 1.3.

Dans la RFC 8446 qui définit ce protocole il est indiqué :

Static RSA and Diffie-Hellman cipher suites have been removed; all public-key based key exchange mechanisms now provide forward secrecy.

Nous proposons ici de présenter quelques notions mathématiques qui permettent la mise en oeuvre de cette confidentialité persistante (forward secrecy).

En particulier, TLS 1.3 repose sur des variantes d’un mécanisme d’échange de clefs imaginé en 1976 et utilisant des concepts mathématiques issus de la théorie des groupes.

Un peu de théorie

Une des caractéristiques des mathématiques est l’abstraction.

Cette abstraction consiste parfois à observer différents ensembles, les opérations associées et en déduire des structures communes.

L’une des structures algébriques les plus classiques est celle de groupe, qui intervient dans de nombreuses branches des mathématiques mais aussi en physique théorique, cristallographie, etc.

Structure de groupe

Un groupe est un ensemble GG muni d’une opération (notée ici *) qui permet d’effectuer des calculs sur cet ensemble en associant à deux éléments a,ba, b un troisième élément c=abc = a * b de GG.

Pour que cette opération définisse une structure de groupe, on exige :

  • l’opération est associative : a(bc)=(ab)ca * (b * c) = (a * b) * c (on omettra donc les parenthèses)
  • il existe un élément neutre eGe \in G tel que ge=eg=gg * e = e * g = g pour tout élément gg du groupe GG
  • les éléments de GG sont inversibles : pour tout aGa \in G, il existe bGb \in G tel que ab=ba=e{a * b = b * a = e}.
    Sous ces conditions, on montre que l’inverse est unique — je vous laisse le vérifier en exercice. On le notera a1a^{-1}, ou a-a lorsque l’opération du groupe est l’addition ++.
Exemples
  • L’ensemble Z\Z muni de l’opération d’addition ++ est un groupe.
    L’« inversion » de nn consiste alors à prendre son opposé n-n.
  • L’ensemble Q\Bbb{Q}^{*} des nombres rationnels non nuls muni de l’opération de multiplication ×\times est un groupe.
    L’inversion du nombre ab\frac{a}{b} (avec a,ba, b entiers non nuls) donne alors ba\frac{b}{a}.

Exponentiation et logarithme

L’exponentiation en base gg consiste à appliquer l’opération * de façon itérée à un élément gg d’un groupe GG.

On définit ainsi g0=eg^0 = e puis par récurrence gn+1=ggng^{n+1} = g * g^n pour nNn \in \N.

Exemples
  • L’exponentiation de l’addition sur Z\Z correspond à la multiplication, par exemple : a+a+a+a=4a{a + a + a + a = 4a} (aa désignant un entier quelconque)
  • La notation avec un exposant est réservée à l’exponentiation de la multiplication, qui correspond à la classique « puissance n-ème » : a×a×a×a=a4{a \times a \times a \times a = a^4}
Exponentiation rapide

Pour calculer gng^n, on peut naïvement effectuer des multiplications successives pour calculer la suite g,g2,g3,...,gng, g^2, g^3, ..., g^n.

Si l’on procède ainsi, le nombre de multiplications à effectuer est n1n-1.

Il existe une approche beaucoup plus efficace qui consiste à multiplier les résultats intermédiaires par eux-mêmes.

Par exemple, pour calculer h=g42h = g^{42}, on peut remarquer que 42=1010102{42 = 101010_2} (notation binaire) puis :

  • On part de h=eh = e (élément neutre)
  • On calcule successivement g,g2,g4=(g2)2,g8=(g4)2,g16=(g8)2,g32=(g16)2g, g^2, g^4 = {(g^2)}^2, g^8 = {(g^4)}^2, g^{16} = {(g^8)}^2, g^{32} = {(g^{16})}^2, en multipliant hh par g2kg^{2^k} à l’étape kk si le bit correspondant en notation binaire est à 11.
  • Le nombre obtenu est dans notre cas g2g8g32=g42g^2 * g^8 * g^{32} = g^{42}.

Ce calcul fait intervenir 55 multiplications au lieu des 4141 de la méthode naïve. Pour un exposant nn, ce nombre de multiplications est de l’ordre de log2(n)\log_2(n).

Notons que cet algorithme d’exponentiation rapide ne fait aucune hypothèse sur le groupe dont il est question ni sur la loi de composition *.

💻  En voici une implémentation (en Go), dans le cas classique de la multiplication des entiers :

// Computes a^n in O(log n) steps
func Exponentiate(a int, n int) int {
res := 1
for n > 0 {
if n%2 == 1 {
res *= a
n = (n - 1) / 2
} else {
n /= 2
}
a *= a
}
return res
}
Logarithme

Pour un groupe GG et un élément gg de ce groupe, le problème du logarithme en base gg consiste à résoudre l’équation gn=hg^n = h d’inconnue nn.

Suivant les cas, il existera zéro, une ou plusieurs solutions nn à cette équation — parfois une infinité.

Groupes cycliques

Un groupe cyclique est un cas particulier de groupe qui a les propriétés additionnelles suivantes :

  • GG est fini, on notera nn son nombre d’éléments.
  • GG est monogène, c’est-à-dire qu’il existe un élément gg à partir duquel on peut obtenir tous les autres par exponentiation.

On a alors G={g0,g1,...,gn1}{G = \{g^0, g^1, ..., g^{n-1}\}} et nécessairement (je vous laisse le prouver) gn=g0=eg^n = g^0 = e.

Calcul du logarithme discret

Le logarithme (discret) en base gg sur un groupe cyclique GG à nn éléments et généré par gg peut être défini comme une fonction logg:G{0,1,...,n1}\log_g: G \to \{0, 1, ..., n - 1 \} qui vérifie glogg(h)=hg^{\log_g(h)} = h pour tout hGh \in G.

Cette relation ne donne a priori ni formule explicite de calcul ni algorithme autre qu’une méthode par force brute consistant à tester successivement avec 0,1,2,...,n10, 1, 2, ..., n - 1.

On effectue alors en moyenne de l’ordre de nn opérations d’exponentation.

Il est cependant possible de le calculer de façon plus efficace :

  • sur n’importe quel groupe cyclique, par exemple avec l’algorithme baby-step giant-step que nous décrivons ci-dessous
  • ce nombre d’opérations peut encore être réduit si la décomposition de nn en produit de nombres premiers vérifie certaines conditions (algorithme de Pohlig-Hellman)
  • sur des cas particuliers de groupes, d’autres considérations peuvent amener à réduire drastiquement la complexité du problème
💡 Algorithme « Baby-step giant-step »

Ce paragraphe visant à présenter cet algorithme est facultatif, vous pourrez librement y revenir ensuite.

Cet algorithme proposé en 1971 permet d’obtenir logg(h)\log_g(h) en un nombre d’opérations de l’ordre de n\sqrt{n}.

Notons G={g0,g1,...,gn1}G = \{g^0, g^1, ..., g^{n-1}\} un groupe cyclique à nn éléments et NN l’arrondi supérieur de n\sqrt{n} (noté N=nN = \lceil \sqrt{n} \rceil).

Définissons alors :

  • Babies={0,1,2,...,N1}\textnormal{Babies} = \{ 0, 1, 2, ..., N-1 \} les entiers de 00 à N1N-1 par pas de 11
  • Giants={0,N,2N,...,(N1)N}\textnormal{Giants} = \{ 0, N, 2N, ..., (N-1)N \} les entiers de 00 à (N1)N(N-1)N par pas de NN

L’application f:Babies×GiantsGf: \textnormal{Babies} \times \textnormal{Giants} \to G définie par f(i,j)=gi+jf(i, j) = g^{i + j} est surjective.

Je vous laisse vous en convaincre en exercice, en considérant pour gkGg^k \in G quelconque la division euclidienne de kk par NN.

f(i,j)=hf(i, j) = h équivaut à résoudre gigj=hg^i * g^j = h soit gi=hgjg^i = h * g^{-j}

On est donc amené à chercher une collision entre les séquences (gi)iBabies(g^i)_{i \in \textnormal{Babies}} et (hgj)jGiants(h*g^{-j})_{j \in \textnormal{Giants}}, qui contiennent chacun N=nN = \lceil \sqrt{n} \rceil éléments.

On sait résoudre ce problème en O(n)O(\sqrt{n}) opérations (par exemple avec une table de hachage).

Les indices i,ji, j obtenus vérifient alors gi+j=hg^{i + j} = h ce qui résoud le problème du logarithme discret.

Échange de clés Diffie-Hellman

En 1976 est publié un article intitulé New Directions in Cryptography.

Cet article définit l’un des premiers mécanismes cryptographiques d’échange de clef, qui porte le nom d’échange de clés Diffie-Hellman.

Ce mécanisme permet à deux personnes, que nous appellerons Amandine et Bastien, d’établir une clef secrète S que eux seuls connaissent en échangeant sur un canal non sécurisé.

Nous verrons plus loin comment ce mécanisme est utilisé en pratique dans le protocole TLS.

Description de l’échange
  1. Amandine et Bastien ont choisi un groupe cyclique GG de taille nn et un générateur gg de ce groupe — ces données sont publiques.
    Le groupe GG étant fini, on peut encoder ses éléments sous forme de nombres de taille définie.
  2. Amandine génère un entier aléatoire aa, avec 0<a<n0 < a < n. Elle conserve secrètement aa et transmet à Bastien gag^a (sur le canal non sécurisé).
  3. De même, Bastien génère un entier aléatoire bb, avec 0<b<n0 < b < n. Il conserve secrètement bb et transmet à Amandine gbg^b (sur le canal non sécurisé).
  4. Bastien utilise sa clef secrète bb pour calculer (ga)b=gab(g^a)^b = g^{ab}.
  5. Amandine utilise sa clef secrète aa pour calculer (gb)a=gba=gab(g^b)^a = g^{ba} = g^{ab}.

À l’issue de cet échange, Amandine et Bastien ont tous deux connaissances du secret partagé S=gab{S = g^{ab}}.

Robustesse

Les clefs gag^a et gbg^b circulant sur des canaux non sécurisés, elles peuvent être utilisées par une tierce personne pour tenter d’obtenir le secret SS.

Si cette personne est capable de calculer l’un des logarithmes discrets logg(ga)\log_g(g^a) ou logg(gb)\log_g(g^b), elle peut alors obtenir l’un des exposants secrets aa ou bb et recalculer SS.

La résolution du logarithme discret est donc un vecteur d’attaque potentiel contre le mécanisme de Diffie-Hellman.

Bien que cela ne soit pas prouvé dans le cas général, on considère d’ailleurs que Diffie-Hellman est aussi sûr que le problème du logarithme discret.

La difficulté de calcul du logarithme sera donc déterminante dans le choix du groupe cyclique utilisé en pratique.

💻 Implémentation avec Golang

⚠️ Les implémentations naïves présentées dans cet article ne doivent évidemment pas être utilisées en production, leur but est purement didactique.

Nous proposons ci-dessous une implémentation avec différents groupes cycliques.

Cette implémentation est écrite en Go, dont nous utiliserons le module crypto, mais il n’est pas nécessaire d’être familier avec ce langage pour lire la suite.

Une interface CyclicGroup

L’interface ci-dessous définit ce qu’on attendra d’une implémentation d’un groupe cyclique.

On y retrouve les notions suivantes :

  • Identity, Compose, Inverse qui correspondent aux axiomes d’un groupe (élément neutre, loi de composition interne et inversion)
  • Order, Generator qui correspondent au cas d’un groupe cyclique
type CyclicGroup interface {
Identity() interface{}
Compose(a, b interface{}) interface{}
Inverse(a interface{}) interface{}
Exponentiate(a interface{}, exp *big.Int) interface{}
Generator() interface{}
Order() *big.Int
String() string
}

💡 On a utilisé des empty interface (qui peuvent contenir n’importe quelle valeur) pour typer les éléments du groupe, dont nous ne savons rien a priori. Dans d’autres langages, on pourrait utiliser des types génériques (inexistant en Go).

Groupe multiplicatif modulo p

Rappelons quelques définitions vues dans un article précédent.

On note Z/nZ\Z/n\Z l’ensemble des nombres entiers modulo nn (nn désigne un entier positif quelconque).

Compter dans Z/nZ\Z/n\Z revient à compter avec les nombres {0,1,...,n1}\{0, 1, ..., n - 1\} en considérant tous les calculs comme effectués modulo nn.

Par exemple, modulo 77, on a 5×5=25=4{5 \times 5 = 25 = 4} et la table de multiplication de Z/7Z\Z/7\Z est la suivante :

x0123456
00000000
10123456
20246135
30362514
40415263
50531642
60654321

On sait que lorsque pp est un nombre premier les éléments de Z/pZ\Z/p\Z différents de 00 sont tous inversibles pour la multiplication : Z/pZ\Z/p\Z est un corps que l’on notera aussi FpF_p.

On remarque également sur ce particulier que 33 permet de générer les 66 éléments non nuls de Z/7Z\Z/7\Z :
30=13^0 = 1, 31=33^1 = 3, 32=9=23^2 = 9 = 2, 33=63^3 = 6, 34=43^4 = 4, 35=53^5 = 5.

De fait, on montre qu’il existe toujours au moins un nombre dans FpF_p qui permet de générer tous les éléments non nuls par exponentiation, comme c’est le cas de 33 dans F7F_7.

Un tel nombre est appelé une racine primitive modulo pp.

Dès lors, l’ensemble des éléments non nuls de FpF_p muni de la multiplication est un groupe cyclique, d’ordre p1p-1.

Implémentation de MultGroup

Voici ci-dessous une implémentation très simple des groupes multiplicatifs modulo pp.

Notons que l’on utilise le type big.Int pour manipuler des entiers de taille arbitraire.

type MultGroup struct {
P *big.Int
Gen *big.Int
}
func (group *MultGroup) Order() *big.Int {
// P - 1
return new(big.Int).Add(group.P, big.NewInt(-1))
}
func (group *MultGroup) Identity() interface{} {
return big.NewInt(1)
}
func (group *MultGroup) Compose(a, b interface{}) interface{} {
// a * b % P
return new(big.Int).Mod(
new(big.Int).Mul(a.(*big.Int), b.(*big.Int)),
group.P,
)
}
func (group *MultGroup) Inverse(a interface{}) interface{} {
return new(big.Int).ModInverse(a.(*big.Int), group.P)
}
func (group *MultGroup) Exponentiate(a interface{}, exp *big.Int) interface{} {
return new(big.Int).Exp(a.(*big.Int), exp, group.P)
}
func (group *MultGroup) Generator() interface{} {
return group.Gen
}

💡 On utilise l’exponentiation modulaire des entiers implémentée nativement en Go, plus efficace que l’exponentiation rapide générique présentée précédemment du fait d’optimisations spécifiques au calcul modulaire.

Implémentation naïve de Diffie-Hellman

Je vous propose une implémentation naïve (cliquez sur le bouton Run ▶️ pour l’exécuter) de Diffie-Hellman en Go.

Le premier résultat utilise le groupe multiplicatif du corps F1291799F_{1291799} :

---
Diffie-Hellman: F_1291799 multiplicative group
Group order 1291798
Generator 17
---
Amandine generated secret key:
1266948
Amandine transmitted (public) key:
91778
Bastien generated secret key:
81716
Bastien transmitted (public) key:
1089774
Amandine computed shared secret:
489232
Bastien computed shared secret:
489232

Évidemment, ce groupe d’ordre 12917981291798 n’est pas à utiliser en pratique.

Je laisse d’ailleurs aux lecteurs et lectrices le soin d’implémenter l’algorithme baby-step giant-step décrit plus haut pour casser le secret ci-dessus…

Notons que les groupes multiplicatifs associés aux corps finis sont le choix d’origine pour l’échange de Diffie-Hellman et qu’ils sont encore utilisés aujourd’hui, avec des groupes dont le paramètre pp est sur 2048 bits ou plus.

Utilisation des courbes elliptiques

Qu’est-ce qu’une courbe elliptique ?

L’équation y2=x3+486662x2+xy^2 = x^3+486662x^2+x d’inconnues x,yx, y dans le corps FpF_p (avec p=225519{p = 2^{255} - 19}) définit une courbe elliptique sur FpF_p.

Le sujet est bien trop vaste pour une vraie présentation dans le cadre de cet article, remarquons simplement ceci :

  • il s’agit d’une courbe plane, son équation relie deux inconnues xx et yy de la même façon que l’équation yx2=0{y - x^2 = 0} définit une courbe dans le plan R2\R^2 (en l’occurrence une parabole)
  • cette courbe est, comme la parabole, une courbe algébrique : elle est définie par une équation polynomiale à deux indéterminées
  • c’est une cubique — le terme dominant de son équation est de degré 33. La parabole est quant à elle une conique — degré 22

💡 Parmi les courbes qui ont ces propriétés, les courbes elliptiques ont de plus un genre égal à 11. Le genre désigne ici une notion de géométrie algébrique qui coïncide dans le cas des courbes complexes avec une notion topologique assez visuelle : les courbes elliptiques sur C\Complex ont la même topologie qu’un donut.

Loi de groupe sur les courbes elliptiques

À toute courbe elliptique peut être associée une loi de groupe.

Cette loi est commutative et associe à deux points PP et QQ de la courbe un troisième point noté R=P+QR = P + Q.

💡 Ébauche de construction

L’idée générale est qu’en considérant deux points situés sur cette courbe, on peut en produire un troisième par un calcul algébrique.

Sans rentrer dans les développements, deux points PP et QQ d’une courbe plane définissent une droite — l’unique droite qui passe par PP et QQ (si P=Q{P = Q}, on considère la droite tangente à la courbe en ce point).

Cette droite admet une équation de la forme ax+by=cax + by = c(a,b)(0,0)(a, b) \neq (0, 0).

La recherche de tous les points d’intersections de cette droite avec une courbe elliptique amène à résoudre une équation du troisième degré en xx.

Par exemple pour la courbe définie plus haut : (caxb)2=x3+486662x2+x{(\frac{c - ax}{b})^2 = x^3+486662x^2+x}

Sous certaines hypothèses supplémentaires (notamment pour prendre en compte le cas b=0b = 0 ci-dessus…), on en déduit un mécanisme permettant d’associer aux points PP et QQ un troisième point R=P+QR = P + Q.

On montre alors que l’opération ++ ainsi introduite définit une loi de groupe commutatif.

Notons que malgré le vocabulaire de la géométrie plane utilisé ici (droite, tangente), cette construction est purement algébrique et possible sur n’importe quel corps de base — en particulier les corps finis.

💻 Implémentation en Go

Le package elliptic de Go introduit une interface Curve (reproduite ci-dessous) décrivant une courbe elliptique ainsi que différentes implémentations.

type Curve interface {
// Params returns the parameters for the curve.
Params() *CurveParams
// IsOnCurve reports whether the given (x,y) lies on the curve.
IsOnCurve(x, y *big.Int) bool
// Add returns the sum of (x1,y1) and (x2,y2)
Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int)
// Double returns 2*(x,y)
Double(x1, y1 *big.Int) (x, y *big.Int)
// ScalarMult returns k*(Bx,By) where k is a number in big-endian form.
ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int)
// ScalarBaseMult returns k*G, where G is the base point of the group
// and k is an integer in big-endian form.
ScalarBaseMult(k []byte) (x, y *big.Int)
}

Ce package implémente notamment les courbes P-256 et P-384 recommandées par le NIST et définies sur des corps FpF_p avec pp premier (sur 256256 et 384384 bits respectivement).

Ces courbes sont très utilisées en pratique, bien qu’elles soient l’objet de soupçons de backdoor par la NSA

Diffie-Hellman avec la courbe P-256

Ci-dessous, voici ce que donne notre implémentation de Diffie-Hellman avec la courbe P-256 (exécuter en ligne) :

---
Diffie Hellman: Elliptic Curve P-256
Field F_115792089210356248762697446949407573530086143415290314195533631308867097853951
Group order 115792089210356248762697446949407573529996955224135760342422259061068512044369
---
Amandine generated secret key:
7342462952232507609821760396776010434242597936110644963427068432176148435477
Amandine transmitted (public) key:
4298064935869640021519201203011003733572235803818690789383769808073692516886
Bastien generated secret key:
110170395102730437573897103177357816686836430099641375606421793187578417842509
Bastien transmitted (public) key:
6169708491757107974945465047131128230446890469460906853603235544851377683418
Amandine computed shared secret:
85470343014045070211971750616744066840724631640773885304746048731416023347568
Bastien computed shared secret:
85470343014045070211971750616744066840724631640773885304746048731416023347568

💡 On remarque que l’ordre du groupe généré est relativement proche de celui du corps fini utilisé : sur leurs 7878 chiffres, les 3737 premiers coincident.
C’est une conséquence d’un théorème connu

TLS 1.3 et la confidentialité persistante

Avant TLS 1.3, il était possible d’utiliser le même couple de clefs cryptographiques pour l’authentification et l’échange des clefs de session.

Ce mécanisme est qualifié de statique (par exemple static RSA, lorsque l’algorithme sous-jacent est RSA).

Avec TLS 1.3, des clefs asymétriques à usage unique (clefs éphémères) doivent être utilisées pour chaque session.

Ceci permet de garantir une confidentialité persistante : si une clef privée est compromise dans le futur, elle ne pourra pas être utilisée pour déchiffrer a posteriori des communications chiffrées qui auraient été conservées.

Le mécanisme de Diffie-Hellman permet de satisfaire cette exigence, en partageant une clef secrète S=gabS = g^{ab} — la clé « pre-master » — basée sur des clefs secrètes aa (client) et bb (serveur) éphémères.

Les lecteurs et lectrices souhaitant en savoir plus sur le fonctionnement de TLS pourront lire cette présentation par Cloudflare.

Le livre An Introduction to Mathematical Cryptography, utilisé comme source d’inspiration pour cet article, est une référence pour approfondir les notions théoriques.



Maths et applications, avec les mains et avec du code 💻
Suivre sur Twitter