CRYPTOGRAPHIE APPLIQUEE

• 1. Contexte
1.1 Évolution vers une science
1.2 Objectifs de sécurité
1.3 Cryptographie moderne

• 2. Cryptographie symétrique
2.1 Généralités sur le chiffrement
2.1.1 Types d’attaques d’un système de chiffrement
2.1.2 Premiers systèmes de chiffrement
2.2 Primitives
2.2.1 Algorithmes de chiffrement par bloc
2.2.2 Algorithmes de chiffrement par flot
2.2.3 Fonction de hachage
2.3 Mécanismes cryptographiques
2.3.1 Modes opératoires de chiffrement
2.3.2 Code d’authentification de messages
2.3.3 Authentification de personne
2.3.4 Génération d’aléas

3. Cryptographie asymétrique
3.1 Rappels de mathématiques et d’algorithmique
3.1.1 Calcul modulaire
3.1.2 Exponentiation modulaire
3.2 Système de chiffrement asymétrique
3.2.1 Types d’attaque sur les schémas de chiffrement
3.2.2 Cryptosystème RSA
3.2.2.1 Principes
3.2.2.2 Sécurité
3.3 Mécanisme d’échange de clé et chiffrement hybride
3.3.1 Échange de clé Diffie-Hellman
3.3.2 Chiffrement hybride
3.4 Signature
3.4.1 Généralités sur les schémas de signature
3.4.2 Types d’attaques
3.4.3 Schémas de signature RSA, DSA et ECDSA
3.4.4 Applications des signatures à l’authentification

4. conclusion
INTRODUCTION
Aujourd’hui, les cryptographes ont défini des objectifs et des notions de
sécurité répondant aux besoins des utilisateurs en matière de sécurité
comme la confidentialité, l’intégrité et l’authentification. La cryptographie
est devenue une discipline scientifique à part entière qui utilise des
concepts mathématiques et informatiques pour prouver la sécurité des
schémas. Cependant, de nouvelles attaques viennent périodiquement
ébranler la confiance des utilisateurs.
Récemment deux attaques sur la norme de communications sécurisées
utilisée sur Internet, Secure Socket Layer (SSL), ont été largement
annoncées dans la presse et sur Internet. Ces attaques ne remettent pas
en cause les preuves de sécurité des systèmes mais montrent que la
modélisation des adversaires n’est pas idéale. En effet, pour traiter un
problème de manière théorique, les scientifiques ont besoin de modéliser
la réalité. En cryptographie, il est nécessaire de représenter les buts de
l’adversaire et ses moyens, c’est‐à‐dire ce qu’il cherche à faire et la
manière dont il interagit avec le système. C’est ici que la cryptographie
montre ses limites face à la réalité : il est difficile d’étudier de manière
exhaustive tous les adversaires possibles.

Après avoir rappelé les principes de conception des schémas

cryptographiques de chiffrement et de signature électronique, nous
décrirons quelques limites des systèmes actuels montrant ainsi la
difficulté à concevoir des systèmes sûrs.
• Cette difficulté est aujourd’hui liée à l’implémentation des schémas
cryptographiques dans des systèmes informatiques tels que des cartes à
puce, des cartes accélératrices, etc. Enfin, nous donnerons des exemples
de standards de communications sécurisées.

• Attaque : opération qui tente de violer les objectifs de sécurité d’un

cryptosystème.

• Authentification : preuve d’identité ou preuve de l’origine des données.

Ce terme regroupe l’identification, les signatures et les MAC.

• Cassage (total) : calcul de la clé secrète d’un utilisateur.

• Chiffrement : transformation appliquée à un message pour assurer sa

confidentialité. Il peut être déterministe ou probabiliste.

• Clé : valeur qui paramètre un cryptosystème. Si elle est confidentielle, on

parle alors de clé secrète ou privée, sinon on parle de clé publique.

• Confidentialité : assurance que seules les personnes autorisées ont accès

à l’information. Pour cela, on utilise des systèmes de chiffrement.
Contrefaçon : fabrication d’un objet sans en avoir le pouvoir légitime
(connaissance de la clé secrète). Contrefaire une signature ou un MAC.

Cryptanalyse : étude des procédés de décryptage, ou plus généralement de la

sécurité des cryptosystèmes.

Cryptographie : étude des procédés permettant d’assurer la confidentialité,

l’intégrité et l’authentification.

Cryptosystème (mécanisme cryptographique) : système de chiffrement et plus

généralement tout schéma de signature, de MAC ou de générateur pseudo-
aléatoire.

Déchiffrement : transformation inverse du chiffrement qui consiste à retrouver,

à l’aide d’une clé secrète, l’information initiale contenue dans le message chiffré.

Décryptage : action de « casser » le chiffrement, et donc de retrouver le texte

clair d’un chiffré, sans connaître la clé secrète.

Fonction à sens unique : fonction simple à calculer mais difficile à inverser.

Fonction à sens unique à trappe :fonction à sens unique pour laquelle une
information supplémentaire, appelée « trappe », facilite l’inversion.

Fonction de hachage : transformation déterministe d’une chaîne de bits de

taille variable en une chaîne de bits de taille fixe, telle que toute modification
de la valeur d’entrée modifie la valeur de sortie.

Générateur pseudo-aléatoire : transformation déterministe permettant de

produire une chaîne de bits apparaissant aléatoire à partir d’une entrée de
petite taille.

Identification : preuve d’identité lors d’un contrôle d’accès.

Intégrité : assurance qu’un message n’a pas subi de modifications volontaires
ou non.

MAC : donnée de taille fixe jointe à un message qui prouve l’identité de

l’émetteur et qui garantit l’intégrité du message. Contrairement aux
signatures, seules les personnes possédant la clé secrète peuvent vérifier un
MAC.

Objectifs de sécurité : les services assurés par les systèmes cryptographiques

Primitive : opération mathématique de base à partir de laquelle des
cryptosystèmes pourront être construits. Par exemple, la primitive de
chiffrement RSA consiste à calculer c = m e mod N où pk = (e, N ) est la clé
publique.

Protocole : ensemble de messages échangés entre plusieurs entités.

Système (ou schéma) : ensemble d’opérations reliées combinant une ou

plusieurs primitives entre elles avec d’autres techniques afin d’augmenter la
sécurité et éventuellement traiter des messages de taille variable. Le système
de chiffrement RSA consiste à rajouter un padding puis à utiliser la primitive de
chiffrement RSA. Il est d’usage de parler de schéma de signature et de système
de chiffrement.

Signature : donnée de taille fixe jointe à un message et qui prouve l’identité de

l’émetteur, garantit l’intégrité du message et assure la non-répudiation. Tout
le monde ayant accès à la clé publique peut vérifier la signature.
1. Contexte

1.1 Évolution vers une science

1.2 Objectifs de sécurité

1.3 Cryptographie moderne

La cryptographie a pour but de garantir la protection des communications
transmises sur un canal public contre différents types d’adversaires. La
protection des informations se définit en termes de confidentialité,
d’intégrité et d’authentification.

La confidentialité garantit que les données transmises ne sont pas

dévoilées à une tierce personne.

L’intégrité assure que ces données n’ont pas été modifiées entre
l’émission et la réception.

Enfin, l’authentification de message assure qu’elles proviennent bien de la

bonne entité et l’authentification de personne, aussi appelée
identification, garantit qu’une entité qui cherche à s’identifier vis‐à‐vis
d’un système informatique est bien celle qu’elle prétend être.

On distingue traditionnellement les systèmes symétriques et

asymétriques. En cryptographie conventionnelle, aussi appelée
cryptographie symétrique (ou à clé secrète), les correspondants partagent
la même clé pour chiffrer et déchiffrer.
L’histoire de la cryptographie symétrique est très ancienne, mais les
connaissances académiques dans ce domaine sont assez récentes et
remontent à l’invention du système de chiffrement par bloc appelé Data
Encryption Standard (DES) au début des années 1970. En 1976, Diffie et
Hellman ont révolutionné la cryptographie en inventant des systèmes
asymétriques dans lesquels émetteur et récepteur ne partagent plus de clé
commune : une clé, rendue publique, permet de chiffrer un message, la
seconde est gardée secrète et permet au destinataire de déchiffrer. Cette
découverte a modifié la cryptographie car jusqu’alors, pour envoyer un
message chiffré, les correspondants devaient s’échanger au préalable une
information secrète : la clé. En inventant la cryptographie asymétrique, Diffie
et Hellman ont conçu un système où les correspondants peuvent s’échanger
une information secrète sans se rencontrer.

Exemple :
cela permet aujourd’hui d’échanger un code de carte bleue avec un site
marchand sans avoir besoin de rencontrer auparavant le responsable du
site.
Dans leur article, ils montrent aussi comment la cryptographie à clé publique
permet de résoudre le problème des signatures électroniques, sans toutefois
proposer un tel système. Cependant, ils décrivent les propriétés des
Trois chercheurs du MIT (Massachusetts Institute of Technology) ont
alors tenté de prouver que de telles fonctions n’existent pas jusqu’au
jour où en 1977, ils en ont trouvé une. Cette fonction est aujourd’hui
appelée RSA des noms des chercheurs Rivest, Shamir et Adleman.
Aujourd’hui, la cryptographie à clé publique a permis de résoudre de
nombreux problèmes pratiques mais elle reste beaucoup moins utilisée
que la cryptographie à clé secrète. En effet, elle demande la mise en
place d’infrastructures à clé publique (Public-Key Infrastructure : PKI). De
plus, les systèmes symétriques offrent de bien meilleures performances
et ne requièrent pas l’utilisation d’une infrastructure spécifique. Comme
nous allons le voir dans la suite, l’association des deux types de
cryptographie permet de concevoir des systèmes sûrs, efficaces et
pratiques.
Mais la cryptographie moderne a aussi permis de résoudre des
problèmes complètement nouveaux. Par exemple, elle a développé des
techniques permettant de convaincre quelqu’un que l’on connaît un
secret sans révéler la moindre information sur ce secret. Ces méthodes,
appelées à divulgation nulle de connaissance (zero-knowledge ), ont
permis la création de systèmes d’identification et se sont aussi avérées
très utiles pour prouver la sécurité de protocoles cryptographiques.
1.1 Évolution vers une science

L’histoire de la cryptographie a été pendant longtemps l’histoire des codes

secrets et depuis l’Antiquité, ils ont décidé du sort des hommes et des
nations. En effet, jusqu’aux années 1970, l’unique objectif de la
cryptographie était de construire des systèmes de chiffrement. Les
cryptosystèmes sauvèrent les Grecs des Perses, accompagnèrent César dans
ses conquêtes, firent arrêter et décapiter Marie Stuart, décidèrent Wilson à
rejoindre les Alliés et permirent d’épargner des milliers de vies pendant la
Seconde Guerre mondiale.

L’invention de la radio a donné un nouvel élan à la cryptographie, car il est

devenu encore plus facile d’intercepter une communication longue distance.
La Seconde Guerre mondiale a été profondément affectée par l’utilisation de
la cryptographie et le cassage des systèmes cryptographiques utilisés pour les
communications radio. Il est intéressant de voir que les premières machines
calculatoires conçues et construites par les Britanniques pour casser le
système de chiffrement allemand, Enigma, sont les premiers exemples réels
d’« ordinateurs », si bien que l’on peut dire que la cryptographie est à
l’origine de l’informatique.
La révolution d’Internet et l’utilisation de plus en plus massive d’informations
sous forme numérique facilitent les communications et rendent de ce fait
plus fragiles les informations que l’on détient. En effet, les réseaux
« ouverts » créent des brèches de sécurité car il est plus aisé pour un
adversaire d’accéder aux informations. De même, le remplacement de
l’Homme par des machines rend les relations beaucoup plus anonymes alors
qu’en même temps, l’accès aux données demande des moyens
d’authentification forts. De plus, la dématérialisation des documents change
les moyens de preuve juridique : les signatures numériques doivent remplir
certaines exigences que nous ne connaissions pas avec les signatures
manuscrites. Ainsi, la révolution numérique des communications et de
l’information a ouvert de nombreux champs d’investigation à la
cryptographie, différents du seul besoin de confidentialité, de sorte que
celle‐ci a envahi notre vie quotidienne : carte à puce, transaction bancaire,
Internet, téléphone cellulaire, télévision à péage...

Dans le même temps, la cryptologie est devenue une science. La cryptologie,

la science du secret d’après son étymologie grecque, comprend d’une part la
cryptographie, art de la conception de systèmes sécurisés, et d’autre part la
cryptanalyse, art du cassage des systèmes. Par abus de langage, nous
emploierons souvent le terme cryptographie à la place de cryptologie.
Les différentes techniques employées, mélangeant mathématiques classiques
du XVIIIe siècle et informatique théorique, lui confèrent aujourd’hui une place
à part parmi les sciences. Depuis les années 1970, on a assisté à une
explosion de la recherche en cryptographie. Beaucoup de systèmes ont été
proposés, et beaucoup ont été détruits. Notre compréhension de la notion
subtile de « sécurité cryptographique » a constamment progressé et, de nos
jours, les cryptosystèmes sont prouvés sûrs (sous certaines hypothèses
plausibles). Les relations fascinantes entre la cryptographie, la théorie de la
complexité et la théorie algorithmique des nombres ont petit à petit enrichi
ces trois domaines de recherche.
1.2 Objectifs de sécurité

Commençons par voir quels services de sécurité peut garantir la

cryptographie et quelles sont ses applications dans la vie « quotidienne ».

La cryptographie ne permet pas de résoudre tous les problèmes de sécurité

informatique. Cependant, elle apporte des garanties et des briques de base
sur lesquelles des produits peuvent être construits. Il est bien connu que la
sécurité d’un système se mesure à son maillon le plus faible. En général, le
maillon le plus faible d’un système informatique n’est pas le système
cryptographique mais, par exemple, son implémentation informatique.

En outre, il existe diverses attaques contre lesquelles la cryptographie n’est

pas d’un grand secours, comme les virus informatiques ou les chevaux de
Troie logiciels qui profitent de la confiance exagérée des utilisateurs dans les
messages qu’ils reçoivent ou dans les logiciels qu’ils utilisent (voir
l’article[H 5 440]).
La cryptographie participe à la sécurité informatique en proposant des
primitives et des mécanismes permettant d’atteindre les objectifs de
confidentialité, de protection en intégrité et d’authentification. Pour assurer
le service de confidentialité, la cryptographie propose des systèmes de
chiffrement à clé secrète ou à clé publique. La protection en intégrité et
l’authentification de l’origine des données peuvent être assurées en utilisant
des codes d’authentification de messages (cryptographie à clé secrète) ou des
signatures électroniques (cryptographie à clé publique). Enfin, le service
d’identification peut être garanti par l’utilisation de preuves d’identité.

1.3 Cryptographie moderne

La cryptographie ne se contente plus aujourd’hui de construire des systèmes.
On demande bien souvent qu’une preuve de sécurité soit apportée,
permettant d’estimer la sécurité du schéma. Ainsi, pendant de nombreuses
années, cryptographes et cryptanalystes se sont combattus et tour à tour les
uns prenaient le dessus sur les autres. De nos jours, il est rare qu’un nouveau
système soit proposé sans preuve. Mais qu’est-ce qu’une preuve de sécurité ?
Comment évalue-t-on la force des adversaires ? Que cherchent-ils à casser ?
Et quels sont leurs moyens ?
:

Les travaux de Shannon dans les années 1940 sur les communications
(théorie de l’information) sont précurseurs des futurs travaux théoriques en
cryptographie. En particulier, l’article intitulé Communication Theory of
Secrecy Systems a dégagé et étudié la notion d’entropie et a prouvé la
sécurité parfaite du schéma de chiffrement de Vernam. Shannon a aussi
présenté des notions importantes sur la sécurité d’un protocole
cryptographique en distinguant sécurité inconditionnelle et sécurité
calculatoire. Dans le premier cas, on suppose que l’adversaire a une
ressource de temps infini, alors que dans le second cas, l’adversaire est borné
dans le temps.

Il ne peut effectuer qu’un nombre fini d’étapes de calcul, d’où le nom de

sécurité calculatoire. Il est en effet raisonnable de penser que si, pour casser
un système, il faut utiliser un million de machines pendant un million
d’années, alors le système est sûr. En pratique, on suppose que pour casser
un système cryptographique, l’adversaire a accès à plusieurs ordinateurs. On
peut quantifier le nombre d’opérations qu’il peut faire ainsi que le nombre
d’informations qu’il est capable de stocker.
Par exemple, un ordinateur cadencé à 1 GHz effectue un milliard de cycles
par seconde, soit environ 2 30 opérations élémentaires en 1 s. Si un million
d’ordinateurs à 1 GHz fonctionnent pendant cent mille ans, alors ils sont
capables d’effectuer environ 2 92 opérations. D’un point de vue pratique,
on dira qu’un système est sûr si le nombre d’opérations minimales pour le
casser nécessite plus de 2 80 opérations. Si on veut se protéger de manière
plus sûre, on augmentera le niveau de sécurité à 2128.

La formalisation de la sécurité d’un protocole n’a pas été sans difficulté.

On verra que plusieurs définitions sont possibles pour définir la
confidentialité d’un système de chiffrement. Les preuves de sécurité
permettent de relier le cassage d’un système à un problème réputé Par
conséquent, pour l’attaquant, il n’existe pas de méthode permettant de
casser le système cryptographique sans savoir aussi résoudre le problème
conjecturé difficile. Ainsi, il a tout intérêt à tenter de résoudre le problème
sous-jacent. D’un point de vue théorique, les cryptographes établissent
des relations entre différents problèmes de la même manière qu’en
théorie de la complexité, où des relations entre des problèmes différents
sont établies difficile.
 On dit qu’un problème est difficile s’il n’existe pas d’algorithme pour le
résoudre en temps polynomial.

Nota :

la complexité en temps est polynomiale si le nombre d’étapes de calcul T

qui dépend du paramètre de sécurité k s’exprime comme un polynôme en
k : il existe une constante c > 0 telle que T (k) < k c pour k suffisamment
grand.
La complexité des problèmes difficiles (nombre d’opérations pour les
résoudre) est donc au moins superpolynomiale ou bien même
exponentielle : le temps nécessaire pour les résoudre est proportionnel à
2 k si k représente la taille des entrées en bits. Ces problèmes sont difficiles
car le temps de calcul est multiplié par 2 chaque fois que la taille des
entrées augmente d’un bit !
En théorie de la complexité, on distingue la classe de complexité appelée ,
pour polynomiale, qui regroupe l’ensemble des problèmes ayant des
algorithmes efficaces pour les résoudre et la classe des problèmes pour
lesquels aucun algorithme efficace (polynomial) n’est connu pour les
résoudre. Enfin, si la célèbre conjecture s’avérait fausse, toute
construction théorique de cryptosystèmes sûrs et efficaces serait vouée à
l’échec.
Il est d’usage de distinguer les algorithmes cryptographiques en deux
catégories : les primitives et les cryptosystèmes ou mécanismes
cryptographiques. Les primitives sont des briques de base ayant certaines
propriétés et qui permettent de concevoir des mécanismes. Les
cryptosystèmes sont censés garantir la confidentialité, l’intégrité et/ou
l’authentification.
Si l’on montre qu’il existe une attaque contre ces mécanismes, alors cette
attaque doit aussi permettre de montrer que les primitives ne vérifient
pas les propriétés qu’elles étaient supposées satisfaire.
 Enfin, il est important de voir que la cryptographie moderne fait
son entrée depuis quelques années dans les organismes de
standardisation tels que l’Organisation internationale de normalisation
(ISO), l’American National Standards Institute (ANSI), l’Internet
Engineering Task Force (IETF) et le National Institute of Standards and
Technology (NIST). En effet, il existe différents projets internationaux
(P1363), européens (NESSIE) ou japonais (Cryptrec) visant à évaluer la
sécurité de certains algorithmes. Jusqu’à présent, les normes en matière
de sécurité étaient conçues à partir de schémas heuristiquement sûrs,
c’est‐à‐dire pour lesquels il n’existait pas d’attaques connues. Cependant,
comme de nombreux standards ont été cassés par la communauté
cryptographique, les organismes de standardisation sont demandeurs de
tels projets au cours desquels les schémas sont évalués par des
spécialistes du domaine.
2. Cryptographie symétrique

2.1 Généralités sur le chiffrement

2.1.1 Types d’attaques d’un système de chiffrement
2.1.2 Premiers systèmes de chiffrement

2.2 Primitives
2.2.1 Algorithmes de chiffrement par bloc
2.2.2 Algorithmes de chiffrement par flot
2.2.3 Fonction de hachage

2.3 Mécanismes cryptographiques

2.3.1 Modes opératoires de chiffrement
2.3.2 Code d’authentification de messages
2.3.3 Authentification de personne
2.3.4 Génération d’aléas
La cryptographie symétrique est très souvent utilisée bien qu’elle souffre
de problèmes inhérents au fait qu’émetteur et récepteur doivent partager
la même clé.

Le premier argument en faveur des systèmes symétriques est qu’ils sont

plus rapides que les systèmes asymétriques car ils utilisent directement
les instructions câblées des processeurs du commerce. En effet, la
cryptographie à clé publique requiert l’utilisation de l’arithmétique sur les
grands nombres qui n’est pas implémentée dans les processeurs des
ordinateurs usuels.

Dans un premier temps, nous présentons quelques primitives

(algorithmes de chiffrement par bloc, par flot et fonctions de hachage) qui
permettent de construire les protocoles ou mécanismes garantissant la
confidentialité, l’intégrité et l’authentification de l’origine des données
(systèmes de chiffrement et codes d’authentification de message : MAC).
 2.1 Généralités sur le chiffrement

Un algorithme de chiffrement se compose des éléments suivants :

• l’espace des messages : un ensemble de chaînes de bits (messages
clairs) ;
• l’espace des messages chiffrés : un ensemble de chaînes de bits
(messages chiffrés) ;
• l’espace des clés K : un ensemble de chaînes de bits (clés) ;
• un algorithme de chiffrement prenant ses entrées dans K × et ses sorties
dans ;
• un algorithme de déchiffrement prenant ses entrées dans K × et
retournant un élément de .
Les algorithmes vérifient de plus la relation suivante : pour toute clé k Î ,
pour tout message
• 2.1.1 Types d’attaques d’un système de chiffrement

Il existe plusieurs objectifs pour un adversaire. Si l’adversaire trouve la clé

de déchiffrement, on dit alors que le système est complètement cassé. S’il
est capable de déchiffrer tous les messages, on dit que le système est
cassé. Un objectif moins fort est de déchiffrer un chiffré cible c * donné.
Enfin, dans certaines applications, on souhaite qu’aucun bit du clair ne
puisse être appris à la vue du chiffré. On parle alors de sécurité
sémantique. On formalise cet objectif sous la forme du jeu suivant : dans
une première phase, l’adversaire choisit deux messages différents M 0 et
M 1 de même taille et les envoie à un oracle de chiffrement. Ce dernier
choisit aléatoirement un bit b. Si b = 0, il chiffre le message M 0 et si b = 1,
il chiffre M 1 . Le chiffré c * correspondant est renvoyé à l’adversaire. Le
but de l’adversaire est de deviner correctement quel message a été chiffré
dans c *. Il est clair qu’avec une probabilité de 1/2, l’adversaire devine le
bit b.
 On définit son avantage de gagner ce jeu comme étant la différence entre
la probabilité qu’il devine correctement le bit b et 1/2, et on dit que
l’adversaire gagne le jeu de la sécurité sémantique si son avantage est non
négligeable, c’est‐à‐dire qu’il existe une constante c > 0 telle que
l’avantage de l’adversaire soit supérieur à 1/k c où k représente le
paramètre de sécurité, soit la taille en bits de la clé k. La probabilité est
prise sur l’espace composé du bit b, de la chaîne d’aléa de l’adversaire et
de la chaîne aléatoire de l’oracle de chiffrement si le chiffrement est
randomisé.

Pour atteindre ces objectifs, l’adversaire a accès à certains moyens :

• dans une attaque à chiffrés seuls, l’adversaire intercepte des messages
chiffrés mais ne connaît pas le clair correspondant ;
• dans une attaque à clairs connus (known plaintext attack ), l’adversaire
connaît des paires clairs/chiffrés pour des messages clairs non choisis ;
• dans une attaque à clairs choisis (chosen plaintext attack ), l’adversaire a
accès à une machine de chiffrement et peut obtenir le chiffré de
n’importe quel message clair ;
• enfin, dans une attaque à chiffrés choisis (chosen ciphertext attack ),
l’adversaire a accès à une machine de déchiffrement. Il peut obtenir le
clair de tout chiffré sauf celui de c *.
• 2.1.2 Premiers systèmes de chiffrement

• Une pratique saine en cryptographie est que la description des

algorithmes de chiffrement et de déchiffrement soit publique et que seule
une donnée de petite taille, appelée la clé, soit détenue de manière
secrète. Ces principes de base constituent les « principes de Kerckhoffs »
du nom du militaire français qui les énonça en 1883. En effet, la sécurité
d’un mécanisme cryptographique ne peut être assurée par son secret. La
description peut toujours être plus ou moins rapidement obtenue par les
attaquants. Par conséquent, afin de raisonner correctement et de
concevoir des systèmes sûrs, autant supposer que les algorithmes sont
publics. Cela permet une analyse sérieuse de l’algorithme par toute la
communauté des cryptologues.

• Le but du chiffrement est de garantir la confidentialité des

communications. Les premiers algorithmes de chiffrement étaient basés
sur les principes de substitution et de permutation.

• Le chiffrement de César est un exemple de chiffrement par substitution,

où l’on chiffre une lettre du clair par une lettre située deux positions
(modulo 26) plus loin dans l’alphabet. Ainsi, la lettre « a » est remplacée
lors du chiffrement par la lettre « c », la lettre « b » par la lettre « d », ...,
• la lettre « x » par la lettre « z », la lettre « y » par la lettre « a » et la lettre
« z » par la lettre « b ». L’inconvénient de ce système est que les
propriétés statistiques du langage du message clair ne sont pas modifiées.
Par exemple, la lettre la plus courante en anglais est le « e ». Ainsi en
observant la lettre la plus fréquente dans le message chiffré, on en
déduira que cette lettre correspond au chiffrement de la lettre « e », si le
message clair est en anglais. Afin d’éliminer ces propriétés statistiques, les
cryptographes ont construit des systèmes de substitution
polyalphabétique : une même lettre en clair peut être chiffrée de
différentes manières.

• On peut citer ici le chiffrement de Vigenère, cassé par Babbage et Kasiski.

Dans le système de Vigenère, la clé est un mot de passe, CRYPTO par
exemple. Pour chiffrer la première lettre du message DEMAIN ATTAQUE,
on utilise la première lettre du mot de passe, C, qui indique de combien
de positions on doit décaler la lettre D. Il peut être utile de représenter les
lettres par des nombres et de les additionner modulo 26. La lettre A sera
représentée par 0 et la lettre Z par 25. Les espaces sont éliminés. Ainsi, D
sera chiffrée par la lettre C pour obtenir la lettre F. Pour chiffrer la
deuxième lettre du clair E, on utilise la deuxième lettre du mot de passe,
R, et le chiffrement est V. On continue jusqu’à la fin du mot de passe, puis
on recommence au début. Ainsi, le chiffré complet est FVKPBBCKRPKIG. Il
est facile de voir que les lettres A et E sont chiffrées de deux façons
différentes.
En cryptanalyse, on appelle recherche exhaustive ou attaque par force
brute, une attaque qui consiste à tester toutes les clés de déchiffrement
pour retrouver le clair. Cependant, pour casser le système de Vigenère, la
recherche exhaustive sur la clé peut prendre un temps très grand selon sa
longueur. En effet, pour toute longueur t du mot de passe, il existe (26)t
mots de passe différents. Si l’on teste tous les mots de passe ayant 20
lettres, il faut effectuer 292 tests, ce qui est totalement hors de portée. La
cryptanalyse de ce système a donc requis l’utilisation de techniques plus
fines que la force brute. Elle est basée sur l’observation que si la même
lettre apparaît décalée d’un multiple de la longueur du mot de passe,
alors elle sera chiffrée de la même façon. Cela permet de déduire la
longueur de la clé. Des statistiques sur les lettres montrent que certains
digrammes ou trigrammes (combinaison de 2 ou 3 lettres consécutives)
sont plus fréquentes que d’autres. Par exemple, le trigramme « the » en
anglais apparaît très fréquemment alors que la probabilité d’apparition du
trigramme « xyz » est quasi nulle.
 Toutes ces observations ont permis d’attaquer efficacement le
chiffrement de Vigenère. Pour diffuser certaines propriétés statistiques du
langage clair (comme la fréquence de digrammes ou de trigrammes) sur
tout le message chiffré, l’idée est d’échanger la position des lettres entre
le clair et le chiffré : c’est le principe du chiffrement par permutation.
Pendant longtemps, les systèmes de chiffrement étaient basés sur une
succession de substitutions et de permutations. Encore au début du XX e
siècle, les machines électriques à rotors, comme Hagelin ou Enigma,
étaient basées sur ces opérations.

• En 1926, l’américain Vernam proposa un système de chiffrement basé sur

le même principe que le chiffrement de Vigenère mais où cette fois la clé
est aussi longue que le message. Par conséquent, une même lettre peut
être chiffrée en autant de lettres possibles qu’il y a de lettres dans
l’alphabet. Il est d’usage pour présenter ce système d’utiliser l’alphabet
binaire composé de 0 et de 1 : selon un codage approprié de l’alphabet,
on peut représenter n’importe quelle lettre par une suite de quelques
bits.
• C’est le principe du codage ASCII par exemple. Pour générer une clé de
chiffrement, on génère une suite aléatoire de 0 et de 1. Le chiffré du
message m sous la clé k est c = m Å k où Å désigne le XOR des deux
chaînes binaires m et k (encadré 1). Pour déchif- frer ce message, il
convient de calculer c Å k = (m Å k ) Å k = m Å (k Å k ) = m Å 0 n = m, où n
représente la taille du message m et 0n désigne la chaîne de bits
composée de n bits à zéro.
• En 1940, Shannon prouva que ce système était sûr contre n’importe quel
adversaire ayant une puissance de calcul infinie sous réserve que la clé
soit aussi longue que le message et qu’elle ne soit utilisée qu’une seule
fois. Ainsi, dans ce système, aussi appelé One-Time Pad, la recherche
exhaustive sur les clés est impossible. En effet, à chaque chiffré
correspondent tous les clairs possibles : pour tout message clair m ′, on
peut trouver une clé k ′ telle que c ′ soit le chiffré de m ′ : c ′ = m ′ Å k ′.
Cela a permis aux espions russes durant la Guerre froide de ne pas être
arrêtés mais uniquement soupçonnés. En effet, comme ils déchiraient de
leur carnet la clé de chiffrement, n’importe quel message clair était
possible. L’inconvénient principal de ce système est l’échange et la gestion
des clés : si l’on désire chiffrer un message d’un gigabit, il faut auparavant
échanger un gigabit de clé et cette clé échangée ne servira qu’une seule
fois !
• Cependant, Shannon démontra aussi que l’on peut construire des
systèmes de chiffrement sûrs en utilisant les propriétés de confusion et de
diffusion où une même clé de chiffrement, de petite taille, peut être
utilisée pour chiffrer plusieurs messages. La propriété de confusion
cherche à rendre complexes les relations entre le chiffré et la clé et entre
le chiffré et le clair. En effet, comme le chiffré peut être intercepté, il doit
être impossible d’exploiter des relations avec la clé ou avec le clair. La
propriété de diffusion dissipe les propriétés statistiques du clair en les
répartissant dans le chiffré et diffuse sur tout le chiffré l’influence du
changement d’un bit de clé ou de clair. Cependant, les systèmes basés sur
ces propriétés ne seront plus « inconditionnellement sûrs» comme le
système de Vernam, mais uniquement « calculatoirement sûrs ». On
montre dans la suite (§ 2.2.1 et 2.2.2 ) comment construire de tels
systèmes, sûrs « en pratique ».

• L’opération binaire appelée XOR ou OU exclusif, notée Å, est équivalente

au calcul modulo 2. Cette opération est associative et commutative. La
table de vérité est la suivante : 0 Å 0 = 0 ; 0 Å 1 = 1 ; 1 Å 0 = 1 et 1 Å 1 = 0.
On étendra cette notation aux chaînes de bits en considérant que les
opérations de XOR se font bit à bit. Ainsi, les propriétés importantes sont :
quelle que soit la chaîne de bit a codée sur n bits, a Å a = 0 n et a Å 0 n = a
si 0 n représente la chaîne de n bits à 0.
• 2.2 Primitives

• Nous décrivons ici les primitives de cryptographie symétrique que sont les
algorithmes de chiffrement par bloc, par flot et les fonctions de hachage.

• 2.2.1 Algorithmes de chiffrement par bloc

• Les algorithmes de chiffrement par bloc (block ciphers ) sont parmi les
primitives les plus importantes dans les systèmes cryptographiques. Ils
assurent la confidentialité, mais ils peuvent aussi être utilisés dans la
construction d’autres primitives ou mécanismes comme les générateurs
aléatoires, les algorithmes de chiffrement par flot, les codes
d’authentification de messages ou les fonctions de hachage.
• Les block ciphers opèrent sur des messages clairs de taille fixe. Un block
cipher est une fonction qui envoie un bloc de n bits de clair vers un bloc
de n bits de chiffré. On peut les voir comme un chiffrement par
substitution sur un grand ensemble de caractères : chaque bloc de 64 bits
est substitué par un autre bloc de 64 bits. Cette fonction est paramétrée
par une clé k de bits, tirée aléatoirement. Afin de permettre le
déchiffrement unique, la fonction de chiffrement doit être bijective
(inversible). Ainsi l’espace des messages clairs et celui des chiffrés sont
tels que , et l’espace des clés est .

• Un chiffrement (parfaitement) aléatoire est un block cipher

implémentant toutes les (2 n ) ! bijections possibles sur les 2 n éléments.
Chacune des (2 n ) ! clés spécifie une permutation. Si la taille des blocs est
trop petite, le système est alors vulnérable aux attaques basées sur les
analyses statistiques comme le système de chiffrement par substitution
de César . Comme on le verra par la suite, cela peut être évité en utilisant
des modes opératoires. D’autres attaques peuvent aussi être considérées
mais leur complexité augmente très rapidement avec la longueur du bloc
ou de la clé. En pratique, pour des valeurs de n et suffisamment grandes,
les block ciphers « apparaissent » comme aléatoires (pour quelqu’un qui
n’a pas la clé). On notera E la fonction de chiffrement et D la fonction de
déchiffrement.
• Il existe deux grandes familles de chiffrement par bloc. La première famille
est celle des schémas basés sur des réseaux de Feistel et est connue
depuis l’invention du DES en 1976. La seconde famille contient les
schémas basés sur des réseaux de substitution-permutation, aussi
appelés SP Networks. Elle a été introduite plus récemment. L’AES
(Advanced Encryption Standard), le successeur du DES, est issu de cette
famille. Ces deux grandes familles font partie des algorithmes de
chiffrement par bloc itéré mettant en jeu la répétition séquentielle d’une
fonction interne appelée fonction de tour. Les paramètres incluent le
nombre de tours r (rounds), la taille n du bloc, et la taille de la clé k à
partir de laquelle r sous-clés k i sont dérivées. À cause de l’inversibilité
(permettant un déchiffrement unique), pour chaque valeur k i , la fonction
de tour est une bijection. Le choix du nombre de tours est important :
c’est un compromis entre sécurité (beaucoup de tours) et efficacité (peu
de tours). La clé est alors répartie par un algorithme de dérivation de clé
(key scheduling ) en r sous-clés. Le schéma général du DES est donné sur
la figure 1.
Figure 1 - Schéma général du Data Encryption Standard (DES)
• Comme nous l’avons vu, un algorithme de chiffrement par bloc doit être
une permutation afin que la fonction de déchiffrement permette
d’obtenir un unique antécédent. Or il est « assez » facile de construire des
fonctions à clé ressemblant à des fonctions aléatoires, c’est‐a‐dire ayant
les propriétés de confusion et de diffusion en utilisant des XOR avec la clé,
des substitutions et des permutations. Les réseaux de Feistel (figure 2 et
encadré 2) sont une construction générique permettant de transformer
une fonction en une permutation.
Figure 2 - Réseau de Feistel
• Le but d’un réseau de Feistel est de transformer une fonction F en
permutation. Autrement dit, la fonction F n’est pas forcément
bijective, mais la fonction

G : (L i , R i ) (L i +1 = R i , R i +1 = (R i ) Å L i ) est bijective. En effet, il est

possible d’inverser (L i +1, Ri +1) de manière unique. ETant donné
(L i +1, R i +1), on pose

R i = L i +1, puis L i = (L i +1) Å R i +1. Il est facile de verifier que

L i = (L i +1) Å R i +1 car (L i +1) Å R i +1
= (R i ) Å R i +1 = (R i ) Å (R i ) Å L i = L i .

• Le problème avec les réseaux de Feistel est que seule une moitié des
bits L i est mixée à chaque tour. L’autre moitié R i se retrouve au tour
suivant L i +1 sans être modifiée. Ainsi, par rapport à un réseau SP, où
tous les bits du bloc sont mixés à chaque tour, il faudra environ deux
fois plus de tours pour une sécurité équivalente aux schémas de cette
famille.
Figure 3 - Tour d’un réseau SP
• Le DES est un algorithme de chiffrement par bloc basé sur un réseau de
Feistel utilisant des clés de 56 bits et des sous-clés de 48 bits. La taille des
blocs est de 64 bits et il y a 16 tours. Nous renvoyons à la norme FIPS
PUB 81 pour la description de ce schéma. Le nombre total des clés
possibles est 256. Un adversaire qui possède un couple clair/chiffré peut
alors essayer toutes les clés pour retrouver la clé utilisée. Une attaque qui
retrouve la clé s’appelle une key recovery attack. En 1970, on pensait
qu’essayer les 256 clés différentes était une opération impossible en
pratique sauf peut-être pour quelques organisations. De nos jours, un
regroupement d’ordinateurs sur Internet ou la construction de machines
dédiées permet d’effectuer 256 chiffrements DES en un jour. Le NIST a
donc proposé d’utiliser l’algorithme Triple-DES (3DES) : pour chiffrer un
bloc de clair M, il est d’abord chiffré avec le DES et une clé k 1 , puis le
résultat est déchiffré avec une deuxième clé k 2 et enfin rechiffré avec une
clé k 3 : .
Par conséquent, la taille des clés est de 3 × 56 = 168 bits et le temps
d’exécution est trois fois plus important que pour le DES. Une autre
solution aurait été de faire trois chiffrements. Cependant, avec cet
algorithme, si k 2 = k 3 ou k 1 = k 2 , on obtient un algorithme équivalent à
l’algorithme DES. On peut aussi se demander pourquoi le NIST a proposé
le Triple-DES et non le double DES. En fait, il existe une attaque sur le
double DES demandant le même temps qu’une attaque exhaustive sur le
simple DES et exigeant environ 263 bits de mémoire. Pour cette raison, le
NIST a proposé d’utiliser directement le 3DES, pour lequel le même type
d’attaque a une complexité en temps de 2112 et en mémoire 263 bits.
• Il existe aussi une autre version du 3DES, appelée 3DES 2 clés pour lequel
• k 3 = k 1 . Cette variante permet de diminuer la taille de la clé, sans pour
autant affaiblir le schéma. Cependant, les mauvaises performances du
3DES et l’arrivée de réseaux informatiques de plus en plus rapides ont
accéléré le remplacement du 3DES. Son successeur, l’AES, a été
standardisé par le NIST en 2000 (FIPS PUB 197).

• L’AES est un algorithme de chiffrement par bloc basé sur un réseau SP

utilisant des clés de 128, 192 ou 256 bits. Le nombre de tours dépend de
la taille des clés : pour des clés de 128 bits, 10 tours sont nécessaires, 12
tours pour des clés de 192 bits et 14 tours pour des clés de 256 bits. Enfin,
la taille des blocs est de 128 bits. Nous renvoyons à la norme FIPS PUB 197
pour la description détaillée de ce schéma.

• Chaque tour d’un block cipher issu de la famille des réseaux SP est
constitué d’une succession d’un XOR avec la sous-clé du tour, d’une
couche de substitution et d’une couche de permutation (figure 3). Les
fonctions de la couche de substitution et de la couche de permutation
sont de garantir la confusion et la diffusion.
• 2.2.2 Algorithmes de chiffrement par flot

• Les algorithmes de chiffrement par flot (stream cipher ) sont une classe
importante d’algorithmes de chiffrement. Ils chiffrent individuellement
chaque caractère (ou bit) d’un message clair, un à la fois, en utilisant une
transformation qui évolue grâce à une fonction de mise à jour. Par
opposition, les algorithmes de chiffrement par bloc chiffrent
simultanément des groupes de caractères (ou bits) du clair en utilisant
une transformation fixe. Les stream ciphers sont généralement plus
rapides que les block ciphers en hardware et ont des circuits moins
complexes. Ils sont aussi plus appropriés dans certains contextes (comme
les communications téléphoniques) quand le stockage temporaire des
données avant réémission est limité ou que chaque caractère doit être
traité dès qu’il est reçu. Enfin, ils ont la propriété de ne pas avoir de
propagation d’erreur et sont donc avantageux quand des erreurs de
transmission sont très probables, par exemple dans les communications
mobiles. Cependant, la théorie dans ce domaine, assez proche de celle
des générateurs aléatoires, n’est pas encore bien établie, contrairement à
celle des block ciphers.

• La construction de stream ciphers est basée sur le principe du chiffrement

de Vernam, mais évite ses inconvénients : la clé est différente et aussi
longue que le message mais elle est issue d’une autre clé, fixe et de petite
taille.
• Pour ce faire, les stream ciphers génèrent, à partir d’une clé de petite
taille, un flot d’aléa vu comme une clé aléatoire plus longue servant à un
système de Vernam. La clé aléatoire, appelée clé du flot (keystream), peut
être générée bit par bit ou octet par octet suivant le système.
L’algorithme permettant la génération de la clé du flot est un générateur
pseudo-aléatoire (GPA) : k s = GPA (k ), c = m Å k s .

• Les algorithmes de chiffrement par flot ont l’avantage d’être très rapides.
En revanche, ils présentent des propriétés qui ne sont pas forcément
souhaitables comme la malléabilité du chiffré : étant donné un chiffré c
correspondant à un clair m, il est facile d’obtenir le chiffré du clair m Å δ
en calculant c Å δ. Ainsi, bien qu’un adversaire ne connaisse pas le clair, il
est capable de modifier le chiffré et de maîtriser la modification induite
sur le clair. De même, si l’on sait que c correspond au chiffré du message
m, on peut calculer le chiffré de n’importe quel clair m ′ en calculant
c Å m Å m ′ = m Å k s Å m Å m ′ = k s Å m ′. Il faut remarquer que cette
attaque ne remet pas en cause la confidentialité du clair, mais plutôt son
intégrité. Il n’est pas exigé qu’un algorithme de chiffrement garantisse
l’intégrité. Cependant, la propriété de malléabilité du chiffré permet de
montrer que le chiffrement n’est pas sûr dans le cas d’attaques à chiffrés
choisis.
• L’algorithme RC4, conçu par les laboratoires RSA, est un algorithme très
rapide et très simple à implémenter. Il est utilisé dans de nombreuses
normes comme SSL, IPsec (voir l’article [IP 5 605]) ou la norme WEP (voir
l’article [TE 7 377]) pour les réseaux sans fil. Quelques faiblesses ont été
découvertes mais qui ne remettent pas en cause la sécurité de
l’algorithme. Cependant, dans certaines implémentations de la norme
WEP, la mise en œuvre du RC4 présente des faiblesses (voir l’article
[TE 7 377]).

• Dans une communication GSM (voir l’article [TE 7 364]), la voix est
numérisée, compressée, puis transmise sous forme de blocs de 114 bits
appelés trames. Environ 217 trames sont échangées chaque seconde
entre le mobile et la station hertzienne du réseau. La communication est
bidirectionnelle et le générateur doit produire 228 bits de clé de flot pour
chaque couple de trames. Ce générateur est appelé A5/1 en Europe et
A5/2 en Asie. Il est fondé sur trois registres à décalage de longueur totale
64 bits. Après une phase d’initialisation de ces registres, qui utilise la clé
secrète de 64 bits, la génération de la suite pseudo-aléatoire commence
en suivant la règle suivante : dans chacun des registres, on privilégie une
position particulière (les bits de contrôle d’horloge) et on prélève à
chaque top d’horloge le bit qui s’y trouve ; une valeur majoritaire (0 ou 1)
se dégage des trois registres ainsi prélevés et seuls les registres qui ont
« voté » pour le bit gagnant sont décalés. Après 328 tops d’horloge, une
suite de 328 bits a été générée.
• Les 100 premiers sont trop prévisibles et ne sont pas utilisés. Il reste donc
114 bits pour les communications mobile vers base et 114 bits pour les
communications base vers mobile. Le niveau de sécurité atteint est
raisonnable même si la sécurité n’est pas en 264 comme le laisse supposer
la taille des clés. Une attaque est possible si l’on dispose d’une puissance
de calcul assez importante ainsi que de suffisamment de couples de
trames en clair et chiffrées. La phase de précalcul est assez longue, mais
on peut ensuite retrouver n’importe quelle clé avec un simple ordinateur
en quelques minutes à partir de 2 s de communication ou en 1 s avec
2 min de communication. Cette faiblesse d’A5/1 a entraîné une
modification de l’algorithme de chiffrement, appelé F8, pour la troisième
génération de mobiles appelée UMTS (voir l’article [TE 7 368]). Il s’agit
aujourd’hui d’un block cipher.

• Un générateur aléatoire peut être construit en utilisant un algorithme de

chiffrement par bloc. En effet, étant donné qu’un block cipher doit se
comporter comme une permutation aléatoire, alors les sorties peuvent
être vues comme des bits aléatoires et imprédictibles. Les modes
opératoires CFB (Cipher FeedBack) ou OFB (Output FeedBack) sont des
moyens pour générer un flux aléatoire à partir d’un algorithme de
chiffrement par bloc.
• Ils sont décrits au paragraphe 2.3.1. Même si les modes CFB et OFB sont
plus lents que les stream ciphers, on les préfère car leur sécurité est
mieux connue : elle dépend uniquement de l’algorithme de chiffrement
par bloc (bloc de 64 bits et clé de 128 bits) pour lequel on ne dispose
aujourd’hui d’aucune attaque significative.

• 2.2.3 Fonction de hachage

• La fonction de hachage est la dernière primitive dont nous ayons besoin.

Les fonctions de hachage sont des fonctions très utiles en informatique.
Elles permettent de représenter les éléments d’entrée sur peu de bits.

L’espace d’entrée des fonctions de hachage est composé de toutes les

chaînes de bits de taille quelconque, noté {0, 1}*. L’espace de sortie est
l’ensemble des chaînes de bits de taille n, {0, 1}n. Toute entrée sera
transformée en une chaîne de n bits. En cryptographie, les fonctions de
hachage sont utilisées pour construire des schémas de signature et des
codes d’authentification de messages. Elles sont basées sur les mêmes
principes de confusion et de diffusion que les algorithmes de chiffrement
par bloc.
 Les propriétés attendues des fonctions de hachage sont les suivantes.

• Fonction à sens unique : étant donné y, il est difficile de trouver en un

temps raisonnable une entrée x telle que H (x ) = y.

• Fonction résistante aux collisions : il est difficile de trouver en un temps

raisonnable x et x ′ (x ¹ x ′ ) tels que H (x ) = H (x ′ ). Il est clair que de tels
éléments existent car l’espace d’entrée est beaucoup plus grand que
l’espace de sortie.

• Fonction résistante à un deuxième antécédent : étant donné x et y tels

que y = H (x ), il est difficile de trouver en un temps raisonnable x ′ ¹ x tel
que H (x ′ ) = y.

• Les exemples de fonctions de hachage sont MD5 (Message Digest numéro

5) et SHA-1 (deuxième version de la norme américaine Secure Hash
Algorithm FIPS PUB 180-1). Dobbertin a trouvé des faiblesses sur la
fonction de compression de MD5 et aujourd’hui seule la fonction SHA-1
est recommandée. La taille de sortie de la fonction MD5 est de 128 bits
alors que celle de SHA-1 est de 160 bits.
• Afin d’analyser la sécurité des fonctions de hachage, nous avons besoin du
résultat suivant. Selon le paradoxe des anniversaires, si l’on tire t valeurs
avec remise dans un ensemble de N valeurs, alors la probabilité d’obtenir
au moins une collision est proportionnelle à t 2/N. Ainsi, si , on obtient au
moins une collision avec probabilité strictement supérieure à 1/2.

• Nota :
• le nom de ce résultat vient du fait que si N = 365, alors en prenant 23
valeurs au hasard, on obtiendra au moins une collision avec une
probabilité supérieure à 1/2. En particulier, si dans une salle, il y a 23
personnes, il y a plus d’une chance sur deux qu’il existe au moins deux
personnes qui ont leur anniversaire le même jour de l’année. En revanche,
étant donné une valeur parmi N, la probabilité qu’il y ait une collision avec
cette valeur en effectuant t tirages aléatoires avec remise est t /N.

• Ce paradoxe permet d’estimer la probabilité de collision d’une fonction de

hachage.
• En effet, si on modélise la fonction de hachage comme une fonction
aléatoire, on peut voir ses sorties comme des valeurs aléatoires dans
{0, 1}n. Ainsi en calculant hachés, on a plus d’une chance sur deux
d’obtenir une collision. Par conséquent, les sorties d’une fonction de
hachage doivent être suffisamment grandes. La puissance de calcul pour
obtenir une collision sur SHA-1 est donc de 2 80 opérations et 264 pour
MD5.

• 2.3 Mécanismes cryptographiques

• Nous décrivons ici les mécanismes cryptographiques utilisant les

primitives définies précédemment pour garantir la confidentialité,
l’intégrité, l’authentification de documents et l’identification de
personnes.
• 2.3.1 Modes opératoires de chiffrement

• On a vu que l’on savait chiffrer de longs messages avec un algorithme de

chiffrement par flot mais comment fait-on avec un algorithme de
chiffrement par bloc ?

• Les modes opératoires découpent un message M en blocs Mi de longueur

n. Si la taille du message M en bits n’est pas un multiple de la taille du
bloc, il faut ajouter des bits de bourrage pour compléter le dernier bloc.
Cette opération s’appelle le padding. Une méthode simple consiste à
toujours « padder » le message avec un bit à 1 suivi d’autant de bits à zéro
que nécessaire pour obtenir un multiple de n.

• Mode ECB
• Le mode opératoire le plus simple, appelé ECB (Electronic Code Book,
figure 4) consiste à chiffrer individuellement chaque bloc par un appel au
block cipher E. Formellement, on peut écrire que pour tout bloc de clair Mi
, le chiffré est Ci = E k (Mi ).
• Mais ce mode permet-il de construire un schéma de chiffrement sûr ?
Supposons que l’on chiffre chaque caractère individuellement par un
appel au block cipher. Même si ce mode opératoire utilise un bon
algorithme de chiffrement par bloc, il n’est pas sûr en pratique. En effet,
chaque caractère est chiffré par un bloc particulier de 64 bits mais
toujours de la même façon. Une analyse statistique de la fréquence des
blocs permet de retrouver le chiffré des lettres les plus fréquentes comme
dans la cryptanalyse du chiffrement de César De la même manière, si on
chiffre un texte codé en Unicode, format permettant de représenter
différents alphabets, on ne peut mettre que 4 octets dans un bloc de 64
bits car chaque octet de clair est codé par deux octets dont l’un est
constant (pour la langue anglaise par exemple). Ainsi, en analysant la
fréquence des quadrigrammes, on est capable de casser ce mode de
chiffrement, aussi forte la primitive de chiffrement soit-elle. Un autre
défaut de l’ECB est qu’il est déterministe : une attaque sur ce mode
permet de trouver tout clair à partir d’une phase de précalcul si la taille
des clés est suffisamment petite pour effectuer une attaque exhaustive.
• Par exemple, si l’adversaire sait que le clair est un fichier Word, alors
certains bits de l’en-tête sont connus et sont fixes d’un fichier à l’autre.
• Ainsi, on peut supposer que l’adversaire connaît par exemple le premier
bloc du clair M1 et le bloc de chiffré C 1 . Il peut alors essayer toutes les
clés en testant si pour toutes les clés possibles k i . Sur un algorithme
comme le DES, cette attaque demande 256 opérations de chiffrement, soit
environ une journée. On peut aussi précalculer et stocker les valeurs , en
triant ces valeurs suivant la première coordonnée. Ensuite, lorsque
l’attaquant voit passer le chiffré C avec comme premier bloc C 1 , le temps
d’une recherche par dichotomie dans ce tableau ne demande que 56
comparaisons dans le pire des cas. Enfin, l’adversaire lit directement la clé
k i utilisée et peut déchiffrer les autres blocs de C. Cette attaque basée
essentiellement sur une phase de précalcul s’appelle une attaque par
dictionnaire. Il est également possible de faire un compromis entre le
temps mis pour casser un chiffré donné et la mémoire utilisée lors de la
phase de précalcul. Remarquons aussi que cette attaque est possible avec
l’AES par exemple, mais sa complexité est beaucoup plus importante (il
faut essayer les 2128 clés possibles) et elle ne peut pas être mise en œuvre
actuellement en un temps raisonnable.
Figure 4 - Mode de chiffrement Electronic Code Book (ECB)
Figure 5 - Mode de chiffrement Cipher Block Chaining (CBC)
• Notons enfin que ce mode a l’avantage d’être parallélisable, ce qui signifie
qu’une implémentation matérielle ou logicielle (sous forme de bitslice )
pourrait par exemple commencer le chiffrement du deuxième bloc avant
que le premier bloc n’ait été complètement traité. Cet avantage est
essentiel pour atteindre un très haut débit de chiffrement. De plus, si une
erreur de transmission survient sur le réseau, comme le changement d’un
bit du chiffré ou l’effacement d’un bloc de chiffré, le déchiffrement peut
toujours avoir lieu et seulement un bloc de clair sera erroné.

• Mode CBC

• Le chiffrement en mode CBC (Cipher Block Chaining) est un mode

opératoire probabiliste qui ne souffre pas des problèmes du mode ECB si
l’adversaire a accès à un clair à un instant donné. C’est le mode le plus
utilisé. Le fonctionnement du mode CBC est le suivant et est décrit sur la
figure 5 : tirer aléatoirement un vecteur d’initialisation C 0 Î {0, 1}n, et pour
chaque bloc Mi , Ci = E k (Mi Å C i – 1).
• Pour déchiffrer le bloc Ci pour , on calcule Mi = C i – 1 Å Dk (Ci ). Ce mode n’est
cependant pas parallélisable car pour commencer le chiffrement du deuxième
bloc, il faut connaître le premier bloc de chiffré. Mais il est
autosynchronisable, ce qui veut dire qu’en cas d’erreur de transmission, seuls
le bloc de clair concerné et le suivant seront erronés. En effet, d’après la
formule du déchiffrement, pour déchiffer Cj , il suffit que C j – 1 et Cj soient
correctement transmis.

• Autres modes opératoires

• Enfin, les trois derniers modes permettent de générer un flux aléatoire en

utilisant un algorithme de chiffrement par bloc. On peut remarquer que dans
ces trois modes, on peut utiliser une fonction aléatoire au lieu d’une
permutation aléatoire.

– Le mode CFB (Cipher FeedBack), décrit figure 6, génère aléatoirement

un bloc C 0 Î {0,1}n, puis pour chaque bloc Mi , on calcule Ci = E k (C i –
1) Å Mi . Pour obtenir la formule de déchiffrement, il suffit d’inverser dans
la formule précédente Mi et Ci : Mi = E k (C i – 1) Å Ci .
Figure 6 - Mode de chiffrement Cipher FeedBack (CFB)
 Le mode OFB (Output FeedBack) génère aléatoirement un bloc
V 0 = C 0 Î {0, 1}n, puis pour chaque bloc Mi , on calcule Vi = E k (Vi – 1), et
Ci = Vi Å Mi . Pour déchiffrer, à partir du germe initial C 0 , on peut
recalculer la suite d’aléas Vi et déchiffrer tout bloc Ci en utilisant la
formule Mi = Ci Å Vi .

Enfin, le mode compteur (CTR) permet de chiffrer en utilisant un compteur

de blocs entre deux équipements. Le compteur, ctr, est initialisé à 0 et
pour chiffrer le i-ème bloc, on calcule Ci = Mi Å E k (ctr ) et on incrémente
le compteur. Pour déchiffer, le correspondant maintient le compteur
dans le même état que l’émetteur et calcule Mi = Ci Å E k (ctr ). Le
problème du mode CTR est que lorsque plusieurs personnes veulent
communiquer avec la même clé, le compteur ne peut pas être connu de
tous. Une version randomisée de ce mode est alors possible. La valeur
ctr est tirée aléatoirement dans {0, 1}n et la machine de chiffrement
chiffre le premier bloc avec cette valeur, le deuxième avec ctr + 1 et
ainsi de suite.

Sécurité des modes opératoires

On peut montrer que les modes CBC, CFB, CTR et CTR randomisé
garantissent la confidentialité des communications tant que moins de
2 n / 2 blocs sont chiffrés, si la primitive de chiffrement par bloc se comporte
comme une permutation aléatoire.
• Le changement de clé est une opération très sensible aux attaques. Ainsi,
il faut éviter de changer de clé lorsque cela n’est pas nécessaire pour
garantir la sécurité. Si l’on utilise le DES ou le 3DES, il faut changer de clé
tous les gigabits par exemple, alors qu’avec l’AES, en pratique, la clé a une
durée de vie quasi illimitée.

• 2.3.2 Code d’authentification de messages

• Les codes d’authentification de messages (Message Authentication Code :

MAC) permettent de garantir l’intégrité des messages. Un algorithme de
MAC génère une valeur appelée tag, de taille fixe, pour tout message
d’entrée. Toute modification du message, même d’un bit, change
complètement le tag. Cette valeur est transmise avec le message. Ce tag
est calculé en utilisant une clé secrète et seules les personnes qui la
connaissent peuvent calculer et/ou vérifier un tag. Pour construire des
mécanismes de MAC, on utilise des algorithmes de chiffrement par bloc
ou des fonctions de hachage.
• Les propriétés recherchées sont que le calcul d’un MAC doit être
imprédictible, c’est‐à‐dire que la fonction doit se comporter comme une
fonction aléatoire.

• L’objectif d’un adversaire contre un algorithme de génération de MAC est

de contrefaire l’algorithme en calculant un nouveau tag valide τ associé à
un message m étant donné des paires de messages/tags valides (mi , τi ).

• Le schéma de MAC le plus utilisé est le CBC-MAC et est décrit sur la

figure 7. Pour calculer un tag τ sur un message M, on calcule un CBC sans
vecteur d’initialisation sur le message et le dernier bloc représente le tag.
Figure 7 - Schéma d’authentification CBC-MAC
Figure 8 - Schéma d’authentification EMAC
• Il est aisé de vérifier que le dernier bloc d’un chiffrement en mode CBC
dépend de tout le message. Ainsi, toute modification du message
provoquera une modification du tag avec une probabilité écrasante.
Contrairement au chiffrement CBC, le vecteur d’initialisation C 0 est fixé à
0 n afin de garantir l’intégrité du premier bloc. Ce schéma ne garantit que
l’intégrité de messages de taille fixe. Dans certaines applications où la
taille des messages est toujours la même, par exemple dans le cas
d’instructions à authentifier, il est possible d’utiliser un tel schéma. Si la
taille des messages varie, un adversaire qui ne connaît pas la clé de MAC
est capable de créer un tag valide pour de nouveaux messages.

• Si l’on veut pouvoir assurer avec ce schéma l’intégrité pour des messages
de taille variable, il faut ajouter un surchiffrement du tag avec une autre
clé : τ = E k ′ (CBC – MACk (M )) où CBC – MACk (M ) désigne le MAC
précédent. Ce schéma s’appelle EMAC pour Encrypted MAC et est décrit
sur la figure 8. La sécurité de ce schéma est garantie uniquement si moins
de 2 n / 2 blocs de messages sont authentifiés. Si E est l’algorithme DES,
alors la taille des blocs est de n = 64 bits et il est possible de calculer
2 32 MAC assez rapidement. Il est préférable d’utiliser un algorithme
comme l’AES utilisant des blocs de 128 bits. En effet, l’utilisation du DES
avec la majorité des MAC basée sur un CBC conduit à des attaques
nécessitant quelques jours de calcul si l’on estime que la recherche d’une
clé DES peut se faire en un jour.
• Enfin, il est possible de construire un schéma de MAC en utilisant des
fonctions de hachage. Le schéma HMAC est très rapide et beaucoup
utilisé dans les protocoles de sécurité proposés par l’IETF. Il existe une
instanciation de ce schéma avec la fonction de hachage MD5 (HMAC-
MD5) et une autre avec SHA-1 (HMAC-SHA-1). Pour authentifier un
message M avec la clé K et la fonction de hachage H, on calcule
τ = H (K Å opad ││ H (K Å ipad ││ M )) où ││ dénote la concaténation des
chaînes de bits. Les constantes opad et ipad sont en fait les octets 0x36 et
0x5C, dupliqués k / 8 fois si k est la taille de la clé K en bits. Dans les
protocoles SSL (ou TLS) et IPsec, les fonctions HMAC sont souvent utilisées
comme générateurs d’aléas afin de produire des clés de session de
chiffrement et de MAC à partir d’une clé maître. Cette fonction est alors
utilisée pour ses propriétés d’imprédictibilité.

• 2.3.3 Authentification de personne

• L’authentification de personne, aussi appelée identification, permet à une

entité de prouver qu’elle est bien celle qu’elle prétend être. La technique
du login /mot de passe n’est pas sûre car un adversaire qui écoute le canal
peut rejouer cette authentification et se faire passer pour l’utilisateur.
• Un protocole d’authentification entre un utilisateur et un vérifieur est un
ensemble de questions posées par le vérifieur auxquelles l’utilisateur doit
être capable de répondre. L’adversaire peut être simplement passif, c’est‐
à‐dire qu’il écoute des communications entre un utilisateur et un vérifieur
honnêtes et tente ensuite de se faire passer pour l’utilisateur à partir de
ces seules informations. Mais il peut être aussi actif : dans ce cas, il peut
prendre la place du vérifieur et poser des questions à l’utilisateur pour
essayer d’extraire de l’information sur son secret. Idéalement, une preuve
d’authentification doit permettre à un utilisateur de prouver qu’il connaît
un secret associé à une clé publique tout en assurant que le vérifieur
n’obtient aucun bit d’information sur le secret et ne peut pas
ultérieurement se faire passer pour l’utilisateur. Une preuve d’identité,
pour être sûre, ne doit pas être transférable. La cryptographie à clé
publique permet de construire de tels schémas en utilisant des preuves
zero knowledge. La cryptographie symétrique propose des méthodes pour
l’identification mais les garanties de sécurité ne sont pas aussi fortes que
celles apportées par les techniques zero knowledge. Dans la suite, on
décrit le système IFF et le système OTP.
• Le protocole IFF (Identification Friends and Foes) permet de construire un
schéma d’identification sûr en pratique mais qui n’est pas zero knowledge. tant
que t > 0. Le problème de ce mécanisme est qu’un client qui veut s’authentifier
avec n serveurs doit gérer n mots de passe ou bien les serL’utilisateur et le
vérifieur partagent une clé secrète k pour l’algorithme DES par exemple. Le
vérifieur envoie un challenge aléatoire r pris dans l’ensemble {0, 1}64 et
l’utilisateur répond par y = E k (r ). En réception, le vérifieur calcule avec sa clé y
′ = E k (r ) et contrôle que si . Il est évident que si le vérifieur ne choisit pas les
challenges de manière aléatoire dans {0, 1}64 et s’il redemande une ancienne
valeur du challenge déjà envoyé, alors une personne qui aura espionné le canal
pourra s’identifier.
• Cependant, d’après le paradoxe des anniversaires, si les valeurs de r sont
prises au hasard dans {0, 1}64, la probabilité qu’un ancien r soit redemandé est
proportionnelle à t 2/ 264 où t est le nombre de valeurs déjà demandées. Ainsi, il
est recommandé de changer de clé k toutes les 222 interactions pour que la
probabilité d’obtenir sur un ancien r soit d’environ une sur un million.
• Il existe un autre mode d’identification appelé One-Time Password (OTP) basé
sur des fonctions de hachage supposées se comporter comme des fonctions à
sens unique 3.
• L’idée consiste à utiliser un mot de passe pwd et à le hacher t fois. La
dernière valeur h t = H t (pwd) est conservée par le serveur. Lorsque le client
veut s’authentifier, il calcule à l’aide de son mot de passe,
h t –1 = H t –1 (pwd) et le serveur vérifie si . Si l’égalité est vérifiée, le serveur
stocke
• h t –1 à la place de h t et ainsi de suite veurs doivent se synchroniser pour
qu’ils connaissent tous la valeur h t – t ′. Ce mécanisme a été proposé par
Lamport et est parfois appelé chaîne de Lamport . Il est utilisé dans certains
produits d’authentification sur Internet.

• 2.3.4 Génération d’aléas

En cryptographie, on a souvent besoin d’aléas pour générer des clés ou
pour randomiser les schémas de signature ou de chiffrement. En général,
les générateurs aléatoires mixent diverses sources d’aléas (horloge, copie
d’écran, numéro de processus, mouvements de la souris, intervalle entre
plusieurs frappes...) dans une première phase. Ensuite, un traitement
algorithmique permet de lisser la distribution de sortie du générateur en
utilisant par exemple des fonctions de hachage ou des algorithmes de
chiffrement par bloc.
• Il est difficile de générer des bits aléatoires. Un générateur de bits pseudo-
aléatoires (pseudorandom bit generator : PRBG) est un algorithme
déterministe qui, étant donné une suite binaire de longueur k, produit
une suite binaire de longueur qui apparaît aléatoire. L’entrée du PRBG est
appelée le germe, alors que la sortie du PRBG est appelée une suite de
bits pseudo-aléatoires.

• La sortie d’un PRBG n’est pas aléatoire ; en fait, le nombre des suites de
sortie possibles est au plus une petite fraction, , de toutes les suites
binaires possibles de longueur . L’objectif est de prendre une suite binaire
vraiment aléatoire et de l’étendre en une suite de longueur supérieure de
telle sorte qu’un attaquant ne puisse pas efficacement distinguer les
suites de sortie du PRBG des suites vraiment aléatoires de longueur . Par
exemple, les générateurs congruentiels linéaires produisent une suite
pseudo- aléatoire de nombres x 1, x 2, x 3 ... selon la formule de récurrence
xn = ax n – 1 + b mod m pour , où a, b et m sont des paramètres qui
caractérisent le générateur et x 0 est le germe. De tels générateurs sont
fréquemment utilisés pour simuler des nombres aléatoires, mais ne
peuvent pas être utilisés en cryptographie car ils sont prédictibles.
• En effet, étant donné une suite de sortie partielle, le reste de la suite peut
être reconstruit même si les paramètres a, b et m sont inconnus.
L’exigence de sécurité minimale pour un PRBG est que la longueur k du
germe soit suffisante pour qu’une recherche exhaustive sur les 2 k
éléments ne soit pas possible en un temps raisonnable. Les deux
propriétés des sorties du PRBG sont que les bits de sortie doivent être
statistiquement indistinguables de suites vraiment aléatoires et qu’ils ne
soient pas prédictibles par un attaquant dont les ressources en temps et
en mémoire sont limitées. Il existe des PRBG basés sur des principes de
cryptographie à clé publique comme le générateur de Blum-Blum et Shub
mais qui sont moins performants. Nous ne décrirons ici que des
générateurs basés sur des primitives symétriques.

• La norme ANSI X9.17 décrit un générateur pseudo-aléatoire efficace

utilisant une clé k Î {0, 1}k et un état s 0 Î {0, 1}n. Pour générer un bloc de n
bits, le générateur utilise l’état s i – 1 et le temps à l’instant i, t i , et calcule
la sortie y i = E k (s i – 1 Å E k (t i )) et le nouvel état s i = E k (y i Å E k (t i )). La
valeur y i est retournée par le générateur et la valeur s i est le nouvel état
du générateur.
• Sous l’hypothèse que l’algorithme par bloc se comporte comme une
permutation aléatoire, ce générateur est prouvé sûr tant que moins de
2 n / 2 blocs y i ont été générés, même si l’adversaire choisit l’état initial ou
le temps t i .

• La norme PUB FIPS 186 décrit un générateur pseudo-aléatoire basé sur

des fonctions de hachage utilisant une clé k Î {0, 1}k et un état s 0 Î {0, 1}n.
Pour générer un bloc de n bits, le générateur utilise l’état s i – 1 et le temps
à l’instant i, t i , et calcule
• Δ s i – 1 = (s i – 1 – s i ) mod 2 n, y i = ((Δ s i – 1 + t i ) mod 2 n ) et
• s i = (s i – 1 + y i + 1) mod 2 n. La fonction représente une fonction de
hachage avec la clé s 0 , c’est‐à‐dire = Hk (s 0 + x mod 2 n ) et Hk (·)
représente la fonction de hachage où k est le vecteur d’initialisation de la
fonction de hachage. La valeur y i est retournée par le générateur et la
valeur s i est le nouvel état du générateur. Ce générateur est prouvé sûr
sous l’hypothèse que la fonction de hachage se comporte comme une
fonction aléatoire même si l’adversaire peut connaître la clé tant que
moins de 2 n / 2 blocs y i ont été générés.
3. Cryptographie asymétrique
• 3.1 Rappels de mathématiques et d’algorithmique
3.1.1 Calcul modulaire
3.1.2 Exponentiation modulaire
3.2 Système de chiffrement asymétrique
3.2.1 Types d’attaque sur les schémas de chiffrement
3.2.2 Cryptosystème RSA
3.2.2.1 Principes
3.2.2.2 Sécurité
3.3 Mécanisme d’échange de clé et chiffrement hybride
3.3.1 Échange de clé Diffie-Hellman
3.3.2 Chiffrement hybride
3.4 Signature
3.4.1 Généralités sur les schémas de signature
3.4.2 Types d’attaques
3.4.3 Schémas de signature RSA, DSA et ECDSA
3.4.4 Applications des signatures à l’authentification d’entité
• La cryptographie à clé publique (asymétrique) a été inventée par Diffie et
Hellman dans leur article précurseur. Ils cherchaient à résoudre le
problème de l’échange de clé. Comment échanger une clé secrète sans
avoir besoin de se rencontrer ?

• Ils ont défini la notion de fonction à sens unique, centrale aujourd’hui

pour la cryptographie. Les fonctions à sens unique, one-way functions,
sont des fonctions pour lesquelles il existe un algorithme efficace
permettant de calculer l’image d’un point, mais il n’existe pas
d’algorithme efficace pour inverser la fonction.

• Exemple :
• il est facile, connaissant deux nombres premiers p et q, de les multiplier
pour obtenir N = pq, mais on ne sait pas comment factoriser efficacement
N, c’est‐à‐dire retrouver p et q en un temps raisonnable.

• Les fonctions à sens unique à trappe sont des fonctions à sens unique
telles que la connaissance d’une trappe, la clé secrète, rend possible
l’inversion efficace de la fonction.
• Elles permettent de concevoir des systèmes de chiffrement asymétrique
et des schémas de signature électronique. En 1977, Rivest, Shamir et
Adleman proposent le système RSA. On peut remarquer qu’il a fallu plus
de vingt ans aux cryptographes pour comprendre comment chiffrer ou
signer de façon sûre avec RSA.

• Dans un système à clé publique, chaque entité a une clé secrète sk et une
clé publique pk associée. Pour envoyer un message à A, B doit obtenir la
clé publique de A et chiffrer le message avec cette clé. En réception, seul A
qui connaît sa clé secrète sk peut déchiffrer.

• 3.1 Rappels de mathématiques et d’algorithmique

• On rappelle ici quelques résultats sur les structures mathématiques et
comment les manipuler de manière efficace. Un entier p ou q désignera
un grand nombre premier, N désignera le produit de deux grands
nombres premiers p et q, et n la taille de N en bits.
3.1.1 Calcul modulaire

• Les systèmes à clé publique utilisent souvent le corps = {0, 1, ..., p – 1}, où p est
un nombre premier, muni des opérations d’addition et de multiplication pour
lesquelles on ne garde que le reste de la division euclidienne du résultat par p.
On dit alors que l’on calcule modulo p. Dans un corps, tous les éléments non
nuls sont inversibles. Dans , ces éléments forment un groupe cyclique, appelé
groupe multiplicatif, de cardinalité
p – 1 et noté . Si q est un nombre premier divisant l’ordre p – 1 de , alors il
existe un sous-groupe cyclique d’ordre q, noté Gq , ce qui signifie qu’il existe un
élément générateur g Î Gq tel que pour tout entier y Î Gq , il existe tel que y = g
x
mod p. Dans le cas où N est un nombre composé, l’ensemble des éléments
= {0, 1, ..., N – 1} muni des opérations d’addition et de multiplication modulo N
forme un anneau. Dans ce cas, les seuls éléments inversibles sont ceux qui ne
sont pas divisibles par p ou q. Soit a un entier, on dit que b est l’inverse de a
modulo N s’il vérifie la relation ab = 1 mod N, c’est‐à‐dire s’il existe un entier tel
que ab = 1 + kN, ou s’il existe k tel que ab – kN = 1. Par conséquent, d’après la
réciproque du théorème de Bézout, seuls les entiers a premiers avec N, c’est‐à‐
dire qui ne sont pas multiples de p ou de q, sont en fait inversibles modulo N. Il
y a donc ϕ (N ) = pq – p – q + 1 = (p – 1) (q – 1) éléments inversibles. En effet, les
multiples de p entre 0 et N – 1 s’écrivent sous la forme kp pour k variant de 0 à
q – 1. Il y a donc q multiples de p. De même, il y a p multiples de q. Mais 0 a été
compté deux fois, d’où la formule.
• Dans ces structures, le petit théorème de Fermat et le théorème d’Euler
vont nous être utiles pour concevoir les systèmes cryptographiques à clé
publique. Le petit théorème de Fermat dit que dans le groupe , pour tout
élément x Î , x p –1 = 1 mod p. Dans le cas du groupe Gq , on a la relation
x q = 1 mod p pour tout x Î Gq . Le théorème d’Euler permet de généraliser
ces théorèmes dans le cas d’un anneau et affirme que si N = pq, pour tout
entier m Î , m (p – 1) (q – 1) = 1 mod N. La leçon de ces théorèmes est que l’on
calcule modulo q dans les exposants si les éléments sont pris dans Gq et
modulo (p – 1) (q – 1) dans les exposants si les calculs s’effectuent modulo
N.

• 3.1.2 Exponentiation modulaire

• D’un point de vue algorithmique, il est possible de calculer efficacement

une exponentielle modulaire ab mod N pour tout entier N. Avant de
commencer l’exponentiation, b peut être réduit modulo ϕ (N ) et a
modulo N. Ainsi, si N fait n bits, alors b mod ϕ (N ) fait au plus n bits.
L’algorithme naïf consisterait à calculer b – 1 multiplications modulaires
en utilisant une récursion basique. La complexité de ce calcul est
multiplications, donc exponentielle en la taille de l’entrée b. En effet, la
valeur b mod ϕ (N ) est représentée sur n bits, , et donc . Ainsi, si
n = 1024, il faudra au moins 21023 multiplications, ce qui est irréaliste. Il
faut donc utiliser une autre technique.
• L’algorithme d’exponentiation binaire a une complexité linéaire en la taille
n de l’exposant b : seulement 2 × n multiplications modulaires sont
nécessaires. L’idée de cet algorithme est de décomposer l’exposant sous
forme binaire :

Par conséquent :
Enfin, les termes pour lesquels b i = 0 donnent un facteur 1 dans ce
produit et les autres un facteur . Les n facteurs peuvent être calculés avec
n carrés modulaires. En effet, on obtient à partir de en élevant au carré : .
Ensuite, il suffit de faire au plus n – 1 multiplications pour calculer le
produit. On obtient donc l’algorithme d’exponentiation binaire (a, b, N )
décrit ci‐après, où la variable T contient à la i-ème itération de la boucle et
S contient le produit.

Entrée :
Sortie : a b mod N
• S ¬ 1, T ¬ a
• Pour i de 0 à n – 1 :
• si — b i = 1 alors S ¬ T × S mod N
• si — i ¹ n – 1, T ¬ T 2 mod N
• Retourner S
3.2 Système de chiffrement asymétrique
• Il existe plusieurs schémas de chiffrement à clé publique mais le plus connu et
le plus utilisé est le système RSA. Dans la suite, nous ne nous intéresserons
qu’à ce cryptosystème.

• 3.2.1 Types d’attaque sur les schémas de chiffrement

• L’objectif le plus ambitieux d’un adversaire qui souhaite attaquer un système

de chiffrement à clé publique est de retrouver la clé secrète du destinataire. Si
cet objectif est atteint, le schéma est dit complètement cassé car l’adversaire
peut déchiffrer tous les chiffrés. Un autre objectif est de systématiquement
retrouver le clair associé à un chiffré. Si cet objectif est atteint, le schéma de
chiffrement est cassé. Enfin, un objectif plus faible consiste à distinguer le
chiffrement du message clair 0 de celui du message clair 1. Dans certaines
applications où l’espace des messages se réduit à un bit, par exemple un ordre
de vente ou d’achat d’actions sur Internet, le schéma ne doit pas laisser fuir le
moindre bit d’information sur le clair. Cette sécurité est appelée la sécurité
sémantique comme en cryptographie symétrique.

• L’adversaire peut monter différents types d’attaques pour atteindre son

objectif.
• Dans un système à clé publique, un adversaire passif peut toujours
monter une attaque à clairs choisis (chosen plaintext attack : CPA) car il a
accès à la clé de chiffrement et peut donc obtenir le chiffré de n’importe
quel message clair. Une attaque plus forte est une attaque à chiffrés
choisis (chosen ciphertext attack : CCA) où l’adversaire choisit des chiffrés
de son choix et obtient par certains moyens le clair correspondant. On
distingue habituellement deux types d’attaques à chiffrés choisis :

• attaque à chiffrés choisis non adaptative. Dans cette attaque, l’adversaire

obtient les clairs pour des chiffrés de son choix mais ces chiffrés doivent
être choisis avant de recevoir le chiffré cible c qu’il souhaite déchiffrer ;

• attaque à chiffrés choisis adaptative. Dans cette attaque, l’adversaire peut

avoir accès à la machine de déchiffrement (mais pas à la clé secrète
directement), même après avoir vu le chiffré cible c qu’il souhaite
déchiffrer. L’adversaire peut demander le déchiffrement pour des chiffrés
reliés au chiffré cible mais n’a pas le droit de demander le déchiffrement
de c directement.
• Les attaques à chiffrés choisis adaptatives peuvent apparaître à première
vue comme des attaques très puissantes mais peu réalistes. Cependant,
dans certains schémas, le message clair contient de la redondance
(intégrité) et le clair n’est retourné par la machine de déchiffrement que si
la marque d’intégrité est vérifiée. Dans le cas d’un protocole comme SSL,
un message d’erreur peut alors être renvoyé. L’adversaire qui envoie un
chiffré peut alors apprendre à la vue de la réponse de la machine si le clair
correspondant vérifie ou non la redondance (voir attaque sur SSL). Ainsi, il
peut apprendre certains bits du message clair. On montre alors que si le
schéma est résistant face aux attaques à chiffrés choisis, alors le schéma
est résistant face à ces attaques appelées reaction attack.

• Enfin, la combinaison d’un objectif et d’un type d’attaque permet de

définir la notion de sécurité. On dit par exemple qu’un schéma est
sémantiquement sûr contre des attaques à chiffrés choisis si aucun
attaquant mettant en œuvre une attaque à chiffrés choisis ne peut
distinguer le chiffré de 0 du chiffré de 1.
3.2.2 Cryptosystème RSA
• Nous présentons ici le système RSA et les principes mathématiques
nécessaires à ce schéma.

• Problème de la factorisation
• Étant donné un entier N de grande taille, produit de deux grands nombres
premiers p et q, retrouver p et q.

• Ce problème est difficile pour une fraction non négligeable des entiers N si
N est suffisamment grand. Le record de factorisation a été atteint pour un
module de 530 bits avec l’algorithme GNFS (General Number Field Sieve)
en 2003. On conjecture qu’avec cet algorithme, le nombre d’opérations
pour factoriser un module de 1 024 bits est de l’ordre de 280 opérations.

• Le problème général de la factorisation pour un entier aléatoire n’est pas

un problème difficile car avec une probabilité de 1/2, le nombre aléatoire
sera pair et 2 sera un des facteurs. Cependant, dans le cas particulier où N
est le produit de deux grands nombres premiers, le problème de la
factorisation paraît difficile. On peut remarquer qu’il existe un très grand
nombre de nombres premiers p et q entre 2 n / 2 – 1 et 2 n / 2.
• En effet, d’après le théorème sur la densité des nombres premiers, un
entier pris au hasard dans l’intervalle [B, C ] est premier avec une
probabilité de :
soit environ 2 /n. Ainsi, il y a environ 2 n / 2/n nombres premiers entre
2 n / 2–1 et 2 n / 2 et si n = 1 024, on a environ 2 512 / 2 9 = 2503 nombres
premiers entre 2511 et 2 512. Par conséquent, une recherche exhaustive
n’est pas possible en temps raisonnable si n est trop grand : la complexité
de cette recherche demanderait un temps proportionnel à . Le meilleur
algorithme connu aujourd’hui pour factoriser a une complexité en temps
de calcul sous-exponentielle en la taille de N. Il nécessite environ
opérations pour retrouver p et q.

• 3.2.2.1 Principes
• Le problème RSA est relié au problème de la factorisation. Avant de le
définir, nous avons besoin de préciser quelques notations. Les valeurs e et
d sont des nombres premiers avec ϕ (N ) et vérifient la relation
e × d = 1 mod ϕ (N ) = 1 + k ϕ (N ). On pose pk = (e, N ) une clé publique
RSA et sk = d la clé secrète associée.
On peut générer de manière efficace des nombres premiers assez grands.
L’algorithme de Miller-Rabin permet de générer un nombre premier de
n / 2 bits en multiplications.
• Le résultat est un entier non premier avec une probabilité négligeable. La
probabilité d’erreur est un paramètre de cet algorithme, on peut donc la
définir aussi petite que l’on veut. Ensuite, il suffit de calculer
ϕ (N ) = (p – 1) · (q – 1) et de calculer d = e –1 mod ϕ (N ), ce que l’on peut
faire de manière efficace avec l’algorithme d’Euclide étendu.
• Pour chiffrer un message M, on applique un encodage inversible, aussi
appelé fonction de padding f (·), m = f (M ), et on calcule
c = me mod N. Pour déchiffer c, on calcule m = c d mod N et on inverse la
fonction de padding pour retrouver le message M. Ce calcul permet en
effet de retrouver le message m car :

• c d = med = m1 + kϕ (N ) = m × (m ϕ (N ) )k = m × (1)k = m mod N

• Problème RSA
• Étant donné un entier N de grande taille, produit de deux grands nombres
premiers p et q, e un entier premier avec ϕ (N ), et c Î aléatoirement
choisi, calculer m tel que c = me mod N.

• Ce problème paraît difficile pour une fraction non négligeable des entiers
c et si N fait 1 024 bits. On peut alors définir l’hypothèse RSA.
• Hypothèse RSA

• Étant donné un entier N de grande taille, produit de deux grands nombres

premiers p et q, et e un entier premier avec ϕ (N ), il est difficile en un
temps raisonnable de calculer m tel que c = me mod N pour une fraction
non négligeable des entiers c Î .

• La sécurité du système RSA repose sur le problème de la factorisation car

on ne connaît pas d’autre méthode permettant de retrouver m à partir de
c = me mod N que de factoriser N pour retrouver ϕ (N ) et inverser e
modulo ϕ (N ). Cependant, il se pourrait qu’il existe une technique
permettant de retrouver m sans factoriser N. Il est difficile de calculer
ϕ (N ), pour quiconque ne connaît pas la factorisation de N. En effet, il est
aussi difficile de factoriser que de calculer ϕ (N ) = (p – 1) (q – 1). Il est
évident que si l’on sait factoriser, on peut calculer efficacement ϕ (N ).
Réciproquement, si on connaît la valeur ϕ (N ) = N + 1 – (p + q ), alors on
connaît le produit p · q et la somme de p et q, car p + q = N + 1 – ϕ (N ). Il
ne reste plus qu’à résoudre une équation du second degré
X 2 – [N + 1 – ϕ (N )] × X + N pour obtenir les racines p et q.

• Enfin, si e est petit, le problème RSA peut être résolu pour l’ensemble
négligeable des entiers inférieurs à N 1/e.
• En effet, si x < N 1/e, x e mod N = x e dans les entiers : la réduction
modulaire n’a pas été utilisée car x e < N. Il suffit donc d’extraire une
racine e-ième dans , ce qui est un problème facile. La difficulté du
problème RSA est donc de trouver x tel qu’il existe λ Î [0, N e – 1[ vérifiant x
e
= y + λN. Si λ est connu, alors on peut calculer y + λN et il suffit d’extraire
une racine e-ième dans .

• 3.2.2.2 Sécurité
• Depuis son invention en 1977, plusieurs personnes ont tenté de casser ce
système. Dans l’article Twenty years of attacks on the RSA cryptosystem,
Dan Boneh dresse un tableau de toutes les attaques sur ce système. Pour
chiffrer avec ce système, on recommande d’utiliser un formatage
probabiliste comme celui décrit dans le standard PKCS #1. Le padding
assure que le message à chiffrer soit suffisamment grand, supérieur à
N 1/e, pour que la réduction modulaire soit utile. De même, le padding est
randomisé pour assurer la sécurité sémantique du schéma. Pour une
analyse des différentes méthodes de padding pour le système RSA, le
lecteur lira l’article de David Pointcheval How to Encrypt Properly with
RSA.
 3.3 Mécanisme d’échange de clé et chiffrement
hybride
• En pratique, on ne chiffre pas des données avec un algorithme de
chiffrement asymétrique. On utilise la cryptographie asymétrique pour
échanger une clé de session et la cryptographie symétrique pour chiffrer
les données avec cette clé de session.

• En effet, l’avantage de la cryptographie à clé publique est de garantir la

confidentialité sans échange de clé préalable. En revanche, les systèmes à
clé publique sont plus lents en pratique que les systèmes symétriques. Les
systèmes asymétriques nécessitent une arithmétique sur les grands
nombres qui n’est pas directement câblée sur les processeurs aujourd’hui.
• Ainsi, les systèmes sont environ 100 fois plus lents. Le chiffrement
hybride utilise les avantages des deux types de cryptographie pour
chiffrer. On présente dans un premier temps le principe du mécanisme
d’échange de clé de Diffie et Hellman et dans un deuxième temps le
principe du chiffrement hybride. Ces deux systèmes sont très utilisés en
pratique.
3.3.1 Échange de clé Diffie-Hellman
• Contrairement au cryptosystème RSA qui permet de chiffrer, le
mécanisme d’échange de clé de Diffie et Hellman permet d’échanger une
clé symétrique, mais ne permet pas de chiffrer. Dans leur article
précurseur , Diffie et Hellman ont décrit un mécanisme permettant à
deux entités de communiquer sans se rencontrer. Pour présenter ce
mécanisme, nous avons besoin de définir le problème du logarithme
discret, très utilisé en cryptographie.

• Problème du logarithme discret

• Étant donné un nombre premier p de grande taille, q un diviseur premier

de p – 1 de grande taille, g un générateur du sous-groupe Gq , et un
élément y aléatoirement choisi dans Gq , trouver x mod q tel que
• y = g x mod p.

• Ce problème est difficile si p fait 1 024 bits et q 160 bits. Le meilleur

algorithme connu demande dans ce cas 280 opérations.

• La sécurité du mécanisme Diffie-Hellman repose sur un problème relié au

problème du logarithme discret mais a priori plus facile.
• Soit p un nombre premier, q un grand nombre premier diviseur de p – 1 et
g un générateur du groupe Gq dans . Dans le protocole de Diffie et Hellman,
pour échanger une clé de session k, une entité A tire a Î aléatoirement,
calcule g a mod p et transmet cette valeur à B. De même, l’entité B tire b Î
aléatoirement, calcule g b mod p et la transmet à A. La clé de session est
dérivée de g ab mod p via une fonction de hachage k = H (g ab mod p ). Les
deux entités A et B peuvent calculer g ab mod p : à partir de g a mod p et b, B
calcule (g a )b mod p, et réciproquement pour A.
• Le but d’un adversaire est de calculer g ab mod p à partir des échanges
interceptés g a mod p et g b mod p. Formellement, on a le problème
suivant :
•
• Problème Diffie-Hellman

• Étant donné g a mod p et g b mod p, calculer g ab mod p.

• Il est clair que si l’on sait résoudre le problème du logarithme discret, alors
on peut résoudre le problème Diffie-Hellman. En effet, si l’attaquant sait
calculer a à partir de g a mod p, alors il peut calculer (g b )a mod p comme B
pour résoudre le problème Diffie-Hellman. Cependant, comme dans le cas
du problème RSA, on ne sait pas si la réciproque est vraie. Est-ce qu’un
attaquant sachant résoudre le problème Diffie-Hellman sait résoudre le
problème du logarithme discret ?
3.3.2 Chiffrement hybride
• Pour chiffrer un message M, l’émetteur génère une clé de session k pour
un algorithme symétrique, l’AES par exemple, et chiffre cette clé avec la
clé publique RSA du destinataire, pk : c 0 = E pk (k ). Puis il chiffre son
message avec la clé de session de l’algorithme à clé sécrète c 1 = E k (M ).
L’émetteur transmet c 0 et c 1 au destinataire. En réception, ce dernier
déchiffre c 0 en utilisant sa clé de déchiffrement RSA et retrouve la clé de
session k. Il peut ensuite déchiffrer c 1 en utilisant l’algorithme AES avec la
clé k et obtient le message M.

• 3.4 Signature
• Les schémas de signature permettent de garantir l’intégrité d’un fichier et
l’authentification de l’émetteur. Les signatures électroniques doivent
garantir les mêmes propriétés que les signatures manuscrites. Elles
doivent pouvoir être opposées aux signataires. La propriété de non-
répudiation assure au destinataire d’un message signé que son signataire
ne pourra pas déclarer qu’il ne l’a pas signé.

• Exemple :
• un juge peut vérifier qu’une facture a été signée et que le client doit donc
• Les signatures électroniques sont entrées dans la législation française
depuis le 20 mars 2000. Aujourd’hui, elles nous permettent par exemple
de déclarer nos revenus sur Internet. Contrairement aux codes
d’authentification de messages qui garantissent aussi intégrité et
authentification, les signatures électroniques peuvent être vérifiées par
toute personne qui connaît la clé publique du signataire. De plus, la
propriété de non-répudiation ne peut pas être assurée par les systèmes
symétriques car comme le destinataire partage la clé symétrique avec le
signataire, ce dernier peut prétendre qu’un message signé l’a été par le
destinataire. Ainsi, seule la cryptographie à clé publique permet
d’atteindre cette propriété. Enfin, il est à remarquer qu’une clé de
signature ne doit être connue que par son signataire pour assurer la non-
répudiation. Cette exigence impose alors de prendre certaines mesures de
protection lors de la génération de la clé secrète. Par exemple, une clé de
signature ne devrait pas être générée par une autorité car l’autorité
pourrait potentiellement connaître la clé. Dans le cas d’une clé de
déchiffrement, la clé secrète peut être connue par d’autres personnes.
•
• Exemple :
• dans le cas de la confidentialité de dossiers médicaux, la clé de
déchiffrement peut être connue de l’hôpital et du médecin traitant. En
effet, si ce dernier est en vacances lorsqu’un patient arrive à l’hôpital, il
peut être utile de conserver une copie de la clé de déchiffrement.
3.4.1 Généralités sur les schémas de signature
• Une signature électronique doit dépendre du signataire et du document à
signer. Les signatures manuscrites ne dépendent que du signataire mais
ne peuvent pas être détachées du document. Dans le monde
électronique, il est aisé de copier un fichier et de modifier son contenu.
Les signatures électroniques ne peuvent donc pas dépendre uniquement
du signataire.

• Un schéma de signature est composé d’un algorithme de génération de

clé , d’un algorithme de génération de signature et d’un algorithme de
vérification de signature . L’algorithme de génération de clé retourne une
clé publique pk et une clé de signature sk. Ensuite, l’algorithme prend
comme entrée un message m et une clé sk et génère une signature s pour
le message m. L’algorithme de vérification de signature prend comme
entrée le message m, la signature s et la clé pk et retourne un bit 0 si la
signature n’est pas correcte pour le message m et 1 si la signature est
valide. Un algorithme de signature doit être capable de signer des
messages de taille quelconque.

• Pour des raisons de performance et de sécurité des schémas, on ne signe

pas en général tout le message m mais seulement un haché h. Ce modèle
de schémas de signature est appelé hash- and-sign. Le problème est que
deux messages qui ont la même image par H auront la même signature.
• Il est donc essentiel que les fonctions de hachage employées vérifient les
propriétés de résistance aux collisions et de résistance à une seconde pré-
image. La propriété de résistance aux collisions est essentielle car elle
permet par exemple d’empêcher un signataire de répudier une signature
en créant des fichiers ayant la même image par H. Si un signataire est
capable de trouver des collisions pour deux messages x et x ′, alors il
pourrait renier une signature sur le message x en prétendant avoir signé
le message x ′. De même, la propriété de résistance à un deuxième
antécédent empêche un attaquant de trouver un deuxième message
ayant la même signature qu’un message signé donné.

• 3.4.2 Types d’attaques

• Le but d’un adversaire est de contrefaire des signatures, c’est‐à‐dire
produire des signatures qui seront acceptées comme celles d’un autre
signataire. Nous décrivons ici ce que signifie casser un schéma de
signature :

• cassage total : un adversaire est capable soit de calculer la clé secrète du

signataire, soit de trouver un algorithme de signature fonctionnellement
équivalent à l’algorithme de génération de signature ;
• contrefaçon sélective : un adversaire est capable de créer une signature
valide pour un message particulier ou pour une classe de messages choisis
a priori ;

• contrefaçon existentielle : un adversaire est capable de contrefaire une

signature pour au moins un message. L’adversaire a peu ou pas de
contrôle sur le message pour lequel la signature a été obtenue.

• Il y a deux attaques de base sur les schémas de signature :

• attaque à clé seulement : dans certaines attaques, l’adversaire connaît
seulement la clé publique de vérification du signataire ;

• attaques à messages : ici, l’adversaire est capable d’obtenir des signatures

correspondant soit à des messages connus, soit à des messages choisis :

– attaque à messages connus : un adversaire obtient des signatures

pour un ensemble de messages, connus par l’adversaire mais qu’il n’a
pas choisis,

– attaque à messages choisis : un adversaire choisit un ensemble de

messages pour lesquels il obtient une signature.
 – Cette attaque est non adaptative dans le sens où les messages sont
tous choisis avant que l’adversaire n’obtienne leur signature,
– attaque adaptative à messages choisis : l’adversaire peut utiliser le
signataire comme un oracle ; il demande des signatures pour des
messages qui dépendent de la clé publique et des signatures
précédemment obtenues. Cette attaque est l’analogue des attaques à
chiffrés choisis dans le cas des schémas de chiffrement à clé publique.

• Bien que les attaques adaptatives à messages choisis semblent être

impossibles à monter en pratique, un schéma de signature bien conçu
doit néanmoins résister à ces attaques.

• 3.4.3 Schémas de signature RSA, DSA et ECDSA

• Schéma de signature RSA
• Le schéma de signature le plus connu est le schéma RSA. De même que
dans le cas du chiffrement RSA, il faut utiliser un padding pour garantir la
sécurité du schéma. On peut trouver dans le document une description du
padding PKCS # 1 version 2.1 à utiliser : le message M est encodé en
utilisant la fonction de padding f (·), puis le résultat m = f (M ) est élevé à
la puissance d modulo N.
• Seul le possesseur de la clé secrète peut effectuer ce calcul :
s = m d mod N. Toute personne qui connaît la clé publique pk = (e, N ) peut
vérifier la validité d’une signature (M, s ) si l’égalité s e mod est vérifiée où
m est calculé à partir du message M et en utilisant la fonction de padding
f (·). En effet, si (M, s ) est un couple valide, alors s = m d mod N et donc s
e
= m ed = m mod N. Il a été prouvé qu’un adversaire capable de créer une
signature valide pour un nouveau message peut être utilisé pour
contredire l’hypothèse RSA.

• La fonction de padding PKCS # 1 v2.1 est très importante car si le message

n’est ni haché ni paddé et si l’algorithme de signature calcule simplement
s = m d mod N où m = M (f ) avec f ici la fonction identité, alors il est facile
de contrefaire existentiellement une signature : il suffit de choisir
aléatoirement et de poser M = m = s e mod N. Il est facile de voir qu’un tel
message m a bien pour signature s. Cependant, l’adversaire n’a aucun
moyen d’obtenir un message M ayant un sens. Le choix du padding est
très important pour la sécurité de la signature RSA. Par conséquent,
quand on parle de signature RSA, il vaut mieux parler du schéma
RSA-PKCS # 1 v2.1 pour être précis. Le padding PKCS # 1 a été révisé en
1999 pour adopter des schémas prouvés sûrs sous certaines hypothèses.
 En effet, les paddings proposés dans PKCS # 1 v1.5 contraient les attaques
élémentaires mais leur conception était heuristique : on ne connaissait
pas d’attaque contre le schéma RSA utilisé avec ce padding mais il se peut
qu’il existe une attaque contre ce schéma de signature sans qu’il existe
pour autant un attaquant contre le problème RSA. Encore aujourd’hui,
beaucoup d’implémentations utilisent ces paddings.

• Schémas de signature DSA et ECDSA

• Il existe un autre schéma de signature appelé DSA (Digital Signature

Algorithm) normalisé par le NIST. Le signataire utilise une clé secrète et
une clé publique y = g x mod p. Pour signer un message m, le signataire
tire aléatoirement un random k dans et calcule r = (g k mod p ) mod q, puis
s = k –1 {h (m ) + xr } mod q. La signature du message m est le couple (r, s ).
Pour vérifier une signature (r, s ) sur le message m, le signataire vérifie si
0 < r < q et 0 < s < q et calcule w = s –1 mod q et h (m ). Puis, il calcule u
1 = w · h (m ) mod q et u 2 = rw mod q et accepte la signature si l’équation
suivante est vérifiée . La sécurité de ce schéma repose sur le problème du
logarithme discret.

• Ce schéma peut aussi être défini dans le groupe des points d’une courbe
elliptique et le schéma prend le nom de ECDSA (Elliptic Curve Digital
Signature Algorithm).
• Dans une telle structure, le problème du logarithme discret est
apparemment encore plus difficile, ce qui permet de prendre des clés plus
petites pour un niveau de sécurité équivalent. On peut remarquer que le
schéma de signature DSA n’a pas été prouvé aussi difficile à casser que
résoudre le problème du logarithme discret. Ainsi, il se pourrait qu’un
adversaire soit capable de créer une signature valide pour un nouveau
message sans être pour autant capable de résoudre le problème du
logarithme discret.

• Ce schéma de signature est probabiliste et utilise un générateur pseudo-

aléatoire. La description de ce générateur est donnée dans la norme et
nous l’avons décrit au paragraphe. Il est important d’avoir un bon
générateur d’aléa pour utiliser de manière correcte DSA ou ECDSA. En
effet, la connaissance des 3 bits de poids fort ou de poids faible pour
environ une centaine de signatures permet de casser ce schéma.
• Comparaison
• On peut comparer les différents schémas en fonction de la taille de la clé
ou du temps de génération ou de vérification ou du problème sur lequel
repose la sécurité du schéma. Le schéma ECDSA utilise des clés plus
courtes et est le plus rapide en vérification. Le schéma RSA est rapide
pour la génération de signature. Le schéma DSA est plus rapide que RSA
en vérification et a des signatures plus courtes que RSA. L’avantage du
schéma DSA par rapport au schéma ECDSA est que le problème du
logarithme discret sur courbe elliptique est un problème plus récent et
donc moins étudié que celui sur . De plus, le schéma DSA n’a pas de
preuve de sécurité, contrairement à RSA et ECDSA.

• 3.4.4 Applications des signatures à

l’authentification d’entité

• Les signatures numériques permettent d’assurer l’authentification des

entités. Le protocole d’authentification décrit dans la norme ITU X.509
emploie des signatures RSA. Pour s’authentifier, l’utilisateur reçoit un
challenge r et renvoie une signature sur le message r.
• N’importe quel vérifieur peut s’assurer que la signature est correcte.
• L’utilisateur fait la preuve qu’il connaît la clé de signature d. De même,
dans le protocole SSL, le serveur s’authentifie en faisant la preuve qu’il est
capable de déchiffrer correctement. L’authentification du client est, elle,
optionnelle et se fait conformément au protocole X.509.

• Enfin, il est important de noter ici qu’il vaut mieux utiliser une clé pour
chaque usage cryptographique différent, par exemple, une clé de
signature et une autre clé pour authentifier, même si c’est la même
opération de signature qui est utilisée. En effet, si le vérifieur, au lieu
d’envoyer un challenge aléatoire, envoie un message, il obtient en
réponse une signature pour un message de son choix.
 4. Applications de la cryptographie : protocoles de
communication
• 4.1 Avantages et inconvénients des méthodes
symétriques et asymétriques
4.1.1 Avantages de la cryptographie symétrique
4.1.2 Inconvénients de la cryptographie symétrique
4.1.3 Avantages de la cryptographie asymétrique
4.1.4 Inconvénients de la cryptographie
asymétrique
4.2 SSL/TLS
4.3 IPsec
4.4 S / MIME
• La cryptographie est utilisée aujourd’hui dans de nombreuses
applications : dans les téléphones portables, sur Internet ou pour la
télévision à péage. Dans le cas des téléphones mobiles, la cryptographie
est utilisée pour assurer la confidentialité des communications. En effet, la
loi sur les télécommunications oblige les opérateurs à garantir la sécurité
des communications des utilisateurs. En particulier dans le cas des
téléphones mobiles, les communications entre le téléphone et la station
hertzienne sont chiffrées. On utilise uniquement la cryptographie à clé
secrète et l’algorithme de chiffrement est un algorithme par flot appelé
A5. Sur Internet, la cryptographie permet de garantir la confidentialité de
certaines communications comme la transmission du code d’une carte
bleue (protocole SSL) ou d’assurer la confidentialité, l’intégrité et
l’authentification de l’émetteur dans les messageries électroniques
(protocole S/MIME) (voir l’article [H 5 330]). Enfin, la cryptographie est
aussi utilisée dans le cas des télévisions à péage pour que seuls les
usagers autorisés puissent avoir accès aux programmes. Ainsi, les
programmes sont chiffrés et seuls les abonnés connaissent la clé de
déchiffrement. De plus, la cryptographie permet aujourd’hui par exemple
de détecter les décodeurs pirates mais, pour des raisons économiques,
ces systèmes sont peu employés.
 4.1 Avantages et inconvénients des méthodes
symétriques et asymétriques
• Dans cette partie, nous résumons quelques avantages et inconvénients
des cryptosystèmes symétriques et asymétriques.
Les points importants en pratique sont :
• la cryptographie à clé publique permet de concevoir des schémas de
signature efficaces qui garantissent la propriété de non-répudiation. Elle
permet aussi de faciliter la distribution de clés de session pour des
systèmes symétriques ;

• la cryptographie symétrique est très efficace pour chiffrer ou pour

garantir l’intégrité et l’authentification des données.
 4.1.1 Avantages de la cryptographie symétrique

• Les algorithmes symétriques sont conçus pour chiffrer très rapidement

d’importants volumes de données. Certaines implémentations sous forme
matérielle atteignent des débits de quelques gigabits par seconde alors
que les implémentations logicielles atteignent des débits de centaines de
mégabits par seconde.
Les clés des systèmes symétriques sont relativement courtes.
Les algorithmes de chiffrement symétriques sont des primitives utilisées
pour construire différents mécanismes cryptographiques comme les
générateurs pseudo-aléatoires de nombres, les fonctions de hachage ou
encore les codes d’authentification de messages.
Les systèmes symétriques ont une histoire assez longue, même si la
plupart des connaissances dans ce domaine ont été acquises depuis
l’invention récente des ordinateurs et en particulier depuis la conception
de la norme du Data Encryption Standard au début des années 1970.
 4.1.2 Inconvénients de la cryptographie symétrique
• Dans une communication entre deux parties, la clé doit rester secrète des
deux côtés.

• Dans un grand réseau, il peut y avoir beaucoup de paires de clés à gérer

sur chaque équipement. S’il y a n entités dans le réseau, chaque entité
requiert n – 1 clés afin de pouvoir discuter avec toutes les autres entités.
En conséquence, le système de gestion de clés doit gérer n (n – 1) / 2 clés
dans le système.

• Selon les mécanismes cryptographiques choisis, il se peut que le système

nécessite de changer les clés assez souvent.

• On ne peut pas concevoir de schéma de signature électronique basé sur

de la cryptographie symétrique si l’on veut garantir la propriété de non-
répudiation.
 4.1.3 Avantages de la cryptographie asymétrique
• Seule la clé secrète a besoin d’être conservée de manière secrète.
L’authentification de la clé publique doit cependant être garantie.

• Selon l’usage, une paire de clés (publique/secrète) peut être utilisée plus
longtemps qu’une clé symétrique.

• La cryptographie à clé publique permet de réaliser des schémas de signature

électronique assurant un service de non-répudiation.

• Dans un grand réseau, le nombre de clés est beaucoup plus petit que dans un
système symétrique car seulement 2n clés sont nécessaires s’il y a n
utilisateurs dans le réseau.

• 4.1.4 Inconvénients de la cryptographie asymétrique

• Les performances des systèmes asymétriques sont beaucoup moins bonnes
que celles des systèmes symétriques car ces systèmes nécessitent de pouvoir
calculer sur des grands nombres.
• La taille des clés est généralement plus grande pour ces systèmes que pour
les systèmes à clé secrète.

• Aucun cryptosystème à clé publique n’a été prouvé inconditionnellement

sûr. (On peut dire la même chose pour les algorithmes symétriques de
chiffrement par bloc ou par flot.) Les cryptosystèmes à clé publique sont
cependant prouvés sûrs si certaines hypothèses de théorie algorithmique
des nombres existent.

• La cryptographie à clé publique nécessite la mise en place d’une

infrastructure de gestion de clé afin d’éviter les attaques par le milieu.

• 4.2 SSL/TLS
• Le protocole SSL (Secure Socket Layer) a été inventé par la société
Netscape, puis standardisé au niveau de l’IETF sous le nom TLS (Transport
Layer Security).

• Tout protocole de communications sécurisées s’effectue en deux phases. La

première phase permet aux entités d’échanger une clé maître, de négocier
les algorithmes de chiffrement symétrique et de code d’authentification de
messages et d’authentifier les entités.
• La deuxième phase permet d’échanger les données de manière
confidentielle et intègre en utilisant les clés et algorithmes symétriques
échangés dans la première phase.

• La première phase est la plus importante. On peut utiliser l’algorithme

d’échange de clé Diffie-Hellman mais le plus souvent, il s’agit d’un
chiffrement hybride avec l’algorithme RSA. Dans ce cas, c’est le client qui
choisit une clé maître et la chiffre avec la clé publique du serveur. Le
serveur s’authentifie vis‐à‐vis du client en prouvant sa connaissance de sa
clé secrète. Pour ce faire, il déchiffre la clé maître en utilisant sa clé
secrète RSA. Puis il génère deux clés MAC, l’une du serveur vers le client
et l’autre du client vers le serveur et deux clés de chiffrement dans les
deux sens. Le client fait de même pour générer les clés en utilisant la clé
maître avec un générateur pseudo-aléatoire basé sur la fonction HMAC.
Le serveur génère le MAC des messages envoyés précédemment avec la
clé serveur vers client et le client avec la clé client vers serveur.
• Les vérifications de ces MAC permettent au client et au serveur de
s’assurer qu’ils partagent bien les mêmes clés symétriques. De plus, le
client authentifie le serveur car pour calculer la clé de MAC, il a dû
correctement déchiffrer la clé maître et seul le serveur, possédant
légitimement la clé secrète RSA, a pu effectuer ce déchiffrement. Le client
peut optionnellement s’identifier au serveur en utilisant le protocole
X.509.

• 4.3 IPsec

• Le fonctionnement du protocole IPsec est similaire à celui du protocole

SSL. Il est standardisé par l’IETF. Le protocole IPsec a été conçu pour
assurer la sécurité du protocole IP (Internet Protocol). Il faut ajouter ce
protocole de sécurité au protocole IP. La sécurité du protocole est prise
en compte de manière native dans la version 6 du protocole IP, ce qui
n’est pas le cas de la version 4 utilisée actuellement.
• Il existe deux modes : l’un permettant de chiffrer de bout en bout et
l’autre permettant la création de tunnels sécurisés, c’est‐à‐dire que les
données sont chiffrées uniquement entre deux routeurs par exemple et
non à l’intérieur du réseau de l’entreprise supposé sécurisé. Dans le cas
d’un tunnel, tout le paquet IP est chiffré alors que seule la partie
« données » est chiffrée dans le cas d’un chiffrement de bout en bout car
on ne peut pas chiffrer l’en-tête qui contient les adresses IP. Dans le cas
d’un tunnel, les protocoles IPsec garantissent la confidentialité de
l’adresse IP. Cela peut aussi être garanti en utilisant des mécanismes de
translation d’adresse sur le routeur de sortie de l’entreprise.

• Durant la première phase, le protocole Internet Key Exchange (IKE)

permet d’échanger la clé maître, d’authentifier les entités et de gérer les
associations de sécurité (Security Association : SA). Les associations de
sécurité contiennent les algorithmes de chiffrement et de MAC, et les clés
de chiffrement et d’authentification des données.
• Ces SA sont stockées dans des bases de données de sécurité (SADB) en
utilisant comme clé de la base de données l’adresse IP de la machine
émettrice et le numéro de SA. Ainsi, quand une station du réseau reçoit
un paquet IP sécurisé, elle utilise le bon algorithme de chiffrement et de
MAC et la bonne clé de chiffrement et de MAC.

• Durant la deuxième phase, le protocole Encapsulated Security Payload

(ESP) permet de garantir la confidentialité et l’intégrité des données, et de
l’en-tête dans le cas d’un tunnel, alors que le protocole Authentication
Header (AH) permet de garantir l’intégrité des paquets IP, y compris
certaines données de l’en-tête des paquets IP. En effet, les champs qui
varient, comme le nombre de routeurs traversés, ne peuvent pas être
utilisés pour calculer le MAC car les routeurs intermédiaires n’ont pas la
clé de MAC.

• Pour plus de détails, le lecteur est invité à consulter l’article Protocole

IPsec [IP 5 605].
4.4 S / MIME
• Le protocole S/MIME permet d’envoyer des messages chiffrés et signés
dans les e-mails. Le standard Cryptographic Message Syntax (CMS) décrit
le format des en-têtes des messages signés et des messages chiffrés. L’en-
tête de ces fichiers doit contenir la signature et des informations
supplémentaires comme les certificats des clés publiques permettant de
vérifier la signature de ces fichiers.

• Pour plus de détails, le lecteur est invité à consulter l’article Sécurité des
e-mails : PGP et S/MIME [H 5 330].
5. Conclusion

• La cryptographie a défini les notions de sécurité et prouvé la sécurité de

cryptosystèmes de chiffrement, de codes d’authentification de messages
et de signatures numériques. De plus, des protocoles de plus haut niveau,
comme des systèmes de communications sécurisées ou de votes
électroniques, ont été conçus.

• Aujourd’hui, la cryptographie tente de concevoir des systèmes plus sûrs et

plus efficaces comme par exemple des systèmes garantissant intégrité et
confidentialité en passant une seule fois sur le message clair au lieu de
passer une première fois pour le chiffrer et de repasser pour garantir
l’intégrité du chiffré. Enfin, tous les modèles d’adversaires n’ont pas
encore été définis. Aujourd’hui, les attaques du monde réel sont réalisées
soit sur des protocoles qui n’ont pas été prouvés sûrs, soit parce que le
modèle d’adversaire ne reproduit pas le monde réel. Ainsi, dans certaines
cartes à puce, l’adversaire peut accéder à des informations sur la clé
secrète à partir d’observations sur le temps de calcul ou la puissance
consommée. Enfin, certaines attaques sont dues à une mauvaise
implémentation des mécanismes