Lenght of the ElGamal cipher

Question

Ok, it's kind of stupid question, but I want to make sure.

What is the length of the ElGamal cipher? It's equal to the size of 2 elements of the cyclic group, right? But lengths of elements are NOT always the same, right?

Toy example:

We pick p = 23, q = 11 (p = 2q+1), our generator is 18, so G = {18,2,13,4,3,8,6,16,12,9,1}. Sekret key x is 6 (a random form {1,q-1}), h = g^x mod p = 8.

Now is the fun part:

1) Encryption of m = 18 with r = 8 is (16,3)

2) Encryption of m = 18 with r = 7 is (6,9)

Am I getting different length ciphers because it's the toy example or what? Padding? All group elements have identical length? I haven't noticed any length difference in the real ElGamal implementation.

Answer 1

One common possibility is that your non-toy ElGamal cipher express integers as fixed-width octet strings, of width large enough for any element in the base field; that could be with I2OSP of PKCS#1v2.2 or equivalent, but there are a number of other (less common) ways.

Another possibility is that you did not try hard enough to find shorter ciphertext for your non-toy ElGamal cipher. When ASN.1 representation of integers is used, the digit size is an octet, and for some parameters an integer might be under the maximum size with low probability, like down to about 1/256 ≈ 0.4%. Even with two integers, quite a few hundred attempts might be necessary to observe a ciphertext below the usual size. There are other conventions where observing shorter ciphertexts would require billions attempts.