Justification du cryptage RSA
Troisième partie : Propriété justifiant le cryptage RSA

Nous avons établi deux démonstrations différentes dans le but de justifier le principe du cryptage RSA. Nous présentons d’abord la démonstration la plus rapide, la seconde étant plus longue mais intéressante également. Ces deux démonstrations vont utiliser les théorèmes démontrés précédemment.  

 

 

Montrons que, p et q étant deux nombres premiers distincts, a étant un entier naturel et r tel que r º 1 [(p-1)(q-1)], alors a^r º a [pq]  

                       

r = k(p-1)(q-1) + 1

a^r = a^{k(q-1)(p-1)+1}

 

D’après le théorème j,

a^{k(q-1)(p-1)+1} º a [p]

a^r º a [p]

p divise a^r – a

                                                                                                                                               

De même on montre que q divise a^r – a

p et q étant premiers entre eux (p et q premiers et distincts), d’après le théorème e pq divise a^r – a ce qui revient à a^r º a [pq]  

 

 

Montrons que, p et q étant deux nombres premiers distincts et r tel que r º 1 [(p-1)(q-1)], alors p^r º p [pq]

 

p divise p^r – p

Or r º 1 [(p-1)(q-1)]

Donc p^r – p = p^{(p-1)(q-1)*d + 1} – p

p^r – p = p( p^(p-1)(q-1)*d – 1)

p^r – p = p( [p^d(p-1)]^q-1 – 1)

Or p L q = 1

Donc p^d(p-1) L q = 1

 

En utilisant la seconde forme du petit théorème de Fermat, on obtient que q divise [p^d(p-1)]^q-1 – 1

q divise donc p^r – p

Or on p divise aussi p^r – p, de plus p et q sont premiers entre eux, donc par théorème pq divise p^r – p. Ce qui s’écrit également p^r º p [pq]

 

Montrons ensuite que p et q étant premiers avec p distinct de q, r étant tel que r º1 [(p-1)(q-1)], alors a^r º a [(p-1)(q-1)]

 

Cas 1 :

si a = p^k, k appartient à N

D’après la démonstration précédente, 

p^r º p [pq]

Par théorème,

p^kr º p^k [pq]

a^r º a [pq]  

Cas 2 :

si a = q^l, l appartient à N

de même, a^r º a [pq]

 

Cas 3 :

si a L b = 1 et a L q = 1

alors, a^q-1 L p = 1                     

donc d’après le petit théorème de Fermat,

(a^q-1)^p-1 = 1 [p]

p divise a^(p-1)(q-1) – 1

de même q divise a^(p-1)(q-1) – 1

                                                                                                                       

Donc par théorème, p et q étant premiers, pq divise a^(p-1)(q-1) :

a^(p-1)(q-1) º 1 [pq]

a^d(p-1)(q-1) º 1 [pq], d appartient à N

a^{d(p-1)(q-1)+1} º a [pq]

a^r º a [pq]

 

Cas 4 : (cas général)

Si a = p^kq^la’ avec a’ L p = 1 et a’ L q = 1

a^r º p^krq^lra’^r [pq]

Or d’après le cas 1, (p^k)^r º p [pq]

D’après le cas 2, (q^l)^r º q [pq]

D’après le cas 3, a’^r º a’ [pq]

Donc on obtient :

a^r º p^kq^la’ [pq]

a^r º a [pq]