alt="bold upper A"/> 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
