Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen
Чтение книги онлайн.

Читать онлайн книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen страница 45

Название: Cryptography, Information Theory, and Error-Correction

Автор: Aiden A. Bruen

Издательство: John Wiley & Sons Limited

Жанр: Зарубежная компьютерная литература

Серия:

isbn: 9781119582403

isbn:

СКАЧАТЬ alt="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 large factors. The ideal case is when p minus 1 equals 2 q, where q itself is prime. For example, take p equals 11 so q equals 5 period In the ideal case, p has the greatest possible number of different generators (for its size) so that it is easy to find a generator. However, such primes p, known as Sophie‐Germain primes, are conjectured to be rare. In any event, only a finite number are known to exist.

      Using the Diffie–Hellman idea, it is possible to construct a public‐key cryptosystem called the El Gamal Cryptosystem.

      El Gamal Cryptosystem

      As СКАЧАТЬ