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

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.

We are given a discrete logarithm problem (DLOG) ( also called the index calculus ); That is given a, b, and P find x such that a = b^x mod P is held. The above is actually the multiplicative notation for finite field DLOG as used by OP. ECC DLOG is additive and has different notation as;

• That is given points A and the base B find x such that A = [x]B is held on the curve E(F_P). [x]B simply means that add the point B x-times to itself.

Compression

The beginning byte provides information about compression.

• 02 compression and choose y
• 03 compression and choose -y
• 04 No compression

To find the y, put the x into the curve equation and solve the quadratic residue by the Tonelli-Shanks algorithm.

---

In your case, both are given, no problem. Use the uncompressed public key.

The current record for secp256k1 is 114-bit On 16 June 2020 by Aleksander Zieniewic and they provided their software. So, if you don't have a low target, you cannot break the discrete log.

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

A point Q in the Elliptic curve when used affine coordinate system it has two coordinates as Q=(x,y) where x,y from the defining field (P in your case). When checking a point Q is either on the curve or not put x and y into the curve equation y^2 = x^3+ax+b and check the equality.

To uncompress insert the value of x into the equation x^3+ax+b mod P to get let say value a, then use the Tonelli-Shanks algorithm to find the square root of a in this equation y^2 = a mod P to find y and -y. According to compression value choose y or -y.

update per comment

I tried using the compressed public key but it was still bigger than mod p.

Compression a point requires information about what is the compression. Now you have given two forms of the public key a;

1. No compression: since the beginning starts with 04
2. Compression but choose the -y since starts wiht 03

Using capitals here not to confuse with hex a;

A = 04
4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa
385b6b1b8ead809ca67454d9683fcf2ba03456d6fe2c4abe2b07f0fbdbb2f1c1

A = 03
4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa

You can use the curve equation to derive the second part with chosen -y

And you can compare the coordinate values with

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0x4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa
if a>p:
    print("a")

or use yours eye and mind;

P   = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
x(A)= 4f355bdcb7cc0af728ef3cceb9615d90684bb5b2ca5f859ab0f0b704075871aa
y(A)= 385b6b1b8ead809ca67454d9683fcf2ba03456d6fe2c4abe2b07f0fbdbb2f1c1