[PDF] CRYPTANALYSE DE RSA Jan 2 2015 Algorithme 2 :





Previous PDF Next PDF



Algorithmique Cours 5 : Cryptographie et cryptosystème RSA ROB3

Algorithmes de chiffrement. Deux classes d'algorithmes de chiffrement : ?. Cryptographie symétrique (ou à clé privé). Les clés de cryptage et de décryptage 



Cryptosystème RSA

Cryptosystème RSA. Anca Nitulescu anca.nitulescu@ens.fr Algorithme d'Euclide étendu ... L'algorithme d'Euclid étendu calcule des coeficients (uv).



La cryptographie asymétrique avec RSA

Aug 12 2019 Ce que l'on appelle RSA est un algorithme de chiffrement et déchiffrement. ... l'Union Européenne



Sur lalgorithme RSA

Enfin on va calculer la valeur de ? en un produit de deux nombres premiers distincts. Ceci nous servira en effet dans l'algorithme RSA. Lemme 1.1 Soient p et q 



La sécurité informatique

Cryptologie - Clé publique - A08. 12. Premier algorithme à clé publique – RSA. ? Cet algorithme a été proposé en 1977 par Rivest Shamir et.



La cryptographie RSA

Le cryptage RSA du nom de ses concepteurs



Grands nombres premiers Cryptographie RSA

L'algorithme procède par élimination : il s'agit de supprimer de la table complète de tous les entiers allant de 2 jusqu'à n tous les entiers qui sont 



CRYPTANALYSE DE RSA

Jan 2 2015 Algorithme 2 : Fabrication des clés. Entrée : Deux nombres premiers p et q. Sortie : Une clé privée d et une clé publique e. 1: Calculer ?(N)=(p ...



Analyse cryptographique des altérations dalgorithmes

Aug 12 2011 Algorithme de signature numérique standardisé par le NIST aux États-. Unis



TP : RSA 1 Algorithmes de RSA avec bc

Comprendre les algorithmes mis en jeu dans le système RSA. 2. Utiliser OpenSSL pour chiffrer/déchiffrer des clés avec RSA. Outils : bc calulateur de précision 



[PDF] Cryptosystème RSA - DI ENS

Il existe u et v tels que xu + nv = pgcd(xn) = 1 Trouver l'inverse d'un élément revient à calculer u L'algorithme d'Euclid étendu calcule des coeficients 



[PDF] Algorithmique Cours 5 : Cryptographie et cryptosystème RSA ROB3

Algorithmes de chiffrement Deux classes d'algorithmes de chiffrement : ? Cryptographie symétrique (ou à clé privé) Les clés de cryptage et de décryptage 



[PDF] Sur lalgorithme RSA

Le RSA a été inventé par Rivest Shamir et Adleman en 1978 C'est l'exemple le plus courant de cryptographie asymétrique toujours considéré comme sûr



[PDF] La cryptographie RSA

Le cryptage RSA du nom de ses concepteurs Ron Rivest Adi Shamir et Leonard Adleman est le premier algorithme de chiffrement asymétrique Il a été découvert 



[PDF] Grands nombres premiers Cryptographie RSA

Grands nombres premiers Cryptographie RSA François DE MARÇAY Département de Mathématiques d'Orsay Université Paris-Sud France 1 Limitations physiques



[PDF] La cryptographie asymétrique avec RSA - Zeste de Savoir

12 août 2019 · 1 Un peu d'histoire et beaucoup de mathématiques Ce que l'on appelle RSA est un algorithme de chiffrement et déchiffrement



[PDF] [RSA : Rivest Shamir Adleman] - Zenk - Security

Présentation du RSA Comment génère t'on les clés publique privé ? Algorithme de Bézout Pseudo-code RSA Présentation pratique en JAVA Etude de la sécurité 



[PDF] CRYPTANALYSE DE RSA - Abderrahmane Nitaj

Algorithme 1 : Fabrication du module Entrée : Une taille t pour le module du cryptosyt`eme RSA Sortie : Un module RSA N de taille t



[PDF] Cryptographie RSA - Laure Gonnord

Rivest Shamir Adleman ou RSA est un algorithme asymétrique de cryptographie à clé publique très utilisé dans le commerce électronique et plus généralement 



[PDF] La cryptographie RSA vingt ans après - Apprendre-en-lignenet

L'algorithme RSA est moins rapide que les algorithmes classiques à une seule clef ce qui est un handicap lorsque l'on doit coder des messages volumineux Aussi 

  • Comment fonctionne l'algorithme RSA ?

    Le cryptage RSA fonctionne en utilisant une paire de clés - clés publiques et privées - pour crypter et décrypter les données. La clé publique est utilisée pour chiffrer les données, tandis que la clé privée est utilisée pour déchiffrer les données.

  • Comment coder en RSA ?

    Protocole RSA pour le codage
    e × d + m × (p – 1)(q – 1) = 1 Pour ce faire, elle peut utiliser un algorithme de calcul très connu depuis l'Antiquité (vers 300 ans avant Jésus-Christ) appelé algorithme d'Euclide. Elle calcule également n = p × q.

  • Quels sont les deux outils mathématiques indispensables du chiffrement RSA ?

    RSA a besoin d'une clé publique (constituée de 2 nombres (n,e) ) et d'une clé privée (1 seul nombre d ). Avec ces nombres, le couple (n,e) est appelée la clé publique et le nombre d est la clé privée.

  • Algorithmes de cryptographie symétrique (à clé secrète)

    Chiffre de Vernam (le seul offrant une sécurité théorique absolue, à condition que la clé ait au moins la même longueur que le message à chiffrer, qu'elle ne soit utilisée qu'une seule fois et qu'elle soit totalement aléatoire)DES.3DES.AES.RC4.RC5.MISTY1.
CRYPTANALYSE DE RSA

CRYPTANALYSE DE RSA

Abderrahmane Nitaj

Laboratoire de Mathematiques Nicolas Oresme

Universite de Caen, France

http://www.math.unicaen.fr/ ~nitaj nitaj@math.unicaen.fr c

Version du 28 juin 2009

Table des matieres

Contenu i

Preface 1

1 Introduction au cryptosysteme RSA 3

1.1 Principe de RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1.1 Le module RSA . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1.2 Les cles publiques et privees . . . . . . . . . . . . . . . . . . .

5

1.1.3 Envoi d'un message . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1.4 Dechirement d'un message . . . . . . . . . . . . . . . . . . .

8

1.1.5 Signature d'un message . . . . . . . . . . . . . . . . . . . . . .

9

1.1.6 Preuve de RSA . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.2 Un exemple d'utilisation de RSA . . . . . . . . . . . . . . . . . . . .

12

1.2.1 Transformation d'un texte en nombres . . . . . . . . . . . . .

12

1.2.2 L'exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

1.3 Cryptanalyses elementaires de RSA . . . . . . . . . . . . . . . . . .

15

1.3.1 Cryptanalyse de RSA connaissant'(N) . . . . . . . . . . . .15

1.3.2 Utilisation du m^eme module et deux exposants dierents . . .

16

1.3.3 Utilisation de modules dierents pour le m^eme message. . . .

18

1.3.4 Cryptanalyse de RSA sijpqj< cN1=4: Methode de Fermat21

2 Cryptanalyse de RSA par les fractions continues 25

2.1 Les fractions continues . . . . . . . . . . . . . . . . . . . . . . . . . .

25
i iiTABLE DES MATIERES

2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.1.2 Denitions et proprietes . . . . . . . . . . . . . . . . . . . . .

26

2.2 Cryptanalyse de RSA par les fractions continues . . . . . . . . . . . .

37

2.2.1 L'attaque de Wiener . . . . . . . . . . . . . . . . . . . . . . .

38

3 Cryptanalyse de RSA par l'algorithme LLL 43

3.1 L'algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

3.1.1 Introduction aux reseaux . . . . . . . . . . . . . . . . . . . . .

43

3.1.2 L'algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . .

50

3.2 Cryptanalyse de RSA par la reduction des reseaux . . . . . . . . . . .

59

3.2.1 La methode de Coppersmith : polyn^omes a une variable . . .

59

3.2.2 Factorisation deN. . . . . . . . . . . . . . . . . . . . . . . .69

Bibliographie 73

Preface

Si vous enseignez a un homme, vous n'enseignez qu'a une personne. Si vous enseignez a une femme, vous enseignez a toute une famille.

KA"IÒÊ" Y®¯è

@QÓ@

IÒÊ" @X@

AÓ @ ,@XQ¯IÒÊ" Y®¯ Cg.PIÒÊ" @X@ La cryptographie moderne est basee sur les mathematiques pour securiser l'infor- mation. On distingue deux types de protocoles cryptographiques : la cryptographie a cle privee et la cryptographie a cle publique. La cryptographie a cle publique a ete introduite par Whiteld Die et Martin Hellman en 1976, marquant ainsi la nais- sance de la cryptographie moderne. Le principe de la cryptographie a cle publique repose sur deux types de cles : une cle publique et une cle privee. Pour chirer un message, on utilise la cle publique de son destinataire. Alors, seul le destinataire peut dechirer le message recu avec sa propre cle privee. En 1978, Ronald Rivest, Adi Shamir et Leonard Adleman ont propose le premier cryptosysteme a cle publique, appeleRSA. Ce cryptosysteme est devenu le plus repandu dans le monde car il est facile a realiser mais tres dicile a casser. En eet, sa securite repose sur l'un des problemes les plus diciles en mathematiques : la factorisation des grand nombres. Dans ce travail, nous introduisons les principes generaux du cryptosysteme RSA ainsi que certaines attaques permettant de le casser, si les parametres de securite sont mal choisis ou s'il verient des relations permettant a un attaquant d'en tirer prot. Dans le chapitre 1, nous donnons les principes generaux du cryptosysteme RSA et nous presentons quelques attaques elementaires permettant de le casser. Dans le chapitre 2, nous presentons une introduction a la theorie des fractions continues et leur utilisation pour attaquer le cryptosysteme RSA dans certains cas. Dans le chapitre 3, nous presentons quelques aspects de la reduction des reseaux, plus precisement l'algorithmeLLLet son utilisation pour attaquer le cryptosysteme RSA gr^ace a la methode de Coppersmith. Dans ce travail, la plupart des resultats sont illustres par des algorithmes pro- grammes a l'aide des systemes de calculMaple 12etMagamadont un calculateur 1

2TABLE DES MATIERES

en ligne est a l'adressehttp://magma.maths.usyd.edu.au/calc/.

Chapitre 1

Introduction au cryptosysteme

RSACelui qui n'aime pas gravir les montagnes, vivra toute sa vie dans les trous.

Abou Al Qasim Achabi

.Q®mÌ'@á

K.QëYË@YK.

ÈAJ.m.Ì'@Xñª“I.m'

BáÓð

G.A‚Ë@ Õae...A®Ë@ ñK.@1.1 Principe de RSA Toutes les operation du cryptosysteme RSA se passe dans un ensemble de nombre entiers. Soientpetqdeux nombres premiers assez grands. On noteN=pq. Le nombreNest appelemodule RSA. Supposons que deux personnesAetBveulent communiquer de facon s^ure en utilisant le cryptosysteme RSA. Pour cela, ils doivent, chacun de son cote preparer un module RSA, deux cleseetd, executer une procedure de chirement et de signature et une procedure de dechirement et de verication de la signature.

1.1.1 Le module RSA

Avant tout, pour utiliser le cryptosysteme RSA, chacun des intervenants A et B doit fabriquer son propre module RSA. L'algorithme 1 peut ^etre alors utilise. 3

4CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTEME RSAAlgorithme 1: Fabrication du moduleEntree :Une tailletpour le module du cryptosyteme RSA.

Sortie :Un module RSANde taillet.

1:Prendre un nombre premier aleatoirepdans l'intervalleh

2t2 ;2t+12 i

2:Prendre un nombre premier aleatoireqdans l'intervalleh

2t2 ;2t+12 i

3:Sip=qalors

4:Aller a l'etape 2.

5:Sinon

6:N=pq.

7:Fin SiCommepetqsont dans l'intervalleh

2t2 ;2t+12 i , alors on a 2 t< pq <2t+1; ce qui montre queN=pqest de taillet.

Maple 1.1.1.

Avec Maple 12, l'algorithme 1 peut ^etre realise comme ceci.Programme t:=1024: x1:=round(2.0^(t/2)): x2:=round(2.0^((t+1)/2)): m1:=(rand(x1 .. x2))(): p:=nextprime(m1); m2:=rand(x1 .. x2)(): q:=nextprime(m2);

N:=p*qCommentaires

<----- la taille du module RSA <----- la borne inferieur 2^(t/2) <----- la borne superieur 2^((t+1)/2) <----- une valeur aleatoire <----- le nombre premier p <----- une valeur aleatoire <----- le nombre premier q <----- le module RSAMagma 1.1.2. Avec Magma, l'algorithme 1 peut ^etre realise comme ceci.

1.1. PRINCIPE DE RSA5Programme

t:=1024; x1:=Round(2.0^(t/2)); x2:=Round(2.0^((t+1)/2)); m1:=Random(x1,x2); p:=NextPrime(m1); m2:=Random(x1,x2); q:=NextPrime(m2);

N:=p*q;

N;Commentaire

<----- la taille du module RSA <----- la borne inferieur 2^(t/2) <----- la borne superieur 2^((t+1)/2) <----- une valeur aleatoire <----- le nombre premier p <----- une valeur aleatoire <----- le nombre premier q <----- le module RSA <----- affichage du module RSADans Magma, la fonctionRSAModulus(t,e)permet de creer un module RSAN at-bits tel que pgcd(e;(N)) = 1. Voici un exemple et sa verication.Programme t:=100; e:=3;

N:=RSAModulus(t,e);

N; f:=Factorization(N); f;

Log(N)/Log(2);

p:=f[1,1]; q:=f[2,1]; p; q;Commentaire <--- Taille du module <--- L'exposant publique <--- Creation du module <--- Affichage de N <--- Sa factorization <--- Affichage de la factorisation <--- Taille du module <--- Premier nombre premier <--- Deuxieme nombre premier <--- Affichage de p <--- Affichage de p1.1.2 Les cles publiques et privees Apres avoir fabrique un module RSA, chacun des intervenants doit preparer une cle secretedet une cle publiquee: Dans certains cas, on peut prendre pour la cle publique des valeurs speciques, par exemplee= 3 oue= 216+1. Dans ce cas, les etapes 2 a 5 de l'algorithme 2 ne sont pas executees. La fonctionjoue un r^ole central dans le cryptosysteme RSA et s'appelle la fonction d'Euler. Denition 1.1.3.Soitnun nombre entier. La fonction indicatrice d'Euler est (n) = #faj0an1;pgcd(a;n) = 1g:

6CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTEME RSAAlgorithme 2: Fabrication des clesEntree :Deux nombres premierspetq.

Sortie :Une cle priveedet une cle publiquee.

1:Calculer(N) = (p1)(q1).

2:Prendre un nombre aleatoireedans l'intervalle [1;(N)].

3:Sipgcd(e;(N))6= 1alors

4:Aller a l'etape 2.

5:Sinon

6:Calculerde1(mod(N)).

7:Fin SiCette fonction est denie pour tout entiern2. Si la decomposition en facteurs

premiers est n=sY i=1p xii; alors on a : (n) =sY i=1p xi1 i(pi1):

Maple 1.1.4.

Dans Maple 12, la fonctionest tout simplementphi. Attention, pour calculer (N), Maple est oblige de factoriserN, ce qui peut ^etre tres dicile siNest du type module de RSA.Programme with(numtheory):

N:=5*8*61:

phi(N);Commentaires <--- Package numtheory "Theorie des Nombres" <--- un exemple simple <--- Calcul de phi(n)La reponse est immediate : 960.

Magma 1.1.5.

Dans Magma, la fonctionest tout simplementEulerPhi. Attention, pour calculer (N), Magma aussi est oblige de factoriserN, ce qui peut ^etre tres dicile siNest du type module de RSA.Programme

N:=5*8*61:

EulerPhi(N);Commentaires

<--- un exemple simple <--- Calcul de phi(N)Maple 1.1.6.

1.1. PRINCIPE DE RSA7

Avec Maple 12, l'algorithme 2 peut ^etre ecrit comme ceci ou on suppose que la procedure 1.1.1 a ete executee.Programme phi:=(p-1)*(q-1): e:=rand(3..phi/2)(): while(gcd(e,phi) <> 1) do e:=rand(3..phi)(); od; d := modp(1/e, phi);Commentaires <--- L'indicateur d'Euler <--- On choisit un exposant e aleatoire <--- il faut que pgcd(e,phi)=1 <--- On reprend un autre exposant e <--- d est l'inverse de d modulo phiMagma 1.1.7. Avec Magma, l'algorithme 2 peut ^etre ecrit comme ceci.Programme t:=102; x1:=Round(2.0^(t/2)); x2:=Round(2.0^((t+1)/2)); m1:=Random(x1,x2); p:=NextPrime(m1); m2:=Random(x1,x2); q:=NextPrime(m2);

N:=p*q;

N; phi:=(p-1)*(q-1); e:=Random(3,Round(phi/2)); while(GCD(e,phi) gt 1) do e:=Random(3,Round(phi/2)); end while; d:= InverseMod(e,phi); d;Programme <-- Taille du module <-- Valeur aleatoire <-- Valeur aleatoire <-- Valeur aleatoire <-- Premier nombre premier <-- Valeur aleatoire <-- deuxieme nombre premier <-- Module RSA <-- Valeur de N <-- phi <-- Un exposant public aleatoire <-- procedure de recherche <-- GCD(e,phi)=1 <-- Inverse de e modulo phi <-- Valeur de l'exposant prive1.1.3 Envoi d'un message Supposons maintenant que les intervenants A et B possedent chacun son module

RSA et ses cles,NA,eA,dApour A etNB,eB,dBpour B.

Si A veut envoyer un message a B, il peut proceder comme dans l'algorithme 3.

Maple 1.1.8.

8CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTEME RSAAlgorithme 3: Chirement d'un messageEntree :Un message clair et la cle publique (NB;eB).

Sortie :Un message chireC.

1:Transformer le message en un nombre entierMde l'intervalle [2;NB].

2:CalculerCMeB(modNB).

3:Envoyer le messageC.Avec Maple 12, l'algorithme 3 peut ^etre programme de la facon suivante.

Programme

M:=12345:

C:=modp(M&^e,N):Commentaires

<--- un exemple simple de message <--- &^ permet de calculer M^e modulo NMagma 1.1.9. Avec Magma, l'algorithme 3 peut ^etre programme de la facon suivante.Programme

M:=12345;

C:=Modexp(M,e,N);Commentaires

<--- un exemple simple de message <--- Fonction pour calculer M^e modulo N1.1.4 Dechirement d'un message Supposons enn queBa recu un message chireCde la part de A. Alors B peut le

dechirer en utilisant sa cle secretedBcomme dans l'algorithme 4.Algorithme 4: Dechirement d'un messageEntree :Un message chireCet la cle privee (NB;dB).

Sortie :Un message clairM.

1:CalculerMCdB(modNB).

2:Transformer le nombreMen un message clair.Maple 1.1.10.

Avec Maple 12, l'algorithme 4 qui permet de dechirer un messageCpeut ^etre le suivant.Programme

M2:=modp(C&^d,N):

M-M2Commentaires

<--- Calcul de C^d modulo N <--- Permet de verifier que M2=M

1.1. PRINCIPE DE RSA9

Magma 1.1.11.

Avec Magma, l'algorithme 4 qui permet de dechirer un messageCpeut ^etre le suivant.Programme

M2:=Modexp(C,d,N);

M-M2;Commentaires

<--- Calcul de C^d modulo N <--- Permet de verifier que M2=M1.1.5 Signature d'un message Supposons que A veut envoyer un messageMa B. Comment B peut-il ^etre s^ur que le message recu a bien ete envoye par A. Pour resoudre ce probleme, RSA peut ^etre utilise aussi bien pour transmettre un message que pour le signer. Pour cela, A et B doivent avoir chacun ses cles publiques et privees,NA,eA,dApour

A etNB,eB,dBpour B.

Tout d'abord, A utilise la cle publique (NB;eB) de B pour transmettre le message Cet produire une signatureSdu message a l'aide de sa propre cle privee (NA;eA). En eet, A doit produire et transmettreCetScomme ceci (voir algorithme 5).

CMeB(modNB); S=CdA(modNA):

En possession du message chireCet de la signatureS, B peut alors verier si c'est bien A qui a transmit ce message en utilisant la cle publique (NA;eA) de A, du fait de la relation (voir algorithme 6). Squotesdbs_dbs30.pdfusesText_36
[PDF] algorithme rsa exercice corrigé

[PDF] cryptage rsa exemple

[PDF] cryptographie asymétrique algorithme

[PDF] chiffrement asymétrique et symétrique

[PDF] chiffrement asymétrique exemple

[PDF] cryptographie exercices corrigés pdf

[PDF] les nombres en lettres pdf

[PDF] les nombres en lettres de 0 ? 1000

[PDF] ap seconde chiffres significatifs

[PDF] chiffres significatifs excel

[PDF] les chiffres significatifs cours

[PDF] chiffres significatifs sinus

[PDF] precision d une mesure et chiffres significatifs

[PDF] chiffres significatifs exacts

[PDF] chiffres significatifs exos