Spécialité math terminale S, cryptage RSA
Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
-
G0rk4
- Membre Relatif
- Messages: 166
- Enregistré le: 04 Oct 2007, 19:36
-
par G0rk4 » 12 Jan 2008, 13:57
Salut, je sais que ce n'est pas la bonne section, mais vu la difficulté de l'exo je pense qu'il sera plus approprié ici que dans la section "lycée" (où personne n'y a répondu d'ailleur).
L'énoncé est assez long mais prenez le temps de le lire svp, ça ne doit pas être trop compliqué pour vous.
Le système RSA :
*présentation du système*
Les clés de codage sont deux entiers e et n. L'entier n est le produit de 2 nombres premier p et q très grands (la norme RSA est de choisir un nombre de 154 chiffres !); e est un entier premier avec (p-1)(q-1). On découpe le texte du message en blocs, puis on fait correspondre à chaque lettre son équivalent numérique. Ensuite, pour chaque bloc de chiffres B, on forme un bloc codé M, où M est le reste de la division euclidienne de B^e par n. Ainsi: M congru à B^3 [n]
1)a) Montrer qu'il existe des entiers u et v tels que:
ue+v(p-1)(q-1) = 1
b) Montrer qu'il existe un entier d tel que:
ed+v(p-1)(q-1) = 1, avec 0En déduire alors que v est négatif.
2) Soit x un entier. Montrer que x^(ed) est congru à x [p] et que x^(ed) est congru à x [q]. En dédure que x^(ed) est congru à x [x]
3) Montrer que 2 blocs de chiffres B et B' disctincts sont codés par 2 blocs M et M' distincts.
4) Montrer que, si M est congru à B^e [n], alors B est congru à M^d [n]. Cette formule permet donc un décodage du message chiffré M. Les clés de décodage sont ici d,p et q : en effet, le calcul de d nécessite la conaissance de p et q.
Bon le 1)a) est facile, je ne comprends pas très bien la question 1)b), qu'y a-t-il à démontrer ?
le 2) je sais que d'après Fermat x^p est congru à x [p], de même pour q, mais je ne vois vraiment pas comment arriver à une telle forme (x^(ed) est congru à x [p] ou [q]) je sais aussi que 4|(p-1)(q-1) et que 2 ne divise pas e mais je ne vois pas du tout comment je pourrais aller plus loin.
pour le reste c'est encore pire, je pense que pour le 3 il faut démontrer l'unicité de la transformation et pour le 4 avec tous les éléments qu'il me manque je ne peux même pas le commencer.
-
gol_di_grosso
- Membre Irrationnel
- Messages: 1402
- Enregistré le: 22 Sep 2007, 13:28
-
par gol_di_grosso » 12 Jan 2008, 14:20
supposons que u soit > (p-1)(q-1) ou negatif dans ce cas il existe d>0 et <(p-1)(q-1) tel que
u \equiv d mod (p-1)(q-1) (c'est le reste dans la division euclidienne de u par (p-1)(q-1) qui est compris entre 0 et (p-1)(q-1)) puis c'est evident qu'il est pas égal à 0)
bref on a
donc
d'après a) on a
donc on a
ça va ?
-
G0rk4
- Membre Relatif
- Messages: 166
- Enregistré le: 04 Oct 2007, 19:36
-
par G0rk4 » 12 Jan 2008, 14:44
ça va presque, comment passe-t-on de ue congru à de [(p-1)(q-1)] à ue congru à 1 [(p-1)(q-1)] tu dis que c'est d'après la question 1)a)
-
gol_di_grosso
- Membre Irrationnel
- Messages: 1402
- Enregistré le: 22 Sep 2007, 13:28
-
par gol_di_grosso » 12 Jan 2008, 14:48
ue+v(p-1)(q-1) = 1
donc ue-1=v(p-1)(q-1)
donc ue -1 congru à 0 mod(p-1)(q-1)
c'est à dire ue congru à 1 mod (p-1)(q-1)
c ça que t'a pas compris ?
-
G0rk4
- Membre Relatif
- Messages: 166
- Enregistré le: 04 Oct 2007, 19:36
-
par G0rk4 » 12 Jan 2008, 14:52
ah oui oui si d'accord c'est moi qui ai mal compris dsl, ça va. Donc on a bien répondu à la question, c'est super merci beaucoup. Saurais-tu m'aider pour la suite ?
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 22:20
-
par yos » 12 Jan 2008, 15:33
Bonjour.
Remplace l'exposant ed par sa valeur 1+|v|(p-1)(q-1). Que dire de
? Question : on dit pas que x est étranger à p??
-
gol_di_grosso
- Membre Irrationnel
- Messages: 1402
- Enregistré le: 22 Sep 2007, 13:28
-
par gol_di_grosso » 12 Jan 2008, 15:55
si t'arrive toujours pas pense que si
alors
yos a écrit: Question : on dit pas que x est étranger à p??
non maintenant on dit plutot premier entre eux qu'étranger...
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 22:20
-
par yos » 12 Jan 2008, 17:06
gol_di_grosso a écrit:non maintenant on dit plutot premier entre eux qu'étranger...
On dit les deux c'est pas le problème : je demande si c'est en hypothèse ou pas.
-
gol_di_grosso
- Membre Irrationnel
- Messages: 1402
- Enregistré le: 22 Sep 2007, 13:28
-
par gol_di_grosso » 12 Jan 2008, 17:29
yos a écrit:On dit les deux c'est pas le problème : je demande si c'est en hypothèse ou pas.
ah désolé non on dit pas vu que ça sera le message (enfin je crois)
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 22:20
-
par yos » 12 Jan 2008, 17:49
Alors il faut distinguer le cas p|x du cas p étranger à x dans la question 2 en plus de ce que j'avais écrit plus haut.
-
G0rk4
- Membre Relatif
- Messages: 166
- Enregistré le: 04 Oct 2007, 19:36
-
par G0rk4 » 12 Jan 2008, 18:33
ok je vais réflechir à tout ça, de toute façon l'exercice n'est pas pour tout de suite :) merci beaucoup de vos réponses, je reposte dans quelques jours.
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 51 invités