Bitcoin Forum
December 05, 2016, 02:41:59 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Elliptic curve point multiplication  (Read 1943 times)
qqq123
Newbie
*
Offline Offline

Activity: 11


View Profile
April 28, 2012, 03:51:30 PM
 #1

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.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480905719
Hero Member
*
Offline Offline

Posts: 1480905719

View Profile Personal Message (Offline)

Ignore
1480905719
Reply with quote  #2

1480905719
Report to moderator
1480905719
Hero Member
*
Offline Offline

Posts: 1480905719

View Profile Personal Message (Offline)

Ignore
1480905719
Reply with quote  #2

1480905719
Report to moderator
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
April 28, 2012, 03:59:35 PM
 #2

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

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
qqq123
Newbie
*
Offline Offline

Activity: 11


View Profile
April 28, 2012, 04:10:22 PM
 #3

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
Newbie
*
Offline Offline

Activity: 11


View Profile
April 28, 2012, 04:22:50 PM
 #4

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
Newbie
*
Offline Offline

Activity: 11


View Profile
April 29, 2012, 03:07:22 AM
 #5

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
Global Moderator
Legendary
*
Offline Offline

Activity: 1932



View Profile
May 01, 2012, 12:30:31 AM
 #6

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

It is pitch black. You are likely to be eaten by a grue.

Tired of annoying signature ads? Ad block for signatures
someone42
Member
**
Offline Offline

Activity: 78

Chris Chua


View Profile
May 01, 2012, 05:37:50 AM
 #7

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
Newbie
*
Offline Offline

Activity: 11


View Profile
May 01, 2012, 02:21:06 PM
 #8

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...
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!