Elgamal encryption method

Taher Elgamal (2010), inventor of the process

The Elgamal encryption method or Elgamal cryptosystem (also al-Jamal cryptosystem ) is a public key encryption method developed in 1985 by the cryptologist Taher Elgamal , which is based on the idea of ​​the Diffie-Hellman key exchange . The Elgamal encryption method, like the Diffie-Hellman protocol, is based on operations in a cyclic group of finite order. The Elgamal encryption method is provably IND-CPA -safe under the assumption that the Decisional Diffie Hellman problem is difficult in the underlying group.

The Elgamal signature process is related to the encryption process described here (but not identical to it) . Elgamal is not subject to any patent .

description

Like all asymmetric cryptosystems , the Elgamal cryptosystem also uses a public and a secret key . The public key is used for encryption and can be published, while the secret key is used for decryption and may only be known to the recipients of the message. This means that the recipient of the message must generate a key pair from public and private keys once. Then anyone can use the public key to encrypt a message as often as they want and send it to the recipient. In the following description it is assumed, as in cryptography, that a sender wants to send a message to a recipient.

Parameter generation

The receiver chooses a finite , cyclic group with primary order and producer so that it is large enough to provide the desired security. will be published. ${\displaystyle \mathbb {G} =\langle g\rangle }$ ${\displaystyle q}$ ${\displaystyle g}$ ${\displaystyle q}$ ${\displaystyle \mathbb {G} }$

In the following , as is usual in cryptography, multiplicative is written, i.e. H. the group operation is represented by a painting point instead of a plus, as is common in much of mathematics, and the multiple applications of the same are represented as an exponent rather than a factor. In principle, the exponent is an integer, however, in the case under consideration, exponents that are integer multiples of are irrelevant for the result, which is why it is alternatively legitimate to regard exponents as elements of the remainder class field . The exponent 0 that this makes possible leads to the fact that the encryption contains the unchanged plain text, but only occurs with a negligible probability and therefore does not cause any problems if the exponents are chosen really randomly. ${\displaystyle \mathbb {G} }$ ${\displaystyle q}$ ${\displaystyle \mathbb {Z} _{q}}$

It is possible for several parties to use the same group, in some applications the group used is even standardized.

Key generation

1. The recipient chooses an exponent at random . This is the recipient's private key. ${\displaystyle a\leftarrow \mathbb {Z} _{q}}$
2. The recipient calculates the group element as his public key and makes it known. ${\displaystyle \left[g^{a}\right]\in \mathbb {G} }$

Encryption

1. The sender wants to send the message . ${\displaystyle m\in \mathbb {G} }$
2. The sender randomly chooses an exponent . ${\displaystyle r\leftarrow \mathbb {Z} _{q}}$
3. The sender calculates the group element . ${\displaystyle c_{0}=g^{r}\in \mathbb {G} }$
4. The sender calculates the cipher . (Note: the sender knows the recipient's public key .) ${\displaystyle c_{1}=\left[g^{a}\right]^{r}\cdot m\in \mathbb {G} }$ ${\displaystyle \left[g^{a}\right]}$
5. The sender sends to the recipient. ${\displaystyle (c_{0},c_{1})}$

Decryption

1. The recipient calculates the plain text as . (Please note: is the recipient's private key and only known to him.) ${\displaystyle m}$ ${\displaystyle c_{0}^{-a}\cdot c_{1}=\left[g^{r}\right]^{-a}\cdot \left[g^{ar}\cdot m\right]=g^{-ra+ar}\cdot m=g^{0}\cdot m=1\cdot m=m}$ ${\displaystyle a}$

Group selection

Two variants have prevailed as a choice for the finite, cyclic group : subgroups of multiplicative residual class groups and of elliptic curves over finite fields. ${\displaystyle \mathbb {G} }$

The first variant is classic: For prime there is a field (more precisely: remainder class field ) and the elements of the unit group (ie the “multiplicative” group of the same) are all numbers not equal to zero, concrete . The order of the group is therefore . Since is prime, it is divisible by two and the unit group is therefore not of prime order for any group. Now let be a divisor of , then the unit group has a subgroup with order . If it is a prime number, this subgroup is therefore prime and is potentially suitable for use. In practice it has become established to choose that which is suitable. is then referred to as a certain prime number , a Sophie-Germain prime number . In this case, the subgroup is then the subgroup of the square remainders, for which it applies that each element can be written as having another element . ${\displaystyle p}$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle G=\lbrace 1,\dots ,p-1\rbrace }$ ${\displaystyle p-1}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle p>3}$ ${\displaystyle q}$ ${\displaystyle p-1}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\textstyle {\frac {p-1}{2}}=q}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle g}$ ${\displaystyle h^{2}}$ ${\displaystyle h}$

Similar problems also apply to the use of elliptic curves over finite fields: These too do not initially have a prime order, so that a suitable generator of a subgroup of prime order must first be found here as well.

The specific problems that imply the use of a group with a non-primary order are dealt with in more detail in the section Problems with subgroups and are independent of the specific group used.

Regardless of the security, the choice of the group is also important in other ways: Only elements of the (sub) group used can be encrypted and decrypted, as the cipher would otherwise reveal information about the plaintext even without knowledge of the private (and even the public) key would. The consequence of this is that it is usually necessary to convert plaintexts to elements of the subgroup beforehand, which is not always trivial. Probably the simplest case arises when using the remainder class of a safe prime number : For all integers between (inclusive) and (exclusive), either or part of the subgroup is of prime order, so that the functioning element can simply be used. ${\displaystyle p=2q+1}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle p-n}$

A concrete example

The subgroup of squares of ${\displaystyle \mathbb {G} }$ ${\displaystyle \mathbb {Z} _{23}^{\times }}$

${\displaystyle \times }$	1	2	3	4th	6th	8th	9	12	13	16	18th
1	1	2	3	4th	6th	8th	9	12	13	16	18th
2	2	4th	6th	8th	12	16	18th	1	3	9	13
3	3	6th	9	12	18th	1	4th	13	16	2	8th
4th	4th	8th	12	16	1	9	13	2	6th	18th	3
6th	6th	12	18th	1	13	2	8th	3	9	4th	16
8th	8th	16	1	9	2	18th	3	4th	12	13	6th
9	9	18th	4th	13	8th	3	12	16	2	6th	1
12	12	1	13	2	3	4th	16	6th	18th	8th	9
13	13	3	16	6th	9	12	2	18th	8th	1	4th
16	16	9	2	18th	4th	13	6th	8th	1	3	12
18th	18th	13	8th	3	16	6th	1	9	4th	12	2

The powers of the elements in ${\displaystyle \mathbb {G} }$

${\displaystyle g^{x}}$	0	1	2	3	4th	5	6th	7th	8th	9	10
1	1	1	1	1	1	1	1	1	1	1	1
2	1	2	4th	8th	16	9	18th	13	3	6th	12
3	1	3	9	4th	12	13	16	2	6th	18th	8th
4th	1	4th	16	18th	3	12	2	8th	9	13	6th
6th	1	6th	13	9	8th	2	12	3	18th	16	4th
8th	1	8th	18th	6th	2	16	13	12	4th	9	3
9	1	9	12	16	6th	8th	3	4th	13	2	18th
12	1	12	6th	3	13	18th	9	16	8th	4th	2
13	1	13	8th	12	18th	4th	6th	9	2	3	16
16	1	16	3	2	9	6th	4th	18th	12	8th	13
18th	1	18th	2	13	4th	3	8th	6th	16	12	9

As a group, we choose the subgroup of squares from with as the generator, so that applies . Since 23 is a sure prime number, there is only one "large" subset that contains 11 elements; this is the so-called "subgroup of square remnants" or more simply the "subgroup of squares". The name has its origins in the fact that this group contains exactly those elements that can be written as the square of another element. This is always exactly half of all group elements, so that this subgroup has the prime order if and only if the modulus is a sure prime number, which is the case in our example according to the construction. ${\displaystyle G=\mathbb {Z} _{23}^{\times }}$ ${\displaystyle g=2}$ ${\displaystyle \langle g\rangle =\mathbb {G} \subset G}$

There is is a quadratic remainder and therefore part of the subgroup. Since all elements except the neutral element (here: “ ”) in groups of prime order apply that they create the entire group, it has prime order itself and is therefore a suitable generator. ${\displaystyle 5\cdot 5\equiv 2{\pmod {23}}}$ ${\displaystyle 2}$ ${\displaystyle 1}$ ${\displaystyle 2}$

The calculation with elements from clearly runs almost exactly like the calculation with whole numbers, only that after each operation the calculation is always modulo 23 (see first table). However, it is important to understand that it only contains 11 elements and not 22 or 23. ${\displaystyle \mathbb {Z} _{23}^{\times }}$ ${\displaystyle \mathbb {G} }$

The calculation of powers works in the same way as normal power calculations, for example . From the finite size of the group alone, however, it already follows that elements must repeat themselves from a certain point. Since, in the primary order groups considered here, each element except 1 (which only generates itself) is a producer of the entire group, the cycle includes all elements and has a length . Thus, since for all group elements rule, and thus for all exponents is considered that it is sufficient to calculate any powers the power to the exponent modulo expected. So For example: . (See the second table for the powers of all elements of .) ${\displaystyle g^{3}=g\cdot g\cdot g}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle h}$ ${\displaystyle h^{q}=1=h^{0}}$ ${\displaystyle x}$ ${\displaystyle h^{q+x}=1\cdot h^{x}=h^{x}}$ ${\displaystyle q=11}$ ${\displaystyle 2^{27}=2^{2\cdot 11+5}\equiv 2^{5}\equiv 9}$ ${\displaystyle \mathbb {G} }$

Key generation

1. The receiver draws a random exponent . This is the recipient's private key. ${\displaystyle a:=5}$
2. The recipient calculates the group element as his public key and makes it known. ${\displaystyle g^{a}=2^{5}\equiv 9\mod 23}$

Encryption

1. The sender wants to send the message . ( because of .) ${\displaystyle m=8}$ ${\displaystyle 8\in \mathbb {G} }$ ${\displaystyle 13^{2}=169\equiv 8\mod 23}$
2. The sender draws a random exponent . ${\displaystyle r=7}$
3. The sender calculates the cipher as follows: ${\displaystyle c}$
   • ${\displaystyle c_{0}:=g^{r}=2^{7}\equiv 13\mod 23}$.
   • ${\displaystyle c_{1}:=\left[g^{a}\right]^{r}\cdot m=9^{7}\cdot 8\equiv 9\mod 23}$.
   • ${\displaystyle c:=(c_{0},c_{1})=(13,9)}$
4. The sender sends the cipher to the recipient. ${\displaystyle c}$

Decryption

1. The receiver calculates the plaintext as follows: . ${\displaystyle m}$ ${\displaystyle m:=c_{0}^{-a}\cdot c_{1}=13^{-5}\cdot 9\equiv 13^{11-5}\cdot 9\equiv 13^{6}\cdot 9\equiv 6\cdot 9\equiv 8\mod 23}$

Note that an inversion (i.e. exponentiation with −1 in the exponent) of is actually necessary for decryption, but this can be carried out by simply subtracting the secret key ( ) from the group order ( ) without additional effort, together with the exponentiation that is necessary anyway: Since adding or subtracting in the exponent has no effect on the result, negative exponents ( ) can be replaced by positive ( ). In the example, saying . ${\displaystyle (c_{0})^{a}}$ ${\displaystyle a}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle -a}$ ${\displaystyle q-a}$ ${\displaystyle 13^{-5}\equiv 13^{11-5}=13^{6}\mod 23}$

safety

In cryptography, a standard assumption is the assumption that a well-studied mathematical problem is "difficult" to solve. If it can be shown that breaking a cryptographic method is equivalent to solving one of these problems, then it is ensured that it is at least as difficult. Elgamal's security is closely related to several standard assumptions.

In the following, a promising attacker means an attacker whose runtime is limited by an arbitrary but fixed polynomial function in the logarithm of the group order (= he is efficient ) and whose probability of success relative to the logarithm of the group order is at least as large as the inverse of any but fixed polynomial function (= it has a non-negligible probability of success ). ${\displaystyle q}$ ${\displaystyle q}$

Security against key extraction

Computing the secret key from the public key is exactly the problem of pulling discrete logarithms . Although there are algorithms for this that are significantly more powerful than brute force , these are either too inefficient to solve the problem in sufficiently large groups or require universal quantum computers . It is important to understand the limits of this statement: In principle, the existence of attacks is conceivable that do not make it necessary to know the secret key in order to extract plain text, which means that the statement is largely worthless on its own. ${\displaystyle a}$ ${\displaystyle \left[g^{a}\right]\in \mathbb {G} }$

The assumption that discrete logarithms are difficult to draw is a standard assumption in cryptography.

proof

The problem of extracting the secret key from the public one is exactly the problem of drawing discrete logarithms. Since we assume that no promising attacker is able to do this (DLog assumption!), There is also no promising attacker who can extract the private key.

Security against plain text extraction

The security term, which means the practical impossibility of extracting randomly selected plaintexts, is called "OW-CPA" (short for "One-Way under Chosen Plaintext Attacks" = "one way under attacks with selected plaintexts"). Specifically, this means that there is no efficient attacker who has a non-negligible probability of success in finding the plaintext for a given public key and a cipher with random plaintext.

ElGamal's OW-CPA security is equivalent to the Computational Diffie-Hellman Conjecture (CDH). This says that there is no efficient attacker who has a non-negligible probability of success in finding the group element for a given triplet . In contrast to the discrete logarithm problem, it is not necessary to determine the exponents . It is sufficient to be able to determine in order to decrypt the message. ${\displaystyle (g,g^{x},g^{y})\in \mathbb {G} ^{3}}$ ${\displaystyle g^{xy}\in \mathbb {G} }$ ${\displaystyle x,y}$ ${\displaystyle g^{xy}}$

Again it is important to understand that OW-CPA security is not sufficient for almost all practical applications: For example, OW-CPA allows you to learn a significant portion of the plain text or to check whether a cipher contains a certain plain text.

The CDH assumption is a stronger (i.e. more daring) assumption than the assumption that it is difficult to draw discrete logarithms, but it is also a standard cryptographic assumption that has not been seriously questioned.

proof

To prove OW-CPA security, we will use an attacker on the security of ElGamal to build an attacker for the Computational Diffie-Hellman problem. To this end, we carry out two security games: One in the role of the attacker with a CDH verifier and one with any attacker on the OW-CPA security from ElGamal in the role of the challenger.

1. Received with and unknown from the CDH challenger. ${\displaystyle \mathbb {G} ,(g^{x},g^{y})\in \mathbb {G} ^{2}}$ ${\displaystyle x}$ ${\displaystyle y}$
2. Take a random exponent . ${\displaystyle r\leftarrow \mathbb {Z} _{q}}$
3. Pass (group, public key, cipher) to the OW-CPA attacker. ${\displaystyle \mathbb {G} ,g^{x},(g^{y},g^{r})}$
   • These values ​​are indistinguishable from those in a real OW-CPA game, since in both cases all values ​​were chosen genuinely randomly.
4. Receive a (supposed) plain text from the OW-CPA attacker . ${\displaystyle m\in \mathbb {G} }$
5. Calculate ${\displaystyle h:=g^{r}\cdot m^{-1}}$
6. Pass to the CDH challenger. ${\displaystyle h}$

If the OW-CPA attacker is promising, there is a non-negligible probability that he will output the clearly determined “correct” plaintext , so that what the correct answer is in the CDH game. Since the running time of the simulator is essentially given as the sum of the (according to assumption) polynomial running time of the OW-CPA attacker and some clearly efficient operations, it is also polynomial. Since the simulator is also successful in the CDH game if and only if the OW-CPA attacker is successful, it is a promising attacker if and only if the OW-CPA attacker is. ${\displaystyle m}$ ${\displaystyle g^{r}=g^{xy}\cdot m}$ ${\displaystyle h}$

Since we assume that there is no promising CDH attacker (CDH assumption!), But we have shown that the existence of a promising OW-CPA attacker implies the existence of one, there cannot be a promising OW-CPA attacker giving ElGamal OW-CPA-safe.

Semantic security

IND-CPA or "semantic security" describes the weakest security term that is considered acceptable in modern cryptography for at least individual applications and clearly means that an attacker cannot obtain any information about the plain text from the cipher. (In contrast to the previous section, the attacker must also not be able to extract any part of the information here.) In the case of asymmetric encryption, this term can be defined as follows: The attacker receives a public key and can then choose two plaintexts to give to the challenger gives. The latter then chooses one of the two plaintexts with a coin toss, encrypts it with the method and returns the cipher to the attacker. If there is no efficient attacker who can now decide with a not negligibly better probability than (which can be achieved by pure guessing) which of the two selected plaintexts the cipher contains, the method is semantically secure. ${\textstyle {\frac {1}{2}}}$

For ElGamal, this property is equivalent to the Decisional-Diffie-Hellman conjecture . This states that there is no practicable algorithm that is able to distinguish between random events significantly better than it could by guessing. Although this assumption is even stronger (ie “more daring”) than the CDH assumption, it is also accepted as a standard assumption in cryptography. ${\displaystyle x,y,z\leftarrow \mathbb {Z} _{p}}$ ${\displaystyle g^{x},g^{y},g^{xy}\in \mathbb {G} }$ ${\displaystyle g^{x},g^{y},g^{z}\in \mathbb {G} }$

proof

This proof is similar to that for OW-CPA security, but the games are different: Our simulator now has the role of the attacker in a Decisional Diffie Hellman game (DDH) and that of the challenger in an IND-CPA game .

1. Received with unknown from the DDH challenger. ${\displaystyle \mathbb {G} ,(g^{x},g^{y},g^{z})\in \mathbb {G} ^{3}}$ ${\displaystyle x,y,z}$
2. Pass (group, public key) to the IND-CPA attacker. ${\displaystyle \mathbb {G} ,g^{x}}$
   • These values ​​are indistinguishable from those in a real IND-CPA game, since in both cases all values ​​were chosen genuinely randomly.
3. Receive two different plaintexts from the IND-CPA attacker . ${\displaystyle m_{0},m_{1}\in \mathbb {G} }$
4. Draw a random bit . ${\displaystyle b\leftarrow \mathbb {B} }$
5. Pass as cipher to the IND-CPA attacker. ${\displaystyle c:=(g^{y},g^{z}\cdot m_{b})}$
6. Got a bit from the IND-CPA attacker. ${\displaystyle b'\in \mathbb {B} }$
7. Hand in to the DDH challenger ${\displaystyle b'':=(b=b')}$

There are now two cases for the analysis:

• If so, the IND-CPA simulation is perfect. It is the IND-CPA attacker's probability of success. Since the simulator gives the correct answer (1) in the DDH game exactly when the IND-CPA attacker guesses wrong, the simulator is probably correct in this case . This is the case with probability . ${\displaystyle xy=z}$ ${\textstyle {\frac {1}{2}}+\epsilon }$ ${\textstyle {\frac {1}{2}}+\epsilon }$ ${\textstyle {\frac {1}{2}}}$
• If is, then a cipher is random. In this case, the IND-CPA attacker cannot inherently have a better strategy than guessing, with the probability that he guesses correctly or incorrectly. Since the simulator gives the correct answer (0) in the DDH game exactly when the IND-CPA attacker guesses wrong, the simulator is probably correct in this case . Overall, this case occurs with a probability of . ${\displaystyle xy\neq z}$ ${\displaystyle c}$ ${\displaystyle b}$ ${\textstyle {\frac {1}{2}}}$ ${\textstyle {\frac {1}{2}}}$ ${\textstyle {\frac {1}{2}}}$

It should be noted that in the latter case , an encryption of or may be due to pure coincidence with a probability of each , but these cases “cancel out” each other and are therefore irrelevant. ${\textstyle c}$ ${\textstyle {\frac {1}{|\mathbb {G} |}}}$ ${\textstyle m_{0}}$ ${\textstyle m_{1}}$

The weighted average of the simulator's probability of success in the DDH game is thus obtained . If the IND-CPA attacker were promising, it would not be negligible and thus also . Since the running time of the simulator is clearly polynomial and the same also applies to the IND-CPA attacker, if the IND-CPA attacker is successful, the simulator represents exactly one promising DDH attacker. ${\textstyle {\frac {1}{2}}\times \left({\frac {1}{2}}+\epsilon \right)+{\frac {1}{2}}\times {\frac {1}{2}}={\frac {1}{2}}+{\frac {\epsilon }{2}}}$ ${\displaystyle \epsilon }$ ${\textstyle {\frac {\epsilon }{2}}}$ ${\displaystyle p}$

Since we assume that there is no promising DDH attacker (DDH assumption!), But we have shown that the existence of a promising IND-CPA attacker implies the existence of such, there cannot be a promising IND-CPA attacker giving ElGamal IND-CPA-safe.

Insecurity against attacks with selected ciphers

IND-CCA describes another security term established in modern cryptography, which among other things ensures that an attacker does not manipulate a cipher without either the decryption fails or the new plain text has no recognizable relation to the old one. While this is usually a desirable or even necessary property, it can be “too strong” in special applications because it is incompatible with some properties that are desirable in these applications. This is also the case with ElGamal: Due to its homomorphism and rerandomizability, the procedure can not inherently offer IND-CCA security.

Security against attacks with non-adaptively selected ciphers

IND-CCA1 denotes a weakened variant of IND-CCA (which is also referred to as IND-CCA2) that does not contradict homomorphism. Assuming that the Decisional Diffie Hellman problem remains severe even if the attacker is granted temporary access to a certain oracle (Computational Static Diffie Hellman oracle / CSDH oracle), ElGamal fulfills this security concept. It must be emphasized that on the one hand this assumption is not an established cryptographic standard assumption, but on the other hand it has been proven in the generic group model for idealized groups (which is a strong indication but not a proof of security in the groups actually used).

proof

The proof is largely analogous to that for IND-CPA security, but differs in that the IND-CCA1 attacker also receives temporary access to a decryption oracle. First, however, it is necessary to define the DDH ^CSDH game:

• The DDH ^CSDH challenger draws a random exponent and passes it to the attacker. ${\displaystyle x\leftarrow \mathbb {Z} _{q}}$ ${\displaystyle g^{x}}$
• The attacker may (often polynomially) pass a group element to the challenger, who replies with . ${\displaystyle h\in \mathbb {G} }$ ${\displaystyle h^{x}}$
• The challenger takes a random bit and two random exponents with . If it passes the tuple to the attacker , otherwise . ${\displaystyle b\in \mathbb {B} }$ ${\displaystyle y,z\in \mathbb {Z} _{q}}$ ${\displaystyle xy\neq z}$ ${\displaystyle b=0}$ ${\displaystyle g^{y},g^{z}}$ ${\displaystyle g^{y},g^{x\cdot y}}$
• The attacker responds with one bit and wins if and only if ${\displaystyle b'\in \mathbb {B} }$ ${\displaystyle b=b'}$

Obviously, an attacker can guess at a 50% chance of success. We therefore only consider efficient attackers to be promising if their probability of success is more than negligibly higher than 50%. The DDH ^CSDH assumption states that there are no such attackers.

With this we can now adapt the proof of DDH security. First we change our simulator as follows:

1. Received with unknown from the DDH ^CSDH challenger. ( Difference to the DDH proof : the simulator does not yet receive an or .) ${\displaystyle \mathbb {G} ,g^{x}\in \mathbb {G} }$ ${\displaystyle x}$ ${\displaystyle g^{y}}$ ${\displaystyle g^{z}}$
2. Pass (group, public key) to the IND-CCA1 attacker. ${\displaystyle \mathbb {G} ,g^{x}}$
3. Answer decryption requests: ( Difference to DDH proof : entire phase)
   • Received a cipher with unknown from the IND-CCA1 attacker. ${\displaystyle g^{a},g^{b}}$ ${\displaystyle a,b}$
   • Submit as an oracle request to the DDH ^CSDH challenger. ${\displaystyle g^{a}}$
   • Receive from DDH ^CSDH challenger. ${\displaystyle g^{xa}}$
   • Pass to the IND-CCA1 attacker ${\displaystyle g^{b}\cdot \left[g^{xa}\right]^{-1}}$
4. Receive two different plaintexts from the IND-CCA1 attacker . ${\displaystyle m_{0},m_{1}\in \mathbb {G} }$
5. Received with unknown from the DDH ^CSDH challenger. ( Difference to the DDH proof : In the DDH proof, the simulator receives these values ​​at the beginning.) ${\displaystyle g^{y},g^{z}\in \mathbb {G} ^{2}}$ ${\displaystyle y,z}$
6. Draw a random bit . ${\displaystyle b\leftarrow \mathbb {B} }$
7. Pass as a cipher to the IND-CCA1 attacker. ${\displaystyle c:=(g^{y},g^{z}\cdot m_{b})}$
8. Got a bit from the IND-CPA attacker. ${\displaystyle b'\in \mathbb {B} }$
9. Hand in to the DDH challenger ${\displaystyle b'':=(b=b')}$

The further argumentation is exactly analogous to that of the IND-CPA proof: The existence of a promising attacker on the IND-CCA1 security from ElGamal implies the existence of a promising attacker on the DDH ^CSDH game. Since the DDH ^{CSDH assumption} excludes such an attacker, this means that there is no promising attacker on the IND-CCA1 security from ElGamal and ElGamal is therefore IND-CCA1-safe.

Uncertainty about quantum computers

With a variant of the Shor algorithm, quantum computers are able to draw discrete logarithms in any cyclic groups of finite order. As a result, a quantum computer equipped with a sufficient number of interlockable qubits would efficiently be able to completely break any variant of ElGamal by calculating the secret key from the public.

Other characteristics

In addition to its security, ElGamal also offers other properties that can be useful in some contexts.

Homomorphic encryption

They are ciphers of the plaintexts with the encryption coincidences for the public key . Then, without knowing the secret key, they can be linked by component-wise linking with the group operation to form a cipher of : ${\displaystyle c,c'}$ ${\displaystyle m,m'}$ ${\displaystyle r,r'}$ ${\displaystyle \left[g^{a}\right]}$ ${\displaystyle m\cdot m'}$

${\displaystyle (c_{0},\ c_{1})\cdot (c_{0}',c_{1}')=(c_{0}\cdot c_{0}',\ c_{1}\cdot c_{1}')=\left(g^{r}\cdot g^{r'},\ g^{ar}\cdot m\cdot g^{ar'}\cdot m'\right)=\left(g^{r+r'},\ g^{ar+ar'}\cdot m\cdot m'\right)=\left(g^{r+r'},\ g^{a(r+r')}\cdot m\cdot m'\right)}$

Rerandomizability

Let it be a plain text cipher with random encryption for the public key . Then, without knowing the secret key, a cipher can be calculated with the same plain text, which cannot be seen in a direct comparison. Let it be a freshly chosen exponent: ${\displaystyle c=:(c_{0},\ c_{1})}$ ${\displaystyle m}$ ${\displaystyle r}$ ${\displaystyle \left[g^{a}\right]}$ ${\displaystyle c'}$ ${\displaystyle r'}$

${\displaystyle (c_{0},\ c_{1})\cdot \left(g^{r'},\left[g^{a}\right]^{r'}\right)=\left(g^{r}\cdot g^{r'},\ g^{ar}\cdot m\cdot g^{ar'}\right)=\left(g^{r+r'},\ g^{ar+ar'}\cdot m\right)=\left(g^{r+r'},\ g^{a(r+r')}\cdot m\right)}$

To a certain extent, this involves using the homomorphism property with a newly generated cipher whose plain text is the neutral element ("1").

Indistinguishability of recipients

ElGamal ciphers offer anonymity in the sense that a cipher, even if the attacker selected plain text, cannot see for which of several public keys (from the same group!) It was created.

An asymmetrical encryption method is anonymous in the sense used here under attacks with selected plaintexts, if there is no promising attacker who can win the following game better than by guessing (probability of success ): ${\textstyle {\frac {1}{2}}}$

1. The challenger generates two pairs of keys and gives the public keys to the attacker
2. The attacker gives the challenger a valid clear text . ${\displaystyle m}$
3. The challenger randomly chooses one of the two public keys, encrypts it with it and passes the cipher to the attacker. ${\displaystyle m}$
4. The attacker gives the challenger his guess with which key the cipher was generated and wins exactly when he is right.

proof

The proof is done again by reduction with the following simulator:

1. Received with unknown from the DDH challenger. ${\displaystyle \mathbb {G} ,(g^{x},g^{y},g^{z})\in \mathbb {G} ^{3}}$ ${\displaystyle x,y,z}$
2. Draw a random bit and a random group element . ${\displaystyle b\leftarrow \mathbb {B} }$ ${\displaystyle h\leftarrow \mathbb {G} }$
3. If this is the case, hand it over to the attacker, otherwise . ${\displaystyle b=0}$ ${\displaystyle g^{x},h}$ ${\displaystyle h,g^{x}}$
4. Receive plain text from the attacker. ${\displaystyle m\in \mathbb {G} }$
5. Hand over to the attacker ${\displaystyle (g^{y},g^{z}\cdot m)}$
6. Get a bit from the attacker. ${\displaystyle b'\in \mathbb {B} }$
7. Hand in to the DDH challenger ${\displaystyle b'':=(b=b')}$

The further analysis is almost identical to that for semantic security: Here, too, there are two cases:

• If so , then there is an overwhelming probability that neither of the two public keys is a cipher of , but in both cases it is pure coincidence. In this case, the IND-CPA attacker cannot inherently have a better strategy than guessing, with the probability that he guesses correctly or incorrectly. Since the simulator gives the correct answer (0) in the DDH game exactly when the IND-CPA attacker guesses wrong, the simulator is probably correct in this case . ${\displaystyle xy\neq z}$ ${\displaystyle (g^{y},g^{z})}$ ${\displaystyle m}$ ${\displaystyle b}$ ${\textstyle {\frac {1}{2}}}$ ${\textstyle {\frac {1}{2}}}$
• If so, the simulation is perfect. The attacker's probability of success is to correctly guess the public key. Since the simulator gives the correct answer (1) in the DDH game exactly when the attacker guesses correctly, the simulator is probably correct in this case . ${\displaystyle xy=z}$ ${\textstyle {\frac {1}{2}}+\epsilon }$ ${\textstyle {\frac {1}{2}}+\epsilon }$

Since both cases occur with probability , the result is the probability of success of the simulator in the DDH game . If the attacker were promising, it would not be negligible and therefore not. Since the runtime of the simulator is clearly polynomial in the security parameter and the same also applies to the attacker, the simulator represents exactly a promising DDH attacker if the attacker is promising that the recipient cannot be distinguished. ${\textstyle {\frac {1}{2}}}$ ${\textstyle {\frac {1}{2}}\left({\frac {1}{2}}+{\frac {1}{2}}+\epsilon \right)={\frac {1}{2}}+{\frac {\epsilon }{2}}}$ ${\displaystyle \epsilon }$ ${\textstyle {\frac {\epsilon }{2}}}$

Since we assume that there is no promising DDH attacker (DDH assumption!), But we have shown that the existence of a promising recipient discriminator implies the existence of such, there can be no promising attacker who can attack an ElGamal- Cipher with known (or even selected) plain text shows which recipient it is intended for.

Encrypt for multiple recipients

There are public keys from different recipients. The product of these keys is in turn a public key, the private key of which is the sum of the private keys. This enables a message to be encrypted for several recipients in such a way that they are only able to decrypt the cipher when they work together. This decryption can also take place in any order. ${\displaystyle g^{x_{0}},g^{x_{1}},\dots ,g^{x_{n}}}$

We now consider the case for only two parties: It is and a cipher from with encryption random . Both parties can now calculate respectively . If these values are now in any order with multiplied, it follows: . ${\displaystyle g^{y}=g^{x_{0}+x_{1}}=g^{x_{0}}\cdot g^{x_{1}}}$ ${\displaystyle c=(c_{0},\ c_{1})=(g^{r},\ g^{yr}\cdot m)}$ ${\displaystyle m}$ ${\displaystyle r}$ ${\displaystyle g^{-r\cdot x_{0}}}$ ${\displaystyle g^{-r\cdot x_{1}}}$ ${\displaystyle c_{1}}$ ${\displaystyle g^{yr}\cdot m\cdot g^{-r\cdot x_{0}}\cdot g^{-r\cdot x_{1}}=g^{(x_{0}+x_{1})r}\cdot g^{-rx_{0}}\cdot g^{-rx_{1}}\cdot m=g^{r(x_{0}+x_{1}-x_{0}-x_{1})}\cdot m=g^{0}\cdot m=m}$

It should also be noted in this context that a partially decrypted cipher is a valid cipher with regard to the remaining keys. The following applies: what, together with a regular cipher for the public key , is random . This property can be particularly useful in combination with the rerandomizability and zero-knowledge evidence when designing complex protocols. ${\displaystyle g^{yr}\cdot m\cdot g^{-r\cdot x_{0}}=g^{(x_{0}+x_{1})r}\cdot g^{-rx_{0}}\cdot m=g^{r(x_{0}+x_{1}-x_{0})}\cdot m=g^{rx_{1}}}$ ${\displaystyle c_{0}}$ ${\displaystyle g^{x_{1}}}$ ${\displaystyle r}$

Subsequent over-encryption with a known private key

While only the public keys are required for several recipients for the encryption described above, these must be available at the time of encryption. On the other hand, if the secret key is known, it can also be added later. Again, let it be a plain text cipher with random encryption for the public key . Let another public key to which the private key belongs. A party who knows this private key and the cipher can now calculate and multiply this by what gives it the cipher , which has the previously described structure of a cipher with a key divided between several parties. ${\displaystyle c=:(c_{0},\ c_{1})=:\left(g^{r},g^{rx}\cdot m\right)}$ ${\displaystyle m}$ ${\displaystyle r}$ ${\displaystyle \left[g^{a}\right]}$ ${\displaystyle g^{y}}$ ${\displaystyle y}$ ${\displaystyle \left[g^{r}\right]^{y}=g^{ry}}$ ${\displaystyle c_{1}}$ ${\displaystyle c'=:(c_{0}',\ c_{1}')=:\left(g^{r},g^{rx}\cdot g^{ry}\cdot m\right)=\left(g^{r},g^{r(x+y)}\cdot m\right)}$

It should be noted in this context that there is no need for a well-known key, but can be generated fresh. As with the regular distribution of a key, this property is primarily useful when used in more complex protocols in conjunction with other primitives. ${\displaystyle g^{y}}$

Security problems with protocol deviations

Even if Elgamal is safe, this statement only applies if the procedure was implemented correctly. Unsafe special cases can arise due to poor choice of parameters or errors in implementation.

Multiple use of random encryption

For reasons of efficiency, the sender could come up with the idea of using the same randomness several times for several messages to the same recipient . In this case, the (comparatively complex) exponentiation in the group would only be necessary once and one group operation would remain per message. ${\displaystyle m_{0},m_{1},\dots }$ ${\displaystyle r}$

Such a procedure is, however, extremely insecure, which can already be seen from the fact that the same plain text would be mapped to the same ciphers, which is incompatible with IND-CPA security. In addition, a single plaintext cipher pair is sufficient for the attacker to decrypt all other messages: be the plaintext cipher pair known to the attacker and another cipher with the same coincidence. In this case and . Even if there is no plaintext / cipher pair, the consequences are potentially disastrous, since the quotient of the plaintexts is still the same as the quotient of the ciphertexts and thus considerable information about the relation of the plaintexts becomes public: ${\displaystyle m_{0},(c_{0},c_{1})}$ ${\displaystyle (c_{0}',c_{1}')}$ ${\displaystyle c_{0}=c_{0}'}$ ${\textstyle {\frac {c_{1}'\cdot m_{0}}{c_{1}}}={\frac {\left(g^{ar}\cdot m_{1}\right)\cdot m_{0}}{g^{ar}\cdot m_{0}}}=m_{1}}$ ${\textstyle {\frac {c_{1}}{c_{1}'}}={\frac {g^{ar}\cdot m_{0}}{g^{ar}\cdot m_{1}}}={\frac {m_{0}}{m_{1}}}}$

All of this can be clearly explained by the fact that the actual encryption at ElGamal is similar to that of a one-time pad : The DDH assumption means that it is indistinguishable from chance, even if and are known. The actual encryption then takes place in that the plain text is masked with this pseudo-random element. The multiple use of the same randomness now has the consequence that the masking element is used multiple times, which corresponds to the known insecure multiple use of the encryption randomness with one-time pads. ${\displaystyle g^{ar}}$ ${\displaystyle g^{a}}$ ${\displaystyle g^{r}}$

Problems with subgroups

For the safety of the ElGamal, the DDH assumption must apply in the group used. A necessary condition for this is that the order of is prime so that the trivial group is the only real subgroup of . If this is not the case, this can have fatal consequences: ${\displaystyle q}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle \mathbb {G} }$

For each divisor of the group order , there is a subgroup of with the order . An element is an element of this subgroup if and only if , with which it is easy to check for each element in which subgroups it is present. This enables discriminatory attacks against ElGamal: Be the public key and the first element of a cipher the producer of the entire group . In this case, the cipher reveals for all known factors of whether the plaintext is in the subgroup with the respective order. ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle n}$ ${\displaystyle h\in \mathbb {G} }$ ${\displaystyle h^{n}=1}$ ${\displaystyle g^{a}}$ ${\displaystyle g^{r}}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle q}$

This problem occurs especially when using residue class groups when a simple prime number is used as the modulus. Since 0 is not a member of the multiplicative group, the group order in this case is . The correct countermeasure in this case is to use a primary order subgroup, whereby it must be ensured that this subgroup is still large enough to withstand other attacks. In practice, when used correctly in most cases as a safe prime elected and the subgroup of squares of the associated device group used the prime field. It is important here, however, that the producer is actually a square, since otherwise the cipher can be seen whether the plaintext is a square. While this may not appear particularly bad at first glance, there are (under the DDH assumption) demonstrably secure protocols that are completely broken as a result ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle p}$

Another problem with subgroups that can occur with non-prime ordering concerns elements that produce only very small subgroups:

If the recipient chooses an exponent when generating the key so that his public key only generates a very small subgroup, the “mask” generated by the random encryption will also be in this subgroup. Effectively, this means that it can be easily found through a full search and the cipher can then be easily deciphered. This can look like this, for example: ${\displaystyle a}$ ${\displaystyle g^{a}}$ ${\displaystyle \left[g^{a}\right]^{r}}$

1. The recipient chooses the group with the producer . ${\displaystyle \mathbb {G} =\mathbb {Z} _{13}^{\times }}$ ${\displaystyle g=2}$
2. The recipient chooses and calculates as his public key ${\displaystyle a=4}$ ${\displaystyle A\equiv 2^{4}\equiv 3\mod 13}$

However,

${\displaystyle \langle 3\rangle =\lbrace 1,3,9\rbrace }$

or . Ie creates the subgroup of order 3. Because according to the main theorem about finitely created Abelian groups, it decays according to ${\displaystyle 3^{3}\equiv 1\mod 13}$ ${\displaystyle 3}$ ${\displaystyle \mathbb {G} }$

${\displaystyle \mathbb {Z} _{13}^{\times }\cong \mathbb {Z} _{3}^{+}\times \mathbb {Z} _{4}^{+}}$

The consequence of this is that the sender only multiplies the plain text by one of three group elements , regardless of which exponent is selected. In particular, the cipher is identical to the plaintext in one of three cases. ${\displaystyle m}$ ${\displaystyle \lbrace 1,3,9\rbrace }$ ${\displaystyle k}$

literature

• Taher ElGamal : A public key cryptosystem and a signature scheme based on discrete logarithms . July 1985. (English)
• Johannes Buchmann : Introduction to Cryptography. 3rd, expanded edition. Springer, Berlin et al. 2004, ISBN 3-540-40508-9 .
• Dietmar Wätjen: Cryptography. 1st edition. Spektrum Akademischer Verlag, Heidelberg 2004, ISBN 3-8274-1431-8 .

Individual evidence

1. ↑ Helger Lipmaa: " On the CCA1-Security of Elgamal and Damgård's Elgamal ", 2008 (English)
2. ↑ Mihir Bellare, Alexandra Boldyreva, Anand Desai, David Pointcheval: Key-Privacy in Public-Key Encryption
3. ↑ Florian Weber: "On Generators of Diffie-Hellman-Groups" (English)