Copy Link
Add to Bookmark
Report
UnderWayy Issue 3 02 Cryptage par TbH
Premiers liens entre les sciences et la machine : les maths et la cryptographie (Past & present) .
I-: Premiere machine de cryptage et de decryptage:
Les toutes premieres machines crees qui resultaient d'une application mathematiques on ete des machines de cryptographie.
A l'epoque de la seconde guerre mondiale les U boot allemands faisait passer leur message par ondes hertziennes. Une methode de cryptographie fiable etait donc indispensable.
a-: L'Enigma :
L'enigma servait à crypter les messages. Utilises dans les U-boot allemand elle a donnee beaucoup de file a retordre aux alliers. C'etait la premiere machine digne de ce nom pour crypter les messages. En fait la premiere machine enigma concu fut presentee en 1923, juste apres son invention. Cette machine etait mecanique. Puis elle fut considerablement amelioree pour devenir une machine electrique.
Concretement la machine enigma etait constitué de trois rotords. La machine travaillait sur un alphabet de 26 lettres. Ce qui donnait 26^3=17576 solutions pour une lettre tapee.
Shematiquement voici ce que donnerais la machine enigma pour 6 lettres :
_____ _____ _____
| | | | | |
a-----|\ | | | | |
b | \ | | --|\ ----|\ |
c | \|------|/ | \/ | \/|--|
d | | | | /\ | /\|--|
e-----|- | | |/ \---|/ |
f | \ | | /| | |
| \|------|-/ | | |
----- ----- -----
.
.
.
Pour une question de clarete je n'est represente ici que le cable liant a vers e. Il en etait de meme pour les 25 autres lettres de l'alphabet.
Concretement l'Enigma marchait ainsi. Des cables electriques reliaient les rotords et ces retords tournaient, de maniere a ce qu'il puisse avoir differentes combinaisons. En effet le courant qui passaient par les fils electriques d'un rotords a l'autre etait dirige sur le rotord sur lequel il arrivait de maniere a ne pas passer sur l'axe de la meme lettre. Cette assemblage de position de rotord etait la combinaison du cryptage que les alliers (en particulier les anglais de Betchley) devaient trouver.
En plus de cette combinaison de position de rotords (soit 17576 position possible), les allemands pouvaient deplace les retords, ce qui donnait pour une lettre 6*17576 = 105456 solutions.
En plus du choix des placement des rotords, il existait une marque exterieur de la position par rapport au fils electriques. Cette marque etait une bague place sur le rotord qui donnait 26 choix possible ( de A a Z ). Cette bagues pouvait ainsi etre changer chaque jour par rapport aux lignes (numerote de 1 a 26 ). Ainsi si on placait N en position 1, O etait place en position 2 etc. Ainsi si le decrypteur savait que le rotord etait en position G, il ne pouvait pas devine la position reelle du cablage. Par contre il pouvait tout a fait dire que si G=10, M=16.
Une troisieme difficule intervenait, celle des paires. En faite lors de la connexion chaque lettre avait une connexion electrique. Les allemands pouvait ainsi faire des couples de liaisons en utilisant de fil double pour que le tour soit joue.
Exemple :
si on imagine la substitution des lettres par le placement des rotords ainsi :
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
F Z E R C A T Y U O P Q S W J K L D M G I X N V H B
Si on imagine que sur le tableau de connexion on avait :
(DG) (EN) (ZS) (AL) (VC) (QP) (UI) (MH) (XT) (WR) (BO) (KF) (JY)
Imaginons qu'on tape V, par l'intermediaire du tableau de connexion on aura C, qui par l'intermediaire du placement des rotord donnera N, qui par l'intermediaire du tableau des connexions finira par donner E.
Cette maniere de coder donnait plusieur defaults, on savait en effet par avance que si B donnait Y alor Y donnait B, bref connaitre le tableau de connecxion donnait un gros avantage au decrypteur, puis on etait sur que si on trouvait la lettre "A" dans un message code, alor a ce moment la on savait que l'original n'etait pas A. Enfin on pouvait voir une certaine frequence de lettres qui revenaient plus ou moins mais reguliere pour chaque lettre.
Mais elle donnait deux gros avantage : une lettre ne pouvait donner la meme lettre apres codage, et on 1 305 093 289 500 manieres de relier 7 paires de lettre (dans l'exemple choisi il y en a 13) pour 6*17576 position de rotord.
Voila en gros le mecanisme de l'Enigma... On comprend facilement la difficulte des decrypteur qui durant la guerre ont fait une dure bataillle contre cette machine. Alan Turing fut parmis ceux qui se bataient contre elle. Et c'est de lui qu'est nee une reponse...
A noter que la fonction crypt de vos unix ont le meme principe de fonctionnement. En fait plus vous cryptez
vos message (c'est a dire que pour un message je fais intervenir 3 fois crypt) plus vous mettez des rotords
a votre machine...
b-:La bombe de Turing :
Turing proposa une parade à cette machine.
Elle tenait compte des faiblesse d'enigma. Ainsi les allies durant presque toute la guerre connaissait
les projets des Allemands. La guerre maritime contre les U-BOOTs tourna ainsi à l'avantage des allies.
Je ne decrirais pas le principe de la bomb de Turing. Tout de fois vous pourrez la retrouver dans le
livre "Alan Turing ou l'enigme de l'intelligence" d'Andrew Hodges.
II-: Le cryptographie actuelle dans les regles mathematiques :
a-: introduction
~~~~~~~~~~~~~~~~
Le cryptage des donnes est utilise depuis l'antiquite. Et jusqu'a aujourd'hui (cet a dire la democratisation des ordinateurs).
Il s'agissait souvent de technique assez rudimentaire, dont la complexite mathematique n'etait pas tres eleve.
L'inviolabilite de ces codes dependaient du secret qui entourait la technique de codage.
La cryptologie est reelement nee apres la premiere guerre mondiale. C'est a dire quand les machine tel Enigma ou encore Typex. Cette science est constemment en devellopement depuis cette date avec l'evolution des machines a calculer,
les algorhytmes se sont affinees... Mais encore aujourd'hui aucun mathematiciens n'a pu trouver une technique de cryptologie qui ne puisse etre decrypter. A l'heure actuelle, la complexitee des alorgythmes, des clef choisie, de l'alphabet, ne nous permettent que de repousser la date t a la quelle le message sera techniquement decrypte...
b-: notion elementaire :
~~~~~~~~~~~~~~~~~~~~~~~~
La cryptographie reviens a rendre incomprehensible un texte aux personnes à qui il n'est pas destine. Pour cela on opere a une transformation du message a transmettre sans tenir compte des regles linguistiques.
Si un texte peut etre code par l'envoyeur il faut que le destinataire puisse le decrypter, avec les informations qu'il connait deja. C'est a dire que le cryptage repose sur une operation qui a sont inverse : en gros si le codage se poduit avec f(x), ou pourra le decoder avec -f(x).
A ceci s'ajoute la notions de cles :
Il existe dans ce cas la deux systemes, l'une a clefs prive, l'autre a clefs publique. Beaucoup d'article on ete fait
a ce sujet ( de celui de stealthyx dans #h/p/c/l/p 1 et UnderWayy 2 a celui de Protek dans cryptel 2). Je ne m'atarderais donc pas beaucoup sur ces notions.
-cryptosysteme : un cryptosysteme est un procede pour tranformer un texte en un autre texte completement inintelligible... En informatique il se traduit par la transformation tout d'abord des lettres en chiffres (binaire pour notre cas). Pour la transformation on peut choisir que n chiffre serviront a coder une lettre..Ainsi si on trabail en binaire on aura 2^n possibilté de coder un texte ( 2 car on est en base binaire, et base decimal on aurait eu 10, etc).
-Systeme a clefs prive.
Dans ce systeme on connait generalement l 'algorythme de procede de codage. En effet pour pouvoir assurer la securite du message code seul la cle a besoin de rester secrete. Si on ne connais pas k, la securite du chiffrement ne pourra
pas etre cassee.
On peut shematiser le systeme ainsi :
soit P le message,
soit k la cle prive,
soit G le procede general de codage,
soit H le procede de decodage,
soit C le message crypte.
|----->decrypteur possede G, C.
|
origine du message|--[P]-->crypatge du message par Gk(P)=C|--[C]-->destinataire qui decrypte avec Hk(C)=P
| |
|-------------------[passage de la cle prive]---------------------------------------------------|
Le decrypteur a donc dans ce cas la deux equations :
Gk(P)=C et Hk(C)=P
On deux inconnu k et P. Comment calculer k??? Si le decrypteur ne connait que G, H et C il ne pourra pas pouvoir
decrypter ce message. Et par consequent ne peut pas calculer k. En fait on NE PEUT PAS SAVOIR MATHEMATIQUEMENT la
valeur de k. Il faut aboutir a d'autre moyen. Sur le reseau une bonne maniere de prendre une cles prive est la methode par sniffing.
-Systeme a cles publique :
Ici on connais non seulement l'algorithme qui permet le cryptage mais aussi une des deux cles utilises :
shema :
soit P le message
soit k' la cle publique
soit k la cle privee
soit G le procede de cryptage
soit H le procede de decodage
soit C le message crypte.
|------>decrypteur possede G, C, k'
|
|---------------------------------[k']------------------|-----------------------------------|
origine du message|--[P]-->cryptage du message par G(k')P=C|--[C]-->destinataire qui decrypte avec Hk(C)=P
-cryptage a partir de la machine :
Nous allons etudier dans ce qui suit le systeme de codage a empilement et le systeme RSA. Ces deux types de systeme sont deux systeme a cle publique base sur le probleme NP. Le probleme NP (ou probleme non resoluble en temps polynomiaux) se resume au fait
que un algorithme a un temps d'execution qui devient de plus en plus lent selon sa taille. Par contre la verification de ces problemes sont rapides quelque soit l'algorithme. Plus precisement, lors de l'execution de l'algorithme le temps d'execution croit d'une maniere exponentielle tels qu'une fonction n : 2^n ; alors que la resolution elle se fait de cette maniere : n^2. Comme vous le savez deja les fonction (n) exponentielle (2^n) croient plus que les fonction polynomiales (n^2). On peut ainsi facilement construire des fonctions a sens unique. Ces fonctions ont la proprietes d'etre facilement calculable mais dont l'inversion, elle (c'est a dire dans le cas qui nous interresse, la fonction inverse a celle de cryptage, c'est a dire de decryptage) est beaucoup plus difficile, voir completement impossible a accomplir par un ordinateur. Pour pouvoir calculer cette fonction il faudra que l'ordinateur puisse connaitre certaine propriete de celle ci. Et c'est le role de la clef prive. Ainsi la cle publique permet detablire la fonction facile a calculer & la cle prive permet d'inverser facilement la fonction utilisee.
Pour revenir sur la machine, il faut savoir qu'avant d'etre transforme par la fonction de cryptage, le texte (lettre, nombre en base decimal, caracteres speciaux) sont transformees sous forme de nombre en base 2. C'est a dire que chaque lettre, chaque nombre aura un representant sous forme de 0 et de 1. Plus on acceptera de donner de bits a la converstion de ces caracteres plus la possiblite de transformez des lettres en base deux sera grande : par exemple si on prend cinq bit, la possibite de caracteres en base deux sera de 2^5= 35. On a donc plus de choix que pour notre alphabet, mais en prenant 5 bit il reste insuffisant pour rajouter les dix chiffres (0,1,2,3...,9).
Nous ferons aussi une courte d'escription du systeme DES, qui lui ne se sert que cle privé, mais dont on a beaucoup plus de mal a decrypter...
c-: systeme de codage a empilement :
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Le systeme de codage a empilement est peu connu, mais merite notre attention. Inventee par Ralph Merkle et Martin Hellman (dont nous reprendrons les exemples paru dans son article "Les mathematiques de la criptographie revelee").
Le systeme du codage a empilement est proche du probleme a empilement qui est lui meme un probleme NP.
Le probleme est simple, si on imagine un ensemble de x jeton n de taille differentes, et un cylindre C=6790, il nous faut trouver un sous ensemble de ces dix jetons qui puisse remplire parfaitement le cylindre, c'est a dire dont la somme soit = a 6790.
Pour trouver il nous faudrais rechercher 2^x empilements. Imaginons que le total des jetons soit de 1000, il nous faudrait verifier 2^1000 empilements!!!!
Nous avons dit plus haut que pour certain probleme NP, il etait possible de faire agir une gache (la cle prive) pour pouvoir retrouver l'empilement qui nous interresse sans pour autant devoir chercher les 2^1000 empilements possibles. La connaissance de la gache va nous permettre de passer d'un probleme d'empilement difficile a un probleme d'empilement plus simple mais similaire.
Pour revenir a la cryptographie si par exemple la cle publique correspond a l'ensemble a={2292,1089,211,1625,1283,599,759,315,2597,2463} tel que a1=2292, a2=1089....a10=2463.
On a par ailleur un texte qui debute par un mots tel que les premier chiffre binaire lors de la conversion du texte en langage machine soit : 00111011101011011010. Comme n=10, on va reprendre les dix premiers 0 et 1 du message et ainsi de suite tel que la premiere portion qui va etre code soit x=0011101110. On vas donc avoir pour cette premiere portion :
C=a1x1+a2x2...a10x10, soit C=2292*0+1089*0+211*1+......2463*0=6790
Pour resumer, pour coder un message il nous faut un ensemble a constitue de n chiffres. Ainsi pour un bloc de x de n chiffre, on pourra le code ainsi : C=a1x1+a2x2+...+anxn et ainsi de suite pour le reste du message. Voici pour le principe du codage, il ne s'avere en fait etre qu'une somme de produit scalaire / C=a.x . On appelera "a" un "vecteur cle revele"
Pour decoder le destinataire devra prendre l'ensemble qui constitue sa cle prive ("a'"="vecteur cle secrete) et il pourra ainsi creer la fonction inverse necessaire au decodage ou si vous preferez trouvera plus facilement l'empilement solution pour C=6790. A noter qu'ici n=10. C'est a dire qu'il serait tres simple de decrypter le message sans pour autant avoir la cle prive, puisque il n'y aurait que 2^10 empilement (c'est a dire 1024) à tester, voir on pourrais trouver (si le texte est assez long) une certaine regularite, puisque l'operation se repeterais tout 10 premiers chiffres du texte en binaire...
Plus precisement pour fabriquer son vecteur cle (revele) a, l'utilisateur commence par choisr un vecteur a', tel que tout element a'i soit plus grand que la somme des précents :
a'i>a'1+a'é+a'3+...+a'(i-1).
Etudions un texte codé obtenu par le produit scalaire a'.x' ou x' est le message à transmettre en binaire et ou a' = {3, 5, 11, 20 41, 83, 169, 340, 679, 1358 }... C'=3.x'1+5.x'2+....+1358.x'10= 1260
a'10=1358>C' donc x'10 vaut 0 (si il valait 1 C' serait > ou = a 1358)
a'9 = 679 < C'
a'1+...+a'8 < 679
x'i = 0 ou x'1=1
donc a'1.x'1+a'2.x'2+...+a'8.x'8 < 679
si x'9 = 0 C' < 679.
Or C' = 1260 donc x'9= 1
D'ou a'1x'1+...+a'8x'8=1260-679 = 581 = C''
a'8 < C'
a'1+...+a'7 < a'8 = 340
donc x'1.a'1+...+a'7.x'7 < 340
si x'8 = 0 C'' < 340
Or C''= 581 donc X'8 = 1
etc...
si on continue jusqu'au bout on a un bloc x'={0,0,1,1,1,0,1,1,1,0}
On a donc retrouvé le message initial ...
Comment peut on à present creer une cle publique, c'est à dire une clé qui permette de crypter le message et que TOUT LE MONDE CONNAIS, sans pour autant faciliter le travail du décrypteur ???
SIMPLE :))))
On fait agir l'arythmetique des congruences....
<<<===================================== Arithmétique des congruences ==============================>>>
Imaginons une fonction telque x|----f--->13x+1 .
Cette fonctions est usuel.
Le domaine est R, les limites à - l'infinie et à + l'infinie sont respectivements - l'infinie et + l'infinie, f est croissante sur R.
Si on veut coder un message avec cette fonction il sera tres simple de la décrypter. Il suffirait de trouver une fonction g qui soit l'inverse de f telque g(x) = x/13 - 1
Ils peut arriver qu'un expression permettant de trouver x a patir de f(x) soit delicate. A ce moment on preferera evaluer x par encadrement ...
C la qu'on fait intervenir l'arithmetique des congruences.
on divise f(x) par un nombre qconque m et on guarde le reste de la division.
soit : f'(x) = f(x) modulo m
On obtient ainsi une courbe completement differente, et f' n'est pas croissante sur R mais completement
désordonnée.
On ne peut donc plus facilement trouver le message... Car la transformation de x par f à été brouillé
par l'arithmetique des congruences...
<<<=================================================================================================>>>
En ce qui concerne le systeme à empilement pour obtenir le vecteur cle a on prend deux nombre qconques
m et n par exemple. On obtient le vecteur ai ainsi :
ai=a'iw modulo m
Voila le tour est joué !!!
d-: systeme de codage RSA :
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Sans doute le systeme a cle publique le plus utilisé.
Fonde sur un autre probleme NP : la décomposition de grands nombre en facteur premier (c'est à dire un nombre entier > 1 qui ne soit divisible par aucun autre sauf lui meme et 1). Trouver les facteurs premier d'un grand nombre prends de longues heures, alors que verifier si des facteurs premiers conviennent prend bien moins de temps...
De plus il est extrement simple pour un ordinateur de trouver des facteurs premiers, mais beaucoup
moins simple de trouver la decomposition d'un nombre en facteurs premier.
Avant de lire ce qui suit je previent que les notions ennoncées dans le systeme à empilement sont aussi valable ici. En particulier la notion d'arithmetique des congruences...
Pour construire une cle de codage (cle publique), on choisi deux grands nombre premier p et q et un nombre aleatoire E.
Le produit n=pq et E sont place dans le catalogue public comme cle de codage : (n , E). Ainsi pour crypter un message, un utilisateur prend la cle publique, et effectue l'operation : Ci = Pi^E modulo n, ou Pi represente un bloc de nombre (le message a d'abord ete tranforme en nombre, puis scinde en bloc p1, p2, p3 etc...), sachant que chaque bloc Pi doit etre compris entre 0 et n-1 (valeurs comprises).
Comment obtenir la cle prive, qui servira à decrypter n'importe quel message crypte avec (n ,E)???
On fait intevenir l'indicateur d'Euler :
Je n'ais pas le temps d'expliquer bien l'indicateur d'Euler et du theoreme qui en debouche, retenez
simplement que :
on note §(n) = (p-1)(q-1) si n= pq.
§(n) garantie qu'il y'a toujour un inverse D de E modulo §(n)
On a ainsi : ED = 1(p-1)(q-1)
<=> D = 1/E(p-1)(q-1)
Pour decoder le destinataire eleve le nombre Pi a la puissance D-ieme, reduit modulot n.
P = C^D modulo n
Pour ceux qui veulent en savoir plus sur l'indicateur d'Euler allez voir les bouquins que je vous propose plus bas...
e-: systeme de codage DES :
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Le principe de DES est de crypter les messages par bloc de 64 bits. L'algorythme possede 19 etape distinctes
que nous verons en details plus bas. La cle prive est elle de 54 bits.
1-: transposition initiale du bloc de 64 bits.
On note qu'a cette etape la cle n'intervient pas.
2 a 17-: iterations (utilisation de la cle)
18-:invertissement de la premiere chaine de 32 bits avec la seconde.
19-: transposition finale. C'est la transposition inverse a la transposition initiale.
detail d'une iteration :
On imagine qu'on coupe un bloc de 64 bits en deux blocs de 32 bits.
On a donc a chaque iterations deux blocs de 32 bits en entre et sortie.
Le premier bloc en sortie est en fait qu'un simple copie du second bloc en entre.
Le seconde bloc de la sortie lui est le "ou exclusif" du premier bloc en entre et
d'une fonction f calcule a partir du second bloc.
On a donc soit G le premier bloc en entre et D le second. Soit G2 le 1er bloc en
sortie et D2 le second. Soit M' le message apres l'iteration.
M'= G2+(G (OU EX.) f(D, K))
<=> M' = D+(G (OU EX.) f(D, K'))
ou K est la cle utilise à l'etape étudié (il y 'en a 16)...
Dans chacune des iterations une cle differentes entre en jeu en fait. Avant le demarage de l'algorythme la cle K est tranposee sur 56 bits. On "decoupe" en suite cette cle en deux blocs de 28 bits avant chaque iterations sur lesquels on fait une permutation CIRCULAIRE vers la gauche x fois, x etant determine par l'iteration. Puis on fait une ultime transpositions et l'on obtient K', qui va servir a l'iteration .
Pour la construction de f je vous renvois au texte que j'ai join ci dessous que j'ai corrigé (en particulier
pour les variables).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Détail de la fonction f :
f prend pour arguments une chaîne de 32 bits, D et une chaîne de 56 bits, K'. Le résultat de f est sur 32 bits. Le calcul se décompose en 4
étapes:
1. D est "augmenté" en une chaîne de 48 bits suivant une fonction d'expansion E. E(A) est composé de tous les bits de D dans un certain ordre , 16 d'entre eux apparaissant deux fois.
2. E(D) (OU EX.) K' est calculé et le résultat B est découpé en 8 sous chaînes de 6 bits B=B1B2B3B4B5B6B7B8
3. On utilise maintenant huit boites-S S1...S8. Chaque Si est un tableau de 4x16 entiers compris entre 0 et 15. Etant donné
une sous-chaîne de six bits Bj = b1b2b3b4b5b6, on calcule une chaîne de quatre bits Sj(Bj) ainsi. Les deux bits b1b6
forment la représentation binaire de l'indice d'une ligne r de Sj (0=<r=<3) et les quatre bits b2B3B4B5 composent la
représentation binaire de l'indice d'une colonne c de la table (0=<c=<15). Sj(Bj) est alors la représentation binaire sur
quatre bits du coefficient Sj(r,c). On peut ainsi voir chaque Sj comme une fonction qui admet en entrée une chaîne de six
bits (ou une chaîne de deux et une chaîne de quatre) et produit une chaîne de quatre bits. De cette manière on calcule
Cj=Sj(Bj) (1=<j=<8)
4. La chaîne C=C1C2C3C4C5C6C7C8 de longueur 32 est réordonnée suivant une permutation fixée P. Le résultat P(C)
définit f(D,K')
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Chainage du DES :
le chainage de DES permet d'eviter une attaque assez courante dont je n'ais pas le temps d'expliquer le
principe ici... Ca sera pour une autre fois. L'une de ces methodes et le chainage par blocs de chiffrements.
Avant le chiffrement d'un bloc on calcule un OU EXCLUSIF avec le bloc precedant (de 64 bits donc) deja chiffre. Le premier bloc a un OU EXCLUSIF avec un vecteur d'initialisation. Ainsi on ne se retrouve plus qu'avec une serie de grosse substitution monoalphabetique (bloc par bloc) mais a une seule substitution
liee.
{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{Decryptage : cryptanalise}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
f-: Comment decrypter le systeme de codage à empilement ???
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Ce systeme est tres facilement decryptable, on a trouve l'alghorythme dans les annees 70/80. Par
consequent, pour des raisons de temps (underwayy 3 est en retard comme a son habitude d'ailleur), je ne
vais pas vous expliquer cette methode, en particulier par ce qu'il n'est plus utilise par personne.
Meme si son etude aurait ete tres interressante je laisse cela à d'autres.
g-: Comment decrypter le RSA ???
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
On a vu que le principe de base de RSA était la décomposition d'un nombre n en le produit de 2 nombres premiers. Une attaque assez
évidente de RSA serait donc de tenter de trouver la factorisation de n=pq. Cependant les plus puissants algorithmes existants à ce jour
ne peuvent résoudre ce problème pour plus de 130 chiffres alors qu'il existe des algorithmes très efficaces pour calculer les puissances
de nombres entiers modulo k. Ce n'est donc pas une menace très dangereuse si on choisit n de 200 chiffres et p, q de 100 chiffres.
Les attaques de RSA les plus percutantes et les plus novatrices sont certainement ce qu'on appelle les timing attacks.RSA consiste en
la programmation de la fonction R=y^x mod n, avec n public et y pouvant être intercepté par l'attaquant. Le but de l'attaquant sera
alors de trouver x, la clef secrète.Pour l'atttaque, la victime doit calculer y^x mod n pour quelqes valeurs de y où y, n et le temps de
calcul sont connus de l'attaquant. Notons au passage que si un nouvel exposant x est choisi pour chaque opération l'attaque ne
fonctionne plus. L'information nécessaire et les mesures de temps de calcul peuvent être obtenus à l'aide d' un protocole interactif
puisqu'un attaquant pourrait enregistrer les messages reçus par la cible et mesurer le temps mis pour répondre à chaque y.L'attaque
peut être traitée comme un problème de détection de signal. Le signal consiste en la variation de temps due aux exposants inconnus et
les propriétés du signal déterminent le nombre de mesures du temps requises pour l'attaque.Etant donnés j messages y0, y1, ..., yj-1
avec des mesures de temps correspondantes T0, T1, ..., Tj-1, la probabilité qu'une réponse xb pour le premier bit exposant b soit
correcte est proportionnelle à :
où t(yi,xb) est le temps requis pour les b premières itérations du calcul de yi^x mod n en utilisant le bit exposant xb, et F est la probabilité
attendue de distribution de T-t(y,xb) sur toutes les valeurs de y et xb correct. Comme F est définie comme la distribution de probabilité
de Ti-t(yi,xb), si xb est correct c'est la meilleure fonction pour pour prédire Ti-t(yi,xb).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
h-: Comment decrypter le DES ???
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Une des attaques les plus classiques de D.E.S. est la méthode de cryptanalyse différentielle, inventée par Biham et Shamir. Elle ne
donne pas de moyen de casser la fonction D.E.S. à 16 tours, mais elles permet une attaque efficace des variantes avec un nombre de
tours plus réduit.
Le principe de cette attaque est d'ignorer la permutation initiale IP et son inverse : elles ne jouent aucun rôle dans la cryptanalyse.
La cryptanalyse différentielle étudie la comparaison entre le ou-exclusif de deux textes clairs et le ou-exclusif des textes chiffrés
correspondant. En général on aura deux textes clairs L0R0 et L0*R0* avec un ou-exclusif spécifique L0'R0' = L0R0+L0*R0*
La meilleure façon d'étudier cette méthode est de prendre un exemple simple : un D.E.S à 3 tours.
Exemple
On commence avec une paire de textes clairs L0R0 et L0*R0* et leurs textes chiffrés L3R3 et L3*R3*.
On a R3 = L2+f(R2,K3) = R1+f(R2,K3)= L0+f(R0,K1)+f(R2,K3)
De même R3* = L2*+f(R2*,K3) = R1+f(R2*,K3)= L0+f(R0*,K1)+f(R2*,K3)
On a donc R3' = L0'+f(R0,K1)+f(R0*,K1)+f(R2,K3)+f(R2*,K3)
Si on suppose R0 = R0* on aurait f(R0,K1) = f(R0*,K1) alors R3' = L0'+f(R2,K3)+f(R2*,K3)
On peut calculer R3' à partir des textes cryptés et L0' à partir des textes clairs. On a alors f(R2,K3)+f(R2*,K3) = R3'+L0'
Or f(R2,K3)=P(C) et f(R2*,K3)=P(C*) où C et C* sont les sorties des huit boites S. Donc P(C)+P(C*) = R3'+L0'.
D'où C' = C+C* = P-1(R3'+L0')
R2 = L3 et R2* = L3* sont connus (ils font partie des textes chiffrés). On peut donc alors calculer E=E(L3) et E*=E*(L3*) à l'aide de la
description de la fonction d'expansion. Ces valeurs sont les entrées des boites-S du troisième tour. On connait donc E,E* et C' dans le
troisième tour. On peut alors appliquer de façon systématique le test suivant : testj(Ej,Ej*,Cj*) = {Bj+Ej : Bj E INj(Ej',Cj')}
où Ej' = Ej+Ej* et INj(Bj',Cj') = { Bj E (Z2)6 : Sj(Bj)+Sj(Bj+Bj') = Cj'}
On applique ce test sur les valeurs possibles de J1,...,J8. On trouve ainsi les 48 bits de K3, la clé du troisième tour. La clé de 56 bits se
calcule ensuite par une recherche exhaustive sur les 2^8=256 possibilités des huit bits inconnus.
Extension
On peut utiliser la cryptographie différentielle sur des D.E.S à plus de tour (cela fonctionne bien sur 6 tours). Mais contre des D.E.S. à 8
tours cela nécessite 2^14 textes clairs, 10 tours 2^24 et 16 tours 2^39 !!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
Voila, c fini. C'etait simple non ???
La prochaine fois je vous expliquerais IDEA, quelques autres methodes pour decrypter DES, on etudiera
en detail l'algorythme de PGP et un petit plus, parraissant anodin mais qui bien au contraire et l'une des base de la cryptographie moderne : les problemes intrinsequement difficiles (c'est a dire, ceux aux quels ont a faire les cryptanaliste quand il etudie RSA) ...
Bibliographie :
"Cryptographie appliquée" ; Bruce Schneider ; Vuibert
"Cryptographie, théorie et partiques" ; Stinson Douglas ; Vuibert
"Codes & Cryptographie" ; Welsh Dominic ; Oxford Sciences Publications
"Algorythmique et cryptographie" ; Robin Guy ; Ellipses
The blAck Hole
