18976_1.jpg

La Cryptologie

basic-cryptology.jpg

Presentation

Afin de pouvoir gouverner, les dirigeants du monde entier ont dû trouver un moyen de cacher efficacement leurs ordres transmis par message et cela depuis des millénaires. C’est, à la base, pour cela que fut créée la science du secret, la cryptologie. Nous sommes deux étudiants en 3ème année de licence MIASHS (Mathématique et Informatique appliquées aux Sciences Humaines et Sociales) qui avons choisi de traiter ce sujet dans le cadre de notre TER (Travaux Encadrés de Recherches). La cryptologie regroupe deux disciplines, la cryptographie qui permet de protéger des messages et la cryptanalyse qui permet d’analyser les messages protégés.

Il existe un éternel combat dans lequel s’affronte le camps des concepteurs de code et le camp des briseurs de code. Nous vous expliquerons où en est ce combat et comment nous en sommes arrivé là.

Nous prendrons l’exemple de la carte à paiement sans contact, un sujet actuel, en vous expliquant son fonctionnement, ses intérêts et ses défauts.

Enfin nous vous proposerons de réfléchir et d’expérimenter un peu tout ce que vous aurez appris en vous permettant de coder vos propres messages et d’essayer d’en décoder.

Bonne lecture!

Histoire du code

La cryptographie peut être divisée en deux branches, la transposition et la substitution. La transposition consiste à redistribuer les lettres du message que l’on veut coder. Par exemple la transposition dite « en dents de scie » consiste à écrire le message que l’on veut codé sur deux lignes, la première ligne correspondant aux lettres impairs du message et la deuxième ligne correspondant au lettres pairs du message. Il ne reste plus ensuite qu’à écrire la deuxième ligne à la suite de la première.


1

Par convention on écrit le message clair en minuscules et le message codé en majuscules. Cela permet d’éviter des erreurs lors du décodage.

La transposition fut utilisée par les spartiates au Vème siècle avant JC afin de transmettre des informations militaires. Ces informations étaient codées grâce à une scytale, un bâton en bois autour duquel était enroulée une bande de cuir ou de parchemin. L’expéditeur écrit son message sur la bande enroulée autour de la scytale ce qui donne un message totalement incompréhensible une fois la bande déroulée. Le destinataire n’a plus qu’à ré-enrouler la bande autour de sa propre scytale de même diamètre que celle de l’expéditeur afin de lire le message.


2

La substitution consiste à apparier les lettres de l’alphabet au hasard et de substituer ensuite dans le message que l’on veut chiffrer la nouvelle lettre de la paire à celle du message. César utilisait un codage par substitution qui consistait simplement à décaler les lettres de trois lettres.


3

Cette méthode de substitution devient célèbre sous le nom de chiffre de César. Le terme chiffre est uniquement utilisé dans le cadre du codage par substitution. La différence entre ces deux méthodes de cryptographie est que la transposition conserve l’identité des lettres mais change leur position alors que la substitution change l’identité des lettres mais garde leur position.

Chaque chiffre est caractérisé par une clef. Dans le cas du chiffe de César par exemple, la clef correspond à l’alphabet chiffré utilisé pour chiffrer le texte clair. Un message est chiffré ou déchiffré grâce à un algorithme. L’algorithme est précisé grâce à la clef. Afin de déchiffré un message, nous avons besoin de l’algorithme et de la clef. Théoriquement si une personne intercepte le message et n’a en sa possession que l’un ou l’autre, elle sera dans l’incapacité de déchiffrer le message. L’importance de la clef par rapport à l’algorithme est un principe de base de la cryptographie établi par Auguste Kerckhoffs, un linguiste hollandais en 1883 : « La sécurité d’un système de cryptement ne doit pas dépendre de la préservation du secret de l’algorithme. La sécurité ne repose que sur le secret de la clef. » Pour qu’un chiffre soit bien sécurisé, il doit avoir un nombre de clefs envisageables suffisant. En effet si le nombre de clefs envisageable est insuffisant, l’intercepteur a juste à tester les quelques clefs envisageables et tombera assez vite sur la bonne.

Parallèlement à la cryptographie fut développé la cryptanalyse, science permettant d’analyser des messages codés afin d’en comprendre le vrai sens, par les Arabes. Ils remarquèrent entre autre que certaines lettres étaient plus utilisées que d’autre. Ainsi quand ils se trouvaient face à un message codé, s’ils pensaient que celui ci était chiffré par substitution, ils avaient juste à calculer les fréquences d’apparitions des lettres chiffrés et à les associer à la fréquence d’apparition des lettres clairs.


4

Si le texte chiffré est assez court, les fréquences ne sont pas suffisamment significatives, et les cryptanalystes utilisent également des méthodes de logique en essayant de deviner certains mots du texte et en faisant plusieurs tests.

Le chiffrage par substitution classique pouvant être facilement analyser pour peu que l’on connaisse la langue dans lequel le texte avait été chiffré, il fallut trouver une méthode de codage plus sécurisée.

C’est ainsi que fut créé le chiffre de Vigenère en 1460, une méthode de codage par substitution permettant de crypter un texte à part d’un ou de plusieurs mots clefs.


5

La clef de ce texte chiffré est le mot « clef » . On chiffre le texte à partir du carré de Vigenère :


6

La première colonne correspond à l’alphabet clair et la première ligne à l’alphabet relatif à la clef. Ainsi pour chiffrer un texte avec la clef « clef », on applique un décalage relatif à la lettre « c » toutes les 4 lettres en partant de la première, un décalage relatif à la lettre « l » toutes les 4 lettres en partant de la deuxième, un décalage relatif à la lettre « e » toutes les 4 lettres en partant de la troisième et enfin un décalage relatif à la lettre « f » toutes les 4 lettres en partant de la quatrième.

Plus la clef est longue et est composée de plusieurs mots, plus le déchiffrage devient compliqué voir impossible. Cependant cette méthode montrait plusieurs faiblesses :

La clef ne devait être connu que de l’expéditeur et du destinataire, la clef ne devait donc pas être interceptée

La clef ne devait pas pouvoir être trop facile à deviner, par exemple le mot « clef » est une très mauvaise clef

Il est toujours possible de pouvoir deviner certains mots en fonction de leur emplacement ou de leur longueur

img/12.jpg

Arithmetique modulaire

Si aujourd'hui la cryptologie et les mathématiques semblent indisociables cela n'a pas toujours été le cas.

En effet les théories mathématiques qui ont permis de mettre en place la cryptologie moderne n'ont été défini qu'à partir du XIXème siècle.

Un exemple marquant serait le chiffre de vigenére qui fut inventé au XIVème s'est vu en premier reposer sur un système de grille pour le coder/décoder. Aujourd'hui les outils mathématiques qui sont à notre disposition nous permettent de le voir d'une toute autre manière, c'est sur ces outils que nous allons nous concentrer dans cette seconde partie.

Les congruances:

Si les origines des congruances remontent à la Grèce Antique, on associe sa définition formelle en 1801, date de la publication "Disquisitiones arithmeticae"" de Carl Friedrich Gauss. Ce livre de théories des nombres pose les fondements de l'arithmétique modulaire avec notamment les anneaux ℤ/nℤ qui comme nous le verrons permettront de faire le lien entre les mathématiques et les cryptogrammes.

gauss3.jpg
Définition:

Deux entiers a et b sont dit congruents modulo n ( avec n ∈ ℤ et et n ≥ 2) si leur différence est divisible par n (il existe un entier k tel que a – b = kn)

Mais une définition équivalente qui nous interessera davantage pour la compréhension de ce dernier est que le reste de la division euclidienne de a par n est égale à celui de la division de b par n.

Chose importante, la congruance implique une relation équivalence de part sa réflexivité (a ≡ a [n] ), sa symétrie (a ≡ b [n] ⇔ b ≡ a [n]) et sa transitivité (si a ≡ b [n] et b ≡ c [n] alors a ≡ c [n] ).

Ainsi 8 ≡ 2 [3] signifie premièrement que 8 - 2 est divisible par 3 mais surtout que 8 et 2 appartiennent à la même classe d'équivalence.

De cette façon on peux associer chaque entier (infinité) à un nombre n fini de classe dans ce que l'on appelera l'anneau ℤ/nℤ avec n un entier positif supérieur ou égal à 2.

Dans l'exemple précèdent nous nous trouverons donc dans l'anneau ℤ/3ℤ qui contient 3 classes d'équivalences. Celle dont le reste de la division euclidiene par 3 est 0, celle dont le reste est 1 et celle dont le reste est 2 (le reste étant toujours inférieur à n, on a donc n classes, 3 en l'occurence). Les nombres de ces classes peuvent respectivement s'écrire sous la forme 3k, 3k+1 et 3k+2 avec k ∈ ℕ.

Par convention nous représenterons toujours les classes d'équivalence de ℤ/nℤ par l'unique nombre de cette classe compris entre 0 et n-1 (dans de rares calculs nous utiliserons cependant l'unique nombre de la classe entre -n+1 et 0) car étant tous équivalents autant représenter la classe par son plus petit élément positif.

Un comportement important des congruances est que pour tout a, b on a a + b ≡ a [n] + b[n]

img/modular-arithmetic24.png

exemple: on peut calculer 5 + 2 modulo 3 de 2 façon 5 + 2 ≡ 7 ≡ 1 [3] mais aussi 5 ≡ 2 [3] ce qui donne 5 + 2 ≡ 2 + 2 ≡ 4 ≡ 1 [3] Une fois de plus on voit que tout élément des classes d'équivalences sont semblables

Il en est de même avec les soustractions multiplications, puissances,...

img/modular-arithmetic54.png

Mais alors à quoi bon peuvent servir les congruances et classes d'équivalences pour coder/décoder un message?

Et bien tout simplement en associant chaque élément de l'alphabet de notre cryptogramme à une classe d'équivalence dans un anneau ℤ/nℤ avec n le nombre de d'éléments de l'alphabet.

Il suffira alors d'utiliser une application (transposition, fonction linéaire...) pour coder le message et son inverse pour le décoder.

Malheureusement cela n'est pas si simple que ça, en effet il faut tout d'abord que cette application soit bijective dans ℤ/nℤ. Et comme nous allons le voir, cela ne dépend pas uniquement de la fonction mais surtout de l'anneau ℤ/nℤ.

img/patate_reciproque.jpg

Prenons l'exemple de ℤ/6ℤ, dans la table de multiplication ci-dessous on remarque les multiples de 2, 3 et 4 ne sont jamais égaux a 1. Or la définition de l'inverse u d'un nombre a est: a*u ≡ 1 [n] Par ce fait ils ne sont pas inversibles.

img/ring-map118.png
Théorème:

La classe de x est inversible dans ℤ/nℤ si et seulement si x est premier avec n.

Ce qui implique que tout élément non nul de ℤ/nℤ est inversible si et seulement si n est un nombre premier. On le notera ℤ/pℤ. On dit que ℤ/pℤ est un corps fini.

Maintenant que nous nous trouvons dans ℤ/pℤ il est simple de coder à l'aide d'un chiffrement affine ou chiffrement de hill (à l'aide d'une matrice inversible). Et pour le décodage il suffira de faire l'application inverse (calcul de la matrice inverse pour le chiffrement de hill).

On définit φ(n) comme étant le nombre d'éléments inversibles de ℤ/nℤ. Cette fonction est appelée l'indicatrice d'euler. Dans le cas ou p premier on a donc φ(p) = n-1 (0 étant le seul élément non inversible). Si n et m sont égaux ou premiers entre eux on a φ(n*m) = φ(n)*φ(m).

Petit théorème de Fermat:

Si p premier et a non divisible par p alors ap–1 ≡ 1  [p]

img/11903-004-3101EDBE.jpg

rappel:

lemme d'euclide: Si un nombre premier p divise le produit de deux nombres entiers b et c, alors p divise b ou c.

Lemme de Gauss : si un nombre entier a divise le produit de deux autres nombres entiers b et c, et si a est premier avec b, alors a divise c.

Une démonstration astucieuse:

On suppose que a n'est pas divisible par p et soit N =  a.2a.3a.….(p – 1)a notons rk le reste de la division euclidienne de ka par p, pour tout entier k de 1 à p – 1. N = 1.2. … .(p – 1).ap–1 = (p – 1)!ap–1. De même on a aussi  N ≡ r1.r2. … .rp–1 [p] Or r1.r2. … .rp–1 = (p – 1)! car (r1, r2, … , rp–1) est une permutation de (1, 2, … , p – 1). En effet, 0 ≤ rk ≤ p – 1 et aucun rk n'est nul, car ℤ/pℤ est un corps. les rk sont distincts deux à deux, car si ri = rj alors (i – j)a est divisible par p (lemme d'Euclide), donc  i – j aussi, donc (comme –p < i – j < p) i = j. On vient de montrer que (p – 1)!ap–1 ≡ (p – 1)! (mod p), autrement dit (p – 1)!(ap–1 – 1) est divisible par p. Par application du lemme d'Euclide, on obtient la conclusion : ap–1 – 1 est divisible par p, équivalent de ap–1 ≡ 1  [p].

Petit rappel du Protocole RSA:

On choisit p et q, deux nombres premiers distincts On calcule leur produit n = pq On calcule l'indicatrice d'Euler et comme p et q premiers on trouve φ(n) = φ(p) . φ(q)= (p - 1)(q -1) On choisit un entier naturel e premier avec φ(n) et strictement inférieur à φ(n), appelé exposant de chiffrement On calcule l'entier naturel d, inverse de e modulo φ(n), et strictement inférieur à φ(n), appelé exposant de déchiffrement 

img/RSA inventeurs.jpg

Pour coder un message il nous suffit alors de connaître e et n: C = Me [n] De même pour déchiffrer il nous suffit de connaître d et n: M = Cd [n]

Vérifions que l'on a bien Me.d ≡ M [n]

Par le petit théorème de Fermat nous avons Mp-1 ≡ 1 [p] et Mq-1 ≡ 1 [q] Et par construction de d on a e.d ≡ 1 [φ(n)] ≡ 1[(p-1)(q-1)] que l'on peut aussi écrire sous la forme e.d = 1 +k(p-1)(q-1)

Etudions Me.d modulo p et modulo q: Grâce au petit théorème de Fermat nous avons Me.d ≡ M1+k(p-1)(q-1) ≡ M.(Mp-1)k(q-1) ≡ M.1k(q-1) ≡ M.1 ≡ M [p]

de même:

Me.d ≡ M1+k(p-1)(q-1) ≡ M.(Mq-1)k(p-1) ≡ M.1k(p-1) ≡ M.1 ≡ M [q]

d'où Me.d - M est divisible par p et par q or ces derniers sont premiers entre eux (car premiers) et donc Me.d - M est divisible par q et par p donc par n = p.q. On retombe donc bien sur le message d'origine après ces 2 opérations.

Remerciements

Nous remercions Mademoiselle Ninon Eyrolles et Monsieur Marc Michel Corsini pour nous avoir guidés pendant toute l'année.

Contacts

Pour nous contacter : myriam.giralde@u-bordeaux.fr ou yoann.itier@u-bordeaux.fr