Public key Exceeding Mod P? A Clarification Request On The Discrete Logarithm Problem

Question

I tried to observe / implement the discrete logarithm problem but I noticed something about it; but before I get into it let me give some clarification which is open to correction.

a = b^x mod P

Where as

a = the public key of the address;

b = the generator point of the secp256k1 koblitz curve (this is the curve in context);

x = the discrete log;

P = the modular integer.

I coupled all parameters below:

A = 044f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa385b6b1b8ead809ca67454d9683fcf2ba03456d6fe2c4abe2b07f0fbdbb2f1c1 (uncompressed public key)
034f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa : (compressed public key)

B = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8 (uncompressed generator point)

02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 (compress generator point)

X = ?

P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

I don't actually know what part of the parameters I should use ( compressed or uncompressed)

N. B : I tried the uncompressed public key to Mod P but the uncompressed public key exceeded the Mod P in size.

What should I do about this?

Answer 1

It is important to note that the Elliptic Curve Discrete Logarithm Problem (ECDLP) is slightly different from the normal Discrete Logarithm Problem (DLP).

In DLP, the ^ operator is actually exponentiation and it is operating on integers so mod p is just the normal modulus. However for ECDLP, ^ is actually elliptic curve point multiplication. This is different from exponentiation and is a much more involved process. You also cannot mod p with a point because they are not integers. While there is a modulo, it is part of the point multiplication process itself.

The compressedness of the parameters you use does not really matter. In the end, the compression is just the encoding of a point. You need to parse this encoding to determine the X and Y coordinates of the point; both uncompressed and compressed allow you to determine them. The uncompressed just gives you the X and Y coordinates directly while the compressed one gives you the X and whether Y is even or odd so that you can compute the correct Y coordinate. When you do the point multiplication, you are not handling the encoded point as an integer and just multiplying it with x. You are doing elliptic curve point multiplication which is way more complicated.