RSA

La mécanique et quelques exemples

On choisit $n = pq$, un nombre assez grand.

• Clé publique : $(a,n)$ où $a$ et $m = (p-1)(q-1)$ sont relativement premiers, ce qui garantit que $a$ est inversible modulo $m$,
• Clé privé : $(c,n)$ où $c$ est l'inverse de $a$ modulo $m$.
• Fonction d'encryption : $y = x^a \mod n$
• Déchiffrement $x= y^c \mod n$

Exemple

On se donne deux nombres premiers, $p=43, q=59$, puis on calcule $n=pq$ n

Pour l'encryption, on a besoin de $m=(p-1)(q-1)$ et d'un nombre $a$, inversible modulo $n$. La chose la plus simple à faire (mais probablement pas si sécuritaire que ça, c'est de prendre $a=$ un nombre premier). On doit calculer l'inverse de $a$ mod $m$, 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 $x=1819$

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 ?