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

spécialité math terminale S, cryptage RSA

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.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 51 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite