Scribd Logo
Upload

Welcome to Scribd!

  • 263 views

    The Elgamal Cryptosystem: Joint Advanced Students Seminar 2005

    Uploaded by

    Hanuma Pantham
    The document summarizes a presentation on the ElGamal cryptosystem. It introduces public key cryptography and the discrete logarithm problem. It then describes the key generation, encryption, and decryption processes of the ElGamal cryptosystem. An example is provided to illustrate encrypting and decrypting a message with ElGamal. The presentation emphasizes the importance of correct implementation, citing an issue with GnuPG that compromised all signatures for years due to a small private exponent.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    The Elgamal Cryptosystem: Joint Advanced Students Seminar 2005

    Uploaded by

    Hanuma Pantham
    263 views24 pages
    The document summarizes a presentation on the ElGamal cryptosystem. It introduces public key cryptography and the discrete logarithm problem. It then describes the key generation, encryption, and decryption processes of the ElGamal cryptosystem. An example is provided to illustrate encrypting and decrypting a message with ElGamal. The presentation emphasizes the importance of correct implementation, citing an issue with GnuPG that compromised all signatures for years due to a small private exponent.

    Original Title

    ElGamal Cryptosystem

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document summarizes a presentation on the ElGamal cryptosystem. It introduces public key cryptography and the discrete logarithm problem. It then describes the key generation, encryption, and decryption processes of the ElGamal cryptosystem. An example is provided to illustrate encrypting and decrypting a message with ElGamal. The presentation emphasizes the importance of correct implementation, citing an issue with GnuPG that compromised all signatures for years due to a small private exponent.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    263 views24 pages

    The Elgamal Cryptosystem: Joint Advanced Students Seminar 2005

    Uploaded by

    Hanuma Pantham
    The document summarizes a presentation on the ElGamal cryptosystem. It introduces public key cryptography and the discrete logarithm problem. It then describes the key generation, encryption, and decryption processes of the ElGamal cryptosystem. An example is provided to illustrate encrypting and decrypting a message with ElGamal. The presentation emphasizes the importance of correct implementation, citing an issue with GnuPG that compromised all signatures for years due to a small private exponent.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 24

    Joint Advanced Students Seminar 2005

    The ElGamal Cryptosystem


    Andreas V. Meier
    meiera@in.tum.de

    TUM Informatik

    Andreas V. Meier The ElGamal Cryptosystem p.1/23

    Structure
    Public Key Cryptography Assigned Complexity Problems ElGamal Cryptosystem Importance of Correct Implementation Summary

    Andreas V. Meier The ElGamal Cryptosystem p.2/23

    Public Key Cryptography


    Introduced 1976 by Dife and Hellman Basic concept: Trapdoor functions (see following presentation) Features:
    sender verication private key part remains at owner public key part freely distributable no secret channel neccessary no pre-shared keys

    Prominent representative: RSA (1977) ... and ElGamal

    Andreas V. Meier The ElGamal Cryptosystem p.3/23

    Public Key Cryptography - Procedure


    Scenario:
    Alice wants to send an encrypted message to Bob

    Procedure 1. Bob computes a public and a private key, the keypair 2. Bob publishes his public key 3. Alice Encrypts the message using Bobs public key 4. Alice sends the message to Bob. 5. Bob encrypts the message using his private key Effect:
    Nobody intercepting the message can read nor alter it unrecognized

    Andreas V. Meier The ElGamal Cryptosystem p.4/23

    Public Key Cryptography - Scheme

    public key Alice encrypt using public key Bob decrypt using private key

    encrypted message

    Andreas V. Meier The ElGamal Cryptosystem p.5/23

    Public Key Cryptography - Algorithm


    Two public parameters:
    p: prime number g: generator such that n [1; p 1] : k; n = g k mod p Alice generates a private random integer a Bob generates a private random integer b Alice generates her public value g a mod p Bob generates his public value g b mod p Alice computes g ab = (g a )b mod p Bob computes g ba = (g b )a mod p

    Procedure: 1. 2. 3.

    4. Both now have a shared secret k since k = g ab = g ba

    Andreas V. Meier The ElGamal Cryptosystem p.6/23

    Public Key Cryptography - Summary


    Features
    able to set up a secure channel between two parties based on the Discrete Logarithm Problem

    Problems
    vulnerable to the man-in-the-middle attack vulnerable to chosen-plaintext attacks ( signed keys) not useful for one way communication (e.g. email)

    Andreas V. Meier The ElGamal Cryptosystem p.7/23

    Dife-Hellmann Problem DH
    Instance:
    A multiplicative group (G, ), a generator g of G, two public key parts g a and g b

    Question:
    Find the common key g ab

    Andreas V. Meier The ElGamal Cryptosystem p.8/23

    Discrete Logarithm Problem - DL


    Instance:
    A multiplicative group (G, ), a generator g of G, |G| = n, and an element x

    Question:
    Find the unique integer a, 0 a n 1, such that g a = x. a can be described as logg x

    Andreas V. Meier The ElGamal Cryptosystem p.9/23

    Complexity of DL and DH
    Lower bound: (p) with p = greatest prime divisor of the group order Related problem: Decision DH (DDH)
    Instance: the triple g a , g b and g c Question: is c ab

    (mod p)?

    Andreas V. Meier The ElGamal Cryptosystem p.10/23

    Algorithms for DL
    Given: Generator g of G, beta G Wanted: a,1 < a < p 1 Assumption: Multiplication of x, y G in O(1) 2. sort the list wrt. the second coordinate 3. given a , perform a binary search on the list First step: O(n), Second step: O(n log n), Third step: O(log n) Neglecting logarithmic factors: Precomputation-time: O(1) Space: O(n), Solving in O(1)
    Shank, Pollard Rho, Pholig-Hellman

    1. compute all possible g i into a list of pairs (i, g i )

    Andreas V. Meier The ElGamal Cryptosystem p.11/23

    Complexity of DL - Reduction to Addition


    So far we had a multiplicative Group (G, ) Idea: DL in Additive Group (G, +)

    Andreas V. Meier The ElGamal Cryptosystem p.12/23

    ElGamal Cryptosystem
    Presented in 1984 by Tather Elgamal Key aspects:
    Based on the Discrete Logarithm problem Randomized encryption

    Application:
    Establishing a secure channel for key sharing Encrypting messages

    Andreas V. Meier The ElGamal Cryptosystem p.13/23

    ElGamal Cryptosystem - Key Generation


    Participant A generates the public/private key pair 1. Generate large prime p and generator g of the multiplicative Group Z pf of the integers modulo p. p 2. Select a random integer a, 1 a p 2, and compute g a mod p. 3. As Public key is (p, g, g a ); As Private key is a.

    Andreas V. Meier The ElGamal Cryptosystem p.14/23

    ElGamal Cryptosystem - Encryption Procedure


    Participant B encrypts a message m to A 1. Obtain As authentic public key (p, g, g a ). 2. Represent the message as integers m in the range {0, 1, . . . , p 1}. 4. Compute = g k mod p and = m (g a )k . 5. Send ciphertext c = (, ) to A 3. Select a random integer k , 1 k p 2.

    Andreas V. Meier The ElGamal Cryptosystem p.15/23

    ElGamal Cryptosystem - Decryption Procedure


    Participant A receives encrypted message m from B 1. Use private key a to compute ( p1a ) mod p. Note: p1a = a = aak 2. Recover m by computing ( a ) mod p.

    Andreas V. Meier The ElGamal Cryptosystem p.16/23

    ElGamal Cryptosystem - Encryption Sample


    Alice choses her public key (17, 6, 7):
    Prime p = 17 Generator g = 6 Private key part a = 5 Public key part g a mod p = 65 mod 17 = 7

    Bob encrypts his message m = 13:


    He chooses a random k = 10 He calculates = g k mod p = 610 mod 17 = 15 He encrypts = m g k mod p = (13 710 ) mod 17 = 9

    Bob sends = 15 and = 9 to Alice.

    Andreas V. Meier The ElGamal Cryptosystem p.17/23

    ElGamal Cryptosystem - Decryption Sample


    Alice receives = 15 and = 9 from Bob.
    Her public key is (p, g, g a ) = (17, 6, 7) Her private key is a = 5

    Alice now decrypts the message using her private key:


    Decryption factor

    Decryption: ( 9) mod p = (9 9) mod 17 = 13

    ( a ) mod p = 155 mod 17 = 1511 mod 17 = 9

    Alice has now decrypted the message and received: 13

    Andreas V. Meier The ElGamal Cryptosystem p.18/23

    ElGamal Cryptosystem - Summary


    Features:
    use of a random factor k for encryption variant of DH: shared secret is g ak

    Problems:
    Duplicates message length Depends on intractability of DL and DH

    Andreas V. Meier The ElGamal Cryptosystem p.19/23

    Importance of Correct Implementation - GnuPG Issue


    Problem discovered late 2003 by Phong Q. Nguyen in GnuPG
    Too small private exponent and too short nonce used for signature generation. Present for almost four years!

    Effects
    All signatures created with GnuPG up to the day of x

    considered compromised

    Andreas V. Meier The ElGamal Cryptosystem p.20/23

    Importance of Correct Implementation - Code Sample


    / IMO u s i n g a k much l e s s e r than p i s s u f f i c i e n t and i t g r e a t l y improves t h e e n c r y p t i o n performance . and add a l a r g e s a f e t y margin . / n b i t s = wiener_map ( o r i g _ n b i t s ) 3 / 2 ; nbytes = ( n b i t s +7) / 8 ; We use Wiener s t a b l e

    Wiener Table: |p| 512 768 qbit 119 145

    1024 165

    1280 183

    1536 198

    1792 212

    2048 225

    2304 237

    ... ...

    Small k in signature lattice attack

    Andreas V. Meier The ElGamal Cryptosystem p.21/23

    Summary
    What have we heared in this presentation?
    Public Key scheme - suitable for sharing symetric keys Discrete Logarithm Problem - even harder than

    F ACT ORIZE

    ElGamal Cryptosystem Importance of correct implementation of cryptosystems

    Andreas V. Meier The ElGamal Cryptosystem p.22/23

    Discussion
    Questions from the audience? Why are hybrid cryptosystems used for encrypting e.g. a

    vpn?

    Andreas V. Meier The ElGamal Cryptosystem p.23/23

    Literature
    Cryptography: Theory and practice, Douglas R. Stinson New directions in cryptography, Dife and Hellman Handbook of applied Cryptography, Menezes, van

    Oorschot, Vanstone

    A Public Key Cryptosystem and a Signature Scheme Based

    on Discrete Logarithms, Tather Elgamal

    Andreas V. Meier The ElGamal Cryptosystem p.24/23

    You might also like