El Gamal Encryption
Learn about the El Gamal encryption scheme through slides by Prof. Jonathan Katz, covering topics like Dlog-based PKE, Diffie-Hellman key exchange, encryption process, security aspects, practical considerations, and vulnerability to chosen-ciphertext attacks. Discover the key principles and implications of this encryption method for protecting sensitive data in digital communication.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
El Gamal Encryption Slides by Prof. Jonathan Katz. Lightly edited by me.
Diffie-Hellman key exchange G, q, g, h1 h2 (G, q, g) G(1n) x q h1 = gx y q h2 = gy c2 = k m k = (h2)x m = c2 k-1 k = (h1)y
El Gamal encryption Public key G, q, g, h1 h2, h1y m h2 (G, q, g) G(1n) x q h1 = gx k = (h2)x m = c2 k-1 y q h2 = gy c2 = k m k = (h1)y
El Gamal encryption Gen(1n) Run G(1n) to obtain G, q, g. Choose uniform x q. The public key is (G, q, g, gx) and the private key is x Encpk(m), where pk = (G, q, g, h) and m G Choose uniform y q. The ciphertext is gy, hy m Decsk(c1, c2), where sk = x Output c2/c1x = c2 c1-x 5
Security? If the DDH assumption is hard for G, then the El Gamal encryption scheme is CPA-secure Follows from security of Diffie-Hellman key exchange, or can be proved directly Note that the discrete-logarithm assumption alone is not enough here Secure for encryption of multiple messages (using the same public key)! Note that sender(s) must use fresh randomness for each encryption 6
El Gamal in practice Parameters G, q, g are standardized and shared Need to encode message as a group element In some groups, there are natural ways to do this In other cases, not as easy Will see later a better way of resolving this issue 7
Chosen-ciphertext attacks? El Gamal encryption is not secure against chosen- ciphertext attacks Follows from the fact that it is malleable Given ciphertext (c1, c2), transform it to obtain the ciphertext (c1, c 2) = (c1, c2) for arbitrary Since (c1, c2) = (gy, hy m), we have (c1, c 2) = (gy, hy ( m)) I.e., encryption of m becomes an encryption of m! 8
Attack! (Assume 2 G *p) G, q, g, h c1, c2 c1, 2 c2 First bid: m Second bid: 2m 9
