Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Is it not possible to check to see if $m\in\{g^n\mid n\in\mathbb{N}\}$? Does your scheme prevent $\langle g\rangle$ from being all nonzero elements of the field? I'm just curious... I can't see the details at a glance. –  rschwieb Sep 12 '12 at 18:53
    
Nitpick: The question is about whether the element $m$ is in the subgroup generated by $g$. It will always be an element of the finite field. IOW the title is a bit misleading. –  Jyrki Lahtonen Sep 13 '12 at 6:37
add comment

2 Answers

up vote 2 down vote accepted

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$.

share|improve this answer
    
+1 That's all folks! Unless you can factor $m$, when you can work by using multiplicativity of the Legendre symbol (and quadratic law of reciprocity) and verify that $m$ is also a quadratic residue ($\langle g\rangle$ will consist of precisely the quadratic residues modulo $p$). In OP's case that alternative would probably be computationally more demanding. –  Jyrki Lahtonen Sep 13 '12 at 6:35
    
Thank you! That gives me an easy check for m. I appreciate it! –  Chris C Sep 13 '12 at 14:54
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.