Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This question is a companion to the equivalent question on elliptic curves.

Preliminaries

Diffie-Hellman, Elgamal, DSA, etc. are examples of protocols that work in the integers modulus a large prime $p$. However, for security reasons, we do not use all the integers in $\mathbb{Z}^*_p$ but only a subset of them. The subset is of size $q<p$ and $q$ is also a prime number. The subset is also chosen so that it also forms a group, $\mathbb{G}_q$, with closure under multiplication (a multiplicative subgroup). Number theory tells us that such a group can be found iff $q$ divides $(p-1)$.

With Elgamal in particular, messages must be encoded into $\mathbb{G}_q$. If the message is an $\ell$-bit bitstring $\{0,1\}^\ell$ and $\ell<|q|$, then it can be treated like an integer and will be in $\mathbb{Z}_p$ (and $\mathbb{Z}_q$) (we'll ignore the corner case of all zeros). The problem is that it is unlikely to also be in $\mathbb{G}_q$ (depending on how much smaller $q$ is than $p$).

Questions

How can you map numbers from $\mathbb{Z}_q$ to $\mathbb{G}_q$ and back when:

  • $p=2q+1$
  • $p=aq+1$ with an $a$ such that, e.g., |p|=1024 and |q|=160

(I'll accept the best answer for the second case) (As the second case appears not to be possible—see my answer—I've accepted an answer for the first case)

Format

This question is somewhat rhetorical for me personally, but I think it is a good place to gather different answers in one place (and things have been slow). With that in mind, use one technique per answer. Also relevant could be encoding-free Elgamal (such as hashed Elgamal) that sidesteps the problem.

share|improve this question
    
Can you elaborate more on the security reasons that we do not use all elements in $\mathbb{Z}_p^*$ but only a subset of them? –  curious Nov 29 '13 at 22:53

3 Answers 3

up vote 6 down vote accepted

For $p = 2q+1$, one can note that elements of $\mathbb{G}_q$ are exactly the non-zero quadratic residues modulo $p$:

  • Since $p$ is prime, $\mathbb{Z}_p$ is a field. Hence, the polynomial $X^q-1$, being of degree $q$, cannot have more than $q$ roots in $\mathbb{Z}_p$. So $\mathbb{G}_q$ contains all the $q$ values of order $1$ or $q$.

  • If $x$ is a non-zero quadratic residue ($x = y^2 \mod p$ for some value $y$) then $x^q = y^{2q} = y^{p-1} = 1 \mod p$. Thus, every non-zero quadratic residue is a $q$-th root of $1$, therefore an element of $\mathbb{G}_q$.

  • Since $q$ is a big prime, it is odd, therefore $p = 3 \mod 4$. This implies that if $x$ is a quadratic residue, then $-x$ is not, and vice versa. Thus, there are $(p-1)/2 = q$ non-zero quadratic residues.

This yields the following mapping:

  • If $x \in \mathbb{G}_q$ then it is a square and has two square roots, $y$ and $-y$ for a value $y$. Computing the square root modulo $p$ is easy: $y = x^{(p+1)/4} \mod p$. $y$ can be viewed as an integer between $1$ and $p-1$. Set $z = y - 1$ if $y \leq q$, or $z = p - y - 1$ otherwise. This always yields a value such that $0 \leq z \lt q$, i.e. a value in $\mathbb{Z}_q$.

  • For the inverse mapping, just compute $(z+1)^2 \mod p$.

share|improve this answer
    
Could you explain to me why "if x is a quadratic residue, then -x is not, and vice-versa"? Thanks –  user1086 Nov 15 '11 at 13:04
2  
@sophie: when working modulo a prime $p$ which is equal to 3 modulo 4, $-1$ is not a square (there is no $z$ such that $z^2 = p-1 \mod p$). This implies that if $x$ is a (non-zero) square (there is a $y \neq 0$ such that $y^2 = x \mod p$) then $-x \mod p$ cannot be a square; and it also works in the other direction (if $x$ is not a square than $-x$ is a square). This can be linked to Fermat's theorem (not the famous one): $x^{p-1} = 1 \mod p$; hence $x^{(p-1)/2} = ±1 \mod p$. This implies that $y = x^{(p+1)/4} \mod p$ is a square root of either $x$ or $-x$ (try it !). –  Thomas Pornin Nov 16 '11 at 15:20
    
Can you also explain why since $q$ is a big prime, it is odd, therefore $p = 3 \mod 4$ and that implies that $x$ is a quadratic residue? –  curious Nov 23 '12 at 9:40
1  
$q$ is a prime so it is odd ($2$ is the only even prime). Therefore $q = 2k+1$ for some integer $k$. So, $p = 2q+1 = 4k+3$, which means that $p = 3 \mod 4$. Whe computing modulo a prime $p$ which is equal to 3 modulo 4, $-1$ is not a quadratic residue, so $x$ and $-x$ cannot be both quadratic residues (but one of them necessarily is). –  Thomas Pornin Nov 23 '12 at 12:13

For the second case, mapping numbers from $\mathbb{Z}_q$ to $\mathbb{G}_q$ and back when:

  • $p=aq+1$ with an $a$ such that, e.g., |p|=1024 and |q|=160

It appears an efficient subgroup encoding/decoding scheme does not exist. Although it has not been proven that one cannot exist, notable cryptographers have conjectured it in the literature. For example, Chevallier-Mames, Paillier, and Pointcheval state:

(U)sing a group encoding remains incompatible with the optimization which consists in working in a small subgroup of $\mathbb{Z}^*_p$ of of prime order $q$ where $q$ is a 160-bit prime, a setting in which group exponentiations are much faster. [CPP06]

share|improve this answer

Probably the easiest solution for the case a=2 is to map $m\in\{1\ldots q\}$ to $(m/p)m$ where $(m/p)$ is the Legendre symbol. The inverse can be obtained by mapping a quadratic residue $x\in Z/(pZ)^*$ either to x or -x depending on which of the two residue classes contains an integer in $\{1\ldots q\}$.

This is of course a well know solution, but I can't find a reference at the moment.

share|improve this answer

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.