Cryptographie et Nombres Premiers : Comprendre l'Algorithme RSA

La cryptographie, science du secret, englobe la cryptographie — le codage secret d’un message — et la cryptanalyse — le décodage d’un message codé. C’est la technique de communiquer au moyens de messages codés (on dit aussi chiffrés, car ce sont des méthodes numériques qui sont aujourd'hui principalement utilisées), les clés de décodage n'étant (en principe...) connues que des seuls correspondants. C'est un vaste et complexe sujet, très en vogue de nos jours, car si elle fut utilisée naguère par les seuls militaires ou gouvernements, cette "science" nouvelle, on parle aujourd'hui de cryptologie, voit son application dans les problèmes de confidentialité liés aux télécommunications, à la sécurité bancaire, et Aujourd'hui, en particulier avec le développement d'internet, transmettre des informations confidentielles de façon sécurisée est devenu un besoin primordial... Aussi, bien qu'il s'agisse d'une science très ancienne, la cryptologie est toujours d'actualité. Décryptons l'un des algorithmes les plus utilisés, l'algorithme RSA, basé sur une propriété simple des nombres premiers. Le chiffrement RSA (nommé par les initiales de ses trois inventeurs) est un algorithme de cryptographie asymétrique, très utilisé dans le commerce électronique, et plus généralement pour échanger des données confidentielles sur Internet. Cet algorithme a été décrit en 1977 par Ronald Rivest, Adi Shamir et Leonard Adleman. RSA a été breveté1 par le Massachusetts Institute of Technology (MIT) en 1983 aux États-Unis. Le brevet a expiré le 21 septembre 2000. Le protocole RSA est fondé sur un résultat d’arithmétique dont la démonstration peut prendre un peu de temps dépendant du message. Rappel: - un nombre n est premier s’il est divisible que par lui-même et par 1. - p et q sont dits premiers entre eux si le plus grand entier divisant à la fois p et q est 1. De ce théorème, on déduit alors le protocole RSA pour le codage.