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 0
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 n'y arrive pas: 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])
le reste c'est une catastrophe, j'aurais vraiment besoin d'aide, le prof y a été trop fort en nous donnant un exo aussi compliqué...