bits.

Cryptography · 1976 · Whitfield Diffie & Martin E. Hellman

New Directions in Cryptography

Reframe key distribution through public information and computational asymmetry, opening public-key exchange and digital signatures.

How to read the original

  1. Read the key-distribution problem before the modular construction.
  2. Use Public Key Cryptography to distinguish a public-key cryptosystem from public key distribution.
  3. Follow the separate authentication discussion; equality of a shared value is not evidence of peer identity.

Public discussion can establish a secret under assumptions

Diffie and Hellman examine new cryptographic possibilities, including public-key systems, key distribution, and signatures. Their modular exchange illustrates how two parties can derive a common value without transmitting that value directly. Correctness follows from algebra; resistance to an observer depends on computational assumptions and parameter choices. These are separate arguments, and neither authenticates the participants by itself.

Use an original toy exchange with public prime p=23 and base g=5. Alice chooses private exponent a=6 and sends A=5^6 mod 23=8. Bob chooses b=15 and sends B=5^15 mod 23=19. Alice computes B^6 mod 23=2. Bob computes A^15 mod 23=2. They agree because (g^b)^a and (g^a)^b both equal g^(ab) modulo p.

Make the observer’s problem explicit

An observer sees p,g,A,B. Recovering a from A is a discrete-logarithm problem. Computing g^(ab) from g^a and g^b is the computational Diffie-Hellman problem in the chosen group. Discrete-logarithm hardness and this shared-secret problem should not be casually described as proved equivalent in every setting. The tiny group above offers no meaningful security: an observer can enumerate candidate exponents immediately.

Repeated squaring makes modular exponentiation efficient without constructing the enormous integer g^a first. Each multiplication is reduced modulo p. Efficiency for honest participants is only one requirement; group structure, public-value validation, random exponent generation, and resistance to implementation leakage also affect a real protocol. A raw shared group element is normally processed through a specified key-derivation step rather than used indiscriminately as an application key.

Trace an active substitution

Suppose Mallory replaces both public messages with M=5^3 mod 23=10. Alice computes 10^6 mod 23=6, while Mallory computes Alice’s public 8^3 mod 23=6. Bob computes 10^15 mod 23=5, while Mallory computes Bob’s public 19^3 mod 23=5. Mallory now has one key with Alice and a different key with Bob.

No discrete logarithm was solved. Alice and Bob performed the arithmetic correctly but had no authenticated evidence about whose public value they received. Mallory can relay transformed traffic between the two conversations under a simplistic encryption model. The problem is missing identity and transcript binding, not failure of the exponentiation identity.

Authentication changes the protocol contract

One repair is to authenticate the exchange using a trusted verification key or another previously established authentication mechanism. The authenticated material should bind the participants and relevant handshake values so a valid message cannot be transplanted into a different context. Saying “sign the key” without specifying what is signed, who is trusted, and how freshness is handled leaves important ambiguity.

This does not make key distribution free of trust. It changes which trust is needed and how it can scale. A public-key directory must protect the association between identity and key. Compromised endpoints can still reveal secrets after an otherwise correct exchange. Secure erasure and ephemeral exponent policies affect what later key compromise reveals.

The paper should therefore be read as a conceptual and mathematical opening, not a recipe for deploying the toy arithmetic. Use standard, maintained protocol implementations for actual security. For learning, prove agreement, enumerate the small group to demonstrate its insecurity, and trace an active attack separately. That separation makes clear which property each mechanism supplies and which assumptions remain unproved.

Reconstruction exercise

Using p=23 and g=5, choose private exponents a=4 and b=7. Compute both public values and both shared-secret calculations, showing modular reductions or a small standard-library script. Then replace the exchanged values with Mallory’s public value for exponent three. Calculate the two secrets Mallory shares with the endpoints and explain why they need not be equal. Identify the new information an authenticated handshake must establish beyond merely obtaining equal modular results.

Worked solution

Alice’s public value is 5^4 mod 23=4, and Bob’s is 5^7 mod 23=17. Their shared value is 17^4 mod 23=8, also 4^7 mod 23=8. Mallory sends 10, the public value for exponent three. Alice obtains 10^4 mod 23=18, which Mallory also obtains as 4^3 mod 23. Bob obtains 10^7 mod 23=14, matching Mallory’s 17^3 mod 23. These are separate bilateral exchanges, so their keys need not agree with one another. The adversary’s success does not require reversing exponentiation. Authentication must establish that the relevant public value and transcript belong to the intended peer and session under an explicit trust model. A correct arithmetic equality alone establishes no identity. The small parameters are educational and can be exhaustively attacked, independently of the active-substitution flaw.

Test the limits and transfer the idea

1. Finite group analysis · allow 45 minutes

Find a public value that leaks one bit

Work in the nonzero residues modulo 23 with the intended subgroup generated by g = 2. List its elements and establish its order. A participant reuses private exponent a and computes shared value Y^a mod 23 for a received public value Y.

Analyze malicious inputs Y = 1 and Y = 22. Assume an attacker can distinguish the resulting derived key through a protocol response. What can each input reveal? Show that checking 1 < Y < 23 is insufficient, and propose a subgroup membership and identity check for this toy group. State what this local check does not solve.

Get a starting hint

Since 22 is -1 modulo 23, its powers depend only on exponent parity. For the intended subgroup, test Y^11 modulo 23 and separately reject the identity.

Compare your reasoning with the worked solution

The powers 2^0 through 2^10 modulo 23 are 1,2,4,8,16,9,18,13,3,6,12; the next power is 1. Thus the subgroup has order 11. Since 11 is prime and 2 is not the identity, every nonidentity element in this subgroup also has order 11.

Input Y = 1 forces the shared value to 1 for every a. Input Y = 22 gives (-1)^a, so the value is 1 for even a and 22 for odd a. Under the exercise's key-distinguishing response assumption, the attacker learns parity. Without such an observation, the algebra alone does not show that the bit becomes visible. The interval check 1 < Y < 23 accepts 22 and therefore fails to enforce subgroup membership.

A toy validation is 1 < Y < 23 and pow(Y,11,23) == 1. It excludes the identity and 22, because 22^11 is 22 modulo 23. In this prime-order subgroup it accepts only elements of the intended nontrivial order. This does not authenticate the peer, prevent all protocol attacks, make tiny parameters secure, or specify a safe key-derivation function.

This is an original adversarial-input exercise extending the paper's modular-exponentiation mechanism. It is not a claim that the paper presents this exact validation recipe or that these tiny parameters are suitable for real cryptography. The distinction between honest algebra and an adversarially supplied group element is the learning objective.

Check your reasoning

  • Lists the 11-element subgroup and explains its order.
  • Derives the identity attack and parity leak with an explicit observation assumption.
  • Gives the subgroup test and states its authentication and parameter-size limits.

2. Algorithm trace · allow 40 minutes

Separate efficient evaluation from easy inversion

For p = 29, g = 2, private exponents a = 9 and b = 13, compute both public values and the shared residue using repeated squaring. Show the square table instead of evaluating an enormous integer first. Prove agreement symbolically.

Then recover a from its public value by exhaustive search over exponents 0 through 27. Explain why this successful attack on the toy parameters neither contradicts the paper nor proves a hardness claim for large groups. Count the squarings and selected multiplications for your evaluation of 2^13 when starting with accumulator 1.

Get a starting hint

Use 13 = 8 + 4 + 1. Reduce after every multiplication. For the shared value, raise the other participant's public value to your own exponent.

Compare your reasoning with the worked solution

Repeated squares of 2 modulo 29 are 2, 4, 16, and 24 for exponents 1,2,4,8. Thus A = 2^9 = 24 × 2 mod 29 = 19, and B = 2^13 = 24 × 16 × 2 mod 29 = 14.

To compute B^9, square 14 to get residues 14,22,20,23 for exponents 1,2,4,8. Then B^9 = 23 × 14 mod 29 = 3. The other side gives A^13 = 3 as well. Algebraically, (g^b)^a = g^(ab) = (g^a)^b in the multiplicative group, independently of how repeated squaring is organized.

For 2^13, the displayed table uses three squarings. Starting with accumulator 1 and multiplying selected powers for bits 1,4,8 uses three selected multiplications; an implementation that initializes the accumulator to its first selected power can save the multiplication by 1. State the convention before comparing operation counts.

assert pow(2,9,29) == 19
assert pow(2,13,29) == 14
assert pow(14,9,29) == pow(19,13,29) == 3
candidates = [a for a in range(28) if pow(2,a,29) == 19]
assert candidates == [9]

Twenty-eight trials are trivial. The example demonstrates efficient forward evaluation and a tiny exhaustive inverse search, not an asymptotic lower bound. The paper's security reasoning concerns appropriately difficult instances and adversary capabilities; modular exponentiation's correctness is an algebraic fact, while computational security requires additional assumptions and parameters.

Check your reasoning

  • Obtains public values 19 and 14 and shared value 3 with modular traces.
  • Proves agreement and gives explicit multiplication-count conventions.
  • Finds exponent 9 and separates toy search from a general hardness proof.

Check your understanding

Why do honest endpoints derive the same value?

  • Because their private exponents must be equal.
  • Because exponent multiplication commutes in g^(ab) under the group operation.
  • Because both transmit their private exponents.
Explanation

Each raises the other public power to its own exponent, yielding the same combined exponent.

A middle party substitutes its own public values and establishes two different keys. Which missing property does this expose?

  • Authentication of peer and exchange context.
  • Correctness of modular multiplication.
  • The need to publish every private exponent.
Explanation

Unauthenticated agreement does not establish who supplied a public value.

Original paper and sources

Whitfield Diffie and Martin E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory IT-22(6), November 1976, pp. 644-654. Linked resource is an author-hosted copy.

Read the original paper →

Read the primary paper: Stanford University