Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Sécurité informatique Université Kasdi Merbah Ouargla Département Mathématique

Sécurité informatique Université Kasdi Merbah Ouargla Département Mathématique et informatique Crypto II : Rappels mathématiques Master informatique industrielle Mars 2013 Master informatique industrielle Sécurité informatique 1 Rappels mathématiques 1. Quelques pré-requis mathématiques – Divisibilité et primalité – PGCD et Algorithmes d’Euclide 2. Arithmétique modulaire – Addition modulaire dans Zn – Multiplication modulaire dans Zn 3. Inversion modulaire – Inversion modulaire dans Zn – Calcul de l‘inverse modulaire 4. Ordre de et Fonction d’Euler 5. Exponentiation modulaire dans Zn 6. Multiplication/factorisation : Cryptographie RSA – Fonction à sens unique – Chiffrement RSA – exemple – Mise en œuvre de RSA 2 Master informatique industrielle Sécurité informatique 2 1- Quelques pré-requis mathématiques I Master informatique industrielle Sécurité informatique 3 • La divisibilité propriétés : • Division euclidienne 1- Quelques pré-requis mathématiques II Master informatique industrielle Sécurité informatique 4 • PGCD : le Plus Grand Commun Diviseur Propriétés : et Primalité : • Algorithme d’Euclide Tant que b # 0 faire r a mod b a b b r Fin tant que retourner a Exemple : pgcd(42,30)=6 (42,30)(30,12) (30,12)(12,6) (12,6) ( 6,0) Complexité : O((logn)2) ou O((loga)2) 1- Quelques pré-requis mathématiques III Master informatique industrielle Sécurité informatique 5 • Algorithme d’Euclide étendu Complexité : O((logn)2) ou O((loga)2) 1. Si b= 0 alors da, x1,y0 2. x21, x10,y20,y11 Tant que b > 0 faire q [a/b] d a mod b (ou d a - b.q) x x2 - q.x1 yy2 -q.y1 x2x1 , x1x y2 y1 , y1y a b, bd Fin tant que d a, x x2 , y y2 3. retourner (d,x,y) 2 - Arithmétique modulaire I Master informatique industrielle Sécurité informatique 6 Addition modulaire : Z7 2 + 4 = 6 4 + 5 = 9 = 7 + 2 = 2 mod 7 3 + 4 = 7 = 0 mod 7 … Soustraction modulaire : Z7 4 – 2 = 2 mod 7 1 – 5 = -4 = 7 – 4 = 3 mod 7 (Zn , +) forme un groupe commutatif d’ordre n + 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5 2 - Arithmétique modulaire II Master informatique industrielle Sécurité informatique 7 Multiplication modulaire : Z7 3 x 5 = 5 + 5 + 5 = 10 + 5 = 3 + 5 = 8 = 7 + 1 = 1 mod 7 3 x 5 = 15 = 2 x 7 + 1 = 1 mod 7 6 x 4 = 24 = 3 x 7 + 3 = 3 mod 7 … (Zn , +, x ) forme un anneau commutatif : Élément inversible : a est inversible si Congruence modulaire (relation d’équivalence) X 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1 3 – Inversion modulaire I Master informatique industrielle Sécurité informatique 8 Notation : b=1/a mod n ou mieux b=a-1 mod n 1-1 = 1 mod 7 2-1 = 4 mod 7 3-1 = 5 mod 7 4-1 = 2 mod 7 5-1 = 3 mod 7 6-1 = 6 mod 7 Tous les éléments sont inversibles • L’ensemble des élément inversibles modulo n, noté Forme un groupe commutatif X 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1 3 – Inversion modulaire II Master informatique industrielle Sécurité informatique 9 Division modulaire dans Z7 INVERSION MODULAIRE DANS Z6 1-1 = 1 mod 6 5-1 = 5 mod 6 4-1 = ?? mod 6 Les inverses de 2,3,4 ne sont pas définis modulo 6 X 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 2 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1 X 1 5 1 1 5 5 5 1 3 – Inversion modulaire III Master informatique industrielle Sécurité informatique 10 A retenir : deux cas différents 1. n est premier : (Zn, +,x) est un corps Tous les éléments de sont inversibles  2. n n’est pas premier : (Zn, +,x) est un anneau Seuls les éléments de sont inversibles  3 – Calcul de l’inverse modulaire Master informatique industrielle Sécurité informatique 11 On utilise les coefficients de Bezout (application dans algorithme d’Euclide étendu): Calcul pratique (voir exercice n°2 TD n° 1): 4 – Ordre de et fonction d’Euler I Master informatique industrielle Sécurité informatique 12 Lorsque n est premier, tous les éléments de sont premiers avec n Dans le cas général ce nombre est donné par la fonction d’EULER Fonction d’Euler Pour tout entier n , Φ(n) désigne l’ordre de c.-à-d. le nombre d’entiers de 1 à n-1 qui sont premiers avec n. Par convention : 4 – Ordre de et fonction d’Euler II Master informatique industrielle Sécurité informatique 13  Si n est de la forme La formule générale : si n est un produit de facteurs premiers 4 – Ordre de et fonction d’Euler III Master informatique industrielle Sécurité informatique 14 Si pgcd(a,n) = 1 alors  Théorème d’Euler (cas général): Exemple : • Dans Z26, ϕ(n)= ϕ(26)=(13-1)(2-1)=12 312 = 1 mod 26 , 512 = 1 mod 26, 712 = 1 mod 26, … 5 – Exponentiation modulaire Master informatique industrielle Sécurité informatique 15 Calculer Règle n° 1 : dans une exponentiation modulaire (modulo n) les exposants doivent être pris modulo Φ(n) Soit Alors On a définit : Règle n° 2 : effectuer des réductions modulaires au fur et à mesure Exemple : x=11 = (1011)2 = 8+2+1= 23+21+20 a. Bits forts - faibles : on calcule successivement b. Bits faibles-forts : on calcule successivement 6 – Multiplication/factorisation – Fonction à sens unique Master informatique industrielle Sécurité informatique 16 Pour une relation y=f(x), calculer y est facile mais trouver x est difficile En mathématiques : la multiplication / factorisation par des nombres premiers  Soit p et q 2 nombres premiers, n=p.q est facile à calculer  En revanche n=p.q trouver (p,q) est difficile La multiplication/factorisation est un problème à sens unique. Meilleur algorithme connu (NFS- Number Field Sieve) Chiffrement – RSA Master informatique industrielle Sécurité informatique 17 RSA - Exemple Master informatique industrielle Sécurité informatique 18 Mise en œuvre de RSA Master informatique industrielle Sécurité informatique 19 Difficultés pratiques Master informatique industrielle Sécurité informatique 20 • Primalité : Trouver des grands nombres premiers (≈ 512bits) – plus grand nombre factorisé environ 200 chiffres – n ≈ 1024bits ≈ 300 chiffres – Exemple d’algorithmes de primalité : algorithme de Wilson, petit théorème de Fermat, algorithme de Miller Rabin,… Exercice RSA 1. Déchiffrer le message reçu chiffré avec la clé (e=11, n=35) 2. Chiffrer le message avec la clé publique (e=7, n=55). Calculer p, q, et d et déchiffrer uploads/Science et Technologie/ math-crypto 1 .pdf