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.

  • $\begingroup$ There's about a $\frac{2}{256}$ of one of the parts being a byte shorter. Padding may be applied depending on the encoding. $\endgroup$
    – SEJPM
    Jan 25 '18 at 12:40

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.