ElGamal encryption
The ElGamal encryption scheme or ElGamal cryptosystem (also al - Jamal cryptosystem ) is a program developed by cryptographers Taher Elgamal in 1985, public-key encryption scheme which is based on the idea of the Diffie -Hellman key exchange. The ElGamal encryption scheme is based, as well as the Diffie- Hellman protocol, on operations in a cyclic group of finite order. The ElGamal encryption scheme is provable IND - CPA - secure assuming that the decisional Diffie -Hellman problem is difficult in the underlying group.
Related to the encryption methods described herein (but not identical to ) the ElGamal signature scheme. Elgamal is not subject to patent.
- 2.1 Parameter generation
- 2.2 Key Generation
- 2.3 encryption
- 2.4 decryption
- 3.1 Theoretical Security
- 3.2 Practical Security 3.2.1 Avoidance of multiple use of the same multiplier
- 3.2.2 Avoidance of small ( sub-) groups
Description
Like all asymmetric cryptosystems also uses the ElGamal cryptosystem, a public and a secret key. The public key is used for encryption and can be published while the private key decryption is used and may be known only to the recipients of the message. That is, the receiver of the message must create a unique key pair of public and private keys. Then everyone can freely use the public key to encrypt a message and often send to the recipient. In the following description it is assumed as in cryptography assume that a sender wants to send a message to a recipient.
Parameter generation
The receiver selects a finite cyclic group with generator.
For the safety of the procedure, it is irrelevant whether each recipient " his own" cyclic group uses or whether all parties are working with the same cyclic group. In fact, it is such that depending on the used method ( Elgamal with number fields versus ElGamal elliptic curve ), both variants are used.
Key generation
Encoding
Decryption
Because it is:
A concrete example
As a choice for the finite cyclic group, two variants have prevailed. For the multiplicative unit group, ie, with prime, or the set of rational points of an elliptic curve is chosen on either. Because of better clarity here is an example for the first variant with ( unrealistic ) is chosen small.
For prim is a body and the elements of the unit group are all non-zero numbers, ie. The order of the group is therefore. As described in the section "Avoidance of small ( sub) groups," requires the certainty that the group order does not fall apart again into many small divider. Because prime, can not be avoided as a divisor of. Therefore, at least selected so that, again with prim applies (see Sophie Germain prime ).
Specifically, then, the following sequence:
Parameter generation
Selects the recipient and as a producer. (Because only two sub-groups. )
Key generation
Encoding
Decryption
Security
Theoretical security
Under a security primitives are understood in cryptography a well-studied, standard mathematical problem, which is generally accepted as "severe". It can be shown that the breaking of a Kryptografieverfahrens equivalent to solving one of these security primitives, it is determined that this is at least as difficult. The security of Elgamal is closely linked with several standard mathematical problems.
Breaking Elgamal by computing the secret key from the public key is exactly the discrete logarithm problem. There are, however, no efficient algorithms for computing discrete logarithms known, so that this - calculate not " acceptable " in time - for sufficiently large moduli.
Solving the Diffie- Hellman problem ( CDH) is equivalent to the inversion of the Elgamal encryption. That means that anyone who can find a certain probability at any ElGamal cipher the corresponding plaintext, solve CDH with the same probability, ie known and can determine the group element. In contrast to the discrete logarithm problem is not required to determine the exponent. It is sufficient to be able to determine to decrypt the message.
The stronger security property IND - CPA is equivalent to the Decisional Diffie -Hellman problem.
All three assumptions are standard assumptions in cryptography. Therefore, it is now assumed that the ElGamal cryptosystem can not be broken in a reasonable time within the meaning of the above safety items.
Practical Security
Even if Elgamal is theoretically safe, this statement only applies to the general case, ie any Elgamal problem. Due to poor choice of parameters or error in the implementation special cases can be generated which are still uncertain.
Avoid the multiple use of the same multiplier
For efficiency, the transmitter could come up with the idea for multiple messages to the same recipient to use the same. In this case, the ( complex ) exponentiation in the group would be necessary only once and it would remain a (simple ) multiplication per message. This is not recommended for security reasons, because it would thereby possible for an attacker to decrypt with a once of found plaintext ciphertext pair all prior and subsequent messages. This is due to that it is possible for a known and solve for. This in turn implies that it can be converted to and is there publicly, to determine the message leaves (see known plaintext attack).
Avoidance of small ( sub-) groups
Safety Elgamal based on the fact that it is difficult in any cyclic group may be to determine the exponent. Therefore particularly important to ensure that not too small, otherwise the exponent could be determined by simple enumeration. This problem arises, however, even when self is plentiful, but divided into many small sub-groups. After the main theorem on finitely generated abelian groups, any finite abelian group (and cyclic groups are abelian ) are decomposed into the direct sum of sub- groups, with a prime divisor of the group order is from. Ideally, one would therefore choose a group whose order is itself prime. Otherwise there is a risk that the recipient chooses in the key generation an index so that its public key is no longer a producer, but only on a small subset of.
For the worst case, at this point a small example given:
However applies
Or. That generates the subgroup of order 3 because disintegrates after the main theorem on finitely generated abelian groups according
The consequence of this is that the transmitter the plaintext only multiplied by one of three group elements no matter which exponent is chosen. In particular in one of three cases, the cipher text is identical to the plaintext.