The aim of this question is to show that there are some groups in which the discrete logarithm problem (DLP) is easy. In

[answerhappygod]

The Aim Of This Question Is To Show That There Are Some Groups In Which The Discrete Logarithm Problem Dlp Is Easy In 1 (112.55 KiB) Viewed 44 times

The aim of this question is to show that there are some groups in which the discrete logarithm problem (DLP) is easy. In this example, we will consider the multiplicative group G whose elements are exactly the set Z where p is a prime and the multiplication operation is multiplication modulo p. In particular, p=2* + í for some positive integer t> 2. The number of elements in Zp, i.e., the order of the group, is 2. Recall that under DLP, we are given g and h such that g* = h (mod p) for some unknown I, and we need to find r. We will assume that g is a generator of this group. As an example, you may consider p = 28 +1 = 257. Then g = 3 is a generator of this group. (Hint: It might be helpful to run parts (a) through (d) with these example values first to understand what they mean.) (a) Show that g2' = 1 (mod p). (2 marks) (b) Show that the square root of g2" modulo p, i.e., g* = g24-4 = -1 (mod p). (2 marks) Since r is a number in the set {0,1,...,2"}, we can write r in binary as: r = bo 20+ b . 21 + b2 - 22 +.... + br. 24 (1) where b; are bits. If bo = 0, then I=b1-21 +52 - 22+...+b2 = 2y, for some integer y, i.e., x is an even number. On the other hand, if bo = 1, then 1=1+b12? + b2 - 22+...+b. 24 = 2y +1, for some integer y, i.e., I is an odd number. Let m= 2-1 (c) Show that if bo = 0, then (g")" =1 (mod p). (2 marks) (a) Show that if bo = 1, then (g)" =p-1 (mod p). (2 marks) (e) Let p=257, let g = 3 be the generator of the group Z357. Let g" = h = 130 (mod 257) be given. Using the above method, find the least significant bit (LSB) of r. Show your steps. (2 marks)