Introduction a la Cryptologie Chapitre Le cryptosysteme RSA

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.