In cryptography, we often encrypt and sign messages that contain characters. However, asymmetric key cryptosystems (where Alice and Bob use different keys), such as RSA and ElGamal, are based on arithmetic operations on integers. Symmetric key cryptosystems (where Alice and Bob use the same key), such as DES and AES, are based on bitwise operations on bits (a bit is either 0 or 1 and is an abbreviation for binary digit). Therefore, we must convert characters into integers or bits before applying the cryptosystem to the message.
Because a computer can only handle bits, there already exists a method for converting characters into integers or bits, which uses the ASCII (American Standard Code for Information Interchange) table. A part of the ASCII table from Wikipedia is shown in the following table (note that the binary representation on the Wikipedia site uses only seven bits, but we use eight bits by prepending an extra 0):
| Character | Decimal | Hexadecimal | Binary |
|---|---|---|---|
| (space) | 32 | 20 | 00100000 |
| ! | 33 | 21 | 00100001 |
| \( \vdots \) | \( \vdots \) | \( \vdots \) | \( \vdots \) |
| A | 65 | 41 | 01000001 |
| B | 66 | 42 | 01000010 |
| \( \vdots \) | \( \vdots \) | \( \vdots \) | \( \vdots \) |
| a | 97 | 61 | 01100001 |
| b | 98 | 62 | 01100010 |
| \( \vdots \) | \( \vdots \) | \( \vdots \) | \( \vdots \) |
For example, if Alice wants to send the message "Hey Bob!" encrypted to Bob using a symmetric key cryptosystem, she first converts it into its integer representation and then into its binary representation:
\( \eqalign{ H &\rightarrow 72 &&\rightarrow 01001000 \\ e &\rightarrow 101 &&\rightarrow 01100101 \\ y &\rightarrow 121 &&\rightarrow 01111001 \\ &\rightarrow 32 &&\rightarrow 00100000 \\ B &\rightarrow 66 &&\rightarrow 01000010 \\ o &\rightarrow 111 &&\rightarrow 01101111 \\ b &\rightarrow 98 &&\rightarrow 01100010 \\ ! &\rightarrow 33 &&\rightarrow 00100001 } \)
That is, the message "Hey Bob!" is represented with integers as "72 101 121 32 66 111 98 33" and in binary as "01001000 01100101 01111001 00100000 01000010 01101111 01100010 00100001".
The exponent of a number indicates how many times the number is multiplied by itself. For example:
\( 4^{3} = 4 \cdot 4 \cdot 4 = 64 \)
Here, 3 is the exponent (or power), and 4 is the base. In words, we say "4 to the power of 3."
Here are the laws of exponents:
| Law | Example |
|---|---|
| \( x^{1} = x \) | \( 3^{1} = 3 \) |
| \( x^{0} = 1 \) | \( 4^{0} = 1 \) |
| \( x^{-1} = \frac{1}{x} \) | \( 5^{-1} = \frac{1}{5} \) |
| \( x^{m} \cdot x^{n} = x^{m+n} \) | \( x^{2} \cdot x^{3} = (x \cdot x) \cdot (x \cdot x \cdot x) = x \cdot x \cdot x \cdot x \cdot x = x^{5} = x^{2+3} \) |
| \( \frac{x^{m}}{x^{n}} = x^{m-n} \) | \( \frac{x^{4}}{x^{2}} = \frac{x \cdot x \cdot x \cdot x}{x \cdot x} = x \cdot x \cdot \frac{x \cdot x}{x \cdot x} = x \cdot x \cdot 1 = x^{2} = x^{4-2} \) |
| \( (x^{m})^{n} = x^{m \cdot n} \) | \( (x^{2})^{3} = (x \cdot x) \cdot (x \cdot x) \cdot (x \cdot x) = x \cdot x \cdot x \cdot x \cdot x \cdot x = x^{6} = x^{2 \cdot 3} \) |
| \( (x \cdot y)^{n} = x^{n} \cdot y^{n} \) | \( (x \cdot y)^{2} = (x \cdot y) \cdot (x \cdot y) = x \cdot x \cdot y \cdot y = x^{2} \cdot y^{2} \) |
| \( (\frac{x}{y})^{n} = \frac{x^{n}}{y^{n}} \) | \( (\frac{x}{y})^{3} = (\frac{x}{y}) \cdot (\frac{x}{y}) \cdot (\frac{x}{y}) = \frac{x \cdot x \cdot x}{y \cdot y \cdot y} = \frac{x^{3}}{y^{3}} \) |
| \( x^{-n} = \frac{1}{x^{n}} \) | \( x^{-3} = (x^{-1})^{3} = (\frac{1}{x})^{3} = \frac{1}{x} \cdot \frac{1}{x} \cdot \frac{1}{x} = \frac{1 \cdot 1 \cdot 1}{x \cdot x \cdot x} = \frac{1}{x^{3}} \) |
You already use modulo computation when you look at a clock and, for example, need to figure out what time it will be 3 hours after 11 o'clock, which is 2 o'clock. In mathematics, we write this as:
\( (11 + 3) \: mod \: 12 = 2 \)
Here, 12 is the modulus because we want the time as an integer between 0 and 11 (in this case, 12 o'clock is denoted by 0). In words, we say "11 plus 3 modulo 12 equals 2." The result of a modulo computation is an integer between 0 and the modulus minus 1. For example, with modulus 3, we have:
For example, if we look at \( 27 \: mod \: 5 \), modulo computes how many times 5 divides into 27 and then returns the remainder, which is 2 in this case. That is, \( 27 \: mod \: 5 = 2 \). But how do we get this result?
First, we compute how many times we can multiply 5 by an integer \( x \) so that the result is as close as possible to 27 without exceeding it. In other words, we find the maximum value of \( x \) such that \( 5 \cdot x \leq 27 \). In this case, \( x = 5 \) because \( 5 \cdot 5 = 25 \leq 27 \). Then, by subtracting 25 from 27, we get the answer: \( 27 - 25 = 2 \).
If the integer is negative, for example \( -27 \: mod \: 5 \), we have to do it slightly differently, and the answer is \( -27 \: mod \: 5 = 3 \). In this case, the integer \( x \) is negative and should be the closest integer such that \( 5 \cdot x \) does not exceed -27. That is, we find the minimum value of \( -x \) such that \( 5 \cdot -x \geq -27 \). Here, \( -x = -6 \) because \( 5 \cdot -6 = -30 \geq -27 \). Then, by subtracting -30 from -27, we get the answer: \( -27 - (-30) = -27 + 30 = 3 \).
It is important that \( x \) or \( -x \) is an integer such as \( -14, 3, 17 \), etc., and NOT a fraction or decimal such as \( \frac{1}{4}, \frac{-3}{7}, 2.5, 5.1 \), etc.
If two integers \( a \) and \( b \) modulo the same modulus \( c \) return the same remainder \( r \), then we say that \( a \) and \( b \) are congruent modulo \( c \). That is, if \( a \: mod \: c = r \) and \( b \: mod \: c = r \), then \( a \equiv b \: (mod \: c) \). Also, notice that if the modulus \( c \) is greater than the integer \( a \), i.e., \( c > a \), the result will always be \( a \: mod \: c = a \).
A prime number is an integer greater than 1 that can only be divided evenly by 1 and itself. "Divided evenly" means the result is an integer, not a float. For example, if you divide 13 by 3, you get the float \( \frac{13}{3} = 4.333 \). We see that 13 is a prime number because it can only be divided evenly by 1 and itself: \( \frac{13}{1} = 13 \) and \( \frac{13}{13} = 1 \).
If an integer is not a prime number, it is called a composite number. For example, the integer 6 is a composite number because it can be divided evenly by 1, 2, 3, and 6:
\( \frac{6}{1} = 6 \), \( \frac{6}{2} = 3 \), \( \frac{6}{3} = 2 \), and \( \frac{6}{6} = 1 \)
The term "composite" means "something made by combining things." So, a composite number is an integer made by multiplying prime numbers:
Therefore, every integer greater than 1 is either a prime number or a product of prime numbers (a composite number).
The famous Greek mathematician Euclid proved that there are infinitely many prime numbers.
Michael Rabin and Gary Miller developed an algorithm that determines whether an integer is a prime or a composite number by testing the integer with multiple bases, denoted by \( a \). The algorithm is called the Rabin-Miller primality test.
Before we describe what the greatest common divisor of two integers is, we first define what we mean by a divisor. In this context, a divisor of an integer \( x \) is any integer that divides \( x \) evenly, meaning the result is not a fraction. For example, if you divide \( x=12 \) by 5, you get the fraction \( \frac{12}{5} = 2.4 \), so 5 is not a divisor of \( x=12 \). For \( x=12 \), the divisors are 1, 2, 3, 4, 6, and 12 because \( \frac{12}{1} = 12 \), \( \frac{12}{2} = 6 \), \( \frac{12}{3} = 4 \), \( \frac{12}{4} = 3 \), \( \frac{12}{6} = 2 \), and \( \frac{12}{12} = 1 \).
Similarly, the divisors of 16 are 1, 2, 4, 8, and 16 because \( \frac{16}{1} = 16 \), \( \frac{16}{2} = 8 \), \( \frac{16}{4} = 4 \), \( \frac{16}{8} = 2 \), and \( \frac{16}{16}=1 \).
The greatest common divisor of 12 and 16 is therefore 4, because it is the largest integer among their common divisors. In mathematics, we write this as \( \gcd(12, 16) = 4 \).
Two integers whose greatest common divisor is 1 are called relatively prime numbers or co-primes. For example, 15 and 28 are relatively prime because \( \gcd(15, 28) = 1 \) (note that 28 is not a prime number).
If one of the two integers is a prime number, the greatest common divisor will always be 1, i.e., \( \gcd(a, p) = 1 \), where \( a \) is any integer (either prime or composite) and \( p \) is a prime number.
One method to compute the greatest common divisor of two integers is by using the Euclidean algorithm, developed by the famous Greek mathematician Euclid. See "The extended Euclidean algorithm" for more information about how to compute the greatest common divisor of two integers.
The extended Euclidean algorithm is an extension of the Euclidean algorithm, which only returns the greatest common divisor of two integers. Given two integers \( a \) and \( b \), the extended Euclidean algorithm returns the integers \( a \), \( b \), \( \lambda \), and \( \mu \) such that:
\( a \cdot \lambda + b \cdot \mu = \gcd(a, b) \)
Here, \( \lambda \) and \( \mu \) are called the Bézout coefficients for \( a \) and \( b \). Only if \( a \) and \( b \) are relatively prime, i.e., \( \gcd(a, b) = 1 \), then:
\( a \cdot \lambda + b \cdot \mu = 1 \)
In this case, \( \lambda \; mod \; b \) is the inverse of \( a \), denoted \( a^{-1} = \lambda \; mod \; b \), and \( \mu \: mod \: a \) is the inverse of \( b \), denoted \( b^{-1} = \mu \: mod \: a \) (see "Modulo computation" for more information about the \( mod \) operator). One useful property of an integer and its inverse is that \( a \cdot a^{-1} \; mod \; b = 1 \) and \( b \cdot b^{-1} \; mod \; a = 1 \).
You can easily compute \( \gcd(a, b) \), \( \lambda \), and \( \mu \) for example with \( a=5 \) and \( b=39 \) using a simple table. First, let us create a table with three columns (we do not yet know how many rows there will be). Let us denote the entry in the first row and first column as [1,1], the entry in the first row and second column as [1,2], the entry in the second row and first column as [2,1], and so on.
Next, we write \( b=39 \) in entry [1,1] and \( a=5 \) in entry [2,1]. Then we try to find the largest integer \( q_{1} \) such that \( q_{1} \cdot a \leq b \). We have \( q_{1}=7 \), which we write in entry [2,2], because \( 7 \cdot 5 = 35 \leq 39 \), and a remainder of \( r_{1}=4 \), which we write in entry [3,1].
Again, we try to find the largest integer \( q_{2} \) such that \( q_{2} \cdot r_{1} \leq a \). We have \( q_{2}=1 \), which we write in entry [3,2], because \( 1 \cdot 4 = 4 \leq 5 \), and a remainder of \( r_{2}=1 \), which we write in entry [4,1]. Notice that we are repeating the same process as before, just with the numbers in the next row.
The next computation returns a remainder of \( r_{3} = 0 \) because \( q_{3} \cdot r_{2} = 4 \cdot 1 = 4 \leq 4 = r_{1} \). We have now computed \( \gcd(5, 39)=r_{2}=1 \) since \( r_{3} = 0 \). Because 5 and 39 are relatively prime, we know that \( \lambda \) and \( \mu \) exist, and we can start using the last column.
First, we write \( x_{1}=0 \) in entry [4,3] and \( x_{2}=1 \) in entry [3,3]. Then we write \( x_{3}=q_{2} \cdot x_{2} + x_{1} = 1 \cdot 1 + 0 = 1 \) in entry [2,3]. For entry [1,3], we compute as before, just with numbers from the row above, i.e., \( x_{4}=q_{1} \cdot x_{3} + x_{2} = 7 \cdot 1 + 1 = 8 \).
Finally, we have that \( a \cdot x_{4} \pm b \cdot x_{3} = r_{2} \), where we need to decide whether it should be plus or minus between the two terms. Because \( a \cdot x_{4} = 5 \cdot 8 = 40 \), \( b \cdot x_{3} = 39 \cdot 1 \), and \( 40 \geq 39 \), we have \( 5 \cdot 8 - 39 \cdot 1 = 1 \) (which is the same as \( 5 \cdot 8 + 39 \cdot (-1) = 1 \)), so the Bézout coefficients are \( \lambda=8 \) and \( \mu=-1 \). Notice that \( a^{-1} = \lambda \; mod \; b = 8 \; mod \; 39 = 8\) and \( b^{-1} = \mu \; mod \; a = -1 \: mod \: 5 = 4\), where \( a \cdot a^{-1} \; mod \; b = 5 \cdot 8 \; mod \; 39 = 1 \) and \( b \cdot b^{-1} \; mod \; a = 39 \cdot 4 \; mod \; 5 = 1 \).
The table for computing \( 5 \cdot \lambda + 39 \cdot \mu = \gcd(5, 39) \) is:
| \( b=39 \) | \( x_{4}=8 \) | |
| \( a=5 \) | \( q_{1}=7 \) | \( x_{3}=1 \) |
| \( r_{1}=4 \) | \( q_{2}=1 \) | \( x_{2}=1 \) |
| \( r_{2}=1 \) | \( q_{3}=4 \) | \( x_{1}=0 \) |
| \( r_{3}=0 \) |
The set of integers \( \{ \dots, -2, -1, 0, 1, 2, \dots \} \) is denoted by the symbol \( \mathbb{Z} \), i.e., \( \mathbb{Z} = \{ \dots, -2, -1, 0, 1, 2, \dots \} \), and is called the ring of integers or an additive group. The group of integers modulo \( n \) is a subset of \( \mathbb{Z} \) and is denoted by \( \mathbb{Z}/n\mathbb{Z} \), but we use the shorthand \( \mathbb{Z}_{n} \). This subset contains the following elements (because we compute modulo \( n \)):
\( \mathbb{Z}_{n} = \{ 0, 1, 2, \dots, n - 1 \}\)
Notice that whenever we perform addition or multiplication in \( \mathbb{Z}_{n} \), we always compute the result modulo \( n \) to obtain an integer in \( \mathbb{Z}_{n} \). To illustrate this, let us look at \( n = 5 \):
\( \mathbb{Z}_{5} = \{ 0, 1, 2, 3, 4 \}\)
When adding \( 3 \) and \( 4 \) in \( \mathbb{Z}_{5} \), we do the following: \( (3 + 4) \: mod \: 5 = 7 \: mod \: 5 = 2 \). Likewise, when multiplying \( 3 \) by \( 4 \) in \( \mathbb{Z}_{5} \), we have: \( (3 \cdot 4) \: mod \: 5 = 12 \: mod \: 5 = 2 \).
An integer \( a \) in \( \mathbb{Z}_{n} \) has an inverse if the greatest common divisor of \( a \) and \( n \) is 1, i.e., \( \gcd(a, n) = 1 \) (see "The extended Euclidean algorithm" for more information). The integer \( a \) is then called a unit. The set of units (all integers with an inverse in \( \mathbb{Z}_{n} \)) is denoted by \( (\mathbb{Z}/n\mathbb{Z})^{*} \). Again, we use the shorthand \( \mathbb{Z}_{n}^{*} \). If \( a_{1} \) and \( a_{2} \) are units, then their product \( (a_{1} \cdot a_{2}) \: mod \: n \) is also always a unit (i.e., \( a_{1} \cdot a_{2} \) is in the group \( \mathbb{Z}_{n}^{*} \)), but the sum \( (a_{1} + a_{2}) \: mod \: n \) may NOT be a unit (i.e., \( a_{1} + a_{2} \) is in \( \mathbb{Z}_{n} \) but may not be in \( \mathbb{Z}_{n}^{*} \)). We see the difference in the two sets \( \mathbb{Z}_{8} \) and \( \mathbb{Z}_{8}^{*} \):
If we choose \( n \) to be a prime number \( p \), then for all integers \( a \) except 0 in \( \mathbb{Z}_{p} \), we have \( \gcd(a, p) = 1 \), which means that \( \mathbb{Z}_{p}^{*} \) contains all integers from \( \mathbb{Z}_{p} \) except 0, i.e.:
\( \mathbb{Z}_{p}^{*} = \{ 1, 2, 3, \dots, p - 1 \}\)
For example, for \( p=7 \), the only difference between the two sets \( \mathbb{Z}_{7} \) and \( \mathbb{Z}_{7}^{*} \) is the integer 0:
The number of elements in \( \mathbb{Z}_{n}^{*} \) is denoted by \( \phi(n) \), named after the famous Swiss mathematician Euler, and is called Euler's phi function. As we saw previously, if \( n \) is a prime number \( p \), then \( \phi(p) = p-1 \). The number of elements in a group \( G \) is also called the order of \( G \) and is written as \( \left| G \right| \). The order of:
If, for example, we choose the elements \( x \), \( a \), and \( b \) from the group \( \mathbb{Z}_{p}^{*} \) and want to compute \( x^{a + b} \: mod \: p \), then in the exponent we actually compute \( a + b \) modulo the order of the group, i.e., \( a + b \: mod \: (p-1) \) because \( \left| \mathbb{Z}_{p}^{*} \right| = \phi(p) = p-1 \). So, what we actually compute is \( x^{a + b \: mod \: (p-1)} \: mod \: p \). The same is true if we had chosen one of the other groups: we always compute modulo the order of the group in the exponent. Therefore, next time you look at an equation from a cryptosystem and wonder why they suddenly compute, for example, modulo \( p-1 \) instead of modulo \( p \), it is because the equation is used in the exponent of some integer.
In the following, we use the group \( \mathbb{Z}_{p} \) as an example for simplicity, but any group could be chosen.
There exists an element \( g \) in the group of integers \( \mathbb{Z}_{p} \) (see "The group of integers and units" for more information), where \( p \) is a prime number, whose powers generate every element in the set of units \( \mathbb{Z}_{p}^{*} \). That is, there exists an integer \( g \) in \( \mathbb{Z}_{p} \) such that:
\( \mathbb{Z}_{p}^{*} = \{ g^{1} \: mod \: p, g^{2} \: mod \: p, g^{3} \: mod \: p, \dots, g^{p-1} \: mod \: p \} \)
where \( g^{p-1} \: mod \: p = 1 \) because \( p-1 \: mod \: (p-1) = 0 \) (remember that the order of \( \mathbb{Z}_{p}^{*} \) is \( p-1 \), and we compute modulo the order of the group in the exponent of \( g \) because \( g \) belongs to the group \( \mathbb{Z}_{p}^{*} \)), and \( g^{0} = 1 \). Such a \( g \) is called a generator or a primitive root of the group, and it's denoted as \( \left< g \right> = \mathbb{Z}_{p}^{*} \). We also say that the order of \( g \) is \( ord(g) = p-1 \) because \( g \) generates the group \( \mathbb{Z}_{p}^{*} \) with \( p-1 \) elements.
To clarify, let's look at an example with the prime number 5. Recall that \( \mathbb{Z}_{5}^{*} = \{ 1, 2, 3, 4 \} \) (see "The group of integers and units" for the example). The group \( \mathbb{Z}_{5}^{*} \) has 2 as a generator because the powers of 2 generate every element in the group, i.e., \( \left< 2 \right> = \mathbb{Z}_{5}^{*} \):
The last power is 4 because \( p - 1 = 5 - 1 = 4 \). On the other hand, 4 is NOT a generator of \( \mathbb{Z}_{5}^{*} \) because the powers of 4 only generate the integers 1 and 4:
If you don't know the factorization of the integer \( p-1 \), then the only way to find a generator is to perform the above computation, i.e., check that it generates every element in the group \( \mathbb{Z}_{p}^{*} \). However, if you know the factorization of \( p-1 \), then for every prime number \( q \) that evenly divides \( p-1 \), we check that \( g^{(p-1)/q} \: mod \: p \neq 1 \) for a random integer \( g \) in the group \( \mathbb{Z}_{p} \). If this is the case, then \( g \) is a generator of \( \mathbb{Z}_{p}^{*} \).
Because the prime factorization problem is hard (the problem of computing the factorization of the integer \( p-1 \)), we use a so-called safe prime \( p \). A safe prime \( p \) is of the form \( p = 2 \cdot q + 1 \) where \( q \) is a prime number. Now, the factorization of \( p-1 \) is always only \( 2 \) and \( q \). For example, if we compute the safe prime \( p = 2 \cdot 5 + 1 = 11 \) with the prime number \( q = 5 \), we see that \( g = 7 \) is a generator of the group \( \mathbb{Z}_{11}^{*} \) because:
where 2 and \( q=5 \) are the only prime numbers that divide \( p-1=11-1=10 \) evenly. For the same reason, \( g = 5 \) is not a generator of \( \mathbb{Z}_{11}^{*} \) because:
The group \( \mathbb{Z}_{n}^{*} \), where \( n \) is a composite number, may not have a generator, but if \( n \) is a prime number \( p \), then the group \( \mathbb{Z}_{p}^{*} \) has at least one generator.
Let \( g \) be a generator of the group \( G \). Given the values \( g \) and \( H \), the discrete logarithm (DL) problem is to compute the exponent \( a \) in the following equation, which is considered a hard problem:
\( g^{a} = H \)
The exponent \( a \) is also called the discrete logarithm of \( H \) to the base \( g \).
For example, if we use the group \( \mathbb{Z}_{p}^{*} \), where \( p \) is a large prime number and \( g \) is a generator of the group, then given \( g \), \( p \), and \( H \), it is hard to compute \( a \) such that the following equation holds:
\( g^{a} \: mod \: p = H \)
In addition to the DL problem, there are two related problems: the Diffie-Hellman (DH) problem and the Decisional Diffie-Hellman (DDH) problem. Given the values \( g \), \( g^{a} \), and \( g^{b} \), the DH problem is to compute the exponent \( a \cdot b \) in \( g^{a \cdot b} \).
Similarly, given the values \( g \), \( g^{a} \), \( g^{b} \), and \( g^{c} \), the DDH problem is to decide whether \( c = a \cdot b \) or whether \( c \) is a random integer.
You may have noticed that if we can solve the DL problem, that is, compute \( a \) in \( g^{a} = H \), then we can also solve the DH problem: first compute \( a \) from \( g^{a} \), then \( b \) from \( g^{b} \), and finally calculate \( a \cdot b \). This also implies that we can solve the DDH problem: first compute \( a \cdot b \) as described above, then compute \( c \) from \( g^{c} \), and finally check whether \( c = a \cdot b \).
The security of an asymmetric (public-key) cryptosystem, such as RSA or ElGamal, is measured with respect to chosen plaintext attacks (CPA) and chosen ciphertext attacks (CCA).
In a chosen plaintext attack (sometimes called a semantic attack), Alice and Bob's adversary, Eve, is passive; she only observes the ciphertexts sent between Alice and Bob and tries to guess the plaintexts. An asymmetric cryptosystem is considered CPA-secure if Eve's advantage in correctly guessing the plaintext in the following game is negligible:
Eve sends a message \( m \) to an oracle, which returns a ciphertext \( c \) that is either an encryption of \( m \) or a random message of the same length as \( m \). Eve then tries to guess what \( c \) is an encryption of.
Therefore, if an asymmetric cryptosystem is CPA-secure, the only information that a ciphertext reveals is the length of the encrypted message.
In a chosen ciphertext attack, Eve is active, making this a stronger attack compared to a chosen plaintext attack. Now, Eve can have ciphertexts decrypted by the oracle. An asymmetric cryptosystem is considered CCA-secure if Eve's advantage in correctly guessing the plaintext in the following game is negligible:
Eve sends a ciphertext \( c_{i} \) to an oracle, which returns the decrypted message \( m_{i} \) of \( c_{i} \). This can be repeated as many times as Eve wants. Then, Eve sends a message \( m \) to the oracle, which returns a ciphertext \( c \) that is either an encryption of \( m \) or a random message of the same length as \( m \). Finally, Eve sends a ciphertext \( c_{i}' \), which must be different from \( c \), to the oracle, and it returns the decrypted message \( m_{i}' \) of \( c_{i}' \). This can also be repeated as many times as Eve wants. Eve then tries to guess what \( c \) is an encryption of.
Again, if an asymmetric cryptosystem is CCA-secure, the only information that a ciphertext reveals is the length of the encrypted message.
The security of digital signatures, such as RSA and ElGamal, is measured with respect to a chosen plaintext attack (CPA).
In a chosen plaintext attack, Alice and Bob's adversary, Eve, is passive; she only observes the messages and signatures exchanged between Alice and Bob and tries to forge a signature. A digital signature scheme is considered CPA-secure if Eve's advantage in forging a signature in the following game is negligible:
Eve sends a message \( m_{i} \) to an oracle, which returns its signature \( \sigma_{i} \). This process can be repeated as many times as Eve wishes. Finally, Eve outputs a message \( m \), which must be different from all previously queried messages \( m_{i} \), along with a signature \( \sigma \). Eve wins the game if \( \sigma \) is a valid signature for the message \( m \).
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).
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 \).
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.
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 } \)
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.
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 \).
| Public parameters | |
| A trusted third party publishes a large prime number \( p \) and a generator \( g \) of the group \( \mathbb{Z}_{p}^{*} \). | |
| Key creation | |
| Alice: Chooses the secret key \( 1 \leq a \leq p-1 \) Computes \( A = g^{a} \: mod \: p \). | |
| Alice sends the public key \( pk = (p, g, A) \) to Bob. | |
| Encryption | |
| Bob: Chooses a unique random ephemeral key \( 1 \leq k \leq p-1 \). Uses Alice's public key \( pk = (p, g, A) \) and the ephemeral key \( k \) to compute the ciphertext \( (c_{1}, c_{2}) = E_{pk}(m) \) of the plaintext \( 1 \leq m \leq p-1 \), where \( c_{1} = g^{k} \: mod \: p \) and \( c_{2} = m \cdot A^{k} \: mod \: p \). | |
| Bob sends the ciphertext \( (c_{1},c_{2}) \) to Alice. | |
| Decryption | |
| Alice: Computes \( x = c_{1}^{a} \: mod \: p \) and its inverse \( x^{-1} \) using the extended Euclidean algorithm. Calculates the plaintext \( m' = D_{sk}(c_{1}, c_{2}) = x^{-1} \cdot c_{2} \: mod \: p \), where \( m' = m \). | |
Try a demo of the encryption scheme here.
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.
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.
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.
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, because otherwise 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).
| Public parameters | |
| A trusted third party publishes a large prime number \( p \) and a generator \( g \) of the group \( \mathbb{Z}_{p}^{*} \). | |
| Key creation | |
| Samantha: Chooses a secret signing key \( 1 \leq s \leq p-1 \). Computes the public verification key \( v = g^{s} \: mod \: p \). | |
| Samantha sends the public key \( pk = (p, g, v) \) to Victor. | |
| Signing | |
| Samantha: Chooses a unique random ephemeral key \( 1 \leq e \leq p-1 \). Computes the inverse \( e^{-1} \) of \( e \) using the extended Euclidean algorithm. Computes the fingerprint \( \mathcal{H}(m) \) of the message \( m \), where \( 1 \leq \mathcal{H}(m) \leq p-1 \). Uses the secret key \( sk = s \) and the ephemeral key to sign the fingerprint by 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) \). | |
| Samantha sends the signature \( (\sigma_{1}, \sigma_{2}) \) and the message \( m \) to Victor. | |
| Verification | |
| Victor: Computes the fingerprint \( \mathcal{H}(m) \) of the message \( m \). Uses Samantha's public key \( pk = (p, g, v) \) to verify the signature by checking that \( v^{\sigma_{1}} \cdot \sigma_{1}^{\sigma_{2}} \: mod \: p \) is equal to \( g^{\mathcal{H}(m)} \: mod \: p \). The signature is valid only if these two values are equal. | |
Try a demo of the signature scheme here.
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 modified version of the ElGamal signature scheme that allows for shorter signatures.
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 \).
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.
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} } \)
| Public parameters | |
| A trusted third party publishes two large prime numbers \( p \) and \( q \) such that \( p \: mod \: q = 1 \), and a generator \( g = g_{1}^{(p-1)/q} \: mod \: p \) of order \( q \) from the group \( \mathbb{Z}_{p}^{*} \) (where \( g_{1} \) is a generator of the group \( \mathbb{Z}_{p} \)). | |
| Key creation | |
| Samantha: Chooses the secret signing key \( 1 \leq s \leq q-1 \). Computes the public verification key \( v = g^{s} \: mod \: p \). | |
| Samantha sends the public key \( pk =(p,q,g,v) \) to Victor. | |
| Signing | |
| Samantha: Computes the fingerprint \( \mathcal{H}(m) \) of the message \( m \), where \( 1 \leq \mathcal{H}(m) \leq q-1 \). Chooses a unique random ephemeral key \( 1 \leq e \leq q-1 \). Uses the secret key \( sk = s \) and the ephemeral key to sign the fingerprint by computing \( (\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 \) (\( \| \) denotes concatenation). | |
| Samantha sends the signature \( (\sigma_{1},\sigma_{2}) \) and the message \( m \) to Victor. | |
| Verification | |
| Victor: Computes the fingerprint \( \mathcal{H}(m) \) of the message \( m \). Uses Samantha's public key \( pk = (p, q, g, v) \) to verify the signature by checking that \( \mathcal{H}(\mathcal{H}(m) \: \| \: g^{\sigma_{2}} \cdot v^{-\sigma_{1} \: mod \: q} \: mod \: p) = \sigma_{1} \), where \( \| \) denotes concatenation. The signature is valid only if this equality holds. | |
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.
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 \).
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.
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 \).
| Public parameters | |
| A trusted third party publishes two large prime numbers \( p \) and \( q \) such that \( p \: mod \: q = 1 \), and a generator \( g = g_{1}^{(p-1)/q} \: mod \: p \) of order \( q \) from the group \( \mathbb{Z}_{p}^{*} \) (where \( g_{1} \) is a generator of the group \( \mathbb{Z}_{p} \)). | |
| Key creation | |
| Samantha: Chooses a secret signing key \( 1 \leq s \leq q-1 \). Computes the public verification key \( v = g^{s} \: mod \: p \). | |
| Samantha sends the public verification key \( pk =(p,q,g,v) \) to Victor. | |
| Signing | |
| Samantha: Computes the fingerprint \( \mathcal{H}(m) \) of the message \( m \) using the SHA-1 hash function, where \( 1 \leq \mathcal{H}(m) \leq q-1 \). Chooses a unique random ephemeral key \( 1 \leq e \leq q-1 \). Computes the inverse \( e^{-1} \) of \( e \) using the extended Euclidean algorithm. Uses the secret key \( sk = s \) and the ephemeral key to sign the fingerprint by computing \( (\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 | |
| Victor: Computes the fingerprint \( \mathcal{H}(m) \) of the message \( m \). Computes the inverse \( \sigma_{2}^{-1} \) of \( \sigma_{2} \) using the extended Euclidean algorithm. Calculates \( V_{1} = \mathcal{H}(m) \cdot \sigma_{2}^{-1} \: mod \: q \) and \( V_{2} = \sigma_{1} \cdot \sigma_{2}^{-1} \: mod \: q \). Verifies that \( (g^{V_{1}} \cdot v^{V_{2}} \: mod \: p) \: mod \: q = \sigma_{1} \). | |
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 \).