Mémoire - Candidat no 000803-022

La cryptographie à clé publique RSA :un algorithme pour chiffrer et déchiffrerdes messages en toute confidentialité

Par Joey Litalien, candidat no 000803–022

Mémoire de recherche en mathématique présenté àl’Organisation du Baccalauréat Internationaldans le cadre du programme du diplôme

3945 mots

Collège François-Xavier-Garneau, Québec, QC, CanadaSession d’examens de mai 2012

La cryptographie à clé publique RSA Candidat no 000803–022

RésuméLe souci de confidentialité n’a jamais été aussi grand

depuis l’arrivée des médias sociaux et des systèmes decommandes en ligne sur la toile, mais à quel point lesprocédures utilisées aujourd’hui pour crypter et décryp-ter des messages sont-elles fiables ? Considérant les dif-férents algorithmes d’encodage assurant la sécurité destransactions bancaires et des échanges d’information, Ri-vest, Shamir et Adleman publièrent en 1978 l’article « AMethod for Obtaining Digital Signatures and Public-KeyCryptosystems » mettant au point la cryptographie à clépublique RSA et pavant ainsi la voie vers une véritablerévolution du domaine de la cryptologie. Les auteurs sug-gèrent une méthode mathématique sécuritaire exploitantla théorie élémentaire des nombres, principalement l’arith-métique modulaire, la fonction φ(n) d’Euler ainsi que lePetit théorème de Fermat et ciblent astucieusement le po-tentiel mathématique émanant de la difficulté à factoriseren un temps raisonnable un grand nombre n issu du pro-duit de deux nombres premiers p et q. Ce mémoire se veutune explication mathématique détaillée du protocole RSAet précise comment et pourquoi il fonctionne toujours de-puis son invention tout en commentant sa valeur sur lemarché mondial. Évidemment, une certaine partie de cetessai sera consacrée aux notions fondamentales de théoriedes nombres nécessaires à la compréhension de la matière.Ayant les outils mathématiques requis, le lecteur sera enmesure de comprendre l’algorithme et les principes qui endécoulent, dont la signature électronique et la construc-tion de grands nombres premiers par méthode analytiqueutilisant la fonction des nombres premiers π(x) et le sym-bole de Jacobi J(a, b) pour le test de primalité de Solovay-Strassen.

2


Remerciements

Comme préambule à ce mémoire, je souhaiterais adresser mesplus sincères remerciements aux personnes qui m’ont apporté leuraide et qui ont contribué à l’élaboration de ce mémoire ainsi qu’à laréussite de ces deux formidables années au Baccalauréat Internatio-nal.

Je tiens à exprimer ma reconnaissance envers Monsieur MarioFortin, professeur au département de mathématiques du CollègeFrançois-Xavier-Garneau, qui s’est toujours montré à l’écoute toutau long de la réalisation de ce mémoire. Je lui communique toutema gratitude pour l’aide et le temps qu’il a bien voulu me consacreret sans qui ce mémoire n’aurait jamais vu le jour. Je remercie aussiau passage Madame Louise Coll, professeur au même département,pour avoir nourri mon amour inconditionnel des mathématiques du-rant mes trois premières sessions au collège.

J’aimerais également remercier Olivier M. pour m’avoir agréable-ment initier au langage LATEX2ε, Simon-Pierre R. pour son supportmathématique et ses commentaires pertinents, Olivier S. pour sonsoutien moral, mes parents pour m’avoir constamment appuyé dansmes études collégiales, Carl F. Gauss pour son impensable génie etcertains proches qui ont finalement compris qu’il était bien possiblede faire des mathématiques durant les longues périodes de vacances.

Merci à tous et à toutes.

3


« J’ai trouvé une merveilleuse démonstration de cette proposition,mais la marge est trop étroite pour la contenir »

Pierre de Fermat (1601–1665),sur son dernier théorème.

4


Table des matières

1 Introduction 7

2 Un prélude au cryptosystème RSA 92.1 Rivest, Shamir et Adleman . . . . . . . . . . . . . . . 92.2 Une simplification de la cryptographie asymétrique . 102.3 L’algorithme RSA : une première rencontre . . . . . . 10

3 Quelques prérequis en théorie des nombres 123.1 Plus grand commun diviseur . . . . . . . . . . . . . . 123.2 Algorithme d’Euclide . . . . . . . . . . . . . . . . . . 123.3 Identité de Bézout . . . . . . . . . . . . . . . . . . . 133.4 Congruence modulo n . . . . . . . . . . . . . . . . . 143.5 Inverse modulaire . . . . . . . . . . . . . . . . . . . . 143.6 Fonction φ(n) d’Euler . . . . . . . . . . . . . . . . . 153.7 Petit théorème de Fermat généralisé par Euler . . . . 16

4 Le principe mathématique du code RSA 174.1 Le protocole d’échange . . . . . . . . . . . . . . . . . 174.2 Le cœur de l’algorithme . . . . . . . . . . . . . . . . 184.3 Deux exemples . . . . . . . . . . . . . . . . . . . . . 18

4.3.1 Utilisation de petits entiers p et q . . . . . . . 184.3.2 Application aux échanges commerciales . . . 19

4.4 Une signature électronique . . . . . . . . . . . . . . . 204.5 Comment chiffrer du texte . . . . . . . . . . . . . . . 21

4.5.1 Tableau 1 . . . . . . . . . . . . . . . . . . . . 22

5 Construire de grands nombres premiers 235.1 Une méthode générale . . . . . . . . . . . . . . . . . 235.2 Le théorème des nombres premiers et π(x) . . . . . . 235.3 Le test de primalité de Solovay-Strassen . . . . . . . 23

5.3.1 Le symbole de Jacobi J(a, b) . . . . . . . . . . 245.3.2 L’algorithme vulgarisé . . . . . . . . . . . . . 24

6 La cryptographie moderne 256.1 Le RSA aujourd’hui . . . . . . . . . . . . . . . . . . . 256.2 Des algorithmes pour factoriser n . . . . . . . . . . . 256.3 L’ordinateur quantique . . . . . . . . . . . . . . . . . 26

5


7 Conclusion 27

8 Annexes 308.1 Preuve que φ(n) est multiplicative . . . . . . . . . . . 308.2 Suppléments sur le test de primalité de Solovay-Strassen 31

8.2.1 Pseudocode de l’algorithme . . . . . . . . . . 318.2.2 Exemple . . . . . . . . . . . . . . . . . . . . . 31

8.3 Graphique 1 . . . . . . . . . . . . . . . . . . . . . . . 32

6


1 Introduction

L’ardent désir d’élucider un mystère a toujours été pour l’hommeune constante source de ludisme. Bien qu’il ait parfois été indifférentà l’idée de connaître l’inconnu, l’homme s’est exalté plus souventqu’autrement devant l’énigme et le secret ayant jonché son histoire.Des innombrables guerres antiques jusqu’au jour présent, ces luttesd’information ont délibérément forcé les états à se doter de codessophistiqués capables d’assurer la confidentialité des messages en-voyés. Ils ont d’ailleurs joué un rôle prépondérant dans l’élaborationde moyens de communication sécuritaires et ont permis d’aboutir àla définition que l’homme d’aujourd’hui se fait de la cryptographiemoderne.

Le chiffre de César, l’analyse fréquentielle linguistique, le chiffrede Vigenère brisé par Babbage, le télégramme de Zimmerman, lamachine Enigma, les travaux de Turing pendant la Seconde Guerremondiale et la cryptographie symétrique 1 ; voilà un bref portrait del’évolution de la cryptologie qui a mené à la sécurité infrangible quenous – enfin, certains – connaissons aujourd’hui.

La cryptologie, science contemporaine englobant la cryptographieet la cryptanalyse, constitue pour moi l’aboutissement d’une longueépopée ciselée par les arcanes de la diplomatie. Elle rassemble enelle seule le savoir de centaines de scientifiques qui, au cours deleurs recherches, ont élaboré des systèmes capables de dissimuleret de préserver les messages des plus grands stratèges militaires etpolitiques. À mes yeux, elle représente une facette trop souvent ou-blié des sciences mathématiques, une invention hors pair qui gît àl’ombre d’une société où la confidentialité y est presque inaliénable.

Je m’attarderai essentiellement à la cryptographie à clé publiquede type RSA en étudiant le processus mathématique de l’algorithmedécrit par ses inventeurs Rivest, Shamir et Adleman dans l’articleoriginal « A Method for Obtaining Digital Signatures and Public-Key Cryptosystems » [14]. Fondamentalement, je montrerai com-ment chiffrer et déchiffrer un message en toute sécurité, tout en abor-dant les notions mathématiques nécessaires relatives à la théorie des

1. Le lecteur intéressé se référera à [19] pour une histoire expliquée de la cryptologie.

7


nombres telles que la théorie des congruences de Gauss, l’algorithmed’Euclide, le théorème d’Euler émanant du petit théorème de Fermatet la fonction φ(n). Des exemples concrets seront également présen-tés afin de valider le cryptosystème RSA, ainsi qu’une explicationrigoureuse concernant la signature électronique. La génération degrands nombres premiers et le test de primalité de Solovay-Strassenutilisant le symbole de Jacobi J(a, b) 2 seront finalement explicités,suivis d’une discussion sur la valeur du code RSA à ce jour.

2. Je suis ici la notation de [17], mais il est plus fréquent de voir(ab

).8


2 Un prélude au cryptosystème RSA

2.1 Rivest, Shamir et Adleman

En 1976, Whitfield Diffie et Martin Hellman firent paraître leurarticle « New directions in cryptography » portant sur l’élabora-tion d’une cryptographie asymétrique et introduisirent le conceptde cryptographie à clé publique sans toutefois suggérer un algo-rithme mathématique l’expliquant rigoureusement. À la lecture dece papier, Ronald L. Rivest, diplômé de Yale en mathématique, doc-teur de Stanford et à ce temps chercheur en informatique au MIT(Massachussets Institute of Technology), entreprit des recherches encryptographie afin de mettre au point une fonction à sens uniquecapable de répondre aux exigences d’un chiffre asymétrique.

Leonard M. Adleman et Adi Shamir, également chercheurs enmathématique informatique, se joignirent bientôt à Rivest afin deformer une équipe idyllique et accomplie. Rivest et Shamir étanttous deux des spécialistes de l’informatique capable d’intégrer par-faitement des nouvelles idées mathématiques et de cibler assidûmentle cœur des problèmes, Adleman se faisait le censeur du trio. Aprèsun an d’hypothèses et de théories insolites bien souvent renverséespar Adleman, l’équipe en vint à mettre en œuvre le concept de cryp-tographie asymétrique.

Ron Rivest fit la découverte en 1977. Or, celle-ci étant le fruitd’une collaboration sans précédent, il décida d’ajouter les noms deses collègues à son article. Prêt à contempler l’annihilation de sonœuvre, Rivest porta son article à Adleman qui n’y décela cependantaucune faiblesse apparente. Sa seule et unique critique fut la listedes auteurs. Considérant qu’il n’avait pas assez contribué à la décou-verte, Adleman demanda la résiliation de sa signature, mais Rivestrefusa. L’article [14] parut alors en 1978, contenant le nom des troismathématiciens. Le sytème RSA – acronyme de Rivest, Shamir etAdleman – étant né et allait devenir le chiffre le plus important dela cryptographie moderne. 3

3. Voir [19] sous la section Alice et Bernard s’affichent en public, p. 338–340.

9


2.2 Une simplification de la cryptographie asymétrique

La cryptographie asymétrique utilise des fonctions à sens uniqueet à brèche secrète, c’est d’ailleurs ce qui fait sa force. Une tellefonction est difficilement inversible à moins de posséder la clé privée,mais est facilement utilisable pour quiconque la connaît.

On suppose qu’Alain veut envoyer un message à Béatrice. 4 Pource faire, il doit tout d’abord contacter cette dernière afin qu’ellegénère deux clés : une clé publique CB qu’elle envoie à Alain etune clé privée DB qu’elle conserve précieusement. Alain possédantla clé publique CB, il crypte son message et l’envoie à Béatrice. À laréception, elle utilise sa clé privée DB pour décrypter le texte. Dansla mesure où les deux compagnons désireraient partager un secret,ils doivent tous deux générer les deux clés différentes et s’échangerles clés publiques.

Bonjour Béatrice Chiffrement−−−−−−−→CB

a6G2k&%bL Envoi−−−→ a6G2k&%bL

Dechiffrement−−−−−−−−−→DB

Bonjour Béatrice

Figure 1Vulgarisation de la cryptographie à clé publique

2.3 L’algorithme RSA : une première rencontre

Le code RSA est un système cryptographique à clé publique, paropposition la cryptographie symétrique. Il repose sur l’utilisation decette clé (diffusée publiquement) et d’une clé privée (gardée secrète).L’une permet de chiffrer un message, tandis que l’autre sert à ledéchiffrer. Ces clés assurent la confidentialité du contenu envoyé.

Le fonctionnement de ce code est assez complexe, mais com-prendre comment le casser en est presque enfantin. En effet, il suffitd’être en mesure de décomposer un grand nombre en ses facteurs pre-miers afin d’accéder au message authentique. Mais que faire lorsquece nombre est de l’ordre de 500 chiffres ? Certes, même pour lesordinateurs les plus puissants et les scientifiques de notre époque,

4. Ces deux noms sont utilisés pour différencier A et B. On voit plus souvent Alice et Bob.

10


la factorisation d’un très grand entier en un temps respectable estimpossible. . . pour le moment.

Le code RSA se base principalement sur la théorie des nombres,plus particulièrement sur l’arithmétique modulo n et le petit théo-rème de Fermat généralisé par Euler. Évidemment, quelques notionsmathématiques connexes sont aussi importantes. Elles seront expli-citées à la section suivante. La méthode cryptographique fonctionneen raison de trois facteurs :

• Il est difficile pour un ordinateur de factoriser un grand nombre ;• Il est facile pour un ordinateur de construire de grands nombrespremiers ;

• Il est facile pour un ordinateur de vérifier si un grand nombreest premier ou non.

Afin de comprendre entièrement le fonctionnement mathéma-tique du code RSA, il est nécessaire d’introduire certaines notionsfondamentales. 5

5. On fera en partie référence à [17] sous la section Quelques outils de théorie des nombres,p. 214–217.

11


3 Quelques prérequis en théorie des nombres

3.1 Plus grand commun diviseur

Définition 1 (Plus grand commun diviseur). (i) Soit a, b ∈ Z∗.On dit que a divise b s’il existe x ∈ Z∗ tel que a = bx. On notela division a | b. (ii) Le plus grand commun diviseur, abrégé pgcd,de a et b est noté (a, b) ou pgcd(a, b). 6 Il satisfait aux deux critèressuivants :

(a, b) | a et (a, b) | bSi x | a et x | b, alors x | (a, b)

Plus formellement, on écrit

pgcd(a, b) = max{x ∈ Z∗ : x | a et x | b} (1)

3.2 Algorithme d’Euclide

L’algorithme d’Euclide permet de déterminer le plus grand com-mun diviseur de deux entiers dont on ignore la factorisation. C’estEuclide, dans son septième tome des « Éléments », qui instaura l’ap-plication répétée de la division algorithmique stipulant qu’un entiera peut être divisé par un entier positif b tel que le reste r de ladivision est plus petit que b. 7

Théorème 2 (Algorithme d’Euclide). Soit a, b ∈ N∗ tels que a ≥ b.On effectue la division euclidienne de a par b selon la suite {ri}. Onnomme le quotient qi et le reste ri. Ainsi, on a

a = bq1 + r1, 0 ≤ r1 ≤ b.

En substituant r1 à b, on obtient

b = r1q2 + r2, 0 ≤ r2 ≤ r1.

Et en itérant, on a donc

ri−1 = riqi+1 + ri+1, 0 ≤ ri+1 ≤ ri. (2)

6. On utilisera plus souvent la notation (a, b) que pgcd(a, b).7. Pour une explication approfondie sur l’Algorithme d’Euclide étendu, le lecteur intéressé

se référera à [4] sous la section The Euclidean Algorithm, p. 31–35.

12


La suite {ri} étant strictement décroissante, il existe n ∈ N tel quern+1 = 0. Alors, rn = (a, b).

Preuve Il faut tout d’abord montrer que rn | a et rn | b. Puisquern+1 = 0, la dernière équation s’écrit rn−1 = qn+1rn. Donc, rn | rn−1.On a également que l’avant dernière équation est rn−2 = qnrn−1+rn.Puisque rn | rn−1, alors rn | qnrn−1 + rn. Donc, rn | rn−2. On itèreen remontant les équations une à une. Finalement, on obtient rn | ripour tout i. Ainsi, rn | r1q2 + r2 = b. De la même manière, puisquern | b et rn | ri, alors rn | bq1+ r1 = a. Comme de fait, rn | a et rn | bet on peut conclure que rn | (a, b).

On pose d tel que d | a et d | b. On désire montrer qued | rn. On procède donc inversement. On sait que d | r1 = a − bq1.Dans la seconde équation, on a d | b et d | r1 et corollairementd | r2 = b− r1q2. En itérant, on obtient d | ri pout tout i et d | rn.

On en conclue que rn = (a, b).

�

3.3 Identité de Bézout

Théorème 3 (Théorème de Bachet-Bézout). Soit a, b ∈ Z∗. Il existex, y ∈ Z tels que

ax+ by = (a, b). (3)

Preuve On utilise la preuve du théorème 2. On pose quec = (a, b). Puisqu’on sait que c = rn, on remonte les équationsune à une. Comme rn−2 = qnrn−1 + rn, alors

rn = rn−2 − qnrn−1

Dans cette équation, on substitue rn−1 = rn−3 − qn−1rn−2 pour ob-tenir

rn = rn−2 − qn(rn−3 − qn−1rn−2)= rn−2(1 + qn−1qn)− qnrn−3

On effectue une substitution à rebours. On substituern−2 = rn−4 − qn−2rn−3 et on itère. À la fin, on obtientrn = r1x1 + r2y1 pour x1, y1 ∈ Z. En remplaçant r2 = b − r1q2,on obtient

13


rn = r1x1 + (b− r1q2)y1= r1(x1 − q2y1) + by1

On substitue r1 = a− bq1 pour finalement obtenir

rn = (a− bq1)(x1 − q2y1) + by1

= a(x1 − q2y1) + b(−q1x1 + q1q2y1 + y1)

= ax+ by

Où x = x1 − q2y1 et y = −q1x1 + q1q2y1 + y1.

�

3.4 Congruence modulo n

La théorie des congruences a été introduite par Carl FriedrichGauss (1777–1855) dans son ouvrage « Disquisitiones Arithmeti-cae », publié en 1801 alors qu’il n’était âgé que de 24 ans. 8 Elleest de même appelée « l’arithmétique modulo n » et est une théorieprépondérante en théorie algébrique des nombres puisqu’elle permetla résolution des problèmes portant sur les nombres entiers. Elle dé-coule de l’analyse du reste obtenu par une division euclidienne.

Définition 4 (Congruence sur les entiers modulo n). Soit n ∈ Z∗.On dit que a est « congru à b modulo n », et on écrit a ≡ b (modn),si n | (a− b), c’est-à-dire s’il existe x ∈ Z tel que a− b = nx.

Propriétés des congruences Soit a, b, c, d, x, y ∈ Z et n ∈ N.Alors,

a ≡ c (mod n) et b ≡ d (mod n) =⇒ ab ≡ cd (mod n),a ≡ c (mod n) et b ≡ d (mod n) =⇒ a+ b ≡ c+ d (mod n),a ≡ c (mod n) et b ≡ d (mod n) =⇒ ax+ by ≡ cx+ dy (mod n).

3.5 Inverse modulaire

Théorème 5 (Inverse modulaire). Soit a, n ∈ Z∗ tels que a < n. Si(a, n) = 1, alors il existe x ∈ {1, . . . , n−1} 9 unique appelé « inverse

8. Voir [4] sous la section Karl Friedrich Gauss, p. 68.9. L’ensemble {1, . . . n− 1} sous-entend qu’il s’agit de l’ensemble {1, 2, 3, . . . n− 1}. On

utilisera ici et par la suite la première notation.

14


modulaire » tel que 10

ax ≡ 1 (mod n). (4)

Preuve Comme (a, b) = 1, le théorème 3 assure l’existence dex, y ∈ Z tels que ax+ny = (a, n) = 1. Donc, ax = 1−ny, ou encoreax ≡ 1 (mod n). Si x /∈ {1, . . . , n− 1}, alors on peut lui ajouter ouretrancher un multiple de n pour l’y ramener sans pour cela changerla congruence ax ≡ 1 (mod n). Donc, l’existence est prouvée.

Maintenant, supposons qu’il existe une deuxième solutionx′ ∈ {1, . . . , n− 1} telle que ax′ ≡ 1 (mod n). Alors, on a quea(x− x′) ≡ 0 (modn). Ainsi, n | a(x− x′). Comme (a, n) = 1, alorsn | x−x′. On obtient x−x′ = kn où k ∈ Z, donc x ≡ x′ (modn). Delà, on déduit que x = x′ puisque x, x′ ∈ {1, . . . , n− 1}. La solutionest unique.

�

3.6 Fonction φ(n) d’Euler

La fonction d’Euler, connue également sous le nom de « fonc-tion indicatrice d’Euler » est une fonction en théorie des nombresessentielle de l’arithmétique modulaire. Elle est notée par la lettregrecque phi φ. 11

Définition 6 (Fonction d’Euler). φ(n) est le nombre d’entiers dansl’ensemble {1, . . . , n−1} qui sont relativement premiers avec n pourn > 1 et φ(1) = 1.

Théorème 7 (Fonction d’Euler avec un nombre premier). Si n estun nombre premier p, alors tous les entiers inférieurs à p sont rela-tivement premiers à celui-ci, et donc φ(p) = p− 1. 12

10. On voit parfois la notation a−1 ≡ 1(modn) qui signifie la même chose que ax ≡ 1(modn).Néanmoins, puisqu’il s’agit de calcul modulaire, a−1 ≡ 1 (mod n) 6= 1/a ≡ 1 (mod n).11. On voit aussi la notation ϕ. Ces deux lettres grecques différentes sont bien souvent

employées afin de distinguer la fonction d’Euler et le nombre d’or 1+√5

2.

12. Dans le cas où n est le produit de deux nombres premiers p et q, alorsφ(pq) = φ(p)φ(q) = (p−1)(q−1). Ainsi, la fonction d’Euler est multiplicative. La démonstra-tion de cette propriété est ici laissée de côté, mais elle se trouve en Annexe suivant la preuvede [4], p. 138–139. Il est également à noter que tout n > 0 peut s’écrire φ(n) =

∑d|n φ(d) ou

encore φ(n) = n∏

p|n (1− 1/p) d’après le théorème fondamental de l’arithmétique.

15


Preuve Puisque n est premier, ses seuls diviseurs possibles sont 1et n. On a donc que tous les entiers inférieurs à n sont relativementpremiers avec lui.

�

3.7 Petit théorème de Fermat généralisé par Euler

Théorème 8 (Petit théorème de Fermat-Euler). Soit a ∈ N. Si(a, n) = 1, alors

aφ(n) ≡ 1 (mod n). (5)

Preuve Soit A = {a1, a2, . . . , aφ(n)} l’ensemble de tous les en-tiers positifs inférieurs et relativement premiers à n. Puisque lepgcd(a, n) = 1, alors l’ensemble B = {aa1, aa2, . . . , aaφ(n)} est né-cessairement congru avec l’ensemble A. En prenant le produit de cescongruences, on obtient

(aa1)(aa2) · · · (aaφ(n)) ≡ a1a2 · · · aφ(n) (mod n)aφ(n)(a1a2 · · · aφ(n)) ≡ aa1 · · · aaφ(n) (mod n)

Puisque le pgcd(a1a2 · · · aφ(n), n) = 1, on peut diviser de chaque côtépar a1a2 · · · aφ(n) et on obtient aφ(n) ≡ 1 (mod n).

�

16


4 Le principe mathématique du code RSA

4.1 Le protocole d’échange

Choix de p et q Le receveur choisit p, q ∈ P où P est l’ensembledes nombres premiers. 13 Il calcule ensuite le module de chiffrementn = pq. Pour générer p et q, il est possible de déterminer des grandsnombres au hasard pour ensuite effectuer un test de primalité surceux-ci. 14 Les nombres p et q demeurent secrets.

Calcul de la fonction d’Euler Le receveur calcule la fonctiond’Euler φ(n) = (p− 1)(q − 1) à partir de p et q.

Choix d’une clé de cryptage Le receveur choisit un nombree ∈ {1, ..., n− 1} tel que pgcd(e, φ(n)) = 1, ce qui signifie que eest relativement premier avec φ(n). Ce nombre constitue l’exposantde chiffrement et est appelé clé de cryptage. Il est également public.

Construction d’une clé de décryptage D’après le théorèmeBachet-Bézout, il existe x, y ∈ Z tels que pgcd(e, φ(n)) = ex+φ(n)y.Ainsi, il existe également un inverse modulaire d ∈ {1, . . . , n − 1}tel que ed ≡ 1 (mod φ(n)). Le receveur calcule la clé de décryptaged avec l’Algorithme d’Euclide étendu. Le couple (n, e) constitue laclé publique, alors que le couple (n, d) constitue la clé privée.

Cryptage du message m à envoyer L’expéditeur veut envoyerun message m ∈ {1, . . . , n − 1} tel que pgcd(m,n) = 1. Pour lechiffrer, il calcule le reste de la division de me par n grâce à la clépublique. Ainsi, me ≡ a (modn) où a ∈ {1, . . . , n−1}. L’expéditeurenvoie le message crypté a au receveur.

Décryptage du message m reçu En recueillant le message cryptéa, le receveur calcule ad (mod n), ce qui redonne le message m.

13. La notation P est assez courante malgré ne pas être universelle. Elle sera fréquemmentutilisée dans le présent mémoire. À noter que P ⊂ N.14. Les spécifications sur les entiers p et q seront données à la section 6.1.

17


4.2 Le cœur de l’algorithme

Comment se fait-il que le procédé mathématique de cryptage etdécryptage fonctionne ? La réponse réside dans les propriétés descongruences.

Proposition 9 (Cryptage-décryptage RSA). Si on encode un mes-sage m tel que (m,n) = 1 comme a, où me ≡ a (mod n), alors ledécodage redonne m puisque ad ≡ m (mod n).

Preuve Si me ≡ a (mod n), alors

ad ≡ (me)d = med = mkφ(n)+1 = mkφ(n).m = (mφ(n))k.m

≡ 1k.m = 1.m = m (mod n)

Effectivement, comme ed ≡ 1 (mod φ(n)), alors ed = kφ(n) + 1 oùk ∈ Z∗ et on retrouve m grâce aux propriétés des exposants et desmodulos.

�

4.3 Deux exemples

Voici deux exemples fictifs mettant en œuvre le principe du codeRSA précédemment expliqué.

4.3.1 Utilisation de petits entiers p et q

D’emblée, on choisit p = 53 et q = 47, ce qui donne

n = 53× 47 = 2491.

On calcule ensuite la fonction d’Euler.

φ(n) = (p− 1)(q − 1) = 52× 46 = 2392.

On sélectionne un nombre e = 11. On a bien que pgcd(11, 2392) = 1.

Puis on calcule d, l’inverse de e modulo φ(n). Autrement dit, oncherche le plus petit entier d tel que 11d + 1 | φ(n). On trouved = 435. En effet, 1 = 435× 11− 2× 2392.

18


La clé publique est donc (2491, 11) et la clé privée est (2491, 435).On désire maintenant chiffrer le message m = 31. On a quepgcd(31, 2491) = 1. On calcule donc

3111 ≡ 928 (mod 2491)

et on l’envoie. Finalement, on calcule à la réception

928435 ≡ 31 (mod 2491).

On a récupéré le message m en toute confidentialité.

4.3.2 Application aux échanges commerciales

Une compagnie désire organiser un système de commandes parInternet. Elle décide donc d’instaurer un cryptage à clé publiqueRSA pour la transmission du numéro de carte de crédit de ses clients.Ce numéro comporte 16 chiffres auquel on doit ajouter la date d’ex-piration à 4 chiffres, suivie du code de vérification à 3 chiffres, pourun total de 23 chiffres. La firme choisit donc p et q, deux grandsnombres premiers. Ces deux entiers sont de l’ordre de 25 chiffres,pour un n d’environ 50 chiffres. La compagnie utilise Maple © 15comme suit afin de créer p et q :

α := nextprime((rand(10(β−1))..10β))()) (6)

Où α est le nombre premier et β son nombre de chiffres. Cetteopération génère les deux entiers premiers

p = 2079837531178409018889287

q = 4219989946770158557629509.

Le produit de ces deux nombres donnent

n = pq = 8776893472488152265104597671066650101750835170083

et la fonction d’Euler

φ(n) = (p− 1)(q − 1)

= 8776893472488152265104591371239172153183258651288.

L’entreprise crée également sa clé de cryptage

e = 2189375175

19


qui satisfait à (e, φ(n)) = 1 et calcule avec l’Algorithme d’Euclideétendu

d = 6681565402936615015268898856751168789622988067411.

Un client désire effectuer un achat. Son numéro de carte de cré-dit est 4960 9713 5329 0087, la date d’expiration est le 07/14 etle code de vérification est 597. Le message à envoyer est doncm = 49609713532900870714597. Avant d’envoyer, le logiciel calcule

me ≡ a ≡ 4545491832524543130442973

810910307214256675191921 (mod n).

À la réception, la firme calcule

ad ≡ 49609713532900870714597 (mod n).

Malheureusement, les entiers p et q sont trop petits dans cet exempleet il serait facile pour un ordinateur d’effectuer la factorisation. Defait, Maple © 15 installé sur un ordinateur avec processeur Intel ®Core i7 de 1,60 GHz factorise n en 2,1 secondes.

4.4 Une signature électronique

La méthode décrite jusqu’à présent fonctionne de manière ex-haustive, mais néglige toutefois une information importante, soitl’auteur du message chiffré. Préférablement, les virements banquairessécurisés par RSA doivent être accompagnés d’une signature élec-tronique, sans quoi il devient bien simple de se faire passer pourquelqu’un d’autre.

Dans un tel scénario, tant l’expéditeur et le receveur se fabriquentun système à clé publique, soit un triplet (n, e, d). Rappelons quela cryptographie RSA non-authentifiée demande au receveur seule-ment de créer sa clé. Ici, deux clés publiques sont générées.

Fabrication des deux clés L’expéditeur publie (nA, eA) et gardesecrètement dA, tandis que le receveur publie (nB, eB) et garde se-crètement dB.

Signature du message L’expéditeur débute par apposer sa signa-ture en calculant m1 ≡ mdA (mod nA). Encore une fois, il faut que(m1, nA) = 1.

20


Cryptage du message m à envoyer Si (m1, nB) = 1, il chiffreensuite avec la clé de cryptage du receveur m2 ≡ meB

1 (mod nB)puis l’envoie. Si jamais (m1, nB) 6= 1, ce qui est très peu probablepuisque nB ne possède que deux diviseurs étant pB et qB, l’expédi-teur doit légèrement changer son message m tel que (m1, nA) = 1 et(m1, nB) = 1.

Décryptage du message m Afin de décrypter le message m, lereceveur doit tout d’abord récupérer m1. Pour ce faire, il effectuem1 ≡ mdB

2 (mod nB). Enfin, il retrouve le message m en utilisanteA étant public en calculant m ≡ meA

1 (mod nA).

En se basant sur la preuve de la proposition 1 à la section 3.4,il est possible de montrer le processus mathématique utilisé pour lerecouvrement du message signé. En effet,

mdB2 ≡ meBdB

1 ≡ mk1φ(nB)+11 ≡ (m

φ(nB)1 )k1 .m1 ≡ m1 (mod nB).

Par ailleurs,

meA1 ≡ mdAeA ≡ mk2φ(nA)+1 ≡ (mφ(nA))k2 .m ≡ m (mod nA).

avec k1, k2 ∈ Z∗.�

Si le message avait été envoyé par un fraudeur, le receveur s’enaurait rapidement rendu compte à la réception. Dans le cas d’unecarte de crédit à 23 chiffres comme à l’exemple 4.3.2, le messagem n’aurait certes pas été constitué d’un tel nombre de chiffres. Dela même manière, un texte chiffré par un imposteur donnerait desphrases décousues et illisibles.

4.5 Comment chiffrer du texte

Signer et chiffrer des nombres semblent désormais possible grâceau code RSA. Mais que faire lorsqu’on désire coder autre chose quedes nombres ? Heureusement, il existe certaines tables d’équivalencestandards permettant la conversion. Le protocole ASCII (AmericanStandard Code for Information Interchange) est la norme de codagede caractères en informatique la plus connue à ce jour. Inventé en

21


1961, ce code assigne à chaque lettre de l’alphabet un nombre binairede 7 chiffres. 15 16 Il permet aussi une conversion en système octal, dé-cimal ou hexadécimal. Le tableau suivant ne présente qu’une petitepartie de la charte originale. 17

4.5.1 Tableau 1Code ASCII de l’alphabet latin majuscule en décimal et en binaire

Caractère Code en base Caractère Code en base10 2 10 2

A 65 1000001 N 78 1001110B 66 1000010 O 79 1001111C 67 1000011 P 80 1010000D 68 1000100 Q 81 1010001E 69 1000101 R 82 1010010F 70 1000110 S 83 1010011G 71 1000111 T 84 1010100H 72 1001000 U 85 1010101I 73 1001001 V 86 1010110J 74 1001010 W 87 1010111K 75 1001011 X 88 1011000L 76 1001100 Y 89 1011001M 77 1001101 Z 90 1011010

Tableau réalisé avec LATEX2ε.

15. Il y a donc 27 = 128 manières de disposer une telle combinaison.16. On découpe habituellement le texte en blocs et on effectue le cryptage-décryptage RSA

sur chacun d’eux afin de faciliter la tâche.17. Le tableau complet est facilement accessible sur le web.

22


5 Construire de grands nombres premiers

5.1 Une méthode générale

Le code RSA nécessite la génération de deux très grands nombrespremiers. Pour ce faire, on génère au hasard des nombres entiers deβ chiffres et on teste s’ils sont premiers. Le théorème des nombrespremiers affirme que pour tout x ∈ R+, le nombre π(x) est définicomme le nombre d’entiers premiers inférieurs ou égaux à x. Ainsi,il donne la distribution asymptotique des nombres premiers parmiles entiers.

5.2 Le théorème des nombres premiers et π(x)

Théorème 10 (Théorème des nombres premiers). 18 Soit

π(x) = # {p ≤ x | p ∈ P} (7)

alorsπ(x) ∼ x

ln(x)=⇒ lim

x→+∞π(x)

ln(x)x

= 1. (8)

Si on choisit au hasard un nombre n, on peut calculer approxi-mativement la probabilité que n soit premier. En effet, on a

Prob(n ∈ P) ≈n

ln(n)

n=

1

ln(n). (9)

Par exemple, on désire avoir un entier premier n de β = 500 chiffres.On calcule avec (9) la probabilité de tirer un nombre qui sera impair.Par conséquent, on veut un nombre se terminant par {1, 3, 5, 7, 9}.On effectue

(12

)ln(10500) =

(15

)500 ln(10) = 575, 646. On a donc

environ une chance sur 576 d’avoir un nombre premier en tirant auhasard un entier de 500 chiffres.

5.3 Le test de primalité de Solovay-Strassen

Solovay-Strassen est un test probabiliste permettant de savoirsi un nombre impair est un nombre composé ou probablement pre-mier, contrairement à un test déterministe qui confirme la prima-lité d’un nombre. 19 L’article original [14] propose l’utilisation de18. La preuve est d’un niveau très avancé et ne sera pas présentée ici.19. Le test de primalité AKS (Agrawal, Kayal et Saxena) est un test déterministe.

23


Solovay-Strassen pour obtenir de grands nombres premiers. Ce testutilise toutefois le symbole de Jacobi.

5.3.1 Le symbole de Jacobi J(a, b)

Définition 11 (Symbole de Jacobi). Soit a, b ∈ N tels que (a, b) = 1.Le symbole de Jacobi prend les valeurs {0,+1,−1}. Si b ∈ P, alors 20

J(a, b) =

0 si a ≡ 0 (mod b)+1 si ∃x ∈ N x2 ≡ a (mod b)−1 si @ un tel x.

(10)

5.3.2 L’algorithme vulgarisé

Théorème 12 (Test de primalité de Solovay-Strassen). SoitE = {1, . . . , n− 1} . Si n ∈ P et si a ∈ E, alors 21{

(a, n) = 1

J(a, n) ≡ an−12 (mod n)

(11)

Si n /∈ P , alors au moins la moitié des nombres de E ne satisfontpas à (10). On dira qu’ils échouent au test . Dès qu’un nombre a ∈ Eéchoue au test, on sait que n n’est pas premier. Si on choisit a ∈ Eau hasard, on a donc

Prob(a réussit le test | n /∈ P) ≤ 1

2. (12)

L’algorithme de Solovay-Strassen consiste à choisir aléatoirement,r fois de suite, n ∈ N et a ∈ {1, . . . n− 1} tels que (a, n) = 1,et de comparer J(a, b) et a

n−12 (mod n). Dès que l’on trouve un

résultat différent, on est certain que n est composé. Au contraire,si on trouve un résultat identique à chaque essai r consécutif, alorson peut affirmer que n ∈ P avec une probabilité X supérieure àX = 1−

(12

)r. 22 23

20. Si n /∈ P, on peut alors écrire b = p1 · · · pr et J(a, b) est défini parJ(a, b) = J(a, p1) · · · J(a, pr) =

∏ni=1 J(a, pi).

21. Euler a prouvé que pour tout nombre premier p impair,(

ap

)≡ a

p−12 (mod p) où

(ap

)est le symbole de Legendre.22. À r fixé, l’algorithme de Solovay-Strassen prend de l’ordre de r(log n)k opérations.23. Des suppléments sur Solovay-Strassen sont disponibles en Annexe dont un exemple de

test sur un nombre n donné. Par ailleurs, le graphique 1 aussi en Annexe présente X(r) etmontre la convergence hâtive vers 1,0 à partir d’environ r = 10 essais.

24


6 La cryptographie moderne

6.1 Le RSA aujourd’hui

Le chiffre RSA, malgré avoir été inventé il y a plus de trente ans,tient toujours. Il a véritablement incité des centaines de mathéma-ticiens à trouver de meilleurs algorithmes capables de factoriser nen un temps raisonnable. À ce jour, personne n’a encore été en me-sure de briser le fameux code. Il suffit d’augmenter le nombre dechiffres de n pour confondre les plus astucieux chercheurs se pen-chant sur le sujet. La confiance qu’inspire l’algorithme RSA reposeprincipalement sur l’échec. À vrai dire, toutes les tentatives de bri-ser le code depuis se sont avérées vaines et n’ont conduites qu’à desimples spécifications sur p, q, e et d.

Le tableau 1 de l’article original [14] évaluait en 1978 à 74 ansle temps nécessaire pour factoriser un nombre de 100 chiffres,3,8×109 années pour un nombre de 200 chiffres et 4,2×1025 annéespour un nombre de 500 chiffres. Étant donné l’évolution fulgurantedu domaine de l’informatique et l’augmentation de la puissance desordinateurs, un n de 100 chiffres est maintenant déconseillé. SelonDelahaye dans [7] et [18], les experts recommandent des nombresn de 768-bit (232 chiffres) pour des données très peu importantes,mais ils conseillent 1024-bit (309 chiffres) pour un usage commer-cial et 2048-bit (617 chiffres) pour un contenu gardé secret sur unelongue période de temps.

Le RSA est implanté dans plus de 300 millions de programmes in-formatiques. Les platformesWindows ,Mac OS et Linux contiennentnécessairement des programmes cachés utilisant l’algorithme RSA.En outre, plusieurs institutions gouvernementales, universitaires etmême militaires l’utilisent. Le SWIFT (Society for Worldwide In-terbank Financial Telecommunication) l’emploie également.

6.2 Des algorithmes pour factoriser n

Il existe plusieurs algorithmes de factorisation pour de grands en-tier n. Les plus efficaces sont le crible quadratique de Pomerance, laméthode des courbes elliptiques de Lenstra ainsi que le crible géné-

25


ral sur les corps de nombres 24 de Pollard, Adleman, Buhler, Lenstraet Pomerance, soit le meilleur algorithme de factoriation connu àce jour. 25 Ce dernier a d’ailleurs permis à Thorsten Kleinjungle etal. en décembre 2009 de factoriser un n de 232 chiffres (RSA-768)après plus de 2 ans de recherche dans le cadre du RSA FactoringChallenge. 26

6.3 L’ordinateur quantique

En 1994, Peter W. Shor mit au point un algorithme probabi-liste théorique capable de factoriser un entier n en temps polyno-mial mieux connu sous le nom d’Algorithme de Shor . 27 Malheureu-sement, ce protocole ne fonctionne que sur un ordinateur quantiquequi n’a pas encore été inventé, même en 2012. Si on réussit un jourà construire de telle machine à calculer, la cryptographie mathéma-tique sera irrémédiablement ébranlée, si ce n’est pas à jamais com-promise. La factorisation de clés de plus de 500 chiffres ne prendraitalors que quelques minutes ! Soulignons que de réelles démarchesont été entreprises quant à la création d’un ordinateur quantique.En 2001, l’équipe du laboratoire d’IBM sous la supervision d’IsaacChuang réussit à factoriser le nombre 15 en 3×5 sur un ordinateur àsept bits quantiques simultanément dans un état superposé. 28 Il fau-dra encore quelques années, voire des dizaines, avant d’effectuer lafactorisation d’un n de 2048-bit. L’algorithme RSA est donc encoreen sécurité pour un bon moment.

24. L’idée exploitée par une telle méthode vient de Pierre de Fermat : si on trouve x, y ∈ Ztels que x2 ≡ y2 (modn), alors (x+y)(x−y) = 0 (modn) et le pgcd(x+y, n) ou pgcd(x−y, n)donne un diviseur non trivial de n.25. Il utilise O

{exp

[(649log n

) 13 (log log n)

23

]}étapes pour factoriser un nombre entier n.

26. Le lecteur intéressé se réfèrera à [1] pour plus d’informations sur la procédure mathé-matique utilisé pour factoriser RSA-768.27. L’algorithme fonctionne en temps O((log n)3) et en espace O(log n). On n’élaborera

point sur le principe de l’algorithme de Shor, puisqu’il découle de notions mathématiques etphysiques extrêmement poussées pouvant faire l’objet d’un seul mémoire.28. Voir [16] pour plus de détails sur la procédure.

26


7 Conclusion

Somme toute, il est non seulement possible, mais également trèsastucieux de faire usage de la théorie élémentaire des nombres encryptographie afin de chiffrer et déchiffrer des messages. On a, commede fait, montré par l’entremise de diverses notions mathématiquesrelatives aux propriétés des nombres premiers le fonctionnementalgorithmique du protocole RSA en s’attardant principalement auprocessus d’encodage-décodage en plus d’y joindre une explicationdétaillée sur la signature électronique et l’élaboration de grandsnombres premiers par méthode analytique. Partant, on a mis lu-mière sur le génie de Rivest, Shamir et Adleman qui, trente-quatreans après, démontre toujours son inhérente élégance et son prestigemalgré l’arrivée de nouveaux algorithmes de cryptage symétriquetels le DES (Data Encryption Standard) et le AES (Advanced En-cryption Standard) sur l’échiquier commercial.

La cryptographie à clé publique RSA est une invention qui, commeon l’a mentionné, a encore de bien belles années devant elle. Les ma-thématiciens créeront-ils un jour un code réellement impossible à dé-crypter, aboutissement de leur ultime quête du secret absolu ? Seulela cryptographie quantique changera la donne. On dit que la Pre-mière Guerre mondiale a été la guerre des chimistes avec le chlore etle gaz moutarde et que la Deuxième a été celle des physiciens avec labombe atomique. Certes, la Troisième, s’il y en a une, sera celle desmathématiciens qui eux auront en main l’arme suprême : le contrôlede l’information.

27


Médiagraphie

[1] Aoki K., Franke J., Lenstra A.K., Thomé E., Bos J. W., GaudryP., Kruppa A., Montgomery P. L., Osvik D. A., te Riele H., Ti-mofeev A. & P. Zimmermann. « Factorization of a 768-bit RSAmodulus », ACM Digital Library, Crypto ’10 Proceedings of the30th annual conference on advances in cryptology, 2010.

[2] Baldoni M. W., Ciliberto C. & G. M. Piacentini Cattaneo. « Ele-mentary number theory, cryptography and codes », Università diRoma, Rome (Italie), Éditions Springer, 2009, 522 pages.

[3] Bayart, Frédéric. « La cryptographie expliquée », BibMath,www.bibmath.net/crypto/plan.php3 , janvier 2012.

[4] Burton M., David. « Elementary number theory », University ofNew Hampshire, Durham (É.-U.), Allyn & Bacon Inc., 390 pages.

[5] Cayrel, Pierre-Louis. « Arithmétique modulaire pour la crypto-graphie », Université de Limoges, Limoges (France), Bases dedonnées IUT, 47 pages.

[6] de Koninck, Jean-Marie & Armel Mercier. « Introduction à lathéorie des nombres », Mont- Royal (Canada), Éditions Modulo,1994, 254 pages.

[7] Delahaye, Jean-Paul. « La cryptographie RSA 20 ans après »,Pour la Science, no 267, 2000.

[8] Dietzfelbinger, Martin. « Primality testing in polynomial time :from randomized algorithms to PRIMES is in P », Lecture Notesin Computer Science (LNCS), vol. 3000, Springer Editions, 2004,147 pages.

[9] Ireland, David. «RSA algorithm », DI Managemant (Cryptogra-phy), www.di-mgt.com.au/rsa_alg.html , janvier 2012.

[10] Maplesoft. « Maple 15.01 », Waterloo Maple © Inc., Ontario(Canada), 2011.

[11] Oetiker T., Partl H., Hyna I. & E. Schlegl. « The not so shortintroduction to LATEX2ε », Version 4.31, GNU General PublicLicense, Cambridge (É.-U.), 2010.

[12] R. Simanca, Santiago & Scott Sutherland, « The RSA Pu-blic key cryptosystem », Mathematical Problem Solving withComputers (Notes for MAT 331, 2002), Stony Brook University,

28


www.math.sunysb.edu/∼scott/Book331/RSA_Public_key.html ,janvier 2012.

[13] Richman, Fred. « Quadratic reciprocity : the Jacobi symbol »,Florida Atlantic University, Department of Mathematics, BocaRaton (É.-U.), math.fau.edu/richman/jacobi.htm, janvier 2012.

[14] Rivest R. L., A. Shamir & L. Adleman, « A method for obtai-ning digital signatures and public key cryptosystems », Commu-nications of the ACM, vol. 21, no 2, 1978, p. 120–126.

[15] Rosenberg, Burton. « The Solovay-Strassen primality test »,Cryptography (Notes for MATH 609/597), University of Miami,Miami (É.-U.), 2000.

[16] Ross, Michael. « IBM’s Test-Tube Quantum Computer makeshistory first demonstration of Shor’s historic factoring al-gorithm », IBM Press release of December 2001, www-03.ibm.com/press/us/en/pressrelease/965.wss , janvier 2012.

[17] Rousseau, Christiane & Yvan Saint-Aubin. «Mathématiques ettechnologie », Montréal (Canada), Éditions Springer, 2008, 593pages.

[18] RSA Laboratories. « Standards Initiatives : Public-KeyCryptography Standards (PKCS) », EMC Corporation,www.rsa.com/rsalabs/node.asp ?id=2213 , janvier 2012.

[19] Singh, Simon. « Histoire des codes secrets », Éditions Livre dePoche, 1999, 504 pages.

[20] Weisstein, Eric. Wolfram Mathworld,www.mathworld.wolfram.com, janvier 2012.

29


8 Annexes

8.1 Preuve que φ(n) est multiplicative

Preuve Soit m,n ∈ N tels que (m,n) = 1. Il faut montrer queφ(mn) = φ(m)φ(n). On dispose d’abord les entiers positifs inférieursà mn dans la matrice A comme suit :

A =

1 m+ 1 2m+ 1 · · · (n− 1)m+ 12 m+ 2 2m+ 2 · · · (n− 1)m+ 2...

......

......

i m+ i 2m+ i · · · (n− 1)m+ i...

......

......

m 2m 3m · · · nm

(13)

On considère la i-ème ligne de la matrice A. Si (m, i) = d > 1,alors aucun élément de la i-ème n’est relativement premier avec met donc ne l’est nécessairement pas avec mn. Tous les éléments de lai-ème ligne étant de la forme km+ i où k = n− 1, si (m, i) = d > 1,alors d | m et d | i selon la définition du pgcd et d | km + i. Dece fait, pour trouver la fonction φ(n) étant le nombre d’entiers dansl’ensemble {1, . . . ,mn− 1} qui sont relativement premiers avec mn,il suffit d’examiner la i-ème ligne telle que (m, i) = 1. On compteφ(mn) lignes satisfaisant à ce critère. Parmi ces lignes, on doit main-tenant déterminer le nombre d’entiers relativement premiers avecmn. On a i,m + i, 2m + i, . . . , (n − 1)m + i. Puisque (m, i) = 1,chaque entier n est relativement premier avec m. De tels entiersforment un système complet de résidus modulo n et donc il y aexactement φ(n) de ces entiers qui sont relativement premiers avecn. Comme φ(n) entiers sont relativement premiers avecm, ils le sontnécessairement avec mn.

En résumé, il y a précisément φ(m) lignes de la matrice A conte-nant des entiers relativement premiers avec mn. Chacune de ceslignes contient φ(n) entiers relativement premiers avec mn. Ainsi,φ(mn), soit le nombre total d’entiers de A relativement premiersavec mn, vaut bien φ(m)φ(n).

�

30


8.2 Suppléments sur le test de primalité de Solovay-Strassen

8.2.1 Pseudocode de l’algorithme

Selon [8], l’algorithme peut être écrit comme suit :

Entrées : n : variable entière impaire dont on veut connaître laprimalité ; r : variable qui représente le nombre de fois où la primalitésera testée.Sortie : composé si n est composé, sinon probablement premierrépéter r fois :

choisir a au hasard dans {2, . . . , n− 1}x←− J(a, n)

si x = 0 ou an−12 6≡ x (mod n), alors retourne composé

retourne probablement premier.

8.2.2 Exemple

On veut savoir si le nombre impair n = 713 est premier. Oncalcule n−1

2= 356. On choisit ensuite a = 123 < n et on teste

an−12 (mod n) = 123356 (mod 713) = 94.

Après, on détermine le symbole de Jacobi modulo n. Cette opérationexige une bonne connaissance des propriétés de J(a, n).

J(a, n) (mod n) = J(123, 713) (mod 713) = −1.

Déja, on sait que n est composé, puisque J(a, n) 6= an−12 (modn). Si

l’égalité avait été vraie, on aurait du recommencer avec un a diffé-rent, et ce, r fois de suite jusqu’à ce qu’on obtienne une probabilitésuffisante que n soit premier . Dans cet exemple, c’était facile à voirque 713 = 23× 31.

31


8.3 Graphique 1

Probabilité X(r) = 1−(12

)r qu’un nombre n soit premier enfonction du nombre d’essais r consécutifs et aléatoires selon

l’algorithme de Solovay-Strassen

r

X(r)

302010

0,2

0,4

0,6

0,8

1,0

Graphique réalisé avec Maple © 15

32

Documents

Mémoire - Candidat no 000803-022