Le système RSA

Construction du système par Bob :

- Choix de 2 grands nombres premiers p et q;

- calcul de n = pq et de ϕ(n) = (p − 1)(q − 1) ;

- choix d’un b tel que pgcd(b, ϕ(n)) = 1 ;

- calcule de a = b^{−1} mod ϕ(n) ;

- publication de b et n.

Chiffrement de x par Alice : e_{K}(x) = x^{b} mod n

Déchiffrement de y = e_{K}(x) par Bob : d_{K}(y) = y^{a} mod n

Clé : (n, p, q, a, b)

- clés publiques : n et b,

- clés privées : p, q et a.

Le système RSA

Algo. square − and − multiply pour le calcul de y dans y = x^{c} mod n = sm(x, c, n, |c|, 1) avec |c|= l le nombre de bits de la représentation binare de c et bin(c, i) le i^{ème} bit de c.

sm(x, c, n, l, z)

z si l = 0

sm(x, c, n, l − 1, (z2 ∗ x mod n)) si bin(c, l) = 1 sm(x, c, n, l − 1, z2) sinon

sachant que z2 = z^{2} mod n.

Exemple : p = 101, q = 113, x = 9726.