La cryptographie

 

 

 

Cette activité propose une présentation simplifiée à objectif pédagogique du système de cryptage RSA. Ce système est utilisé actuellement pour sécuriser les transactions par Internet. Le niveau est celui de terminale S spécialité mathématiques et les notions abordées recouvrent une grande partie du programme d’arithmétique de ce niveau. L’activité est donc à envisager en fin d'année. Les travaux à effectuer nécessitent un ordinateur équipé d’un tableur. Le tableur choisi, ici, est Lotus 123 mais les quelques fonctions ou lignes de code utilisées sont aisément transportables à tout autre tableur. Pour Excel, il suffit de remplacer le @ par un = en début d'instruction et de supprimer les @ situés à l'intérieur des instructions. Le travail peut être effectué en salle informatique mais aussi dans le cadre d’un devoir à la maison. L'activité est présentée ici au format htm pour la visualiser. Les quelques imperfections de présentation ( alignements par exemple) sont absentes de la version papier téléchargeable.

 

Pour télécharger le fichier zippé (85 KO) au format Word, cliquez sur activiteRSA

 

 


Sommaire

 

 

I La cryptographie affine

 

a.       Présentation de la méthode

b.       Construction d’un crypteur ( feuille A du fichier tableur )

c.       Un crypteur défaillant

d.       Construction d’un décrypteur ( feuille B du fichier tableur)

 

II Le système RSA

 

a.       Présentation de la méthode

b.       Un exemple de codage ( feuille C du fichier tableur )

c.       Le petit théorème de Fermat ( feuille D du fichier tableur )

d.       Construction d’un crypteur RSA ( feuille E du fichier tableur )

e.       Construction du décrypteur (simplifié) RSA ( feuille F du fichier tableur )

f.         Le découpage ( feuille G du fichier tableur )

g.       La signature électronique ( feuille H du fichier tableur )

III Quelques ajouts théoriques

 

Auteur: Philippe Scatton et André Chopplet

Professeurs de mathématiques

Lycée Clemenceau Reims

Contact par email pour tout commentaire

 

 


I La cryptographie affine

 

Les cadres grisés sont à compléter manuellement. Le travail à effectuer nécessite d'ouvrir un certain nombre de feuilles dans un fichier tableur unique que vous créerez en début d'activité et qui s’étoffera au fur et à mesure du déroulement de l’activité.

 

 

a/ Présentation

 

 


On associe à chaque lettre de l’alphabet numérotée par le nombre x de l’intervalle [ 0 ; 25 ], le nombre y défini par y = ax + b a et b sont deux nombres connus uniquement de l'émetteur et du récepteur.

Le couple ( a b ) s’appelle la clé du codage. La quatrième ligne du tableau est obtenue en prenant le modulo 26 de la troisième ligne, ceci afin de n’obtenir que des nombres de l’intervalle [ 0 ; 25 ]

 

Ainsi, avec a = 5 et b = 8, on obtient :

 

 

A

B

C

D

E

F

G

H

I

J

K

L

M

Numérotation  x

0

1

2

3

4

5

6

7

8

9

10

11

12

y = ax + b

8

13

18

23

28

33

38

43

48

53

58

63

68

y modulo 26

8

13

18

23

2

7

12

17

22

1

6

11

16

Lettre obtenue

I

N

S

X

C

H

M

R

W

B

G

L

Q

 

 

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Numérotation  x

13

14

15

16

17

18

19

20

21

22

23

24

25

y = ax + b

73

78

83

88

93

98

103

108

113

118

123

128

133

y modulo 26

21

0

5

10

15

20

25

4

9

14

19

24

3

Lettre obtenue

V

A

F

K

P

U

Z

E

J

O

T

Y

D

 

 

b/ Création d’un « crypteur » affine

 

 


Ouvrez LOTUS 123, créez un nouveau fichier principal qui vous suivra durant cette activité. Effectuez les manipulations suivantes dans la feuille A :

 

 

 

 

Codez le message suivant: «CESAR UTILISE LE CODAGE AFFINE »

 

c/ Un alphabet incomplet

 

 


Modifiez le crypteur précédent avec la clé ( 10 ; 6 ) puis avec la clé ( 12 ; 7 )

 

Quelle remarque peut-on faire ? Conjecturez la condition nécessaire sur le nombre a pour définir un crypteur correct?

Preuve de l'assertion précédente :

 

Supposons que  c'est-à-dire que l'on a deux lettres identiques dans l'alphabet codé,

On peut alors écrire que alors

et que  à condition que a soit premier avec 26 (d'aprés le théorème de Gauss).

On en conclue alors que x = x  car x et x' sont deux entiers naturels inférieurs à 26.

 

Si a n’est pas premier avec 26, que se passe-t-il?

 

Le réflexe est alors de définir le pgcd noté d de a et 26  et les entiers k et k’ tels que 26=kd et tel que a = k’d.

 

On rappelle que les deux entiers k et k’ sont premiers entre eux.

 

En s’aidant d'un crypteur incorrect, donnez des exemples de couples de nombres distincts qui donnent la même lettre codée et émettez une conjecture.

 

 

 

 

Plus généralement, si , alors  et on peut trouver un entier p tel que.

On peut donc écrire que soit . Comme k et k’ sont premiers entre eux, le théorème de Gauss permet d'affirmer que x - x' est divisible par k. Avec la clé ( 12 ; 7 ), k est égal à 13. Vérifiez sur votre crypteur que deux nombres congrus modulo 13 donnent la même lettre codée..

 

Il est inutile de décoder toutes les lettres de l’alphabet pour décoder un message. Soit la clé ( 19 ; 3 ), comment décrypter la lettre M ?

 

M est repéré par le nombre 12. On cherche donc x tel que 19x + 3 soit congru à 12 modulo 26. Montrer qu’alors  x vérifie l’équation diophantienne 26k-19x=17 ?

 

 

 

Résoudre cette équation par la méthode habituelle :

Solution particulière de 26k-19x=1 par l’algorithme d’Euclide

Solution particulière de 26k-19x=17 et solution générale  par le théorème de Gauss

 

26 = 19x1+7

19 = ...........

 

 

 

 

 

 

Sachant que x appartient à l'intervalle [ 0 ; 25 ], donnez la valeur de x.                                                                                                                                      

 

 

Vérifiez avec votre crypteur.

 

d/ Création d’un « décrypteur »

 

 


Ouvrez une nouvelle feuille B dans votre fichier LOTUS123 puis entrez en D1 le nombre 5 et en F1, le nombre 8. Il s'agit de la clé. Il nous faut maintenant construire la clé de décodage.

 

Pour cela, Cliquez sur CREATION puis FONCTION@ et indiquez le nom "calculclededecodage" et recopiez le code de programmation suivant dans l'éditeur de scripts présent à l'écran.

Function calculclededecodage ( valeur As Integer)

           

            u = 0

            j = 0

            r = 0

            Do

                        u = u + 1

                        j = valeur * u

                        r = j Mod 26

            Loop While r <> 1

            calculclededecodage = u

           

End Function

 

Interprétation du code:

 

u, j et r sont des ...

 

On les initialise à 0

 

 

On incrémente u

 

Quels sont les nombres j ?

Quel est le nombre r ?

 

Pourquoi s'arrête-t-on dès que r = 1?

 

 

 

Fermez l'éditeur de scripts.

 

Le nombre u trouvé vérifie  k est un entier naturel. C'est le premier nombre de la clé de décodage. Pourquoi?

 

Pour coder, on procède par un "codage affine" du type ax+b.  Ici, on a utilisé la fonction définie par

Pour décoder, nous allons résoudre l'équation d'inconnue x : (attention, il s'agit bien d'une équation avec le signe de congruence ).

 

Pour cela, nous isolons x en multipliant les deux membres de la congruence par u.

 

On obtient alors    mais  donc .

 

On montre ainsi que le décodage est également effectué par une fonction affine définie par

 

  u est bien le nombre celui découvert par la fonction calculclededecodage et où v est égal à -8u.

 

Revenons au tableur:

 

 

Recopiez les précédentes formules jusqu'à la colonne Z par exemple.

 

Test de notre décrypteur :

 

Entrez le message suivant dans la ligne 6, une lettre dans chaque cellule.

 

 

ICVXCDJAEUXCQIWVQWXW

  

 

 


1 Le système RSA

 

 

a/ Présentation

 

 

 


Plusieurs inconvénients pour le système précédent (abandonné depuis longtemps bien entendu) :

 

 

 

 

 

Voici le principe du système RSA (le plus utilisé actuellement) qui propose d’utiliser deux types de clés, l’une publique et l’autre privée. Schématiquement, le principe est très différent du codage précédent car la personne qui veut envoyer un message codé, va demander au destinataire une clé (que chacun peut connaître) et grâce à laquelle il va coder son message. Mais seul le destinataire pourra décoder le dit message car lui seul sait comment la clé a été fabriquée.

 

Le message a est codé en le message b par la formule :


et le décodage par :

d et e sont des nombres qui seront déterminés plus bas..

 

La clé publique connue de tous est formée des nombres n = pq et d’un nombre e premier avec (  p -1 )( q -1 ) (explication toujours plus bas) mais sans connaître les nombres premiers p et q. Chacun peut donc coder a avec les deux nombres n et e mais pour le décodage, il est nécessaire de connaître p et q pour pouvoir calculer le nombre d (calcul toujours plus bas, un peu de patience...) du décodage car il faut avoir la valeur du produit ( p -1 )( q -1 ). Ce nombre d est la clé privée.

 

 

b/ Un exemple de codage

 

 

 


Je choisis la clé publique : n = 247 et e = 35
Pouvez-vous casser le code et retrouver les nombres p et q ?

 

 

 

 

Pouvez-vous coder le nombre 3?

 

Il faut calculer 3^35 modulo 247.

 

Les capacités du tableur ne suffisent pas pour ce calcul. Voici deux propositions pour résoudre ce problème:

 

 

Ouvrez une nouvelle feuille C puis cliquez sur CREATION puis FONCTION@ et indiquez le nom "calculpuissance" et recopiez le code de programmation suivant dans l'éditeur de scripts présent à l'écran.

 

 

Function calculpuissance ( u1 As Integer , u2 As Integer , u3 As Integer )

           

            r=0      

            t=u1    

            n=0

           

            Do

                        n = n + 1

                        r = t Mod u3

                        t = u1*r Mod u3

            Loop While n < u2-1

            calculpuissance = t

 

End Function

Interprétation du code avec u1=3, u2=35 etu3=247

 

On calcule donc 3^35 modulo 247

 

r, n et t sont des entiers

On initialise les r, t et n en remarquant que t est initialisé à la valeur 3

 

On incrémente le compteur n

 

r est le nombre congru à 3 modulo 247

t est le nombre congru à 3^2 modulo 247

et on recommence.

 

On s'arrête-t-on dès que n = 34

 

 

 

Avec la boucle ainsi créée, le tableur calcule toutes les puissances successives de 3 jusqu'à 3^35 mais en utilisant uniquement les nombres congrus à ces puissances d'où un effort de calcul moindre.

 

 

 

Codez ainsi le message suivant: DEMAIN MIDI

 

c/ Le petit théorème de Fermat

 

 

 


Dans la réalité, les nombres premiers choisis sont très grands ce qui rend très difficile la factorisation du nombre n. La clé privée est donc le nombre d  que seul connaît le demandeur du message et qui lui permettra de décoder le texte reçu.

 

Cette méthode de cryptographie est basée sur le petit théorème de Fermat.

 

Ouvrez une nouvelle feuille D

 

 

Petit théorème de Fermat

 

Soit p un nombre premier et a un entier naturel (autre que 0 et 1) non divisible par p, alors ap-1 est congru à 1 modulo p

 

 

 

Conséquence : ap est congru à a modulo p, ce qui nous ramène à notre problème de codage-décodage.

 

d/ Un crypteur RSA

 

 

 


Revenons au système RSA:

 

On appelle a le message qu'Annabelle désire recevoir de Béatrice. Annabelle choisit deux nombres premiers 13 et 19 et calcule le produit 13x19 = 247. puis elle choisit un entier e premier avec (  p -1 )( q -1 ), par exemple 35 qui est premier avec 12x18. Elle dit à Béatrice qu'elle utilise la clé publique ( n , e ) soit ( 247, 35 ) et lui demande de coder son message avec cette clé. Le message codé et envoyé par Béatrice devient b = ae.

 

Ainsi Béatrice code DEMAIN MIDI avec la clé (247, 35) par 165 62 103 0 310 117 103 31 165

 

C'est le message que reçoit Annabelle.

 

On montre, grâce au théorème de Fermat  que ak(p-1)(q-1)+1 est congru à  a  modulo n pour tout a et k.

Il reste à montrer que l’on peut écrire le nombre k(p-1)(q-1)+1 sous la forme ed d'où


 


ce qui fait que en élevant à la puissance d le message b envoyé par Béatrice, Annabelle le décodera.

 

Pourquoi peut-on dire qu’il existe deux entiers d et k tels que ed - k(p-1)(q-1) = 1. Conclure.

 

Application pratique : Création d'un crypteur RSA (à vous de le construire en suivant les démarches précédentes)

 

Ouvrez une nouvelle feuille E. J’utilise la clé publique suivante : codage RSA, n = 391 et e = 5. Vous pouvez utiliser les premières ligne du crypteur précédent qui permettent de coder les lettres à l'aide d'un entier compris entre 0 et 25.

 

Vous désirez m’envoyer le message : BONJOUR

 

Codez ce message à l'aide de votre crypteur. Qu'obtenez-vous?

 

 

 

Pour décoder ce message, j’ai besoin des deux nombres premiers p et q dont le produit est 391. Ici, il n’est pas difficile de découvrir qu’il s’agit de 17 et 23.

 

Je cherche donc le ( ou plutôt un ) nombre d tel que ed - k(p-1)(q-1) = 1 à savoir 5d - 352k = 1.

A vous de jouer (dans la suite, c’est l’ordinateur qui donnera la réponse…) puisqu’il s’agit d’une équation diophantienne.

 

Solution particulière de 5d - 352x = 1 par l’algorithme d’Euclide

Solution générale  par le théorème de Gauss

 

352 = 5x70+2

5 = ...........

Inutile, ici

 

Je choisis d =    .

 

J'utilise la fonction créée précédemment @calculpuissance(...;...;...)

 

 

 

 

 

e/ Construction d’un décrypteur simplifié RSA

 

 

 


Pour décrypter un message, il faut détenir la clé privée d c'est-à-dire connaître le produit (p-1)(q-1), ce qui demande de connaître p et q  et donc de savoir factoriser l'entier n. Il n'était pas très compliqué de factoriser 391 mais que pouvez-vous proposer pour le nombre 90 338 904  079* ?

Actuellement, les nombres utilisés sont de l'ordre de 768 bits ce qui signifie que ces nombres s'écrivent dans le système binaire à l'aide de 768 chiffres 0 ou 1.

 

Par exemple, le nombre suivant écrit sur 25 bits

 

1  0  0  1  0  1  0  1  0  1  0  0  0  1  0  1  0  1  0  1  1  0  1  1  1

vaut dans le système décimal :

 

1x224+0x223+0x222+1x221+0x220+1x219+0x218+......+1x21+1x20

 

soit le nombre 19 565 239 qui comporte déjà 8 chiffres.

 

Combien un nombre N écrit sur 768 bits dans le système binaire comporte-il de chiffres dans le système décimal ?

 

On peut écrire l'inégalité suivante :1x2768 "d N < 1x2768 + 1x2767 + ... + 1x20

soit, en appliquant la formule connue des sommes de séries géométriques :

 

2768"d N < 2769 - 1

En prenant le logarithme décimal de chacun des membres de la double inégalité, on obtient :

 

768log(2) "d logN < log(2769 - 1)

et

231 "d logN < 232

que l'on peut écrire sous la forme :

10231"d N < 10232

ce qui prouve que N possède 231 chiffres dans son écriture. Inutile donc de tenter de factoriser un tel nombre par de simples calculs.

 

Ouvrez une nouvelle feuille F dans votre fichier LOTUS et nommez-la décrypteur RSA.

Attention ! ici, la factorisation de n sera indiquée par vous-mêmes à l’ordinateur. Il n’est, bien entendu, pas dans notre propos de casser le code RSA, ce qui est illégal et, de toute façon, impossible à l’heure actuelle en raison de la taille des nombres utilisés.

 

Choisissez une largeur de 5 pour les colonnes

 

 

Function calculded ( H1 As Integer, J1 As Integer)

           

            u = 0

            j = 0

            r = 0

            Do

                        u = u + 1

                        j = 1+H1 * u

                        r = j Mod J1

                       

            Loop While r <> 0

           

            d= j \ J1

            calculded = d

           

End Function

Interprétation du code:

 

 

 

 

On incrémente u

 

Quels sont les nombres j ?

Quel est le nombre r ?

 

Pourquoi s'arrête-t-on dès que r = 0?

 

Qu’est le nombre d ?

 

 

Un test : B1=391 D1=17 F1=23 I1=5 donnent L1=141

 

 

 

32

350

242

156

242

234

32

242

0

56

 

 

f/ Le découpage

 

 

 


Dans cet exemple simplifié , les répétitions de lettres sont évidentes et nous retrouvons le problème évoqué dans le début du deuxième paragraphe et représenté par le diagramme des fréquences d’apparition des lettres de l’alphabet.

Dans la réalité, le système RSA procède par découpage du message en blocs. Voici une explication du système employé :

 

Nous allons utiliser la clé publique n = 5767 qui est le produit de 73 par 79 puis nous choisissons le nombre e égal à 9317. Ce nombre est premier avec 72x78.

 

Le message à transmettre est : "demain mardi 8 h 30"

Nous découpons le message en blocs de deux caractères pour obtenir :

 

Dd

em

ai

nD

ma

rd

iD

8D

hD

30

 

Le symbole D désigne l’espace.

Nous utilisons un alphabet qui comporte 37 signes à savoir les 26 lettres de l’alphabet habituel numérotées de 0 pour le "a" au 25 pour le "z", les dix chiffres numérotés de 26 pour le "0" à 35 pour le "9", 36 pour l’espace. Nous obtenons ainsi un système numérique comme le système décimal ou binaire qui comporte 37 symboles. C’est le système de base 37.  

Ainsi, le bigramme "em" est chiffré "décimalement" par 4x371 +12x370 soit 160.

Le nombre 160 est codé par la clé publique sous la forme 1609317 modulo 5767 et on obtient alors 3718.

Revenons au système de base 37 en divisant successivement 3718 par 37 pour découvrir les puissance de 37 cachées dans ce nombre :

Nous obtenons 3718=37x100+18=37x(37x2+26)+18=2x37²+26x37+18 et donc le trigramme obtenu est c0s et, ceci, de manière unique ( ! ).

Pour le bigramme "ma", on a 12x371 +0x370 soit 444et 4449317 modulo 5767 donne 1337.

Or 1337=37x36+5 d’où le trigramme aDf.

Remarquez alors qu’il n’est pas évident de repérer la répétition de la lettre "m" codée dans ces deux trigrammes. Ainsi "emma" est codé "c0saDf"

Défi : créez une feuille G qui permette de coder le message précédent.

 

g/ La signature électronique

 

 

 


Un des intérêts du système RSA est qu'il permet de signer le message envoyé autrement dit lorsque vous recevrez le message de Béatrice, vous serez sûr que celui-ci provient bien de Béatrice. Voici la procédure mise en place :

 

Béatrice reçoit un message d’Annabelle. Est-ce bien un message d’Annabelle ?

 

Annabelle code son message à l’aide de sa clé privée d qu’elle seule connaît puis une seconde fois à l’aide de la clé publique e’ que lui a fourni Béatrice. Béatrice reçoit le message d’Annabelle. Elle décode le message d’abord à l’aide de sa clé privée d’ (ce qui lui assure la confidentialité du message) puis, ensuite,  à l’aide de la clé publique e fournie par Annabelle (ce qui lui assure l’origine du message).

 

Exercice :

Annabelle propose la clé publique ( 5989 ; 625 )

Béatrice propose la clé publique ( 7031 ; 10625 )

Béatrice reçoit le message suivant d’Annabelle :

 

1

5975

3805

942

5975

893

3489

 

Ce message provient-il d’Annabelle ?

Et celui-ci ?

 

2118

4076

2118

6937

6937

0

5652

2118

3805

2118

5316

5054

2118

3805

4823

5544

0

6937

5448

0

3805

3805

0

1

2118

4365

4365

2118

 

 

 

Vous pouvez utiliser la feuille H pour calculer les clés secrètes. On ne tient pas compte, ici, de la difficulté évoquée plus haut de la répétition des lettres.

 

 

 

 

 


1 Ajouts théoriques

 

 

Ainsi w ( 20 ) = 8 car 1, 3, 7, 9, 11, 13, 17 et 19 sont premiers avec 20.

Il est immédiat que w (p ) = p – 1 si p est premier.

Exercice : démontrer que w (pq ) = ( p – 1)( q – 1 ) si p et q sont premiers.