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.

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?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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 $

And that about wraps it up. Please feel free to add comments if more explanations are needed.

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 $ :)

share|improve this answer
add comment

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.