I detailed here the DGK (Ivan Damgård, Martin Geisler and Mikkel Krøigaard) cryptosystem, and I managed to get it to work, most of the time...
The BIG problem that I am facing at the moment is that the key generation algorithm sometimes produces bad keys. The paper states that:
- we generate $h$ of order $v_p v_q$ modulo p and q
- we generate $g$ of order $u v_pv_q$ modulo p and q
That sounds simple enough, right? But what does it mean? The naive approach (and I'm going to provide it only for $h$, since it works similarly for $g$) is this:
If $h \in \mathbb{Z}_n^*$ must have order $v_p v_q$, then the following conditions must be met:
- $h^{v_p} \neq 1$
- $h^{v_q} \neq 1$
- $h^{v_p v_q} = 1$
- Must ensure that $h \in \mathbb{Z}_n^* \Rightarrow gcd(h, n) = 1$
- Also, we make sure that $h > 1$
Now, I have tested this approach and it seems to take quite a lot of time to produce a "good" value (perhaps I had an error in the code or I have no idea why it takes forever), so another approach would be to use the Chinese Remainder Theorem to obtain $h$ (and $g$):
- Compute $h \in \mathbb{Z}_n^*$ of order $v_p v_q$ modulo p and q $\Rightarrow h = h_r^{p_r q_r u} \pmod n$, where $h_r$ is a random number in $\mathbb{Z}_n^*$ and $p_r$, $q_r$ are the random components of p and q. In order to obtain p and q, we choose 2 random primes, $v_p$ and $v_q$ and we compute $p = p_r u v_p + 1$ and $q = q_r u v_q + 1$, such that p and q are prime.
- $n = p q$ and $\mathbb{Z}_n^* \simeq \mathbb{Z}_p^* \times \mathbb{Z}_q^*$
- h represented in $\mathbb{Z}_p^* \times \mathbb{Z}_q^*$ is $(h_p, h_q)$
- $h_r$ represented in $\mathbb{Z}_p^* \times \mathbb{Z}_q^*$ is $(h_{rp}, h_{rq})$
- $h^{v_p v_q} \overset{\mathbb{Z}_p^* \times \mathbb{Z}_q^*}{\longleftrightarrow} (h_p^{v_p v_q}, h_q^{v_p v_q}) = ((h_{rp}^{p_r q_r u})^{v_p v_q}, (h_{rq}^{p_r q_r u})^{v_p v_q})$
- $h_p^{p - 1} = 1 \pmod p$ and $h_q^{q - 1} = 1 \pmod q$
- $p - 1 = p_r u v_p$ and $ q - 1 = q_r u v_q$
- $(h_p^{v_p v_q}, h_q^{v_p v_q}) = (1^{q_r v_q}, 1^{p_r v_p}) \overset{\mathbb{Z}_n^*}{\longleftrightarrow} 1 \pmod n$
From the above math, it seems obvious that if I choose $h = h_r^{p_r q_r u} \pmod n$, where $h_r$ is a random number and I ensure that $h \in \mathbb{Z}_n^* \Rightarrow \gcd(h, n) = 1$ and $h > 1$, then I should get a "good" $h$ of order $v_p v_q$, but not of order $v_p$ or $v_q$ in $\mathbb{Z}_n^*$.
Unfortunately, for some reason, this does not work well. I often get $\gcd(p_r q_r u, n) \neq 1$, which means that no matter what is the value of $h_r$, $h_r^{p_r q_r u} \pmod n = 1$. Because of this, I added another condition while generating p and q: $\gcd(p_r, v_p) = 1$ and $\gcd(q_r, v_q) = 1$. Although it seems to avoid the above issue, I am unable to explain it. Also, now I've hit another issue: It looks like I sometimes end up with g of order $v_p$ in $\mathbb{Z}_p^*$, which messes up the decryption algorithm: $E(m,r)^{v_p} = (g^{v_p})^m\pmod p$
Does anybody have any idea how to fix his? I'm almost sure that I have to impose extra conditions while generating p and q, but I am unable to figure it out and it would really be great to understand what exactly is going on... Is there a cleaner way to generate numbers of a certain order modulo n?