Algorithme RSA : Preuve que le déchiffrement fonctionne

• Comme c=m^e mod n, c^d mod n = m^ed mod n
  
  
• Comme ed = 1 mod (p-1)(q-1) il existe un entier k tel que ed = 1 + k(p-1)(q-1)
  
  
• Par conséquent c^d mod n = m^{1+k(p-1)(q-1)} mod n
  
  
• Or (théorème de Fermat) m^(p-1) mod p = 1 si m n’est pas multiple de p. Par élévation à la puissance k(q-1) puis multiplication par m on obtient : m^{1+k(p-1)(q-1)} mod p = m égalité qui reste vraie (2 membres=0) si m est multiple de p
  
  
• Par symétrie m^{1+k(p-1)(q-1)} mod q = m donc m^{1+k(p-1)(q-1)} - m est divisible par p et q donc par pq (p et q premiers et différents)
  
  
• Par conséquent c^d mod n = m^{1+k(p-1)(q-1)} mod pq = m