# Les codes correcteurs au service de la cryptographie symétrique et asymétrique

Abderrahman Daif

► To cite this version:

Abderrahman Daif. Les codes correcteurs au service de la cryptographie symétrique et asymétrique. Cryptographie et sécurité [cs.CR]. Université Paris 8, 2019. Français. NNT: 2019PA080101 . tel-04047802

HAL Id: tel-04047802

https://hal.science/tel-04047802

Submitted on 27 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
École doctorale
Cognition, Langage, Interaction

Spécialité
Informatique

THÈSE DE DOCTORAT DE L'UNIVERSITÉ PARIS VIII

Présentée par

Abderrahman DAIF

Pour obtenir le grade de

DOCTEUR

Sujet de la thèse :

Les codes correcteurs au service de la cryptographie
symétrique et asymétrique.

Soutenue le 3 mai 2019 devant le jury composé de :

M. Claude CARLET	Directeur de thèse
M. Cédric TAVERNIER	Co-directeur de thèse
M. Sylvain DUQUESNE	Rapporteur
M. Damien VERGNAUD	Rapporteur
M. Sylvain GUILLEY	Examinateur
Mme. Sihem MESNAGER	Examinateur
M. Emmanuel PROUFF	Examinateur
<figure><img src="image_2.png" /></figure>
Remerciements

Tout d'abord je tiens à remercier mes deux directeurs de thèse, CLAUDE CAR-
LET et CÉDRIC TAVERNIER qui ont gentiment accepté d'encadrer cette thèse, et
qui ont énormément contribué à sa réussite. Merci à eux pour leur disponibilité
permanente, leurs encouragements, et leur soutien.

Je tiens également à remercier le professeur SYLVAIN GUILLEY avec qui j'ai eu la
chance d'échanger sur divers projets, et qui m'a apporté son conseil à plusieurs
reprises.

Un grand merci aussi aux rapporteurs et aux membres du jury, qui ont pris le soin
de relire cette thèse, et de me faire part de leurs précieux conseils.

Je remercie mes collègues de l'équipe Cyber-sécurité chez Assystem, ainsi que les
membres de la BU Connect qui ont tous contribué, chacun à sa manière, à la
réussite de cette thèse. Je remercie en particulier GREGORY LANDAIS qui n'a
jamais hésité à apporter son soutien et à partager ses idées avec moi.

Je remercie mes amis et camarades de classe, les membres de P8, COC et OP.

Enfin, je remercie ma famille pour leur soutien, en particulier mes parents, mon
épouse, et mon fils adoré.

Merci à toutes ces personnes qui ont fait de cette thèse une réussite !
<figure><img src="image_3.png" /></figure>
# Résumé

Dans la première partie de cette thèse nous étudions les différentes méthodes de masquage permettant de lutter contre les attaques physiques sur les cryptosystèmes embarqués. Rappelons les données du problème. Juste après la naissance du nouveau standard de chiffrement symétrique appelé AES au début de ce siècle, des travaux ont montré que les attaques par canaux auxiliaires (SCA) constituent une menace pour les systèmes de chiffrement implémentés dans des dispositifs embarqués. La consommation électrique pendant une opération de chiffrement ou le temps de calcul peuvent divulguer des informations sur des valeurs intermédiaires manipulées au cours de l'exécution de l'algorithme de chiffrement. Ceci entraîne des attaques pratiques sur les composants électriques. Les rayonnements électromagnétiques, et même les sons émis par les machines à rotor peuvent également donner à l'attaquant une fenêtre de visibilité sur les valeurs intermédiaires au cours du calcul. Ce type d'attaques fournit à l'adversaire une version bruitée de certaines valeurs comme le poids de Hamming de certaines données sensibles. Par ailleurs, les attaques par injection de faute (FIA) consistent à agir sur les conditions environnementales du système (tension, température, rayonnement, lumière, ...) pour générer des erreurs pendant l'exécution de l'algorithme de chiffrement ou déchiffrement et observer ensuite le comportement résultant. De telles attaques peuvent être conçues en ciblant simplement un transistor avec un faisceau laser, ce qui génère un dysfonctionnement lié à la modification de la fréquence du travail pendant le calcul, entraînant une mauvaise valeur de certains bits.

Nous présentons quelques méthodes de masquage pour protéger l'AES contre les SCA et FIA. Chacune de ces méthodes repose sur une structure particulière (le partage du secret, le produit scalaire, les codes correcteurs...). Nous étudions également le détail de la structure de l'AES pour mieux évaluer comment s'implémentent ces méthodes et mesurer la complexité de chacune. Pour ce faire, nous reconstruisons chacune des transformations qui composent l'AES en utilisant ces différentes méthodes de masquage. Cette étude montre la difficulté de masquer à la fois les deux opérations qui interviennent dans les fonctions de l'AES (addition et multiplication) et en même temps de détecter les erreurs potentielles. Pour surmonter ce problème, nous avons conçu un masquage basé sur les codes LCD. Cette
méthode a été introduite initialement en 2014 par CLAUDE CARLET et SYLVAIN GUILLEY, et permet de protéger contre les deux types d'attaques. Cependant, le masquage de la multiplication restait un problème ouvert. Pour le résoudre nous avons choisi de restructurer cette méthode en utilisant une représentation de corps finis au lieu d'espaces vectoriels. La nouvelle méthode permet ainsi de masquer l'addition et la multiplication, de détecter les erreurs potentielles, et apporte également un gain intéressant en terme de complexité algorithmique (nous passons d'une complexité quadratique à une complexité linéaire).

Dans la deuxième partie, nous étudions les problématiques liées à la gestions des clés pour les systèmes de chiffrement asymétriques. En 1976, DIFFIE et HELLMAN ont marqué le début d'une nouvelle ère dans le domaine de la cryptographie avec l'invention de la cryptographie asymétrique (à clé publique). La cryptographie asymétrique est préférable à la cryptographie symétrique, puisqu'elle permet de communiquer en toute sécurité sans passer par l'échange préalable d'une clé secrète. Deux ans après l'invention de la cryptographie asymétrique, le premier algorithme de chiffrement a été proposé par RIVEST, SHAMIR et ADLEMAN, ce schéma est connu jusqu'à nos jours sous le nom de RSA. Bien que ces systèmes soient efficaces en particulier pour échanger les clés, ils ne permettent malheureusement pas d'identifier le propriétaire d'une clé publique. Il a fallu donc trouver une solution qui permette de créer ce lien entre la clé publique et l'identité de son possesseur dans le but de se protéger contre l'usurpation d'identité.

Nous étudions donc les différentes infrastructures de gestion de clés. En particulier les schémas basés sur les certificats (PKI), et le chiffrement basé sur l'identité (IBE). Nous étudions les travaux réalisés ces dernières années sur IBE. Nous exposons les exigences que doit satisfaire un système de gestion de clés, ces exigences concernent particulièrement le problème de révocation, l'autorité de séquestre, et la décentralisation. Enfin nous présentons une version flexible d'IBE pour satisfaire ces exigences, et qui répond à besoin réel dans le monde industriel.
Abstract

In the first part of this thesis, we are studying different masking methods to pro-
tect embedded cryptosystems against physical attacks. Just after the birth of the
advanced encryption standard called AES, various studies have shown that side
channel attacks (SCA) represent a threat to cryptosystems implemented in em-
bedded devices. The measurement of power consumption during an encryption
operation, or the calculation of the time taken by calculi may disclose information
about the manipulated values during the execution of the encryption algorithm.
This leads to practical attacks on the electrical components. The electromagnetic
radiation and even the sounds emitted by the rotor machines can also give the
attacker a window of visibility on the intermediate values during the calculation.
This type of attack provides a noisy version of values (such as the Hamming weight
of some sensitive data) to the opponent. In addition, fault injection attacks (FIA)
consist in acting on the environmental conditions of the system (voltage, tempe-
rature, radiation...) to generate faults during the execution of the encryption or
decryption algorithm and then observe the resulting behavior. Such attacks can be
designed by simply illuminating a transistor with a laser beam, which generates a
malfunction related to the change of the working frequency during the calculation
and which causes a bad value of certain bits.

We are presenting some masking methods to protect the AES against SCA and
FIA. Each of these methods is based on a particular structure (secret sharing, inner
product, correcting codes ...). We are also studying the details of the AES to better
evaluate in a finer way how these methods apply and measure the complexity of
each. To do this, we reconstruct each of the transformations that composes the
AES using these different masking methods.

This study shows the difficulty of both masking in the two operations that compose
the AES (addition and multiplication) and in the same time detecting potential
errors. To overcome this problem, we designed a masking method based on LCD
codes. This method initially introduced in 2014 by CLAUDE CARLET and SYLVAIN
GUILLEY protects against both types of attacks. However, masking the multiplica-
tion remained an open problem. To solve this problem we chose to restructure this
method using a representation of finite fields instead of vector spaces. The new
method thus makes it possible to mask the addition and the multiplication, to
detect the potential errors, and brings an interesting gain in terms of algorithmic
complexity (we go from a quadratic complexity to a linear complexity).

In the second part, we study issues related to key management for asymmetric en-
cryption systems. In 1976, DIFFIE and HELLMAN marked the beginning of a new
era in the field of cryptography with the invention of public key cryptography.
Public key cryptography is preferable to symmetric cryptography since it allows
secured communication without the need for prior exchange of a secret key. Two
years after the invention of public key cryptography, the first encryption scheme
was proposed by RIVEST, SHAMIR and ADLEMAN, this scheme is known today as
the RSA. Although these systems are effective for exchanging keys, they unfortu-
nately do not identify the owner of a public key. It was therefore necessary to find
a solution that would create this link between the public key and the identity of
its owner in order to protect against identity usurpation.

In this thesis, we are therefore studying different key management infrastructures.
Particularly, certificate-based schemes (PKI) and identity-based encryption (IBE).
We are studying the work done in recent years on IBE. We outline the requirements
that must be met by a key management system. These requirements relate parti-
cularly to the problem of revocation, key-escrow, and decentralization. Finally, we
present a flexible version of IBE to meet these requirements.
# Table des matières

Remerciements i

Résumé iii

Abstract v

1 Introduction générale 1

1.1 L'organisation du document 2

1.2 Introduction à la cryptographie 2

1.3 Vocabulaire 3

1.3.1 La cryptographie symétrique 3

1.3.2 La cryptographie asymétrique 4

1.3.3 La théorie de la complexité 7

1.3.4 Les fonctions de hachage 10

1.3.5 La signature numérique 11

1.4 L'infrastructure à clé publique 13

1.4.1 Le protocole de Diffie-Hellman 13

1.4.2 L'attaque de l'homme au milieu 13

1.4.3 Le principe des certificats 15

1.4.4 Le fonctionnement de l'infrastructure de gestion de clés (PKI) 16

1.5 Le chiffrement basé sur l'identité (IBE) 18

1.5.1 Le principe général 18

1.5.2 Les exigences d'un système de gestion de clé 20

1.5.3 Comparaison entre PKI et IBE 21

1.5.4 Conclusion 23

1.6 Les codes correcteurs 23

1.6.1 L'encodage 24

1.6.2 Le décodage 25

1.6.3 Les codes parfaits 26

1.6.4 Les codes de Reed-Muller binaires 28

1.7 L'AES 32
TABLE DES MATIÈRES

<table><tr><td>1.7.1 Chiffrement</td><td>34</td></tr><tr><td>1.7.2 Déchiffrement</td><td>35</td></tr></table>

# I Les techniques de masquage pour lutter contre les attaques par canaux auxiliaires (SCA) et les attaques par injection de fautes (FIA) 37

## 1 L'état de l'art sur le masquage 39

<table><tr><td>1.1 Le masquage booléen</td><td>42</td></tr><tr><td>1.1.1 Le schéma Ishai-Sahai-Wagner (ISW)</td><td>42</td></tr><tr><td>1.1.2 Le schéma de Rivain et Prouff (RP)</td><td>44</td></tr><tr><td>1.2 Le masquage basé sur les polynômes</td><td>53</td></tr><tr><td>1.2.1 Le schéma de Shamir sur le partage du secret</td><td>53</td></tr><tr><td>1.2.2 Les codes de Reed-Solomon</td><td>55</td></tr><tr><td>1.2.3 Le masquage basé sur le partage du secret</td><td>55</td></tr><tr><td>1.2.4 Le schéma sécurisé de calcul multipartite BGW</td><td>57</td></tr><tr><td>1.2.5 L'algorithme de multiplication de Prouff et Roche</td><td>58</td></tr><tr><td>1.3 Le masquage basé sur le produit scalaire (IPM)</td><td>59</td></tr><tr><td>1.4 Le masquage basé sur les codes</td><td>62</td></tr><tr><td>1.4.1 Rappels</td><td>62</td></tr><tr><td>1.4.2 Le masquage par somme directe orthogonale (ODSM)</td><td>64</td></tr><tr><td>1.4.3 Exemple</td><td>71</td></tr><tr><td>1.5 Conclusion</td><td>73</td></tr></table>

## 2 Le masquage par somme directe sur un corps fini 75

<table><tr><td>2.1 Introduction</td><td>76</td></tr><tr><td>2.1.1 Objectifs</td><td>76</td></tr><tr><td>2.1.2 Vocabulaire</td><td>76</td></tr><tr><td>2.2 L'addition et la multiplication</td><td>78</td></tr><tr><td>2.2.1 L'addition</td><td>78</td></tr><tr><td>2.2.2 La multiplication par une valeur publique</td><td>79</td></tr><tr><td>2.2.3 La multiplication entre deux valeurs sensibles</td><td>80</td></tr><tr><td>2.3 Sécurité et performances</td><td>81</td></tr><tr><td>2.4 Exemple général : La boîte de substitution (SubBytes)</td><td>84</td></tr><tr><td>2.5 Détection et correction des erreurs</td><td>86</td></tr><tr><td>2.6 Conclusion</td><td>88</td></tr></table>
## II La cryptographie basée sur l'identité 89

### 1 Introduction 91

1.1 Rappels sur la théorie des groupes 92

1.2 Les courbes elliptiques 94

1.2.1 Définition 94

1.2.2 Les formules d'addition et doublement 95

1.2.3 Le groupe de torsion 96

1.2.4 Le couplage sur les courbes elliptiques 97

1.2.5 L'échange des clés à trois 98

1.2.6 La signature courte 98

1.3 Le schéma de Boneh et Franklin 99

1.3.1 Les avantages du schéma de Boneh et Franklin (BF-IBE) 100

1.3.2 Le schéma BF-IBE 100

1.3.3 La sécurité du schéma BF-IBE 102

1.3.4 L'enrôlement et la mise à jour des clés 105

1.4 Critiques et améliorations 105

1.4.1 Émission sécurisée des clés 106

1.4.2 Conclusion 109

### 2 Amélioration d'IBE 111

2.1 Introduction 112

2.2 Les paramètres du système 112

2.3 L'extraction de la clé privée 113

2.3.1 L'enrôlement 113

2.3.2 La mise à jour des clés 115

2.4 Analyse de sécurité 116

2.5 La révocation des clés 117

2.5.1 La problématique 117

2.5.2 Les solutions existantes 118

2.5.3 La solution proposée 118

2.6 Récapitulatif 119

### 3 Conclusion et perspectives 121

3.1 La protection contre les attaques par canaux auxiliaires et les attaques par injection de faute 122

3.1.1 Rappel 122

3.1.2 Le masquage 122

3.1.3 Perspectives 124

3.2 Les infrastructures de gestion des clés 124

3.2.1 Rappel 124
TABLE DES MATIÈRES

<table><tr><td>3.2.2 Les solutions proposées et les perspectives</td><td>126</td></tr><tr><td>Index alphabétique</td><td>131</td></tr></table>
# 1 | Introduction générale

## Sommaire

<table><tr><td>1.1</td><td>L'organisation du document</td><td>2</td></tr><tr><td>1.2</td><td>Introduction à la cryptographie</td><td>2</td></tr><tr><td>1.3</td><td>Vocabulaire</td><td>3</td></tr><tr><td>1.3.1</td><td>La cryptographie symétrique</td><td>3</td></tr><tr><td>1.3.2</td><td>La cryptographie asymétrique</td><td>4</td></tr><tr><td>1.3.3</td><td>La théorie de la complexité</td><td>7</td></tr><tr><td>1.3.4</td><td>Les fonctions de hachage</td><td>10</td></tr><tr><td>1.3.5</td><td>La signature numérique</td><td>11</td></tr><tr><td>1.4</td><td>L'infrastructure à clé publique</td><td>13</td></tr><tr><td>1.4.1</td><td>Le protocole de Diffie-Hellman</td><td>13</td></tr><tr><td>1.4.2</td><td>L'attaque de l'homme au milieu</td><td>13</td></tr><tr><td>1.4.3</td><td>Le principe des certificats</td><td>15</td></tr><tr><td>1.4.4</td><td>Le fonctionnement de l'infrastructure de gestion de clés (PKI)</td><td>16</td></tr><tr><td>1.5</td><td>Le chiffrement basé sur l'identité (IBE)</td><td>18</td></tr><tr><td>1.5.1</td><td>Le principe général</td><td>18</td></tr><tr><td>1.5.2</td><td>Les exigences d'un système de gestion de clé</td><td>20</td></tr><tr><td>1.5.3</td><td>Comparaison entre PKI et IBE</td><td>21</td></tr><tr><td>1.5.4</td><td>Conclusion</td><td>23</td></tr><tr><td>1.6</td><td>Les codes correcteurs</td><td>23</td></tr><tr><td>1.6.1</td><td>L'encodage</td><td>24</td></tr><tr><td>1.6.2</td><td>Le décodage</td><td>25</td></tr><tr><td>1.6.3</td><td>Les codes parfaits</td><td>26</td></tr><tr><td>1.6.4</td><td>Les codes de Reed-Muller binaires</td><td>28</td></tr><tr><td>1.7</td><td>L'AES</td><td>32</td></tr><tr><td>1.7.1</td><td>Chiffrement</td><td>34</td></tr><tr><td>1.7.2</td><td>Déchiffrement</td><td>35</td></tr></table>
## 1.1 L'organisation du document

Dans ce document nous allons traiter deux sujets distincts, mais faisant partie tous les deux du domaine de la protection de l'information.

Le premier que nous allons traiter concerne les contre-mesures pour lutter contre les attaques par canaux auxiliaires et les attaques par injection de faute qui visent les composants électroniques. Tout d'abord nous exposons l'état de l'art des différentes techniques existantes, remontrons les avantages et les limites de chacune, puis nous présentons une contre-mesure alternative basée sur les codes correcteurs.

Le deuxième sujet est relatif aux problématiques liées à la gestion des clés publiques (génération, distribution, renouvellement et révocation). Dans la partie II du document nous verrons un état de l'art des différentes solutions qui sont proposées par la communauté des cryptologues, notamment la cryptographie basée sur l'identité. Nous étudierons les points forts et les points faibles de chacune des solutions par rapport aux besoins réels dans les grandes infrastructures, et enfin nous présenterons une architecture qui répond de manière optimale à ces exigences.

## 1.2 Introduction à la cryptographie

Le développement rapide des communications par internet impacte massivement nos vies quotidiennes, et il engendre un besoin impérieux de sécurisation des informations et des technologies associées. D'où le rôle de plus en plus capital de la cryptographie. La cryptographie constitue un moyen de protection de la vie privée grâce à un ensemble de techniques bien établies et de normes pour protéger les communications contre les écoutes, la falsification, et les attaques de différents types.

La cryptographie a très longtemps été basée sur le traitement du langage, les manipulations consistaient souvent à faire des substitutions (remplacement des lettres) ou des transpositions (mélange des lettres). Depuis l'antiquité, l'une des utilisations les plus célèbres est le chiffre de CÉSAR, nommé en référence à JULES CÉSAR qui l'utilisait pour ses communications secrètes. Le chiffre de CÉSAR consiste simplement à décaler les lettres de l'alphabet. Le texte chiffré s'obtient en remplaçant chaque lettre du texte clair (le message original) par une lettre à distance fixe dans l'ordre de l'alphabet. Cette distance représente la clé de chiffrement de ce système.

Pour déchiffrer, le destinataire doit posséder la clé de déchiffrement qui est l'opposé de la clé de chiffrement. Dans le cas de l'alphabet latin, le chiffre de CÉSAR n'a que 26 clés possibles, il est donc assez facile de casser ce crypto-système.

La cryptographie moderne est fortement basée sur la théorie de l'information et les problèmes difficiles en mathématiques, tels que la factorisation des entiers, le logarithme discret, l'apprentissage en présence d'erreurs (The Learning With
*Errors* (LWE)), l'apprentissage en présence de bruit (*Learning Parity with Noise* (LPN)) ...

La sécurité des systèmes cryptographiques est donc basée sur la difficulté supposée à résoudre ces problèmes, ce qui rend ces algorithmes difficiles à briser.

<figure><img src="image_4.png" /></figure>

### 1.3 Vocabulaire

**Le chiffrement** est un procédé cryptographique qui permet de rendre la compréhension d'un message impossible à toute personne qui ne détient pas la clé de déchiffrement.

**Le déchiffrement** est l'opération inverse du chiffrement. Il permet d'extraire le message clair à partir du message chiffré (le cryptogramme) à l'aide de la clé de déchiffrement.

**Le décryptage** est l'opération qui permet d'extraire le message clair du cryptogramme sans utiliser la clé de déchiffrement. Le décryptage n'est possible que si l'adversaire est capable de trouver une faille dans le système de chiffrement utilisé.

**La cryptanalyse** est la science qui consiste à étudier et à trouver les failles potentielles dans les systèmes cryptographiques qui existent.

**La cryptologie** est la science qui combine la cryptographie et la cryptanalyse.

#### 1.3.1 La cryptographie symétrique

On dit qu'un système cryptographique est symétrique lorsque les clés de chiffrement et de déchiffrement se déduisent facilement l'une de l'autre. Les deux clés sont donc sensibles et doivent être maintenues secrètes pour garantir la sécurité. Ce mode de chiffrement à toujours été utilisé depuis l'antiquité pour des fins militaires, politiques ou personnelles. Il reste la méthode la plus simple et la plus rapide en terme de calculs. Aujourd'hui encore, avec l'évolution rapide qu'a connu la cryptographie symétrique ce dernier siècle depuis l'invention d'ENIGMA, la machine de chiffrement utilisée par les allemands durant la seconde guerre mondiale, jusqu'à
l'Advanced Encryption Standard (AES) [DR00], la cryptographie symétrique reste le moyen de chiffrement le plus sûr. Cependant, avec le développement technologique, il est impossible de faire un échange de clé pour chaque transaction (Achat sur internet, connexion sécurisée à distance ...), de plus, pour chaque utilisateur il faut sécuriser un nombre de clés équivalent au nombre de correspondants. Ces inconvénients sont devenus un handicap pour le développement des systèmes de communication dans les années quatre-vingt. Ceci a poussé la communauté des cryptologues à introduire un autre type de cryptographie appelée "cryptographie asymétrique".

## 1.3.2 La cryptographie asymétrique

En 1976, DIFFIE et HELLMAN ont marqué le début d'une nouvelle ère dans le domaine de la cryptographie avec l'invention de la cryptographie à clé publique (appelée aussi : la cryptographie asymétrique) [DH76]. Contrairement à la cryptographie symétrique, la clé de chiffrement et la clé de déchiffrement ne sont pas identiques et même, la seconde ne se déduit pas facilement de la première, de sorte que chaque utilisateur peut posséder une clé publique pour le chiffrement, et une clé secrète pour le déchiffrement. Pour la communication, l'expéditeur chiffre son message en utilisant la clé de chiffrement du destinataire (qui est publique), et envoie ensuite le cryptogramme. Le destinataire, étant donné qu'il est le seul à détenir la clé de déchiffrement, est donc le seul à pouvoir déchiffrer le cryptogramme, et en extraire le message.

La cryptographie à clé publique est préférable à la cryptographie symétrique, puisqu'elle permet de communiquer en toute sécurité sans passer par un échange préalable des clés. Chaque utilisateur peut garder secrète sa clé de déchiffrement et publier la clé de chiffrement associée. Ainsi, si *n* utilisateurs veulent communiquer de manière confidentielle via un crypto-système à clé publique, ils auront besoin de *n* couples de clés (publique/secrète), tandis que dans la cryptographie symétrique, il est nécessaire de générer $\binom{n}{2} = \frac{n(n-1)}{2}$ clés. Mais, en termes de rapidité et de complexité des calculs, les crypto-systèmes à clé publique connus aujourd'hui sont beaucoup moins efficaces que les crypto-systèmes symétriques, et ils ont également besoin de clés beaucoup plus longues pour assurer le même niveau de sécurité. C'est pourquoi la cryptographie symétrique est encore largement utilisée et étudiée de nos jours. Les crypto-systèmes à clé publique sont principalement utilisés pour assurer le partage des clés secrètes (symétriques) de manière confidentielle, et pour réaliser des signatures numériques. La figure 1.1 illustre la différence entre les deux modèles de cryptographie.

Deux ans après l'invention de la cryptographie à clé publique, le premier schéma de chiffrement a été proposé par RIVEST, SHAMIR et ADLEMAN [RSA78], ce schéma est connu jusqu'à nos jours sous le nom de RSA. Cette invention a orienté le
<figure><img src="image_5.png" /><figcaption>FIGURE 1.1 – Comparaison entre la cryptographie symétrique et asymétrique</figcaption></figure>

développement de la cryptographie en parallèle avec le développement informa-
tique pour fournir progressivement un ensemble d'outils permettant d'assurer les
principaux objectifs de la sécurité informatique :

**La confidentialité** : elle consiste à rendre l'information inintelligible à d'autres personnes que les seuls acteurs de la transaction.

**L'intégrité** : elle consiste à déterminer si les données n'ont pas été altérées durant la communication (de manière fortuite ou intentionnelle).

**La non-répudiation** : elle consiste à garantir qu'aucun des correspondants ne pourra nier la transaction.

**L'authentification** : elle consiste à garantir à chacun des correspondants que son partenaire est bien celui qu'il croit être.

KERCKHOFFS exprime dans son traité intitulé “La cryptographie militaire” que la sécurité d’un crypto-système ne doit reposer que sur le secret de la clé, et donc tous les autres paramètres peuvent être supposés publiquement connus. Ce principe est devenu une pièce essentielle pour la conception d’un crypto-système. Son importance se reflète dans le fait de permettre à de nombreux cryptanalystes de s’attaquer aux crypto-systèmes existants et ainsi en assurer la robustesse. Depuis le commencement de la cryptographie à clé publique, la recherche sur ce sujet n’a pas cessé de proposer de nouveaux systèmes et d’affaiblir ou renforcer
les existants. Cryptographes et cryptanalystes s'affrontent afin de concevoir et d'évaluer des systèmes à la fois rapides et fiables.

## Exemple 1 (RSA)

Soient $p$, et $q$ deux grands nombres premiers distincts (de longueur supérieur à 2048 bits par exemple), et $n = pq$. On note $\varphi(n) = (p - 1)(q - 1)$ l'indicateur d'Euler.

- La clé secrète est constituée de $p, q$, et d'un entier $d$ premier avec $\varphi(n)$.

- La clé publique est constituée de $n$, et d'un entier $e$ premier avec $\varphi(n)$ tel que : $ed = 1 \pmod{\varphi(n)}$.

- L'opération de chiffrement est définie par : $x \mapsto x^e \pmod{n}$.

- L'opération de déchiffrement est définie par : $x \mapsto x^d \pmod{n}$.

■

Bien qu'on ne sache pas encore le démontrer, la seule attaque générale connue actuellement contre RSA reste la factorisation de $n$. Cependant, certains choix malheureux des paramètres ou une mauvaise implémentation peuvent compromettre la sécurité. Selon les dernières recommandations de sécurité relatives au Transport Layer Security (TLS) publié par l' ANSSI<fnref n="1" /> [ANS16], d'ici 2030, les clés RSA doivent avoir une taille minimale de 2048 bits, et les clés ECDSA (Elliptic Curve Digital Signature Algorithm) doivent avoir une taille minimale de 256 bits. Les cryptosystèmes basés sur la théorie des nombres, tel que RSA, ne permettent malheureusement pas d'identifier le propriétaire d'une clé publique. Il a fallu donc trouver une solution qui permettra de créer ce lien entre la clé publique et l'identité de son possesseur dans le but de se protéger contre l'usurpation de l'identité. Pour répondre à ce besoin, SHAMIR en 1984 a introduit le concept de la cryptographie basée sur l'identité [Sha84] connu aussi sous le nom d'IBE (Identity Based Encryption). Dans ce type de crypto-systèmes la clé publique est remplacée par une chaîne quelconque de caractères (un identifiant, une adresse mail, un numéro de téléphone ...). La clé secrète est extraite grâce à une autorité de confiance à partir de la clé publique, et par conséquent, protège en plus contre l'usurpation d'identité.

Depuis que la notion d'IBE a été posée en 1984, plusieurs propositions de schémas IBE ont été proposées [DQ86, HJW00, MY91, TI89, Tan87]. Cependant, aucune de celles-ci n'est pleinement satisfaisante. En attendant de construire ce cryptosystème, une autre solution a déjà été mise en œuvre, c'est ce qu'on appelle la cryptographie basée sur les certificats, aussi connue sous le nom de la PKI (Public Key Infrastructure). Il s'agit d'un ensemble de procédures qui combinent le chiffrement, le hachage et la signature numérique afin de garantir la confidentialité,

<footnote n="1">1. Agence Nationale de la Sécurité des Systèmes d'Information</footnote>
l'intégrité, la non-répudiation et l'authentification.

1.3.3 La théorie de la complexité

La théorie de la complexité est un domaine central dans la théorie de l'information. Elle s'intéresse à l'étude de la complexité intrinsèque des tâches de calcul.
La complexité algorithmique est une fonction qui exprime la consommation d'un programme en espace mémoire et/ou en temps de calcul durant son exécution en fonction de la taille des valeurs en entrée, ceci permet d'évaluer et comparer la performance des algorithmes. On dit qu'un algorithme est rapide si sa complexité algorithmique s'exprime par une fonction polynomiale (linaire, quadratique, cubique ...) ou logarithmique de la taille des entrées. D'autre part, un algorithme est lent si sa complexité est exponentielle.

**Définition 1** (La machine de TURING)

Une machine de TURING est un modèle mathématique de calcul inventé en 1936
par ALAN TURING. Ce modèle définit une machine abstraite qui manipule des
symboles appartenant à un alphabet Γ sur une bande (mémoire) selon un tableau
de règles Q (les états). La mémoire est un ruban infini de cases qui contiennent
chacune un élément de l'alphabet, la première case de ce ruban comporte un sym-
bole unique *d* qui désigne le début de la mémoire, et la tête de lecture pointe
toujours sur cette case au début du programme. Le tableau de règles comporte
toujours un état initial (*e*<sub>i</sub>) qui s'exécute en premier, un état final *e*<sub>f</sub> qui arrête le
programme, et des états intermédiaires qui dépendent de la machine. Chaque état
permet d'exécuter des actions comme : déplacer la tête de lecture à droite (D) ou
à gauche (G), écrire un symbole sur la case sélectionnée, ou bien effacer le contenu
de la case.

Exemple 2

Soit $M = (\Gamma, Q)$ la machine de TURING qui permet de calculer le successeur d'un entier dans une représentation binaire. $M$ est définie par :

— L'alphabet binaire $\Gamma = \{0,1\}$;

— L'ensemble des états $Q = \{e_i, e_1, e_2, e_3, e_f\}$ tels que :

— $e_i$: l'état initial qui pointe sur le premier caractère de la mémoire, et qui parcoure tout le ruban (vers la droite D) jusqu'à trouver la première case vide “_”, ensuite passe à l'état $e_1$.

— $e_1$: la tête de lecture pointe sur le dernier chiffre du mot sur le ruban, s'il s'agit de 0 il le remplace par 1 et il passe à l'état final $e_f$, sinon il remplace le 1 par 0 et déplace la tête de lecture vers la gauche. L'état continue à chercher le dernier 0 du mot pour le remplacer par 1 et passer à l'état final. Si le mot n'est composé que de 1, alors l'état passe à $e_2$.
# CHAPITRE 1. INTRODUCTION GÉNÉRALE

- $e_2$: Le mot maintenant n'est composé que des 0, cet état permet de remplacer le premier caractère du mot par 1, et passer ensuite à l'état $e_3$.

- $e_3$: Enfin l'état $e_3$ permet d'ajouter le caractère 0 à la fin du mot, et passer ensuite à l'état finale.

Soit $n$ le mot stocké sur le ruban, pour calculer $n + 1$ par la machine de TURING $M$ nous distinguons trois cas possibles :

<table><thead><tr><th></th><th>Le cas facile</th><th>la cas intermédiaire</th><th>Le pire des cas</th></tr><tr><th></th><th>$n$ est pair</th><th>$n$ est impair</th><th>$n$ est composé que de 1</th></tr></thead><tbody><tr><th>$n$ =</th><td>11010</td><td>10111</td><td>11111</td></tr><tr><th>$e_i$</th><td><span style="color:blue;">d</span>11010</td><td><span style="color:blue;">d</span>10111</td><td><span style="color:blue;">d</span>11111</td></tr><tr><th>$e_1$</th><td><span style="color:blue;">d</span>11010</td><td><span style="color:blue;">d</span>10110</td><td><span style="color:blue;">d</span>11111</td></tr><tr><th>$e_2$</th><td>-</td><td>-</td><td><span style="color:blue;">d</span>00000</td></tr><tr><th>$e_3$</th><td>-</td><td>-</td><td><span style="color:blue;">d</span>10000</td></tr><tr><th>$e_f$</th><td><span style="color:blue;">d</span>11011</td><td><span style="color:blue;">d</span>11000</td><td><span style="color:blue;">d</span>100000</td></tr></tbody></table>

Dans le pire des cas, la tête de lecture pour cette machine parcoure le ruban $3log_2(n)$ fois, ce qui signifie que la complexité de cet algorithme est logarithmique.

<figure><img src="image_6.png" /><figcaption>FIGURE 1.2 – Une machine de TURING pour calculer le successeur d'un entier</figcaption></figure>

Malgré la simplicité du modèle, il est possible pour n'importe quel algorithme de construire une machine de TURING (MdT) capable de le simuler. Elle est particu-
lièrement utile en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité.

Nous distinguons deux familles de MdT :

— La MdT déterministe (MdTD) : il s'agit du modèle classique où chaque fonction de transition $f : \Gamma \times Q \to \Gamma \times Q \times \{D, G, X\}$ associe un seul triplet $(e', s', h) \in \Gamma \times Q \times \{D, G, X\}$ à tout couple $(e, s) \in \Gamma \times Q$ où $e$ désigne l'état courant de la MdTD et $s$ le symbole lu dans la case courante de la bande.

— La MdT non-déterministe (MdTND) : Dans ce modèle, la fonction de transition $f$ peut associer plusieurs triplets $(e', s', h)$ au même couple $(e, s)$. Plus formellement la fonction de transition d'une MdTND est définie par : $f : \Gamma \times Q \to 2^{\Gamma \times Q \times \{D,G,X\}}$.

Il est toujours possible de construire un algorithme pour résoudre n'importe quel problème mathématique, cependant, il est difficile de déterminer s'il existe des algorithmes polynomiaux pour tous les problèmes existants. En effet, à ce jour, il existe des problèmes que nous ne savons pas encore résoudre en temps polynomial comme les problèmes de factorisation et du logarithme discret.

**Définition 2 (le problème de factorisation)**

Soit $n$ un nombre composé, et $p_1, \dots, p_u$ les facteurs premiers de $n$ (i.e. $n = \prod_{i=1}^u p_i^{a_i}$ avec $a_i \ge 1$). Le problème de factorisation consiste à trouver l'ensemble $\{p_1, \dots, p_u\}$ étant donné $n$.

**Définition 3 (le problème du logarithme discret)**

Soit $G$ un groupe cyclique engendré par $g$ d'ordre $n$ :

$$G = \{1, g, g^2, \dots, g^{n-1}\}.$$

Étant donné $y \in G$, le problème du logarithme discret consiste à trouver un entier $0 \le u \le n-1$ tel que :

$$y = g^u.$$

Il existe deux façons de voir un problème :

— Problème de décision : il s'agit d'un problème dont la réponse est binaire (oui ou non), comme par exemple le test de primalité qui consiste à décider si un entier est premier ou pas.

— Problème de calcul : il s'agit de déterminer l'existence de la solution et de la trouver.

En d'autres termes, les problèmes de décision permettent de tester les solutions cherchées par les problèmes de calculs, par exemple, si nous posons le problème de calcul qui consiste à retrouver les facteurs premiers d'un entier $n$ (le problème de factorisation), un problème de décision associé consiste à tester si un nombre premier $p$ est facteur de $n$.
Étant donné qu'il existe toujours des problèmes que nous savons pas résoudre en temps polynomial, et que nous avons aucune preuve sur l'existence d'une telle solution. les spécialistes en théorie de la complexité ont classé les problèmes mathématiques en 3 classes fondamentales :

- La classe P : L'ensemble des problèmes de décision qui admettent un algorithme de résolution en temps polynomial.

- La classe NP : classe des problèmes où les solutions des problèmes de décision peuvent être vérifiées en temps polynomial par une MdTND.

- La classe NP complet (NPC) : un problème est NPC s'il est NP, et en plus, il existe une réduction polynomiale de tous les problèmes NP vers celui-ci. Cela implique que le problème NPC est au moins aussi difficile que tous les autres problèmes de la classe NP.

<figure><img src="image_7.png" /><figcaption>FIGURE 1.3 – Le rôle des MdT pour classifier les problèmes mathématiques</figcaption></figure>

## 1.3.4 Les fonctions de hachage

### Définition 4 (Fonction à sens unique)

Une fonction à sens unique est une fonction qui peut être aisément calculée, mais qui est difficile à inverser.

Une fonction de hachage est une fonction à sens unique qui permet de calculer une empreinte de longueur fixe à partir d'une donnée de taille quelconque fournie en entrée, cette empreinte peut ensuite servir à identifier rapidement la donnée initiale.

$$ \mathcal{H} : \{0,1\}^* \to \{0,1\}^k . $$
Les fonctions de hachage ont une importance majeure en informatique, et particulièrement dans le domaine de la sécurité. Par exemple, pour éviter de stocker en clair les mots de passe sur une machine pour des raisons de sécurité, les systèmes d'exploitation stockent uniquement l'empreinte du mot de passe, ainsi, il suffit de comparer l'empreinte stockée avec celle du mot de passe demandé. Une autre utilisation importante des fonctions de hachage est la signature numérique.

Il existe une grande variété de fonctions de hachage : *Secure Hash Algorithm* (SHA), *Message Digest* (MD), *The Elliptic Curve Only Hash* (ECOH), HAVAL, Tiger... La famille SHA a été conçue par la NSA<fnref n="2" /> et publiée par NIST<fnref n="3" /> pour être utilisée avec la signature numérique standard *Digital Signature Standard* (DSS). Il existe une similitude entre la famille SHA et la famille MD. Cependant, la famille SHA est composée de fonctions mathématiques supplémentaires et produit une empreinte de 160 bits au lieu de 128 bits, ce qui la rend plus résistante face aux attaques à force brute, y compris les attaques basées sur le paradoxe des anniversaires qui consiste à chercher des collisions.

### Définition 5 (Le paradoxe des anniversaires)

Le paradoxe des anniversaires concerne la probabilité que, dans un ensemble de $n$ personnes choisies au hasard, une paire d'entre eux ait le même anniversaire. La probabilité n'atteint 100% que lorsque le nombre de personnes atteint 367 (puisqu'il n'y a que 366 anniversaires possibles, y compris le 29 février). Cependant, la probabilité de 99,9% est atteinte avec seulement 70 personnes, et 50% de probabilité avec 23 personnes.

Bien entendu, il ne s'agit pas d'un paradoxe dans le sens d'une contradiction logique, mais parce qu'il s'agit d'une vérité mathématique qui contredit l'intuition. En effet, intuitivement, la probabilité pour 23 personnes est très inférieure à 50%.

### Définition 6 (Fonction de hachage)

Une fonction de hachage $\mathcal{H}$ est dite résistante aux collisions s'il est difficile de trouver deux entrées qui hachent la même sortie ; c'est-à-dire qu'il est difficile de trouver deux entrées $x$ et $y$ telles que $\mathcal{H}(x) = \mathcal{H}(y)$ avec $a \neq b$.

### 1.3.5 La signature numérique

La signature numérique est une des applications de la cryptographie à clé publique, il s'agit de la transposition dans le monde numérique de la signature manuscrite. Elle permet de garantir l'identité du signataire, l'intégrité et la provenance du document signé. Pour signer un document ou un message $m$, il est possible (pour

<footnote n="2">2. National Security Agency</footnote>

<footnote n="3">3. National Institute of Standards and Technology</footnote>
# CHAPITRE 1. INTRODUCTION GÉNÉRALE

certain algorithmes comme RSA) de chiffrer l'empreinte de ce message $\mathcal{H}(m)$ avec la clé secrète du signataire SK.

$$ \text{Sign}(m) = \text{Enc}(\mathcal{H}(m), \text{SK}). $$

Ainsi, pour vérifier la signature, il suffit de déchiffrer la signature du message avec la clé publique du signataire et tester si elle est identique à l'empreinte du message :

$$ \mathcal{H}(m) \stackrel{?}{=} \text{Dec}(\text{Sign}(m), \text{PK}). $$

<table><caption>TABLE 1.1 – Les fonctionnalités des différents algorithmes cryptographiques</caption><thead><tr><th>Type d'algorithme</th><th>Chiffrement</th><th>Signature</th><th>Hachage</th><th>Échange de clés</th></tr></thead><tbody><tr><td colspan="5" style="text-align: center; font-weight: bold;">La cryptographie asymétrique</td></tr><tr><td>RSA</td><td>✓</td><td>✓</td><td>-</td><td>✓</td></tr><tr><td>ECC</td><td>✓</td><td>✓</td><td>-</td><td>✓</td></tr><tr><td>Diffie-Hellman</td><td>-</td><td>-</td><td>-</td><td>✓</td></tr><tr><td>El Gamal</td><td>✓</td><td>✓</td><td>-</td><td>✓</td></tr><tr><td>DSA</td><td>-</td><td>✓</td><td>-</td><td>-</td></tr><tr><td colspan="5" style="text-align: center; font-weight: bold;">La cryptographie symétrique</td></tr><tr><td>AES</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>3DES</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Blowfish</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>IDEA</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>RC4</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td>SAFER</td><td>✓</td><td>-</td><td>-</td><td>-</td></tr><tr><td colspan="5" style="text-align: center; font-weight: bold;">Les fonctions de hachage</td></tr><tr><td>MD2, MD4, MD5</td><td>-</td><td>-</td><td>✓</td><td>-</td></tr><tr><td>sha1, sha224, sha256, ...</td><td>-</td><td>-</td><td>✓</td><td>-</td></tr><tr><td>HAVAL</td><td>-</td><td>-</td><td>✓</td><td>-</td></tr><tr><td>Tiger</td><td>-</td><td>-</td><td>✓</td><td>-</td></tr></tbody></table>

Une signature numérique qui possède une validité juridique au niveau Européen permet les fonctionnalités suivantes :

**Caractère unique** : Chaque document, dossier ou transaction est signé(e) avec une signature unique, et donc non réutilisable.

**Intégrité** : La signature ne peut être ni modifiée ni altérée. Toute tentative de modification sera automatiquement détectée.
**Incontestable** : La signature ne doit pouvoir être réalisée que par la personne possédant le certificat correspondant.

**Vérification** : L'identité du signataire doit être confirmée par une autorité de confiance.

Il faut bien noter que ces garanties sont assurées sous l'hypothèse que le problème mathématique utilisé (par exemple la factorisation pour le cas de RSA) est un problème difficile. Donc, d'un point de vue théorique ; il existe toujours une probabilité très négligeable de reproduire une fausse signature.

La fonction de hachage garantit l'intégrité du message, la signature de l'empreinte fournit l'authentification et la non-répudiation, et le chiffrement permet d'assurer la confidentialité.

Dans le tableau 1.1 nous avons listé quelques algorithmes cryptographiques connus.

## 1.4 L'infrastructure à clé publique

### 1.4.1 Le protocole de Diffie-Hellman

Le protocole de Diffie-Hellman (DH) du nom de ses auteurs DIFFIE et HELLMAN [DH76] est une méthode d'échange sécurisée de clés cryptographiques sur un canal public. La sécurité de cette méthode est basée sur le problème du logarithme discret (voir la définition 3 page 9).

L'implémentation la plus simple (qui est celle d'origine) de ce protocole utilise le groupe multiplicatif d'entiers modulo $p$, où $p$ est premier, et $g$ est une racine primitive modulo $p$ (un générateur). Cela permet que le secret partagé qui en résulte ait une distribution uniforme sur l'intervalle $1 à p - 1$.

Le processus commence quand deux parties (Alice et Bob par exemple), s'accordent sur les paramètres publics $p$ et $g$, ensuite :

- Alice choisit un nombre secret $a$, et calcule la valeur publique : $g^a$;

- Bob choisit également un nombre secret $b$, et calcule la valeur publique : $g^b$;

- Alice et Bob échangent leurs valeurs publiques $g^a$ et $g^b$;

- Alice calcule : $g^{ab} = (g^b)^a$.

- Bob calcule : $g^{ab} = (g^a)^b$.

Ainsi, la clé partagée devient : $g^{ab}$ que seuls, Alice et Bob semblent capables de construire.

### 1.4.2 L'attaque de l'homme au milieu

"Man-In-The-Middle" (MITM) qu'on peut traduire en français par *l'homme au milieu* est une attaque basée sur l'usurpation d'identité, et qui vise les protocoles
<figure><img src="image_8.png" /><figcaption>FIGURE 1.4 – Diffie-Hellman</figcaption></figure>

d'échange de clés. L'attaquant s'introduit discrètement au milieu d'une communication entre deux parties qui croient communiquer directement entre elles. Il établit ensuite des connexions indépendantes avec les victimes et relaie les messages entre eux pour leur faire croire qu'ils parlent directement les uns aux autres sur une connexion privée, alors qu'en réalité toute la conversation est contrôlée par l'attaquant.

<figure><img src="image_9.png" /><figcaption>FIGURE 1.5 – L'attaque de l'homme du milieu</figcaption></figure>

Pour le protocole DH (Figure 1.5), l'attaquant (Charlie) intervient au moment de l'échange de clé entre Alice et Bob, il fait croire à Alice que c'est lui Bob, et lui envoie sa clé publique *C* au lieu de *B*, de la même façon, il fait croire à Bob que c'est lui Alice et lui envoie sa clé publique *C* au lieu de *A*. A la fin, l'attaquant Charlie possède deux clés privées *K* et *K'* qui lui permettront de déchiffrer toutes les communications entre Alice et Bob. Pour rester transparent, Charlie doit déchiffrer tous les messages d'une des victimes et les rechiffrer par la clé du destinataire.
La méthode la plus simple pour résoudre ce problème d’usurpation d’identité consiste à faire signer toutes les clés par une autorité de confiance. Le document obtenu par ce procédé s’appelle alors *un certificat*.

1.4.3 Le principe des certificats

La cryptographie à clé publique représente une avancée remarquable dans l'histoire
de la cryptographie. Elle permet aux utilisateurs d'échanger un secret sans être en
contact direct. Cependant, un problème se présente, il s'agit de l'authenticité des
clés publiques. En effet, la clé publique ne porte aucune information sur l'identité
de son possesseur. Les utilisateurs doivent alors s'assurer de l'authenticité des clés
publiques pour lutter contre l'usurpation d'identité.

L'infrastructure de gestion de clés (IGC), aussi connue sous le nom de PKI : *Public Key Infrastructure*, se compose de programmes, de formats de données, de procédures, de protocoles de communication, de politiques de sécurité et de mécanismes cryptographiques à clé publique fonctionnant de manière globale afin de permettre à un large éventail de personnes dispersées de communiquer de manière sécurisée et normalisée. En d'autres termes, une PKI établit un niveau de confiance dans un environnement. La PKI est un cadre d'authentification ISO<fnref n="4" /> qui utilise la cryptographie à clé publique et la norme X.509. Le cadre a été configuré pour permettre l'authentification sur différents réseaux privés ou publics. Les protocoles et les algorithmes particuliers ne sont pas spécifiés, c'est pourquoi la PKI est considérée comme un cadre et non une technologie spécifique.

La PKI fournit l'authentification, la confidentialité, la non-répudiation et l'intégrité
des messages échangés. C'est un système hybride d'algorithmes de chiffrement
symétriques et asymétriques, qui ont été discutés dans des sections antérieures.
Il existe une différence entre la cryptographie à clé publique et la PKI. La cryptographie à clé publique est un type d'algorithme de chiffrement, tandis que la PKI comme son nom l'indique est une infrastructure. L'infrastructure suppose que l'identité du récepteur peut être assurée facilement par des certificats et qu'un algorithme asymétrique effectuera automatiquement le processus d'échange de clés.
L'infrastructure contient de ce fait les éléments qui identifieront les utilisateurs, créeront et distribueront des certificats, les maintiendront et révoqueront des certificats, distribueront et maintiendront des clés de chiffrement et permettront à toutes les technologies de communiquer et de travailler ensemble dans un environnement sécurisé.

Un certificat électronique est un document numérique permettant de valider le lien
entre une clé publique et son propriétaire. Il contient principalement les éléments
suivant :

<footnote n="4">4. International Organization for Standardization</footnote>
- Une clé publique;

- L'identité du dépositaire de la clé secrète associée à cette clé publique;

- Une plage de validité du certificat : date de début - date de fin;

- L'identité de l'autorité de certification (CA);

- Une description de l'algorithme de chiffrement compatible avec la clé publique, ainsi que la longueur des clés;

- Une description de l'algorithme de signature utilisé pour signer ce certificat;

- Une description de la fonction de hachage utilisée pour la signature;

- La signature électronique des informations précédentes par l'autorité de certification (CA).

Un certificat électronique doit respecter un format standard appelé " la norme X.509 ". Cette norme a été définie par l'union internationale des télécommunica-
tions (UIT) en 1988 pour s'adapter aux différents protocoles informatiques (TLS,
S/MIME, SET, IPsec, ...).

1.4.4 Le fonctionnement de l'infrastructure de gestion de clés (PKI)

Plusieurs autorités de rôles différents s'occupent de la gestion des certificats dans
une PKI :

- *Registration Authority (RA)* : L'autorité d'enregistrement qui authentifie les entités et génère le couple (clé secrète, clé publique) durant la phase d'enrôlement.

— *Certification Authority (CA)* : L'autorité de certification, qui signe les demandes des certificats et les listes des révocations.

— *Directory Service (DS)* : Le service d'annuaire utilise la norme LDAP (*Light-weight Directory Access Protocol*) pour stocker de manière sécurisée tous les certificats, et les fournir aux utilisateurs (exemple : *Active directory* de Microsoft).

— *Revocation Service (RS)* : Le service de révocation qui gère la liste des certificats révoqués CRL (Certificate Revocation List).

Pour bien administrer la génération et la distribution des clés par ces différentes
autorités, il faut respecter un protocole précis. Il existe trois phases importantes
dans ce protocole :

1. La phase d'enrôlement : Cette phase décrit comment générer un certifi-
cat d'utilisateur. Pour ce faire, ce dernier s'authentifie auprès de l'autorité
d'enregistrement (RA). Il s'agit souvent d'un officier de sécurité qui assure le
bon fonctionnement du système. Si l'autorité décide de valider cette requête,
elle génère un couple de clés secrète et publique au format "CSR" (Certificate
Signing Request ) pour l'utilisateur <fnref n="5" />. Elle les envoie ensuite à l'utilisateur en question via un canal privé. L'utilisateur à son tour envoie sa requête (la clé publique), à l'autorité de certification (CA) pour la signer. Enfin, la CA génère un certificat associé à la clé publique, et l'identité de son possesseur. Une copie de ce certificat est ensuite placée dans la base de données du système qui est gérée par le service d'annuaire (DS), pour qu'elle puisse être accessible aux autres utilisateurs.

<figure><img src="image_10.png" /><figcaption>FIGURE 1.6 – La phase d'enrôlement dans une PKI</figcaption></figure>

2. **La phase de communication** : Cette phase décrit le protocole à respecter pour une communication sécurisée entre deux utilisateurs. On prend l'exemple d'Alice et Bob qui essaient de communiquer, Alice représente l'émetteur, et Bob le récepteur. Alice commencera d'abord par récupérer le certificat de Bob (Bob-cert) au près du DS. Elle devra ensuite vérifier les éléments suivants :

— l'identité qui figure sur le certificat est-elle effectivement celle du récepteur, en l'occurrence Bob;

— la signature de la CA figurante sur le certificat;

— la non-expiration du certificat;

— l'absence de révocation du certificat auprès de la CRL.

Une fois tous ces tests satisfaits, Alice pourra envoyer son message chiffré avec la clé qui figure sur le certificat.

3. **La phase de révocation** : La phase de révocation est une pièce indispensable dans un système de gestion de clés. C'est le seul moyen d'exclure un utilisateur qui possède déjà un certificat valide. Pour révoquer un certificat, le plus simple est de générer une liste des certificats révoqués (CRL), ce fishier au format PEM (*Privacy Enhanced Mail*) est signé par la suite par la

<footnote n="5">5. Idéalement, c'est l'utilisateur qui est censé générer ses propre clés, mais souvent, en pratique c'est la RA qui s'en charge pour des raisons de sécurité, telle que la sauvegarde des clés, et l'assurance de leurs niveau de résistance face aux différentes attaques.</footnote>
<figure><img src="image_11.png" /><figcaption>FIGURE 1.7 – La phase communication dans une PKI</figcaption></figure>

CA pour éviter toute falsification. Enfin, la CRL est publiée sur le réseau pour la rendre accessible à tous les utilisateurs. Il est possible que les utilisateurs s'informent en quasi temps réel de l'état du certificat avec le protocole OCSP<fnref n="6" />. Il est également primordial de mettre à jour la CRL de manière périodique pour que les utilisateurs puissent se synchroniser.

Il existe plusieurs logiciels libres pour implémenter une PKI tels que EJBCA, OpenCA, OpenXPKI... la plupart de ces logiciels sont basés sur des bibliothèques cryptographiques libres comme OpenSSL ou GnuPG.

## 1.5 Le chiffrement basé sur l'identité (IBE)

### 1.5.1 Le principe général

En 1984, dans [Sha84] SHAMIR a introduit un type de chiffrement asymétrique dans lequel la clé publique pourrait être une chaîne librement choisie. Ce type de cryptographie s'appelle “ La cryptographie basée sur l'identité ” et elle est connue sous le nom de Identity Based Encryption (IBE). Dans un tel schéma, il existe quatre algorithmes :

1. **Configuration** : génère les paramètres globaux du système et une clé maître;

2. **Extraction** : utilise la clé maître pour générer la clé privée associée à une chaîne de caractère;

3. **Chiffrement** : chiffre les messages à l'aide de l'identité du destinataire;

4. **Déchiffrement** : déchiffre les messages à l'aide de la clé privée correspondante.

<footnote n="6">6. Online Certificate Status Protocol</footnote>
La principale innovation de ce schéma est l'utilisation de l'identité de l'utilisateur (adresse mail, Numéro de téléphone, identifiant...) en tant que clé publique pour le chiffrement et la vérification de signature. Ceci réduit considérablement la complexité de la gestion des clés. En effet, dans un tel schéma, contrairement au cas de la PKI, il n'est nul besoin de créer ni de gérer les certificats. De plus, une seule autorité est nécessaire pour gérer le système. Cette autorité s'appelle *Private Key Generator (PKG)*. Elle sert comme son nom l'indique à générer (extraire) la clé secrète de l'utilisateur à partir de son identité grâce à la clé maître.

Après que le problème a été posé en 1984, il y a eu plusieurs propositions pour les schémas IBE [DQ86, HJW00, MY91, TI89, Tan87]. Mais jusqu'aux résultats de BONEH et FRANKLIN [BF01], aucune de ces propositions n'était totalement satisfaisante. Certaines solutions exigeaient que les utilisateurs ne se connaissent pas. D'autres solutions exigeaient que le PKG passe beaucoup de temps pour chaque demande de génération de clé privée. Certaines solutions nécessitaient un matériel anti-effraction. La figure 1.8 résume l'architecture d'IBE pour la phase d'enrôlement (a, b) et la phase de communication (1, 2, 3, 4).

<figure><img src="image_12.png" /><figcaption>FIGURE 1.8 – La distribution des clés dans un schéma IBE</figcaption></figure>

La mise en œuvre de l'IBE de BONEH et FRANKLIN repose sur un groupe bilinéaire composé des points d'une courbe elliptique et d'une fonction bilinéaire correspondante pour effectuer les calculs nécessaires. Dans la partie II, nous allons étudier de manière détaillée ces outils. Nous étudierons les améliorations proposées au fur et à mesure par la communauté durant ces dernières années. Nous proposerons enfin l'architecture, qui, selon nous, répond aux exigences du monde industriel notamment celles des infrastructures critiques telles que les “smart grid” [ABB+15].
## 1.5.2 Les exigences d'un système de gestion de clé

Un système de gestion de clé doit effectuer plusieurs tâches. Dans un environnement d'entreprise par exemple, qu'il s'agisse de protéger les e-mails, les bases de données ou les documents. Nous avons regroupé les critères nécessaires pour un système efficace en six exigences :

1. **Fournir des clés de chiffrement.** Les utilisateurs et les applications doivent pouvoir chiffrer les données pour tous les destinataires. Si un utilisateur ne peut pas accéder facilement à la clé publique d'une grande variété de destinataires internes, groupes d'annuaires, clients ou partenaires, il se peut qu'il lui soit impossible de chiffrer ces données. Dans ce cas si un utilisateur ne peut pas facilement chiffrer les données, le processus métier<fnref n="7" /> cessera de fonctionner ou, pire, l'utilisateur stockera en clair les données sur des supports non protégés.

2. **Authentifier les utilisateurs et livrer les clés de déchiffrement.** Un système de gestion des clés doit pouvoir à la fois authentifier et fournir des clés aux groupes et aux utilisateurs. Le système d'authentification doit s'intégrer à l'infrastructure existante, sinon les coûts d'infrastructure, et d'authentification des utilisateurs seront doublés.

3. **Gérer conjointement les clés avec les partenaires.** Dans de nombreux cas, il est souhaitable d'échanger des données chiffrées avec des partenaires, dans lesquels chaque partenaire gère uniquement les clés pour ses propres utilisateurs. De cette façon, un message de la société A peut s'adresser aux destinataires de la société B sans exiger que la société A connaisse comment authentifier les utilisateurs de la société B. La société B peut donc gérer sa propre infrastructure d'authentification et de gestion des messages sans avoir besoin de coordonner avec la société A.

4. **Fournir des clés aux composants d'infrastructure de confiance.** Lors du chiffrement du courrier ou des fichiers dans une entreprise, les processus métiers et techniques intermédiaires, tels que l'audit, la numérisation de contenu ou les antivirus, peuvent nécessiter l'accès au contenu des données chiffrées. Le système de gestion des clés doit être capable de fournir des clés sur ces composants.

5. **Récupérer les clés.** Dans le cas d'un utilisateur révoqué ou quittant l'organisation, un administrateur doit pouvoir accéder aux données chiffrées. Les récentes règles concernant le "*e-discovery*"<fnref n="8" /> ont fait de cette exigence une

<footnote n="7">7. Un processus métier est une collection d'activités ou de tâches structurées ou liées qui produisent un service ou un produit spécifique (servir un objectif particulier) pour un client.</footnote>

<footnote n="8">8. La procédure *e-discovery* incite les entreprises à archiver automatiquement tous les documents et communications électroniques dans le cadre de la recherche de preuves pouvant être</footnote>
importance primordiale. Si un système de gestion de clés laisse un élément de données dans un état où il ne peut pas être déchiffré, cela peut représenter une responsabilité légale importante et une perturbation des processus métiers.

6. Étendre le réseau. Les entreprises prospères sont amenées à grandir, et parfois elles le font très rapidement. Un système de gestion de clé efficace doit tenir compte d'un volume de transaction croissant et être déployable dans des locaux géographiquement dispersés. Les entreprises doivent envisager comment la gestion des clés fonctionnera si, et quand, elles rencontreront 10 ou même 1000 fois le volume de transactions qu'elles traitent actuellement.

### 1.5.3 Comparaison entre PKI et IBE

Pour comparer deux architectures de gestion de clés publiques telles que la PKI et IBE, nous allons d'abord étudier la compatibilité entre ces systèmes et la liste des six exigences listées auparavant.

#### 1.5.3.1 La PKI

1. Les systèmes à clé publique ont un problème inhérent relatif à la localisation d'une clé publique d'un utilisateur spécifique. Les utilisateurs des systèmes basés sur des certificats sont souvent confrontés au fait qu'ils ne peuvent pas trouver un certificat pour un utilisateur spécifique. Ce qui rend la communication sécurisée impossible. Les groupes présentent un problème similaire, car la mise en œuvre des certificats pour les groupes nécessite un système de distribution de clés privées et le schéma d'authentification des certificats doit permettre de transférer les utilisateurs à l'intérieur et à l'extérieur des groupes.

2. En général, l'authentification des utilisateurs dans un système basé sur les certificats doit se produire avant que l'utilisateur puisse recevoir un message. Cela signifie qu'il doit y avoir une étape d'inscription (enrôlement) qui se déroule avant que les données puissent être chiffrées. Dans le cas d'un utilisateur provisoire il peut s'agir d'un défaut insurmontable. En supposant que cette étape soit surmontée, le destinataire peut déchiffrer les données tant que la clé privée correspondante est disponible.

3. Les communications entre partenaires peuvent être effectuées dans un système de chiffrement à clé publique, mais un répertoire partagé doit être mis en place.

<footnote>utilisées dans un procès civil ou commercial.</footnote>
4. Pour fournir des clés à un système d'archivage intermédiaire, un système de partage de clé privée doit être déployé.

5. Les clés peuvent être récupérées si une base de données de clé privée est maintenue, par exemple un HSM<fnref n="9" />. Si cette base de données est compromise ou endommagée, les clés peuvent devenir irrécupérables. Les clients peuvent être programmés pour chiffrer des données vers un intermédiaire de confiance, ce qui permet de récupérer les messages via cet intermédiaire.

6. Théoriquement, les systèmes à clé publique peuvent s'adapter en fonction de la taille du réseau. Cependant, l'expérience avec les grands déploiements a montré que les problèmes d'interface utilisateur concernant la gestion et la révocation des certificats et des clés rendent l'utilisation à grande échelle de la PKI très coûteuse.

### 1.5.3.2 IBE

1. En utilisant IBE, les clés sont toujours disponibles pour tous les destinataires. La clé de chiffrement est dérivée simplement de l'identité du récepteur. Les groupes sont traités aussi facilement, car une clé peut être faite à partir d'un nom de groupe aussi facilement qu'un nom individuel.

2. IBE s'interface avec les infrastructures d'authentification existantes, de sorte que toutes les ressources d'authentification déjà déployées (par exemple, les répertoires ou l'authentification web) peuvent être réutilisées. L'expérience client pour obtenir une clé de déchiffrement peut être identique à la connexion à un portail, par exemple. Nous allons voir dans la partie II que nous pouvons améliorer l'IBE de BONEH et FRANKLIN pour pouvoir distribuer les clés secrètes sur un canal public en utilisant le masquage.

3. IBE permet à l'expéditeur de sélectionner un serveur de clé local, un serveur de clé d'un partenaire ou un service pour protéger les données, en fonction de ses besoins particuliers.

4. Parce qu'IBE génère mathématiquement toutes les clés de déchiffrement sur le serveur (PKG), le serveur peut régénérer de manière sécurisée les clés des composants d'infrastructure au besoin.

5. Dans un système basé sur IBE, toutes les clés sont générées à partir de la clé maître stockée sur le serveur de clé. Tant qu'elle est récupérable, toute clé peut être régénérée de manière sécurisée.

<footnote n="9">9. *Hardware Security Module* : Il s'agit d'un dispositif informatique physique qui protège et gère les clés cryptographiques pour une authentification forte. Ces modules se présentent généralement sous la forme d'une carte à puce ou d'un périphérique externe qui se connecte directement à un ordinateur ou à un serveur réseau.</footnote>
6. IBE permet d'ajouter des applications et des transactions supplémentaires avec très peu ou pas d'infrastructure de gestion de clé supplémentaire. Les serveurs de clés peuvent fonctionner indépendamment, ce qui autorise une dispersion géographique et un bon équilibrage de charges.

1.5.4 Conclusion

Les approches traditionnelles de la gestion des clés, y compris la gestion des clés symétriques et, plus récemment, la PKI, n'ont pas été convaincantes au regard des exigences d'un système de gestion de clé. De plus, elles sont difficiles à utiliser, à mettre en œuvre et à gérer, et extrêmement coûteuses. En revanche, le chiffrement basé sur l'identité (IBE) répond parfaitement aux exigences en terme de chiffrement des données, d'authentification, de gestion des clés avec des partenaires extérieurs, de fourniture des clés aux composants d'infrastructure fiables, de restauration des clés et d'adaptation avec la croissance envisageable du réseau dans le future.

1.6 Les codes correcteurs

La théorie du codage est née avec la publication de SHANNON intitulée “A mathematical theory of communication” sur la théorie de la communication [SW63] et les travaux de HAMMING sur les codes [Ham50]. Au cours du demi-siècle écoulé, la théorie du codage s'est transformée en une discipline en protection de l'information qui croise les mathématiques et l'informatique et qui a des applications dans presque tous les domaines de la communication tels que la transmission par satellite ou par téléphone cellulaire, l'enregistrement sur des supports de stockage comme les disques, les clés USB, et d'autres supports. Le rôle des codes correcteurs est de corriger les erreurs de transmission ou de lecture de données numériques, ou les erreurs survenant au cours de leur inscription sur un support physique ou encore lorsque les données subissent une altération sur le support de stockage.
Le message transmis est constitué de “mots” de longueur fixe *k* et écrits dans un alphabet 𝒜 (dans le cas binaire l'alphabet est l'ensemble {0, 1} que l'on notera $\mathbb{F}_2$); chaque mot subit par la suite une opération d'encodage qui donne aux mots transmis une certaine structure afin de pouvoir détecter et corriger les erreurs potentielles. Pour y parvenir, les codes augmentent la longueur du message à transmettre. On obtient alors un mot de code d'une longueur $n > k$ qui peut être transmis sur un canal bruité ou stocké sur un support susceptible de subir des modifications. La structure du mot de code (qui dépend du code utilisé lors de l'encodage) permet de reconstituer le message initialement envoyé, même lorsqu'un nombre suffisamment faible de ses bits est perdu ou altéré. La figure 1.9
schématise le système de communication sur un canal bruité.

<figure><img src="image_13.png" /><figcaption>FIGURE 1.9 – Le schéma général d’un système de communication</figcaption></figure>

Il existe plusieurs familles de codes correcteurs d'erreurs, qui peuvent être linéaires ou pas. Dans cette partie, c'est la famille des codes linéaires qui retiendra particulièrement notre attention. D'ailleurs, nous l'utiliserons ultérieurement pour présenter une solution de masquage basée sur ce type de codes.

## 1.6.1 L'encodage

Soit $\mathbb{F}_q$ un corps fini à $q$ éléments. Un code linéaire $\mathcal{C}$ de dimension $k$ et de longueur $n$ est un sous-espace vectoriel de $\mathbb{F}_q^n$ de dimension $k$. Si $q = 2$ le code est dit binaire, sinon, on parle de code linéaire de base $q$. L'application d'encodage pour un code linéaire $\mathcal{C}$ est une application linéaire injective de $\mathbb{F}_q^k$ dans $\mathbb{F}_q^n$ (voir la figure 1.10).

**Définition 7 (la matrice génératrice)**

Soit $\mathcal{C}$ un code linéaire de longueur $n$ et de dimension $k$ dans $\mathbb{F}_q^n$. On appelle une matrice génératrice de $\mathcal{C}$ toute matrice $G \in \mathbb{F}_q^{k \times n}$ dont les lignes forment une base de $\mathcal{C}$ :

$$ \forall c \in \mathcal{C} \quad \exists! x \in \mathbb{F}_q^k \mid xG = c. $$

Un code linéaire est donc défini ainsi :

$$ \mathcal{C} = \{c = xG \mid \forall x \in \mathbb{F}_q^k \}. \qquad (1.1) $$

**Définition 8 (Le poids de HAMMING)**

Le poids de HAMMING d'un vecteur binaire $v$ correspond au nombre de 1 qu'il contient, et on le note $\omega_H(v)$.
<figure><img src="image_14.png" /><figcaption>FIGURE 1.10 – L’encodage pour les codes linéaires</figcaption></figure>

**Définition 9 (La distance de HAMMING)**

La distance de HAMMING entre deux vecteurs binaires $u$ et $v$ est égale au poids de HAMMING de $u - v$, et on la note $d_H(u, v)$.

**Définition 10 (La distance minimale)**

Étant donné un code $\mathcal{C}$, sa distance minimale $d_{\mathcal{C}}$ est définie comme la distance de HAMMING minimale entre deux mots de $\mathcal{C}$ :

$$d_{\mathcal{C}} = \min \{d_H(x, y) \mid x, y \in \mathcal{C}, x \neq y\} . \qquad (1.2)$$

Les paramètres d'un code linéaire sont notés $[n, k, d_{\mathcal{C}}]$, avec $n$ la longueur du code, $k$ la dimension, et $d_{\mathcal{C}}$ la distance minimale.

## 1.6.2 Le décodage

**Définition 11 (Le code dual)**

Le code dual d'un code linéaire $\mathcal{C}$ est le sous espace vectoriel de $\mathbb{F}_q^n$ noté $\mathcal{C}^{\perp}$ et égale à :

$$\mathcal{C}^{\perp} = \{d \in \mathbb{F}_q^{n-k} \mid \forall c \in \mathcal{C}, \langle c, d \rangle = 0\}, \qquad (1.3)$$

où $\langle \cdot, \cdot \rangle$ désigne le produit scalaire usuel modulo $q$.

Dans le reste du document nous allons noter $\mathcal{D}$ le code dual de $\mathcal{C}$. On appelle matrice de parité (aussi appelée : matrice de contrôle) la matrice génératrice du code dual; on la note souvent $H \in \mathbb{F}_q^{(n-k) \times n}$. Nous pouvons donc construire le code dual ainsi :

$$\mathcal{D} = \{d = yH \mid \forall y \in \mathbb{F}_q^{n-k}\}. \qquad (1.4)$$
## Propriété 1

Soient $\mathcal{C}$ un code linéaire de paramètres $[n, k, d]$, $\mathcal{D}$ son code dual, et $G \in \mathbb{F}_q^{k \times n}$ et $H \in \mathbb{F}_q^{(n-k) \times n}$ les matrices génératrices de $\mathcal{C}$ et $\mathcal{D}$ respectivement. On a :

$$ G \cdot H^T = 0. \qquad (1.5) $$

## Propriété 2 (Capacité de correction)

La capacité de correction (maximale) d'un code linéaire dépend de sa distance minimale $d$, et elle vaut :

$$ t = \left\lfloor \frac{d-1}{2} \right\rfloor. \qquad (1.6) $$

La méthode la plus simple (aussi coûteuse) pour décodeur s'appelle le "décodage par syndrome". Soit $x \in \mathbb{F}_q^k$ l'information à coder, $c = xG \in \mathbb{F}_q^n$ le mot de code associé à $x$, et $e \in \mathbb{F}_q^n$ un vecteur d'erreur, tel que $\omega_H(e) \le t$, avec $t$ la capacité de correction. On note $v = c + e$ le vecteur reçu. Pour détecter la présence des erreurs il suffit de calculer le syndrome : $\varepsilon = vH^T = (c+e)H^T = xGH^T + eH^T = eH^T$ (par l'équation 1.5), si le syndrome est nul alors $e=0$, sinon $e \ne 0$. Pour corriger l'erreur, il faut parcourir tous les vecteurs $e'$ de poids inférieur ou égal à $t$ et vérifier si $e'H^T = \varepsilon$, et puisque ce système d'équations n'admit qu'une seule solution alors il suffit de trouver une seule pour pouvoir corriger l'erreur.

## Propriété 3

Soit $n$ la longueur du code, et $t$ la capacité de correction. La complexité algorithmique du décodage par syndrome correspond au nombre de vecteurs d'erreur possibles de poids inférieur ou égal à $t$ :

$$ \sum_{i=1}^{t} \binom{n}{i}. $$

**Preuve :** Il suffit de remarquer que si l'erreur est de poids $i$, alors le nombre de vecteurs de poids $i$ est $\binom{n}{i}$. Donc, le nombre de vecteurs d'erreurs possibles est : $\sum_{i=1}^{t} \binom{n}{i}$. ■

### 1.6.3 Les codes parfaits

#### Définition 12 (Code parfait)

Soit $\mathcal{C}$ un code de longueur $n$ et de capacité de correction $t$. Le code $\mathcal{C}$ est dit **parfait** si et seulement si :

$$ \mathbb{F}_2^n = \bigcup_{c \in \mathcal{C}} \{x \in \mathbb{F}_2^n \mid d_H(c, x) \le t\}. $$
En d'autres termes, les boules fermées et disjointes de rayon $t$ et centrées en les mots de code couvrent tout l'espace vectoriel.

<figure><img src="image_15.png" /></figure>
en éliminant les $d-1$ dernières coordonnées de chaque mot de code est de cardinal $M$, que $M \le q^{n-d_c+1}$ et donc que $k \le n-d_c+1$.

## Définition 13 (Code MDS)

Un code linéaire $C$ vérifiant $d_c = n-k+1$ est dit MDS (Maximum Distance Separable), i.e. sa matrice de parité est de rang $d-1$.

### 1.6.4 Les codes de Reed-Muller binaires

Les codes de Reed-Muller sont une famille de codes correcteurs d'erreurs linéaires. Cette famille de codes doit son nom aux travaux de REED et MULLER. En 1954, MULLER [Mul54] a découvert le principe de ces codes, et indépendamment, REED [Ree54] a proposé la méthode de décodage. Ces codes, comme nous allons le voir dans cette section, ont une capacité de détection et correction qui s'adapte selon le besoin (en assurant un compromis entre la capacité de correction et la cardinalité). Entre 1969 et 1973 les codes de Reed-Muller proposaient le meilleur compromis de l'époque, et ils ont été choisi par les satellites Mariner 9 et Viking du NASA<fnref n="10" /> pour la transmission des images de Mars vers la Terre. On leur a ensuite préféré les codes de Reed-Solomon.

#### Définition 14 (Un monôme)

Soit $x = (x_1, \dots, x_m) \in \mathbb{F}_2^m$ un vecteur binaire de longueur $m$. Un monôme est une fonction booléenne $\varphi_I : \mathbb{F}_2^m \to \mathbb{F}_2$ qui renvoie le produit de quelques coordonnées de $x$ selon l'ensemble $I \subseteq \{1, \dots, m\}$ :

$$ \varphi_I(x) = \prod_{i \in I} x_i, $$

#### Exemple 3

Les monômes possibles pour le vecteur $x = (x_1, x_2, x_3)$ sont : $1, x_1, x_2, x_3, x_1x_2, x_1x_3, x_2x_3, x_1x_2x_3$.

Le degré d'un monôme correspond au nombre de coordonnées que nous multiplions. Par conséquent, seule la fonction constante 1 est de degré 0.

Il existe plusieurs façons de représenter une fonction booléenne (un mot de code). La plus classique c'est la forme algébrique normale (FAN), qui consiste à représenter la fonction sous sa forme polynomiale (comme dans l'exemple 4). Une autre façon, et qui nous intéresse particulièrement dans ce manuscrit, est la forme vectorielle, elle consiste à représenter la fonction par sa table de vérité, donc un vecteur de longueur $2^m$ (pour un code binaire).

<footnote n="10">10. National Aeronautics and Space Administration</footnote>
Nous remarquons que toute fonction booléenne est composée de la somme de plusieurs monômes, et que son degré correspond au degré maximal des monômes qui interviennent dans sa forme algébrique normale.

**Exemple 4**

Soit la fonction booléenne $f(x_1, x_2, x_3) = 1+x_2+x_1x_3$, cette fonction est composée du monôme 1 de degré 0, du monôme $x_2$ de degré 1, et du monôme $x_1x_3$ de degré 2, il s'agit donc d'une fonction de degré 2.

**Définition 15** (Les codes de Reed-Muller binaires)

Le code de Reed-Muller (RM) est l'ensemble des fonctions booléennes à $m$ variable, de degrés au plus $r$, et on le note :

$$RM(r, m) = \{f : \mathbb{F}_2[x_1, \dots, x_m] \to \mathbb{F}_2 \mid \deg(f) \le r\}.$$

Un code de Reed-Muller dépend donc des deux paramètres $r$ et $m$.

**Exemple 5**

Soit $C = RM(1,3)$ le code de Reed-Muller d'ordre 1 à 3 variables. La liste des mots de code qui appartiennent à $C$ est :

<table><thead><tr><th>la FAN</th><th>la table de vérité</th></tr></thead><tbody><tr><td>0</td><td>0 0 0 0 0 0 0</td></tr><tr><td>1</td><td>1 1 1 1 1 1 1</td></tr><tr><td>x<sub>1</sub></td><td>0 1 0 1 0 1 0</td></tr><tr><td>x<sub>1</sub> + 1</td><td>1 0 1 0 1 0 1</td></tr><tr><td>x<sub>2</sub></td><td>0 0 1 1 0 0 1 1</td></tr><tr><td>x<sub>2</sub> + 1</td><td>1 1 0 0 1 1 0 0</td></tr><tr><td>x<sub>2</sub> + x<sub>1</sub></td><td>0 1 1 0 0 1 1 0</td></tr><tr><td>x<sub>2</sub> + x<sub>1</sub> + 1</td><td>1 0 0 1 1 0 0 1</td></tr><tr><td>x<sub>3</sub></td><td>0 0 0 0 1 1 1 1</td></tr><tr><td>x<sub>3</sub> + 1</td><td>1 1 1 1 0 0 0 0</td></tr><tr><td>x<sub>3</sub> + x<sub>1</sub></td><td>0 1 0 1 1 0 1 0</td></tr><tr><td>x<sub>3</sub> + x<sub>1</sub> + 1</td><td>1 0 1 0 0 1 0 1</td></tr><tr><td>x<sub>3</sub> + x<sub>2</sub></td><td>0 0 1 1 1 1 0 0</td></tr><tr><td>x<sub>3</sub> + x<sub>2</sub> + 1</td><td>1 1 0 0 0 0 1 1</td></tr><tr><td>x<sub>3</sub> + x<sub>2</sub> + x<sub>1</sub></td><td>0 1 1 0 1 0 0 1</td></tr><tr><td>x<sub>3</sub> + x<sub>2</sub> + x<sub>1</sub> + 1</td><td>1 0 0 1 0 1 1 0</td></tr></tbody></table>

**Propriété 4** (La dimension d'un code RM)

La dimension du code $RM(r, m)$ est donnée par la formule :

$$k = \sum_{i=0}^{r} \binom{m}{i}.$$
**Preuve :** Le code $RM(r, m)$ est un sous-espace vectoriel de $\mathbb{F}_{2^{2m}}$, et la famille des monômes de degré au plus $r$ forme une base pour ce sous-espace vectoriel. Pour démontrer la formule précédente il suffit de remarquer que le nombre de monômes de degré $i$ vaut $\binom{m}{i}$, ensuite compter le nombre de monômes de degré 0 jusqu’à $r$. ■

La matrice génératrice d'un code $RM(r, m)$ est construite à partir de la table de vérité des monômes qui appartiennent à ce code. Chaque ligne correspond à un monôme dont elle est la liste des valeurs. Pour l'exemple précédent il s'agit des monômes $\{1, x_1, x_2, x_3\}$, mais en général l'ensemble des monômes est défini par :

$$ \left\{ \prod_{i=1}^{m} x_i^{v_i} \mid v \in \mathbb{F}_2^m , \quad \omega_H(v) \le r \right\} . $$

La matrice génératrice du code $RM(1, 3)$ est donc définie par :

$$ G = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} \begin{matrix} 1 \\ x_1 \\ x_2 \\ x_3 \end{matrix} $$

## Propriété 5

Pour tout $0 < r < m$ nous avons la propriété suivante :

$$ RM(r, m) = \left\{ (u, u + v) \in \mathbb{F}_2^{2m} \mid u \in RM(r, m-1), \ v \in RM(r-1, m-1) \right\}. $$

**Preuve :** Soit $f \in RM(r, m)$, nous avons :

$$ f(x_1, \dots, x_m) = x_1 f_1(x_2, \dots, x_m) + f_2(x_2, \dots, x_m), $$

avec $f_1$ une fonction de degré au plus $r-1$ appartenant au code $RM(r-1, m-1)$, et $f_2$ une fonction de degré au plus $r$ appartenant au code $RM(r, m-1)$. Nous avons :

$$ f(x_1, \dots, x_m) = \begin{cases} f_2(x_2, \dots, x_m) & \text{si } x_1 = 0 \\ f_1(x_2, \dots, x_m) + f_2(x_2, \dots, x_m) & \text{si } x_1 = 1 \end{cases} $$

Soient $u, v \in \mathbb{F}_2^{2m-1}$ les tables de vérité de $f_2$ et $f_1$ respectivement. La table de vérité de $f$ est donc définie par : $(\underbrace{u}_{x_1=0}, \underbrace{u+v}_{x_1=1})$. ■
**Propriété 6 (La distance minimale d'un code RM)**

La distance minimale d'un code de Reed-Muller de paramètres (r, m) est 2<sup>m-r</sup>.

**Preuve :** On montre par récurrence sur $m$. Pour $m = 1$ nous avons :

$$
- RM(0, 1) = \{(0, 0), (1, 1)\},
$$

$$
- RM(1, 1) = \{(0, 0), (0, 1), (1, 0), (1, 1)\}.
$$

Supposons que la distance minimale pour $RM(r, m-1)$ est $d_{m-1} = 2^{m-1-r}$. D'après la propriété 5 nous avons : $RM(r, m) = \{(u, u+v) \mid u \in RM(r, m-1), v \in RM(r-1, m-1)\}$, donc $d_m = \min\{\omega_H(u) + \omega_H(u+v)\}$ (avec $\omega_H$ désignant le poids de HAMMING) et puisque $RM(r-1, m-1) \subset RM(r, m-1)$ donc $u+v \in RM(r, m-1)$. D'après l'hypothèse de récurrence nous avons :

- Pour $u \neq v : \omega_H(u + v) \geq 2^{m-1-r}$ et $\omega_H(u) \geq 2^{m-1-r}$ donc $\omega_H(u, u + v) \geq 2^{m-1-r} + 2^{m-1-r} = 2^{m-r}$. Ainsi, sans perte de généralité, pour $v = 0$ : $d_m = \min\{\omega_H(u) + \omega_H(u)\} = 2^{m-r}$.

- Pour $u = v : \omega_H(u, u + v) = \omega_H(v, 0) = \omega_H(v)$, et puisque $v \in RM(r - 1, m - 1)$, alors $\omega_H(u, u + v) \ge 2^{m-r}$.

■

**Propriété 7 (Le dual d'un code RM)**

Le code dual d'un code de Reed-Muller de paramètres (r, m), avec r < m est le
code de Reed-Muller de paramètres (m − r − 1, m) :

$$
RM(r, m)^{\perp} = RM(m - r - 1, m) .
$$

**Preuve :** Pour $m = 2$ nous avons :

$$
RM(0, 2) = \{ (0000), (1111) \} .
$$

$$
RM(1, 2) = \left\{ \begin{array}{l} (0000), (0101), (1010), (1111), \\ (0011), (0110), (1001), (1100) \end{array} \right\} .
$$

Les deux codes sont orthogonaux, pour le prouver il suffit de remarquer que tous
les mots de *RM*(1, 2) sont de poids pairs.

Maintenant, supposons que la propriété 7 est vraie pour *m* − 1, et montrons qu'elle est vraie aussi pour *m*, nous avons :

$$
RM(r, m-1)^{\perp} = RM(m-r-2, m-1) .
$$

$$
RM(r - 1, m - 1)^{\perp} = RM(m - r - 1, m - 1) .
$$
# CHAPITRE 1. INTRODUCTION GÉNÉRALE

Et d'après la propriété 5 nous avons :

$$RM(r, m) = \left\{ (u, u + v) \in \mathbb{F}_2^{2m} \mid \begin{array}{l} u \in RM(r, m-1), \\ v \in RM(r-1, m-1) \end{array} \right\}.$$

$$RM(m-r-1, m) = \left\{ (u', u' + v') \in \mathbb{F}_2^{2m} \mid \begin{array}{l} u' \in RM(m-r-1, m-1), \\ v' \in RM(m-r-2, m-1) \end{array} \right\}.$$

Donc $\langle v, u' \rangle = \langle u, v' \rangle = 0$, et puisque $RM(r-1, m-1) \subset RM(r, m-1)$, donc le produit scalaire $\langle v, v' \rangle$ vaut aussi zéro. Calculons maintenant le produit scalaire entre un élément de $RM(r, m)$ et un élément de $RM(m-r-1, m)$ :

$$\begin{align*} \langle (u, u + v), (u', u' + v') \rangle &= \langle u, u' \rangle + \langle (u + v), (u' + v') \rangle \\ &= \langle u, u' \rangle + \langle u, u' \rangle + \langle u, v' \rangle + \langle u', v \rangle + \langle v, v' \rangle \\ &= 0. \end{align*}$$

Ainsi, nous avons prouvé que : $RM(m-r-1, m) \subset RM(r, m)^{\perp}$, pour démontrer l'égalité, il suffit de montrer que les deux codes ont la même dimension (donc même cardinalité) :

$$\begin{align*} \dim(RM(r, m)^{\perp}) &= 2^m - \dim(RM(r, m)) \\ &= 2^m - \sum_{i=0}^{r} \binom{m}{i} \\ &= \sum_{i=0}^{m} \binom{m}{i} - \sum_{i=0}^{r} \binom{m}{i} \\ &= \sum_{i=r+1}^{m} \binom{m}{i} \\ &= \sum_{i=0}^{m-r-1} \binom{m}{i} \\ &= \dim(RM(m-r-1, m)). \end{align*}$$

<figure><img src="image_16.png" /></figure>

## 1.7 L'AES

En 1997, un appel d'offre a été lancé par NIST<fnref n="11" /> qui avait pour but d'élaborer un algorithme de chiffrement symétrique qui remplace le standard du chiffrement des données (DES<fnref n="12" />). Ainsi en 2000, le standard de chiffrement avancé connu sous le nom AES<fnref n="13" /> [DR00] a été choisi parmi 15 candidats et devint ensuite le nouveau standard pour le chiffrement civil. L'AES repose sur les principes de diffusion et confusion énoncés par SHANNON [Sha49] :

<footnote n="11">11. National Institute of Standards and Technology</footnote>

<footnote n="12">12. Data Encryption Standard</footnote>

<footnote n="13">13. Advanced Encryption Standard</footnote>
**La diffusion** : signifie que si nous changeons un ou plusieurs bits du texte en clair, en moyenne la moitié des bits du texte chiffré devrait changer, et de même, si l'on change un bit du cryptogramme, environ la moitié des bits en message clair devraient changer. En d'autres termes, la redondance statistique dans le texte en clair est dissipée dans les statistiques du texte chiffré, ainsi, aucune corrélation entre l'entrée et la sortie ne doit s'apercevoir.

**La confusion** : signifie que chaque bit du cryptogramme est calculé à partir de plusieurs bits de la clé dans l'objectif de rendre le lien entre la clé et le texte chiffré aussi complexe que possible.

L'AES est un réseau de substitution et de permutation, qui opère sur des blocs de taille 128, 196 ou 256 avec une clé de longueur 128, 196 ou 256 bits respectivement. Il faut 10 tours pour une clé de 128 bits, 12 pour une clé de 192 bits et 14 pour une clé de 256 bits.

<table><caption>TABLE 1.2 – Le nombre de tours en fonction de la taille des clés.</caption><thead><tr><td></td><td>Longueur de la clé</td><td>Nombre de tours</td></tr></thead><tbody><tr><td>AES-128</td><td>128</td><td>10</td></tr><tr><td>AES-192</td><td>192</td><td>12</td></tr><tr><td>AES-256</td><td>256</td><td>14</td></tr></tbody></table>

Un tour comprend plusieurs étapes de traitement (des transformations) qui agissent sur une valeur de 128 bits (pour le cas AES-128), constituée de 16 octets arrangés en une matrice 4 × 4. Ces transformations sont basées sur des opérations sur le corps fini $K = \mathbb{F}_2[\alpha]/P(\alpha)$ tel que $P(\alpha) = \alpha^8+\alpha^4+\alpha^3+\alpha+1$. Chacune des classes d'équivalence de ce corps est représentée par un polynôme de degré au plus 7 à coefficients dans $\mathbb{F}_2$. Pour simplifier nous allons exprimer chaque polynôme de ce corps $Q(\alpha) = \sum_{i=0}^{7} c_i \alpha^i$ par deux chiffres en hexadécimal, tel que la représentation binaire de cet entier correspond aux coefficients du polynôme qu'il représente (i.e. $(c_7...c_0)$).

**Exemple 6**

$$ 
\begin{aligned}
Q(\alpha) &= \alpha^5 + \alpha^4 + \alpha^3 + \alpha^2 + \alpha \\
&= 0 \cdot \alpha^7 + 0 \cdot \alpha^6 + 1 \cdot \alpha^5 + 1 \cdot \alpha^4 + 1 \cdot \alpha^3 + 1 \cdot \alpha^2 + 1 \cdot \alpha + 0.
\end{aligned}
$$

est représenté par l'entier 00111110 en binaire, et qui vaut $3E$ en hexadécimal. Donc le polynôme $Q(\alpha)$ sera représenté par l'entier $3E$. ■

Pour chaque élément non nul $x$ dans $K$, il existe un élément inverse que l'on notera $x^{-1}$ tel que : $x \cdot x^{-1} = 1$. Nous allons également noter $x_i$ le $i^{ème}$ coefficient du polynôme $x$ pour $0 \le i \le 7$.
## 1.7.1 Chiffrement

L'algorithme de chiffrement AES est composé des quatre transformations suivantes :

- **SubBytes** : aussi connue sous le nom "S-Box", c'est une fonction bijective non linéaire $S : K \rightarrow K$ qui assure la propriété de confusion. Elle permet de substituer indépendamment les octets d'un bloc grâce à une table de substitution prédéfinie, cette table est calculée grâce à la fonction suivante :

$$S(x)_i = x_i^{-1} \oplus x_{(i+4) \bmod 8}^{-1} \oplus x_{(i+5) \bmod 8}^{-1} \oplus x_{(i+6) \bmod 8}^{-1} \oplus x_{(i+7) \bmod 8}^{-1} \oplus c_i, \quad (1.7)$$

pour $0 \le i < 8$, avec $c_i$ désigne le $i^{ème}$ coefficient de l'élément $c = 63$, et l'opération $\oplus$ qui désigne le XOR.

- **ShiftRows** : cette transformation opère indépendamment sur les lignes de la matrice en entrée $M \in K^{4 \times 4}$. Elle opère une permutation circulaire sur les octets dans chaque ligne. Pour l'AES-128, la première ligne est laissée inchangée. Chaque octet de la deuxième ligne est décalé d'un pas vers la gauche. De même, la troisième et quatrième ligne sont décalées par des décalages de deux et trois respectivement. Si on considère $M \in K^{4 \times 4}$ la matrice en entrée alors :

$$\text{ShiftRows}(M_{i,j}) = M_{i,(i+j) \bmod 4} \mid \forall 0 \le i, j \le 3.$$

- **MixColumns** : Dans cette étape, les quatre octets de chaque colonne de la matrice en entrée sont combinés à l'aide d'une transformation linéaire inversible. Cette transformation consiste en un produit matriciel entre une matrice prédéfinie notée $L \in K^{4 \times 4}$ et la matrice en entrée $M$ :

$$\text{MixColumns}(M) = \begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{bmatrix} \cdot M.$$

Avec **ShiftRows**, **MixColumns** fournit la propriété de diffusion dans le chiffrement.

- **AddRoundKey** : Dans cette étape, la sous-clé est combinée avec la matrice en entrée. Pour chaque tour, une sous-clé dérivée de la clé principale à l'aide du générateur de clés de RIJNDAEL (qui lui aussi utilise les transformations précédentes); Chaque sous-clé est de la même taille que la matrice $M$. La sous-clé est ajoutée en combinant chaque octet de la matrice avec l'octet correspondant de la sous-clé à l'aide d'une addition dans $K$ (notée $\oplus$).

Durant l'opération de chiffrement, ces transformations sont exécutées dans l'ordre indiqué dans la figure 1.12.
<figure><img src="image_17.png" /><figcaption>FIGURE 1.12 – L'opération de chiffrement pour l'AES-128</figcaption></figure>

1.7.2 Déchiffrement

Pour déchiffrer, il suffit d'appliquer l'opération inverse de chacune des transforma-
tions que nous avons vues précédemment :

— **InvSubBytes**: L'opération inverse de **SubBytes** peut être calculée grâce à la fonction suivante $S'$ : $x \mapsto y^{-1}$ tel que :

$$
y_i = x_{(i+2) \bmod 8} \oplus x_{(i+5) \bmod 8} \oplus x_{(i+7) \bmod 8} \oplus c_i, \quad (1.8)
$$

pour $0 \le i < 8$.

— InvShiftRows :

$$
\mathrm{InvShiftRows}(M_{i,j}) = M_{i,(i-j) \bmod 4} \mid \forall 0 \le i,j \le 3;
$$
# CHAPITRE 1. INTRODUCTION GÉNÉRALE

- **InvMixColumns** : Pour inverser la transformation MixColumns, il suffit de multiplier la matrice en entrée par la matrice inverse de $L$ qui est égale à :

$$L^{-1} = \begin{bmatrix} 0E & 0B & 0D & 09 \\ 09 & 0E & 0B & 0D \\ 0D & 09 & 0E & 0B \\ 0B & 0D & 09 & 0E \end{bmatrix}.$$

- **AddRoundKey** : L'addition et la soustraction sont identiques dans un corps de caractéristique 2.
Première partie

LES TECHNIQUES DE
MASQUAGE POUR LUTTER
CONTRE LES ATTAQUES PAR
CANAUX AUXILIAIRES (SCA)
ET LES ATTAQUES PAR
INJECTION DE FAUTES (FIA)
<figure><img src="image_18.png" /></figure>
# 1 | L'état de l'art sur le masquage

## Sommaire

<table><tr><td>1.1</td><td>Le masquage booléen</td><td>42</td></tr><tr><td>1.1.1</td><td>Le schéma Ishai-Sahai-Wagner (ISW)</td><td>42</td></tr><tr><td>1.1.2</td><td>Le schéma de Rivain et Prouff (RP)</td><td>44</td></tr><tr><td>1.2</td><td>Le masquage basé sur les polynômes</td><td>53</td></tr><tr><td>1.2.1</td><td>Le schéma de Shamir sur le partage du secret</td><td>53</td></tr><tr><td>1.2.2</td><td>Les codes de Reed-Solomon</td><td>55</td></tr><tr><td>1.2.3</td><td>Le masquage basé sur le partage du secret</td><td>55</td></tr><tr><td>1.2.4</td><td>Le schéma sécurisé de calcul multipartite BGW</td><td>57</td></tr><tr><td>1.2.5</td><td>L'algorithme de multiplication de Prouff et Roche</td><td>58</td></tr><tr><td>1.3</td><td>Le masquage basé sur le produit scalaire (IPM)</td><td>59</td></tr><tr><td>1.4</td><td>Le masquage basé sur les codes</td><td>62</td></tr><tr><td>1.4.1</td><td>Rappels</td><td>62</td></tr><tr><td>1.4.2</td><td>Le masquage par somme directe orthogonale (ODSM)</td><td>64</td></tr><tr><td>1.4.3</td><td>Exemple</td><td>71</td></tr><tr><td>1.5</td><td>Conclusion</td><td>73</td></tr></table>
# CHAPITRE 1. L'ÉTAT DE L'ART SUR LE MASQUAGE

Juste après la naissance de l'AES au début de ce siècle, des travaux ont montré que les attaques par canaux auxiliaires constituent une menace pour les cryptosystèmes implémentés dans des dispositifs embarqués. La consommation électrique pendant une opération de chiffrement ou le temps de calcul peuvent divulguer des informations sur des valeurs intermédiaires manipulées au cours de l'algorithme de chiffrement, ceci entraîne des attaques pratiques sur les composants électriques [Koc96, KJJ99]. Les rayonnements électromagnétiques [QS01, GMO01, RR01, QS02], et même les sons émis par les machines à rotor [Kah74] peuvent également donner à l'attaquant une fenêtre de visibilité sur les valeurs intermédiaires au cours du calcul. Ce type d'attaques fourni à l'adversaire une version bruitée de valeurs telles que le poids de HAMMING de certaines données sensibles.

Par ailleurs, les attaques par injection de fautes consistent à agir sur les conditions environnementales du système (tension, horloge, température, rayonnement, lumière, ...) pour générer des défauts pendant l'exécution du chiffrement et observer ensuite le comportement résultant. De telles attaques peuvent être conçues en éclairant simplement un transistor avec un faisceau laser (l'effet photovoltaïque) [SA02, AK97] ; ce qui génère un dysfonctionnement lié à la modification de la fréquence du travail pendant le calcul, et qui entraîne une mauvaise valeur de certains bits. L'utilisation d'une erreur lors d'un calcul pour deviner la clé secrète a été observée pratiquement dans les implémentations de RSA qui utilisent le théorème chinois des restes [JLQ99, BDL01, AK97]. En ce qui concerne le chiffrement métrique et en particulier l'AES ; une attaque simple et directe a été proposée par BLÖMER [BS03] qui vise à changer un seul bit juste après la première addition de la clé (AddRoundKey). L'objectif est de réinitialiser un seul bit dans l'état interne $M^0$ (en général, $M^i$ indique l'état au début du $i$-ème tour), et observer si la valeur du texte chiffré a changé. Si le texte chiffré a changé ou a été détecté comme défectueux par un circuit de détection de défaut, l'attaquant saura que la valeur correcte du bit est 1, sinon elle est égale à 0. Étant donné que le bit modifié est le résultat d'un XOR entre le texte en clair supposé connu et la clé secrète, l'attaquant pourra donc deviner facilement la valeur du bit concerné de la clé. Bien que cette attaque puisse en principe récupérer la clé de chiffrement en entier, elle a été jugée pratiquement impossible en raison du temps précis requis pour l'injection de fautes et de la précision stricte sur la position exacte de l'injection.

En raison de la très grande variété d'attaques SCA (Side Channel Attack) et FIA (Fault Injection Attack) signalées contre les systèmes et les dispositifs cryptographiques, des efforts importants ont été déployés pour concevoir des contre-mesures avec une sécurité prouvable. Ces contre-mesures partent toutes de l'hypothèse qu'un dispositif cryptographique dispose d'une partie sécurisée de mémoire et que seuls les calculs peuvent fuiter. Les contre-mesures les plus courantes pour lutte contre de telles attaques sont le masquage [GP99, CJRR99] et le brouillage
[RPD09]. Le brouillage est une solution simple qui consiste à ajouter une série aléatoire d'opérations pendant le (dé)chiffrement afin de camoufler les fuites émises par le composant pendant l'exécution des différentes opérations de l'algorithme de (dé)chiffrement. Tandis que le masquage consiste à exprimer chaque variable intermédiaire sensible apparaissant dans le calcul en plusieurs parties indépendantes. Il est indispensable que ces parties ne puissent révéler aucune information sur la donnée sensible s'il en manque au moins une.

Si nous considérons $f: E \to E$ une des transformations qui composent un cryptosystème symétrique quelconque (AES-128 par exemple), le masquage de cette transformation consiste à concevoir une fonction indéterministe (une variable aléatoire) **mask**: $E \to F$, ainsi qu'une transformation alternative $f': F \to F$ telles que :

$$f'(\mathbf{mask}(x)) = \mathbf{mask}(f(x)),$$

où $x$ représente la donnée sensible à protéger, et $\mathbf{mask}(x)$ le masqué associé à $x$. Il faut noter également que la transformation alternative $f'$ ne doit révéler aucune information sur la donnée sensible $x$ durant son exécution, si c'est le cas, on dit alors que $f'$ est Probing secure (voir la définition 16 page 43). D'un autre côté, pour réussir à détecter et éventuellement corriger les erreurs potentielles susceptibles d'être injectées, il faudra que l'espace d'arrivée $F$ de la fonction de masquage soit un code correcteur d'erreurs prédéfini et qui offre la possibilité de détecter ou corriger les injections d'erreurs. Pour cela, nous allons voir dans le chapitre 2 qu'il est possible de concevoir un masquage détecteur d'erreurs.
## 1.1 Le masquage booléen

Plusieurs solutions ont été proposées pour protéger le chiffrement symétrique des attaques par canaux auxiliaires. La méthode de masquage la plus classique, appelée masquage booléen, consiste à exprimer la donnée sensible $x$ comme somme de plusieurs parties $x_0, x_1, \dots, x_d$ (ce qu'on appelle en anglais “shares”) telles que : $x = \bigoplus_{i=0}^d x_i$ et pour tout ensemble $S \subset \{x_0, \dots, x_d\}^1$, les éléments de $S$ ne révèlent aucune information sur $x$. Le masquage consiste ensuite à appliquer les opérations qui composent le système de chiffrement à chacune de ces parties sans impliquer directement la donnée sensible $x$ dans le processus de calcul.

Ce type de décomposition est $\mathbb{F}_2$-linéaire, par conséquent, le masquage des transformations additives est simple à réaliser. En effet, si on considère $(x_0, \dots, x_d)$ et $(y_0, \dots, y_d)$ les shares associés aux données sensibles $x$ et $y$ respectivement (i.e. $x = \bigoplus_{i=0}^d x_i$, $y = \bigoplus_{i=0}^d y_i$) alors, on peut considérer $((x_0 \oplus y_0), \dots, (x_d \oplus y_d))$ les shares associés à $x \oplus y$ (car : $x + y = \bigoplus_{i=0}^d (x_i \oplus y_i)$).

D'un autre côté, il est moins intuitif de masquer les transformations non additives (non-linéaires). En effet, nous allons voir dans les schémas qui suivent que le masquage des opérations telles que la multiplication demande - dans le meilleur des cas - une complexité quadratique.

Chaque transformation $f$ qui compose l'algorithme de chiffrement (ou déchiffrement) doit être remplacée par une fonction $f'$ telle que $f'(x_0, \dots, x_d) = (y_0, \dots, y_d)$ et que $\bigoplus_{i=0}^d y_i = f(x)$. Dans ce cas de figure, l'adversaire aura besoin d'au moins $d+1$ variables intermédiaires pour construire la donnée sensible $x$, c'est ce qu'on appelle un masquage d'ordre $d$. Cependant, un masquage d'ordre $d$ est toujours théoriquement vulnérable à une SCA d'ordre ($d+1$) qui exploite les fuites liées à $d+1$ variables intermédiaires en même temps [Mes00, RPD09, SP06]. Dans la pratique les effets de bruit impliquent que la complexité d'une attaque d'ordre $d$ augmente exponentiellement avec $d$.

### 1.1.1 Le schéma Ishai-Sahai-Wagner (ISW)

Une première solution pour masquer les fonctions non linéaires a été proposée par Ishai et al. dans [ISW03]. Le schéma présenté permet de sécuriser l'implémentation matérielle de tout circuit à n'importe quel ordre choisi $d$. Ils décrivent un moyen de transformer le circuit pour se protéger en un nouveau circuit (traitant des valeurs masquées) de sorte qu'aucun sous-ensemble de $d$ de ses fils ne révèle des informations sur les valeurs sensibles. Pour ce faire, ils supposent - sans perte de généralité - que le circuit à protéger est exclusivement composé de portes logiques "NON" (que nous allons noter $\neg$) et "ET" (que nous allons noter $\wedge$). Dans ce contexte, la

<footnote n="1">1. Le cardinal de l'ensemble $S$ est strictement inférieur au nombre de parties.</footnote>
protection de la porte logique de type "NON" revient à protéger l'addition binaire (XOR) (car $\neg x = x \oplus 1$), ce qui a l'avantage de se généraliser comme l'ont montré RIVAIN et PROUFF (voir ci-dessous) aux mêmes opérations dans $\mathbb{F}_{2^n}$, et qui s'applique directement à l'AES. La sécurisation d'une porte "NOT" pour n'importe quel ordre $d$ est simple puisque $x = \bigoplus_{i=0}^{d} x_i$ implique $\neg x = \neg x_0 \oplus \bigoplus_{i=1}^{d} x_i$. La principale difficulté est donc de sécuriser les portes "ET".

Soient $(x_0, \dots, x_d)$, $(x'_0, \dots, x'_d) \in \mathbb{F}_2^d$, les shares associés à $x$ et $x'$ respectivement (i.e. $x = \bigoplus_{i=0}^{d} x_i \in \mathbb{F}_2$ et $x' = \bigoplus_{i=0}^{d} x'_i \in \mathbb{F}_2$). Pour sécuriser la porte ET, il faut construire une fonction $(x_0, \dots, x_d), (x'_0, \dots, x'_d) \mapsto (y_0, \dots, y_d)$ telle que : $\bigoplus_{i=0}^{d} y_i = (\bigoplus_{i=0}^{d} x_i)(\bigoplus_{i=0}^{d} x'_i)$. Pour répondre à cette question, ISHAI et al. ont suggéré la solution suivante :

- Pour tout $0 \le i < j \le d$, choisir un bit aléatoire $r_{i,j}$ (le masque),

- Pour tout $0 \le i < j \le d$, calculer $r_{j,i} = (r_{i,j} \oplus x_i x'_j) \oplus x_j x'_i$,

- Pour tout $0 \le i \le d$ calculer $y_i = x_i x'_i \oplus \bigoplus_{j=0, j \ne i}^{d} r_{i,j}$.

L'utilisation du masque $r_{i,j}$ est essentielle dans ce schéma, c'est lui qui permet de protéger les opérations effectuées grâce à cette couche aléatoire. Il faut noter également que l'utilisation des parenthèses pour calculer $r_{j,i}$ indique l'ordre dans lequel les opérations sont effectuées, ce qui est primordial pour la probing security. En effet, en respectant cet ordre, le masque $r_{i,j}$ interviendra dans toutes les opération "$\oplus$" afin de masquer les valeurs sensibles.

**Définition 16 (Probing Attack)**

L'attaque PA (en anglais : Probing Attack) fait partie de la famille SCA, elle consiste à placer une aiguille métallique sur un des fils d'une carte électronique et lire la valeur transportée par ce fil pendant le calcul.

**Définition 17 (t-Probing Security)**

On dit qu'un algorithme atteint un niveau de sécurité t-PS (t-Probing security) si chaque ensemble de t variables intermédiaires (au plus) de l'exécution ne laisse fuir aucune information sur les variables sensibles.

**Exemple 7**

Pour $d = 2$ on obtient :

<table><thead><tr><th rowspan="2">i \ j</th><th colspan="3">r</th><th rowspan="2">y</th></tr><tr><th>0</th><th>1</th><th>2</th></tr></thead><tbody><tr><td>0</td><td>-</td><td>r<sub>0,1</sub></td><td>r<sub>0,2</sub></td><td>x<sub>0</sub>x'<sub>0</sub> &oplus; r<sub>0,1</sub> &oplus; r<sub>0,2</sub></td></tr><tr><td>1</td><td>r<sub>0,1</sub> &oplus; x<sub>0</sub>x'<sub>1</sub> &oplus; x<sub>1</sub>x'<sub>0</sub></td><td>-</td><td>r<sub>1,2</sub></td><td>x<sub>1</sub>x'<sub>1</sub> &oplus; r<sub>1,0</sub> &oplus; r<sub>1,2</sub></td></tr><tr><td>2</td><td>r<sub>0,2</sub> &oplus; x<sub>0</sub>x'<sub>2</sub> &oplus; x<sub>2</sub>x'<sub>0</sub></td><td>r<sub>1,2</sub> &oplus; x<sub>1</sub>x'<sub>2</sub> &oplus; x<sub>2</sub>x'<sub>1</sub></td><td></td><td>x<sub>2</sub>x'<sub>2</sub> &oplus; r<sub>2,0</sub> &oplus; r<sub>2,1</sub></td></tr></tbody></table>
On peut donc vérifier que :

$$y_0 = x_0 x'_0 \oplus \underbrace{r_{0,1} \oplus r_{0,2}}_{r'_0}$$

$$y_1 = x_1 x'_1 \oplus x_1 x'_0 \oplus x_0 x'_1 \oplus \underbrace{r_{0,1} \oplus r_{1,2}}_{r'_1}$$

$$y_2 = x_2 x'_2 \oplus x_2 x'_0 \oplus x_0 x'_2 \oplus x_2 x'_1 \oplus x_1 x'_2 \oplus \underbrace{r_{0,2} \oplus r_{1,2}}_{r'_2}$$

$$xx' = (x_0 \oplus x_1 \oplus x_2)(x'_0 \oplus x'_1 \oplus x'_2)$$

$$= \underbrace{x_0 x'_0}_{y_0 - r'_0} \oplus \underbrace{x_1 x'_1 \oplus x_1 x'_0 \oplus x_0 x'_1}_{y_1 - r'_1} \oplus \underbrace{x_2 x'_2 \oplus x_2 x'_0 \oplus x_0 x'_2 \oplus x_2 x'_1 \oplus x_1 x'_2}_{y_2 - r'_2}$$

$$= y_0 \oplus y_1 \oplus y_2 .$$

Comme nous l'avons mentionné précédemment, l'ordre d'exécution des opérations est très important, l'idée consiste à faire intervenir le masque $r_{i,j}$ (avec $i < j$) dans chacune des additions ($\oplus$). Comme nous le constatons dans cet exemple les shares obtenus : $y_0, y_1$ et $y_2$ contiennent tous une trace de ce masque (qui est respectivement $r'_0, r'_1$ et $r'_2$).

Pour vérifier que ce masquage est $2-PS$, il suffit de calculer toutes les combinaisons possibles de $a$ et $b$ dans $\{r_{0,1}, r_{0,2}, r_{1,0}, r_{1,2}, r_{2,0}, r_{2,1}, y_0, y_1, y_2\}$ et constater qu'aucune combinaison de révèle des informations sur les données sensibles. D'un autre côté, si nous combinons 3 variables, par exemple : $y_0 \oplus y_1 \oplus y_2$ nous pouvons obtenir l'information $xx'$.

Ce schéma permet de masquer les deux opérations logiques "ET" et "NON", ces deux opérations représentent la base de toutes les transformations qui composent un cryptosystème. Cependant, ce schéma induit un surcoût important pour le circuit masqué. En effet, toutes les portes logiques de type "ET" sont encodées en utilisant $(d+1)^2$ portes de type "ET" et $2d(d+1)$ portes de type "XOR", et nécessite la génération de $d(d+1)/2$ bits aléatoires à chaque cycle d'horloge.

Pour réduire le problème de surcoût, RIVAIN et PROUFF [RP10] ont présenté une solution similaire avec des améliorations remarquables au niveau de la complexité des calculs.

## 1.1.2 Le schéma de Rivain et Prouff (RP)

RIVAIN et PROUFF [RP10] ont présenté une version améliorée du schéma précédent. L'idée consiste à adapter ce qui était fait pour des opérations sur $\mathbb{F}_2$ à des opérations sur $\mathbb{F}_{2^n}$, permettant ainsi d'opérer directement sur des données de taille plus grande.
Soit $\mathbb{F}_{2^8} = \mathbb{F}_2[\alpha]/P(\alpha)$ le corps fini utilisé pour AES (voir la section 1.7 page 32), soit $a \in \mathbb{F}_{2^8}$ une donnée sensible, et $a_0, \dots, a_d$ les shares associés à $a$ définis par : $a = \bigoplus_{i=0}^{d} a_i$, pour simplifier nous allons apposer une flèche en haut de la variable pour designer qu'il s'agit du mot masqué : $\vec{a} = (a_0, \dots, a_d) \in \mathbb{F}_{2^8}^{d+1}$.

L'algorithme 1 permet de masquer un octet selon la méthode de RIVAIN et PROUFF, l'algorithme opère sur une donnée de taille 8 bits (un octet), et renvoie un vecteur de taille $d + 1$ octets.

<table><thead><tr><th>Algorithm 1 RPMaskByte</th><th>Complexité : d additions</th></tr></thead><tbody><tr><td>1: entrée : une donnée sensible $a \in \mathbb{F}_{2^8}$ et l'ordre du masquage $d$</td><td></td></tr><tr><td>2: sortie : $\vec{a} = (a_0, \dots, a_d) \in (\mathbb{F}_{2^8})^{d+1}$ tel que $\bigoplus_{i=0}^{d} a_i = a$</td><td></td></tr><tr><td>3: $a_0 \leftarrow a$</td><td></td></tr><tr><td>4: pour $i = 1$ jusqu'à $d$ faire :</td><td></td></tr><tr><td>5: $a_i \leftarrow \mathbb{F}_{2^8}$</td><td></td></tr><tr><td>6: $a_0 \leftarrow a_0 \oplus a_i$</td><td></td></tr><tr><td>7: renvoyer $\vec{a}$</td><td></td></tr></tbody></table>

L'algorithme 2 représente l'opération inverse de l'algorithme précédent, il permet d'extraire la donnée sensible à partir d'une donnée masquée.

<table><thead><tr><th>Algorithm 2 RPUnmaskByte</th><th>Complexité : (d + 1) additions</th></tr></thead><tbody><tr><td>1: entrée : un masqué $\vec{a} = (a_0, \dots, a_d) \in (\mathbb{F}_{2^8})^{d+1}$</td><td></td></tr><tr><td>2: sortie : la donnée sensible $a \in \mathbb{F}_{2^8}$ tel que $\bigoplus_{i=0}^{d} a_i = a$</td><td></td></tr><tr><td>3: $a \leftarrow 0$</td><td></td></tr><tr><td>4: pour $i = 0$ jusqu'à $d$ faire :</td><td></td></tr><tr><td>5: $a \leftarrow a \oplus a_i$</td><td></td></tr><tr><td>6: renvoyer $a$</td><td></td></tr></tbody></table>

Dans le schéma de RIVAIN et PROUFF, une donnée sensible $a \in \mathbb{F}_{2^8}$ dépend des $d+1$ shares $a_0, \dots, a_d$, il s'agit donc d'un masquage d'ordre $d$ et qui protège contre toute attaque d'ordre inférieur à $d+1$. Pour appliquer ce schéma sur l'AES il faudra reconstruire toutes les transformations (Inv)SubBytes, (Inv)MixColumns et AddRoundKey qui composent l'AES (la transformation (Inv)ShiftRows n'opère pas sur les données, il s'agit juste d'une permutation des octets, il est donc inutile de la masquer). Comme nous l'avons expliqué dans la section 1.7, ces transformations se composent essentiellement de trois types d'opérations dans $\mathbb{F}_{2^8}$ : l'addition, la multiplication et l'inverse.
## 1.1.2.1 La linéarité du masquage

### Définition 18 (La linéarité)

Soient $E$ et $F$ deux espaces vectoriels sur un corps $K$, on dit que $f: E \to F$ est une fonction linéaire si pour tous $x, y \in E$ et $\lambda, \mu \in K$ nous avons :

$$f(\lambda x + \mu y) = \lambda f(x) + \mu f(y).$$

### Propriété 8

La variable aléatoire `RPMaskByte`: $\mathbb{F}_8 \to \mathbb{F}_8^{d+1}$ satisfaisant : `RPMaskByte`(x) = $(x_0, \dots, x_d)$ tels que $\sum_{i=0}^{d} x_i = x$ est linéaire.

### Preuve :

Soient $a, b \in \mathbb{F}_{2^8}$ deux valeurs sensibles, et $\vec{a}, \vec{b} \in \mathbb{F}_{2^8}^{d+1}$ deux vecteurs tels que :
$\vec{a} = \text{RPMaskByte}(a)$ et $\vec{b} = \text{RPMaskByte}(b)$. Nous avons :

$$ \begin{aligned} \text{RPMaskByte}(a) \oplus \text{RPMaskByte}(b) &= \vec{a} \oplus \vec{b} \\ &= (a_0, \dots, a_d) \oplus (b_0, \dots, b_d) \\ &= (a_0 \oplus b_0, \dots, a_d \oplus b_d) \\ &= \text{RPMaskByte}(a \oplus b). \end{aligned} $$

Donc la fonction `RPMaskByte` est bien linéaire.

<figure><img src="image_19.png" /></figure>

En général la linéarité d'une fonction de masquage est une propriété importante. Elle permet de masquer plus facilement les opérations linéaires dans le corps fini utilisé. Les opérations comme l'addition, la multiplication par un scalaire, et l'exponentiation avec un exposant sous la forme $2^n$ sont toutes des opérations linéaires faciles à masquer.

Comme nous l'avons montré dans la preuve précédente, pour masquer l'addition il suffit d'additionner les shares des valeurs en entrée respectivement.

**Algorithm 3 RPAdd**

Complexité : $(d + 1)$ additions

1: **entrée** : $\vec{a} = \text{RPMaskByte}(a)$ et $\vec{b} = \text{RPMaskByte}(b)$

2: **sortie** : $\vec{c} = \text{RPMaskByte}(a \oplus b)$

3: **pour** $i = 0$ **jusqu'à** $d$ **faire** :

4: $c_i \leftarrow a_i \oplus b_i$

5: **renvoyer** $\vec{c}$

## 1.1.2.2 La multiplication par un scalaire

Un cas particulier de multiplication qui sera intéressant pour plus tard, c'est la multiplication entre un mot masqué et une valeur non masquée. Souvent, dans un chiffrement symétrique comme l'AES, les données sensibles sont multipliées
par des valeurs publiques. Par exemple : La transformation *MixColumns* (voir la section 1.7 page 32) consiste à multiplier la matrice intermédiaire par une matrice prédéfinie, il est donc inutile de masquer les données publiques.

La multiplication par un scalaire est une opération linéaire, ceci simplifie son masquage. Soient $a, \lambda \in \mathbb{F}_{2^8}$ tels que $a$ une donnée sensible associé à $\vec{a} \in \mathbb{F}_{2^8}^{(d+1)}$ et $\lambda$ une donnée publique non masquée. Nous avons $\lambda\vec{a} = \lambda a_0 \oplus \dots \oplus \lambda a_d$ donc nous pouvons considérer $\vec{c} = (\lambda a_0, \dots, \lambda a_d)$ le masqué associé à $\lambda\vec{a}$.

<table><thead><tr><th>Algorithm 4 RPMult2</th><th>Complexité : (d + 1) multiplications</th></tr></thead><tbody><tr><td>1: entrée : $\vec{a} = \text{RPMaskByte}(a)$ et $\lambda$</td><td></td></tr><tr><td>2: sortie : $\vec{c} = \text{RPMaskByte}(\lambda a)$</td><td></td></tr><tr><td>3: pour $i = 0$ jusqu'à $d$ faire :</td><td></td></tr><tr><td>4: $c_i = \lambda a_i$</td><td></td></tr><tr><td>5: renvoyer $\vec{c}$</td><td></td></tr></tbody></table>

### 1.1.2.3 La multiplication entre deux données masquées

La multiplication entre deux vecteurs n'est pas linéaire, ce qui mène à des calculs supplémentaires pour garder la même structure du masque. L'algorithme de RIVAIN et PROUFF est identique à celui de l'opération "ET" du schéma ISW de la section précédente. En revanche, cette fois on traite des éléments du corps fini $\mathbb{F}_{2^8}$. Comme pour la multiplication ISW, il est important de bien respecter les parenthèses dans la ligne 6 de l'algorithme pour atteindre la *probing security*.

<table><thead><tr><th>Algorithm 5 RPMult</th><th>Complexité : $(d+1)^2$ multiplications et $2d(d+1)$ additions</th></tr></thead><tbody><tr><td>1: entrée : $\vec{a} = \text{RPMaskByte}(a)$ et $\vec{b} = \text{RPMaskByte}(b)$</td><td></td></tr><tr><td>2: sortie : $\vec{c} = \text{RPMaskByte}(ab)$</td><td></td></tr><tr><td>3: pour $i = 0$ jusqu'à $d$ faire :</td><td></td></tr><tr><td>4: pour $j = i + 1$ jusqu'à $d$ faire :</td><td></td></tr><tr><td>5: $r_{i,j} \leftarrow \mathbb{F}_{2^8}$</td><td></td></tr><tr><td>6: $r_{j,i} \leftarrow (r_{i,j} \oplus a_i b_j) \oplus a_j b_i$</td><td></td></tr><tr><td>7: pour $i = 0$ jusqu'à $d$ faire :</td><td></td></tr><tr><td>8: $c_i \leftarrow a_i b_i$</td><td></td></tr><tr><td>9: pour $j = 0$ jusqu'à $d$ faire :</td><td></td></tr><tr><td>10: si $j \neq i$ alors :</td><td></td></tr><tr><td>11: $c_i \leftarrow c_i \oplus r_{i,j}$</td><td></td></tr><tr><td>12: renvoyer $\vec{c}$</td><td></td></tr></tbody></table>

Étant donné que la complexité de cet algorithme est quadratique (donc coûteuse),
les auteurs ont proposé de distinguer le cas particulier ou $a = b$. En effet, l'exponentiation avec un exposant de la forme $q^n$ dans un corps $\mathbb{F}_q$ est toujours linéaire.

### 1.1.2.4 L'exponentiation

Les algorithmes précédents (RPAdd, RPMult et RPMult2) sont suffisants pour masquer les transformations AddRoundKey et (Inv)MixColumns. Cependant, la transformation (Inv)SubBytes (les équations 1.7 et 1.8 pages : 34, 35) est composée d'un autre type d'opérations qui est l'inverse ($x \to x^{-1}$).

Soit : $K = \mathbb{F}_2[\alpha]/P(\alpha)$, le corps fini utilisé dans l'AES, nous avons :

$$ \forall x \in K, \quad x^{-1} = x^{254}. $$

#### Propriété 9

Soient $\mathbb{F}_{p^k}$ un corps fini de caractéristique $p$ premier, et $n$ un entier naturel. La fonction $f(x) = x^{p^n}$ est linéaire dans $\mathbb{F}_{p^k}$. Par conséquent :

$$ \forall d \in \mathbb{N}^*, \forall a_0, \dots, a_d \in \mathbb{F}_{p^k}, (a_0 + \dots + a_d)^{p^n} = a_0^{p^n} + \dots + a_d^{p^n}. $$

Nous pouvons distinguer deux types d'exponentiation. D'abord l'exponentiation avec un exposant de la forme $p^n$ (dans notre cas $p = 2$ et $n = 8$), ce type de puissance est linéaire dans $\mathbb{F}_{p^n}$ d'après la propriété 9, elle est donc plus facile à calculer. Pour ce faire, il suffit d'appliquer l'exponentiation à chacune des parts indépendamment.

**Algorithm 6 RPExp2**

**Complexité** : $n \cdot d$ multiplications

1: **entrée** : $\vec{a} = \text{RPMaskByte}(a)$ et un entier de la forme $2^n$
2: **sortie** : $\vec{c} = \text{RPMaskByte}(a^{2^n})$
3: **pour** $i = 0$ **jusqu'à** $d$ **faire** :
4:     $c_i = a_i^{2^n}$
5: **renvoyer** $\vec{c}$

L'autre type d'exponentiation, ce sont toutes les autres formes d'exposant qui ne sont pas des puissances de 2. Pour nous le but est de calculer $a^{254}$ en utilisant les deux algorithmes RPMult et RPExp2. On remarque que ce dernier algorithme est beaucoup moins gourmand en termes de complexité que le premier. RIVAIN et PROUFF ont donc présenté un algorithme d'exponentiation pour l'exposant 254 qui utilise le moins de multiplications possible et plus de carrés.
<table><caption>**Algorithm 7 RPInverse** Complexité : $4d^2 + 15d + 4$ multiplications $8d^2 + 12d$ additions</caption><tr><td>1:</td><td>entrée : $\vec{a} = \text{RPMaskByte}(a)$</td><td></td></tr><tr><td>2:</td><td>sortie : $\vec{c} = \text{RPMaskByte}(a^{-1})$</td><td></td></tr><tr><td>3:</td><td>$\vec{z} \leftarrow \text{RPExp2}(\vec{a}, 2)$</td><td>$z \leftarrow a^2$</td></tr><tr><td>4:</td><td>RPRefresh($\vec{z}$)</td><td></td></tr><tr><td>5:</td><td>$\vec{c} \leftarrow \text{RPMult}(\vec{z}, \vec{a})$</td><td>$c \leftarrow a^3$</td></tr><tr><td>6:</td><td>$\vec{w} \leftarrow \text{RPExp2}(\vec{c}, 4)$</td><td>$w \leftarrow a^{12}$</td></tr><tr><td>7:</td><td>RPRefresh($\vec{w}$)</td><td></td></tr><tr><td>8:</td><td>$\vec{c} \leftarrow \text{RPMult}(\vec{c}, \vec{w})$</td><td>$c \leftarrow a^{15}$</td></tr><tr><td>9:</td><td>$\vec{c} \leftarrow \text{RPExp2}(\vec{c}, 16)$</td><td>$c \leftarrow a^{240}$</td></tr><tr><td>10:</td><td>$\vec{c} \leftarrow \text{RPMult}(\vec{c}, \vec{w})$</td><td>$c \leftarrow a^{252}$</td></tr><tr><td>11:</td><td>$\vec{c} \leftarrow \text{RPMult}(\vec{c}, \vec{z})$</td><td>$c \leftarrow a^{254}$</td></tr><tr><td>12:</td><td>renvoyer $\vec{c}$</td><td></td></tr></table>

Pour bien assurer le niveau de sécurité souhaité il est important que les entrées de la fonction `RPMult` soient indépendantes, d'où le besoin d'ajouter une fonction de rafraîchissement. En effet, la non-utilisation de la fonction `RPRefresh` de la ligne 4 par exemple impactera le calcul de $\vec{c}$ de la ligne 5, nous remarquons qu'à cette ligne l'algorithme multiplie $\vec{a} = (a_0, a_1, ..., a_d)$ par $\vec{z} = (a_0^2, a_1^2, ..., a_d^2)$. Donc pour camoufler cette dépendance entre $\vec{a}$ et $\vec{z}$, il est primordial d'insérer une fonction de rafraîchissement. Pour ce faire, l'algorithme `RPRefresh` permet de générer des masques aléatoires $r_1, ..., r_d$, et les appliquer à la donnée masquée.

Soit $a = a_0 \oplus \bigoplus_{i=1}^{d} a_i$, nous avons : $a = a_0 \oplus (r_1 \oplus \cdots \oplus r_d) \oplus \bigoplus_{i=1}^{d} a_i \oplus r_i$, nous obtenons ainsi un autre mot masqué $\vec{a} = (a_0 \oplus (r_1 \oplus \cdots \oplus r_d), a_1 \oplus r_1, ..., a_d \oplus r_d)$.

<table><caption>**Algorithm 8 RPRefresh** Complexité : $2d$ additions</caption><tr><td>1:</td><td>entrée : $\vec{a} = \text{RPMaskByte}(a)$</td><td></td></tr><tr><td>2:</td><td>sortie : $\vec{c} = \text{RPMaskByte}(a)$</td><td></td></tr><tr><td>3:</td><td>$c_0 \leftarrow x_0$</td><td></td></tr><tr><td>4:</td><td>pour $i = 1$ jusqu'à $d$ faire :</td><td></td></tr><tr><td>5:</td><td>$r \leftarrow \mathbb{F}_{2^8}$</td><td></td></tr><tr><td>6:</td><td>$c_0 \leftarrow c_0 \oplus r$</td><td></td></tr><tr><td>7:</td><td>$c_i \leftarrow x_i \oplus r$</td><td></td></tr><tr><td>8:</td><td>renvoyer $\vec{c}$</td><td></td></tr></table>

### 1.1.2.5 Le masquage de l'AES

Comme nous l'avons présenté dans la section 1.7, l'AES est composé de quatre transformations qui s'exécutent dans un ordre spécifique et de manière itérative
# CHAPITRE 1. L'ÉTAT DE L'ART SUR LE MASQUAGE

(voir 1.12). Les deux transformations **MixColumns** et **AddRoundKey** représentent la partie linéaire du programme, et c'est la partie la plus facile à masquer. Tandis que **SubBytes** représente la partie non-linéaire qui par conséquent est plus difficile à masquer.

L'AES opère sur une matrice d'octets $(M_{i,j})_{1\le i,j\le 4}$ dans $\mathbb{F}_{2^8}$. Notons : $(\vec{M}_{i,j})_{1\le i,j\le 4}$ la matrice masquée associée à un message $M$ pour le tour en cours, et $(\vec{K}_{i,j})_{1\le i,j\le 4}$ la matrice masquée de la clé $K$ pour le même tour, i.e. $\vec{M}_{i,j} = (M_{i,j,0}, \dots, M_{i,j,d})$ tel que : $M_{i,j} = \bigoplus_{z=0}^{d} M_{i,j,z}$ et $\vec{K}_{i,j} = (K_{i,j,0}, \dots, K_{i,j,d})$ telle que : $K_{i,j} = \bigoplus_{z=0}^{d} K_{i,j,z}$. Nous rappelons que l'objectif dans cette construction est de concevoir pour chaque transformation $f$ de l'AES une transformation alternative $f'$ telle que :

$$f'(\text{mask}(a)) = \text{mask}(f(a)).$$

**Algorithm 9 RPMask**

Complexité : 16d additions

1: **entrée** : une matrice $M \in \mathbb{F}_{2^8}^{4 \times 4}$ et l'ordre du masquage $d$

2: **sortie** : $\vec{M} \in (\mathbb{F}_{2^8}^{d+1})^{4 \times 4}$ tel que $\vec{M}_{i,j} = \text{RMMaskByte}(M_{i,j}, d)$

3: **pour** $i = 1$ **jusqu'à** 4 **faire** :

4: &nbsp;&nbsp;&nbsp;&nbsp;**pour** $j = 1$ **jusqu'à** 4 **faire** :

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\vec{M}_{i,j} \leftarrow \text{RPMaskByte}(M_{i,j}, d)$

6: **renvoyer** $\vec{M}$

Pour masquer l'opération **AddRoundKey**, il suffit d'additionner grâce à l'algorithme **RPAdd** chaque octet de la matrice intermédiaire $\vec{M}$ avec son équivalent dans la matrice qui correspondant à la clé de session $\vec{K}$.

**Algorithm 10 RPAddRoundKey**

Complexité : 16(d + 1) additions

1: **entrée** : $\vec{M} = \text{RPMask}(M)$ et $\vec{K} = \text{RPMask}(K)$

2: **sortie** : $\vec{C}$ tel que $\vec{C} = \text{RPMask}(\text{AddRoundKey}(M, K))$

3: **pour** $i = 1$ **jusqu'à** 4 **faire** :

4: &nbsp;&nbsp;&nbsp;&nbsp;**pour** $j = 1$ **jusqu'à** 4 **faire** :

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\vec{C}_{i,j} \leftarrow \text{RPAdd}(\vec{M}_{i,j}, \vec{K}_{i,j})$

6: **renvoyer** $\vec{C}$

L'algorithme **MixColumns** consiste à multiplier la matrice intermédiaire $\vec{M}$ par la matrice prédéfinie :

$$L = \begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{bmatrix}.$$
La version masquée de l'algorithmme MixColumns consistera donc à remplacer la multiplication ordinaire par RPMult2.

**Algorithm 11** RPMixColumns
64(d + 1) additions

Complexité : 64(d + 1) multiplications et

1: **entrée** : $\vec{M} = \text{RPMask}(M)$

2: **sortie** : $\vec{C}$ tel que $\vec{C} = \text{RPMask}(\text{MixColumns}(M))$

3: **pour** $i = 1$ **jusqu'à** 4 **faire** :

4: &nbsp;&nbsp;&nbsp;&nbsp;**pour** $j = 1$ **jusqu'à** 4 **faire** :

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\vec{C}_{i,j} \leftarrow \vec{0}$

6: &nbsp;&nbsp;&nbsp;&nbsp;**pour** $u = 1$ **jusqu'à** 4 **faire** :

7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\vec{C}_{i,j} \leftarrow \text{RPAdd}(\text{RPMult2}(\vec{M}_{i,u}, L_{u,j}), C_{i,j})$

8: **renvoyer** $\vec{C}$

Étant donné que l'algorithmme SubBytes opère sur les octets de la matrice intermédiaire $\vec{M}$ de manière indépendante, alors il suffira de concevoir un algorithme qui permettra de masquer la transformation pour un seul octet, et l'appliquer ensuite sur les seize octets de la matrice $\vec{M}$.

Soient $a = \bigoplus_{i=0}^{d} a_i \in \mathbb{F}_2^8$ une donnée sensible et $\vec{a} = \text{RPMaskByte}(a)$ un masqué associé à cette donnée. Nous noterons, $y = a^{-1}$ l'inverse de $a$ dans $\mathbb{F}_{2^8}$ (i.e. $ay = 1$) et $\vec{y} = \text{RPMaskByte}(y)$. L'opération SubBytes consiste à calculer $c = S(a)$ tel que :

$$c_j = y_j \oplus y_{(j+4) \bmod 8} \oplus y_{(j+5) \bmod 8} \oplus y_{(j+6) \bmod 8} \oplus y_{(j+7) \bmod 8} \oplus 63_j,$$

avec $c_j$ désigne le $i^{eme}$ bit de l'octet $c$. Ainsi, nous obtiendrons :

$$ \begin{align*} c_j &= (y_0)_j \oplus (y_0)_{(j+4) \bmod 8} \oplus (y_0)_{(j+5) \bmod 8} \oplus (y_0)_{(j+6) \bmod 8} \oplus (y_0)_{(j+7) \bmod 8} \oplus : b_0 \\ & (y_1)_j \oplus (y_1)_{(j+4) \bmod 8} \oplus (y_1)_{(j+5) \bmod 8} \oplus (y_1)_{(j+6) \bmod 8} \oplus (y_1)_{(j+7) \bmod 8} \oplus : b_1 \\ & \vdots \\ & (y_d)_j \oplus (y_d)_{(j+4) \bmod 8} \oplus (y_d)_{(j+5) \bmod 8} \oplus (y_d)_{(j+6) \bmod 8} \oplus (y_d)_{(j+7) \bmod 8} \oplus : b_d \\ &= b_0 \oplus \cdots \oplus b_d \oplus 63. \end{align*} $$

Nous pouvons donc considérer $\vec{b} = (b_0 \oplus 63, b_1, \dots, b_d) = \text{RPMaskByte}(S(a))$.
# CHAPITRE 1. L'ÉTAT DE L'ART SUR LE MASQUAGE

## Algorithm 12 RPSubByte

8d² + 43d + 33 additions

Complexité : 4d² + 15d + 4 multiplications et

1. entrée : $\vec{a} = RPMaskByte(a)$

2. sortie : $\vec{c}$ tel que $\vec{c} = RPMaskByte(SubByte(c))$

3. $\vec{y} \leftarrow RPInverse(\vec{a})$

4. $\vec{c} \leftarrow \vec{0}$

5. pour $i = 0$ jusqu'à $d$ faire :

6. pour $j = 0$ jusqu'à 8 faire :

7. $((c_i)_j \leftarrow (y_i)_j \oplus (y_i)_{(j+4) \bmod 8} \oplus (y_i)_{(j+5) \bmod 8} \oplus (y_i)_{(j+6) \bmod 8} \oplus (y_i)_{(j+7) \bmod 8}) \bmod 8$

8. $c_0 \leftarrow c_0 \oplus 63$

9. renvoyer $\vec{x}'$

La ligne 5 de l'algorithme permet de parcourir les shares de $\vec{c}$, tandis que la ligne 6 permet de parcourir les bits.

Pour résumer, voici la complexité totale des quatre transformations de l'AES, en fonction du nombre d'additions et multiplications dans $\mathbb{F}_{2^8}$.

<table><caption>TABLE 1.1 – Le nombre d'opérations pour chacune des transformations de l'AES avec la méthode masquage RP.</caption><thead><tr><th></th><th>La multiplication</th><th>L'addition</th></tr></thead><tbody><tr><td>SubBytes</td><td>64d<sup>2</sup> + 240d + 64</td><td>128d<sup>2</sup> + 688d + 528</td></tr><tr><td>ShiftRows</td><td>0</td><td>0</td></tr><tr><td>MixColumns</td><td>64(d + 1)</td><td>64(d + 1)</td></tr><tr><td>AddRoundKey</td><td>0</td><td>16(d + 1)</td></tr></tbody></table>
1.2 Le masquage basé sur les polynômes

Le masquage basé sur les polynômes a été introduit séparément par PROUFF et ROCHE [PR11], et GOUBIN et MARTINELLI [GM11]. Cette méthode combine d'une part le schéma de SHAMIR sur le partage du secret “Shamir's Secret Sharing Scheme” (SSS) [Sha79], qui permet de partager un secret entre un groupe d'entités, et d'autre part les techniques sécurisées de calcul multipartite [BGW88].

1.2.1 Le schéma de Shamir sur le partage du secret

Les schémas de partage du secret peuvent être très utiles pour la gestion des clés cryptographiques. Afin de protéger les données, nous pouvons les chiffrer, mais pour protéger la clé secrète, nous avons besoin d'une méthode différente. Dans son livre "Introduction To Combinatorial Mathematics" [Liu68] LIU avait introduit le problème suivant :

Onze scientifiques travaillent sur un projet secret. Ils souhaitent verrouiller les documents dans un cabinet afin que le cabinet puisse être ouvert si et seulement si six ou plus des scientifiques sont présents. Quel est le plus petit nombre de serrures nécessaires ? Quel est le plus petit nombre de clés pour les verrous que chaque scientifique doit porter ?

Il est facile de constater que dans le cas de ce problème, le nombre minimal de serrures nécessaire est : $\binom{11}{6} = 462$ et le nombre minimal de clés par personne est $\binom{10}{5} = 252$. Cependant, cette solution reste théorique à cause du nombre exponentiel de clés nécessaires, et qui devient de plus en plus important lorsque le nombre d'utilisateurs augmente. Pour répondre à cette problématique d'un point de vue cryptographique SHAMIR a proposé un schéma de partage du secret qui nécessite un nombre de clés constant, dans ce schéma chaque utilisateur possède une seule clé quel que soit le nombre d'utilisateurs. Dans son article [Sha79], SHAMIR a présenté un schéma qui permet de diviser une donnée $m$ en $n$ morceaux de telle sorte que $m$ soit facilement reconstruite à partir de $d + 1$ morceaux quels qu'ils soient (avec $d < n$), mais même une connaissance complète de $d$ morceaux ne révèle absolument aucune information sur la donnée secrète $m$.

Soit $f : F \to E$ une fonction polynomiale de degré $d$ définie par : $f(x) = c_0 + \sum_{i=1}^{d} c_i x^i$. Soient $\alpha_1, \alpha_2, \dots, \alpha_n \in F^*$ des valeurs distinctes non nulles, avec un nombre $n$ d'utilisateurs strictement inférieur au cardinal de $F$. Nous noterons $\beta_i = f(\alpha_i) \in E$ l'image de $\alpha_i$ par $f$ pour $1 \le i \le n$. Le schéma SSS consiste à protéger l'information $c_0$ (le coefficient de degré 0 de $f$) et la rendre accessible si et seulement si au moins $d+1$ utilisateurs réunissent leurs clés. Pour ce faire, il suffit de transmettre à chaque utilisateur une clé privée $\beta_i$ (l'entrée $\alpha_i$ peut être supposée publique), et maintenir la fonction $f$ secrète pour tous les utilisateurs.
<figure><img src="image_20.png" /></figure>

Ainsi, par interpolation, pour construire $f$ et trouver le coefficient $c_0$ (sachant que $c_0 = f(0)$) il faut et il suffit d'avoir au moins $d+1$ entrées et leurs images par $f$.

**Définition 19 (L'interpolation de Lagrange)**

Étant donné un ensemble de $n + 1$ points : $(\alpha_0, \beta_0), \dots, (\alpha_n, \beta_n)$ dans $F \times E$, tels que tous les $\alpha_i$ sont différents, il existe un polynôme unique $f$ de degré $n$ tel que $f(\alpha_i) = \beta_i$ avec $0 \le i \le n$. Ce polynôme s'appelle *le polynôme d'interpolation de Lagrange*, et il est défini par la formule suivante :

$$f(x) = \sum_{j=0}^{n} \beta_j \left( \prod_{i=0, i \neq j}^{n} \frac{x - \alpha_i}{\alpha_j - \alpha_i} \right).$$

Pour vérifier cette formule, il suffit de remarquer que :

$$\prod_{i=0, i \neq j}^{n} \frac{x - \alpha_i}{\alpha_j - \alpha_i} = \begin{cases} 1 & \text{si } x = \alpha_j \\ 0 & \text{si } x \neq \alpha_j \end{cases},$$

donc, pour n'importe quel $\alpha_k$ nous avons :

$$\begin{aligned} f(\alpha_k) &= \beta_k \underbrace{\left( \prod_{i=0, i \neq k}^{n} \frac{\alpha_k - \alpha_i}{\alpha_k - \alpha_i} \right)}_{=1} + \sum_{j=0, j \neq k}^{n} \beta_j \underbrace{\left( \prod_{i=0, i \neq j}^{n} \frac{\alpha_k - \alpha_i}{\alpha_j - \alpha_i} \right)}_{=0} \\ &= \beta_k \end{aligned}$$

Il est également possible d'interpréter $f$ comme un système d'équations défini par :

$$\underbrace{\begin{bmatrix} 1 & \alpha_0 & \alpha_0^2 & \dots & \alpha_0^d \\ 1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^d \\ \vdots & & \vdots & & \vdots \\ 1 & \alpha_d & \alpha_d^2 & \dots & \alpha_d^d \end{bmatrix}}_{A} \times \underbrace{\begin{bmatrix} c_0 \\ c_1 \\ \vdots \\ c_d \end{bmatrix}}_{C} = \underbrace{\begin{bmatrix} \beta_0 \\ \beta_1 \\ \vdots \\ \beta_d \end{bmatrix}}_{B} \quad (1.1)$$
Étant donné que les $\alpha_i$ sont tous distincts et non nuls, la matrice $A$ (qui est publique) est donc inversible et nous pourrons ainsi calculer les coefficients de $f$ donnés par : $C = A^{-1} \times B$. Comme nous pouvons le constater, ce système n'est soluble que si nous avons réuni au moins $d + 1$ clés $(\alpha_i, \beta_i)$, et le nombre de clés pour chaque utilisateur reste constant quel que soit le nombre d'utilisateurs au total.

Cette façon d'encoder l'information en utilisant des systèmes d'équations linéaires a été introduite initialement par REED et SOLOMON dans leur célèbre article sur le code de Reed-Solomon [RS60].

### 1.2.2 Les codes de Reed-Solomon

Un code Reed-Solomon (RS) est un code correcteur d'erreurs décrit pour la première fois dans un article de REED et SOLOMON en 1960 [RS60]. Grace à leurs distance minimale optimale, les codes RS ont été utilisés pour protéger les information sur les CD-ROM, les DVD, les communications sans fil, les communications spatiales, etc.

Il existe différentes procédures de codage pour les codes RS et, par conséquent, il existe différentes façons de décrire l'ensemble des mots de code. Dans la vue originale de REED et SOLOMON, dans un code RS de paramètres $[n, k, d]$ chaque mot de code est une séquence de valeurs de fonction d'un polynôme de degré inférieur à $k$. Pour obtenir un mot de code, le message est interprété comme la description d'un polynôme $P$ de degré inférieur à $k$ sur le corps fini $\mathbb{F}_q$. À son tour, le polynôme $P$ est évalué en $k \le n \le q$ points distincts.

L'idée consiste à considérer le mot source $m = (m_0, \dots, m_{k-1})$ comme un polynôme sur un corps fini, où les symboles qui composent le message (par exemple, les octets) sont des coefficients de ce polynôme $P_m(x) = m_0 + m_1 x^1 + \dots + m_{k-1} x^{k-1}$. Ainsi, le mot de code associé à $m$ est $c = (P_m(x_i))_{1 \le i \le n}$, où $x_i$ sont des points distincts de $\mathbb{F}_q$. Pour reconstruire le polynôme $P_m(x)$ il suffit d'obtenir $k$ points $(x_i, P_m(x_i))$, on en déduit alors que la distance minimale d'un code RS est $n - k + 1$ et sa capacité de correction vaut : $\lfloor \frac{n-k}{2} \rfloor$. Ainsi, les codes RS atteignent bien la borne de Singleton, et sont alors des codes MDS.

### 1.2.3 Le masquage basé sur le partage du secret

Le masquage booléen comme celui que nous avons présenté précédemment permet de sécuriser efficacement les implémentations contre les SCA du premier ordre. Il est cependant particulièrement vulnérable aux SCA d'ordre supérieur en raison des propriétés physiques intrinsèques des dispositifs électroniques [Mes00]. En 2011, GOUBIN et MARTINELLI [GM11] en parallèle avec PROUFF et ROCHE [PR11] ont présenté une nouvelle méthode de masquage basée sur le schéma SSS de la section
# CHAPITRE 1. L'ÉTAT DE L'ART SUR LE MASQUAGE

précédente. Le masquage d'une information sensible $a \in \mathbb{F}_{2^s}$ consiste à générer une fonction $f_a : \mathbb{F}_{2^s} \to \mathbb{F}_{2^s}$ de degré $d$ telle que $f(x) = a + \sum_{i=1}^d c_i x^i$, et renvoyer le vecteur $\vec{a} = (f_a(\alpha_1), \dots, f_a(\alpha_n))$ avec $\alpha_1, \dots, \alpha_n$ des éléments publics dans $\mathbb{F}_{2^s}$ et $n = 2d + 1$.

Soit $A$ une matrice dans $\mathbb{F}_{2^s}^{n \times n}$ définie par :

$$A_{i,j} = \alpha_i^j. \qquad (1.2)$$

Pour masquer une valeur sensible $a$, il suffit générer un vecteur aléatoire $\vec{c} \in \mathbb{F}_{2^s}^n$ tel que $c_0 = a$, et calculer ensuite :

$$\mathbf{mask}(a) = A \cdot \vec{c}. \qquad (1.3)$$

<table><thead><tr><th>Algorithm 13 mask</th><th>Complexité : n<sup>2</sup> multiplications et n<sup>2</sup> additions</th></tr></thead><tbody><tr><td>1: entrée : a &isin; F<sub>2s</sub></td><td></td></tr><tr><td>2: sortie : a &isin; F<sub>2s</sub><sup>n</sup></td><td></td></tr><tr><td>3: c &larr; <sup>$</sup>&#x2213; F<sub>2s</sub><sup>n</sup></td><td>Génération des coefficients de f</td></tr><tr><td>4: c<sub>0</sub> &larr; a</td><td>Le premier coefficient vaut a</td></tr><tr><td>5: a &larr; A &middot; c</td><td></td></tr><tr><td>6: renvoyer a</td><td></td></tr></tbody></table>

Pour démasquer nous avons besoin d'extraire le premier élément du vecteur $\vec{c}$ de l'algorithme 13. Nous avons : $\vec{c} = A^{-1} \cdot \vec{a}$, donc :

$$a = \langle A_0^{-1}, \vec{a} \rangle, \qquad (1.4)$$

avec $A_0^{-1}$ correspond à la première ligne de la matrice inverse de $A$.

<table><thead><tr><th>Algorithm 14 unmask</th><th>Complexité : n multiplications et n additions</th></tr></thead><tbody><tr><td>1: entrée : a &isin; F<sub>2s</sub><sup>n</sup></td><td></td></tr><tr><td>2: sortie : a &isin; F<sub>2s</sub><sup>n</sup></td><td></td></tr><tr><td>3: renvoyer &lang;A<sub>0</sub><sup>-1</sup>, a&rang;</td><td></td></tr></tbody></table>

Nous remarquons que cette méthode de masquage consiste à utiliser les codes de Reed-Solomon pour protéger l'information, et comme $n = 2k + 1 > k$, cette méthode permet de détecter jusqu'à $k + 1$ erreur. Ainsi, ce masquage a l'avantage de profiter de nombreux résultats déjà publiés sur ce code.

## Propriété 10

Le masquage basé sur le partage du secret est une généralisation du masquage booléen.
Pour démontrer cette propriété, il suffit de constater que le cas particulier $A_0^{-1} = (1, \dots, 1)$ est un masquage booléen.

Le code RS étant linéaire, le masquage de l'addition et la multiplication par un scalaire sont triviales. Cependant, le produit de deux masqués ne peut pas être résolu avec la propriété linéaire de la transformation car la multiplication de deux polynômes de même degré donne un polynôme de degré double du polynôme d'origine. GOUBIN et MARTINELLI, ainsi que PROUFF et ROCHE ont proposé deux approches différentes pour calculer la multiplication en utilisant le schéma de calcul multipartite BGW [BGW88, GRR98] qui utilise $2d + 1$ parts (d'ou le choix $n = 2d + 1$).

### 1.2.4 Le schéma sécurisé de calcul multipartite BGW

BEN-OR, GOLDWASSER et WIGDERSON [BGW88] ont présenté une méthode simple pour réduire le degré de la fonction $h(x) = f_a(x)f_b(x)$. Le but de ce schéma est de calculer de manière sécurisé $(f_{ab}(\alpha_1), \dots, f_{ab}(\alpha_n))$ à partir de $(f_a(\alpha_1), \dots, f_a(\alpha_n))$ et $(f_b(\alpha_1), \dots, f_b(\alpha_n))$. Soit :

$$h(x) = h_0 + h_1x + \dots + h_dx^d + \dots + h_{2d}x^{2d},$$

avec $h_0 = ab$, et soit : $\vec{s} = (s_0, \dots, s_{2d})$ tel que $s_i = h(\alpha_i) = f_a(\alpha_i)f_b(\alpha_i)$. Soit $k(x)$ une troncature de $h$ définie par :

$$k(x) = h_0 + h_1x + \dots + h_dx^d.$$

L'objectif est donc de trouver le vecteur $\vec{r} = (r_0, \dots, r_{2d})$ tel que : $r_i = k(\alpha_i)$.

**Proposition 1 ([BGW88])**

Soient $\vec{s} = (s_0, \dots, s_{2d})$ et $\vec{r} = (r_0, \dots, r_{2d})$ définis ci-dessus, il existe une matrice constante $M \in \mathbb{F}^{2d \times 2d}$ telle que :

$$\vec{r} = M\vec{s}.$$

**Preuve :**

Soient $\vec{h} = (h_0, \dots, h_{2d}) \in \mathbb{F}^{2d}$, $\vec{k} = (h_0, \dots, h_d, 0, \dots, 0) \in \mathbb{F}^{2d}$, $A \in \mathbb{F}^{2d \times 2d}$ telle que $A_{i,j} = \alpha_i^j$ et $P \in \mathbb{F}^{2d \times 2d}$ une matrice de projection telle que :

$$P \cdot (x_0, \dots, x_{2d}) = (x_0, \dots, x_d, 0, \dots, 0).$$

Nous avons :

$$\begin{aligned} \vec{r} &= A\vec{k} \\ &= AP\vec{h} \\ &= (APA^{-1})\vec{s}, \end{aligned}$$
car $\mathcal{A}$ est une matrice inversible.

Grâce à cette proposition nous pouvons construire une fonction $k$ de degré $d$ et
calculer le vecteur $\vec{r} = k(\vec{\alpha})$ à partir des masques de $a$ et $b$. Cependant, comme
nous l'avons mentionné auparavant, les coefficients de $k$ ne sont pas aléatoires, et
donc, par mesure de sécurité il faudra rafraîchir le masque obtenu. Pour ce faire,
l'idée consiste à construire un polynôme $k'(x) = k(x) + q(x)$, avec $q$ un polynôme
aléatoire défini par $q(x) = \sum_{i=1}^{2d} q_i x^i$ (On note que le coefficient de degré zéro est
nul). Cela revient à additionner un masqué du produit $ab$ (qui est le polynôme $k$)
et le masqué de l'élément $0$ (qui est le polynôme $q$).

1.2.5 L’algorithme de multiplication de Prouff et Roche

Soient $a$ et $b$ deux valeurs sensibles, et $(f_a(\alpha_i))_{1\le i\le n}$ et $(f_b(\alpha_i))_{1\le i\le n}$, les parts associées à $a$ et $b$. Pour mieux visualiser l’algorithme de multiplication de PROUFF et ROCHE il faudra imaginer $n$ joueurs, tels que chaque joueur $i$ possède deux parts $f_a(\alpha_i)$ et $f_b(\alpha_i)$, et calcule $w_i = f_a(\alpha_i)f_b(\alpha_i)$ pour construire un polynôme de degré $2d$ dont le coefficient de degré zéro est $ab$, ensuite, chaque joueur va “masquer” $w_i$ en générant un polynôme $Q_i = w_i + \sum_{k=1}^d r_k \alpha_j^k$, et partager $Q_i(\alpha_j)$ avec chaque joueur $j$. Enfin, chaque joueur pourra “démasquer” le vecteur $Q_{*,i}$ (qui correspond à la $i$ème colonne de $Q$) qu’il a reçu pour en extraire sa part $f'_{ab}(\alpha_i)$.

**Algorithm 15 Mult**
**Complexité** : $n^2(d+1) + n$ multiplications et $n^2(d+2)$ additions

1: **entrée** : mask(a), mask(b) = (f_a(α_i))_{1≤i≤n}, (f_b(α_i))_{1≤i≤n} ∈ F_{2^s}^n.

2: sortie : mask(ab).

3: $Q \in \mathbb{F}_{2^s}^{n \times n}$

4: $\vec{w} \in \mathbb{F}_{2^s}^n$

5: **pour** $i = 1$ **jusqu'à** $n$ **faire** :

6: $w_i \leftarrow f_a(\alpha_i)f_b(\alpha_i)$

7: $r \leftarrow \mathbb{F}_{2^s}^d$

8: **pour** $j = 1$ **jusqu'à** $n$ **faire** :

9: $Q_{i,j} \leftarrow w_i + \sum_{k=1}^{d} r_k \alpha_j^k$ Masquage de $w_i$

10: $\vec{c} \in \mathbb{F}_{2^s}^n$

11: **pour** $i = 1$ **jusqu'à** $n$ **faire** :

12: $c_i \leftarrow \text{unmask}(Q_{*,i})$

13: renvoyer $\vec{c}$
# 1.3 Le masquage basé sur le produit scalaire (IPM)

Le masquage IPM (Inner Product Masking) ou le masquage basé sur le produit scalaire a été introduit par BALASCH et al. en 2012 [BFGV12, BFG15]. Comme son nom l'indique, l'opération de masquage consiste à générer deux vecteurs $\vec{u}$ et $\vec{v}$ de longueur $d + 1$ tels que leur produit scalaire vaut $m (\langle\langle \vec{u}, \vec{v} \rangle\rangle = m)$, avec $m$ désignant la donnée sensible. Ainsi, assurer une protection d'ordre $d$ contre SCA.

<table><thead><tr><th>Algorithm 16 IPmask</th><th>Complexité : n multiplications et n additions</th></tr></thead><tbody><tr><td>1: entrée : m ∈ F<sub>2s</sub>.</td><td></td></tr><tr><td>2: sortie : (ũ, ṽ) tels que &lt;ũ, ṽ&gt; = m.</td><td></td></tr><tr><td>3: c ← 0 ∈ F<sub>2s</sub></td><td></td></tr><tr><td>4: pour i = 2 jusqu'à n faire :</td><td></td></tr><tr><td>5: u<sub>i</sub> ← $\mathbb{F}_{2s}^*$</td><td></td></tr><tr><td>6: v<sub>i</sub> ← $\mathbb{F}_{2s}^*$</td><td></td></tr><tr><td>7: c ← c ⊕ u<sub>i</sub>v<sub>i</sub></td><td></td></tr><tr><td>8: u<sub>1</sub> ← $\mathbb{F}_{2s}^*$</td><td></td></tr><tr><td>9: v<sub>1</sub> ← (m ⊕ c)u<sub>1</sub><sup>-1</sup></td><td></td></tr><tr><td>10: renvoyer (ũ, ṽ)</td><td></td></tr></tbody></table>

Si nous considérons le cas particulier $\vec{u} = \vec{1} = (1, \dots, 1)$, alors le masquage consistera à générer un vecteur $\vec{v} = (v_1, \dots, v_n)$ tel que : $\sum_{i=1}^n v_i = m$. Ainsi, nous retrouvons la méthode de masquage classique que nous avons abordé précédemment. De la même façon, nous avons vu dans l'équation 1.4 page 56, que le masquage basé sur le partage du secret consiste à calculer un produit scalaire entre le vecteur $\vec{a} = (f(\alpha_0), \dots, f(\alpha_d))$ et le vecteur $\vec{v} = A_0^{-1}$ qui correspond à la première ligne de l'inverse de la matrice $A$ définie dans l'équation 1.1. Nous constatons ainsi que :

### Propriété 11

Le schéma IPM est une généralisation du masquage classique et du masquage basé sur le partage du secret.

Dans le schéma original [BFGV12] les deux vecteurs $\vec{u}$ et $\vec{v}$ changent en permanence. Cependant, les auteurs ont proposé une autre version en 2015 [BFG15] dans laquelle le vecteur $\vec{u}$ est supposé public, avec $u_0 = 1$, et reste identique durant tout le calcul, ce choix permet d'optimiser la complexité algorithmique des calculs.
# CHAPITRE 1. L'ÉTAT DE L'ART SUR LE MASQUAGE

<caption>**Algorithm 17 IPmask2** Complexité : $n-1$ multiplications et $n-1$ additions</caption>

1: **entrée** : $m \in \mathbb{F}_{2^s}$.

2: **sortie** : $\vec{z}$ tel que $\langle \vec{u}, \vec{z} \rangle = m$.

3: $z \in \mathbb{F}_{2^s}^n$

4: $z_0 \leftarrow 0$

5: **pour** $i = 2$ **jusqu'à** $n$ **faire** :

6: $z_i \leftarrow \mathbb{F}_{2^s}^s$

7: $z_0 \leftarrow z_0 \oplus u_i z_i$

8: **renvoyer** $\vec{z}$

En fixant $\vec{u}$, on obtient un masquage linéaire :

$$ \langle \vec{u}, \vec{z} \rangle + \langle \vec{u}, \vec{z}' \rangle = \langle u, z + z' \rangle . $$

Pour calculer la multiplication nous considérons la matrice $L \in \mathbb{F}_{2^s}^{n \times n}$ définie par :

$$ \forall 1 \le i, j \le n, \quad L_{i,j} = u_i u_j . $$

<caption>**Algorithm 18 IPMult** Complexité : $3n^2 - n$ multiplications et $3n^2 - n - 1$ additions</caption>

1: **entrée** : $\vec{z} = \text{IPmask2}(m), \vec{z}' = \text{IPmask2}(m')$.

2: **sortie** : $\vec{y} = \text{IPmask2}(mm')$.

3: $A \stackrel{\$}{\leftarrow} \mathbb{F}_{2^s}^{n \times n} \mid \sum_{i=1}^n \sum_{j=1}^n L_{i,j} A_{i,j} = 0$

4: $R \in \mathbb{F}_{2^s}^{n \times n} \mid R_{i,j} = z_i z_j'$

5: $B \leftarrow R + A$

6: $b \leftarrow 0 \in \mathbb{F}_{2^s}$

7: **pour** $i = 2$ **jusqu'à** $n$ **faire** :

8: **pour** $j = 1$ **jusqu'à** $n$ **faire** :

9: $b \leftarrow b + L_{i,j} B_{i,j}$

10: **renvoyer** $\vec{y} = (B_{1,1} + b, B_{1,2}, \dots, B_{1,n})$

**Démonstration :**

Nous avons :

$$ \begin{aligned} b &= \sum_{i=2}^{n} \sum_{j=1}^{n} L_{i,j} B_{i,j} \\ &= \sum_{i=2}^{n} \sum_{j=1}^{n} u_i u_j (z_i z_j' + A_{i,j}) \\ &= \sum_{i=2}^{n} (u_i z_i \sum_{j=1}^{n} u_j z_j' + L_{i,j} A_{i,j}) \\ &= \sum_{i=2}^{n} (u_i z_i m' + \sum_{j=1}^{n} L_{i,j} A_{i,j}) \\ &= (m' \sum_{i=2}^{n} u_i z_i) + (\sum_{i=2}^{n} \sum_{j=1}^{n} L_{i,j} A_{i,j}) \\ &= m' (m - z_1) + \sum_{j=1}^{n} L_{1,j} A_{1,j} . \end{aligned} $$
## 1.3. LE MASQUAGE BASÉ SUR LE PRODUIT SCALAIRE (IPM)

Ainsi, nous obtenons :

$$ 
\begin{align*}
\langle \vec{u}, \vec{y} \rangle &= b + \sum_{i=1}^{n} u_i B_{1,i} \\
&= m'(m - z_1) + \sum_{j=1}^{n} L_{1,j} A_{1,j} + \sum_{i=1}^{n} u_i (R_{1,i} + A_{1,i}) \\
&= m'(m - z_1) + \sum_{j=1}^{n} L_{1,j} A_{1,j} + \sum_{i=1}^{n} u_i (z_1 z'_i + A_{1,i}) \\
&= m'(m - z_1) + \sum_{j=1}^{n} L_{1,j} A_{1,j} + (z_1 \sum_{i=1}^{n} u_i z'_i) + (\sum_{i=1}^{n} u_i A_{1,i}) \\
&= m'(m - z_1) + \sum_{j=1}^{n} L_{1,j} A_{1,j} + z_1 m' + \sum_{i=1}^{n} L_{1,i} A_{1,i} \\
&= mm'.
\end{align*}
$$

Pour construire la matrice A de la ligne 3, il suffit de tirer une matrice aléatoire $A \stackrel{\$}{\leftarrow} \mathbb{F}_{2^n}$ telle que :

$$ A_{n,n} = \left[ \sum_{j=1}^{n-1} \sum_{i=1}^{n} A_{i,j} L_{i,j} + \sum_{i=1}^{n-1} A_{i,n} L_{i,n} \right] L_{n,n}^{-1}. $$

Ainsi, le coût de cette opération est : $n^2$ multiplications et $n^2$ additions.

Enfin, il est toujours avantageux d'avoir une implémentation particulièrement efficace pour calculer le carré. Nous avons :

$$ 
\begin{align*}
m^2 &= \left( \sum_{i=1}^{n} u_i z_i \right)^2 \\
&= \sum_{i=1}^{n} (u_i z_i)^2 \\
&= \sum_{i=1}^{n} u_i (u_i z_i^2) .
\end{align*}
$$

Ainsi, on en déduit l'algorithmes suivant :

**Algorithm 19 Exp2**

Complexité : $2n$ multiplications

1: **entrée** : $\vec{z} = \text{IPmask2}(m)$.

2: **sortie** : $\vec{y} = \text{IPmask2}(m^2)$.

3: $\vec{y} \leftarrow \vec{0} \in \mathbb{F}_{2^s}^n$

4: **pour** $i = 1$ **jusqu'à** $n$ **faire** :

5: $y_i \leftarrow u_i z_i^2$

6: **renvoyer** $\vec{y}$
## 1.4 Le masquage basé sur les codes

Un inconvénient principal des schémas de masquage est la surcharge importante nécessaire à leur réalisation. Le coût des calculs est généralement important du fait du traitement du masque, et en particulier de la multiplication. De plus, les schémas de masquage supposent habituellement des masques aléatoires distribués uniformément, autrement dit, un générateur aléatoire suffisamment bon doit être implémenté en plus du système de chiffrement protégé. Par conséquent, le masquage ajoute généralement du temps et de l'espace à des implémentations cryptographiques aussi bien matérielles que logicielles.

Pour surmonter ces obstacles, il existe des schémas de masquage à faible entropie, ou ce qu'on appelle LEMS (Low Entropy Masking Schemes). Le but est d'offrir un compromis raisonnable entre la bonne protection contre les attaques SCA offerte par le masquage et le coût qui résulte de leur mise en œuvre. Pour mettre en œuvre de tels schémas, plusieurs solutions ont été proposées [PR07, CDG+14, CDGM12, Car13]. Une solution également appelée méthode RSM (Rotating Sbox Masking) [NSGD12] consiste à précalculer et stocker des boites S masquées qui correspondent à toutes les valeurs possibles de masques. D'autres consistent à calculer les boites S masquées pour le masque choisi ...

Dans cette section nous présentons une méthode simplifiée pour générer rapidement des masques uniformes. Cette méthode consiste à utiliser des codes correcteurs d'erreurs, et en particulier les codes linéaires.

### 1.4.1 Rappels

Soit $k$ et $n$ deux entiers naturels, tels que $k \le n$. On note $\mathbb{F}_2^n$ l'espace vectoriel de longueur $n$ dans $\mathbb{F}_2 = \{0, 1\}$. Soit $\mathcal{C}$ un sous espace vectoriel de $\mathbb{F}_2^n$ de dimension $k$, $\mathcal{C}$ est donc un code linéaire de longueur $n$ de dimension $k$.

**Définition 20 (espaces vectoriels supplémentaires)**

Soit $\mathcal{C}$ et $\mathcal{D}$ deux sous espaces vectoriels de $\mathbb{F}_2^n$. On dit que $\mathcal{C}$ et $\mathcal{D}$ sont supplémentaires, si tout vecteur de $\mathbb{F}_2^n$ s'écrit de manière unique comme la somme d'un vecteur de $\mathcal{C}$ et d'un vecteur de $\mathcal{D}$ :

$$ \forall z \in \mathbb{F}_2^n, \quad \exists! (c, d) \in \mathcal{C} \times \mathcal{D} \quad | \quad z = c + d, \qquad (1.5) $$

et on note $\mathbb{F}_2^n = \mathcal{C} \oplus \mathcal{D}$.

**Propriété 12**

Les propriétés suivantes sont équivalentes :

1. $\mathcal{C}$ et $\mathcal{D}$ sont supplémentaires,
2. l'application $\mathcal{C} \times \mathcal{D} \to \mathbb{F}_2^n, (c, d) \mapsto c+d$ est bijective,

3. $\mathcal{C} \cap \mathcal{D} = \{0\}$ et $\dim(\mathcal{C}) + \dim(\mathcal{D}) = n$.

**Preuve :**

— 1 ⇔ 2 : la surjectivité correspond à l'existence d'un couple $(c, d)$ dans $\mathcal{C} \times \mathcal{D}$, pour tout $z$ dans $\mathbb{F}_2^n$, et l'injectivité, correspond à l'unicité de $(u, v)$, qui est par définition le cas pour $\mathcal{C}$ et $\mathcal{D}$ supplémentaires.

— 1 ⇒ 3 : Supposons qu'il existe un vecteur $x \in \mathcal{C} \cap \mathcal{D}$. Par définition :

$$ \forall z \in \mathbb{F}_2^n, \quad \exists! (c, d) \in \mathcal{C} \times \mathcal{D} \mid z = c + d. $$

Or pour $z = 0$ nous avons : $z = 0 \oplus 0 = x \oplus x$, donc $x = 0$ car il existe un unique couple $(c, d)$. Ainsi, $\mathcal{C} \cap \mathcal{D} = \{0\}$, et puisque $\mathcal{C} \oplus \mathcal{D} = \mathbb{F}_2^n$ alors $\dim(\mathcal{C}) + \dim(\mathcal{D}) = n$.

— 1 ⇔ 3 : Nous avons : $\dim(\mathcal{C}) + \dim(\mathcal{D}) = \dim(\mathbb{F}_2^n) \Rightarrow \forall z \in \mathbb{F}_2^n, \exists (c, d) \in \mathcal{C} \times \mathcal{D} \mid z = c+d$, et puisque $\mathcal{C} \cap \mathcal{D} = \{0\}$, alors ce couple $(c, d)$ est unique.

<figure><img src="image_21.png" /></figure>

**Définition 21 (Le code dual)**

Soit $\mathcal{C}$ un code linéaire de $\mathbb{F}^n$. L'orthogonal de $\mathcal{C}$ est un espace vectoriel que l'on note $\mathcal{C}^{\perp}$ défini par :

$$ \mathcal{C}^{\perp} = \{d \in \mathbb{F}^n \mid \forall c \in \mathcal{C} \quad \langle d, c \rangle = 0\}. $$

Avec $\langle \cdot, \cdot \rangle$ désigne le produit scalaire usuel. Dans le cas des codes linéaires, on dit que $\mathcal{C}^{\perp}$ est le code dual de $\mathcal{C}$.

**Définition 22 (Les codes LCD [Mas92])**

Soit $\mathcal{C}$ un code linéaire de paramètres $[n, k, d_c]$, et $\mathcal{D}$ son code dual. On dit que $\mathcal{C}$ est un code LCD (Linear code with complementary dual) si $\mathcal{C}$ et $\mathcal{D}$ sont supplémentaires.

On notera pour la suite $G$ et $H$ les matrices génératrices de $\mathcal{C}$ et $\mathcal{D}$ respectivement.

**Propriété 13**

Soient $\mathcal{C}$ un code linéaire de paramètres $[n, k, d_c]$, et $G$ sa matrice génératrice. $\mathcal{C}$ est un code LCD si et seulement si la matrice $GG^{\top}$ est inversible.

**Preuve :**

Pour démontrer cette propriété nous allons démontrer chaque implication. Dans le théorème 12 nous avons montré qu'un code $\mathcal{C}$ est LCD si et seulement si $\mathcal{C} \cap \mathcal{D} = \{0\}$, il suffit donc de démontrer les implications suivantes :
1. $GG^T$ est inversible $\implies \mathcal{C} \cap \mathcal{D} = \{0\}$;

2. $GG^T$ n'est pas inversible $\implies \mathcal{C} \cap \mathcal{D} \neq \{0\}$ (la contraposée de $\mathcal{C} \cap \mathcal{D} = \{0\} \implies GG^T$ est inversible).

1. Soit $x \in \mathbb{F}_2^k$ un mot source et $c = xG \in \mathcal{C}$ le mot de code associé à $x$, nous avons : $cG^\top(\tilde{G}G^\top)^{-1}G = xGG^\top(GG^\top)^{-1}G = xG = c$. Ainsi, si en plus $c \in \mathcal{D}$ (i.e. $cG^\top = 0$) alors : $cG^\top(GG^\top)^{-1}G = c = 0$.

2. Inversement, si nous supposons que $GG^\top$ n'est pas inversible, alors il existe un vecteur non-nul $x \in \mathbb{F}_2^k$ tel que $x(GG^\top) = 0$. Soit $c = xG \in \mathcal{C}$ le mot de code associé à $x$. Nous avons $\forall x' \in \mathbb{F}_2^k$ :

$$ \begin{aligned} \langle xG, x'G \rangle &= xG(x'G)^\top \\ &= xGG^\top x'^\top \\ &= 0. \end{aligned} $$

Donc $c$ est aussi un mot du dual, ce qui implique que dans ce cas $\mathcal{C} \cap \mathcal{D} \neq \{0\}$. ■

Soit $\mathcal{C}$ un code LCD de paramètres $[n, k, d_c]$, il existe une projection orthogonale de l'espace vectoriel $\mathbb{F}_2^n$ vers $\mathbb{F}_2^k$ définie par :

$$ \Pi_{\mathcal{C}} = G^{\top}(GG^{\top})^{-1}. \qquad (1.6) $$

En parallèle, puisque le dual de $\mathcal{C}$ est aussi un code LCD, il existe une projection $\Pi_{\mathcal{D}}$ définie par :

$$ \Pi_{\mathcal{D}} = H^{\top}(HH^{\top})^{-1}. \qquad (1.7) $$

En effet, par définition, chaque élément de $\mathbb{F}_2^n$ s'écrit de manière unique comme somme de deux éléments de $\mathcal{C}$ et $\mathcal{D}$. i.e. $\forall z \in \mathbb{F}_2^n, \exists! c, d \in \mathcal{C} \times \mathcal{D}$ tels que $z = c+d = xG + yH$. Alors :

$$ x = zG^{\top}(GG^{\top})^{-1}, \qquad (1.8) $$

$$ y = zH^{\top}(HH^{\top})^{-1}. \qquad (1.9) $$

### 1.4.2 Le masquage par somme directe orthogonale (ODSM)

Le masquage ODSM (Orthogonal Direct Sum Masking) a été présenté pour la première fois en 2014 dans [BCC+14]. Il s'agit d'un LEMS qui protège contre les attaques par canaux cachés et les attaques par injection de fautes.

Le masquage consiste à choisir un code LCD $\mathcal{C}$ de paramètres $[n, k, d_c]$ pour en-coder l'information sensible $x \in \mathbb{F}_2^k$ (i.e. calculer $c = xG$), et ensuite la masquer par l'addition d'un mot aléatoire du dual. Le masque agira dans ce cas comme un bruit intentionnellement ajouté. La fonction de masquage est définie par :

$$ \text{mask}(x) = xG + rH, \qquad (1.10) $$
où $G$ est la matrice génératrice de $C$, $H$ est la matrice génératrice de $C^{\perp}$, et $r$ un vecteur aléatoire dans $\mathbb{F}_2^{n-k}$.

Comme l'information et le bruit appartiennent à deux sous-espaces supplémentaires, il est toujours possible de récupérer les deux en utilisant la fonction de projection de l'équation 1.6. Cette projection sera utilisée principalement pour extraire le masque ou bien pour démasquer la donnée sensible à la fin du programme de (dé)chiffrement. Pour extraire la donnée sensible $x$ à partir d'un masqué $z \in \mathbb{F}_2^n$ il suffit d'appliquer l'opération suivante :

$$ \mathit{unmask}(z) = z G^{\top} (GG^{\top})^{-1}. \qquad (1.11) $$

Pour appliquer ce masquage à l'AES, nous allons classer les transformations qui composent ce dernier en trois types d'opérations :

(i) L'addition : qui opère sur deux octets;

(ii) Les transformations linéaires : qui opèrent sur un seul octet (utilisée dans la transformation MixColumns et en partie de SubBytes);

(iii) Les transformations non linéaires : qui opèrent sur un seul octet (comme la SubBytes).

### 1.4.2.1 L'addition

Comme dans la plupart des schémas de masquage, l'addition reste l'opération la plus simple à masquer. Puisque l'ODSM est une opération linéaire, il est donc évident de calculer l'addition de deux masqués. Soient $x_1, x_2$ deux mots sensibles dans $\mathbb{F}_2^k$, et $z_1 = \mathbf{mask}(x_1)$, $z_2 = \mathbf{mask}(x_2)$ les masqués associés à $x_1$ et $x_2$ respectivement. Nous avons :

$$ \begin{aligned} z_1 \oplus z_2 &= (x_1 G \oplus r_1 H) \oplus (x_2 G \oplus r_2 H) \\ &= (x_1 \oplus x_2) G \oplus (r_1 \oplus r_2) H \\ &= \mathbf{mask}(x_1 \oplus x_2) . \end{aligned} $$

Masquer l'addition consiste donc à additionner les deux masqués :

$$ \mathbf{Add}(z_1, z_2) = z_1 \oplus z_2 . \qquad (1.12) $$

Il est également possible d'additionner un masqué $z$ avec une donnée non masquée $k$ dans le but d'obtenir un résultat qui garde le même masque $r$ :

$$ z \oplus kG = (x \oplus k)G \oplus rH . $$
## 1.4.2.2 Les transformations linéaires

L'opération MixColumns est une fonction linaire qui opère sur des blocs de quatre octets et renvoie un seul octet, On peut la résumer dans la fonction suivante :

$$f(x_1, x_2, x_3, x_4) = 02x_1 \oplus x_2 \oplus x_3 \oplus 03x_4. \qquad (1.13)$$

Les coefficients 02 et 03 appartiennent au corps $K = \mathbb{F}_2[X]/X^8+X^4+X^3+X+1$ et représentent les éléments suivants $\alpha$ et $\alpha+1$ respectivement (voir l'exemple 6 page 33).

### Proposition 2

il existe un isomorphisme $\Psi$ entre le groupe additif $\mathbb{F}_{2^k}$ et l'espace vectoriel $\mathbb{F}_2^k$ défini par :

$$\forall x = \sum_{i=0}^{k-1} c_i \alpha^i \in \mathbb{F}_{2^k}, \quad \Psi(x) = (c_0, \dots, c_{k-1}) \in \mathbb{F}_2^k.$$

Nous avons donc :

$$\Psi(x \oplus y) = \Psi(x) \oplus \Psi(y).$$

### Exemple 8

Soient $x = 1 + \alpha^3 + \alpha^6 + \alpha^7 \in K$ et $y = \alpha^3 + \alpha^4 + \alpha^6 \in K$ nous avons :

$$\begin{aligned}
\Psi(x \oplus y) &= \Psi(1 + \alpha^3 + \alpha^6 + \alpha^7 + \alpha^3 + \alpha^4 + \alpha^6) \\
&= \Psi(1 + \alpha^4 + \alpha^7) \\
&= (10001001).
\end{aligned}$$

$$\begin{aligned}
\Psi(x) \oplus \Psi(y) &= (10010011) \oplus (00011010) \\
&= (10001001).
\end{aligned}$$

Soit $l$ une opération linéaire définie par :

$$l: K \to K \\ x \mapsto \lambda x,$$

Nous pouvons représenter cette opération comme un produit dans l'espace vectoriel $\mathbb{F}_2^8$ (nous passons d'une multiplication dans le corps $\mathbb{F}_{2^8}$ vers une multiplication matricielle dans $\mathbb{F}_2^8$). En effet, puisque le groupe additif $\mathbb{F}_2^8$ et l'espace vectoriel $\mathbb{F}_2^8$ sont isomorphes, il existe pour chaque $\lambda \in K$ une matrice $L \in \mathbb{F}_2^{8 \times 8}$, telle que $\lambda x = \Psi(x)L$. La matrice $L$ est conçue à partir de l'isomorphisme $\Psi$ où la ieme ligne de la matrice correspond à $\Psi(\alpha^i \lambda)$.
Exemple 9

Calculons le produit $x\lambda$, avec $x = A2 = \alpha + \alpha^5 + \alpha^7$ et $\lambda = 02 = \alpha$ :

$$
\begin{align*}
(\alpha + \alpha^5 + \alpha^7)\alpha \\
&= \alpha^2 + \alpha^6 + \alpha^8 \\
&= \alpha^2 + \alpha^6 + \alpha^4 + \alpha^3 + \alpha + 1 \\
&= 1 + \alpha + \alpha^2 + \alpha^3 + \alpha^4 + \alpha^6.
\end{align*}
$$

$$
\left[ \underbrace{0 \ 1 \ 0 \ 0 \ 0 \ 1 \ 0 \ 1}_{\Psi(\alpha+\alpha^5+\alpha^7)} \right] \underbrace{\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 \end{bmatrix}}_{L} = [1 \ 1 \ 1 \ 1 \ 1 \ 0 \ 1 \ 0] \\
= \Psi(1 + \alpha + \alpha^2 + \alpha^3 + \alpha^4 + \alpha^6) \\
= \Psi((\alpha + \alpha^5 + \alpha^7)\alpha).
$$

En général chaque opération linéaire de la forme : $l(x) = xL$ peut être transformée
en une opération masquée : $l'(z) = zL'$, avec $z = \mathbf{mask}(x)$. Dans le cas ODSM $L'$
est une matrice constante définie par :

$$
L' = G^{\top} (GG^{\top})^{-1} L G \oplus H^{\top} (HH^{\top})^{-1} H . \quad (1.14)
$$

En effet, si : $z = \mathbf{mask}(x) = xG + rH$, alors :

$$
\begin{align*}
zL' &= \left( xG \oplus rH \right) \left( G^\top (GG^\top)^{-1} LG \oplus H^\top (HH^\top)^{-1} H \right) \\
&= \left( x \underbrace{GG^\top (GG^\top)^{-1}}_{=I_n} LG \right) \oplus \left( x \underbrace{GH^\top (HH^\top)^{-1}}_{=0} H \right) \\
&\quad \oplus \left( r \underbrace{HG^\top (GG^\top)^{-1}}_{=0} LG \right) \oplus \left( r \underbrace{HH^\top (HH^\top)^{-1}}_{=I_n} H \right) \\
&= xLG \oplus rH \\
&= \mathbf{mask}(xL).
\end{align*}
$$

Il faut noter que les auteurs de ce masquage, proposent de garder intentionnel-
lement le masque *r* identique après chaque opération, pour des raisons que nous
allons évoquer ultérieurement. Mais cela n'empêche pas qu'il soit assez facile de
changer le masque après chaque opération.

1.4.2.3 Les transformations non linéaires

Pour les opérations non-linéaires il existe deux approches, la première consiste à
stocker en mémoire la table de substitution masquée (d'où l'intérêt de garder le
même masque tout au long du chiffrement ou déchiffrement), la seconde consiste à calculer cette transformation dans une zone sécurisée du composant.

$$ 
\begin{aligned}
S'(z) &= S(\text{unmask}(z))G \oplus zH^\top(HH^\top)^{-1}H \\
&= S(x)G \oplus rH \\
&= \text{mask}(S(x)) .
\end{aligned}
$$

Dans le chapitre 2 nous allons voir comment sécuriser la transformation **SubBytes** grâce au masquage DSM avec des opérations dans $K$. Cette solution est avantageuse pour les équipements ayant une mémoire de stockage limitée ou bien qui ne possèdent pas une zone de calcul sécurisée.

### 1.4.2.4 La détection des erreurs

Un grand avantage de ce schéma de masquage est qu'il permet de générer des masques aléatoires de longueur $n$ à partir d'un aléa de taille beaucoup plus petite $k$. Ceci représente un gain important pour le temps d'exécution. Un autre point innovant à noter pour ce schéma ; c'est la détection des erreurs, ce qui permet de détecter certaines injections de fautes.

Soit $z = xG \oplus rH = \text{mask}(x)$ le masqué associé à $x$, et $r$ le masque utilisé. Soit $e \in \mathbb{F}_2^n$ l'erreur injectée. D'après la définition 20 page 62, il existe un unique vecteur $u \in \mathbb{F}_2^k$ et un unique vecteur $v \in \mathbb{F}_2^{n-k}$ tels que $e = uG \oplus vH$. Notons : $z' = z \oplus e$ le mot obtenu après l'injection de faute. Nous avons :

$$ 
\begin{aligned}
z' &= z \oplus e \\
&= (x \oplus u)G \oplus (r \oplus v)H .
\end{aligned}
$$

Grâce à la projection de l'équation 1.9 page 64 nous pouvons extraire $r \oplus v$ et le comparer avec le masque utilisé $r$. Cependant, si l'erreur est tirée de manière aléatoire, alors il existe une probabilité de $\frac{1}{2^{n-k}}$ que $v$ soit égal à zéro (et donc $v \oplus r = r$). Ainsi, la probabilité de détecter une attaque de type FIA vaut $1 - 2^{k-n}$. Bien que cette probabilité soit importante, les injections de fautes restent plus difficiles à réaliser en pratique. Expérimentalement, il est plus facile de produire des erreurs qui ont un poids de HAMMING faible, donc pour contourner l'ODSM il faudra que l'erreur $e$ appartienne au code $C$, ce qui signifie que le nombre d'erreurs injectées doit être supérieur à la distance minimale de $C$. Ceci explique l'intérêt de choisir un code dont la distance minimale est optimale.

### 1.4.2.5 Sécurité et performances

Pour ce schéma de masquage nous supposons que la donnée sensible dépend du message (ou la valeur intermédiaire de chaque tour) et de la clé (clé maître ou clé de session), l'attaquant doit donc recueillir une quantité suffisante de traces pour récupérer le secret.
**Définition 23 (Transformée de FOURIER)**

Soit $f : \mathbb{F}_2^n \to \mathbb{R}$ une fonction “pseudo booléenne” (à valeurs réelles), la transformée de FOURIER de $f$ est définie par :

$$ \hat{f}(z) = \sum_{a \in \mathbb{F}_2^n} f(a)(-1)^{\langle a, z \rangle}. $$

**Propriété 14**

Soit $P : \mathbb{F}_2^n \to \mathbb{R}$ une fonction pseudo booléenne de degré numérique $d^°(P)$, alors :

$$ \forall z \in \mathbb{F}_2^n, \quad \omega_H(z) > d^°(P) \implies \hat{P}(z) = 0. $$

**Preuve :**

Comme $P$ est une fonction polynomiale, alors par définition elle s'écrit ainsi :
$$ P(y_1, \dots, y_n) = \sum_{I \in \mathbb{F}_2^n} a_I y^I, \text{ avec } y^I = \prod_{i=1}^n y_i^{l_i} \text{ et } a_I \in \mathbb{R}. \text{ Par linéarité de la transformée de FOURIER, nous avons :} $$

$$ \hat{P}(z) = \sum_{I \in \mathbb{F}_2^n} a_I \hat{M}_I(z), $$

avec $M_I(y) = y^I$. Montrons que $\forall z \in \mathbb{F}_2^n, \omega_H(z) > \omega_H(I) \implies \hat{M}_I(z) = 0$.

Soit $z \in \mathbb{F}_2^n$ tel que $\omega_H(z) > \omega_H(I)$, il existe au moins une position $i$ telle que $z_i = 1$ et $I_i = 0$, nous pouvons donc supposer - sans perte de généralité - que cette position $i$ égal à $n$ (la dernière position). Notons $y = (y', y_n) \in \mathbb{F}_2^n$ avec $y' = (y_1, \dots, y_{n-1}) \in \mathbb{F}_2^{n-1}$ et $y_n \in \mathbb{F}_2$. Nous avons :

$$ \begin{aligned} \hat{M}_I(z) &= \sum_{y' \in \mathbb{F}_2^{n-1}} \sum_{y_n \in \mathbb{F}_2} y^I(-1)^{\langle y, z \rangle} \\ &= \sum_{y' \in \mathbb{F}_2^{n-1}} (y', 0)^I (-1)^{\langle y', z_1, \dots, z_{n-1} \rangle} (1 + (-1)) \\ &= 0. \end{aligned} $$

Donc nous avons bien : $\hat{P}(z) = \sum_{I \in \mathbb{F}_2^n} a_I \times 0 = 0$. ■

**Théorème 2 (L'ordre du masque ODSM [BCC$^{+}$14])**

ODSM permet de protéger contre les attaques de type SCA sur une variable pour un ordre de masquage $d$ tel que $d < d_C$, où $d_C$ est la distance minimale de $C$.

**Preuve : [BCC$^{+}$14]**

Soient :

$$ \Psi : \mathbb{F}_2^k \to \mathbb{F}_2^n \text{ la fonction d'encodage de } \mathcal{C} \text{ (i.e. } \Psi(x) = xG), $$
— $\Phi: \mathbb{F}_2^n \to \mathbb{R}$ une fonction pseudo-booléenne d'un degré numérique donné $j$. Ce degré représente le nombre de bits de $z$ exploités par l'attaquant, en d'autres termes la fonction $\Phi$ peut modéliser le produit de $j$ bits de $z$.

— et $f: \mathbb{F}_2^n \to \mathbb{F}_2$ la fonction indicatrice de $\mathcal{D}$ :

$$f(d) = \begin{cases} 1 & \text{si } d \in \mathcal{D} \quad (\text{i.e. } \exists y \in \mathbb{F}_2^{n-k} \mid yH = d). \\ 0 & \text{sinon.} \end{cases}$$

Soient $X$ et $D$ deux variables aléatoires uniformément distribuées dans $\mathbb{F}_2^k$ et $\mathcal{D}$ respectivement.

**Proposition 3** (Condition de sécurité d'ordre $j$ sur l'encodage des masques)

Pour toute fonction pseudo-booléenne $\Phi$ de degré numérique inférieur ou égal à $j$, la fuite $\Phi(\Psi(X) \oplus D)$ résiste aux attaques SCA sur une variable pour un ordre $j$ si $\mathcal{D}$ est un code de distance dual égal à $j + 1$ ($d_{\mathcal{D}}^{\perp} = j + 1$).

Cette proposition est une simple reformulation du théorème précédent, et pour la démontrer il suffit de montrer qu'il n'existe aucune dépendance entre $x \in \mathbb{F}_2^k$ et $\mathbb{E}[\Phi(\Psi(X) \oplus D)|X = x]$, en d'autres termes, il faut montrer que :

$$\mathrm{Var}[\mathbb{E}[\Phi(\Psi(X) \oplus D)|X]] = 0.$$

Nous avons :

$$\begin{aligned} \mathbb{E}[\Phi(\Psi(X) + D) \mid X = x] &= \sum_{d \in \mathcal{D}} \frac{1}{|\mathcal{D}|} \Phi(\Psi(x) \oplus d) \\ &= 2^{-(n-k)} \sum_{d \in \mathbb{F}_2^n} f(d) \Phi(\Psi(x) \oplus d) \\ &= 2^{-(n-k)} (f \otimes \Phi)(\Psi(x)). \end{aligned}$$

Ainsi, il faut montrer que la valeur $(f \otimes \Phi)(\Psi(x))$ ne dépend pas de $x$.

Soit $g: \mathbb{F}_2^n \to \mathbb{R}$ une fonction pseudo booléenne, et $\hat{g}$ sa transformée de FOURIER. Nous avons : $g$ est constante $\iff \forall z \neq 0, \hat{g}(z) = 0$. Notons : $g = f \otimes \Phi$, la transformée de FOURIER transforme un produit de convolution en un produit dans $\mathbb{R}$, ainsi nous avons : $\hat{g}(z) = \widehat{f \otimes \Phi}(z) = \hat{f}(z)\hat{\Phi}(z)$. Il reste donc à démontrer que :

$$\hat{f}\hat{\Phi} = 0. \qquad (1.15)$$

Comme $\Phi$ dans la proposition 3 est de degré numérique $j$, alors d'après la propriété 14 nous avons : pour tout $z$ dans $\mathbb{F}_2^n$ tel que $\omega_H(z) > j$ alors $\hat{\Phi}(z) = 0$. En d'autres termes, ce masquage protège contre la SCA pour un ordre $j$ si $\forall z \in \mathbb{F}_2^n, 0 < \omega_H(z) \le j, \hat{f}(z) = 0$, ce qui signifie également que la distance minimale du dual de $\mathcal{D}$ est $d_{\mathcal{D}}^{\perp} = d_C = j + 1$ (puisque $C$ et $\mathcal{D}$ sont des codes LCD). ■
1.4.3 Exemple

Comme la plupart des composants électroniques opèrent sur des octets (par exemple les cartes à puces, ou les TPM), il est préférable pour ce genre d'architectures de prendre une longueur de code *n* multiple de *k* = 8. Dans [CDD<sup>+</sup>15] CARLET et al. ont présenté une méthode efficace pour construire des codes optimaux pour ce type de masquage.

Soit $\mathcal{C}$ un code LCD de paramètres $[16, 8, 5]$, tels que $G$ est sa matrice génératrice et $H$ sa matrice de parité (donc la matrice génératrice de son supplémentaire $\mathcal{D}$), avec :

$$
G = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{bmatrix}, \quad H = \begin{bmatrix} 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}.
$$

Soient $x = (1, 0, 0, 1, 1, 0, 1, 1) = \Psi(9B)$ une donnée sensible et $r = (0, 1, 0, 1, 1, 1, 0, 1) = \Psi(5D)$ le masque à utiliser. Après l'opération mask, le mot masqué associé à $x$ sera
donc :

$$
z = xG \oplus rH = (0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0) = \Psi(3B38).
$$

Pour extraire $x$ ou $r$ à partir de $z$ (les équations 1.8 et 1.9), nous avons :

$$
\begin{align*}
zG^{\top}(GG^{\top})^{-1} &= (1, 0, 0, 1, 1, 0, 1, 1) = \Psi(9B), \\
zH^{\top}(HH^{\top})^{-1} &= (0, 1, 0, 1, 1, 1, 0, 1) = \Psi(5D).
\end{align*}
$$

Il faut noter que les matrices $G^\top(GG^\top)^{-1}$ et $H^\top(HH^\top)^{-1}$ sont précalculées :

$$
G^{\top}(GG^{\top})^{-1} = \begin{bmatrix} 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \end{bmatrix}, \quad H^{\top}(HH^{\top})^{-1} = \begin{bmatrix} 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}.
$$

Calculer MixColumns :

Dans cet exemple nous allons calculer la fonction $f$ de l'équation 1.13 qui représente
le fonctionnement de la transformation MixColumns :

$$
f(x_1, x_2, x_3, x_4) = 02x_1 \oplus x_2 \oplus x_3 \oplus 03x_4 .
$$
# CHAPITRE 1. L'ÉTAT DE L'ART SUR LE MASQUAGE

Comme nous l'avons vu dans la partie (opération (ii)); les fonctions : $x \mapsto 02x$ et $x \mapsto 03x$ équivalent respectivement : $\Psi(x) \mapsto \Psi(x)L$ et $\Psi(x) \mapsto \Psi(x)M$ telles que :

$$L = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \end{bmatrix}, \quad M = \begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}.$$

Soient $z_1, z_2, z_3, z_4$ les masqués associés à $x_1, x_2, x_3, x_4$ respectivement, et $L', M'$ les matrices associées à $L$ et $M$ respectivement, et qui sont calculées grâce à l'équation 1.14. Nous pouvons construire la fonction alternative à $f$ ainsi :

$$f(z_1, z_2, z_3, z_4) = z_1 L' \oplus z_2 \oplus z_3 \oplus z_4 M' .$$

Avec :

$$L' = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \end{bmatrix}, \quad M' = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix}.$$
1.5 Conclusion

Dans ce chapitre nous avons présenté une variété de schémas de masquage les plus connus. Nous avons essayé de présenter des méthodes qui sont basées sur différents concepts. Chaque schéma possède ses propres avantages et faiblesses, il y en a qui s'adaptent mieux à certains besoins mais pas d'autres et tout dépend du support qui va accueillir cette solution. Pour conclure, nous avons résumé un bon schéma de masquage en quatre points essentiels :

1. Indéterministe : Pour un niveau de sécurité plus élevé, il est important que le schéma de masquage soit indéterministe, c'est-à-dire que la donnée sensible soit combinée avec une valeur aléatoire dans le processus du masquage;

2. Homomorphe : L'opération de masquage doit pouvoir masquer les deux opérations de base (addition et multiplication). En d'autres termes, il faudra construire des opérations alternatives à l'addition et à la multiplication qui coopèrent avec la nouvelle structure de la donnée traitée;

3. Léger : La complexité algorithmique représente aussi un défi majeur pour le concepteur. Il est important de prendre en compte la mémoire très limitée des composants électroniques avant de construire une fonction de masquage;

4. Structuré : Le mot masqué doit avoir une structure d'un code correcteur afin de protéger contre FIA.
<figure><img src="image_22.png" /></figure>
2 | Le masquage par somme directe sur un corps fini

Sommaire

<table><tr><td>2.1</td><td>Introduction</td><td>76</td></tr><tr><td>2.1.1</td><td>Objectifs</td><td>76</td></tr><tr><td>2.1.2</td><td>Vocabulaire</td><td>76</td></tr><tr><td>2.2</td><td>L'addition et la multiplication</td><td>78</td></tr><tr><td>2.2.1</td><td>L'addition</td><td>78</td></tr><tr><td>2.2.2</td><td>La multiplication par une valeur publique</td><td>79</td></tr><tr><td>2.2.3</td><td>La multiplication entre deux valeurs sensibles</td><td>80</td></tr><tr><td>2.3</td><td>Sécurité et performances</td><td>81</td></tr><tr><td>2.4</td><td>Exemple général : La boîte de substitution (SubBytes)</td><td>84</td></tr><tr><td>2.5</td><td>Détection et correction des erreurs</td><td>86</td></tr><tr><td>2.6</td><td>Conclusion</td><td>88</td></tr></table>
## 2.1 Introduction

### 2.1.1 Objectifs

Nous remarquons que les schémas de masquage que nous avons présentés dans le chapitre précédent ne protègent pas tous contre les deux attaques SCA et FIA simultanément. Le masquage booléen, le masquage basé sur le partage du secret et le masquage basé sur le produit scalaire permettent tous de masquer l'addition et la multiplication et protéger ainsi contre SCA. D'un autre côté, le masquage ODSM propose une solution pour masquer uniquement l'addition, et en même temps détecter certaines injections des erreurs.

Pour surmonter tout ça, nous allons présenter dans ce chapitre un schéma de masquage qui pourra accomplir les tâches suivantes [CDGT18] :

- Masquer l'information sensible de manière efficace, il faut que la fonction de masquage soit non-déterministe, et qu'elle permette de masquer les deux opérations d'addition et de multiplication;

- Détecter les erreurs potentielles et éventuellement les corriger si le besoin l'impose;

- Réduire le plus possible la complexité algorithmique en termes de temps de calcul (la génération de l'aléa, et la quantité d'opérations) et de l'espace mémoire (l'évolution de la longueur du masqué en termes de l'ordre désiré).

Comme nous l'avons constaté dans le chapitre précédent, pour masquer l'AES, il suffit de réussir à masquer l'addition et la multiplication dans le corps $\mathbb{F}_{256}$. Donc pour atteindre les trois objectifs ci-dessus il faudra construire les trois algorithmes suivantes :

1. **mask**: $x \mapsto z$ tel que z soit un mot de code;

2. **Add**: $\text{mask}(x), \text{mask}(y) \mapsto \text{mask}(x + y)$;

3. **Mult**: $\text{mask}(x), \text{mask}(y) \mapsto \text{mask}(xy)$.

La solution que nous proposons dans ce chapitre et qui permet de réaliser ces objectifs est basée sur la même approche que ODSM. Cependant, dans ce schéma nous avons choisi de travailler dans le corps fini $\mathbb{F}_{256}$ qui est le corps de base de toutes les opérations qui composent l'AES. Ce choix nous permet d'avoir plus de flexibilité pour manipuler les polynômes, et donc plus de maîtrise pour atteindre l'objectif final.

### 2.1.2 Vocabulaire

Pour commencer, nous allons établir un vocabulaire qui sera utilisé tout au long de ce chapitre.
Soit $K = \mathbb{F}_{256} = \mathbb{F}_2[\alpha]/(\alpha^8+\alpha^4+\alpha^3+\alpha+1)$ un corps fini de 256 éléments. Chaque élément de ce corps est une classe d'équivalence représentée par un polynôme de degré au plus 7. Soient $\mathcal{C}$ et $\mathcal{D}$ deux sous-espaces vectoriels de dimension 1 dans $K^n$ (contrairement à la construction du chapitre précédent; il s'agit ici de $\mathbb{F}_{256}^n$ et non pas $\mathbb{F}_2^n$). Pour faire la distinction entre les éléments de $K$ et de $K^n$, nous allons exprimer les éléments de l'espace vectoriel $K^n$ avec une flèche en dessus. Soient $\vec{g}, \vec{h} \in K^n\setminus\{0\}$ des générateurs de $\mathcal{C}$ et $\mathcal{D}$ respectivement tels que $\langle\vec{g}, \vec{h}\rangle = 0$, $\langle\vec{g}, \vec{g}\rangle \neq 0$ et $\langle\vec{h}, \vec{h}\rangle \neq 0$. Nous avons :

$$ \mathcal{C} = \{x \cdot \vec{g} \mid x \in K\}, $$

et :

$$ \mathcal{D} = \{x \cdot \vec{h} \mid x \in K\}, $$

où “ · ” désigne un produit entre un scalaire et un vecteur (exemple : $x \cdot \vec{g} = (xg_1, \dots, xg_n) \in K^n$). Notons $\mathcal{K}$ le sous-espace vectoriel de $K^n$ formé à partir des éléments de $\mathcal{C}$ et $\mathcal{D}$ :

$$ \mathcal{K} = \{c \oplus d \mid c \in \mathcal{C}, d \in \mathcal{D}\} \subseteq K^n. $$

### Remarque 1

Pour $n = 2$, le code $\mathcal{C}$ est un code LCD, et dans ce cas $\mathcal{K} = K^n$.

Le masquage PDSM (Polynomial Direct Sum Masking) [CDGT18] consiste à additionner le mot de code associé à la donnée sensible avec un ou plusieurs mots aléatoires dans le dual :

$$ \mathbf{mask}(x) = x \cdot \vec{g} \oplus r \cdot \vec{h} \in \mathcal{K}. \qquad (2.1) $$

**Algorithm 20 mask(x)**
**Complexité** : $2n$ multiplications et $n$ additions
1: **entrée** : $x \in K$
2: **sortie** : $\mathbf{mask}(x) \in \mathcal{K}$
3: $r \leftarrow K$
4: $\vec{z} \leftarrow \vec{0} \in \mathcal{K}$
5: **pour** $i = 1$ **jusqu'à** $n$ **faire** :
6:     $z_i \leftarrow xg_i \oplus rh_i$
7: **renvoyer** $\vec{z}$

Pour extraire l'information sensible $x$ à partir d'un masqué $\vec{z} = \mathbf{mask}(x)$, il suffit de multiplier ce dernier par $\vec{g}$ et par le scalaire $g' = \langle\vec{g}, \vec{g}\rangle^{-1}$ :

$$ \mathbf{unmask}(\vec{z}) = \langle\vec{z}, \vec{g}\rangle \langle\vec{g}, \vec{g}\rangle^{-1}. \qquad (2.2) $$
**Preuve :** Cette opération se déduit directement de l'équation 1.8 (par symétrie nous pouvons également extraire $r$ grâce à l'équation 1.9). Nous avons :

$$ 
\begin{align*}
\langle \vec{z}, \vec{g} \rangle \langle \vec{g}, \vec{g} \rangle^{-1} &= \langle x \cdot \vec{g} \oplus r \cdot \vec{h}, \vec{g} \rangle \langle \vec{g}, \vec{g} \rangle^{-1} \\
&= \left( x \langle \vec{g}, \vec{g} \rangle \oplus r \underbrace{\langle \vec{h}, \vec{g} \rangle}_{=0} \right) \langle \vec{g}, \vec{g} \rangle^{-1} \\
&= x \langle \vec{g}, \vec{g} \rangle \langle \vec{g}, \vec{g} \rangle^{-1} \\
&= x.
\end{align*}
$$

<figure><img src="image_23.png" /></figure>

**Algorithm 21 Unmask($\vec{z}$)** Complexité : $(n + 1)$ multiplications et $n$ additions

1: **entrée** : $\vec{z} = \text{mask}(x) \in \mathcal{K}$

2: **sortie** : $x \in K$

3: $x \leftarrow 0 \in K$

4: **pour** $i = 1$ **jusqu'à** $n$ **faire** :

5: $x \leftarrow x \oplus z_i g_i$

6: $x \leftarrow x \langle \vec{g}, \vec{g} \rangle^{-1}$ Nous supposons que la valeur $\langle \vec{g}, \vec{g} \rangle^{-1}$ est précalculée

7: **renvoyer** $x$

La figure 2.1 résume l'ensemble des éléments qui sont utilisés pour ce schéma de masquage.

<figure><img src="image_24.png" /><figcaption>FIGURE 2.1 – Représentation graphique de l'ensemble des éléments du masquage DSM.</figcaption></figure>

## 2.2 L'addition et la multiplication

### 2.2.1 L'addition

Cette méthode de masquage est une fonction linéaire par rapport à l'addition. Considérons $\text{mask}(x)$ et $\text{mask}(y)$ la valeur masquée d'une donnée sensible $x$ et $y$
respectivement, la valeur masquée de $x \oplus y$ correspond à :

$$ \mathbf{mask}(x) \oplus \mathbf{mask}(y) = \mathbf{mask}(x \oplus y). $$

**Algorithm 22 Add($\vec{z}, \vec{z'}$)**

Complexité : $n$ additions

1: **entrée** : $\vec{z} = \mathbf{mask}(x), \vec{z'} = \mathbf{mask}(y) \in \mathcal{K}$

2: **sortie** : $\mathbf{mask}(x \oplus y) \in \mathcal{K}$

3: $\vec{u} \leftarrow \vec{0} \in \mathcal{K}$

4: **pour** $i = 1$ **jusqu'à** $n$ **faire** :

5: $u_i \leftarrow z_i \oplus z'_i$

6: **renvoyer** $\vec{u}$

En ce qui concerne la multiplication, nous allons distinguer deux types de multiplications.

### 2.2.2 La multiplication par une valeur publique

Le cas le plus simple est la multiplication entre une valeur masquée et une valeur non masquée. Ce cas permet de gagner en complexité en évitant de masquer les valeurs publiques inutilement (exemple : la matrice de MixColumns et les coefficients de la transformation SubBytes). Ainsi, pour masquer le produit $\lambda x$ à partir d'une donnée publique $\lambda$ et le masqué de $x$, nous procédons ainsi :

$$ \begin{aligned} \lambda \cdot \mathbf{mask}(x) &= \lambda \cdot (x \cdot \vec{g} \oplus r \cdot h) \\ &= \lambda x \cdot \vec{g} \oplus \lambda r \cdot \vec{h} \\ &= \mathbf{mask}(\lambda x). \end{aligned} $$

**Algorithm 23 mult1($\lambda, \vec{z}$)**

Complexité : $n$ multiplications

1: **entrée** : $\lambda \in \mathcal{K}$ et $\vec{z} = \mathbf{mask}(x) \in \mathcal{K}$

2: **sortie** : $\mathbf{mask}(\lambda x) \in \mathcal{K}$

3: $\vec{u} \leftarrow \vec{0} \in \mathcal{K}$

4: **pour** $i = 1$ **jusqu'à** $n$ **faire** :

5: $u_i \leftarrow \lambda z_i$

6: **renvoyer** $\vec{u}$
2.2.3 La multiplication entre deux valeurs sensibles

Le deuxième cas est la multiplication entre deux valeurs masquées, nous avons :

$$
\mathbf{mask}(xy) = \langle \vec{g}, \vec{g} \rangle^{-1} \cdot \left[ \mathbf{mask} \left( r_t + \langle \mathbf{mask}(x), \mathbf{mask}(y) \rangle \right) - \left( r_t + \langle \vec{h}, \vec{h} \rangle^{-1} \langle \mathbf{mask}(x), \vec{h} \rangle \langle \mathbf{mask}(y), \vec{h} \rangle \right) \cdot \vec{g} \right],
$$

avec $r_t$ un masque intermédiaire généré pendant le calcul pour sécuriser le produit
scalaire $\langle \mathbf{mask}(x), \mathbf{mask}(y) \rangle$. En effet, ce produit (comme indiqué dans la preuve
ci-dessous) permet d'extraire la valeur sensible $xy$.

Preuve : Nous avons :

$$
\begin{align*}
r_t \oplus \langle \mathbf{mask}(x), \mathbf{mask}(y) \rangle
&= r_t \oplus \langle x \cdot \vec{g} \oplus r \cdot \vec{h}, y \cdot \vec{g} \oplus r' \cdot \vec{h} \rangle \\
&= r_t \oplus \langle x \cdot \vec{g}, y \cdot \vec{g} \rangle \oplus \langle x \cdot \vec{g}, r' \cdot \vec{h} \rangle \oplus \langle r \cdot \vec{h}, y \cdot \vec{g} \rangle \oplus \langle r \cdot \vec{h}, r' \cdot \vec{h} \rangle \\
&= r_t \oplus xy \langle \vec{g}, \vec{g} \rangle \oplus \underbrace{xr' \langle \vec{g}, \vec{h} \rangle \oplus yr \langle \vec{h}, \vec{g} \rangle}_{=0} \oplus rr' \langle \vec{h}, \vec{h} \rangle \\
&= r_t \oplus xy \langle \vec{g}, \vec{g} \rangle \oplus rr' \langle \vec{h}, \vec{h} \rangle .
\end{align*}
$$

$$
\begin{align*}
\langle \mathbf{mask}(x), \vec{h} \rangle &= \langle x \cdot \vec{g} \oplus r \cdot \vec{h}, \vec{h} \rangle \\
&= x \langle \vec{g}, \vec{h} \rangle \oplus r \langle \vec{h}, \vec{h} \rangle \\
&= r \langle \vec{h}, \vec{h} \rangle .
\end{align*}
$$

Nous obtenons donc :

$$
\begin{align*}
\langle \vec{g}, \vec{g} \rangle^{-1} \cdot \left[ \mathbf{mask} \left( r_t \oplus \langle \mathbf{mask}(x), \mathbf{mask}(y) \rangle \right) - \left( r_t \oplus \langle \vec{h}, \vec{h} \rangle^{-1} \langle \mathbf{mask}(x), \vec{h} \rangle \langle \mathbf{mask}(y), \vec{h} \rangle \right) \cdot \vec{g} \right] \\
&= \langle \vec{g}, \vec{g} \rangle^{-1} \cdot \left[ \left( r_t \oplus xy \langle \vec{g}, \vec{g} \rangle \oplus rr' \langle \vec{h}, \vec{h} \rangle \right) \cdot \vec{g} \oplus r'' \cdot \vec{h} - \left( r_t \oplus rr' \langle \vec{h}, \vec{h} \rangle \right) \cdot \vec{g} \right] \\
&= \langle \vec{g}, \vec{g} \rangle^{-1} \cdot \left[ xy \langle \vec{g}, \vec{g} \rangle \cdot \vec{g} \oplus r'' \cdot \vec{h} \right] \\
&= xy \cdot \vec{g} \oplus r'' \langle \vec{g}, \vec{g} \rangle^{-1} \cdot \vec{h} \\
&= \mathbf{mask}(xy) .
\end{align*}
$$

<figure><img src="image_25.png" /></figure>
**Algorithm 24** Mult2($\vec{z}, \vec{z}'$)

Complexité : $7n + 2$ multiplications et $4n + 1$ additions

un masque temporaire

1: **entrée** : $\vec{z} = \text{mask}(x), \vec{z}' = \text{mask}(y) \in \mathcal{K}$

2: **sortie** : $\text{mask}(xy) \in \mathcal{K}$

3: $r_t \stackrel{\$}{\leftarrow} K^*$

4: $a \leftarrow r_t$

5: $b \leftarrow 0 \in K$

6: $c \leftarrow 0 \in K$

7: $\vec{u} \leftarrow \vec{0} \in \mathcal{K}$

8: **pour** $i = 1$ **jusqu'à** $n$ **faire** :

9: $a \leftarrow a \oplus z_i z_i'$

10: $b \leftarrow b \oplus z_i h_i$

11: $c \leftarrow c \oplus z_i' h_i$

12: $\vec{u} \leftarrow \langle \vec{g}, \vec{g} \rangle^{-1} (\text{mask}(a) \oplus \text{Mult1}(r_t \oplus bc\langle \vec{h}, \vec{h} \rangle^{-1}, \vec{g}))$

13: **renvoyer** $\vec{u}$

Nous supposons que les valeurs $\langle \vec{g}, \vec{g} \rangle^{-1}$ et $\langle \vec{h}, \vec{h} \rangle^{-1}$ sont précalculées.

## 2.3 Sécurité et performances

### Propriété 15

Soient $\vec{g}$ et $\vec{h}$ deux vecteurs dans $K^n$ tels que $\langle \vec{g}, \vec{h} \rangle = 0$. Notons $\mathcal{C} = \{x \cdot \vec{g} \mid \forall x \in K\}$ et $\mathcal{D} = \{x \cdot \vec{h} \mid \forall x \in K\}$ les codes associés à $\vec{g}$ et $\vec{h}$ respectivement. Les deux conditions $\langle \vec{g}, \vec{g} \rangle \neq 0$ et $\langle \vec{h}, \vec{h} \rangle \neq 0$ impliquent :

- $\vec{g}$ et $\vec{h}$ sont linéairement indépendants (i.e. $\forall \lambda \in K \ \lambda \cdot \vec{g} \neq \vec{h}$);

- $\mathcal{C} \cap \mathcal{D} = \{\vec{0}\}$;

- $\forall \vec{z} \in \mathcal{K}, \exists! (x, y) \in K^2 \text{ tels que } \vec{z} = x \cdot \vec{g} \oplus y \cdot \vec{h}.$

### Preuve :

- Pour la première propriété, supposons qu'il existe $\lambda \in K$ tel que : $\lambda \cdot \vec{g} = \vec{h}$, alors : $\lambda \langle \vec{g}, \vec{h} \rangle = \langle \lambda \cdot \vec{g}, \vec{h} \rangle = \langle \vec{h}, \vec{h} \rangle = 0$. La réciproque se démontre de la même façon.

- La deuxième propriété se déduit directement de la première, les deux générateurs $\vec{g}$ et $\vec{h}$ sont linéairement indépendants, alors le seul élément en commun entre les deux sous-espace vectoriels générés par $\vec{g}$ et $\vec{h}$ est l'élément neutre 0.

- La troisième propriété est une conséquence du théorème du rang : $\text{dim}(\mathcal{K}) = \text{dim}(\mathcal{C}) + \text{dim}(\mathcal{D})$.
<figure><img src="image_26.png" /></figure>

## Définition 24 (matrice génératrice)

Soit $\mathcal{C}$ le code décrit dans la propriété 15, la matrice génératrice de $\mathcal{C}$ est définie par : $G \in \mathbb{F}_2^{8 \times 8n}$ telle que la ieme ligne de cette matrice correspond à la représentation binaire par $\Psi$ (proposition 2) de $\alpha^i \cdot \vec{g}$ (i.e. $G_i = \Psi(\alpha^i \cdot \vec{g})$).

## Exemple 10

Soient $\vec{g} = (1, 1, \alpha^3 + \alpha^4 + \alpha^7) \in K^3$ avec $K = \mathbb{F}_2[\alpha]/\alpha^8 + \alpha^4 + \alpha^3 + \alpha + 1$, et $\mathcal{C}$ le code généré par $\vec{g}$. La matrice génératrice de $\mathcal{C}$ est définie par :

$$G = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \end{bmatrix}.$$

Par exemple la troisième ligne de $G$ correspond à :

$$ \begin{aligned} \Psi(\alpha^3 \cdot \vec{g}) &= \Psi(\alpha^3, \alpha^3, \alpha^6 + \alpha^7 + \alpha^{10}) \\ &= \Psi(\alpha^3, \alpha^3, \alpha^6 + \alpha^7 + \alpha^2\alpha^8) \\ &= \Psi(\alpha^3, \alpha^3, \alpha^6 + \alpha^7 + \alpha^2(\alpha^4 + \alpha^3 + \alpha + 1)) \\ &= \Psi(\alpha^3, \alpha^3, \alpha^6 + \alpha^7 + \alpha^6 + \alpha^5 + \alpha^3 + \alpha^2) \\ &= \Psi(\alpha^3, \alpha^3, \alpha^2 + \alpha^3 + \alpha^5 + \alpha^7) \\ &= (0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1) . \end{aligned} $$

<figure><img src="image_27.png" /></figure>

## Définition 25 (La distance minimale)

Soit $\mathcal{C} = \{x \cdot \vec{g} \mid \forall x \in K\}$ un code généré par un vecteur non nul $\vec{g} \in K^n$. Nous définissons la distance minimale de $\mathcal{C}$ par :

$$d_{\mathcal{C}} = \min\{\omega_{H}(\Psi(v)) \mid v \in \mathcal{C}^{*}\},$$

avec $\omega_H$ désignant le poids de HAMMING.

## Théorème 3

Le masquage de l'équation 2.1 permet de protéger contre les attaques de type SCA sur une variable jusqu'à l'ordre $d_{\mathcal{D}^{\perp}} - 1$, où $d_{\mathcal{D}^{\perp}} - 1$ est la distance minimale du dual de $\mathcal{D}$.

**Preuve :** Comme dans ce qui précède, soient $\vec{g}, \vec{h} \in K^n$ deux générateurs de $\mathcal{C}$ et $\mathcal{D}$ respectivement, tels que : $\langle \vec{g}, \vec{h} \rangle = 0$, $\langle \vec{g}, \vec{g} \rangle \neq 0$ et $\langle \vec{h}, \vec{h} \rangle \neq 0$. L'opération de masquage qui consiste à calculer $\vec{z} = x \cdot \vec{g} + r \cdot \vec{h}$, pour une donnée sensible $x$ et
un masque aléatoire $r$, équivaut à $z' = \Psi(x)G + \Psi(r)H = \Psi(z)$, avec $G$ et $H$ deux matrices génératrices de $C$ et $D$ respectivement. On observe ainsi que cette opération de masquage fait partie de la famille DSM. Le théorème 2 page 69 prouve que la dernière opération de masquage ($z' = xG + rH$) peut être attaquée par SCA monovarié d'ordre supérieur seulement à l'ordre $j \ge d_{D\perp}$ (dans le cas d'ODSM $D\perp = C$).

Le tableau 2.1 résume la complexité algorithmique de chaque algorithme présenté, cette complexité est calculée en fonction de la taille du masque et du nombre d'opérations (addition et multiplication) effectuées.

<table><thead><tr><th></th><th>nb. multiplications</th><th>nb. d'additions</th></tr></thead><tbody><tr><td>mask</td><td>2n</td><td>n</td></tr><tr><td>unmask</td><td>n + 1</td><td>n</td></tr><tr><td>Add</td><td>0</td><td>n</td></tr><tr><td>Mult1</td><td>n</td><td>0</td></tr><tr><td>Mult2</td><td>7n + 2</td><td>4n + 1</td></tr></tbody></table>

TABLE 2.1 – Une vision globale sur la complexité algorithmique de chaque fonction en terme de nombre d'opérations.

La complexité algorithmique du masquage dépend souvent de la complexité de l'algorithme de multiplication (Mult2). En effet, c'est toujours l'opération la plus gourmande en terme d'opérations, cette complexité est exprimée en fonction de la longueur de la valeur masquée et du nombre d'opérations dans le corps fini $\mathbb{F}_{2^8}$. Dans le tableau 2.2 nous présentons un comparatif des méthodes de masquage que nous avons présenté en terme de complexité, longueur, et de caractéristiques.

<table><thead><tr><th></th><th>BM</th><th>SSM</th><th>IPM</th><th>ODSM</th><th>PDSM</th></tr></thead><tbody><tr><td>L'addition</td><td>Oui</td><td>Oui</td><td>Oui</td><td>Oui</td><td>Oui</td></tr><tr><td>La multiplication</td><td>Oui</td><td>Oui</td><td>Oui</td><td>Non</td><td>Oui</td></tr><tr><td>Le nombre de parts n</td><td>d + 1</td><td>2d + 1</td><td>2d + 1</td><td>d + 1</td><td>d + 1</td></tr><tr><td>La complexité algorithmique</td><td>O(n<sup>2</sup>)</td><td>O(n<sup>3</sup>)</td><td>O(n<sup>2</sup>)</td><td>-</td><td>O(n)</td></tr><tr><td>Détection des erreurs</td><td>Non</td><td>Oui</td><td>Non</td><td>Oui</td><td>Oui</td></tr></tbody></table>

TABLE 2.2 – Comparatif entre PDSM et l'état de l'art

Pour mesurer la résistance du PDSM face aux attaques du type SCA, nous avons calculé le taux de réussite d'une attaque d'ordre 2 en utilisant les même paramètres pour les différents schémas de masquage que nous avons présentés. Nous remarquons, que le schéma IPM a la meilleur résistance (à partir de 4200 traces), ensuite SSM (à partir de 3700 traces), puis PDSM (à partir de 3000 traces) et enfin BM
(à partir de 400 traces). La schéma IPM est une généralisation du schéma SSM, ce qui explique son score par rapport à SSM. Le schéma PDSM, utilise uniquement une graine de taille 8 bits (r) pour calculer le masque ($r \cdot \tilde{h}$). Ainsi, pour obtenir une meilleure résistance face aux attaques d'ordres supérieurs, il sera intéressant d'étudier le comportement de ce schéma en utilisant plusieurs graines.

<figure><img src="image_28.png" /><figcaption>FIGURE 2.2 – Comparaison du taux de réussite d'une attaque SCA d'ordre 2 par rapport au nombre de traces entre le masquage PDSM et l'état de l'art.</figcaption></figure>

## 2.4 Exemple général : La boîte de substitution (SubBytes)

Pour mieux observer le rôle de chacun des algorithmes que nous avons présentés dans ce chapitre, nous allons présenter une application de chacun d'entre eux dans une seule transformation qui les englobe tous. La transformation SubBytes est définie mathématiquement par la fonction suivante :

$$ \text{SubByte}(x) = 63 \oplus 05x^{-1} \oplus 09x^{-2} \oplus F9x^{-4} \oplus 25x^{-8} \oplus F4x^{-16} \oplus 01x^{-32} \oplus B5x^{-64} \oplus 8Fx^{-128} \in K. $$

Cette fonction englobe les trois opérations que nous avons vues précédemment :

- Add : pour remplacer l'addition ($\oplus$);

- Mult1 : pour remplacer la multiplication par un coefficient;
## 2.4. EXEMPLE GÉNÉRAL : LA BOÎTE DE SUBSTITUTION (SUBbytes)

— `Mult2` : pour remplacer la multiplication entre les données sensibles, dans ce cas il s'agit des puissances de $x$.

Avant de définir la version masquée de `SubBytes`, nous devons définir la fonction `Inverse` qui permettra de calculer l'inverse d'un élément dans $K$. Comme dans le section 1.1.2, nous allons nous baser sur le théorème d'EULER ?? . Pour le cas AES, $K = \mathbb{F}_2[\alpha]/(\alpha^8 + \alpha^4 + \alpha^3 + \alpha + 1)$. Nous avons : $\forall x \in K\setminus\{0\}, x^{255} = 1$, ainsi :

$$ \forall x \in K\setminus\{0\}, \quad x^{-1} = x^{254}. \qquad (2.3) $$

Pour calculer l'inverse, nous allons utiliser l'algorithme 2 dans [RP10], ce dernier permet de calculer cette exponentiation en utilisant le plus petit nombre possible d'opérations `Mult2`. Cependant, dans notre cas, il n'est pas nécessaire de rafraîchir le masque car cette opération est déjà incluse dans l'algorithme `Mult2`.

**Algorithm 25 Inverse($\tilde{z}$)** Complexité : $77n + 22$ multiplications et $44n + 11$ additions

1: **entrée** : $\tilde{z} = \text{mask}(x) \in \mathcal{K}$
2: **sortie** : $\tilde{y} = \text{mask}(x^{-1}) \in \mathcal{K}$
3: $\tilde{x} \leftarrow \text{Mult2}(\tilde{z}, \tilde{z})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{x} \leftarrow \tilde{z}^2$
4: $\tilde{y} \leftarrow \text{Mult2}(\tilde{x}, \tilde{z})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{y} \leftarrow \tilde{z}^3$
5: $\tilde{w} \leftarrow \text{Mult2}(\tilde{y}, \tilde{y})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{w} \leftarrow \tilde{z}^6$
6: $\tilde{w} \leftarrow \text{Mult2}(\tilde{w}, \tilde{w})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{w} \leftarrow \tilde{z}^{12}$
7: $\tilde{y} \leftarrow \text{Mult2}(\tilde{w}, \tilde{y})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{y} \leftarrow \tilde{z}^{15}$
8: $\tilde{y} \leftarrow \text{Mult2}(\tilde{y}, \tilde{y})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{y} \leftarrow \tilde{z}^{30}$
9: $\tilde{y} \leftarrow \text{Mult2}(\tilde{y}, \tilde{y})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{y} \leftarrow \tilde{z}^{60}$
10: $\tilde{y} \leftarrow \text{Mult2}(\tilde{y}, \tilde{y})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{y} \leftarrow \tilde{z}^{120}$
11: $\tilde{y} \leftarrow \text{Mult2}(\tilde{y}, \tilde{y})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{y} \leftarrow \tilde{z}^{240}$
12: $\tilde{y} \leftarrow \text{Mult2}(\tilde{y}, \tilde{w})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{y} \leftarrow \tilde{z}^{252}$
13: $\tilde{y} \leftarrow \text{Mult2}(\tilde{y}, \tilde{x})$ &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{y} \leftarrow \tilde{z}^{254}$
14: **renvoyer** $\tilde{y}$

Maintenant que nous avons conçu les fonctions de base qui composent l'AES, il est temps de les utiliser pour calculer la transformation `MSubBytes` :
**Algorithm 26** MSubBytes($\tilde{z}$) Complexité: $136n + 36$ multiplications et $81n + 18$ additions

1: **entrée** : $\tilde{z} = \text{mask}(x) \in \mathcal{K}$

2: **sortie** : $\text{mask}(\text{SubBvtes}(x)) \in \mathcal{K}$

3: $\vec{v} \leftarrow \text{Inverse}(\tilde{z}) \qquad \vec{v} = \tilde{z}^{-1}$

4: $\vec{u} \leftarrow \text{mask}(63)$

5: $\lambda = \{05, 09, F9, 25, F4, 01, B5\}$ Les coefficients de SubBvtes

6: **pour** $i = 1$ **jusqu'à** 7 **faire** :

7: $\vec{u} \leftarrow \text{Add}(\vec{u}, \text{Mult1}(\lambda_i, \vec{v})) \qquad \vec{u} = \vec{u} + \lambda \cdot \vec{v}$

8: $\vec{v} \leftarrow \text{Mult2}(\vec{v}, \vec{v})$

9: $\vec{u} \leftarrow \text{Add}(\vec{u}, \text{Mult1}(8F, \vec{v})) \qquad \vec{u} = \vec{u} + 8F \cdot \vec{v}$

10: **renvoyer** $\vec{u}$

## 2.5 Détection et correction des erreurs

Pour pouvoir détecter et corriger les erreurs, il est important que la valeur masquée soit un mot de code, pour $n = 2$ l'espace d'arrivée $\mathcal{K}$ correspond à l'espace vectoriel $K^2$, la distance minimale étant 1, il est donc impossible de détecter les erreurs. Pour surmonter cela, il faut que $\mathcal{K}$ soit un sous-espace vectoriel de $K^n$ et donc un code correcteur d'erreur avec une distance minimale supérieure à 2. Nous proposons donc d'augmenter la taille de l'espace de départ à $n = 3$, et nous travaillons donc sur $\mathcal{K} \subsetneq K^3$.

Soient $\vec{g}, \vec{h}$ deux vecteurs dans $K^3 \setminus \{\vec{0}\}$ tels que : $\langle \vec{g}, \vec{h} \rangle = 0$, $\langle \vec{g}, \vec{g} \rangle \neq 0$ et $\langle \vec{h}, \vec{h} \rangle \neq 0$. Soient $\mathcal{C}$ et $\mathcal{D}$ les codes générés à partir de $\vec{g}$ et $\vec{h}$ respectivement. Le cardinal de $\mathcal{C}$ et $\mathcal{D}$ est $|\mathcal{C}| = |\mathcal{D}| = 2^8$. Soient $G, H \in \mathbb{F}_2^{8 \times 24}$ la matrice génératrice de $\mathcal{C}$ et $\mathcal{D}$ respectivement. On rappelle que dans ce cas $G$ et $H$ ne sont pas toujours orthogonales ($GH^\top \neq 0$). Notons $\mathcal{K} = \mathcal{C} \oplus \mathcal{D}$ l'ensemble des valeurs masquées (i.e. $\mathcal{K} = \{\tilde{z} = \vec{c} \oplus \vec{d} \mid \forall (\vec{c}, \vec{d}) \in \mathcal{C} \times \mathcal{D}\}$). La matrice génératrice de $\mathcal{K}$ est définie par :

$$J = \left\lfloor \frac{G}{H} \right\rfloor \in \mathbb{F}_2^{16 \times 24}.$$

### Propriété 16

$\mathcal{K}$ est un code linéaire, de paramètres $[24, 16, d_{\mathcal{K}}]$, avec une capacité de correction égale à :

$$\left\lfloor \frac{d_{\mathcal{K}}}{2} - 1 \right\rfloor.$$

Notons $L \in \mathbb{F}_2^{8 \times 24}$ la matrice de parité de $\mathcal{K}$, i.e. $JL^\top = 0$. Si l'on considère $\vec{u} = \tilde{z}+\vec{e}$ le mot masqué erroné, avec $\vec{e}$ le vecteur d'erreur. Le syndrome de décodage consiste