1. Home
2. The ElGamal cryptosystem
3. The protocols explained

The math and definitions explained

function extended_gcd(a, b)
    if b = 0 then
        return (a, 1, 0)
    else
        (d, x', y') = extended_gcd(b, a mod b)
        return (d, y', x' - (a div b) * y')

The ElGamal cryptosystem was first described by Taher ElGamal in 1985 and is closely related to the Diffie-Hellman key exchange. While the Diffie-Hellman key exchange provides a method for Alice and Bob to share a secret key, it does not by itself enable them to communicate messages securely.

ElGamal is a public key cryptosystem based on the discrete logarithm problem for a group \( G \). In this system, every person has a key pair \( (sk, pk) \), where \( sk \) is the secret key and \( pk \) is the public key. Given only the public key, one would need to solve the discrete logarithm problem to obtain the secret key.

The cryptosystem serves two purposes: first, as an encryption scheme (described in this section) that helps Alice and Bob exchange sensitive information over an insecure channel that may be eavesdropped by their adversary Eve; and second, as a digital signature scheme (detailed in the next section) that enables the creation of digital signatures. The signature scheme differs slightly from the encryption scheme. Various other digital signature schemes, such as the Schnorr signature scheme and the Digital Signature Algorithm (DSA), are based on ElGamal's signature scheme but utilize shorter keys.

The group used in ElGamal can be \( \mathbb{Z}_{p}^{*} \) where \( p \) is a prime number, a subgroup of \( \mathbb{Z}_{p}^{*} \) of order \( q \) where \( q \) is a prime number, or an elliptic curve group. In the following, we use the group \( \mathbb{Z}_{p}^{*} \) for simplification, but this group is not used in practice because it's insecure: Alice and Bob's adversary Eve can tell whether a ciphertext is an encryption of a meaningful message or some random letters (i.e., when the used group in ElGamal is \( \mathbb{Z}_{p}^{*} \), it's not CPA-secure).

Key Generation

In the encryption scheme, Alice (or a trusted third party) first chooses a large prime number \( p \), such that the discrete logarithm problem is hard in the group \( \mathbb{Z}_{p}^{*} \), and a generator \( g \) of the group \( \mathbb{Z}_{p}^{*} \). Next, Alice chooses the secret key \( sk = a \) between \( 1 \) and \( p-1 \) and computes \( A = g^{a} \: mod \: p \). Alice then publishes the public key \( pk = (p, g, A) \). Notice that both Alice's friend Bob and their adversary Eve can see the public key, but they have to compute the discrete logarithm of \( A \) to get the secret key, i.e., compute the value \( a \).

Encryption Process

Suppose that Bob has a secret message he wants to send to Alice and he needs to hide the content from Eve. Bob first converts the message into an integer \( m \) such that \( 1 \leq m \leq p-1 \), i.e., the plaintext \( m \) is in the group \( \mathbb{Z}_{p}^{*} \). He also chooses a random number \( k \) between \( 1 \) and \( p-1 \), which is called an ephemeral key. The ephemeral key is only used to encrypt a single message \( m \) before being discarded. After using \( k \) to encrypt the message, Bob chooses a new ephemeral key for any future messages. Bob encrypts \( m \) using the encryption algorithm \( E \) with Alice's public key \( pk = (p, g, A) \) by calculating \( (c_{1}, c_{2}) = E_{pk}(m) \) where \( c_{1} = g^{k} \: mod \: p \) and \( c_{2} = m \cdot A^{k} \: mod \: p \). The resulting values \( (c_{1}, c_{2}) \) are called the ciphertext and are sent to Alice.

Decryption Process

When Alice receives the ciphertext \( (c_{1}, c_{2}) \), she first computes \( x = c_{1}^{a} \: mod \: p \) and then calculates the inverse \( x^{-1} \) of \( x \) using the extended Euclidean algorithm. The extended Euclidean algorithm gives her the equation \( x \cdot \lambda + p \cdot \mu = \gcd(x, p) \) where \( x^{-1} = \lambda \: mod \: p \) is the inverse of \( x \) and \( x \cdot x^{-1} \: mod \: p = 1 \) (remember that in the case of ElGamal, \( x^{-1} \) only exists because \( \gcd(x, p) = 1 \)). Finally, she decrypts the received ciphertext with the decryption algorithm \( D \) and her secret key \( sk = a \) by computing \( m' = D_{sk}(c_{1}, c_{2}) = x^{-1} \cdot c_{2} \: mod \: p \) where \( m' = m \) because:

\( \eqalign{ m' &= x^{-1} \cdot c_{2} \: mod \: p &&(x = c_{1}^{a}) \\&= (c_{1}^{a})^{-1} \cdot c_{2} \: mod \: p &&(c_{1} = g^{k}, c_{2} = m \cdot A^{k}) \\ &= ((g^{k})^{a})^{-1} \cdot m \cdot A^{k} \: mod \: p &&(A = g^{a}) \\ &= ((g^{k})^{a})^{-1} \cdot m \cdot (g^{a})^{k} \: mod \: p &&(\mbox{exponent rule}) \\ &= (g^{k \cdot a})^{-1} \cdot m \cdot g^{a \cdot k} \: mod \: p &&((g^{k \cdot a})^{-1} \cdot g^{a \cdot k} = 1) \\ &= m } \)

Group Security Analysis

So, why is \( \mathbb{Z}_{p}^{*} \) an insecure group while, e.g., the subgroup \( G \) of \( \mathbb{Z}_{p}^{*} \) of order \( q \) is a secure group where \( p \) and \( q \) are prime numbers? First, we have to define what a secure cryptosystem is: When an adversary like Eve intercepts a ciphertext, she shouldn't be able to tell whether it's an encryption of a specific message or just random letters (this is also the definition of a CPA-secure cryptosystem).

In the following discussion, we will use — without proof — a theorem stating that if Eve can determine whether the exponent \( a \cdot k\) from \( A^{k} = (g^{a})^{k} = g^{a \cdot k} \) in \( c_{2} \) is an even or odd number, she can distinguish whether a ciphertext is an encryption of a meaningful message or just random letters. This means that if the DDH problem is easy to solve for the group being used, then ElGamal is not CPA-secure (in other words: if the DDH problem is hard in the group being used, then ElGamal is CPA-secure).

First, we need some definitions: We say that \( y \) is a quadratic residue modulo a prime number \( p \), written as \( y \in QR(p) \), if there exists a number \( x \) such that \( y \: mod \: p = r \) and \( x^{2} \: mod \: p = r \), i.e., \( y \equiv x^{2} \: (mod \: p) \) (they have the same residue \( r \)). If no such \( x \) exists, then \( y \) is called a non-quadratic residue modulo \( p \), written as \( y \in NQR(p) \). For example, with the prime number \( p = 7\), we have:

\( \eqalign{ 1^{2} &\equiv 1 \: (mod \: 7) \\2^{2} &\equiv 4 \: (mod \: 7) \\3^{2} &\equiv 2 \: (mod \: 7) \\4^{2} &\equiv 2 \: (mod \: 7) \\5^{2} &\equiv 4 \: (mod \: 7) \\6^{2} &\equiv 1 \: (mod \: 7)} \)

which tells us that \( \{1, 2, 4\} \in QR(7) \) (the numbers on the right side of \( \equiv \)) and \( \{3, 5, 6\} \in NQR(7) \) (the remaining numbers excluding 0). Notice that half of the numbers from \( 1, 2, \dots, p-1 \) are quadratic residues modulo \( p \) and the other half are quadratic non-residues modulo \( p \).

A famous Swiss mathematician named Euler defined the equation \( (g^{i})^{(p-1)/2} \: mod \: p \) where \( g \) is a generator of the group \( \mathbb{Z}_{p}^{*} \). If \( (g^{i})^{(p-1)/2} \: mod \: p = 1 \) then \( g^{i} \in QR(p) \) and if \( (g^{i})^{(p-1)/2} \: mod \: p = -1 \) then \( g^{i} \in NQR(p) \). Another important observation that we will use without proof is that if \( g^{i} \in QR(p) \), then the exponent \(i\) is an even number. Otherwise, \(i\) is an odd number.

Finally, we will define \( LSB(g^{i}) \) as the value of the least significant bit of \( i \) (when expressed in binary) and we have that \( LSB(g^{i}) = 0 \) if the exponent \( i \) is an even number and \( LSB(g^{i}) = 1 \) otherwise. Using the above definitions we have that \( LSB(g^{i}) = 0 \) if and only if \( (g^{i})^{(p-1)/2} \: mod \: p = 1 \) or \( g^{i} \in QR(p) \). We also have that \( LSB(g^{i}) \cdot LSB(g^{j}) = LSB(g^{i \cdot j}) \).

Now, let us return to the ElGamal cryptosystem and examine how Eve can determine whether a ciphertext contains a meaningful message or random letters. Remember, we only need to prove that she can identify whether the exponent \( a \cdot k \) is even or odd. Suppose a trusted third party has chosen the prime number \( p = 7 \) and the generator \( g = 3 \) of the group \( \mathbb{Z}_{7}^{*} \). Let's assume that Alice has chosen the secret key \( a = 2 \) and the ephemeral key \( k = 5 \). She then computes \( A = g^{a} \: mod \: p = 3^{2} \: mod \: 7 = 2 \) and \( c_{1} = g^{k} \: mod \: p = 3^{5} \: mod \: 7 = 5 \). For the value of \( c_{2} = m \cdot A^{k} \: mod \: p \), we have:

\( \eqalign{ A^{k} \: mod \: p &= (g^{a})^{k} \: mod \: p \\ &= g^{a \cdot k} \: mod \: p \\ &= 3^{2 \cdot 5} \: mod \: 7 \\ &= 3^{10} \: mod \: 7 \\ &= 4} \)

Eve doesn't know the values of \( a \) and \( k \), but she can use Euler's equation to compute:

\( \eqalign{ A^{(p-1)/2} \: mod \: p &= (g^{a})^{(p-1)/2} \: mod \: p = 2^{(7-1)/2} \: mod \: 7 = 1 \\ c_{1}^{(p-1)/2} \: mod \: p &= (g^{k})^{(p-1)/2} \: mod \: p = 5^{(7-1)/2} \: mod \: 7 = -1} \)

i.e., \( A \in QR(7) \) and \( c_{1} \in NQR(7) \) which means that \( LSB(A) = LSB(g^{a}) = 0 \) (i.e., the exponent \( a \) in \( A \) is an even number, which is true because \( a = 2 \)) and \( LSB(c_{1}) = LSB(g^{k}) = 1\) (i.e., the exponent \( k \) in \( c_{1} \) is an odd number, which is true because \( k = 5 \)). Now Eve knows that the exponent \( a \cdot k \) is an even number (which is true because \( a \cdot k = 10 \)) because she can use the following multiplication rule: \( LSB(g^{a \cdot k}) = LSB(g^{a}) \cdot LSB(g^{k}) = 0 \cdot 1 = 0 \). Using the above theorem, Eve can now tell whether a ciphertext is an encryption of a meaningful message or some random letters.

The reason why Eve can tell whether the exponent \( a \cdot k \) is an even or odd number is because all the numbers in the group \( \mathbb{Z}_{p}^{*} \) excluding 0 can be divided into quadratic residues modulo \( p \) or non-quadratic residues modulo \( p \). This observation is used to construct the secure subgroup \( G \) of \( \mathbb{Z}_{p}^{*} \) of order \( q \) where \( G = QR(p) \), i.e., all numbers in \( G \) are quadratic residues modulo \( p \). Now if Eve tries to use the above method, she always gets \( LSB(x) = 0 \) for any number \( x \) in the subgroup \( G \). In other words: ElGamal is CPA-secure in the subgroup \( G \) because the DDH problem in \( G \) is hard.

Homomorphic Properties

ElGamal is also a partially homomorphic cryptosystem with respect to pointwise multiplication, meaning that ciphertexts can be combined through the operation \( (a,b) \cdot (c,d) = (a \cdot c, b \cdot d) \). This property can be demonstrated as follows:

\( \eqalign{ E_{pk}(m) \cdot E_{pk}(m') \: mod \: p &= (g^{k} \: mod \: p, m \cdot A^{k} \: mod \: p) \cdot (g^{k'} \: mod \: p , m' \cdot A^{k'} \: mod \: p) &&(\mbox{pointwise multiplication}) \\ &= (g^{k} \cdot g^{k'} \: mod \: p, m \cdot A^{k} \cdot m' \cdot A^{k'} \: mod \: p) &&(\mbox{exponent rule}) \\ &= (g^{k + k'} \: mod \: p, (m \cdot m') \cdot A^{k+k'} \: mod \: p) \\ &= E_{pk}(m \cdot m' \: mod \: p) } \)

In other words, pointwise multiplication of two ciphertexts corresponds to multiplying the two underlying plaintexts. ElGamal is partially homomorphic, not fully homomorphic, because only multiplication (not addition) has this property.

This property can be both an advantage and a disadvantage for the cryptosystem. It is advantageous, for example, when Alice has some private data \( m \) on which she wants a cloud service to perform computations. She first computes \( (c_{1}, c_{2}) = E_{pk}(m) \) and then sends the ciphertext \( (c_{1}, c_{2}) \) to the cloud service. The cloud service can then perform computations on Alice's data by calculating \( (c_{1}, c_{2}) \cdot (c_{1}', c_{2}') \: mod \: p \) for some \( (c_{1}', c_{2}') = E_{pk}(m') \). Alice then receives and decrypts the resulting ciphertext, which yields the data \( m \cdot m' \: mod \: p \). On the other hand, this property can be a disadvantage: for example, if Eve intercepts a ciphertext \( (c_{1}, c_{2}) \) sent from Alice to Bob and computes \( (c_{1}, c_{2}) \cdot (c_{1}', c_{2}') \: mod \: p \) for some \( (c_{1}', c_{2}') = E_{pk}(m') \), which she then sends to Bob. When Bob decrypts the ciphertext, he obtains the plaintext \( m \cdot m' \: mod \: p \) instead of the original plaintext \( m \).

Security Considerations

The ephemeral key (k) must never be reused when creating signatures. Doing so can lead to complete private key compromise!

The ephemeral key (k) must be:

• Truly random: Use cryptographically secure random number generators
• Used only once: Never reuse the same ephemeral key for different messages
• Securely erased: After encryption or signing is complete

Parameter Requirements (2025):

• Prime modulus p should be at least 2048 bits
• For subgroup schemes (Schnorr/DSA), q should be at least 224 bits
• Use strong primes that resist specialized attacks

Known Attacks:

• Small subgroup attacks: Can occur when parameters aren't verified
• Pohlig-Hellman attack: Effective when the order of the group has small factors
• Baby-step Giant-step and Pollard's rho: Generic discrete logarithm attacks
• Malleability issues: ElGamal encryption is malleable by design (homomorphic property)

Quantum Computing Threats:

Shor's algorithm on a sufficiently powerful quantum computer can break ElGamal and all discrete logarithm-based cryptosystems in polynomial time. Organizations planning for long-term security should consider post-quantum alternatives like:

• Lattice-based cryptography
• Hash-based signatures
• Code-based cryptosystems

Comparison with Other Cryptosystems

The protocol

Try a demo of the encryption scheme here.

Example

Alice uses the prime number \( p = 283 \) and the generator \( g = 189 \) of the group \( \mathbb{Z}_{283}^{*} \), which are chosen by a trusted third party. She then chooses the secret key \( sk = a = 129 \) and computes \( A = g^{a} \: mod \: p = 189^{129} \: mod \: 283 = 33 \). Finally, she publishes the public key \( pk = (p, g, A) = (283, 189, 33) \).

Alice's friend Bob decides to send the message \( m = 123 \) to Alice. He first chooses the ephemeral key \( k = 33 \) and then computes the ciphertext \( (c_{1}, c_{2}) = E_{pk}(m) = (219, 269) \), where \( c_{1} = g^{k} \: mod \: p = 189^{33} \: mod \: 283 = 219 \) and \( c_{2} = m \cdot A^{k} \: mod \: p = 123 \cdot 33^{33} \: mod \: 283 = 269 \), which he sends to Alice.

Before Alice can decrypt the ciphertext, she computes \( x = c_{1}^{a} \: mod \: p = 219^{129} \: mod \: 283 = 39 \) and the inverse \( x^{-1} \) of \( x \) using the extended Euclidean algorithm. The extended Euclidean algorithm gives her the equation \( \gcd(x, p) = x \cdot \lambda + p \cdot \mu = 39 \cdot (-29) + 283 \cdot 4 = 1 \), where \( x^{-1} = \lambda \: mod \: p = -29 \: mod \: 283 = 254 \). Finally, she decrypts the ciphertext by computing \( m' = D_{sk}(c_{1}, c_{2}) = x^{-1} \cdot c_{2} \: mod \: p = 254 \cdot 269 \: mod \: 283 = 123 \).

Two people, Samantha and Victor, use a digital signature when one of them—say, Samantha—needs to send a digitally signed piece of data, such as a document or message, to Victor, and it is important that Victor knows it is from Samantha. For example, Samantha might want to send money to her friend Carla through her bank, where Victor works. Before Victor withdraws the money from Samantha's account, he needs to verify that the transfer request is actually from Samantha and not from someone else. If the signature scheme is insecure, it would be possible for Samantha's adversary, Eve, to forge a signature on a message stating that Samantha wants to send money to Eve, and Victor would believe that the message is from Samantha.

Key Generation for Signatures

In ElGamal's signature scheme, Samantha (or a trusted third party) first chooses a large prime number \( p \) and a generator \( g \) of the group \( \mathbb{Z}_{p}^{*} \). She then chooses the secret signing exponent \( s \) between \( 1 \) and \( p-1 \) and computes the public verification exponent \( v = g^{s} \: mod \: p \). Now \( pk = (p, g, v) \) is her public key and \( sk = s \) is her secret key, which she sends to Victor.

Signature Creation Process

To sign a message \( m \), Samantha first computes the fingerprint \( \mathcal{H}(m) \) of the message using a publicly known hash function \( \mathcal{H} \), such that \( 1 \leq \mathcal{H}(m) \leq p-1 \). A hash function always produces the same output for the same input, and its output has a fixed length regardless of the input size. This means that, no matter how large the message Samantha wants to sign, the signing algorithm remains efficient because Samantha signs the fingerprint \( \mathcal{H}(m) \) instead of the entire message \( m \).

Before Samantha can sign the fingerprint \( \mathcal{H}(m) \), she needs a random number \( e \) (called an ephemeral key) between \( 1 \) and \( p-1 \) such that \( \gcd(e, p-1) = 1 \), because she also needs the inverse \( e^{-1} \) of \( e \). She computes \( e^{-1} \) using the extended Euclidean algorithm, which gives her the equation \( e \cdot \lambda + (p-1) \cdot \mu = \gcd(e, p-1) \), where \( e^{-1} = \lambda \: mod \: (p-1) \) and \( e \cdot e^{-1} \: mod \: (p-1) = 1 \) (remember that in the case of ElGamal, \( e^{-1} \) only exists because \( \gcd(e, p-1) = 1 \)). She then signs the fingerprint using the signing algorithm \( S \) with the secret signing key \( sk = s \), computing \( (\sigma_{1}, \sigma_{2}) = S_{sk}(\mathcal{H}(m)) \), where \( \sigma_{1} = g^{e} \: mod \: p \) and \( \sigma_{2} = (\mathcal{H}(m) - s \cdot \sigma_{1}) \cdot e^{-1} \: mod \: (p-1) \). Finally, Samantha sends the signature \( (\sigma_{1}, \sigma_{2}) \) of \( \mathcal{H}(m) \) and the message \( m \) to Victor.

Verification Process

To verify the signature, Victor first uses the same hash function \( \mathcal{H} \) as Samantha to compute the fingerprint \( \mathcal{H}(m) \) of the message \( m \). He then verifies the signature \( (\sigma_{1}, \sigma_{2}) \) of \( \mathcal{H}(m) \) by computing \( V_{1} = v^{\sigma_{1}} \cdot \sigma_{1}^{\sigma_{2}} \: mod \: p \) and checking that it is equal to \( V_{2} = g^{\mathcal{H}(m)} \: mod \: p \). The signature is valid only if \( V_{1} = V_{2} \), because:

\( \eqalign{ V_{1} &= v^{\sigma_{1}} \cdot \sigma_{1}^{\sigma_{2}} \: mod \: p &&(v = g^{s} \: \mbox{and} \: \sigma_{1} = g^{e}) \\ &= (g^{s})^{\sigma_{1}} \cdot (g^{e})^{\sigma_{2}} \: mod \: p &&(\mbox{exponent rule}) \\ &= g^{s \cdot \sigma_{1}} \cdot g^{e \cdot \sigma_{2}} \: mod \: p &&(\mbox{exponent rule}) \\ &= g^{s \cdot \sigma_{1} + e \cdot \sigma_{2}} \: mod \: p &&(\sigma_{2} = (\mathcal{H}(m) - s \cdot \sigma_{1}) \cdot e^{-1}) \\ &= g^{s \cdot \sigma_{1} + e \cdot ((\mathcal{H}(m) - s \cdot \sigma_{1}) \cdot e^{-1})} \: mod \: p &&(e \cdot e^{-1} = 1) \\ &= g^{s \cdot \sigma_{1} + (\mathcal{H}(m) - s \cdot \sigma_{1})} \: mod \: p &&(s \cdot \sigma_{1} - s \cdot \sigma_{1} = 0) \\ &= g^{\mathcal{H}(m)} \: mod \: p &&(V_{2} = g^{\mathcal{H}(m)}) \\ &= V_{2} } \)

Only if Samantha's and Victor's adversary, Eve, knows how to solve the discrete logarithm problem—i.e., to compute the secret key \( sk = s \) from the public key \( pk = g^{s} \: mod \: p \)—will she be able to sign documents on behalf of Samantha. But the discrete logarithm problem is hard to solve in the group \( \mathbb{Z}_{p}^{*} \) when the prime number \( p \) is large.

It's important that Samantha signs the fingerprint instead of the message itself for several reasons:

1. Efficiency: Hashing allows signing of arbitrarily large messages with fixed computational effort
2. Security: Prevents existential forgery attacks (explained below)
3. Integrity: Even minor changes to the message result in a completely different hash
4. Domain conversion: Maps message data to the mathematical domain required by the signature algorithm

Without using a hash function, Eve could easily forge a signature by computing the following values: First, Eve randomly chooses \( w \) and \( z \) between 1 and \( p-1 \) such that \( \gcd(w, p-1)=1 \), because she needs the inverse \( w^{-1} \) of \( w \) (which she computes with the extended Euclidean algorithm). She then uses Samantha's public key \( pk = (p, g, v) \) to compute \( \sigma_{1} = g^{z} \cdot v^{w} \: mod \: p \), \( \sigma_{2} = -\sigma_{1} \cdot w^{-1} \: mod \: (p-1) \), and the message \( m = -\sigma_{1} \cdot z \cdot w^{-1} \: mod \: (p-1) \). (The message may seem a bit odd, but the content of the message is not important—only that Eve can forge a signature.) We see that \( (\sigma_{1}, \sigma_{2}) \) is a valid signature of \( m \) because Victor's final check is still true, i.e., \( v^{\sigma_{1}} \cdot \sigma_{1}^{\sigma_{2}} \: mod \: p \) is equal to \( g^{m} \: mod \: p \), which is the same as \( \sigma_{1}^{\sigma_{2}} \: mod \: p \) being equal to \( g^{m} \cdot v^{-\sigma_{1}} \: mod \: p \):

\( \eqalign{ V_{1} &= \sigma_{1}^{\sigma_{2}} \: mod \: p &&(\sigma_{1} = g^{z} \cdot v^{w} \: \mbox{and} \: \sigma_{2} = -\sigma_{1} \cdot w^{-1}) \\ &= (g^{z} \cdot v^{w})^{(-\sigma_{1} \cdot w^{-1})} \: mod \: p &&(\mbox{exponent rule}) \\ &= (g^{z} \cdot (g^{s})^{w})^{(-\sigma_{1} \cdot w^{-1})} \: mod \: p &&(\mbox{exponent rule}) \\ &= (g^{z} \cdot g^{s \cdot w})^{(-\sigma_{1} \cdot w^{-1})} \: mod \: p &&(\mbox{exponent rule}) \\ &= (g^{z + s \cdot w})^{(-\sigma_{1} \cdot w^{-1})} \: mod \: p &&(\mbox{exponent rule}) \\ &= g^{z \cdot (-\sigma_{1} \cdot w^{-1}) + (s \cdot w) \cdot (-\sigma_{1} \cdot w^{-1})} \: mod \: p &&(m = -\sigma_{1} \cdot z \cdot w^{-1} \: \mbox{and} \: w \cdot w^{-1} = 1) \\ &= g^{m - s \cdot \sigma_{1}} \: mod \: p &&(\mbox{exponent rule}) \\ &= g^{m} \cdot g^{- s \cdot \sigma_{1}} \: mod \: p &&(\mbox{exponent rule}) \\ &= g^{m} \cdot (g^{s})^{-\sigma_{1}} \: mod \: p &&(v = g^{s}) \\ &= g^{m} \cdot v^{-\sigma_{1}} \: mod \: p = V_{2} } \)

However, if Samantha uses a secure hash function, i.e., \( (\sigma_{1}, \sigma_{2}) = S_{sk}(\mathcal{H}(m)) \), the above method is no longer possible because Eve would now be required to find a preimage of the hash function, which is computationally hard. In other words, think of \( -\sigma_{1} \cdot z \cdot w^{-1} \) (the value of the message in the above attack) as a fingerprint; now Eve must find a message \( m \) such that \( \mathcal{H}(m) = -\sigma_{1} \cdot z \cdot w^{-1} \).

The ElGamal signature \( (\sigma_{1}, \sigma_{2}) \) is approximately \( 2 \cdot \log_{2}(p) \) bits in length, since \( \sigma_{1} \) is \( \log_{2}(p) \) bits and \( \sigma_{2} \) is \( \log_{2}(p-1) \) bits (because \( \sigma_{1} \) is computed modulo \( p \) and \( \sigma_{2} \) is computed modulo \( p-1 \)). Therefore, for the signature scheme to be secure, the prime number \( p \) should be at least \( 2048 \) bits according to today's standards, which implies that the ElGamal signature \( (\sigma_{1}, \sigma_{2}) \) is at least \( 4096 \) bits long.

Below, we present some variants of the ElGamal signature scheme that use shorter signatures: the Schnorr signature and the Digital Signature Algorithm (DSA). Both of these schemes use a subgroup of order \( q \) (explained in more detail later), where \( q \) is a prime number typically chosen to be between \( 160 \) and \( 230 \) bits. As a result, the Schnorr and DSA signatures \( (\sigma_{1}', \sigma_{2}') \) are between \( 320 \) and \( 460 \) bits in length (since both \( \sigma_{1}' \) and \( \sigma_{2}' \) are computed modulo \( q \), making the signature approximately \( 2 \cdot \log_{2}(q) \) bits long).

Practical Applications

While pure ElGamal signatures are rarely used in practice today due to their large size, the variants (Schnorr and DSA) described in the following sections are widely deployed in modern cryptographic systems.

Comparison of Signature Schemes

The protocol

Try a demo of the signature scheme here.

Example

A trusted third party chooses the prime number \( p = 379 \) and the generator \( g = 360 \) of the group \( \mathbb{Z}_{379}^{*} \). Samantha then chooses the secret key \( sk = s = 77 \) and computes the public verification key \( v = g^{s} \: mod \: p = 360^{77} \: mod \: 379 = 202 \). She then publishes the public key \( pk = (p, g, v) = (379, 360, 202) \).

The message Samantha wants to sign is \( m = \mbox{"Transfer 100 USD to Carla"} \), for which she computes the fingerprint \( \mathcal{H}(m) = 273 \) using a publicly known hash function \( \mathcal{H} \). She then chooses the ephemeral key (a unique random number) \( e = 187 \) such that \( \gcd(e, p-1) = \gcd(187, 379-1) = 1 \), and computes the inverse \( e^{-1} \) of \( e \) using the extended Euclidean algorithm. The extended Euclidean algorithm gives her the equation \( \gcd(e, p-1) = e \cdot \lambda + (p-1) \cdot \mu = 187 \cdot (-152) + (379-1) \cdot 75 = 1 \), where \( e^{-1} = \lambda \: mod \: (p-1) = -152 \: mod \: (379-1) = 283 \).

Finally, she signs the fingerprint by computing \( \sigma_{1} = g^{e} \: mod \: p = 360^{187} \: mod \: 379 = 358 \) and \( \sigma_{2} = (\mathcal{H}(m) - s \cdot \sigma_{1}) \cdot e^{-1} \: mod \: (p-1) = (273 - 77 \cdot 358) \cdot 283 \: mod \: (379-1) = 133 \), where \( (\sigma_{1}, \sigma_{2}) = S_{sk}(\mathcal{H}(m)) = (358, 133) \) is the signature of \( \mathcal{H}(m) \) that she sends to Victor along with the message \( m \).

Victor verifies the signature by first computing the fingerprint \( \mathcal{H}(m) = 273 \) of the message using the same hash function \( \mathcal{H} \) as Samantha. He then uses Samantha's public key to verify that \( v^{\sigma_{1}} \cdot \sigma_{1}^{\sigma_{2}} \: mod \: p = 202^{358} \cdot 358^{133} \: mod \: 379 = 145 \) is equal to \( g^{\mathcal{H}(m)} \: mod \: p = 360^{273} \: mod \: 379 = 145 \).

The Schnorr signature was first proposed by Claus P. Schnorr in 1989 and is a more efficient variant of the ElGamal signature scheme that allows for shorter signatures.

• Shorter signatures: ~320-460 bits vs ~4096 bits for ElGamal
• Provable security: Based on the discrete logarithm problem
• Key aggregation: Supports signature aggregation for multi-signature applications
• Batch verification: Multiple signatures can be verified together efficiently

Schnorr Key Generation

First, Samantha (or a trusted third party) chooses two prime numbers \( p \) and \( q \) such that \( p \: mod \: q = 1 \) (by first choosing \( q \) and then computing \( p = i \cdot q + 1 \) for \( i \geq 2 \) until \( p \) is a prime number), and a generator \( g \) of order \( q \) from the group \( \mathbb{Z}_{p}^{*} \). If a generator \( g \) has order \( q \), it means that it generates a subgroup \( G \) of \( \mathbb{Z}_{p}^{*} \) with \( q \) elements, i.e., \( |G|=q \). Samantha can easily find \( g \) by computing \( g = g_{1}^{(p-1)/q} \: mod \: p \), where \( g_{1} \) is a generator of the group \( \mathbb{Z}_{p} \). Next, Samantha chooses a secret signing key \( s \) between \( 1 \) and \( q-1 \) and computes the public verification key \( v = g^{s} \: mod \: p \). Samantha publishes her public key \( pk = (p, q, g, v) \) and stores her secret key \( sk = s \). Notice that both Victor and their adversary Eve can see the public key, but they would have to solve the discrete logarithm problem for \( v \) to obtain the secret key \( s \).

Signature Creation Process

Suppose Samantha wants to sign a large message \( m \). She first computes the fingerprint \( \mathcal{H}(m) \) of the message \( m \) using a publicly known hash function \( \mathcal{H} \), and then signs the fingerprint instead of the message itself. One property of a hash function is that the input can be of arbitrary length, but the output always has a fixed length. The hash function used by Samantha returns a fingerprint such that \( 1 \leq \mathcal{H}(m) \leq q-1 \). Samantha then chooses a unique random number \( e \) (an ephemeral key, which is only used once for each signature) such that \( 1 \leq e \leq q-1 \). Finally, she uses the signing algorithm \( S \) with the secret key \( sk = s \) to compute the signature \( (\sigma_{1}, \sigma_{2}) = S_{sk}(\mathcal{H}(m)) \), where \( \sigma_{1} = \mathcal{H}(\mathcal{H}(m) \: \| \: g^{e} \: mod \: p) \) and \( \sigma_{2} = e + s \cdot \sigma_{1} \: mod \: q \) (the symbol \( \| \) means concatenation). She then sends the signature \( (\sigma_{1}, \sigma_{2}) \) and the message \( m \) to Victor.

Verification Process

To verify the signature, Victor first uses the same hash function \( \mathcal{H} \) as Samantha to compute the fingerprint \( \mathcal{H}(m) \) of the message \( m \). He then computes \( S = \mathcal{H}(\mathcal{H}(m) \: \| \: g^{\sigma_{2}} \cdot v^{-\sigma_{1} \: mod \: q} \: mod \: p) \) and checks that \( S \) is equal to \( \sigma_{1} \). The signature is valid only if \( S = \sigma_{1} \), because:

\( \eqalign{ S &= \mathcal{H}(\mathcal{H}(m) \: \| \: g^{\sigma_{2}} \cdot v^{-\sigma_{1}} \: mod \: p) &&(\sigma_{2} = e + s \cdot \sigma_{1}) \\ &= \mathcal{H}(\mathcal{H}(m) \: \| \: g^{e + s \cdot \sigma_{1}} \cdot v^{-\sigma_{1}} \: mod \: p) &&(v = g^{s}) \\ &= \mathcal{H}(\mathcal{H}(m) \: \| \: g^{e + s \cdot \sigma_{1}} \cdot (g^{s})^{-\sigma_{1}} \: mod \: p) &&(\mbox{exponent rule}) \\ &= \mathcal{H}(\mathcal{H}(m) \: \| \: g^{e + s \cdot \sigma_{1}} \cdot g^{-(s \cdot \sigma_{1})} \: mod \: p) &&(\mbox{exponent rule}) \\ &= \mathcal{H}(\mathcal{H}(m) \: \| \: g^{e + s \cdot \sigma_{1} - (s \cdot \sigma_{1})} \: mod \: p) &&((s \cdot \sigma_{1})-(s \cdot \sigma_{1}) = 0) \\ &= \mathcal{H}(\mathcal{H}(m) \: \| \: g^{e} \: mod \: p) \\ &= \sigma_{1} } \)

Security Considerations

Schnorr signatures offer several security advantages:

• Provable security: Security reducible to the discrete logarithm problem under the random oracle model
• Non-malleability: More resistant to certain signature manipulation attacks
• Simplicity: Simpler design means fewer implementation pitfalls

As with ElGamal signatures, never reuse the ephemeral key \(e\). Doing so would allow an attacker to recover the private key.

Practical Applications

Schnorr signatures have seen renewed interest in recent years, particularly in blockchain technology, due to their elegant mathematical properties and efficiency benefits.

The protocol

Example

A trusted third party chooses the two prime numbers \( p = 2111 \) and \( q = 211 \), the generator \( g_{1} = 434 \) of the group \( \mathbb{Z}_{2111} \), and computes the generator \( g = g_{1}^{(p-1)/q} \: mod \: p = 434^{(2111-1)/211} \: mod \: 2111 = 682 \) of order \( q = 211 \). Samantha then chooses the secret key \( sk = s = 116 \) and computes the public verification key \( v = g^{s} \: mod \: p = 682^{116} \: mod \: 2111 = 1758 \). She then publishes her public key \( pk = (p, q, g, v) = (2111, 211, 682, 1758) \).

The message Samantha wants to sign is \( m = \mbox{"Transfer 100 USD to Carla"} \), for which she computes the fingerprint using the hash function \( \mathcal{H} \): \( \mathcal{H}(m) = 189 \). She then chooses an ephemeral key (a unique random number) \( e = 82 \) and computes the signature \( (\sigma_{1}, \sigma_{2}) = (121, 192) \), where \( \sigma_{1} = \mathcal{H}(\mathcal{H}(m) \: \| \: g^{e} \: mod \: p) = \mathcal{H}(189 \: \| \: 682^{82} \: mod \: 2111) = 121 \) and \( \sigma_{2} = e + s \cdot \sigma_{1} \: mod \: q = 82 + 116 \cdot 121 \: mod \: 211 = 192 \). Finally, she sends the signature \( (\sigma_{1}, \sigma_{2}) = (121, 192) \) and the message \( m \) to Victor, who works at the bank.

Victor verifies the signature by first computing the fingerprint \( \mathcal{H}(m) = 189 \) of the message using the same hash function \( \mathcal{H} \) as Samantha. He then computes \( S = \mathcal{H}(\mathcal{H}(m) \: \| \: g^{\sigma_{2}} \cdot v^{-\sigma_{1} \: mod \: q} \: mod \: p) = \mathcal{H}(189 \: \| \: 682^{192} \cdot 1758^{-121 \: mod \: 211} \: mod \: 2111) = 121 \) and checks that \( S = 121 \) is equal to \( \sigma_{1} = 121 \).

The Digital Signature Algorithm (DSA), proposed by NIST (the National Institute of Standards and Technology) in 1991 and published as the DSS (Digital Signature Standard) in 1994, is a modified version of the Schnorr and ElGamal signature schemes. DSA allows for shorter signatures compared to the original ElGamal signature.

The Digital Signature Algorithm (DSA) is a FIPS-standardized signature scheme with these key properties:

• Security basis: Discrete logarithm problem in a prime-order subgroup
• Compact signatures: Similar size to Schnorr (~320-460 bits)
• Standardization: FIPS 186 standard widely adopted in government applications
• Variants: Adapted for use with elliptic curves (ECDSA)

DSA has an interesting historical background:

• Developed by David W. Kravitz, an NSA employee, in the early 1990s
• Patented by the US government (now expired) but freely available for public use
• Created as an alternative to the RSA algorithm which was patented at the time
• Selected as the Digital Signature Standard (DSS) by NIST in 1994
• Met with initial controversy due to its classified development process

Key Generation for DSA

First, Samantha (or a trusted third party) chooses two prime numbers \( p \) and \( q \) such that \( p \: mod \: q = 1 \) (this is typically done by first choosing \( q \) and then computing \( p = i \cdot q + 1 \) for \( i \geq 2 \) until \( p \) is prime), and a generator \( g \) of order \( q \) from the group \( \mathbb{Z}_{p}^{*} \). If a generator \( g \) has order \( q \), it means that it generates a subgroup \( G \) of \( \mathbb{Z}_{p}^{*} \) with \( q \) elements, i.e., \( |G|=q \). Samantha can easily find \( g \) by computing \( g = g_{1}^{(p-1)/q} \: mod \: p \), where \( g_{1} \) is a generator of the group \( \mathbb{Z}_{p} \). Next, Samantha chooses a secret signing key \( s \) and computes the public verification key \( v = g^{s} \: mod \: p \). Samantha publishes her public key \( pk = (p, q, g, v) \) and stores her secret key \( sk = s \). Notice that both Victor and their adversary Eve can see the public key, but they would need to solve the discrete logarithm problem for \( v \) to obtain the secret key \( s \).

Signature Creation Process

Instead of signing the message \( m \) itself, Samantha signs its fingerprint \( \mathcal{H}(m) \), which is computed using a publicly known hash function \( \mathcal{H} \). In DSA, the hash function used is SHA-1, where \( 1 \leq \mathcal{H}(m) \leq q-1 \). One property of a hash function is that the input can be of arbitrary length, but the output always has a fixed length.

Samantha chooses a unique random number \( e \) (an ephemeral key that is only used once for each signature) such that \( 1 \leq e \leq q-1 \) and \( \gcd(e, q) = 1 \), because she also needs the inverse \( e^{-1} \) of \( e \). (Remember that in the case of DSA, \( e^{-1} \) only exists when \( \gcd(e, q) = 1 \).) The inverse \( e^{-1} \) is computed using the extended Euclidean algorithm, which gives her the equation \( e \cdot \lambda + q \cdot \mu = \gcd(e, q) \), where \( e^{-1} = \lambda \: mod \: q \) and \( e \cdot e^{-1} \: mod \: q = 1 \). Finally, she computes the signature using the signing algorithm \( S \) with the secret key \( sk=s \) by \( (\sigma_{1}, \sigma_{2}) = S_{sk}(\mathcal{H}(m)) \), where \( \sigma_{1} = (g^{e} \: mod \: p) \: mod \: q \) and \( \sigma_{2} = (\mathcal{H}(m) + s \cdot \sigma_{1}) \cdot e^{-1} \: mod \: q \). Samantha sends the signature \( (\sigma_{1}, \sigma_{2}) \) and the message \( m \) to Victor.

Verification Process

To verify the signature, Victor first uses the SHA-1 hash function \( \mathcal{H} \), as Samantha did, to compute the fingerprint \( \mathcal{H}(m) \) of the message \( m \). He then computes the inverse \( \sigma_{2}^{-1} \) of \( \sigma_{2} \) using the extended Euclidean algorithm, which gives him the equation \( \sigma_{2} \cdot \lambda + q \cdot \mu = \gcd(\sigma_{2}, q) \), where \( \sigma_{2}^{-1} = \lambda \: mod \: q \) and \( \sigma_{2} \cdot \sigma_{2}^{-1} \: mod \: q = 1 \). (Remember that in the case of DSA, \( \sigma_{2}^{-1} \) only exists because \( \gcd(\sigma_{2}, q)=1 \).) Finally, he computes \( V_{1} = \mathcal{H}(m) \cdot \sigma_{2}^{-1} \: mod \: q \) and \( V_{2} = \sigma_{1} \cdot \sigma_{2}^{-1} \: mod \: q \), and checks that \( S = (g^{V_{1}} \cdot v^{V_{2}} \: mod \: p) \: mod \: q \) is equal to \( \sigma_{1} \). The signature is valid only if \( S = \sigma_{1} \), because:

\( \eqalign{ S &= (g^{V_{1}} \cdot v^{V_{2}} \: mod \: p) \: mod \: q &&(v=g^{s}) \\ &= (g^{V_{1}} \cdot (g^{s})^{V_{2}} \: mod \: p) \: mod \: q &&(\mbox{exponent rule}) \\ &= (g^{V_{1}} \cdot g^{s \cdot V_{2}} \: mod \: p) \: mod \: q &&(V_{1} = \mathcal{H}(m) \cdot \sigma_{2}^{-1} \: \mbox{and} \: V_{2} = \sigma_{1} \cdot \sigma_{2}^{-1}) \\ &= (g^{\mathcal{H}(m) \cdot \sigma_{2}^{-1}} \cdot g^{s \cdot \sigma_{1} \cdot \sigma_{2}^{-1}} \: mod \: p) \: mod \: q &&(\mbox{exponent rule}) \\ &= (g^{\mathcal{H}(m) \cdot \sigma_{2}^{-1} + s \cdot \sigma_{1} \cdot \sigma_{2}^{-1}} \: mod \: p) \: mod \: q \\ &= (g^{(\mathcal{H}(m) + s \cdot \sigma_{1}) \cdot \sigma_{2}^{-1}} \: mod \: p) \: mod \: q &&(e \cdot \sigma_{2} \: mod \: q = \mathcal{H}(m) + s \cdot \sigma_{1} \: mod \: q) \\&= (g^{e \cdot \sigma_{2} \cdot \sigma_{2}^{-1}} \: mod \: p) \: mod \: q &&(\sigma_{2} \cdot \sigma_{2}^{-1} \: mod \: q = 1) \\&= (g^{e} \: mod \: p) \: mod \: q \\ &= \sigma_{1} } \)

It may not be immediately obvious that \( e \cdot \sigma_{2} \: mod \: q = \mathcal{H}(m) + s \cdot \sigma_{1} \: mod \: q \), but as we can see:

\( \eqalign{ e \cdot \sigma_{2} \: mod \: q &= e \cdot ((\mathcal{H}(m) + s \cdot \sigma_{1}) \cdot e^{-1}) \: mod \: q \\ &= e \cdot (\mathcal{H}(m) \cdot e^{-1} + s \cdot \sigma_{1} \cdot e^{-1}) \: mod \: q \\ &= \mathcal{H}(m) \cdot e^{-1} \cdot e + s \cdot \sigma_{1} \cdot e^{-1} \cdot e \: mod \: q &&(e \cdot e^{-1} \: mod \: q = 1) \\ &= \mathcal{H}(m) + s \cdot \sigma_{1} \: mod \: q } \)

The reason why it is important that the value \( e \) is only used once for each signature is that, otherwise, it would be easy for Eve to compute Samantha's secret key \( s \). The second part of the signature, \( \sigma_{2} = (\mathcal{H}(m) + s \cdot \sigma_{1}) \cdot e^{-1} \: mod \: q \), can be rearranged to \( s = (\sigma_{2} \cdot e - \mathcal{H}(m)) \cdot \sigma_{1}^{-1} \: mod \: q \). Thus, knowing the value of \( e \) allows Eve to easily recover the private key \( s \). Suppose Samantha signs two different messages, \( m \) and \( m' \), using the same \( e \). She then produces two signatures, \( (\sigma_{1}, \sigma_{2}) \) and \( (\sigma_{1}', \sigma_{2}') \), where \( \sigma_{2} = (\mathcal{H}(m) + s \cdot \sigma_{1}) \cdot e^{-1} \: mod \: q \) and \( \sigma_{2}' = (\mathcal{H}(m') + s \cdot \sigma_{1}) \cdot e^{-1} \: mod \: q \). Eve can now compute the value of \( e \) by first calculating:

\( \eqalign{ \sigma_{2} - \sigma_{2}' &= ((\mathcal{H}(m) + s \cdot \sigma_{1}) \cdot e^{-1} - (\mathcal{H}(m') + s \cdot \sigma_{1}) \cdot e^{-1}) \: mod \: q \\ &= ((\mathcal{H}(m) \cdot e^{-1} + s \cdot \sigma_{1} \cdot e^{-1}) - (\mathcal{H}(m') \cdot e^{-1} + s \cdot \sigma_{1} \cdot e^{-1})) \: mod \: q \\ &= (\mathcal{H}(m) \cdot e^{-1} + s \cdot \sigma_{1} \cdot e^{-1} - \mathcal{H}(m') \cdot e^{-1} - s \cdot \sigma_{1} \cdot e^{-1}) \: mod \: q &&(s \cdot \sigma_{1} \cdot e^{-1} - s \cdot \sigma_{1} \cdot e^{-1} = 0) \\ &= (\mathcal{H}(m) \cdot e^{-1} - \mathcal{H}(m') \cdot e^{-1}) \: mod \: q\\ &= (\mathcal{H}(m) - \mathcal{H}(m')) \cdot e^{-1} \: mod \: q } \)

By rearranging the equation \( \sigma_{2} - \sigma_{2}' = (\mathcal{H}(m) - \mathcal{H}(m')) \cdot e^{-1} \: mod \: q \), Eve can solve for \( e \) as follows: \( e = (\mathcal{H}(m) - \mathcal{H}(m')) \cdot (\sigma_{2} - \sigma_{2}')^{-1} \: mod \: q \).

Security Considerations

DSA requires careful implementation to avoid several security pitfalls:

• Random number generation: The ephemeral key must come from a cryptographically secure random number generator
• Key length: Modern implementations should use at least 2048-bit p and 256-bit q
• Parameter validation: All parameters should be validated to prevent small subgroup attacks
• Modern hash functions: While the original DSA used SHA-1, modern implementations should use SHA-256 or stronger

The reason why it is important that the value \( e \) is only used once for each signature is that, otherwise, it would be easy for Eve to compute Samantha's secret key \( s \)...

Practical Applications

As computing power increases, DSA implementations are gradually transitioning to elliptic curve variants (ECDSA) for improved efficiency with smaller key sizes while maintaining equivalent security.

The protocol

Example

A trusted third party chooses the two prime numbers \( p = 467 \) and \( q = 233 \), and the generator \( g_{1} = 383 \) of the group \( \mathbb{Z}_{467} \). The generator \( g \) of order \( q = 233 \) is computed as \( g = g_{1}^{(p-1)/q} \: mod \: p = 383^{(467-1)/233} \: mod \: 467 = 51 \). Samantha chooses the secret signing key \( s = 193 \) and computes the public verification key \( v = g^{s} \: mod \: p = 51^{193} \: mod \: 467 = 117 \). She then publishes her public key \( pk = (p, q, g, v) = (467, 233, 51, 117) \).

The message Samantha wants to sign is \( m = \mbox{"Transfer 100 USD to Carla"} \), for which she computes the fingerprint using the SHA-1 hash function \( \mathcal{H} \): \( \mathcal{H}(m) = 84 \). She then chooses an ephemeral key (a unique random number) \( e = 83 \) such that \( \gcd(e, q) = \gcd(83, 233) = 1 \), and computes the inverse \( e^{-1} \) of \( e \) using the extended Euclidean algorithm. The extended Euclidean algorithm gives her the equation \( \gcd(e, q) = e \cdot \lambda + q \cdot \mu = 83 \cdot 73 + 233 \cdot (-26) = 1 \), where \( e^{-1} = \lambda \: mod \: q = 73 \: mod \: 233 = 73 \).

Next, she computes the signature \( (\sigma_{1}, \sigma_{2}) = (135, 110) \), where \( \sigma_{1} = (g^{e} \: mod \: p) \: mod \: q = (51^{83} \: mod \: 467) \: mod \: 233 = 135 \) and \( \sigma_{2} = (\mathcal{H}(m) + s \cdot \sigma_{1}) \cdot e^{-1} \: mod \: q = (84 + 193 \cdot 135) \cdot 73 \: mod \: 233 = 110 \). Finally, she sends the signature \( (\sigma_{1}, \sigma_{2}) = (135, 110) \) and the message \( m \) to Victor, who works at the bank.

Victor verifies the signature by first computing the fingerprint \( \mathcal{H}(m) = 84 \) of the message, just as Samantha did, using the SHA-1 hash function \( \mathcal{H} \). He then computes the inverse \( \sigma_{2}^{-1} = 197 \) of \( \sigma_{2} = 110 \) using the extended Euclidean algorithm, and the two values \( V_{1} = \mathcal{H}(m) \cdot \sigma_{2}^{-1} \: mod \: q = 84 \cdot 197 \: mod \: 233 \) and \( V_{2} = \sigma_{1} \cdot \sigma_{2}^{-1} \: mod \: q = 135 \cdot 197 \: mod \: 233 \). Finally, he verifies that \( (g^{V_{1}} \cdot v^{V_{2}} \: mod \: p) \: mod \: q = (51^{5} \cdot 117^{33} \: mod \: 467) \: mod \: 233 = 135 \) is equal to \( \sigma_{1} = 135 \).