Elliptic curve point multiplication

[qqq123]

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.

[kokjo]

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

[qqq123]

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.

[qqq123]

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.

[qqq123]

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.

[grue]

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

why?

[someone42]

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().

[qqq123]

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...