Key Management - Codes: The Guide to Secrecy from Ancient to Modern Times - page 233

public ver A ,ver B , and certified that these are indeed their respective verification
algorithms, and not, say, for Eve or Mallory. Alice and Bobwant to establish
akey k for use with a symmetric encryption scheme E k , and they develop k in
the following fashion, which is Di7e-Hellman with digital signatures added.
Protocol Steps :
1. Alice and Bobagree upon a large prime p and a primitive root α modulo p .

p ) ∗ , and Bobselects a random

2. Alice selects a random (secret) integer e A ∈ ( F

F p ) ∗ . (secret) integer e B ∈ (

α e A (mod p ), which she sends to Bob. 3. Alice computes m 1 ≡

( α e A ) e B (mod p ), and sends 5. Bobcomputes k ≡

m 2 =( α e B ,E k (sig B ( α e B ,α e A )))

to Alice.

( α e B ) e A (mod p ) and obtains sig B ( α e B ,α e A ) via E − 1

5. Alice computes k ≡

k

acting on E k (sig B ( α e B ,α e A )).

6. Alice requests that Trent certify that ver B is indeed Bob's verification
algorithm, and if it is so certified, she uses it to verify Bob's signature.
Then she sends

m 3 = E k (sig A ( α e A ,α e B ))

to Bob.

7. Bobdeciphers via E − k , asks Trent to certify that ver A is Alice's verification
algorithm. If so, he uses it to verify Alice's signature.

Analysis : With the three messages, m 1 ,m 2 ,m 3 , this is a three-pass
version of Di7e-Hellman, using digital signatures to do the authentication in
conjunction with Trent. The STS protocol establishes a key k , mutually con-
firmed by Alice and Bob, whose identities have been verified to each other, but
not to Eve or Mallory. Thus, we indeed have an authenticated key-agreement
protocol, so now Alice and Bobcan use k to encrypt all subsequent messages
between them.
We have seen schemes for distributing keys over large networks (see the
Kerberos protocol on page 196 for instance). However, we might want to decide
upon keys in advance and pre -distribute them. We briefly met this concept
on page 162, and the following scheme is designed to deal with the problems
discussed therein. The scheme below was introduced by Blom in 1985 (see [27]).
However, we present a simplified version given in [32] several years later.

Blom's KeyPredistribution Scheme — Simplified
Basic Assumptions : We suppose that there is a network of m ∈ N users,

and that keys are taken from F p where p ≥ m is a public prime. Each user on