Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 4 / 3G (Coding and Cryptography)

In Diffie-Hellman key exchange, Alice and Bob publicly agree on a cyclic group $G=⟨g⟩$ in which the discrete logarithm problem is believed hard. Alice chooses a secret $a$ and sends $A=g^a$; Bob chooses a secret $b$ and sends $B=g^b$. They independently computeThusis their shared key. A passive eavesdropper sees $g,g^a,g^b$ but is believed unable to compute $g^{ab}$ efficiently; this is the computational Diffie--Hellman assumption. The basic protocol does not authenticate the participants and is therefore vulnerable to a man-in-the-middle attack unless the exchanged values are authenticated.

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.