Leçon 7: Arithmétique des nombres entiers

VN2016 · June 2017

Bonjour,
Pour la leçon 7, je décide de parler de la cryptographie R.S.A. Pourtant, je ne comprends pas pourquoi, il faut choisir l'exposant 0 < e < (p-1)(q-1)? pareil pourquoi 1 =< d < (p-1)(q-1). Qu'est-ce qui se passe si e et d n'appartiennent pas à cet intervalle?
Merci pour vos réponses.

michael · June 2017

Salut,

je ne maîtrise pas assez RSA pour t'en donner tous les tenants et aboutissants mais, de ce que j'en ai compris :

* sur le plan théorique, choisir $e$ entre $0$ et $\varphi(pq)$ ($\varphi$ désignant bien entendu l'indicatrice d'Euler) ne change rien dès lors que $e$ et $\varphi(pq)$ sont premiers entre eux. Sur le plan pratique, je n'en sais rien.

* Concernant $d$, le choisir entre $0$ et $\varphi (pq)$ nous assure l'unicité de ce nombre (inverse de $e$ modulo $\varphi (pq)$) dans cet "intervalle". De manière générale, quand on travaille modulo $r$ ($r >0$), on aime bien prendre les représentants de nos classes entre $0$ et $r-1$ mais ça n'a rien d'obligatoire. D'ailleurs, il est parfois bien utile de prendre un représentant "négatif".

Quelles sont tes sources pour RSA ?

m.

M.Floquet · June 2017

Bonsoir, normalement $e,d\in (\mathbb{Z}/\phi(n) \mathbb{Z})^{\times}$ tel que $ed \equiv 1\pmod {\phi(n)}$. La difficulté réside dans le fait qu'il est difficile de calculer l'indicatrice d'Euler (c'est au moins aussi dur que de factoriser $n$) et donc de trouver le $d$ privé (clé de déchiffrement). Généralement on prend $n=pq$ avec $p,q$ premiers impairs distincts pour éviter les attaques faciles. Sinon, imagines qu'un attaquant intercepte un chiffré c'est-à-dire un $c=m^e \pmod{n}$ et qu'il trouve un facteur commun non trivial à $p,q$ (possible par hypothèse avec le $pgcd$), il sera en mesure de calculer $\phi(n)$ puis de retrouver $d$ avec Euclide étendu et donc retrouver le $m$ original.

VN2016 · June 2017

Bonsoir,
Merci michael, M.Floquet pour vos réponses.
Je joint un fichier pdf avec ce message. C'est le cours d'EXO 7 sur la cryptographie. Le RSA de ce cours est très bien expliqué (dernière chapitre). Il y a aussi les vidéos si vous suivez le lien.
Pourtant, je ne trouve pas des explications concernant l'encadrement de d et e. J'ai testé sur exel avec les petits p, q. Evidemment, si je ne repecte pas ces encadrements, le déchiffrement ne marche pas.

M.Floquet · June 2017

Bonsoir, peut-être le "Introduction à la cryptographie" de Buchmann pourra te fournir plus d'indications...

michael · June 2017

Une idée comme ça : avec excel, si tu calcules tes puissances brutalement, tu dépasses les capacités de calcul du logiciel, ce qui pourrait (conditionnel) expliquer que ton déchiffrement ne marche pas avec un $e$ et/ou un $d$ et/ou un message $m$ trop gros.
Tu peux t'en sortir avec l'exponentiation rapide modulaire : au lieu de calculer $m^{25}$ modulo $n$ brutalement, tu écris l'exposant en base $2$ : $25 = 16+8+1=2^4+2^3+1$ et tu ne calcules que des carrés que tu réduis immédiatement modulo $n$ pour ne jamais dépasser $n^2$. Par exemple, pour calculer $m^{16}=(((m^2)^2)^2)^2$, tu calcules $m^2$ que tu réduis modulo $n$, puis ta réduction au carré que tu réduis modulo $n$, etc.

Mais peut-être aussi que, comme toi, un truc m'échappe concernant l'intervalle dans lequel prendre $d$ et $e$.

michael · June 2017

J'ai oublié : l'exponentiation rapide fonctionne évidemment parce que $m^{25}=m^{16} \times m^8 \times m$.

Samuel DM · June 2017

Lorsque j'ai écrit mes cours d'arithmétique de TS, j'ai bien apprécié ce document : CultureMath - RSA.

M.Floquet · June 2017

Ce qu'il faut retenir c'est que pour communiquer on utilise jamais ce RSA tel que. Et il y a aussi le choix des nombres premiers qui peut être intéressant

MonsieurX · June 2017

J'en profite pour demander, il faut faire une leçon de quelle niveau pour l'oral 1 ? On peut pas "dépasser" la TS ?
Merci

M.Floquet · June 2017

Au niveau "TS" on peut parler de pas mal de choses avec la spécialité arithmétique. Par exemple le pgcd de "Polezzi" ou encore le lemme de Thue avec application simple à la somme de deux carrés (sans utiliser la théorie anneaux/groupes) et bien d'autres résultats intéressants et élémentaires (tu)