Formation Générale en Cryptographierobert.rolland.acrypta.com/telechargements_crypto/fgc/fgc.pdf · (norme ISO 7498-2). Lors d’une communication, il s’agit d’empêcher un

Formation Générale enCryptographie

Robert Rolland

[email protected]

C.N.R.S., Institut de Mathematiques de Luminy

F13288 Marseille cedex 9, France

Formation Generale en Cryptographie – p. 1

I-1. Les buts à atteindre

• Secret, confidentialit e.

• Int egrit e des donn ees.

• Authentification .

• Non-r epudiation .

• Signature .

• Certification .

• Contr ole d’acc es.

• Gestion des cl es.


I-1.1 Secret, confidentialité

La confidentialit e est la propriété qu’uneinformation n’est ni disponible ni divulguée auxpersonnes, entités ou processus non autorisés(norme ISO 7498-2).Lors d’une communication, il s’agit d’empêcherun tiers de prendre connaissance del’information contenue dans un messagetransmis sur un canal non sécurisé.


I-1.2 Intégrité des données

On doit éviter que les données transmises soientmodifiées ou forgées par un adversaire. Plusprécisément : l’intégrité est la prévention d’unemodification non autorisée de l’information.L’intégrité du système et de l’information garantitque ceux-ci ne sont modifiés que par une actionvolontaire et légitime. Les attaques contrel’intégrité sont appelées substitutions .


I-1.3 Authentification

L’authentification consiste à vérifier l’identité desdifférents éléments impliqués dans un dialogue.Il peut s’agir d’authentifier une personne : onparle aussi dans ce cas d’identification . Onparlera par exemple d’identification del’expéditeur, du destinataire. Il peut s’agir aussid’authentifier une machine, notamment dans lecadre d’une relation client-serveur à travers unréseau ouvert ou un réseau fermé.


I-1.3 Authentification (suite)

On peut vouloir également authentifier undocument, son auteur, le serveur sur lequel onl’a récupéré, etc. La notion d’authentificationrecouvre différentes variantes plus ou moinssimilaires. Dans le cas d’un message, il s’agit deprouver son origine. Les attaques contrel’authentification sont appelées mascarades .


I-1.4 Non-répudiation

C’est un mécanisme qui empêche de nier uncontrat. La non-répudiation consiste à prouverpar exemple qu’un message a bien été émis parson expéditeur ou a bien été reçu par sondestinataire. L’auteur d’un message ne peut nierl’avoir écrit ou transmis. Cette fonctionnalité doitdonc permettre à un tiers de juger un conflitéventuel entre l’expéditeur et le destinataire.


I-1.5 Signature

C’est un mécanisme qui garantit l’authentificationde l’expéditeur, l’intégrité des données et la nonrépudiation. On peut en outre vouloirl’empêchement d’un rejeu par l’expéditeurlui-même ou par un tiers.


I-1.6 Certification

Une entité connue, digne de confiance, valideune certaine information. Cette entité est alorsappelée authorit e de certification .Typiquement, il peut s’agir d’un tiers deconfiance, qui dispose d’un mécanisme pourcertifier que la clé publique d’un utilisateur estbien celle qui est présente sur un serveur declés.


I-1.7 Contrôle d’accès

L’accès à certaines ressources est limité auxpersonnes autorisées. Par exemple retraitd’argent à un terminal bancaire (ATM :Automated Teller Machine) ou encore connexionà un ordinateur.


I-1.8 Gestion des clés

En général les systèmes cryptographiquesutilisent des clés (clés secrètes, clés privées,clés publiques). La gestion de ces clés(génération, distribution, stockage, intégrité,recouvrement, utilisation) est un problèmedifficile.


I-2. Techniques cryptographiques

• Chiffrement .

• Signature .

• Authentification .

• Echange de cl es.


I-2.1 Chiffrement

Le chiffrement consiste à transformer un texte clairen texte chiffr e. Le dechiffrement est l’opération quiconsiste à retrouver le texte clair à partir du textechiffré lorsqu’on dispose de la clé. Le decryptageconsiste à retrouver le texte clair à partir duchiffré lorsqu’on ne connaît pas la clé. Ainsi unexpediteur chiffre un texte clair et envoie le chiffréà un destinataire . Celui-ci le déchiffre et récupèreainsi le texte clair. Un attaquant (ou ennemi) passifécoute la communication et tente à partir duchiffré une cryptanalyse afin de le décrypter.


I-2.1 Chiffrement (suite)

• Chiffrement à clé secrète• Chiffrement à flot• Chiffrement par bloc

• Chiffrement à clé publique


I-2.1.1 Chiffrement à clé secrète

Dans un système a cl e secr ete ou sym etrique unexpediteur et un destinataire partagent une mêmecl e secr ete. Cette clé est utilisée à la fois pour lechiffrement et pour le dechiffrement et doit restersecrète de tout observateur ennemi . Le systèmeconsiste en une fonction de chiffrement publiqueC et en une fonction de déchiffrement publique D.


I-2.1.1 Chiffrement à clé secrète (suite)

La fonction C prend en entrée la clé secrète K etun texte clair x et renvoie en sortie le texte chiffréy = C(K,x). La fonction D prend en entrée la clésecrète K et le chiffré y et renvoie le texte clairx = D(K, y).



A chaque clé K sont associées une fonction dechiffrement CK = C(K, .) et une fonction dedéchiffrement DK = D(K, .). L’expéditeur chiffrele texte clair x pour obtenir le texte chiffr e (oucryptogramme) y = CK(x) et envoie y audestinataire. Le destinataire rétablit le texte clairen calculant x = DK(y). Autrement ditDK ◦ CK = Id.Les fonctions CK et DK sont secrètes.



Les problèmes difficiles principaux liés à un telsystème sont : echanger la cl e secr ete, la stocker ,eviter de l’exposer lors de son utilisation pourchiffrer ou déchiffrer. Le problème d’échange dela clé est spécifique de la cryptographie à clésecrète. La clé doit être communiquée par uncanal sûr. L’utilisation d’une clé secrètes’accompagne de la notion de sph ere de confiancepour le partage de la clé. Le partage de clés quiest acceptable en réseau fermé n’est plusenvisageable en réseau ouvert.


I-2.1.1.1 Chiffrement à flot

Une méthode de chiffrement à flot opereindividuellement sur chaque bit de texte clair enutilisant une transformation qui varie en fonctionde la place du bit d’entrée.

Le cryptosyst eme de Vernam appelé aussione-time-pad ou encore masque jetable est leprototype de ces systèmes. Il utilise une clésecrète très longue qui devrait de manière idéalereprésenter une suite aléatoire de bits.


I-2.1.1.1 Chiffrement à flot (suite)

Si on a un message m de n bits à chiffrer, onconsidère les n premiers bits de la clé quiconstituent un mot K et on calcule le "ou exclusifbit à bit" entre le message et cette partie de laclé, c’est-à-dire que le texte chiffré s’écrit sous laforme c = m ⊕ K. Le destinataire qui partage lamême clé extrait de la même façon la partie K etrécupère alors le texte clair m en calculantm = c ⊕ K. Les deux interlocuteurs jettent lapartie K utilisée et peuvent effectuer unenouvelle transaction.



0 1 1 0 1 0 1 1 1 1 0 . . . . . . . . . . . . . .

1 1 1 0 0 1 0

1 0 0 0 11 1

clé

texte clair

texte chiffré

partie utilisée nouvelle clé

m

K

c=m XOR K

Figure 1: Le one-time pad



Construire une clé aussi longue et qui de plussoit une suite aléatoire de bits n’est pas chosefacile. Il est possible de réaliserapproximativement un tel système, à partir d’ungenerateur pseudo-al eatoire et d’un germe .


I-2.1.1.2 Chiffrement par bloc

Un système de chiffrement par bloc opère avecune transformation fixe qui s’applique sur desblocs de texte clair, de taille fixe.

ENTREE SORTIE

CLE

Block

Cipher


I-2.1.1.2 Chiffrement par bloc (suite)

• DES (Data Encryption Standard). C’est lestandard ANSI X3.92, proposé en 1974,publié dans le Federal Register en 1975,adopté comme standard en 1977 (FIPS-46).Il utilise une clé de 56 bits, des données de 64bits. Ce système est maintenant considérécommme trop faible (taille trop petite desclés). Il est encore utilisé principalement dansle 3-DES.



• 3-DES. Appelé encore Triple DES, c’est lestandard ANSI X9.71 et ISO 9732 (1985). Oncompose 3 circuits précédents de la façonsuivante : on utilise deux clés DES k1 et k2 .On chiffre le texte clair avec k1 on déchiffre lasortie avec k2 et on chiffre cette deuxièmesortie avec k1. On a donc 112 bits de clé, uneentrée de 64 bits et une sortie de 64 bits.

• MISTY1. Il utilise une clé de 128 bits et chiffredes blocs de données de 64 bits. La sortie estaussi un bloc de 64 bits.



• IDEA (International Data EncryptionAlgorithm). Proposé en 1992 par Lai etMassey. Il utilise une clé de 128 bits, desdoneées de 64 bits.

• AES (Advanced Encryption Standard).Standard américain qui remplace le DES.Proposé en 1998 par J. Daemen et V. Rijmensous le nom de Rijndael, retenu en partie parle NIST en 2000. Standard FIPS-197 en2001. Les données sont de 128 bits, les clés :128, 196 ou 256 bits.



• Camellia . Ce système offre aussi un choixpour la taille des clés : 128, 196 ou 256 bits.La taille des textes clairs et chiffrés est fixée à128 bits.

• SHACAL-2 . Il utilise une clé secrète de 512 bitset travaille sur des blocs de 256 bits.

MISTY1, AES (version 128 bits de données),Camellia, SHACAL-2 ont été retenus par le projeteuropéen NESSIE (New European Schemes forSignatures, Integrity, and Encryption).


I-2.1.2 Chiffrement à clé publique

En 1976, Diffie et Hellman introduisent l’idée desystème cryptographique à clé publique. En1977, Rivest, Shamir et Adleman proposent lesystème cryptographique RSA. Aujourd’hui, ilexiste divers systèmes à clé publique. Dans uncryptosystème à clé publique, chaque utilisateurA dispose d’une paire de clés : une cl e priv ee dA

et une cl e publique eA. La clé privée de A n’estconnue que de A. La clé publique est publiée etconnue de tous.


I-2.1.2 Chiffrement à clé publique (suite)

Il doit, bien entendu, être impossible en pratiquede calculer dA à partir de eA. On dispose enoutre d’une fonction publique de chiffrement Equi à une clé eA et un texte clair x faitcorrespondre y = E(eA, x), le chiffré de x àdestination de A. On dispose également d’unefonction publique de déchiffrement D qui à la cléprivée dA de A et à un chiffré y à destination deA fait correspondre x = D(dA, y), le texte clairassocié à y. Remarquons que seule la clé privéeest secrète; les fonctions E et D sont publiques.



Notons EA = E(eA, .) la fonction de chiffrement àdestination de A et DA = D(dA, .) la fonction dedéchiffrement de A. Donc

DA ◦ EA = Identité.

Si l’expéditeur B veut communiquer le texte clairm à A, il calcule le texte chiffré c = EA(m) enutilisant la clé publique de A, et il envoie c à A.Le destinataire A retrouve le texte clair encalculant m = DA(c) grâce à sa clé privée.



L’existence d’un tel cryptosystème est basée surla possibilité de construire des paires defonctions réciproques l’une de l’autre, EA et DA,qui sont faciles à calculer et où EA est très dureà inverser. Les systèmes à clé publique reposentsur la difficulté d’effectuer en pratique certainscalculs.

Dans un tel système il n’y a pas de clé secrète àéchanger : la clé privée ne sort pas de chez A etla clé publique est connue de tous.



Il reste les problèmes de gestion de clé :

• comment éviter que la clé publique soitcorrompue par une attaque malveillante duserveur de clés ou même forgée?

• comment éviter que la clé privée soitexposée, soit lorsqu’elle est stockée(faiblesse du moyen de stockage), soit lors deson utilisation (inspection de la mémoire de lamachine utilisant la clé, virus malveillants,etc)?



• RSA (Rivest-Shamir-Adleman). Ce systèmeest basé sur la difficulté de factoriser unproduit de deux nombres premiers. Associé àl’encodage KEM (Key EncapsulationMechanism) il a été retenu par le projetNESSIE. Associé à OAEP (OptimalAsymmetric Encryption Padding) c’est lestandard de RSALAB.

• ElGamal . Ce système est basé sur la difficultédu problème du logarithme discret danscertains groupes.



• PSEC (Provable Secure Elliptic CurveEncryption). Ce chiffrement utilise le calculsur le groupe des points d’une courbeelliptique. Associé à KEM, il a été égalementretenu par le projet NESSIE.

• Rabin . Ce système est basé sur la difficultéd’extraire une racine carrée modulo unproduit n de deux grands nombres premiers.

• McEliece . Ce système est basé sur la difficultédu décodage d’un code correcteur linéairebinaire quelconque.


I-2.2 Signature

Un algorithme de signature numérique aplusieurs volets.

1) Un condens e du message est calculé avecune fonction de hachage publique h. Lemessage M est transformé en un messagem = h(M) de longueur fixée.

2) Chaque utilisateur A dispose d’une clépublique eA et d’une clé privée dA. Une fonctionde signature S fait correspondre à une clé privéedA et à un message condensé m un appendices = S(dA,m).


I-2.2 Signature (suite)

L’utilisateur A, qui veut signer un message M ,commence par en faire un condensé m = h(M),puis il calcule, grâce à sa clé privée, l’appendices = S(dA,m). Il peut alors transmettre sonmessage signé (M, s). Le destinataire utilise lafonction de vérification V qui à une clé publiqueeA, et à un message signé (M, s) faitcorrespondre V(eA,M, s), valant "vrai" si (M, s)correspond bien à un message signé par A et"faux" sinon.



Remarquons que le processus de signatureimplique la non-r epudiation . En effet, puisque toutle monde connaît la clé publique de A, tout lemonde peut s’assurer que la signature est bienconforme. Comme A est le seul à avoir accès àla fonction SA = S(dA, .), tout le monde peuts’assurer que c’est bien A qui a signé lemessage M . Il existe aussi des signatures arecouvrement de message dans lesquels lemessage est récupéré à partir de la signature.



• RSA (Rivest-Shamir-Adleman). C’estl’algorithme RSA utilisé "à l’envers" : celui quisigne, chiffre avec sa clé privée. Tout lemonde peut vérifier avec la clé publique decelui qui a signé. La signature RSA associéeà l’encodage PSS (Probabilistic SignatureScheme) a été retenu par le projet NESSIE.



• DSS (Digital Signature Standard) Utilise DSA(Digital Signature Algorithm) basé sur ladifficulté du problème du logarithme discretsur le groupe multiplicatif Z/pZ (p étant ungrand nombre premier). D’autres alternativessont possibles dans le standard DSS : onpeut utiliser aussi ECDSA (Elliptic CurveDigital Signature Algorithm) basé sur ladifficulté du problème du logarithme discretsur le groupe des points d’une courbeelliptique, ou encore RSA. Le standardECDSA a été retenu par le projet NESSIE.


I-2.3 Authentification

L’authentification est un mécanisme qui couvreplusieurs fonctionnalités voisines. Il garantit quel’expéditeur d’un message est bien celui qu’ilprétend être et que le message n’est pascorrompu ou forgé (identification et intégrité desdonnées). On peut penser à utiliser unprocessus de signature pour obtenirl’authentification. La signature demande desfonctionnalités différentes de celles del’authentification. L’authentification ne requiertpas la non-répudiation.



• Il est possible de construire des MAC(Message Autentication Code) en utilisantdes systèmes de chiffrement par bloc à clésecrète (DES, AES).

• Le système d’authentification deFeige-Fiat-Shamir qui fournit un processusd’identification basé sur la difficulté del’extraction d’une racine carrée modulo n,lorsque n est un nombre composé et que safactorisation n’est pas connue.



• UMAC (retenu par le projet NESSIE). Laconception de ce système utilise une familletrès intéressante de fonctions de hachage.

• Certains systèmes d’identification mutuellesont basés sur des protocoles d’échanges designatures.

• Plus généralement, les preuves de savoir,éventuellement à divulgation nulle.


I-2.4 Échange de clés

• Utilisation de chiffrement (par exemple RSA)

• Diffie-Hellman . Ce système qui permetd’échanger des clés a été le premierprotocole utilisant le principe de lacryptographie à clé publique.


I-3. Techniques mathématiques

• Fonctions .⊲ Fonctions a sens unique

⊲ Fonctions a sens unique avec trappe

⊲ Fonctions de hachage

• Arithm etique et alg ebre .⊲ Arithmetique dans Z et dans Z/nZ

⊲ Les corps finis et les courbes elliptiques sur lescorps finis

• Generateurs pseudo-al eatoires .

• Complexit e des algorithmes .Formation Generale en Cryptographie – p. 44

I-3.1 Fonction à sens unique

Une fonction a sens unique est une fonction qui estfacile a calculer et difficile a inverser (c’est-à-direque f−1(y) est difficile à calculer en pratique pour"presque tout" y). Les significations exactes de"facile" et "difficile" dans la définition précédentedemandent quelques notions de th eorie de lacomplexit e des algorithmes .

Exemples: fonction RSA, fonction puissancemodulo p.


I-3.1 Fonction à sens unique avec trappe

Une fonction a sens unique avec trappe est unefonction à sens unique, mais qui devient facile àinverser si on connaît un secret (la trappe).

Exemple: fonction RSA.


I-3.2 Fonction de hachage

Une fonction de hachage transforme unmessage de taille quelconque en un resum e courtde taille fixe . L’image d’un message par unefonction de hachage s’appelle le condens e dumessage, l’empreinte du message, le resum e dumessage ou encore le message hach e. Unefonction de hachage n’est surement pasinjective, cependant elle doit en pratique vérifierles conditions suivantes :


I-3.2 Fonction de hachage (suite)

• resistance a la determination d’une pr e-image , cequi signifie qu’ il doit être impossible enpratique , à partir d’un résumé m, de retrouverun message M ayant ce résumé, i.e. tel quem = h(M).

• resistance aux collisions , ce qui signifie qu’il estimpossible en pratique de construire deuxmessages M1 et M2 ayant le même résumé :h(M1) = h(M2).



• SHA1 (Secure Hash Algorithm), qui fournit ensortie un bloc de 160 bits.

• MD5 (Message Digest), qui donne uneempreinte sur 128 bits.

• SHA-256, SHA-384, SHA-512 . Ce sont desaméliorations de SHA1 de manière à fournirune résistance aux attaques brutalescomparable à la résistance des diversesversions de AES (SHA-256 à mettre enrapport avec AES-128, etc). Le projetNESSIE les a retenues.



• Whirlpool . Cette fonction a une sortie de 512bits. Whirlpool a été retenu par le projetNESSIE.

• Utilisation de systèmes de chiffrement parbloc (par exemple AES).


I-4. Les mises en œuvre, les protocoles

• PGP.

• SSH .

• Station to station protocol .

• Kerberos .

• SSL.


I-5. La normalisation

• l’ISO (International Standards Organization),

• l’ITU (International Telecommunication Union),

• l’ANSI (American National Standards Institute),

• l’ECMA (European Computer ManufacturersAssociation),

• l’IEEE (Institute of Electrical and ElectronicsIngineers),


I-5. La normalisation (suite)

• le NIST (National Institute of Standards andTechnology),

• l’AFNOR (Association Française pour laNORmalisation).

Dans le cas de l’Internet, les standards sontappelés des RFC (Request For Comments). Ilpeut s’agir de définitions de protocoles, deprojets, de compte-rendus de réunions, despécifications de standards, etc.


I-5. La normalisation (suite)

Les RFC sont des documents publics,accessibles par exemple surhttp://www.rfc-editor.org. Il en existe deuxsous-catégories notables, les STD et les FYI : lesSTD sont les standards officiels et les FYI sontles documents d’apprentissage (For YourInformation). Les "drafts" sont les documentsdes groupes de travail, généralement mis à ladisposition de tous et sur lesquels chacun peutémettre des remarques et suggestions.


Documents

Formation Générale en Cryptographierobert.rolland.acrypta.com/telechargements_crypto/fgc/fgc.pdf · (norme ISO 7498-2). Lors d’une communication, il s’agit d’empêcher un