15

From how I understand it, the equation for the public key is defined as so:

K = k * G

With K being the public key, k the private key and G the generator point.

  • Is G a constant? (as far as I read, it is a constant.)
  • If it is, how is it not possible to simply do K/G = k?
  • If it is not, how is it created out of the private key?
0

3 Answers 3

36

How I understood it, the equation for the public key is defined as so K = k * G With K being the public key, k the private key and G the generator point.

That's correct.

Now my first question, is G a constant? (as far as I read, it is a constant)

It is. It is the point with coordinates (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424). You can verify that these coordinates satisfy the curve equation: Y^2 = X^3 + 7 (mod 115792089237316195423570985008687907853269984665640564039457584007908834671663).

And if it is, how is it not possible to simply do K/G = k?

The answer is simply that we don't know of an efficient way to do "division" for elliptic curves (which is called the discrete logarithm problem), and it is assumed no such way can be found. The best known algorithm for doing this for this specific curve takes around 2128 iterations, an impossibly large amount.

You have to be aware that the * in k * G as you write it is no ordinary multiplication (what would that even mean for points?). It is a rather complicated operation, and people have figured out useful properties of it which are somewhat similar to multiplication (it forms a cyclic group, so the same symbol is used). But nobody ever found a way to perform the reverse operation, and this became the basis for elliptic curve cryptography.

1
  • This cleared up a lot for me. Thank you for the explanation and links! Dec 14, 2021 at 16:18
6

Mathematicians like their analogies, sometimes those analogies can be helpful, but they can equally be confusing, particularly to those new to a field.

In mathematics a "group" consists of a set of elements and an operator that satisfies some requirements. The operator must be associative, there must exist an identity element, and for every element there must exist an inverse element under the operator.

Some groups are written by analogy to addition, that is the group operator is represented by a "+" sign, and the identity element is represented by "0". Other groups are written by analogy to multiplication, that is the group operator is written as a multiplication operation (e.g. "*","." or nothing at all) and the identity element is represented by "1". Elliptic curves are traditionally written by analogy to addition.

We can conceive of applying the group operator repeatedly to k copies of G. If the group is written by analogy to addition then this is analogous to multiplication, if the group is written by analogy to multiplication then this is analogous to exponentiation.

So k * G refers not to regular multiplication but to an operation that is in a particular way analogous to multiplication.

You might naively think that this would take time proportional to k, but thanks to the associativity we can calculate it in time proportional to the logarithm of k. So we can quickly calculate k * G even for very large k.

Reversing the operation is not so easy though. The problem is known as the "Elliptic curve discrete logarithm problem" and the best known methods have a complexity proportional to roughly the square root of the number of elements in the group.

Why is it called the "Elliptic curve discrete logarithm problem" when it's more analogous to division than to a logarithm in the notation typically used for elliptic curves? because it's a variant of a similar problem studied for a group that is traditionally written by analogy to multiplication.

1
  • 1
    "Other groups are written by analogy to multiplication, that is the . Elliptic curves are traditionally written by analogy to addition." Probably a few words got eaten there. Also I suggest using the full name "discrete logarithm" rather than the abbreviated "discrete log" as it's not necessarily obvious to a profane what this "log" means.
    – Stef
    Dec 16, 2021 at 10:58
-1

k = K/G is somewhat misleading notation. In many ways, it's better to write k = K * G^-1. This emphasizes that there are two operations involved in "division": multiplication, and taking the inverse (Also, it makes it easier to recognize that K * G^-1 and G^-1 * K are distinct concepts and that the existence of G^-1 need to be shown to exist. This isn't as important here because elliptic curve multiplication is abelian and always has an inverse, but those are considerations that you need to keep in mind when dealing with groups and rings in general.)

Elliptic curve math takes place in an abstract group, not within the real number system, and using real number notation encourages misleading intuition (and in abstract algebra, the slash is used for quotient groups, not for dividing elements of a group). The fact that taking the inverse in elliptic curve math is hard is what makes it a cryptographic system in the first place. Otherwise, anyone who had the public key could invert the encryption rather trivially. "Cryptographic system" almost by definition refers to a system with some operation such that finding a*b is significantly easier than finding a^-1.

(There are ways of calculating K * G^-1 without explicitly calculating G^-1, but they're still as hard or harder than finding G^-1.)

And if it is not, how is it created out of the private key?

Huh? You just gave the equation for the public key: K = k * G.

Also, I think that you should include that you're talking about secp256k1 in the body of your text, rather than just as a tag. It might be inferred from this being the Bitcoin SE, but it's good for it to be explicit.

4
  • 2
    I find this explanation more confusion to be honest. G^-1 isn't a thing you can compute. What would its type be? Not a point, because then KG^-1 would be point^2, which doesn't exist. And not a scalar because then KG^-1 would be a point. You'd need to introduce a concept of "points inverted", which AFAIK doesn't exist, and also is unrelated to how K/G is actually computed in algorithms like Pollard's rho... which actually take in K and G as inputs - not just G - and output k. Dec 15, 2021 at 3:13
  • 2
    @PieterWuille: You're erroneously applying real arithmetic to abstract algebra, just as Accumulation warned against. The "type" of a product over an abstract group has units which are the product of the units of the two inputs, but the dimension is not so simple. For example, a 3-D vector cross product has 3-D just like both inputs, and a vector dot product yields a scalar no matter what the dimension of the inputs was. Another example: a square matrix has an inverse with the same dimension as itself, and that poses no problems when multiplying the inverted matrix by column vectors.
    – Ben Voigt
    Dec 15, 2021 at 19:49
  • 1
    The answer literally states "... but they're still as hard or harder than finding G^-1". This is, to the best of my knowledge, a false statement, as there is no known way of computing G^-1 (even ignoring the question of what its type would be). Algorithms for computing a discrete logarithm (= division of two group elements) take two group elements as input. They do not compute the inverse of one and then multiply it with the other. You could certainly define "inverse of a group element w.r.t. scalar multiplication" as some abstract object, but that isn't how you'd compute it. Dec 15, 2021 at 20:21
  • 2
    There is more wrong here. The inverse we're talking about is the inverse w.r.t. scalar multiplication (number times group element), not the inverse w.r.t. the group operation itself (group element plus group element). The latter exists for every element in every group (including non-abelian groups). The former however, if you'd want to define it, certainly does not exist for every element of an abelian group; it does for every non-zero element in secp because it's cyclic with prime order, but in general it won't exist for elements with non-maximal order in the group. Dec 15, 2021 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.