Week11-DiffieHellman and Discrete Log

Chapter Overview

  • Prepared by Christof Paar and Jan Pelzl

  • Title: Public-Key Cryptosystems Based on the Discrete Logarithm Problem

  • Version: February 22, 2010

  • Based on Understanding Cryptography by the same authors

Content of Chapter

  • Diffie-Hellman Key Exchange

  • The Discrete Logarithm Problem

  • Security of the Diffie-Hellman Key Exchange

Diffie-Hellman Key Exchange (DHKE)

  • Significance: First public-key algorithm published.

  • Application: Widely implemented in commercial products for secure key exchange.

  • Purpose: Allows two users to securely exchange a symmetric encryption key.

  • Limitation: Only exchanges secret values; not used for encryption directly.

  • Security Basis: Effectiveness relies on the difficulty of computing discrete logarithms.

Historical Context

  • Initial Proposal: 1976 by Whitfield Diffie and Martin Hellman.

  • Influences: Work of Ralph Merkle influenced the development of DHKE.

  • Utilized In: Secure Shell (SSH), Transport Layer Security (TLS), and Internet Protocol Security (IPSec).

DHKE Mechanism

  • Provides a practical solution to the key distribution problem.

  • Enables two parties to derive a common secret key over an insecure channel.

  • Core Concept: Exponentiation in finite fields (specifically prime fields) is a one-way function.

  • Key computed: k = (α^a)^b mod p where p is prime and α is a generator.

Setup Process of DHKE

  1. Choose a large prime p.

  2. Select an integer α such that α ∈ {2,3,...,p−2}.

  3. Publish p and α.

Example of DHKE

  • Participants: Alice and Bob.

  • Process:

    • Alice chooses private key a, computes public key A = α^a mod p.

    • Bob chooses private key b, computes public key B = α^b mod p.

    • They compute the shared secret key: kAB = B^a mod p and kAB = A^b mod p.

  • Domain Parameters: Example with p = 29, α = 2, Alice's private key as 5, Bob's private key as 12.

Importance of Group Theory

  • Group Definition: A set of elements G combined with an operation o.

    • Properties required:

      1. Closure: For all a, b in G, the result of a o b is also in G.

      2. Associativity: a o (b o c) = (a o b) o c.

      3. Identity Element: There exists 1 in G such that a o 1 = a.

      4. Inverse Element: For every a in G, there exists a^-1 in G such that a o a^-1 = 1.

      5. Abelian Group: If a o b = b o a for all a, b in G.

Cyclic Groups in Cryptography

  • Finite Structures: Cryptographic algorithms typically involve finite cyclic groups.

  • Order of an Element: The smallest positive integer k such that a^k = 1.

  • Primitive Element: An element that can generate all members of the group.

Discrete Logarithm Problem (DLP)

  • Given parameters: Primitive element α in group Zp* and element β, find x such that α^x ≡ β mod p.

  • Example provided: solve 5^x ≡ 41 mod 47.

Diffie-Hellman Problem (DHP)

  • Definition: Given group G, primitive element α, and elements A and B, find the element corresponding to α^ab.

  • Security Implications: Solving DHP requires solving DLP.

Security of Diffie-Hellman Key Exchange

  • Security relies upon the challenge of the DLP in cyclic groups.

  • Recommended that primes used should be at least 1024 bits long for security.

  • To enhance long-term security, a prime length of 2048 bits is advised.

Attacks on DLP

  • Various algorithms exist to compute discrete logarithms:

    • Generic Algorithms: Applicable to any cyclic group; e.g., brute-force search.

    • Non-generic Algorithms: Optimized for specific groups, notably in Zp.

    • Historical Records: Documented advancements in computing discrete logarithms over years.

Conclusion: Lessons Learned

  • DHKE is key for secure key exchange based on cyclic groups.

  • DLP is critical for asymmetric cryptography and underpins many public-key algorithms.

  • Compliance with security measures regarding prime sizes is imperative for effective cryptographic systems.