Cours 6 : Crypto 1 (version courte) Flashcards
Nommer les trois eres de la cryptographie.
« Classique »
• Jusqu’au masque jetable (chiffre de Vernam)
• Chiffrement “manuel”-> chiffrement faible
« Moderne »
• Crypto électro-mécanique et WWII (voir applet Enigma)
• Guerre froide …
• Crypto électronique et informatique – DES
• Chiffrement par machines spécialisées è chiffrement plus complexes
• Réservés aux organisations pouvant acquérir l’équipement
« Âge d’or »
• Chiffrement à clé publique – 1979
• Signature numérique
• « Démocratisation » de la cryptographie
- Cryptographie sur PC
- Levée des restrictions d’exportations de cryptographie
- Internet et e-commerce
Qu’est-ce qu’une information?
Valeur instantanée d’une variable aléatoire qui est transmise vers un récepteur à travers un canal de communication.
Quels sont les concepts importants de la theorie de l’information?
§ Variable aléatoire
§ Canal de communication
§ Transmission
Definir le modele de Shannon.
Source
§ Produit des symboles d’un “alphabet” (sigma)
§ Fonctionne “sur demande” (d’où le “bouton”)
Codage
§ Regroupe et transforme les symboles de la source dans un format
pouvant être transmis ou sauvegardé
Canal
§ Peut introduire du bruit
§ Transmission peuvent être interceptés
Décodage
§ Permet de reconstruire le message original
(séquence des symboles de source)
Definir ce que sont les sources d’information.
Alphabet
§ Ensemble discret fini S = {s1, …, sM}
§ Par convention taille de S, |S| = M
Contrôle
§ un “bouton” qui permet d’obtenir un symbole à la fois
Principe de la boîte noire
§ Autre que le bouton et un nombre petit d’observations (symboles), on ne peut rien savoir sur le contenu ou fonctionnement de la source (sauf peut-être Alice, mais pas Ève, Irène ou Bob).
Pourquoi cette abstraction ??
§ Permet de discuter de l’efficacité du codage (théorie de l’information)
§ Permet d’analyser correctement la résistance à certaines menaces .
- Algorithmes de chiffrement,
- Choix de mots de passes et phrases de passe
Definir ce que sont les sources derivees.
Source par bloc
§ Étant donné une source S, et un entier positif b,
la source Sb représente la source obtenue en encapsulant S par une
boîte qui mets b symboles de S dans un tampon (“buffer”) avant
de les sortir à l’extérieur
§ Noter que l’alphabet de Sb est maintenant Sb
Source par échantillonnage
§ Étant donné une source S, et un entier positif b,
la source S1/b représente la source obtenue en encapsulant S par
une boîte qui émet seulement le 1er symbole de chaque b symboles
sortie de S dans
§ L’alphabet de S1/b est le même que S, soit S
Definir les elements du codage.
Translittération
§ Un codage traduit les symboles de source vers un autre “alphabet”
T = { t1, …, tN},
Fonction de codage
§ F : S à T,
• t = F(s), représente comment le symbole s devra être transmis
Fonction de décodage
§ F-1: T à S
• s ‘ = F -1(t),
Ø si s ‘ ≠ s, il n’y a eu une erreur de transmission/codage
Quel est le premier theoreme de Shannon.
- Efficacité maximum d’un code compresseur est approx. égale à H(S)
- Il existe un code compresseur (sans erreur) avec efficacité H(S) + 1
Definir l’algorithme de chiffrement.
Alphabet
§ Entrée : T
§ Sortie : en général T, mais peut-être un autre alphabet
Fonction de chiffrement
§ Clé de chiffrement = ke
§ t’ = E (ke, t) = Ek1 (t)
Fonction de déchiffrement
§ Clé de déchiffrement = kd
§ t = D (kd, t’) = Dk2(t)
Ne corrige pas les erreurs donc,
§ En général t = t’
Quelle est la methode de l’analyse frequentielle?
- Établir/retrouver fréquences des symboles de la source
- Calculer les fréquences des symboles chiffrés obtenus
- Comparer histogrammes de fréquences
- Établir relations entre symboles chiffrés et symboles de sources
- Essayer de déchiffrer le texte
Quelles sont les difficultes/precisions de l’analyse frequentielle?
• Codage connu => possible d’inverser le codage
• Paramètre de difficulté
Ø Entropie de la source du message
§ Entropie haute => histogramme « plat » è difficile
§ Entropie basse => histogramme « escarpé » è plus facile
• Variante - Analyse par bloc
Ø Si entropie trop haute pour S, alors on essaie avec S2, S3 , …
Ø Compromis: taille de tableau de correspondance vs. entropie
Ø Limite ultime = Entropie du langage
Definir la difference entre un processus markovien et un processus non-markovien.
Un processus non-markovien est dit avec memoire, c-a-d que Les probabilités de symboles peuvent dépendre des symboles antérieurs sortis de la source.
Un processus markovien est dis sans memoire, c-a-d que la probabilite d’apparition d’un symbole ne depend pas de l’apparitiion anterieur d’autre symboles, elle est completement independante.
Qu’est-ce que la transliteration?
Un codage traduit les symboles de source vers un autre
“alphabet”. Ce concept est appele la transliteration.
Quels sont les 4 algo classiques mono-alphabetiques?
Algo de Cesar, Algo de decalage, Algo de substitution, Algo afin.
Definir la confusion.
Confusion : propriété de rendre la relation entre la clé de chiffrement et le texte chiffré la plus complexe possible.