Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Cryposystème de El Gamal

No description
by

amel ben lazreg

on 10 December 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Cryposystème de El Gamal

Plan
I. introduction
II. principe algorithmique
III- Algorithme
IV- Simulation
V-Avantages et inconvénients
VI- Conclusion
Introduction
Le chiffre d'El-Gamal est une méthode de cryptographie à clé publique inventée par Taher ElGamal en 1985. Sa sécurité repose, comme le protocole de Diffie et Hellman, sur la difficulté de calculer le logarithme discret.
Rappel Diffie et Hellman
El GAMAL
Taher Elgamal est l'auteur d'un algorithme de cryptographie à clef publique qui porte son nom .

Il est aussi directeur de l'ingénierie chez RSA Security avant de fonder Securify en 1998 dont il devient le PDG


Alice calcule deux clés, une clé publique et une
clé privée : elle choisit d'abord :

L'algorithme est décrit pour un groupe
multiplicatif ℤp*, p premier, mais
n'importe quel groupe cyclique fini pour
lequel le problème du logarithme discret
est difficile convient.
Le message clair de Bob est supposé être un
m dans ℤp*.
Bob

Le schéma de signature
Comme dans la plupart des schémas de
signature numérique, un utilisateur signe
un document en chiffrant un hachage h avec
sa clé secrète, et tout le monde peut alors
vérifier la signature au moyen de sa clé
publique. De manière précise, pour signer
un entier 0<=h<=p-1, on tire au hasard un
entier k dans ce même intervalle,
premier avec p-1, et on calcule
puis
La signature est le couple (r,s).
Pour vérifier une signature avec la clé publique y, on vérifie:
et
La condition (1) est très importante.
Si un programme omet de la vérifier,
on peut lui faire accepter de fausses
signatures sur n'importe quelle valeur
de hachage h' pourvu qu'on connaisse
une signature valide. On calcule
u=h h^-1 mod p-1. Alors,
La robustesse
de ce système repose sur le fait que:

Pour retrouver
M
, il doit savoir calculer (
P^k mod p
). Ceci impose de trouver
k
et donc il doit savoir résoudre l'équation suivante (en k)
y=a^k mod p
pour n'importe quel entier
y
.

On appelle ce problème le calcul du logarithme discret modulo p. C'est un problème pour lequel
on ne dispose pas d'algorithme rapide
.

Le défaut
du système d'ElGamal est que
le message chiffré est deux fois plus long que le message original
.

En revanche, le fait d'utiliser un paramètre aléatoire k est un plus en termes de sécurité : le même message M chiffré à 2 moments différents donnera deux messages codés distincts!

Ce système est peu utilisé comme méthode directe de cryptographie.

En revanche, il est très utilisé dans
les procédés de signature
électronique, souvent avec des groupes plus compliqués que (Z/pZ)∗, mais dans lesquels il est néanmoins très compliqué de résoudre le problème du logarithme discret.

Conclusion
L'entier s est la clé secrète, le triplet (p, g, h)
la clé publique. Cette dernière seule est
connue de Bob.
Alice va envoyer un message à Bob
Principe algorithmique
Alice peut déchiffrer le message reçu en
calculant m = c2 / c1s. En effet :

Le but de l'algorithme Diffie-Hellman est de créer
un secret commun aux personnes qui veulent
communiquer et d'utiliser ce secret pour chiffrer
les données échangées.

Tout ce qui est en
vert
est publique.
Tout ce qui est en
rouge
est privé.
Elgamal = Diffie Hellman changement de clé + cryptage en multipliant mod p
Inconvénient
Avantages
Le chiffrement ElGamal est
probabiliste
, ce qui signifie que d'un seul texte en clair on peut chiffrer
plusieurs cryptogrammes possibles.
Pour AlGamel, le schéma de chiffrement ( encryption scheme) et le génération de la signature digitale (digital signature) sont deux processus différents.

Le principe de la signature digital d'AlGamel constitue la base pour DSA.

Pour la signature (r,s) a deux fois la longueur de bit de x (la signature à chiffré)
---> ce qui rend cette solution inadéquate pour les quelques systèmes tel que e cryptage de a signature d'une carte bancaire ...
Full transcript