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

is and the private key of is . Since and are publicly known, it is important that it be infeasible to calculate the solution to . This requires that have a large number of bits. When signing a message , chooses an integer relatively prime to such that . Then transmits a signature in the form of the pair , where

(3.10)

      (In other words,

      and , the hash of the message , is some integer such that . (The hash function maps strings of 0's and 1's onto the integer in the proper range).

      The signature is verified by 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 .

If both conditions hold, then accepts the signature as coming from . The reason for this is as follows: Substituting equation (3.10) into the second condition, we get

      (3.11)

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

      (3.12)

i.e.

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

      For a simple example, let , , and . Then has the private key and the public key since and . Let the hash of the message be . . Then . Thus, 's signature is . Condition 2 is then satisfied for this signature.

      

3.8 Intruder‐in‐the‐Middle Attack on the Diffie–Hellman