U L B M’H O E B

U L B M’HO E B

Faculté des Sciences Exaes et des Sciences de la Nature et de la Vie

D M I

Sécurité informatique

S

A ’ :

ère Année Master « Vision Artificielle ».ème Année Master « Architeures Distribuées ».

Par :D. Abdelhabib BMaitre de conférences B

/

Remarques

C , ’ ’ ’ :[email protected]

C C C CC-BY

Responsable : Dr. BOUROUIS Abdelhabib:::::::::::::::::::::::::::Sécurité informatique — -

[email protected]

http://creativecommons.org/

Table des matières

Notions de base أساسية مفاهيم . Introduion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sécurité informatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . L’architeure de sécurité OSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . Les attaques de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Les menaces relevant de problèmes non spécifiques à l’informatique . . . . .. Les pannes et les erreurs (non intentionnelles) . . . . . . . . . . . . . . . .. Les menaces intentionnelles . . . . . . . . . . . . . . . . . . . . . . . .

. Exemples d’attaques intentionnelles à caraère informatique . . . . . . . . . . . . Attaques, servcices et mécanismes . . . . . . . . . . . . . . . . . . . . . . . . . . Les services de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Politique de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Les méthodologies de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Méthode M.A.R.I.O.N . . . . . . . . . . . . . . . . . . . . . . . . . . .. Méthode MEHARI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Méthode M.E.L.I.S.A . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Fiabilité des systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. La struure série . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. La struure parallèle . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Bases de la cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Confusion et diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Cryptosystème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Classes d’attaques sur les primitives cryptographiques . . . . . . . . . . .

... L’attaque à texte chiffré seul (ciphertext-only attack) . . . . . . ... L’attaque à texte clair connu (known-plaintext attack) . . . . . ... L’attaque à texte clair choisi (chosen-plaintext attack) . . . . . . ... L’attaque adaptative à texte clair choisi (adaptive chosen plain-

text attack) . . . . . . . . . . . . . . . . . . . . . . . . . . . ... L’attaque à texte chiffré choisi (chosen ciphertext attack) . . . . ... L’attaque adaptative à texte chiffré choisi (adaptive chosen ci-

phertext attack) . . . . . . . . . . . . . . . . . . . . . . . . .

Crptographie symétrique متماثل تشفير . Cryptosystèmes symétriques المتناظرة) التشفير (أنظمة . . . . . . . . . . . . . . .

i

ii TABLE DES MATIÈRES

. Chiffre par substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Chiffre de César . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Chiffre affine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

... Chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . ... Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . ... Cryptanalyse . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Chiffre de Vigenère . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... Chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . ... Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . ... Cryptanalyse . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Autres chiffres par substitution . . . . . . . . . . . . . . . . . . . . . . . Chiffres par transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chiffre par bloc et chiffre de flux . . . . . . . . . . . . . . . . . . . . . . . . . . . Modes opératoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. ECB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. CBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. PCBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. CFB ou CFC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

... Forme simple . . . . . . . . . . . . . . . . . . . . . . . . . . ... Version détaillée . . . . . . . . . . . . . . . . . . . . . . . .

.. OFB ou OFC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. CTR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. CTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Padding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fonionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Dérivation des sous-clés . . . . . . . . . . . . . . . . . . . . . . . . . . .. Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Clés faibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Attaques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Triple Data Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . . Advanced Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Le vainqueur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fonionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Attaques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Password-based cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . .

Cryptographie asymétrique . Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fondement théorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Authentification de l’origine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Transmission sécurisée de la clé symétrique . . . . . . . . . . . . . . . . . . . . . Bases mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Petit théorème de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . .. Propriétés de la congruence modulo n dans Z . . . . . . . . . . . . . . .

Responsable : Dr. BOUROUIS Abdelhabib:::::::::::::::::::::::::::Sécurité informatique — - ii

TABLE DES MATIÈRES iii

.. éorème de Bachet-Bézout . . . . . . . . . . . . . . . . . . . . . . . . .. Algorithme d’Euclide étendu . . . . . . . . . . . . . . . . . . . . . . .

... L’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . .. éorème des Restes Chinois . . . . . . . . . . . . . . . . . . . . . . .

... Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . ... Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . ... éorème . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . ... Généralisation . . . . . . . . . . . . . . . . . . . . . . . . .

.. Indicatrice d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Calcul de la puissance modulaire . . . . . . . . . . . . . . . . . . . . . . Rivest Shamir Adleman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Création des clés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Chiffrement et déchiffrement du message . . . . . . . . . . . . . . . . .

. Cryptosystème de ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fonionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Echange de clés . Cryptographie quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Introduion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fonionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Echange de clés Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . . .. Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Exemple concret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fondement mathématique . . . . . . . . . . . . . . . . . . . . . . . . .. L’attaque de l’homme du milieu . . . . . . . . . . . . . . . . . . . . . .

Fonctions de hachage . Introduion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Propriétés des fonions de hachage . . . . . . . . . . . . . . . . . . . . . . . .

.. Preimage resistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. nd preimage resistance . . . . . . . . . . . . . . . . . . . . . . . . . . .. Collision resistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fonion de compression. . . . . . . . . . . . . . . . . . . . . . . . . . .. Pseudo-collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Effet avalanche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

... Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . .. Critère d’avalanche strie . . . . . . . . . . . . . . . . . . . . . . . . . .. Critère d’indépendance Bit . . . . . . . . . . . . . . . . . . . . . . . .

. Construion de fonions de hachage . . . . . . . . . . . . . . . . . . . . . . . . MAC basée sur une fonion de hachage . . . . . . . . . . . . . . . . . . . . . . . MAC basée sur un chiffre symétrique par bloc CBC-MAC . . . . . . . . . . . .

Signature digitale . Introduion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fonionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Responsable : Dr. BOUROUIS Abdelhabib:::::::::::::::::::::::::::Sécurité informatique — - iii

iv TABLE DES MATIÈRES

.. Signatures avec appendices . . . . . . . . . . . . . . . . . . . . . . . . .. Signatures avec recouvrement . . . . . . . . . . . . . . . . . . . . . . . .. Signatures basées sur les certificats/sur l’identité . . . . . . . . . . . . . . .. Signature déterministe/probabiliste . . . . . . . . . . . . . . . . . . . .

. Attaques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Déclinaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Signature de Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Digital Signature Standard et Digital Signature Algorithm . . . . . . . . . . . . . . Schemas de signature basés sur RSA . . . . . . . . . . . . . . . . . . . . . . . .

Bibliography

Responsable : Dr. BOUROUIS Abdelhabib:::::::::::::::::::::::::::Sécurité informatique — - iv

Table des figures

. Catégories des attaques aives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Intégrité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Contrôle d’accès. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Taux de défaillance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Moyennes utilisées dans la SdF. . . . . . . . . . . . . . . . . . . . . . . . . . . . MTBF et MTTR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Struures de fiabilité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Struures de base en fiabilité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ciffrement et déchiffrement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Taxonomie des cryptosystèmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . Chiffrement en présence d’espion. . . . . . . . . . . . . . . . . . . . . . . . . .

. La machine de Lorenz utilisée par les Allemands durant la Seconde Guerre mondiale.. . Cryptographie symétrique (à clé secrète). . . . . . . . . . . . . . . . . . . . . . . Jules cesar ou juillet av. J.-C. ou av. J.-C. - mars av. J.-C. . . . . Table de Vigenere. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Substitution homophonique Henri IV . . . . . . . . . . . . . . . . . . . . . . Scytale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chiffre par flux synchrone et asynchrone. . . . . . . . . . . . . . . . . . . . . . . Chiffrement en mode ECB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Déchiffrement en mode ECB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chiffrement en mode CBC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Déchiffrement en mode CBC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chiffrement en mode PCBC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Déchiffrement en mode PCBC. . . . . . . . . . . . . . . . . . . . . . . . . . . . Chiffrement en mode CFB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Déchiffrement en mode CFB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chiffrement en mode CFB en générale. . . . . . . . . . . . . . . . . . . . . . . . Déchiffrement en mode CFB en générale. . . . . . . . . . . . . . . . . . . . . . . Chiffrement en mode OFB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Déchiffrement en mode OFB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chiffrement en mode CTR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Déchiffrement en mode CTR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . CTS opérant sur un chiffrement en mode CBC. . . . . . . . . . . . . . . . . . . . Data Encryption Standard. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Schémas de Feistel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Permutation initiale (IP ) et finale (IP´��1). . . . . . . . . . . . . . . . . . . .

v

vi TABLE DES FIGURES

. L0 et R0 dans la permutation initiale. . . . . . . . . . . . . . . . . . . . . . . . . Expansion (E) et Permutation (P) au début de chaque ronde. . . . . . . . . . . . . Tableaux pour la génération des clés de rondes. . . . . . . . . . . . . . . . . . . . Tables de substitution S à S. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tables de substitution S à S. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Schéma général du DES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Génération de sous clé DES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Décalage dans la création des sous-clés de DES. . . . . . . . . . . . . . . . . . . . Triple DES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Données et clés AES (cas Nk = ). . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm - AES(St, K). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm - Round(St, T). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm - FinalRound(St, T). . . . . . . . . . . . . . . . . . . . . . . . . . . La procédure SubBytes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . AES-S-Box. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Transformation SubBytes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TransformationShiftRows. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Transformation MixColums. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm - ExpandedKey(K,W) Cas . . . . . . . . . . . . . . . . . . . . . . Algorithm - ExpandedKey(K,W) Cas . . . . . . . . . . . . . . . . . . . . . . S-Box inverse d’AES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm - AES

1��1(St,K). . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm - InvRound(St, T). . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm - InvFinalRound(St, T). . . . . . . . . . . . . . . . . . . . . . . .

. Cryptographie asymétrique (à clé publique et privée). . . . . . . . . . . . . . . . . Pierre de Fermat - Première décennie du XVIIe siècle à Beaumont-de-Lomagne

(France) - janvier à Castres (France). . . . . . . . . . . . . . . . . . . . . . Leonhard Paul Euler - avril à Bâle (Suisse) - septembre (à ans) à

Saint-Pétersbourg (Russie). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ron Rivest, Adi Shamir et Len Adleman. . . . . . . . . . . . . . . . . . . . . . . Taher Elgamal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Cryptographie quantique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Whitfield Diffie et Martin Hellman. . . . . . . . . . . . . . . . . . . . . . . . . . Déroulement de l’échange de clés Diffie-Hellman. . . . . . . . . . . . . . . . . . . Schéma général pour l’échange de clés Diffie-Hellman. . . . . . . . . . . . . . . . Exemple concret d’échange de clés Diffie-Hellman.. . . . . . . . . . . . . . . . .

. Fonion de hachage appliquée à entrées différentes. . . . . . . . . . . . . . . . . Fonion de hachage itérative. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Schéma général d’une fonion de hachage. . . . . . . . . . . . . . . . . . . . . . Effet avalanche. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Schéma détaillé d’une fonion de hachage. . . . . . . . . . . . . . . . . . . . . . Construion de fonions de hachage. . . . . . . . . . . . . . . . . . . . . . . . . HMAC SHA-. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fonionnement de CBC-MAC. . . . . . . . . . . . . . . . . . . . . . . . . . . . CBC-MAC avec chiffrement du dernier bloc. . . . . . . . . . . . . . . . . . . .

Responsable : Dr. BOUROUIS Abdelhabib:::::::::::::::::::::::::::Sécurité informatique — - vi

Liste des tableaux

. Chiffrement de Vigenère de « texte secret » avec la clé « clef ». . . . . . . . . . . . . Déchiffrement de Vigenère de « vpbygdihtpx » avec la clé « clef ». . . . . . . . . . . i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Portfolio d’eStream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Le portfolio eStream d’ECRYPT. . . . . . . . . . . . . . . . . . . . . . . . . .

. Etapes de calcul des coefficients de Bézout par l’algorithme d’Euclide étendu. . . .

vii

viii LISTE DES TABLEAUX

Responsable : Dr. BOUROUIS Abdelhabib:::::::::::::::::::::::::::Sécurité informatique — - viii

Liste des Algorithmes

. E- Calcule une puissance modulaire. . . . . . . . . . . . . . E- Calcule une puissance modulaire. . . . . . . . . . . . . . . E-- Calcule une puissance modulaire de façon ré-

cursive. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EMR Calcule une puissance modulaire de façon récursive. . . . . . . . . .

ix

x LISTE DES ALGORITHMES

Responsable : Dr. BOUROUIS Abdelhabib:::::::::::::::::::::::::::Sécurité informatique — - x

Chapitre

Notions de base أساسية مفاهيم

Sommaire. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sécurité informatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . L’architecture de sécurité OSI . . . . . . . . . . . . . . . . . . . . . . . . . . . Les attaques de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Les menaces relevant de problèmes non spécifiques à l’informatique . . . .. Les pannes et les erreurs (non intentionnelles) . . . . . . . . . . . . . . .. Les menaces intentionnelles . . . . . . . . . . . . . . . . . . . . . . .

. Exemples d’attaques intentionnelles à caractère informatique . . . . . . . . . . . Attaques, servcices et mécanismes . . . . . . . . . . . . . . . . . . . . . . . . . Les services de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Politique de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Les méthodologies de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Méthode M.A.R.I.O.N . . . . . . . . . . . . . . . . . . . . . . . . . .. Méthode MEHARI . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Méthode M.E.L.I.S.A . . . . . . . . . . . . . . . . . . . . . . . . . .

. Fiabilité des systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. La struure série . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. La struure parallèle . . . . . . . . . . . . . . . . . . . . . . . . . .

. Bases de la cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Confusion et diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . .. Chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Cryptosystème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Classes d’attaques sur les primitives cryptographiques . . . . . . . . . .

... L’attaque à texte chiffré seul (ciphertext-only attack) . . . . . ... L’attaque à texte clair connu (known-plaintext attack) . . . . ... L’attaque à texte clair choisi (chosen-plaintext attack) . . . . . ... L’attaque adaptative à texte clair choisi (adaptive chosen plain-

text attack) . . . . . . . . . . . . . . . . . . . . . . . . . . ... L’attaque à texte chiffré choisi (chosen ciphertext attack) . . . ... L’attaque adaptative à texte chiffré choisi (adaptive chosen ci-

phertext attack) . . . . . . . . . . . . . . . . . . . . . . . .

C : Notions de base أساسية مفاهيم

. Introduction

Les trois lois de la robotique d’Isaac Asimov :

. Un robot ne peut porter atteinte à un être humain ni en restant passif, laisser cet être humainexposé au danger,

. Un robot doit obéir aux ordres donnés par des êtres humains sauf quand de tels ordres sont encontradiion avec la première loi,

. Un robot doit protéger sa propre existence dans la mesure où une telle proteion ne s’opposepas à la première et seconde loi.

Un système d’information est une organisation d’aivités consistant à acquérir, stocker, transformer,diffuser, exploiter, gérer … les informations. Un des moyens techniques pour faire fonionner unsystème d’information est d’utiliser des systèmes informatiques qui sont devenus la cible de ceux quiconvoitent l’information. Assurer la sécurité de l’information implique ainsi d’assurer la sécurité dessystèmes informatiques.

L’évolution des risques est justifiée par la croissance de l’Internet, la croissance des attaques, lesfailles des technologies, les failles des configurations, les failles des politiques de sécurité, le change-ment de profil des pirates et la complexité croissante qui entraine une plus grande vulnérabilité.

Souffrons-nous du complexe de Frankenstein ou faut-il craindre avec raison les effets perversd’une informatisation trop rapide de la société ?

. Sécurité informatique

La sécurité informatique c’est l’ensemble des moyens techniques, organisationnels, juridiques ethumains mis en œuvre pour minimiser la vulnérabilité d’un système contre des menaces¹ acciden-telles ou intentionnelles.

En anglais : deux termes différents :— « Sécurité = Safety » qui signifie proteion de systèmes informatiques contre les accidents dus à

l’environnement, les défauts du système …etc. Par exemple les systèmes informatiques contrô-lant des procédés temps réels et mettant en danger des vies humaines (transports, énergie, …)

— « Sécurité = Security » qui signifie proteion des systèmes informatiques contre des aionsmalveillantes intentionnelles. Par exemple les systèmes informatiques réalisant des traitementssensibles ou comprenant des données sensibles.

Ainsi la sécurité informatique concerne en français deux domaines :

. Les méthodes et moyens mis en œuvre pour éviter les défaillances « naturelles » dont les effetsont un caraère catastrophique (safety).

. Les méthodes et moyens mis en œuvre pour se protéger contre les défaillances résultant d’uneaion intentionnelle (security).

. En anglais : threat.


. L’architeure de sécurité OSI

. L’architecture de sécurité OSI

L’architeure de sécurité OSI ou « Security architeure for Open Systems Interconneion » dé-crite dans la recommandation X. du CCITT et le standard ISO -, définit les élémentsd’architeure relatifs à la sécurité convenant à une application lorsqu’il faut assurer une proteionde sécurité dans un environnement de systèmes ouverts.

. Les attaques de sécurité

Les menaces sont l’ensemble des aions de l’environnement d’un système pouvant entrainer despertes financières et coûts humains. Nous pouvons citer :

.. Les menaces relevant de problèmes non spécifiques à l’informatique

. Risques matériels accidentels : pour ceci, les techniques de proteion sont assez bien maitri-sées (Incendie, explosion, inondation, tempête, foudre).

. Vol et sabotage de matériels : Vol d’équipements matériels, destruion d’équipements, des-truion de supports de sauvegarde.

. Autres risques : Tout ce qui peut entrainer des pertes financières dans une société. Pertes plutôtassociées à l’organisation, à la gestion des personnels (Départ de personnels stratégiques, grèves,…etc).

.. Les pannes et les erreurs (non intentionnelles)

. Pannes/dysfonionnements du matériel.. Pannes/dysfonionnements du logiciel de base.. Erreurs d’exploitation (oubli de sauvegarde, écrasement de fichiers).. Erreurs de manipulation des informations (erreur de saisie, erreur de transmission, erreur d’uti-

lisation, …). Erreurs de conception des applications.. Erreurs d’implantation.

Tout ce qui précède est rangé dans la case Accident. Le reste est une Malveillance.

.. Les menaces intentionnelles

Qui sont l’ensemble des aions malveillantes (qui constituent la plus grosse partie du risque) quidevraient être l’objet principal des mesures de proteion. Parmi les objeifs des attaques :

— Désinformer— Empêcher l’accès à une ressource— Prendre le contrôle d’une ressource— Récupérer de l’information présente sur le système— Utiliser le système compromis pour rebondir— Constituer un réseau de « botnet » (ou réseau de machines zombies).



F . – Catégories des attaques aives.

Une menace intentionnelle est dite attaque.

Proportions des menaces : Aions malveillantes % (en croissance), Risques accidentels %,Pannes et erreurs %, Autres %.

Deux types d’attaque peuvent être distingués :

. Attaques passives : copie illicite de données. (capture, écoute, …)— Détournement des données (l’écoute, les indiscrétions). Exemples : espionnage industriel,

espionnage commercial, violations déontologiques.— Détournement des logiciels. Exemple : copies illicites.

. Attaques aives : modification/suppression illicite de données.— Modifications des informations. Exemple : la fraude financière informatique.— Le sabotage des informations (logique).— Modification des logiciels. Exemples : Bombes logiques, virus, ver.

Les menaces aives appartiennent principalement à quatre catégories (illustrées dans la figure ??) :

. Interruption = problème lié à la disponibilité des données.

. Interception = problème lié à la confidentialité des données.

. Modification = problème lié à l’intégrité des données.

. Fabrication = problème lié à l’authenticité des données.

Il est possible de préciser la notion de risque en la décrivant comme le produit d’un préjudice parune probabilité d’occurrence :

risque = préjudice ˆ d’occurrence probabilité.

Cette formule exprime qu’un évènement dont la probabilité est assez élevée, par exemple la dé-faillance d’un disque dur, mais dont il est possible de prévenir le préjudice qu’il peut causer, par dessauvegardes régulières, représente un risque acceptable ; il en va de même pour un évènement à lagravité imparable, comme l’impa d’un météorite de grande taille, mais à la probabilité d’occurrencefaible.

Il va de soi que, dans le premier cas, le risque ne devient acceptable que si les mesures de préventioncontre le préjudice sont effeives et efficaces : cela irait sans dire, si l’oubli de cette condition n’étaittrès fréquent.


. Exemples d’attaques intentionnelles à caraère informatique

. Exemples d’attaques intentionnelles à caractère informatique

. D : Pour rentrer dans un système on essaye de piéger des usagers et de se faireprendre pour quelqu’un d’autre. Exemple : simulation d’interface système sur écran ou simu-lation de terminal à carte bancaire.

. R (« R ») : Espionnage d’une interface, d’une voie de communication (télépho-nique, réseau local) pour capter des opérations (même cryptées elles peuvent être utilisables).Répétition de l’opération pour obtenir une fraude. Exemple : Plusieurs fois la même opérationde créditer un compte bancaire.

. A : On observe le trafic de messages échangés pour en déduire des informa-tions sur les décisions de quelqu’un.Exemples : Bourse : augmentation des transaions sur une place financière. Militaire : le débutde concentration entraine un accroissement de trafic important.

. I : On obtient des informations confidentielles non divulguables à partir d’un fais-ceau de questions autorisées (et d’un raisonnement visant à faire ressortir l’information). Exemple :Soit le fichier d’un hôpital, la loi informatique et liberté interdit la divulgation d’informationspersonnelles (sur les maladies), mais autorise des opérations statistiques (améliorer les connais-sances épidémiologiques), donc pas de possibilité de séleion sur le nom, le numéro de sécuritésociale, l’adresse, …etc. Mais questions à caraère statistiques autorisées. Pour obtenir des in-formations confidentielles poser des questions à caraère statistique comportant un faisceaude contraintes permettant en fait de filtrer une seule personne comme question sur les effeifs(sexe = masculin, age = , arrêt maladie, …).

. R : Un usager d’un service (informatique) affirme n’avoir pas : émis un ordre quile gêne a postériori (commande, virement, …) reçu un ordre (idem).Une menace répudiationimplique le traitement d’une transaion de telle façon qu’aucune preuve des entités de sécuritéimpliquées ne subsiste à la transaion. Dans une application Web, cela peut se traduire parl’usurpation des informations d’identification d’un utilisateur innocent.

. M : Une personne non autorisée, un usager oumême un agent autorisé s’attribuent des avantages illicites en modifiant un ?chier, un mes-sage (le plus souvent cette modification est réalisée par programme et entre dans la catégoriesuivante).

. M : Les modifications à caraère frauduleuses : Pour s’attribuerpar programme des avantages. Par exemple :— virement des centimes sur un compte.— Les modifications à caraère de sabotage : Pour détruire avec plus ou moins de motivations

des systèmes ou des données.Deux types de modifications :(a) Infeions informatiques à caraère unique : Bombe logique ou cheval de Troie. Dans un

programme normal on introduit un comportement illicite mis en aion par une condi-tion de déclenchement ou trappe (la condition, le moment ou l’on bascule d’un compor-tement normal à un comportement anormal). Par exemple : licenciement de l’auteur duprogramme date quelconque.

(b) Infeions auto reprodurices : Il s’agit d’une infeion informatique simple (du type pré-cédent) qui contient de plus une partie de recopie d’elle même afin d’en assurer la propaga-tion. Virus : à aion brutale. Ver : à aion lente (détruisant progressivement les ressourcesd’un systèmes).



. Attaques, servcices et mécanismes

Pour considérer efficacement les besoins de sécurité d’une organisation et évaluer et choisir lesnombreux produits et politiques de sécurité, le responsable de la sécurité a besoin de moyens systé-matiques de définition des exigences de sécurité et de caraérisation des approches qui satisfont cesexigences. Une approche possible est de considérer trois aspes de la sécurité de l’information :

. Services de sécurité : un service qui améliore la sécurité des systèmes informatiques et destransferts d’information d’une organisation. Les services sont conçus pour contrer les attaquesde sécurité, et ils utilisent un ou plusieurs mécanismes de sécurité.On peut penser aux services de sécurité de l’information par analogie avec les types de fonc-tions associées aux documents physiques. La plupart des aivité humaines, dans des domainesaussi divers que le commerce, la politique étrangère, les aions militaires, dépendent de l’uti-lisation de documents et de la confiance des deux partis en l’intégrité de ces documents. Lesdocuments portent signatures et dates ; ils peuvent nécessiter une proteion contre la divulga-tion, la falsification ou la destruion ; être attestés, enregistrés, etc. Ã� mesure que les systèmesd’information deviennent plus diffus et essentiels à la conduite des affaires humaines, l’infor-mation éleronique prend en charge bien des rôles traditionnellement dévolus aux documentspapier. En conséquence, les fonions associées aux documents papier doivent être accompliessur des documents au format dématérialisé.Plusieurs aspes propres aux documents éleroniques font qu’assurer ces fonions ou servicesest un défi :— il est habituellement possible de distinguer entre un document papier original et sa pho-

tocopie. Cependant, un document éleronique est purement une séquence de bits ; il n’ya pas de différence entre « l’original » et toutes ses copies ;

— une altération d’un document papier peut laisser des preuves physiques. Par exemple, uneffacement peut laisser une tache ou une surface rugueuse. L’altération de bits dans unemémoire d’ordinateur ou un signal ne laisse à priori aucune trace ;

— tout processus de « preuve » associé à un document physique dépend des caraéristiquesphysiques du document (par exemple, la forme d’une signature manuelle ou un tampon denotaire). De telles preuves d’authenticité d’un document éleronique doivent être baséessur des signes présents dans l’information elle-même.

. Mécanismes de sécurité : un mécanisme est conçu pour déteer, prévenir ou rattraper uneattaque de sécurité.Un seul mécanisme ne peut fournir tous les services de sécurité. On peut noter qu’un élémentparticulier sous-tend la plupart des mécanismes de sécurité en usage : les techniques crypto-graphiques.Le chiffrement - ou des transformations similaires - de l’information est le moyen le pluscourant pour fournir une sécurité. Ainsi, dans ce cours on insistera sur le développement,l’utilisation et la gestion de ces techniques.

. Attaque de sécurité : une aion qui compromet la sécurité de l’information possédée par uneorganisation.La sécurité de l’information traite de la prévention de la fraude, ou, à défaut, de sa détec-tion dans des systèmes d’information à l’intérieur desquels l’information elle-même n’a pasd’existence physique significative. On verra dans les transparents suivants une liste d’exemplesévidents de tricherie, qui se sont produits dans des cas réels. Ce sont des exemples d’attaquesspécifiques qu’une organisation ou un individu peut avoir à affronter. La nature de l’attaquevarie considérablement selon les circonstances.


. Les services de sécurité

Heureusement, il est possible d’approcher le problème en examinant les types génériques d’at-taques pouvant être rencontrées. Ce sera le sujet de la prochaine seion.

. Les services de sécurité

Ce sont les services de base (objeifs de base) qu’on veut assurer ou enjeux de la sécurité dessystèmes d’information devant être maitrisés.

Cinq principaux services à garantir :. A : consistant à s’assurer que seules les personnes autorisées aient accès aux

ressources. Pouvoir s’assurer de l’identité². L’authentification consiste à s’assurer de l’identitéd’un utilisateur, c’est-à-dire de garantir à chacun des correspondants que son partenaire est biencelui qu’il croit être. Un contrôle d’accès peut permettre (par exemple par le moyen d’un motde passe qui devra être crypté) l’accès à des ressources uniquement aux personnes autorisées.³

. I : garantie que l’information n’est pas altérée. Voir la figure ... C : garantie que l’information n’est pas divulguée à des tiers non autorisés

(frauduleusement ou non). Les personnes autorisées ont accès aux éléments considérés. Laconfidentialité consiste à rendre l’information inintelligible à d’autres personnes que les seulsaeurs de la transaion.

. D : garantie de la continuité du service. Les éléments considérés sont accessiblesau moment voulu par les personnes autorisées.

. N-/ : permettant de garantir qu’une transaion effeuée ne peutêtre niée ni et si elle n’a pas eu lieu.

Le contrôle d’accès consiste à vérifier si une entité (une personne, un ordinateur, …) demandantd’accéder à une ressource a les droits nécessaires pour le faire.

Un contrôle d’accès offre ainsi la possibilité d’accéder à des ressources physiques (par exemple unbâtiment, un local, un pays) ou logiques (par exemple un système d’exploitation ou une applicationinformatique spécifique).

Parfois dans la littérature du domaine, on considère un autre service de base qui est le contrôled’accès. A notre avis, il ne s’agit pas d’un service de base. Il est lié étroitement à l’authentification etcomprend généralement composantes :

. Un mécanisme d’authentification de l’entité (par mot de passe, carte à puce, une clé, un élé-ment biométrique, …etc.).

. Un mécanisme d’autorisation (ou d’habilitation) après vérification que l’aion demandée estautorisée (à ce moment). L’habilitation peut avoir une durée limitée !.

. Un mécanisme de traçabilité(respe d’une procédure, heures ouvrées, …etc.). Possibilité depouvoir retrouver a posteriori le responsable d’une aion.

Aujourd’hui, les entreprises sont de plus en plus amenées à tracer leurs accès informatique à l’aided’un « Reporting des Droits d’Accès ».

. s’identifier, c’est communiquer son identité, s’authentifier, c’est apporter la preuve de son identité. L’identification des utilisateurs est fondamentale pour gérer les accès aux espaces de travail pertinents et maintenir

la confiance dans les relations d’échange.



F . – Intégrité.

F . – Contrôle d’accès.

. Politique de sécurité

Une politique de sécurité des systèmes d’information (PSSI) est un ensemble de règles qui fixentles aions autorisées et interdites dans le domaine de la sécurité. C’est un plan d’aions définies(ensemble des modèles d’organisation, des procédures et des bonnes pratiques techniques) permet-tant d’assurer la sécurité du système d’information (maintenir un certain niveau de sécurité) et nese limite pas à la sécurité informatique. Elle constitue alors le principal document de référence etun outil de communication sur l’organisation et les responsabilités SSI, les risques SSI et les moyensdisponibles pour s’en prémunir.

Pour garantir la sécurité, une PSSI est souvent élaborée autour de axes majeurs : la sécuritéphysique des installations, la sécurité logique du système d’information et la sensibilisation des uti-lisateurs aux contraintes de sécurité.

L’audit de sécurité est essentiel dans la SSI. Il permet de mettre en évidence les faiblesses de lamise en œuvre d’une politique de sécurité qui peuvent venir de la politique elle-même si elle est malconçue ou inadaptée aux besoins de l’entreprise, ou bien d’erreurs quand à sa mise en application.

Des audits sont nécessaires suite à la mise en place initiale d’une PSSI, puis périodiquement pours’assurer que les mesures de sécurité sont mises à niveau et que les usages restent conformes auxprocédures.

L’établissement de la PSSI passe généralement par les étapes suivantes :

. Identification des vulnérabilités— En mode fonionnement normal (définir tous les points faibles)— En cas d’apparition de défaillances, un système fragilisé est en général vulnérable : c’est

dans un de ces moments intermédiaires qu’une intrusion peut le plus facilement réussir.


. Les méthodologies de sécurité

. évaluation des probabilités associées à chacune des menaces.. évaluation du coût d’une intrusion réussie.. Choix des contre mesures.. évaluation des coûts des contre mesure.. Décision.

L’établissement de la PSSI est souvent réalisé utilisant une démarche claire. Une méthodologieprésente, de façon détaillée la conduite de projet d’élaboration d’une PSSI.

. Les méthodologies de sécurité

Réalisées par des grands utilisateurs de techniques de sécurité ou des groupes de travail elles sontapplicables par des prestataires de service sous forme d’audit de sécurité, d’analyse de risques et depropositions d’aions pour améliorer la situation.

Diverses méthodes d’analyse des risques existent, certaines simples d’utilisation, avec parfois desoutils logiciels en simplifiant l’utilisation. D’autres méthodes sont réservées à des grands comptes dufait de leur complexité et des ressources humaines impliquées. Quelques unes sont devenu standardsde fait dans certaines entreprises et organisations. Il est convenable de faire un choix judicieux de laméthode qui s’applique le mieux à l’entreprise ou organisme public visé.

Les critères qui guident le choix sont variés et peuvent inclure :

. l’existence d’outils logiciels en facilitant l’utilisation, la qualité de la documentation et l’exis-tence d’un club d’utilisateurs afin d’avoir un retour d’expériences.

. l’origine géographique de la méthode, la culture du pays jouant beaucoup sur le fonionne-ment interne des entreprises et leur rapport au risque.

. la langue de la méthode, il est essentiel de maitriser le vocabulaire employé.. la facilité d’utilisation et le pragmatisme de la méthode.. la compatibilité avec une norme nationale ou internationale.. le coût de la mise en œuvre.. la taille de l’entreprise à laquelle elle est adaptée.. la quantité de moyens humains qu’elle implique et la durée de mobilisation.. le support de la méthode par son auteur, une méthode abandonnée n’offre plus la possibilité

de conseil et de support de la part son éditeur.. sa popularité, une méthode très connue offre un réservoir de personnels qualifiés pour la mettre

en œuvre.

.. Méthode M.A.R.I.O.N

Méthode d’Analyse des Risques Informatiques et Optimisation par Niveau. (à partir de ).

CLUSIF : Club des Utilisateurs de La Sécurité Informatique Français.

APSAD : Assemblée Plénière des Sociétés d’Assurances Dommages.

Objeif : Mettre en place le schéma direeur de la sécurité des systèmes d’information SDSSI.

Trois approches selon le sujet traité :



. Marion-AP (avant-projet) (Applicable aux grands comptes et aux compagnies d’assurance).. Marion-PME.. Marion-RSX (Applicable aux réseaux).

Les six étapes d’élaboration du Schéma Direeur de Sécurité du Système d’Information :

. Analyse des risques : établissement de scénarios des risques courus par l’entreprise.. Expression du risque maximum admissible : calcul de la perte maximale subie par l’entreprise

face à des évènements mettant sa survie en péril.. Analyse des moyens de la sécurité existants : identifier et qualifier les moyens de la sécurité

(organisation générale, physique et logique). Évaluation des contraintes techniques et financières : recensement des contraintes générales,

techniques, humaines et détermination d’un budget pour la prévention et la proteion.. Choix des moyens de sécurité : moyens à mettre en œuvre ou à améliorer pour supprimer les

risques en fonion des contraintes et du coût parade/risque. Plan d’orientation : phase de bilan définissant le plan technique détaillé et rédaion finale du

SDSSI.

La méthode MARION n’a plus évolué depuis (devenue obsolète). Le CLUSIF propose dé-sormais une méthode harmonisée d’analyse des risques (Méhari).

.. Méthode MEHARI

La méthode harmonisée d’analyse des risques (MEHARI) est une méthode visant à la sécurisa-tion informatique d’une entreprise ou d’un organisme. Elle a été développée et est proposée par leCLUSIF et a rendu la méthode précédente (MARION) obsolète.

Le CLUSIF a présenté le janvier une nouvelle version de sa méthode MEHARI.

.. Méthode M.E.L.I.S.A

Délégation générale à l’armement .

. MELISA S - Confidentialité des données sensibles. MELISA P - Pérennité de fonionnement du système. MELISA M - Sécurité micro mini informatique. MELISA. R - Sécurité réseau

Plusieurs autres méthodes d’analyse de risques existent comme EBIOS⁴, OCTAVE⁵ et il n’estpas possible de donner ici une liste exhaustive.

. Fiabilité des systèmes

La disponibilité du système désigne son aptitude à délivrer le service, alors que sa fiabilité désigneson aptitude à ne pas l’interrompre. Une défaillance survient lorsque le service délivré diffère du

. EBIOS. OCTAVE


http://www.ssi.gouv.fr/site_article173.html

http://www.cert.org/octave/


service demandé. Dans certains cas, notre système « refuse » d’assurer son service, dans d’autres,généralement plus graves, il « décide » de faire autre chose que le service demandé.

La sûreté de fonionnement (SdF)⁶ est l’aptitude à éviter l’apparition de défaillances et à minimiserleurs effets lorsqu’elles se sont produites. La sûreté comprend quatre composantes qui sont la fiabilité,la maintenabilité, la disponibilité et la sécurité. On trouvera aussi l’acronyme FMDS pour désignerla sûreté de fonionnement (comme fiabilité, maintenabilité, disponibilité et sécurité) ou le termeanglais de RAMS (pour reliability, availability, maintainability and safety) …

. La fiabilité d’un système est la probabilité pour que le système fonionne correement pen-dant une durée donnée dans des conditions définies. R(t) = P [S non défaillant sur (0, t)]

. La disponibilité est l’aptitude d’un système à être opérationnel au moment où il est sollicité,c’est la probabilité que le système soit disponible à un instant donné. D(t) = P [S non dé-faillant à l’instant t]

. La maintenabilité d’un système est la probabilité de retour à un bon fonionnement dans unedurée de temps donnée. Les différentes pannes pouvant être cataleiques⁷ (l’élément fonc-tionne ou ne fonionne pas), ou aléatoires (défaillance statistiquement indépendante d’uneprécédente, la panne d’un élément n’affee pas les autres). M(t) = P [S est réparé sur (0, t)]

. La sécurité est l’aptitude d’un système à ne pas connaitre de pannes considérées comme catas-trophiques pendant une durée donnée.

F . – Taux de défaillance.

F . – Moyennes utilisées dans la SdF.

Le comportement d’un système peut être décrit dans le temps comme une suite d’états de bon etde mauvais fonionnement.

. Terme anglais : « Dependability ». Défaillance cataleique : Défaillance qui est à la fois soudaine et complète (Norme CEI--).



F . – MTBF et MTTR

On appelle MTTR, (Mean Time To Repair, temps moyen de toute réparation), le temps néces-saire à la remise en état du système et MTBF (Mean Time Between Failure, temps moyen de bonfonionnement) le temps moyen entre deux pannes successives ou durée moyenne entre deux dé-faillances consécutives d’un équipement réparé.

MTTF : Durée moyenne de fonionnement d’une entité avant la première défaillance (anglais :Mean Time To Failure). Taux de défaillance : λ = 1

MTTF

Si MTTR ! MTTF alors MTTF « MTBF alors λ = 1MTBF

Taux de réparation : µ = 1MTTR

MUT : Durée moyenne de fonionnement après réparation (anglais Mean Up Time)

MDT : Durée moyenne d’indisponibilité après défaillance (anglais Mean Down Time)

MTBF = MDT +MUT

La disponibilité (Avaibility) est définie comme étant le rapport :

A =MTBF

MTBF +MTTR

et l’indisponibilité comme en étant le complément (le matériel est indisponible lorsqu’il n’est plusdisponible) :

I = 1 ´ A =MTTR

MTBF +MTTR

avec :I

A=

MTTR

MTBF

Pour rendre un système plus efficace, on peut jouer sur valeurs : augmenter la MTBF, les com-posants réseaux seront alors plus onéreux ou diminuer les temps d’indisponibilité et c’est la mainte-nance qui devient plus coûteuse.

Selon les relations existantes entre les différents composants du système (Figure .), la résistanceà la défaillance sera plus ou moins grande. Généralement, on distingue quatre struures de base :

. la struure série sans redondance : dans un tel système lorsque l’un des composants tombe enpanne, l’ensemble du système est indisponible ;



. la struure avec duplication de systèmes : dans une telle organisation, la panne d’un seulcomposant n’affee pas le fonionnement global du système ;

. la struure avec duplication de toutes les unités : ici la panne de plusieurs composants ne rendpas le système indisponible ;

. enfin, la struure avec duplication partielle : compte tenu des coûts engendrés par la duplica-tion totale, seuls sont dupliqués, ici, les systèmes les plus sensibles.

F . – Struures de fiabilité.

La mesure de la disponibilité globale d’un système dépend de sa struure. Deux struures élé-mentaires sont à la base de tout système : la struure série et la struure parallèle (Figure .).

.. La structure série

La disponibilité résultante est plus petite que celle du composant le plus faible :

Atotale =i=nź

i=1

Ai

F . – Struures de base en fiabilité.

L’indisponibilité est alors :

Itotale = 1 ´ Atotale = 1 ´

i=nź

i=1

Ai = 1 ´

i=nź

i=1

(1 ´ Ii)



Si A « 1, c’est-à-dire que I est très petit on peut écrire :

Itotale =i=nÿ

i=1

Ii

On montrerait aussi que :

MTBFs =1

ři=ni=1

1MTBFi

.. La structure parallèle

L’indisponibilité du système est plus petite que celle du composant qui a la plus faible indisponi-bilité :

Itotale =i=nź

i=1

Ii

La disponibilité est alors :

Atotale = 1 ´ Itotale = 1 ´

i=nź

i=1

Ii = 1 ´

i=nź

i=1

(1 ´ Ai)

De même, on montre que :

MTTRp =1

ři=ni=1

1MTTRi

. Bases de la cryptographie

La cryptologie, étymologiquement la science du secret, ne peut être vraiment considérée commeune science que depuis peu de temps. Cette science englobe la cryptographie qui signifie

l’écriture secrète et la cryptanalyse qui est l’analyse de cette dernière.

La cryptologie est un art ancien et une science nouvelle : un art ancien car Jules César l’utilisait déjà ;une science nouvelle parce que ce n’est un thème de recherche scientifique académique (comprendreuniversitaire) que depuis les années . Cette discipline est liée à beaucoup d’autres, par exemplel’arithmétique modulaire, l’algèbre, la complexité, la théorie de l’information, ou encore les codescorreeurs d’erreurs.

.. Terminologie

. Chiffrement (تشفير) : transformation (syntaxique) à l’aide d’une clé de chiffrement d’un mes-sage intelligible appelé texte clair واضح) (نص ou libellé en un message incompréhensible ouinintelligible appelé texte chiffré ou cryptogramme si on ne dispose pas d’une clé de déchiffre-ment (en anglais encryption) ; En cryptographie, le chiffrement, parfois appelé à tort cryptage.



. Chiffre شيفرة) أو (شفرة : anciennement code secret, par extension l’algorithme utilisé pour lechiffrement ;

. Cryptogramme (نصمشفر) : message chiffré ; Le destinataire légitime doit pouvoir déchiffrerle cryptogramme et obtenir le texte clair.

. Décrypter الشفرة) (كسر : retrouver le message clair correspondant à un message chiffré sansposséder la clé de déchiffrement (terme que ne possèdent pas les anglophones, qui eux « cassent» des codes secrets), ceci est effeué par un espion (cryptanaliseur, décrypteur ou oreille indis-crète) ⁸ ;

. Cryptographie التعمية) أو التشفير (علم : étymologiquement « écriture secrète », devenue parextension l’étude de cet art (donc aujourd’hui la science visant à créer des cryptogrammes,c’est-à-dire à chiffrer) ;

. Cryptanalyse التشفير) تحليل (علم : science analysant les cryptogrammes en vue de les décrypter ;. Cryptosystème التعمية) (نظام : un ensemble composé d’algorithmes cryptographiques et de

tous les textes en clairs, textes chiffrés et clés possibles. Cryptologie : science regroupant la cryptographie et la cryptanalyse.

Le fait de coder un message de telle façon à le rendre secret s’appelle chiffrement. La méthodeinverse, consistant à retrouver le message original, est appelée déchiffrement.

F . – Ciffrement et déchiffrement.

Le chiffrement se fait généralement à l’aide d’une clé de chiffrement, le déchiffrement nécessitequant à lui une clé de déchiffrement. On distingue généralement deux types de clés :

— Les clés symétriques : il s’agit de clés utilisées pour le chiffrement ainsi que pour le déchiffre-ment. On parle alors de chiffrement symétrique ou de chiffrement à clé secrète.

— Les clés asymétriques : il s’agit de clés utilisées dans le cas du chiffrement asymétrique (aussi ap-pelé chiffrement à clé publique). Dans ce cas, une clé différente est utilisée pour le chiffrementet pour le déchiffrement.

On appelle décryptement (le terme de décryptage peut éventuellement être utilisé également) lefait d’essayer de déchiffrer illégitimement le message (que la clé de déchiffrement soit connue ounon de l’attaquant).

Lorsque la clé de déchiffrement n’est pas connue de l’attaquant on parle alors de cryptanalyse oucryptoanalyse ⁹. La cryptologie est la science qui étudie les aspes scientifiques de ces techniques etelle englobe la cryptographie et la cryptanalyse.

Le but d’un système cryptographique (aussi appelé cryptosystème) est de chiffrer un message intel-ligible en un texte chiffré incompréhensible et de déchiffrer le cryptogramme et obtenir le texte clair.Cependant, un espion ne doit pas être en mesure de décrypter (ou cryptanalyser) le texte chiffré.

Il existe plusieurs types de cryptosystèmes. Le classement suivant nous servira tout au long de notreétude.

. Il ne faut donc pas confondre déchiffrement (opération effeuée par le destinataire légitime) et décryptement(opération que l’espion tente d’effeuer).

. On entend souvent aussi le terme plus familier de cassage



. Les cryptosystèmes à usage restreint.. Les cryptosystèmes à usage général.

(a) A clé secrète (aussi appelés symétriques).(b) A clé publique (aussi appelés asymétriques).(c) Par échange quantique.

Un système cryptographique est dit à usage restreint si sa sécurité repose sur la confidentialité desopérations de chiffrement et de déchiffrement. Le plus simple des systèmes historiques de ce genreest le procédé dit de Jules César.

Il consiste simplement à remplacer chaque lettre du texte clair par celle qui la suit trois lettres plusloin dans l’alphabet (en revenant au début si nécessaire, c’est-à-dire que x, y et z sont chiffrés para, b et c, respeivement). Ainsi, le mot bonjour devient erqmrxu. Les systèmes à usage restreintsont souvent conçus par des amateurs et sont presque toujours un jeu d’enfant pour les cryptana-lystes professionnels. Encore plus important, ces systèmes ne sont d’aucune valeur dans le contextecontemporain de communications entre un grand nombre d’utilisateurs.

Un système cryptographique est dit à usage général si sa sécurité ne repose pas sur le secret desopérations de chiffrement et de déchiffrement mais plutôt sur une information appelée la clé, la-quelle est souvent relativement courte. Les individus qui utilisent de tels systèmes doivent pouvoirfacilement générer leurs propres clés sans avoir recours au concepteur du système de telle sorte quecelui-ci ne jouisse d’aucun avantage particulier s’il décide de passer au camp des cryptanalystes.

F . – Taxonomie des cryptosystèmes.

.. Confusion et diffusion

En cryptologie, confusion et diffusion sont deux propriétés dans une méthode de chiffrement quiont été identifiées par C S dans son document « Communication eory of Secrecy



Systems » publié en ¹⁰.

D’après la définition originale de S, la confusion correspond à une volonté de rendre la re-lation entre la clé de chiffrement et le texte chiffré la plus complexe possible. Les struures algébriqueset statistiques doivent être cachées.

La diffusion est une propriété où la redondance statistique dans un texte en clair est dissipée dansles statistiques du texte chiffré. En d’autres termes, un biais en entrée ne doit pas se retrouver ensortie et les statistiques de la sortie doivent donner le moins possible d’informations sur l’entrée.Des relations entre les bits en entrée et en sortie pourraient être utiles pour le cryptanalyste. Ceconcept est lié à la notion plus moderne d’effet avalanche. Dans un chiffrement avec une bonnediffusion, l’inversion d’un seul bit en entrée doit changer chaque bit en sortie avec une probabilitéde . (critère d’avalanche stri voir ...).

Pour introduire la confusion, la substitution (remplacer un symbole du texte clair par un autre) futune première approche. Pour les chiffrements modernes, des boîtes S (S-Box) sont utilisée à cet effet .Pour la diffusion, elle est augmenté par la permutation/transposition. Les chiffrements utilisent pourcela des boîtes T (T-Box). D’autres mécanismes peuvent être déployés, comme des transformationslinéaires (par exemple dans Rijndael).

On appelle chiffrement produit un chiffrement par blocs qui combine plusieurs transformationsélémentaires (substitutions, transpositions, opérations linéaires ou arithmétiques) pour garantir à lafois la diffusion et la confusion.

.. Chiffrement

Bob, doit transmettre à Alice, un message M P Messages-a-Envoyer. M est dit « en clair ». Estelle,une espionne, écoute la voie de communication pour connaître M . Bob, construit un texte chiffréC P Messages-Chiffrés. C = Ek(M) ou C = Mk

E .

La fonion Ek dépend d’un paramètre k appelé clé de chiffrement. Le chiffrement est donc unetransformation d’un texte pour en cacher le sens. La possibilité de chiffrer repose donc sur la connais-sance de l’algorithme de chiffrement E et de la clé k de chiffrement.

F . – Chiffrement en présence d’espion.

.. Déchiffrement

Le déchiffrement est l’opération inverse permettant de récupérer le texte en clair à partir du texteC chiffré. Il repose sur la fonion DK de Messages-Chiffrés dans Messages-à-Envoyer telle que M =DK(C) ou C = MK

D

On doit avoir DK(Ek(M)) = M . DK est donc une fonion inverse à gauche de Ek.

. « Communication theory of secrecy systems », Bell System Technical Journal, vol. , n., p. -,



Pour un couple cr = (E,D) donné de famille de fonion de chiffrement et de déchiffrement,l’ensemble des couples (k,K) vérifiant cette propriété est noté CLE(cr).

.. Cryptosystème

Pour que les opérations précédentes assurent la confidentialité du transfert entre Alice et Bob, ilest nécessaire qu’au moins une partie des informations E,D, k,K soit ignorée du reste du monde.Décrypter ou casser un code c’est parvenir au texte en clair sans posséder au départ ces informationssecrètes. C’est l’opération que doit réaliser Estelle pour retrouver M .

L’art de définir des codes est la cryptographie.Un spécialiste en cryptographie est appelé cryptographe.L’art de casser des codes est appelé cryptanalyse. Un spécialiste en cryptanalyse est appelé cryp-tanalyste.Un cryptosystème est l’ensemble des deux méthodes de chiffrement et de déchiffrement ainsique les clés, les textes en clair et les textes chiffrés possibles.

Un système de chiffrement est dit inconditionnellement sûr si un attaquant est incapable dele casser même en disposant d’une capacité infinie de calcul.

On ne peut pas faire mieux en terme de sécurité !. Claude Shanon a prouvé l’existence de telsystème. A savoir le masque jetable utilisant un générateur de nombres aléatoires pour la clé estinconditionnellement sûr.

Un système de chiffrement est dit à sécurité prouvée si on peut démontrer que sa sécurité estéquivalente à la résolution d’un problème réputé difficile.

Il s’agit par exemple de démontrer la relation suivante : un système donné est sûr si un entierdonnée n ne peut être faorisé.

Ce modèle est très employé en cryptographie asymétrique.

Un système de chiffrement est dit sûr au sens de la théorie de la complexité si le meilleuralgorithme pour le casser nécessite n opérations avec n un nombre suffisamment grand pourque l’algorithme ne puisse être exécuté.

Il n’existe aucun algorithme de chiffrement satisfaisant le critère de sécurité dans le modèle calcula-toire. Ce modèle est pourtant le plus employé en cryptographie symétrique. En pratique, on déclareun système de chiffrement sûr s’il résiste à l’état de l’art de la cryptanalyse (recherche exhaustive,cryptanalyse linéaire …).

Un système de chiffrement assure une confidentialité parfaite si Pr[x|y] = Pr[x] pour toutx P Messages-à-Envoyer et y P Messages-Chiffrés, c’est à dire si la probabilité a postériori quele texte clair soit x étant donné le texte chiffré y, est identique à la probabilité à priori que letexte soit x.

Le chiffrement par décalage est un système de chiffrement à confidentialité parfaite.

Si (Messages-à-Envoyer, Message-Chiifrés, K) caraérise un système de chiffrement tel que|Messages-à-Envoyer| = |Messages-Chiffrés| = |K|, alors ce système assure une sécurité parfaitesi et seulement si chaque clé est utilisée avec la même probabilité 1

|K|et pour chaque x P

Messages-à-Envoyer et y P Messages-à-Envoyer, il existe une clé k unique tel que Ek(x) = y.



Le surchiffrement est un procédé cryptographique qui consiste à chiffrer, avec d’autres algo-rithmes et des clés différentes, des données qui avaient déjà été chiffrées. On peut le faire autantde fois que nécessaire mais cela implique nécessairement des performances amoindries.

Cette méthode permet normalement de s’assurer qu’en cas de vulnérabilité d’un des systèmes uti-lisés, les autres pourront prendre le relais et assurer encore une forte proteion. Il permet aussi decacher certaines propriétés statistiques dans les cas où des chiffrements faibles seraient utilisés.

.. Classes d’attaques sur les primitives cryptographiques

Il y a niveaux d’attaques dont on peut faire l’hypothèse qu’un adversaire peut effeuer. Onappelle attaque une tentative de cryptanalyse.

Un des axiomes fondamentaux de la cryptographie, énoncé pour la première fois par AugusteKerckhoffs au XIXe siècle, est que l’ennemi possède tous les détails de l’algorithme et qu’il ne luimanque que la clé spécifique pour le chiffrement.

La plupart de ces attaques ne s’appliquent pas seulement aux cryptosystèmes, mais également auxsystèmes de signature numérique et des codes d’authentification de messages MACs pour forger desmessages ou des signatures.

... L’attaque à texte chiffré seul (ciphertext-only attack)

Le cryptanalyste dispose du texte chiffré de plusieurs messages, tous ayant été chiffrés avec le mêmealgorithme. La tâche du cryptanalyste est de retrouver le plus grand nombre de messages clairs pos-sibles, ou mieux encore de retrouver la ou les clés qui ont été utilisées, ce qui permettrait de déchiffrerd’autres messages chiffrés avec ces mêmes clés.

Tout système cryptographique vulnérables à ce type d’attaque est considéré comme complètementnon sûr.

... L’attaque à texte clair connu (known-plaintext attack)

Le cryptanalyste a non seulement accès aux textes chiffrés de plusieurs messages, mais aussi auxtextes clairs correspondants. La tâche est de retrouver la ou les clés qui ont été utilisées pour chiffrerces messages ou un algorithme qui permet de déchiffrer d’autres messages chiffrés avec ces mêmesclés.

... L’attaque à texte clair choisi (chosen-plaintext attack)

Le cryptanalyste a non seulement accès aux textes chiffrés et aux textes clairs correspondants, maisde plus il peut choisir les textes en clair. Cette attaque est plus efficace que l’attaque à texte clairconnu, car le cryptanalyste peut choisir des textes en clair spécifiques qui donneront plus d’infor-mations sur la clé.

... L’attaque adaptative à texte clair choisi (adaptive chosen plaintext at-tack)

C’est une attaque à texte clair choisi dans laquelle le choix du texte clair suivant peut dépendre dutexte chiffré reçu des demandes antérieures.



... L’attaque à texte chiffré choisi (chosen ciphertext attack)

Le cryptanalyste peut choisir différents textes chiffrés à déchiffrer. Les textes déchiffrés lui sontalors fournis. Par exemple, le cryptanalyste a un dispositif qui ne peut être désassemblé et qui faitdu déchiffrement automatique. Sa tâche est de retrouver la clé.

... L’attaque adaptative à texte chiffré choisi (adaptive chosen ciphertextattack)

Une attaque à texte chiffré choisi où le choix du texte chiffré peut dépendre du texte clair reçu dedemandes antérieures.


Chapitre

Crptographie symétrique متماثل تشفير

Sommaire. Cryptosystèmes symétriques المتناظرة) التشفير (أنظمة . . . . . . . . . . . . . . . Chiffre par substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Chiffre de César . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Chiffre affine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

... Chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . ... Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . ... Cryptanalyse . . . . . . . . . . . . . . . . . . . . . . . . .

.. Chiffre de Vigenère . . . . . . . . . . . . . . . . . . . . . . . . . . . ... Chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . ... Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . ... Cryptanalyse . . . . . . . . . . . . . . . . . . . . . . . . .

.. Autres chiffres par substitution . . . . . . . . . . . . . . . . . . . . . . Chiffres par transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chiffre par bloc et chiffre de flux . . . . . . . . . . . . . . . . . . . . . . . . . Modes opératoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. ECB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. CBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. PCBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. CFB ou CFC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

... Forme simple . . . . . . . . . . . . . . . . . . . . . . . . . ... Version détaillée . . . . . . . . . . . . . . . . . . . . . . .

.. OFB ou OFC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. CTR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. CTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Padding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fonionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Dérivation des sous-clés . . . . . . . . . . . . . . . . . . . . . . . . . .. Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Clés faibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Attaques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

C : Crptographie symétrique متماثل تشفير

. Triple Data Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . Advanced Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . .

.. Le vainqueur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fonionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Attaques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Password-based cryptography . . . . . . . . . . . . . . . . . . . . . . . . . .

F . – La machine de Lorenz utilisée par les Allemands durant la Seconde Guerre mondiale..

. Cryptosystèmes symétriques المتناظرة) التشفير (أنظمة

La cryptographie symétrique متماثل) أو متناظر ,(تشفير également dite à clé secrète (بالمفتاحpar)السري) opposition à la cryptographie à clé publique العام) بالمفتاح ,((تشفير est la plus an-

cienne forme de chiffrement. Des traces de son utilisation par les égyptiens remonte à av.

J.-C. Le chiffre de Jules César est plus récent où le « ROT »¹ est une variante.

Plus formellement :

Tels que soit k = K, soit la connaissance d’une des deux clés permet d’en déduire facilementl’autre.

Conséquences :— Dichotomie du monde : les bons et les mauvais— Multiplication des clés (un secret n’est partagé que par 2 interlocuteurs), donc pourNinterlo-

cuteurs N.(N ´ 1)/2 couples— La qualité d’un cryptosystème symétrique s’analyse par rapport à des propriétés statistiques des

textes chiffrés et la résistance aux classes d’attaques connues.— En pratique tant qu’un cryptosystème symétrique n’a pas été cassé, il est bon, après il devient

mauvais.

. Une variante du chiffre de César avec un décalage de positions au lieu de .


. Chiffre par substitution

F . – Cryptographie symétrique (à clé secrète).


Principe général : A chaque lettre ou groupe de lettres on substitue une autre lettre ou un autregroupe de lettres.

Substitution mono alphabétique : Pour chaque lettre de l’alphabet de base on se donne une autrelettre utilisée dans le texte chiffré.

.. Chiffre de César

C’est un exemple historique où on décale les lettres de positions. C’est un chiffremono-alphabétique.

F . – Jules cesar ou juillet av. J.-C. ou av. J.-C. - mars av. J.-C.

Indice Clair A B C D E F G H I J K L M N O P Q R S T U V W X Y Zhiffré D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

La forme générale des chiffres par décalage sur l’alphabet à lettres (Pour le chiffre de Césark = 3 :

Ek(x) = x+ k mod 26

Dk(y) = y ´ k mod 26

Exemple :



Nous voulons chiffrer le texte « INFORMATIQUE ». Nous pouvons nous servir du tableau suivantafin d’obtenir le texte chiffré qui est dans ce cas « LQIRUPDWLTXH » :

Texte clair I N F O R M A T I Q U EIndice clair Indice chiffré (Indice clair + 3) mod 26Texte chiffré L Q I R U P D W L T X H

.. Chiffre affine

Le chiffre affine est une généralisation par rapport à celui de César.

... Chiffrement

Au lieu de prendre une clé fixe k = 3, il est possible d’utiliser la formule : Ek(x) = (ax +b) mod 26 où clé= (a, b), a P Z26 et b P Z26.

Si le coefficient a vaut , alors le codage affine correspond au chiffre par décalage.

Exemple : prenons a = 3 et b = 5. Nous avons pour le chiffrement la formule :

Ek(x) = (3x+ 5) mod 26

Le texte clair « INFORMATIQUE » aura le texte chiffré correspondant « DSUVEPFKDBNR »comme le montre le tableau suivant :

Texte clair I N F O R M A T I Q U EIndice clair Indice chiffré (3 ˆ (Indice clair) + 5) mod 26

Texte chiffré D S U V E P F K D B N R

... Déchiffrement

La fonion de déchiffrement est : Dk(y) = (a´1y ´ ba´1) mod 26, tel que aa´1 = 1 mod 26.D’après le théorème de Bachet-Bézout (voir ..), a´1 existe si a est premier avec . Dans notrecas a´1 = 9 dans Z26, ce qui donne Dk(y) = (9y ´ 45) mod 26 = (9y + 7) mod 26.

Essayons de vérifier que le déchiffrement de « DSUVEPFKDBNR » avec la clé (,) donne bien« INFORMATIQUE » comme le montre le tableau suivant :

Texte chiffré D S U V E P F K D B N RIndice chiffré Indice clair ( ˆ(Indice chiffré) + 7) mod 26

Texte chiffré I N F O R M A T I Q U E

... Cryptanalyse

Il n’existe que entiers compris entre et et premiers avec (, , , , , , , , , , et ). Il n’existe donc que 12ˆ26 = 312 clés de chiffrement possible et non 26ˆ26 = 262 = 676.Si l’on sait qu’un code affine a été utilisé, on peut le casser par force brute en essayant les clés(recherche exhaustive).



Si le cryptogramme est suffisament long, on peut tenter d’identifier les lettres selon leur fréquenced’apparition dans les messages. En effet une lettre est, par cette méthode, toujours remplacée par lamême lettre. La lettre E, par exemple, étant en français très fréquente, si, dans le message chiffré,la lettre T est très fréquente, on peut supposer que E est remplacé par T et ne rechercher que lescodages affines permettant cette substitution. Pour plus de détails, voir ??.

.. Chiffre de Vigenère

Le chiffre de Vigenère est un système de chiffrement, élaboré par Blaise de Vigenère (-),diplomate français du XVIe siècle. C’est un système de substitution ou de chiffrement polyalpha-bétique. Cela signifie qu’il permet de remplacer une lettre par une autre qui n’est pas toujours lamême.

Contrairement au chiffre de César ou à ROT qui se contentaient d’utiliser la même lettre desubstitution. C’est donc une méthode relativement plus « solide » que les deux autres. Il résiste ainsià l’analyse de fréquences, ce qui est un avantage décisif sur les chiffrements monoalphabétiques. Il aété cassé par le major prussien Friedrich Kasiski en et n’offre plus depuis cette époque aucunesécurité.

... Chiffrement

Pour ce chiffre, une clé se présente généralement sous la forme d’un mot ou d’une phrase. Si la cléest plus courte que le message clair, elle sera dupliquée autant de fois que nécessaire pour avoir lalongueur du texte clair².

Exemple :

Nous voulons chiffrer le texte clair « texte secret » à l’aide de la clé « clef ». On peut utiliser laformule ECL(xn) = (xn + CL(n mod 4)) mod 26 où n est le rang de la lettre x du message clairà chiffrer. CL est une fonion qui donne l’indice de la lettre de la clé correspondante à xn. Nousavons utilisé (mod 4) dans la formule de CL parce que la taille de la clé = 4. Le tableau . illustrele processus de chiffrement.

De la même manière il est possible de se baser sur la fameuse table de Vigenère .. Les colonnesreprésentent le texte clair et les lignes le texte chiffré. Pour chiffrer par exemple la lettre claire « t »avec la lettre clé « f » on obtient la lettre chiffrée « y » qui est la cellule obtenue par l’interseion dela colonne « t » et la ligne « f ».

.

. c l e fCL

... Déchiffrement

On peut utiliser la formule DCL(yn) = xn = (yn ´ CL(n mod 4)) mod 26. Le processus dedéchiffrement est illustré par le tableau ..

Si nous voulons se baser sur la table de vigenère, alors pour chaque lettre chiffrée y on cherche lalettre de la clé qui lui correspond. On fixe la ligne de la lettre de la clé et on cherche dans celle-ci lalettre chiffré. On remonte dans la colonne pour trouver la lettre claire correspondante. Par exemple,

. plus la clé sera longue et variée et mieux le texte sera chiffré.



Texte clair t e x t e s e c r e tindice clair indice clé indice chiffré ECL(xn) = (xn + CL(n mod 4)) mod 26

Texte chiffre v p b y g d i h t p x

T . – Chiffrement de Vigenère de « texte secret » avec la clé « clef ».

F . – Table de Vigenere.

Texte chiffré v p b y g d i h t p xindice chiffré indice clé indice clair DCL(yn) = (yn ´ CL(n mod 4)) mod 26

Texte clair t e x t e s e c r e t

T . – Déchiffrement de Vigenère de « vpbygdihtpx » avec la clé « clef ».



si on veut déchiffrer « g », la lettre de la clé qui lui correspond est « c ». On cherche dans la ligne « c »la lettre « g » et la colonne correspondante indique « e » qui est la lettre claire recherchée.

... Cryptanalyse

Si l’on connait le nombre de symboles que comporte la clé, il devient possible de procéder paranalyse de fréquences sur chacun des sous-textes déterminés en séleionnant des lettres du messageclair à intervalle la longueur de la clef (autant de sous-textes que la longueur de la clef ). C’est l’attaquebien connue sur les chiffrements monoalphabétiques.

Friedrich Wilhelm Kasiski a proposé en une méthode efficace pour déterminer la taille de laclef (test de Kasiski) en repérant la répétition de certains motifs dans le message chiffré.

Première : Détermination de la longueur de la clé Elle consiste à chercher des répétitions dansle texte chiffré. Considérons par exemple le mot-clé « ABCD » qui sert à chiffrer « MESSAGERTRES MESQUIN MESOPOTAMIEN ».

Clé répétée A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B CTexte en clair M E S S A G E R T R E S M E S Q U I N M E S O P O T A M I E NTexte chiffré M F U V A H G U T S G V M F U T U J P P E T Q S O U C P I F P

T . – i

Dans l’exemple ci-dessus, le trigramme « MES » est chiffré en « MFU » deux fois et « PET » unefois. Babbage et Kasiski comprirent que des répétitions de cette sorte leur offraient la prise dont ilsavaient besoin pour attaquer Vigenère.

. soit la même séquence de lettres du texte clair a été chiffrée avec la même partie de la clef.. soit deux suites de lettres différentes dans le texte clair auraient (possibilité faible) par pure

coïncidence engendré la même suite dans le texte chiffré.

Le premier cas étant le plus probable, on calcule le nombre de lettres entre deux séquences iden-tiques. Dans notre cas, il y a lettres entre les deux « MFU », on en déduit que la longueur dela clé est un diviseur de (sinon la clé et les deux « MES » ne seraient pas alignés). La clé peutdonc posséder soit , , , ou lettres (avec une lettre, nous aurions un chiffrement monoal-phabétique facilement cassé avec une analyse fréquentielle). Avec un texte plus long, on découvriraitd’autres séquences qui permettraient d’affiner le résultat et réduire la taille de la clé à une ou deuxpossibilités.

.. Autres chiffres par substitution

— Les substitutions homophoniques :au lieu d’associer un seul caraère chiffré à un caraèreclair, on dispose d’un ensemble de possibilités de substitution de caraères dans laquelle onchoisit aléatoirement.

— Les substitutions de polygrammes : au lieu de substituer des caraères on substitue par exempledes digrammes (groupes de deux caraères)— Au moyen d’une table (système de Playfair)— Au moyen d’une transformation mathématique (système de Hill).

— Le masque pseudo aléatoire :Principe du masque jetable³ mais en utilisant un masque pseudoaléatoire (le grain est la clé).

. Appelé aussi chiffre de Vernam.



F . – Substitution homophonique Henri IV .

. Chiffres par transposition

Un chiffrement par transposition (ou chiffrement par permutation) est un chiffre qui consiste àchanger l’ordre des lettres, donc à construire des anagrammes. Cette méthode est connue depuisl’Antiquité, puisque les Spartiates utilisaient déjà une scytale.

.. Principe général

On procède à un réarrangement de l’ensemble des caraères (une transposition) qui cache le sensinitial. La technique est très peu résistante aux attaques statistiques. Le plus souvent on utilise deuxvisions géométriquement différentes du texte.

F . – Scytale.

Le chiffrement par transposition demande de découper le texte clair en blocs de taille identique ; lamême permutation est alors utilisée sur chacun des blocs. Le texte doit éventuellement être complété(procédé de bourrage) pour permettre ce découpage. La clé de chiffrement est la permutation elle-même.

Le nombre de permutations possibles d’une longueur donnée, qui est la faorielle de cette lon-gueur, augmente donc rapidement avec celle-ci. Par exemple un mot de trois lettres ne peut êtrepermuté que dans 6(= 3!) positions différentes. Ainsi « col » ne peut se transformer qu’en « col »,« clo », « ocl », « olc », « lco » ou « loc ».

Lorsque le nombre de lettres croît, le nombre d’arrangements augmente rapidement et il devientplus difficile de retrouver le texte original sans connaître la permutation, et sans aucune connaissancesur le texte clair. Ainsi pour un chiffre par transposition qui utilise des blocs de 20 caraères, il y a20! possibilités, soit combinaisons.

Exemple de transposition matricielle : Le message en clair est écrit dans une matrice. La clé unepermutation de [1..n] ou n est le nombre de colonne. La technique de transposition consiste à lire


. Chiffre par bloc et chiffre de flux

la matrice en colonne selon un ordre donné par la clé.

Le message clair : MESSAGE SECRET A CHIFFRER PAR TRANSPOSITION.

M E S S A GE S E C R ET A C H I FF R E R P AR T R A N SP O S I T IO N

Le message crypté est donc : METFRPO ARIPNT SCHRAI SECERS GEFASI ESARTON.

. Chiffre par bloc et chiffre de flux

Le chiffrement par bloc كتل) (تشفير (en anglais block cipher) est une des deux grandes catégo-ries de chiffrements modernes en cryptographie symétrique, l’autre étant le chiffrement par flot. Laprincipale différence vient du découpage des données en blocs de taille généralement fixe pour leschiffres par bloc. La taille de bloc est comprise entre 32 et 512 bits, dans le milieu des années 1990 lestandard était de 64 bits mais depuis 2000 et le concours AES le standard est de 128 bits. Les blocssont ensuite chiffrés les uns après les autres.

Un chiffrement itératif résulte de l’application itérée d’un chiffrement (en général un chiffrementproduit).

Chaque itération est appelée un tour (round en anglais). Chaque tour fait intervenir une sous-cléqui en général est dérivée (on dit souvent cadencée) de la clé principale.

Dans les systèmes auels, le chiffrement est obtenu en itérant une fonion de tour qui est cryptographi-quement faible dans le sens où elle ne constitue pas à elle seule un système suffisamment robuste.Chaque itération est appelée un tour ou encore une ronde. Chaque tour prend en entrée la sortiedu tour précédent (ou le bloc de texte clair dans le cas du premier tour) et chiffre cette entrée grâceà la fonion de tour et à la clé de tour construite avec la clé K. Le nombre de tours sera noté Nr. SiM est le texte clair on calcule successivement :

M0 = M ,

M1 = F (m0, K1),

…

MNr = F (MNr´1, KNr),

c = MNr.

Tel que F : t0, 1utd ˆ t0, 1utr Ñ t0, 1utd

où td est la taille du message clair et tr celle de la clé.

Le calcul est parfois augmenté d’une phase de prétraitement (avant de commencer les itérations)et d’une phase de post-traitement (après la dernière itération).

La clé de tour est obtenue à partir de la clé secrète. Ainsi pour mener à bien le calcul itératif quenous venons de décrire, on doit donc associer à la clé secrète K, de taille tk, Nr sous-clés (ou clésde tour) de taille tr.



Le procédé qui permet de calculer ces sous-clés est appelé schéma de diversification de la clé ouschéma de production des sous-clés.

Le chiffrement de flux ou chiffrement par flot تدفقي) (تشفير (En anglais stream cipher) peut traiterdes données de longueur quelconque et n’a pas besoin de les découper. Il est largement utilisé dansdes systèmes et des applications temps-réel (transmission video/audio par exemple). Il est de pratiquecourante d’utiliser des « générateurs pseudo-aléatoires » comme base pour engendrer la clé privée.Plus précisément, le générateur pseudo-aléatoire est utilisé pour fournir un flux de bits additionnés(XOR) avec les bits correspondants du texte clair pour produire des bits du texte chiffré. Autrementdit, la séquence pseudo-aléatoire générée (déterminée par une clé partagée à priori) est utilisée comme« masque jetable »⁴ au lieu d’une séquence véritablement aléatoire, avec l’avantage que la séquencegénérée peut être beaucoup plus longue que la clé (ce qui n’est pas possible pour une séquencepurement aléatoire).

La figure . illustre le fonionnement d’un chiffre par flux. Les bits mi du texte clair sont addi-tionnés (modulo ) avec les bits si du flux de la clé pour obtenir les bits ci du texte chiffré. Le fluxsi est obtenu d’un générateur de nombres pseudo-aléatoires avec comme germe la clé privé partagéek. Il est qualifié de synchrone si le flux de bits si ne dépend que de la clé k et asynchrone s’il dépendaussi du texte chiffré précédent.

Une liste non-exhaustive de chiffrements par flot :

. A/, algorithme publié en , utilisé dans les téléphones mobiles de type GSM pour chiffrerla communication par radio entre le mobile et l’antenne-relais la plus proche,

. RC, le plus répandu, conçu en par Ronald Rivest, utilisé notamment par le protocoleWEP du WiFi.

. Py, un algorithme récent d’Eli Biham.. E0 utilisé par le protocole Bluetooth.

F . – Chiffre par flux synchrone et asynchrone.

Toutefois, le XOR n’est pas la seule opération possible. L’opération d’addition dans un groupe estégalement envisageable (par exemple, addition entre deux oets, modulo 256). Un chiffrement parbloc peut être converti en un chiffrement par flot grâce à un mode opératoire qui permet de chaînerplusieurs blocs et traiter des données de taille quelconque.

Soit ‘ l’opération booléenne XOR :

. Chiffrement du message M avec la clé K : M ‘ K = C

. Déchiffrement du message C avec la clé K : C‘K = (M ‘K)‘K = M ‘ (K‘K) = M

. One-time pad.


. Modes opératoires

Le projet eStream⁵ du réseau ECRYPT⁶ a vu le jour en ayant pour but, après quatre ans, deproduire un portfolio pour promouvoir de nouveaux systèmes de chiffrement par flot. Auellement,il recommande au total sept⁷ algorithmes dans deux catégories différentes hardware et software (parordre alphabétique) :

Software Hardware-bit key -bit keyHC- Grain vRabbit MICKEY v

Salsa/ TriviumSosemanuk -

T . – Portfolio d’eStream .


Un chiffrement par bloc fournit simplement une méthode de chiffrement d’une seule chaîne de nbits, et non pas un « MESSAGE » de longueur arbitraire. Par ailleurs, même quand il est seulementnécessaire de chiffrer une chaîne de n bits, un mode de fonionnement devrait être employé pouréviter les attaques cryptanalytiques résultant de la répétition de fragments de « texte clair ».

Il est possible de transformer un chiffrement par bloc en un chiffrement par flot en utilisant unmode d’opération :

.. ECB

(Eleronic CodeBook) où chaque bloc chiffré (déchiffré) indépendamment des autres, voir lesfigures . et .. Vulnérable aux attaques texte-clair/texte-chiffré même en ignorant totalement laclé. Le texte clair M est découpé en blocs mi où chacun est chiffré séparément des autres donnantlieu à un bloc chiffré ci. Ensuite, les blocs chiffrés sont concaténés pour former le message chiffré C.

Pour le chiffrement ci = Ek(mi) et le déchiffrement mi = Dk(ci).

Il faut noter q’utilisant la même clé, deux blocs de texte en clair identiques donnent deux blocschiffrés également identiques et vice versa.

Les avantages de ce mode sont les suivants :

. Le travail de chiffrement ou de déchiffrement peut être parallélisé. Plusieurs machines ou CPUpeuvent travailler simultanément sur des parties différentes du message.

. Il permet un accès aléatoire dans le texte chiffré.. Une erreur de transmission d’un bit affee uniquement le décodage du bloc courant (pas de

propagation d’erreurs).

Par contre, ce mode a les désavantages suivants :

. http://www.ecrypt.eu.org/stream/index.html. http://www.ecrypt.eu.org/. L’algorithme F-FCSR-H v proposé en sous le profile Hardware a été éliminé suite à la publication des

résultats d’attaques cryptanalytiques.


http://www.ecrypt.eu.org/stream/index.html

http://www.ecrypt.eu.org/


F . – Chiffrement en mode ECB.

F . – Déchiffrement en mode ECB.

. Les répétitions du texte en clair ne sont pas masquées et se retrouvent sous la forme de répéti-tions de textes chiffrés.

. Des portions complètes du message peuvent être modifiées, répétées ou remplacées sans diffi-culté (qttaque reply).

. La perte de synchronisation (perte ou ajout d’un bit) est irrécupérable.

.. CBC

(Cipher Block Chaining) inventé par IBM en où on chaîne le chiffrement (déchiffrement).On effeue un XOR entre le bloc en clair auel et le bloc chiffré précédent avant d’être chiffré. Lepremier bloc est additionné (XOR) avec un Veeur Initial. Voir les figures . et ..

Vulnérable aux erreurs (modification d’un bloc) en plus il faut déchiffrer tout un grand fichierpour consulter une petite partie. Les algorithmes de chiffrement et de déchiffrement sont commesuit :

ci = EK(mi ‘ ci´1), c0 = EK(m0 ‘ IV ) et mi = DK(ci) ‘ ci´1, m0 = DK(c0) ‘ IV .

F . – Chiffrement en mode CBC.




F . – Déchiffrement en mode CBC.

. Les répétitions de texte en clair sont masquées dans le texte chiffré.. La valeur du veeur d’initialisation IV n’a pas besoin d’être secrète.. Accès aléatoire aux texte chiffré.. Parallélisation possible du déchiffrement.

Par contre, ce mode a les désavantages suivants :. Deux textes en clair commençant pareil auront le même début de texte chiffré.. Une erreur de transmission d’un bit affee uniquement le décodage du bloc courant ainsi que

le décodage du même bit dans le bloc suivant (propagation limitée).. La perte de synchronisation (perte ou ajout d’un bit) est irrécupérable.

.. PCBC

Propagating cipher-block chaining ou plaintext cipher-block chaining. Il a été conçu pour produirede petits changements dans le texte chiffré à propager indéÃ«niment lors du déchiffrement, ainsi quelors du chiffrement.

Voir les figures . et .. Les algorithmes de chiffrement et de déchiffrement sont comme suit :

ci = EK(mi ‘ mi´1 ‘ ci´1), c0 = EK(IV ‘ m0) et mi = DK(ci) ‘ mi´1 ‘ ci´1, m0 =IV ‘ DK(c0)

F . – Chiffrement en mode PCBC.

.. CFB ou CFC

Cipher Feedback Chaining ou chiffrement à rétroaion. Ce mode et les suivants agissent commeun chiffrement par flux. Ils génèrent un flux de clés qui est ensuite appliqué au document original.Dans ce mode, le flux de clé est obtenu en chiffrant le précédent bloc chiffré. CFB est un chiffrement



F . – Déchiffrement en mode PCBC.

par flot. Son grand intérêt est qu’il ne nécessite que la fonion de chiffrement, ce qui le rend moinscher à câbler ou programmer pour les algorithmes ayant une fonion de chiffrement différente dela fonion de déchiffrement (exemple : AES).

... Forme simple

Voir les figures . et ..

F . – Chiffrement en mode CFB.

F . – Déchiffrement en mode CFB.

De manièe simple les algorithmes de chiffrement et de déchiffrement sont comme suit :

ci = EK(ci´1) ‘ mi, mi = EK(ci´1) ‘ ci et c0 = IV .

Les avantages de ce mode sont :

. Accès aléatoire au texte chiffré.. Parallélisation du déchiffrement.. Propagation limitée d’erreurs.. IV n’est pas secret.



... Version détaillée

Le mode nécessite deux paramètres k : (1 ď k ď n), la taille de la variable de rétroaion(feedback) et j : (1 ď j ď k) le nombre de bits de texte clair à chiffrer pour chaque étape.

En pratique, il semblerait judicieux de toujours choisir j = k. En fait, ce qui est recommandé parla deuxième édition de la norme ISO/IEC et tout autre choix semble réduire le niveau globalde sécurité du schéma.

De manièe détaillée, le texte clair est découpé en blocs mi de taille j où 1 ď s ď td. En plus dutexte clair M = m1m2...mk, on a besoin d’un bloc initial de taille td tiré aléatoirement IV . Oncalcule alors successivement :

Z1 = EK(IV ), c1 = m1 ‘ MSBs(Z1),

I2 = LSBtd´s(IV )||c1,

Z2 = EK(I2), c2 = m2 ‘ MSBs(Z2),

…

Ik = LSBtd´s(Ik1)||ck1,

Zk = EK(Ik), ck = mk ‘ MSBs(Zk).

Tel que B1||B2 représente le bloc formé par la concaténation (la juxtaposition) des deux blocsB1et B2. MSBu(B) représente le bloc constitué par les u bits de B les plus à gauche (les u bits lesplus significatifs).

Tel queuest un entier tel que 0 ď u ď n et n est la taille de B en bits. LSBu(B) représente lebloc des u bits de B les plus à droite (les u bits les moins significatifs).

Le déchiffrement s’effeue en calculant successivement :

Z1 = EK(I1), m1 = c1 ‘ MSBs(Z1)

I2 = LSBtd´s(I1)||c1

Z2 = EK(I2), m2 = c2 ‘ MSBs(Z2)

…

Ik = LSBtd´s(Ik1)||ck1

Zk = EK(Ik), Pk = ck ‘ MSBs(Zk)

Il est tout à fait possible de réaliser ce schéma utilisant un registre à décalage.


. Il est possible de chiffrer un flot de valeurs plus petites que la taille standard du bloc géré parl’algorithme.

. Les répétitions de texte en clair sont masquées dans le texte chiffré.. La valeur du veeur d’initialisation IV n’a pas besoin d’être secrète.

. La perte de synchronisation (perte ou ajout d’un bit) est récupérable.


. Une erreur de transmission d’un bit affee uniquement le décodage du bloc courant ainsi quele déco-dage du même bit dans le bloc suivant.



F . – Chiffrement en mode CFB en générale.

F . – Déchiffrement en mode CFB en générale.



.. OFB ou OFC

Output Feedback Chaining ou chiffrement à rétroaion de sortie. Dans ce mode, le flux de cléest obtenu en chiffrantle précédent flux de clé. C’est un mode de chiffrement de flot qui possède lesmêmes avantages que CFB. De plus, il est possible de le précalculer en chiffrant successivement leveeur d’initialisation. Il n’est donc sûr que si la fonion de chiffrement alliée à la clé forment unebonne suite pseudo-aléatoire. Voir les figures . et ..

A� partir d’un bloc initial O0 = IV tiré aléatoirement, on construit un masque jetable par itéra-tion. Les algorithmes de chiffrement et de déchiffrement sont comme suit :

ci = mi ‘ Oi, mi = ci ‘ Oi, Oi = EK(Oi´1) et O0 = IV

Le message chiffré est O0c1c2 . . . ck.

Le déchiffrement s’effeue en calculant les Oi successifs à partir de Z0 comme on l’a fait pour lechiffrement puis en écrivant mi = ci ‘ Oi.

F . – Chiffrement en mode OFB.

F . – Déchiffrement en mode OFB.


. Les répétitions de texte en clair sont masquées dans le texte chiffré.

. La valeur du veeur d’initialisation IV n’a pas besoin d’être secrète.

. Ce mode n’amplifie pas les erreurs. Une erreur de transmission d’un bit affee uniquement cebit lors du décodage.


. La perte de synchronisation (perte ou ajout d’un bit) est irrécupérable.



.. CTR

CounTeR ou Chiffrement basé sur un compteur et connu aussi sous le nom Integer CounterMode (ICM) et Segmented Integer Counter (SIC) mode. Dans ce mode, le flux de clé est obtenu enchiffrant les valeurs successives d’un compteur come illustré dans les figures . et .. Ce modecombine de nombreux avantages, car il permet le chiffrement par flot, est précalculable, permet unaccès aléatoire aux données, est parallélisable et n’utilise que la fonion de chif-frement. Le compteurutilisé peut être une suite pseudo-aléatoire qu’il sera facile de retrouver à partir de la graine (veeurd’initialisation).

F . – Chiffrement en mode CTR.

F . – Déchiffrement en mode CTR.

Pour le chiffrement, le texte clair M est découpé en blocs de taille td. Dans ce mode on disposed’un compteur de taille td. On tire au sort une valeur initiale CTR1 pour ce compteur. On calculealors :

Z1 = EK(CTR1), c1 = m1 ‘ Z1. Puis on incrémente le compteur.

En générale, on calcule successivement :

CTRi = CTRi ´ 1 + 1 mod 2td, Zi = EK(CTRi), ci = mi ‘ Zi.

Le texte chiffré transmis est constitué de la valeur CTR1 du compteur suivi des blocs c1c2 . . . ck.

Pour le déchiffrement, Il se fait en calculant succéssivement à partir de la valeur initiale du comp-teur :

Zi = EK(CTRi), mi = ci ‘ Zi, CTRi+1 = CTRi + 1 mod 2td,

Le mode CTR est un mode très simple à implémenter. Il est très sûr et n’utilise pas la fonionde déchiffrement du circuit. Le texte chiffré, qui doit contenir la valeur initiale du compteur, estun peu plus long que le texte clair. On peut dans ce mode faire des accès aléatoires de manière pluscommode que dans le mode OFB puisqu’il faut seulement chiffrer la valeur du compteur pour lebloc considéré. Ce mode est particulièrement intéressant.



.. CTS

CipherText Stealing ou chiffrement avec vol de texte. Dans ce mode, applicable à un chiffrementpar blocs (ECB, CBC, etc.), les deux derniers blocs sont partiellement combinés de façon à obtenirun message de même taille. Ici, un exemple de CTS opérant sur un chiffrement en mode CBC surla figure .. Le dernier bloc est complété d’abord par des zeros puis combiné (ou exclusif ) avec lebloc chiffré précédent avant d’être chiffré.

F . – CTS opérant sur un chiffrement en mode CBC.

Les deux derniers blocs sont échangés et combinés en partie, ce qui nécessitera de les obtenir tousles deux pour en décrypter un. CTS n’est pas un mode de chiffrement par flot, mais permet d’éviterl’utilisation de bourrage dans les chiffrements par blocs, et donne une taille de message crypté égaleà la taille du message clair. Il est très utilisé dans les protocoles ou formats ne supportant pas unetaille quelconque.

Une liste non-exhaustive de chiffrements par bloc :. DES, l’ancêtre conçu dans les années , a été passablement étudié. AES, le remplaçant de DES. Blowfish, Serpent et Twofish, des alternatives à AESIl y en a encore bien d’autres qui sont adaptés à des besoins particuliers. Certains consomment plus

de mémoire ou sont plus gourmands en puissance de calcul. Un chiffrement par bloc peut égalementêtre utilisé comme une fonion de hachage, c’est-à-dire une fonion à sens unique. Une variante deDES est employée pour le système de mots de passe dans Unix. Une chaîne contenant uniquementdes zéros est chiffrée avec une clé correspondant au mot de passe (une composante aléatoire appelée« sel » est encore intégrée à l’algorithme).

Ce chiffrement est itératif et se fait 25 fois avant d’obtenir le résultat final.

Lors d’ Asiacrypt’, Adi Shamir posa cette question. En réponse, le projet eStream du réseauECRYPT ⁸ vu le jour ; celui-ci ayant pour but après quatre ans de produire un portfolio pour pro-mouvoir de nouveaux systèmes de chiffrement à Ã¬ot. Suite à ces quatre ans de recherche, le portfolioest maintenant disponible et recommande au total huit algorithmes dans deux catégories différenteshardware et software (par ordre alphabétique) :

. http://www.ecrypt.eu.org/stream/index.html


http://www.ecrypt.eu.org/stream/index.html


Software HardwareHC- F-FCSR-H vRabbit Grain v

Salsa/ MICKEY vSosemanuk Trivium

T . – Le portfolio eStream d’ECRYPT.

. Padding

En plus, la plupart des modes d’opération nécessitent un texte en clair divisé en une série de blocsd’une longueur q fixe donnée. Le dernier bloc peut avoir une longeur inférieure à q. Ce phénomènenécessite un remplissage (bourrage) pour compléter le bloc et obtenir la taille exigée.

Pour résoudre ce problème, l’expéditeur et le destinataire doivent se mettre d’accord sur une mé-thode de remplissage. Une méthode de remplissage implique le rajout de bits au texte clair selon uneformule convenue.

Pour le chiffrement par bloc, le remplissage permet d’avoir un bloc de la taille adéquate si celui-ciest trop court. Pour le chiffrement par flot, il permet d’éviter d’avoir une longueur par flot susceptibled’être attaquée, cela évite aussi que l’attaquant ne connaisse la taille du flux.

En cryptographie asymétrique, les cryptosystèmes considèrent souvent le message en clair commeun très grand nombre qui est injeé dans une formule. Ces nombres ont souvent des propriétésqui doivent être respeées et le remplissage permet de garantir ces caraéristiques. La plupart desfonions de hachage découpent les données en blocs de taille fixe et le dernier bloc doit être remplide manière adéquate.

. Zero padding :Le remplissage est réalisé selon l’une des trois méthodes suivantes :(a) Padding method (ISO/IEC -) : Remplir par des bits à 0 jusqu’à l’obtention d’une

taille multiple de la taile d’un bloc ⁹(b) Padding method (ISO/IEC - et ISO/IEC -) :¹⁰ Commencer le remplissage

par un bit à 1 suivi de bits à 0 ce qui correspond aux valeurs d’oet (en hexadécimal)80 00 00 . . .. Ce rembourrage est la première étape d’un schéma de bourrage en deuxétapes utilisée dans de nombreuses fonions de hachage MD et SHA notamment. Dansce contexte, il est spécifié par RFC¹¹ étape ..

(c) Padding method (ISO/IEC -) : Les données de remplissage comprennent (dans cetordre) : La longueur des données du texte en clair (en bits) exprimé en big-endian binairesur n bits (un bloc), les données du texte clair, la chaine de remplissage constituée d’autantde bits à 0 que nécessaire (éventuellement une chaine nulle càd de taille 0) pour avoir unetaille du texte en clair (après remplissage) multiple de la taille exigée d’un bloc.

Si le texte clair initial est toujours de taille fixe, alors il n’est pas nécessaire de délimiter et les02 premières méthodes sont non ambigues.

. PKCS# :¹² Le standard PKCS définit des remplissages qui évitent des attaques potentiellesdans le cadre de la cryptographie asymétrique. pour PKCS#, la chaine de remplissage (Pad-

. Applicable sûrtout si la taille du texte clair est fixe.. Préférée par les utilisateurs de cartes à puces. http://www.faqs.org/rfcs/rfc.html. Utilisée par PKCS#, PKCS# et RFC Cryptographic Message Syntax (CMS) Seion . (anciennement

RFC qui a remplacé RFC et RFC ).


http://www.faqs.org/rfcs/rfc1321.html

. Data Encryption Standard

ding String) est une séquence d’oets identiques qui indique sa taille : PS = 01, si ||M || mod8 = 7 ; PS = 02 02, si ||M || mod 8 = 6 ; …, PS = 08 08 08 08 08 08 08 08, si|M || mod 8 = 0. Le remplissage est effeué même si le texte en clair original est d’une taillemultiple à celle d’un bloc.

. Merkle-Damgård : Dans le cadre des fonions de hachage, on peut appliquer un renforcementde Merkle-Damgård qui consiste à ajouter un bit à 1, une suite de bits à 0 et finalement la tailledu message à hacher¹³. Si l’on se contentait d’ajouter uniquement des 0, les messages « 000 »et « 0000 » produiraient le même condensé ce qui est totalement incompatible avec la notionde hachage cryptographique.

. ANSI X. : Les oets remplis de zéros (0) sont rajoutés et le dernier oet définit les limitesde remplissage ou le nombre d’oets rajoutés. Par exemple, la taille du bloc est de 8 oets, etle remplissage est nécessaire pour 4 oets (au format hexadécimal) :…|27 3F EE 41 9B D8 2D DD|AE B5 DD 3C |

. ISO : Les oets remplis de valeurs aléatoires sont rajoutés et le dernier oet définit leslimites de remplissage ou le nombre d’oets rajoutés. Par exemple, la taille du bloc est de 8oets, et le remplissage est nécessaire pour 4 oets (au format hexadécimal) :…|27 3F EE 41 9B D8 2D DD|AE B5 DD 3C E A |


Le Data Encryption Standard (DES) est un algorithme de chiffrement par bloc utilisant des clésde 56 bits. Son emploi n’est plus recommandé aujourd’hui, du fait de sa lenteur à l’exécution et deson espace de clés trop petit permettant une attaque systématique en un temps raisonnable.

Quand il est encore utilisé c’est généralement en Triple DES, ce qui ne fait rien pour améliorer sesperformances. DES a notamment été utilisé dans le système de mots de passe UNIX.

Le premier standard DES est publié par FIPS ¹⁴ le janvier sous le nom FIPS PUB . Ladernière version avant l’obsolescence date du oobre FIPS PUB -.

.. Histoire

En mai , le National Bureau of Standards américain demande la création d’un algorithme dechiffrement utilisable par les entreprises. à cette époque, IBM dispose déjà d’un algorithme appeléLucifer, conçu en par Horst Feistel.

En bonne logique, cet algorithme aurait dû être séleionné par le NBS. En pratique, ce fut presquele cas : la NSA demanda à ce que Lucifer soit modifié, par ses soins. Ainsi fut créé le DES, qui futadopté comme standard en novembre .

Cela suscita des rumeurs selon lesquelles la NSA aurait volontairement affaibli l’algorithme, dansle but de pouvoir le casser. étrangement, le DES s’est révélé résistant à plusieurs attaques ne devantapparaître dans la communauté académique que beaucoup plus tard. Encore plus étonnant, Lucifer,lui, résistait moins bien.

. Un entier codé sur bits pour MD et SHA-.. Federal Information Processing Standard : sont des standards publics développés et annoncés par le gouvernement

des états-Unis pour l’usage des agences gouvernementales non militaires et entrepreneurs gouvernementaux. Beaucoupde standards FIPS sont des versions modifiées des standards ANSI, IEEE, ISO, …etc.



Ceci permet de penser que la NSA avait connaissance dès cette époque de ces techniques de cryp-tanalyse et qu’elle aurait donc, en réalité, rendu DES moins faible.

F . – Data Encryption Standard.

.. Fonctionnement

L’algorithme DES transforme un bloc de bits en un autre bloc de bits. Il manipule des clésindividuelles de bits, représentées par bits (avec un bit de chaque oet servant pour le contrôlede parité). Ce système de chiffrement symétrique fait partie de la famille des chiffrements itératifspar blocs, plus particulièrement il s’agit d’un schéma de Feistel, du nom de Horst Feistel à l’originedu chiffrement Lucifer. Voir la figure ..

F . – Schémas de Feistel.

Dans un schéma de Feistel, le clair est de longueur paire et découpé en une moitié gauche L etune moitié droite R. Le ième tour du schéma prend en entrée un bloc (Li´1, Ri´1) et le transforme(en faisant intervenir la ième sous-clé Ki) en un bloc (Li, Ri). Le premier tour prend en entrée lebloc (L,R) et le dernier tour produit le chiffré (L1, R1). La relation entre (Li´1, Ri´1) et (Li, Ri)est :

Li = Ri´1, Ri = Li´1 ‘ f(Ri´1, Ki) où f est un chiffrement produit.



Un chiffrement de Feistel est inversible, que f soit une bijeion ou non. En effet, on a

Ri´1 = Li, Li´1 = Ri ‘ f(Ri´1, Ki).

Ainsi, le permuté (R,L) du clair s’obtient à partir de celui (R1, L1) du chiffré en lui appliquantun chiffrement de Feistel de même schéma et en prenant comme liste de sous-clés de déchiffrementla même que celle des sous-clés de chiffrement, mais dans l’ordre inverse.

D’une manière générale, on peut dire que DES fonionne en trois étapes :

Les notations Lj etRj désignent des blocs de 32 bits : à partir d’un bloc de 64 bits (b1, b2, . . . b64),Lj est le sous-bloc (de gauche, L mis pour « left ») (b1, b2, . . . b32), tandis que Rj est le sous-bloc(de droite, R mis pour « right ») (b33, b34, . . . b64).

. Permutation initiale et fixe d’un bloc ,sans aucune incidence sur le niveau de sécurité. Voir lafigure ..

. Le résultat est soumis à 16 itérations d’une transformation, ces itérations dépendent à chaqueronde d’une autre clé partielle de bits. Cette clé de ronde intermédiaire est calculée à partirde la clé initiale de l’utilisateur (grâce à un réseau de tables de substitution et d’opérateursXOR) comme suit :f(Ri´1, Ki) = P (S(E(Ri´1) ‘ Ki)) où S dénote les Si (boîtes S).Si(Bi) transforme Bi = b1b2 . . . b6 le mot de 6 bits à l’entrée en un autre mot de 4 bits enprenant r (row) comme la ligne dans la table Si et c comme la colonne tel que r = b1b6 (il y a possibilités (,,,)) et b2b3b4b5 donne le numéro de colonne 0 ď c ď 15. Ainsi, S1(011011)donne r = (01) = 1 deuxième ligne, c = (1101) = 13, alors la sortie = (0101) = 5.Lors de chaque ronde, le bloc de 64 bits est découpé en deux blocs de 32 bits, et ces blocs sontéchangés l’un avec l’autre selon un schéma de Feistel. Le bloc de 32 bits ayant le poids le plusfort (celui qui s’étend du bit 32 au bit 63) subira une transformation.

. le dernier résultat de la dernière ronde est transformé par la fonion inverse de la permutationinitiale. Voir la figure ..

DES utilise huit tables de substitution (les S-Boxes) illustrées par les Figures . et . quifurent l’objet de nombreuses controverses quant à leur contenu. On soupçonnerait une faiblessevolontairement insérée par les concepteurs. Ces rumeurs furent dissipées au début des années par la découverte de la cryptanalyse différentielle qui démontra que les tables étaient bien conçues.

Exemple : S5(000111) :

— b1b6 = 01, on lit donc la deuxième ligne.— b2b3b4b5 = 0011 = 3, on regarde donc la ème colonne et le résultat est 12 = 1100.

.. Dérivation des sous-clés

Pour la dérivation des clés de ronde de bits à partir de clé principale de bits :

En prenant K = k1...k64 une clé de -bit (y compris bits de parité impaire)

. Définir vi, 1 ď i ď 16 tel que : vi = 1 pour i P 1, 2, 9, 16 ; vi = 2 autrement. (Ce sont lesvaleurs du décalage circulaire à gauche pour -bit.)

. T = PC1(K) ; représenter T comme deux parties de -bit (C0, D0). (Utiliser PC1 de la Fi-gure . pour séleionner les bits à partir de K : C0 = k57k49 . . . k36, D0 = k63k55 . . . k4.)



. Pour i allant de 1 à 16, calculer Ki comme suit : Ci = (Ci´1 ö vi), Di = (Di´1 ö vi),Ki = PC2(Ci, Di). (Utiliser PC2 de la Figure . pour séleionner les bits à partir dela concaténation b1b2 . . . b56 de Ci et Di : Ki = b14b17 . . . b32. A savoir ö dénote un décalagecirculaire à gauche.)

.. Déchiffrement

Le déchiffrement est identique au chiffrement sauf que les sous-clés sont prises dans l’ordre inverse.k16 puis k15, …et enfin k1.

Pour engendrer les sous-clés dans l’ordre inverse, les décalages à droite à utiliser sont , , , , ,, , , , , , , , , , .

Nous pouvons observer que C0 = C16 et D0 = D16. Ainsi, k16 peut être derivé après PC1.

k16 = PC2(C16, D16) = PC2(C0, D0) = PC2(PC1(k))

Pour engendrer k15 nous avons besoin de variables intermédiaires C15 and D15, qui peuvent êtredéduites de C16 et D16 utilisant les décalages à droite (right shifts (RS)) :

k15 = PC2(C15, D15) = PC2(RS2(C16), RS2(D16)) = PC2(RS2(C0), RS2(D0))

Pour tout message m et clé k nous avons DESk(m) = DESk(m). (complémentarité).

Enfin, pour tester le bon fonionnement le texte clair « Now is the time for all » représenté par

« P = EFDFCC » en hexadécimal (-bitASCII plus parité) et la clé K = 0123456789ABCDEF donne le texte chiffré

« C = FAEADAABFDECBB ».

.. Clés faibles

Une clé faible produit un comportement indésirable lorsqu’elle est utilisée dans des opérations dechiffrement. La définition exae d’une clé faible varie souvent selon le cryptosystème considéré.

Pour DES, il existe des clés faibles ainsi que des clés semi-faibles.

Une clé faible K est définie par : Ek(Ek(M)) = M

Où E est l’opération de chiffrement et M est un message clair. Chiffrer deux fois un message enclair avec la même clé produira ce message en clair. Ce surchiffrement agit donc comme la fonionidentité ce qui est à éviter.

Le fonionnement de DES est propice à la présence de clés faibles. En effet, la clé de bitsproduit sous-clés, chacune d’entre elles est utilisée dans le tour correspondant. Les clés faibles deDES sont celles qui produisent sous-clés identiques. Hors clés non impaires, c’est le cas pour lesclés suivantes :

FFFFEEEE

EEEEFFFF

FEFEFEFEFEFEFEFE

Comme les sous-clés sont identiques et que DES est un réseau de Feistel, la fonion de chiffre-ment est également celle de déchiffrement. On a de fao un double chiffrement équivalent à un



chiffrement suivi d’un déchiffrement. Le message en clair n’est donc pas chiffré et apparaît inchangéà la sortie.

Les clés semi-faibles de DES sont des clés K1 et K2 distines satisfaisant la propriété suivante :

EK1(EK2(M)) = M

Où E est l’opération de chiffrement DES. On compte clés de ce type dans DES, dont les clésfaibles. Ces clés sont :

FEFEFEFE

FEFEFEFE

FEFEFEFE

EFEFEFEF

EEEE

EEEE

FFEFFEFFEFFE

FEFFEFFEFFEF

FFFF

FFFF

EFEEFEEFEEFE

FEEFEEFEEFEE

Les clés semi-faibles sont celles qui une fois les utilisées pour générer les sous-clés, génèrentseulement deux sous-clés au lieu de différents.

De telles clés sont bien sûr à bannir mais leur présence ne rend pas DES moins robuste en théorie.DES a un espace de clés qui contient 256 possibilités. La probabilité de trouver une clé faible avec untirage aléatoire parfait est de

= , ˆ ´, c’est un évènement hautement improbable.On peut aussi simplement tester la clé pour vérifier qu’elle n’est pas faible. DES est un chiffrementqui a été passablement cryptanalysé et les clés faibles sont un problème qui a été relégué au deuxièmeplan puisqu’il est désormais possible de mener une recherche exhaustive des clés de DES.

La liste est incomplète mais plusieurs chiffrements par bloc possèdent des clés faibles :

— IDEA, les clés faibles sont identifiables avec une attaque par texte clair choisi, la relation entreles bits du texte clair et ceux du texte chiffré devient prévisible. Des publications de JoanDaemen en 1993 ont confirmé les risques d’avoir des clés avec de longues séquences de bits nuls(plus de 14 bits nuls consécutifs). Daemen a montré que la classe de clés faibles comptait 251clés, un nombre qui peut paraître énorme mais insignifiant par rapport aux 2128 clés possibles.La probabilité d’obtenir une clé faible dans IDEA est alors de 2´76 ce qui est inférieur à laprobabilité d’une clé faible dans DES. Les clés faibles étant faciles à déteer, cette découvertene pose pas un problème majeur en pratique.

— Blowfish, les clés faibles produisent de mauvaises S-Boxes puisque ces substitutions dépendentde la clé. Il existe une attaque par texte clair choisi sur une version réduite de Blowfish qui estfacilitée par l’utilisation des clés faibles.

— RC, un chiffrement par flot n’est pas à l’abri non plus des clés faibles. Les clés qui commencentpar 000FD ont % de chance de produire une sortie qui commence par 0000.



.. Attaques

Plusieurs attaques ont été découvertes sur DES. Elles permettent de diminuer les coûts d’unerecherche exhaustive des clés qui se monte à 255 opérations en moyenne. Certaines de ces méthodesne sont plus efficaces avec des algorithmes de chiffrement plus récents du fait de l’introduion d’uneffet avalanche.

. Avant , attaques contre des versions réduites (t ă 16 tours).. La cryptanalyse différentielle découverte par Eli Biham et Adi Shamir en permet de trou-

ver la clé en utilisant 247 textes clairs. Voir . . ... L’attaque-T (Tickling attack) est une variante de la cryptanalyse différentielle découverte en

lors de la conception de DES par les chercheurs d’IBM. Pendant une vingtaine d’années,le silence a été complet sur cette découverte. C’est Don Coppersmith qui révélera le secret en. à l’époque, elle avait incité les concepteurs de DES à renforcer le contenu des tables desubstitution (au lieu de l’affaiblir comme la rumeur le laissait entendre).

. La cryptanalyse linéaire inventée par Mitsuru Matsui en . Voir .... Le compromis temps-mémoire est un concept inventé par Martin Hellman au début des an-

nées . En partant du principe que le même message va être chiffré plusieurs fois avec desclés différentes, on pourrait calculer une immense table qui contient toutes les versions chif-frées de ce message. Lorsque l’on intercepte un message chiffré, on peut le retrouver dans latable et obtenir la clé qui avait été utilisée pour le coder.Cette attaque n’est bien sûr pas faisable car nous avons besoin d’une table de l’ordre du milliardde GB. Le génie d’Hellman a été de trouver un moyen pour réduire cette table à environ téraoet (soit million de fois moins que la table compète), ce qui est faisable de nos jours.

. D’autres attaques sont spécifiques à des implémentations et ne sont pas forcément spécifiques àDES. Dans le cas d’un DES implémenté dans du matériel, on pourrait analyser la consomma-tion élerique et déduire certaines informations sur la clé (une consommation accrue indiquedes bits aifs). Le même style d’attaque peut aussi être employé sur un ordinateur en calculantle temps mis pour chiffrer avec des textes différents ou en analysant la mémoire utilisée.

. Toutes les autres attaques sur DES visent à réduire le temps de calcul d’une recherche exhaustiveen utilisant des machines spécifiquement conçues pour la tâche (grâce à des FPGA en parallèlepar exemple). Une telle machine a été construite en . Deep Crack a coûté environ dollars et pouvait casser la clé en moins d’une semaine. Le calcul distribué en utilisantles ordinateurs des particuliers (distributed.net) a prouvé son efficacité en cassant une clé enmoins de heures.



F . – Permutation initiale (IP ) et finale (IP´��1).

F . – L0 et R0 dans la permutation initiale.

F . – Expansion (E) et Permutation (P) au début de chaque ronde.

F . – Tableaux pour la génération des clés de rondes.



F . – Tables de substitution S à S.

F . – Tables de substitution S à S.



F . – Schéma général du DES.

F . – Génération de sous clé DES.



F . – Décalage dans la création des sous-clés de DES.


. Triple Data Encryption Standard

. Triple Data Encryption Standard

Le Triple DES (aussi appelé DES) est un algorithme de chiffrement symétrique enchainant applications successives de l’algorithme DES sur le même bloc de données de bits, avec ou clés DES différentes.

Cette utilisation de trois chiffrements DES a été développée par Walter Tuchman (chef du projetDES chez IBM), il existe en effet d’autres manières d’employer trois fois DES mais elles ne sont pasforcément sûres.

La version de Tuchman utilise un chiffrement, suivi d’un déchiffrement pour se conclure à nouveaupar un chiffrement. Le Triple DES est généralement utilisé avec seulement deux clés différentes. Lemode d’usage standard est de l’utiliser en mode EDE (Encryption, Decryption, Encryption, c’est-à-dire Chiffrement, Déchiffrement, Chiffrement) ce qui le rend compatible avec DES quand onutilise trois fois la même clé. Dans le cas d’une implémentation matérielle cela permet d’utiliser lemême composant pour respeer le standard DES et le standard Triple DES. Dans le mode proposépar Tuchman, voir la Figure ., DES s’écrit plus formellement de cette manière :

C = Ek3DES

(Dk2

DES

(Ek1

DES(M)

))Une autre variante de Triple DES est celle de Carl Ellison, mais elle ne fait pas partie du standard

défini pour DES :

C = Ek3DES

(T

(Ek2

DES

(T

(Ek1

DES(M)

))))où T est une fonion de transposition destinée à augmenter la diffusion. Cette fonion prend

en entrée un bloc de 8192 oets, remplit la graine d’un générateur de nombres pseudo-aléatoiresavec l’histogramme des oets, et mélange les oets du bloc grâce à la sortie du générateur. L’histo-gramme n’est pas changé par les permutations et donc l’opération inverse est possible. David Wagnera proposé une attaque sur le schéma d’Ellison en .

Même quand clés de bits différentes sont utilisées, la force effeive de l’algorithme n’est quede bits (si k3 = k1 et non bits (cas où toutes les clés sont indépendantes), à cause d’uneattaque rencontre au milieu. Cette attaque reste cependant peu praticable, en effet elle nécessite unstockage de données de l’ordre de 256 mots de bits, de plus ce stockage doit être « interrogeable» en un temps très court. C’est pour éviter ce genre d’attaque que le Double DES est simplementproscrit et que l’on passe direement à du Triple DES, le Double DES n’assure en effet qu’une forceeffeive moyenne de bits.

Bien que normalisé (par exemple par le NIST), bien connu, et assez simple à implémenter, ilest assez lent, et appelé à être remplacé par des algorithmes plus modernes tels qu’AES, égalementreconnu via le NIST aux états-unis comme sûr pour tout échange d’information.



F . – Triple DES.

. Advanced Encryption Standard

Advanced Encryption Standard est un processus de standardisation lancé en par le NISTqui demande aux cryptologues de concevoir un nouvel algorithme de chiffrement par bloc destinéau gouvernement des états-Unis. Le but était de remplacer Triple DES, qui a lui-même remplacétemporairement le Data Encryption Standard (DES). Ce dernier étant vulnérable à un grand nombred’attaques cryptanalytiques et fonionne avec une clé de seulement bits, sa sécurité n’était plusgarantie puisque une recherche exhaustive était désormais envisageable en un temps relativementcourt.

Comme la spécification de AES n’est pas gardée secrète et qu’elle ne se limite pas aux états-unis(cela était également le cas pour DES et DES), ce chiffrement est destiné à diverses utilisations,entre autres :

— Applications militaires/gouvernementales.— Produits commerciaux.— Logiciels libres.— Matériel dédié au chiffrement (routeurs, etc.)

Les exigences du nouveau standard étaient fortes car il est destiné à une utilisation intensive (pré-vue) jusqu’en , date à laquelle on estime que sa sécurité sera limitée de par les avancées techno-logiques et les recherches en cryptanalyse.

Un bloc de données de bits a été exigé. Des clés de et bits devaient également êtresupportées.

Le chiffrement devait bien sûr être robuste à toutes les attaques connues comme la cryptanalyselinéaire ou différentielle. La rapidité des opérations de chiffrement/déchiffrement était primordiale,AES n’étant pas restreint à une utilisation logicielle mais également matérielle avec des contraintesliées aux ressources disponibles (taille de la mémoire RAM ou ROM).

candidats furent proposés pour la première étape du concours :



CAST-, CRYPTON, DEAL, DFC, E, FROG, HPC, LOKI, MAGENTA, MARS, RC,Rijndael, SAFER+, Serpent et Twofish.

Après une première élimination, suite à la découverte de plusieurs failles, dans un certain nombred’entre eux, la liste fut réduite à candidats. Les concepteurs ont mutuellement « cryptanalysés »leurs chiffres et ont « joué le jeu » du concours. Certains chiffres, trop lents, ont été rapidementécartés. D’autres ont nécessité une cryptanalyse plus intensive.

Les cinq finalistes étaient :

— MARS— RC— Rijndael— Serpent— Twofish

.. Le vainqueur

En Oobre , le NIST annonce que Rijndael de Vincent Rijmen et Joan Daemen a remportéle concours AES et entrait dans un processus de standardisation officielle. Le Novembre ,AES a été approuvé dans le standard FIPS PUB par le NIST.

.. Fonctionnement

L’algorithme prend en entrée un bloc de bits ( oets). Les clés secrètes ont au choix suivantla version du système bits ( oets), bits ( oets) ou bits ( oets). Les données etles clés sont découpées en oets et placées dans des tableaux. Les données comportent td = oetsp0, p1, . . . , p15 qui sont classés dans un tableau ayant lignes et colonnes. Le tableau est remplicolonne par colonne. De même la clé est découpée en oets (tk = 16, tk = 24 ou tk = 32 oets)k0, k1, . . . , ktk´1. Ces oets sont aussi classés dans un tableau de lignes et Nk colonnes (Nk = ,Nk = ou Nk = ).

F . – Données et clés AES (cas Nk = ).

Suivant la version (la taille de la clé), le nombre de tours noté nr est différent. Le nombre nr estdonné dans le tableau suivant.

Nk nr

Le système crée nr + 1 clés de tour ayant chacune oets à partir de la clé initiale K. Ces cléssont stockées dans un tableau unidimensionnel TK et sont notées TK[0], TK[1], . . . TK[nr].



La procédure suivante de la Figure . décrit le fonionnement global du système AES. Elleprend en entrée un tableau de données St (texte clair) qui est modifié par la procédure et renvoyéen sortie (texte chiffré).

F . – Algorithm - AES(St, K).

Les procédures appelées Round, Figure ., et FinalRound, Figure ., sont elles-mêmes com-posées :

La procédure SubBytes, Figure ., est la seule transformation qui ne soit pas linéaire. C’est doncgrâce à celle-ci que le système est résistant. Elle utilise une opération sur le corps fini à éléments.

Le corps fini à éléments : Considérons le polynôme P (X) = X8 +X4 +X3 +X + 1 (quiest utilisé comme modulo).

F . – Algorithm - Round(St, T).

Ce polynôme à coefficients dans le corps à éléments F2 = t0, 1u est irréduible sur ce corps.

Les éléments du corps à éléments seront les oets b7b6b5b4b3b2b1b0 considérés comme despolynômes b(X) = b7X

7+ b6X6+ b5X

5+ b4X4+ b3X

3+ b2X2+ b1X+ b0, ce qui nous permet

de définir les deux opérations suivantes :

Addition : a7a6a5a4a3a2a1a0 + b7b6b5b4b3b2b1b0 = c7c6c5c4c3c2c1c0, avec c(x) = a(x)+ b(x),ce qui donne aussi ci = ai ‘ bi.

Multiplication : (a7a6a5a4a3a2a1a0) ‚ (b7b6b5b4b3b2b1b0) = c7c6c5c4c3c2c1c0, avec c(x) =a(x) ˆ b(x) mod P (x).

Par exemple :



F . – Algorithm - FinalRound(St, T).

F . – La procédure SubBytes.

(X6 +X4 +X2 +X + 1) ‚ (X7 +X + 1) = X13 +X11 +X9 +X8 +X7 +X7 +X5

+X3 +X2 +X +X6 +X4 +X2 +X + 1= X13 +X11 +X9 +X8 +X7 +X6 +X5 +X4 +X3 + 1= X7 +X6 + 1 mod X8 +X4 +X3 +X + 1

On a ainsi une struure de corps et donc tout élément non nul est inversible. Nous noterons gl’application de F256 dans F256 définie par :

g(x) =

#

0 si x = 0

x´1 sinon

L’inverse d’un élément b(x) se trouve par l’algorithme d’Euclide étendu :

b(x)a(x) +m(x)c(x) = 1 et b(x) ‚ a(x) mod m(x) = 1.

Alors : b(x)´1 = a(x) mod m(x).

La fonction affine f :

Définissons b = f(a) grâce à une matrice

b7b6b5b4b3b2b1b0

=

1 1 1 1 1 0 0 00 1 1 1 1 1 0 00 0 1 1 1 1 1 00 0 0 1 1 1 1 11 0 0 0 1 1 1 11 1 0 0 0 1 1 11 1 1 0 0 0 1 11 1 1 1 0 0 0 1

a7a6a5a4a3a2a1a0

‘

01100011

Responsable : Dr. BOUROUIS Abdelhabib

:::::::::::::::::::::::::::Sécurité informatique — -


La matrice carrée qui intervient est une matrice circulante, elle correspond donc à une multiplica-tion de polynômes modulo x8 ´ 1.

Ce qui correspond à b(x) = ((x4 + x3 + x2 + x+1)a(x) mod (x8 +1))‘ (x6 + x5 + x+1).On remarque que g´1 = g et que f´1 est définie par :

b7b6b5b4b3b2b1b0

=

0 1 0 1 0 0 1 00 0 1 0 1 0 0 11 0 0 1 0 1 0 00 1 0 0 1 0 1 00 0 1 0 0 1 0 11 0 0 1 0 0 1 00 1 0 0 1 0 0 11 0 1 0 0 1 0 0

a7a6a5a4a3a2a1a0

‘

00000101

La procédure SubByte :

On définit alors : s(a) = f(g(a)) qui est réalisée en appliquant la transformation affine f dansGF (2) à l’inverse de a dans GF (28).

On a donc aussi : s´1(b) = g(f´1(b)).

Il est donc possible de se servir de la S-Box de la Figure . dont les valeurs sont en hexadécimalpour réaliser cette transformation.

Par exemple, si ai = 53 en hexadécimal, alors bi = ED ce qui correspond à la ligne et la colonne.

De même, si ai = CF en hexadécimal, alors bi = 8A ce qui correpond à la ligne c et la colonnef .

La procédure SubByte, la Figure ., applique s à chaque oet de l’entrée St.

F . – AES-S-Box.

La procédure ShiftRows

Cette procédure, Figure ., consiste à opérer une rotation à gauche sur chaque ligne du tableaud’entrée. Le nombre de cases dont on décale la ligne i (0 ď i ď 3) est de i.



F . – Transformation SubBytes.

La transformation inverse est immédiate à calculer.

La procédure MixColumns :

La transformation MixColums, Figure ., consiste à appliquer à chaque colonne du tableau desdonnées une même transformation que nous allons décrire.

Considérons une colonne c = (c1, c2, c3, c4)t.

Les élément ci sont des éléments de F265. Chaque colonne c est transformée en une colonne dgrâce à la transformation linéaire suivante donnée par sa matrice dont les coefficients sont dans F265

et que nous écrivons comme des oets en hexadécimal :

d0d1d2d3

=

02 03 01 0101 02 03 0101 01 02 0303 01 01 02

ˆ

c0c1c2c3

Là encore la matrice utilisée est circulante. La transformation correspond en fait à une multiplica-

tion par un polynôme fixe : A(x) = 03x3 + 01x2 + 01x+ 02, modulo 1 + x4 :

F . – TransformationShiftRows.

d(x) = A(x) ˆ c(x) mod x4 + 1

où

c(x) = c0 + c1x+ c2x2 + c3x

3,

et

d(x) = d0 + d1x+ d2x2 + d3x

3.



F . – Transformation MixColums.

Le polynôme A(x) est premier avec x4 + 1, il est donc inversible modulo x4 + 1 est son inverseest B(x) = 0Bx3 + 0Dx2 + 09x+ 0E.

On retrouve donc c(x) à partir de d(x) en effeuant le produit

c(x) = B(x) ˆ d(x) mod x4 + 1,

ou en effeuant le produit matricielc0c1c2c3

=

0E 0B 0D 0909 0E 0B 0D0D 09 0E 0B0B 0D 09 0E

ˆ

d0d1d2d3

Lors de cette opération, chaque colonne est multipliée par la matrice suivante (pour une clé de

bit) :2 3 1 11 2 3 11 1 2 33 1 1 2

L’opération de multiplication est définie par : multiplication par signifie aucun changement, la

multiplication par deux correspond au décalage vers la gauche d’une position, et la multiplicationpar trois correspond à un décalage vers la gauche puis addition ‘ ou XOR avec la valeur initiale nondécalée. Après déplacement, un XOR conditionnel avec xB doit être effeuée si la valeur décaléeest plus grand que xFF.

La procédure AddRoundKey :

La procédure AddRoundKey est très simple. Elle consiste à faire un ou exclusif entre les bits del’état St et les bits de la clé de tour T . On obtient une nouvelle valeur de l’état. St := St ‘ T .

La procedure KeyExpansion :

La clé de chiffrement K stockée dans un tableau de lignes et Nk colonnes (Nk = 4, 6, 8) estétendue en un tableau W ayant lignes et 4ˆnr+1 colonnes. La clé de tour TK[i] (0 ď i ď nr)est donnée par les colonnes 4 ˆ i, 4 ˆ i+ 1, 4 ˆ i+ 2, 4 ˆ i+ 3 du tableau W .

Il y a deux façons de construire le tableau W suivant que Nk = , ou Nk = . La procédure deconstruion est nommée ExpandedKey.

) Cas Nk = 4 ou Nk = 6 est illustré dans la Figure .



F . – Algorithm - ExpandedKey(K,W) Cas .

La procédure utilise la fonion s sur les oets définie précédemment. Elle utilise aussi des constantesde F256,

données par RC[i] = αi, où α est l’élément de F256 correspondant au polynôme X(α = 02).L’élévation à la puissance i se fait dans le corps F256.

) Cas Nk = 8 est illustré dans la Figure ..

.. Déchiffrement

Le déchiffrement consiste à appliquer les opérations inverses, dans l’ordre inverse et avec des sous-clés également dans l’ordre inverse.

En commençan par le dernier bloc chiffré. L’opération InvShiftRows est l’inverse de ShiftRows. Lesoets des dernières lignes sont décalés à droite de façon cyclique selon l’indice de la ligne.

La première ligne demeure inchangée. La dexième est décalée par . La troisième par et la dernièrepar .

L’opération InvSubBytes est l’inverse de SubBytes, dans laquelle la S-box inverse est appliquée (in-verse de la transformation affine suivie de la multiplication inverse dans GF (2)).

La Fgure . illustre la boite S-Box inverse utilisée par AES.

L’opération InvMixColumns est l’inverse de MixColumns. Elle opère sur les données colonne parcolonne Tel que : a1��1(x) = 0bx3 + 0dx2 + 09x+ 0e.

c(x) = a´1(x)d(x) mod X4 + 1, ou en effeuant le produit matricielc0c1c2c3

=

0E 0B 0D 0909 0E 0B 0D0D 09 0E 0B0B 0D 09 0E

ˆ

d0d1d2d3

Responsable : Dr. BOUROUIS Abdelhabib

:::::::::::::::::::::::::::Sécurité informatique — -


F . – Algorithm - ExpandedKey(K,W) Cas .

F . – S-Box inverse d’AES.



L’opération AddRoundKey, est l’inverse d’elle même puisqu’elle n’effeue qu’un XOR.

F . – Algorithm - AES1��1(St,K).

F . – Algorithm - InvRound(St, T).

F . – Algorithm - InvFinalRound(St, T).

.. Attaques

Il n’existe pas de clés faibles ni semi-faibles dans ce cryptosystème.

L’AES n’a pour l’instant pas été cassé et la recherche exhaustive (à force brute à) demeure la seule so-lution. Rijndael a été conçu de telle manière à rendre des méthodes classiques comme la cryptanalyselinéaire ou différentielle très difficiles.

Attaques sur des versions simplifiées :



Des attaques existent sur des versions simplifiées d’AES. Niels Ferguson et son équipe ont proposéen une attaque sur une version à tours de l’AES bits. Une attaque similaire casse unAES de ou bits contenant tours. Un AES de bits peut être cassé s’il est réduit à tours avec une contrainte supplémentaire. En effet, cette dernière attaque repose sur le principe desà related-keys à (clés apparentées).

Dans une telle attaque, la clé demeure secrète mais l’attaquant peut spécifier des transformationssur la clé et chiffrer des textes à sa guise. Il peut donc légèrement modi ?er la clé et regarder commentla sortie de l’AES se comporte.

Attaques sur la version compète :

Certains groupes ont affirmé avoir cassé AES complet mais après vérification par la communautéscientifique, il s’avérait que toutes ces méthodes étaient erronées. Cependant, plusieurs chercheursont mis en évidence des possibilités d’attaques algébriques, notamment l’attaque XL et une versionaméliorée, la XSL. Ces attaques ont été le sujet de nombreuses controverses et leur efficacité n’a pasencore été pleinement démontrée, le XSL faitappel à une analyse heuristique dont la réussite n’estpas systématique. Deplus, elles sont impraticables car le XSL demande au moins 287 opérations voire2100 dans certains cas. Le principe est d’établir les équations (quadratiques / booléennes) qui lientles entrées aux sorties et de résoudre ce système qui ne comporte pas moins de inconnues et équations pour bits. La solution de ce système reste pour l’instant impossible à détermi-ner. En l’absence d’une preuve formelle sur l’efficacité d’attaques similaires au XSL, l’AES est doncconsidéré comme sûr. On peut toutefois parier que dans les années à venir, les avancées en cryptana-lyse et la relative simplicité de la struure d’AES devraient ouvrir des brèches dans l’algorithme. Sipareille découverte venait à se produire, des méthodes similaires à AES comme Camellia pourraientrapidement devenir obsolètes.

Recommandations de la NSA :

La NSA a annoncé que tous les finalistes qui avaient participé au concours AES pouvaient êtreconsidérés comme sûrs et qu’ils étaient suffisamment robustes pour chiffrer les données non-classifiéesdu gouvernement américain. En juin , le gouvernement américain a en effet annoncé :

« L’architeure et la longueur de toutes les tailles de clés de l’algorithme AES (, et )sont suffisantes pour protéger des documents classi ?és jusqu’au niveau »SECRET« . Le niveau»TOP SECRET« nécessite des clés de ou bits. L’implémentation de l’AES dans des produitsdestinés à la proteion des systèmes et/ou documents liés à la sécurité nationale doit faire l’objetd’une analyse et d’une certification par la NSA avant leur acquisition et leur utilisation »

Autres attaques :

Cette dernière phrase prend tout son sens lorsqu’on sait que des attaques sont possibles sur des sys-tèmes défaillants. On peut en effet analyser la consommation élerique (des pics de consommationindiqueraient des calculs lourds) ou encore le temps nécessaire au chiffrement. Ce genre d’attaquevise surtout des systèmes à boites noires à dans lesquels une clé secrète constante est codée dans lematériel et utilisée pour chiffrer plusieurs messages, par exemple des cartes à puce.

On peut toutefois se demander pourquoi aucun concours officiel n’a été lancé pour promouvoirla recherche d’attaques sur AES. Dans ce domaine, la méthode de chiffrement asymétrique RSAremporte la palme avec plusieurs concours dotés de gains élevés.

. Password-based cryptography


Chapitre

Cryptographie asymétrique

Sommaire. Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fondement théorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Authentification de l’origine . . . . . . . . . . . . . . . . . . . . . . . . . . . . Transmission sécurisée de la clé symétrique . . . . . . . . . . . . . . . . . . . . Bases mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Petit théorème de Fermat . . . . . . . . . . . . . . . . . . . . . . . . .. Propriétés de la congruence modulo n dans Z . . . . . . . . . . . . . . .. éorème de Bachet-Bézout . . . . . . . . . . . . . . . . . . . . . . . .. Algorithme d’Euclide étendu . . . . . . . . . . . . . . . . . . . . . .

... L’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . .. éorème des Restes Chinois . . . . . . . . . . . . . . . . . . . . . .

... Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . ... Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . ... éorème . . . . . . . . . . . . . . . . . . . . . . . . . . . ... Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . ... Solution . . . . . . . . . . . . . . . . . . . . . . . . . . ... Généralisation . . . . . . . . . . . . . . . . . . . . . . . .

.. Indicatrice d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Calcul de la puissance modulaire . . . . . . . . . . . . . . . . . . . . . Rivest Shamir Adleman . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Création des clés . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Chiffrement et déchiffrement du message . . . . . . . . . . . . . . . .

. Cryptosystème de ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fonionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Principe

La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrementqui s’oppose à la cryptographie symétrique. Elle repose sur l’utilisation d’une clé publique

(qui est diffusée) et d’une clé privée (gardée secrète), l’une permettant de coder le message et l’autrede le décoder. Ainsi, l’expéditeur peut utiliser la clé publique du destinataire pour coder un message

C : Cryptographie asymétrique

que seul le destinataire (en possession de la clé privée) peut décoder, garantissant la confidentialitédu contenu. Inversement, l’expéditeur peut utiliser sa propre clé privée pour coder un message que ledestinataire peut décoder avec la clé publique ; c’est le mécanisme utilisé par la signature numériquepour authenti ?er l’auteur d’un message.

Tels que la connaissance de k (la clé de chiffrement) ne permet pas d’en déduire celle de K (la cléde déchiffrement). Un tel cryptosystème est dit asymétrique, la clé k est appelée la clé publique, laclé K est appelée la clé privée.

F . – Cryptographie asymétrique (à clé publique et privée).

. Fondement théorique

Montrer que la recherche de K à partir de k revient à résoudre un problème mathématique no-toirement très compliqué, c’est à dire demandant un grand nombre d’opérations et beaucoup demémoire pour effeuer les calculs.

La cryptographie asymétrique est fondée sur l’existence de fonctions à sens unique. Une fois lafonion appliquée à un message, il est extrêmement difficile de retrouver le message original. Enréalité, on utilise des fonctions à sens unique et à brèche secrète. Une telle fonion est difficile àinverser, à moins de posséder une information particulière, tenue secrète, nommée clé privée.

RSA (l’algorithme le plus utilisé à l’heure auel) la déduion de K à partir de k revient à résoudrele problème de faorisation d’un grand nombre un problème sur lequel travaille les mathématiciensdepuis plus de ans, On estime que le plus rapide ordinateur que l’on puisse construire utilisantla meilleure méthode connue met plus de ans pour retrouver la clé privée d’un système RSAutilisant un modulo de bits (ordre de grandeur de la taille des clés).

. Authentification de l’origine

D’autre part, l’utilisation par Alice de sa clé privée sur le condensat d’un message, permettra à Bobde vérifier que le message provient bien d’Alice : il appliquera la clé publique d’Alice au condensatfourni (condensat chiffré avec la clé privée d’Alice) et retrouve donc le condensat original du message.Il lui suffira de comparer le condensat ainsi obtenu et le condensat réel du message pour savoir siAlice est bien l’expéditeur. C’est donc ainsi que Bob sera rassuré sur l’origine du message repu : ilappartient bien à Alice. C’est sur ce mécanisme notamment que fonionne la signature numérique.


. Transmission sécurisée de la clé symétrique

. Transmission sécurisée de la clé symétrique

La cryptographie asymétrique répond à un besoin majeur de la cryptographie symétrique : lepartage sécurisé d’une clé entre deux correspondants, afin de prévenir l’interception de cette clépar une personne tierce non autorisée, et donc la leure des données chiffrées sans autorisation.

Les mécanismes de chiffrement symétrique étant moins coûteux en temps de calcul, ceux-ci sontpréférés aux mécanismes de chiffrement asymétrique. Cependant toute utilisation de clé de chiffre-ment symétrique nécessite que les deux correspondants se partagent cette clé, c’est-à-dire la connaissentavant l’échange. Ceci peut être un problème si la communication de cette clé s’effeue par l’inter-médiaire d’un medium non sécurisé, « en clair ». Afin de pallier cet inconvénient, on utilise unmécanisme de chiffrement asymétrique pour la seule phase d’échange de la clé symétrique, et l’onutilise cette dernière pour tout le reste de l’échange.

. Bases mathématiques

.. Petit théorème de Fermat

En mathématiques, le petit théorème de Fermat est un résultat de l’arithmétique modulaire, quipeut aussi se démontrer avec les outils de l’arithmétique élémentaire. Il s’énonce comme suit :

« Si p est un nombre premier et si a est un entier non divisible par p (premier avec p), alorsap´1 ´ 1 est un multiple de p. Autrement dit, ap´1 ” 1 mod p. »

Un énoncé équivalent est :

« Si p est un nombre premier et si a est un entier quelconque, alors ap ´ a est un multiple de p.Autrement dit, ap = a mod p »

F . – Pierre de Fermat - Première décennie du XVIIe siècle à Beaumont-de-Lomagne (France) - janvier à Castres (France).

Il doit son nom à Pierre de Fermat, qui l’énonce la première fois en sans apporter de démons-tration.

Voici quelques exemples (basés sur le second énoncé) :‹ 53 ´ 5 = 120 ” 0 mod 3 ou 53 = 125 ” 5 mod 3.‹ 72 ´ 7 = 42 ” 0 mod 2.‹ 25 ´ 2 = 30 ” 0 mod 5.



‹ (´3)7 + 3 = ´2184 ” 0 mod 7.‹ 297 ´ 2 = 158456325028528675187087900670 ” 0 mod 97.

Une légère généralisation du théorème s’énonce de la manière suivante :

Si p est un nombre premier et si m et n sont des entiers striement positifs tels que m ” nmod p ´ 1 alors, pour tout entier a : am ” an mod p.

Le petit théorème de Fermat est généralisé par le théorème d’Euler :

Pour tout entier naturel non nul n et tout entier a premier avec n, on a aφ(n) ” 1 mod n.

où φ(n) désigne la fonion φ d’Euler comptant les entiers entre 1 et n qui sont premiers avec n.Si n est un nombre premier, alors φ(n) = n ´ 1, on retrouve le petit théorème de Fermat.

F . – Leonhard Paul Euler - avril à Bâle (Suisse) - septembre (à ans) àSaint-Pétersbourg (Russie).

.. Propriétés de la congruence modulo n dans Z

Soit n un entier naturel non nul. Considérons dans la relation notée telle que pour tous entiersrelatifs x et y :

x ” y mod n ô x ´ y est un multiple de n dans Z ô Dk tel que x ´ y = kn

Il s’agit d’une relation d’équivalence et on appelle cette relation congruence modulo n dans Z.

x ” y mod n se lit : « x est congru à y modulo n ».

Pour des entiers relatifs x1, x2, y1, y2, λ et tout entier naturel non nul n on a :

#

x1 ” y1 mod n

x2 ” y2 mod nñ

$

’

’

’

&

’

’

’

%

x1 + x2 ” y1 + y2 mod n

x1 ´ x2 ” y1 ´ y2 mod n

x1x2 ” y1y2 mod n

λx1 ” λy1 mod λn

@ c P Z, si x1 ” y1 mod n alors x1 + c ” y1 + c mod n

@ c P Z, si x1 ” y1 mod n alors x1c ” y1c mod n

Il en découle que : si x1 ” y1 mod n alors ´ x1 ” ´y1 mod n

@ k P Z˚+, si x1 ” y1 mod n, alors xk

1 ” yk1 mod n



(x1 + x2) mod n = (x1 + (x2 mod n)) mod n

= ((x1 mod n) + x2) mod n

= ((x1 mod n) + (x2 mod n)) mod n

(x1x2) mod n = (x1(x2 mod n)) mod n

= ((x1 mod n)x2) mod n

= ((x1 mod n)(x2 mod n)) mod n

.. éorème de Bachet-Bézout

C’est un résultat d’arithmétique élémentaire, qui prouve l’existence de solutions à l’équation dio-phantienne linéaire :

a ¨ x+ b ¨ y = PGCD(a, b)

Il s’annonce comme suit :Etant donnés deux entiers relatifs a et b non tous deux nuls, si d est le PGCD de a et de b alors ilexiste deux entiers relatifs x et y tels que x ¨ a+ y ¨ b = d.Deux entiers relatifs a et b sont premiers entre eux si et seulement s’il existe deux entiers relatifs x ety tels que x ¨ a+ y ¨ b = 1.

.. Algorithme d’Euclide étendu

Il s’agit d’une variante de l’algorithme d’Euclide qui permet, à partir de deux entiers x et y, decalculer non seulement leur plus grand commun diviseur (PGCD), mais aussi un de leurs couplesde coefficients de Bézout (deux entiers α et β tels que αx + βy = PGCD(x, y)). Quand x et xsont premiers entre eux, α est alors l’inverse pour la multiplication de x modulo y, ce qui est un casparticulièrement utile. L’algorithme d’Euclide étendu fournit également une méthode efficace nonseulement pour déterminer quand une équation diophantienne ax+ by = c possède une solution,ce que permet déjà l’algorithme d’Euclide simple, mais également pour en calculer dans ce cas unesolution particulière, dont on déduit facilement la solution générale.

... L’algorithme

On présente, sous forme de suite, le calcul du PGCD et des coefficients de Bézout pour deuxentiers naturels x et y. Le quotient (entier) de x par y est noté q. Pour x = 120 et y = 23 (on posetoujours x ě y), on vérifiera que le calcul conduit aux quatres colonnes ri, qi, αi et βi de l’exemple.

L’initialisation consiste en :. Pour i = 0 : r0 = x dans ce cas (x = 120), q0 =indéfinie, α0 = 1 et β0 = 0.. Pour i = 1 : r1 = y dans ce cas (y = 23), q1 = quotion de division de ri´1 = r0 = x = 120

par ri = r1 = y = 23, α1 = 0 et β1 = 1.Par la suite et pour chaque étape i :

‹ ri = le reste de la division de ri´2 par ri´1



i ri qi αi βi

0 120 - 1 01 23 5 0 1

(a) Initialisation.

i ri qi αi βi

0 120 - 1 01 23 5 0 12 5 4 1 ´53 3 1 ´4 214 2 1 5 ´265 1 2 ´9 476 0 - - -

(b) Déroulement des calculs.

T . – Etapes de calcul des coefficients de Bézout par l’algorithme d’Euclide étendu.

‹ qi = quotient de ri´1 par ri‹ αi = αi´2 ´ qi´1 ˆ αi´1

‹ βi = βi´2 ´ qi´1 ˆ βi´1

Les calculs sont effeués jusqu’à avoir ri = 0. La ligne avant (pour i ´ 1) donne les valeurssouhaitées :

α = αi´1 et β = βi´1.

Dans le cas étudié, α = ´9 et β = 47. Donc, 123 ˆ (´9) + 23 ˆ 47 = PGCD(125, 23) = 1

Le PGCD de x et y est le dernier reste non nul. Autrement dit, PGCD(x, y) = ri´1.

.. éorème des Restes Chinois

Le théorème des restes chinois est un résultat d’arithmétique modulaire traitant la résolution desystèmes de congruences. Ce résultat, établi initialement pour Z/nZ, se généralise en théorie desanneaux. Ce théorème est utilisé en théorie des nombres. La forme originale du théorème, contenuedans un livre du mathématicien chinois Qin Jiushao publié en .

... Exemple

Combien l’armée de Han Xing comporte-t-elle de soldats si, rangés par colonnes, il reste deuxsoldats, rangés par colonnes, il reste trois soldats et, rangés par colonnes, il reste deux soldats ?

... Exemple

Une bande de pirates possède un trésor constitué de pièces d’or d’égale valeur. Ils projettent dese les partager également, et de donner le reste au cuisinier chinois. Celui-ci recevrait alors pièces.Mais les pirates se querellent, et six d’entre eux sont tués. Un nouveau partage donnerait au cuisinier pièces. Dans un naufrage ultérieur, seuls le trésor, six pirates et le cuisinier sont sauvés, et le partagedonnerait alors pièces d’or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisiniers’il décide d’empoisonner le reste des pirates ?

... éorème

Soient n1, . . . , nk des entiers deux à deux premiers entre eux. Autrement dit, PGCD(ni, nj) = 1

lorsque i ‰ j. Alors pour tous entiers a1, . . . , ak, il existe un entier x, unique modulo n =śk

i=1 ni



et tel que

x ” a1 mod n1

. . .x ” ak mod nk

Une solution x peut être trouvée comme suit :

Pour chaque i, les entiers ni et n̂i = nni

= n1 . . . ni´1ni+1 . . . nk sont premiers entre eux, etd’après le théorème de Bachet-Bézout on peut trouver (en utilisant par exemple l’algorithme d’Eu-clide étendu) des entiers ui etvi , tels que uini + vin̂i = 1. Si on pose ei = vin̂i, alors nous avons

ei ” 1 (mod ni)

et

ei ” 0 (mod nj) pour j ‰ i.

Une solution particulière de ce système de congruences est par conséquent

x =k

ÿ

i=1

aiei ,

et les autres solutions sont les entiers congrus à ce x modulo le produit n.

... Solution

Le problème des soldats se réduit à

x ” 2 mod 3

x ” 3 mod 5

x ” 2 mod 7

On obtient alors

n = 3 ˆ 5 ˆ 7 = 105

n1 = 3 et n̂1 = 35 , or 2n̂1 ” 1 mod 3 donc e1 = 70

n2 = 5 et n̂2 = 21 , or n̂2 ” 1 mod 5 donc e2 = 21

n3 = 7 et n̂3 = 15 , or n̂3 ” 1 mod 7 donc e3 = 15

Une solution pour x est alors x = 2 ˆ 70 + 3 ˆ 21 + 2 ˆ 15 = 233

et les solutions sont tous les entiers congrus à 233 modulo 105, c’est-à-dire à 23 modulo 105.

... Solution

Le problème des pirates se réduit à :

x ” 3 mod 17

x ” 4 mod 11

x ” 5 mod 6

On obtient alors

n = 17 ˆ 11 ˆ 6 = 1122



n1 = 17 et n̂1 = 66 , or 8n̂1 ” 1 mod 17 donc e1 = 66 ˆ 8 = 528

n2 = 11 et n̂2 = 102 , or 4n̂2 ” 1 mod 11 donc e2 = 102 ˆ 4 = 408

n3 = 6 et n̂3 = 187 , or 6n̂3 ” 1 mod 6 donc e3 = 187

Une solution pour x est alors x = 3 ˆ 528 + 4 ˆ 408 + 5 ˆ 187 = 4151

et les solutions sont tous les entiers congrus à 4151 modulo 1122, c’est-à-dire à 785 modulo 1122.

... Généralisation

Si certains modules ne sont pas premiers entre eux (D ni, nj : PGCD(ni, nj) ‰ 1 ^ i ‰ j), alorsil faut déduire de nouvelles équations en se basant sur les équations initiales et sur la faorisationdes ni. Par exemple :

x ” 1 mod 6 ô

#

x ” 1 mod 2

x ” 1 mod 3

x ” 4 mod 15 ô

#

x ” 1 mod 3

x ” 4 mod 5

#

x ” 1 mod 6

x ” 4 mod 15ô

$

’

&

’

%

x ” 1 mod 2

x ” 1 mod 3

x ” 4 mod 5

Un autre exemple :

x ” 1 mod 9 ô x ” 1 mod 3

x ” 4 mod 15 ô

#

x ” 1 mod 3

x ” 4 mod 5#

x ” 1 mod 9

x ” 4 mod 15ô

#

x ” 1 mod 9

x ” 4 mod 5

.. Indicatrice d’Euler

La fonion indicatrice est aussi appelée fonion phi d’Euler ou simplement la fonion phi, car lalettreφ est communément utilisée pour la désigner. Elle est nommée en l’honneur du mathématiciensuisse Leonhard Euler (-) qui fut le premier à l’étudier.

L’indicateur d’Euler φ est la fonion de l’ensemble N˚ des entiers striement positifs dans lui-même qui à n associe le nombre d’entiers striement positifs inférieurs ou égaux à n et premiersavec n.

φ(n) = card(tm P N˚ | m ď n et m premier avec nu).

Exemples :‹ φ(12) = card(t1, 5, 7, 11u) = 4‹ φ(13) = card(t1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12u) = 12‹ φ(14) = card(t1, 3, 5, 9, 11, 13u) = 6



... Propriétés

n désigne un entier striement positif.

‹ La valeur φ(n) est égale au nombre de générateurs d’un groupe cyclique d’ordre n.‹ La valeur φ(n) est égale à l’ordre du groupe des éléments inversibles de l’anneau Z/nZ.‹ Siu et v sont deux entiers striement positifs et premiers entre eux, alorsφ(u.v) = φ(u).φ(v).‹ Un entier p ą 0 est premier si et seulement si φ(p) = p ´ 1.

Pour le calcul de n, il vaut mieux faoriser en un produit de nombres premiers pi :

Si n =q

ź

i=1

pkii alors φ(n) =q

ź

i=1

(pi ´ 1)pki´1i = n

qź

i=1

(1 ´

1

pi

)

Où ki est un entier striement positif.

.. Calcul de la puissance modulaire

Le calcul de y = xn mod m où n P N˚, m P N˚ et x P Z˚ avec x ă m peut se faire de plusieursmanières.

Si on procède naïvement (direement) d’abord au calcul de xn, on risque de provoquer un dé-passement de capacité en plus du nombre considérable d’opérations (n ´ 1 multiplications et unedivision = n) effeuées (complexité de l’algorithme soujacent O(n)).

Les calculs de proche en proche permettent d’éviter le dépassement de capacité. Après chaquemultiplication on applique le modulo. Cela augmente le nombre d’opérations nécessaires à 2(n´1).Bien que les opérations prennent pourtant moins de temps que précédemment (moins d’échangesentre cache ou antémémoire et mémoire/moins d’utilisation du swapping dans le cas de mémoirevirtuelle). L’algorithme profite de la propriété suivante :

b1 ” b mod m et c1 ” c mod m ñ b1c1 ” bc mod m

Par exemple, pour obtenir 51063 mod 2159, on peut faire les calculs suivants :

5 mod 2159 = 5 ;

52 mod 2159 = 25 ;

53 mod 2159 = 25 ˆ 5 mod 2159 = 125 ;

54 mod 2159 = 125 ˆ 5 mod 2159 = 625 ;

55 mod 2159 = 625 ˆ 5 mod 2159 = 3125 = 966 ; etc.

Un calcul efficace de ces produits successifs est possible. On peut faire mieux et plus rapidement,à moindre frais. Prenons un exemple simple, sans se préoccuper pour le moment du modulo.

Pour calculer a128, il est maladroit d’effeuer les 127 produits successifs qui définissent la puis-sance. Pour avoir le résultat, il vaut beaucoup mieux procéder ainsi :

calcul de a2, puis de a4, a8, a16, a32, a64 et enfin a128, ce qui ne demandera que 7 élévations aucarré successives.

Mais si l’exposant n’est pas une puissance de 2 ?

Prenons par exemple a96 : à défaut d’être lui-même une puissance de 2, 96 s’écrit comme sommede deux puissances de 2 : 96 = 64 + 32. Par suite, a96 = a64 ˆ a32, dont le calcul résulte desélévations au carré obtenues plus haut.



La méthode peut toujours être mise en œuvre car écrire un nombre sous la forme d’une sommede puissances de 2 revient à décomposer ce nombre dans la base 2.

Par exemple : 1063 = (10000100111)2

On déduit la décomposition de 1063 en somme de puissances de 2 :

1063 = 210 + 25 + 22 + 21 + 20 = 1024 + 32 + 4 + 2 + 1.

On peut écrire : a1063 = a(1+2+4+32+1024) = a ˆ a2 ˆ a4 ˆ a32 ˆ a1024

On procède ensuite à des élévations au carré successives à partir de a :

a , a2 , a4 , a8, a16, a32 , a64, a128, a256, a512, a1024

Il nous n’intéresse que ceux entourés, qui permettent d’obtenir a1063

Remarquons qu’ils correspondent en fait à des 1 dans la représentation binaire. Il suffit de faire leproduit de ces entiers, éventuellement modulo un autre entier, pour avoir le résultat cherché.

Cela se traduit par l’algorithme suivant :

Algorithme . : E- Calcule une puissance modulaire.Entrées : x, n,m : entiers. m est le module et n est l’exposant (entiers striement positifs.),

x est un entier non nul.Sorties : y le réseltat de xn mod m

y Ð 1 tant que n ą 0 faire si n mod 2 = 1 alors y Ð xy mod m

n ÐX

n2

\

x Ð x2 mod m

retourner y

Une autre version de l’algorithme moins lisible et intuitive est donnée ci-dessous :

Algorithme . : E- Calcule une puissance modulaire.Entrées : x, n,m : entiers. m est le module et n est l’exposant (entiers striement positifs.),

x est un entier non nul.Sorties : y le résultat de xn mod m

si n mod 2 ‰ 0 alors y Ð x sinon y Ð 1

répéter n Ð

X

n2

\

si n ‰ 0 alors x Ð x ˆ x mod m si n mod 2 ‰ 0 alors

y Ð y ˆ x mod m

jusqu’à n = 0 retourner y

Une autre piste consiste à utiliser la récursivité, avec l’avantage d’une écriture relativement simpleet naturelle. Supposons que l’on cherche à calculer xn mod m. On peut alors écrire :


. Rivest Shamir Adleman

puissance(x, n) =

$

’

&

’

%

x, sin = 1

puissance(x2, n/2), sinpair estx ˆ puissance(x2, (n ´ 1)/2), sin ą 2impair est

Alors :

Si n est pair, xn mod m est égal (x2)n2 mod m

Si n est impair, xn mod m est égal x(x2)n´12 mod m

On peut en déduire l’écriture d’une fonion récursive. L’exposant n est amené ainsi à avoir desvaleurs de plus en plus petites, par divisions par successives. Il finira par valoir , et dans ce cas, onsait que la valeur à retourner est x.

Algorithme . : E-- Calcule une puissance modu-laire de façon récursive.

Entrées : x, n,m : entiers. m est le module et n est l’exposant (entiers striement positifs.),x est un entier non nul.

Sorties : y le résultat de xn mod m si n mod 2 = 0 alors y Ð xy mod m

y Ð 1 tant que n ą 0 faire si n mod 2 = 1 alors y Ð xy mod m

n ÐX

n2

\

x Ð x2 mod m

retourner y

Algorithme . : EMR Calcule une puissance modulaire de façon récursive.Entrées : x, n,m : entiers. m est le module et n est l’exposant (entiers striement positifs.),

x est un entier non nul.Sorties : le résultat de xn mod m

si n mod 2 = 0 alors retourner (ExpModRec(x2, n/2, m)) mod m

sinon si n ‰ 1 alors retourner (xExpModRec(x2, (n ´ 1)/2, m)) mod m

sinon retourner x

. Rivest Shamir Adleman

Rivest Shamir Adleman ou RSA est un algorithme asymétrique de cryptographie à clé publique,très utilisé dans le commerce éleronique, et plus généralement pour échanger des données confi-dentielles sur Internet.

Cet algorithme a été décrit en par Ron Rivest, Adi Shamir et Len Adleman, d’où le sigle RSA.RSA a été breveté par le MIT en aux états-Unis. Le brevet a expiré le septembre . En



, c’est le système à clé publique le plus utilisé (carte bancaire française, de nombreux sites webcommerciaux ….).

(a) De gauche à droite : Ron Rivest, AdiShamir et Len Adleman (). (b) Au M.I.T.

F . – Ron Rivest, Adi Shamir et Len Adleman.

Ronald Rivest, Adi Shamir et Leonard Adleman, dans « A Method for Obtaining Digital Signaturesand Public-key Cryptosystems », ont publié l’idée d’utiliser les anneaux Z/nZ et le petit théorème deFermat pour obtenir des fonions trappes, ou fonions à sens unique à brèche secrète. RSA reposesur le calcul dans les groupes Z/nZ, plus précisément sur l’exponentiation modulaire. Voici unedescription des principes mathématiques sur lesquels repose l’algorithme RSA.

Toutefois, le passage des principes à la pratique requiert de nombreux détails techniques qui nepeuvent pas être ignorés, sous peine de voir la sécurité du système anéantie. Par exemple, il estrecommandé d’encoder le message en suivant l’OAEP (Optimal Asymmetric Encryption Padding).

.. Création des clés

. Choisir p et q, deux nombres premiers distins.. Noter n leur produit, appelé module de chiffrement : n = pq.. Calculer l’indicatrice d’Euler de n : ϕ(n) = (p ´ 1)(q ´ 1).. Choisir e, un entier premier avec ϕ(n), appelé exposant de chiffrement.. Comme e est premier avec ϕ(n), il est, d’après le théorème de Bachet-Bézout, inversible

mod ϕ(n), c’est-à-dire qu’il existe un entier d tel que e.d ” 1 mod ϕ(n) où d est l’expo-sant de déchiffrement.

Le couple (n, e) est appelé clé publique, alors que le couple (n, d) est appelé clé privée.

.. Chiffrement et déchiffrement du message

Si M est un entier inférieur à n représentant un message, alors le message chiffré sera représentépar C ” M e mod n.

Pour déchiffrer C, on utilise d, l’inverse de e modulo ϕ(n) et on calcule Cd mod n.

On a alors, Cd mod n ” (M e)d mod n ” M ed mod n

Comme ed ” 1 mod ϕ(n) par définition de modulo, on a ed = 1+kϕ(n) = 1+k(p´1)(q´1),avec k P N.


. Cryptosystème de ElGamal

Or, pour tout entier M, M1+k(p´1)(q´1) ” M mod p et M1+k(p´1)(q´1) ” M mod q.

En effet,‹ Si M est premier avec p alors, d’après le petit théorème de Fermat, Mp´1 ” 1 mod p doncMk(p´1)(q´1) ” 1 mod p puis M1+k(p´1)(q´1) ” M mod p

‹ SiM n’est pas premier avec p, comme p est un nombre premier, cela signifie queM est multiplede p donc M1+k(p´1)(q´1) ” 0 ” M mod p

(un raisonnement analogue prouve la congruence modulo q)

L’entier M1+k(p´1)(q´1) ´ M est donc un multiple de p et de q. Comme p et q sont premiers (etpremiers entre eux), une conséquence du lemme de Gauss permet d’affirmer que M1+k(p´1)(q´1) ´

M est un multiple de pq, c’est-à-dire de n.

On a donc : Cd ” M ed ” M1+k(p´1)(q´1) ” M mod n

On constate que pour chiffrer un message, il suffit de connaitre e et n. En revanche pour déchiffrer,il faut d et n.

Pour calculer d à l’aide de e et n, il faut trouver l’inverse de emodulo (p´1)(q´1) ce qui nécessitede connaitre les entiers p et q, c’est-à-dire la décomposition de n en faeurs premiers.

Dans la pratique, deux problèmes majeurs apparaissent :‹ choisir un nombre premier de grande taille‹ calculer M = Cd mod n

Une méthode simple pour choisir un nombre premier de grande taille est de créer une suite aléa-toire de bits, puis de le tester avec le test de primalité. Un problème apparait pour cette deuxièmeopération : la méthode naïve serait d’utiliser le crible d’Eratosthène, mais elle est trop lente. Enpratique, on utilise un test de primalité probabiliste (test de primalité de Fermat par exemple). Cetest n’assure pas que le nombre est premier, mais il y a une forte probabilité pour qu’il le soit. Onpeut également utiliser un test de primalité déterministe en temps polynomial qui assure que lenombre est premier (comme le test de primalité AKS). Bien que moins rapide, il assure la primalitédu nombre.

Le calcul de M = Cd mod n peut être assez long. Calculer d’abord Cd, puis calculer le moduloavec n est coûteux en temps et en calculs. Dans la pratique, on utilise l’exponentiation modulaire.

On peut conserver une forme différente de la clé privée pour permettre un déchiffrement plusrapide à l’aide du théorème des restes chinois.

. Cryptosystème de ElGamal

L’algorithme ElGamal est un algorithme de cryptographie asymétrique basé sur les logarithmesdiscrets. Il a été créé par Taher Elgamal. Cet algorithme est utilisé par le logiciel libre GNUPrivacyGuard, de récentes versions de PGP, et d’autres systèmes de chiffrement, et n’a jamais été sous laproteion d’un brevet contrairement à RSA. Il peut être utilisé pour le chiffrement et la signatureéleronique. L’algorithme DSA du NIST est basé sur ElGamal.

Lorsque nous travaillons avec des nombres réels, logb(y) est la valeur x, telle que bx = y. Nouspouvons définir un logarithme discret analogue. Si b et n des entiers , avec n ă b, le logarithmediscret d’un entier y à la base b est un nombre entier x, tel que bx = y mod n.

Le logarithme discret est aussi appelé indice (index), et nous écrivons x = indb,ny.



F . – Taher Elgamal.

Bien qu’il soit assez facile d’élever un nombre à de grandes puissances modulo p,le calcul inversedu logarithme discret est beaucoup plus difficile. Le système El Gamal repose sur la difficulté de cecalcul.

.. Fonctionnement

. Alice calcule h = gx avec g, h P Z‹p pour un grand nombre premier p, g étant un élément

générateur de Z‹p, et divulgue sa clé publique (p, g, h). La valeur x est sa clé privée.

. Si Bob veut envoyer un message à Alice, il convertit d’abord son message sous la forme d’unnombre m P Z‹

p.. Bob génère un nombre entier k aléatoirement et calcule c1 = gk et c2 = m.hk Il envoie

(c1, c2) à Alice.. Alice peut reconstruire le message initialm en calculant c2/cx1 . En réalité, elle calcule le nombre

α = p ´ 1 ´ x. Elle calcule ensuite m = cα1 c2 mod p et retrouve le message initial.

On remarque que :c2cx1

=mhk

gxk=

mgxk

gxk= m

Il n’est pas obligatoire d’utiliser Z‹p. Tout groupe cyclique convient.

Casser l’algorithme ElGamal est dans la plupart des cas au moins aussi difficile que de calculerle logarithme discret. Cependant, il est possible qu’il existe des moyens de casser l’algorithme sansrésoudre le problème du logarithme discret.


Chapitre

Echange de clés

Sommaire. Cryptographie quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Introduion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fonionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. Echange de clés Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . .. Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Exemple concret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fondement mathématique . . . . . . . . . . . . . . . . . . . . . . . .. L’attaque de l’homme du milieu . . . . . . . . . . . . . . . . . . . . .

. Cryptographie quantique

.. Introduction

La cryptographie quantique, plus correement nommée distribution quantique de clés, désigneun ensemble de protocoles permettant de distribuer une clé de cryptage secrète entre deux

interlocuteurs distants, tout en assurant la sécurité de la transmission grâce aux lois de la physiquequantique et de la théorie de l’information.

Cette clé secrète peut ensuite être utilisée dans un algorithme de chiffrement symétrique, afin dechiffrer et déchiffrer des données confidentielles.

.. Historique

Stephen Wiesner a émis pour la première fois, au début des années , l’idée de pouvoir utiliserles phénomènes quantiques dans des applications liées à la sécurité. Dans son article fondateur, ilintroduit le concept de codage sur des observables conjuguées, et l’illustre par une technique deconception de billets de banques infalsifiables. Curieusement, cet article sera rejeté par l’IEEE aucours des années , et ne sera ?nalement publié qu’en dans SIGACT News.

A la suite de la publication de cet article, Charles H. Bennett et Gilles Brassard proposent en la première technique de cryptographie quantique proprement dite, qui se fonde sur les observablesconjuguées de Wiesner.

C : Echange de clés

En , de façon indépendante du travail de Bennett et Brassard, Artur Ekert, alors doorantau Wolfson College de l’université d’Oxford, développe une approche de cryptographie quantiquedifférente, fondée sur les corrélations quantiques pouvant exister entre deux photons, un phénomènenommé intrication quantique.

Ces deux protocoles, généralement abrégés en BB et E, sont largement reconnus commeles deux protocoles fondateurs de la cryptographie quantique moderne. La majorité des protocolesauels ont d’ailleurs été développés en s’inspirant de ceux-ci.

La communication de données confidentielles par un canal de transmission classique (par exempleInternet) nécessite l’utilisation d’algorithmes de cryptographie classiques : algorithmes de chiffre-ment asymétrique ou de chiffrement symétrique. Dans le cas du chiffrement symétrique, les deuxinterlocuteurs doivent posséder a priori une clé secrète, c’est-à-dire qui ne soit connue que d’euxdeux.

Se pose alors la question suivante : comment transmettre une clé de cryptage entre deux inter-locuteurs () à distance, () à la demande, et () avec une sécurité démontrable ? Auellement, latechnique se rapprochant au mieux de ces trois critères est une transmission physiquement sécurisée,de type valise diplomatique.

La cryptographie quantique cherche à répondre à ces trois critères en transmettant de l’informationentre les deux interlocuteurs en utilisant des objets quantiques, et en utilisant les lois de la physiquequantique et de la théorie de l’information pour déteer tout espionnage de cette information. S’iln’y a pas eu espionnage, une clé parfaitement secrète peut être extraite de la transmission, et celle-cipeut être utilisée dans tout algorithme de chiffrement symétrique a ?n de transmettre un message.Le système de cryptographie quantique est utilisé uniquement pour générer et transmettre une clé,et non le message en lui-même pour deux raisons essentielles :

. Les bits d’informations communiqués par les mécanismes de la cryptographie quantique nepeuvent être qu’aléatoires. Ceci ne convient pas pour un message, mais convient parfaitementbien à une clé secrète, qui doit être aléatoire.

. Même si le mécanisme de la cryptographie quantique garantit que l’espionnage de la commu-nication sera toujours déteé, il est possible que des bits d’informations entrent en possessionde l’espion avant que celui-ci ne soit déteé. Ceci est inacceptable pour un message, mais sansimportance pour une clé aléatoire qui peut être simplement jetée en cas d’interception.secrète,qui doit être aléatoire.

.. Fonctionnement

Lors d’un protocole de cryptographie quantique, deux interlocuteurs distants (généralement nom-més Alice et Bob) disposent :

. D’objets quantiques, c’est-à-dire d’objets physiques qui se comportent selon les lois de la phy-sique quantique. En pratique, ces objets sont toujours des impulsions lumineuses (des pho-tons), qui peuvent prendre plusieurs formes : photons uniques, états cohérents, paires de pho-tons intriqués, etc.

. D’un canal quantique, qui permet le transit des impulsions lumineuses. Il peut s’agir d’unefibre optique, qui permet facilement de guider la lumière, ou de l’air libre, auquel cas Alice etBob doivent se faire face.

. Enfin, d’un canal classique de communication (comme Internet), qui doit être authentifié :Alice doit être certaine qu’elle parle bien à Bob.


. Cryptographie quantique

Entre Alice et Bob se trouve un espion, aussi appelé adversaire, qu’il est d’usage de nommer Eve (del’anglais eavesdropper). Eve a accès à tout ce qui transite entre Alice et Bob, classique ou quantique,et n’est limitée que par les lois de la physique. En revanche, elle ne peut pas accéder aux systèmesd’Alice et de Bob, qui sont supposés physiquement sécurisés.

F . – Cryptographie quantique.

Alice code tout d’abord une information aléatoire sur chaque impulsion lumineuse, puis l’envoieà Bob par le canalquantique.Celui-ci mesure alors l’information que porte l’impulsion qu’il a reçu.Après la transmission, Bob possède donc un ensemble de mesures qui sont corrélées aux donnéesenvoyées par Alice, mais qui ont pu être espionnées par Eve.

L’une des propriétés fondamentales de la cryptographie quantique est la capacité des deux interlo-cuteurs à déteer la présence de l’espion, mais aussi à évaluer précisément la quantité d’informationque celui-ci a intercepté.

Ceci résulte de deux aspes fondamentaux de la mécanique quantique :

. D’après le théorème de non-clonage, il est impossible de dupliquer un objet quantique in-connu,

. Le postulat de réduion du paquet d’onde entraine que réaliser une mesure sur un objetquantique perturbe généralement l’objet en question.

Si Eve cherche à obtenir de l’information sur l’état de l’objet qui transite par le canal quantique,elle introduit donc des anomalies (bruit ou erreurs), qui peuvent être déteées par Alice et Bob.

Il est possible d’établir formellement un lien entre la quantité d’anomalies et la quantité d’infor-mation interceptée par Eve, grâce à des démonstrations mathématiques appelées preuves de sécurité,qui combinent les lois de la physique quantique et de la théorie de l’information.

Information secrète résiduelle :

Alice et Bob évaluent tout d’abord le niveau d’erreurs et de bruit séparant leurs deux ensembles dedonnées.

Les différences entre leurs données peuvent provenir de :

‹ L’intervention d’Eve, qui rajoute des erreurs et du bruit‹ Les erreurs et le bruit de fond, qui ne peuvent jamais être évités complètement.

Néanmoins, puisque les erreurs de communication et les effets de l’observation d’Eve ne peuventpas être distingués, Alice et Bob doivent supposer que toutes les incohérences sont dues à l’aiond’un espion.



Ensuite, grâce aux preuves de sécurité et à ce niveau de bruit, Alice et Bob peuvent évaluer la quan-tité d’information qui a été interceptée par Eve, notée IE . En parallèle, la théorie de l’informationleur permet d’évaluer la quantité d’information qu’ils partagent après la transmission, IAB.

Finalement, si la quantité d’information ∆I = IAB ´ IE reste supérieure à zéro, c’est-à-dire quele niveau d’espionnage reste en dessous d’un certain seuil, alors une clé secrète de taille maximale ?Ipeut être extraite de la transmission.

Dans le cas contraire, aucune extraion n’est possible, et l’échange doit donc être interrompu.

Extraction de la clé :

S’il reste un avantage à Alice et Bob après l’évaluation de l’information secrète résiduelle, ils peuventlancer l’extraion de la clé proprement dite. Souvenons-nous qu’Alice et Bob ne partagent pas encoreune clé, mais des données corrélées.

L’extraion est composée de deux étapes : la réconciliation et l’amplification de confidentialité.

Réconciliation :

La réconciliation consiste à générer une chaine de bits partagée par Alice et Bob à partir des donnéescorrélées, en particulier à l’aide d’un algorithme de correion d’erreurs. Pour ce faire, l’émetteur oule récepteur utilise un code correeur pour générer un ensemble de syndromes, qu’il envoie à l’autrepartie afin qu’elle puisse corriger ses données. Puisque le canal classique de transmission n’est pascrypté, ces informations sont supposées connues de l’espion. Il est donc impératif d’en envoyer aussipeu que possible, afin de ne pas lui apporter trop d’information.

Amplification de confidentialité :

L’amplification de confidentialité est une technique qui transforme la clé corrigée en une clé secrèteplus petite.

Les bits de la clé passent au travers d’un algorithme qui répartit l’ignorance de l’espion sur la cléfinale. De cette manière, l’information de l’espion sur la clé finale peut être rendue arbitrairementpetite.

En première approximation, la taille de la clé secrète finale est égale à la « taille » de l’informationpartagée avant réconciliation, diminuée du nombre de bits connus (ou supposés connus) par l’espion,et diminuée du nombre de bits publiés lors de la correion d’erreur.

. Echange de clés Diffie-Hellman

En cryptographie, l’échange de clés Diffie-Hellman, du nom de ses auteurs Whitfield Diffie etMartin Hellman, inventée en , est une méthode par laquelle deux personnes nommées conven-tionnellement Alice et Bob peuvent se mettre d’accord sur un nombre (qu’ils peuvent utiliser commeclé pour chiffrer la conversation suivante) sans qu’une troisième personne appelée Eve puisse décou-vrir le nombre, même en ayant écouté tous leurs échanges¹.

.. Principe

. Alice et Bob ont choisi un groupe (soit un corps fini, dont ils n’utilisent que la multiplication,soit une courbe elliptique) et une génératrice g de ce groupe².

. Standard IETF RFC .. g est une racine primitive de p sachant que p est un grand nombre premier.



(a) Merkle, Hellman et Diffie(s). (b) Whitfield Diffie. (c) Martin-Hellman.

F . – Whitfield Diffie et Martin Hellman.

. Alice choisit un nombre au hasard a (1 ă a ă p´ 1), élève g à la puissance a, et dit à Bob ga

mod p.. Bob fait de même avec le nombre b (1 ă b ă p´1). Autrement dit,Bob élève g à la puissance

b, et dit à Alice gb mod p.. Alice, en élevant le nombre reçu de Bob à la puissance a, obtient gba mod p.. Bob fait le calcul analogue et obtient gab mod p, qui est le même. Mais puisqu’il est difficile

d’inverser l’exponentiation dans un corps fini, c’est-à-dire de calculer le logarithme discret, Evene peut pas découvrir a et b, donc ne peut pas calculer gab mod p.

F . – Déroulement de l’échange de clés Diffie-Hellman.

.. Exemple concret

. Alice et Bob choisissent un nombre premier p et une base g. Dans notre exemple, p = 23 etg = 5.

. Alice choisit un nombre secret a = 6.. Elle envoie à Bob la valeur ga mod p = 56[23] = 8.. Bob choisit à son tour un nombre secret b = 15.. Bob envoie à Alice la valeur gb mod p = 515[23] = 19.



. Alice peut maintenant calculer la clé secrète : (gb mod p)a mod p = 196[23] = 2.. Bob fait de même et obtient la même clé qu’Alice : (ga mod p)b mod p = 815[23] = 2.

F . – Schéma général pour l’échange de clés Diffie-Hellman.

F . – Exemple concret d’échange de clés Diffie-Hellman..

.. Fondement mathématique

La méthode utilise la notion de groupe (multiplicatif ), par exemple celui des entiers modulo p,où p est un nombre premier (dans ce cas, les opérations mathématiques (multiplication, puissance,division) sont utilisées telles quelles, mais le résultat doit être divisé par p pour ne garder que le reste,appelé modulo). Les groupes ayant la propriété de l’associativité, l’égalité (gb)a = (ga)b est valide etles deux parties obtiennent bel et bien la même clé secrète.

La sécurité de ce protocole réside dans la difficulté du problème du logarithme discret : pour queEve retrouve gab à partir de ga et gb, elle doit élever l’un ou l’autre à la puissance b ou à la puissance arespeivement. Mais déduire a (resp.b) de ga (resp. gb) est un problème que l’on ne sait pas résoudreefficacement. Eve est donc dans l’impossibilité (calculatoire) de déduire des seules informations ga,gb, g et p, la valeur de gab.

Il faut toutefois que le groupe de départ soit bien choisi et que les nombres utilisés soient suffi-samment grands pour éviter une attaque par recherche exhaustive. A l’heure auelle, un nombrepremier p de l’ordre de chiffres ainsi que a et b de l’ordre de chiffres sont tout simple-ment impossibles à casser même avec les meilleurs algorithmes de résolution du logarithme discret.Si une solution pratique pour résoudre un logarithme discret venait à apparaître, d’autres systèmescryptographiques pourraient tomber, notamment le système d’El Gamal, qui repose sur le mêmeprincipe.



.. L’attaque de l’homme du milieu

Ce protocole est vulnérable à l’attaque de l’homme du milieu, qui implique un attaquant capablede lire et de modifier tous les messages échangés entre Alice et Bob. Cette attaque repose sur l’inter-ception de ga et gb, ce qui est facile puisqu’ils sont échangés en clair ; l’élément g étant supposé connupar tous les attaquants. Pour retrouver les nombres a et b et ainsi casser complètement l’échange, ilfaudrait calculer le logarithme discret de ga et gb, ce qui est impossible en pratique.

Mais dans l’attaque de l’homme du milieu, l’attaquant se place entre Alice et Bob, intercepte laclé ga envoyée par Alice et envoie à Bob une autre clé ga1 , se faisant passer pour Alice. De même, ilremplace la clé gb envoyée par Bob à Alice par une clé gb1 , se faisant passer pour Bob.

L’attaquant peut ainsi communiquer avec Alice en utilisant la clé partagée gab1et communiquer

avec Bob en utilisant la clé partagée ga1b.

Alice et Bob croient ainsi avoir échangé une clé secrète alors qu’en réalité ils ont chacun échangéune clé secrète avec l’attaquant, l’homme du milieu.

Solution

La parade classique à cette attaque consiste à signer les échanges de valeurs à l’aide d’une pairede clés asymétriques certifiées par une tierce partie fiable, ou dont les moitiés publiques ont étééchangées auparavant par les deux participants.

Alice peut ainsi être assurée que la clé qu’elle reçoit provient effeivement de Bob, et inversementpour Bob.




Chapitre

Fonctions de hachage

Sommaire. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Propriétés des fonctions de hachage . . . . . . . . . . . . . . . . . . . . . . .

.. Preimage resistance . . . . . . . . . . . . . . . . . . . . . . . . . . . .. nd preimage resistance . . . . . . . . . . . . . . . . . . . . . . . . . .. Collision resistance . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Fonion de compression. . . . . . . . . . . . . . . . . . . . . . . . . .. Pseudo-collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Effet avalanche . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

... Motivations . . . . . . . . . . . . . . . . . . . . . . . . . .. Critère d’avalanche strie . . . . . . . . . . . . . . . . . . . . . . . . .. Critère d’indépendance Bit . . . . . . . . . . . . . . . . . . . . . . .

. Construction de fonctions de hachage . . . . . . . . . . . . . . . . . . . . . . . MAC basée sur une fonction de hachage . . . . . . . . . . . . . . . . . . . . . MAC basée sur un chiffre symétrique par bloc CBC-MAC . . . . . . . . . . .

. Introduction

On nomme fonion de hachage une fonion particulière qui, à partir d’une donnée fournieen entrée, calcule une empreinte servant à identifier rapidement, bien qu’incomplètement,

la donnée initiale. Les fonions de hachage sont utilisées en informatique et en cryptographie.

F . – Fonion de hachage appliquée à entrées différentes.

C : Fonctions de hachage

Le résultat d’une fonion de hachage peut être appelé selon le contexte somme de contrôle, em-preinte, hash, résumé de message, condensé, condensat ou encore empreinte cryptographiquelorsque l’on utilise une fonion de hachage cryptographique. On l’appelait autrefois aussi signa-ture, mais cette terminologie est moins utilisée afin d’éviter une confusion avec son sens juridique :le hachage est en effet aussi employé pour les signatures numériques.

F . – Fonion de hachage itérative.

. Propriétés des fonctions de hachage

Une fonion de hachage h est une fonion h : t0, 1u˚ Ñ t0, 1un

.. Preimage resistance

Etant donné une sortie y, il est difficile de trouver x tel que h(x) = y. ” à sens unique. En d’autrestermes, on ne peut pas trouver une fonion qui permet d’inverser le processus de hachage.

.. nd preimage resistance

Etant donné une entrée x, il est difficile de trouver x1 tel que h(x1) = h(x). ” faible résistanceaux collisions.

Autrement dit, une fonion de hachage est résistante aux collisions faibles s’il est difficile deconstruire des messages différents possédant la même empreinte. On entend par calculatoirementdifficile voir impossible en un temps raisonnable même avec l’aide d’ordinateurs très puissants. Cettedéfinition empêche un éventuel attaquant de modifier le message signé d’une personne et ainsi imitersa signature.

.. Collision resistance

Il est difficile de trouver x et x1tel que h(x) = h(x1). ” résistance forte aux collisions.

Idée : calculer une version condensée y d’un message m. Le condensé/résumé devrait être spécifiqueà ce message.

. Utiliser y au lieu de m de façon sûre.

. As-tu reçu m correement ? Voici y pour vérifier. (partage de fichier)

. As-tu déchiffré c correement ?

. Je signe y pour prouver que j’ai écrit m


. Propriétés des fonions de hachage

.. Fonction de compression.

Une fonion f : t0, 1um Ñ t0, 1un où n ă m est appelée une fonion de compression.

Si la fonion de compression f est résistante au collisions, alors la fonion de hachage h obtenueest résistante aux collisions.

Une fonction de hachage sans clé (en anglais unkeyed) est aussi appelée Modification/Manipula-tion Detection Code (MDC). On peut s’en servir pour s’assurer de l’intégrité d’un message.

Une fonction de hachage avec clé (en anglais keyed) est aussi appelée Message AuthenticationCode (MAC).

Elle a un paramètre additionnel (la clé) qui permet de vérifier l’intégrité et la provenance du mes-sage en même temps.

F . – Schéma général d’une fonion de hachage.

Ã�tant donnée une valeur k et un message x, la valeur hk(x) est facile à calculer. Ce résultat estsouvent appelé valeur MAC.

hk(x) a une valeur fixe de n bits, pour toute valeur de k et toute entrée x.

Ã�tant donné un ensemble de couples (xi, hk(xi)), il est impossible de créer un nouveau messagex différent de tous les messages xi et telle que pour un certain i : hk(x) = hk(xi)

.. Pseudo-collision

En cryptographie, on parle de pseudo-collision pour désigner deux résultats issus d’une mêmefonion de hachage qui présentent des similitudes significatives. Une signature A et une signatureB peuvent par exemple avoir % de leur bits en commun lorsque on les compare deux par deux.La recherche de pseudo-collisions précède la découverte d’une faille, nommée collision compète quirend la fonion de hachage « non-cryptographique ».

Une attaque qui recherche des pseudo-collisions n’est pas très utile à priori mais peut s’avérer fatalesi l’empreinte générée par la fonion de hachage est tronquée ou est soumise à une transformationparticulière qui la rend plus vulnérable (par exemple, prendre un bit sur deux pour faire une em-preinte plus courte).



.. Effet avalanche

L’effet avalanche est une propriété recherchée dans les fonions de hachage cryptographiques et lesalgorithmes de chiffrement par bloc. Elle provoque des modifications de plus en plus importantesau fur et à mesure que les données se propagent dans la struure de l’algorithme. De ce fait, enperturbant un seul bit en entrée, on obtient idéalement une sortie totalement différente, (soit envi-ron bit sur deux sera changé) d’où le nom de ce phénomène. L’effet avalanche permet de rendrel’inversion de la fonion plus difficile grâce à ses propriétés chaotiques (s’il est bien conçu).

Le terme a été inventé par Horst Feistel mais le concept remonte à la théorie de Shannon sur ladiffusion. En , le concept se voit précisé avec le « critère d’avalanche strie ».

... Motivations

La diffusion des modifications sur les entrées est très importante. Si ce n’est pas le cas et que lessorties présentent un biais statistique, il serait possible d’établir des prédiions sur les entrées àpartir de l’observation des sorties. L’effet avalanche est donc recherché lors de la conception d’uneprimitive de chiffrement. Pour ces raisons, la plupart des chiffrements par bloc utilisent le produitde plusieurs sous-chiffrements. Les fonions de hachage emploient des blocs de grande taille pourfaciliter la diffusion.

F . – Effet avalanche.

.. Critère d’avalanche stricte

Le critère d’avalanche strie (Stri Avalanche Criterion) est une propriété des fonions boo-léennes utilisées en cryptographie. Il a été introduit par Webster et Tavares en . Une fonionsatisfait ce critère si pour toute inversion d’un seul bit en entrée alors chaque bit en sortie a unechance sur deux d’être modifié.

L’uniformisation des sorties a pour but d’empêcher les prédiions dues à un biais statistique.

.. Critère d’indépendance Bit

Le bit independence criterion (BIC) indique que les bits J et K en sortie doivent changer demanière autonome et indépendante lorsque un bit quelconque i est inversé, et cela pour tout i, jet k.


. Construion de fonions de hachage

. Construction de fonctions de hachage

Dans le cadre des fonions de hachage cryptographiques, la construion de Merkle-Damgård estunec onstruion algorithmique qui permet de résoudre le problème du hachage cryptographiqueen acceptant un message de taille quelconque tout en produisant une sortie de taille fixe, et ensatisfaisant les contraintes de sécurité liées à la cryptographie :

‹ Résistance aux collisions (difficulté de trouver deux messages distins qui produisent la mêmeempreinte)

‹ Résistance aux attaques sur les préimages (difficulté de trouver un message à partir de sonempreinte, difficulté de forger un deuxième message produisant la même empreinte que lepremier)

La construion de Merkle-Damgård emploie une fonion de compression avec une entrée etune sortie de taille fixe, et divise le message à hacher en blocs de taille fixe. Les blocs sont ensuiteenvoyés les uns après les autres dans la fonion de compression. Le résultat de chaque compressionest ensuite transmis au bloc suivant selon plusieurs schémas :

‹ Miyaguchi-Preneel‹ Matyas-Meyer-Oseas‹ Davies-Meyer

Dans ces schémas :

. Le premier bloc utilise un veeur d’initialisation IV constant puisque aucun autre bloc ne leprécède.

. Un chiffrement symétrique par bloc EK générique de n-bits de paramètre K (une clé K) ;. Une funion g qui transforme les n bits d’entrée en une clé K adaptée pour E (si les clés pour

E sont également de longueur n, g est la fonion identité).

Alors pour :

. Matyas-Meyer-Oseas : H = IV ; Hi = Eg(Hi−)(xi) ‘ xi.. Davies-Meyer : H = IV ; Hi = Exi(Hi−) ‘ Hi−.. Miyaguchi-Preneel : H = IV ; Hi = Eg(Hi−)(xi) ‘ xi ‘ Hi−.

La construion de Merkle-Damgård produit un hachage résistant aux collisions pour autant que lafonion de compression utilisée est également résistante aux collisions. De la qualité de la fonionde compression dépendra la résistance de l’algorithme à la cryptanalyse. Le principe de Merkle-Damgård est utilisé notamment dans MD et SHA-.

Voici une liste non exhaustive de fonions de hachage les plus utilisées : AR, Boognish, FFT-hash, HAS-, Hava, MD, MD, MD, MD, N-hash, PANAMA, RIPEMD, RIPEMD-,RIPEMD-, RIPEMD-, SHA-, SHA-, SHA-, SHA-, SHA-, SHA-, Snefru,StepRightUp, Tiger, VSH, Whirlpool.



F . – Schéma détaillé d’une fonion de hachage.

F . – Construion de fonions de hachage.


. MAC basée sur une fonion de hachage

. MAC basée sur une fonction de hachage

Il est possible de construire un MAC en se basant sur une fonion de hachage existante en com-binaison avec une clé secrète. Ce type de MAC est dit Hash-based message authentication code ouHMAC. La construion et l’analyse des HMACs ont été publiées pour la première fois en parMihir Bellare, Ran Canetti, et Hugo Krawczyk (qui a écrit la RFC ). FIPS PUB généraliseet standardise l’utilisation des HMACs.

N’importe quelle fonion itérative de hachage, comme MD ou SHA-, peut être utilisée dansle calcul d’un HMAC ; le nom de l’algorithme résultant est HMAC-MD ou HMAC-SHA-. Laqualité cryptographique du HMAC dépend de la qualité cryptographique de la fonion de hachageet de la taille et la qualité de la clé.

La fonion HMAC est définie comme suit :

HMACK(m) = h

((K ‘ opad) || h

((K ‘ ipad) || m

))Tels que :

‹ h : une fonion de hachage itérative,‹ K : la clé secrète complétée avec des zéros pour qu’elle atteigne la taille de bloc de la fonionh,

‹ m : le message à authentifier,‹ « || » désigne une concaténation et ‘ un ou exclusif,‹ ipad et opad, chacune de la taille d’un bloc, sont des constantes définies par : ipad = 0x363636 . . . 3636

et opad = 0x5c5c5c . . . 5c5c. Donc, si la taille de bloc de la fonion de hachage est , ipadet opad sont 64 répétitions des oets, respeivement, 0x36 et 0x5c.

La figure . illustre le fonionnement global de HMAC SHA-.

F . – HMAC SHA-.

HMAC-SHA- et HMAC-MD sont utilisés dans les protocoles IPsec et TLS.



. MAC basée sur un chiffre symétrique par bloc CBC-MAC

Il est possible de définir une MAC en se basant sur un chiffre symétrique par bloc connu. CBC-MAC est l’un des algorithmes de MAC de ce genre. Il est basé sur un chiffrement par bloc utiliséselon un mode d’opération CBC (cipher block chaining). Ce principe a été formulé en dansun standard du NIST (FIPS PUB , Standard on Computer Data Authentication). On le retrouveaussi dans les standards ANSI X. et ISO/IEC .

Pour chiffrer, les données sont découpées en blocs de taille adéquate (selon le chiffrement par blocutilisé, au minimum un chiffrement par bloc de bits). Les blocs sont chiffrés les uns après lesautres, le résultat chiffré du bloc précédent est transmis au bloc suivant.

Soit Ek(Mi) l’opération de chiffrement sur un bloc de données Mi avec la clé k.

F . – Fonionnement de CBC-MAC.

Le chiffrement se fait comme suit (illustré par la figure .) :

. Les données sont découpées en blocs de taille fixe M0, . . . ,Mn´1 avec un remplissage selon lanorme PKCS# pour le dernier bloc,

. Soit C0 = 0 un veeur d’initialisation,. Les blocs sont traités au fur et à mesure : Ci+1 = Ek(Ci ‘ Mi)

Le code d’authentification correspond à une partie du dernier bloc chiffré Cn´1 (extraion de à bits dans le standard du NIST).

F . – CBC-MAC avec chiffrement du dernier bloc.


Chapitre

Signature digitale

Sommaire. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fonctionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.. Signatures avec appendices . . . . . . . . . . . . . . . . . . . . . . . .. Signatures avec recouvrement . . . . . . . . . . . . . . . . . . . . . . .. Signatures basées sur les certificats/sur l’identité . . . . . . . . . . . . . .. Signature déterministe/probabiliste . . . . . . . . . . . . . . . . . . .

. Attaques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Déclinaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Signature de Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Digital Signature Standard et Digital Signature Algorithm . . . . . . . . . . . . Schemas de signature basés sur RSA . . . . . . . . . . . . . . . . . . . . . . .

. Introduction

La signature numérique est un mécanisme permettant d’authentifier l’auteur d’un documentéleronique et de garantir son intégrité, par analogie avec la signature manuscrite d’un do-

cument papier. Une signature digitale apporte la non-répudiation à l’origine. Le signataire ne peutconvaincre un tiers qu’il n’est pas le signataire, il ne peut répudier sa signature.

Un mécanisme de signature numérique doit présenter les propriétés suivantes :

‹ Il doit permettre au leeur d’un document d’identifier la personne ou l’organisme qui a apposésa signature.

‹ Il doit garantir que le document n’a pas été altéré entre l’instant où l’auteur l’a signé et lemoment où le leeur le consulte.

Pour cela, les conditions suivantes doivent être réunies :

‹ Authentique : L’identité du signataire doit pouvoir être retrouvée de manière certaine.‹ Infalsifiable : La signature ne peut pas être falsifiée. Quelqu’un ne peut se faire passer pour un

autre.‹ Non réutilisable : La signature n’est pas réutilisable. Elle fait partie du document signé et ne

peut être déplacée sur un autre document.‹ Inaltérable : Un document signé est inaltérable. Une fois qu’il est signé, on ne peut plus le

modifier.

C : Signature digitale

‹ Irrévocable : La personne qui a signé ne peut le nier.

La signature éleronique n’est devenue possible qu’avec la cryptographie asymétrique. Elle se dif-férencie de la signature écrite par le fait qu’elle n’est pas visuelle, mais correspond à une suite denombres.

Un schéma de signature numérique est définie par trois algorithmes : l’algorithme de générationde clés, l’algorithme de signature, et l’algorithme de vérification.

. Fonctionnement

Supposons que l’on dispose d’un algorithme de chiffrement à clé publique. NotonsCA, la fonionde chiffrement et DA celle de déchiffrement. Rappelons que la fonion DA est connue de tous, parla clé publique associée à l’algorithme, tandis que CA n’est connue que par la propriétaire légitimede ce couple de fonions, Alice, qui seule détient la clé privée.

Lorsque Alice souhaite signer un message M , elle calcule S = CA(M). Toute personne disposantdu message M et de la signature S peut alors vérifier qu’Alice est à l’origine de la signature encalculant DA(S). Si cette quantité est bien égale à M , alors on peut être certain qu’Alice est l’auteurde la signature, car seule elle peut produire CA(M), puisqu’elle est la seule à connaitre CA et quecette fonion est bijeive. On peut être également sûr que le message n’a pas été altéré. En effet,pour altérer le message, il faudrait également altérer la signature de manière cohérente, ce qui n’estpossible que si l’on dispose de CA.

Pour être un peu plus précis, ce n’est jamais un message M qu’Alice signe, mais l’empreinte de Mpar une fonion de hachage. La sûreté de la signature dépend alors du soin apporté au choix de lafonion de hachage.

Il faut, qu’étant donné un message et son empreinte, il soit très difficile de fabriquer un messageayant une empreinte (et donc une signature) égale. L’intérêt de la fonion de hachage est de per-mettre de signer une quantité de données beaucoup plus petite que le message entier (et de longueurfixe).

La signature numérique nécessite souvent l’utilisation de certificats éleroniques. Ceux-ci sont gé-nérées par des autorités de certification (CA), qui permettent d’identifier de façon unique la personne(ou l’entité) qui détient les clés publique et privée : ils peuvent être vus comme la carte d’identiténumérique de cette personne ou entité.

En plus de ce rôle, les certificats peuvent permettre de chiffrer des informations.

Une signature digitale est produite par un algorithme de génération de signatures digitales et estvérifiée par un algorithme de vérification de signatures digitales Un schéma de signatures digitalesconsiste en un algorithme de génération de signatures digitales associé à son algorithme de vérifica-tion Il existe deux classes de schémas de signatures :

. Avec appendice (où le message original doit être fournit à l’algorithme de vérification). Avec recouvrement (où le message original est récupéré à partir de la signature).

.. Signatures avec appendices

Chaque signataire a une clé privée pour signer et une clé publique correspondante pour vérifierles signatures produites. Soient M un ensemble fini de messages, S un ensemble fini de signatureset K un ensemble fini de paires de clés (publique et secrète).


. Fonionnement

Pour toute paire de clés publique et privée (k, k1), il existe un algorithme de signature avec appen-dice Sigk1 et un algorithme de vérification correspondant V erk tels que la signature d’un messagex est

y = Sigk1(x) : M Ñ S

et

V erk(x, y) : M ˆ S Ñ tvrai, fauxu

PKCS# proposé par RSA Lab est un exemple.

.. Signatures avec recouvrement

Soient M un ensemble fini de messages, MS un ensemble fini de messages signables, S un en-semble fini de messages signés et K un ensemble fini de paires de clés (publique et secrète) Pourtoute paire de clé publique et secrète (k, k1), il existe un algorithme de signature avec recouvrementSigk1 qui applique MS Ñ S, une fonion de redondance R : M Ñ MS et un algorithme devérification correspondant V erk : S Ñ MS tels que la signature d’un message x est

y = Sigk1(R(x))

et

x1 = V erk(x)

Si x1 R MS alors la signature est rejetée, sinon la signature est acceptée et le message x = R1��1(x1)

est récupéré. ISO/IEC est un exemple.

.. Signatures basées sur les certificats/sur l’identité

Une autre manière de classifier les signature est de savoir la manière d’approuver la clé publiqueutilisée pour la vérification. La problème majeur dans la gestion des clés asymétriques est commentgarantir que la clé publique qu’on détient appartient bien à celui qu’on le pense bien être. Dansles signatures basées sur les certificats, la clé publique est attestée par un tiers de confiance, connusous le nom autorité de certification ou CA, qui délivre un certificat permettant d’attester que la clépublique en question appartient à l’entité corree. Ceci est connu sous le nom de Infrastructure àClé Publique ou public-key infrastructure (PKI).

L’alternative à l’utilisation d’une PKI est un système basé sur l’identité. La clé publique peut êtredireement dérivée de l’identité de la personne (par exemple, à partir de son adresse e-mail). Celasupprime le besoin de certificats, du fait que la clé publique est direement liée à l’identité del’entité avec laquelle on communique. Cependant, l’utilisation d’un système basé sur l’identité posedes contraintes sur la la clé publique. Si une entité avec une certaine identité souhaite utiliser lesystème alors sa clé publique doit être liée à son identité. Cela signifie que la clé publique est fixé àl’avance, et que la clé privée doit être calculée ensuite par l’algorithme de génération de clés.

.. Signature déterministe/probabiliste

Selon le cryptosystème asymétrique utilisé, une signature digitale peut être déterministe où unmessage est signé par une entité toujours d’une seule manière (même signature). Elle peut être pro-babiliste dans le sens où pour chaque message et entité, plusieurs signatures peuvent être associéeset une seule est obtenue à la fois de façon probabiliste.



. Attaques

Le but d’un adversaire est de forger une signature au nom d’un tiers.

Si un adversaire forge ainsi toutes les signatures qu’il désire au nom d’un tiers, le schéma de signa-ture est dit totalement cassé.

Si un adversaire peut forger des signatures pour certains messages, le schéma de signature est ditsélectivement forgeable.

Si un adversaire peut forger au moins une signature dont il ne contrôle par le contenu, le schémade signature est dit existentiellement forgeable.

. Déclinaisons

Historiquement, les premières signatures ont été individuelles. Elles ont été introduites par la suite :

‹ Les signatures de groupe où un membre ayant sa propre clé peut signer pour le groupe, leresponsable du groupe (identifié par sa propre clé) pouvant seul établir qui a émis la signature.

‹ Les signatures de cercle, qui leur sont similaires, mais où il n’est plus possible d’identifier in-dividuellement le signataire.

Des variantes existent comme lesK parmiN , oùK la signature est considérée comme valable siKmembres du groupe parmi les N définis ont signé. Ce système sera utilisé par exemple lorsque l’au-torisation de plusieurs services sera nécessaire pour déclencher un dispositif d’une gravité dépassantles prérogatives de chacun d’eux.

Tel serait le cas par exemple pour une procédure de mise sur écoute téléphonique nécessitant lesaccords à la fois d’une instance autorisée de l’exécutif et d’une instance autorisée du législatif. Oninterdit ainsi l’usage de renseignements d’états à des fins personnelles, puisque le déblocage nécessiteune coordination externe qui sera donc elle-même tracée.

. Signature de Rabin

Proposée par Michael O. Rabin en (parmi les premiers schémas). Elle est existentiellementforgeable.

. Génération des clés‹ Soit n la clé publique telle que n = pq avec p et q deux grands premiers formant la clé

secrète.

. Génération de la signatureSoit le message m à signer :

‹ rm = R(m) où R est la fonion de redondance‹ s =

?rm mod n et s est la signature de m

. Vérification de la signatureSoit la signature s fournie :

‹ rm = s2 mod n‹ si rm P Ms alors m = R´1(rm), sinon la signature est rejetée


. Digital Signature Standard et Digital Signature Algorithm

. Digital Signature Standard et Digital Signature Algorithm

Proposé par Kravitz est adopté par plusieurs instances dont le NIST en , puis finalementadopté en , DSS (Digital Signature Standard) est la norme de signature numérique du gou-vernement Américain. Elle se base sur l’algorithme DSA (Digital Signature Algorithm), qui utiliseSHA comme fonion de hachage à sens unique et Elgamal pour la génération et la vérification dela signature.

Il s’agit d’un schéma de signature digitale basé sur les certificats, avec appendice et probabiliste.

Le Digital Signature Algorithm (DSA), est un algorithme de signature numérique standardisépar le NIST aux Eats-Unis, du temps où le RSA était encore breveté. Cet algorithme fait partiede la spécification DSS pour Digital Signature Standard adoptée en (FIPS ). Une révisionmineure a été publiée en (FIPS -) et le standard a été amélioré en dans FIPS -.Il est couvert par le brevet N° aux USA ( juin ) attribué à David Kravitz, ancienemployé de la NSA, et il peut être utilisé gratuitement.

Le processus se fait en trois étapes :

. Génération des clés : Leur sécurité repose sur la difficulté du problème du logarithme discretdans un groupe fini.

‹ Choisir¹ un nombre premier p de L-bit, avec 2L´1 ă p ă 2L, et L est divisible par . pest appelé module.

‹ Choisir un nombre premier q de N-bit avec 2N´1 ă q ă 2N , de telle façon que p´1 = qz,avec z un entier (q est diviseur de p-).

‹ Choisir h, avec 1 ă h ă p ´ 1 de manière à ce que g = hz mod p ą 1. Où g est lagénératrice du groupe. (g est de l’ordre de q mod p). Généralement h = 2 est utilisé.

‹ Générer (pseudo)aléatoirement un entier x, la clé secrète avec 0 ă x ă q‹ Calculer y = gx mod p‹ La clé publique est (p, q, g, y). La clé privée est x.

Les entiers p, q, et g peuvent être publiques et peuvent être communs à un groupe d’uti-lisateurs. Les clés privé et publique d’un utilisateur sont x et y, respeivement. Elles sontnormalement fixées pour une durée de temps limitée.

. Signature du document :‹ Générer un nombre (pseudo)aléatoire s, 1 ă s ă q‹ Calculer s1 = (gs mod p) mod q‹ Calculer s2 = (H(m) + s1 ˆ x)s´1 mod q, où H(m) est le résultat d’un hachage

cryptographique, par exemple avec SHA-, sur le message m‹ La signature est (s1, s2)

. Vérification du document signé :‹ Rejeter la signature si 0 ă s1 ă q ou 0 ă s2 ă q n’est pas vérifié‹ Calculer w = (s2)

´1( mod q)‹ Calculer u1 = H(m) ˆ w( mod q)‹ Calculer u2 = s1 ˆ w( mod q)‹ Calculer v = [gu1 ˆ yu2 mod p] mod q‹ La signature est valide si v = s1

. L = , N = |L = , N = |L = , N = |L = , N = . Les autorités de certification (CA)doivent choisir une combinaison plus grande que celles utilisables par leurs clients.



Une séquence de bits tx1, . . . , xnu de longueur n est convertie en un entier par la règle suivante² :

tx1, . . . , xnu Ñ (x12n´1) + (x22

n´2) + . . .+ (xn´12) + xn.

Il faut noter que le premier bit de la séquence corresponds au bit le plus significatif de l’entiercorrespondant, et le dernier bit correspond au bit le moins significatif.

. Schemas de signature basés sur RSA

Beaucoup de schémas de signature numérique réversibles (avec recouvrement) sont basés sur l’uti-lisation de l’algorithme de chiffrement RSA. Dans cette seion, nous allons décrire un schéma designature réversible issu du standard ISO/IEC -. Tous les schémas de cette norme sont baséssur des principes similaires. Les versions non réversibles (avec appendice) de ce schéma sont égale-ment normalisées dans la norme ISO/IEC - et ANSI X..

Lorsque RSA est utilisé pour produire des schémas de signature numérique, la clé publique devérification se compose du module n et de l’exposant de déchiffrement d. La clé privée de signaturesera l’exposant de déchiffrement e.

Le problème rencontré en utilisant le système RSA pour produire des signatures numériques estle fait qu’il est facile de trouver des paires (α, β) tel que β = αe mod n en utilisant uniquementl’exposant de déchiffrement d. Cela est faisable en choisissant une valeur β pour la signature et encalculant le message α = βd mod n associé à cette signature.

Il est important de noter que, dans cette attaque, l’attaquant peut choisir la signature β, mais apeu de contrôle sur la valeur du message associé α. La sécurité des systèmes de signature à base deRSA vient de la manière dont α est construit. En règle générale, la valeur α n’est pas le message quidoit être signé, mais un codage spécial de ce message connu sous le nom de message représentatif. Lasécurité d’un schéma de signature basé sur RSA vient du fait qu’il est difficile pour un attaquant detrouver une signature β tel que le message représentatif associé α est un codage valide d’un messagedonné m.

Le schéma de signature décrit ici est basé sur un certificat, déterministe et réversible. Il est à noterque la norme ISO/CEI - contient également des versions probabilistes de ce schéma.

. La génération des clésIdentique au cryptosystème RSA sauf que la clé publique de vérification comprend le mo-dule n et l’exposant de déchiffrement d, et la clé privée de signature comprend l’exposant dechiffrement e.

. SignatureSoit m est un message court. Pour signer ce message en utilisant une clé publique constituéd’un module n et un exposant de déchiffrement d, les étapes suivantes sont nécessaires :

(a) Un message représentatif α est construit de cinq éléments :

α = header||padding||m||hash||trailer

Où chaque élément possède un signification et un rôle :X header consiste en une séquence courte de bits qui identifient le schéma signature

utilisé.

. L’opération inverse permet de convertir un entier en une chaine de bits.


. Schemas de signature basés sur RSA

X padding consiste en une séquence de bits pour le remplissage. Utilisé afin de garantirque le message représentatif α possède la même longueur que le module n.

X m est le message à signer.X hash est le résultat de hachage du message m calculé utilisant une fonion de hashage

choisie.X trailer consiste en une séquence courte de bits qui peut (optionnellement) identifier

la fonion de hachage utilisée.(b) Calculer la signature σ = αd mod n.

. VérificationPour verifier la signature σ utilisant un module n et une clé privé e, les étapes suivantes sontnécessaires :

ù Calculer le message représentatif α = σe mod n.ù Découper le message représentatif en parties : header, padding, m, hash, et trailer.ù Vérifier si les éléments header, padding, et trailer sont valides. Le format de ces élé-

ments est spécifié par le standard ; si l’un de ces éléments n’est pas valide alors la signatureest déclarée invalide.

ù Optionnellement, l’identité la fonion de hachage peut être récupérée à partir de trailer.ù Vérifier si le hash reçu est identique au hash code calculé utilisant le message reçu m. Le

cas échant, la signature est déclarée invalide.ù Si tout s’est bien passé durant les étapes précédentes, déclarer la signature comme valide et

donner m.




Bibliographie

[] A. Menezes, P. Van Oorschot, S. Vanstone.Handbook of Applied CryptographyCRC press, .http://cacr.uwaterloo.ca/hac/

[] R. Anderson. Wiley, .Security Engineering - A Guide to Building Dependable Distributed Systemshttp://www.cl.cam.ac.uk/~rja/book.html

[] Oded Goldreiche Foundations of Cryptography : volume Cambridge University Press .Draft : http://www.wisdom.weizmann.ac.il/~oded/foc-drafts.html

[] Oded Goldreiche Foundations of Cryptography : volume Cambridge University Press .Draft : http://www.wisdom.weizmann.ac.il/~oded/foc-book.html

[] David E. Newton.Encyclopedia of CryptologyABC-CLIO (Oober , ).

[] Fred B. Wrixon.Codes, Ciphers and Other Cryptic and Clandestine Communication : Ways to SendSecret Messages from Hieroglyphs to the InternetBlack Dog & Leventhal Publishers ; Revised edition (January , ).

[] Philippe GuillotLa cryptologie : L’art des codes secretsEDP Sciences. .

[] Jean-François CarpentierLa sécurité informatique dans la petite entreprise : Etat de l’art et bonnes pratiquesEni .

[] Gilles Bailly-MaîtreArithmétique et cryptologieEllipses .

[] Robert Rolland, Pierre Barthélemy, Pascal VéronCryptographie : Principe et mises en oeuvreHermès – Lavoisier (nd Ed)

http://cacr.uwaterloo.ca/hac/

http://www.cl.cam.ac.uk/~rja14/book.html

http://www.wisdom.weizmann.ac.il/~oded/foc-drafts.html

http://www.wisdom.weizmann.ac.il/~oded/foc-book.html

BIBLIOGRAPHIE

[] Philippe GuillotCourbes elliptiques : Une présentation élémentaire pour la cryptographieHermès – Lavoisier .

[] Fred Piper, Sean MurphyCryptography : A Very Short IntroductionOxford Paperbacks .

[] Saiful Azad, Al-Sakib Khan PathanPractical Cryptography : Algorithms and Implementations Using C++Auerbach Publications ( décembre )

[] Jonathan Katz, Yehuda LindellIntroduction to Modern Cryptography : Principles and ProtocolsChapman and Hall-CRC ; .

[] Alex W. Dent, Chris J. MitchellUser’s Guide To Cryptography And StandardsArtech House .

[] Antoine JouxAlgorithmic CryptanalysisChapman and Hall-CRC, .

[] Christopher SwensonModern Cryptanalysis : Techniques for Advanced Code BreakingJohn Wiley & Sons ( mars )

[] Jessica FridrichSteganography in Digital Media : Principles, Algorithms, and ApplicationsCambridge University Press ( novembre )

[] Patrick DucrotCours de :Sécurité Informatiquehttp://www.ducrot.org/securite.pdf

[] G. Florin, S. NatkinCours de :Introduction à la sécurité des systèmes d’informationhttp://deptinfo.cnam.fr/Enseignement/CycleProbatoire/RSX/cours_introduction.pdf

Cours de :Sécurité Informatiquehttp://repo.mynooblife.org/Securite/La%Securite%Informatique.pdf


http://www.ducrot.org/securite.pdf

http://deptinfo.cnam.fr/Enseignement/CycleProbatoire/RSX112/cours_introduction.pdf

http://repo.mynooblife.org/Securite/La%20Securite%20Informatique.pdf

Documents

U L B M’H O E B