Procédés de chiffrement

par Philippe GUILLOT

Agrégé de Mathématiques
Chef du Laboratoire de Cryptologie de l’unité SSI (Sécurité des Systèmes d’information) de
Thomson-CSF Communications

1. Systèmes de chiffrement....................................................................... E 6 450 - 2

1.1 Définition ...................................................................................................... — 2
1.2 Classification des attaques ......................................................................... — 2
1.3 Sécurité conditionnelle et sécurité inconditionnelle ................................ — 2
1.4 Différents modèles ...................................................................................... — 2
1.5 Chiffrement analogique ou chiffrement numérique................................. — 3
2. Générateurs de clé (ou de pseudo-aléa) ............................................ — 3
2.1 Critères de conception ................................................................................ — 4
2.2 Registres à décalage rebouclés en période maximale (RRPM) ............... — 4
2.3 Complexité linéaire...................................................................................... — 4
2.4 Schéma type ................................................................................................ — 4
2.5 Critères d’évaluation ................................................................................... — 5
2.6 Modes d’utilisation ...................................................................................... — 6
3. Calcul par bloc.......................................................................................... — 6
3.1 Critères de conception ................................................................................ — 7
3.2 Le DES .......................................................................................................... — 7
3.3 Qualification statistique .............................................................................. — 8
3.4 Modes d’utilisation standards .................................................................... — 8
4. Systèmes à clé publique ........................................................................ — 9
4.1 Définition ...................................................................................................... — 9
4.2 Chiffrement El Gamal .................................................................................. — 9
4.3 Le RSA .......................................................................................................... — 10
4.4 Autres utilisations........................................................................................ — 10
4.5 Sécurité des systèmes à clé publique........................................................ — 10
5. Conclusion ................................................................................................. — 10
Références bibliographiques ......................................................................... — 11

raditionnellement, en raison de la sensibilité des informations manipulées,

T les milieux militaires et gouvernementaux se sont toujours intéressés aux
procédés de chiffrement. Avec l’essor des réseaux de télécommunications et la
banalisation des données enregistrées, bien d’autres organisations institution-
nelles, commerciales et privées (banques, assurances, etc.) sont maintenant
concernées par les problèmes de sécurité.
En réalité, ce qui détermine le problème de la sécurité dans les systèmes
d’information modernes est en fait :
— un très important volume d’informations traitées et transmises par des enti-
tés complexes, automatisées et standardisées ;
— une grande diversité des types d’information (phonie, télégraphie, messa-
ges, données informatiques, images, fac-similés, etc.) et des supports de trans-
mission (liaisons filaires, radio, satellites, fibres optiques, etc.) ;
— l’extraordinaire extension géographique d’un réseau de télécommuni-
cations qui rend son contrôle très difficile, voire quasi impossible.

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
© Techniques de l’Ingénieur, traité Électronique E 6 450 − 1
PROCÉDÉS DE CHIFFREMENT _____________________________________________________________________________________________________________

Tous ces éléments concourent à accroître la vulnérabilité du système et l’inté-

rêt d’une attaque visant à lire ou à altérer par modification, destruction, répéti-
tion, etc., l’information résidente ou véhiculée dans le système.
Les procédés de chiffrement, objet de cet article, constituent les mécanismes
de protection contre l’écoute des signaux transportés. Ils interviennent de plus
en plus comme éléments dans bien d’autres mécanismes pour assurer divers
services de sécurité (intégrité de données, authentification, signature, etc.) dans
des applications où le problème de la sécurité dépasse le simple cadre de la
confidentialité de l’information : transactions financières, TV à péage, antidé-
marrage automobile, etc.
Nota : cet article fait de larges emprunts à l’édition précédente rédigée par Gilles Coléou.

1. Systèmes de chiffrement 1.3 Sécurité conditionnelle et sécurité

inconditionnelle

1.1 Définition
Trois éléments sont déterminants pour l’attaque d’un système
cryptographique :
Un système de chiffrement peut être vu comme une famille de
— la quantité d’information dont dispose le décrypteur ;
transformations inversibles ( C K ) K ∈ K dépendant d’un paramètre K
— le temps et les moyens alloués, en particulier en termes écono-
appelé clé de chiffrement. Ce paramètre doit être gardé secret dans miques, pour aboutir au décryptement ; ces deux derniers paramè-
les systèmes conventionnels alors qu’il peut être révélé dans les tres sont à comparer en pratique à la durée de vie de l’information
systèmes à clé publique. et aux gains escomptés.
L’émetteur chiffre son message clair M et obtient un crypto- Un système sera dit inconditionnellement sûr, si, quels que soient
gramme Γ = CK (M ) qu’il transmet sur le canal. Ce cryptogramme les moyens mis en œuvre, la quantité d’information connue est
est inintelligible hormis sur le récepteur habilité qui seul possède la insuffisante pour conduire au décryptement. Le décrypteur, quelle
clé de déchiffrement secrète K ’ correspondante. Il effectue alors la que soit la quantité de cryptogramme interceptée, n’a pas plus
transformation inverse DK ’(Γ ) = M pour retrouver le clair (figure 1). d’information sur le clair qu’il n’en avait a priori (statistiques du
clair).
Si les opérations de cryptanalyse se révèlent trop complexes pour
1.2 Classification des attaques aboutir en un temps inférieur à la durée de vie de l’information, le
système est dit conditionnellement sûr.

Pour tout système de chiffrement, se pose immédiatement le pro-

blème de sa résistance vis-à-vis d’une attaque d’un éventuel décryp-
teur. Il est habituel d’évaluer un système dans les conditions les plus 1.4 Différents modèles
défavorables pour le concepteur. Il est généralement admis que le
cryptanalyste connait entièrement le système de chiffrement et les
caractéristiques (en termes statistiques) des messages clairs. Sa
seule inconnue reste la clé secrète de déchiffrement. La relation liant la clé de déchiffrement K ’ à la clé de chiffrement
L’attaque opérationnellement la plus réaliste est celle à clair pro- K permet d’établir une classification.
bable. Le décrypteur ne connaît que les statistiques du clair. Par
exemple, en télégraphie, il possède la fréquence des diverses lettres
de l’alphabet pour la langue utilisée. Mais l’attaque considérée pour 1.4.1 Système de chiffrement « clé une fois »
l’évaluation d’un système est celle à clair connu (ou éventuellement (one time pad )
à clair choisi). Ici l’ennemi connaît une certaine quantité de clairs
correspondant aux cryptogrammes interceptés.
Un système sera réputé comme sûr lorsqu’il résistera à ce dernier Dans ce système de chiffrement défini par Shannon [10], chaque
type d’attaque. symbole de clair est combiné à un symbole d’une suite aléatoire
secrète uniquement connue de l’émetteur et du récepteur. Chaque
symbole de la suite aléatoire n’est utilisé qu’une fois.
C’est le seul système dont on puisse prouver qu’il est incondi-
Émetteur Chiffrement Déchiffrement Récepteur tionnellement sûr.
Canal non protégé L’inconvénient majeur évident du système vient du fait que, préa-
E C D R
M Γ = CK (M ) M = DK ’ (Γ ) lablement à toute communication, les correspondants doivent
Clair Cryptogramme Clair déchiffré s’échanger secrètement une suite aléatoire d’une taille égale au
message transmis. Aussi, ce système n’est-il réservé qu’aux
communications de très haute sécurité et à faible débit lorsque les
Figure 1 – Modélisation d’un système de chiffrement conditions d’exploitation l’exigent.

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
E 6 450 − 2 © Techniques de l’Ingénieur, traité Électronique
____________________________________________________________________________________________________________ PROCÉDÉS DE CHIFFREMENT

1.4.2 Systèmes conventionnels

Clair
Dans ces systèmes, la clé de chiffrement K et la clé de déchiffre-
ment K ’ sont identiques. Cette unique clé secrète n’est connue que
des entités autorisées. Ces systèmes sont aussi parfois qualifiés de K kn
G C
systèmes à clé secrète, ou systèmes à clé symétrique. Clé secrète Suite de clé
La nécessité d’acheminer ce paramètre secret vers les différents
correspondants reste l’inconvénient majeur de ces systèmes. Le
soin et la rigueur apportés à la gestion des clés déterminent dans Cryptogramme
une large mesure leur niveau de sécurité.
C fonction de calcul
Les systèmes conventionnels peuvent être modélisés d’une facon G générateur de clé
générale par la donnée de deux modules (figure 2) :
— un module d’élaboration de pseudo-aléa G qui crée à partir de
la clé une suite pseudo-aléatoire ( k n ) n ∈ N ; Figure 2 – Schéma de principe d’un système de chiffrement
conventionnel
— un circuit de calcul C qui effectue la combinaison entre le clair
et la suite pseudo-aléatoire.
On trouve alors deux grandes familles de systèmes convention-
nels suivant l’endroit où réside la complexité cryptologique :
Annuaire
— dans G : ce sont les générateurs de clé ;
— dans C : ce sont les calculs par bloc. A KA

B KB
Consultation
1.4.3 Systèmes à clé publique de l’annuaire C KC
B? . .
. .
. .
KB
Dans ces systèmes, les clés de chiffrement et de déchiffrement
sont distinctes et ce qui lie ces clés repose sur une relation mathé-
A B
matique complexe. La clé de déchiffrement n’est pas calculable avec Γ = CK (M )
la connaissance de la seule clé de chiffrement, mais nécessite la KA' B KB'
connaissance d’une information secrète supplémentaire. La publi-
cation de la clé de chiffrement ne risque pas d’entrainer la compro-
mission de la clé de déchiffrement. C
Lorsque le correspondant A veut transmettre un message au cor- KC'
respondant B, il consulte l’annuaire pour trouver la clé KB de chiffre-
ment de B. Il transmet le cryptogramme Γ = C KB ( M ) . Seul B qui
Figure 3 – Schéma de principe d’un système de chiffrement
connait la clé de déchiffrement correspondante K ’B peut déchiffrer à clé publique
par M = D K B′ ( Γ ) (figure 3).

On tend de plus en plus à entièrement numériser le signal. Les

transformations cryptologiques s’effectuent alors sur les échan-
1.5 Chiffrement analogique tillons de celui-ci. Ce sont ces techniques qui permettent d’obtenir le
ou chiffrement numérique plus haut niveau de sécurité.

Les techniques de chiffrement analogique consistent à effectuer

des transformations variables et secrètes directement sur le signal 2. Générateurs de clé
analogique. Elles sont surtout utilisées lorsqu’on ne dispose pas
d’une grande largeur de bande pour la transmission, principalement (ou de pseudo-aléa)
lorsque les procédés de numérisation du signal pour rester dans la
bande allouée sont très sophistiqués (vocodeur, compression
d’image, etc.). On peut citer à titre d’exemple deux types de réalisa-
tion. Pour un générateur de clé, la complexité est entièrement conte-
nue dans le circuit d’élaboration de pseudo-aléa. Le circuit de calcul
■ Pour la parole, on trouve des procédés dits à trame glissante est réduit à un simple OU EXCLUSIF. La suite de clé ( k n ) n ∈ N est éla-
dans lesquels le signal de parole est découpé en segments d’envi-
ron 30 ms. Le chiffrement s’obtient en permutant temporellement et borée à partir de la clé secrète K et d’un complément d’initialisation
en inversant spectralement de facon pseudo-aléatoire les différents appelé clé de message (CM ). Cette dernière permet de faire varier la
segments de parole. On utilise généralement un générateur de clé suite de clé pour le chiffrement de chaque message (figure 4).
pour créer le pseudo-aléa nécessaire.
■ Pour les signaux de télévision, il est possible de brouiller l’image Remarque : ces systèmes correspondent à l’évolution prati-
en décalant ou, de manière plus efficace, en permutant pseudo-aléa- que du système parfait de Shannon. Il n’est hélas plus possible
toirement les lignes (procédé Canal +). de démontrer ici la sécurité parfaite du système car la suite pro-
Le développement croissant du numérique dans les télécommu- duite est périodique (le générateur de clé est un automate fini et
nications rend obsolètes ces techniques de chiffrement analogique. déterministe).

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
© Techniques de l’Ingénieur, traité Électronique E 6 450 − 3
PROCÉDÉS DE CHIFFREMENT _____________________________________________________________________________________________________________

2.3 Complexité linéaire

Clair
cn
K kn
2.3.1 Définition
CM G

γn Il apparaît alors une propriété essentielle d’un générateur de clé :

il ne doit pas être linéaire. Mais en réalité, toute suite binaire pério-
Cryptogramme dique peut être engendrée par un registre à décalage rebouclé
linéairement. Il suffit par exemple de considérer un registre circulant
dont la taille est égale à la période de la suite considérée.
Figure 4 – Générateur de clé
La taille du plus petit registre linéaire synthétisant cette suite est
appelée complexité linéaire de la suite. Cette longueur mesure en
quelque sorte l’énergie qu’il faudrait dépenser pour décrypter un
2.1 Critères de conception générateur de clé en le synthétisant par un registre linéaire.

La suite ( k n ) n ∈ N engendrée par un générateur de clé doit : 2.3.2 Comment accroître la complexité linéaire
— avoir une période minimale garantie très grande vis-à-vis de la d’un système
taille des messages à chiffrer ;
— apparaître complètement aléatoire à un observateur extérieur, On se contentera ici de donner quelques exemples [9]. Suppo-
bien qu’en réalité elle soit périodique et reproductible (ce genre de sons que nous disposions de deux RRPM de taille respective r et s
suite est pour cette raison qualifié de pseudo-aléatoire). que l’on choisira premiers entre eux.
Si on cherche à combiner les séquences issues de ces deux regis-
tres, il est possible d’effectuer deux types d’opérations : un OU
2.2 Registres à décalage rebouclés EXCLUSIF et un ET. Toute autre opération booléenne peut être
décrite à partir de ces deux-là. On a les résultats suivants :
en période maximale (RRPM) — opération OU EXCLUSIF (figure 6a) : la période de la suite
résultante est (2r – 1)(2s – 1) ; sa complexité linéaire est r + s ;
— opération ET (figure 6b) : la période reste (2r – 1)(2s – 1), mais
Un registre rebouclé linéairement (Linear FeedBack Shift Regis-
cette fois, la complexité linéaire a considérablement augmenté, elle
ter) en période maximale (RRPM) est un registre à décalage dont le
polynôme caractéristique est primitif. Dès que l’état de départ d’un vaut r × s . La suite ( k n ) n ∈ N n’est plus linéaire. Hélas, elle présente
tel registre n’est pas identiquement nul (état stable du registre), il 1 3
engendre une suite de période 2n – 1, où n est la taille du registre. des biais statistiques Prob [ k n = 1 ] = --- et Prob [ k n = 0 ] = --- .
4 4
Par exemple, le registre de la figure 5 est un RRPM puisque son
L’emploi de l’opérateur ET s’avère donc cryptologiquement très
polynôme de rebouclage P(X ) = X 4 + X + 1 est primitif et il engen-
intéressant (accroissement de la longueur de récursion et non-linéa-
dre la suite de période 15 = 2 4 – 1 soit 100010011010111··· rité du système), mais il faudra corriger le biais statistique résultant.
En outre, les suites issues de RRPM ont d’excellentes propriétés
statistiques : toutes les figures jusqu’à l’ordre n – 1 sont quasi équi-
probables. Il y a par exemple (2n – 1) UNS pour (2n – 1 – 1) ZÉROS. Le
seul biais provient de l’absence de la figure stable 0 ··· 0. 2.4 Schéma type
Ces circuits présentent donc toutes les propriétés nécessaires à la
fabrication de pseudo-aléa : période très grande 2n – 1 et qualités
statistiques. Aussi, ce seront les constituants essentiels entrant dans Au vu des arguments précédents, on peut considérer que le
l’architecture d’un générateur de clé. schéma de la figure 7 donne l’architecture type d’un générateur de
Mais ils ne peuvent à eux seuls constituer un générateur de clé. clé.
En effet, la suite de clé qu’ils engendrent est linéaire et il est facile de Le générateur est constitué de deux parties :
montrer [5] qu’il suffit de connaitre (2n – 1) termes de la suite pour
retrouver l’état de départ et le rebouclage d’un registre de taille n. — un étage linéaire formé de n RRPM de longueurs respectives
ri , deux à deux premières entre elles, permettant de produire une
séquence de très longue période ( 2 r1 Ð 1 ) × … × ( 2 rn Ð 1 ) ;
— un étage non linéaire f dont le rôle est d’accroître la complexité
linéaire et de rendre le système non linéaire. Il faudra prendre soin
de choisir une fonction équidistribuée, c’est-à-dire dont la table de
vérité comporte autant de 0 que de 1. Dans ce cas, chaque valeur de
la suite de clé sera équiprobable.
Un schéma bien connu de ce type est celui de Geffe (figure 8).
0 0 0 1 Sn
Sécurité du schéma de Geffe : le tableau 1 donne les valeurs de la
fonction de filtrage du schéma de Geffe (figure 8). Il s’agit bien
P (X ) = 1 + X + X 4
d’une fonction équidistribuée.
S = 100010011010111 1000100… Cependant, on observe que la valeur de zn est corrélée à celle de
Suite de période 15 rn puisqu’elles sont égales dans 6 cas sur 8 seulement et différentes
dans 2 cas sur 8. Il en est de même pour les valeurs de zn et de tn.
Par contre, les valeurs de zn et de sn sont indépendantes, car elles
Figure 5 – RRPM de longueur 4 sont autant de fois égales et différentes (4 fois sur 8).

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
E 6 450 − 4 © Techniques de l’Ingénieur, traité Électronique
____________________________________________________________________________________________________________ PROCÉDÉS DE CHIFFREMENT

an

r r

kn = an ! bn
rn
bn
1
s s
sn zn
0
Période de kn = (2r – 1) (2s – 1) tn
Complexité linéaire de kn = r + s

a combinaison par OU EXCLUSIF

t

zn = rn sn ! tnsn

an
Figure 8 – Générateur de Geffe
r

kn = an bn

bn Tableau 1 – Table de vérité de la fonction de filtrage

du schéma de Geffe
s
rn sn tn zn
Période de kn = (2r – 1) (2s – 1)
0 0 0 0
Complexité linéaire de kn = rs
0 0 1 1
b combinaison par ET 0 1 0 0
PPCM (r, s) = 1 0 1 1 0
1 0 0 0
Figure 6 – Combinaison des séquences issues de deux RRPM. 1 0 1 1
1 1 0 1
1 1 1 1

L’existence de ces corrélations permet de reconstituer l’état

interne des registres à partir de l’observation d’une quantité suffi-
sante de termes de la séquence de sortie du générateur [9].
Cet exemple souligne l’importance d’un autre critère : celui de
r1 l’absence de corrélation entre entrée et sortie de la fonction de fil-
trage.

2.5 Critères d’évaluation

r2 kn
f
. .
. .
. . Divers critères permettent d’appréhender la qualité cryptologique
d’un générateur de clé.

2.5.1 Taille de la clé

rn
Elle détermine le nombre d’essais systématiques à effectuer pour
retrouver la clé. Elle doit avoir une taille minimale fonction des
Figure 7 – Architecture type d’un générateur de clé moyens de calcul de l’opposant.

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
© Techniques de l’Ingénieur, traité Électronique E 6 450 − 5
PROCÉDÉS DE CHIFFREMENT _____________________________________________________________________________________________________________

2.5.2 Période et non-linéarité du générateur

Chiffrement Déchiffrement
Il s’agit de dépasser un seuil minimal qui est fonction des caracté-
K K
ristiques d’emploi du générateur : débit et durée d’utilisation d’une
clé (cryptopériode), relativement aux moyens à mettre en œuvre par
l’adversaire. Ces paramètres sont très souvent surdimensionnés
vis-à-vis du besoin pour se réserver une marge de sécurité suffi-
sante (complexité linéaire égale à 1020 par exemple).
kn kn

2.5.3 Qualité pseudo-aléatoire de la suite cn γn cn

C’est le paramètre le plus observable. Il s’agit de vérifier que les Clair Cryptogramme Clair
termes de la suite de clé sont équidistribués et indépendants les uns
des autres :
Figure 9 – Mode autosynchronisant
1
Prob [ k n = 0 ] = Prob [ k n = 1 ] = --- (1)
2

1
Prob [ k n = 0 ⁄ k n Ð 1, k n Ð 2, k n Ð 3, … ] = Prob [ k n = 0 ] = --- (2) Clair Cryptogramme Clair
2
Cette vérification peut se faire par des tests statistiques [4]. On
détermine la probabilité d’un événement particulier dans une suite
aléatoire et on regarde si les occurrences de cet événement dans la K K
suite de clé sont conformes à la valeur théorique attendue.
Prenons à titre d’exemple le test le plus simple, celui des fréquen-
ces d’ordre 1 : dans une suite aléatoire, la probabilité d’apparition Chiffrement Déchiffrement
1
d’un zéro est égale à --- . Par conséquent, sous l’hypothèse d’équi-
2 Figure 10 – Mode autoclave sur le clair
probabilité et d’indépendance des termes de la suite de clé, si on en
prélève N, le nombre N 0 de zéros doit suivre une loi binomiale de
1
paramètres N et --- . Les observations sont cumulées et interprétées est erroné en réception, tous les termes de la suite de clé
2
au moyen d’un test d’adéquation à la loi théorique. kj + 1 ... kj + p , qui dépendent de γi , risquent d’être faux.
Ce test peut naturellement être défini pour des ordres supérieurs. Ce mode d’utilisation est très intéressant (pas de synchronisa-
D’autres tests sont aussi applicables [4]. tion), mais ne peut être mis en œuvre que sur des lignes de trans-
mission de très bonne qualité (taux d’erreur inférieur à 10–6).

2.6 Modes d’utilisation 2.6.3 Mode propagateur d’erreur à horizon infini

(ou autoclave sur le clair)
2.6.1 Mode nominal Dans ce mode (figure 10), la suite de clé dépend de la clé et de
toutes les valeurs précédentes du clair :
Dans ce mode d’utilisation, la suite de clé n’est fonction que de la
clé K, de la clé de message CM et du rang n (figure 4) : kn = f (K , cn – 1, cn – 2 ... c0)

kn = f (K, CM, n) Ce mode est intéressant lorsqu’on cherche à garantir l’intégrité

des données transmises. Au message M est concaténée une figure
Ce mode ne propage pas les erreurs de transmission ; l’erreur se fixe connue F et l’ensemble est chiffré dans ce mode. Si un bit de
produisant sur le bit de cryptogramme γi reste localisée sur le bit de cryptogramme γi est modifié, le bit de clair correspondant ci sera
clair déchiffré ci . Ce mode nécessite une synchronisation de départ erroné, ainsi que tous les bits de clé de rang suivant kp , p > i, avec
pour les générateurs en émission et en réception. Tout décalage
1
dans la suite de clé en réception conduit à un déchiffrement complè- une probabilité de --- (propagation d’erreur infinie) :
2
tement incompréhensible.
1
pour p > i Prob [ k p réception = k p émission ] = ---
2
2.6.2 Mode autosynchronisant
(ou autoclave sur le cryptogramme) De ce fait, après déchiffrement, en lieu et place de la figure F, on
retrouvera une séquence F ’ complètement décorrélée de F (la moi-
tié des termes seront faux).
Dans ce mode, la suite de clé est fonction de la clé et des p précé-
dentes valeurs binaires du cryptogramme (figure 9) mémorisés
dans un registre glissant :
kn = f (K,γn – 1, γn – 2, γn – 3, ..., γn – p)
3. Calcul par bloc
Ce mode ne nécessite pas de synchronisation de départ (autosyn-
chronisant). La réception sans erreur de p termes de cryptogramme
permet de générer correctement le terme de suite de clé suivant. Ce Dans ce type de système conventionnel, toute la complexité cryp-
mode propage les erreurs de transmission sur p termes puisque si γi tologique est localisée dans le circuit de calcul. La clé secrète est

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
E 6 450 − 6 © Techniques de l’Ingénieur, traité Électronique
____________________________________________________________________________________________________________ PROCÉDÉS DE CHIFFREMENT

Clair Cryptogramme Entrée

X Y
Permutation initiale
n bit n bit

K T K T –1 L0 R0
K1

n bit n bit f

Y X

Cryptogramme Clair

a chiffrement b déchiffrement L 1 = R0 R1 = L0 ! f (R0 , K1)

K2
Figure 11 – Calcul par bloc en mode dictionnaire
f

directement utilisée pour paramétrer une transformation T. Le clair

est traité par bloc de n bit. Un calcul par bloc réalise donc une per-
mutation de l’ensemble des 2n mots binaires de longueur n sur lui-
même. La clé sert à choisir la permutation à effectuer. Au déchiffre- L2 = R1 R2 = L1 ! f (R1 , K2)
ment, on applique la permutation inverse paramétrée par la même
clé (figure 11).

3.1 Critères de conception

L15 = R14 R15 = L14 ! f (R14 , K15)
K16
Suivant la théorie de Shannon, deux critères sont essentiels : la
diffusion et la confusion. De plus, la taille des blocs ( ≥ 64 bit) doit f
être suffisante pour éviter une attaque exhaustive consistant à créer
pour chaque clé la collection des couples clair/cryptogramme.
R16 = L15 ! f (R15 , K16) L16 = R15
3.1.1 Diffusion
Une modification même minime sur un paramètre d’entrée (clé
ou message clair) doit se répercuter (se diffuser) sur l’ensemble du Permutation initiale inverse
cryptogramme. En d’autres termes, les valeurs de chaque compo-
sante de la fonction de chiffrement doivent dépendre de toutes les
variables. D’un point de vue statistique, la modification d’un seul bit Sortie
de clair ou de clé doit provoquer la modification de chaque bit de
1
cryptogramme avec une probabilité de --- . Figure 12 – Schéma bloc du DES
2
Toute la clé intervient dans le calcul du cryptogramme et le cryp-
tanalyste doit la retrouver globalement et non pas morceau par
morceau.
dans FIPS 46-2 (Federal Information Processing Standards) du NIST
(National Institute of Standards and Technology).
3.1.2 Confusion
Le DES, dans son mode nominal, travaille sur des blocs de clair de
64 bit, la clé est formée de 64 bit dont 56 bit utiles et 8 bit de parité.
Cette propriété signifie que la dépendance exprimée ci-dessus
doit être suffisamment complexe et inextricable pour empêcher de La transformation DES est en réalité la composition de 16 trans-
dégager une structure particulière sur la fonction de calcul. formations élémentaires paramétrées par des sous-clés
(K1, K2 ... K16) extraites de la clé.
La transformation élémentaire Ti paramétrée par Ki est la
suivante :
3.2 Le DES
— le bloc d’entrée de 64 bit est découpé en deux blocs de 32 bit
Li et Ri ;
3.2.1 Description — et on a :
Li + 1 = Ri
Le DES (Data Encryption Standard ) (figure 12) est le plus connu
des algorithmes de cette classe. Sa description peut être trouvée Ri + 1 = Li ⊕ f ( Ri , Ki )

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
© Techniques de l’Ingénieur, traité Électronique E 6 450 − 7
PROCÉDÉS DE CHIFFREMENT _____________________________________________________________________________________________________________

Cette transformation est quasi involutive et ce, quelle que soit la 3.3 Qualification statistique
nature de f. En effet, il suffit d’inverser le rôle de R et L pour trouver
la transformation inverse :
Tout comme pour le générateur de clé se pose le problème d’éva-
Ri = Li + 1 luation de tels systèmes. L’approche la plus courante est celle de la
Li = Ri + 1 ⊕ f ( Li + 1 , Ki ) qualification statistique. On cherche à voir s’il existe une différence
notable entre le comportement d’une permutation aléatoire (on tire
au hasard l’image de chaque élément) et celui de l’algorithme défini.
Il est facile de vérifier que l’algorithme de déchiffrement est iden- Les principaux tests mis en œuvre consistent à vérifier :
tique à celui de chiffrement à condition d’utiliser la séquence des — qu’il n’existe pas de corrélation entre le bloc de sortie et le bloc
sous-clés dans l’ordre inverse (K16, K15 ... K2, K1). de clé ou le bloc de clair ;
— que la modification d’un bit de clair ou de clé provoque la
modification de chaque bit de cryptogramme avec une probabilité
1
3.2.2 Sécurité du DES de --- .
2

Le problème de la sécurité du DES se pose en regard de deux

types d’attaques : 3.4 Modes d’utilisation standards
— une attaque mathématique contre l’algorithme ;
— une attaque par essais systématiques de toutes les clés. Quatre modes d’utilisation pour les algorithmes par bloc sont
Les attaques mathématiques [2] et [6] exploitent des corrélations standardisés au sein de l’ANSI (ANSI X3.106 et FIPS PUB 81).
entre le clair et le résultat d’un calcul intermédiaire du crypto-
gramme pour déterminer les valeurs de certaines composantes des
sous-clés. Elles nécessitent une quantité très importante de couples
3.4.1 Mode dictionnaire ECB
(Electronic Code Book )
clair/cryptogramme connus (de l’ordre de 243), ce qui les rend prati-
quement inopérantes. Elles ont cependant contribué à renforcer les C’est le mode nominal (figure 11). Le clair est découpé en blocs
critères de conception des fonctions non linéaires utilisées dans ce de p bits. Le cryptogramme est calculé par :
type d’algorithme.
Y n = TK ( X n )
Ce mode nécessite une synchronisation bloc. Une erreur sur un
3.2.3 Triple DES bit de cryptogramme crée un bloc entier erroné de clair déchiffré.

3.4.2 Mode chaîné CBC (Cipher Block Chaining)

La taille relativement réduite de l’espace des clés (256) au regard
des moyens de calcul actuels est le facteur le plus compromettant Ce mode (figure 14) nécessite un vecteur d’initialisation Y0. Le
pour la sécurité du DES. Pour pallier cette faiblesse, la NSA (Natio- clair est chiffré par bloc de p bits et on a :
nal Security Agency) a proposé comme standard le triple DES au
sein du projet CAPSTONE. — chiffrement :
Il consiste à surchiffrer à l’aide de deux clés indépendantes K1 et Yn = TK ( Xn ⊕ Yn Ð 1 )
K2, ce qui porte la taille totale de la clé à 112 bit.
La fonction de chiffrement, illustrée par la figure 13 est : — déchiffrement :

X n = T KÐ1 ( Y n ) ⊕ Y n Ð 1
M ° T K 1 ° ( T K 2 ) Ð 1 ° T K 1( M )
Ce mode nécessite une synchronisation de départ. Si une erreur
où T est la fonction de chiffrement du simple DES. de transmission apparaît sur le bloc Yn , elle reste localisée au
même endroit dans le bloc de clair X n+1 déchiffré, et le bloc X n sera
La fonction de déchiffrement est : complétement erroné (1 bit sur 2 est faux en moyenne).

M ° ( T K1 ) Ð1 ° T K ° ( T K1 ) Ð1 ( M )
2

Ce procédé permet de rester compatible avec le simple DES en X1 X2 Xn

prenant K1 = K2.

Y0

TK TK TK
M Γ
DES DES–1 DES
Clair Cryptogramme

K1 K2 K1 Y1 Y2 Yn – 1 Yn

Figure 13 – Schéma du triple DES en chiffrement Figure 14 – Mode chaîné CBC

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
E 6 450 − 8 © Techniques de l’Ingénieur, traité Électronique
____________________________________________________________________________________________________________ PROCÉDÉS DE CHIFFREMENT

3.4.3 Mode autosynchronisant CFB

(Cipher Feed Back mode)
4. Systèmes à clé publique
Dans ce mode (figure 15), le clair est traité par bloc de k bits. On
effectue le OU EXCLUSIF avec les k bits de gauche issus de l’algo- 4.1 Définition
rithme. Les k bits de cryptogramme obtenus sont réinjectés en
entrée de l’algorithme en décalant le registre d’entrée de k positions Cette notion relativement récente a été introduite en 1976 par
vers la gauche. La valeur de k est en généralement prise égale à 8. Diffie et Hellman [3]. La relation qui lie les clés de chiffrement et de
Ce mode est autosynchronisant. Dans le cas où k = 8, après huit déchiffrement repose sur l’existence de fonction à sens unique ou à
octets de cryptogramme correctement reçus, les entrées en émis- trappe.
sion et en réception sont identiques. Les erreurs de transmission Une fonction à sens unique est caractérisée par :
seront propagées sur huit octets.
— une grande facilité de calcul de l’image de la fonction ;
— une impossibilité calculatoire d’inverser la fonction.
3.4.4 Mode générateur de clé OFB Une fonction à trappe est une fonction qui est à sens unique sauf
(Output FeedBack mode) en connaissant une information secrète supplémentaire (la trappe)
qui permet de l’inverser.
Dans ce mode (figure 16), la clair est traité par bloc de k bit et on Pour construire un tel système, il faut choisir un problème algo-
effectue le OU EXCLUSIF avec les k bit de gauche issus de l’algo- rithmiquement difficile. Il suffit alors de choisir une clé de déchiffre-
rithme. La sortie de l’algorithme à la ne itération devient l’entrée de ment que l’on tient secrète et de calculer la clé publique de
la (n + 1)e itération : chiffrement correspondante.

En = TK ( En Ð 1 )
Yn = Kn ⊕ Xn ( bloc de k bits ) 4.2 Chiffrement El Gamal
Ce mode est à synchronisation de départ et ne propage pas les
erreurs de transmission. L’algorithme de calcul par bloc se com- Ce système est basé sur l’existence d’une fonction à sens unique.
porte exactement comme un générateur de clé. Un exemple de ce type de fonction est donné par l’exponentiation
modulo un grand nombre premier p.
Étant donnés deux entiers a et n, il existe des algorithmes qui per-
mettent de calculer rapidement y = a n modulo p. L’opération inverse
qui consiste à retrouver n à partir de la donnée de y et de a (loga-
rithme discret en base a) est, elle, algorithmiquement très difficile.
E k décalages
L’utilisateur choisit un grand nombre premier p (150 chiffres) et un
k bit élément générateur g du groupe Z ⁄ p Z des entiers modulo p. Il
choisit également un entier x, strictement inférieur à p qui consti-
tuera sa clé secrète et calcule y = g x modulo p qu’il diffuse et qui
constitue sa clé publique.
K T
L’espace des messages est constitué des entiers strictement infé-
rieurs à p.
k bit Pour chiffrer un message M, il faut choisir un nombre aléatoire k.
Le cryptogramme est alors constitué des deux composantes suivan-
Clair Cryptogramme
tes (les opérations ont lieu modulo p) :
k bit k bit
Γ = ( g k, My k ) = ( Γ 1, Γ 2 )

Figure 15 – Mode autosynchronisant CFB La véritable clé de chiffrement du message est la quantité
y k modulo p. La première composante du cryptogramme Γ1 est une
donnée qui permet au destinataire de la calculer grâce à sa clé
secrète.
On notera que la taille du cryptogramme est le double de celle du
message clair, ce qui peut parfois poser des problèmes d’exploita-
En tion.
Pour déchiffrer, on calcule successivement :
n bit
n bit Γ 1x ≡ ( g k ) x ≡ ( g x) k ≡ y k modulo p

et
K T M ≡ Γ 2 × ( Γ 1x ) Ð1 modulo p
En + 1
k bit Remarque : l’exemple précédent utilise le groupe multiplicatif
des entiers modulo p. Tout autre choix est possible, en parti-
Clair Cryptogramme culier de nombreux systèmes récents utilisent le groupe des
k bit k bit points d’une courbe elliptique [7], ce qui présente l’avantage de
pouvoir utiliser des clés plus courtes (160 bit) pour un niveau de
sécurité équivalent.
Figure 16 – Mode générateur de clé OFB

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
© Techniques de l’Ingénieur, traité Électronique E 6 450 − 9
PROCÉDÉS DE CHIFFREMENT _____________________________________________________________________________________________________________

4.3 Le RSA 4.4 Autres utilisations

L’algorithme de Rivest, Shamir et Adelman (RSA) [8] est construit Ces algorithmes sont parfois qualifiés d’algorithmes asymétri-
à partir d’une fonction à sens unique avec trappe. Celle-ci est basée ques car la nature des clés est différente : l’une est publique et
sur le problème difficile de la factorisation des grands nombres l’autre secrète. Cette caractéristique s’avère très intéressante dans
entiers. À l’heure actuelle (1998), les meilleurs algorithmes de facto- plusieurs mécanismes de sécurité : authentification, signature, etc.
risation permettent de prétendre factoriser des nombres entiers de
130 chiffres environ avec des moyens de calcul très puissants Dans un schéma de signature, le rôle des clés publique et secrète
(réseaux d’ordinateurs) en plusieurs centaines d’heures. est inversé : la clé de chiffrement est tenue secrète de telle sorte que
seule l’autorité habilitée puisse signer un message ; par contre, la
Des nombres de 200 chiffres sont totalement hors de portée des clé de déchiffrement est rendue publique pour que tous puissent
algorithmes actuels. vérifier la signature.
Partant de ce principe, chaque utilisateur va choisir deux grands Un autre avantage de ces systèmes vient du fait qu’il n’est pas
nombres premiers p et q (de 100 chiffres par exemple) qu’il garde nécessaire de diffuser le secret qui reste localisé là où il a été créé.
secrets. Il rend public leur produit N = p × q et un nombre r, pre- C’est donc une bonne alternative au problème de gestion des clés.
mier avec Φ (N ) = (p – 1)(q – 1) qui est l’ordre du groupe multiplica- En revanche, la complexité des calculs effectués ne permet pas
tif des entiers modulo N. d’atteindre des débits élevés. Avec des nombres de plus de 150 chif-
L’espace des messages est formé des entiers strictement infé- fres, les débits sont actuellement de l’ordre de quelques dizaines de
rieurs à N. La fonction de chiffrement est : kilobits par seconde.
X ° X r ( modulo N ) C’est pourquoi ce procédé n’est en pratique utilisé en chiffrement
que pour transmettre une clé qui sera utilisée ensuite par un sys-
La fonction de déchiffrement est : tème conventionnel (DES par exemple), pour chiffrer l’ensemble du
message à un débit bien plus élevé.
Y ° Y s ( modulo N )
où s est l’inverse de r modulo Φ (N ). Cette clé est secrète puisqu’il
est nécessaire de connaître Φ (N ) pour la calculer.
4.5 Sécurité des systèmes à clé publique
On a bien :
Y s = ( X r ) s = X rs = X kΦ (N ) + 1 = X
L’attaque reconnue comme la plus efficace contre le RSA reste la
puisque Φ (N ) est l’ordre du groupe Z ⁄ N Z et que par conséquent factorisation de N. Le comportement des divers algorithmes de fac-
X Φ (N ) = 1. torisation est fonction de la taille et de la forme des nombres qui
Il est très facile de voir que la connaissance de Φ (N ) est équiva- composent N. Il est donc nécessaire d’avoir une bonne méthodologie
lente à celle de la factorisation de N. de création des clés.

Si la factorisation de N est connue, Φ (N ) se calcule facilement La sécurité des systèmes à clé publique est une sécurité condi-
puisque : tionnelle qui est soumise :
— aux progrès technologiques effectués en matière de puissance
Φ (N ) = (p – 1)(q – 1) de calcul ; on observe depuis plusieurs décennies que pour un coût
Inversement, si Φ (N ) est connu, alors : de mise en œuvre constant, la puissance des calculateurs est multi-
pliée par un facteur 10 tous les 5 ans ;
— à des progrès mathématiques qui peuvent conduire à une
 pq = N
 amélioration notable des performances des algorithmes de factori-
p + q = N + 1 Ð Φ (N) sation et de calcul des logarithmes discrets.
Il est important de noter que la notion de fonction à sens unique
Il est donc simple d’en déduire p et q.
avec ou sans trappe est aujourd’hui une notion calculatoire empiri-
Exemple numérique (sans valeur cryptologique compte tenu de la que. Le calcul du logarithme discret est dans sa généralité un pro-
taille des entiers manipulés) : le concepteur choisit deux entiers pre- blème difficile et il n’existe actuellement que des algorithmes de
miers p = 7 et q = 11. complexité exponentielle pour le résoudre. On ne sait cependant
Il calcule N = 7 × 11 = 77 et Φ (N ) = 6 × 10 = 60 . Il choisit r pre- pas démontrer cette difficulté, et l’existence même de fonction à
mier avec 60, par exemple r = 13 et calcule son inverse modulo 60 (par sens unique reste un problème théorique ouvert.
l’algorithme d’Euclide par exemple). On trouve s = 37.
La clé publique est :
N = 77, r = 13
La clé secrète est : 5. Conclusion
s = 37
L’espace des messages est :
{0, 1, 2, ..., 76} La sécurité d’un système de chiffrement est essentiellement fonc-
La fonction de chiffrement est l’élévation à la puissance 13 modulo tion de l’algorithme utilisé, des procédures de mise en œuvre et du
77 et la fonction de déchiffrement est l’élévation à la puissance 37 soin très particulier apporté au problème de gestion des clés : élabo-
modulo 77. ration et distribution. Les divers systèmes existants présentent à la
fois avantages et inconvénients. Le tableau 2 résume les caractéris-
Si le clair est X = 19, alors le cryptogramme est :
tiques des différents systèmes.
Y ≡ X 13 ≡ 61 modulo 77 Le choix d’un système de chiffrement doit s’effectuer en fonction
Le déchiffrement de Y = 61 donne des spécificités du système dans lequel il s’intègre : débit néces-
saire, propagation d’erreur acceptable ou non, environnement opé-
Y 37 ≡ 61 37 ≡ 19 ≡ X modulo 77 rationnel pour la gestion des clés, etc.

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
E 6 450 − 10 © Techniques de l’Ingénieur, traité Électronique
____________________________________________________________________________________________________________ PROCÉDÉS DE CHIFFREMENT

Tableau 2 – Caractéristiques des différents systèmes de chiffrement

Générateur de clé Calcul par bloc Système clé publique/RSA
Critères de sécurité Taille de la clé Taille de la clé Liés à un problème difficile
période et complexité Statistique (factorisation par exemple)
linéaire
Qualité statistique
Débit Existent pour tous les débits Tous débits jusqu’à plusieurs Limité à quelques dizaines de kilobits/seconde
(limitation technologique centaines de mégabit/seconde pour un RSA de haute sécurité
uniquement)
Mode d’utilisation Nominal ECB Dictionnaire de façon pratiquement exclusive
Autosynsynchronisant CFB
À propagation d’erreur infi- CBC
nie OFB
Propagation d’erreur Pas de propagation Sur un bloc entier Sur un bloc entier tout bit erroné provoque
en mode nominal Taux d’erreur canal Taux d’erreur canal multiplié un taux d’erreur de 0,5 sur le bloc
inchangé par 0,5 fois la taille du bloc
Facilité d’implantation Simple à moyenne Moyenne Difficile. Nécessite la réalisation de circuit
spécialisé pour atteindre des débits importants
(> 10 kbit/s)
Gestion des clés Délicate, problème Délicate, problème Pas de distribution de secret mais problème
de distribution de secret de distribution de secret d’élaboration de clé et de certification de la donnée
publique

Les constructeurs proposent ou bien des équipements spécifi- La cryptologie, qui au départ était la science du chiffrement, s’est
ques (téléphones chiffrants, module chiffre pour télécopieurs, etc.) développée en direction d’autres services de sécurité : protocoles
ou bien des fonctions intégrées dans des terminaux (carte chiffre d’échange de clé, signature, authentification sans divulgation (prou-
pour microcalculateur, etc.). Parfois ces fonctions sont réalisées en ver qu’on est soi sans dire qui on est).
logiciel pour des raisons économiques, mais elles sont entachées Le développement récent de la cryptologie quantique [1] illustre
des problèmes inhérents à ce type de réalisation : faiblesse des bien cette diversification. Il s’agit d’exploiter le principe d’indivisibi-
débits, aspects sécurité informatique. lité du photon pour transférer un secret avec une sécurité absolue.

Références bibliographiques
[1] BENNETT (C.H.), BESSETTE (F.), BRASSARD [4] KNUTH (D.E.). – The art of computer pro- [7] MENEZES (A.J.). – Elliptic curves public key
(G.), SALVAIL (L.) et SMOLIN (J.). – Experi- gramming vol. 2. 2e éd. Addison Wasley, cryptosystems. 128 p. Kluwer academic
mental quantum cryptography. Journal of 1981. publishers. 1993.
cryptology, vol. 5, n° 1, p. 3 à 28. 1992. [8] RIVEST (R.), SHAMIR (A.) et ADLEMAN (L.). –
[5] MASSEY (J.). – Shift-register synthesis and A method for obtaining digital signatures
[2] BIHAM (E.) et SHAMIR (A.). – Differential BCH decoding. IEEE Transaction on informa- and public key cryptosystems. Communica-
cryptanalysis of the Date Encryption Stan- tion theory (USA). 15 janv. 1969. tion of the ACM (USA) n° 2, 1978.
dard, 188 p. Springer-Verlag, 1993.
[6] MATSUI (M.). – Linear cryptanalysis method [9] RUEPPEL (R.A.). – Analysis and design of
[3] DIFFIE (W.) et HELLMAN (M.E.). – Privacy and for the DES cipher. Advances in cryptology – stream cipher, 244 p. Springer-Verlag. 1986.
authentication : an introduction to cryptogra- Eurocrypt ‘93, p. 387 à 397. Springer-Verlag. [10] SHANNON (C.E.). – Communication theory
phy, Proc. IEEE (USA) 67, mars 1979. 1993. of secrecy systems. BSTJ (USA) oct. 1949.

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
© Techniques de l’Ingénieur, traité Électronique E 6 450 − 11