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

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

alt="bold upper A"/> is left-parenthesis p comma g comma g Superscript a Baseline right-parenthesis and the private key of bold upper A is a. Since p and g are publicly known, it is important that it be infeasible to calculate the solution x to g Superscript x Baseline identical-to g Superscript a Baseline mod p. This requires that p have a large number of bits. When signing a message upper M, bold upper A chooses an integer k relatively prime to p minus 1 such that 1 less-than-or-equal-to k less-than-or-equal-to p minus 2. Then bold upper A transmits a signature in the form of the pair left-parenthesis Rem left-parenthesis g Superscript k Baseline right-parenthesis comma s right-parenthesis, where

      (In other words, upper R e m left-bracket k Superscript negative 1 Baseline left-parenthesis h minus a g Superscript k Baseline right-parenthesis comma p minus 1 right-bracket equals s right-parenthesis

      and h, the hash of the message upper M, is some integer such that 1 less-than-or-equal-to h less-than-or-equal-to p minus 2. (The hash function maps strings of 0's and 1's onto the integer h in the proper range).

      The signature is verified by bold upper B who checks the conditions:

      1 The left integer in the signature pair, namely , lies in the interval .

      2 The congruence is satisfied. In other words, we check that .

      (3.11)g Superscript a g Super Superscript k Baseline g Superscript k left-parenthesis k Super Superscript negative 1 Superscript left-parenthesis h minus a g Super Superscript k Superscript right-parenthesis right-parenthesis Baseline identical-to g Superscript h Baseline left-parenthesis mod p right-parenthesis

      This means that if bold upper A computed s, then condition 2 will be satisfied. Conversely, if condition 2 is satisfied, then (since g is a primitive root of p) the exponents must give the same remainder on division by p minus 1. Hence,

      (3.12)a g Superscript k Baseline plus k s identical-to h left-parenthesis mod p minus 1 right-parenthesis

Rem left-bracket a g Superscript k Baseline plus k s comma p minus 1 right-bracket equals Rem left-bracket h comma p minus 1 right-bracket

      which is a restatement of Eq. (3.10). So the computation carried out by bold upper A is the only way to satisfy the second condition.

      For a simple example, let p equals 11, g equals 2, a equals 4 and k equals 7. Then bold upper A has the private key a equals 4 and the public key left-parenthesis p comma g comma g Superscript a Baseline right-parenthesis equals left-parenthesis 11 comma 2 comma 5 right-parenthesis since g Superscript a Baseline equals 2 Superscript 4 Baseline equals 16 and Rem left-parenthesis 16 right-parenthesis equals 5. Let the hash of the message upper M be h equals 1. Rem left-bracket k Superscript negative 1 Baseline left-parenthesis h minus a g Superscript k Baseline right-parenthesis comma p minus 1 right-bracket equals Rem left-bracket 3 left-parenthesis 1 minus left-parenthesis 4 right-parenthesis left-parenthesis 7 right-parenthesis right-parenthesis comma 10 right-bracket equals Rem left-bracket 9 comma 10 right-bracket. Then s equals 9. Thus, bold upper A's signature is left-parenthesis 7 comma 9 right-parenthesis. Condition 2 is then satisfied for this signature.

      

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