7.3 Le principe du code RSA
217
2. Soient a, b, m ∈ N. Alors,
(ma, mb) = m(a, b).
3. Soient a, b, c ∈ N. Si c | ab et (c, b) = 1, alors c | a.
4. Si p est premier et p | ab, alors p | a ou p | b.
Preuve 1. Soit F = {ax + by | x, y ∈ Z, ax + by > 0} et soit c = (a, b). Alors, c ∈ F
par le corollaire 7.4. Supposons que d = ax
+ by
∈ F est tel que d > 0 et d < c.
Comme c | a et c | b, alors c | ax
+ by
. Donc, c | d. Mais 0 < d < c. Contradiction.
2. `
A cause de 1., on a
(ma, mb) = min{max + mby | x, y ∈ Z, max + mby > 0}
= m min{ax + by | x, y ∈ Z, ax + by > 0}
= m(a, b).
3. Comme (c, b) = 1, de par le corollaire 7.4, il existe x, y ∈ Z tels que cx + by = 1.
Multiplions cette ´ egalit´ e par a. On obtient acx + aby = a. On a c | acx et c | aby.
Donc, c | (acx + aby), c’est-` a-dire c | a.
4. On applique 3. `
a c = p premier. Si (p, b) = 1, on obtient p | a en vertu de 3. Sinon,
(p, b) = d > 1. Mais les seuls diviseurs de p sont 1 et p. Donc, d = p = (p, b),
c’est-` a-dire p | b.
Le corollaire suivant est tr` es utile.
Corollaire 7.6 Soient a et n deux entiers tels que a < n. Si (a, n) = 1, alors il existe
un x ∈ {1, . . . , n − 1} unique tel que ax ≡ 1 (mod n).
Preuve Commen¸ cons par l’existence. Puisque (a, n) = 1, le corollaire 7.4 assure l’existence de x, y ∈ Z tels que ax + ny = (a, n) = 1. Donc, ax = 1 − ny ou encore,
ax ≡ 1 (mod n). Si x /
∈ {1, . . . , n − 1}, alors on peut lui ajouter ou retrancher un
multiple de n pour l’y ramener sans pour cela changer la congruence ax ≡ 1 (mod n).
Donc, l’existence est prouv´ ee.
Passons ` a l’unicit´ e. Supposons maintenant qu’il existe une deuxi` eme solution x
∈
{1, . . . , n−1} telle que ax
≡ 1 (mod n). Alors, a(x−x
) ≡ 0 (mod n). Donc, n | a(x−x
).
Comme (n, a) = 1, alors n | x − x
. Mais x − x
∈ {−(n − 1), . . . , n − 1}. Donc, la seule
possibilit´ e est x − x
= 0.
7.3 Le principe du code RSA
Nous pr´ esentons la m´ ethode cryptographique RSA en suivant l’article original [7].
Nous commen¸ cons par rapidement faire le tour de toutes les ´ etapes. Dans un deuxi` eme
temps, nous reviendrons les pr´ eciser une ` a une et donner des d´ etails.
217
2. Soient a, b, m ∈ N. Alors,
(ma, mb) = m(a, b).
3. Soient a, b, c ∈ N. Si c | ab et (c, b) = 1, alors c | a.
4. Si p est premier et p | ab, alors p | a ou p | b.
Preuve 1. Soit F = {ax + by | x, y ∈ Z, ax + by > 0} et soit c = (a, b). Alors, c ∈ F
par le corollaire 7.4. Supposons que d = ax
+ by
∈ F est tel que d > 0 et d < c.
Comme c | a et c | b, alors c | ax
+ by
. Donc, c | d. Mais 0 < d < c. Contradiction.
2. `
A cause de 1., on a
(ma, mb) = min{max + mby | x, y ∈ Z, max + mby > 0}
= m min{ax + by | x, y ∈ Z, ax + by > 0}
= m(a, b).
3. Comme (c, b) = 1, de par le corollaire 7.4, il existe x, y ∈ Z tels que cx + by = 1.
Multiplions cette ´ egalit´ e par a. On obtient acx + aby = a. On a c | acx et c | aby.
Donc, c | (acx + aby), c’est-` a-dire c | a.
4. On applique 3. `
a c = p premier. Si (p, b) = 1, on obtient p | a en vertu de 3. Sinon,
(p, b) = d > 1. Mais les seuls diviseurs de p sont 1 et p. Donc, d = p = (p, b),
c’est-` a-dire p | b.
Le corollaire suivant est tr` es utile.
Corollaire 7.6 Soient a et n deux entiers tels que a < n. Si (a, n) = 1, alors il existe
un x ∈ {1, . . . , n − 1} unique tel que ax ≡ 1 (mod n).
Preuve Commen¸ cons par l’existence. Puisque (a, n) = 1, le corollaire 7.4 assure l’existence de x, y ∈ Z tels que ax + ny = (a, n) = 1. Donc, ax = 1 − ny ou encore,
ax ≡ 1 (mod n). Si x /
∈ {1, . . . , n − 1}, alors on peut lui ajouter ou retrancher un
multiple de n pour l’y ramener sans pour cela changer la congruence ax ≡ 1 (mod n).
Donc, l’existence est prouv´ ee.
Passons ` a l’unicit´ e. Supposons maintenant qu’il existe une deuxi` eme solution x
∈
{1, . . . , n−1} telle que ax
≡ 1 (mod n). Alors, a(x−x
) ≡ 0 (mod n). Donc, n | a(x−x
).
Comme (n, a) = 1, alors n | x − x
. Mais x − x
∈ {−(n − 1), . . . , n − 1}. Donc, la seule
possibilit´ e est x − x
= 0.
7.3 Le principe du code RSA
Nous pr´ esentons la m´ ethode cryptographique RSA en suivant l’article original [7].
Nous commen¸ cons par rapidement faire le tour de toutes les ´ etapes. Dans un deuxi` eme
temps, nous reviendrons les pr´ eciser une ` a une et donner des d´ etails.