SOS-MATH

Bonjour, j'ai un petit problème de compréhension dans cette méthode de chiffrement


dans l'histoire de Alice et Bob, Alice donne la clée publique (n,e) à Bob et a gardé sa clée privée "d", Bob transmet un message noté "m" à Alice en utilisant la clée publique,
le m devient donc M car m^e est congru à M modulo (n)
ensuite Alice va déchiffrer ce message grâce à sa clée privée :
donc M^d est congru à ((m^e)^d) qui est congru à m modulo (n)

je comprend pas commment on passe de M^d congru à ((m^e)^d) modulo (n) à ((m^e)^d) congru à m modulo (n)

pouvez vous m'aider s'il vous plait

Bonjour,
ce n'est pas très simple d'expliquer ce chiffrement :
1) Alice choisit deux nombres premiers \(p\) et \(q\) puis génère un nombre \(n\) : \(n=pq\)
puis choisit une valeur de \(e\), telle que \(pgcd((p-1)(q-1),e)=1\).
les valeurs rendues publiques sont \((n,e)\), clé publique et les nombres premiers \(p\) et \(q\), qui ne sont jamais publiés s'appellent les nombres RSA.
Ensuite, avec le théorème de Bezout, elle détermine deux nombres \(d\) et \(k\), tels que \(e\times d+k\times (p-1)(q-1)=1\).
Le nombre \(d\) obtenu s'appelle la clé privée du système.
2) Bob veut ensuite écrire à Alice un message transformé en un nombre \(m\), inférieur à \(m\) : Ce nombre \(m\) est codé à l'aide de la clé publique \((n,e)\) et devient \(M\) défini par :
\(M\eq m^e [n]\) : ce nombre peut être envoyé de façon non protégé car il est déjà codé.
Alice reçoit ce nombre \(M\) et l'élève à la puissance \(d\) modulo \(n\) (avec sa clé privée) : \(M^d\eq (m^e)^d\eq m [n]\)
Qu'est-ce qui justifie le passage \(m^{ed}\eq m [n]\) ? c'est avec cela :
comme \(e\times d+k\times (p-1)(q-1)=1\), on a \(m^{e\times d+k\times (p-1)(q-1)}\eq m[n]\) soit \(m^{ed}\times (m^{(p-1)(q-1)})^k\eq m [n]\).
Or il existe un théorème (Euler) qui dit que \(m^{(p-1)(q-1)}\eq 1[n]\), ce théorème est un peu difficile à justifier.
Il restera donc \(m^{ed}\eq m [n]\).
Voilà le point épineux est délicat à expliquer au niveau terminale.
j'espère t'avoir éclairé un peu
Bon courage

Je vais essayer de compléter mon message pour justifier le fait que \(m^{(p-1)(q-1)}\eq 1 [pq]\).
On sait que deux entiers premiers \(p\) et \(q\) sont aussi premiers entre eux ;
dans ce cas si on sait que \(p|S\) et que \(q|S\), alors leur produit divise aussi S : \(pq|S\).
On suppose que \(m\) est inférieur à p et q, donc m va être premier avec p et q.
On part du théorème de Fermat : comme \(m\) est premier avec \(p\), on a \(m^{p-1}\eq 1 [p]\) donc \((m^{p-1})^{q-1}\eq 1^{q-1}\eq 1 [p]\).
Donc on a \(m^{(p-1)(q-1)}\eq 1 [p]\).
Le même raisonnement aboutirait à la même congruence modulo q : \(m^{(p-1)(q-1)}\eq 1 [q]\), donc \(p|m^{(p-1)(q-1)}-1\) et \(q|m^{(p-1)(q-1)}-1\) et d'après la remarque faite précédemment \(pq|m^{(p-1)(q-1)}-1\) ainsi \(m^{(p-1)(q-1)}-1\eq 0 [pq]\) donc \(m^{(p-1)(q-1)}\eq 1 [pq]\)
Est-ce plus clair ?

Bonjour, oui c'est beaucoup plus clair, néanmoins je ne comprend pas cette étape

Qu'est-ce qui justifie le passage m^{ed}\eq 1 [n] ? c'est avec cela :


Vous écrivez congru à 1 modulo n or ce serait plutôt congru à m modulo n si j'ai bien compris puisque on a [/TeX]m^{(p-1)(q-1)}\eq 1 [pq][/TeX], non?

et après

comme e\times d+k\times (p-1)(q-1)=1, on a \([TeX]\)m^{e\times d+k\times (p-1)(q-1)}\eq m[n] soit m^{ed}\times (m^{(p-1)(q-1)})^k\eq m [n]\([TeX]\).

çà
là je ne vois pas trop non plus

Oui, j'avais fait une erreur que je viens de corriger dans mon message.
comme \(de+k(p-1)(q-1)=1\) si on élève m à cette puissance, on reste égale à m d'où : \(m^{de+k(p-1)(q-1)}\eq m^1\eq m [n]\).
Ensuite, on décompose l'exposant comme déjà dit pour finalement arriver à \(m^{de}\eq m [n]\).

ah mais oui, m^1 = m ben oui c'est sûr
merci beaucoup pour ces belles explications !

Bon courage pour la suite, le chiffrement RSA est une notion assez délicat pour des terminales.
A bientôt