Introduction a la Cryptologie Chapitre Le cryptosysteme RSA

Michael Eisermann

Description

Niveau: Supérieur, Master
Introduction a la Cryptologie Chapitre 6 : Le cryptosysteme RSA Michael Eisermann (Institut Fourier, UJF Grenoble) Annee 2008-2009 IF / IMAG, Master 1, S1-S2 document mis a jour le 7 juillet 2009FOURIERINSTITUTfi www-fourier.ujf-grenoble.fr/~eiserm/cours _ crypto

• cryptosysteme rsa


• fourierinstitutfi www-fourier


• developpement mathematique


• algorithmes precedents


• test de primalite selon miller–rabin

Informations

• Publié par: profil-infoe-2012
• Nombre de lectures: 32
• Langue: Français

Extrait

Introduction a` la Cryptologie
Chapitre 6 : Le cryptosysteme` RSA
Michael Eisermann (Institut Fourier, UJF Grenoble)
Annee´ 2008-2009
IF / IMAG, Master 1, S1-S2
document mis a` jour le 7 juillet 2009
INSTITUTi f FOURIER
www-fourier.ujf-grenoble.fr/~eiserm/cours#cryptoDev´ eloppement algorithmique : implementation´ de RSA.
Assembler tous les algorithmes prec´ edents´ .
Production des grands nombres premiers.
Objectifs de ce chapitre
Dev´ eloppement mathematique´ : le cryptosysteme` RSA.
Le petit theor´ eme` de Fermat.
Le test de primalite´ selon Miller–Rabin.Objectifs de ce chapitre
Dev´ eloppement mathematique´ : le cryptosysteme` RSA.
Le petit theor´ eme` de Fermat.
Le test de primalite´ selon Miller–Rabin.
Dev´ eloppement algorithmique : implementation´ de RSA.
Assembler tous les algorithmes prec´ edents´ .
Production des grands nombres premiers.Sommaire
1 Le cryptosysteme` RSA
2 Grands nombres premiersSommaire
1 Le cryptosysteme` RSA
Le petit theor´ eme` de Fermat
Le cryptosysteme` RSA
Signature et authentification
2 Grands nombres premiersDemonstration.´ Poura;b2Z on a
!
pX pp k p k p p(a +b) = a b a +b mod p:
k
k=0

pRappel : sip2N est premier et 0<k<p, alorsp divise .
k
p pOn a 0 = 0 et 1 = 1, puis on procede` par recurrence´ sura2N :
p p p(a + 1) a + 1 a + 1 mod p:
p pSia< 0 on conclut para ( a) ( a)a mod p.
Corollaire (petit Fermat, formulation dansZ= )p
p p 1 ´ ´Soitp premier. Toutx2Z=p verifiex =x et toutx2Z= verifiex = 1.p
Demonstration.´ Toutx2Z= s’ecr´ it commex =a ou` a2Z.p
p p p pDansZ on aa a mod p. DansZ= on a doncx =a =a =a =x.p
p p 1 Pourx2Z= =Z= l’egalit´ e´ x =x impliquex = 1.p p
Le petit theor´ eme` de Fermat
´ `Theoreme (petit Fermat, formulation dansZ)
pSip2N est premier alors touta2Z ver´ ifiea a mod p.
pRappel : sip2N est premier et 0<k<p, alorsp divise .
k
p pOn a 0 = 0 et 1 = 1, puis on procede` par recurrence´ sura2N :
p p p(a + 1) a + 1 a + 1 mod p:
p pSia< 0 on conclut para ( a) ( a)a mod p.
Corollaire (petit Fermat, formulation dansZ= )p
p p 1 ´ ´Soitp premier. Toutx2Z=p verifiex =x et toutx2Z= verifiex = 1.p
Demonstration.´ Toutx2Z= s’ecr´ it commex =a ou` a2Z.p
p p p pDansZ on aa a mod p. DansZ= on a doncx =a =a =a =x.p
p p 1 Pourx2Z= =Z= l’egalit´ e´ x =x impliquex = 1.p p
Le petit theor´ eme` de Fermat
´ `Theoreme (petit Fermat, formulation dansZ)
pSip2N est premier alors touta2Z ver´ ifiea a mod p.
Demonstration.´ Poura;b2Z on a
!
pX pp k p k p p(a +b) = a b a +b mod p:
k
k=0p pOn a 0 = 0 et 1 = 1, puis on procede` par recurrence´ sura2N :
p p p(a + 1) a + 1 a + 1 mod p:
p pSia< 0 on conclut para ( a) ( a)a mod p.
Corollaire (petit Fermat, formulation dansZ= )p
p p 1 ´ ´Soitp premier. Toutx2Z=p verifiex =x et toutx2Z= verifiex = 1.p
Demonstration.´ Toutx2Z= s’ecr´ it commex =a ou` a2Z.p
p p p pDansZ on aa a mod p. DansZ= on a doncx =a =a =a =x.p
p p 1 Pourx2Z= =Z= l’egalit´ e´ x =x impliquex = 1.p p
Le petit theor´ eme` de Fermat
´ `Theoreme (petit Fermat, formulation dansZ)
pSip2N est premier alors touta2Z ver´ ifiea a mod p.
Demonstration.´ Poura;b2Z on a
!
pX pp k p k p p(a +b) = a b a +b mod p:
k
k=0

pRappel : sip2N est premier et 0<k<p, alorsp divise .
kp pSia< 0 on conclut para ( a) ( a)a mod p.
Corollaire (petit Fermat, formulation dansZ= )p
p p 1 ´ ´Soitp premier. Toutx2Z=p verifiex =x et toutx2Z= verifiex = 1.p
Demonstration.´ Toutx2Z= s’ecr´ it commex =a ou` a2Z.p
p p p pDansZ on aa a mod p. DansZ= on a doncx =a =a =a =x.p
p p 1 Pourx2Z= =Z= l’egalit´ e´ x =x impliquex = 1.p p
Le petit theor´ eme` de Fermat
´ `Theoreme (petit Fermat, formulation dansZ)
pSip2N est premier alors touta2Z ver´ ifiea a mod p.
Demonstration.´ Poura;b2Z on a
!
pX pp k p k p p(a +b) = a b a +b mod p:
k
k=0

pRappel : sip2N est premier et 0<k<p, alorsp divise .
k
p pOn a 0 = 0 et 1 = 1, puis on procede` par recurrence´ sura2N :
p p p(a + 1) a + 1 a + 1 mod p:Corollaire (petit Fermat, formulation dansZ= )p
p p 1 ´ ´Soitp premier. Toutx2Z=p verifiex =x et toutx2Z= verifiex = 1.p
Demonstration.´ Toutx2Z= s’ecr´ it commex =a ou` a2Z.p
p p p pDansZ on aa a mod p. DansZ= on a doncx =a =a =a =x.p
p p 1 Pourx2Z= =Z= l’egalit´ e´ x =x impliquex = 1.p p
Le petit theor´ eme` de Fermat
´ `Theoreme (petit Fermat, formulation dansZ)
pSip2N est premier alors touta2Z ver´ ifiea a mod p.
Demonstration.´ Poura;b2Z on a
!
pX pp k p k p p(a +b) = a b a +b mod p:
k
k=0

pRappel : sip2N est premier et 0<k<p, alorsp divise .
k
p pOn a 0 = 0 et 1 = 1, puis on procede` par recurrence´ sura2N :
p p p(a + 1) a + 1 a + 1 mod p:
p pSia< 0 on conclut para ( a) ( a)a mod p.