Cryptologie : la division et son reste

Article rédigé par M. Franck GACON

La cryptologie se partage entre la cryptographie, qui inclut l’étude des mécanismes destinés à assurer la confidentialité, et la cryptanalyse, dont le but est de déjouer les protections ainsi mises en place. Comment transmettre des données personnelles sans risquer qu’elles soient lues par un tiers indésirable ? Comment continuer à préserver la confidentialité des échanges alors que se multiplient les réseaux de communication ? Longtemps réservée aux usages diplomatiques et militaires, la cryptologie répond aujourd’hui aux besoins du marché et constitue un domaine scientifique en pleine activité. Elle intervient dans de multiples applications et représente l’élément essentiel de la sécurisation du commerce électronique et du réseau Internet.

Il nous arrive à tous, quotidiennement de voir apparaître lors de connexions internet le message « transaction sécurisée certificat SSL ». Un certificat SSL se compose d’une clé publique et d’une clé privée. La clé publique est utilisée pour le cryptage des informations et la clé privée est utilisée pour les décrypter.

Mais quelle diablerie permet de transmettre un message codé avec une clé connue de tous, et de le décoder avec une clé différente connue du destinataire seul ? Notre but ici n’est pas de décrire le protocole SSL, ni même d’effleurer le sujet mais simplement d’illustrer un procédé montrant comment une telle magie est possible grâce à une opération bien simple en apparence : la division euclidienne.

Notre but ici n’est pas de décrire le protocole SSL, ni même d’effleurer le sujet mais simplement d’illustrer un procédé montrant comment une telle magie est possible grâce à une opération bien simple en apparence : la division euclidienne.

Comment coder simplement ?

En informatique, les données sont stockées et transmises en base 2, ce qui signifie qu’un message est constitué d’une succession de 0 et de 1. Pour coder cette succession de chiffres, elle est tout d’abord découpée en groupes de longueur n, et chaque groupe est multiplié «scalairement» par n nombres déterminés. Choisissons par exemple 4 nombres: 26, 65, 23, 46. Cette suite sera notre « suite codante ». Prenons un message binaire découpé par blocs de 4 : 1101-1100-0010 Multiplier «scalairement» le premier groupe, 1101, par notre suite codante, c’est calculer la somme: S1 = 1 x 26 + 1 x 65 + 0 x 23 + 1 x 46 = 137. De même pour les groupes suivants. S2 = 1 x 26 + 1 x 65 + 0 x 23 + 0 x 46 = 91, S3 = 0 x 26 + 0 x 65 + 1 x 23 + 0 x 46 = 23. Le message transmis devient donc 137-91-23

De l’impossibilité de décoder

Pour décoder le message, il faut remonter de cette série de nombres à la succession de 0 et de 1 : passer de la somme S1 = 137 à 1101 ; de S2 = 91 à 1100, et ainsi de suite. Il est nécessaire pour cela de connaître les 4 nombres (26, 65, 23, 46) puis il suffit de faire tous les essais possibles de somme des 4 nombres; ce qui est facile, il n’y a ici que 2 4 = 16 sommes possibles. Cependant, dans la pratique, on ne retient pas seulement 4 nombres, mais plusieurs centaines. Alors, faire tous les essais possibles devient une tâche impossible, même pour un ordinateur très puissant; ainsi, avec 100 nombres, les sommes possibles sont de 2 100 soit environ 10 30 . A l’heure où l’on évoque des capacités de calcul en téraflops pour les ordinateurs (1000 milliards d’opérations par seconde), il faudrait, sans algorithme approprié, de nombreuses années de calcul.

Il est donc impossible de remonter de la suite de nombres qui forment le message codé à la succession de 0 et de 1 pour revenir au message en clair, ceci même pour quelqu’un connaissant la suite des nombres codants.

Conséquence très importante: il n’est plus nécessaire de préserver le secret du code. Le futur destinataire envoie donc son code à ceux qui lui expédieront des messages, sans avoir à prendre de précautions particulières. Il peut même mettre son code dans des petites annonces de journaux. Ses correspondants lui envoient leurs messages codés sans plus de précautions, et ceci en toute sécurité. Personne ne pourra décoder les messages.

Certes, mais à quoi tout cela servira-t-il puisque, semble-t-il, le destinataire ne pourra pas, lui non plus, décoder le message?

Tout part de la remarque suivante: le décodage serait très facile si la suite de nombres codant était telle que chaque nombre soit plus grand que la somme des précédents. Ainsi, au lieu d’avoir 26, 65, 23, 46, si les nombres étaient 2, 5, 8 et 16, le décodage deviendrait trivial.

En effet, multiplions scalairement cette suite par quatre nombres p, q, r, s, égaux chacun à 0 ou à 1. On obtient: S = 2p + 5q + 8r + 16s. Si la somme est inférieure à 16, s est bien sûr forcément égal à 0. Mais, ce qui est plus intéressant, la réciproque est vraie. Si s est égal à 0, alors 2p + 5q + 8r est au maximum égal à 2 + 5 + 8, et donc par construction de la suite, inférieur à 16. La méthode de décodage s’en déduit très facilement. Si l’on part d’une somme S supérieure ou égale au nombre le plus grand de la suite, ce nombre est associé à un 1. On le retranche alors de la somme S et on continue le processus. Si la somme S est inférieure au nombre le plus grand de la suite, on en déduit que ce nombre est associé à un 0, et on continue le processus avec la somme S. Dans ce cadre, pour une suite codante de 100 nombres, le nombre d’opérations n’est plus de 2 100 mais seulement de l’ordre d’une centaine.

Comment garder le secret ?

En fait, c’est le destinataire qui initie le mécanisme.

Le destinataire garde secret la suite (2, 5, 8, 16), ainsi que trois nombres qu’il aura soigneusement choisis. Dans cet exemple nous retiendrons 13, 25 et 81 (Ces trois nombres ont une particularité, ils sont tels que le produit des deux premiers, divisé par le troisième, donne pour reste 1, en effet 13 x 25 = 325 = 4 x 81 + 1). Le destinataire ne communique ces nombres à personne. Ils les utilisent pour générer la suite codante (26, 65, 23, 46) comme expliqué dans le tableau ci-après.

Le destinataire n’envoie aux expéditeurs que la suite codante et ce, de manière publique, puisque nous avons vu la difficulté de décoder lorsque la suite codante atteint une certaine taille (100 nombres). Pour procéder au codage, l’expéditeur du message n’a besoin que de cette suite de chiffres.

Ainsi, chaque partie dispose d’une clé différente :

• • – l’expéditeur du message utilise une suite codante fournie par le destinataire
  • – le destinataire du message conserve dans sa manche une suite secrète (2, 5, 8, 16) ainsi que les nombres 13, 25 et 81 qu’il a judicieusement choisi

Le tableau ci-contre explicite le processus de codage et de décodage avec sa démonstration mathématique.