ElGamal ciphertext lenght

Question

I'm studying for an exam and answering practice questions and I would love clarification on something. Apologies if it seems really simple.

My lecture notes indicate that for ElGamal:

the ciphertext is twice the length of the plaintext.

Here is my exercise:

• the public key $y$ which is $5496$
• my chosen plaintext $m$ which is $104$
• $p$ which is $9323$ and $g$ which is $5261$
• my secret value $k$ which is $92$

These values were all supplied for the exercise so I have to work with them.

I have calculated $g^k \bmod p$ which is $8606$

I have also calculated $(y^k×m) \bmod p$ which is $3095$

Therefore, $3095$ is the ciphertext, correct?

My plaintext $m$ was $104$ which is 3 digits, and my ciphertext is only... 4?

Realistically, if the result is $\bmod p$ then $p$ is 4 digits and no result would ever be greater than that.

So is this statement not so literal? Wherein, it's not that $3095$ is twice the length of $104$, it's that $3095$ decoded from numbers to text is twice the length of $104$ decoded from numbers to text?

Therefore, if A = 0 then 104 = KE and 3095 = DAJF which is... twice the length.

Is this the correct theory behind the statement that the ciphertext is twice the length of the plaintext?

Answer 1

Several issues:

1. (Typo now fixed) $g$ and $G$ where visually different, I do not see a reason why.
2. (Fixed by now using secret value where there was secret key) When enciphering, one does not need a secret key; the deciphering party is assumed to know the private key matching the public key, and keep it secret. The $k$ is the random secret nonce (number used once) drawn for encryption, not a "secret key". That's confirmed by $g^k\not\equiv y\pmod p$.
3. $y^k\cdot m\bmod p$ would be part of the ciphertext; something else is needed for successful decryption. Argument: $y^k\bmod p$ is essentially random for one not knowing $k$, thus so is $y^k\cdot m\bmod p$ for any particular $m$ coprime to $p$, thus $y^k\cdot m\bmod p$ can't allow recovering $m$ for one with no clue about $k$ (or something related).
   Yes, that other component of the ciphertext is $g^k\bmod p$.
4. (My bad).
5. All $m$ with $1\le m<p$ are counted as having the same size. The ciphertext comprises two integers in $\Bbb Z_p^*$ while the plaintext is one, thus the ciphertext is twice as large as the plaintext. Cryptographers count the maximum size of message and cryptogram, rather than their actual size. As an aside they use bits or octets, rather than decimal digits, but the later is OK in the context of this exercise.
   Non-negative integers strictly less than integer $p$ can all be expressed with $\lceil\log_b p\rceil$ digits in base $b$, where the notation $\lceil y\rceil$ is for $y$ rounded up to integer, and $\log_b(x)=\log(x)/\log(b)$; the base $b$ is $2$, $256$ or $10$ for bits, octets, or decimal digits.
6. We have $p-1=2\cdot59\cdot79$ when usually, in ElGamal, it is chosen $p$ prime with $(p-1)/2$ also prime, since that improves security against the Pohlig-Hellman discrete logarithm method. But since $p$ is way too small for security anyway, that' not a big deal. Or perhaps the next step is showing that attack at work to break the encryption; e.g. by recovering the private key from $y$, or recovering $k$ from $g^k\bmod p$.