Agreement from public powers
Public-key encryption and key agreement solve related but different problems: here two participants calculate a common value using public messages, rather than directly encrypting a message. We first prove agreement, then ask what this calculation does and does not establish.
Definition 10.1.1
(Order of a residue and the exchange)
Let be a prime and let be a nonzero residue modulo . Its order is the least positive integer with . Such an exists because the nonzero residues form a finite multiplicative group. Public parameters are . Alice chooses a private exponent and Bob chooses in the same set. They publish, respectively,
Alice computes and Bob computes . The exponent range specifies this mathematical experiment, not a complete prescription for secure key generation.
Theorem 10.1.2
(Agreement)
If both parties receive the other's unmodified public value, then their computed values agree:
Proof
(Exponent laws under honest delivery)
The modular exponentiation identities follow from associativity of multiplication and . Reducing exponents modulo does not change a power of , since in the field. The equality proves correctness under honest delivery; it is not a proof that an observer cannot compute the result.
Worked example 10.1.3
(A small calculation modulo 23)
Let , , and . The order of is : Fermat's theorem gives , while and ; no proper divisor of can be the order. The public values are and . Both parties compute
These tiny parameters make arithmetic visible; they are not secure parameters.
What an observer sees
An observer sees . The discrete logarithm task asks, given and in the subgroup generated by , for an exponent with . If an observer finds such an exponent, the observer can compute . This implication does not prove its converse: computing the shared value and recovering an exponent are different problems.
Concept lensStructural
The same exchange in a different representation
The map is an isomorphism from the additive group onto the subgroup generated by , so the exchange is the product of exponents carried into that subgroup. Run the identical exchange in with generator , publishing and modulo . With , , and the observer recovers because . Abstractly the groups are the same; any hardness lies in the representation by residues modulo .
Theorem 10.1.4
(Exponent recovery reveals the common value)
If an observer finds any integer with , then .
Proof
(Any logarithm of suffices)
Since , we have . The exponent need not equal : any solution of agrees with modulo , and powers of depend only on the exponent modulo .
Worked example 10.1.5
(Breaking the toy exchange with a table of powers)
In the example, a table of powers immediately reveals ; using and the public gives the shared value . Security therefore does not follow merely from calling an exponent private. For this finite toy group a complete table is feasible, and an unlimited observer can always enumerate the finite exponent range. Practical security is a computational claim under assumptions about a specified group, implementation and attacker, not information-theoretic secrecy proved by the agreement identity.
Worked example 10.1.6
(Degenerate exponents and small orders)
If Alice's exponent is , then and the common value is whatever Bob chooses; the observer reads the result directly from . A small order is equally damaging. Modulo the residue has order , so every public value and every common value lies in . With and , both parties publish and compute . The observer knows the rule exactly: the common value is precisely when , that is, when both exponents are odd. Agreement holds in both cases; what has changed is the size of the group generated by .
Common mistake
(Correctness is not secrecy)
Equality of the honest parties' computations holds even in a group small enough for an observer to enumerate every exponent. A secrecy claim needs a threat model and additional assumptions.
Why authenticity matters
Counterexample mode
Public-value substitution
Suppose an active attacker can replace messages and chooses exponents and . The attacker sends to Alice instead of Bob's , and to Bob instead of Alice's . Alice computes , which the attacker also computes as ; Bob computes , which the attacker also computes as . Thus the attacker can establish two separate shared values. The honest participants have not authenticated whom they are sharing with, and their values need not agree. For instance, in the example modulo the attacker takes and sends to both sides. Alice computes and Bob computes , while the attacker computes and . The agreement theorem is not contradicted: its hypothesis of unmodified delivery is exactly what fails.
Authentication must bind the exchanged values to the intended parties and protocol context. A real key-establishment protocol also specifies safe parameters, public-value checks, randomness, a key-derivation function and key confirmation where required. The toy calculation is not a protocol or implementation recommendation.
Exercises
Quick check
(For the modulo-23 example, verify , and the common value.)
Use repeated squaring modulo .
Solution · Answer
Repeated squaring gives the public values and ; both and reduce to modulo .
Quick check
(If has order , why do exponents and give the same public value?)
Use .
Solution · Answer
in the field.
Quick check
(An observer learns from the public value . How can the observer calculate the common value from ?)
Apply the exponent-recovery theorem.
Solution · Answer
Compute the public value raised to : .
Quick check
(Does the equality alone prevent the public-value substitution above? Explain.)
Check the hypothesis of the agreement theorem.
Solution · Answer
No. The equality assumes delivery of the intended public values. Substituted values let an attacker share a value with each participant instead.
Further reading
Diffie and Hellman, “New Directions in Cryptography” (1976) introduces public-key distribution. NIST SP 800-56A Rev. 3 describes discrete-logarithm key-establishment schemes and notes an update is planned.