Un peu de maths (et d’info)

IFT6271--Hiver20142e cours

Louis Salvail

Pourquoi?Nous commençons par étudier les outils cryptographiques nécessaires (mais pas suffisants) pour la mise au point de mécanismes de sécurité performants.

Ces outils sont des constructions mathématiques qui sont facilement représentables sur les ordinateurs.

La sécurité de la plupart des méthodes cryptographiques intéressantes repose sur la difficulté de résoudre certains problèmes mathématiques.

L’informatique théorique permet d’analyser la difficulté algorithmique pour la résolution de ces problèmes mathématiques.

Nombres entiers et premiersLes nombres que nous allons utiliser par la suite

sont des nombres entiers (positifs).

Le nombre entier a est divisible par le nombre entier b si a=kb pour k un autre nombre entier: a/b=k.

Les nombres premiers sont au centre de la plupart des protocoles cryptographiques.

Un nombre entier n est premier s’il n’admet que deux diviseurs distincts : 1 et lui-même.

Tout nombre entier n peut s’écrire de façon unique par un produit de puissances de nombres premiers : n=p1

a1 p2a2 ... pt

at

PGCDLe PGCD entre les entiers a et b est le plus grand commun diviseur de a et b.

k=PGCD(a,b) -> k⋅i=a et k⋅j=b pour i,j des entiers. De plus, il n’existe pas d’entier k’>k, i’ et j’ tels que k’⋅i’=a et k’⋅j’=b.

Exemples:

PGCD(5,25)=5: 5⋅5=25

PGCD(14,35) = 7: 14=2⋅7 et 35=5⋅7,

PGCD(21,55) = 1.

Lorsque les entiers n et m sont tels que PGCD(n,m)=1 on dit alors qu’ils sont relativement premiers.

Arithmétique modulaire

Quelle heure sera-t-il dans 12 heures?

Quelle heure sera-t-il dans 25 heures?

Quelle heure sera-t-il dans 23 heures?

Quelle heure sera-t-il dans 34 heures?

Quelle heure sera-t-il dans n heures, sachant qu’il est t heures?

Rép: n+t mod 12

Un registre d’ordinateur est une horloge avec 2k valeurs possibles pour k=8,16,32,64,...

1236

0

Arithmétique modulaire (II)

L’expression n mod m désigne le reste de la division entière de n par m:

39 mod 5 = 4 -> 39=7*5 + 4,

7 mod 124 = 7 -> 7=0*124 + 7.

Si on ajoute le nombre entier v à un registre d’ordinateur de k bits contenant la valeur initiale n, le registre contiendra alors la valeur :

n+v mod 2k. 0 00 0 1111

k=8

Les valeurs 0,1,2,...,2k-1 peuvent être représentées.

On peut voir les valeurs possibles mod m comme l’ensemble des valeurs Zm = {0,1,2,...,m-1}.

L’addition mod m de deux éléments a et b dans Zm est toujours dans Zm puisque a+b mod m est par définition dans Zm.

De plus, comme l’addition de nombres naturels, chaque élément a∈Zm admet un autre élément b∈Zm tel que :

a+b = 0 mod m.

On peut appeler -a cet élément b.

Exemple : 3+4=0 mod 7 et donc 4=-3 mod 7.

Groupe additif Zm

Multiplication modulaireVoyons le comportement de a⋅b mod m pour

a,b∈Zm :

Z6 -> 1*3=3 mod 6, 2⋅3=0 mod 6, 3⋅3=3 mod 6, 4*3=0 mod 6, 5⋅3=3 mod 6.

Z5 -> 1⋅3=3 mod 5, 2⋅3=1 mod 5, 3⋅3= 4 mod 5, 3⋅4=2 mod 5.

Z5 a la propriété que pour tout a,b∈Z5 il existe un et un seul k∈Z5 tel que a⋅k=b mod 5. Cette propriété est vérifiée dans Zp pour n’importe quel nombre premier p.

Dit autrement, pour tout a∈Zp, il existe k∈Zp tel que a⋅k=1 mod p. Cet élément k, dénoté a-1, est appelé son inverse.

a⋅k mod pa⋅k mod p induit une induit une permutation de permutation de ZZpp-{0}-{0}

lorsque lorsque kk visite ces visite ces éléments.éléments.

a⋅k mod pa⋅k mod p induit une induit une permutation de permutation de ZZpp-{0}-{0}

lorsque lorsque kk visite ces visite ces éléments.éléments.

Un peu de pratique1579+1580 mod 1581 = ?

1579+2= 0 mod 1581 -> 1579 = -2 mod 1581,

1580+1=0 mod 1581 -> 1580 = -1 mod 1581,

1579+1580 mod 1581=-2-1 mod 1581 = -3 mod 1581 = 1578 mod 1581.

1579⋅1580 mod 1581 = -2⋅-1 = 2 mod 1581.

Voyons un chiffrement dans Z26 (les lettres de l’alphabet) :

La clé secrète est k∈Z26 :

Chiffrement 1 : a∈ Z26 -> a+k mod 26, Déchiffrement?

Chiffrement 2 : a∈ Z26 -> a⋅k mod 26, Déchiffrement?

Supposons que les messages n’ont que 23 lettres différentes et supposons que k∈ Z23. Pouvons-nous déchiffrer le chiffrement 2?

Évaluation des formes modulaires

Lorsque nous additionnons ou multiplions mod m, nous pouvons réduire mod m avant ou après l’opération sans changer le résultat :

(a+b) mod m = [a (mod m) + b (mod m)] (mod m)

(a⋅b) mod m = [ a (mod m) ⋅ b (mod m)] (mod m)

Exemple: Est-ce que le nombre 13456515 est divisible par 3?

La méthode magique dit que 1+3+4+5+6+5+1+5= 30 et puisque 3+0 = 3 est divisible par 3 alors 13456515 est divisible par 3.

Pourquoi?Pourquoi?xx11xx22...x...xtt mod 3 = x mod 3 = x11⋅10⋅10t-1t-1+x+x22⋅10⋅10t-2t-2+ ... +x+ ... +xtt⋅10⋅1000 (mod 3) (mod 3)

= x= x11⋅10⋅10t-1t-1 mod 3+ ... +x mod 3+ ... +xtt⋅10⋅1000 mod 3 mod 3 (mod 3)(mod 3) = x= x11 mod 3+x mod 3+x22 mod 3+... +x mod 3+... +xtt mod 3 mod 3 (mod 3)(mod 3)

Pourquoi?Pourquoi?xx11xx22...x...xtt mod 3 = x mod 3 = x11⋅10⋅10t-1t-1+x+x22⋅10⋅10t-2t-2+ ... +x+ ... +xtt⋅10⋅1000 (mod 3) (mod 3)

= x= x11⋅10⋅10t-1t-1 mod 3+ ... +x mod 3+ ... +xtt⋅10⋅1000 mod 3 mod 3 (mod 3)(mod 3) = x= x11 mod 3+x mod 3+x22 mod 3+... +x mod 3+... +xtt mod 3 mod 3 (mod 3)(mod 3)

1010rr mod 3 = 1 mod 3 = 1 pour pour toute valeur toute valeur rr..

Le groupe multiplicatif Zn*

Zn*={a: PGCD(a,n)=1}, autrement dit Zn* contient tous les nombres inférieurs à n qui sont relativement premiers à n.

Le groupe Zn* est un groupe dans lequel il fait bon multiplier :

a,b∈Zn* -> a⋅b mod n ∈ Zn*,

pour chaque a∈Zn*, il existe a-1∈Zn* tel que a⋅a-1=1 mod n.

On nomme inverse de a cette valeur a-1.

Le chiffrement du message a∈Zn* avec clé k∈Zn*: a⋅k mod n est maintenant déchiffrable.

Étant donné deux nombres a et n, comment trouver leur PGCD(a,n)?

Un des plus vieux algorithmes connus en théorie des nombres permet de le faire rapidement. Il s’agit de l’algorithme d’Euclide...

Une extension de cet algorithme permet aussi, étant donnés a et m, de calculer a-1 t.q. a⋅a-1= 1 mod m.

EuclideNaissance : Grèce, env. -325

Calculer le PGCDL’algorithme d’Euclide calcule

PGCD(a,n), a<n en temps correspondant au nombre de

chiffres dans le représentation décimale de a.

Exponentiation modulaire

Comme nous allons le voir lorsque nous parlerons des systèmes à clefs publiques, l’exponentiation modulaire est une opération très importante.

Tandis qu’il est facile et efficace de calculer y=ax mod n, il est difficile de calculer son inverse (c.-à-d. calculer x étant donnés y, a et n).

Souvenons-nous que ax mod n = a⋅a⋅...⋅a mod n.

x fois!

Exponentiation rapideRappelons-nous l’évaluation des formes modulaires:

312 mod 7 = (32 mod 7)6 = (2 mod 7)6 mod 7= (23 mod 7)2 mod 7= 12 mod 7 = 1 mod 7.

Attention: ax mod m ≠ ax mod m mod m, par exemple nous avons 25 mod 3 mod 3 = 1, mais 25 mod 3 = 2!

Pour l’exponentiation rapide, nous utilisons la méthode suivante :Pour l’exponentiation rapide, nous utilisons la méthode suivante :

aa2929 = a⋅a = a⋅a2828 = a⋅(a = a⋅(a1414))22=a⋅((a=a⋅((a77))22))22=...=a⋅((a⋅(a⋅a=...=a⋅((a⋅(a⋅a22))22))22))22

comparé àcomparé à

aa2929=a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a=a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a

Pour l’exponentiation rapide, nous utilisons la méthode suivante :Pour l’exponentiation rapide, nous utilisons la méthode suivante :

aa2929 = a⋅a = a⋅a2828 = a⋅(a = a⋅(a1414))22=a⋅((a=a⋅((a77))22))22=...=a⋅((a⋅(a⋅a=...=a⋅((a⋅(a⋅a22))22))22))22

comparé àcomparé à

aa2929=a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a=a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a⋅a

7 multiplications7 multiplications

28 multiplications28 multiplications

Il s’agit du groupe multiplicatif ZN*= { a |

PGCD(a,N)=1 } où N=pq pour p et q premiers.

La fonction φ(N) = |ZN*| = (p-1)(q-1) est le nombre

d’éléments dans ZN*.

Z15*={1,2,4,7,8,11,13,14}.

Euler a montré que (sa généralisation du théorème de Fermat), pour tout a et N tels que PGCD(a,N)=1,

aφ(N) mod N = 1.

Chaque élément a∈ZN* admet un inverse a-1∈ZN

*:

a⋅a-1 mod N = 1. (une conséquence d’Euler)

Le groupe RSA

aa-1-1= a= aφ(N)-1φ(N)-1 mod N mod N

Logarithmes discretsLe logarithme discret est en quelque sorte l’inverse de l’exponentiation modulaire :

Étant donné (y,a,n), trouver x tel que ax = y (mod n).

La valeur a est souvent appelée la base du logarithme.

Exemples :

logarithme en base 2 de 3 (mod 13): 21=2,22=4,23=8,24=3... Réponse : 4.

logarithme en base 3 de 4 (mod 13): 31=3,32=9,33=1,34=3⋅33=3,35=32 ⋅33=9,...! Réponse : aucun.

En général il est (supposé) difficile de calculer les logarithmes discrets... ça demande beaucoup, beaucoup de multiplications!

Arithmétique sur des bitsLes ordinateurs fonctionnant avec une représentation des nombres en binaire, les opérations sur des registres de bits sont très efficaces.

C’est pourquoi la plupart des systèmes de chiffrement efficaces sont définis par des opérations sur des registres de bits dont la taille est constante.

L’arithmétique des ordinateurs est basée sur Z2={0,1} :

l’addition : a,b∈Z2, a⊕b = a+b mod 2,

la multiplication : a,b∈Z2, a⋅b=a∧b = a⋅b mod 2.

Arithmétique sur des registres de bits

Soient a=a1,a2,...,ak et b=b1,b2,...,bk des registres de k bits (c.-à-d. ai,bj∈Z2 pour tout 1≤i,j≤k). Nous définissons :

a⊕b := a1⊕b1, a2⊕ b2,..., ak⊕bk

Nous définissons Bk comme étant l’ensemble des chaînes de k bits.

L’addition dans Bk est semblable à celle dans Z2k

mais est plus facile (efficace) à réaliser, car nous n’avons pas à nous préoccuper des retenues.

Problèmes difficilesCertains problèmes mathématiques sont réputés difficiles à résoudre sur un ordinateur.

C’est-à-dire qu’aucun algorithme efficace n’est connu à ce jour pour les résoudre.

Ceci n’exclut pas qu’un algorithme efficace puisse être trouvé.

On dit d’un algorithme qu’il est efficace si le nombre d’étapes de calcul t(n) nécessaires pour traiter une entrée de n bits de long, est tel que t(n)<poly(n) pour un polynôme poly(n), pourvu que n soit suffisamment grand.

Retour sur l’exponentiation

Exp_iterative(a,x,n)Exp_iterative(a,x,n)y=a;y=a;pour i=1 a (x-1) fairepour i=1 a (x-1) fairey=a*y mod ny=a*y mod n

fin_pourfin_pourretourne yretourne y

Exp_rapide(a,x,n)Exp_rapide(a,x,n)r=1r=1Tant que x <> 0 faireTant que x <> 0 faireSi (x mod 2)=1 alorsSi (x mod 2)=1 alorsr = r*a mod nr = r*a mod nx=x-1x=x-1

a=a*a mod na=a*a mod nx=x/2x=x/2

retourne rretourne r

Si x est long de t chiffres, alors la boucle Pour sera

exécutée jusqu’à 10t fois. De plus, multiplier a⋅y n’est pas

gratuit!

Si x est long de t chiffres, alors la boucle Pour sera

exécutée jusqu’à 10t fois. De plus, multiplier a⋅y n’est pas

gratuit!

calcul de ax (mod n)

Si x est long de t chiffres, alors la boucle Tant que

sera exécutée jusqu’à lg(10)⋅t fois avec 2

multiplications à chaque fois.

Si x est long de t chiffres, alors la boucle Tant que

sera exécutée jusqu’à lg(10)⋅t fois avec 2

multiplications à chaque fois.

Des problèmes de calcul modulaire faciles

Addition a+b mod m.

Multiplication a*b mod m.

Exponentiation ab mod m.

Trouver le PGCD(a,b) de deux nombres entiers a et b. Par l’algorithme d’Euclide.

Étant donné a et m, trouver a-1 tel que a⋅a-

1=1 mod m lorsque a∈Z*m (Euclide modifié).

Des problèmes de calcul modulaire faciles (II)

Vérifier qu’un nombre N est premier,

Test probabiliste très performant (Rabin-Miller)

Tirer un nombre premier p aléatoire de k>0 bits.

Tirer un nombre Q aléatoire de k bits,

Vérifier si Q est premier (Rabin-Miller),

Si c’est le cas, alors retourner Q,

Sinon, recommencer...

Il y a environ Il y a environ x/ln(x) nombres x/ln(x) nombres

premiers entre 0..x premiers entre 0..x

Des problèmes de calcul modulaire supposés

difficilesLe problème de factorisation : Étant donné un entier N, donner ses facteurs premiers.

Étant donné N=pq, trouver φ(N)=(p-1)(q-1).

Le problème RSA: Étant donnés e et N=pq pour p et q premiers inconnus, trouver d tel que e⋅d=1 mod φ(N).

Le problème de Diffie-Hellman : Étant donnés g et p premiers, gx mod p, gy mod p trouver gxy mod p.

supposé difficile si p=2q+1, q premier, et supposé difficile si p=2q+1, q premier, et si g=h2 mod p pour h un générateur.si g=h2 mod p pour h un générateur.

supposé difficile si p=2q+1, q premier, et supposé difficile si p=2q+1, q premier, et si g=h2 mod p pour h un générateur.si g=h2 mod p pour h un générateur.

Principes qui régissent la sécurité des systèmes

modernesLes cryptosystèmes modernes ont leur sécurité exprimée en ces termes :

« À moins que l’adversaire ne passe un temps

déraisonnable à calculer, le système X est sûr. »

En fait, la sécurité de ces systèmes est habituellement exprimée en des termes plus faibles :

« En supposant que le problème Y ne peut être

résolu en temps raisonnable, le système X est sûr. »

Les chiffres modernes pratiques à clé secrète ont une sécurité ad hoc. Le problème Y sous-jacent n’est pas bien défini.

Ceci serait sûr en Ceci serait sûr en pratique!pratique!

Ceci est sûr en pratique que Ceci est sûr en pratique que si Y était difficilesi Y était difficile

RSARSA est un problème proche du problème de factorisation.

Le problème de factorisation est à l’étude depuis longtemps.

Il y a près de 90 ans (1919), les Français Pierre et Eugène Carissan construisaient une machine à factoriser appelée machine à congruences.

Elle pouvait factoriser des nombres de moins de 13 chiffres décimaux en 18 minutes.

En 2005, la factorisation du problème RSA de 200 chiffres a été réussie (20 000 $):

Question ouverte pour 212 chiffres ($30 000)

L’Américain L’Américain Lehmer en Lehmer en inventa une inventa une

aussi en aussi en 1926!1926!

L’Américain L’Américain Lehmer en Lehmer en inventa une inventa une

aussi en aussi en 1926!1926!

La machine de Lehmer!La machine de Lehmer!

Nous allons maintenant voir comment fonctionne les chiffres à clé secrète modernes.

Nous verrons les principes de construction importants.

Nous en verrons deux qui sont utilisés aujourd’hui : DES et AES.