# VDF / RSA groups

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.

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$$.

• VDFs were defined here, to be precise. (This is a good survey.) Commented Jun 11, 2021 at 3:39

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.