Crypto1 Flashcards
Qu’est-ce que l’information?
Valeur instantanée d’une variable aléatoire qui est transmise vers un récepteur à travers un canal de communication
Quel est la mesure du manque d’information obtenue par l’obersavation d’une variable aléatoire?
l’entropie( généralement en bits)
Qu’est-ce que la théorie de l’information?
On représente la variable aléatoire et son observation directe comme une SOURCE d’information
(équivalent à une boîte noire qui qui produit de façon aléatoire une série de bits représentant la valeur de la variable aléatoire)
Quelles sont les caractéristiques de la source d’information?
- Elle produit de l’information pure, sous forme abstraite
- Elle ne s’adapte pas au canal de transmission ( le codage oui)
- Ne peut pas être interprétée par un récepteur
À quoi sert le codage?
Avoir une représentation physique des données pour pouvoir les transportées et les interprétés ( s’adapte au canal de transmission, permer au récepteur de décoder l’information, et le convertir en forme intelligible)
PAS DU CHIFFREMENT
permet la compression
Quel est le lien entre le théorème de shannon et le codage?
Permet de calculer la compression maximal sans perte d’information
Quel est le modèle de base de Shannon?
Alice [Source] -> Codeur(Irène) –> Canal –> décodeur -> [récepteur] Bob
Qu’est-ce que la source du modèle de shannon?
- Produit des symboles d’un alphabet sigma, fonction “sur demande” ( un bouton)
Qu’est-ce que le codage du modèle de shannon?
Regroupe et transforme les symboles de la source dans un format pouvant être transmis ou sauvegardé
Qu’est-ce que le canal du modèle de shannon?
Moyen par lequel l’information est voyagé
Peut introduire du bruit, transmission peuvent être interceptés
Qu’est-ce que le décodage du modèle de shannon?
Permet de reconstruire le message original (déquence des symboles de source)
Qu’est-ce que l’alphabet d’une source d’information?
Ensemble discret fini Sigma = sigma1, sigma2, sigma{m}, symboles capable d’émettre
- la taille de sigma = |sigma| = M
Qu’est-ce que le contrôle d’une source d’information?
un “bouton” qui permet d’obtenir un symbole à la fois
Qu’est-ce que le principe de la boìte noire?
On ne peut rien savoir sur le contenue ou le fonctionnement de la source, autre que le bouton et un petit nombre d’observation(sauf pe alice, mais pas eve, ni irène ni Bob)
Pourquoi l’abstraction de la boite noire de la source d’information?
- Permet de discuter de l’efficacité du codage
- Permet d’analyser correctement la résistance à certaines menaces
Qu’est-ce qu’une source par bloc?
source S^b représente la source obtenue en encapsulant S par une boîte qui mets b symboles de S dans un tampon, avant de les sortir à l’extérieur
alphabet est maintenant sigma^b
Qu’est-ce qu’une source par échantillonage?
source S^{1/b} = boite qui émet seulement le 1er symbole de chaque b symboles sortie de S
l’alphabet reste sigma
Quel est l’interprétation déterministe d’une source?
La boìte noire connait à l’avance toute les séquence de symboles
Quel est l’interprétation probabiliste d’une source?
La boite choisit les symboles au fur et à mesure selon une distribution de probabilité
Quel sont les deux modèles de processus probabiliste d’une source?
Processus markovien( sans mémoire) - Processus non-morkovien (les probabilités de symboles peuvent dépendre des symboles antérieur sortis de la source)
Qu’est-ce que la translittération?
traduire les symboles de source vers un autre “alphabet” (codage)
Quel est le premier théorème de shannon? (codage)
- l’efficacité maximum d’un code compresseur est environ égale à H(s)
- Il existe un code compresseur (sans errur) avec l’efficacité H(s) + 1
Quel est la définition de l’entropie de Shannon?
H(S) = sommation pi log2(1/pi)
Quel est la valeur minimal de l’entropie?
H(s) = 0, quand prob(S = sigma) = 1 pour un sigma donné
Quel est la valeur maximal de l’entropie?
H(S) = log(N) bis quand prob(S=sigma i) = prob (S=sigma j) pour tout sigma i, sigma j element de SIGMA
(équiprobable)
Quel est l’entrophie d’une source markovienne?
H(S^b) = b*H(S)
Quel est l’entrophie d’une source non markovienne?
H(S^b) <= b * H(S)
Quel est l’entropie d’un alphabet équiprobable?
log2(M) M étant le nombre de symboles de l’alphabet SIGMA
exemple, l’entropie d’un alphabet contenant tous les lettres de l’alphabet, log2(26) = 4.7 bits
Que dit le premier théorème de Shannon par rapport à l’entropie?
Chaque symbole émit par S peut être codé indificuellement avec une moyenne de H(S) bits
Que dit le premier théorème de Shannn par rapport à un codage qui regroupe 2 lettre à la fois?
on peut coder chaque digramme avec H(S^2) bits, soit H(S^2)/2 bits par symboles
Quel est le taux de compression?
soit logN, le nombre de bits par symboles avec un codage sans compression, et soit H(S^b)/b bits par lettre pour un encodage avec compression par bloc de b lettre, le taux de compression se définis par
H(S^b)/b / logN
pour une transmission sans perte (environ capable 1/10 de nos jours)
Quel est l’entropie du langage associé à la source S ( langage = ensemble de chaînes que S génères)
HL(S) = lim(b-> infini) H(S^b)/b
représente le minimum de bits par symboles qu’il sera nécessaire pour coder des chaînes de symboles émises par S, même si on permet de coder par blocs de plusieurs symboles à la fois
À quoi sert le code correcteur d’erreur?
compenser le bruit du canal de transmission
Comment mesurer l’efficacité du code correcteur d’erreur?
Il dépend du niveau de bruit introduit par le canal( mesuré par l’entropie de Shannon).
- Se mesure égaelement en nombre de bits nécessaire par symbole de source, pour un code qui corrige “presque toutes les erreurs”
Quel est le 2e théorème de Shannon?
- Établit le lien entre l’efficacité du code correcteur d’erreur et le niveau de bruit du canal
Quel est le modèle de Shannon révisé?
[alice] Source -> (sigma) -> Codeur -> (tau) -> Chiffrement (tau prime) -> déchifrement -> (taux) -> décodeur -> (sigma) -> Récepteur [Bob]
Eve à accès a sigma, tau?), et tau prime
Irène à accès a la boite de codage et de chiffrement
alice : source, Bob récepteur
Est-ce qu’on est capable d’aller cherche l’algorithme de chiffrement?
oui, mais pas la clé utilisée pour chiffrer
Est-ce que le codage est important, ou est-ce qu’on doit seulement se concentrer sur le chiffrement?
Le codage très important, même si algo en béton et clé infini, si codage pourrir, vulnérnérabilité plus facile à faire
Quel est le rôle de Irène ( L’ingénieur)
Choisir l’algo de chiffrement, déterminer la politique de choix et gestion de clés et doit tenir en compte le codage (en consigérant caractéristiques de la source, en influencant le choix de codage et en choisissant et adaptant l’algorithme de chiffrement en conséquence)
Est-ce que les algorithmes de chiffrement corriges les erreurs?
non, donc en gnéral tau = tau prime
Qu’est ce qu’un algorithme de substitution?
On prend un texte en claire et, pour chacune des lettres du texte, on utilise la lettre comme index dans une table de substitution pour trouver l’équivalent chiffré
- possède la confusion
Qu’est-ce qu’un algorithme de transposition (bit shifting)?
On prend un texte en clair et on permute la position des lettres ( ou bits ou wtv) entre elles en fonction d’une clé
- Antiquité : utilisait baton autour duquel on enroulait une lanière de cuir où était écrit le texte
- mauvaise confusion car facile de retrouver la clé à partir du texte chiffré
- diffusion raisonnable car la disparition d’une lettre entraîne la modification de tout le texte chiffré
qu’est-ce qu’est l’algorithme de vigenère?
- algorithme polyalphabétique (une lettre peut avoir 2 valeurs)
clé K = k1k2..km, mot/phrase de longueur m,
xi -> 9xi + k(i mod m) mod 26
Quels sont les deux propriété recherché dans un algorithme de chiffrement?
confusion et diffusion
Qu’est-ce que la confusion?
Propriété de rendre la relation entre la clé de chiffrement et le texte chiffré la la plus complexe possible
Qu’es-ce que la diffusion?
Propriété où la redondance statistique dans un texte en clair est dissipée dans les statistiques du texte chiffré
Quel est l’objectif de la confusion et de la diffusion?
- Empêcher de retrouver la clé à partir de paires texte chiffré et texte déchiffré ( attaque à texte choisi)
- Rendre plus difficile l’analyse fréuentielle
Quels sont les deux étapes de la cryptanalyse par force brute?
1) déchiffrer le texte chiffré avec la clé à essayer
2) voir si le résultat est cohérent
Combien de clés possible par force brute?
2^N où l’entropie de la source K générant les clés H(K) <= N
et N = N bits de clés
Comment savoir si on a la bonne clé par force brute?
- Patron ou format reconnaissable
- texte a du sens
- le text “marche” ( ex mot de passe etc)
Qu’est-ce qui détermine la difficulté de la cryptanalyse par force brute?
l’entropie du message
Entropie basse = moins de messages valides = plus facile
entropie élevé = plusieurs message valides = difficile
Qu’est-ce qu’est l’analyse fréquentielle?
trouver les fréquences de symboles d’une source, puis faire la meme chose avec les symboles chiffrés obtenus
comparer les histogrammes de fréquences et établir des relations entres les symbols
Qu’est-ce qui détermine la difficulté de la cryptanalyse par analyse fréquentielle?
Entropie haute = histogramme plat = difficile
Entropie basse = histogramme “escarpé” = plus facile
Quoi faire si l’entropie est trop haute pour S durant l’analyse fréquentielle?
essayer pour S^2, S^3
limite ultime : entropie du langage
L’entropie de Shannon s’applique seulement aux sources markoviennes. Quoi faire pour calculer l’entropie de sources non-markoviennes?
La pseudo-entropie (La fréquence des symboles)
Qu’est-ce que la pseudo entropie?
sommation des fi(SN) log(1/fi(SN)).
ou SN est la sous séquence des N premier symboles
L’analyse des fréquences. Presque la vrai entropie
Un estimateur statistique de l’entropie
L’entropie par bloc est donné par quelle formule?
H(S^b)/b / log2(N)
Qu’obtient-on lorsque la taille b du bloc tend vers l’infini durant l’analyse fréquentielle?
on optient l’entropie du langage
Comment maximiser l’entropi sur symboles de codage?
- faire du codage par bloc
- faire du bourrage avec caractères aléatoires
- implémenter de la compression
