Brainscape's Knowledge GenomeTM

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


See full index

7 - Calcul Formel > Cours LB partie 1 > Flashcards

Cours LB partie 1 Flashcards

1
Q

De quelles façons peut-on sécuriser une communication entre deux personnes qui ne se sont jamais rencontrées ?

A
  • En utilisant un protocole d’échange de clés puis de la cryptographie symétrique
  • En utilisant du chiffrement asymétrique
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Protocole d’échange de clés Diffie-Hellman

A
  • A et B choisissent un groupe cyclique (G, ×) d’ordre q et un générateur du groupe G
  • A calcule hA = gx pour 0 ≤ x < q - 1 aléatoire
  • B calcule hB = gy pour 0 ≤ y < q - 1 aléatoire
  • A et B s’échangent hA et hB publiquement
  • A calcule hBx et B calcule hAy, et hAy = hBx
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Correction du protocole Diffie-Hellman (schéma de preuve)

A

hAy
= gxy
= gxy
= gyx
= hBx

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

Détail du calcul de complexité de Diffie-Hellman

A
  • Choisir p premier → polynomial
  • Choisir un générateur du groupe G = ({Z}/p{Z})* → polynomial
  • Calculer gx dans ({Z}/p{Z})* → polynomial
    Diffie-Hellman est donc polynomial
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Comment choisir un entier premier aléatoire ?

A

En faisant une boucle entre 2b-1 et 2b et en utilisant un test de primalité sur chaque élément avec
- test de Miller-Robin probabiliste polynomial
- test AKS déterministe polynomial
donc polynomial au total car la probabilité de tomber sur un entier premier est d’environ 1/logn

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

Comment choisir un générateur pour un groupe ({Z}/p{Z})* ?

A

Si p = 2q + 1 avec q premier, il existe un algorithme polynomial

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

Comment calculer gx dans ({Z}/p{Z})* ?

A
  • Mauvaise méthode :
    • Exponentiation classique
    • Complexité exponentielle en logp
  • Bonne méthode :
    • Exponentiation rapide : x = x0 + 2x1 + … + 2kxk → gx = gx0 × (g2)x1 × … × (g2k)xk
    • O(k) multiplications pour calculer (g2i) et O(k) multiplications supplémentaires, avec chacune en O(logp2), donc logpO(1) en tout
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Quels sont les problèmes auxquels on se rapporte pour évaluer la sécurité d’un protocole ?

A
  • Problème du logarithme discret
  • Problème de Diffie-Hellman calculatoire
  • Problème de Diffie-Hellman décisionnel
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Problème du logarithme discret

A
  • Entrée : G, q, g, h ∈ G
  • Sortie : x tel que h = gx
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Problème de Diffie-Hellman calculatoire

A
  • Entrée : G, q, g, h1, h2 ∈ G
  • Sortie : gxy où h1 = gx, h2 = gy et 0 ≤ x, y ≤ q
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Problème de Diffie-Hellman décisionnel

A
  • Entrée : G, q, g, h1, h2, h3 ∈ G
  • Sortie : Est-ce que h3 = gxy si h1 = gx, h2 = gy et 0 ≤ x, y ≤ q ?
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Comparaison de la complexité des trois problèmes LD, DHC et DHD

A

DHD ≤ DHC ≤ LD, puisqu’on peut résoudre DHC avec LD (et pas l’inverse) et DHD avec DHC (et pas l’inverse)

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

Hypothèse du logarithme discret

A

Les trois problèmes LD, DHC et DHD sont difficiles

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

Qu’est-ce qu’un protocole asymétrique ?

A

Un protocole dans lequel il y a
- une clé publique avec laquelle tout le monde peut encoder
- une clé privée avec laquelle seuls ceux qui l’ont peuvent déchiffrer

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

Générées des clés dans le protocole de chiffrement asymétrique El-Gamal

A
  • G un group cyclique d’ordre q avec g un générateur
  • 0 ≤ x ≤ q aléatoire
  • Clé publique pk = (G, q, g, h = gx)
  • Clé privée sk = x
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Chiffrement d’un message dans le protocole de chiffrement asymétrique El-Gamal

A
  • m ∈ G un message
  • 0 ≤ y ≤ q aléatoire
  • Encpk(m) = (gy, hy × m) ∈ G2
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Déchiffrement d’un message dans le protocole de chiffrement asymétrique El-Gamal

A

Soit c = (c1, c2) ∈ G2, alors Decsk(c) = c2/c1x = c2 × (c1-1)x

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

Correction du protocole de chiffrement asymétrique El-Gamal (schéma de preuve)

A

Dec(Enc(m))
= hy × m / (gy)x
= (gx)y × m / (gy)x
= gxy × m / gxy
= m

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

Calcul d’inverse dans ({Z}/p{Z})*

A
  • Inverse de a : 1/a mod p tel que 0 < a < p ⇔ b tel que a × b = 1 mod p
  • Algorithme d’Euclide étendu sur (a, p) → (r, s) tel que a × r + p × s = 1 ⇔ a × r = 1 - p × s = 1 mod p, donc b = r
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Que peut-on dire de l’attaque “Écoute des communications” sur le protocole d’échange de clés de Diffie-Hellman ? (schéma de preuve)

A

L’écoute des protocoles permet d’obtenir gx et gy, obtenir gxy à partir de là revient à résoudre DHC, l’attaque est donc difficile

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

Que peut-on dire de l’attaque “Tentative de déchiffrement d’un message” sur le protocole El-Gamal ? (schéma de preuve)

A
  • Supposons que l’attaque est facile, alors algorithme A qui prend (pk, c1, c2) = (gx, gy, gxy × m) et renvoie m = c2/c1x
  • Soit alors un algorithme R qui prend (gx, gy) et renvoie c2/A(gx, gy, c2) = c2/m = (gxy × m)/m = gxy
  • R permet de résoudre DHC avec A, donc A ne peut pas exister
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Quels sont les objectifs possibles d’une attaque ?

A
  • Total break : retrouver la clé secrète
  • One-way : déchiffrer un message
  • Indistingabilité : retrouver un bit d’information du message
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Quels sont les moyens possibles pour une attaque ?

A
  • Chosen plaintext : savoir chiffrer un message
  • Chosen cyphertext : savoir déchiffrer un message
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Comment montrer qu’un protocole est insécuritaire ?

A

En construisant un algorithme en temps polynomial qui permet d’effectuer une attaque

25
Q

Qu’est-ce qu’un chiffrement malléable ?

A

Un chiffrement est dit malléable si étant donné un chiffré c d’un message inconnu m, alors on peut créer un chiffré c’ != c d’un message m’ lié à m
Ainsi, si Enc(m) = (c1, c2) = (gy, hym avec h = gx, on peut écrire (c’1, c’2) = (c1, c2gu) = Enc(mgu) = Enc(m’)

26
Q

Comment effectuer une attaque OW-CPA sur El-Gamal ?

A
  • Récupérer c le chiffrement de m et encoder un message m’ = mgu à partir de lui
  • Utiliser un oracle de déchiffrement D que l’on ne peut pas appliquer sur Enc(m) = (c1, c2) mais qu’on va pouvoir utiliser sur Enc(m’) = (c’1, c’2) = (c1, c2gu)
  • Renvoyer m’ / gu = m
27
Q

Difficulté de IND-CCA sur El-Gamal

A

Facile d’après la facilité de OW-CCA

28
Q

Difficulté de IND-CPA sur El-Gamal

A

Difficile sous hypothèse DHD

29
Q

Difficulté de OW-CCA sur El-Gamal

A

Facile d’après le cours

30
Q

Difficulté de OW-CPA sur El-Gamal

A

Difficile d’après le cours

31
Q

Difficulté de TB-CCA sur El-Gamal

A

?

32
Q

Difficulté de TB-CPA sur El-Gamal

A

Difficile sous hypothèse DHC ou LD

33
Q

Algorithme naïf pour le calcul du logarithme discret

A
  • Entrée : G, q, g, h ∈ G
  • Sortie : x tel que h = gx
  • Algorithme :
    • Pour x de 0 à q-1 :
      • Si h == gx
        • Renvoyer x
34
Q

Complexité de l’algorithme naïf pour le calcul du logarithme discret

A

L’algorithme effectue O(q) produits dans G, donc il est exponentiel en log(q) la taille de l’entrée (h)

35
Q

Hypothèse nécessaire à l’algorithme de Pohlig-Hellman

A

On considère que l’ordre q n’est pas premier et que l’on connaît une factorisation q = Πi=1..h qi avec les qi premiers entre eux et on cherche à réduire le logarithme discret sur G d’ordre q à h lorgarithmes discrets sur des petits groupes d’ordre qi

36
Q

Idée de l’algorithme de Pohlig-Hellman

A

Plutôt qu’effectuer le clacul du logarithme discret en une seule fois sur le groupe G d’ordre q, on cherche à à le réduire sur des plus petits groupes d’ordre qi

37
Q

Qu’est-ce que l’ordre d’un élément g d’un groupe G ?

A

ordre(g) = min{n ∈ G* | gn = 1}

38
Q

Ordre de gi = gq/qi (énoncé)

A

ordre(gi) = qi

39
Q

Ordre de gi = gq/qi (schéma de preuve)

A
  • Montrer que si G est fini, alors ∃ u > v tels que gu = gv, car go = gu-v = 1 donc gu × g-v = 1
  • Montrer que (gq/qi)qi = gq = 1
  • Montrer que qi est le plus petit ordre de gi possible car gij != 1 pour j < qi car (qi × j)/q < q
40
Q

Sous-groupe Gi de G d’ordre qi

A

Gi = <gi> = {gi0, …, giq-1}

41
Q

Congruence modulo ordre dans un groupe (énoncé)

A

Si G = <g> d'ordre q, alors gx = gy si et seulement si x = y mod q</g>

42
Q

Congruence modulo ordre dans un groupe (schéma de preuve)

A

⇐
x = y mod q, donc il existe k tel que x = y + kq et gx = gy + kq = gygkq = gy

⇒
gx = gy, alors gx / gy = 1 = gx-y donc x - y = 1 mod q et x = y mod q

43
Q

Lien entre (x mod q) et (x mod q1, …, x mod qh) où (q1, …, qh) est une factorisation de q

A

Si on connaît (x mod q1, …, x mod qh) , on peut retrouver (x mod q) en utilisant le théorème des restes chinois

44
Q

Théorème des restes chinois (énoncé)

A

Il y a une bijection C entre (x mod q1, …, x mod qh) et (x mod q) sous l’hypothèse que q = Πi=1..h qi avec les qi premiers entre eux

45
Q

Théorème des restes chinois (schéma de preuve)

A
  • Les deux parties sont de la même taille, donc il suffit de montrer qu’il y a une injection pour conclure qu’une bijection existe
  • Prendre x et x’ tels que C(x) = C(x’) et montrer que x = x’ mod q en sachant que x = x’ mod qi pour i = 1..h, c’est-à-dire que qi divise x - x’ pour i = 1..h donc le produit des qi divise x - x’ si les qi sont premiers entre eux, et on trouve bien que q divise x - x’ donc x = x’ mod q
46
Q

Lien entre la division euclidienne et les nombres premiers entre eux

A

Si a divise c, b divise c et a et b sont premiers entre eux, alors ab divise c

47
Q

Algorithme de Pohlig-Hellman pour le calcul du logarithme discret

A
  • Entrée : G = <g> d'ordre q, q = Πi=1..h qi, h ∈ G</g>
  • Sortie : x tel que h = gx
  • Algorithme :
    • Pour i de 1 à h :
      • gi = gq/qi
      • hi = hq/qi
      • xi = LD(gi, hi)
    • Renvoyer x = ResteChinois(x1, …, h)
48
Q

Calcul de la complexité de l’algorithme de Pohlig-Hellman

A
  • Calcul de gi : logq multiplications dans G
  • Calcul de hi : logq multiplications dans G
  • Calcul de xi : LD(qi)
  • Total : LD(q) = Σi=1..h LD(qi) + log(q)O(1) = h × q1/h + log(q)O(1)
49
Q

Quelle est la forme optimale de q pour appliquer l’algorithme de Pohlig-Hellman ?

A

Pour appliquer l’algorithme de façon optimale, il faut prendre q = 2q’ tel que p = 2q’ + 1 et q’ premier, et travailler dans G’ = <g2>

50
Q

Principe de l’algorithme “pas de bébé pas de géant”

A

On voudrait pré-calculer tous les LD, mais cela a un coût trop élevé (O(q)), donc on pré-calcule seulement certains points appelés “pas de géants”

51
Q

Qu’est-ce que les pas de géants ?

A

Soit t = floor(sqrt(q)), on calcule
- g0 → 0
- gt → t
- …
- gfloor(q/t) × t → floor(q/t) × t
C’est-à-dire qu’on calcule tous les h × t possibles

52
Q

Qu’est-ce que les pas de bébés ?

A

Soit h avec un exposant x inconnu tel que h × t ≤ x ≤ (h + 1) × t, on teste
- h
- h/g
- h/g2
- …
- h/gt-1

53
Q

Quel lien faire entre les pas de géants et les pas de bébés ?

A

Si un pas de bébé correspond à un pas de géant, on parle de collision et on a alors h/gi = ght ⇔ h = ght + i

54
Q

Correction de l’algorithme “pas de géants pas de bébés” (énoncé)

A

Il y a toujours une collision

55
Q

Correction de l’algorithme “pas de géants pas de bébés” (schéma de preuve)

A

On peut écrire x = x1t + x0, et on a x1 ≤ x / t ≤ q / t, donc h = gx = gx1t + x0 = gx1t × gx0 et h / gx0 = gx1t

56
Q

Complexité de l’algorithme “pas de géants pas de bébés”

A
  • Calcul de gt en O(log(q)) multiplications dans G puis calcul de chaque pas de géant en O(floor(q/t)) donc O(sqrt(q)) au total
  • t = O(sqrt(q)) tests d’appartenance à la table en O(1) (avec des tables de hachage)
  • Total : O(sqrt(q)) opérations et O(sqrt(q)) éléments de G en mémoire
57
Q

Bilan de complexité du calcul du logarithm discret

A
  • Pour G un groupe générique, calcul exponentiel avec Pohlig-Bellman et “Pas de géants pas de bébés”
  • Pour G = (ZZ/pZZ)*, calcul sous-exponentiel (mais pas polynomial !)
58
Q

Que représentent les niveaux de sécurité “112” et “128” ?

A

Il faut au moins 2112 et 2118 calculs pour attaquer un protocole qui a un tel niveau de sécurité

59
Q

À partir de quelle taille de clé la norme de niveau de sécurité (128) est-elle respectée pour “Pas de bébés pas de géants” ?

A

Sur |G| = 2256 = q, une attaque en O(sqrt(q)) (pas de bébés pas de géants) prens bien O(2128) étapes de calcul

7 - Calcul Formel (3 decks)

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