La cryptographie

TOGRAPHIE CLASSIQUE (à clés privées) Principe général - La connaissance de la méthode et de la clé de chiffrement et celle de la méthode et de la clé de déchiffrement se déduisent facilement l'une de l'autre. - Les deux méthodes et les clés sont connues de l'émetteur et du destinataire => L'émetteur et le destinataire doivent se mettre préalablement d'accord sur un secret (la clé) pour utiliser le chiffre. Deux problèmes - L'échange préalable à toute communication sécurisée d'un secret ("la distribution de clés)

Gérard FLORIN

CNAM-Cedric

6

- Dans un réseau de N entités susceptibles de communiquer secrètement il faut distribuer N*(N-1)/2 clés.

Gérard FLORIN

CNAM-Cedric

7

Les méthodes de chiffrement par substitution Principe général A chaque lettre ou groupe de lettres on substitue une autre lettre ou un autre groupe de lettres. La substitution simple (substitution mono alphabétique) Pour chaque lettre de l'alphabet de base on se donne une autre lettre utilisée dans le texte chiffré.

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

Exemple historique: Le chiffre de César

On décale les lettres de 3 positions

ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC

Gérard FLORIN

CNAM-Cedric

8

Les techniques d'attaque statistique - Analyse statistique des textes cryptés. - Détermination des fréquences d'apparition des symboles - Comparaison avec les fréquences types caractéristiques des langues Fréquences d'apparition (en anglais) Lettres E 13,05 T9,02 Digrammes Trigrammes TH 3,16 THE 4,72 IN 1,54 ING 1,42

Une analyse statistique d'un texte suffisamment long permet de casser un code mono ou même poly-alphabétique Le problème est de disposer: - de puissance de calcul - de suffisamment de texte en regard de la longueur des clés utilisées.

Gérard FLORIN CNAM-Cedric 9

La substitution poly-alphabétique - Une attaque est facile avec un seul alphabet. - On utilise une suite de chiffres mono alphabétiques. - La suite des chiffres mono alphabétiques est réutilisée périodiquement. Exemple : le chiffre de Vigenere On prend les 26 chiffres de César. Les chiffres associés aux 26 décalages possibles sont représentés par une lettre. Ex : chiffre avec décalage de k associé à la k iéme lettre de l'alphabet

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 Z B->C 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->

- On choisit une clé de répétition comme une suite de lettres: un mot ou une phrase ou un livre - Cette clé répétée indéfiniment vis à vis de chaque lettre d'un texte à chiffrer sert à déterminer le chiffre à utiliser.

Gérard FLORIN CNAM-Cedric 10

Autres substitutions Les substitutions homophoniques Au lieu d'associer un seul caractère crypté à un caractère en clair on dispose d'un ensemble de possibilités de substitution de caractères dans laquelle on choisit aléatoirement. Les substitutions de polygrammes Au lieu de substituer des caractères on substitue par exemple des digrammes (groupes de deux caractères) - Au moyen d'une table (système de Playfair) - Au moyen d'une transformation mathématique (système de Hill).

Gérard FLORIN

CNAM-Cedric

11

Les chiffres de substitution à longueur de clé égale à celle du texte (systèmes à clés jetables) - Pour éviter les attaques statistique il faut utiliser une substitution qui rend le texte crypté non analysable statistiquement. Exemple de solution: - Générer une clé qui est une suite binaire parfaitement aléatoire Phénomène physique aléatoire Le bruit électro magnétique - Pour chiffrer un message faire le ou exclusif du message et de la clé. - Si chaque clé ne sert qu'une fois le chiffre est incassable. Difficultés de la méthode - Volume des clés Devant être connu aux deux bouts. - Problème de synchronisation Si l'on perd une seule donnée on ne sait plus décrypter.

Gérard FLORIN CNAM-Cedric 12

Les méthodes de chiffrement par transposition Principe général On procède à un réarrangement de l'ensemble des caractères (une transposition) qui cache le sens initial. La technique est très peu résistante aux attaques statistiques. Exemple Le plus souvent on utilise deux visions géométriquement différentes du texte.

T E C TEC E R E R X S E T E T XSE TET

- On enroule une fine langue de papyrus ou de peau sur un tambour d'un diamètre donné (technique assyrienne 400 av JC). - On écrit horizontalement un texte sur la lamelle enroulée. - Quand la lamelle est déroulée les lettres sont incompréhensibles. - Pour décrypter le message il faut un cylindre du bon diamètre.

Gérard FLORIN CNAM-Cedric 13

Exemple de transposition à base matricielle - Le message en clair est écrit dans une matrice. - La clé est la matrice. - La technique de transposition de base consiste à lire la matrice en colonne. Exemple (6,5):

M E E E R S T A E N R S S S E A S P A C G R T O

Le message crypté est donc: MEERSE TAESS NRSEAS AC P GRTO

Gérard FLORIN

CNAM-Cedric

14

Chiffre à transposition avec chiffre à substitution simple. - On combine la transposition avec une substitution et on réarrange l'ordre des colonnes selon une permutation qui est ajoutée à la matrice pour former la clé. Exemple d'ordre d'exploration des colonnes 1 6 4 3 2 5, le texte crypté est: "MEERSGRTO SEAS SN NRE TAEAC P " - On peut générer et mémoriser simplement des permutations en prenant une clé sous forme d'un mot qui ne comporte pas deux fois la même lettre On numérote les colonnes dans l'ordre ou apparaissent les lettres du mot dans l'alphabet. Exemple ESPOIR correspond à la permutation 1 6 4 3 2 5.

Gérard FLORIN

CNAM-Cedric

15

Le DES "Data Encryption Standard" -Dès le début des années 1960 la technologie des circuits intégrés permet de travailler à des circuits combinatoires complexes permettant d'automatiser: la méthode de substitution. la méthode de transposition. => Idée d'appliquer ces techniques en cascade dans un produit de chiffres. - Mise au point à partir de 1968 d'une méthode de cryptage basée sur 16 étages de substitutions et transpositions basés sur des clés (IBM) - Appel d'offre NBS (1973) pour la mise au point d'un système de cryptographie - Proposition IBM (1975) - Adoption définitive et normalisation du DES d'IBM (1978) par le NBS ("National Bureau of Standards"). -Normalisation ANSI X3.92 connue sous le nom de DEA ("Data Encryption Algorithm").

Gérard FLORIN CNAM-Cedric 16

Principes Généraux du DES Choix possibles pour la sécurité - Méthodes simples de chiffrement et des clés très longues . Le DES - Produit de transpositions et substitutions nombreuses et compliquées pour une clé relativement courte => facilité de transport. - Les chiffres à substitution et à transposition sont faciles à réaliser en matériel. Les boîtes de transposition "P-Box" Les boites de substitution "S-Box"

Gérard FLORIN

CNAM-Cedric

17

Boîte de transposition (P - box "Permutation box") Exemple pour 8 bits (solution matérielle) 1 3

Le bit 1 remplace le 3 Facile à réaliser par simple câblage Autre solution (logicielle) par des tables Exemple de transposition sur 64 bits La permutation initiale du DES

58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

Le bit 1 remplace le 58

Gérard FLORIN

CNAM-Cedric

18

Boîte de substitution (S - box) Exemple de solution matérielle pour 3 bits

0 0 1 Demultiplexeur Transposition Multiplexeur 3 8 8 3 0 1 1

- Trois bits sélectionnent un fil en sortie - L'ensemble subit une transposition. - Le résultat