Cours Sécurité Réseau la Cryptographie
Cours de Cryptographie
(version préliminaire 2005/2006)
Daniel Barsky
février 2006
Résumé
Le but de ce cours est une introduction à la cryptographie moderne utilisée dans la transmission et le stockage sécurisé de données. L’accent mis sur les principes et les outils mathématiques utilisés (arithmétique, algèbre, algorithmique, complexité, probabilité, théorie de l’information,..), ainsi que sur les protocoles.
Les problèmes informatiques, les produits et les normes sont décrits dans
des cours plus appliqués (réseaux, sécurité réseaux, )
Table des Matières
1 Introduction 5
1.1 Qu’est ce que la cryptographie . . . . . . . . . . . . . . . . . 6
1.2 Qualités d’un cryptosystème . . . . . . . . . . . . . . . . . . . 7
2 Historique 9
2.1 Codes à répertoire . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Codes de permutation ou de transposition . . . . . . . . . . . 10
2.3 Codes de substitution . . . . . . . . . . . . . . . . . . . . . . 12
2.3.1 Cryptanalyse des codes de César . . . . . . . . . . . . . . 13
2.4 Le code de Vigénère . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Chiffrement de Hill . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 Commentaires historiques . . . . . . . . . . . . . . . . . . . . 15
3 Quelques méthodes de codage 17
3.1 Chiffrement en chaˆ?ne . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Codes à confidentialité parfaite . . . . . . . . . . . . . . . . . 17
3.3 Registres à décalage . . . . . . . . . . . . . . . . . . . . . . . 18
3.3.1 Régistres à décalages . . . . . . . . . . . . . . . . . . . . 19
3.4 Lutte contre le brouillage . . . . . . . . . . . . . . . . . . . . 20
4 Sécurité d’un cryptosystème 22
4.1 Différentes notions de sécurité . . . . . . . . . . . . . . . . . . 23
5 Les codes modernes 24
5.1 Objectifs des codes actuels . . . . . . . . . . . . . . . . . . . . 25
5.2 Les familles de codes modernes . . . . . . . . . . . . . . . . . 26
5.3 Codes symétriques . . . . . . . . . . . . . . . . . . . . . . . . 26
5.4 Codes asymétriques . . . . . . . . . . . . . . . . . . . . . . . 27
5.5 Les échanges de clefs . . . . . . . . . . . . . . . . . . . . . . . 28
5.5.1 Protocole d’échange de clefs . . . . . . . . . . . . . . . . 29
2
TABLE DES MATIERES` 3
6 Applications de la cryptographie 30
6.1 Quel cryptosystème choisir . . . . . . . . . . . . . . . . . . . 31
6.2 Quelques utilisations de la cryptographie . . . . . . . . . . . . 31
6.3 Quelles mathématiques pour la cryptographie . . . . . . . . . 32
7 Codes à clefs secrètes 34
7.1 Description de DES . . . . . . . . . . . . . . . . . . . . . . . 34
7.1.1 Quelques apects techniques de DES . . . . . . . . . . . . 35
7.2 Description d’AES . . . . . . . . . . . . . . . . . . . . . . . . 38
7.2.1 Quelques apects techniques d’AES . . . . . . . . . . . . . 40
7.3 Infrastructure des systèmes à clef secrète . . . . . . . . . . . . 44
8 Codes à clefs publiques 46
8.1 Principe des codes à clef publique . . . . . . . . . . . . . . . . 46
8.1.1 Fonctions à sens unique . . . . . . . . . . . . . . . . . . 46
8.2 Le système RSA . . . . . . . . . . . . . . . . . . . . . . . . . 47
8.2.1 Description du cryptosystème RSA . . . . . . . . . . . . 47
8.2.2 Protocole d’envoi d’un message en RSA . . . . . . . . . . 48
8.2.3 Protocole de signature RSA . . . . . . . . . . . . . . . . 49
8.2.4 Exemple académique de codes RSA . . . . . . . . . . . . 50
8.2.5 Exemple de code RSA . . . . . . . . . . . . . . . . . . . 52
8.2.6 Sécurité du système RSA . . . . . . . . . . . . . . . . . 54
8.3 Le cryptosystème El Gamal . . . . . . . . . . . . . . . . . . . 55
8.3.1 Description du cryptosystème El Gamal . . . . . . . . . . 55
8.3.2 Signature El Gamal . . . . . . . . . . . . . . . . . . . . 56
8.3.3 Sécurité du système EL Gamal . . . . . . . . . . . . . . . 58
8.3.4 Exemple académique de code El Gamal . . . . . . . . . . 58
8.4 Infrastructure des systèmes à clef publique . . . . . . . . . . . 60
9 Fonctions de Hachage 63
9.1 Construction des fonctions de hachage . . . . . . . . . . . . . 64
9.1.1 Attaques des anniversaires . . . . . . . . . . . . . . . . . 65
9.1.2 Exemple académique de fonction de hachage . . . . . . . . 66
9.1.3 Fonction de hachage standard . . . . . . . . . . . . . . . 66
10 Quelques protocoles cryptographiques 68
10.1 Protocoles de signature . . . . . . . . . . . . . . . . . . . . . 68
10.1.1 Protocole de signature à clef privée . . . . . . . . . . . . 68
10.1.2 Protocole de signature à clef publique . . . . . . . . . . . 69
10.2 Protocoles de datation . . . . . . . . . . . . . . . . . . . . . . 70
TABLE DES MATIERES`
10.2.1 Protocole de datation . . . . . . . . . . . . . . . . . . . 71
10.3 Signature avec fonction de hachage . . . . . . . . . . . . . . . 71
10.4 Fonction de hachage et mot de passe . . . . . . . . . . . . . . 72
10.5 Preuve sans transfert de connaissance . . . . . . . . . . . . . 73
10.5.1 Preuve sans transfert de connaissances . . . . . . . . . . . 74
10.5.2 Transfert inconscient . . . . . . . . . . . . . . . . . . . . 75
11 Rappels Mathématiques 77
11.1 Théorie de l’information . . . . . . . . . . . . . . . . . . . . . 77
11.1.1 Rappels de probabilités discrètes . . . . . . . . . . . . . . 77
11.1.2 Confidentialité parfaite . . . . . . . . . . . . . . . . . . . 78
11.1.3 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . 80
11.2 Théorie de la complexité . . . . . . . . . . . . . . . . . . . . . 81
11.2.1 Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . 82
11.2.2 Complexité algorithmique . . . . . . . . . . . . . . . . . 83
11.2.3 Algorithmes polynomiaux . . . . . . . . . . . . . . . . . 84
11.3 Rappels d’arithmétique . . . . . . . . . . . . . . . . . . . . . 86
11.3.1 La division euclidienne . . . . . . . . . . . . . . . . . . . 86
11.3.2 Plus Grand Commun Diviseur . . . . . . . . . . . . . . . 88
11.3.3 Algorithme du PGCD . . . . . . . . . . . . . . . . . . . 89
11.3.4 Les Congruences . . . . . . . . . . . . . . . . . . . . . . 92
11.4 Tests de primalité . . . . . . . . . . . . . . . . . . . . . . . . 100
11.5 Méthode de factorisation . . . . . . . . . . . . . . . . . . . . . 102
11.6 Rappels d’algèbre . . . . . . . . . . . . . . . . . . . . . . . . . 104
11.6.1 Anneau des polynômes . . . . . . . . . . . . . . . . . . . 104
11.7 Courbes elliptiques . . . . . . . . . . . . . . . . . . . . . . . . 113
11.7.1 Courbes Elliptiques sur un corps fini . . . . . . . . . . . . 117
Bibliographie 120
Index 121
Chapitre 1
Introduction.
Le but du cours est de donner une introduction à la cryptographie moderne utilisée dans la transmission et le stockage sécurisé de données. Après un rapide historique de la cryptographie on examinera les principaux systèmes cryptographiques actuellement utilisés
• Les codes par flots
– les codes basés sur les registres à décalages
• les codes par blocs
– Les systèmes à clef secrètes ou symétriques: AES avec un rappel sur DES et les systèmes dérivés
– Les systèmes à clefs publiques ou asymétriques: RSA et El Gamal
L’accent sera mis sur les principes et les outils mathématiques utilisés (arithmétique, algèbre, algorithmique, complexité, probabilité, théorie de l’information,..). Néanmoins des protocoles seront décrits et on a ajouté une sensibilisation aux Infrastructure pour les Systèmes à Clef Publique (Public Key Infrastructures) et au systèmes de Management des Clefs Secrètes (Symmetric Keys Management).
La mise en oeuvre d’un cryptosystème à clef publique (public key infrastructure ou PKI) ainsi que celle d’un cryptosystème à clef secrète seront juste évoquées. Les problèmes de mise en oeuvre informatique, les produits et les normes sont décrits dans des cours plus appliqués (réseaux, sécurité réseaux, ).
On emploiera indifféremment les mots cryptographie, chiffrement et même parfois codage.
5
CHAPITRE 1. INTRODUCTION
Ce cours s’est beaucoup inspiré des cours de Fran¸cois Arnaux, [2], JeanLouis Pons, [14], et Guy Robin, [17], ainsi que des livres de Douglas Stinson ,[23], Neal Koblitz, [11], John Daemen et Vincent Rijmen, [6], Benne de Weger, [25] et Gilles Zémor, [27], ainsi que de celui de Simon Singh, [21], pour la partie historique.
1.1 Qu’est ce que la cryptographie.
La cryptographie ou science du secret est un art très ancien, c’est finalement l’art de remplacer un secret encombrant par un secret miniature
La cryptographie est l’art de rendre inintelligible, de crypter, de coder, un message à ceux qui ne sont pas habilités à en prendre connaissance. Le chiffre, le code est le procédé, l’algorithme, qui permet de crypter un message.
La cryptanalyse est l’art pour une personne non habilitée, de décrypter, de décoder, de déchiffrer, un message.
La cryptologie est l’ensemble formé de la cryptographie et de la cryptanalyse.
La cryptologie fait partie d’un ensemble de théories et de techniques liées à la transmission de l’information (théorie des ondes électro-magnétiques, théorie du signal, théorie des codes correcteur d’erreurs, théorie de l’information, théorie de la complexité, ).
Un expéditeur Alice veut envoyer un message à un destinataire Bob en évitant les oreilles indiscrète d’Eve` , et les attaques malveillantes de Martin.
Pour cela Alice se met d’accord avec Bob sur le cryptosystème qu’ils vont utiliser. Ce choix n’a pas besoin d’être secret en vertu du principe de Kerckhoff. Par exemple ils peuvent décider d’utiliser un des systèmes suivants
• un code par blocs (block-cipher) à clef publique ou code asymétrique.
• un code par blocs à clef secrète ou code symétrique.
• un code par flots ou en continu (stream-cipher).
Chacun de ces systèmes dépend d’un ou deux paramètres de taille assez réduite (128 à 2048 bits) appelés la clef de chiffrement et la clé de déchiffrement. Les clefs de chiffrement et de déchiffrement n’ont aucune
1.2. QUALITES D’UN CRYPTOSYST´ EME` 7
raison d’être identiques. Seule la clef de déchiffrement doit impérativement
être secrète.
Pour crypter le messageM Alice le découpe en blocs (xi)1?i?n, de taille 1 pour des codes par flots, de taille 128 à 256 bits pour des codes par blocs comme AES.
Alice transforme chaque bloc xi de texte en clair à l’aide de la fonction de chiffrement, eKC, dépendant d’une clef de chiffrement, KC, en un bloc yi, le texte chiffré.
A L’autre extrémité Bob` déchiffre, décrypte le message codé à l’aide la fonction de déchiffrement, dKD, dépendant d’une clef de décryptage ou de déchiffrement, KD.
1.2Qualités d’un cryptosystème.
Alice veut être certaine
• qu’une personne non-autorisée (Eve) ne peut pas prendre connaissance` de ses messages
• que ses messages ne sont pas falsifiés par un attaquant malveillant (Martin)
• que le destinataire (Bob) a bien pris connaissance de ses messages et ne pourra pas nier l’avoir re¸cu (non-répudiation)
• que son message n’est pas brouillé par les imperfections du canal de transmission (cette exigence ne relève pas du cryptage mais de la correction d’erreur)
Bob veut être certain
• que le message re¸cu est authentique c’est à dire
– que le message n’a pas été falsifié par un attaquant malveillant (Martin).
– que le messages vient bien d’Alice (autrement dit qu’un attaquant (Oscar) ne se fait pas passer pour Alice, mascarade)
• que l’expéditeur (Alice) ne pourra pas nier avoir envoyé le message
(non-répudiation)
CHAPITRE 1. INTRODUCTION
• que le message n’est pas brouillé (par les imperfections du canal de transmission ou par un brouillage intentionnel), autrement dit qu’il est identique à l’original que lui a envoyé Alice.
Les qualités demandées à un système cryptographique sont résumées par les mots clefs suivants:
• Intégrité des données: le message ne peut pas être falsifié sans qu’on s’en aper¸coive
• Identité des interlocuteurs du message:
– l’émetteur est suˆr de l’identité du destinataire c’est à dire que seul le destinataire pourra prendre connaissance du message car il est le seul à disposer de la clef de déchiffrement.
– Authentification, le receveur est suˆr de l’identité de l’émetteur grâce à une signature
• Non-répudiation se décompose en 3
– non-répudiation d’origine l’émetteur ne peut nier avoir écrit le message
– non-répudiation de reception le receveur ne peut nier avoir re¸cu le message.
– non-répudiation de transmission l’émetteur du message ne peut nier avoir envoyé le message.
Chapitre 2
Historique.
Il y avait historiquement deux grandes familles de codes classiques avec des hybrides
• Les codes à répertoire
• Les codes à clefs secrètes qui se subdivisent en deux familles
– les codes de transposition ou de permutation qui sont des codes par blocs.
– les codes de substitution qui peuvent être des codes par blocs ou par flots
On trouve des utilisations attestées par des documents historiques comme par exemple
• Scytale à Sparte vers -450, (principe des codes de permutation).
• Code de Jules César vers -50, (principe des codes de substitution).
• Les codes à répertoires, très anciens ont été utilisés intensivement jusqu’au début du 20-ième siècle.
2.1Codes à répertoire.
Ces codes manquent de souplesse ils ne permettent pas de coder des mots nouveaux sans des échanges de codes entre l’expéditeur et le destinataire ce qui accroˆ?t le risque de voir le code intercepté. Ils ne sont plus utilisés pour les usages publics.
On peut par exemple créer le dictionnaire suivant:
9
rendez-vous ? 175demain ? oiseaux midi ? à vendreVilletaneuse ? au marché
La phrase en clair:
RENDEZ VOUS DEMAIN MIDI VILLETANEUSE
devient avec ce code
175 OISEAUX A VENDRE AU MARCH` E´
Il faut donc disposer de distionnaires qui prévoient toutes les possibilités. Donc sauf si on se restreint à tranmettre des informations très limitées, la taille du dictionnaire s’accroit démesurément. Au 19e siècle on avait ainsi pour des usages commerciaux ou militaires des dictionnaires de plusieurs milliers de mots de codes. Tous changement du code nécessitait l’envoi de documents volumineux avec un risque d’interception non négligeable.
2.2 Codes de permutation ou de transposition.
On partage le texte en blocs, on garde le même alphabet mais on change la place des lettres à l’intérieur d’un bloc (on les permute).
Un exemple historique dont le principe est encore utilisé dans les codes à clef secrète (DES, AES) est la méthode de la grille (principe de la scytale utilisé par les spartiates).
On veut envoyer le message suivant:
RENDEZ VOUS DEMAIN MIDI VILLETANEUSE
L’expéditeur et le destinataire du message se mettent d’accord sur une grille de largeur fixée à l’avance (ici une grille de 6 cases de large).
L’expéditeur écrit le message dans la grille en rempla¸cant les espaces entre les mots par le symbole . Il obtient:
RENDEZ
VOUS
DEMAIN
MIDI
VILLET
ANEUSE
Il lit le texte en colonne et obtient ainsi le message crypté:
2.2. CODES DE PERMUTATION OU DE TRANSPOSITION
RDVAEVEMINNOMILEDUADLUESIIESZNTEC
Pour augmenter la sécurité les deux interlocuteurs peuvent décider l’ajout d’une clef.
Le but est de pouvoir changer facilement le cryptage d’un message tout en gardant le même algorithme de codage. Pour cela on rajoute une clé secrète constituée par l’ordre de lecture des colonnes.
Exemples1. On choisit la clé: CAPTER
On numérote les colonne en fonction du rang des lettres du mot CAPTER dans l’alphabet c’est à dire
2,1,4,6,3,5
et on lit les colonnes dans l’ordre indiqué.
EVEMINRDDADUADLUZNTENOMILEESIIES
On a 6! codes différents.
Pour décoder le message précédent on range en colonne sur la grille en suivant l’ordre des colonnes donné par le mot de code
On a affaire à un code à clef secrète ou code symétrique car la clef de décodage est la même que la clef de codage.
2.3 Codes de substitution.
Dans les codes de substitution par flots ou par blocs l’ordre des lettres est conservé mais on les remplace par des symboles d’un nouvel alphabet suivant un algorithme précis.
Exemples2. Code de César:
Pour coder on remplace chaque lettre par son rang dans l’alphabet.
A=1, B=2, C=3, .,M=13, N=14, ,S=20, ,X=24, Y=25, Z=26
D’après Suetone, Vie des douze Césars, Jules César pendant la guerre des
Gaules avait utilisé le code de substitution par flot suivant
lettre codée=lettre claire+3 modulo 26
Le message en clair
RENDEZ VOUS DEMAIN MIDI VILLETANEUSE
devient
UHQGHC YRXV GHPDLQ PLGL YLOOHWDQHXVH
Avantage: on peut considérer toute la famille des codes
lettre codée=lettre claire+n modulo 26
ou` n est un entier entre 0 et 25 appelé la clef du code.
Avec la clef n = 7 le texte codé du message précédent devient:
YLUKLG CVBZ KLTHPU TPKP CPSSLAHULBZLBZL
Le décodage se fait en utlisant la relation
lettre claire=lettre codée -n mod 26
On a encore affaire à un code en continu ou par flot symétrique ou à clef secrète.
2.4. LE CODE DE VIGEN´ ERE`
2.3.1 Cryptanalyse des codes de César.
On considère un message codé avec une substitution monoalphabétique:
JTVMNKKTVLDEVVTLWTWITKTXUTLWJERUTVTWTHDXATLIUNEWV.
JTVIEVWELOWENLVVNOEDJJTVLTPTXYTLWTWUT
SNLITTVQXTVXUJXWEJEWTONKKXLT.
Décodage par analyse de fréquence.
Analyse de fréquence
Lettre % fran¸cais % texteLettre % fran¸cais % texte
A 9,4 1N 7,2 5
B 1,0 0O 5.1 2,5
C 2,6 0P 2,9 1
D 3,4 2,5Q 1,1 1
E 15,9 8R 6,5 1
F 1 0S 7,9 1
G 1 0T 7,3 20
H 0,8 1U 6,2 4,5
I 8,4 3,8V 2,1 12
J 0,9 5,1W 0 9,9
K 0 4,7X 0,3 6
L 5,3 9Y 0,2 1
M 3,2 1Z 0,3 0
On peut donc faire l’hypothèse que T=E puis que V=S (à cause des lettres doublées) puis que les voyelles A, I, O, U correspondent à D,E, N, X et finalement on obtient la correspondance
| A | B | C | D | E | F | G | H | I | J | K | L | M |
| D | R | O | I | T | S | H | M | E | F | G | J | K |
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| L | N | P | Q  | U | V | W | X | Y | Z | A | B | C |
2.4Le code de Vigénère.
La faiblesse des codes de César et des systèmes analogues est que la fréquence des lettres est conservée ce qui permet une cryptanalyse aisée par analyse de fréquences.
Pour améliorer la sécurité on peut faire un code de César par blocs dans lequel on change de substitution pour chaque lettre d’un bloc. On obtient ainsi le code de Vigénère, mis au point par Leon Batista Alberti au 15-ième siècle et développé par Blaise de Vigénère.
Très suˆrs pendant 4 siècles. Ils ont été cryptanalysés officiellement par Charles Babbage et Friedrich Wilhelm Kasiski au 19-ième siècle.
Le code de César et le code de substitution sont des codes monoalphabétiques. Le code de Vigénère est un code polyalphabétique ou par blocs.
• On se fixe une longueur de bloc m.
• On découpe le message en blocs de m-lettres.
• On chiffre par blocs de m lettres. On décide par exemple que la première lettre d’un bloc de m est codée avec un code de César de clef n1, la deuxième avec un code de César de clef n2 et la m-ième par un code de César de clef nm.
Exemples3. m = 5, n1 = 3, n2 = 14, n3 = 7, n4 = 22, n5 = 19, le message en clair est:
n
M= Ce système de codage n’est pas suˆr, mais plus que le code de César si
o la clé est longue . on partage en blocs de taille 5 en partant de la gauche
CESYS TEMED ECODA GENES TPASS URMAI SPLUS QUELE CODED ECESA RSILA CLEES TLONG UEXXX
Les XXX ont été ajoutés pour compléter le dernier bloc. La manière de compléter le dernier bloc peut être une faiblesse du code. Le message codé devient:
e(M)= FSZUL WSTAW HQVZT JSUAL WDHOL XFTWB VDSQL TILHX FCKAW HQLOT UGPHT FZLAL WZVJZ XSETQ
La cryptanalyse du cryptosystème de Vigénère peut se faire, si le message est assez long, à texte chiffré connu, cf. le chapitre 4, en remarquant que des répétitions de lettres assez longues (3 au moins) doivent correspondre dans le texte clair à des répétitions de lettres aussi. Ceci permet de majorer la taille de la clé. On se ramène alors à la cryptanalyse d’un chiffrement de
César.
2.5. CHIFFREMENT DE HILL
Ici compte tenu de la longueur du texte on trouve les doublets AW et AL
éloignés de 40 lettres et 45 lettres dont le PGCD est 5 ce qui suggère une clef de longueur 5.
Une fois que l’on a déterminé la longueur de la clef, le décodage est le même que celui de 5 codes de César.
2.5Chiffrement de Hill.
Ce cryptosystème généralise celui de Vigénère. Il a été publié par L. S. Hill en 1929.
• On choisit un alphabet de n lettres (on prendra dans nos exemples n = 26) et une taille m pour les blocs, par exemple m = 2. Alors P = E = (Z/26Z)2, (en général Z/nZ).
• La clef de codage est une matrice inversible K ? GLm(Z/26Z), si m = 2
Si ( est le message clair alors le message codé sera:
La clé de déchiffrage est la matrice inverse de K dans GLm(Z/26Z).
Par exemple avec alors.
Le cryptosystème de Hill succombe facilement aux attaques à texte clair choisi.
2.6Commentaires historiques.
Les méthodes historiques pour authentifier un message se retrouvent dans les cryptosystèmes modernes
On utilisait des messagers qui devaient échanger des signes de reconnaissance convenus (phrase de reconnaissance, lettres d’introduction, etc..) avec le destinataire pour authentifier le messager, l’expéditeur ou le destinataire, pour éviter les faux messages.
Pour éviter la falsification du message on le mettait dans une enveloppe scellée revétue de cachets, le message lui-même était signé, l’écriture permettait elle aussi l’authentification du message, etc
Le destinataire pouvait parfois accuser réception en guise de protocole de non répudiation.
La cryptanalyse a été pratiquée depuis la plus haute antiquité. Le code de César a été cryptanalysé par les lettrés arabes du 9-ième siècle; Al Kindi a décrit la méthode de l’analyse statistique.
Tous les rois avaient leurs cryptographes-cryptanalystes (les Rossignol pour Louis XIV) et leur cabinet noir.
Les rapports entre cryptographie et cryptanalyse sont analogues aux rapports entre blindage et artillerie. Le code de César a tenu 9 siècle, celui de Vigenère a tenu 4 siècles, le standard DES a tenu 20 ans. le standard RSA est en passe d’être supplanté par les codes elliptiques.
Chapitre 3
Quelques méthodes de codage.
3.1 Chiffrement en chaˆ?ne.
Dans les systèmes cryptographiques que nous avons décrits les éléments de texte clair sont chiffrés de la même manière à partir de la clef K
y = y1y2 ··· = eK(x1)eK(x2)
On peut procéder différemment. On se donne une clé K et pour chaque entier i une fonction fi(K,x1, ,xi?1) qui dépend de K et des blocs précédents xi.
La valeur Ki = fi(K,x1, ,xi?1) est la clé utilisée pour coder le i-ième bloc xi
| texte codé Exemples4. On prend | |
| P = E = Z/26Z, | K = 8 et f1(K) = K |
Ki = fi(K,x1, ,xi?1) = xi?1, eKi(xi) = xi + Ki
Le chiffrement est dit synchrone si f ne dépend pas des xi, il est dit asynchrone si f dépend effectivement des xi.
3.2 Codes à confidentialité parfaite.
La théorie de l’information due à Claude Shannon permet de définir un code à confidentialité parfaite, voir la dfinition 11.1.6 page 79. Grossièrement il s’agit de codes tels que la connaissance du texte crypté ne permette d’avoir aucune information sur le texte en clair.
17
CHAPITRE 3. QUELQUES METHODES DE CODAGE´
De tels codes existent, ce sont les codes de Vernam ou codes à masques jetables, (1917). Ils reposent sur la fabrication de clefs ‘au hasard’ aussi longues que le texte à coder et qui ne servent qu’une fois.
La mise en oeuvre de ces codes est lourde et délicate. La fabrication de clefs ‘au hasard’ est un problème très difficile et mal résolu. Le stockage et la transmission de ces clés posent un problème de sécurité.
Ils sont rarement utilisés.
Le principe de ces codes est le suivant. On tranforme le texte en une suite de chiffres en base b (souvent b = 2). On fabrique ensuite une suite aléatoire de chiffres de même longueur et l’on ajoute les deux suites ainsi obtenues sans retenue, c’est à dire que l’on fait le calcul chiffre à chiffre modulo b.
Exemples5. On transforme les lettres de l’alphabet en nombres de 1 à 26 donc ici b = 26 lettre codée ?lettre claire+lettre de la clé mod 26
On code le message chiens qui comporte 6 lettres avec la clef KZUTEG
(message=CHIENS) + (clef=KZUTEG) = NHDYSZ
On constate que si l’on avait envoyé le message cerise avec la clé KCNPZC on aurait obtenu
(message=CERISE) + (clé=KCNPZC) =NHDYSZ
Il est donc impossible de remonter au texte clair si on change de clé aléatoirement à chaque fois.
Cet exemple montre que la confidentialité est parfaite. Ces codes sont très suˆr. Mais leur mise en oeuvre est très délicate et ils sont très lents.
3.3 Registres à décalage.
On a construit des codes par flots qui cherchent à imiter les codes de Vernam mais qui sont très rapides et très faciles à mettre en oeuvre afin de pouvoir coder et décoder à la volée en temps réel (Télévision, ).
Une famille de tels codes est basée sur les registres à décalages ou suites récurrentes linéaires sur un corps fini ou encore dans la terminologie anglosaxone les linear feedback register ou en abrégé LFBR.
3.3. REGISTRES A D` ECALAGE´
On fabrique avec les registres à décalage des suites pseudo-aléatoires pour générer la clef du code. Ces codes sont donc beaucoup moins suˆrs que les codes de Vernam mais ne nécessitent pas la fabrication et la transmission d’une clef aléatoire de la longueur du message à transmettre.
3.3.1 Régistres à décalage ou suites récurrentes linéaires sur un corps fini.
Pour des raisons techniques le corps fini considéré sera le corps à 2 éléments F2 ' Z/2Z, c’est à dire que F2 = {0,1}, muni des deux lois + et ×
0 + 0 = 0, 1 + 0 = 0 + 1 = 1, 1 + 1 = 0
0 × 0 = 0 1 × 0 = 0 × 1 = 0 1 × 1 = 1
ces deux lois sont associatives et la loi + distributive par rapport à la loi ×, c’est à dire:
(a+b)+c = a+(b+c), (a×b)×c = a×(b×c), (a+b)×c = (a×c)+(b×c).
On se donne un entier m, la longueur de la récurrence, et des éléments
k1, ,km ? Z/2Z, les conditions initiales
c0, ,cm?1 ? Z/2Z les coefficients de la récurrence
On construit une suite d’éléments (zi)i?N de Z/2Z:
z1 = k1, , zm = km, zm+1 = c0zm1 + ··· + cm?1zm
m?1
zm+i = c0zi + ··· + cm?1zm?1+i= X cjzj+i
j=0
Il est facile de montrer que la clef est périodique (il existe T tel que zi+T = zi pour i assez grand); mais si on choisit bien les ki et les cj la période est grande devant m.
Exemples6. Exemple: m=4, (k1,k2,k3,k4) = (1,0,0,0) et
zi+4 = (zi + zi+1) mod 2
On vérifie que la période est 15.
CHAPITRE 3. QUELQUES METHODES DE CODAGE´
On considère alors le chiffrement en chaˆ?ne (synchrone ou asynchrone) dont la clef est K = z1z2zn . On code alors en effectuant un XOR sur le message avec la clé K. C’est à dire qu’on fait une somme modulo 2 (sans retenue) d’un bit du message et du bit de même rang de la clef. Exemples7. Chiffrement en chaˆ?ne synchrone par XORisation:
message : 10010111010011000 clef : 10100111010001011 message codé : 00110000000010011
Ce type de codage se prète très bien au codage en temps réel d’images, de sons. La clef peut être construite par des registres à décalage qui peuvent être facilement cablés. Sous la forme indiquée ce système de codage est peu suˆr à cause de son caractère linéaire..
Pour le rendre plus suˆr on utilise n registres à décalages que l’on combine entre eux à l’aide d’une fonction booléenne non-linéaire c’est à dire une fonction non linéaire, f, du corps fini à 2n-éléments F2n que l’on identifie avec un F2-espace vectoriel de dimension n et à valeurs dans le corps à deux éléments F2 ' Z/2Z. Cette fonction est appelée fonction de combinaison ou fonction de filtrage. On lui demande de satisfaire certains critères cryptographiques.
Remarquons que le cardinal de l’ensemble, Bn, des fonctions boolénnes de F2n dans F2 est 22n et qu’il croit extrèmement vite
| n | 4 | 5 | 6 | 7 | 8 |
| Bn | 216 | 232 | 264 | 2128 | 2256 |
donc le choix de bonnes fonctions cryptographiques nécessite des preuves mathématiques.
3.4 Lutte contre le brouillage.
Le canal de transmission d’un message est souvent brouillé de manière naturelle (parasites dus aux activités humaines ou aux phénomènes naturels dans les transmissions électromagnétiques, hertziennes ou filaires).
Le stockage des données se dégrade naturellement avec le temps (action des particules très énergiques, poussières, rayures sur les CD et DVD, etc.).
Pour lutter contre tous ces brouillages on dispose de la théorie des codes correcteurs d’erreurs. elle est basée
3.4. LUTTE CONTRE LE BROUILLAGE
• sur la théorie des espaces vectoriels sur un corps fini.
• sur la théorie des polynômes sur un corps fini.
• plus généralement sur la géométrie algébrique sur un corps fini.
Exemples8. Exemples de codes correcteurs d’erreurs
L’exemple le plus simple de code correcteur d’erreurs est la répétition du message un certain nombre de fois en espérant que les parasites (supposés aléatoires) n’affecteront pas toujours la même partie du message. Mais cette méthode est lourde pour des messages longs et ralentit fortement la transmission des données.
Autre exemple de code correcteur d’erreurs: on suppose que le message est une suite de 0 et de 1 (des bits). On les groupe par paquets de 7 et on ajoute dans chaque paquet de 7 bits un huitième bit (0 ou 1) de telle sorte que la somme de ces 8 chiffres soit paire (code de Hamming). Ce code repère au plus une erreur dans chaque groupe de 8 bits.
Chapitre 4
Sécurité d’un cryptosystème.
Le principe de Kerckhoff stipule que
La sécurité d’un cryptosystème ne repose pas sur le secret du cryptosystème mais seulement sur la clef du cryptosystème qui est un paramètre facile à changer, de taille réduite (actuellement de 64 à 2048 bits suivant le type de code et la sécurité demandée) et donc assez facile à transmettre secrètement.
On suppose donc pour toutes les évaluation de sécurité d’un cryptosystème que l’attaquant connait le système cryptographique utilisé, la seule partie secrète du cryptosystème est la clef.
Par exemple dans un cryptosystème basé sur des régistres à décalage on suppose que l’attaquant connait la forme des récurrences linéaires ainsi que la fonction de combinaison mais pas les conditions intiales des récurrences qui constituent la clef du code.
Les principaux types d’attaques:
• attaque à texte chiffré connu: l’opposant ne connait que le message chiffré y.
• attaque à texte clair connu: l’opposant dispose d’un texte clair x et du message chiffré correspondant y
• attaque à texte clair choisi: l’opposant a accès à une machine chiffrante. Il peut choisir un texte clair et obtenir le texte chiffré correspondant y.
• attaque à texte chiffré choisi: l’opposant a accès à une machine déchiffrante. Il peut choisir un texte chiffré, y et obtenir le texte clair correspondant x.
22
4.1. DIFFERENTES NOTIONS DE S´ ECURIT´ E´
4.1Différentes notions de sécurité d’un cryptosystème.
• La sécurité inconditionnelle qui ne préjuge pas de la puissance de calcul du cryptanalyste qui peut être illimitée.
• La sécurité calculatoire qui repose sur l’impossibilité de faire en un temps raisonnable les calculs nécessaires pour décrypter un message.
• La sécurité prouvée qui réduit la sécurité du cryptosystème à un problème bien connu réputé difficile, par exemple on pourrait prouver un théorème disant qu’un système cryptographique donné est suˆr si un entier donné n ne pêut être factorisé.
• La confidentialité parfaite qualité des codes pour lesquels un couple (message clair, message chiffré) ne donne aucune information sur la clef.
Toutes ces notions de suˆreté reposent sur la théorie de l’information de Claude Shannon. Il a pu donner un sens précis basé sur les probabilités à la première notion si l’on précise le type d’attaques permises. Il a aussi donné un sens précis à la notion de confidentialité parfaite.
La deuxième notion repose sur la théorie de la complexité. Dans la pratique il faut préciser le type d’attaque. C’est celle que l’on utilise dans la plupart des applications.
Chapitre 5
Les codes modernes.
Tout d’abord nous allons donner une descrition un peu formelle d’un cryptosystème
Définition 5.0.1.Un cryptosystème est un dictionnaire entre les messages en clair et les messages chiffrés.
Afin de pouvoir travailler efficacement sur les codes et définir de manière quantitative leur sécurité on est amené à les modéliser et donc à définir de manière axiomatique un cryptosystème. Définition formelle d’un cryptosystème
Définition 5.0.2.Formellement un cryptosystème est un quintuplet
(P,C,K,E,D)
ou`
• P est un ensemble fini de blocs : les mots en clair
• C est un ensemble fini de blocs: les mots codés
• K est un ensemble : l’espace des clefs
• Pour tout K ? K une règle de chiffrement eK ? E et une règle de déchiffrement correspondante dK ? D. Chaque eK : P ? C et dK : C ? P sont des fonctions telles que dK(eK(x))) = x pour tout x ? P
Pour chaque K ? K (la clef du code) la transformation (bijective) eK est appelée le procédé de chiffrement, ou l’algorithme de codage, entre les textes en clair P et les textes codés C.
La fonction inverse dK de eK est appelée la fonction de décodage.
On exige que tout message codé puisse être décodé.
24
5.1. OBJECTIFS DES CODES ACTUELS
Un code moderne est donc constitué
• D’un algorithme de chiffrement f = fKC, supposé connu de tous, dépendant d’un paramètre KC, la clé de chiffrement. L’algorithme est fixé et public, seule la clé change, principe de Kerckhoff.
• De la valeur de la clé de chiffrement, KC qui est secrète ou non suivant que l’on a affaire à un code à clef secrète ou à un code à clef publique.
• D’un algorithme de déchiffrement g = gKD = f?1 (supposé connu de tous) dépendant d’une clé de déchiffrement, KD, différente ou non de KC.
• De la valeur de la clé de déchiffrement, KD, qui est toujours secrète.
5.1Objectifs des codes actuels.
• Les messages ne peuvent être déchiffrés que par le destinataire (confidentialité des données).
• Ils ne peuvent être modifiés par un tiers non autorisé (intégrité des données).
• L’identité des différents participants peut être vérifiée (authentification).
• L’expéditeur ne peut nier avoir émis le message et le destinaire ne peut nier l’avoir re¸cu (non-répudiation des données).
• Il doit permettre de coder et décoder rapidement (en temps réel pour certaines applications).
• Il doit au moins résister aux attaques connues et si possible avoir une sécurité prouvée.
Il n’existe pas de codes qui réunissent toutes ces qualités simultanément. Il faut donc un compromis adapté à chaque situation.
26 CHAPITRE 5. LES CODES MODERNES
5.2 Les familles de codes modernes.
Les principales familles de codes modernes sont
• Les codes par flot (registres à décalage)
les codes symétriques (ou à clé secrète).
• les codes par blocs les codes asymétriques (ou à clé publique) Les codes à clef publique sont basés sur la notion de fonction à sens unique.
5.3 Codes symétriques.
Les principes des codes symétriques commerciaux modernes du type DES (Data Encrytion Standard) ont été mis au point dans les années 1970 par IBM avec l’aide de la NSA (National Security Agency), ce sont des hybrides de codes de substitutions et de codes de transpositions.
Ils restent très suˆrs avec des clés assez courtes de 128 bits à 256 bits. Leur suˆreté est non prouvée. Leur cryptanalyse a fait des progrès (cryptanalyse linéaire et différentielle), ce qui permet de mieux cerner leur sureté.
Les codes à clé secrète sont les plus employés actuellement car ils sont
éprouvés, résistants, rapides et assez facile à mettre en oeuvre. Actuellement leur sécurité est garantie (mais non prouvée) avec des clés assez courtes de 128 à 256 bits pour le standard actuel AES.
Mais il faut échanger la clé secrète avec le destinataire d’ou` un risque. Ils nécessitent un grand nombre de clés. Il faut
clés pour que n interlocuteurs puissent échanger des informations d’ou` un problème de fabrication et d’échange de clefs fiables.
Ils ont du mal à réaliser sans tiers de confiance le partage des clefs, la signature, l’authentification, et la non répudiation des messages transmis. Ils s’adjoignent parfois un code asymétrique pour cela, voir le cryptosystème PGP.
La génération actuelle de codes symétriques est le cryptosystème AES développé dans les années 2000 à la suite d’un appel d’offre international par John Daemon et Vincent Rijmen, [6]. Il utilise dans sa conception nettement plus de mathématiques que son prédécesseur le DES.
5.4. CODES ASYMETRIQUES´
5.4Codes asymétriques.
Les principes des codes asymétriques ont été mis au point par Diffie et Hellman en 1976. Ils ont dégagé la notion de fonction à sens unique. Ce sont des fonctions qui sont faciles à calculer c’est à dire calculable en temps polynomial en fonction de la taille des données mais tel que l’image réciproque (les antécédents) d’un élément est très difficile à calculer explicitement (au moins calculatoirement). Autrement dit on demande que la fonction inverse ne soit pas calculable en temps polynomial en fonction de la taille des données.
La première solution celle de Diffie, Hellmann et Merkle était basée sur le problème du sac à dos dont il a été démontré que c’est un problème de type problème de type NP (NP pour Non Polynomial).
C’est donc un problème dont la solution exige un calcul en temps non polynomial en fonction de la taille des données, sous réserve de la validité de la conjecture P6= NP. On peut donc espérer qu’il permette de fabriquer un cryptosystème offrant une sécurité calculatoire élevée.
Malheureusement toutes les instances (réalisations) de ce problème ne sont pas de type NP. En particulier les réalisations pratiques de Diffie, Hellmann et Merkle utilisaient des sacs à dos qui n’étaient pas dans la classe NP. Leur cryptosystème a succombé à l’attaque des cryptanalystes (en particulier Shamir).
Dans la solution suivante, 1978, le cryptosystème RSA (Rivest-Shamir et Adleman), la fonction à sens unique sous-jacente est la multiplication des entiers qui appartient à la classe P (P pour Polynomial) des problèmes polynomiaux en temps. Sa fonction réciproque la factorisation des entiers est actuellement dans la classe NP des problèmes non polynomiaux en temps, c’est un fait d’expérience pas un théorème.
D’autres solutions sont apparues peu après: le sytème El Gamal, les codes basés sur les courbes elliptiques.
Les cryptosystèmes asymétriques reposent sur des structures mathématiques
élaborées. Leur suˆreté est bonne mais non prouvée. Leur cryptanalyse dépend beaucoup des progrès des mathématiques correspondantes.
Sauf pour les codes elliptiques, ils nécessitent des clés longues (1024 à 2048 bits) pour avoir une suˆreté équivalentes à celle d’un cryptosystème à clef secrète de 128 à 256 bits. Ils sont 1000 à 1500 fois plus lents. Mais ils
permettent de réaliser facilement les fonctionnalités suivantes
28 CHAPITRE 5. LES CODES MODERNES
• partage des clefs,
• authentification
• intégrité
• non répudiation
et bien d’autres encore grâce au fait que la clef est en fait constituée de deux clefs la clef de codage et la clef de décodage et que cette dernière est attachée à une personne et la caractérise.
Ils ne nécessitent que n paires de clés (une clé secrète et une clé publique) pour n interlocuteurs.
On les utilise souvent pour la transmission des clés secrètes des codes symétriques.
5.5 Les échanges de clefs.
Un problème important rencontré dans l’utilisation d’un cryptosystème est l’échange des clefs entre des interlocuteurs. C’est un des moments ou` la sécurité du cryptosystème est la plus vulnérable.
Rappelons que dans un cryptosystème à clef secrète lorsque deux interlocuteur veulent converser il leur faut échanger une clef. Il faut donc autant de clefs qu’il y a de paires non ordonnées d’interlocuteurs c’est à dire pour
n interlocuteurs . Le nombre de clefs à échanger entre n
interlocuteurs est donné par le tableau suivant
| nombre d’interlocuteurs | nombre de clés secrètes | nombre de clés publiques |
| 2 | 1 | 2 |
| 3 | 3 | 3 |
| 4 | 6 | 4 |
| 5 | 10 | 5 |
| 10 | 45 | 10 |
| 100 | 4950 | 100 |
| 1000 | 499 500 | 1 000 |
| 1 000 000 | 499 999 500 000 | 1 000 000 |
5.5. LES ECHANGES DE CLEFS´
Par contre dans un système à clef publique il faut autant de paires de clefs qu’il y a d’interlocuteurs. Chaque interlocuteur dispose en effet d’une clef publique pour le cryptage des messages qui lui sont adressés et d’une clef privée pour le décryptage des messages qu’il re¸coit.
5.5.1 Protocole d’échange de clefs.
Diffie, Hellmann et Merkle vers 1974 résolvaient le problème de partage d’une clé secrète sans envoi physique de la clef.
Leur protocole est le suivant:
1. Alice et Bob choisissent d’un commun accord sur une ligne non protégée un grand nombre premier p. et ? un générateur de Z/pZ
2. Alice choisit a et calcule ?a = ?a (mod p)
3. Bob choisit b et calcule ?b = ?b (mod p)
4. Alice et Bob s’échangent ?a et ?b
5. Alice calcule ?ba (mod p) et Bob calcule
On a
c’est la clef commune d’Alice et Bob.
Pourquoi ce protocole est-il suˆr? Si Eve intercepte la communication entre` Alice et Bob, elle peut lire les nombres ?a et ?b.
Pour calculer la clef commune d’Alice et de Bob, il faut qu’Eve puisse en déduire a et b c’est à dire qu’elle puisse calculer le logarithme discret dans Fp.
Pour l’instant il n’existe pas d’algorithme rapide, c’est à dire polynomial en temps en fonction de la taille des données, pour calculer le logarithme discret dans Fp. Les meilleurs algorithmes connus sont sous-exponentiels, cf. la sous-section 11.4. Pour un premier p de l’ordre de 10500 il faut des mois, voire des années, pour calculer un logarithme discret.
Par contre cet échange de clef peut-être soumis à d’autres types d’attaques.
Chapitre 6
Applications de la cryptographie.
Jusqu’au 20-ième siècle la cryptographie (légale) était essentiellement réservée aux militaires et aux diplomates et accessoirement aux industriels et banquiers.
Le développement des moyens de communications électromagnétiques facile à intercepter, des stockages de données confidentielles dans des sites assez faciles à pénétrer et sur des supports (bandes ou disques, magnétiques optiques) faciles à dupliquer ont généré une demande de cryptosystèmes suˆrs faciles d’emploi et rapides pour des usages civils et commerciaux.
Les codes symétriques ou à clefs secrètes, type DES (Data Encryption Standard), IDEA (International Digital Encryption Algorithm), AES (Advanced Encryption Standard) ont été créés pour couvrir ces besoins. L’application première de la cryptographie est et reste encore la transmission sécurisée de données sensibles.
Le commerce en ligne, la consultation des données bancaires sur internet, le paiement par carte bancaire ont entraˆ?né une explosion de l’utilisation de la cryptographie mais ont aussi une extension de ses applications. Cette extension a été facilitée par la mise au point des procédés de transferts de clefs de Diffie et Hellman et des codes asymétriques ou à clefs publiques de type RSA ou El Gamal.
Les codes à clef publique permettent de résoudre avec des protocoles légers les questions de transfert de clefs, d’identification, d’authentification, de signature entre correspondants.
Aujourd’hui les plus gros utilisateurs de cryptosystèmes sont les institutions financières (banques, bourses, ), les télécommunications (téléphonie mobile,WIFI, Internet, ), les sites d’achats en ligne,
30
6.1. QUEL CRYPTOSYSTEME CHOISIR`
Il est probable que le tatouge (watermarking) des données numériques ainsi que la gestion des droits numériques (digital right management ou DRM) vont entraˆ?ner une demande accrue de cryptographie.
Le mariage de la cryptographie et de la théorie de la complexité aboutit à des extensions spectaculaires du champ de la cryptographie classique. Ces nouvelles applications sont développées au chapitre 10 page 68.
6.1Quel cryptosystème choisir.
Chacun des cryptosystèmes existant codes par flots, codes par blocs à clé secrète, codes à clés publiques ont leurs avantages et leurs inconvénients. Ils ont chacuns des applications privilégiées et sont souvent utilisés en association.
Les codes par flots basés sur les registres à décalage sont très utilisés en télécommunications (télévision à péage), à cause de leur rapidité. ils permettent de faire du codage et du décodage à la volée en temps réel.
Les codes par blocs à clé secrète sont les plus employés car ils réalisent un excellent compromis entre rapidité et sécurité. Ils ne nécessitent que des clefs assez courtes pour un bon niveau de sécurité (128/256 bits). Par contre ils nécessitent d’échanger de nombreuses clés secrètes avec un risque pour la sécurité. On peut les associer à un cryptosystème à clef publique pour échanger les clefs qui doivent être changées très régulièrement pour garder une bonne sécurité et ausi pour réaliser les signatures et authentifications.
Les cryptosystèmes asymétriques sont plus lents. Ils nécessitent des clés longues (1024/2048 bits) sauf les codes elliptiques (128/256 bits). Ils ne nécessitent pas d’échange de clés secrètes et permettent de réaliser facilement des fonctionalités très utiles (signature, authentification, non répudiation, ).
6.2Quelques utilisations de la cryptographie.
La nécessité de pouvoir identifier de manière suˆre:
• le titulaire d’un compte en banque qui veut retirer de l’argent, ou qui paye par carte bancaire,
• un avion au moment de la procédure d’atterrissage, un véhicule suivi par GPS,
32 CHAPITRE 6. APPLICATIONS DE LA CRYPTOGRAPHIE
• sur un champ de bataille ses propres troupes et celles de l’ennemi,
a entraˆ?né le développement des protocoles d’identification largement basés sur les principes des codes asymétriques.
La recherche d’une sécurité accrue pour les sites sécurisés de paiemant en ligne profite du développement des
• Les protocoles de preuves sans apport de connaissance.
• La signature aveugle.
basés sur la théorie de la preuve sans apport de connaissance (zero-knowledge proof ).
La nécessité de conserver l’anonymat dans certaines situations (secret médical par exemple, secret de la vie privée, etc..) peut être assuré grâce au
• Le transfert inconscient.
Il y a encore bien d’autres applications.
6.3 Quelles mathématiques pour la cryptographie.
Actuellement tous les cryptosystèmes utilisent des mathématiques. Elles sont utilisées aussi pour définir et tester la sécurité des cryptosystèmes.
• Logique: théorie de la complexité.
• Théorie de l’information
• Probabilités: pour la théorie de l’information.
• Combinatoire (théorie de graphes): construction de cryptosystèmes asymétriques, preuves sans apport d’information, partage de secret à seuil.
• Algèbre, corps finis, polynômes sur un corps fini,
• Théorie des nombres (arithmétique modulaire, théorie algébrique des nombres) : construction de cryptosystèmes asymétriques (RSA, ElGamal), générateurs de nombres aléatoires.
• Géométrie algébrique sur un corps fini: construction de cryptosystèmes basés sur les courbes elliptiques sur un corps finis, cryptosystèmes basés sur les codes correcteurs d’erreurs.
6.3. QUELLES MATHEMATIQUES POUR LA CRYPTOGRAPHIE´
• Algorithmique: mesure de la complexité algorithmique, réalisation pratique d’algorithmes performants.
La réalisation pratique des cryptosystèmes repose sur une implantation informatique, leur degré de sécurité, leurs performances en dépendent grandement.
Chapitre 7
Codes à clefs secrètes.
Devant l’explosion des besoins de cryptage pour des données non-classifiées (c’est à dire non militaires et non diplomatiques) le National Bureau of Standards des Etats-Unis a lancé un appel d’offre avec un cahier des charges en 1973.
Cet appel d’offre a donné naissance au cryptosystème DES (Data Encrytion Standard). Il a été publié en 1975 et adopté par le NBS en 1977 comme standard de cryptage pour les applications non classifiées. Il reprend les principes et une partie du système de cryptage d’IBM denommé LUCIFER.
Il est à la base d’autres cryptosystèmes plus récents comme IDEA, FEAL, CAST, RC5, BLOW-FISH.
Il est remplacé aujourd’hui par AES (Advanced Encrytion Standard) de J. Daeme et V. Rijmen, basé sur le même principe avec une clé plus longue (128 à 256 bits), plus structuré et avec des fonctionnalités plus étendues. AES a été retenu en 2000 après un appel d’offre international.
7.1 Description de DES.
C’est un système cryptographique produit, basé sur un schéma de Feistel. Il compose des opérations de cryptage, autrement dit il effectue un produit d’opérations de cryptage. Il répéte 16 fois un algorithme la fonction d’étage qui dépend d’un paramètre la clef d’étage. La répétition de cet algorithme mélange les bits du message en clair en respectant les principes de C. Shannon: confusion et diffusion.
• La confusion gomme les relations entre le texte clair et le texte chiffré pour éviter les attaques par analyse statistique. Autrement dit un
34
7.1. DESCRIPTION DE DES
changement d’un seul bit dans le texte clair doit affecter un grand nombre de bits (tous) du texte chiffré.
• La diffusion disperse la redondance du texte clair dans le texte chiffré, par exemple deux lettres doublées ne doivent pas rester côte à côte après cryptage.
7.1.1 Quelques apects techniques de DES.
DES utilise une clé K de 56 bits utiles, en fait une clé de 64 bits dont les bits 8, 16, 24, 32, 40, 48, 56 ne sont pas utilisés pour la clé mais participent à un code correcteur qui permet de vérifier que la clé n’a pas été altérée.
DES est un cryptosystème par blocs qui travaille sur des blocs de 64 bits.
La clé de DES est trop courte pour les puissances de calcul actuelles. La taille de la clé secrète 56 bits le rend aujourd’hui vulnérable aux attaques par force brute. En 1997 la clé a été cassée en 3 semaines par une fédération de machines sur internet. Elle a été cassée en 56 heures en 1998.
En 1999 la clé a été cassée en moins d’une journée, 22 heures, grâce à un ordinateur dédié couplé avec un réseau de plusieurs millers d’ordinateurs.
Afin de prolonger la durée de vie de DES en attendant AES on a introduit le triple DES. Il consiste à appliquer successivement au message DES muni de la clef K, à le décoder avec DES muni de la clef K’ et de le recoder avec DES muni de la clef K. Au total tout se passe comme si on avait codé le message avec une clé nettement plus longue.
C’est un système de chiffrement itéré à 16 étages
1. La clé K donne naissance à 16 sous-clés, les clefs d’étage, de 48 bits K1, K2, ,K16
2. Etant donné un bloc de texte clair de 64 bits, X, on construit, grâce à la fonction d’étage g0, un nouveau texte, X0, par permutation de l’ordre des bits grâce à la permutation initiale IP.
g0(X) = X0 = IP(X)
3. on sépare les 32 bits de gauche, L0, et les 32 bits de droites, R0, de
X0, donc X0 = L0R0
4. On effectue 16 itérations (ou tours ou étages). On calcule la valeur de la fonction d’étage g(Xi?1,Ki) = LiRi, 1 ? i ? 16 suivant la règle
Li = Ri?1
Ri = Li?1 ? f(Ri?1,Ki)
ou` ? est la somme dans Z/2Z de Li?1 et f(Ri?1,Ki) et ou` f une fonction non linéaire qui participe à la diffusion et qui est décrite par les S-boˆ?tes
5. Pour finir on applique la permutation inverse de la permutation initiale, IP?1, à R16L16
le schéma suivant résume ce qui précède, il est extrait du cours de Jean-Louis Pons, [14].
7.1. DESCRIPTION DE DES
ENSAM Aix-en-Provence
FIG. 1 – Architecture du DES
18
7.2 Description d’AES.
Le principe de l’AES, très proche du DES. C’est aussi un système cryptographique produit constitué d’une suite d’opérations de permutation et de substitution.
AES travaille sur des blocs de 128 bits avec des clefs de longueur 128, 256 ou 384 bits. Le passage à une clé de 128 bits minimum rend impossible dans le futur prévisible les recherches exhaustives de clefs. Si on suppose que l’on a un algorithme capable de comparer en une seconde 256 clefs (i.e de casser DES en une seconde) il lui faudra 149 mille milliards d’années pour casser AES.
AES résiste à toutes les attaques connues (attention ce n’est qu’un fait d’expérience pas une preuve).
Les deux schémas qui suivent sont extraits respectivement des sites
09/09/2005 file:/home1/barsky/enseignement/cours- #1
7.2.1 Quelques apects techniques d’AES.
Pour toute la partie mathématique on pourra consulter dans les compléments mathématiques la section sur les extensions de corps et les anneaux de polynômes sur un corps fini, section 11.6 page 104.
AES est un système de chiffrement itéré constitué d’un algorithme de chiffrement, la fonction d’étage, répété de Nr fois, avec Nr allant de 10 à 14, et d’une clef d’une longueur de 128, 192 ou 256 bits pour chaque étage, la clef d’étage.
Un algorithme de diversification de clef , ExpandKey[i], permet de créer une clef pour chacun des étages, i, à partir de la clef secrète K.
On notera Ne le nombre d’étages. La fonction d’étage, g, est l’ensemble des opérations que l’on fait subir au texte qui arrive à l’étage i. Elle est la même pour tous les étages sauf le dernier dans un soucis de simplicité.
La fonction g consiste en l’application successive de 4 opérations SubBytes, ShiftRows, MixColumns, AddRoundKey.
A partir de la clef secrète,` K, on génére des sous clefs d’étage par l’algorithme de diversification de la clef, ExpandKey[i]. On obtient les clefs d’étage: K1, ,KNe.
On note x le texte initial (texte en clair), wi le texte utilisé en entrée à l’étage i et y sera le texte crypté final.
Tous les textes sont supposés transformés en une suite de zéros et de uns.
Si K et L sont deux telles suites on note
K ? L
L’opération XOR entre le suite K et la suite L, c’est à dire l’addition sans retenue modulo 2 entre K et L, cf. page 20.
Avec ces notations la description schématique d’AES est la suivante:
1. On initialise w0 à x et et on effectue l’opération AddRoundKey
W0 ? K
2. Pour chacun des 1 < i ? Ne ? 1 étages suivants on effectue sur wi les opérations suivantes
(a) l’opération de substitution SubBytes
(b) sur le résultat de SubBytes une permutation notée ShiftRows (permutation circulaire sur les éléments des lignes de la matrice des octets si,j)
(c) sur le résultat de ShiftRows une opération notée MixColumns (application linéaire sur l’espace des matrices sur F28)
(d) Sur le résultat de MixColumns l’opération AddRoundKey[i] avec la sous-clé de l’étage i
3. Pour le dernier étage Ne on supprime l’opération MiXColumns On va décrire maintenant chacune des opérations utilisées.
L’opération ExpandKey
L’opération ExpandKey dépend de la taille de blocs choisie, Nb × 32, qui peut être égale à 128, 160, 192 ou 224, 256 bits, et de la taille de clé choisie, Nk ×32, qui peut être égale à 128, 160, 192, 224 ou 256 bits. On supposera dans la suite que la longueur de la clef est de 192 bits avec donc Nk = 6.
Extension de la clef secrète K. On écrit la clef K sous forme d’une matrice de Nk colonne de 4 bytes chacune (donc 4 lignes l’élément d’une ligne étant un mot de 8 bits) dénotés k0, ,k5
| k0 | k1 | k2 | k3 | k4 | k5 |
Ensuite cette matrice est étendue en une matrice de taille Nb(Nr +1) ou` Nr est le nombre d’étages par l’algorithme suivant
• Si i n’est pas un multiple de Nk (la longueur de la clef) alors la colonne d’indice i, ki, est la XORisation de la colonne d’indice i ? Nk, ki?Nk, et de la colonne d’indice i?1, ki?1. C’est donc l’addition bit à bit sans retenue de la colonne ki?Nk et de la colonne ki?1, ki = ki?Nk ? ki?1.
• Si i est un multiple de Nk on applique à chacun des bytes de la colonne ki?1 la permutation ?S décrite au paragraphe suivant suivie d’une rotation dans les bytes de la nouvelle colonne ki?1 et de l’addition d’une constante d’étage définie par Fieldto Binary(xj?1) pour l’étage j. On XOR le résultat obtenu avec la colonne ki?Nk.
On obtient ainsi
| k0 | k1 | k2 | k3 | k4 | k5 | ki·Nb | k(i+1)Nb?1 | |||
| clé d’étage 0 | clé d’étage i | |||||||||
L’opération SubBytes
L’opération SubBytes est la seule opération non linéaire. On suppose que le message wi est un nombre de 128 bits=16 octets, (si,j)0?i,j?3, écrit en base 2. On le réécrit sous la forme d’une matrice Si, ou` les si,j sont des
| octets. | |||
| s0,0 s Si = 1,0 s2,0 | s0,1 s1,1 s2,1 | s0,2 s1,2 s2,2 | s0,3 s1,3 s2,3 |
| s3,0 | s3,1 | s3,2 | s3,3 |
L’opération SubBytes consiste en une permutations ?S sur {0,1}8, agissant indépendamment sur chacun des octets si,j de l’étage i.
Pour décrire ?S on travaille dans un surcorps du corps à 2 éléments, F2, le corps fini à 256 éléments, F28, que l’on identifie avec les polynômes de degré ? 8, munis de l’addition et de la multiplication modulo le polynôme irréductible de F[x], x8 +x4 +x3 +x+1, cf. la paragraphe 11.6.1, page 104, de rappel sur les anneaux de polynômes,
F28 ' F2[x]/(x8 + x4 + x3 + x + 1)F2[x]
On associe à l’octet a7a6a1a0 l’élément
7
BinarytoField(a7a6a1a0) = Xaixi
i=0
du corps F28 dont l’application inverse est FieldtoBinary. On a dans le corps F28 l’opération FieldInv qui à un élément z 6= 0 du corps associe z?1 et à z = 0 associe 0.
Exemples9. Calcul dans F28. Calculons FieldInv(00000011) on a:
• FieldtoBinary(00000011)=x + 1
• FieldInv(x + 1)=x7 + x6 + x5 + x4 + x2 + x
car on a l’identité de Bézout
(x + 1)(x7 + x6 + x5 + x4 + x2 + x) + (x8 + x4 + x3 + x + 1) = 1
obtenue par l’algorithme d’Euclide ou directement, donc dans F28 ' F[x]/(x8 + x4 + x3 + x + 1)
(x + 1)?1 = (x7 + x6 + x5 + x4 + x2 + x)
et donc
• BinarytoField(x7 + x6 + x5 + x4 + x2 + x)=(11110110)
Revenons à la description de l’opération SubBytes c’est à dire à la description de la permutation ?S pour le mot de 8 bits (a7a6a1a0) consiste en
• application de BinarytoField à (a7a6a1a0) = (b7b6b1b0) qui donne a ? F28
• application FieldInv à a qui donne a?1 si a 6= 0 ou 0 si a = 0
• ajout de l’élément c = (c7c6c1c0) = BinarytoField(01100011) à a?1 pour obtenir b = (b7b6b1b0)
• application de Fieldto Binary à b c est une constante d’AES.
L’opération ShiftRows
C’est la permutation cyclique dans les lignes de la matrice Si
| a | b | c | d | ?? | a | b | c | d |
| e | f | g | h | f | g | h | e | |
| i | j | k | l | k | l | i | j | |
| m | n | o | p | p | m | n | o |
L’opération MixColumns
C’est une transformation linéaire dans les colonnes; la colonne j est transformée de la manière suivante (les calculs sont faits dans F28)
L’opération AddRoundKey
AddRoundKey[i] est l’addition de la clef obtenue à l’étage i par l’algorithme de diversification des clés, ExpandKey[i], au texte obtenu à l’issue de l’étape MixColumns.
On écrit la clef ExpandKey[i], supposée ici de 128 bits, sous la forme d’une matrice de 4 × 4 bytes et on l’ajoute au résultat de l’étape précédente par
un XOR
| a0,0 | a0,1 | a0,2 | a0,3 | M | k0,0 | k0,1 | k0,2 | k0,3 | = | b0,0 | b0,1 | b0,2 | b0,3 |
| a1,0 | a1,1 | a1,2 | a1,3 | k1,0 | k1,1 | k1,2 | k1,3 | b1,0 | b1,1 | b1,2 | b1,3 | ||
| a2,0 | a2,1 | a2,2 | a2,3 | k2,0 | k2,1 | k2,2 | k2,3 | b2,0 | b2,1 | b2,2 | b2,3 | ||
| a3,0 | a3,1 | a3,2 | a3,3 | k3,0 | k3,1 | k3,2 | k3,3 | b3,0 | b3,1 | b3,2 | b3,3 |
Si la clef avait une taille 32Nk bites on l’écrirait sous la forme d’une matrice de Nk colonnes de 4 bytes et on procéderait de même.
7.3 Infrastructure des systèmes à clef secrète.
Les infrastructures pour les systèmes à clef secrète consistent en toutes les dispositions techniques et l’organisation nécessaires pour gérer un système cryptographique à clef secrète.
Autant il est facile pour un ordinateur de retenir une clé secrète de 128 bits, autant c’est difficile pour une personne. On utilise alors le système des mots de passe. Mais pour ne pas affaiblir la sécurité du cryptosystème le mot de passe doit obéir à certaines règles
• Avoir une entropie, cf. le paragraphe 11.1.3 page 80, au moins égal à 128 bits. Pour avoir une entropie de 128 bits il suffit de choisir 22 caractères au hasard dans un alphabet de 64 lettres (minuscules, majuscules, chiffres, point et espace).
• Il doit résister aux attaques-dictionnaires.
• Un mot de passe ne doit pas être réutilisé
On peut prendre les mesures suivantes pour améliorer la sécurité d’un système de mots de passe
• On utilise le mot de passe pour calculer une clé de session qui change à chaque fois.
7.3. INFRASTRUCTURE DES SYSTEMES` A CLEF SECR` ETE`
• On rajoute des ingrédients pour éviter les attaques dictionnaires (sel).
• On itère la fonction de hachage, par exemple 1000 fois. Pour l’utilisateur le temps de calcul est à peine affecté. Pour l’attaquant qui procède par attaque-dictionnaire, c’est prohibitif.
On utilise aussi un système de gestion des clefs (Symmetric Keys Management) qui
1. émet les clefs
2. les authentifie
3. les archive
4. les garde en dépôt
Un des systèmes les plus utilisés est Kerberos, cf. [25].
Chapitre 8
Codes à clefs publiques.
Diffie et Hellman ont dégagé vers 1976 la notion de code à clef publique ou code asymétrique fondée sur la notion de fonction à sens unique.
Les codes asymétriques les plus utilisés sont
• RSA basé sur la difficulté calculatoire de la factorisation des grands entiers.
• El Gamal basé sur la difficulté calculatoire de calculer le logarithme discret dans un corps fini.
• McEliece basé sur la théorie algébrique des codes correcteurs d’er -reurs. Il repose sur la difficulté calculatoire du décodage d’un code linéaire (problème NP complet). Considéré comme suˆr il nécessite des clefs extrèmement longues 1019 bits.
• Chor-Rivest basé une instance du problème du sac à dos considéré comme suˆr.
• Les cryptosystèmes basés sur les courbes elliptiques qui sont des modifications des autres cryptosystèmes, comme El Gamal. Ils utilisent le groupe des points d’une courbe elliptique sur un corps fini au lieu du groupe multiplicatif du corps fini, par exemple Menezes-Vanstonne.
8.1 Principe des codes à clef publique.
8.1.1 Fonctions à sens unique.
On cherche une fonction f entre des ensembles P et E telle que
46
• le calcul de f(x) pour x ? P se fait en temps polynomial en fonction de la taille des données.
• le calcul de f(?1)(y) pour y ? E ne se fait pas en temps polynomial en fonction de la taille des données. Le plus souvent la fonction f possède une porte dérobée (trapdoor) qui permet de calculer facilement f?1(y) lorsqu’on a une information supplémentaire comme la clef secrète.
Autrement dit on cherche des fonction f : P ? E appartenant à la classe des problèmes P (calculables en temps polynomial en fonction de la taille des données) et telle que la fonction réciproque (ou l’image réciproque si ne suppose pas f bijective) f(?1) appartienne à la classe des problèmes NP, (non calculables en temps polynomial en fonction de la taille des données, mais vérifiables en temps polynomial).
La mise au point de telles fonctions a révolutionné la cryptographie et élargi son champ d’application.
8.2 Le système RSA.
Le système RSA est nommé d’après le nom de ses inventeurs: Rivest, Shamir, Adleman.
Il est basé sur la fonction à sens unique produit de deux entiers
f : N × N ?? N
(n,m) 7?? f(n,m) = n × m
sa fonction réciproque étant la décomposition d’un nombre entier en un produit de facteur premier, cf la section arithmétique dans les compléments de mathématiques, section 11.3 page 86.
Le calcul du produit de deux nombres entiers est une opération “facile”, “rapide”, “calculatoirement facile” (c’est à dire faisable en temps polynomial en fonction de la taille des données) alors que la décomposition en facteurs premiers n’est pas “facile”, est “lente”, “calculatoirement difficile” (c’est à dire qu’elle n’est pas faisable en temps polynomial en fonction de la taille des données)
8.2.1 Description du cryptosystème RSA.
On a un ensemble (Ai)i?I de correspondants (personnes physiques ou ordinateurs). Le principe du cryptosystème RSA est le suivant
• Chacun des correspondants Ai choisit deux nombres premiers pi et qi distincts. On note ni = piqi, le module du cryptosystème de Ai et ?(ni) = (pi ? 1)(qi ? 1), l’indicatrice d’Euler de ni.
• Ai choisit ensuite un nombre ei l’exposant de la clé publique premier avec ?(ni) (autrement dit le Plus Grand Commun Diviseur (PGCD ou GCD en anglais) de ei et ?(ni) est 1. On note ce PGCD ei??(ni) = 1) en pratique on impose de plus 1 ? ei ? ?(ni) ? 1.
• Puis Ai calcule l’inverse di de ei modulo ?(ni), di est appelé exposant de la clé secrète c’est à dire en pratique, on cherche di ? N tel qu’il existe ki ? N avec di × ei = 1 + ki?(ni) et 1 ? di ? ?(ni) ? 1
• Chacun des correspondants Aj publie dans un annuaire public les nombres nj et ej qui forment sa clé publique de chiffrement et garde secret pj, qj et dj qui forment sa clé secrète de déchiffrement.
En pratique on choisit les nombres premiers pi et qi de taille comparable de telle sorte que leur produit ni = piqi soit un nombre d’au moins 300 chiffres en base 10 et plutôt 500 pour une protection longue.
8.2.2 Protocole d’envoi d’un message en RSA.
Alice veut envoyer un message M à Bob. La clef publique d’Alice (resp Bob) est (na,ea), (resp. (nb,eb)), sa clef secrète est (pa,qa,da) (resp. (pb,qb,d)b). Elle suit le protocole suivant
1. Alice commence par transformer le message en une suite de chiffres, par exemple en rempla¸cant les lettres et les différents symboles utilisés par des chiffres (de 0 à 255 dans le cas du code ASCII).
2. Alice regarde dans l’annuaire public la clé de chiffrement nb,eb de Bob. Elle découpe le message M en blocs M de taille approximativement nb.
3. Elle calcule
fb(M) = M0 ? Meb mod nb
et envoie M0 = fb(M) à Bob.
4. Pour récupérer le texte en clair Bob calcule
fb?1(M0) = (M0)db = fb(M)db ? Mebdb = M1+kb?(nb) mod nb
D’après le théorème d’Euler (cf. théorème 11.3.19 page 97) on a
M?(nb) ? 1 mod nb
et par conséquent
fb?1(M0) ? M mod nb
Si la taille de M est adaptée à celle de nb, il n’y a pas d’ambiguitét Bob récupère donc bien le message d’Alice.
8.2.3 Protocole de signature RSA.
Le cryptosystème RSA permet aussi facilement de réaliser l’authentification de l’expéditeur (en admettant que sa clef privée n’est utilisée que par lui).
1. Alice commence par découper le message M en blocs M de taille bien choisie par rapport à na et nb. Elle crypte chaque bloc du message avec sa clé secrète, da, elle obtient à partir du texte en clair M un premier texte crypté, M00
M00 = fa?1(M) ? Mda mod paqa
2. Avec la clé publique de Bob, elle crypte M00 et obtient un deuxième texte crypté, M0
qui constitue sa signature du message M.
3. Elle crypte alors le message M avec la clé publique de Bob en suivant le protocole précédent et obtient le texte crypté du message fb(M)
fb(M) = Meb mod nb
4. Elle envoie à Bob le couple
(fb(M),M0)
qui constitue le message chiffré et signé d’Alice à Bob.
Pour décoder et vérifier la signature qui authentifie l’expéditeur du message, d’Alice, Bob effectue les opérations suivantes
1. Il calcule d’une part
(Si le choix de la taille des blocs M est bien choisie par rapport à na et nb, il n’y a pas d’ambiguité au décodage)
2. Il calcule d’autre part, en décodant comme au paragraphe 8.2.2,
fb?1fb(M) ? M mod nb
3. Il compare les deux résulats obtenus. S’il constate que M = M, c’est à dire que les deux résultats sont les mêmes, il est suˆr alors que le message vient d’Alice car seule Alice connait
c’est à dire sa clé secrète. De plus il est suˆr que le message n’a pas été altéré.
8.2.4 Exemple académique de codes RSA.
Alice publie sa clé publique (nA,eA) = (65,5), sa clef secrète est dA.
Bob publie sa clé publique (nB,eB) = (77,7), sa clef secrète est dB.
Pour trouver les clefs secrètes on décompose en un produit de facteurs premiers nA et nB
nA = 13 · 5 et nB = 7 · 11
On calcule ensuite les indicatrices d’Euler correspondantes
?(nA) = 12 × 4 = 48 et ?(nB) = 6 × 10 = 60
En utilisant l’algorithme de PGCD décrit au paragraphe 11.3.3 page 89 (ou directement) on calcule dA
5 × 29 = 145 = 1 + 3 × 48 =? dA = 29
respectivement dB
7 × 43 = 301 = 5 × 60 + 1 =? dB = 43
Alice veut transmettre le message 3 à Bob. Elle calcule donc
37 ? 31 mod 77 = 7 × 11
et elle envoit 31 à Bob. Bob décode en calculant 3143 ? 311+2+8+32 ? 31 · 37 · 58 · 37 · 31 ? 3 mod 77
(remarquer la manière de calculer une puissance).
Si Alice veut signer le message elle n’envoie pas seulement 31, mais elle calcule d’abord
puis elle calcule
puis elle envoie à Bob le couple
(31,27)
constitué de la signature et du message. Pour décoder Bob calcule
et
3143 ? 3 mod 77
et il constate que les deux résultats coincident. L’expéditeur du message est bien Alice.
Remarque8.2.1. Pour signer le message Alice aurait pu aussi bien mener les calculs dans l’ordre inverse, c’est à dire calculer d’abord avec la clé publique de Bob
puis avec sa clé secrète da elle crypte et obtient un deuxième texte crypté, Mf0
qui constitue sa signature du message M.
Elle crypte alors le message M avec la clé publique de Bob en suivant le protocole précédent et obtient le texte crypté du message fb(M)
fb(M) = Meb mod nb
Elle envoie à Bob le couple
Bob décode en calculant d’une part
fa(Mf0) ? Mf00 mod na
fb?1(fa((Mf0)) = fb?1(fa(fa?1(fb(M)))) ? M mod nb
Les deux protocoles ont leurs avantages et inconvénients. On préfère en général le premier protocole car il suit de plus près la manière traditionnelle de signer une lettre: on signe d’abord avant de la mettre dans l’enveloppe. Le second protocole consiste à mettre la lettre dans l’enveloppe et à signer l’enveloppe.
8.2.5 Exemple de code RSA.
On choisit un alphabet à 40 lettres
A= 0, B= 1, C= 2, D= 3, E= 4, F= 5, ,
, X= 23, Y= 24, Z= 25, =26, .= 27, ?= 28, euros= 29, 0= 30, 1= 31, , 8= 38, 9= 39,
On choisit comme clé publique le couple
n = 2047, e = 179
on a
402 ? 2047 ? 403
on choisit donc de découper les messages en clair en blocs de deux lettres et les messages chiffrés en blocs de trois lettres.
On écrit chaque bloc de deux symboles clairs X1X2 sous la forme 40x1 +x2 ou` xi est le nombre entre 1 et 39 correspondant à Xi.
On écrit chaque bloc de trois symboles codés Y1Y2Y3 sous la forme 402y1 + 40y2 + y3 ou` yi est le nombre entre 0 et 39 correspondant à Yi.
Le message clair est
ENVOYEZ euros2500.
Pour le coder on considère les blocs
| EN = 4 × 40 + 13 = 173, VO = 21 × 40 + 14 = 854, YE = 24 × 40 + 4 = 964, Z = 1026, euros2 = 1192, 50 = 1430, 0. = 1110 | |
| Codage du message | |
| EN 7? (173)179 | mod 2047 = 854 = 0 × 402 + 21 × 40 + 14 = AVO |
| VO 7? (854)179 | mod 2047 = 1315 = 0 × 402 + 32 × 40 + 35 = A25 |
| YE 7? (964)179 | mod 2047 = 452 = 0 × 402 + 11 × 40 + 12 = ALM |
| Z 7? (1026)179 | mod 2047 = 1295 = 0 × 402 + 32 × 40 + 15 = A2P |
| euros2 7? (1192)179 | mod 2047 = 511 = 0 × 402 + 12 × 40 + 31 = AM1 |
| 50 7? (1430)179 | mod 2047 = 1996 = 1 × 402 + 9 × 40 + 36 = BJ6 |
| 0. 7? (1110)179 | mod 2047 = 1642 = 1 × 402 + 1 × 40 + 2 = BBC |
Le message codé est donc
AVOA25ALMA2PAM1BJ6BBC
Pour décoder on factorise
2047 = 23 × 89 =? ?(2047) = 22 × 88 = 1936
et on déduit par l’algorithme d’Euclide que
d = 411.
Remarque8.2.2. En fait les paramètres de ce code sont mal choisis car 22 divise 88 et donc on peut prendre pour d n’importe quel inverse de 179 modulo 88 comme par exemple 59. On constate que 411 = 59 + 4 × 88
8.2.6 Sécurité du système RSA.
La sécurité de RSA repose sur les faits suivants:
• on ne sait pas décoder sans connaˆ?tre l’exposant de la clé secrète d
• trouver d équivaut à factoriser n = pq
• on ne connait pas d’algorithme polynomial en temps en fonction de la taille des données (c’est à dire de la longueur des nombres n et e) pour calculer d c’est à dire pour factoriser n, les meilleurs sont en
opérations.
on dit que l’algorithme est sous-exponentiel
Ce sont des faits d’expérience pas des théorèmes.
Depuis sa création le système RSA a résisté à toutes les attaques de manière satisfaisante si l’on choisit bien p, q et e.
Pour construire et utiliser un code RSA on a besoin de savoir faire rapidement (c’est à dire en temps polynomial au plus) les opérations suivantes:
• construire des grands nombres premiers
• calculer des PGCD
• faire de l’arithmétique modulaire (addition, multiplication, exponentiation)
Pour évaluer et tester la sécurité du code RSA, il faut en particulier
• évaluer la rapidité des algorithmes de factorisations de grands nombres entiers
• Démontrer que la clef secrète de déchiffrement d ne peut pas être obtenue sans factoriser n = pq et plus généralement qu’elle ne peut pas être calculer en temps polynomiale en fonction de n.
• montrer que l’on ne peut pas décoder un message sans la clef secrète
8.3 Le cryptosystème El Gamal.
Le cryptosystème El Gamal est basée sur la fonction à sens unique logarithme discret. On considère un groupe cyclique fini, G, de cardinal n engendré par un générateur, g. Donc
On suppose que le calcul de gi est “facile”, “rapide” “calculatoirement facile” (c’est à dire faisable en temps polynomial en fonction de la taille des données) mais que le calcul de i connaissant gi n’est “pas facile”, est “lent”, “calculatoirement difficile” (c’est à dire: n’est pas faisable en temps polynomial en fonction de la taille des données). Si a = gi, i est appelé le logarithme discret de a.
On utilise les deux réalisations suivantes de G. On considère un nombre premier p et on choisit
c’est à dire que le G est le groupe des éléments inversible pour la multiplication de Z/pZ les entiers modulo p, pour la définition voir dans les compléments mathématiques, le paragraphe sur les congruences 11.3.4 page 92.
D’après un théorème de Gauss, théorème 11.3.13 page 94, le groupe multiplicatif de Z/pZ est cyclique et le calcul de gi mod p est rapide alors qu’on ne connait pas d’algorithme en temps polynomial pour calculer i connaissant a = gi pour de bons choix de p. Plus généralement on peut considérer le groupe multiplicatif des éléments inversibles d’un corps fini à q = ps
éléments, Fq.
Une autre réalisation est comme groupe G le groupe des points d’une courbe elliptique sur un corps fini, E(Fq) qui donne lieu aux cryptosystèmes elliptiques, cf le paragraphe 11.7.1 page 117. Ils se développent actuellement car ils possèdent des avantages en terme de taille de clé et de sécurité prouvée.
8.3.1 Description du cryptosystème El Gamal.
On considère le cryptosystème suivant: Soit p un nombre premier tel que le problème du logarithme discret dans Z/pZ soit difficile.
Soit g une racine primitive modulo p, cf. le théorème 11.3.13 page 94, c’est à dire que g est un générateur du groupe cyclique (Z/pZ)?.
Soit, les messages en clair, et soit les messages cryptés et enfin soit l’espace des clefs
(
(p,g,?) est la clef publique
ou`
? est la clef secrète
Alice veut transmettre un message, M, à Bob
1. Bob choisit un grand nombre premier pb, un générateur gb du groupe cyclique multiplicatif et un entier ?b inférieurs à p
2. Bob calcule ; alors le triplet (?b,gb,pb) constitue sa clef publique, ?b est sa clef secrète.
3. Alice découpe le message M en blocs M de taille inférieure à pb, elle choisit un entier ka (inférieur à pb ? 1) pour chacun des blocs M et calcule
y1 ? gbka (mod pb) et y2 = ?bkaM
La paire eKb(M,ka) = (y1,y2) est le message codé qu’Alice envoie à Bob.
Pour décoder
1. Bob calcule
Comme) on a:
dK(y1,y2) = y2(y1?b)?1 ? ?bkaM(gbka?b)?1 ?
? gb?bkaMgb??bka ? M mod p
et comme M est inférieur à pb il n’y a pas d’ambiguité dans le décodage.
Pour une bonne sécurité, Alice doit changer souvent ka.
8.3.2 Signature El Gamal.
On reprend les notations précédentes. Soit M un bloc d’un message M qu’Alice veut transmettre en le signant à Bob.
1. Alice choisit elle-aussi un grand nombre premier pa tel que le problème du logarithme discret dans soit difficile.
2. Elle choisit aussi un générateur ga de et un entier 0 ? ?a ? pa ? 2 et elle calcule ?a = ga?a.
Elle dispose ainsi elle aussi d’une clef publique (pa,ga,?a) et d’une clef privée
(secrète) ?a. Pour signer le message M, Alice réalise les opérations suivantes
1. elle choisit secret et premier à pa ? 1.
2. elle calcule
?a ? gaka0 mod pa
?a ? (M ? ?a?a)ka0 ?1 mod (pa ? 1)
3. la signature du bloc M est alors sign) avec
4. Puis elle envoie le couple
c’est à dire le quadruplet .
On constate que
Remarque8.3.1. La conditionpremier à pa ?1 est nécessaire car Alice utilise pour calculer ?a la quantité
Cette procédure réalise bien une signature du bloc M. Pour vérifier la signature et décoder Bob suit le protocole suivant:
1. Bob re¸coit le couple constitué par le message crypté par Alice de la signature de ce message c’est à dire le quadruplet .
2. Il décode le message à l’aide de sa clé secrète et récupère M.
3. Il calcule
et il vérifie que
S’il en est ainsi il est suˆr que l’expéditeur du message est bien Alice.
On constate que cette procédure réalise bien une signature du message M car pour fabriquer le couple (?a,?a) Alice a utlisé sa clef secrète et si l’on remplace dans la formule donnant ?a la clé secrète ?a par un autre nombre compris entre 0 et pa ? 1 on n’aura plus l’égalité
8.3.3 Sécurité du système EL Gamal.
La sécurité du cryptosystème EL Gamal repose sur les faits suivants:
• on ne sait pas décoder sans connaˆ?tre la clé secrète ?
• trouver ? équivaut à trouver le logarithme discret de ? = g? dans (Z/pZ)?
• on ne connait pas d’algorithme polynomial en temps en fonction de la taille des données (c’est à dire de la longueur du nombre p) pour calculer ?. Les meilleurs sont en
opérations.
Ce sont des faits d’expérience pas des théorèmes.
8.3.4 Exemple académique de code El Gamal.
Alice et Bob veulent correspondre en employant le système El-Gamal. Alice choisit comme paramètres
pa = 263, ga = 5, ?a = 47
Bob choisit comme paramètres
pb = 257, gb = 5, ?b = 67
On vérifie facilement que pa et pb sont des nombres premiers, que ga et gb sont respectivement des générateurs des groupes cycliques Z/paZ et Z/pbZ. Il suffit pour cela de vérifier (par exemple à l’aide d’une table ou d’un système de calcul faisant de l’arithmétique modulaire) que
pour tout diviseur non trivial da de pa ? 1 et tout diviseur non trivial db de pb ?1. En effet d’après le corollaire 11.3.20 le plus petit entier non nul e tel que) est un diviseur de pa ? 1.
Alice calcule ) = 40 et sa clef publique est
Ka = (pa = 263,ga = 5,?a = 40)
sa clé secrète est ?a = 47.
Bob calcule ) = 201 et sa clef publique est
Kb = (pb = 257,gb = 5,?b = 201)
sa clé secrète est ?b = 67.
On suppose qu’Alice et Bob s’envoient des nombres de deux chiffres en base 10. Alice envoie à Bob le message M qu’elle code en (y1,y2) = (76,251) à l’aide la clé publique de Bob et d’un ka qu’elle garde secret. Bob décode le message en effectuant l’opération y2(y1?b)?1 (mod 257) = 251 × 76?67 (mod 257)
= 251 × 76256?67 (mod 257)
= 251 × 76189 (mod 257) = 251 × 155 (mod 257)
= (?6) × 155 (mod 257) = 98
.Le message en clair d’Alice est M = 98.
On peut retrouver le paramètre ka à l’aide d’une table des puissances de gb (mod 257). On sait que
On trouve à l’aide d’une table ou d’un logiciel de calcul d’arithmétique modulaire ka = 139.
Si Alice veut envoyer le message M = 87 à Bob avec les mêmes paramètres, y compris ka, elle effectue le calcul
z1 = y1 = gbka (mod 257) = 76
z2 = ?bka × 87 (mod 257) = 201139 × 87 (mod 257) = 173
Pour un bon choix de p le système El-Gamal resiste bien aux attaques. Comme le système RSA il est assez lent et nécessite des clefs longues 1024 à 2048 bits actuellement). Il se transpose sans difficulté à n’importe quel groupe cyclique ou` le problème du logarithme discret est difficile, en particulier pour le groupe des points d’une courbe elliptique sur un corps fini. Avec ce groupe malgré les difficultés algorithmique on a de bons codes avec des clefs courtes (128 à 256 bits actuellement) dont la sécurité peut être au moins partiellement prouvée.
8.4 Infrastructure des systèmes à clef publique.
Les infrastructures des systèmes à clef publique ou PKI (Public Key Infrastructure) consistent en toutes les dispositions techniques et organisationnelles nécessaires pour gérer un système cryptographique à clef publique.
On a un ensemble d’interlocuteurs en réseau qui se sont mis d’accord sur un cryptosystème à clef publique (par exemple RSA), sur une fonction de hachage (cf. le chapitre 9 page 63) et sur un protocole de signature. On suppose que chacun d’entre eux dispose d’une paire (Ke,Kd) (clé publique, clé sécrète), (clé de chiffrement, clé de déchiffrement) et que chacun d’entre eux est capable de chiffrer, déchiffrer et signer.
Du fait que les clés publiques ne sont pas confidentielles, il n’est pas nécessaire de les crypter pour les transmettre. Mais il est très important et même vital pour la sécurité des transmissions de s’assurer de l’authenticité des clés ainsi transmises.
En effet si Alice désire transmettre sa clef publique à Bob, n’importe quel opposant, Martin par exemple, peut intercepter le message la contenant. Martin peut ensuite envoyer un message à Bob en se faisant passer pour Alice et contenant sa propre clé publique et donnant comme adresse de retour sa propre adresse. Ainsi il est capable de lire les messages cryptés que Bob envoie à Alice avec la soit-disant clé publique d’Alice que Bob croit posséder. Une fois qu’il les a décryptés et lu il peut les envoyer à Alice dont il possède la clé publique en les modifiant s’il l’estime nécessaire.
Il faut donc d’une certaine manière faire un lien entre chacun des participants au réseau et sa clé publique. Pour cela on utilise les certificats.
Un certificat consiste en une clef publique et une identité digitale (par exemple une suite de symboles contenant le nom du propriétaire de la clef, de la même manière qu’on met une étiquette sur une clé ordinaire), le tout étant cacheté à l’aide de la signature digitale d’une personne ou d’une organisation en laquelle on a confiance et appelée un Tiers de Confiance (Trusted Third Party ou TTP).
8.4. INFRASTRUCTURE DES SYSTEMES` A CLEF PUBLIQUE`
Pratiquement on peut par exemple concaténer, mettre bout à bout, la clef publique, le nom de son possesseur et signer le message obtenu à l’aide de la clef privée du Tiers de Confiance (il faut que personne ne puisse usurper l’identité du Tiers de Confiance).
Il existe plusieurs modèles de réseau avec Tiers de Confiance, avec deux modèles extrèmes, le modèle hierarchique et le modèle distribué. Un système très employé de système hiérarchique de Tiers de Confiance est le modèle X.509, [25].
Les fonctions principales d’un PKI sont
• Emission de paires de clefs (clé publique, clé privée)´
• Attribution d’identifiants uniques aux participants au réseau
• Conservation des clefs
1. Dépot de clefs, utile quand il s’agit de garantir la continuité d’un service en cas de changement de titulaire
2. Archivage des clefs, utile pour pouvoir relire de vieux messages
3. Sauvegarde des clefs, utile en cas de perte de clef
4. Récuperation de clef perdues ces fonctions ne sont pas très distinctes
• Emettre et publier des certificats´
• Révoquer les certificats
• fixer leur durée de validité
• Archiver les certificats expirés (important pour les problèmes de nonrépudiation)
• Donner une datation sécurisée
Système hiérarchique de Tiers de Confiance
Système non-hiérarchique de Tiers de Confiance
Chapitre 9
Fonctions de Hachage.
Les procédures de signature précédentes ont un couˆt prohibitif pour signer des longs messages car la signature est aussi longue que le message. On double donc la longueur du texte à crypter.
Pour réduire la longueur de la signature on peut utiliser une fonction de hachage cryptographique (hash function en anglais), h, ou fonction de condensation. C’est une fonction à sens unique qui sera publique dans les applications.
Les fonctions de hachage ont d’autres applications cryptographiques que la signature, cf le chapitre 10 page 68 sur les protocoles cryptographiques.
Une fonction de hachage est une fonction rapide à calculer mais dont l’image réciproque est dans la classe des problèmes calculatoirement difficiles (la classe NP). Ell transforme un message de longueur arbitraire en une empreinte numérique ou code d’authentification du message de taille fixée, 160 bits en général actuellement. Pour des raisons de sécurité on tend à augmenter la taille de l’empreinte.
Le schéma de calcul d’une signature avec une fonction de hachage est le suivant:
| message | x ? | longueur arbitraire |
| empreinte numérique | z = h(x) ? | 160 bits |
| signature | y = signK(z) | 320 bits |
63
CHAPITRE 9. FONCTIONS DE HACHAGE
En réalité une fonctions de hachage prend un message x de taille inférieure à N fixé qu’elle transforme en une empreinte de taille 160 bits (ou 256 ou 384 ou 512).
Il existe des techniques classiques, cf. [23], pour étendre les fonctions de hachage de domaine de départ fini (fonction de compression) ? N en des fonctions de hachage dont le domaine de départ est constitué de messages de longueur arbitraire. Elles sont appelées alors fonctions de hachage itérées. La principe pour l’itération est le suivant. On suppose que la fonction h peut recevoir deux entrées
• une empreinte hi?1
• un bloc M de taille N
et donner en sortie une empreinte hi.
M ?? ?? h hi?1 ??i |
On peut supposer que cette extension des fonctions de hachage est déjà faite.
Lorsqu’Alice souhaite envoyer un message signé, x, elle calcule d’abord l’empreinte numérique, z = h(x), elle signe avec y = signK(z) et transmet le couple (x,y) par le canal de communication.
Tout le monde peut vérifier la signature en calculant l’empreinte z = h(x) et en utilisant le procédé de vérification de la signature verK(z,y).
9.1 Construction des fonctions de hachage.
La fonction de hachage doit être construite avec soin pour qu’elle n’affaiblisse pas le protocole de signature. Un opposant comme Martin ne doit pas pouvoir forger la signature d’Alice.
Comme une fonction de hachage n’est évidemment pas injective, il existe des couples de messages x0 et x tels que h(x0) = h(x). L’attaque la plus évidente consiste pour Martin à partir d’un message signé (x,y) authentique (y = signK(x)) précedemment calculé par Alice à calculer z = h(x) et à chercher x0 6= x tel que h(x) = h(x0). Si Martin y parvient (x0,y) est un message valide.
Donnons tout d’abord quelques définitions de qualités que l’on peut exiger d’une fonction de hachage.
9.1. CONSTRUCTION DES FONCTIONS DE HACHAGE
Définition 9.1.1.Une fonction de hachage h est à collisions faibles difficiles si étant donné un message x, il est calculatoirement difficile d’obtenir un message x0 6= x tel que h(x) = h(x0).
Définition 9.1.2.Une fonction de hachage h est à collisions fortes difficiles s’il est calculatoirement difficile d’obtenir deux messages différents x et x0tels que h(x) = h(x0)
Définition 9.1.3.Une fonction de hachage est une fonction de hachage à sens unique si étant donnée une empreinte numérique z, il est calculatoirement difficile de trouver un message x tels h(x) = z
Si une fonction de hachage est à collisions fortes difficiles elle est bien suˆr à collisions faibles difficiles, mais aussi à sens unique.
9.1.1 Attaques des anniversaires.
Une fonction de hachage doit aussi résister aux attaques des anniversaires.
Une méthode simple pour obtenir des collisions, i.e. des messages x et x0 tels que h(x) = h(x0) est l’attaque des anniversaires décrite ci-dessous.
On a une fonction de hachage h : X ? Z ou` |X| = m < +? et |Z| = n et m ? 2n. Dans ces conditions il y a au moins n collisions.
On va trouver la borne inférieure de la probabilité de trouver une collision en tirant k messages aléatoires distincts. Cette borne dépend de k et n mais pas de m. On fait l’hypothèse simplificatrice que |h?1(z)| ? m/n.
Il est alors facile de calculer la probabilité pour que k éléments zi ? Z soient tous distincts si l’on tire au hasard k éléments xi ? X.
On ordonne les zi en z1, , zk. Le premier tirage z1 est arbitraire; la probabilité pour que z2 6= z1 est 1 ; la probabilité pour que z3 soit distinct de
z1 et z2 est 1 , etc
La probabilité de collision est donc
avec un peu d’analyse élémentaire on voit facilement en utilisant l’approximation
e?x ? 1 ? x si x petit
CHAPITRE 9. FONCTIONS DE HACHAGE
que:
La probabilité d’une collision est donc 1 . Si l’on veut que cette probabilité soit inférieure à ? alors il suffit de prendre
Par exemple dans une assemblée de 23 personnes la probabilité d’avoir deux dates d’anniversaire égales est supérieure à 1/2.
Une empreinte de 40 bits est vulnérable à une attaque des anniversaires avec probabilité supérieure à 1/2 en utilisant seulement 220 messages aléatoires. Pour une empreinte de 128 bits il faut 264 messages aléatoires. Le choix d’une empreinte de 160 bits donne une bonne résistance aux attaques anniversaires. Mais l’augmentation de la puissance de calcul disponible pour un attaquant pousse à augmenter la taille des empreintes, c’est pourquoi AES prévoit des empreintes de 256 à 512 bits.
9.1.2 Exemple académique de fonction de hachage.
Fonction de hachage de Chaum-van Heijst-Pfitzmann. Elle n’est pas utilisée en pratique car trop lente.
Soit p = 1 + 2q un grand nombre premier tel que q soit aussi premier. Soit ? et ? deux éléments primitifs de (Z/pZ)?. La valeur de log? ? n’est pas publique et l’on suppose qu’elle est calculatoirement difficile à obtenir.
On démontre que la fonction de hachage h : {0,1 ,q ? 1} × {0,1 ,q ? 1} ?? (Z/pZ)?
(x1,x2) 7?? h(x1,x2) = ?x1?x2
résiste aux collisions si le calcul de log? ? est difficile.
9.1.3 Fonction de hachage standard.
Un standard actuel en matière de fonction de hachage est SHA-1 (Secure Hash Algorithm) avec une empreinte de taille 160 bits, faisant suite aux standard MD4 (1990), MD5 (1992), SHA (1995), cf. [23].
9.1. CONSTRUCTION DES FONCTIONS DE HACHAGE
Depuis 2001, une nouvelle version de SHA-1, SHA-2, ainsi que les versions SHA-256, SHA-384 et SHA-512 sont en cours de validation (256, 384, 512 est la taille en bits de l’empreinte).
Chapitre 10
Quelques protocoles cryptographiques.
10.1 Protocoles de signature.
Nous avons déjà décrit des protocoles de signature RSA et El Gamal. Nous allons décrire un protocole de signature utilisable avec les cryptosystèmes symétriques et nous allons rappeler le protocole de signature pour un cryptosystème à clef publique déjà décrit.
10.1.1 Protocole de signature à clef privée.
Signature d’un document à l’aide d’un cryptosystème à clef secrète et d’un arbitre ou tiers de confiance.
Les utilisateurs d’un cryptosystème à clef publique se choisissent un arbitre, Yvan, c’est à dire une entité (personne, organisation, machine) en qui ils ont toute confiance.
Yvan communique avec Alice et Bob. Il partage une clé secrète KA avec Alice et une clé secrète KB avec Bob.
Le protocole de signature est alors le suivant
1. Alice chiffre son message pour Bob avec la clé KA et envoie le résultat à Yvan.
2. Yvan déchiffre le message avec KA et garde l’original.
3. Yvan assemble le message avec un avis certifiant que le message vient d’Alice. Il chiffre le tout avec KB et l’envoie à Bob.
4. Bob déchiffre le message d’Yvan avec KB. Il lit le message et le certificat d’Yvan.
68
10.1. PROTOCOLES DE SIGNATURE
5. Comme il a confiance en Yvan, il admet que le message re¸cu est conforme à l’original et vient bien d’Alice.
Ce protocole est-il suˆr?
Les 3 qualités que l’on demande à un cryptosystème sont-elles bien présentes:
• Intégrité des données.
• Identités des différents interlocuteurs.
• Non-répudiation.
Bien suˆr on suppose qu’Alice garde bien secrète la clef qu’elle partage avec Yvan et qu’Yvan est vraiment un tiers de confiance.
1. La signature est authentique car Yvan est respecté et seul Alice et lui connaissent KA donc la message vient bien d’Alice.
2. La signature est infalsifiable. Seule Alice (et Yvan qui est insoup¸connable) connait KA, donc seule Alice peut envoyer le message codé avec KA.
3. La signature n’est pas réutilisable pour un autre message. Si Bob essaie de prendre le certificat d’Yvan et de l’associer à un autre message censé provenir d’Alice, cette dernière crierait à l’imposture. L’arbitre demandera alors à Bob de produire le texte en clair. Il le chiffrerait avec KA et comparerait avec le message original d’Alice. Il verra qu’ils sont différents et en informera qui de droit.
4. Le document est immuable. Si Bob falsifiait le message après l’avoir re¸cu, Yvan pourrait dévoiler l’imposture comme ci-dessus.
5. La signature ne peut pas être reniée. Si Alice prétend ne pas avoir envoyé le message, le certificat d’Yvan prouverait le contraire (tout le monde a confiance en Yvan).
Bob pourrait nier avoir re¸cu le message mais alors un système d’accusé de réception permettrait d’éviter ce problème.
10.1.2 Protocole de signature à clef publique.
Le protocole est simple
1. Alice chiffre le document d’une part avec sa clé privée, signant ainsi le document, et d’autre part avec la clé publique de Bob
2. Alice envoie les deux document à Bob.
3. Bob déchiffre le premier document avec la clé publique d’Alice et le second avec sa clé privée. Si les deux sont identiques il est suˆr qu’Alice est l’expéditeur.
Ce protocole est-il suˆr?
Les 3 qualités que l’on demande à un cryptosystème sont-elles bien présentes:
• Intégrité des données.
• Identités des différents interlocuteurs.
• Non-répudiation.
Bien suˆr on suppose que chacun des correspondants ne communique à personne sa clé secrète
1. La signature est authentique: quand Bob vérifie le message avec la clé publique d’Alice, il est suˆr que seule Alice pouvait l’avoir crypté avec sa clé privée.
2. La signature est infalsifiable. Seule Alice connait sa clé privée.
3. La signature n’est pas réutilisable. La signature est une fonction du document et elle ne peut pas être transférée sur n’importe quel autre document.
4. Le document est immuable. Si Bob falsifiait le message après l’avoir re¸cu, il ne pourrait pas le signer car la clé privée d’Alice n’est connue que d’elle seule.
5. La signature ne peut pas être reniée. Bob n’a pas besoin de l’aide d’Alice pour vérifier sa signature.
10.2 Protocoles de datation.
Dans certaines circonstances Bob peut duper Alice.
Il peut réutiliser le document (par exemple un chèque signé) et le présenter plusieurs fois à la banque. Pour l’éviter les signatures numériques comportent souvent une datation (date+heure). Cette datation de la signature est attachée au message et signée avec lui.
La banque stocke ces datations dans une base de données.
10.3. SIGNATURE AVEC FONCTION DE HACHAGE
10.2.1 Protocole de datation.
On peut confier la datation des documents à un service officiel de datation. Bob veut dater une signature du message x. Il dispose d’une fonction de hachage à sens unique, h. Il suit alors le protocole suivant
1. Bob calcule z = h(x) et y = sigK(z)
2. Bob soumet (z,y) au service de datation.
3. Le service de datation ajoute la date D et signe le triplet (z,y,D)
Bob peut aussi dater un document, x, seul. Pour cela il collecte un certain nombre d’ informations publiques récentes (qui n’auraient pas pu être prédites auparavant), notée pub. Par exemple les derniers résultats des courses hippiques et les cours actuels de la bourse. Il dispose aussi d’une fonction de hachage publique à sens unique, h. Bob suit alors le protocole suivant:
1. Bob calcule z = h(x)
2. Bob calcule z0 = h(z||pub)
3. Bob calcule y = sigK(z0)
4. Bob publie (z,pub,y) dans le prochain quotidien
La date de la signature de Bob est comprise entre la date des informations pub et la date de parution du quotidien.
10.3 Protocole de signature à clef publique et fonction de hachage.
Les algorithmes à clef publique sont trop lents pour signer de longs documents.
Pour gagner du temps les protocoles de signature numérique sont souvent réalisés avec des fonctions de hachage à sens unique.
Au lieu de signer le document Alice signe l’empreinte du document en suivant le protocole suivant:
1. Alice calcule à l’aide de la fonction de hachage à sens unique, l’empreinte du document.
2. Alice chiffre, à l’aide de l’algorithme de signature numérique, cette empreinte avec sa clef privée, signant par la même occasion le document.
3. Alice envoie le document et l’empreinte signée à Bob (à l’aide de la clef publique de Bob).
4. Bob calcule, à l’aide de la fonction de hachage à sens unique, l’empreinte du document qu’Alice lui a envoyé. Ensuite à l’aide de l’algorithme de signature numérique, il déchiffre l’empreinte signée avec la clef publique d’Alice. La signature est valide si l’empreinte de la signature est la même que l’empreinte qu’il a produite.
Avantage de ce procédé:
• rapidité de la transmission et de la comparaison des empreintes car une empreinte ne comporte que 160 bits ou au plus 512.
• confidentialité car la signature peut être gardée à part du message. On peut donc vérifier l’existence du document sans stocker son contenu.
10.4 Fonction de hachage et mot de passe.
Pour accéder à un ordinateur (ou à un distributeur de billet) on utilise souvent un mot de passe qui doit être reconnu par l’ordinateur. S’il est stocké dans l’ordinateur il y a danger pour la sécurité car un ordinateur peut être facilement infiltré (virus). Grâce à la fonction de hachage on peut résoudre à ce problème:
On dispose d’une fonction de hachage à sens unique, h. L’ordinateur ne stocke pas le mot de passe mp d’Alice mais le résultat de la fonction de hachage à sens unique appliquée à mp. Le protocole est donc le suivant:
1. Alice envoie son mot de passe mp à l’ordinateur.
2. L’ordinateur calcule h(mp)
3. L’ordinateur compare le résultat de ce calcul à celui qu’il a dans sa base de données.
Ce protocole permet de se défendre contre le vol de la base des données des mots de passe des utilisateurs.
En fait on peut encore améliorer ce protocole avec les protocoles de preuve sans transfert de connaissance.
10.5. PREUVE SANS TRANSFERT DE CONNAISSANCE
10.5Preuve sans transfert de connaissance.
Un jeu de Pile ou face par Téléphone. Considérons la situation suivante, cf.
[27].
Alice et Bob viennent de divorcer et habitent dans des villes différentes et veulent par téléphone tirer à pile ou face pour savoir à qui va échoir la voiture, la machine à laver, les livres, etc
Mais Bob hésite à dire à Alice face pour s’entendre dire voilà je jette une pièce, , elle retombe, , pas de chance c’est pile. Ils veulent un protocole qui évite toute tricherie.
Ils se donnent un ensemble E par exemple E = {0,1, ,n} et une partition E = X0 ? X1 de E , X0 sera les entiers pairs de E et X1 les entiers impairs de E. Puis ils se mettent d’accord sur une fonction à sens unique, f, de E dans un ensemble F.
On considère le protocole suivant
1. Alice choisit un élément x ? E aléatoirement (c’est le jet de la pièce), calcule y = f(x) et communique y à Bob (Bob ne peut pas retrouver x à partir de y car f est à sens unique).
2. Bob choisit son bit aléatoire b ? {0,1} et l’annonce à Alice
3. Alice déclare qui a gagné suivant que x ? Xb ou non: elle prouve sa bonne foi en révélant x
4. Bob se convainc qu’il n’y a pas eu tricherie en vérifiant que y = f(x) Ce protocole est-il suˆr:
1. Si la fonction f est bien choisie la donnée de f(x) n’apprend rien à Bob sur x.
2. Pour qu’Alice ne puisse pas tricher, il faut s’assurer qu’elle ne peut pas fabriquer deux entiers x0 ? X0 et x1 ? X1 tels que f(x0) = f(x1), par exemple on peut prendre f bijective car l’ensemble est de taille réduite.
3. f doit être à sens unique en un sens fort pour que la connaissance de f(x) n’apprenne rien à Bob sur l’appartenance de x à X0 ou X1
Ce protocole met en évidence la notion d’engagement: Alice s’engage sur x en publiant f(x). Cela ne révèle rien sur x mais force Alice à ne pas modifier son choix.
10.5.1 Protocole de preuve sans transfert de connaissances.
Le protocole précédent peut être utilisé dans beaucoup de situation ou` l’on veut prouver que l’on connait un secret sans avoir besoin de le révéler.
Pour accéder à un ordinateur on donne son mot de passe qui est reconnu par l’ordinateur et donc stocké dedans. Si l’ordinateur auquel on se connecte est lointain, le mot de passe circule (crypté) sur des canaux qui risquent d’être espionnés.
Pour la sécurité il faudrait le changer souvent. Si la connexion est coupée accidentellement, il faut le redonner sans avoir la possiblité d’en changer.
Le clavier sur lequel on compose le mot de passe peut être espionné.
Il y a donc un intérêt à avoir un système de reconnaissance sans envoi de mot de passe même crypté.
Pour cela il faut disposer d’un secret personnel s et d’un protocole qui permet de persuader l’ordinateur (ou la personne) auquel on se connecte (s’adresse) qu’on connait s sans avoir à le révéler et ce à chaque fois à l’aide de messages différents.
De tels protocoles existent ce sont des applications des idées de complexité calculatoire et de fonctions à sens unique.
Exemples10 (Preuve de possession d’un logarithme discret). Cet exemple est tiré de [27]. On se donne p un nombre premier et g une racine primitive modulo p (théorème 11.3.13 page 94) qui sont publics et tels que le problème du logarithme discret soit un problème calculatoirement difficile.
Supposons que P (le prouveur) détienne le nombre secret s et soit identifié par I = gs mod p. Il s’agit de convaincre V (le vérificateur) que P connait s.
Considérons le protocole suivant:
1. P choisit un r mod p ? 1 aléatoire, il calcule t = ?r (mod p) et le communique à V .
2. V choisit un bit aléatoire ? = 0,1 et le communique à P
( x ? r mod p ? 1 si ? = 0
3. P donne x à V ou`
x ? r + s si ? = 1
10.5. PREUVE SANS TRANSFERT DE CONNAISSANCE
(?x = t mod p si ? = 0
V vérifie alors que .
?x ? It mod p si ? = 1
Comme dans le protocole de pile ou face P s’est engagé sur r en communiquant t = ?r.
Que peut faire un imposteur P? qui ne connait pas s et veut se faire passer pour P auprès de V .
• Il peut suivre le protocole et espérer que ? = 0; dans le cas contraire il ne saura pas quel y communiquer à V.
• Il peut au contraire choisir un r aléatoire et communiquer à V la quantité choisit ? = 1 alors P? donne x0 = r et survit à
la vérification ?x0 = t0I. Mais si ? = 0 alors P? ne sait que faire.
Donc quel que soit la manière dont P? s’y prenne il n’a qu’une chance sur deux de donner la bonne réponse.
1. Au bout de k applications du protocole, V est convaincu avec probabilité de 1 que son interlocuteur détient un logarithme de I
2. L’information révélée à V n’est qu’une liste d’entiers modulo p aléatoires et de leurs images par l’exponentielle x 7?? ?x. Le vérificateur V aurait pu aussi bien se la constituer seul en choisissant au hasard des entiers modulo p et en les exponentiant modulo p.
3. P n’a révélé aucune information sur son secret le logarithme de I.
C’est un exemple de protocole interactif et sans transfert de connaissance (zero knowledge proof).
Il y a d’autres protocoles qui permettent par exemple de réaliser un transfert inconscient.
10.5.2 Transfert inconscient.
Alice dispose d’un ensemble de m secrets {s1,s2, ,sm}. Alice est prête à en donner (vendre) un à Bob.
Bob aimerait obtenir le secret si, mais il ne souhaite pas révéler à Alice lequel des secrets l’intéresse. Il existe des protocoles, [27], qui donnent une solution à ce problème:
1. ils permettent à Bob de disposer de si
2. ils ne lui donnent aucune information sur les autres secrets sj, j 6= i
3. ils ne permettent pas à Alice de savoir quel secret elle a livré à Bob
Chapitre 11
Rappels Mathématiques.
11.1 Théorie de l’information.
La théorie de l’information qui est due à Claude Shannon dans un article fondateur paru en 1949, [18], utilise quelques notions de probabilité qui sont rappelées ci-dessous.
11.1.1 Rappels de probabilités discrètes.
Définition 11.1.1.Une variable aléatoire discrète,X, consiste en un ensemble X, une distribution de probabilités discrètes (px)x?Xsur X et de la donnéePr[X = x]: la probabilité que X se réalise en x. Par définition on a
?x ? X, 0 ? Pr[X = x] ? 1, et XPr[X = x] = 1
x?X
Exemples11. Le jet d’une pièce de monnaie est une variable aléatoire, X, définie sur l’ensemble X = {pile,face}, la probabilité associée étant Pr[X = pile] = Pr[X = face] =
Exemples12. Jet aléatoire d’une paire de dés. On peut le modéliser par la variable aléatoire Z sur l’ensemble
Z = {1,2,3,4,5,6} × {1,2,3,4,5,6}
muni de la probabilité Pr. Si on veut calculer la probabilité pour que la somme des deux dés lors d’un lancer soit 4. Cette valeur correspond à l’évènement
77
Pour définir la confidentialité parfaite on introduit les définitions suivantes:
Définition 11.1.2.Soient deux variables aléatoiresXetYdéfinies sur des ensembles finis X et Y respectivement. La probabibilité mutuelle Pr[X = x,Y = y] = Pr[x,y] est la probabilité pour queXse réalise en x etYse réalise en y.
La probabilité conditionnelle Pr[X = x|Y = y] = Pr[x | y] est la probabilité queXse réalise en x sachant queYs’est réalisé en y.
Définition 11.1.3.Les variables aléatoiresXetYsont dites desvariables aléatoires indépendantes siPr[x,y] = Pr[x|y] pour tout x ? X et tout y ? Y
On a la proposition
Proposition 11.1.4.On a la relation entre probabilité mutuelle et probabilité conditionnelle
Pr[x,y] = Pr[x|y]Pr[y]
Démonstration: C’est évident.
On a le théorème important suivant
Théorème 11.1.5 (Théorème de Bayes).SiPr[y] > 0, on a
Pr[x]Pr[y|x]
Pr[x|y] =
Pr[y]
Démonstration: D’après la proposition 11.1.4 on a
Pr[x,y] = Pr[x|y]Pr[y]
et en échangeant x et y on aussi Pr[x,y] = Pr[y|x]Pr[x].
11.1.2 Confidentialité parfaite.
On considère un cryptosystème (P,C,K,E,D) (définition 5.0.2 page 24) et on suppose qu’une clef K ? K n’est utilisée qu’une fois.
On suppose que l’espace des textes clairs P est muni d’une distribution de probabilités associée à une variable aléatoire x sur P, on définit Pr[x = x] comme étant la probabilité a-priori d’occurence du texte clair x.
De même on suppose que l’espace des clefs K est muni d’une distribution de probabilités associée à la variable aléatoire K sur l’espace des clefs K, on
11.1. THEORIE DE L’INFORMATION
définit Pr[K = K] la probabilité pour que la clé K soit utilisée (souvent on suppose les clés équiprobables).
Rappelons que la clef est toujours choisie par Alice et Bob avant de savoir quel message Alice va transmettre. On peut donc supposer que les variables aléatoires x et K sont indépendantes.
Les deux distributions de probabilités sur P et C induisent une distribution de probabilité sur l’espace des messages chiffrés C associée à la variable aléatoire y. Un tel système sera dit probabilisé.
On pose pour K ? K fixé et pour eK ? E la fonction de chiffrement associée C(K) = {eK(x) : x ? P}
C(K) est l’ensemble des messages chiffrés avec la clef K. Pour tout y ? C on a
Pr[y = y] = X Pr[K = K]Pr[x = dK(y)]
K?K,y?C(K)
ou` dK ? D est la fonction de décodage associée à la clé K.
On a par application du théorème de Bayes
Pr[x = x] × PK?K,y?C(K)Pr[K = K]
Pr[x = x|y = y] =
PK?K,y?C(K) Pr[K = K]Pr[x = dK(y)]
On pose la définition
Définition 11.1.6.Un système cryptographique probabilisé (P,C,K,E,D) assure une confidentialité parfaite siPr[x|y] = Pr[x] pour tout x ? P et tout y ? C, c’est à dire si la probabilité a-posteriori que le texte clair soit x sachant que le texte chiffré est y est égale à la probabilité a-priori que le texte clair soit x.
On démontre les théorèmes suivants
Théorème 11.1.7.Si les vingt-six clefs d’un chiffrement par décalage (code de Cesar) sont utilisées avec la même probabilité alors pour toute distribution d’un bloc de texte clair on a confidentialité parfaite.
Théorème 11.1.8.Un système cryptographique probabilisé (P,C,K,E,D) tel que |K| = |C| = |P| assure une confidentialité parfaite si et seulement si chaque clef est utilisée avec la même probabilité et si pour chaque x ? P et chaque y ? C, il existe une clef K unique telle que eK(x) = y
Ce théorème est une mise en forme des remarques faites lors de l’étude du code de Vernam. On voit bien la différence qu’il y a entre confidentialité parfaite et code incassable. Un code de César est à confidentialité parfaite d’après le théorème précédent pourtant il est facilement cassable.
11.1.3 Entropie.
Pour étudier la situation plus réaliste ou` une clé est utilisée plusieurs fois, Claude Shannon a introduit la notion d’entropie qui permet de modéliser l’information révélée à un opposant lors d’utilisations multiples d’une même clé.
Définition 11.1.9.Soit une variable aléatoireXdéfinie sur un ensemble fini X. L’entropie de la variable aléatoireXest définie comme étant la quantité
H(X) = ? XPr[x]log2Pr[x]
x?X
C’est une notion qui vient de la thermodynamique.
On définit ensuite l’entropie H(L) d’un langage naturel L comme le fran¸cais ou l’anglais. On essaye de quantifier les informations qu’apporte le fait qu’en fran¸cais le Q est presque toujours suivi du U et qu’un S est assez souvent suivi d’un autre S etc
On se donne un cryptosystème (P,C,K,E,D) en langue naturelle L. On définit sa redondance
On choisit une clef et un ensemble fini de messages clairs que l’on chiffre avec cette clé. On appelle clefs parasites les clefs de K qui donnent les mêmes messages chiffrés pour le même ensemble de message.
Définition 11.1.10.La distance d’unicité d’un cryptosystème est la plus petite valeur n, notée n0, telle que le nombre moyen de clefs parasites soit nul. C’est la quantité de texte chiffré nécessaire à un opposant disposant de suffisamment de temps de calcul pour déterminer la clef.
On montre que . Par exemple pour le chiffrement par
substitution sur les 26 lettres de l’alphabet |P| = 26, |K| = 26!, si l’on prend RL = 0,75 qui est une valeur admise pour l’anglais, il vient n0 ? 25. Ceci montre que pour un message de 25 lettres il n’y a en principe (en moyenne) qu’un seul déchiffrement possible (cf. les alphabets T9 sur les portables).
11.2 Théorie de la complexité.
Le but de cette théorie est de classifier les problèmes algorithmiques en fonction de leur difficulté.
Il faut donc un modèle d’odinateur. Le plus utilisé est celui des machines de Turing (Alan Turing, 1912-1954).
Une machine de Turing est la donnée de
1. un alphabet fini ?
2. une bande infinie dans les deux sens formée de cases. Dans chaque case peut être inscrit au plus un symbole de ?. Les cases vides sont marquées par un symbole spécial ?. On pose ?0 = ? ? ?. la bande modélise la mémoire de l’ordinateur. A chaque instant seul un nombre fini de cases de la bande contient un symbole de ?.
3. une tête de lecture/écriture qui se déplace d’une case à l’autre.
4. un ensemble fini d’états Q, l’un d’entre eux étant appelé l’état initial.
5. un programme ou fonction de transition, composé d’un tableau, indexé par Q et ?0.
Pour chaque couple (q,s) ? Q × ?0 le programme possède au plus une instruction qui sera exécutée quand la machine sera dans l’état q et que la tête de lecture lira le symbole s.
Cette instruction est codée
(q0,s0,d) avec q0 ? Q, s0 ? ?0d ? {gauche,droite}.
Son exécution consiste à écrire le symbole s0 à la place de s à déplacer la tête de lecture dans la direction d et à placer la machine dans l’état q0.
Pour faire fonctionner la machine de Turing on inscrit une suite finie de symboles ? ? sur la bande. On place la machine dans l’état initial et on positionne la tête de lecture sur la première case à gauche contenant un symbole de ?.
Ensuite la machine exécute le programme et s’arrête quand elle ne possède pas d’instructions correspondant au symbole lu et l’état ou` elle se trouve.
Exemples13. Testeur de parité. Cette machine teste la parité du nombre de 1 dans un nombre n écrit en base 2. Elle s’arrête dans l’état qi si n a un nombre impair de 1 et elle s’arrête dans l’état qp si n possède un nombre pair de 1.
? = {0,1}, Q = {q0,q1,qp,qi}, état initial q0, fonction de transition
| 1 | ? | ||
| q0 | (q0,?,droite) | (q1,?,droite) | (qp,?,droite) |
| q1 | (q1,?,droite) | (q1,?,droite) | (qi,?,droite) |
Il y a aussi des machines de Turing non déterministes qui peuvent avoir plusieurs instructions possibles pour un couple de (Q,?0). La machine choisit “au hasard” quelle instruction exécuter.
11.2.1 Décidabilité.
On introduit les définitions suivantes
Définition 11.2.1.Soit ? un alphabet et ??l’ensemble des mots sur ?. Un langage sur ? est une partie de ??
Définition 11.2.2.Soit M une machine de Turing sur l’alphabet ? et qy un
état de M. On dit que M accepte la donnée x (par l’état qy) si M s’arrête dans l’état qy lorsque la donnée est x.
L’ensemble des mots acceptés par M s’appelle le langage reconnu par M que l’on note
Lqy(M) = L(M)
Le complémentaire de L(M) dans ?? est l’ensemble des mots pour lesquels soit M ne s’arrête pas soit M s’arrête dans un état 6= qy.
Définition 11.2.3.Un problème de décision D appartient à la classePs’il existe une machine de Turing déterministe qui le résoud en un temps polyomial en fonction de la taille des données (i.e. du nombre de symboles de ? apparaissant dans la donnée). Si ? = {0,1} alors le problème de décision appartient à la classe P des problèmes polynomiaux en temps si
?x ? D ? Ctemps(x) = O(polynôme en log2(x))
Un problème de décision D appartient à la classe NP des problèmes non polynomiaux en temps s’il existe une machine de Turing non-déterministe qui le résoud en un temps polynomial
Conjecture 1. P6=NP.
Autrement dit il existe au moins un problème pour lequel on peut montrer qu’il n’existe pas de machine de Turing déterministe pour le résoudre en temps polynomial et qui peut être résolu en temps polynomial par une machine de Turing non-déterministe.
11.2.2 Complexité algorithmique.
Si on veut exécuter un algorithme sur une donnée x deux couˆts sont à envisager.
• le couˆt en temps Ctemps(x), c’est à dire le nombre d’opérations effectuées pour obtenir le résultat final ou plus formellement le nombre de déplacements de la tête de lecture/écriture avant arrêt de la machine de Turing modélisant l’ordinateur.
• le couˆt en espace, Cespace(x) est la taille de la mémoire utilisée, plus formellement le nombre de case de la bande écrite au moins une fois.
On distingue essentiellement deux notions de complexité algorithmique la complexité polynomiale et la complexité non polynomiale (sous entendu en fonction de la taille des données).
Quel est le couˆt acceptable pour un problème donné. Il n’y a ni réponse claire ni réponse absolue. En 2000 on estimait que
• 240 opérations élémentaires est accessible à un particulier s’il est patient.
• 256 opérations élémentaires est accessible avec de gros moyens.
• 280 opérations élémentaires est hors de portée de quiconque.
Soit un algorithme dont le nombre d’opérations élementaires en fonction de la taille n de l’entrée est décrit par la fonction f. On dispose d’un ordinateur faisant 109 opérations élémentaires par secondes. Le temps pris par l’algorithme suivant les instances de f est:
| f | log2(n) | n | nlog2(n) | n2 | 2n | ||||
| n = 100 | 6,6 · 10?9 | s | 4,4 · 10?7 | s | 7,5 s | 6,7 · 10?7 | s | 10?5 s | 4 · 1013 ans |
| n = 105 | 1,7 · 10?8 | s | 5,2 · 10?6 | s | 10?4 s | 1,7 · 10?3 | s | 10 s | ? 1030086 ans |
| n = 1010 s | 3,3 · 10?8 | 3,5 · 10?5 | s | 10 s | 330 s | 3 siècles | ? 103·109 ans | ||
| n = 1020 | 6,6 · 10?8 s | 2,3 · 10?4 | s | 30 siècles | ? 105 ans | ? 1023 ans | !!! | ||
11.2.3 Algorithmes polynomiaux en fonction de la taille des données.
On décompose tout algorithme arithmétique en opérations élémentaires.
L’opération élémentaire est l’addition de 3 chiffres en base 2 et le report de la retenue retenue + chiffre 1 + chiffre 2 = résultat + retenue
Définition 11.2.4.On dit qu’un algorithme est polynomial en fonction de la taille des données s’il peut être décomposé en un nombre d’opérations élémentaires majoré par une fonction polynomiale du nombre de chiffres des données.
Exemples14. Montrons que l’addition de deux nombres de tailles ? k est une fonction polynomiale de k
| 1 | 1 | 1 | 1 | retenue | ||||
| 1 | 1 | 1 | 1  | 0 ligne 1 | ||||
| + | 1 | 1 | 1 | 1 | 0 ligne 2 | |||
| 1 | 1 | 1 | 1 | 0 résultat |
On suppose que le plus grand des entiers a k chiffres. Décomposons la somme en opérations élémentaires
1. Regarder dans la colonne i (1 ? i ? k +1) les chiffres des lignes lignes 1, 2 et retenue
2. S’il y a 0 dans les lignes 1, 2 et retenue mettre 0 dans la ligne résultat et aller à la colonne i + 1
3. S’il y a un 0 dans deux des lignes 1 et 2 et retenue on reporte 1 dans la ligne résultat et on passe à la colonne i + 1
4. S’il y a un 1 dans deux des lignes 1 et 2 et retenue on reporte 0 dans la ligne résultat on met 1 dans la ligne retenue à la colonne i+1 et on passe à la colonne i + 1
5. S’il y a un 1 dans les 3 lignes 1 et 2 et retenue on reporte 1 dans la ligne résultat on met 1 dans la ligne retenue à la colonne i + 1 et on passe à la colonne i + 1
On admet en première approximation que le temps nécessaire pour faire k opérations élémentaires est proportionnel à k avec une constante dépendant de l’ordinateur et de l’implantation de l’algorithme.
Exemples d’algorithmes polynomiaux en fonction de la taille des entrées:
• L’addition de deux entiers n ? m de longueur ? k est polynomial en fonction de la taille des entrées car (en première approximation) il faut
C · kdéf= O(k) = O(log2(m)) opérations
Ajouter deux entiers de 100 chiffres en base 10 avec un ordinateur faisant 109 opérations par secondes nécessite ? 300 · 10?9sec ? 3µsec. • La multiplication de deux entiers n ? m de taille k et ` nécessite
opérations
Multiplier deux entiers de 100 chiffres en base 10 nécessite ? 90000 · 10?9sec ? 10µ sec.
• Calcul du PGCD de deux entiers, n ? m de taille k ? ` nécessite
opérations
Trouver le PGCD de deux entiers de 100 chiffres en base 10 nécessite ? 27000000 · 10?9 ? 0,027 sec.
• Calculer bm mod n nécessite opérations.
• Décider si un nombre entier n de taille k est premier ou non nécessite
opérations
Tester si un entier de 100 chiffres en base 10 est premier nécessite avec l’algorithme polynomial ? 1026µ sec ? 109 années. Il y a des algorithmes pour tester la primalité d’un entier non polynômiaux et/ou non déterministes qui sont plus efficaces pour des nombres pas trop grands.
le dernier exemple montre que si le polynôme est de degré trop élevé (? 3, un algorithme polynomial peut avoir un couˆt prohibitif.
Exemples d’algorithmes non polynomiaux en fonction de la taille des entrées
• Calcul de n! = 1 · 2 (n ? 1) · n, si l’on calcule brutalement il faut environ
) opérations
Calculer ! nécessite ? 10190µ sec ? 10180 années!!!
• Recherche d’un diviseur d’un entier n, les meilleurs algorithmes nécessitent opérations, C ? 2
Trouver un diviseur d’un nombre de 100 chiffres en base 10 nécessite ? e30 · 10?9 ? 105 sec ? 1,1jours. Un tel algorithme est dit sousexponentiel.
11.3 Rappels d’arithmétique.
Ainsi qu’on l’a vu dans la description des cryptosystèmes à clé publique RSA et El Gamal, leur principe est basé sur de l’arithmétique élémentaire.
11.3.1 La division euclidienne.
Les entiers naturels N = {1,2,3 } sont munis de deux opérations internes l’addition, notée +, et la multiplication, notée × ou · ou même sans symbole, et d’une relation d’ordre total, notée ?, compatible avec l’addition et la multiplication c’est à dire
On définit sur N la division euclidienne
Définition 11.3.1.Si a et b sont deux entiers (b 6= 0) il existe un unique couple d’entiers q et r tel que
( ou bien r = 0
a = b · q + r et ou bien 1 ? r ? b ? 1
on dit que b est un diviseur de a s’il existe q ? N tel que a = bq, on note a|b pour dire a divise b.
Tout entier a possède au moins deux diviseurs triviaux 1 et lui-même car on a toujours
a = 1 · a, a = a · 1
Mais il peut en avoir d’autres par exemple
6 = 2 · 3, 28 = 4 · 7 = 2 · 2 · 7 = 2 · 14
donc 1, 2, 3 et 6 sont des diviseurs de 6 et 1, 2, 4, 7, 14 et 28 sont des diviseurs de 28.
La division euclidienne implique que Z, les entiers relatifs, est un anneau euclidien, i.e. qu’il est muni de deux lois de composition interne l’addition et la multiplication qui possédent certaines propriétés et d’une division euclidienne, cf. [19],
1. La loi + est commutative (pour tout (a,b) ? Z2 on a a + b = b + a), associative ( pour tous (a,b,c) ? Z3 on a (a+b)+c = a+(b+c), il y a un élément neutre, 0, tel que pour tout a ? Z on a a+0 = 0+a = a, tout élément a ? Z possède un opposé b = ?a tel que a+b = b+a = 0.
2. La loi × est commutative (a×b = b×a), associative ((a×b)×c = a× (b×c)), il y a un élément neutre, 1, (a×1 = 1×a = a), la multiplication est distributive par rapport à l’addition ((a+b)×c = (a×c)+(b×c) Dans les entiers naturels on distingue
• 1 qui est une unité, c’est à dire que 1 possède un inverse pour la multiplication (il existe b ? N tel que 1 × b = b × 1 = 1) qui est 1.
• les nombres premiers qui n’ont pas d’autres diviseurs que les diviseurs triviaux i. e. 1 et lui même (e.g. 2,3,5,7, ,37, .).
Le théorème suivant qui découle de l’existence de la division euclideienne est appelé le théorème fondamental de l’arithmétique
Théorème 11.3.2.Tout nombre entier différent de 1 possède une unique décomposition en facteurs premiers à l’ordre près des facteurs, certains facteurs peuvent être répétés.
Démonstration: Pour la preuve voir [19]
Autrement dit si a ? N, a ? 2, alors il existe des nombres premiers p1, p2, , pna non nécessairement distincts tels que
a = p1 × p2 × ··· × pn, pi premier pour 1 ? i ? n
l’entier n dépend de a. L’unicité à l’ordre près des facteurs impose que si on a une égalité
a = q1 × q2 × ··· × qm, qj premier pour 1 ? j ? m
alors nécessairement n = m et il existe une permutation ? des entiers de 1
à na telle que
p1 = q?(1), p2 = q?(2), , pn = q?(n).
On peut écrire la décomposition en facteurs premiers de a ? N en regroupant tous les nombres premiers égaux, alors
avec p1< p2< ··· < p`, pi premier pour 1 ? i ? `
L’unicité à l’ordre près des facteurs impose que si on a une égalité
avec q1< q2< ··· < q`, qj premier pour 1 ? j ? k
alors
` = k et ?i = ?i, pour 1 ? i ? `Exemples15. 10780 = 22 · 5 · 72, 4200 = 23 · 3 · 52 · 7 · 11
11.3.2 Plus Grand Commun Diviseur ou PGCD.
Le plus grand commun diviseur abrégé en PGCD en fran¸cais et GCD (Greatest Common Divisor )en anglais est défini de la manière suivante
Définition 11.3.3.Le plus grand commun diviseur de deux nombres entiers a et b est le plus grand des entiers qui divisent à la fois a et b, on le note PGCD(a,b) ou a ? b ou encore (a,b).
L’ensemble divise a et d divise best non vide, car 1 divise toujours a et b, et il est borné par le plus grand des deux entiers a et b, donc le PGCD existe et de plus il est toujours supérieur ou égal à 1.
Proposition 11.3.4.Le plus grand commun diviseur de a et de b, entiers naturels, s’obtient de la manière suivante. Si
, avec ?i,?i ? 0
sont leur décomposition en facteurs premiers, alors le PGCD de a et de b est:
Démonstration: Pour la preuve voir [19]
Pour calculer le PGCD ni la définition 11.3.3 ni la proposition 11.3.4 ne sont efficaces car elles nécessitent l’une comme l’autre de trouver des diviseurs de a et de b. Or les meilleurs algorithmes connus pour trouver un diviseur non trivial de a ou pour décomposer? a en facteurs premiers ce qui revient
au même sont en O(eClog2(a)log2 log2(a). Ces algorithmes ne sont donc pas polynomiaux en temps en fonction de la taille des données, leur couˆt est prohibitif pour des grands nombres entiers (500 chiffres en base 10 par exemple) même avec des ordinateurs très puissants.
Exemples16. Le PGCD de 4200 = 23 ·3·52 ·7 et de 10780 = 22 ·5·72 ·11 est
PGCD(4200,10780) = 4200 ? 10780 = 22 · 5 · 7 = 140
Par contre l’algorithme de la division euclidienne fournit grâce au théorème de Bézout un algorithme très efficace, polynomial en temps en fonction de la taille des données, pour calculer le PGCD de deux entiers naturels.
11.3.3 Algorithme du plus grand commun diviseur ou algorithme du PGCD.
Considérons le problème suivant:
Soit a ? b deux entiers de taille k au plus. Trouver le PGCD a ? b de a et de b et évaluer le nombre d’opérations élémentaires nécessaires.
Proposition 11.3.5.On écrit les divisions euclidiennes successives
a = bq0 + r1 b = q1r1 + r2
r1 = q2r2 + r3
(11.1) ... rj?2 = qj?1rj?1 + rj
rj?1 = qjrj + rj+1 rj = qj+1rj+1
avec 0 ? r1< b, 0 ? r2< r1, 0 ? r3< r2, , 0 ? rj < rj+1.
On arrête l’algorithme dès qu’un reste est nul et alors
a ? b = rj+1
Démonstration: En effet la dernière identité de division enclidienne de (11.1) montre que rj+1 divise rj, l’avant dernière identité de division enclidienne de (11.1) montre que rj+1 divise rj et rj?1. Puis par récurrence on montre que rj+1 divise a et b.
Donc rj+1 est un diviseur commun de a et de b, est-ce le plus grand? Considérons un diviseur commun de a et de b noté d. Par définition d divise a et b donc d’après la première des identités de division enclidienne de (11.1) on a |r1, alors la deuxième des identités de division enclidienne de (11.1) implique que d|r2 puis par récurrence on montre que d|rj+1.
On a donc montré que tout diviseur d commun de a et de b est un diviseur de rj+1 et comme rj+1 est un diviseur de a e de b c’est le plus grand, autrement dit rj+1 = a ? b.
Cet algorithme nécessite opérations élémentaires. Exemples17. Trouver le PGDCD de 4200 et 10780:
10780 = 2 × 4200 + 2380; 4200 = 2380 + 1820;
2380 = 1 × 1820 + 560,1820 = 3 × 560 + 140, 560 = 4 × 140
PGCD(10780,4200) = 140
L’algorithme de la division euclidienne donne aussi une version effective du théorème de Bézout, autrement dit une version effective du calcul du générateur de l’idéal ha,bi engendré par a et b.
Théorème 11.3.6 (Théorème de Bézout).Soit a et b deux entiers naturels de PGCD: a ? b = d. Alors il existe deux entiers relatifs u, v tels que
d = au + bv
u et v sont appelés les coefficients de Bézout.
Démonstration: on reprend l’algorithme du PGCD à partir de la fin. On
écrit avec les notations précédentes
d = rj+1 = rj?1 ? qjrj = rj?1uj?1(1) ? rjvj(qj)
On a une relation de récurrence facile sur uj et vj.
uj+1 = uj?1 ? qj+1uj vj+1 = vj?1 ? qj+1vj
Exemples18. Relation de Bézout entre 10780 et 4200:
140 = 1820 ? 3 × 560 = 1820 ? 3 × (2380 ? 1820)
= 4 × 1820 ? 3 × 2380 = 4 × (4200 ? 2380) ? 3 × 2380
= 4 × 4200 ? 7 × 2380 = 4 × 4200 ? 7 × (10780 ? 2 × 4200)
= 18 × 4200 ? 7 × 10780 = 75600 ? 75460
Remarque11.3.1. Le couple (u,v)) tel que au + bv = d = a ? b dont l’existence est garantie par le théorème de Bézout n’est pas unique car si (u0,v0) est un tel couple et si (x1,y1) est une solution en nombres entiers relatifs de l’équation
ax1 + by1 = 0
alors on a encore
a(u + x1) + b(v + y1) = d
Par contre on a unicité au signe près si on impose
1 ? |u| ? b, 1 ? |v| ? a
Algorithme d’Euclide.
On donne une version de type programme de l’algorithme d’Euclide.
• Entrée 2 entiers positifs a et b non tous deux nuls
• Sortie a ? b
– Tant que b 6= 0 faire
a ? b := b ? (a mod b)
– si b = 0 retourner a et fin
Algorithme d’Euclide étendu.
On donne une version récursive de type programme de l’algorithme d’Euclide étendu qui donne les coefficients de Bézout pour le PGCD de deux entiers.
1. Entrée 2 entiers positifs a et b non tous nuls
2. Sortie 3 entiers u, v, d tels que au + bv = a ? b = d
(a) Variables entières u1, v1, u2, v2, u3, v3, q, r
(b) Si a = 0 retourner (0,1,b) et fin
(c) sinon Au1 +Bv1 = a et Au2 +Bv2 = b ou` A et B sont les valeurs initiales de a et b
(d) Faire
(u1,v1) := (1,0) (u2,v2) := (0,1)
(e) Tant que b 6= 0 faire
(q,r) := quotient et reste de la division euclidienne de a par b
(u3,v3) := (u1 ? qu2,v1 ? qv2)
(u1v1,a) := (u2,v2,b)
(u2,v2,b) := (u3,v3,r) 3. si b = 0 retourner (u1,v1,a).
11.3.4 Les Congruences.
Les cryptosystèmes RSA et El Gamal reposent sur la théorie des congruences ou arithmétique modulaire.
Définition 11.3.7.Soit a, b et m trois entiers. On dit que a est congru à b modulo m et on écrit
a ? b mod m
si la différence a ? b est divisible par m
Une autre manière de dire la même chose
Corollaire 11.3.8.Soit m un entier non nul, alors a et b sont congrus modulo m si et seulement si les restes de la division euclidienne de a par m et de b par m sont les mêmes
Démonstration: C’est immédiat.
Exemples19. Prenons m = 2 alors deux entiers a et b sont congrus modulo 2 s’il sont soit tous les deux pairs soit tous les deux impairs.
Prenons m = 5 alors 5 est congru à 0 modulo 5 (car 5 ? 0 = 5 est divisible par 5) ou à ?700 modulo 5 (car 5 ? (?700) = 705 est divisible par 5), 3 est congru à ?2 modulo 5 (car 3?(?2) = 5 est divisible par 5) ou à 38 modulo 5 (car 3 ? 38 = ?35 est divisible par 5)
On montre facilement que
Proposition 11.3.9.La relation de congruence est une relation d’équivalence sur les entiers.
c’est à dire que
• a ? a mod m (reflexivité)
• a ? b mod m =? b ? a mod m (symétrie)
(transitivité)
Démonstration: C’est évident.
Proposition 11.3.10.L’addition et la multiplication sont compatibles à la relation de conguence sur les entiers; autrement dit:
Démonstration: Pour la preuve cf. []
Exemples20. Si m = 2 alors la proposition signifie simplement que la somme de deux nombres pairs est paire, que la somme de deux nombres impairs est paire, que la somme d’un nombre pair et d’un nombre impair est impaire et que le produit de deux nombres pairs est pair, celui de deux nombres impairs est impair, celui d’un nombre pair et d’un nombre impair est pair.
Si m = 5 on constate que
5 + 3 ? ?700 ? 2 ? 0 + 38 ? 3 mod 5, 5 × 3 ? 0 × 3 ? 5 × 38 mod 5
On fixe m et on décide de ne pas distinguer deux éléments congrus modulo m. L’ensemble des éléments de Z qui sont congrus modulo m à un entier fixé s’appellera une classe de congruence modulo m. Un élément d’une classe de congruence s’appelle un représentant de la classe de congruence. Parmi les réprésentant d’une classe de congruence, il y en a toujours un, unique, compris entre 0 et m ? 1.
On notera Z/mZ l’ensemble des classes de congruence de Z modulo m. D’après la proposition 11.3.10 on peut munir Z/mZ des deux lois + et × puisque que le résultat modulo m de ces deux opérations ne dépend pas des représentants choisis dans une classe de congruences.
Corollaire 11.3.11.Tout élément de Z/mZ possède un opposé pour l’addition. Les éléments de Z/mZ qui ont un inverse multiplicatif sont ceux dont les représentants dans Z sont premiers à m.
Démonstration: Facile par Bézout
Théorème 11.3.12.Si p est premier Z/pZ est un corps fini à p éléments, c’est à dire que tout élément différent de la classe de zéro possède un inverse multiplicatif. On le note Fp
Démonstration: facile d’après le corollaire précédent.
On peut montrer que pour chaque entier r ? 1 il existe un seul corps fini à q = pr éléments à isomorphisme de corps près, noté Fpr = Fq. Ils s’obtiennent en considérant les quotients
Fq ' Fp[X]/P(x)Fp[X], P(X) ? Fp[X],irréductible, de degré r cf. la section 11.6. Le théorème suivant est du à C.F. Gauss
Théorème 11.3.13.Si p est premier, le groupe multiplicatif
{éléments inversibles de
est cyclique, i.e. il existe g premier à p tel que
Un générateur g du groupe cyclique Z/pZ s’appelle une racine primitive modulo p.
De même si q = pr avec p premier le groupe multiplicatif,, des éléments inversibles de Fq est cyclique.
Démonstration: Pour la preuve cf. [19]
Le théorème suivant joue un rôle extrèmement important en arithmétique modulaire et en particulier pour le décodage du cryptosystème RSA, ainsi que pour la mise en oeuvre du cryptosystème El Gamal
Théorème 11.3.14 (petit théorème de Fermat).Soit p un nombre premier. Tout entier a vérifie la congruence ap ? a (mod p), et si a ? p = 1 on a aussi ap?1 ? 1 (mod p).
Exemples21. p = 7, a = 3 alors
Remarquer la manière de calculer une puissance: écrire l’exposant en base 2 et procéder par élévations au carré successives.
Démonstration: Les éléments inversibles de N modulo p plus petits que p sont 1, 2, ,(p ? 1). Considérons a premier à p donc inversible modulo p et considérons l’ensemble
{a, 2a, 3a, , (p ? 1)a} mod p
c’est une permutation de l’ensemble {1,2, ,(p ? 1)} car a est inversible modulo p. Donc:
Comme (p ? 1)! est premier à p donc inversible modulo p on a
ap?1 ? 1 mod p
Le théorème suivant est appelé: Théorème des restes chinois
Théorème 11.3.15.Soient m1, m2, mr des entiers naturels deux à deux premiers entre eux (i. e. mi ? mj = 1 si i 6= j) et soient a1, a2, ar des
| entiers relatifs. Le système de congruences | |
| ? x ? a mod m , x ? a ??? 1 1 2 (11.2) ??? x ? ar | mod m2 mod mr |
a toujours une solution et deux solutions quelconques sont congrues modulo
M = m1m2mr
Exemples22. Prenons r = 2, m1 = 15, m2 = 14, a1 = 6, a2 = 9. On veut
donc résoudre simultanément
(11.3) x ? 6 mod 15 et x ? 9 mod 14
La première équation impose que x est de la forme x = 6 + 15k avec k ? Z et la deuxième impose que x est de la forme x = 9 + 14` ` ? Z et par
connséquent on doit avoir
6 + 15k = 9 + 14` ?? 15k ? 14` = 3
Comme 14?15 = 1 le théorème de Bézout indique qu’il existe (u,v) = (1,?1) tel que 15u+14v = 1 et donc en prenant k = ` = 3 on a une solution x = 51 du système de congruences (11.3)
Démonstration: Unicité (mod M) de la solution au système de congruences. Si x1 et x2 sont deux solutions alors x = x1 ?x2 ? 0 (mod mi) pour 1 ? i ? r et donc x ? 0 (mod M).
, clairement Mi ? mi = 1 donc il existe un entier Ni tel que MiNi ? 1 (mod mi) et de plus mi |Mj si i 6= j. Alors
Ce théorème permet de remplacer un système de congruences modulo les mi par une congruence unique modulo M = m1 ···r.
Corollaire 11.3.16.Avec les notations du théorème 11.3.15, le système de congruences (11.2)
?
| x ? a mod m , ??? 1 1 ??? équivaut à la congruence unique | x ? a2 x ? ar | mod m2 mod mr |
| y ? x | mod M |
Démonstration: C’est évident.
Remarque11.3.2. Ce corollaire exprime que l’on a
ou` l’isomorphisme est un isomorphisme d’anneau.
Définition 11.3.17.Si m est un entier positif on note ?(m) le nombre d’entiers b < m et premiers à m, ou de manière équivalente ?(m) est le nombre d’entiers b < m inversibles modulo m
La fonction ? est appelée l’indicatrice d’Euler.
Proposition 11.3.18.Si est la décomposition de m en facteurs premiers distincts alors
(11.4)
Démonstration: Il est clair que ?(1) = 1, que si p est premier ?(p) = p?1 et que ?(p?) = (p ? 1)p??1. Par le théorème des restes chinois si m est premier à n alors
?(mn) = ?(m) × ?(n)
Théorème 11.3.19 (Théorème d’Euler).Soit m > 1 un entier et soit a un entier premier à m, alors on a: a?(m) ? 1 (mod m)
Démonstration: Même preuve que pour le petit théorème de Fermat En particulier si p et q sont premiers,
(11.5) ?(pq) = (p ? 1)(q ? 1)
et
(11.6) a(p?1)(q?1) ? 1 mod pq
Il est facile de montrer à partir du théorème d’Euler le corollaire important suivant qui est un cas particulier d’un théorème de Lagrange, [19],
Corollaire 11.3.20.Soit m ? N et soit a ? N tel que a ? m = 1 alors le plus petit entier e ? 1 tel que ae ? 1 (mod m) est un diviseur de ?(m).
Démonstration: Supposons que e ne soit pas un diviseur de ?(m) et
écrivons l’identité de la division euclidienne de ?(m) par e
?(m) = e × q + r avec 0 < r ? e ? 1
on a r 6= 0 car e ne divise par ?(m). Alors ar = avarphi(m)?eq = a?(m) × aeq = a?(m) × (ae)q ? 1 mod m
Or comme 1 ? r ? e ? 1 ceci contredit la définition de e.
Résidus quadratiques modulop.
On va étudier les résidus quadratiques modulo un nombre premier p c’est à dire les carrés modulo un nombre premier p. Cette étude joue un rôle important dans les tests de primalité probabilistes ou non.
Définition 11.3.21 (Symbole de Legendre).On pose si p est premier impair
si a est premier à p et est un carré (mod p) si a est premier à p et n’est pas un carré (mod p) si a n’est pas premier à p
Le symbole est appelé le symbole de Legendre.
C’est un caractère du groupe multiplicatif (Z/pZ)? à valeur dans {±1}?{0} de période p autrement dit:
Théorème 11.3.22 (Euler).Si p est premier impair et a premier à p alors
Démonstration: Pour la démonstration voir [19].
Théorème 11.3.23 (Loi de réciprocité quadratique).Soit p et q des premiers impairs alors
Démonstration: Pour la démonstration voir [19].
Ce théorème (un des plus célèbres de l’arithmétique) est du à C. F. Gauss, il se généralise au symbole de Jacobi ci-dessous. Sa preuve est délicate. Définition 11.3.24 (Symbole de Jacobi).On pose si m = Yp?ii est
pi |m
impair et n ? Z
si m ? n = 1
si m = 1
???0 si m ? n 6= 1
Le symbole de Jacobi possède les propriétés suivantes. Si m est un entier impair
(11.7)
2 +1 si m ? ±1 (mod 8)
(11.8)
m ?1 si m ? ±3 (mod 8)
(11.9)
Il vérifie aussi une loi de réciprocité quadratique: Si m et n sont entiers impairs:
si m ? n ? 3 (mod 4)
(11.10)
sinon
11.4 Tests de primalité.
Pour tester si n est premier on pourrait essayer de le diviser par tous les
?
entiers < n, c’est la méthode du crible d’Eratosthenes. C’est impraticable
?
dès que n est grand car n n’est pas majoré uniformément par un polynôme en logn.
Le temps de calcul devient vite prohibitif. On a vu en effet qu’une division de n par un entier inférieur demande O(log3n) opérations élémentaires donc cette méthode nécessitera
) opérations
Ce n’est donc pas un algorithme polynomial en temps.
Parmi les tests de primalité certains parmi les plus utilisés sont basés sur le petit théorème de Fermat, ou sur les propriétés du symbole de Legendre et sur la théorie des résidus quadratiques.
Il existe, depuis le résultat d’Agrawal-Kayal-Saxena en 2002, [1], des tests de primalité, basés sur le petit théorème de Fermat, qui sont polynomiaux en temps (actuellement en et même). Mais pour l’instant ils sont moins performants que des tests probabilistes comme ceux décrits ci-dessous.
Pour tester si n est premier on procède souvent en pratique de la manière suivante dans les logiciels de calcul formel.
1. Vérifier que n n’est pas divisible par des petits facteurs premiers.
2. Puis pour des a choisis au hasard et tels que 1 ? a ? n et a ? n = 1 calculer an?1 mod n.
3. Si an?1 6? 1 mod n pour au moins un a alors n n’est pas premier.
4. Sinon on ne peut pas conclure (cf. nombres de Carmicha¨el, par exemple 561). On dit que n est pseudo premier.
Pour avoir un résultat suˆr on peut utiliser le test de Lucas
Théorème 11.4.1 (Lucas).Si a est premier à n et si pour tout diviseur
n premier p de n ? 1 on aalors n est premier
Démonstration: La preuve de ce résultat est immédiate.
11.4. TESTS DE PRIMALITE´
On peut aussi utiliser les propriétés des symboles de Legendre et de Jacobi.
Pour tester si p est premier on utilise les remarques suivantes
1. On choisit b premier à n avec 1 ? b ? n?1 et on calcule
2. Si p est premier on doit avoir ) pour tout b
(théorème 11.3.22 page 99.
3. Si p n’est pas premier alors on a) pour au moins
50% des b premiers à n.
On aboutit ainsi au test de primalité de Solovay-Strassen 1. Tirer un entier aléatoire a, 1 ? a ? n ? 1
est probablement premier
2. Si
est décomposable
3. ) choisir un autre a et recommencer.
La loi de réciprocité quadratique rend ce test probabiliste très efficace. Elle évite en effet pour calculer le symbole de Jacobi d’avoir à factoriser a et n.
Exemples23. Testons la primalité de 547. On choisit a = 5. On calcule d’une part
d’autre part
Donc 547 a une chance d’être premier. Pour se conforter on recommence avec 7 au lieu de 5, etc.
Actuellement on est capable de prouver la primalité d’un nombre sans symétrie particulière de 2000 à 3000 chiffres en base 10 en un mois de CPU sur une station de travail. On prouve aussi la primalité de nombres tests comme les nombres de Mersenne (2p?1) ayant plusieurs millions de chiffres.
Pour construire de grands nombres premiers on couple les résultats précédents avec des théorèmes sur la répartition des nombres premiers.
On sait par exemple que le nombre de nombres premiers inférieurs à x,
. On en déduit qu’il y a toujours un nombre premier entre n et 2n (en fait on sait plus). On prend un nombre n au hasard et on teste s’il est premier, s’il ne l’est pas on passe à n + 1, etc.
11.5 Méthode de factorisation.
Principe d’un algorithme très utilisé pour factoriser de grand nombres entiers, le crible quadratique. Il est fondé sur la proposition suivante
Proposition 11.5.1 (Fermat).Soit n un entier positif impair. Il y a une bijection entre les décompositions de n sous la forme n = ab avec a ? b ? 0 entiers et les représentations de n sous la forme n = t2 ? s2, ou` s et t sont des entiers positifs ou nuls. La bijection est donnée par les équations
Exemples24. Soit à factoriser n = 23360947609
?
n = 23360947609 =? E( n) = 152843
On pose t = 152843. On teste s’il existe i pas trop grand tel que
(t + i)2 ? n = (152843 + i)2 ? 23360947609
est un carré.
On trouve que pour i = 2 on a
1528452 ? 23360947609 = 8042
(
p = 152845 + 804 = 152649
et donc n = pq avec . On vérifie aisément
q = 152845 ? 804 = 152041
que p et q sont premiers.
Cette méthode ne marche pas à coup suˆr, on l’a raffinée de diverses manières mais la factorisation d’un nombre reste encore un problème difficile.
Dans la proposition précédente on utilise le fait que l’on a
t2 ? s2 mod n et t 6? ±s mod n
11.5. METHODE DE FACTORISATION´
Ces deux relations impliquent que l’on trouve alors un diviseur non trivial de n en calculant PGCD(t + s,n) et PGCD(t ? s,n). En effet n|t2 ? s2 et n6 |t + s, n6 |t ? s, donc a = PGCD(t + s,n) est un diviseur non trivial de divise a = PGCD(t ? s,n).
Exemples25. On veut factoriser 4633. On remarque que
1182 ? 252 mod 4633,
PGCD(118 + 25,4633) = 41, PGCD(118 ? 25,4633) = 113
On constate que 4633 = 41 × 113.
Pour mettre cette remarque en oeuvre on cherche une famille finie de nombres premiers B = {p1,p2, ,ph}, ou` p1 = ?1 et des entiers bi tels que le plus petit représentant de (b2i mod n) noté {b2i } (i.e le représentant compris entre et + 1) s’écrive avec pour tout j, Pi ?j,i ? 0
(mod 2). On pose alors
et
{b} = Ybi mod n, et c = Yp?j
i p?B
Si b 6? ±c mod n on a gagné et on a un diviseur de n par la remarque précédente. Sinon il faut recommencer avec un autre choix pour B ou pour les bi.
La factorisation des entiers reste un problème difficile. En 1994 il a fallu le travail combiné de 600 personnes pendant 8 mois pour factoriser un nombre de 129 chiffres proposé 17 ans plus tôt et pour cela il fallu développer dans l’intervalle de nouvelles méthodes de factorisation.
En 1999 il a fallu 8 mois de travail pour factoriser un nombre de 155 chiffres. Il a fallu en plus de l’augmentation de puissance des ordinateurs développer et perfectionner de nouvelles méthodes de factorisation.
En 2005 on a factorisé des nombres de 200 chiffres en base 10 en utilisant le crible quadratique et 80 ordinateurs travaillant en parallèle pendant plusieurs mois.
Pour des généralisations des codes RSA ainsi que pour des procédés de factorisation et des tests de primalité, on utilise l’arithmétique sur les courbes elliptiques qui est une sorte de généralisation de l’arithmétique modulaire .
11.6 Rappels d’algèbre.
Ainsi qu’on l’a vu à la section 7.2 page 38 la description d’AES nécessite celle des extensions de corps finis comme quotient d’anneaux de polynômes.
11.6.1 Anneau des polynômes sur un corps
Soit K un corps, par exemple Q, R, C ou un corps fini comme Z/2Z, Z/pZ avec p premier.
Définition 11.6.1.L’anneau des polynômes à coefficients dans K, noté K[X], est l’ensemble des suites finies d’éléments de K,
P = P(X) = (a0,a1, ,an)
appelées polynômes. Deux polynômes
P(X) = (a0,a1, ,an) ? K[X], Q(X) = (b0,b1, ,bm) ? K[X]
(avec m ? n) sont égaux si ai = bi pour 0 ? i ? n et bj = 0 pour n + 1 ? j ? m, en particulier
n+h éléments
Considérons les polynômes
P(X) = (a0,a1, ,an) ? K[X], Q(X) = (b0,b1, ,bm) ? K[X] On définit la somme P(X) + Q(X) par
et le produit P(X) × Q(X) = P · Q = PQ par
avec a`=0 si `>n, b?=0 si m>?
Notations11.6.1. On adopte les notations classiques suivantes
• Le polynôme (0,0, ,0) sera noté 0 et on a P(X) + 0 = 0 + P(X) = P(X) et 0 × P(X) = P(X) × 0 = 0. Le polynôme (1,0,0 ,0) sera noté 1 et on a 1 × P(X) = P(X) × 1 = P(X).
• Le polynôme P(X) = (0,1,0, ,0) sera noté X et appelé l’indéterminée ou la variable.
• Le polynôme sera noté
n facteurs
Xn,
• Si P(X) 6= 0 alors il existe un indice n tel que si
P(X) = (a0,a1, ,am)
on ait a` = 0 pour ` ? n + 1. L’entier n sera appelé le degré du polynôme P et sera noté deg(P). Le degré du polynôme 0 n’est pas défini, on lui donne parfois par convention le degré ??.
• Avec ces notations on écrira le polynôme P(X) = (a0,a1, ,an) de degré n sous la forme P(X) = a0 +a1X +a2X2 +···+anXn, le terme aiXi, 0 ? i ? n sera appelé le terme de degré i de P(X). On remarque que l’on a aussi P(X) = a0 + a1X + ··· + anXn + 0xn+1 + ··· + 0xm
• Un polynôme non nul, P(X), sera dit unitaire si le coefficent de son terme de plus haut degré est 1.
Muni de ces deux opérations K[X] est un anneau commutatif unitaire, cf. [20], muni d’une division euclidienne définie de la manière suivante
Définition 11.6.2 (Division euclidienne).Si A(X) et B(X) sont deux polynômes de K[X] (B 6= 0) il existe un unique couple de polynômes Q(X) et R(X) tel que
( ou bien R = 0
A(X) = B(X)Q(X) + R(X) et ou bien 0 ? deg(R) ? deg(B) ? 1
On dit que B(X) est un diviseur de A(X) s’il existe Q(X) ? K[X] tel que A(X) = B(X)Q(X), on note B(X)|A(X).
On dit que deux polynômes non nuls A(X) et B(X) sont associés s’il existe a ? K?tel que A(X) = a × B(X).
La notion de divisibilté fournit une relation d’ordre partielle sur l’anneau des polynômes.
Tout polynôme A(X) = a0 +a1X +···+anXn a au moins comme diviseurs les éléments non-nuls de K et lui-même car si a 6= 0 ? K alors a?1 existe et on a
Mais il peut en avoir d’autres par exemple:
X2 ? 1 = (X ? 1)(X + 1)
X2 ?1 a donc comme diviseurs les constantes non nulles (=K?), les polynômes X?1 et X+1 à une constante multiplicative non nulle près et lui-même à une constante multiplicative non nulle près.
Un polynôme, P(X), est appelé une unité de K[X] s’il est réduit à un élément de K? = K \ {0}, autrement dit si P?1 existe dans K[X]
Définition 11.6.3.Un polynôme P(X) ? K[X] est appelé un polynôme premier ou si ses seuls diviseurs sont lui-même et les élements de K?
Exemples26. Dans Q[X] le polynôme X2 + 1 est irréductible, par contre dans F2[X] il ne l’est pas car sur F2 on a X2 + 1 = (X + 1)2.
Proposition 11.6.4.Tout polynôme non nul A(X) ? K[X] possède une décomposition en un produit de polynômes premiers
A(X) = a · P1(X)P2(X) Pm(X) ou` a ? K?, Pj(X) premier pour 1 ? j ? m
Cette décomposition est unique à l’unité a près et à l’ordre près des facteurs Pj. Si l’on regroupe tous les polynômes Pj associés la décomposition en produit de polynômes premiers prend la forme suivante
A(X) = a · P1(X)?1P2(X)?2P`(X)?`, ?i ? N, ou` a ? K?, Pj(X) premier pour 1 ? j ? `,
Pi et Pj ne sont pas associés pour i 6= j
sous cette forme la décomposition est unique à l’unité a près et à l’ordre des facteurs si on choisit les Pj unitaires et les ?i ? 1 (c’est à dire qu’on s’interdit des exposant nuls).
Démonstration: La preuve repose sur l’algorithme de division euclideienne, cf. [20].
On définit alors comme dans le cas de Z la notion de Plus Grand Commun Diviseur (PGCD) de deux polynômes. Les degrés des diviseurs unitaires communs à A et B forment un ensemble majoré par le maximum des degrés de A et de B.
Définition 11.6.5.Le PGCD de deux polynômes A(X) et B(X) de K[X] est le polynôme unitaire de plus grand degré D(X) qui divise à la fois A(X) et B(X). On note PGCD(A,B) = A ? B
Proposition 11.6.6.Soient A(X) et B(X) des polynômes non nuls. On peut toujours supposer, quitte à modifier les unités a et b et à utiliser des exposants, que leurs décomposition en produit de facteurs premiers unitaires est
A(X) = a × P1(X)?1P2(X)?2Pr?r,
B(X) = b × P1(X)?1P2(X)?2Pr(X)?r, avec ?i,?i ? 0 alors le PGCD de A et de B est:
A(X) ? B(X) = P1(X)inf{?1,?1}P2(X)inf{?2,?2} Pr(X)inf ?r,?r
Démonstration: Pour la démonstration voir [20].
Ni la définition ni la proposition 11.6.6 ne fournissent d’algorithmes très effecaces pour calculer le PGCD de deux polynômes, A(X) et B(X).
Par contre l’algorithme de la division euclidienne en fournit un très efficace.
Proposition 11.6.7.Le PGCD des polynômes A et B est donné par l’algorithme suivant. On écrit les divisions euclidiennes successives
?
??????AB((XX) =) = BQ(1X(X)Q)R(X1(X)0) ++ RR1(2X(X))
??
????R1(X) = Q2(X)R2(X) + R3(X)
?.
(11.11) ..
?????????RRjj??21((XX) =) = QQjj?(X1()XR)jR(Xj?) +1(XR) +j+1R(Xj()X)
??
??Rj(X) = qj+1(X)rj+1(X)
avec (0 ? deg(R1) < deg(B) ou R1 = 0), (0 ? deg(R2) < deg(R1) ou R2 = 0), 0 ? deg(R3) < deg(R2), , 0 ? deg(Rj) < deg(Rj+1).
On arrête l’algorithme dès qu’un reste est nul et alors
A(X) ? B(X) = Rj+1(X)
La dernière identité de division enclidienne de (11.11)
montre que Rj+1 divise Rj, l’avant dernière identité de division enclidienne de (11.11) montre que Rj+1 divise Rj et Rj?1. Puis par récurrence on montre que Rj+1 divise A et B.
Donc Rj+1 est un diviseur commun de A et de B, est-ce le plus grand? Considérons un diviseur commun de A et de B noté D. Par définition D divise A et B donc d’après la première des identités de division enclidienne de (11.11) on a D|R1, alors la deuxième des identités de division euclidienne de (11.11) implique que D|R2 puis par récurrence on montre que D|Rj+1.
On a donc montré que tout diviseur D commun de A et de B est un diviseur de Rj+1 et comme Rj+1 est un diviseur de A et de B c’est le plus grand, autrement dit Rj+1 = A ? B.
L’arithmétique de K[X] est donc tout à fait parallèle à celle de Z.
• Les deux sont des anneaux munis d’une division euclidienne.
• On définit sur K[X] une notion de factorisation en facteurs premiers,
• On peut définir le PGCD de deux polynômes,
• Il y a sur K[X] une relation de Bezout, un algorithme d’Euclide étendu pour calculer le PGCD.
• etc..
On a le théorème de Bézout comme dans le cas des entiers
Théorème 11.6.8 (Théorème de Bézout).Soient A(X),B(X) ? K[X], alors il existe des polynômes U(X),V (X) ? K[X] tels que
(11.12) A(X)U(X) + B(X)V (X) = A(X) ? B(X) = D(X)
Démonstration: La preuve est la même que sur Z. On reprend l’algorithme du PGCD (11.11) à partir de la fin. On écrit avec les notations précédentes
On a une relation de récurrence facile sur Uj et Vj.
Uj+1 = Uj?1 ? Qj+1Uj
Vj+1 = Vj?1 ? Qj+1Vj
On définit alors les congruences entre polynômes comme dans le cas des entiers
Définition 11.6.9.Si P(X) ? K[X] et si A(X), B(X) appartiennent à K[X] on dit que A et B sont congrus modulo P s’il existe Q ? K[X] tel que A ? B = PQ. On écrira A ? B mod P.
On vérifie aisément que c’est une relation d’équivalence sur l’anneau des polynômes qui est compatible aux opérations sur les polynômes.
Proposition 11.6.10.L’addition et la multiplication sont compatibles à la relation de congruence sur les polyômes; autrement dit si P(X) est un polynôme fixé et si A(X),B(X) ? K[X] alors
Démonstration: Pour la preuve cf. [19]
Proposition 11.6.11.L’anneau des polynômes modulo la relation d’équivalence noté
K[X]/P(X)K[X] ou K[X]/P(X)
est un anneau commutatif unitaire et c’est un corps si P est irréductible Pour la première partie cf. [20]. Si P est irréductible
alors par définition si A(X) 6? 0 (mod P(X)) on a A(X)?B(X) = 1. Donc d’après le théorème de Bezout, il existe U(X),V (X) ? K[X] tels que
A(X)U(X) + P(X)V (X) = 1
et donc
A(X)U(X) ? 1 mod P(X)
Donc si P(X) est irréductible tout élement non nul de K[X]/P(X) possède un inverse multiplicatif, autrement dit c’est un corps.
Proposition 11.6.12.Un système complet de représentants de
K[X]/P(X)K[X]
est l’ensemble des restes de la division euclidienne des polynômes de K[X] par P(X).
Démonstration: C’est immédiat.
Si K est un corps fini, Fp, et si P est un polynôme irréductible sur Fp alors Fp[X]/P(X) est un corps fini qui contient Fp. Sur tout corps fini il y a des polynômes irréductibles de degré n pour tout n, [20].
Exemples27. Sur F2 le polynôme P = X2 + X + 1 est irréductible car il n’est divisible par aucun polynôme de degré 1. En effet les seuls polynômes de degré 1 de F2[X] sont X et X + 1 = X ? 1 et il est clair que dans F2[X]
les équations
X2 + X + 1 = X(X + b), X2 + X + 1 = (X + 1)(X + b)
n’ont pas de solution.
Donc F2[X]/X2 +X +1 est un corps noté dont on va donner les éléments
Rappelons que dans F2 on a 0 + 1 = 1 + 1 = 0, 0 + 1 = 1 + 0 = 1, 0 × 0 = 0 × 1 = 0 × 0 = 0 et 1 × 1 = 1 et donc que dans F2, 1 = ?1 et 1 + 1 = 2 = 0.
L’addition sur est donnée par la table suivante
| + | 1 | X | X + 1 | |
| 1 | X | X + 1 | ||
| 1 | 1 | X + 1 | X | |
| X | X | X + 1 | 1 | |
| X + 1 | X + 1 | X | 1 |
Cette table est évidente.
La multiplication sur est donnée par la table suivante
| × | 1 | X | X + 1 | |
| 1 | 1 | X | X + 1 | |
| X | X | X + 1 | 1 | |
| X + 1 | X + 1 | 1 | X |
Les seules choses à montrer sont
X × X = X2 ? X + 1 mod X2 + X + 1
X × X + 1 = X2 + X ? 1 mod X2 + X + 1
| (X + 1) × (X + 1) = (X + 1)2 ? X + 1 ce qui est vrai car | mod X2 + X + 1 |
| X2 ? (X + 1) = X2 + X + 1 ? 0 | mod X2 + X + 1 |
| X2 + X ? 1 = X2 + X + 1 ? 0 | mod X2 + X + 1 |
| (X + 1)2 ? (X + 1) = X2 + X + 1 ? 0 | mod X2 + X + 1 |
Donc dans l’inverse multiplicatif de X + 1 est X.
Le théorème des restes chinois se généralise sans difficulté à K[X] avec la même preuve.
Corollaire 11.6.13.Si p est un nombre premier et si P(x) est un polynôme irréductible de degré f de Fp[X] alors Fp[X]/P(X)Fp[X] est le corps fini Fq à q = pf éléments. En particulier si p = 2 et P(X) = X8 +X4 +X3 +X +1 alors F2[X]/P(X)F2[X] est le corps fini à 28 = 256 éléments.
Il suffit de remarquer que Fp[X]/P(X)Fp[X] est un Fp
espace vectoriel dont une base est constituée des classes de 1, X, , Xi, , Xf?1, et donc le cardinal de Fp[X]/P(X)Fp[X] est pf = q.
On a vu que est un groupe multiplicatif cyclique à q ? 1 éléments. On peut donc considérer des cryptosystèmes El Gamal utilisant le groupe , par exemple
Exemples28. Considérons p = 3, on montre facilement que le polynôme P(X) = X3 ? X + 1 est un polynôme irréductible de F3[X]. En effet sinon on aurait nécessairement une décomposition
X3 ? X + 1 = (X + a)(X2 + bX + c), avec a,b,c ? F3 ' Z/3Z
avec un facteur de degré 1 au moins. Autrement dit le polynôme P(X) aurait au moins une racine dans F3, or on vérifie aisément avec le petit théorème de Fermat que
P(0) = P(1) = P(2) = 1
Donc F3[X]/(X3 + X + 1)F3[X] n’est autre que le corps F33 à 27 éléments.
On a vu que son groupe multiplicatif est cyclique. Trouvons un générateur g sous forme polynomiale. Montrons que que la classe de X modulo
X3 ? X + 1 engendre.
| i | 1 | 2 | 3 | |
| Xi | 1 | X | X2 | X + 2 |
| i | 4 | 5 | 6 | 7 |
| Xi | X2 + 2X | 2X2 + X + 2 | X2 + X + 1 | X2 + 2X + 2 |
| i | 8 | 9 | 10 | 11 |
| Xi | 2X2 + 2 | X + 1 | X2 + X | X2 + X + 2 |
| i | 12 | 13 | 14 | 15 |
| Xi | X2 + 2 | 2 | 2X | 2X2  |
| i | 16 | 17 | 18 | 19 |
| Xi | 2X + 1 | 2X2 + X | X2 + 2X + 1 | 2X2 + 2X + 2 |
| i | 20 | 21 | 22 | 23 |
| Xi | 2X2 + X + 1 | X2 + 1 | 2X + 2 | 2X2 + X |
| i | 24 | 25 | 26 | |
| Xi | 2X2 + 2X + 2 | 2X2 + 2 | 1 |
Il suffit pour cela de donner le tableau (ci-dessus) des puissances successives de X (mod X3 + X + 1). On prend comme système de représentant de
F3, {0,1,2} (en fait d’après le théorème de Lagrange il suffit de vérifier que
X13 6= 1 (mod X3 ? X + 1)).
11.7 Courbes elliptiques.
Les courbes elliptiques définies sur un corps K sont des courbes décrites par l’ensemble des solutions de certaines équations polynomiales à deux inconnues f(x,y) ? K[X,Y ]. Pour plus de précisions on pourra consulter [23] ou [24].
Définition 11.7.1.Soit R le corps des réels et soit a,b ? R tels que 4a3 + 27q2 6= 0. Une courbe elliptique non singulière définie sur R est l’ensemble E des points P de R2dont les coordonnées (x,y) sont des solutions de l’équation
y2 = x3 + ax + b
plus un point spécial O appelé le point à l’infini.
La condition 4a3 + 27q2 6= 0 assure que la courbe est sans point double. Si 4a3 + 27q2 = 0 on a affaire à une courbe singulière.
Exemples29. La courbe y2 = x3 ? 4x
Si E est une courbe elliptique non-singulière on définit sur les points de E une addition notée + qui fera de l’ensemble des points de E un groupe abélien.
• ?P ? E, par définition P + O = O + P = P.
• Si P,Q ? E avec P = (x1,y1), Q = (x2,y2) on considère les 3 cas
1. x1 6= x2
2. x1 = x2 et y1 = ?y2
3. x1 = x2 et y1 = y2
– Dans le cas 1, on note L la droite passant par P et Q. Elle coupe E en 3 points dont deux, P et Q, sont déjà connus, on note R0 = (x0,y0) le troisième point d’intersection. On prend le symétrique de R0 par rapport à l’axe des abscisses. On obtient un point R = (x0,?y0) = (x,y) qui est encore sur E. On pose par définition
P + Q = R
Par un calcul sans mystère on trouve l’équation de L
on obtient alors les coordonnées de R
– Dans le cas 2, on définit si P = (x,y) ? E, ?P = (x,?y)
(x,y) + (x,?y) = O
– Le cas 3 se ramène au cas 2 en considérant que la droite L est la tangente en P à E. On trouve que l’équation de L est
ensuite le calcul de R est identique.
On montre que la loi ainsi définie est
1. stable sur E: si P et Q appartiennent à E, P + Q ? E
2. associative: P, Q et R appartiennent à E alors (P + Q = +R = P + (Q + R)
3. commutative: P + Q = Q + P
4. possède un élément neutre, O: P + O = O + P = P
5. Chaque point de E admet un opposé pour cette addition: ?P ?
E ?Q ? E tel que P + Q = O
Cette loi fait donc des points de E définis sur K un groupe abélien.
Tout ceci est résumé par les figures suivantes:
courbe elliptique sur R, y2 = x3 ? 4x
courbe elliptique sur R y2 = x3 + 17
11.7.1 Courbes Elliptiques sur un corps fini
Le fait que le corps de base soit R ne joue pas grand rôle dans les calculs précédents (sauf pour pouvoir dessiner les courbes).
Si maintenant on a un corps fini Fq ou` q = pf avec p un nombre premier on peut refaire la théorie en supposant que l’on cherche des solutions dans F2q (on peut prendre Fp = Z/pZ).
Définition 11.7.2.Soit Fq un corps fini avec p ? 5 et soit a,b ? Fq tels que 4a3 + 27q2 6= 0. Une courbe elliptique non singulière définie sur Fq est l’ensemble E des points dont les coordonnées (x,y) sont des solutions de l’équation
y2 = x3 + ax + b
plus un point spécial O appelé point à l’infini.
Exemples30. Calculons par exemple les points de la courbe elliptique y2 = x3 + x + 6 dans F11
| x | x3 + x + 6 mod 11 | résidu quadratique? | y |
| 6 | non | ||
| 1 | 8 | non | |
| 2 | 5 | oui | 4,7 |
| 3 | 3 | oui | 5,6 |
| 4 | 8 | non | |
| 5 | 4 | oui | 2,9 |
| 6 | 8 | non | |
| 7 | 4 | oui | 2,9 |
| 8 | 9 | oui | 3,8 |
| 9 | 7 | non | |
| 10 | 4 | oui | 2,9 |
Cette courbe sur F11 admet 13 points y compris celui à l’infini.
On a le théorème important
Théorème 11.7.3 (Hasse).Soit p un nombre premier supérieur à 3 et soit q = pf. Soit E une courbe elliptique définie sur le corps fini Fq. On note #E le nombre de points de E définis sur Fq. On a
? ? q + 1 ? 2 q ? #E ? q + 1 + 2 q Le calcul de #E est difficile mais il existe un algorithme performant pour le faire l’algorithme de Schoof.
Pour pouvoir utiliser le groupe des points d’une courbe elliptique sur un corps fini, E, il faut ensuite trouver un sous-groupe cyclique aussi gros que possible afin de pouvoir transposer le schéma de codage El-Gamal. Il y a des algorithmes efficaces pour cela.
Avec des sous-groupes cycliques de E à 2160 éléments on a une très bonne sécurité si l’on prend quelques précautions pour éliminer des courbes elliptiques indésirables pour lesquelles le problème du logarithme discret est facile.
L’avantage des cryptosystèmes basés sur les courbes elliptiques est, entre autre, la possibilité d’avoir des clés courtes pour une bonne sécurité.
Sites internet
cryp1 ; donne un resumé et des références sur divers aspects de la cryptographie
hist1 ; site historique
prim1 ; donne des renseignements sur les nombres premiers (records, tests de primalité, )
cryp2 ; donne un resumé et des références sur divers aspects de la cryptographie
aes1
donne une description succincte d’AES et de sa comparaison avec triple
DES
aes2
présente des produits commerciaux utilisant AES
aes3
donne une description succincte d’AES
Bibliographie
[1] Manindra Agrawal, Neeraj Kayal & Nitin Saxena, PRIMES is in P, Annals of Mathematics160, n?2, (2004), 781-793.
[2] Fran¸cois Arnault, Théorie des nombres et Cryptographie, cours DEA Université de Limoges, 2000.
[3] Christophe Bidan, Cryptographie et Cryptanalyse, Cours,
[4] I.F Blake, G. Seroussi, N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, 265 Cambridge University Press 1999.
[5] Johannes A. Buchmann, Introduction to cryptography, Springer, Undergraduate Texts in Mathematics, 2000.
[6] Joan Daemen & Vincent Rijmen, The design of Rijndael Springer Verlag, Berlin Heidelberg New-York, 2002.
[7] W. Diffie, M.E. Helman, New Directions in Cryptography, IEEE Transactions on Information Theory, 22 , 644-654, 1976.
[8] Gilles Dubertet, Initiation à la Cryptographie, éditions Vuibert.
[9] Robert Harris, Enigma, éditions Pocket.
[10] K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, GTM, 1990.
[11] Neal Koblitz, A Course in Number Theory and Cryptography, 2nd edition, Springer, Graduate Texts in Mathematics n?114, , 1994.
[12] Neal Koblitz, Introduction to Elliptic Curves and Modular Forms, Springer-Verlag, GTM 97, 1987.
120
BIBLIOGRAPHIE
[13] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied cryptographie, Discrete Mathematics and its applications, CRC Press, 1997.
[14] Jean-Louis Pons, Introduction à la Cryptographie, cours ENSAM Aix en Provence, 2003.
[15] La Recherche
[16] Pour la Science
[17] Guy Robin, Algorithmique et cryptographie, éditions Ellipses.
[18] Claude E. Shannon, Communication Theory of secrecy systems, Bell Systems Technical Journal, 28 (1949), 656-715.
[19] Bruce Schneier, Cryptographie Appliquée, éditions Thomson Publishing.
[20] Lionel Schwartz, Mathématiques pour la Licence, Algèbre, Dunod, Paris, 1998.
[21] Simon Singh, Histoire des codes secret, JC Lattès, 1999.
[22] Jacques Stern La Science du Secret, Odile Jacob, Paris, 1998.
[23] Douglas Stinson, Cryptographie, théorie et pratique, éditions Vuibert 2e édition, 2003.
[24] Lawrence C. Washington, Elliptic Curves, Number Theory and Cryptography, Discrete Mathematics and its applications, Chapman & Hall/CRC, 2003.
[25] Benne de Weger, Cryptographic Systems, cours Technische Universiteit Eindhoven 2005; bdeweger/
[26] V. V. Yaschenko, Cryptography: An Introduction, Moscow Center for Continuous Mathematics Education, Editor AMS, 2002.
[27] Gilles Zemor´ , Cours de cryptographie, éditions Cassini, 2002.
Index
(a,b), p. 88 Nr, ..p. 40
C, p. 24 K, p. 24 P, p. 24 a ? b, p. 88
Advanced Encrytion
Standard, .. p. 34 AES, p. 34
algorithme de codage, . p. 24
algorithme de
diversification de clef, ..p. 40
analyse de fréquence, .. p. 13 arbitre, .p. 68 arithmétique modulaire, .. p. 92
asynchrone, p. 17
attaque à texte chiffré choisi, ..p. 22
attaque à texte chiffré connu, ..p. 22
attaque à texte clair choisi, .p. 22
attaque à texte clair connu, p. 22 attaques des anniversaires, p. 65
authentification, 8
authentique, ..p. 7
certificat, ..p. 60
clé publique de chiffrement, p. 48
clé secrète, p. 11 clé secrète
de déchiffrement, .p. 48
classe de congruence modulo m, . p. 94
clef d’étage, .. p. 34
clefs parasites, p. 80
couˆt en espace, .. p. 83
couˆt en temps, .. p. 83
code d’authentification, p. 63 code de Vigénère, p. 14 codes à masques jetables, .p. 18
Codes à répertoire, . p. 9
codes de César, ..p. 12
codes de substitution, . p. 12
codes de Vernam, p. 18
codes monoalphabétiques, p. 14
collisions faibles difficiles, .p. 65
collisions fortes difficiles, ..p. 65
complexité calculatoire, p. 74
complexité polynomiale, .. p. 83
complexité
non polynomiale, .p. 83
confidentialité
| 122 |
parfaite, .. p. 23, .. p. 79 confusion et diffusion, . p. 34 congrus modulo P, . p. 109 courbe elliptique non singulière, p. 113 courbe singulière, p. 113
crible d’Eratosthenes, ..p. 100
crible quadratique, . p. 102
INDEX
cryptanalyse, .p. 6 cryptographie, p. 6 cryptologie, p. 6 cryptosystème RSA, p. 27
Data Encrytion Standard, p. 34 degré du polynôme, .p. 105
DES, p. 34 digital right management, p. 31 diviseur, p. 87, p. 105
diviseurs triviaux, .. p. 87 division euclidienne, p. 86 DRM, .. p. 31
empreinte numérique, ..p. 63 engagement, ..p. 73 entropie, p. 80
espace des clefs, . p. 24
exposant de
la clé publique, p. 48
exposant de la clé secrète, ..p. 48
factorisation des entiers, ..p. 27 fonction à sens unique, p. 27 fonction d’étage, .p. 34
fonction de combinaison, ..p. 20
fonction de compression, ..p. 64
fonction de décodage, ..p. 24
gestion des droits numériques, p. 31 hash function, p. 63
indéterminée, .p. 105 indicatrice d’Euler, . p. 97 infrastructure des
systèmes à clef secrète, . p. 44
infrastructures des
systèmes à clef publique, p. 60
Intégrité des données, ..p. 8
Kerberos, ..p. 45
les mots codés, .. p. 24 les mots en clair, p. 24
LFBR, . p. 18
linear feedback register, p. 18
logarithme discret, ..p. 55
méthode de la grille, p. 10 machines de Turing, p. 81
mascarade, p. 7 modèle X.509, p. 61 module du cryptosystème, p. 48
National Bureau of
Standards, .p. 34 nombres premiers, ..p. 87
non-répudiation, .p. 8
non-répudiation
de transmission, p. 8
non-répudiation
d’origine, ..p. 8
non-répudiation de réception, . p. 8 NP, . p. 83 opérations élémentaires, .. p. 84
P, p. 82 par blocs, . p. 14 permutation initiale, p. 35 PGCD, .p. 88
PGP, p. 26
| 124 INDEX |
PKI, p. 60 plus grand commun diviseur, p. 88 point à l’infini, .. p. 113
polyalphabétique, p. 14
polynôme irréductible, 106, ..p. 106
polynôme premier, ..p. 106
polynôme unitaire, . p. 105
polynômes associés, .p. 105
porte dérobée, p. 47 preuve sans apport de connaissance, p. 32 procédé de chiffrement, p. 24 probabibilité mutuelle, .p. 78 probabilité conditionnelle, p. 78 problèmes non polynomiaux
en temps, .. p. 83
problèmes polynomiaux en temps, .. p. 82
produit de polynômes premiers, .. p. 106
protocole interactif, .p. 75 protocoles d’identification, p. 32 Public Key
Infrastructure, . p. 60
réciprocité quadratique, .. p. 99
résidus quadratiques, .. p. 98 règle de chiffrement, p. 24 règle de déchiffrement, .p. 24 racine primitive modulo p, p. 95
redondance, .. p. 80 registres à décalages, .. p. 18 représentant de la classe de congruence, p. 94
Rivest-Shamir et Adleman, .. p. 27
S-boˆ?tes, p. 36 sécurité calculatoire, p. 23 sécurité inconditionnelle, ..p. 23 sécurité prouvée, p. 23 schéma de Feistel, .. p. 34
scytale, .p. 10
Secure Hash Algorithm, .. p. 66
SHA-1, 66
signature, . p. 8
sous-exponentiel, p. 29
suites pseudo-aléatoires, .. p. 19
suites récurrentes
linéaires sur un corps fini, . p. 18 symbole de Jacobi, . p. 99
symbole de Legendre, ..p. 98 Symmetric Keys
Management, . p. 45 synchrone, .p. 17 système cryptographique produit, .p. 34
système de chiffrement itéré, p. 40
système de gestion des clefs, p. 45
tatouge, p. 31 terme de degré i, p. 105
test de Lucas, p. 100
test de primalité
de Solovay-Strassen, p. 101
théorie de l’information, .. p. 23
théorie de la complexité, ..p. 23
Tiers de Confiance, .p. 60
tiers de confiance, .. p. 68
transfert inconscient, .. p. 75
Trusted Third Party, .. p. 60
TTP, p. 60
unité, .. p. 87 unité de K[X], p. 106
variable, p. 105 watermarking, p. 31 INDEX
XOR, .. p. 20 zero-knowledge proof, ..p. 32