Tag Info

New answers tagged number-theory

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