Cryptographie¶

La cryptographie est la science du secret. Les deux principaux types de cryptographie sont la cryptographie à clé secrète et la cryptographie à clé publique. Ces cryptosystèmes sont utilisés sur Internet, pour les cartes bancaires, la télévision cryptée…

Définition de la Cryptographie¶

La cryptographie est la "science des écritures secrètes". La cryptographie concerne l'étude et la conception de chiffrement des informations (cryptage). Elle concerne l 'ensemble des techniques utilisées pour protéger une communication au moyen d'un code graphique (secret).
Le chiffrement correspond à une opération de substitution et/ou de transposition de l'information. La substitution consiste par exemple au remplacement d'une lettre ou symbole par une autre lettre ou symbole. La transposition revient à changer l'ordre des lettres.
D'une information "claire" on passe à une information chiffrée et inintelligible appelée "cryptogramme".
Ce chiffrement repose sur des conventions : les "clés cryptographiques". Un système de cryptographie est basé sur un algorithme de codage appelé méthode et sur une ou plusieurs clés de sécurité.
La cryptographie c'est à la fois la méthode et la clé. L'union de la méthode et de la clé détermine la sécurité du système cryptographique.
Il existe diverses méthodes et clés cryptographiques. Il faut distinguer les méthodes et les clés cryptographiques. La méthode cryptographique est le modèle de conception d'un système cryptographique. La clé est une combinaison d'éléments (lettres ou symboles) qui vont permettre le déchiffrage du message, c'est une combinaison unique.

Applications de la cryptographie¶

Cartes Bancaires

Les banques font partie des premiers utilisateurs de systèmes cryptographies. Les cartes bancaires possèdent trois niveaux de sécurité :

Le code confidentiel : c'est la suite de chiffres à mémoriser et à saisir à l'abri des regards indiscrets.

La signature RSA : permet de vérifier l'identité de la carte sans avoir besoin de secrets; en d'autres termes, cette vérification peut se faire sans connexion à un centre distant.

L'authentification DES : apporte une preuve de légitimité de la carte, et se fait par connexion à un centre distant.

Navigateur Web

Les navigateurs, ou broswers, tels que Mozilla Firefox ou Internet Explorer, utilisent le protocole de sécurité SSL (Secure Sockets Layers), qui repose sur un procédé de cryptographie par clé publique : le RSA.

Histoire de la Cryptographie¶

Chiffre de césar
Le chiffre de César est la méthode de cryptographie la plus ancienne communément admise par l'histoire. Il consiste en une substitution mono-alphabétique : chaque lettre est remplacée("substitution") par une seule autre("mono-alphabétique"), selon un certain décalage dans l'alphabet ou de façon arbitraire.

La Scytale
Chez les Spartiates, la scytale, également connue sous le nom de bâton de Plutarque, était un bâton de bois utilisé pour lire ou écrire une dépêche chiffrés. Considérée comme le plus ancien dispositif de cryptographie militaire connue, elle permettait l'inscription d'un message chiffré sur une fine lanière de cuir ou de parchemin que le messager pouvait porter à sa ceinture.

Après avoir enroulé la ceinture sur la scytale, le message était écrit en plaçant une lettre sur chaque circonvolution. Pour le déchiffrer, le destinataire devait posséder un bâton d'un diamètre identique à celui utilisé pour l'encodage. Il lui suffisait alors d'enrouler la scytale autour de ce bâton pour obtenir le message en clair

LetterLocking

Définition Wikipedia
"Le Letterlocking est un système de protection d'une lettre sans utilisation d'enveloppe, utilisant le pliage et la découpe1. L'apparition du letterlocking remonte au XIIIe siècle en occident lors de l'apparition du papier à lettres flexible2. Des petites fentes, des languettes et des trous placés directement dans une lettre et combinés à des techniques de pliage sont utilisés pour sceller la lettre («letterpacket»), empêchant sa lecture sans casser les scellés ou les glissières, rendant difficile la falsification3. Ces plis et trous peuvent aussi être fixés avec de la ficelle et de la cire à cacheter4 . Un diplomate écossais en Italie, William Keith de Delny, a envoyé des lettres à James VI qui se seraient déchirées si elles n'avaient pas été ouvertes avec précautions.

Outre la sécurisation du contenu, le lettrelocking est aussi un moyen d'expression artistique6. Bien que ces techniques de scellement aient pu être limitées aux ecclésiastiques et à la noblesse, le verrouillage des lettres fut pratiqué par toutes les classes d'écrivains. 7 Un individu pouvait également être reconnu par sa technique personnelle de pliage, comme ce fut le cas avec Jane Whorwood, dont Charles Ier, alors emprisonné au château de Carisbrooke sur l'île de Wight, reconnu une de ses notes par l'apparence des plis..."

La Machine Enigma
La machine allemande Enigma a joué un grand rôle pendant la guerre de l'Atlantique, et son décryptement par les Alliés leur a assuré bon nombre de victoires (notammeent parce que les Allemands ne se doutaient pas que leurs messages étaient déchiffrés).
Enigma ressemble à une machine à écrire : on frappe le clair sur un clavier, et des petites lampes s'allument pour éclairer les lettres résultant du chiffrement.
Le principe de chiffrement qu'utilise Enigma est à la fois simple et astucieux. Simple, car il ne s'agit ni plus ni moins d'une substitution de lettres : par exemple, A devient Q, P devient N, etc. Et astucieux, parce que la substitution change d'une lettre à une autre : si la lettre A correspond à Q la première fois qu'on la saisit, elle pourrait correspondre à M, K, H, ou tout autre lettre différente de Q à la fois suivante (ce principe est possible grâce à un système de rotors).
De plus, un autre avantage non négligeable que possède Enigma est la réversibilité : si on tape le message clair, on obtient le message code, et avec le messsage codé, on obtient le message clair.
L'inconvénient majeur est que jamais la lettre A ne sera codée par A....

La cryptographie à clé secrète ou symétrique¶

f : M --> C

où M est l'ensemble des messages en clair
et C est l'ensemble des messages chiffrés

Comme il s'agit d'une fonction bijective, l'opération permettant de passer de C à M est une fonction inverse de f, c'est le déchiffrement. Ce principe de chiffrement/déchiffrement est dit "symétrique"; car l'utilisation d'une bijection permet l'aller-retour très facilement.
L'emploi d'une bijection se justifie également parce qu'elle permet une correspondance univoque entre les éléments de l'ensemble. Autrement dit, à partir d'un message crypté, il n'est pas possible de tomber sur plusieurs possibilités de messages en clair.
Il est donc primordial, pour lire/écrire des messages cryptés :
- d'utiliser une fonction facilement inversible, en particulier pour un usage privé (il faut être capable de décrypter les messages sans avoir recours à des moyens techniques colossaux).
- de préserver cette fonction secrète, car si un "ennemi" se la procure, il lui suffira de l'inverser pour déchiffrer le message !
Ce dernier point implique un autre problème : l'utilisation d'une même fonction f pour crypter un message risque, à la longue, d'en dévoiler le secret. Ainsi, l'idéal serait de changer régulièrement de fonction de cryptage.
On définit donc un système cryptographique, ou de chiffrement, ou encore un chiffre, comme étant une famille finie 'F' de fonctions 'f' cryptographiques, chacune étant déterminée par un paramètre 'K', appelé clé secrète:
F = (fK)
On utilise ainsi la même "structure" de fonction de chiffrement, mais avec chaque fois un paramètre K différent.

Le principe de Kerckhoffs¶

C'est là le principe énoncé par Auguste Kerckhoffs à la fin du XIXe siècle, dans un article sur la cryptographie militaire :
La sécurité d'un cryptosystème ne doit reposer que sur le secret de la clé. Tous les autres paramètres sont supposés publiquement connus.
Ce principe est le fondement de la cryptographie à clé secrète.

Le chiffre de Vernam¶

En 1917, Gilbert Vernam mit au point un algorithme de chiffrement basé sur une clé secrète parfaitement sûr, tellement sûr qu'il a longtemps protégé le fameux "téléphone rouge", qui reliait la Maison Blanche au Kremlin.
Utilisation :

La clé est de la taille du message à envoyer
Les lettres de cette clé sont choisies de façon totalement aléatoire
La clé ne doit servir qu'une seule et unique fois

Sécurité "inconditionnelle"
Si la clé choisie est soumise aux conditions citées plus haut, l'utilisation d'une loi de groupe garantit une sécurité dite inconditionnelle. En effet, si on admet qu'un cryptanalyste intercepte le message crypté C, il ne pourra rien en déduire, si ce n'est la taille du message en clair M. Il lui est impossbile d'établir une corrélation entre M et C sans connaître K, car étant donné qu'on utilise pour crypter une loi de groupe, il n'existe pour M et C qu'un seul nombre K tel que M = K * C !
Ce problème est comparable au suivant : dans un bateau, il y a trois poules et un canard ; quel est l'âge du capitaine ?
... Même si l'ennemi possédait des ordinateurs ultra puissants, il ne pourrait jamais en trouver la solution. C'est dans ce cas-là que le mot "sécurité inconditionnelle" prend son sens : une puissance de calcul infinie ne décrypterait pas le message.

Le système de Vernam
Il suit le principe détaillé précédemment. Soient :

Un alphabet E, sur lequel s'écrivent les messages en clair et les messages chiffrés
m le nombre de lettres de E (m = #E)

Un message M de n symboles M = (x1,x2,...,xn) se chiffre par la transformation fK :
fK : M (x1,x2,...,xn) --> C (y1,y2,...,yn)
où yi = xi + ki mod m
avec K = (ki,..., kn) la clé choisie aléatoirement dans E, et destinée à ne servir qu'une seule fois.

Pertinence de ce principe
Le système mis au point par Vernam, bien qu'apportant une sécurité optimale, est très peu d'usage dans le monde civil, et est surtout réservé à des organismes possédant des moyens importants. En effet, tout le monde n'est pas en mesure d'utiliser des clés de la manière décrite en début de chapitre :

Générer des clés gigantesques (puisqu'au moins de la taille de l'ensemble des messages à envoyer) nécessite une grande puissance de calcul
Transporter de telles clés, dont le secret doit être maintenu à tout prix, n'est pas chose aisée : tout le monde ne dispose pas de la valise diplomatique...

Il a donc fallu aux cryptographes trouver une alternative plus pratique et moins coûteuse, les schémas de Feistel.

Le DES¶

Le Data Encryption Standard (standard de chiffrement de données) a été publié en 1977, et fut ainsi le premier algorithme cryptographique à petite clé secrète (56 bits) à avoir été rendu public. Le DES consiste en un réseau de Feistel de 16 tours : le message à chiffrer est découpé en blocs de 64 bits, chacun d'eux étant séparé en deux sous-blocs de 32 bits.
L'algorithme du DES sera le plus utilisé dans le monde jusqu'en 1998. A cette époque, une association de particuliers fit construire, pour moins de 250 000 $ (somme dérisoire pour un Etat ou une organisation mafieuse), un processeur capable de casser le DES. A l'heure actuelle, trois jours suffisent aux ordinateurs pour le percer, et ce grâce à des attaques exhaustives !
On aura bien tenté d'améliorer le DES, en doublant la taille de sa clé (on parle alors de TDES), mais cette version n'était pas assez rapide. Le NIST (National Institute of Standards and Technologies) lance donc un concours pour créer un successeur au DES, et ce sont les belges Joan Daemen et Vincent Rijmen qui seront retenus.

L' AES¶

L'Advanced Encryption Standard, ou Rijndael, est donc officialisé le 2 octobre 2000. Joan Daemen et Vincent Rijmen devaient respecter les conditions suivantes :

Une large portabilité
Un chiffrement rapide
Un algorithme simple à comprendre et surtout, libre de droits

L'AES fait subir au message quatre transformations successives, agissant directement sur les octets :

Une transformation non linéaire d'un octet
Un décalage de lignes
Un brouillage de colonnes
Une addition de clés

Conclusion sur la cryptographie à clé secrète¶

Malgré toutes ses évolutions et ses mises en oeuvre, la cryptographie à clé secrète est toujours entravée par un défaut : la condition sine qua non de son succès est et restera le secret de sa clé (principe de Kerckhoffs). Bien qu'ayant pu au fil du temps réduire sa taille, les cryptographes ont toujours été confrontés au problème de la transmission de cette clé... Mais le progrès ne s'arrête jamais ! Si le problème est de conserver le secret de la clé, pourquoi ne pas le contourner... en inventant un système qui la rend publique ?

La cryptographie à clé publique ou asymétrique¶

Diffie et Hellman Clé "publique" et fonctions à sens unique¶

C'est en 1976 que Whitfield Diffie et Martin Hellman, de l'Université Stanford, proposent un principe de chiffrement entièrement nouveau : la cryptographie à clé publique, ou asymétrique.
Expliquons leur procédé de façon imagée :
Alice doit recevoir un message de Bob, mais elle ne fait pas confiance au facteur qui pourrait ouvrir sa lettre. Comment peut-elle être sûre de recevoir ce message sans qu'il soit lu ?...
Alice va d'abord envoyer à Bob un cadenas ouvert, dont elle seule possède la clé. Ensuite, Bob va placer son message dans une boîte, qu'il fermera à l'aide de ce cadenas, avant de l'envoyer à Alice. Le facteur ne pourra donc pas ouvrir la boîte, puisque seule Alice possède la clé !
Ainsi, un système cryptographie à clé publique est en fait basé sur deux clés :

Une clé publique, pouvant être distribuée librement, c'est le cadenas ouvert
Une clé secrète, connue uniquement du receveur, c'est le cadenas fermé

C'est la raison pour laquelle on parle de chiffrement asymétrique.
En résumé, on dispose d'une fonction P sur les entiers, qui possède un inverse S. On suppose qu'on peut fabriquer un tel couple (P,S), mais que connaissant uniquement P, il est impossible (ou au moins très difficile) de retrouver S. Autrement dit, il faut déterminer mathématiquement des fonctions difficilement inversibles, ou "à sens unique".
Trouver de telles fonctions semblait ardu aux mathématiciens. En effet, comment imaginer une fonction qui soit à sens unique pour tout le monde, excepté pour son créateur qui peut l'inverser grâce à la connaissance d'une information particulière (la clé) ? Ce sont Diffie et Hellman qui ont les premiers donné une réponse à cette question.

Le protocole de Diffie et Hellman
Parallèlement à leur principe de cryptographie à clé publique, Diffie et Hellman ont proposé un protocole d'échanges de clés totalement sécurisé, basé sur des fonctions difficiles à inverser.
( 1 ) Alice et Bob se mettent d'accord publiquement sur un très grand nombre premier "p" et sur un nombre "n" inférieur à "p".
( 2 ) Alice engendre une clé secrète "a" et Bob une clé secrète "b".
( 3 ) Alice calcule l'élément public ka et Bob l'élément public kb :
ka = na mod p
kb = nb mod p
( 4 ) Alice transmet sa clé publique ka à Bob, et Bob transmet sa clé publique kb à Alice.
( 5 ) Alice et Bob profitent ensuite de la commutativité de la fonction exponentielle pour établir leur secret commun :
KAlice = (kb) a = (n b) a mod p
KBob = (ka) b = (n a) b mod p
=> KAlice = KBob = nab mod p

Sécurité du système
A priori, il n'y a pas moyen, à partir des informations transmises publiquement (p,n,na,nb), de trouver nab sans caculer un logarithme modulo p, ou faire un quelconque calcul d'une complexité exagérée.
Ainsi, la sécurité du système est dite calulatoire et repose sur deux hypothèses :

L'adversaire dispose d'une puissance de calcul limitée
Avec cette contrainte de puissance et un temps limité, il n'est pas possible d'inverser la fonction exponentielle, ni de trouver nab à partir de p,n,na,nb.

Malgré tout cela, en 2001, des experts français ont réussi à inverser la fonction exponentielle modulaire pour un nombre p de 120 chiffres ! La sécurité d'un système dépend donc des progrès constants dans le domaine de la complexité algorithmique.
Les fonctions à sens unique sont souvent issues de l'arithmétique modulaire, car elles se comportent de manière très irrégulières.

Les limites du système
Le schéma de Diffie-Hellman, bien qu'astucieux, reste un schéma de principe et souffre d'un inconvénient majeur : il n'assure pas les services de sécurité classiques que sont l'authentification mutuelle des deux intervenants, le contrôle de l'intégrité de la clé et l'anti-rejeu (vérifier qu'une information déjà transmise ne l'est pas à nouveau). L'ennemi peut donc facilement usurper l'identité d'Alice, en remplaçant son élément public par le sien.

Le RSA¶

Le principe
Le premier système à clé publique solide à avoir été inventé, et le plus utilisé actuellement, est le système RSA. Publié en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman de l'Institut de technologie du Massachusetts (MIT), le RSA est fondé sur la difficulté de factoriser des grands nombres, et la fonction à sens unique utilisée est une fonction "puissance".
L'algorithme de chiffrement
Départ :

Il est facile de fabriquer de grands nombres premiers p et q (+- 100 chiffres)
Etant donné un nombre entier n = pq, il est très difficile de retrouver les facteurs p et q
( 1 ) Création des clés
La clé secrète : 2 grands nombres premiers p et q
La clé publique : n = pq ; un entier e premier avec (p-1)(q-1)
( 2 ) Chiffrement : le chiffrement d'un message M en un message codé C se fait suivant la transformation suivante :
C = Me mod n
( 3 ) Déchiffrement : il s'agit de calculer la fonction réciproque
M = Cd mod n
tel que e.d = 1 mod [(p-1)(q-1)]

La signature électronique
Après la confidentialité de la transmission d'un message subsiste un problème : son authenticité. Alice voudrait bien envoyer un message M à Bob de telle façon que celui-ci soit sûr qu'elle est réellement l'émettrice du message, et qu'un intrus ne tente pas de venir semer la confusion.
Le système RSA fournit une solution à ce problème :
Rappelons les données :

Alice seule détient la clé secrète d et diffuse la clé publique (n,e)
Alice va se servir de la clé publique pour chiffrer le message M
( 1 ) Alice accompagne son message chiffré de sa signature, qui correspond à : Md
( 2 ) Bob va donc voir si l'égalité (Md)e mod n = M est vérifiée. Si c'est le cas, Alice est bien l'émettrice du message.

Sécurité du système : primalité, factorisation
Comme pour les protocoles fondés sur le logarithme discret, la sécurité du système RSA est calculatoire : elle dépend essentiellement de la difficulté de factoriser un entier qui est le produit de deux grands nombres premiers. Si on sait factoriser n, il est facile de trouver d. Il est à noter qu'il est conseiller d'utiliser des clés de 1024 bits (+- 309 chiffres décimaux).
Le principal objet des attaques est l'implémentation, la mise en oeuvre du RSA. C'est la manière de se servir du système qui peut poser problème, pas le système lui-même (par exemple, prendre une clé trop petite...).
Signalons enfin que le réel problème du RSA (et des autres systèmes à clé publique) n'est pas la sécurité, mais la lenteur. Tous les algorithmes à clé publique sont 100 à 1000 fois plus lents que les algorithmes à clé secrète, quelle que soit leur implémentation (logicielle ou matérielle) !

Exemple : chiffrer BONJOUR
1) Alice crée ses clés :

La clé secrète : p = 53 , q = 97 (Note : en réalité, p et q devraient comporter plus de 100 chiffres !)
La clé publique : e = 7 (premier avec 52*96), n = 53*97 = 5141

2) Alice diffuse sa clé publique (par exemple, dans un annuaire).
3) Bob ayant trouvé le couple (n,e), il sait qu'il doit l'utiliser pour chiffrer son message. Il va tout d'abord remplacer chaque lettre du mot BONJOUR par le nombre correspondant à sa position dans l'alphabet :
B = 2, O = 15, N = 14, J = 10, U = 21, R = 18
BONJOUR = 2 15 14 10 15 21 18
4) Ensuite, Bob découpe son message chiffré en blocs de même longueur représentant chacun un nombre plus petit que n. Cette opération est essentielle, car si on ne faisait pas des blocs assez longs (par exemple, si on laissait des blocs de 2 chiffres), on retomberait sur un simple chiffre de substitution que l'on pourrait attaquer par l'analyse des fréquences (Voir chiffre de César).
BONJOUR = 002 151 410 152 118
5) Bob chiffre chacun des blocs que l'on note B par la transformation C = Bemod n (où C est le bloc chiffré) :
C1 = 27mod 5141 = 128 C2 = 1517mod 5141 = 800 C3 = 4107mod 5141 = 3761 C4 = 1527mod 5141 = 660 C5 = 1187mod 5141 = 204
On obtient donc le message chiffré C : 128 800 3761 660 204.

Conclusion sur la cryptographie à clé publique¶

Après avoir vu les avantages indéniables de la cryptographie à clé publique (transmission de la clé, sécurité, autentification), on est en raison de se demander quel pourrait être l'avenir des systèmes à clé secrète.
Le RSA et ses comparses ont-ils relégué le DES et l'AES aux oubliettes ? Faut-il renier Vernam et Feistel ?
... le ton de la question rend la réponse évidente : NON !
En effet, à l'heure actuelle, on utilise des cryptosystèmes hybrides, qui couplent les avantages des deux principes, alliant la souplesse de gestion des clés de la cryptographie asymétrique et les performances (vitesse) de la cryptographie symétrique.
Il existe deux types de cryptosystèmes hybrides :

Soit, la cryptographie à clé publique sécurise le transport d'une clé symétrique
Soit, les entités émettrice et destinatrice se mettent publiquement d'accord sur un secret commun et l'utilisent ensuite pour chiffrer les données grâce à un algorithme symétrique classique.

Conclusion sur la cryptographie¶

Les cryptographes n'ont cessé de redoubler d'ingéniosité, faisant se succéder des dizaines de systèmes de chiffrement plus recherchés les uns que les autres. Se livrant bataille pour la gloire ou l'argent, ils n'ont cessé de faire évoluer cette science qu'est la cryptographie. Avec d'abord une mécanisation (notamment la machine Enigma), puis grâce à l'avènement des ordinateurs, et avec eux une puissance de calcul surpassant de loin le niveau humain, la cryptographie a su trouver son chemin dans les dédales du progrès.
Progrès qui ne s'arrête jamais ! Déjà maintenant, d'autres voies, encore obscures, se dessinent :

Les ordinateurs quantiques: ils procureraient une puissance de calcul colossale, et une sécurité infaillible ! Cependant, la théorie est là, mais la mise en oeuvre semble très difficile... pour l'instant
la cryptographie multi variable quadratique : des multiples équations faisant intervenir jusqu'à 120 variables
Le chaos chiffrant : "noyer" le message dans un signal chaotique et, connaissant les caractéristiques du signal, le retrouver.
Des méthodes fondées sur les courbes elliptiques
...