Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 4 / 3G / b / Solution

No. The procedure exposes a square-root oracle for the Rabin cryptosystem. The verifier chooses $m$, sends $r=m^2\mathrm{mod}N$, and receives another square root $m_1$. Ifthen the factorization from distinct square roots modulo a semiprime givesFor a product of two odd primes, a square normally has four roots, and a returned root lies outside the pair $\{\pm m\}$ with probability about $1/2$. Repeating chosen-square challenges therefore factors $N$ with overwhelming probability. The attacker can then compute square roots and impersonate Alice. This is the chosen-square attack on Rabin authentication, so the proposed protocol is insecure.