# Generalized ElGamal encryption

The EIGamal encryption scheme is typically described in the setting of the multiplicative group Z*, but can be easily generalized to work in any finite cyclic group *G.*

As with EIGamal encryption, the security of the generalized EIGamal encryption scheme is *based* on the intractability of the discrete logarithm problem in the group *G.* The group *G* should be carefully chosen to satisfy the following two conditions:

- 1. for
*efficiency,*the group operation in*G*should be relatively easy to apply; and - 2. for
*security’,*the discrete logarithm problem in*G*should be computationally infeasible.

The following is a list of groups that appear to meet these two criteria, of which the first three have received the most attention.

- 1. The multiplicative group Z* of the integers modulo a prime
*p.* - 2. The multiplicative group of the finite field
*Wyn*of characteristic two. - 3. The group of points on an elliptic curve over a finite field.
- 4. The multiplicative group F* of the finite field F
_{9}, where*q = p*a prime.^{m}, p - 5. The group of units Z*, where
*n*is a composite integer. - 6. The jacobian of a hyperelliptic curve defined over a finite field.
- 7. The class group of an imaginary quadratic number field.
- 8.25 Algorithm Key generation for generalized EIGamal public-key encryption

SUMMARY: each entity creates a public key and a corresponding private key.

Each entity A should do the following:

- 1. Select an appropriate cyclic group
*G*of order*n,*with generator a. (It is assumed here that*G*is written multiplicatively.) - 2. Select a random integer
*a,*1 <*a < n -*1, and compute the group element a^{a}. - 3. A’s public key is (a, a" ), together with a description of how to multiply elements in
*G;*A’s private key is*a.* - 8.26 Algorithm Generalized EIGamal public-key encryption

SUMMARY: *В* encrypts a message *m* for *A,* which *A* decrypts.

- 1.
*Encryption. В*should do the following:- (a) Obtain A’s authentic public key (a, a:'
^{1}). - (b) Represent the message as an element
*m*of the group*G.* - (c) Select a random integer
*к,*1 <*к < n -*1. - (d) Compute 7 =
*a*and^{1}*S = m- (a*^{a})^{k}. - (e) Send the ciphertext c = (7,
*S)*to A.

- (a) Obtain A’s authentic public key (a, a:'
- 2.
*Decryption.*To recover plaintext*m*from c, A should do the following:- (a) Use the private key
*a*to compute 7“ and then compute*y~*^{a}. - (b) Recover m by computing (7
^{-0}) •*S.*

- (a) Use the private key
- 8.27 Note
*(common system-wide parameters*) All entities may elect to use the same cyclic group*G*and generator*a,*in which case a and the description of multiplication in*G*need not be published as part of the public key (cf. Note 8.20).

8.28 Example *(EIGonml encryption using the multiplicative group of* F_{2}m, *with artificially small parameters*)

*Key generation.* Entity *A* selects the group *G* to be the multiplicative group of the finite field F_{2} j , whose elements are represented by the polynomials over F_{2} of degree less than 4, and where multiplication is performed modulo the irreducible polynomial *f(x) = x ^{4}* +

*x +*1 (cf. Example 2.231). For convenience, a field element

*азх*+ a

^{3}_{2}x

^{[1]}

^{[2]}

^{[3]}

^{[4]}

^{[5]}

^{[6]}

^{[7]}

^{[8]}+

*ax + a*is represented by the binary string (a;

_{0}_{S}«

_{2}rti«o). The group

*G*has order

*n =*15 and a generator is a = (0010).

*A* chooses the private key *a =* 7 and computes = a^{7} = (1011). *A's* public key is *a ^{a} =* (1011) (together with

*a =*(0010) and the polynomial

*f(x)*which defines the multiplication in

*G,*if these parameters are not common to all entities).

*Encryption.* To encrypt a message *m* = (1100), *В* selects a random integer *к =* 11 and computes 7 = a^{11} = (1110), (a^{a})^{n} = (0100), and *S = m ■* (cc®)^{11} = (0101). *В* sends 7 = (1110) and *S =* (0101) to *A.*

*Decryption.* To decrypt, *A* computes 7“ = (0100), *(y ^{a})~ ^{l}* = (1101) and finally recovers

*m*by computing

*in =*(7

^{-0}) • <5 = (1100). □

- [1] SUMMARY: each entity creates a public key and a corresponding private key.
- [2] Integers k,n, and t are fixed as common system parameters.
- [3] Each entity A should perform steps 3-7.
- [4] Choose a kxn generator matrix G for a binary (n, /c)-linear code which can correctt errors, and for which an efficient decoding algorithm is known. (See Note 12.36.)
- [5] Select a random к x к binary non-singular matrix S.
- [6] Select a random n x n permutation matrix P.
- [7] Compute the к x n matrix G = SGP.
- [8] A’s public key is (G, t); A’s private key is (S, G, P).