5.2 The Elliptic Curve Discrete Logarithm Problem PDF Print E-mail

 


 

In the multiplicative group Zp*, the discrete logarithm problem is: given elements r and q of the group, and a prime p, find a number k such that r = qk mod p. If the elliptic curve groups is described using multiplicative notation, then the elliptic curve discrete logarithm problem is: given points P and Q in the group, find a number that Pk = Q; k is called the discrete logarithm of Q to the base P. When the elliptic curve group is described using additive notation, the elliptic curve discrete logarithm problem is: given points P and Q in the group, find a number k such that Pk = Q

Example:

In the elliptic curve group defined by

y2 = x3 + 9x + 17 over F23,

What is the discrete logarithm k of Q = (4,5) to the base P = (16,5)?

One (naï­ve) way to find k is to compute multiples of P until Q is found. The first few multiples of P are:

P = (16,5) 2P = (20,20) 3P = (14,14) 4P = (19,20) 5P = (13,10) 6P = (7,3) 7P = (8,7) 8P = (12,17) 9P = (4,5)

Since 9P = (4,5) = Q, the discrete logarithm of Q to the base P is k = 9.

In a real application, k would be large enough such that it would be infeasible to determine k in this manner.

Next