1<?php 2 3/** 4 * Curves over y^2 + x*y = x^3 + a*x^2 + b 5 * 6 * These are curves used in SEC 2 over prime fields: http://www.secg.org/SEC2-Ver-1.0.pdf 7 * The curve is a weierstrass curve with a[3] and a[2] set to 0. 8 * 9 * Uses Jacobian Coordinates for speed if able: 10 * 11 * https://en.wikipedia.org/wiki/Jacobian_curve 12 * https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates 13 * 14 * PHP version 5 and 7 15 * 16 * @category Crypt 17 * @package EC 18 * @author Jim Wigginton <terrafrost@php.net> 19 * @copyright 2017 Jim Wigginton 20 * @license http://www.opensource.org/licenses/mit-license.html MIT License 21 * @link http://pear.php.net/package/Math_BigInteger 22 */ 23 24namespace phpseclib3\Crypt\EC\BaseCurves; 25 26use phpseclib3\Math\BigInteger; 27use phpseclib3\Math\BinaryField; 28use phpseclib3\Math\BinaryField\Integer as BinaryInteger; 29 30/** 31 * Curves over y^2 + x*y = x^3 + a*x^2 + b 32 * 33 * @package Binary 34 * @author Jim Wigginton <terrafrost@php.net> 35 * @access public 36 */ 37class Binary extends Base 38{ 39 /** 40 * Binary Field Integer factory 41 * 42 * @var \phpseclib3\Math\BinaryField 43 */ 44 protected $factory; 45 46 /** 47 * Cofficient for x^1 48 * 49 * @var object 50 */ 51 protected $a; 52 53 /** 54 * Cofficient for x^0 55 * 56 * @var object 57 */ 58 protected $b; 59 60 /** 61 * Base Point 62 * 63 * @var object 64 */ 65 protected $p; 66 67 /** 68 * The number one over the specified finite field 69 * 70 * @var object 71 */ 72 protected $one; 73 74 /** 75 * The modulo 76 * 77 * @var BigInteger 78 */ 79 protected $modulo; 80 81 /** 82 * The Order 83 * 84 * @var BigInteger 85 */ 86 protected $order; 87 88 /** 89 * Sets the modulo 90 */ 91 public function setModulo(...$modulo) 92 { 93 $this->modulo = $modulo; 94 $this->factory = new BinaryField(...$modulo); 95 96 $this->one = $this->factory->newInteger("\1"); 97 } 98 99 /** 100 * Set coefficients a and b 101 * 102 * @param string $a 103 * @param string $b 104 */ 105 public function setCoefficients($a, $b) 106 { 107 if (!isset($this->factory)) { 108 throw new \RuntimeException('setModulo needs to be called before this method'); 109 } 110 $this->a = $this->factory->newInteger(pack('H*', $a)); 111 $this->b = $this->factory->newInteger(pack('H*', $b)); 112 } 113 114 /** 115 * Set x and y coordinates for the base point 116 * 117 * @param string|BinaryInteger $x 118 * @param string|BinaryInteger $y 119 */ 120 public function setBasePoint($x, $y) 121 { 122 switch (true) { 123 case !is_string($x) && !$x instanceof BinaryInteger: 124 throw new \UnexpectedValueException('Argument 1 passed to Binary::setBasePoint() must be a string or an instance of BinaryField\Integer'); 125 case !is_string($y) && !$y instanceof BinaryInteger: 126 throw new \UnexpectedValueException('Argument 2 passed to Binary::setBasePoint() must be a string or an instance of BinaryField\Integer'); 127 } 128 if (!isset($this->factory)) { 129 throw new \RuntimeException('setModulo needs to be called before this method'); 130 } 131 $this->p = [ 132 is_string($x) ? $this->factory->newInteger(pack('H*', $x)) : $x, 133 is_string($y) ? $this->factory->newInteger(pack('H*', $y)) : $y 134 ]; 135 } 136 137 /** 138 * Retrieve the base point as an array 139 * 140 * @return array 141 */ 142 public function getBasePoint() 143 { 144 if (!isset($this->factory)) { 145 throw new \RuntimeException('setModulo needs to be called before this method'); 146 } 147 /* 148 if (!isset($this->p)) { 149 throw new \RuntimeException('setBasePoint needs to be called before this method'); 150 } 151 */ 152 return $this->p; 153 } 154 155 /** 156 * Adds two points on the curve 157 * 158 * @return FiniteField[] 159 */ 160 public function addPoint(array $p, array $q) 161 { 162 if (!isset($this->factory)) { 163 throw new \RuntimeException('setModulo needs to be called before this method'); 164 } 165 166 if (!count($p) || !count($q)) { 167 if (count($q)) { 168 return $q; 169 } 170 if (count($p)) { 171 return $p; 172 } 173 return []; 174 } 175 176 if (!isset($p[2]) || !isset($q[2])) { 177 throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa'); 178 } 179 180 if ($p[0]->equals($q[0])) { 181 return !$p[1]->equals($q[1]) ? [] : $this->doublePoint($p); 182 } 183 184 // formulas from http://hyperelliptic.org/EFD/g12o/auto-shortw-jacobian.html 185 186 list($x1, $y1, $z1) = $p; 187 list($x2, $y2, $z2) = $q; 188 189 $o1 = $z1->multiply($z1); 190 $b = $x2->multiply($o1); 191 192 if ($z2->equals($this->one)) { 193 $d = $y2->multiply($o1)->multiply($z1); 194 $e = $x1->add($b); 195 $f = $y1->add($d); 196 $z3 = $e->multiply($z1); 197 $h = $f->multiply($x2)->add($z3->multiply($y2)); 198 $i = $f->add($z3); 199 $g = $z3->multiply($z3); 200 $p1 = $this->a->multiply($g); 201 $p2 = $f->multiply($i); 202 $p3 = $e->multiply($e)->multiply($e); 203 $x3 = $p1->add($p2)->add($p3); 204 $y3 = $i->multiply($x3)->add($g->multiply($h)); 205 206 return [$x3, $y3, $z3]; 207 } 208 209 $o2 = $z2->multiply($z2); 210 $a = $x1->multiply($o2); 211 $c = $y1->multiply($o2)->multiply($z2); 212 $d = $y2->multiply($o1)->multiply($z1); 213 $e = $a->add($b); 214 $f = $c->add($d); 215 $g = $e->multiply($z1); 216 $h = $f->multiply($x2)->add($g->multiply($y2)); 217 $z3 = $g->multiply($z2); 218 $i = $f->add($z3); 219 $p1 = $this->a->multiply($z3->multiply($z3)); 220 $p2 = $f->multiply($i); 221 $p3 = $e->multiply($e)->multiply($e); 222 $x3 = $p1->add($p2)->add($p3); 223 $y3 = $i->multiply($x3)->add($g->multiply($g)->multiply($h)); 224 225 return [$x3, $y3, $z3]; 226 } 227 228 /** 229 * Doubles a point on a curve 230 * 231 * @return FiniteField[] 232 */ 233 public function doublePoint(array $p) 234 { 235 if (!isset($this->factory)) { 236 throw new \RuntimeException('setModulo needs to be called before this method'); 237 } 238 239 if (!count($p)) { 240 return []; 241 } 242 243 if (!isset($p[2])) { 244 throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa'); 245 } 246 247 // formulas from http://hyperelliptic.org/EFD/g12o/auto-shortw-jacobian.html 248 249 list($x1, $y1, $z1) = $p; 250 251 $a = $x1->multiply($x1); 252 $b = $a->multiply($a); 253 254 if ($z1->equals($this->one)) { 255 $x3 = $b->add($this->b); 256 $z3 = clone $x1; 257 $p1 = $a->add($y1)->add($z3)->multiply($this->b); 258 $p2 = $a->add($y1)->multiply($b); 259 $y3 = $p1->add($p2); 260 261 return [$x3, $y3, $z3]; 262 } 263 264 $c = $z1->multiply($z1); 265 $d = $c->multiply($c); 266 $x3 = $b->add($this->b->multiply($d->multiply($d))); 267 $z3 = $x1->multiply($c); 268 $p1 = $b->multiply($z3); 269 $p2 = $a->add($y1->multiply($z1))->add($z3)->multiply($x3); 270 $y3 = $p1->add($p2); 271 272 return [$x3, $y3, $z3]; 273 } 274 275 /** 276 * Returns the X coordinate and the derived Y coordinate 277 * 278 * Not supported because it is covered by patents. 279 * Quoting https://www.openssl.org/docs/man1.1.0/apps/ecparam.html , 280 * 281 * "Due to patent issues the compressed option is disabled by default for binary curves 282 * and can be enabled by defining the preprocessor macro OPENSSL_EC_BIN_PT_COMP at 283 * compile time." 284 * 285 * @return array 286 */ 287 public function derivePoint($m) 288 { 289 throw new \RuntimeException('Point compression on binary finite field elliptic curves is not supported'); 290 } 291 292 /** 293 * Tests whether or not the x / y values satisfy the equation 294 * 295 * @return boolean 296 */ 297 public function verifyPoint(array $p) 298 { 299 list($x, $y) = $p; 300 $lhs = $y->multiply($y); 301 $lhs = $lhs->add($x->multiply($y)); 302 $x2 = $x->multiply($x); 303 $x3 = $x2->multiply($x); 304 $rhs = $x3->add($this->a->multiply($x2))->add($this->b); 305 306 return $lhs->equals($rhs); 307 } 308 309 /** 310 * Returns the modulo 311 * 312 * @return \phpseclib3\Math\BigInteger 313 */ 314 public function getModulo() 315 { 316 return $this->modulo; 317 } 318 319 /** 320 * Returns the a coefficient 321 * 322 * @return \phpseclib3\Math\PrimeField\Integer 323 */ 324 public function getA() 325 { 326 return $this->a; 327 } 328 329 /** 330 * Returns the a coefficient 331 * 332 * @return \phpseclib3\Math\PrimeField\Integer 333 */ 334 public function getB() 335 { 336 return $this->b; 337 } 338 339 /** 340 * Returns the affine point 341 * 342 * A Jacobian Coordinate is of the form (x, y, z). 343 * To convert a Jacobian Coordinate to an Affine Point 344 * you do (x / z^2, y / z^3) 345 * 346 * @return \phpseclib3\Math\PrimeField\Integer[] 347 */ 348 public function convertToAffine(array $p) 349 { 350 if (!isset($p[2])) { 351 return $p; 352 } 353 list($x, $y, $z) = $p; 354 $z = $this->one->divide($z); 355 $z2 = $z->multiply($z); 356 return [ 357 $x->multiply($z2), 358 $y->multiply($z2)->multiply($z) 359 ]; 360 } 361 362 /** 363 * Converts an affine point to a jacobian coordinate 364 * 365 * @return \phpseclib3\Math\PrimeField\Integer[] 366 */ 367 public function convertToInternal(array $p) 368 { 369 if (isset($p[2])) { 370 return $p; 371 } 372 373 $p[2] = clone $this->one; 374 $p['fresh'] = true; 375 return $p; 376 } 377} 378