5

Pieter Wuille said:

[...](people often assume that no inverse for EC multiplication exists, which is true, but only to solve for k in k*P = Q; solving for P is possible).

When you multiply a scalar value by an EC point, you get an EC point. According to the above comment, it is possible to take the output point and derive the input point. How is this done? Does it require knowing k?

Note that I'm specifically not asking about extracting the scalar value (k) from the output point.

Also note that this wouldn't be useful to breaking Bitcoin signature algorithm - the generator that private keys are multiplied by is publicly known.

7

k is just a scalar, modulo the order of the elliptic curve group.

Q = k*P

thus:

(1/k)*Q = (1/k)*k*P

thus:

(1/k)*Q = P

You find P by multiplying Q with the multiplication inverse of k modulo the curve order.

  • 1
    ... where the inverse of k can be computed using the extended Euclidean algorithm. – Nate Eldredge Mar 9 '15 at 20:24
  • 2
    ... or by raising it to the (order-2)'th power modulo order (which is only allowed because order is prime in this case). – Pieter Wuille Mar 10 '15 at 12:47

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.