L'algorithme de chiffrement rsa

Bio :
L'algorithme de chiffrement rsa à été découvert pour la première fois en 1973 par l'agence de renseignement britanique et classé top secret. Ca découverte au public à été faite par trois mathématiciens (Ronald *Rivest, Adi *Shamir et Leonard *Adleman) en 1977.
Breveté par le MIT en 1983.
Il est très utilisé dans le commerce en ligne et principalement pour échanger des données confidentielles.
Le RSA est un algorithme de chiffrement dit asymétrique, cela veut dire qu'il dipose de deux clés, une pour crypter le message et une autre pour le décrypter.
La clé utiliser pour crypter ne peut servir à déchiffrer le message et inversement.

Algorithme :
Choisir deux nombres premiers (Nombre dont 1 et lui même sont les diviseurs dont le reste d'une division Euclidienne est 0) p et q.
Calculer n : n = pq
Calculer φ(n) : φ(n) = (p-1)(q-1)
Choisir un nombre e tel que e ≡ 1 mod φ(n) (Il faut qu'ils n'aient aucun diviseur en commun (premier entre eux).
Le nombre e sera la clé publique.
Choisir d tel ed ≡ 1 mod φ(n)

d est donc la clé privée et ne doit pas être transmise, e est la clé publique et peut être transmise ainsi que n à l'interlocuteur par moyen sécurisé ou non.

Soit M le message initial et y le message crypté.
Pour crypter : y = (m^e) mod n
Pour décrypter : m = (y^d) mod n

Pour tester vous pouvez télécharger :
Rsa pour configurer l'algorithme (p,q,n,φ)
Un générateur de nombre premier
Un générateur de e
Un générateur de d
Et l'algorithme pour déchiffrer y

Ps: si vous souhaitez utiliser l'algorithme de chiffrement rsa, veuillez télécharger "Calcul de nombre premier", "E_generateur", "D_generator".
Et de les mettre à la racine du disque principal.

Demonstration et théorème :

Dans cette démonstration, nous utiliserons les notions de congruence et de modulo.
Dans 45 ≡ 3 mod 6 veut dire que le reste de la division euclidienne 45/6 est 3.
Prenon pour exemple Alice et Léo.
φ(n) est appeler l'indicatrice d'Euler, elle permet de connaître le nombre d'entier premier et inférieur à n, lorsque n > 0.
Rappeler vous que e et d ont été choisie tel que ed ≡ 1 mod φ(n)
Et il existe donc un entiet k tel que ed = kφ(n)+1
Rappeler vous également que e et n sont le couple qui constitue la clé public et que d constitue la clé privé

Le principe du chiffrement rsa est d'envoyer des message crypter à un destinatère, et ensuite que lui seul puisse le décrypter.
Alice envoie donc à Leo le message m (rappelez vous que l'on associe une lettre ou un groupe de lettre à un nombre).
Elle à donc effectuer l'opération Y = M^e mod n.
Léo doit donc effectuer l'opération Y^d ≡ M mod n.
Soit Y^d = M = (M^e)^d
On doit démontrer que cela est possible.

Y^d ≡ M^ed mod n
      ≡ M^kφ(n)+1 mod n            Rappeler vous que l'on a dit qu'il existait un nombre k tel que ed = kφ+1
      ≡ M^kφ(n)M mod n          C'est comme 2³ --> 2²⁺¹ --> 2²*2.

A partir de la deux cas se présente :

1° Si M ≡ 1 mod n :
Théorème d'Euler en arithmétique : Pour tout a premier avec n et n > 0 alors a^φ(n) ≡ 1 mod n
Ainsi :
Y^d ≡ M^(φ(n))kM mod n
      ≡ 1^kM mod n           Application du théorème d'Euler : m est premier avec n alors m mod n = 1
      ≡ M mod n

2° Si M ≡ 0 mod n :
Est en cours d'écriture...