Tag Info

New answers tagged

3

The (in my opinion) simplest way to proceed about this is: First compute the square root $m:=\sqrt n$ of $n$ in $\mathbb N$; this can, for instance, be done in time $\mathcal O(\log^3n)$ using a binary search. The next step is to compute $\varphi(m)$ from $\varphi(n)$: by the properties of $\varphi$ we have $$\varphi(n) = (p-1)p(q-1)q=\varphi(m)\cdot m ...


4

Since n = pq, then when an integer modulo n is a square, then it has (in general) four square roots. This can be seen by reasoning modulo p and modulo q: a square has two roots modulo p, and two roots modulo q, which makes for four combinations. More precisely, modulo a prime p, if y has a square root x, it also has another square root which is -x. The same ...


1

After another 5 minutes of thought, I think I solved my own problem. Choose an arbitrary message m, compute c=m^2 % n and submit c and n to the Rabin oracle. If you repeat this enough times (by which I mean probably within 2 iterations) you will choose m in such a way that the oracle gives you ± the other root, which you can then use to factor n.


3

Yes, but it's different and not as cost-efficient. The discrete log variant of the number field sieve goes (very loosely) like this: Collect logarithms of many small primes using sieving and linear algebra (the precomputation stage) Represent the target field element as a product of small primes and use the small logarithms to recover it (the individual ...


5

The main reason why the prime factors $p$ and $q$ of RSA modulus $N$ must be distinct is stated in the question: if they are equal, given $N$ (which by definition is public in RSA), it is trivial to find $p=q=\sqrt N$. A secondary reason is that with $p=q$, a few messages $x\in\{0\dots N-1\}$ can't be reliably deciphered from $x^e\bmod N$: all those $x$ ...



Top 50 recent answers are included