In cryptography we often encrypt and sign messages that contains characters, but asymmetric key cryptosystems (Alice and Bob uses different keys) such as RSA and ElGamal are based on arithmetic operations on integer. And symmetric key cryptosystems (Alice and Bob uses the same key) such as DES and AES are based on bitwise operations on bits (a bit is either equal 0 or 1 and is an abbreviation for binary digit). Therefore, we have to convert the characters into integers or bits before we apply the cryptosystem to the message.
Because a computer can only handle bits, there already exists a method for converting characters into integers or bits, that uses the ASCII (American Standard Code for Information Interchange) table. A part of the ASCII table from Wikipedia is listed in the following table (notice that the binary representation on the Wikipedia site is only seven bits but we use eight bits, i.e. we have prepended 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 \) |
E.g. if Alice wants to send the message "Hey Bob!" encrypted to Bob with 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 } \)
I.e. 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 says how many times to multiply the number by it self. Ex:
\( 4^{3} = 4 \cdot 4 \cdot 4 = 64 \)
where 3 is the exponent (or power) and 4 is the base. In words we say 4 to the power 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 the clock and e.g. needs to figure out what time it's 3 hours after 11 o'clock, which is 2 o'clock. In math we write that as:
\( (11 + 3) \: mod \: 12 = 2 \)
where 12 is the modulus because we want the time as an integer between 0 and 11 (12 o'clock is in this case denoted by 0). In words we say 11 plus 3 modulo 12 is equal 2. The result of a modulo computation is an integer between 0 and the modulus minus 1. E.g. with the modulus 3 we have that:
If we e.g. look at \( 27 \: mod \: 5 \) then modulo computes the number of times 5 divides 27 and then returns the remainder of the result which is 2 in this case, i.e. \( 27 \: mod \: 5 = 2 \). But how did we get this result?
First we compute the number of times it's possible to multiply 5 with the number \( x \) such that we get an integer as close as possible to 27 without exceeding it, i.e. we have to find the maximun value of \( x \) such that \( 5 \cdot x \leq 27 \). In this case we have that \( x = 5 \) because \( 5 \cdot 5 = 25 \leq 27 \). Then by subtracting 27 with 25 we get the answer \( 27 - 25 = 2\).
If the integer is negative e.g. \( -27 \: mod \: 5 \) we have to do it slightly different and the answer is \( -27 \: mod \: 5 = 3 \). In this case the integer \( x \) is negative and should be the closest integer that exceed -27, i.e. we have to find the minimum value of \( -x \) such that \( 5 \cdot -x \geq -27 \). Now we have that \( -x = -6 \) because \( 5 \cdot -6 = -30 \geq -27 \). Then by subtracting -27 with -30 we get the answer \( -27 - (-30) = -27 + 30 = 3\).
It's important that \( x \) or \( -x \) is an integer such as \( -14, 3, 17 \) etc. and NOT a fraction or float such as \( \frac{1}{4}, \frac{-3}{7}, 2.5, 5.1 \) etc.
If two integers \( a \) and \( b \) modulo the same modulus \( c \) returns the same remainder \( r \), then we say that \( a \) and \( b \) are congruent modulo \( c \). I.e. 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 equal \( a \: mod \: c = a \).
A prime number is an integer greater than 1, which only can be divided evenly by 1 and itself. Divided evenly means that the result must not be a float. E.g. if you try to divide 13 with 3 it returns the float \( \frac{13}{3} = 4.333 \). We have that 13 is a prime number because it can only be divided evenly by 1 and itself, i.e. \( \frac{13}{1} = 13 \) and \( \frac{13}{13} = 1 \).
If an integer is not a prime number it's called a composite number. E.g. 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, an integer is either a prime number or a product of prime numbers (a composite number).
The famous Greek mathematician Euclid proved that there are infinite many prime numbers.
Michael Rabin and Gary Miller have developed an algorithm that decides whether an integer is a prime or 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 are, we first define what we mean by a divisor. In this context is a divisor of an integer \( x \) some integer that divides \( x \) evenly, i.e. the result must not be a float. E.g. if you try to divide \( x=12 \) with 5 it returns the float \( \frac{12}{5} = 2.4 \) and 5 is therefore not a divisor of \( x=12 \). For \( x=12 \) we have the divisors 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 \).
Likewise the divisors of 16 is 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 of the common divisors. In math we write that as \( \gcd(12, 16) = 4 \).
Two integers with greatest common divisor 1 are called relatively prime numbers or co-primes. E.g. 15 and 28 are relatively prime numbers because \( \gcd(15, 28) = 1 \) (notice 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 an integer (either a prime number or a composite number) 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 integer.
The extended Euclidean algorithm is an extended version 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) \)
where \( \lambda \) and \( \mu \) are called the Bézout coefficients for \( a \) and \( b \). Only if \( a \) and \( b \) are relatively prime numbers, i.e. \( \gcd(a, b) = 1 \), then:
\( a \cdot \lambda + b \cdot \mu = 1 \)
and \( \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 e.g. \( a=5 \) and \( b=39 \) with a simple table. So, let us first create a table with 3 columns (we do not yet know how many rows there will be in the table). Let us denote the entry in the first row and first column for [1,1], the entry in the first row and second column for [1,2], the entry in the second row and first column for [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 biggest integer \( q_{1} \), such that \( q_{1} \cdot a \leq b \). We have that \( 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 biggest integer \( q_{2} \), such that \( q_{2} \cdot r_{1} \leq a \). We have that \( q_{2}=1 \), which we write in entry [3,2], because \( 1 \cdot 4 = 4 \leq 5 \) and a remainder of \( r_{2}=1 \) that we write in entry [4,1]. Notice that we just computed the same as before, just with integers in a lower 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 \). And because 5 and 39 are relatively prime numbers, we know that \( \lambda \) and \( \mu \) exists and we can then 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 the same as before, just with integers 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 that \( 5 \cdot 8 - 39 \cdot 1 = 1 \) (which is the same as \( 5 \cdot 8 + 39 \cdot (-1) = 1 \)) and 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 a ring of integers or a group. The group of integers modulo \( n \) is a subset of \( \mathbb{Z} \) and is denoted by the symbol \( \mathbb{Z}/n\mathbb{Z} \), but we use the shorthand version \( \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 make an addition or multiplication in \( \mathbb{Z}_{n} \), we always compute the addition or multiplication modulo \( n \) to obtain an integer in \( \mathbb{Z}_{n} \). To illustrate this we look at \( n = 5 \):
\( \mathbb{Z}_{5} = \{ 0, 1, 2, 3, 4 \}\)
When adding \( 3 \) with \( 4 \) in \( \mathbb{Z}_{5} \) we do the following: \( (3 + 4) \: mod \: 5 = 7 \: mod \: 5 = 2 \). Likewise, when multiplying \( 3 \) with \( 4 \) in \( \mathbb{Z}_{5} \) we do the following: \( (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 an unit. The set of units (all integers with an inverse in \( \mathbb{Z}_{n} \)) is denoted by the symbol \( (\mathbb{Z}/n\mathbb{Z})^{*} \). Again, we will use the shorthand version \( \mathbb{Z}_{n}^{*} \). If \( a_{1} \) and \( a_{2} \) are units then is the multiplication \( (a_{1} \cdot a_{2}) \: mod \: n \) also always an unit (i.e. \( a_{1} \cdot a_{2} \) is in the group \( \mathbb{Z}_{n}^{*} \)), but the addition \( (a_{1} + a_{2}) \: mod \: n \) may NOT be an unit (i.e. \( a_{1} + a_{2} \) is in the group \( \mathbb{Z}_{n} \) but may not be in the group \( \mathbb{Z}_{n}^{*} \)). We see the difference in the two sets \( \mathbb{Z}_{8} \) and \( \mathbb{Z}_{8}^{*} \):
If we chose \( n \) to be a prime number \( p \) then for all integers \( a \) excluding 0 in \( \mathbb{Z}_{p} \) we have that \( \gcd(a, p) = 1 \), which result in that \( \mathbb{Z}_{p}^{*} \) contains all integers from \( \mathbb{Z}_{p} \) excluding 0, i.e.:
\( \mathbb{Z}_{p}^{*} = \{ 1, 2, 3, \dots, p - 1 \}\)
E.g. for \( p=7 \) we see that the only difference in 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 the symbol \( \phi(n) \) after a famous Swiss mathematician called Euler and is called Euler's phi function. As we saw previously, then 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 we e.g. chose 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 e.g. modulo \( p-1 \) instead of modulo \( p \), then it's 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 we could have chosen any group.
There exist 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 gives every elements in the set of units \( \mathbb{Z}_{p}^{*} \), i.e. 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 make it clear we look at an example with the prime number 5. We remember 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 generates every elements 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 generates 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 make the above computation, i.e. check that it generates every element in the group \( \mathbb{Z}_{p}^{*} \). Otherwise, if you know the factorization of the integer \( p-1 \), then for every prime number \( q \) that evenly divides the integer \( 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 factorication 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 on 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 \). E.g. 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 divides \( p-1=11-1=10 \) evenly. For the same reason is \( g = 5 \) 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 minimum one generator.
Let \( g \) be a generator of the group \( G \). Given the values \( g \) and \( H \), the discrete logarithm (DL) problem is about computing the exponent \( a \) in the following equation, which is a hard problem:
\( g^{a} = H \)
The exponent \( a \) is also called the discrete logarithm of \( H \) to the base \( g \).
E.g. if we use the group \( \mathbb{Z}_{p}^{*} \) where \( p \) is a large prime number and \( g \) is a generator of the group, then if you are given \( g \), \( p \) and \( H \) it's a hard to compute \( a \), such that it satisfies the following equation:
\( g^{a} \: mod \: p = H \)
Besides the DL problem we have two similar 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 about computing the exponent \( a \cdot b \) in \( g^{a \cdot b} \).
Similar, given the values \( g \), \( g^{a} \), \( g^{b} \) and \( g^{c} \) the DDH problem is about deciding whether \( c = a \cdot b \) or \( c \) is a random integer.
You may have noticed that if we can solve the DL problem, i.e. computing \( a \) in \( g^{a} = H \), then we also can solve the DH problem: first we compute \( a \) in \( g^{a} \), then \( b \) in \( g^{b} \) and finally \( a \cdot b \). Now this also implies that we can solve the DDH problem: first we compute \( a \cdot b \) as described above, then \( c \) in \( g^{c} \) and finally we check whether \( c = a \cdot b \).
Security of an asymmetric key (public-key) cryptosystem such as RSA and ElGamal is measured with respect to a chosen plaintext attack (CPA) and a chosen ciphertext attack (CCA).
In a chosen plaintext attack (sometimes called a semantic attack) is Alice and Bob's adversary Eve passive, i.e. she only observe the sent ciphertexts between Alice and Bob and tries to guess the plaintexts. We say that an asymmetric cryptosystem is CPA-secure if Eve's advantage in guessing correct in the following game is negligible:
Eve sends a message \( m \) to an oracle and it returns a ciphertext \( c \) where \( c \) is either an encryption of \( m \) or a random message with the same length as \( m \). Eve then tries to guess what \( c \) is an encryption of.
Hence, if a asymmetric cryptosystem is CPA-secure, the only information that a ciphertext leaks is the length of the encrypted message.
In a chosen ciphertext attack is Eve active and it's therefore a stronger attack compared to a chosen plaintext attack. Now Eve can get a ciphertext decrypted by the oracle and we say that an asymmetric cryptosystem is CCA-secure if Eve's advantage in guessing correct in the following game is negligible:
Eve sends a ciphertext \( c_{i} \) to an oracle and it returns the decrypted message \( m_{i} \) of \( c_{i} \). This is repeated as many times as Eve wants. Then Eve sends a message \( m \) to the oracle and it returns a ciphertext \( c \) where \( c \) is either an encryption of \( m \) or a random message with the same length as \( m \). Finally Eve sends a ciphertext \( c_{i}' \), that has to be different from \( c \), to the oracle and it returns the decrypted message \( m_{i}' \) of \( c_{i}' \). This is repeated as many times as Eve wants. Eve then tries to guess what \( c \) is an encryption of.
Again, if a asymmetric cryptosystem is CCA-secure, the only information that a ciphertext leaks is the length of the encrypted message.
Security of a digital signature such as RSA and ElGamal is measured with respect to a chosen plaintext attack (CPA).
In a chosen plaintext attack is Alice and Bob's adversary Eve passive, i.e. she only observe the sent messages and signatures between Alice and Bob and tries to forge a signature. We say that a digital signature is 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 and it returns its signautre \( \sigma_{i} \). This is repeated as many times as Eve wants. Finally Eve outputs a message \( m \), which has to be different from the messages \( m_{i} \), and its signature \( \sigma \). Eve wins the game if \( \sigma \) is a valid signature of the message \( m \).
The ElGamal cryptosystem was first described by Taher Elgamal in 1985 and is closely related to the Diffie-Hellman key exchange. The Diffie-Hellman key exchange provides a method of sharing a secret key between Alice and Bob, but does not allow Alice and Bob to otherwise communicate securely.
ElGamal is a public key cryptosystem based on the discrete logarithm problem for a group \( G \), i.e. every person has a key pair \( (sk, pk) \), where \( sk \) is the secret key and \( pk \) is the public key, and given only the public key one has to find the discrete logarithm (solve the discrete logarithm problem) to get the secret key. The cryptosystem is both an encryption scheme (this section) which helps Alice and Bob with the problem of exchanging sensitive information over an insecure channel eavesdropped by their adversary Eve and a digital signature scheme (the next section) which helps them with creating digital signatures. The signature scheme is slightly different from the encryption scheme and various digital signature schemes such as the Schnorr signature scheme and the Digital Signature Algorithm (DSA) are based on ElGamal's signature scheme but with shorter keys.
The group used in ElGamal could either 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 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 publish 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 where he would like to hide the content of the message for 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 one message \( m \), and only one message. I.e. after he has used \( k \) to encrypt one message he discards it and chooses a new one. Bob encrypts \( m \) by using the encryption algorithm \( E \) with the public key \( pk = (p, g, A) \) by \( (c_{1}, c_{2}) = E_{pk}(m) \) where \( c_{1} = g^{k} \: mod \: p \) and \( c_{2} = m \cdot A^{k} \: mod \: p \). The 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 the inverse \( x^{-1} \) of \( x \) with 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 decrypt the received ciphertext with the decryption algorithm \( D \) and the 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 Eve sends a message to another person and receives a ciphertext she shouldn't be able to tell whether it's an encryption of the message or some random letters (this is also the definition of CPA-secure cryptosystem).
In the following we will without proof use a theorem saying that, if Eve can tell 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 tell whether a ciphertext is an encryption of a meaningful message or some random letters. I.e. if the DDH problem is easy for the used group is ElGamal not CPA-secure (in other words: if the DDH problem is hard in the used group is ElGamal CPA-secure).
First we need some definitions: We say that \( y \) is a quadratic residue modulo a prime number \( p \), written \( 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 \)). Otherwise is \( y \) a non-quadratic residue modulo \( p \), written \( y \in NQR(p) \). E.g. for 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 tell 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 exclusive 0). Notice that half of the numbers of \( 1, 2, \dots, p-1 \) are quadratic residues modulo \( p \) and the other half are quadratic non-residues modulo \( p \).
A famous Swiss mathematician 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 is the exponent \(i\) an even number. Otherwise is \(i\) an odd number.
Finally we will define \( LSB(g^{i}) \) as the value of the least significant bit of \( i \) (after we have converted it into a binary number) 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 how Eve can tell whether a ciphertext is an encryption a meaningful message or some random letters (remember that we only have to prove that she can tell whether the exponent \( a \cdot k\) is an even or odd number). Suppose that a trusted third party has chosen the prime number \( p = 7\) and the generator \( g = 3 \) of the group \( \mathbb{Z}_{7}^{*} \). We also 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 \) where for \( c_{2} = m \cdot A^{k} \: mod \: p \) we have that:
\( \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 value 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 know 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 wether a ciphertext is an encryption of a meaningful message or some random letters.
The reason why Eve can tell wether 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 try 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 according to pointwise multiplication, i.e. \( (a,b) \cdot (c,d) = (a \cdot c, b \cdot d) \), because:
\( \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) } \)
i.e. pointwise multiplication of two ciphertexts is the same as multiplying the two corresponding plaintexts. ElGamal is partially homomorphic and not fully homomorphic because it's only multiplication that have this property (and not addition).
This property is both an advantage and a disadvantage of the cryptosystem: It's an advantage when e.g. Alice have some private data \( m \) she wants a cloud service to make some computations on. She first computes \( (c_{1}, c_{2}) = E_{pk}(m) \) and then sends the ciphertext \( (c_{1}, c_{2}) \) to the could service. The cloud service then make some computations on Alice's data by \( (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 her ciphertext, which returns the data \( m \cdot m' \: mod \: p \). On the other hand, it's a disadvantage when e.g. Eve intercept 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 sends to Bob. When Bob decrypts the ciphertext he get the plaintext \( m \cdot m' \: mod \: p \) instead of the plaintext \( m \).
| Public parameters | |
| A trusted third party publish 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 an 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} \) with the extended Euclidean algorithm. Computes 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 is 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 publish 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 \) with 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 decrypt 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 person, Samantha and Victor, uses a digital signature when one of them, say Samantha, needs to send a digital signed piece of data, a document or message, to Victor and it's important that Victor know that it's from Samantha. The case could e.g. be that Samantha wants to send some money to her friend Carla through her bank where Victor work. Before Victor withdraw the money from Samantha's account, he needs to verify that the request of the transfer is from Samantha and not another person. If the signature scheme is insecure it would be possible for Samantha's adversary Eve to forge a signature on a message saying that Samantha wants to send some money to Eve and Victor will 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 where she sends the public key to Victor.
To sign a message \( m \) Samantha first computes the fingerprint \( \mathcal{H}(m) \) of the message with a public known hash function \( \mathcal{H} \) such that \( 1 \leq \mathcal{H}(m) \leq p-1 \). One property of the hash function is that given the same input, the hash function always return the same output. Another property is that the length (or size) of the input can be arbitrary long, but the output will have a fixed length. So, no matter how large the message Samantha wants to sign, the signing algorithm will be equally efficient because Samantha signs the fingerprint \( \mathcal{H}(m) \) instead of the message \( m \).
Before Samantha can sign the fingerprint \( \mathcal{H}(m) \) she needs a random number \( e \) (an ephemeral key) between \(1 \) and \( p-1 \) satisfying \( \gcd(e, p-1) = 1 \) because she also needs the inverse \( e^{-1} \) of \( e \). She computes \( e^{-1} \) with the extended Euclidean algorithm which give her the equation \( e \cdot \lambda + (p-1) \cdot \mu = \gcd(e, p) \) 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 by using the signing algorithm \( S \) with the secret signing key \( sk = s \) by \( (\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 use the same hash function \( \mathcal{H} \) as Samantha to compute the fingerprint \( \mathcal{H}(m) \) of the message \( m \). He then verify 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's equal to \( V_{2} = g^{\mathcal{H}(m)} \: mod \: p \). Only if \( V_{1} = V_{2} \) is the signature valid 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 know 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 \), she will be able to sign document 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 because otherwise could Eve 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 Euclidena 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 last 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 \) is 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 it's now required by Eve to find a preimage of the hash function which is hard. I.e. think of \( -\sigma_{1} \cdot z \cdot w^{-1} \) (the values of the message in the above attack) as a fingerprint, now Eve has to find the 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) \)-bit since \( \sigma_{1} \) is \( \log_{2}(p) \)-bit and \( \sigma_{2} \) is \( \log_{2}(p-1) \)-bit (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 \) has to be at least \( 2048 \)-bit with today's standard which implies that the ElGamal signature \( (\sigma_{1}, \sigma_{2}) \) is at least \( 4096 \)-bit.
In the following we present some variants of the ElGamal signature that uses shorter signatures: The Schnorr signature and the Digital Signature Algorithm (DSA) both uses a subgroup of order \( q \) (more about this later) where \( q \) is a prime number chosen to be between \( 160 \)- and \( 230 \)-bit. And hence, the Schnorr and DSA signature \( (\sigma_{1}', \sigma_{2}') \) are between \( 320 \)- and \( 460 \)-bit (because both \( \sigma_{1}' \) and \( \sigma_{2}' \) are computed modulo \( q \) and the signature is then approximately \( 2 \cdot \log_{2}(q) \)-bit).
| Public parameters | |
| A trusted third party publish a large prime number \( p \) and a generator \( g \) of the group \( \mathbb{Z}_{p}^{*} \). | |
| Key creation | |
| Samantha: Chooses the 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 an unique random ephemeral key \( 1 \leq e \leq p-1 \). Computes the inverse \( e^{-1} \) of \( e \) with 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 \). | |
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 publish the public key \( pk = (p, g, v) = (379, 360, 202) \).
The message Samantha wants to sign is \( m = \mbox{"Transfer 100 USD to Carla"} \) which she computes the fingerprint of \( \mathcal{H}(m) = 273 \) with a public known hash function \( \mathcal{H} \). She then chooses the ephemeral key (an unique random number) \( e = 187 \) such that \( \gcd(e, p-1) = \gcd(187, 379-1) = 1 \) and computes the inverse \( e^{-1} \) of \( e \) with the extended Euclidean algorithm. The extended Euclidean algorithm gives her the equation \( \gcd(e, p-1) = e \cdot \lambda + p \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 together with the message \( m \).
Victor verifies the signature by first computing the fingerprint \( \mathcal{H}(m) = 273 \) of the message with 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 which allows shorter signature.
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 publish 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 have to compute the discrete logarithm of \( v \) to get the secret key \( s \) .
Samantha wants to sign a large message \( m \), therefore she first computes the fingerprint \( \mathcal{H}(m) \) of the message \( m \) with a public known hash function \( \mathcal{H} \) and then she sign the fingerprint instead of the message. One property of a hash function is that the length of the input can be arbitrary long, but the size of the output 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 an unique random number \( e \) (an ephemeral key which is only used once for every 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} \). Only if \( S = \sigma_{1} \) is the signature valid 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 publish two large prime numbers \( p \) and \( q \) satisfying \( 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 an 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 \) (\( \| \) is the concatenation operator). | |
| 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 that \( \mathcal{H}(\mathcal{H}(m) \: \| \: g^{\sigma_{2}} \cdot v^{-\sigma_{1} \: mod \: q} \: mod \: p) = \sigma_{1} \) where \( \| \) means concatenation. | |
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 publish 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"} \) that she computes the fingerprint of with the hash function \( \mathcal{H} \): \( \mathcal{H}(m) = 189 \). She then chooses an ephemeral key (an 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 work in the bank.
Victor verifies the signature by first computing the fingerprint \( \mathcal{H}(m) = 189 \) of the message with 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 a DSS (Digital Signature Standard) in 1994, is a modified version of the Schnorr signature and the ElGamal signature which allows shorter signature compared to the ElGamal signature.
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 \) and computes the public verification key \( v = g^{s} \: mod \: p \). Samantha publish her public key \( pk = (p, q, g, v) \) and store her secret key \( sk = s\). Notice that both Victor and their adversary Eve can see the public key, but they have to compute the discrete logarithm of \( v \) to get the secret key \( s \).
Instead of signing the message \( m \) itself, Samantha signs its fingerprint \( \mathcal{H}(m) \) computed with a public known hash function \( \mathcal{H} \). In DSA is the used hash function SHA-1 where \( 1 \leq \mathcal{H}(m) \leq q-1 \). One property of a hash function is that the length of the input can be arbitrary long, but the size of the output has a fixed length.
Samantha chooses an unique random number \( e \) (an ephemeral key which is only used once for every signature) such that \( 1 \leq e \leq q-1 \) and \( \gcd(e, q) = 1 \) because she also need 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 with 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 use the SHA-1 hash function \( \mathcal{H} \) as Samantha to compute the fingerprint \( \mathcal{H}(m) \) of the message \( m \). He then computes the inverse \( \sigma_{2}^{-1} \) of \( \sigma_{2} \) with 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} \). Only if \( S = \sigma_{1} \) is the signature valid 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 clear that \( e \cdot \sigma_{2} \: mod \: q = \mathcal{H}(m) + s \cdot \sigma_{1} \: mod \: q \), but as we see then:
\( \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's important that the value \( e \) is only used once for every signature, is because it would otherwise be easy for Eve to compute Samantha's secret key \( s \). The second part of the signature, i.e. \( \sigma_{2} = (\mathcal{H}(m) + s \cdot \sigma_{1}) \cdot e^{-1} \: mod \: q \), can be rewritten to \( s = (\sigma_{2} \cdot e - \mathcal{H}(m)) \cdot \sigma_{1}^{-1} \: mod \: q \). And hence, knowing the value \( e \) allows Eve to easily recover the private key \( s \). Assume that Samantha has signed two different messages \( m \) and \( m' \) with the same \( e \), i.e. she has computed the 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 computing:
\( \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 } \)
and then by rearranging the equation \( \sigma_{2} - \sigma_{2}' = (\mathcal{H}(m) - \mathcal{H}(m')) \cdot e^{-1} \: mod \: q \) she have that \( e = (\mathcal{H}(m) - \mathcal{H}(m')) \cdot (\sigma_{2} - \sigma_{2}')^{-1} \: mod \: q \).
| Public parameters | |
| A trusted third party publish two large prime numbers \( p \) and \( q \) satisfying \( 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 verification key \( pk =(p,q,g,v) \) to Victor. | |
| Signing | |
| Samantha: Computes the fingerprint \( \mathcal{H}(m) \) of the message \( m \) with the SHA-1 hash function where \( 1 \leq \mathcal{H}(m) \leq q-1 \). Chooses an unique random ephemeral key \( 1 \leq e \leq q-1 \). Computes the inverse \( e^{-1} \) of \( e \) with 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} \) with the extended Euclidean algorithm. Computes \( 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} \) and computes the generator \( g = g_{1}^{(p-1)/q} \: mod \: p = 383^{(467-1)/233} \: mod \: 467 = 51 \) of order \( q = 233 \). 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 publish 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"} \) which she computes the fingerprint of with the SHA-1 hash function \( \mathcal{H} \): \( \mathcal{H}(m) = 84 \). She then chooses an ephemeral key (an unique random number) \( e = 83 \) such that \( \gcd(e, q) = \gcd(83, 233) = 1 \) and the inverse \( e^{-1} \) of \( e \) with 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 work in the bank.
Victor verifies the signature by first computing the fingerprint \( \mathcal{H}(m) = 84 \) of the message as Samantha with 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 \).