Arithmétique et cryptographie

L’arithmétique est l’étude des nombres, de leurs propriétés et de leurs relations. Lorsque l’on s’intéresse à la cryptographie, outil de codage et de décodage d’information, on utilise l’arithmétique restreinte aux entiers relatifs, et notamment aux notions de divisibilité et de congruence.

MATHÉMATIQUES PROPRIÉTÉ ET RELATION DES NOMBRES

L’arithmétique est l’étude des nombres, de leurs propriétés et de leurs relations. Ces nombres peuvent être les entiers naturels, les entiers relatifs, les nombres rationnels, réels ou encore complexes. On s’intéresse ici aux propriétés des entiers relatifs (appelés ici « entiers »). La première notion fondamentale de l’arithmétique dans Z est la divisibilité. On dit qu’un nombre a divise un nombre b si, et seulement si, il existe un entier k tel que b = ak. Un grand nombre de propriétés sont attachées à cette notion de divisibilité, comme le fait que a divise a, que 1 divise tous les entiers, que la divisibilité est transitive ou encore que tout entier admet un nombre fini de diviseurs. On peut ensuite définir la division euclidienne. Soient a un entier et b un entier naturel non nul, alors il existe deux entiers q (appelé « quotient ») et r (appelé « reste ») tels que a = bq + r avec r compris entre 0 et b. C’est la division que nous effectuons depuis l’école primaire, plus rigoureusement écrite.

LA NOTION DE CONGRUENCE

Un des éléments fondamentaux (et très utilisés en cryptographie) de l’arithmétique dans l’ensemble des entiers relatifs est la notion de congruence. On considère deux entiers a et b et un entier naturel non nul n. On dit alors que a et b sont « congrus » modulo n si, et seulement si, n divise (b – a). Un lien très fort existe entre la congruence et la division euclidienne. En effet, avec les données précédentes, un théorème nous dit que a et b sont congrus modulo n si, et seulement si, ils ont le même reste dans la division euclidienne par n. Un autre outil de l’arithmétique très utile en cryptographie est le théorème de Bézout. Pour l’énoncer, il faut se souvenir du concept de plus grand commun diviseur (PGCD) et d’entiers premiers entre eux (le PGCD de ces deux entiers vaut 1). Ce théorème affirme que deux entiers a et b non nuis sont premiers entre eux s’il existe deux entiers u et v tels que au + bv = 1. Ce couple d’entiers (u ; v) sera un outil essentiel des méthodes de cryptographie.

CODER ET DÉCODER

La cryptographie consiste à chiffrer (coder) puis à déchiffrer (décoder) un texte. Pour le codage, il est nécessaire de transformer le texte en une séquence de nombres, le décodage étant l’opération réciproque qui permet de retrouver le texte source à partir de la séquence chiffrée. La cryptographie a un triple but: d’une part, elle assure la confidentialité (empêcher l’accès aux informations), d’autre part elle permet l’authentification (signature électronique), et enfin elle assure l’intégrité du texte (vérification que le texte n’a pas subi d’altérations). Cette science a toujours existé; elle a été essentiellement utilisée par les militaires (comme pour le déchiffrage des codes de la machine Enigma pendant la Seconde Guerre mondiale) et les diplomates. Aujourd’hui, le champ de la cryptographie s’est largement élargi et a trouvé un regain d’actualité avec les problèmes posés par la sécurité des transactions bancaires, des transmissions de fichiers et de données sous forme électronique.

LE CODAGE MONOGRAPHIQUE

Les systèmes de codage les plus simples sont appelés « monographiques » : chaque lettre de l’alphabet y est transformée en une autre par substitution. Jules César utilisait déjà ce système à l’aide de permutations circulaires – c’est-à-dire que A devient D, B devient E, et ainsi de suite jusqu’à Z, qui devient C. En termes de congruence, si P est une lettre de l’alphabet et C son équivalent codé, on a alors C et P congrus à 3 modulo 26 (décalage de 3 et 26 lettres). On obtient avec cette formule la table des correspondances, et on peut alors décoder n’importe quel message. Si l’exemple précédent est assez simple, il est possible de compliquer les choses en considérant des codages par transformations affines. Dans ce cas, avec les mêmes notations que précédemment, on utilisera la formule C et aP congrus à b modulo 26, avec a et b deux entiers. Cependant, on ne peut pas choisir a et b indifféremment: en réalité, il est nécessaire qu’ils soient premiers entre eux.

LE CODAGE PAR TRANSFORMATIONS AFFINES

Un grand nombre de systèmes de codage ont vu le jour, comme le codage polygraphique ou par blocs, ou encore le codage par exponentiation arithmétique (basé sur des calculs d’exponentielles modulo un nombre premier). Le plus utilisé est le système RSA. Il constitue une véritable révolution dans le monde de la cryptographie, car c’est un système de codage à clés publiques; seules les clés de décodage sont gardées secrètes. Le système est tel que le temps nécessaire pour découvrir la clé de décodage est astronomique, irréaliste en pratique. Le principe est le suivant: on découpe le texte en blocs et on fait correspondre à chaque lettre son équivalent numérique, puis on procède à une exponentiation avec e modulo n (le couple (e ; n) étant la clé publique de codage). Le principe du décodage utilise le théorème de Bézout, à la condition d’avoir la clé de décodage. En effet, le système est fait de telle manière que décoder sans la clé demanderait des milliards d’années.

À RETENIR

L’arithmétique est la science des nombres. La cryptographie (codage et décodage d’information) utilise des outils de l’arithmétique des entiers relatifs, comme la notion de congruence ou le théorème de Bézout. Il existe un grand nombre de systèmes de codage, comme les systèmes monographiques, polygraphiques (ou par blocs), ou encore par exponentiation arithmétique. C’est sur ce dernier principe qu’est construit le système RSA, l’un des plus puissants à ce jour.