2
$\begingroup$

I believe I am overthinking it; however, I need to clear out my doubts.

What is exactly RSA groups and how their order is unknown? I know in RSA N is computed by multiplying two prime numbers (p and q) and it is hard to find p and q given N. Is N what is called RSA group?

In VDF they use unknown order of RSA group; however, N is public.

$\endgroup$

2 Answers 2

7
$\begingroup$

The RSA group for modulus $N$ of secret factorization simply is the multiplicative group of integers modulo $N$, often noted $\mathbb Z_N^*$. That can be viewed or defined as the subset of integers $m$ in the interval $[0,N)$ with $\gcd(N,m)=1$. The group law is multiplication modulo $N$, that is $a*b$ is the remainder of the Euclidean division of $a\times b$, where $\times$ is integer multiplication.

That group has order¹ the Euler totient $\varphi(N)$. That quantity is unknown, since the factorization of $N$ is. We can easily compute $\varphi(N)$ if we know the factorization of $N$, and it turns out we can factor $N$ if we know $N$ and $\varphi(N)$.

Note: RSA encryption/decryption is often operating on the full monoid $[0,N)$ under multiplication modulo $N$, rather than it's group subset $\mathbb Z_N^*$. This requires that $N$ is squarefree for decryption to work reliably.


In Benjamin Wesolowski's Efficient Verifiable Delay Functions (in proceedings of EuroCrypt 2019), $(\mathbf Z/N\mathbf Z)^×$ is $\mathbb Z_N^*$. Their notation reflects a construction of this group as the restriction to invertible elements of the quotient set of equivalence classes in integers (that they note $\mathbf Z$ rather than $\mathbb Z$ above), for the equivalence relation congruent² modulo $N$, under the law $×$ which is compatible with this equivalence relation. I get this is how real math guys do it; I'm not really one.

See comment for more references on VDFs.


¹ that is, since it's a finite set, it's number of elements.

² by definition, $a\equiv b\pmod N\iff\exists q,\,a=b+q\times N$, with all quantities in $\mathbb Z$.

$\endgroup$
1
  • 2
    $\begingroup$ VDFs were defined here, to be precise. (This is a good survey.) $\endgroup$
    – ckamath
    Jun 11, 2021 at 3:39
0
$\begingroup$

how their order is unknown?

The RSA public key may be generated using multiparty computation (MPC) (or, less nicely, by a third trusted party). Then, N is indeed public, but p and q are not, and so the group order is unknown.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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