One important aspect of digital signatures is the computational effort required to (i) sign a message, and (ii) to verify a signature. We will study the computational complexity of the Elliptic Curve algorithm with the public key (p,a,b,q,A,B) used as a digital signature in this problem. (a) How many point additions and doublings do we need on average to perform (i) signing of a message and (ii) verification of a signature? Assume that q has l = log2 q bits. (b) What takes longer, signing or verification? (c) Estimate the number of inversions, additions and multiplications (mod q) required to (i) sign a message, and (ii) to verify a signature. Bonus: Estimate the number of instructions that a 64-bit processor will need to execute for l = 160.

5. One important aspect of digital signatures is the computational effort required to (i) sign a message, and (ii) to verify a signature. We will study the computational complexity of the Elliptic Curve algorithm with the public key (p,a,b,q,A,B) used as a digital signature in this problem. (a) How many point additions and doublings do we need on average to perform (i) signing of a message and (ii) verification of a signature? Assume that q has I=log2q bits. (b) What takes longer, signing or verification? (c) Estimate the number of inversions, additions and multiplications (mod q) required to (i) sign a message, and (ii) to verify a signature. Bonus: Estimate the number of instructions that a 64 -bit processor will need to execute for I=160