1
$\begingroup$

I am currently trying to make an implementation of the ElGamal encryption for educational purposes. As I understand it, when using the encryption with multiplicative cyclic groups, one generates a cyclic group for a safe private key as follows:

  1. Find a safe prime number $p$ (of the form $p = 2*q + 1$ where $q$ is prime)

  2. Find the generator of a cyclic group with order $q$ and modulo $p$ (i.e. a number $g$ less than $p$ such that $g^q \mod p = 1$ and $g^2 \mod p \neq 1$)

For example, for $p = 11$, we'd have $q = 5$, $g = 3, 4, 5$ or $9$, and the cyclic group would have the elements {$1, 3, 9, 5, 4$}.

Then, during the encryption stage, the one performing the encryption should convert $m$, the number representation of the message, into $m_1$, a member of this group. How is this done if $m$ doesn't belong to our group (for example, if it is $2, 6, 7, 8$ or $10$)?

If I am missing something, please tell me what did I get wrong!

Improve this question
$\endgroup$
2
  • $\begingroup$ It seems my understanding of ElGamal key generation was broken; we do not have to use a group of order $q$, rather, we should use a group of order $p$, where the problem does not exist $\endgroup$
    – Mints97
    Jan 24, 2015 at 20:03
  • 1
    $\begingroup$ Your asking about how to encode arbitrary integers to elements of cyclic subgroup $\mathbb G_q$. This question has been covered here $\endgroup$
    – cygnusv
    Jan 24, 2015 at 22:26

1 Answer 1

Reset to default
0
$\begingroup$

Use the Legendre symbol in your case. Explanation: when $p=2.q+1$, the order of the multiplicative group of $F_p$ is p-1=2q. Then there is no other alternative, when you select a random number, it could be a quadratic Residue with probability $\frac{1}{2}$. The legendre symbol of any number a, is : $a^{\frac{p-1}{2}}=a^{q}=\pm 1$

Then except the number 1, all the other quadratic residue (Legendre symbol is 1) have order q.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Ah, so all members of the subgroup should be quadratic residues? Thank you, I didn't realize it! This could prove to be an efficient way to check if a number belongs to the subgroup; however, this doesn't really answer the question: how should I "convert" a number to a member of the subgroup if it is a non-residue? $\endgroup$
    – Mints97
    Jan 24, 2015 at 16:23
  • 1
    $\begingroup$ @Mints97: Of course. Only the set of quadratic residues is a group. What kind of conversion you can do to convert a NQR into a QR? Just by multipling two NQR (distinct or not), you get a QR. Regarding the form of the prime p, if it is congruent to (1 mod 4) or not, (-1) could be or not a QR. $\endgroup$
    – Robert NACIRI
    Jan 24, 2015 at 16:31
  • $\begingroup$ I still don't get it =( this could be used to map NQRs to QRs, but then we wouldn't have a uniform method to map both QRs and NQRs to specific QRs. If we just multiply a NQR by a NQR, we will get a QR, but how do we tell it apart from a number that was already that very QR to begin with? For example, say we got an NQR 2 for input (with group modulo 11 as in my original example). We could square it, and get a QR 4. But what do we do if we get the QR 4 for input? $\endgroup$
    – Mints97
    Jan 24, 2015 at 16:58
  • $\begingroup$ Mints97: Yes of course, it's one of the possible alternative, I've understand your problematic. But we can do better. If you have the liberty of choosing the prime modulus p. Select it such as $p \equiv 1 \; mod \;4$, this condition is equivalent to $(-1) \in QR(p)$. Then randomly select $a \in F_p$ imply $a \in QNR(p) \; \Leftrightarrow -a \in QR(p)$. $\endgroup$
    – Robert NACIRI
    Jan 24, 2015 at 23:03
  • $\begingroup$ Sorry for the typo! You must understand above $p \equiv 3 \; mod \; 4$ and $-1 \in QNR(p)$ $\endgroup$
    – Robert NACIRI
    Jan 24, 2015 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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