Théorie des nombres€¦ · Il faut tester les 256 cl es di erentes, soit 72 057 595 037 927 936 cl es. La puissance des ordinateurs double tous les 18 mois environ : Pour garder

Cryptanalyse differentielle du DESCryptanalyse de RSA

Canaux caches - Side ChannelsBibliographie

Cryptanalyse

Saiida LAZAAR

Departement Mathematiques & InformatiqueENSA de Tanger

Universite AbdelMalek Essaadi

Professeur S. LAZAAR https://lazaarsaiida.wordpress.com



Avant propos

Notes de cours pour etudiants du Master et pour eleves Ingenieurs

c© S. LAZAAR, 2017-2018

Prerequis

Cryptographie




Menaces en temps reel

Attaques en temps reel: voirhttps://cybermap.kaspersky.com/fr/


https://cybermap.kaspersky.com/fr/

https://cybermap.kaspersky.com/fr/



Cryptanalyse

Plan du cours

• Introduction a la cryptanalyse• Principales Attaques contre RSA• Methodes de diffusion, confusion, collision, effet d’avalanche• Attaques differentielles, lineaires• Cryptanalyse de RSA avec les fractions continues• Cryptanalyse de RSA avec les courbes elliptiques• Cryptanalyse de AES• Attaque brute force contre un cryptosysteme base sur lesAutomates Cellulaires.• Vulnerabilites de SSL / TLS




Differents niveaux d’attaques

Nous avons, par ordre de difficulte decroissante, les niveauxsuivants :• Texte chiffre connu : Le cryptanalyste ne connaıt que le messagecode.• Texte clair connu : Le cryptanalyste connaıt un message en clairx et un message code• Texte clair choisi : Le cryptanalyste peut choisir un texte et lechiffrer pour obtenir le message code. Il a acces a une machinechiffrante.• Texte chiffre choisi : Le cryptanalyste peut choisir un textechiffre et obtenir le texte en clair. Il a acces temporairement a unemachine dechiffrante.




Cryptanalyse du chiffrement par decalage (Cesar)

• Elle est basee sur la recherche exhaustive de la cle : On testetoutes les cles possibles.

• Cette methode est brutale mais elle fonctionne bien et esttoujours a considerer grace a l’evolution rapide de la puissance desordinateurs.

• Dans le cas du chiffrement par decalage, il n’y a que 26possibilites, ce qui sera relativement rapide a tester.




Cryptanalyse par analyse de frequences

La subsitution monoalphabetique a resiste aux cryptanalystesjusqu’a ce que le savant Abu Yusuf Al Kindi mette au point(IXeme siecle) la technique d’analyse de frequences.

Principe:- Connaitre d’abord la langue de redaction du message.- Choisir un texte en clair dans la meme langue.- Compter les apparitions de chaque lettre.- Chiffrer et relever le nombre d’apparition des lettres.- Remplacer la lettre la plus frequente dans le texte chiffre par lapremiere lettre la plus frequente dans le texte en clair, etc.

Cette methode est efficace si le cryptogramme est suffisammentlong afin d’avoir des moyennes significatives.




Illustration




Cryptanalyse du DES

DES, quasi-incassable lors de sa creation, peut etre casse en moinsd’une journee grace au progres technologique.

La methode forte :

• Le test de toutes les cles possibles qui est une methode efficacemais longue.• Il faut tester les 256 cles differentes, soit

72 057 595 037 927 936 cles.• La puissance des ordinateurs double tous les 18 mois environ :Pour garder la meme fiabilite qu’en 1977, des experts suggerentque la cle passe a 112 bits afin de garder une securite optimalependant longtemps.




Cryptanalyse lineaire

Cryptanalyse differentielle

En 1990, Adi Shamir et Eli Biham ont invente la cryptanalysedifferentielle.

• Cette methode est appliquee aux algorithmes de chiffrement iteratifs

par blocs et aux fonctions de hachage.

Principe de la methode:• L’attaquant choisit des textes clairs presentant une differencefixe, calcule les chiffres et leurs differences puis assigne desprobabilites a certains types de cles.• Si le nombre d’essais augmente, la probabilite de decouvrir labonne cle augmente.• Dans le cas du DES simple, cette attaque necessite 247 textesclairs et 247 cryptogrammes pour retrouver la cle.• L’AES est resistant a ce type d’attaques.






• L’attaquant utilise des approximations lineaires pour decrire lesoperations conduisant au resultat chiffre.

• Plus le nombre d’essais augmente, plus la probabilite dedecouvrir la bonne cle augmente.

• Cette attaque est performante puisqu’elle necessite seulement243 textes clairs et 243 cryptogrammes pour retrouver une cle DES.

L’AES est resistant a ce type d’attaque.




Cryptanalyse de RSA

Elle s’appuie sur la cle publique pour retrouver la cle privee en un tempsraisonnable ou, a partir d’une partie de la cle privee. Dans la litterature,il existe de nombreuses techniques de cryptanalyse pour RSA longues etcomplexes.

• La resistance d’un texte crypte avec le RSA utilise le fait qu’il estextremement difficile de factoriser en facteurs premiers un grand nombre.

• Les methodes de cryptanalyse du RSA consistent a trouver des

algorithmes de factorisation de plus en plus evolues.

Cependant, il faudra remarquer qu’il a ete admis mais jamaisprouve que la factorisation de n etait necessaire pour casser lecode.




Nous devons nous concentrer sur les methodes qui permettent enfonction des informations publiques de :

Retrouver p et q.

Retrouver ϕ(N).

Retrouver d

En general, ces problemes ont une complexite egale.




Cles peu sures

Nous evoquerons les principales formes d’attaques contrel’algorithme RSA basees sur la factorisation de N.

Puisque ce probleme est considere comme NP-complet, il convientde relacher certaines contraintes pour se ramener a un problemesolvable en temps polynomial.

‘Tous les algorithmes connus pour resoudre des problemesNP-complets ont un temps d’execution exponentiel en la taille desdonnees d’entree dans le pire des cas, et sont donc inexploitablesen pratique meme pour des instances de taille moderee’.




Cles peu sures

Pour ce faire, nous chercherons a utiliser d’autres informationsdisponibles comme la cle publique.

En effet, afin de gagner en performance lors du chiffrement oudechiffrement, des cryptosystemes bases sur des formatsspecifiques de cles sont utilises.

Par exemple, on choisit souvent pour e les valeurs de 3, 17 ou65537 de la forme 2k + 1 pour limiter le nombre de multiplicationsa effectuer lors de l’exponentiation modulaire du chiffrement.




Methodes de factorisation d’entiers

Il existe 6 grands types d’algorithmes dont chacun a une taille pourlaquelle il est le plus efficace :

– Le crible d’Erathostene qui permet de trouver tous les nombrespremiers inferieurs a un certain entier naturel donne N.

– La methode de Rho de Pollard est un algorithme de decomposition enproduit de facteurs premiers seulement effectif pour factoriser les entiersnaturels avec de petits facteurs. Il fut concu par John M. Pollard en 1975.

– Les algorithmes p-1 et p+1 de Pollard: Ce soint algorithmes dedecomposition en produit de facteurs premiers, concus par John MichaelPollard en 1974.

Ils ne fonctionnent qu’avec des entiers dont les facteurs possedent une

forme particuliere.




Methodes de factorisation d’entiers

– La methode de factorisation par courbes elliptiques.

– Le crible quadratique: C’est un algorithme de factorisation fondesur l’arithmetique modulaire dont le temps d’execution dependuniquement de la taille de l’entier a factoriser, et non de proprietesparticulieres de celui-ci.

– Le crible algebrique ou le crible general de corps de nombres estl’algorithme fonde sur l’arithmetique modulaire pour ladecomposition en produit de facteurs premiers, il est le plusefficace des algorithmes classiques.




Fractions continues

Introduction

Une fraction continue est une expression de la forme :

a0 +1

a1 + 1a2+ 1

a3+ 1

...

= [a0, a1, a2, · · · ],

- Donner le developpement de√

2.- On considere l’equation x2 − 6x − 1 = 0. La solution de cetteequation est x = 3 +

√10. Ecrire le developpement en fractions

continues de x .




Fractions continues

Definition

Soit [a0, a1, a2, · · · ] une fraction continue d’un nombre x .- Les nombres entiers ai s’appellent les quotients partiels.- Les nombres [a0, a1, a2, · · · , ak ] s’appellent les reduites de x .

Si x est un nombre irrationnel, alors la suite des entiers ai estinfinie; on obtient une fraction continue infinie.Par contre, si x est rationnel, la suite ai s’arrete a un rang n et xs’ecrit: [a0, a1, a2, · · · , an].Ce qui correspond a:

x = a0 +1

a1 + 1a2+ 1

a3+ 1

...+ 1an




Fractions continues

Theoreme

Tout nombre reel positif x a une ecriture unique comme fractioncontinue:

x = a0 +1

a1 + 1a2+ 1

a3+ 1

...

= [a0, a1, a2, · · · ],

ou les ai sont des entiers positifs. De plus, la fraction continue estfinie si et seulement si le nombre x est rationnel.




Attaque de Wiener

- En 1990, Wiener a montre que si l’exposant prive d < 13N

14 alors

l’information contenue dans l’exposant publique e conduira a lafactorisation de la cle publique N = pq, ce qui conduira a p, q, d .

- Cette attaque est possible grace aux fractions continues.

Theoreme

Soit N = pq un module RSA ou les nombres premiers p et q sontde meme taille (q < p < 2q). Soit e < ϕ(N) un exposant publique

pour lequel la cle secrete d est assez petite: d < 13N

14 . Alors,

connaissant N et e, on peut calculer d et factoriser N.




Attaque de Wiener

Grandes lignes

Soit ϕ(N) = (p − 1)(q − 1) = pq − (p + q) + 1 ≈ N.Or, ed = 1modϕ(N), donc ∃ un entier k , ed − kϕ(N) = 1.Par consequent, e

ϕ(N) −kd = 1

dϕ(N) .

Enfin, on deduit que: eN ∼ k

d . On montre que | eN −kd | <

1d2 .

Le developpement en fraction continue de eN converge vers k

d quiconstitue une reduite de e

N , La convergence est realisee en tempslineaire.On teste les reduites successives. Et on s’arrete des que d permetde factoriser N.




Attaque de Wiener

Theoreme

Soit x est un nombre reel. Si pq est un nombre rationnel qui verifie

|x − p

q| < 1

2q2

alors pq est une convergente de x .




Algorithme probabiliste

Theoreme

Il existe un algorithme probabiliste de type Las Vegas ayant pourentrees le module n et les exposants de chiffrement et dedechiffrement e et d qui calcule la factorisation pq de n.




Comment trouver eN ?

Supposons que p et q soient deux entiers premiers. On resoudl’equation quadratique suivante:

(x − p)(x − q) = 0

ou les racines sont p et q.Nous deduisons alors que x2 − (p + q)x + pq = 0. Sachant quepq = N et ϕ(N) = (p − 1)(q − 1), on en deduit:

x2 − (N − ϕ(N) + 1)x + N = 0.

Or, ϕ(N) = ed−1k . Si la valeur de ϕ(N) est correcte, alors les

racines de l’equation quadratique seront la factorisation de N.




Les attaques par canaux caches

Objectifs : Utiliser les proprietes physiques du composant pourderober des informations sensibles.Les attaques par canaux auxiliaires (side channel attacks) utilisentles proprietes physiques d’un composant ou d’un microprocesseurpendant le processus de chiffrement pour avoir les cles servant asecuriser la transmission de l’information.

Attention : Les machines virtuelles peuvent etre attaquees. Lesattaques SCA sont basees sur l’information recuperee surl’implantation physique du crypto-systeme :

Information temporelle;

Consommation electrique;

Emanation electromagnetique;

Son;

Lumiere, etc.




Side channels

Dans certains cas, l’attaquant se contente d’observer les proprietesphysiques du composant, et de les capter : Attaques passives.




Side channels

Dans d’autres cas, l’attaquant utilise du materiel (rayon laser,sonde, introduction volontaire d’erreurs pour provoquer certainscomportements revelateurs du composant), pour s’emparer del’information lors du calcul.

Il s’agit d’Attaques actives.




Bibliographie

Bibliographie

GILLES LACHAUD. Revue La Recherche, n.346, Octobre2001, pp. 24-30.

William Stallings. Securite des reseaux. Applications etstandards. Vuibert 2002.

Saiida LAZAAR. Securite des reseaux et cryptographie.Edilivre ISBN 2334085693, Mars 2016.

Christophe Grenier. Techniques de cryptanalyse de RSA, 2009.

https://lipn.univ-paris13.fr/ poinsot/Articles/SRenAction-Crypto.pdf

https://www.telecom-paristech.fr/f

https://www.miximum.fr/


Documents

Théorie des nombres€¦ · Il faut tester les 256 cl es di erentes, soit 72 057 595 037 927 936 cl es. La puissance des ordinateurs double tous les 18 mois environ : Pour garder