Livre_silo 30 août 2013 16:32 Page 358
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
358
Informatique pour tous
On dira que a est un menteur fort s’il vérifie les conditions précédentes et si n n’est pas
premier.
On peut montrer qu’au plus un quart des valeurs de 1, n−1 sont des menteurs forts ⁸. Le
test de Miller-Rabin s’effectue donc en pratique de la façon suivante : prendre une valeur a
au hasard comprise entre 1 et n − 1 et effectuer le test avec cette base a. Si a respecte les
conditions données ci-avant, n est probablement premier ; dans ce cas, on recommence
avec un nouveau a pris au hasard. Si au bout de 40 essais, on n’a pas trouvé de a violant
les conditions données plus haut, on considérera que le nombre donné était premier.
Si le nombre testé est premier, quelle est la probabilité que le test de Miller-Rabin le déclare
non premier ? S’il n’ est pas premier, majorer la probabilité que le test de Miller-Rabin le
déclare premier.
Pour effectuer le test aussi vite que possible, on calculera le reste de a
m modulo n
et on effectuera ensuite des mises au carré modulo n successives pour calculer a
2m ,
a
4m ,…,a
2
s−1 m . De plus, on n’ est pas obligé de calculer toutes ces valeurs : on s’arrête
dès le début si a
m
≡ 1[n], on s’arrête également dès qu’on trouve la valeur −1 et enfin, on
peut aussi s’arrêter si l’on trouve la valeur 1. Pourquoi ?
Mettre en œuvre ce test pour vérifier si les grands nombres trouvés avec le test PGP sont
bien premiers.
A.6.4 Application à la cryptographie : la méthode RSA
Parmi les procédés cryptographiques, la méthode RSA, découverte par R. Rivest, A. Shamir et L. Adleman en 1978, est l’une des plus utilisées actuellement. Elle fait partie des
méthodes dites à clé publique : chaque personne possède une clé P publique dont tout le
monde peut avoir connaissance (par exemple dans un annuaire) et une clé S secrète qu’elle
seule connaît. Lorsqu’on veut envoyer un message M à une personne A, on le code avec la
clé publique P A du destinataire. Ce dernier le décode alors avec sa clé secrète S A et peut
le lire.
Un tel système fonctionne donc si on a les propriétés suivantes :
1 S(P (M )) = M pour tout message M .
2 Les paires (S, P ) sont toutes distinctes.
3 Découvrir la clé secrète S à partir de la clé publique P est aussi difficile que déchiffrer
le message codé.
4 Une paire (S, P ) peut se calculer facilement.
La méthode RSA fonctionne de la manière suivante : soient x, y et s trois grands nombres
premiers, tels que x, y ⩽ s. Soient N = xy et p tel que ps mod (x − 1)(y − 1) = 1. On
peut alors montrer que pour tout M , on a M
ps = M (mod N ).
8. Voir sur Wikipédia en anglais l’article Miller–Rabin primality test et notamment l’article de René Schoof
mentionné dans les références (article consulté le 22 mars 2013).
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
358
Informatique pour tous
On dira que a est un menteur fort s’il vérifie les conditions précédentes et si n n’est pas
premier.
On peut montrer qu’au plus un quart des valeurs de 1, n−1 sont des menteurs forts ⁸. Le
test de Miller-Rabin s’effectue donc en pratique de la façon suivante : prendre une valeur a
au hasard comprise entre 1 et n − 1 et effectuer le test avec cette base a. Si a respecte les
conditions données ci-avant, n est probablement premier ; dans ce cas, on recommence
avec un nouveau a pris au hasard. Si au bout de 40 essais, on n’a pas trouvé de a violant
les conditions données plus haut, on considérera que le nombre donné était premier.
Si le nombre testé est premier, quelle est la probabilité que le test de Miller-Rabin le déclare
non premier ? S’il n’ est pas premier, majorer la probabilité que le test de Miller-Rabin le
déclare premier.
Pour effectuer le test aussi vite que possible, on calculera le reste de a
m modulo n
et on effectuera ensuite des mises au carré modulo n successives pour calculer a
2m ,
a
4m ,…,a
2
s−1 m . De plus, on n’ est pas obligé de calculer toutes ces valeurs : on s’arrête
dès le début si a
m
≡ 1[n], on s’arrête également dès qu’on trouve la valeur −1 et enfin, on
peut aussi s’arrêter si l’on trouve la valeur 1. Pourquoi ?
Mettre en œuvre ce test pour vérifier si les grands nombres trouvés avec le test PGP sont
bien premiers.
A.6.4 Application à la cryptographie : la méthode RSA
Parmi les procédés cryptographiques, la méthode RSA, découverte par R. Rivest, A. Shamir et L. Adleman en 1978, est l’une des plus utilisées actuellement. Elle fait partie des
méthodes dites à clé publique : chaque personne possède une clé P publique dont tout le
monde peut avoir connaissance (par exemple dans un annuaire) et une clé S secrète qu’elle
seule connaît. Lorsqu’on veut envoyer un message M à une personne A, on le code avec la
clé publique P A du destinataire. Ce dernier le décode alors avec sa clé secrète S A et peut
le lire.
Un tel système fonctionne donc si on a les propriétés suivantes :
1 S(P (M )) = M pour tout message M .
2 Les paires (S, P ) sont toutes distinctes.
3 Découvrir la clé secrète S à partir de la clé publique P est aussi difficile que déchiffrer
le message codé.
4 Une paire (S, P ) peut se calculer facilement.
La méthode RSA fonctionne de la manière suivante : soient x, y et s trois grands nombres
premiers, tels que x, y ⩽ s. Soient N = xy et p tel que ps mod (x − 1)(y − 1) = 1. On
peut alors montrer que pour tout M , on a M
ps = M (mod N ).
8. Voir sur Wikipédia en anglais l’article Miller–Rabin primality test et notamment l’article de René Schoof
mentionné dans les références (article consulté le 22 mars 2013).