Here is information about the Double and Add algorithm:

Here is the actual problem:

#1 P = 1_1 P # 1a P + P = 2P = 10_2 P # 1b 2P + P - 3P - 10_2 P + I_2 P - 11_2 P # 2a 3P + 3P = 2(11_2 P) = 110_2 P # 2b # 3a 6P + 6P = 12P = 2(110_2 P) = 1100_2 P #3b 12P - P = 13P = 1100_2 P + 1_2 P = 1101_2 P # 4a 13P + 13P = 26P = 2(1101_2 P) = 11010_2 P # 4b initial setting. bit processed: d_4 = 1 DOUBLE, bit processed: d_3 ADD, since d_3 - 1 DOUBLE, bit processed: d_2 no ADD, since d_2 = 0 DOUBLE, bit processed: d_1 ADD, since d_1 = 1 DOUBLE, bit processed: d_0 no ADD, since d_0 = 0 It is instructive to observe how the binary representation of the exponent evolves. We see that doubling results in a left shift of the scalar, with a 0 put in the rightmost position. By performing addition with P, a 1 is inserted into the rightmost position of the scalar. Compare how the highlighted exponents change from iteration to iteration. If we go back to elliptic curves over the real numbers, there is a nice geometric interpretation for the ECDLP: given a starting point P, we compute 2P, 3P, , dP = T, effectively hopping back and forth on the elliptic curve. We then publish the starting point P (a public parameter) and the final point T (the public key). In order to break the cryptosystem, an attacker has to figure out how often we "jumped" on the elliptic curve. The number of hops is the secret d. the private key. In practice, a and k are both in the range p almostequalto 2^150 ... 2^250, and computing T = a middot P and y_0 = k middot P is done using the Double-and-Add algorithm as shown in Sect. 9.2. 1. Illustrate how the algorithm works for a = 19 and for a = 160. Do not perform elliptic curve operation, but keep P a variable. 2. How many (i) point additions and (ii) point doublings are required on average for one "multiplication"? Assume that all integers have n = |log_2 p| bit. 3. Assume that all integers have n = 160 bit, i.e., p is a 160-bit prime. Assume one group operation (addition doubling) requires 20 mu sec. What is the time for one double-and-add operation? #1 P = 1_1 P # 1a P + P = 2P = 10_2 P # 1b 2P + P - 3P - 10_2 P + I_2 P - 11_2 P # 2a 3P + 3P = 2(11_2 P) = 110_2 P # 2b # 3a 6P + 6P = 12P = 2(110_2 P) = 1100_2 P #3b 12P - P = 13P = 1100_2 P + 1_2 P = 1101_2 P # 4a 13P + 13P = 26P = 2(1101_2 P) = 11010_2 P # 4b initial setting. bit processed: d_4 = 1 DOUBLE, bit processed: d_3 ADD, since d_3 - 1 DOUBLE, bit processed: d_2 no ADD, since d_2 = 0 DOUBLE, bit processed: d_1 ADD, since d_1 = 1 DOUBLE, bit processed: d_0 no ADD, since d_0 = 0 It is instructive to observe how the binary representation of the exponent evolves. We see that doubling results in a left shift of the scalar, with a 0 put in the rightmost position. By performing addition with P, a 1 is inserted into the rightmost position of the scalar. Compare how the highlighted exponents change from iteration to iteration. If we go back to elliptic curves over the real numbers, there is a nice geometric interpretation for the ECDLP: given a starting point P, we compute 2P, 3P, , dP = T, effectively hopping back and forth on the elliptic curve. We then publish the starting point P (a public parameter) and the final point T (the public key). In order to break the cryptosystem, an attacker has to figure out how often we "jumped" on the elliptic curve. The number of hops is the secret d. the private key. In practice, a and k are both in the range p almostequalto 2^150 ... 2^250, and computing T = a middot P and y_0 = k middot P is done using the Double-and-Add algorithm as shown in Sect. 9.2. 1. Illustrate how the algorithm works for a = 19 and for a = 160. Do not perform elliptic curve operation, but keep P a variable. 2. How many (i) point additions and (ii) point doublings are required on average for one "multiplication"? Assume that all integers have n = |log_2 p| bit. 3. Assume that all integers have n = 160 bit, i.e., p is a 160-bit prime. Assume one group operation (addition doubling) requires 20 mu sec. What is the time for one double-and-add operation