Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

INF4420A > Crypto1 > Flashcards

Crypto1 Flashcards

1
Q

Qu’est-ce que l’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
2
Q

Quel est la mesure du manque d’information obtenue par l’obersavation d’une variable aléatoire?

A

l’entropie( généralement en bits)

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

Qu’est-ce que la théorie de l’information?

A

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)

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

Quelles sont les caractéristiques de la source d’information?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

À quoi sert le codage?

A

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

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

Quel est le lien entre le théorème de shannon et le codage?

A

Permet de calculer la compression maximal sans perte d’information

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

Quel est le modèle de base de Shannon?

A

Alice [Source] -> Codeur(Irène) –> Canal –> décodeur -> [récepteur] Bob

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

Qu’est-ce que la source du modèle de shannon?

A
  • Produit des symboles d’un alphabet sigma, fonction “sur demande” ( un bouton)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Qu’est-ce que le codage du modèle de shannon?

A

Regroupe et transforme les symboles de la source dans un format pouvant être transmis ou sauvegardé

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

Qu’est-ce que le canal du modèle de shannon?

A

Moyen par lequel l’information est voyagé

Peut introduire du bruit, transmission peuvent être interceptés

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

Qu’est-ce que le décodage du modèle de shannon?

A

Permet de reconstruire le message original (déquence des symboles de source)

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

Qu’est-ce que l’alphabet d’une source d’information?

A

Ensemble discret fini Sigma = sigma1, sigma2, sigma{m}, symboles capable d’émettre
- la taille de sigma = |sigma| = M

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

Qu’est-ce que le contrôle d’une source d’information?

A

un “bouton” qui permet d’obtenir un symbole à la fois

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

Qu’est-ce que le principe de la boìte noire?

A

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)

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

Pourquoi l’abstraction de la boite noire de la source d’information?

A
  • Permet de discuter de l’efficacité du codage

- Permet d’analyser correctement la résistance à certaines menaces

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

Qu’est-ce qu’une source par bloc?

A

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

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

Qu’est-ce qu’une source par échantillonage?

A

source S^{1/b} = boite qui émet seulement le 1er symbole de chaque b symboles sortie de S
l’alphabet reste sigma

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

Quel est l’interprétation déterministe d’une source?

A

La boìte noire connait à l’avance toute les séquence de symboles

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

Quel est l’interprétation probabiliste d’une source?

A

La boite choisit les symboles au fur et à mesure selon une distribution de probabilité

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

Quel sont les deux modèles de processus probabiliste d’une source?

A 
Processus markovien( sans mémoire)
- Processus non-morkovien (les probabilités de symboles peuvent dépendre des symboles antérieur sortis de la source)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Qu’est-ce que la translittération?

A

traduire les symboles de source vers un autre “alphabet” (codage)

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

Quel est le premier théorème de shannon? (codage)

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Quel est la définition de l’entropie de Shannon?

A

H(S) = sommation pi log2(1/pi)

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

Quel est la valeur minimal de l’entropie?

A

H(s) = 0, quand prob(S = sigma) = 1 pour un sigma donné

25
Q

Quel est la valeur maximal de l’entropie?

A

H(S) = log(N) bis quand prob(S=sigma i) = prob (S=sigma j) pour tout sigma i, sigma j element de SIGMA
(équiprobable)

26
Q

Quel est l’entrophie d’une source markovienne?

A

H(S^b) = b*H(S)

27
Q

Quel est l’entrophie d’une source non markovienne?

A

H(S^b) <= b * H(S)

28
Q

Quel est l’entropie d’un alphabet équiprobable?

A

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

29
Q

Que dit le premier théorème de Shannon par rapport à l’entropie?

A

Chaque symbole émit par S peut être codé indificuellement avec une moyenne de H(S) bits

30
Q

Que dit le premier théorème de Shannn par rapport à un codage qui regroupe 2 lettre à la fois?

A

on peut coder chaque digramme avec H(S^2) bits, soit H(S^2)/2 bits par symboles

31
Q

Quel est le taux de compression?

A

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)

32
Q

Quel est l’entropie du langage associé à la source S ( langage = ensemble de chaînes que S génères)

A

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

33
Q

À quoi sert le code correcteur d’erreur?

A

compenser le bruit du canal de transmission

34
Q

Comment mesurer l’efficacité du code correcteur d’erreur?

A

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”

35
Q

Quel est le 2e théorème de Shannon?

A
  • Établit le lien entre l’efficacité du code correcteur d’erreur et le niveau de bruit du canal
36
Q

Quel est le modèle de Shannon révisé?

A

[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

37
Q

Est-ce qu’on est capable d’aller cherche l’algorithme de chiffrement?

A

oui, mais pas la clé utilisée pour chiffrer

38
Q

Est-ce que le codage est important, ou est-ce qu’on doit seulement se concentrer sur le chiffrement?

A

Le codage très important, même si algo en béton et clé infini, si codage pourrir, vulnérnérabilité plus facile à faire

39
Q

Quel est le rôle de Irène ( L’ingénieur)

A

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)

40
Q

Est-ce que les algorithmes de chiffrement corriges les erreurs?

A

non, donc en gnéral tau = tau prime

41
Q

Qu’est ce qu’un algorithme de substitution?

A

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

42
Q

Qu’est-ce qu’un algorithme de transposition (bit shifting)?

A

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é
43
Q

qu’est-ce qu’est l’algorithme de vigenère?

A
  • 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
44
Q

Quels sont les deux propriété recherché dans un algorithme de chiffrement?

A

confusion et diffusion

45
Q

Qu’est-ce que la confusion?

A

Propriété de rendre la relation entre la clé de chiffrement et le texte chiffré la la plus complexe possible

46
Q

Qu’es-ce que la diffusion?

A

Propriété où la redondance statistique dans un texte en clair est dissipée dans les statistiques du texte chiffré

47
Q

Quel est l’objectif de la confusion et de la diffusion?

A
  • 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
48
Q

Quels sont les deux étapes de la cryptanalyse par force brute?

A

1) déchiffrer le texte chiffré avec la clé à essayer

2) voir si le résultat est cohérent

49
Q

Combien de clés possible par force brute?

A

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

50
Q

Comment savoir si on a la bonne clé par force brute?

A
  • Patron ou format reconnaissable
  • texte a du sens
  • le text “marche” ( ex mot de passe etc)
51
Q

Qu’est-ce qui détermine la difficulté de la cryptanalyse par force brute?

A

l’entropie du message
Entropie basse = moins de messages valides = plus facile
entropie élevé = plusieurs message valides = difficile

52
Q

Qu’est-ce qu’est l’analyse fréquentielle?

A

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

53
Q

Qu’est-ce qui détermine la difficulté de la cryptanalyse par analyse fréquentielle?

A

Entropie haute = histogramme plat = difficile

Entropie basse = histogramme “escarpé” = plus facile

54
Q

Quoi faire si l’entropie est trop haute pour S durant l’analyse fréquentielle?

A

essayer pour S^2, S^3

limite ultime : entropie du langage

55
Q

L’entropie de Shannon s’applique seulement aux sources markoviennes. Quoi faire pour calculer l’entropie de sources non-markoviennes?

A

La pseudo-entropie (La fréquence des symboles)

56
Q

Qu’est-ce que la pseudo entropie?

A

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

57
Q

L’entropie par bloc est donné par quelle formule?

A

H(S^b)/b / log2(N)

58
Q

Qu’obtient-on lorsque la taille b du bloc tend vers l’infini durant l’analyse fréquentielle?

A

on optient l’entropie du langage

59
Q

Comment maximiser l’entropi sur symboles de codage?

A
  • faire du codage par bloc
  • faire du bourrage avec caractères aléatoires
  • implémenter de la compression

INF4420A (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions