From this link Generation of a cyclic group of prime order we know how to generate a prime order group.

enter image description here

This illustrates why a prime order group is important.

But why is modulus a prime number also important?

In the theory of RSA, the modulus $N=pq$, and $\operatorname{totient}(N)=(p-1)(q-1)$, if we can find a factor $p'$ of $p-1$, then we can claim there is a $p'$ order sub-group? But it is not a modulus prime group, the $N$ is a composite number, is such a group useful?

  • 1
    $\begingroup$ In classical Diffie-Hellman, you work on the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^{\times}$ where $p$ is prime. All computations are done modulo the prime $p$. $\endgroup$ – Tosh Sep 10 '19 at 10:31
  • 1
    $\begingroup$ Another example is elliptic curve cryptography, which is often performed with an elliptic curve with x and y coordinates in the prime field $\Bbb Z_p$. Yet another is fast implementations of RSA signature and decryption (CRT-based), where the heaviest computations are performed modulo each prime dividing the public modulus. $\endgroup$ – fgrieu Sep 10 '19 at 17:13

Yes, such a group is useful. In particular, when $N= p\cdot q$ where $p,q$ are both strong primes (i.e. $p=2p'+1,q=2q'+1$ where $p',q'$ are also prime numbers).

Discrete logarithm in the prime order cyclic groups (order-$p'$ and order-$q'$) is believed to be hard. Such a group is called a group with hidden order.

A few examples of application: Fujisaki and Okamoto used this group to construct a commitment scheme. It has also been used in constructing a zero-knowledge proof of an integer falls within an interval (range proof).

Note that security does not hold for any arbitrary $N$ (even if it has only two large prime factors), see this paper.

| improve this answer | |
  • $\begingroup$ Thanks, these thoughts are very creative, I've downloaded the paper and looking at it. $\endgroup$ – Ray James Sep 11 '19 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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