SCIENCES & VIE

Les nombres premiers, Ces merveilleux nombres au cœur de la cyber-sécurité.

Les nombres premiers ont depuis toujours fasciné les mathématiciens. Mais pourquoi ? Parce que bien qu’ils soient définis par une propriété simple « un nombre premier est un entier naturel défini par le fait d’avoir exactement deux diviseurs distincts, 1 et lui-même », il existe une infinité de nombres de ce type, et leur répartition, qui ne semble être régie par aucune règle, paraît très irrégulière. Ces nombres sont merveilleux et particulièrement importants en arithmétique. Mais ils font également l’objet d’une actualité brûlante dans les nouvelles technologies, en particulier dans la cyber-sécurité, pour le codage des informations.

Aperçu, petite présentation

La cyber-sécurité est la discipline qui a pour objet d’identifier les diverses menaces que peut courir un système informatique et déterminer la manière la plus efficace de lutter contre la dite menace. Parmi les menaces possibles qui peuvent surgir dans un système d’information se trouve l’espionnage. C’est lorsque un pirate, conventionnellement nommé Oscar, veut à tous prix connaitre le contenu des échanges entre deux individus, conventionnellement nommés Alice et Bob.

La discipline qui consiste à lutter contre ces genres de menaces s’appelle ” la cryptographie”. Celle-ci étudie les manières de chiffrer un message de sorte qu’il ne soit lisible que par le destinateur et son destinataire. Dans ce domaine, les nombres premiers jouent un rôle très important et sont le plus utilisés dans le chiffrement des messages.

Tous nous avons des petits secrets que nous gardons mais que nous aimerions partager en sécurité un jour avec un ami. On a tous ce fort envie de ne plus laisser fuiter nos informations personnelles sur les réseaux sociaux ou sur internet. En général, tous on a besoin de la sécurité qu’elle soit dans la vie réelle ou sur internet.

Voici, dans cet article j’ai eu envie de vous partager quelques notions sur la cyber-sécurité et l’histoire de la cryptographie. En lisant cet article non seulement nous verrons la quintessence des nombres premiers, mais aussi l’importance de l’utilisation de ces derniers dans le chiffrement des messages.

Les Nombres premiers, Anecdote et mystère.

Depuis l’école primaire, nul ou fort que nous soyons en mathématique. Tous, savons qu’un nombre premier est un nombre qui n’est divisible que par 1 et par lui-même. Ainsi commence la liste des nombres premiers : 2,3,5,7,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,… tous ces nombres sont divisibles par 1 et par eux-mêmes.

Dès l’antiquité, les mathématiciens ont commencé à se poser beaucoup des questions sur ces nombres mystérieux dites “nombres premiers”. Il y’a-t-il plusieurs nombres premiers? Leur ensemble est-il infini? Comment se répartissent-ils?

Vers 200 av. J-C, le mathématicien grecque et père de la géométrie Euclide, démontra que l’ensemble des nombres premiers est infini. Sa preuve s’appuie sur la fonction factorielle. Pour tout entier n, on définit l’entier noté “n!” appelé factorielle de n, tel que:

  • Pour n=0, n!=1
  • Pour n≠0, n!=n x (n-1) x (n-2) x … x 1
Lis aussi:  Les 4 interactions fondamentales responsables de tous les phénomènes physiques observés dans l’univers.

Pour tout entier n, l’entier n! +1 n’est divisible par aucun entier d ≤ n!

En effet, pour chaque entier d ≤ n! , la division euclidienne de n! +1 et d se fait toujours avec un reste. Ce qui veut dire que n! +1 est un nombre premier et par suite, l’ensemble des nombres premiers est infini. Soit ∏ (n) le nombre de nombres premiers inférieurs ou égaux à un entier fixé n. Au 18e siècle le prince de mathématicien Gauss et Adrien-Marie Legendre conjecturèrent que :

Depuis lors, d’intenses recherches sont menées sur l’étude de nombres premiers et beaucoup des conjectures sont émises. Parmi ces conjectures on peut citer la célèbre conjecture du mathématicien allemand Riemann dite « Hypothèse de Riemann ». C’est un problème extrêmement difficile à résoudre avec une question de base très simple “comment sont reparti les nombres premiers?”. Cette conjecture fait partie des sept problèmes du millénaire.

La Cryptographie, outil indispensable à plusieurs égards

L’objectif fondamental de la cryptographie comme signalé au début de cet article, est de permettre à deux personnes, soit Alice et Bob de communiquer. Cette communication est à travers un canal sur de telle sorte qu’une troisième personne nommée  Oscar, ayant accès aux informations qui circulent sur le canal de communication ne puisse pas comprendre ce qui est échangé.

La cryptographie est donc à proprement dite, une science des communications secrètes. Dès l’antiquité, des systèmes cryptographiques ont commencés à être élaborés. L’empereur romain César utilisait déjà le chiffrement dit à substitution mono-alphabétique qui consistait à déclarer les lettres de l’alphabet d’un nombre de positions données.

Exemple

César réunit ses officiers et leur communique la clé par le chiffrement des messages, un décalage de six positions. En suite un officier envoi a son collègue qui est au front le message suivant: HJXFW   FZWFNY   JYJ   HTSYJSY    IJ IJATZX.

Connaissant que la clé de chiffrement est un décalage de six positions, comment peut-il déchiffrer ce message? Un décalage de six positions signifie que l’alphabet a été transformé de la manière suivante:

En remplaçant chaque lettre par son équivalent ou correspondant dans l’alphabet on retrouve le vrai message qui est le suivant : CESAR   AURAIT ETE   CONTENT   DE   VOUS.

Autres systèmes cryptographiques.

D’autres systèmes ont été élaborés tels que le code MORSE ou bien la machine Enigma utilisée par les nazis pendant la deuxième guerre mondiale. Mais très vite ces codes se sont avérés inefficaces et très faciles à briser par les pirates. Vers la fin du XXe siècle, avec la révolution de l’internet, des systèmes cryptographiques plus sûrs et plus robustes se sont vu crées.

Problèmes qui se posent

En effet, dans la cryptographie ancienne les différentes personnes sensées échanger les informations devraient se rencontrer physiquement et se convenir d’une clé secrète pour chiffrer leurs échanges. Pour notre exemple précédent, César devrait réunir ses officiers pour leur communiquer le nombre de décalage à considérer dans l’alphabet.

Lis aussi:  La Consanguinité, s’il restait deux personnes sur terre, seront-elles capables de se reproduire et sauver l’humanité ?

Par contre avec internet, des problèmes nouveaux se posent : Comment s’envoyer des messages sécurisés par mail quand on est séparé par des milliers de kilomètres de distance sans avoir l’occasion se rencontrer au préalable pour convenir d’une clé? Comment faire des achats en ligne sans laisser fuiter ses propres coordonnées bancaires?

Ces nombres premiers, Nos héros

Les mathématiciens ont résolu ce problème en inventant la cryptographie dite à clé publique. C’est-à-dire que la clé de chiffrement est connu de tous mais chaque individu garde une clé privée pour déchiffrer les messages qu’il reçoit. Cette méthode se fonde sur la propriété de certaines fonctions mathématiques dites à sens unique. Càd des fonctions faciles à calculer mais dont la réciproque est difficile à calculer en temps raisonnable.

Le premier crypto-système à clé publique à être développé est le RSA. Il se base sur la difficulté de factoriser un entier n, en produit de nombres premiers. Puis, suivront les crypto-systèmes exploitant la difficulté de résoudre le logarithme discret dans un corps fini ou dans le groupe de points d’une courbe elliptique définie sur un corps fini.

L’algorithme RSA

Nous sommes tous en mesure de multiplier deux nombres premiers en un laps de temps et trouver ainsi un nombre composé. Mais il devient plus vite difficile de factoriser un nombre premier ne fut-ce que de dix chiffres en produit de nombres premiers.

Exemples

Calculer à la main 83 x 89 :

C’est une opération très facile

Maintenant factorisons à la main le nombre 3127 en produit de nombres premiers.

La seule méthode applicable à la main est celle dite du crible d’ Ératosthène. Celle-ci consiste à faire une liste de nombres premiers inférieurs ou égal à la racine carrée du nombre considéré (pour notre exemple on a choisi le nombre 3127). Et enfin, les essayer l’un après l’autre pour savoir lesquels divisent le nombre considéré. En appliquant cette méthode pour notre cas, on trouve après beaucoup de temps 3127 = 83 x 89, 83 et 89 sont bel et bien des nombres premiers.

Remarque

Nous constatons qu’on multiplie avec une simplicité extrême deux nombres premiers mais qu’il est très difficile de factoriser à la main un nombre de seulement 4 chiffres. C’est sur cette remarque fondamentale que repose l’algorithme RSA. Le sigle RSA vient des initiales des noms de trois mathématiciens qui ont inventé cet algorithme. Il s’agit de RIVEST, SHAMIR ET ADLEMAN.

Les fondateurs du système RSA. De gauche à droite RONALD RIVEST, ADI SHAMIR et LEONARD ADLEMAN

Le coin des matheux, Démonstration

Les détails de l’algorithme RSA font appel à quelques subtilités mathématiques difficiles à saisir, Néanmoins voici un aperçu de son fonctionnement:

Théorème

Alice et Bob choisissent chacun deux nombres premiers, respectivement p1, q1 et p2, q2. Ils calculent chacun    n1= p1 x q1   et n2= p2 x q2.

Ils calculent chacun la fonction indicatrice d’Euler ;

  • φ (n1)= (p1– 1) (q1-1)
  • φ (n2)= (p2– 1) (q2-1)

Démonstration

Alice choisit dans l’anneau Z/φ (ns)Z un entier un entier e1 premier avec φ (n1) et calcul son inverse de modulo φ (n1) . Le couple (e1, n1) constitue la clé publique d’Alice et le triplet (d1, p1, q1) constituent sa clé privée. Bob génère par le même procédé la clé privée (d2, p2, q2) et la clé publique (e1, n1).

Lis aussi:  La Consanguinité, s’il restait deux personnes sur terre, seront-elles capables de se reproduire et sauver l’humanité ?

Si Bob veut envoyer un message y à Alice, il va le chiffrer de la manière suivante:

y= xe1 mod n1

Alors, Alice va déchiffrer le message y envoyé par Bob comme suit:

                                     X = yd1 = (xe1) d1 = xe1.d1 = x1=x

Ainsi, elle retrouve le message initial que Bob a voulu envoyé.

Exemple :

Pour communiquer avec Bob, Alice se choisit les nombres premiers p1=47 et q1= 59. Elle calcule :

  1. n1= 47×59=2773 et,
  2. φ (n1)= (47-1) (59-1)  = 46×58 = 2668

Elle se choisit la clé publique (17, 2773) car 17 et 2668 sont premiers entre eux et calcule d1 = 17-1 mod 2668 = 157 et garde donc sa clé privée (157, 47, 59). Bob connaissant la clé publique d’Alice, souhaite lui communiquer la lettre B qui correspond au code ASCII 01000010 =66. Il lui suffit de calculer : 6617 mod 2773 = 872.

Et donc, il va envoyer à Alice le nombre 872 pour signifier la lettre B. Alice à son tour, pour déchiffrer le message de Bob, elle va calculer : 872d1 mod 2773 = 872157mod 2773 =66.

Cet algorithme RSA est beaucoup plus utilisé dans le commerce électronique et pour générer des signatures numériques.

Les nombres premiers, toujours cruciaux

Nous signalons que même dans les deux autres crypto-systèmes que nous n’avons pas décrit largement, celui sur le logarithme discret et celui sur les courbes elliptiques. Les nombres premiers sont toujours utilisés et jouent un rôle de premier plan.

En effet, le logarithme discret se calcule dans les corps finis alors que ces corps sont construits à partir de nombres premiers. De même pour les courbes elliptiques, utilisées en cryptographie, elles sont définies sur les corps finis. Ces derniers sont construits grâce aux nombres premiers.

Épilogue

Alors, tout va pour le mieux dans le meilleur des mondes ? Jamais nous n’aurons de problèmes de sécurité dans nos transferts de données ? Pas tout à fait, car la cryptographie doit faire face à une double évolution dans le temps.

Tout d’abord, la recherche en mathématiques, et en particulier en arithmétique, se poursuit. Des méthodes ont déjà été mises au point pour diminuer drastiquement le nombre d’opérations à effectuer pour décomposer un nombre en nombres premiers.Ensuite, l’accroissement de la puissance des ordinateurs se poursuit elle aussi. Enfin, disons que le monde des nombres premiers est infiniment riche. Ces derniers sont cruciaux pour le développement de l’informatique et dans les communications modernes.

Retrouvez-nous dans un nouveau titre. Influenscia ,One goal,One life

Par Daniel NGABO

Afficher plus

Influenscia

Ce blog est un tremplin, une fenêtre ouverte sur le monde de la découverte.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Bouton retour en haut de la page
Fermer
Fermer

Adblock détecté

S'il vous plaît envisager de nous soutenir en désactivant votre bloqueur de publicité