Introduction

Le codage de l'information est un thème qui soulève plusieurs problèmes et qui fait appel à de nombreux domaines: traitement du contenu informationnel, correction des erreurs, cryptage, etc.

Le but de cette note est de présenter une technique de cryptage particulière dite à clé révélée, c'est-à-dire une méthode où l'on peut donner l'algorithme de cryptage, sans permettre à son utilisateur de décrypter des messages utilisant le même procédé. On en voit bien l'utilité : une société X peut proposer à ses clients une façon de crypter les messages (téléphoniques, informatiques, ...) sans que personne (à moins de travaux gigantesques) ne puisse les remettre en clair (sauf ladite société, cela va sans dire). Une des méthodes les plus simples ne fait appel qu'à quelques principes simples d'arithmétique avec des classes de restes.

Ce sera aussi l'occasion de réfléchir aux concepts fondamentaux de mathématiques mis en oeuvre dans des résolutions de problèmes assistées par ordinateur.

Quelques principes

Les opérations div et mod

La notation "a div b" désignera le résultat de la division euclidienne (entière) de a par b. div sera aussi désigné par la suite par FLOOR. Quant à la notation "a mod b", elle désigne le reste de la division de a par b.

Classes de restes

On dit que a et b sont congruents modulo n (notation: a b (mod n)) si a mod n = b mod n. Cela signifie que les divisions de a et b par n ont le même reste.

Exemple: 106 71 (mod 5).

A l'aide de cette relation on peut définir une partition de Z en classes d'équivalence, les classes de restes. Cet ensemble quotient est noté par Z/nZ.

Exemple: Z/4Z = {0, 1, 2, 3} où chaque nombre représente toute une classe. 1 représente {... -7, -3, 1, 5, 9, ... }. Z/nZ est un groupe additif.

L'indicateur d'Euler

Pour un nombre entier n, (n) représente le nombre de nombres premiers avec n (y compris 1) inférieurs à n.

(3) = 2 (les nombres premiers avec 3 inférieurs à 3 sont 1 et 2)
(4) = 2 (les nombres premiers avec 4 inférieurs à 4 sont 1 et 3)
(5) = 4 (les nombres premiers avec 5 inférieurs à 5 sont 1, 2, 3 et 4)
(6) = 2 (les nombres premiers avec 6 inférieurs à 6 sont 1 et 5)
(p) = p-1 (si p est premier)
(pq) = (p-1)(q-1) (si p et q sont deux nombres premiers)
(10) = 4 (10 = 2*5)

La formule pour (pq) se généralise: (n*m) = (n) * (m) si n et m sont deux nombres premiers entre eux. De plus on a : (p^r) = p^r-1 (p-1).

On peut aussi multiplier deux éléments de Z/nZ. On considère Z/nZ* le groupe des éléments de Z/nZ qui possèdent un inverse, c'est-à-dire des éléments a tels que il existe m avec am = 1 ou am 1 (mod n) ou encore s'il existe a et b tels que am + bn = 1.

Selon le théorème de Bezout, cette dernière relation existe si et seulement si m et n sont premiers entre eux. (n) est donc aussi le nombre d'éléments du groupe multiplicatif Z/nZ* des classes de restes modulo n.

Si a est un élément de Z/nZ* alors: {ax | x Z/nZ*} = Z/nZ*. Par conséquent le produit de tous les membres de chacun de ces deux ensembles sont égaux:

ax x (mod n) donc a⁽ⁿ⁾ x x (mod n) (produit sur x Z/nZ*)

Par conséquent a⁽ⁿ⁾ 1 (mod n) si a et n sont premiers entre eux. Ce résultat est connu sous le nom de théorème d'Euler.

Exemple: a⁴ 1 (mod 10) pour tout nombre a premier avec 10 (3, 7, 9, ...).

Cette formule généralise le 'petit' théorème de Fermat: si p est un nombre premier et a n'est pas divisible par p : a^p-1 1 (mod p).

Exemple: a⁴ 1 (mod 5) pour a non divisible par 5.

Le théorème d'Euler nous dit que si la décomposition de n en facteurs premiers est n = pq, et que si M est premier avec n (ce qui est le cas si M est inférieur à p ou q) on a : M ⁽ⁿ⁾ = M ^(p-1)(q-1) 1 (mod n) ou M ⁽ⁿ⁾ mod n = 1.

Par ailleurs le théorème de Bezout permet de dire que si e est premier avec (n), il existe s tel que es 1 (mod (n)).

Méthode de cryptage

Sur cette base une méthode de cryptage simple peut être construite: (n,e) est la clé publique du système de cryptage (ces nombres sont en principe enfouis dans un programme d'ordinateur); s en est la clé privée qui permet le décryptage !

Le principe de cryptage est le suivant : le message est représenté sous la forme d'un nombre que l'on découpe en tranches inférieures à n. Pour une tranche M, on effectue le calcul suivant : C = M^e mod n. C est le message crypté !

Il paraît qu'il est difficile de retrouver s sans retrouver p et q, ce qui serait en principe possible de réaliser en factorisant n. Mais ce travail (si les nombres premiers p et q sont grands) est quasiment impossible à réaliser dans un temps raisonnable ! Pour décrypter il suffit de faire : C^s mod n. En effet C^s mod n = M^es mod n = M^{(a (n) + 1)} mod n = (M^{a (n)} mod n) (M mod n) = M mod n = M.

On notera que e et s jouent un rôle symétrique. s est la clé privée de la clé publique (n,e). Mais e peut aussi être la clé privée de la clé (n,s).

Exemple réduit

n = 221 (= 13*17); (n) = 12*16 = 192 e = 35 ; s = 11 (on vérifie que e*s 1 (mod 192), puisque 11*35 = 2*192+1)

On prend le 'message' M = 12.

Le message crypté est alors : C = 12³⁵ mod 221 = 181.

Pour accélérer le calcul de C, il suffit de calculer préalablement 12 à la puissance 2ⁱ et réduire mod n au fur et à mesure.

On trouve: 12² = 144, 12⁴ 183 (mod 221), 12⁸  118 (mod 221), 12¹⁶ 1 (mod 221), 12³² 1 (mod 221) et donc 12³⁵ = 12³² * 12² * 12 12*144 = 1728 181 (mod 221).

Décryptage : Il s'opère par le calcul C^s mod n = 181¹¹ mod 221 = 12. Il s'agit bien du message initial. Ce calcul s'effectue après avoir calculé les puissances 2e, 4e et 8e de 181 réduites mod n. Elles valent respectivement: 53, 157, 118.

Un exemple plus compliqué

Voici une clef révélée :

n = 149236969185001063708200481991735656309211386
358857348981088595711743

e = 7719068319927551

Pouvez-vous envoyer des messages ? Saurez-vous décrypter le message

C = 553158717909856679607693767493057799388932
50353091125506297769250292 ?

Problèmes annexes

Signature : Un problème peut exister de savoir si un message envoyé de l'expéditeur A à B provient effectivement de A. Pour cela une technique consiste à introduire une signature au message, codée à l'aide de la clé privée de A, et reconstituée par B à l'aide de la clé publique de A. Le fait de retrouver la signature de A grâce à sa clé publique prouve l'origine de l'émetteur du message. Dans la pratique, on restreint ce travail de cryptage "inverse" à une "empreinte" du message seulement.

Problème de calcul : Cette technique pose le problème du calcul avec de grands nombres. Dans la pratique tous les nombres utilisés p, q, e, s sont de l'ordre de 10²⁰⁰. Se confronter avec des grands nombres augmente les difficultés. La perception globale est plus difficile, les manipulations plus lentes. Par conséquent, il est plus facile de perdre le fil du travail. Les lois ne paraissent plus tout à fait les mêmes ! Cela permet d'imaginer pourquoi les jeunes élèves éprouvent de la peine à résoudre des problèmes avec des 'grands' nombres, alors qu'ils peuvent les maîtriser sur des jeux de nombres plus petits.

L'usage de DERIVE

Outil simple, DERIVE est un programme de moins de 300 kB, qui permet de nombreuses manipulations de mathématique formelle.

En particulier, la façon de réaliser des fonctions est très dynamique. Ainsi que le montre la réalisation de m^e mod n (avec réductions successives).

Principe

Code

PMOD(m,e,n) := IF(e=1,
                  MOD(m,n), 
                  IF(MOD(e,2)=0,
                      PMOD(MOD(m^2,n),e/2,n),
                      MOD(m*PMOD(m,e­1,n),n))) 
          

Le mode programmation incite aussi à réaliser des opérations en un seul "passage". Ainsi, pour trouver les coefficients du théorème de Bezout (a et b tels que an + bm = 1) à l'aide de l'algorithme d'Euclide, on cherche simultanément la suite des restes r_n, celle des quotients q_n et celles des coefficients a_n et b_n.

Plus précisément, en supposant n>m cet algorithme commence par chercher q et r tels que: n = qm + r (division euclidienne). Si r vaut 1 le processus s'arrête et on a n - qm = 1. Sinon on recommence le processus avec m et r.

On pose donc: n = r₀, m = r₁
La formule de récurrence liant r_n est: r_n-1 = q_n+1 r_n + r_n+1

La décomposition de r_n en r₀ et r₁ permet de définir a_n et b_n par: r_n = a_n r₀ + b_n r₁

La relation: r_n+1 = r_n-1 - q_n+1 r_n = (a_n-1 - q_n+1 a_n) r₀ + (b_n-1 - q_n+1 b_n) r₁ donne les valeurs de:

a_n+1 = a_n-1 - q_n+1 a_n

b_{n+1 =} b_n-1 - q_n+1 b_n

Toutes ces informations sont mises sous la forme d'un vecteur :

v_n = [r_n, r_n+1, q_n+1, a_n, a_n+1, b_n, b_n+1]

Avec v₀= [r₀, r₁, *, 1, 0, 0, 1] et

vn+1 = [rn+1, MOD(rn,rn+1), 
        qn+2 := FLOOR(rn,rn+1),  an+1, 
        (an - qn+2 an+1), bn+1, 
        (bn - qn+2 bn+1)]

Utilisé dans Bezout:

BEZOUT(r1,r2,q2,a1,a2,b1,b2) := IF (r2=0, 
        [r1,a1,b1], 
        BEZOUT(r2,MOD(r1,r2),
               q2:=FLOOR(r1,r2),a2,a1­q2*a2,b2,b1­q2*b2) 
                 

Ou, si on se contente de faire des soustractions :

BEZOUTS(r1,r2,a1,a2,b1,b2) := IF (r2=0,
               [r1,a1,b1], 
               IF (r2<=r1, 
          BEZOUTS(r1­r2,r2,a1­a2,a2,b1­b2,b2), 
          BEZOUTS(r2,r1,a2,a1,b2,b1))) 
                 

L'appel: BEZOUTS(100,33,1,0,0,1) donne la solution [1,1,­3]. Ce qui correspond à la décomposition de Bezout: 100 ­ 3*33 = 1. Pour terminer, on laisse le soin au lecteur de méditer ces formules trouvées au hasard des exemples proposés par les créateurs du système DERIVE:

MOD(a,b) := LIM(b/2­b*ATAN(COT(pi*x/b))/pi,x,a,1)

INVERSE(u,x) := ITERATE(u,x,x,­1) (inverse de l'opérateur u selon la variable x)

Pour conclure

Il est intéressant de noter que si une partie de l'informatique numérique se consacre à des algorithmes et a tendance à rejeter ce formulaire classique (la formule de Cramer est un désastre en temps de calcul), les systèmes formels, les systèmes parallèles auraient eux tendance à y faire un recours plus fréquent. Jean Beiner, dans sa présentation de 'comment bien programmer' fait ainsi allusion à la mise de processus sous forme linéaire, en particulier dans les systèmes de dessins assistés par ordinateur.

Références

Robert, A. (1984). Note de la séance du groupe Gonseth du 25 septembre 1984 sur les mathématiques et leur utilisation.

Hellmann (1980). Les mathématiques de la cryptographie à clef révélée. In: Les progrès des mathématiques. Paris: Bibliothèque pour la Science.

Sigrist, F. (1992). Les codes correcteurs d'erreurs. Bulletin no 12, avril 1992. Neuchâtel: Société des enseignants neuchâtelois en Sciences.

solutions :

a:=­1357712980221829 

s:= 26249407544218082069643008889915562472245021647
    354645430602084042983 
a*phi(n)+s*e = 1 
m:=8365768584 
PMOD(m,e,n) = 5531587179098566796076937674930577993
              8893250353091125506297769250292