Le chiffrement par substitution consiste à remplacer dans un message une ou plusieurs entités (généralement des lettres) par une ou plusieurs autres entités.

On distingue généralement plusieurs types de cryptosystèmes par substitution:

• La substitution monoalphabétique consiste à remplacer chaque lettre du message par une autre lettre de l'alphabet
• La substitution polyalphabétique consiste à utiliser une suite de chiffres monoalphabétique réutilisée périodiquement
• La substitution homophonique permet de faire correspondre à chaque lettre du message en clair un ensemble possible d'autres caractères
• La substitution de polygrammes consiste à substituer un groupe de caractères (polygramme) dans le message par un autre groupe de caractères

Ce code de chiffrement est un des plus anciens, dans la mesure où Jules César l'aurait utilisé. Le principe de codage repose sur l'ajout d'une valeur constante à l'ensemble des caractères du message, ou plus exactement à leur code ASCII(pour une version "informatique" de ce codage).

Il s'agit donc simplement de décaler l'ensemble des valeurs des caractères du message d'un certain nombre de positions, c'est-à-dire en quelque sorte de substituer chaque lettre par une autre. Par exemple, en décalant le message "COMMENT CA MARCHE" de 3 positions, on obtient "FRPPHQW FD PDUFKH". Lorsque l'ajout de la valeur donne une lettre dépassant la lettre Z, il suffit de continuer en partant de A, ce qui revient à effectuer un modulo 26.
A titre d'exemple, dans le film L'odyssée de l'espace, l'ordinateur porte le nom de HAL. Ce surnom est en fait IBM décalé de 1 position vers le bas...

On appelle clé le caractère correspondant à la valeur que l'on ajoute au message pour effectuer le cryptage. Dans notre cas la clé est C, car c'est la 3^ème lettre de l'alphabet.

Ce système de cryptage est certes simple à mettre en oeuvre, mais il a pour inconvénient d'être totalement symétrique, cela signifie qu'il suffit de faire une soustraction pour connaître le message initial. Une méthode primaire peut consister à une bête soustraction des nombres 1 à 26 pour voir si l'un de ces nombres donne un message compréhensible.
Une méthode plus évoluée consiste à calculer les fréquences d'apparition des lettres dans le message codé (cela est d'autant plus facile à faire que le message est long). Effectivement, selon la langue, certaines lettres reviennent plus couramment que d'autres (en français, par exemple, la lettre la plus utilisée est la lettre E), ainsi la lettre apparaissant le plus souvent dans un texte crypté par le chiffrage de César correspondra vraisemblablement à la lettre E, une simple soustraction donne alors la clé de cryptage...

Dans le cas spécifique du chiffrement de Jules César où la clé de cryptage est N (13^ème lettre de l'alphabet), on appelle ce cryptage ROT13 (le nombre 13, la moitié de 26) a été choisi pour pouvoir crypter et décrypter facilement les messages...).

Les méthodes de chiffrement par transposition consistent à réarranger les données à crypter de telle façon à les rendre incompréhensibles. Il s'agit généralement de réarranger géométriquement les données pour les rendre visuellement inexploitables.

Cette technique de cryptage est vraisemblablement la première preuve de l'utilisation de moyens de chiffrement en Grèce dès 600 avant Jésus Christ pour dissimuler des messages écrits sur des bandes de papyrus.

La technique consistait à:

• enrouler une bande de papyrus sur un cylindre appelé scytale
• écrire le texte longitudinalement sur la bandelette ainsi enroulée (le message dans l'exemple ci-dessus est "comment ça marche")

Le chiffrement symétrique (aussi appelé chiffrement à clé privée ou chiffrement à clé secrète) consiste à utiliser la même clef pour le chiffrement que pour le déchiffrement.

Le chiffrement consiste alors à effectuer une opération entre la clé privée et les données à chiffrer afin de rendre ces dernières inintelligibles. Ainsi, le moindre algorithme (tel qu'un OU exclusif) peut rendre le système quasiment inviolable (la sécurité absolue n'existant pas).

Toutefois, dans les années 40, Claude Shannon démontra que pour être totalement sûr, les systèmes à clefs privées doivent utiliser des clefs d'une longueur au moins égale à celle du message à chiffrer. De plus le chiffrement symétrique impose d'avoir un canal sécurisé pour l'échange de la clé, ce qui dégrade sérieusement l'intérêt d'un tel système de chiffrement.

Ainsi, dans les années 20, Gilbert Vernam et Joseph Mauborgne mirent au point la méthode du one time pad (traduisez méthode du masque jetable), basée sur une clé privée générée aléatoirement, utilisée une et une seule fois, puis détruite. Ainsi à la même époque le Kremlin et la Maison Blanche étaient reliés par le fameux téléphone rouge, c'est-à-dire un téléphone dont les communications étaient cryptées par une clé privée selon la méthode du masque jetable. La clé privée était alors échangée grâce à la valise diplomatique (jouant le rôle de canal sécurisé).

Le principal inconvénient d'un cryptosystème à clefs secrètes provient de l'échange des clés. En effet, le chiffrement symétrique repose sur l'échange d'un secret (les clés). Ainsi, se pose le problème de la distribution des clés :

Pour un groupe de n personnes utilisant un cryptosystème à clés secrètes, il est nécessaire de distribuer n x (n-1) / 2 clés.

Le paradigme de chiffrement à clés publiques est apparu en 1976, avec la publication d'un ouvrage sur la cryptographie par Whitfield Diffie et Martin Hellman.

Dans un cryptosystème asymétrique (aussi appelé cryptosystème à clés publiques), les clés existent par paires (on parle souvent de bi-clés):

• Une clé publique pour le chiffrement
• Une clé secrète pour le déchiffrement

Ainsi, dans un système de chiffrement à clé publique, les utilisateurs choisissent une clé aléatoire dont ils sont seuls connaisseurs (il s'agit de la clé privée). A partir de cette clé, ils déduisent chacun automatiquement un algorithme (il s'agit de la clé publique). Les utilisateurs s'échangent cette clé publique au travers d'un canal non sécurisé.

Lorsqu'un utilisateur désire envoyer un message à un autre utilisateur, il lui suffit de chiffrer le message à envoyer au moyen de la clé publique du destinataire (qu'il trouvera par exemple dans un serveur de clés tel qu'un annuaire). Ce dernier sera en mesure de déchiffrer le message à l'aide de sa clé privée (qu'il est seul à connaître).

Ce système est basé sur une fonction facile à calculer dans un sens (appelée fonction à trappe à sens unique ou en anglais one-way trapdoor function), mais qui est mathématiquement très difficile à inverser sans la clé privée (appelée trappe).

Pour faire une image avec le "monde réel", il s'agit pour un utilisateur de créer une clé aléatoire (la clé privée), puis de fabriquer un grand nombre de cadenas (clé publique) qu'il dispose dans un casier accessible par tous (le casier joue le rôle de canal non sécurisé). Pour lui faire parvenir un document, chaque utilisateur peut prendre un cadenas (ouvert), fermer une valisette contenant le document grâce à ce cadenas, puis envoyer la valisette au propriétaire de la clé publique (le cadenas). Seul le propriétaire sera alors en mesure d'ouvrir la valisette avec sa clé privée.

Le problème consistant à se communiquer la clé de déchiffrement n'existe plus, les clés publiques pouvant être envoyées librement. Le chiffrement par clés publiques permet donc à des personnes de s'échanger des messages cryptés sans pour autant possèder de secret en commun. En contrepartie tout le challenge consiste à (s')assurer que la clé publique que l'on récupère est bien celle de la personne à qui l'on souhaite faire parvenir l'information chiffrée !

Les algorithmes asymétriques (entrant en jeu dans les cryptosystèmes à clé publique) permettent de s'affranchir de problèmes liés à l'échange de clé via un canal sécurisé. Toutefois, ces derniers restent beaucoup moins efficaces (en terme de temps de calcul) que les algorithmes symétriques.

Ainsi, la notion de clé de session est un compromis entre le chiffrement symétrique et asymétrique permettant de combiner les deux techniques.

Le principe de la clé de session est simple : il consiste à générer aléatoirement une clé de session de taille raisonnable, et de chiffrer celle-ci à l'aide d'un algorithme de chiffrement à clef publique (plus exactement à l'aide de la clé publique du destinataire).

Le destinataire est en mesure de déchiffrer la clé de session à l'aide de sa clé privée. Ainsi, expéditeur et destinataires sont en possession d'une clé commune dont ils sont seuls connaisseurs. Il leur est alors possible de s'envoyer des documents chiffrés à l'aide d'un algorithme de chiffrement symétrique.

L'algorithme de Diffie-Hellman (du nom de ses inventeurs Diffie et Hellman) a été mis au point en 1976 afin de permettre l'échange de clés à travers un canal non sécurisé. Il repose sur la difficulté du calcul du logarithme discret dans un corps fini.

L'algorithme de Diffie-Hellman est cependant sensible à l'attaque "Man in the middle" (traduit parfois en "attaque de l'intercepteur" ou "attaque par le milieu".

Le paradigme de signature électronique (appelé aussi signature numérique) est un procédé permettant de garantir l'authenticité de l'expéditeur (fonction d'authentification), ainsi que de vérifier l'intégrité du message reçu.

La signature électronique assure également une fonction de non-répudiation, c'est-à-dire qu'elle permet d'assurer que l'expéditeur a bien envoyé le message (autrement dit elle empêche l'expéditeur de nier avoir expédié le message).

Une fonction de hachage (parfois appelée fonction de condensation) est une fonction permettant d'obtenir un condensé (appelé aussi haché) d'un texte, c'est-à-dire une suite de caractères assez courte représentant le texte qu'il condense. La fonction de hachage doit être telle qu'elle associe un et un seul haché à un texte en clair (cela signifie que la moindre modification du document entraîne la modification de son haché). D'autre part, il doit s'agir d'une fonction à sens unique (one-way function) afin qu'il soit impossible de retrouver le message original à partir du condensé.

Ainsi, le haché représente en quelque sorte l'empreinte digitale (en anglais finger print) du document.

Les algorithmes de hachage les plus utilisés actuellement sont :

• MD5 (MD signifiant Message Digest), créant une empreinte digitale de 128 bits. Il est courant de voir des documents en téléchargement sur Internet accompagnés d'un fichier MD5, il s'agit du condensé du document permettant de vérifier l'intégrité de ce dernier)
• SHA (pour Secure Hash Algorithm, pouvant être traduit par Algorithme de hachage sécurisé) créant des empreintes d'une longueur de 160 bits

En expédiant un message accompagné de son haché, il est possible de garantir l'intégrité d'un message, c'est-à-dire que le destinataire peut vérifier que le message n'a pas été altéré (intentionnellement ou de manière fortuite) durant la communication.

Lors de la réception du message, il suffit au destinataire de calculer le haché du message reçu et de le comparer avec le haché accompagnant le document. Si le message (ou le haché) a été falsifié durant la communication, les deux empreintes ne correspondront pas.

L'utilisation d'une fonction de hachage permet de vérifier que l'empreinte correspond bien au message reçu, mais rien ne prouve que le message a bien été envoyé par celui que l'on croit être l'expéditeur.

Ainsi, pour garantir l'authentification du message, il suffit à l'expéditeur de chiffrer (on dit généralement signer) le condensé à l'aide de sa clé privée (le haché signé est appelé sceau) et d'envoyer le sceau au destinataire.

A réception du message, il suffit au destinataire de déchiffrer le sceau avec la clé publique de l'expéditeur, puis de comparer le haché obtenu avec la fonction de hachage au haché reçu en pièce jointe. Ce mécanisme de création de sceau est appelé scellement.

Les algorithmes de chiffrement asymétrique sont basé sur le partage entre les différents utilisateurs d'une clé publique. Généralement le partage de cette clé se fait au travers d'un annuaire électronique (généralement au format LDAP) ou bien d'un site web.

Toutefois ce mode de partage a une grande lacune : rien ne garantit que la clé est bien celle de l'utilisateur a qui elle est associée. En effet un pirate peut corrompre la clé publique présente dans l'annuaire en la remplaçant par sa clé publique. Ainsi, le pirate sera en mesure de déchiffrer tous les messages ayant été chiffrés avec la clé présente dans l'annuaire.

Ainsi un certificat permet d'associer une clé publique à une entité (une personne, une machine, ...) afin d'en assurer la validité. Le certificat est en quelque sorte la carte d'identité de la clé publique, délivré par un organisme appelé autorité de certification (souvent notée CA pour Certification Authority).

L'autorité de certification est chargée de délivrer les certificats, de leur assigner une date de validité (équivalent à la date limite de péremption des produits alimentaires), ainsi que de révoquer éventuellement des certificats avant cette date en cas de compromission de la clé (ou du propriétaire).

Les certificats sont des petits fichiers divisés en deux parties :

• La partie contenant les informations
• La partie contenant la signature de l'autorité de certification

La structure des certificats est normalisée par le standard X.509 de l'UIT, qui définit les informations contenues dans le certificat :

• Le nom de l'autorité de certification
• Le nom du propriétaire du certificat
• La date de validité du certificat
• L'algorithme de chiffrement utilisé
• La clé publique du propriétaire

L'ensemble de ces informations (informations + clé publique du demandeur) est signé par l'autorité de certification, cela signifie qu'une fonction de hachage crée une empreinte de ces informations, puis ce condensé est chiffré à l'aide de la clé privée de l'autorité de certification; la clé publique ayant été préalablement largement diffusée afin de permettre aux utilisateurs de vérifier la signature avec la clé publique de l'autorité de certification.

Lorsqu'un utilisateur désire communiquer avec une autre personne, il lui suffit de se procurer le certificat du destinataire. Ce certificat contient le nom du destinataire, ainsi que sa clé publique et est signé par l'autorité de certification. Il est donc possible de vérifier la validité du message en appliquant d'une part la fonction de hachage aux informations contenues dans le certificat, en déchiffrant d'autre part la signature de l'autorité de certification avec la clé publique de cette dernière et en comparant ces deux résultats.

Le chiffrement de Vigenère est un cryptosystème symétrique, ce qui signifie qu'il utilise la même clé pour le chiffrement et le déchiffrement. Le chiffrement de Vigenère ressemble beaucoup au chiffrement de César, à la différence près qu'il utilise une clef plus longue afin de pallier le principal problème du chiffrement de César: le fait qu'une lettre puisse être codée d'une seule façon. Pour cela on utilise un mot clef au lieu d'un simple caractère.
On associe dans un premier temps à chaque lettre un chiffre correspondant.

Il consiste à coder un texte avec un mot en ajoutant à chacune de ses lettres la lettre d'un autre mot appelé clé. La clé est ajoutée indéfiniment en vis-à-vis avec le texte à chiffrer, puis le code ASCII de chacune des lettres de la clé est ajouté au texte à crypter. Par exemple le texte "rendezvousamidi" avec la clé bonjour sera codé de la manière suivante:

Texte original:

Clé:

Texte crypté

Pour déchiffrer ce message il suffit d'avoir la clé secrète et faire le déchiffrement inverse, à l'aide d'une soustraction.

Bien que ce chiffrement soit beaucoup plus sûr que le chiffrement de César, il peut encore être facilement cassé. En effet, lorsque les messages sont beaucoup plus longs que la clef, il est possible de repérer la longueur de la clef et d'utiliser pour chaque séquence de la longueur de la clef la méthode consistant à calculer la fréquence d'apparition des lettres, permettant de déterminer un à un les caractères de la clef...

Pour éviter ce problème, une solution consiste à utiliser une clef dont la taille est proche de celle du texte afin de rendre impossible une étude statistique du texte crypté. Ce type de système de chiffrement est appelé système à clé jetable. Le problème de ce type de méthode est la longueur de la clé de cryptage (plus le texte à crypter est long, plus la clef doit être volumineuse), qui empêche sa mémorisation et implique une probabilité d'erreur dans la clé beaucoup plus grande (une seule erreur rend le texte indéchiffrable...).

N’accordez jamais une confiance aveugle à un système de cryptographie " - Gilles Dubertret

C'est à la fin de la première guerre mondiale qu'est apparue la nécessité de crypter les messages (bien que les techniques de chiffrement existaient déjà depuis fort longtemps).
C'est un Hollandais résidant en Allemagne, le Dr Arthur Scherbius qui mit au point à des fin commerciales la machine Enigma, servant à encoder des messages.
Le modèle A de la machine (Chieffrienmaschinen Aktien Gesellschaft) fût présentée en 1923 au Congrès Postal International de Bern. Le prix de cette machine à l'époque (équivalent à 30000 euros aujourd'hui) en fit un échec cuisant. Mais l'idée fit son chemin et la marine de guerre allemande reprit le projet en 1925 et en confia son évolution au service de chiffrement (Chiffrierstelle) du ministère de la guerre allemand. Le modèle Enigma M3 fût finalement adopté par la Wehrmacht (armée Allemande) le 12 janvier 1937.

Ce que les Allemands ignoraient, c'est que les services de contre-espionnage français et Polonais travaillaient également depuis 1930 sur une méthode de déchiffrement. Le Commandant Gustave Bertrand des services secrets français, recruta pour cela Hans Thilo Schmidt (dont le nom de code était Asche), qui travaillait à l'époque pour le Chiffrierstelle.
 

Lorsque la seconde guerre mondiale éclata en 1939, les alliés savaient décrypter les messages d'Enigma. Le 24 juillet 1939, Marian Rejewski ( responsable du Biuro Szyfrow - service européen le plus avancé dans les recherches sur le chiffrement allemand ) remit un modèle de la machine Enigma au Commandant Bertrand et à Alistair Denniston, chef du service de déchiffrement de l'Intelligence Service (IS) britannique.
La guerre s'intensifia et la cadence de déchiffrement augmenta. Ainsi entre les mois d'octobre et juin 1939, plus de 4000 messages chiffrés furent décodés par les services secrets français.
Ces opérations portaient désormais un nom : Opération Z pour les français et Code Ultra (pour Ultra Secret) pour les Anglais.

En Août 1939 les Anglais installèrent à Bletchley Park (80 km de Londres) les services du Code et du Chiffre. Ce n'étaient pas moins de 12000 scientifiques et mathématiciens Anglais, Polonais et français qui travaillaient à "casser" le code d'Enigma.
Parmi ces mathématiciens, on retrouve l'un des inventeurs de l'informatique moderne : Alan Turing, qui dirigeait tous ces travaux.

Les messages décryptés à Bletchley Park arrivaient par tapis roulant à la Huts 6, puis, au poste pour être traduits (2 postes par équipe) :

• un pour les messages en retard
• un pour le matériel urgent

• un au SIS de Broadway
• un au service de ministère approprié ou à Withehall
• un au général concerné sur le terrain.

Les Anglais réussirent ainsi à déchiffrer ces messages codés. Seulement, la Kriegsmarine ( Marine de guerre Allemande), utilisant des mesures de cryptage différentes, le déchiffrement s'avèra plus difficile. La capture sur le U-110 d'une Enigma et surtout de ses instructions permit une avancée importante. Ceci permettant de connaître les positions de sous-marins et de réduire le tonnage coulé par les U-Boot (Cf : Le film U-571).
Le 1^er février 1942, le modèle Enigma M4 fut mis en service. Pendant onze mois, les alliés ne réussirent pas à décrypter ces messages.

Durant toute la guerre, plus de 18 000 messages par jours furent décryptés, et permirent aux forces de l'alliance de connaître les intentions de l'Allemagne.
Le dernier message chiffré fut trouvé en Norvège, signé par l'Amiral Doenitz : " Le Führer est mort. Le combat continue ".
Les Allemands ne se sont jamais doutés que leur précieuse machine pouvait être décryptée.
 

Source :

• Mémorial de Caen : http://www.memorial.fr/index2.htm
• http://www.chronicus.com/sgm/dossgm/Enigma.htm

Enigma avait un fonctionnement de cryptage particulièrement simple.
L'objet était équipé d'un clavier pour la saisie du message, de différentes roues pour le codage, et enfin d'un tableau lumineux pour le résultat.
A chaque pression d'une touche du clavier, une lettre du panneau lumineux s'illuminait.
Il y avait 3 roues de codage appelées "Brouilleur Rotor" qui reliaient le clavier au panneau lumineux.
 

Exemple avec un seul rotor :
Lorsque l'on appuie sur B le courant passe par le rotor et allume A sur le panneau lumineux :

Pour complexifier la machine, à chaque pression sur une touche, le rotor tourne d'un cran.
 

Exemple, rotation du rotor:
Apres la première pression on a :

Suivant les modèles ( M3 ou M4), le système était muni de 3 ou 4 rotors. Les deuxième et troisième rotors avancaient d'un cran quand le premier avait fait un tour complet. Il y avait aussi un tableau de connexion qui mélangeait les lettres de l'alphabet et un réflecteur qui faisait repasser le courant dans les rotors avant l'affichage.
 

Troisième exemple :

------------------------------------------------------------------------------------------------ ----------------
Tableau lumineux | Clavier | Tableau de connexion | Rotor 1 | Rotor 2 | Rotor 3 | Réflecteur
-----------------------------------------------------------------------------------------------------------------
            A------------------a-------<------\/------>>----------------|
            B                           b------->------/\                                      |                  |-->>---|
            C                           c                        |                                     |---->>-----|            |
            D                          d                         |                                                                    |
            E                           e                         |------<--------|            |---<----------------+---<----|
            F                           f                                                  |---<---|                                |--->>---|
---------------------------------------------------------------------------------------------------------------
 

Au final, si l'on revient aux machines Enigma équipées pour 26 lettres, on a:
26 x 26 x 26 = 17 576 combinaisons liées à l'orientation de chacun des trois rotors,
6 combinaisons possibles liées à l'ordre dans lequel sont disposés les rotors,
100 391 791 500 branchements possibles quand on relie les six paires de lettres dans le tableau de connexions : il s'agit de choisir 12 lettres parmi 26 (26! /(12!14!)), puis 6 lettres parmi 12 (12!/6!), et puisque certaines paires sont équivalents (A/D et D/A), il s'agit de diviser par 2⁶.
Les machines Enigma peuvent donc chiffrer un texte selon 17 576 x 6 x 100 391 791 500 = 10¹⁶ combinaisons différentes !
 

Les Polonais inventèrent "la Bombe" (rebaptisée plus tard "Ultra") qui permettait de connaître les réglages Enigma. Seulement, à partir de 1938, c'est l'opérateur lui-même qui établissait le réglage. Pour remédier à ce problème, les polonais trouvèrent la solution: chaque message contenait soit une répétition de mots soit des mots récurrents (appelés "femelles"). Ceci était un indice quant au "noyau" (réglage de base des rotors). Pour découvrir ce réglage, les Polonais utilisaient ensuite la "Grille" (cartes perforées correspondant à toutes les permutations du noyau). Ces cartes étaient empilées les unes sur les autres par rapport à la position des "femelles". Ensuite, on cherchait le point où une série de perforations se recouvrait du haut en bas de la pile.