Cours 6 : Crypto 1 (version courte) Flashcards

1
Q

Nommer les trois eres de la cryptographie.

A

« 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Qu’est-ce qu’une information?

A

Valeur instantanée d’une variable aléatoire qui est transmise vers un récepteur à travers un canal de communication.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Quels sont les concepts importants de la theorie de l’information?

A

§ Variable aléatoire
§ Canal de communication
§ Transmission

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Definir le modele de Shannon.

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Definir ce que sont les sources d’information.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Definir ce que sont les sources derivees.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Definir les elements du codage.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Quel est le premier theoreme de Shannon.

A
    1. Efficacité maximum d’un code compresseur est approx. égale à H(S)
    1. Il existe un code compresseur (sans erreur) avec efficacité H(S) + 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Definir l’algorithme de chiffrement.

A

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’

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Quelle est la methode de l’analyse frequentielle?

A
  1. Établir/retrouver fréquences des symboles de la source
  2. Calculer les fréquences des symboles chiffrés obtenus
  3. Comparer histogrammes de fréquences
  4. Établir relations entre symboles chiffrés et symboles de sources
  5. Essayer de déchiffrer le texte
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Quelles sont les difficultes/precisions de l’analyse frequentielle?

A

• 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Definir la difference entre un processus markovien et un processus non-markovien.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Qu’est-ce que la transliteration?

A

Un codage traduit les symboles de source vers un autre

“alphabet”. Ce concept est appele la transliteration.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Quels sont les 4 algo classiques mono-alphabetiques?

A

Algo de Cesar, Algo de decalage, Algo de substitution, Algo afin.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Definir la confusion.

A

Confusion : propriété de rendre la relation entre la clé de chiffrement et le texte chiffré la plus complexe possible.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Definir la diffusion.

A

Diffusion : propriété où la redondance statistique dans un texte en clair est dissipée dans les statistiques du texte chiffré.

17
Q

Comment peut-on maximiser l’entropie sur les symboles de codage?

A

On peut
• Ajuster le codage pour maximiser l’entropie
Ø Faire du codage par bloc
Ø Faire du bourrage (“padding”) avec des caractères aléatoires
Ø Implémenter de la compression
• Utiliser des algorithmes de chiffrement probabilistes