Bonjour, c’est Bernard !
J’aimerais bien communiquer avec Alice, malheureusement Eve est dans le coin ….
Ah, je sais ! Je vais crypter mes données ! Pas de problèmes, plein d’algorithmes existent déjà comme DES, ou je peux même faire le mien !
Ah … mais il faut que je donne à Alice une clé… et Eve est très en forme sur les attaques ManInTheMiddle ces temps-ci …
Plus sérieusement, comment pourrait faire Bernard pour crypter ses informations sans que Eve ne puisse les décrypter ?
C’est à dire, comment éviter qu’Eve espionne l’échange de la clé, appelée clé privée ?
Ce fut le grand problème des cryptographes jusqu’à ce début de siècle, et jusqu’a l’idée de Diffie et Hellman. En effet, ils ont tout simplement imaginé qu’il était possible de ne pas utiliser seulement une clé privée dans une fonction cryptographique réversible. A partir de l’idée de la boite à cadenas, qui prouve qu’il est possible de ne pas utiliser seulement ces fonctions, l’idée fut de trouver des ( voir une ) fonction à sens unique.
Tout d’abord, qu’est-ce que la boite à cadenas ?
Bernard peut mettre son message dans une boite, qu’il refermera avec un cadenas A dont il est seul possesseur de la clé. Il envoie sa boite à Alice, qui ne peut l’ouvrir, mais qui rajoute un cadenas B dont elle est seule possesseur de la clé , et qui renvoie cette même boite à Bernard ( avec donc les cadenas A et B dessus ). Bernard enlève son cadenas A puisqu’il a la clé, et renvoi la boite à Alice. Alice peut maintenant enlever son cadenas B, ouvrir la boite, et lire le message de Bernard. Ici, le cadenas représente la fonction de cryptage, et la clé représente la clé utilisé. Dans cette exemple, Bernard n’a pas eu besoin d’échanger sa clé avec Alice, et donc, pas de risque d’interception. Et ça, c’est tout simplement une révolution pour le monde de la cryptographie.
Diffie et Hellman trouverons alors une technique utilisant une fonction à sens unique, j’ai nommé le modulo. Nous reviendrons sur cette technique dans un exemple plus bas.
Malheureusement, ces technique annihile l’instantanéité d’un moyen de communication comme l’email.
Si Bernard veut envoyer un message urgent à Alice, mais que celle ci s’est couché tard et dort encore, il devra attendre qu’elle se réveille, prenne son petit dej’, consulte ses emails, lui renvoi, …
Viens alors une autre idée, dont vous avez surement entendu parlé, qui est celle de la cryptographie à clé publique / privée. Cette cryptographie utilise une fonction très difficilement réversible. Très difficilement, pour éviter tout décryptage malencontreux, mais cependant possible pour permettre un décryptage ( autrement, on a affaire à une fonction de hashage ). Et c’est au trio Rivest Shamir Adleman que l’on doit RSA .
L’algorythme n’est pas très dur à comprendre, ni à mettre en place, et je vous conseille de lire la page de Wikipedia fr qui s’y rapporte : http://fr.wikipedia.org/wiki/Rivest_Shamir_Adleman .
Cependant, à cette époque, si Bernard souhaitait crypté un texte d’une longueur conséquente, les temps de calculs devenaient trop important pour être exécuté par un ordinateur personnel. Exit la cryptographie à clé public pour tous. Exit, sans compter Zimmerman et Pretty Good Privacy. L’idée, qui couta d’ailleurs beaucoup de temps et de procédure judiciaire à Zimmerman, était de réussir à mettre à la porté de tous la cryptographie à clé publique. Son logiciel, PGP, fonctionne de la manière suivante :
Tout d’abord, l’utilisateur génère le nombre N de l’algorithme RSA de manière aléatoire, par ses mouvements de souris. Pour tester si les nombres obtenus sont premiers, il existe des techniques très rapide permettant d’obtenir des nombres dits premiers probable. Sur des très grand nombre, comme ceux utilisé dans RSA, le risque que le nombre obtenu soit le résultat d’une factorisation qui n’est pas celle de deux nombres premiers, mais d’au moins un nombre composé, est moins élevé que celui de gagné au Loto ( enfin “risques”, on se comprend ). Ensuite, lors d’un échange, une clé est générée, puis crypté avec RSA ( en utilisant la clé publique du destinataire ), et cette même clé est ensuite utilisé pour crypter le message avec un algorithme à clé privé bien plus rapide, comme DES. La clé publique de l’expéditeur est envoyée avec le message. A la réception, le message est décrypté grâce à la clé contenu dans le décryptage du code RSA grâce a la clé privée du destinataire, pour être enfin intelligible. Et tout ça, PGP doit le fait sans grande assistance de l’utilisateur, permettant une utilisation grand public.
Pour des raisons de brevet, le logiciel PGP fut recodé par des européens, et est disponible sur http://www.pgpi.org/ .
Avec l’évolution de la puissance des ordinateurs ( loi de Moore vous connaissez ? A intervalles réguliers, la puissance doit être doublée pour deux fois moins de place … techniquement réalisable jusqu’à maintenant, mais atteindra bientôt ses limites 
), il est maintenant recommandé d’utiliser des clées de 1024 voir 2048 bits, c’est à dire des nombres assez grand pour ne pas être factorisé dans un temps dit raisonnable.
Revenons à notre problématique. Les solutions qui s’offre à Bernard sont donc :
- Utiliser un algorithme à clé privé, en donnant la clé privée physiquement à Alice.
- Utiliser le système de cadenas, ou de fonction à sens unique.
- Utiliser un système à clé publique, de façon simplifier avec par exemple PGP.
( Si j’étais réellement Bernard, j’opterais pour la troisième solution … )
Maintenant, je vous propose de coder tout d’abord un équivalent du système de cadenas, puis de reproduire le système de Diffie et Hellmann.
Tout d’abord, pour notre équivalent de cadenas, voici ce que doit faire notre fonction ( résumé par ce magnifique schéma 
) :
Entrée utilisateurA ( texte, cleA ) ==> réception utilisateurB ( texteA ) et renvoi ( texteA, cleB ) ==> réception utilisateurA ( texteAB ) et renvoi ( texteB ) ==> réception utilisateurB (texte ). Sauf que pour les deux utilisateurs, ça donnera Entré utilisateurA (texte) ==> sortie utilisateurB (texte).
A vos crayons, méninges, claviers, souris, barres chocolatées 
!
Pour ma part, je l’ai codé en python. Je passe sur les fonctions d’envoi / réception, qui n’apporte pas grand chose au code. J’utiliserais envoi(donnee) qui envoi “donnee” ( par Socket par exemple ), et reception() qui receptionne ce qui à été envoyé.
Une des difficulté de la fonction est de trouvé un algorithme capable de crypter plusieurs fois avec des clés différentes, et de ne pas dépendre du sens de décryptage ( c’est à dire donner le même résultat si on décrypte d’abord avec la clé A puis B, et si on décrypte avec B puis A ).
La fonction est donc décomposé en quatre sous fonctions ( 6 si on compte celles d’envoi/réception ) :
- crypt(texte,cle) qui va crypter texte avec la cle cle
- decrypt(texte,cle) qui inverse la fonction crypt()
- send(texte) qui est la fonction qui gère l’envoi d’un message
- receive(texte) qui est la fonction gérant l’arrivée d’un message
Pour l’algorithme, j’ai choisi de tout simplement utiliser une addition modulo 256 sur la valeur ASCII des caractères. Par exemple, la lettre A(67) crypté avec la lettre B(68) donne chr(67+68). Le protocole utilisera un système de drapeau pour reconnaitre les étapes. Ce drapeau sera en faite un 1,2 ou 3 précédant la suite de caractère. 1 indique que la suite de caractère est seulement codée avec A ( 1ère étape ), 2 indique qu’elle est codée avec AB ( 2ème étape ) et 3 indique qu’elle n’est plus que codée avec B ( dernière étape ).
A présent, le code :
def crypt(clair,cle): i,crypter=0,"" while i < len(clair): char = (ord(clair[i]) + ord(cle[i%len(cle)]))%256 crypter = crypter + chr(char) i += 1 return crypter def decrypt(crypter,cle): i,clair = 0,"" while i < len(crypter): char = (ord(crypter[i]) - ord(cle[i%len(cle)]))%256 clair = clair + chr(char) i += 1 return clair
A ce niveau là, on peut déja testé si notre fonction de dépend pas de l’ordre du cryptage/décryptage :
Ordre normal :
cleA,cleB = "une","deux"
print decrypt(decrypt(crypt(crypt("Texte temoin",cleA),cleB),cleB),cleA)
Texte temoin
Ordre “anormal” :
cleA,cleB = "une","deux"
print decrypt(decrypt(crypt(crypt("Texte temoin",cleA),cleB),cleA),cleB)
Texte temoin
Bien, on peut donc maintenant implementer notre protocole, et intégrer nos deux fonctions, ce qui donne :
def send(texte,cle): envoi(str(1)+crypt(texte,cle)) retour = reception() envoi(str(3)+decrypt(retour[1:],cle)) def receive(cle): donnee = reception() flag,texte = donnee[0],donnee[1:] switch flag: case "1": envoi(str(2)+crypt(texte,cle)) case "2": envoi(str(3)+decrypt(texte,cle)) case "3": print decrypt(texte,cle) else: print "Error : flag:",flag
Pourquoi ai-je mis l’argument “cle” dans mes fonctions send() et receive() ?
Parceque un des problème de notre fonction de cryptage, est que en connaissant une clé et le texte en clair, on connait tout de suite la deuxième clé. Et donc, vous pouvez connaitre la clé de votre correspondant dès le premier message. Ca implique donc soit une clé différente pour chaque correspondant, soit une clé générée aléatoirement pour la session . Et l’argument “cle” devient donc nécéssaire.
Et comme promis, voici maintenant le principe de l’échange de clé Diffie-Hellman-Merkle ( Oui parceque Merkle a aussi contribué ). Je préviens tout de suite, il y aura un peu de math, rien de très compliqué 
.
Ces trois personnes ont donc réussi à trouvé une fonction à sens unique, qui repose sur l’arithmétique du modulo. Tout d’abord, un petit rappel sur l’opération modulo, que je noterai % .
Le modulo représente le reste dans la division euclidiènne d’un nombre par un autre.
Donc 7 % 3 = 1, car 7 = 2*3 + 1. Mais là où cette fonction devient intéressante, c’est que 10 % 3 = 1 aussi !
Et donc, si vous ne connaissez que 3 et 1, vous ne pouvez pas deviner le 7, 10, 13, 4, 1, … il y en a une infinitée. Cette fonction est donc à sens unique.
Celle de DHM s’écrit Y^x % P . Voici comment se déroulerait l’obtention d’une clé :
Tout d’abord, nos amis Alice et Bernard vont se mettre d’accord sur la valeur de Y et P.
Alice choisit un nombre qu’elle garde secret, que l’on appelera A. Bernard fait de même avec un nombre B.
Alice et Bernard appliquent alors leur nombre à la fonction à sens unique.
Pour Alice, on a Y^A % P = @, et pour Bernard Y^B % P = & .
Alice et Bernard se partagent alors leurs résultats @ et &. Pour obtenir la clé, Alice va faire &^A % P, et Bernard @^B % P. Et miraculeusement, ils obtiendront la même clé.
Prenons un exemple concret. Disons que Y = 7, P = 11, A = 3 et B = 6. On a donc @ = 7^3 % 11 = 2, et & = 7^6 % 11 = 4. 3 et 4 sont donc échangé, et la clé sera donc 4^3 % 11 = 2^6 % 11 = 9 !
Comme vous le remarquerez, la clé ne peut dépasser P. Il est donc important de prendre un nombre P très grand ( l’autre opération étant une puissance, il est très probable ( et il est nécéssaire ) que Y^x soit supérieur au moins une fois à P ) .
Maintenant, que sait notre Eve ?
Et bien, elle connait Y = 7, P = 11,@=2 et &=4. Et avec ça, elle ne peut pas deviner la clé ( Ses seules informations sont que la clé est comprise entre 0 et 11, et qu’elle peut prendre toutes les valeurs que peut prendre 7^x % 11 ).
Vous pouvez vous amuser à coder une fonction utilisant ce principe, mais pour ma part je n’en posterais pas une ici, qui serait sans réel intérêt. Je vous donne la fonction pour déterminer @ et &, et celle pour déterminer ensuite la clé :
Determination de A :
def det(Y,P,A): return exp(Y,A) % P
Determination de la cle à partir de & :
def gen_cle(&,A,P): return exp(&,A) % P
C’est ainsi que se cloture cet article, un peu plus long que les autres, il y avait beaucoup à dire .
Enjoy
Ajax