ElGamal Encryption over a Subgroup

Question

Say for instance we are encrypting over a subgroup of ($Z_{67}^*, \bmod 67$).

To perform a round of El Gamal's encryption scheme we should:

1. Choose a subgroup of ($Z_{67}^*, \bmod 67$), of prime order.

2. Choose the parameters of ElGamal's scheme (generator, Bob's secret key, etc.).

3. Choose three random messages, and Alice's parameters, and describe what Alice transmits to Bob in each round

My question is not necessarily how to encrypt, but how to set up for encryption.

Given that in El Gamal's set-up is traditionally:

• $(p, \alpha, \beta)$ is Bob’s public key.

• $(a)$ is his private key

What would $p, \alpha, \beta$ be in this case? For example, is result of $(1) = p$? Result of $(2) = \alpha$?

Answer 1

The multiplicative group $\mathbb{Z_{67}}^*$ has 66 elements. By Lagrange theorem, we can say that the order of any subgroup $G$ of $\mathbb{Z_{67}}^*$ must divide the order of the group, 66. The inverse of the theorem doesn't need to be held, therefore one must check that there are subgroups of order 2,3, and 11, and their products.

With the below SageMath you can list the generators and their order;

def findOrder(a,G):
    temp = a
    for i in range (G.order()):
        if temp == G(1):
            return i+1
        temp = temp*a
        
R = Zmod(67)
grouplist = R.multiplicative_subgroups()
print(grouplist)
for x in grouplist:
    print(x, "order = ", findOrder(R(x[0]),R))

Don't try this code for large groups! This code outputs below with an error for the empty subset!.

( 2,) order =  66
( 4,) order =  33
( 8,) order =  22
(64,) order =  11
(38,) order =  6
(37,) order =  3
(66,) order =  2

Therefore, we have all possible subgroups, no counterexample for the inverse of the Lagrange Theorem.

The only prime orders are 2,3, and 11. For simple security, you need to choose 11. And actually prime is not necessary since ElGamal encryption can be defined over any cyclic group $G$. The security, on the other hand, relies on the Discrete Logarithm problem and when the group is not in prime order, the Pohlig-Hellman enters the game and we are not more secure than the largest prime order.

Ok, let stick with $p=11$ and it has a generator as $g=64$.

• Choose a random integer $\alpha$ from $\{1,\ldots, 10\}$
• Now, compute $\beta = g^{\alpha}$
• The public key $(G,q,g,\beta)$ and the private key is $\alpha$