91Ó°ÊÓ

Let \(E\) be the elliptic curve $$ E: y^{2}=x^{3}+x+1 $$ and let \(P=(4,2)\) and \(Q=(0,1)\) be points on \(E\) modulo 5 . Solve the elliptic curve discrete logarithm problem for \(P\) and \(Q\), that is, find a positive integer \(n\) such that \(Q=n P\).

Alice and Bob agree to use elliptic Diffie-Hellman key exchange with the prime, elliptic curve, and point $$ p=2671, \quad E: Y^{2}=X^{3}+171 X+853, \quad P=(1980,431) \in E\left(\mathbb{F}_{2671}\right) . $$ (a) Alice sends Bob the point \(Q_{A}=(2110,543)\). Bob decides to use the secret multiplier \(n_{B}=1943\). What point should Bob send to Alice? (b) What is their secret shared value? (c) How difficult is it for Eve to figure out Alice's secret multiplier \(n_{A}\) ? If you know how to program, use a computer to find \(n_{A}\). (d) Alice and Bob decide to exchange a new piece of secret information using the same prime, curve, and point. This time Alice sends Bob only the \(x\)-coordinate \(x_{A}=2\) of her point \(Q_{A}\). Bob decides to use the secret multiplier \(n_{B}=875\). What single number modulo \(p\) should Bob send to Alice, and what is their secret shared value?