CRYPTOGRAPHIE

SYMETRIQUE

26/02/2020 cours cryptographie 1

 Grands nombres
10^11 Durée de vie de l’univers (2^37) années
Nombre d’atomes constituant l’univers 10^77 (2265)
Nombre d’atomes constituant la galaxie 10^67 (2223)
Nombre d’atomes constituant la terre 10^51 (2170)
Age de l’univers 10^10 (2^34) années
Age de la terre 10^9 (2^30) années
Temps d’ici à ce que le soleil explose 10^9 (2^30) années
Probabilité de gagner au loto américain 1/4000000 (2^22)
Probabilité de mourir foudroyé 1/9 milliards (2^33)

26/02/2020 cours cryptographie 2

 Chiffrement par blocs
Réseaux de Shannon

L'idée générale du chiffrement par blocs est la

suivante:
1- Remplacer les caractères par un code binaire
2- Découper cette chaîne en blocs de longueur
donnée
3- Chiffrer un bloc en l'"additionnant" bit par bit à
une clef.
4- Déplacer certains bits du bloc.
5- Recommencer éventuellement un certain nombre
de fois l'opération 3. On appelle cela une ronde.
6- Passer au bloc suivant et retourner au point 3
jusqu'à
26/02/2020ce que tout le cours
message
cryptographie soit chiffré. 3
Réseaux S-P de Shannon

26/02/2020 cours cryptographie 4

 Chiffrement par substitution
Les substitutions consistent à remplacer des
symboles ou des groupes de symboles par
d'autres symboles ou groupes de symboles
dans le but de créer de la confusion.

Chiffrement par transposition

Les transpositions consistent à mélanger les
symboles ou les groupes de symboles d'un
message clair suivant des règles prédéfinies
pour créer de la diffusion.

Ces règles sont déterminées par la clé de

chiffrement. Une suite de transpositions
forment une permutation.

26/02/2020 cours cryptographie 5

26/02/2020 cours cryptographie 6
 Chiffrement par produit : la combinaison
des deux
 Le chiffrement par substitution ou par
transposition ne fournit pas un haut niveau de
sécurité, mais en combinant ces deux
transformations, on peut obtenir un chiffrement
robuste.

 La plupart des algorithmes de cryptage par clés

symétriques utilisent le chiffrement par produit.
Un « round » est complété lorsque les deux
transformations ont été faites une fois
(substitution et transposition).

26/02/2020 cours cryptographie 7

26/02/2020 cours cryptographie 8
 Effet d’avalanche

Propriété des chiffrements par blocs composés de

couches (layers) ou "rounds" avec un petit
changement à l'entrée.

Le changement d'un simple bit d'entrée produit

généralement de multiples changements de bits
après un round, plusieurs autres changements de
bits après un autre round jusqu'au changement
éventuel de la moitié du bloc.

26/02/2020 cours cryptographie 9

 Structures de Feistel

 Structure décrite en 1973 (Feistel

– IBM)
Adapte la structure de Shannon
afin de rendre la structure inversible
ce qui permet de réutiliser le
matériel de chiffrement pour
déchiffrer un message. La seule
modification s’effectue sur la
manière dont la clé est utilisée
 Une couche de S-Box et de P-Box
est utilisée par Round

26/02/2020 cours cryptographie 10

 Feistel – principe

Le texte est chiffré à partir de la même

transformation sur le texte clair dans chaque round.

26/02/2020 cours cryptographie 11

 Description du schéma

Dans une construction de Feistel, le bloc

d'entrée d'un round est séparé en deux
parties.
 La fonction de chiffrement est
appliquée sur la première partie du bloc
 et l'opération binaire OU-Exclusif est
appliquée sur la partie sortante de la
fonction et la deuxième partie.
 Ensuite les deux parties sont
permutées et le prochain round
commence.
26/02/2020 cours cryptographie 12
Feistel déchiffrement

L'avantage est que la fonction de chiffrement et la

fonction de déchiffrement sont identiques. Ainsi la
fonction n'a pas à être inversible, c’est la structure
qui l’est

26/02/2020 cours cryptographie 13

D.E.S. (Data Encryption Standard)
Présentation – objectifs

Le D.E.S. (Data Encryption Standard, c’est-à-dire Standard de

Chiffrement de Données) est un standard mondial depuis plus de
15 ans. Bien qu’il soit un peu vieillissant, il résiste toujours très
bien à la cryptanalyse et reste un algorithme très sûr.

Au début des années 70, le développement des communications

entre ordinateurs a nécessité la mise en place d’un standard de
chiffrement de données pour limiter la prolifération d’algorithmes
différents ne pouvant pas communiquer entre eux.

Pour résoudre ce problème, L’Agence Nationale de Sécurité

américaine (N.S.A.) a lancé des appels d’offres.

La société I.B.M. a développé alors un algorithme nommé Lucifer,

relativement complexe et sophistiqué. Après quelques années de
discussions et de modifications, cet algorithme, devenu alors
D.E.S., fut adopté au niveau fédéral le 23 novembre 1976

26/02/2020 cours cryptographie 14

26/02/2020 cours cryptographie 15
Chiffrement symétriques les plus fréquents

26/02/2020 cours cryptographie 16

 DES – Cahier des charges

haut niveau de sécurité

 complètement spécifié et facile à comprendre
 sécurité indépendante de l'algorithme lui-même
disponible à tous
 adaptable à diverses applications
 possibilité d'implantation économique en matériel
 efficace d'utilisation, validable, et exportable

26/02/2020 cours cryptographie 17

 D.E.S. (Data Encryption Standard)
Algorithme

26/02/2020 cours cryptographie 18

Etapes de l’algorithme :
1. Diversification de la clé : fabrication de 16 sous-clés
2. Permutation initiale
3. Calcul médian (16 fois) : application d’un algorithme
complexe appliqué en fonction de la clé
4. Permutation finale

DES – principes généraux

1. 􀂄 La clé
• Constituée de 64 bits dont 56 sont utilisés
aléatoirementdans l’algorithme
• Les 8 autres peuvent être utilisés pour la détection
d’erreurs
• Chacun des 8 bits est utilisé comme bit de parité des 7
groupes de 8 bits.
• Nombre total de clés : 256

26/02/2020 cours cryptographie 19

 Permutation initiale (IP)
Les 64 bits du bloc d’entrée subissent la permutation

Le premier bit sera le bit 58, le second le bit 50, etc.

26/02/2020 cours cryptographie 20

 Calcul médian

1.16 itérations identiques

2. Traite 2 blocs à la fois
- Bloc de 32 bits (données)
􀂉 - Bloc de 48 bits (clés)
3. Résultat = bloc de 32 bits
4. 64 bits initiaux sont divisés en 2 bloc (L et R)
􀂉 - L 3 bits pairs, R 3 bits impairs

26/02/2020 cours cryptographie 21

 Calcul médian

26/02/2020 cours cryptographie 22

 Calcul médian
Fonction F :

1.Expansion

2. Ajout de la clé

3. Transformations
(S-Box, P-Box)

4. Assemblage

26/02/2020 cours cryptographie 23

 Addition de la sous-clé
Les 32 bits sont étendus à 48 bits grâce à une table
d’expansion → E(Rn-1)

26/02/2020 cours cryptographie 24

 Addition de la sous-clé

Le résultat de l’expansion est additionné (xor) à la

sous-clé Kn correspondant à l’itération

26/02/2020 cours cryptographie 25

 Transformations –
S-box
Chaque bloc Bj constitue ensuite l’entrée de
l’opération de substitution réalisée sur base des
SBox

26/02/2020 cours cryptographie 26

 Transformations –
S-box
L'opération de substitution consiste pour
chaque Sbox à calculer :
• b1b6 = n° de ligne
• b2b3b4b5 = n° de colonne

26/02/2020 cours cryptographie 27

26/02/2020 cours cryptographie 28
 Transformations – P-Box

L'opération de permutation est réalisée sur le

résultat de la substitution des S-box et est basée
sur la table suivante:

• Le résultat de cette dernière permutation

est noté F(Rn-1,Kn)

26/02/2020 cours cryptographie 29

 Résultat du calcul médian pour
une ronde

26/02/2020 cours cryptographie 30

 Permutation finale
(IP-1)
Permutation inverse de la permutation initiale

26/02/2020 cours cryptographie 31

26/02/2020 cours cryptographie 32
26/02/2020 cours cryptographie 33
26/02/2020 cours cryptographie 34
26/02/2020 cours cryptographie 35
 DES
Faiblesses et améliorations

26/02/2020 cours cryptographie 36

 Considérations sur la sécurité
1. Questions relatives à la conception de l'algorithme
• caractère confidentiel de la conception
• présence de "trappes"?
• possibilité d'une faiblesse fondamentale?
2. Le nombre d'itérations (16) est il suffisant ?
3. La taille de la clef (56 bits) est elle suffisante?
• originalement, Lucifer prévoyait 128 bits
• possibilité d'une attaque « force brute » réussie?
• possibilité d'une attaque de type « parallèle »
• possibilité de réussite d'une attaque de type "texte
en clair choisi"
4. Toutes ces questions ont reçu des réponses
satisfaisantes

26/02/2020 cours cryptographie 37

 DES - Faiblesses des clés
1. Problème des compléments
• si c = DES(p, k), alors !c = DES(!p, !k)
• n'est pas un problème sérieux
2. Clefs "faibles"
• 0x0101….0101,0xFEFE….FEFE,0x1F1F….1F1F,
0xE0E0….EE0
3. Clefs "semi- faibles"
• paires de clefs dont la deuxième peut décrypter un
message encrypté par la première; p.ex.
0x01FE…01FE et 0xFE01….FE01
• il existe six paires de ce genre
4. Existence possible de paires de clés qui génèrent le
même texte encrypté à partir du même texte en clair
("clustering")
26/02/2020 cours cryptographie 38
Clé complémentaires : 2^55 clés à
tester

64 clés faibles en tout

26/02/2020 cours cryptographie 39

 Longueurs de clés sures
pour 20 ans

26/02/2020 cours cryptographie 40

 6 attaques sur le DES
1. Recherche exhaustive
• Une clé après l'autre, on essaie de déchiffrer un bloc
de données, l'information recueillie sur le texte clair
nous permettant de reconnaître la bonne
• besoin, en moyenne, de 2^55 essais
2. Une machine dédiée
• Deep Crack, tel est le nom de cette machine
extraordinaire, a coûté moins de 210'000$.
• un temps de recherche moyen situé entre 4 et 5
jours.(1998)

26/02/2020 cours cryptographie 41

26/02/2020 cours cryptographie 42
26/02/2020 cours cryptographie 43
 6 attaques sur le DES
3. Cryptanalyse différentielle
• possibilité de produire au moyen de textes clairs
choisis les textes chiffrés correspondants avec
cette clé inconnue
• La meilleure attaque différentielle connue
demande actuellement 247 textes clairs choisis
4. Cryptanalyse linéaire
• l'attaque la plus efficace connue à ce jour contre
DES
• dictionnaire de (M,C) → attaque à texte clair
connu
• statistiques sur un flot de 243 couples de
données (soit la bagatelle de deux fois 64 To).

26/02/2020 cours cryptographie 44

 Cryptanalyse Différentielle
1. Introduite pour la première fois en 1990 par Eli Biham et Adi Shamir .
2.C’est une nouvelle méthode inconnue en ce temps par le publique.
3.C’est une attaque à texte clair choisi qui est efficace que l’attaque par force
brute.
4.Cryptanalyse différentielle traite des paires de textes chiffrés: paires de
textes chiffrés lesquelles les textes clairs correspondants possèdent des
différences particulières .
5.L’analyse se fait à travers l’évolution de ces différences dans la propagation
des textes clairs au niveau des rondes du DES quand ils sont chiffres par la
même clé.
6.Simplement, choisir les paires de textes clairs avec une différence fixe.
7.Les deux textes en clair peuvent être choisi aléatoirement à condition
qu’ils satisfassent les conditions particulières de différence .
8.The cryptanalyst does not even have to know their values. (For DES, the
term “difference” is defined using XOR. This can be different for different
algorithms.)
9. Alors, en utilisant les différences dans les textes chiffrés résultants ,
assigner différentes probabilités aux différentes clés.
10. Plus l’analyse va plus loin et plus de paires de textes chiffrés , une clé
26/02/2020 cours cryptographie 45
emergera comme étant la plus probable. C’est la bonne clé
 Cryptanalyse Différentielle
- Les détails sont trops compliqués.
-Figure represente une ronde du DES.
- Imaginer une paire d’entrées X et X’ qui ont la différence dX. Les
sorties Y et Y’ sont connues. De toute évidence la différence est connue
Both the expansion permutation and the P-box are known, so ΔA and ΔC
are known. B
and B’ are not known, but their difference ΔB is known and equal to ΔA.
(When looking at the
difference, the XORing of Ki with A and A’ cancels out.) So far, so good.
Here’s the trick: For any
given ΔA, not all values of ΔC are equally likely. The combination of ΔA
and ΔC suggests values for
bits of A XOR Ki and A’ XOR Ki. Since A and A’ are known, this gives us
information about Ki.
Look at the last round of DES. (Differential cryptanalysis ignores the
initial and final permutation.
They have no effect on the attack, except to make it harder to explain.)
If we can identify K16 then we
have 48 bits of the key. (Remember, the subkey in each round consists of
48 bits of the 56-bit key.)
The other 8 bits we can get by brute force. Differential cryptanalysis will
get us K16.

26/02/2020 cours cryptographie 46

AES: Rijndael
 Sommaire
 Introduction

 Bases mathématiques
 Specifications

 Motivation for design choice

 Conclusion
 Introduction
 AES (Advanced Encryption Standard)
– Motivation
– 01/02/97 NIST announced the initiation.
 Sécurité

 Computational efficiency
 Memoire

 Compatible Hardware/software
 Simplicité

 Flexibilité

 Licensing requirements
 Introduction(Cont.)
– 10/02/00 NIST announced the AES
algorithm is Rijndael
– Rijndael
 Joan Daemen & Vincent Rijmen
 Rijndael (Rijmen & Daemen)
 Bases Mathématiques

 Le champs GF(28)
Exemple: (57)16x6+x4+x2+x+1
– Addition
– Multiplication
– Multiplication par x
 Polynomiales avec les coefficients
dans GF(28)
– Multiplication par x
 Bases Mathématiques (Suite.)
 Addition
– La somme de deux éléments est
polynomiale avec les coefficients qui
sont donnés par la somme modulo 2
(i.e., 1+1=0) des coefficients des deux
termes.
– Exemple: 57+83=D4
 (x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2
 Bases Mathématiques (Suite.)
 Multiplication
– Multiplication dans GF(28) correspond avec la
multiplication des polynomes modulo un
polynome binaire irreductible de degré 8. Pour
Rijndael, ce polynome est appelé m(x) et est
donné par : m(x)=x8+x4+x3+x+1 or (11B)16 .
– Exemple: 5783=C1
 (x6+x4+x2+x+1) (x7+x+1) =
x13+x11+x9+x8+x6+x5+x4+x3+1
 x13+x11+x9+x8+x6+x5+x4+x3+1 modulo
x8+x4+x3+x+1 = x7+x6+1
 Bases Mathématiques (Suite.)
 L’algorithme d’Euclide etendu
– La multiplication definie auparavant est
associative et elle possède un élément neutre
(‘01’). Pour un polynome b(x) de degré
inférieur à 8, l’algorithme d’Euclide etendu
peut etre utilisé pour calculer les polynomes
a(x), c(x) tel que b(x) a(x) + m(x) c(x) = 1.
– It follows that the set of 256 possible byte
values, with the EXOR as addition and the
multiplication defined as above has the
structure of the finite field GF(28).
 Mathematical background(Cont.)
 Multiplication by x
– If we multiply b(x) by the polynomial x,we
have:
b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x
– xb(x) is obtained by reducing the above result
modulo m(x). If b7=0, the reduction is identity
operation; if b7=1, m(x) must be subtracted
(i.e. EXORed).
– Example: 57  13 = 57 (010210) =
57AE07=FE
 Mathematical background(Cont.)
 Polynomials with coefficients in
GF(28)
– Assume we have two polynomials over
GF(28):
a(x)=a3x3+a2x2+a1x+a0
b(x)=b3x3+b2x2+b1x+b0
– c(x)= a(x) * b(x) =
c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0
 Mathematical background(Cont.)
 Polynomials with coefficients in
GF(28)
– By reducing c(x) modulo a polynomial of
degree 4, the result can be reduced to a
polynomial of degree below 4. In
Rijndael, the polynomial M(x)=x4+1.
As xi mod x4+1=xi mod 4.
 Mathematical background(Cont.)
 Polynomials with coefficients in
GF(28)
– The modular product of a( x ) and b( x
), denoted by d( x ) = a( x ) b( x ) is
given by d( x ) = d3x3+d2x2+d1x+d0
with
d0 = a0b0 a3b1 a2b2 a1b3
d1 = a1b0 a0b1 a3b2 a2b3
d2 = a2b0 a1b1 a0b2 a3b3
d3 = a3b0 a2b1 a1b2 a0b3
 Mathematical background(Cont.)
 Polynomials with coefficients in
GF(28)
– The operation consisting of multiplication by a fixed
polynomial a( x ) can be written as matrix
multiplication where the matrix is a circulant matrix.
We have:
 Specification
 Rijndael is an iterated block cipher with a
variable block length and a variable key
length. The block length and the key
length can be independently specified to
128, 192, or 256 bits.
 Design rationale
– Most cipher design
 Feistel structure
– Wide Trail Strategy
 S-BOX
The only non-linear step …
S-Box is based on the mapping: X -> X –1 ; where X –1
represents multiplicative inverse in the field.
1. Replaces each byte with its inverse GF (28), g (a); beside
00 mapped to itself.
2. Applies an affine transformation (a bitwise modulo-two
matrix, XOR-ed with the hexadecimal number 63.
EXAMPLE: Lets find SRD [12]. ??
 S-BOX
The SubBytes() transformation is a non-linear byte substitution
that operates independently on each byte of the State using a
substitution table (S-box). This S-box, which is invertible, is
constructed by composing two transformations:
1. Take the multiplicative inverse in the finite field GF(28), the
element {00} is mapped to itself.
2. Apply the following affine transformation (over GF(2) ):

for 0≤i<8, where bi is the i^th bit of the byte, and ci is the ith bit of
a byte c with the value {63} or {01100011}. Here and elsewhere, a
prime on a variable (e.g., b’) indicates that the variable is to be
updated with the value on the right.
In matrix form, the affine transformation element of the S-box can be
expressed as:
Transformation affine
 Specification(Cont.)
The cipher Rijndael consists of
• An initial Round Key addition;
• Nr-1 Rounds;
• A final round.
• In pseudo C code,
Rijndael(State,CipherKey) {
KeyExpansion(CipherKey,ExpandedKey) ;
AddRoundKey(State,ExpandedKey);
For( i=1 ; i<Nr ; i++ )
Round(State,ExpandedKey + Nb*i) ;
FinalRound(State,ExpandedKey + Nb*Nr);
}
 Specification(Cont.)
– Round(State,RoundKey){
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,RoundKey);
}

– FinalRound(State,RoundKey){
ByteSub(State) ;
ShiftRow(State) ;
AddRoundKey(State,RoundKey);
}
 Specification(Cont.)
 State bytes array
– Variable size :
16 ,24 or
32 bytes

 Key bytes array

– Variable size :
16 ,24 or
32 bytes
 Specification(Cont.)
 Key expansion
 Specification(Cont.)
 Key expansion
 Specification(Cont.)
 ByteSub

– Invertible S-Box
– One single S-Box for completely cipher
– High non-linearity
 Specification(Cont.)
 ShiftRow
 Specification(Cont.)
 MixColumn

– c(x) = ‘03’x3+‘01’x2+‘01’x+‘02’
– High Intra-column diffusion
– Interaction with Shiftrow
 High diffusion over multiple rounds
 Specification(Cont.)
 Round key addition
 Specification(Cont.)
 Round transfermation
 Specification(Cont.)
 Round transfermation
 Motivation for design choice
 The reduction polynomial m(x)
– m(x)=x8+x4+x3+x+1 or (11B)16
 The ByteSub S-box
– Invertibility
– Complexity of its algebraic expression
in GF(28)
– Simplicity of description
 Motivation for design choice (Cont.)
 The MixColumn transformation
– Invertibility
– Linearity in GF(2)
– Relevant diffusion power
– Speed on 8-bit processors
– Symmetry
– Simplicity of description
 Motivation for design choice (Cont.)
 The ShiftRow offsets
– The four offsets are different and C0 = 0
– Simplicity
 The key expansion
– Use a invertible transformation
– Diffusion of Cipher Key differences into
the Round Keys
– Simplicity of description
 Motivation for design choice (Cont.)
 Number of rounds
– As a security margin
 Conclusion
 Rijndael has the symmetric and
parallel structure.
– Gives implementer a lot of flexibility
– Have not allowed effective cryptanalytic
attacks
 Rijndael is well adapted to modern
processors.
 Rijndael is suited for Smart cards
 Future Discussion
 Strength against known attacks
– Differential cryptanalysis, linear
cryptanalysis, and etc.
 Weak keys
 Application
Feistel Structure
 Wide Trail Strategy

Linear mixing layer

Xi Xi+1
Non-linear layer

Key addition layer