Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I have been studying additive ElGamal and I think I have the hang of it except the part where the message $M$ must be retrieved by computing the discrete log of $g^M$.
From what I've read, the result of such computations is a function of $k$ e.g. for $g=3, M=4, \pmod{17}$ we have $3^4=13 \pmod{17}$ but computing the discrete log however gives $M=4 + 16k$. How do I know that $M=4$ and not $M=20$?
Note that for $g=3,M=20 \pmod{17}$ we also get $M=4+16k$.
The answer is simple if you know the answer to this question:
- Can you use 20 instead of 4 for a plaintext?
To solve this issue you have to limit your message space into $\pmod{17}$ and divide your longer message block in an appropriate way. Now, you know, you have to take the smallest positive value where $k=0$.
The problem with adding homomorphically is a different issue. Before the computation, you have to consider the upper bound of your calculations and choose your modulus according to it. For example, if you are going to add 4 and 8 there is no problem, however, if you are going to add 10 and 9 you have to consider a bigger modulus.
