Annuler
connectez vous
- Un petit rappel de Cours sur le dénombrement - terminale
- Sept Exercices Q.C.M. sur le dénombrement - terminale
- Complexes, calcul vectoriel, problème - sujet de bac - terminale
- Enseignement scientifique : suite, probabilité, fonction - sujet de bac - terminale
- Enseignement scientifique : suite, probabilité, fonction - sujet de bac - terminale
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale Autres ressourcesTopics traitant de Autres ressources [tout]Lister tous les topics de mathématiques
Niveau terminale
Arithmétique du système RSA
Posté par airborne57
Bonjour,
Je souhaite démontrer le théorème suivant qui est un des théorèmes d'arithmétiques du système de cryptographie RSA :
Soit p et q deux nombres premiers. Soit e un entier compris strictement entre 1 et (p-1)(q-1) et premier avec le produit (p-1)(q-1), alors il existe un entier d unique tel que 1 < d < (p − 1)(q − 1) et vérifiant e d ≡ 1 [(p − 1)(q − 1)].
En cherchant sur internet, j'ai trouvé la démonstration suivante:
Si e et (p−1)(q −1) sont premiers entre eux, il existe d'après le théorème de Bezout deux entiers relatifs u0 et v0 tels que u0.e + v0.(p − 1)(q − 1) = 1. Par suite (u, v) est solution de u.e + v.(p − 1)(q − 1) = 1 si et seulement si il existe un entier relatif k tel que u = u0 − k(p − 1)(q − 1) et v = v0 + k e.
Soit donc k tel que u soit le plus petit des entiers positifs. Dans ces conditions u e = 1 − v(p − 1)(q − 1) est congru à 1 modulo (p − 1)(q − 1) et le nombre d recherché est par conséquent égal à u.
Il est unique car s'il en existait un autre, d' alors on aurait e(d−d') ≡ 0 [(p−1)(q−1)].
Comme e est premier avec (p − 1)(q − 1) alors, d'après le théorème de Gauss, d − d′ ≡ 0 [(p − 1)(q − 1)]. Mais comme on a 1 < d < (p − 1)(q − 1) et 1 < d′ < (p − 1)(q − 1) et bien on ne peut avoir que d = d'.
Je n'ai pas de soucis avec cette démonstration si ce n'est que si on considère le plus petit entier relatif k, que je note k0, tel que d=u0-k0(p-1)(q-1) soit positif, je n'arrive pas à comprendre pourquoi cette entier d est tel que 1 < d < (p − 1)(q − 1) ? Si quelqu'un pouvait m'expliquer ce serait gentil 
salut
k n'est pas le plus petit entier positif !!!
k est un entier tel que u soit le plus entier positif !!!!
les solution de ue + v(p - 1)(q - 1) = 1 <=> ue = 1 [(p - 1)(q - 1] (*) sont telles que u = u_0 + k(p - 1)(q - 1)
il existe un entier k tel que u soit le plus petit entier positif et vérifiant donc 0 < u < (p - 1)(q - 1) et vérifiant (*)
...
Désolé pour cette réponse tardive, mais justement ce que j'aimerais comprendre c'est pourquoi il existe forcément un entier k tel que l'entier u soit celui recherché. Je comprends bien que l'on peut choisir le plus petit entier k tel que 1<u mais pourquoi on a forcément u<(p-1)(q-1) pour cet entier k. Désolé si ma question semble peut-être bête mais je dois avouer que l'arithmétique n'est pas mon point fort.
Citation :
Je comprends bien que l'on peut choisir le plus petit entier k tel que 1<u mais pourquoi on a forcément u<(p-1)(q-1) pour cet entier k.
Je comprends bien que l'on peut choisir le plus petit entier k tel que 1<u mais pourquoi on a forcément u<(p-1)(q-1) pour cet entier k.
NON ET NON
relis ce que j'ai écrit : une fois trouvé u_0 (qui n'est pas nul) alors d = u_0 + k(p - 1)(q - 1) avec k entier
donc il existe un entier k tel que d soit le plus petit entier positif
et puisque deux valeurs de d pour des valeurs consécutives de k diffèrent de (p - 1)(q - 1) alors on a forcément 1 < d < (p - 1)(q - 1) pour le plus petit d positif
Juste un commentaire:
Le d calculé selon ed = 1 mod (p-1)(q-1) n'est pas le plus petit qui permet de chiffrer / déchiffrer un message M dans RSA selon la formule . Selon la fonction de Carmichael:
donc , si M et pq sont premiers entre eux.
Si on calcule d_0 tel que ed_0 = 1 mod ppcm( p-1, q-1 ):
pour un certain entier k.
Donc ce d_0 marche aussi pour déchiffrer.
On remarque que tous les d de la forme d = d_0 + c*ppcm(p-1,q-1) marchent aussi, et l'un d'eux est celui trouvé par la formule traditionnelle ed = 1 mod (p-1)(q-1) car ppcm( p-1, q-1 ) divise évidemment (p-1)(q-1).
Si p et q sont de très grands nombres premiers choisis au hasard, il y aura un très grand nombre de d pour un e donné qui permettent de déchiffrer, mais ceci n'affaiblit pas la sécurité de RSA, car ppcm(p-1,q-1) sera probablement très grand aussi, donc la probabilité qu'un méchant puisse trouver l'un de ces d au hasard, ou même par une recherche exhaustive, est faible.