1
$\begingroup$

In ElGamal encryption, it says that the message M that is about to get encrypted must be mapped to its m counterpart in the group G using a reversible mapping function.

Map the message M to an element m of G using a reversible mapping function

Can someone help me understand (and point to some explanatory source) exactly what function this could represent? Can any message be mapped in such a way even though the group G is finite?

|improve this question|||||
$\endgroup$
1
$\begingroup$

In ElGamal encryption, the key-gen starts with a cyclic group $G$, of order $ q$, with generator $g$.

Now you want to map, $M$ into $G$. The simplest one is: if $M < q$ than map $M$ to $M$-th element in the group. If $M \geq q$ divide the $M$ into blocks. Choosing the block size is one bit less than $q$'s bit size, is easier and better. Once you divide, map each as in the first case.

The second case is similar to what we do in the block cipher as in ECB mode. However, ElGamal is a probabilistic encryption scheme, therefore we don't need IV, but you need to use a new random $y$ for each block.

Actually, one can find more mappings, for example, the permutations. Usually, that will be costlier than the simplest one.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ So if I understand this correctly, for a large message I will have to send multiple ciphertexts each with a part of the message? $\endgroup$ – Konstantine Sep 23 '19 at 8:50
  • $\begingroup$ Yes, this is always the case. $\endgroup$ – kelalaka Sep 23 '19 at 8:51
  • $\begingroup$ Note that, ElGamal is probabilistic encryption. For a block cipher, you need a proper mode. $\endgroup$ – kelalaka Sep 23 '19 at 9:28

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.