how to represent message as an integer between 1 and n-1?

Question

I am trying to implement simple El-Gamal cryptosystem.

And I can't understand how to represent message as an integer between 1 and n-1. The only thing that comes to my mind is: if n bit length is k, then divide input message m on t | t < k bits and each piece of bits use as integer number.

I think It is wrong.

So how to represent message as an integer between 1 and n-1?

Answer 1

You could do that which is essentially the equivalent of using ECB mode in block ciphers, but there are attacks on this. An attacker may reorder the different blocks of the ciphertext and you would decrypt it without problem, but the received plaintext would be broken without you knowing this. This may also open the door for replay attacks since the blocks are all encrypted independently. You would need some kind of authenticated encryption.

Back to your original question. Such a problem is usually solved by using hybrid encryption. A block cipher like AES is used to encrypt the whole plaintext with a random key. This random key is in turn encrypted through ElGamal since the key is small enough to be represented in < k bits.

Now depending on the mode of operation of the block cipher this could still be malleable. You would either need to put a hash of the ciphertext/plaintext next to the random key as an integrity check. Or otherwise use an authenticated mode of operation like GCM and add the resulting tag next to the random key. Depending on k, this should fit.

Note that you should use some kind of padding for random key | hash/tag if it doesn't reach k.