3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ [1] yes, a typo, sorry. [2] I incorrectly referred to it as "secret key" it's rather my secret value, yes. [3] $g^k\ mod\ p$ is the other component needed for decryption, no? [4] is it incorrect?? I thought my maths was correct... [5]/[6] sorry, I don't understanding this, could you explain? $\endgroup$ – nongrata May 26 '18 at 8:08
  • $\begingroup$ [4 after edit] but that yields ultimately the same result, 3095? [5 after edit] so but.. given the scenario in the exercise, how can I illustrate that ElGamal duplicates the length of the message? $\endgroup$ – nongrata May 26 '18 at 8:25
  • $\begingroup$ [5 after edit$^2$] oh boy, I'm sorry, I got it. because ciphertext is $max-length(g^k\ mod\ P),max-length(y^k * m\ mod\ p)$ and plaintext is $max-length(m)$, then plaintext is twice the size. out of curiosity then.... what exactly is the max length? $p-1$? $\endgroup$ – nongrata May 26 '18 at 8:37
  • $\begingroup$ 👉👈 okay.. I'm not entirely sure about [5] still. I might have been staring at this too long or the maths/concept is just beyond me, to be honest. You're saying the maximum length is the # of digits which is $⌈log_b\ p⌉$? Where $b = 2$ for bits, $256$ for octets and $10$ for decimals? $\endgroup$ – nongrata May 26 '18 at 9:32

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.