New answers tagged

1

This is not true. In particular, consider $4\in (\mathbb{Z}/5\mathbb{Z})^\times$. We have that $4^2 = 16\equiv 1\bmod 5$, so $\langle 4\rangle = \{1, 4\}$ is not the full group. The theorem you mention is known as Fermat's little theorem, and it states: $\forall x\in (\mathbb{Z}/p\mathbb{Z})^\times$, $x^{p-1}\equiv 1\bmod p$ As you mention, all elements ...


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

Cycles (not necessarily Hamiltonian) in the Cayley graph correspond to relations among generators of the group. The RSA assumption can be written as "It is computationally difficult to find a non-trivial relation in the RSA group $(\mathbb{Z}/pq\mathbb{Z})^*$", which is a property of $(\mathbb{Z}/pq\mathbb{Z})^*$ known as being "pseudo-free" (see The RSA ...


0

I was unable to find a solution to the problem besides the approach suggested in the comments, but I wanted to add a few theorems from group theory that are relevant here. The problem with picking a random group element as a generator is that it might actually be a generator of a smaller subgroup. By Euler's theorem, every element raised to the power of the ...


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


3

The claim is completely false. The security of DDH over appropriate composite-order elliptic curves is not only believed to hold, the assumption that it holds has been widely used in cryptography. To give a single famous example, the BGN cryptosystem was initially defined over composite-order elliptic curves (with a pairing), before being generalized a few ...


Top 50 recent answers are included