RSA et fonction indicatrice d'Euler

Aurélien · May 2004

Bonsoir,

Je dois réaliser un dossier sur RSA et j'ai une question à laquelle je ne trouve pas de réponse :

La clé publique est (n, e).

- n est le produit de deux nombres premier p et q

- e est un nombre entre 2 et (p-1)(q-1) (fonction indicatrice d'Euler i.e. nombre d'entiers inférieurs à n qui sont premiers avec lui) tel que e et (p-1)(q-1) soient premiers entre eux.

=> Les nombres n et e forment la clé publique avec laquelle n'importe qui pourra crypter un message.

Ma question est la suivante :

Quel est ici le rôle de la fonction indicatrice d'Euler ? En d'autres termes, pourquoi faut il que e soit premier avec cette fonction qui, comme son nom l'indique, a pour principal rôle de donner le nombre d'entiers inférieurs à n qui sont premiers avec lui ?

Merci d'avance !!!

Thomas · May 2004

Tout simplement parce que le théorème d'Euler nous dit que pour tout entier $x$ premier avec $n$, on a $$x^{\phi(n)}=1 \mod n$$
Si on note $d$ la clé privé (c'est un entier tel que $ed - \phi(n)k=1$, il existe parce que $e$ et $\phi(n)$ sont premiers entre eux(relation de Bezout) ) et si M est un message à envoyer, alors
on calcule et on envoie $C=M^e \mod n$ (faisable car tout le monde connait $e$ et $n$)
la personne qui reçoie utilise sa clé privée $d$ et calcule $C^d \mod n$
Or $C^d=(M^e)^d=M^{ed}=M^{\phi(n)k+1}=(M^k)^{\phi(n)}\times M=M \mod n$
donc la personne reçoie bien le message $M$.

Thomas

Kashmir · May 2004

Aurélien,

en fait, citer la fonction indicatrice d'Euler dans l'approche mathématique de RSA relève du pur snobisme. On peut très bien faire la présentation du mécanisme en ne citant que Fermat et Bézout (enfin Bachet plus exactement).

(ceci n'enlève rien à la qualité de la réponse Thomas, oeuf corse)

Aurélien · May 2004

Tout d'abord, merci pour vos réponses...

Ensuite, Thomas, je ne comprends pas un détail :

Tu dis que l'on a pour tout x entier premier avec n (soit tout entier x tel que x = 1 mod n) la relation suivante :

x^phi(n) = 1 mod n

Mais il me semble pourtant que l'on a :

x et n premiers entre eux <=> x = 1 mod n <=> x^m = 1^m mod n
Soit en fait x^m = 1 mod n, avec m un entier quelconque...

Donc x n'est pas premier avec n uniquement lorsqu'il est élevé à la puissance phi(n)...

J'en reviens donc à la même question : pourquoi utiliser phi(n) alors qu'une autre valeur conviendrait peut-être. En fait, je me doute bien que phi(n) a une propriété qui le rend indispensable dans cet algorithme mais je ne la vois pas. Désolé de mettre autant de temps à comprendre mais je suis un petit peu crevé et j'ai du mal à voir les choses...

Quant à ta réponse, Kashmir, je ne comprends pas s'il s'agit d'un reproche (ou pas ?)... En quoi est-ce du snobisme ? Et en quoi cela relève-t-il de moi ?

Aurélien

llb · May 2004

"x et n premiers entre eux <=> x = 1 mod n <=> x^m = 1^m mod n
Soit en fait x^m = 1 mod n, avec m un entier quelconque..."

tu démontres comment ça ??

Kashmir · May 2004

Je ne me permettrais pas de faire un quelconque reproche rassures toi.

Je dis juste que RSA est présenté avec la fonction d'Euler alors qu'en fait RSA n'a rien à voir avec cette fonction. Je pense juste qu'elle a inspiré les créateurs du système et qu'à un détour de la démonstration tu reconnais la fonction mais tu peux très bien ne jamais prononcer "fonction d'Euler" quand tu présentes RSA. Les seules choses incontournables sont Bachet et Fermat.

je vais essayer de t'envoyer la démo plus détaillée

Kashmir · May 2004

voilà un extrait de texte

Aurélien · May 2004

Merci beaucoup, beaucoup, beaucoup !!!!

Sinon, llb,

> "x et n premiers entre eux x = 1 mod n x^m = 1^m mod n
> Soit en fait x^m = 1 mod n, avec m un entier quelconque..."
>
> tu démontres comment ça ??

Heu, sauf erreur de ma part, en terminale on voit que :

si a = 1 mod b
alors, a^n = 1^n mod b
et comme 1^n = 1, on a finalement :
a^n = 1 mod b $\forall$ n $\in \N$

Bon, après, ce ne sont que mes souvenirs de terminale (mais bon, ça ne date que de un an et demi).

Merci de me dire si je me trompe...

Aurélien

llb · May 2004

L'affirmation &quotx et n premiers entre eux équivaut a x = 1 mod n" est fausse.

exemple : $2$ et $3$ sont premiers entre eux, pourtant, $2\not\equiv 1\mod 3$.
(et imagine modulo $p$, ou $p$ est premier... tout nombre non divisible par $p$ serait congrus a $1$ modulo $p$.... lol)

ensuite, si $x\equiv 1\mod n$ alors $x^m\equiv 1\mod n$ ca c'est vrai, mais la réciproque est fausse... par exemple $2^2\equiv 1\mod 3$ pourtant $2\not\equiv 1\mod 3$...

A mon avis, ce n'était pas vraiment ça dans ton cours, enfin j'espere

)

Ceci explique la présence de $\varphi(n)$ dans RSA (vivi c'est pédant, mais bon)... Comme le rappelle Thomas au début de son message, pour tout $x$ premier avec $n$ on a $$x^{\varphi(n)}\equiv 1\mod n.$$
(et les entiers tels que $x^m\equiv 1\mod n$ ne seront pas ${\bf tous\ les\ entiers}$ mais uniquement les multiples de $\varphi(n)$.)

Amicalement.

Aurélien · May 2004

Ok, ça remet les choses au clair...

Je comprends mieux maintenant pourquoi je ne comprenais pas avant...

Merci beaucoup.

RSA et fonction indicatrice d'Euler

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 9