New answers tagged

3

Remark: $p$ and $q$ are distinct odd primes (if not, we can factor $N$), thus $\phi(N)=(p-1)(q-1)$. Define $p'=(p-1)/2$ and $q'=(q-1)/2$. It holds $\phi(N)=4\,p'\,q'$. What's asked is not always possible. As a counterexample, assume $k=2$ (which is a possible $k$, from above remark), and $p\equiv 3\equiv q\pmod4$ (which covers about 25% of RSA keys). If we ...


2

Why we don't use additive groups? Is it a security thing? Yes, it's a security consideration. If we used the additive group $(\Bbb Z_N,+)$ rather than $(\Bbb Z_N^*,*)$ for RSA, public encryption would go $M\mapsto C=e\,M\bmod N$ rather than $M\mapsto C=M^e\bmod N$. Problem is, decryption would be trivial since anyone with the public key $(N,e)$ could ...


1

Your question is not clear. Which additive group would you like to use? RSA is hard because the group ${\mathbb Z}_N^*$ has unknown order (assuming the factorization of $N$ is unknown). Which additive group has that property?


1

The immediately obvious solution would be this simple cut-and-choose protocol: Prover: selects a random value $v$ and sends the value $y = v^\ell$ Verifier: selects and sends a random bit $b$ Prover: if $b=0$, sends the value $t_0=v$. If $b=1$, sends the value $t_1=vu$ Verifier: if $b=0$, then verify that $t_0^\ell = y$. If $b=1$, then verify that $t_1^\...


2

What does the order of $U(N)$ has to do with RSA key generation? The usual notation is $\Bbb Z_N^*$ for the multiplicative group modulo $N$, that the question names $U(N)$, and $\Phi(N)$ or equivalently $\varphi(N)$ for its order (number of elements), as given by Euler's totient function. $\forall x\in\Bbb Z_N^*$, it holds $x^{\Phi(N)}\equiv1\pmod N$. This ...


Top 50 recent answers are included