Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen

some order (see Chapter 19). Recall that means the remainder when is divided by . Here, in this section, and in the problems, and will be simply denoted by .

      Procedure. , choose secret numbers and transmit to , , respectively.

       receives and calculates .

       receives and calculates .

      Now, and , are in possession of a common secret key , since .

      An example with a small prime

      , , , . Then:

      The common secret key possessed by is 4. In calculating, we may use the shortcuts that were introduced earlier in Chapter 3.

      The security of the Diffie–Hellman (DH) key‐exchange rests on the assumption that the DH problem described now cannot be solved in a reasonable amount of time, i.e. is intractable.

      Diffie–Hellman problem

Given a prime , , and , find .

      A (potentially) more general problem is the discrete log problem.

      (We remark that in the DH problem it suffices to consider the cases when and .)

      Discrete log problem

      Given a prime and , where is one of the numbers , find .

      It is called the discrete log problem because when is chosen as the logarithmic base. A solution to the discrete log problem (i.e. finding an algorithm for calculating in a reasonable amount of time) would imply a solution to the Diffie–Hellman problem. The converse statement is not known to be true, although there is experimental evidence pointing in that direction.

      We should point out that, for security, one wants to be well‐behaved meaning that has