Print Page - Elliptic curve point multiplication

Title: Elliptic curve point multiplication
Post by: qqq123 on April 28, 2012, 03:51:30 PM

First off, I hope this is the right place to post this.

I'm trying to figure out how to implement elliptic curve point multiplication in php, in order to convert a Bitcoin private key to a Bitcoin public key.

If you have any information about how to do this, or if you can help explain the algorithms used, even in pseudocode, that would be most helpful.

If someone knows php, I can show you what I have so far if that would help.

You can reference my post about this topic in the newbie forum here:
https://bitcointalk.org/index.php?topic=78132.0

Thanks for any help.

Title: Re: Elliptic curve point multiplication
Post by: kokjo on April 28, 2012, 03:59:35 PM

ever heard of wikipedia: http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

Title: Re: Elliptic curve point multiplication
Post by: qqq123 on April 28, 2012, 04:10:22 PM

Well yeah, but I'm having some trouble converting that poorly done and contradictory pseudocode into working code specific to the secp256k1 curve used by Bitcoin...

Thanks for your input.

Title: Re: Elliptic curve point multiplication
Post by: qqq123 on April 28, 2012, 04:22:50 PM

Good question.

I want to use php for two reasons.

1. I will probably use javascript as the first option, but php will be the backup in case the user has javascript disabled.
2. No one (I think, please tell me if you know otherwise) has ever implemented this in php, so if I do, hopefully someone else will have a use for it.

Title: Re: Elliptic curve point multiplication
Post by: qqq123 on April 29, 2012, 03:07:22 AM

I don't suppose anyone here knows php and modular arithmetic well enough to tell me what is wrong with my modular inversion code... It works with positive values, but not negative values.

Code:

function egcd($a, $b){
   $x = 0;
   $y = 1;
   $u = 1;
   $v = 0;
   while($a != 0){
      $q = bcdiv($b, $a);
      $r = bcmod($b, $a);
      $m = bcsub($x, bcmul($u, $q));
      $n = bcsub($y, bcmul($v, $q));
      $b = $a;
      $a = $r;
      $x = $u;
      $y = $v;
      $u = $m;
      $v = $n;
   }
   return array($b, $x, $y);
}
function modinv($a, $m){
   list($g, $x, $y) = egcd($a, $m);
   if($g != 1){
      return "modular inverse doesn't exist";
   }else{
      return bcmod($x, $m);
   }
}

So, modinv(-5, 17) returns "modular inverse doesn't exist". It should return 10. (That is the correct answer to -5^-1 mod 17.)

Thanks.

Title: Re: Elliptic curve point multiplication
Post by: grue on May 01, 2012, 12:30:31 AM

Quote from: znort987 on April 29, 2012, 05:20:38 AM

2. It truly saddens me that people are still using php to build websites.

why?

Title: Re: Elliptic curve point multiplication
Post by: someone42 on May 01, 2012, 05:37:50 AM

Quote from: qqq123 on April 29, 2012, 03:07:22 AM

I don't suppose anyone here knows php and modular arithmetic well enough to tell me what is wrong with my modular inversion code... It works with positive values, but not negative values.

The problem is probably originating from one of the calls to bcmod(). I don't know how php's bignum library does it, but modulus functions in any language can produce unexpected results when one of the operands is negative. You could workaround this by adding $m to $a (if $a is negative) in modinv().

Title: Re: Elliptic curve point multiplication
Post by: qqq123 on May 01, 2012, 02:21:06 PM

Thanks guys, I have taken care of all problems and now have a working ECDSA implementation in php.

As far as it being "impossible to build anything large and maintainable" with php, Wikipedia, Facebook, MediaWiki, Joomla, WordPress, Drupal, Digg, Baidu (I could go on) all use php, so...

Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: qqq123 on April 28, 2012, 03:51:30 PM