• Les nombres premiers et leur rôle dans la cryptographie moderne

    Les nombres premiers

    Définition et conséquences :

    Un nombre premier est un entier strictement supérieur à 1, qui admet exactement deux diviseurs distincts.

    Si p est un nombre premier alors ses seuls diviseurs sont 1 et p.

    (En arithmétique, 1 n'est pas considéré comme un nombre premier pour des raisons de commodité.)

    Exemples :

    2, 3, 5, 7 et 40390761282604429748980603 sont des nombres premiers

    4, 6 1024 et 1947626044289806032 ne sont pas des nombres premiers

    A propos de l'ensemble des nombres premiers... :

    Il existe une infinité de nombres premiers.

    Euclide est l'auteur de la démonstration la plus simple de ce résultat :

    Supposons donc choisi un nombre premier p, p > 5, et formons le produit 2 ´3 ´5 ´... ´p, de tous les nombres premiers compris entre 2 et p, puis posons :

    N = (2 ´3 ´5 ´... ´p) + 1.

    N étant strictement supérieur à 2, N admet un diviseur premier. Soit q ce diviseur.

    Or aucun des nombres de la liste 2, 3, 5, ..., p, n'est un diviseur de N car le reste de la division de N par un nombre quelconque de cette liste est toujours 1.

    Donc q est strictement supérieur à p.

    Donc si on choisi un nombre premier quelconque, on trouve toujours un nombre premier qui lui est strictement supérieur. Il en résulte que le suite des nombres premiers est infinie.

    Note : Il existe plusieurs autres démonstrations de ce théorème. Citons celle d'Euler (1737), de Polya (1920), d'Erdös (1938). Aucune n'est plus simple que celle d'Euclide. Celle d'Euler a le mérite de montrer, pour la première fois, que l'Analyse permet de démontrer des résultats sur des nombres entiers. Cette première incursion de l'Analyse dans l'Arithmétique se mua au XIXe siècle en une véritable invasion pour créer la branche des mathématiques que l'on appelle aujourd'hui la théorie analytique des nombres.

    Par ailleurs, les mathématiciens s'intéressent depuis longtemps aux questions suivantes :

    La répartition des nombres premiers dans la suite des naturels est-elle régulière ?

    Présente-t-elle des particularités intéressantes ?

    Ils sont arrivés à la conclusion que cette répartition était plutôt anarchique, que globalement, la proportion des nombres premiers va en décroissant. Plus précisément, si l'on note suivant l'usage p (x) le nombre de nombres premiers inférieurs à un réel x, alors p (x) est un infiniment grand équivalent "au voisinage de l'infini" à x / ln x.

    Ce résultat a été démontré par Tchebychev en 1896 à partir de conjectures de Legendre (1785) puis de Gauss.

    Les nombres premiers sont une perpétuelle source de recherche pour les savants. Bien que définis de manière simple ils sont l'objet d'analyses théoriques forts complexes et depuis la mise en place d'algorithmes nécessitant des nombres premiers en cryptographie, ils représentent un réel enjeu actuel. Et ce à tel point que de mystérieux mécènes sont prêts à débourser des sommes considérables pour stimuler la recherche dans ce domaine et obtenir des résultats exploitables.

    Nombres premiers et cryptographie

    Définition

    La cryptographie est la science qui cherche à fabriquer des codes secrets, à trouver le code de messages secrets. Aujourd'hui, grâce aux performances de plus en plus élevées des ordinateurs, elle intervient dans tous les domaines de la sécurité militaire mais aussi civile.

    Vocabulaire

    Le chiffrement consiste à traduire un message donné en langage codé.

    Le déchiffrement consiste reconstituer le message initial à partir d'un message codé lorsqu'on connaît le code.

    Le décryptage est la recherche d'une méthode qui permet de trouver le code inconnu.

    Quelques exemples

    Le code dit de Jules César

    On remplace une lettre de l'alphabet naturel par la lettre qui la suit dans l'alphabet (A ® B, B ® C, ..., Z ® A, ).

    Note : Ce code fut utilisé par l'armée romaine, lors des guerres expansionnistes menées par l'Empire.

    Le code Enigma

    On dispose d'une clé secrète, facile à retenir, par exemple, MATH, qui fournit la suite (13, 1, 20, 8) obtenue à partir de la position des lettres dans l'alphabet. On code alors le message à envoyer en joutant 13 points à la première lettre du message (transmission en Morse), 1 point à la seconde, 20 à la troisième, 8 à la quatrième, ainsi de suite en recommençant.

    Note : Ce type de codage fut utilisé pendant la Seconde Guerre mondiale par l'armée allemande. La machine Enigma avait été conçue en 1923 par l'ingénieur Arthur Scherbius. Son code fut brisé en 1943 grâce aux travaux d'Alan M. Turing et à la construction des célèbres calculateurs Colossus par l'armée britannique.

    Cryptographie moderne : le système RSA

    Cette méthode a été inventée en 1978 par trois mathématiciens, Rivet, Shamir et Adleman. Elle est originale en ce sens que l'algorithme de chiffrement et la clé sont connus de tous, et cependant une seule personne peut déchiffrer le message.

    Elle repose sur les résultats d'arithmétiques suivants que nous admettrons :

    Théorème :

    Si p et q sont deux nombres premiers distincts, n = pq, h = (p - 1)(q - 1).

    Si e est un entier, e Î ]1, h[, et e premier avec h.

    Alors, il existe un unique entier d  Î ]1, h[ tel que ed º 1 [mod h]

    Corollaire :

    Si b º ad [mod n], alors a º be [mod n]

    Fonctionnement de base du système :

    Alice, choisit deux nombres premiers p et q, calcule leur produit n = pq, calcul h = (p - 1)(q - 1) et choisit un entier e Î ]1, h[ et premier avec h.

    Puis elle rend publique, dans un annuaire, l'information (Alice : n, e).

    1) Comment Bob envoie-t-il un message à Alice ?

    Alice à choisi p = 13, q = 17 et e = 5, elle communique alors dans l'annuaire ses deux clés publiques n = pq = 221 et e = 5.

    Bob veut envoyer à Alice le message "JE T'AIME"

    Il l'écrit d'abord sous la forme (10, 5, 0, 20, 27, 1, 9, 13, 5), en utilisant la position des lettres dans l'alphabet (A est la 1ère lettre, ...) et en posant 0 correspondant à l'espace et 27 à l'apostrophe.

    Puis Bob élève chaque nombre de la liste à la puissance e = 5 et en prend le reste dans la division par n = 221.

    Message initial                                    Message crypté

    (10, 5, 0, 20, 27, 1, 9, 13, 5)     Þ     (108, 31, 0, 141, 40, 1, 42, 13, 31)

    Bob transmet alors son "message" crypté à Alice.

    2) Comment Alice déchiffre-t-elle le message de Bob ?

    Alice, qui est la seule à connaître p et q, calcule le nombre d  Î ]1, h[ tel que ed º 1 [mod h]. Ici h = 192 et d = 77.

    Alice élève alors chaque nombre du message crypté à la puissance d = 77,  en prend le reste dans la division par n = 221 et reconstitue le texte original, grâce au théorème énoncé plus haut et à son corollaire.

    Message crypté                                    Message initial

    (108, 31, 0, 141, 40, 1, 42, 13, 31)     Þ     (10, 5, 0, 20, 27, 1, 9, 13, 5)

    Alice retrouve ainsi le message "JE T'AIME" transmis par Bob.

    Quelle sera sa réaction ?

    Sûreté du système RSA :

    Pour crypter en RSA, on utilise les nombres e et n, qui sont les clés publiques du destinataire du message crypté, sans connaître p et q (seul le destinataire les connaît).

    Pour déchiffrer le message, le destinataire calcule d, étant le seul à connaître p et q donc h, et reconstitue le message initial.

    Pour décrypter un message il est donc indispensable de retrouver p et q connaissant n et e. Or si pour des nombres premiers p et q de quelques dizaines de chiffres il est facile de décomposer n, l'affaire relève de la gageure pour des nombres premiers d'un millions de chiffres.

    Ainsi RSA est-il considéré comme un "système de sécurité absolu" pourvu qu'on utilise des "grands" nombres premiers.

    La course à la sécurité passe dès lors par la course aux nombres premiers et on comprend que les armées, les banques et autres grands utilisateurs du système RSA ait besoin de nombres premiers démesurés.

    En 1993 le plus grand nombre premier connu était 2756 839 - 1 qui s'écrit avec 227832 chiffres.

    En 1997 le plus grand nombre premier connu était 22 976 221 - 1.

    Vous pouvez consulter le site officiel des "records" de grands nombres premiers en cliquant sur ce lien : Site des records de nombres premiers.


    votre commentaire


    Suivre le flux RSS des articles de cette rubrique
    Suivre le flux RSS des commentaires de cette rubrique