# 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 choose $p_r$ and $q_r$ to be $2 * p_r'$ and $2 * p_q'$, where $p_r'$ and $p_q'$ 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 I 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 I set $g = g_r^{2 p_r q_r} \pmod n$

PS: I'll leave it as homework for the reader to figure out why the factor 2 is required for $p - 1$ and $q - 1$ :)