Ce document a été proposé comme sujet de projet informatique pour les élèves du tronc commun de l'Ecole Polytechnique en 1998-99. Sa difficulté est "facile" (*).

DFC - un Algorithme de Chiffrement

Auteur: Serge Vaudenay
Ecole Normale Supérieure - CNRS

1. Préambule

Afin de répondre aux besoins du commerce électronique pour faire face à la criminalité informatique, le gouvernement américain avait proposé un standard de chiffrement DES en 1977, mais qui est à présent inadapté. Un processus pour définir un nouveau standard a été lancé. Le procédé DFC est l'un des quinze candidats à ce standard. Cet algorithme DFC permet de chiffrer ou de déchiffrer un document numérique au moyen d'une clef secrète.

Dans ce projet, on cherche à implémenter le procédé de chiffrement et de déchiffrement DFC. L'implémentation sera de préférence faite en langage Java, mais d'autres langages pourront être envisagés.

On décrit dans un premier temps une fonction DFC qui permet de chiffrer une chaîne arbitraire de 128 bits au moyen d'une clef représentée par une chaîne de bits de longueur au plus 256.

2. Description de DFC

2.1. Notations

Les objets manipulés sont des chaînes de bits ou des entiers. Les chaînes sont représentées en notation hexadécimale (lorsque leur longueur est multiple de 4, sinon, on complète à gauche par des zéros en précisant la véritable longueur). Par exemple,

d43_x représente la chaîne 110101000011. Les entiers sont représentés en notation décimale. On définit les opérations suivantes.

s transforme la chaîne $s$ en un entier.
$|x|$ _l transforme l'entier $x$ en une chaîne de longueur $l$ .
$s|s'$ concaténation de deux chaînes.
$trunc$ _n(s) tronque la chaîne $s$ sur ces $n$ premiers bits.
$s XOR s'$ ou exclusif bit-à-bit de deux chaînes.
$s AND s'$ et bit-à-bit de deux chaînes.
$NOT s$ complémentation bit-à-bit d'un chaîne.
$+, ., mod$ opérations arithmétiques standards sur les entiers.

Par exemple,

d43_x=3395 et

|3395|

₁₂=d43_x.

2.2. Description de Haut Niveau

La fonction de chiffrement

DFC

_K traite un bloc de 128 bits au moyen d'une clef secrète

K

de longueur arbitraire, au plus 256. La fonction de déchiffrement

DFC

_K^-1 opère également sur des chaînes de 128 bits.

La clef secrète est tout d'abord transformée en une chaîne de 1024 bits $EK$ ("Expanded Key") au moyen d'une fonction $EF$ ("Expanding Function"), soit $EK=EF(K)$ . Comme cela est détaillé dans la section 2.5, $EF$ effectue un schéma de Feistel à quatre étages. Le chiffrement lui-même est un schéma à huit étages semblable. Chaque étage utilise une fonction $RF$ ("Round Function"). Cette fonction transforme une chaîne de 64 bits en une autre au moyen d'un paramètre de 128 bits. Elle est décrite dans la section 2.3.

Etant donné un bloc de 128 bits $PT$ , on le découpe en deux demi-blocs de 64 bits $R$ ₀ et $R$ ₁ de telle sorte que $PT=R$ ₀|R₁. La clef étendue de 1024 bits $EK$ est découpée en huit chaînes de 128 bits par

EK=RK

₁

₂

₈

où

RK

_i est la

i

-ème clef d'étage ("Round Key").

On construit alors une suite $R$ ₀,...,R₉ suivant la récurrence du schéma de Feistel

R

_i+1

_{RK_i}

_i-1

On pose alors

CT=DFC

_K(PT)=R₉|R₈ (voir Fig. 1).

Plus généralement, à partir d'une chaîne $s$ de longueur $128r$ , on découpe $s$ en blocs de longueur 128

s=p

₁

₂

La chaîne

s

définit alors une permutation

Enc

_s sur l'ensemble des chaînes de 128 bits par un schéma de Feistel à

r

étages. Une chaîne de 128 bits

m

est scindée en deux parties de 64 bits

m=x

₀|x₁. On construit alors la séquence

x

₀,...,x_r+1 par

x

_i+1

_{p_i}

_i-1

On définit alors

Enc

_s(m)=x_r+1|x_r. La fonction

DFC

_K est en fait

DFC

_EF(K)

(qui est donc bien un schéma de Feistel à 8 étages). La fonction

EF

est un schéma à 4 étages définit également à partir de

Enc

De manière triviale, on a $DFC$ _K^-1=Enc_revEK où

revEK=RK

₈

₇

₁

Fig. 1: Schéma de Feistel à 8 Etages.

Pour chiffrer une chaîne $PT$ de longueur arbitraire $l$ au moyen d'une clef $K$ , on commence par coder $l$ sur 64 bits par $|l|$ ₆₄ et l'on constitue une chaîne $s$ de bits tous nuls de longueur minimale telle que

PT|s|(|l|

₆₄

soit de longueur multiple de 128. On découpe alors cette chaîne en blocs de 128 bits

PT|s|(|l|

₆₄

₁

₂

On définit ensuite la séquence

CT

₁,...,CT_n par

CT

₁

CT

_i-1

La chaîne

CT=CT

₁|...|CT_n est le résultat du chiffrement de

PT

2.3. La Fonction $RF$

La fonction

RF

utilise un paramètre de 128 bits, soit deux paramètres de 64 bits: un "paramètre

a

", et un "paramètre

b

". Elle traite des chaînes de 64 bits. On définit

RF

_a|b

⁶⁴

₆₄

où

CP

est une permutation sur l'ensemble des chaînes de 64 bits (que l'on définit dans la section 2.4). Cette construction constitue un "module de décorrélation".

2.4. La Permutation $CP$

La permutation

CP

("Confusion Permutation") utilise une table à 6 bits d'entrée et 32 bits de sortie

RT

("Round Table").

Si $y=y$ _l|y_r est l'entrée de $CP$ où $y$ _l et $y$ _r sont des chaînes de 32 bits, on définit

CP(y)=
|

(y_r XOR RT(trunc₆(y_l)))| (y_l XOR KC)

⁶⁴

₆₄

où

KC

est une constante prédéfinie de 32 bits, et

KD

est une constante de 64 bits. La permutation

CP

est schématisée sur la figure 2.

Fig. 2: La Permutation

CP

Les constantes $RT(0),...,RT(63)$ , $KC$ et $KD$ seront définies dans la section 2.6.

2.5. Diversification de la Clef

Afin de créer la séquence

RK

₁,RK₂,...,RK₈ à partir de

K

de longueur au plus 256, on utilise le procédé suivant. On complète tout d'abord

K

par une chaîne constante prédéfinie

KS

que l'on tronque sur 256 bits pour obtenir la chaîne

PK

("Padded Key")

PK=trunc

₂₅₆

(Si

K

est de longueur 128, on note que seuls les 128 premiers bits de

KS

sont utiles.)

On découpe ensuite $PK$ en 8 chaînes de 32 bits $PK$ ₁,...,PK₈ telles que $PK=PK$ ₁|...|PK₈. On définit

OAP

₁

₈

₁

₅

₄

₁

₂

₇

₁

₆

₃

On définit également

OAP

₁

pour

i=2,3,4

(où

KA

_i et

KB

_i sont des constantes définies dans la section 2.6). (Le nom des variables vient de "Odd $a$ -Parameter", "Odd $b$ -Parameter", "Even $a$ -Parameter", et "Even $b$ -Parameter".)

On définit

EF

₁

₄

Cela définit une permutation

Enc

_EF₁(K). De même,

EF

₂

₁

₄

définit une autre permutation

Enc

_EF₂(K).

$Enc$ _EF₁(K) et $Enc$ _EF₂(K) permettent de définir $RK$ . On pose $RK$ ₀=|0|₁₂₈ et

RK

_EF₁(K)

_i-1

_EF₂(K)

_i-1

On définit enfin

EF(K)=RK

₁

₂

₈

2.6. Définition des Constantes

L'algorithme utilise plusieurs constantes prédéfinies:

64 constantes $RT(|0|$ ₆),...,RT(|63|₆) de 32 bits,
une constante $KD$ de 64 bits,
une constante $KC$ de 32 bits,
trois constantes $KA$ ₂,KA₃,KA₄ de 64 bits,
trois constantes $KB$ ₂,KB₃,KB₄ de 64 bits,
une constante $KS$ de 256 bits.

Afin de convaincre qu'aucune trappe n'a été dissimulée dans la conception de DFC, on définit ces constantes à partir de la constante mathématique $e$

 $+oo
   ----  1
e= \    --- = 2.$ b7e15162 8aed2a6a bf7158_x...
   /___  n!
    n=0

EES

(" $e$ Expansion String") est l'expansion hexadécimale des 2144 premiers bits de

e

, on définit

EES=RT(0)|RT(1)|...|RT(63)|KD|KC

trunc

₆₄₀

₂

₃

₄

₂

₃

₄

La chaîne

EES

est la suivante.

b7e15162 8aed2a6a bf715880 9cf4f3c7 62e7160f 38b4da56

a784d904 5190cfef 324e7738 926cfbe5 f4bf8d8d 8c31d763

da06c80a bb1185eb 4f7c7b57 57f59584 90cfd47d 7c19bb42

158d9554 f7b46bce d55c4d79 fd5f24d6 613c31c3 839a2ddf

8a9a276b cfbfa1c8 77c56284 dab79cd4 c2b3293d 20e9e5ea

f02ac60a cc93ed87 4422a52e cb238fee e5ab6add 835fd1a0

753d0a8f 78e537d2 b95bb79d 8dcaec64 2c1e9f23 b829b5c2

780bf387 37df8bb3 00d01334 a0d0bd86 45cbfa73 a6160ffe

393c48cb bbca060f 0ff8ec6d 31beb5cc eed7f2f0 bb088017

163bc60d f45a0ecb 1bcd289b 06cbbfea 21ad08e1 847f3f73

78d56ced 94640d6e f0d3d37b e67008e1 86d1bf27 5b9b241d

eb64749a

On peut recalculer cette chaîne à l'aide du programme Maple par la commande suivante.
convert(floor(evalf((E-2)*2^2144,800)),hex);

2.7. Un Exemple de Chiffrement

Voici un exemple de calcul qui utilise la clef

K=

01234567890123456789012345678901

et le message

PT=0000000000000000 0000000000000000.

On note

RV

_ij la valeur obtenue après le tour

j

dans le calcul de

RK

_i. On a

K =

01234567890123456789012345678901

0123456789012345 6789012345678901
            da06c80abb1185eb 4f7c7b5757f59584

₁

0123456757f59584

₁

da06c80a45678901

₁

890123454f7c7b57

₁

bb1185eb67890123

₁₀

0000000000000000

₁₁

0000000000000000

₁₂

da2e0e338cfde0ad

₁₃

4d94f3e1f9f88702

₁₄

1db16891b4d94189

₁₅

496d91990be5df5c

₁

496d91990be5df5c 1db16891b4d94189

₂₀

496d91990be5df5c

₂₁

1db16891b4d94189

₂₂

a602d54d6849a8e6

₂₃

47fe744df4775602

₂₄

e6965e1e1aa22ad8

₂₅

fe338d5835695c9e

₂

fe338d5835695c9e e6965e1e1aa22ad8

₃₀

fe338d5835695c9e

₃₁

e6965e1e1aa22ad8

₃₂

bca2e2649c823328

₃₃

4e2acbfa4d334a8c

₃₄

3a2e390cdb84b6ff

₃₅

736ccee6099b8943

₃

736ccee6099b8943 3a2e390cdb84b6ff

₄₀

736ccee6099b8943

₄₁

3a2e390cdb84b6ff

₄₂

50203bac2471862e

₄₃

5efe5d55c859d94f

₄₄

c0267e81d0868d26

₄₅

979d063435bd234b

₄

979d063435bd234b c0267e81d0868d26

₅₀

979d063435bd234b

₅₁

c0267e81d0868d26

₅₂

731d89866c9df5ac

₅₃

84c6b187fb68a1e4

₅₄

a95a41963c2fdb84

₅₅

b9ccb771164dfc63

₅

b9ccb771164dfc63 a95a41963c2fdb84

₆₀

b9ccb771164dfc63

₆₁

a95a41963c2fdb84

₆₂

0b54cb25e107c2ab

₆₃

b5636ce10fd014a4

₆₄

81fa21815c0ad0ae

₆₅

73996b00d23b5b92

₆

73996b00d23b5b92 81fa21815c0ad0ae

₇₀

73996b00d23b5b92

₇₁

81fa21815c0ad0ae

₇₂

4c3b7db300977c2f

₇₃

7be02f9bc16f843e

₇₄

c339e4ae2d7e16df

₇₅

13af53a7896725f2

₇

13af53a7896725f2 c339e4ae2d7e16df

₈₀

13af53a7896725f2

₈₁

c339e4ae2d7e16df

₈₂

c50e7eccb65c17a2

₈₃

c9d975f72afdef6a

₈₄

37b2f77af0751899

₈₅

dac0f37721ffcefa

₈

dac0f37721ffcefa 37b2f77af0751899

0000000000000000 0000000000000000

₀

0000000000000000

₁

0000000000000000

₂

6c1b4d8e52704028

₃

16f3bd886ae0475b

₄

393b9f7d70f861d0

₅

32fb659039ed7de6

₆

421352800fce6ba0

₇

a6d043236393c24e

₈

f567576616077eef

₉

bb46bb6ac0093c1d

bb46bb6ac0093c1d f567576616077eef

3. Travail Demandé

Développer une application qui permet de chiffrer et de déchiffrer un fichier. Estimer la vitesse de chiffrement obtenu. Quel est le coût d'une recherche exhaustive de la clef?

4. Références

Data Encryption Standard. Federal Information Processing Standard Publication 46, U. S. National Bureau of Standards, 1977.
E. Biham, A. Shamir. Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993.
H. Feistel. Cryptography and Computer Privacy. Scientific American, vol. 228, pp. 15-23, 1973.
M. Matsui. The First Experimental Cryptanalysis of the Data Encryption Standard. In Advances in Cryptology CRYPTO'94, Santa Barbara, Californie, U.S.A., Lectures Notes in Computer Science 839, pp. 1-11, Springer-Verlag, 1994.
S. Vaudenay. Provable Security for Block Ciphers by Decorrelation. In STACS 98, Paris, France, Lectures Notes in Computer Science 1373, pp. 249-275, Springer-Verlag, 1998.
S. Vaudenay. The Decorrelation Technique Home-Page.
URL:http://lasec.epfl.ch/decorrelation.shtml

DFC - un Algorithme de Chiffrement

1. Préambule

2. Description de DFC

2.1. Notations

2.2. Description de Haut Niveau

2.3. La Fonction RF

2.4. La Permutation CP

2.5. Diversification de la Clef

2.6. Définition des Constantes

2.7. Un Exemple de Chiffrement

3. Travail Demandé

4. Références

2.3. La Fonction $RF$

2.4. La Permutation $CP$