RSA
La mécanique et quelques exemples
On choisit , un nombre assez grand.
Clé publique : où et sont relativement premiers, ce qui garantit que est inversible modulo ,
Clé privé : où est l'inverse de modulo .
Fonction d'encryption :
Déchiffrement
Exemple
On se donne deux nombres premiers, , puis on calcule n
Pour l'encryption, on a besoin de et d'un nombre , inversible modulo . La chose la plus simple à faire (mais probablement pas si sécuritaire que ça, c'est de prendre un nombre premier). On doit calculer l'inverse de mod , chose qu'à la main serait faite avec l'algorithme d'Euclide et la relation de Bézout, mais on peut faire ici directement.
Supposons que l'on veuille transmettre le message
Remarque :
Faire l'exponentiation, puis la réduction modulaire dans notre cas est, à toutes fins pratiques, équivalent (l'ordi va assez vite pour que la différence soit imperceptibe). Voyons avec des nombres un peu plus grands
Une petite fonction utile pour l'algorithme d'Euclide.
Une de pirates!
10 pirates trouvent un sac avec des pièces d'or (égales).
Ils essayent de se partager les pièces de façon juste et équitable.
Ceci est impossible, car il leur reste une piece d'or. Un pirate fâché, qutte.
Les pirates restants essayent de se distribuer le buttin. Ceci est encore impossible, il leur reste deux pièces cette fois.
UDeux autres pirates quittent, et les autres recommencent. Il se trouve que cette fois, tout marche.
Quel est le nombre minimal de pièces ?