# DGK Cryptosystem Key Generation and Decryption Issues

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?

Just in case someone else is trying to implement this cryptosystem, I wish to share the implementation that I am currently using. Someone helped me pick another approach for generating $$h$$ and $$g$$, and, intuitively, it seems secure.

In order to generate $$h$$ and $$g$$, I now apply certain algorithms described in the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone

Specifically, I use Algorithm 4.83, Chapter 4: Selecting an element of maximum order in $$\mathbb{Z}_n^*$$, where $$n = p q$$:

INPUT: two distinct odd primes, $$p$$, $$q$$, and the factorizations of $$p - 1$$ and $$q - 1$$.

OUTPUT: an element $$\alpha$$ of maximum order $$lcm(p - 1; q - 1)$$ in $$\mathbb{Z}_n^*$$, where $$n = p q$$.

1. Use Algorithm 4.80 with $$G = \mathbb{Z}_p^*$$ and $$n = p - 1$$ to find a generator $$a$$ of $$\mathbb{Z}_p^*$$.
2. Use Algorithm 4.80 with $$G = \mathbb{Z}_q^*$$ and $$n = q - 1$$ to find a generator $$b$$ of $$\mathbb{Z}_q^*$$.
3. Use Gauss's algorithm (Algorithm 2.121) to find an integer $$\alpha$$, $$1 \leq \alpha \leq n - 1$$, satisfying $$\alpha \equiv a \pmod p$$ and $$\alpha \equiv b \pmod q$$.
4. Return $$\alpha$$.

For completeness, here are the two algorithms referenced above in Algorithm 4.83:

Algorithm 4.80, Chapter 4 : Finding a generator of a cyclic group:

INPUT: a cyclic group $$G$$ of order $$n$$, and the prime factorization $$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$

OUTPUT: a generator $$\alpha$$ of $$G$$

1. Choose a random element $$\alpha$$ in $$G$$
2. For $$i$$ from $$1$$ to $$k$$ do the following:
• Compute $$b \gets a^{n/p_i}$$ (N.B. $$\pmod n$$)
• If $$b = 1$$ then go to step 1.
3. Return $$\alpha$$.

Algorithm 2.121, Chapter 2 (Gauss's algorithm): The solution $$x$$ to the simultaneous congruences in the Chinese Remainder Theorem (Fact 2.120) may be computed as $$\sum_{i = 1}^{k}{a_i N_i M_i \pmod n}$$, where $$N_i = n / n_i$$ and $$M_i = N_i^{-1} \pmod {n_i}$$. These computations can be performed in $$O((\lg n)^2)$$ bit operations.

Fact 2.120, Chapter 2: (Chinese remainder theorem, CRT) If the integers $$n_1$$, $$n_2$$, ..., $$n_k$$ are pairwise relatively prime, then the system of simultaneous congruences

$$x \equiv a_1 \pmod {n_1}$$

$$x \equiv a_2 \pmod {n_2}$$

$$\vdots$$

$$x \equiv a_k \pmod {n_k}$$

has a unique solution modulo $$n = n_1 n_2 \cdots n_k$$.

In order to apply Algorithm 4.83, we require the factorizations of $$p - 1$$ and $$q - 1$$. The standard approach would be to just factor the random ~200 bit factors $$p_r$$ and $$q_r$$. On the other hand, assuming that we don't break the security assumptions, we can use $$p_r = 2 p_r'$$ and $$q_r = 2 q_r'$$, where $$p_r'$$ and $$q_r'$$ are random primes of the required size. After ensuring that $$p = 2 p_r' v_p u + 1$$ and $$q = 2 q_r' v_q u + 1$$ are also primes, we may compute $$h$$ and $$g$$ with the above algorithms:

• First, we compute $$h_r$$ and $$g_r$$ of order $$LCM(p - 1, q - 1) = (p - 1)(q - 1) / GCD(p - 1, q - 1) = 2 u p_r' v_p q_r' v_q$$ in $$\mathbb{Z}_n^*$$ with Algorithm 4.83
• $$h$$ must have order $$v_p v_q$$ in $$\mathbb{Z}_n^*$$, so we set $$h = h_r^{2 u p_r' q_r'} \pmod n$$
• $$g$$ must have order $$u v_p v_q$$ in $$\mathbb{Z}_n^*$$, so we set $$g = g_r^{2 p_r' q_r'} \pmod n$$

PS: The factor $$2$$ is required for $$p - 1 = 2 p_r' v_p u$$ and for $$q - 1 = 2 q_r' v_q u$$ because the product of three odd primes is odd, and, thus, by adding one, we get an even number larger than 2, which can't be prime, but both $$p$$ and $$q$$ need to be prime numbers.