Cryptography: how to determine if an element is in a finite field?

Question

I'm working on a cryptography project that is basically a semantically secure modification to ElGamal. My question is: how do I determine if an element is in a finite field without calculating the whole field?

If we have two primes, a $q=5$ and a $p=11$ ($p = 2q + 1$, a safe prime). I can pick a $g$ by doing $g = h^2 \bmod p$. Let's say I use $h=6$ and end up with $g=3$. $g$ then generates its own group $\left<g\right>$. For semantic security, the message $m$ that I am going to encrypt must be in $\left<g\right>$... otherwise I must encrypt the additive inverse of $m$ which is guaranteed to be in $\left<g\right>$.

My question then is: if I have $m=5$, how do I determine whether that is in $\left<g\right>$ without calculating the whole field?

Obviously it would be really easy to calculate the field for the values in my example, but I'm using 1024-bit primes and generating the field isn't going to happen in my lifetime. Any suggestions?

Answer 1

The multiplicative group $\mathbb F_p^\times$ is cyclic of order $p-1=2q$. The group $\langle h\rangle$ is a subgroup thereof, hence of order $\in\{1, 2, q, 2q\}$. Then the order of $\langle g\rangle$ is $\in\{1,q\}$, an dI guess you would have started afresh in the first case. ;)

The only way for $m$ not to be in $\langle g\rangle$ is that $\langle m\rangle =\mathbb F_p^\times$. This is equivalent to $m^q\not\equiv 1\pmod p$.

Answer 2

For the particular case of the order $q$ subgroup $G$ of the multiplicative group $\mathbb F^{\times}_p$ modulo a safe prime $p = 2q+1$, there's a convenient trick: instead of working directly with the elements $a \in G$, we can work with the cosets $[a] = \{a,\,p-a\} = aH$, where $H = \mathbb F^{\times}_p/G = \{1,\,p-1\}$ is the order $2$ subgroup of $\mathbb F^{\times}_p$.

The trick is that we can represent the cosets by any of their members: if $a' \in [a]$ and $b' \in [b]$, we have $[a'b'] = [ab]$. Thus, we can choose an arbitrary element of each coset to represent it; a convenient choice is to always take the smallest positive one.

This choice maps $G$ one-to-one to the range $1$ to $q$ — and, conveniently, the map is also onto, so we know that any number in this range is a representative of the coset $[a]$ for some $a \in G$, and that all the cosets thus obtained are distinct.

So we can just work with numbers from $1$ to $q$ instead of the actual elements of $G$, always remembering to reduce the results of calculations modulo $p$ and take the smaller element of the coset $[x] = \{x,\,p-x\}$. Of course, actually figuring out which of $x$ and $p-x$ actually belongs in $G$ takes a bit more work, but fortunately, that's not actually something you need to do very often (if ever).