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

Скачать книгу

some order (see Chapter 19). Recall that Rem left-bracket u comma v right-bracket means the remainder when u is divided by v. Here, in this section, and in the problems, v equals p and Rem left-bracket u comma p right-bracket will be simply denoted by Rem left-parenthesis u right-parenthesis.

      Procedure. bold upper A, bold upper B choose secret numbers a comma b and transmit u equals Rem left-parenthesis g Superscript a Baseline right-parenthesis comma v equals Rem left-parenthesis g Superscript b Baseline right-parenthesis to bold upper B, bold upper A, respectively.

      bold upper B receives u and calculates Rem left-parenthesis u Superscript b Baseline right-parenthesis equals upper K 1.

      bold upper A receives v and calculates Rem left-parenthesis v Superscript a Baseline right-parenthesis equals upper K 2.

      Now, upper K 1 equals Rem left-parenthesis g Superscript a b Baseline right-parenthesis equals Rem left-parenthesis g Superscript b a Baseline right-parenthesis equals upper K 2 and bold upper A, bold upper B are in possession of a common secret key upper K 1 equals upper K 2 equals upper K, since g Superscript a b Baseline equals g Superscript b a.

      An example with a small prime p

      p equals 11, g equals 2, a equals 4, b equals 3. Then:

StartLayout 1st Row 1st Column u 2nd Column equals Rem left-parenthesis g Superscript a Baseline right-parenthesis equals Rem left-parenthesis 2 Superscript 4 Baseline right-parenthesis equals 5 2nd Row 1st Column v 2nd Column equals Rem left-parenthesis g Superscript b Baseline right-parenthesis equals Rem left-parenthesis 2 cubed right-parenthesis equals 8 3rd Row 1st Column upper K 1 2nd Column equals Rem left-parenthesis u Superscript b Baseline right-parenthesis equals Rem left-parenthesis 5 cubed right-parenthesis equals 4 4th Row 1st Column upper K 2 2nd Column equals Rem left-parenthesis v Superscript a Baseline right-parenthesis equals Rem left-parenthesis 8 Superscript 4 Baseline right-parenthesis equals 4 EndLayout

      The common secret key possessed by bold upper A comma bold upper B 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

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

      (We remark that in the DH problem it suffices to consider the cases when 0 less-than-or-equal-to a less-than p minus 1 and 0 less-than-or-equal-to b less-than p minus 1.)

      Discrete log problem

      Given a prime p and Rem left-parenthesis g Superscript x Baseline right-parenthesis, where x is one of the numbers StartSet 0 comma 1 comma 2 comma ellipsis comma p minus 2 EndSet, find x.

      It is called the discrete log problem because log left-parenthesis g Superscript x Baseline right-parenthesis equals x when g is chosen as the logarithmic base. A solution to the discrete log problem (i.e. finding an algorithm for calculating x 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 p to be well‐behaved meaning that p minus 1 has

Скачать книгу