1<?php 2 3/** 4 * Generalized Koblitz Curves over y^2 = x^3 + b. 5 * 6 * According to http://www.secg.org/SEC2-Ver-1.0.pdf Koblitz curves are over the GF(2**m) 7 * finite field. Both the $a$ and $b$ coefficients are either 0 or 1. However, SEC2 8 * generalizes the definition to include curves over GF(P) "which possess an efficiently 9 * computable endomorphism". 10 * 11 * For these generalized Koblitz curves $b$ doesn't have to be 0 or 1. Whether or not $a$ 12 * has any restrictions on it is unclear, however, for all the GF(P) Koblitz curves defined 13 * in SEC2 v1.0 $a$ is $0$ so all of the methods defined herein will assume that it is. 14 * 15 * I suppose we could rename the $b$ coefficient to $a$, however, the documentation refers 16 * to $b$ so we'll just keep it. 17 * 18 * If a later version of SEC2 comes out wherein some $a$ values are non-zero we can create a 19 * new method for those. eg. KoblitzA1Prime.php or something. 20 * 21 * PHP version 5 and 7 22 * 23 * @category Crypt 24 * @package EC 25 * @author Jim Wigginton <terrafrost@php.net> 26 * @copyright 2017 Jim Wigginton 27 * @license http://www.opensource.org/licenses/mit-license.html MIT License 28 * @link http://pear.php.net/package/Math_BigInteger 29 */ 30 31namespace phpseclib3\Crypt\EC\BaseCurves; 32 33use phpseclib3\Math\BigInteger; 34use phpseclib3\Math\PrimeField; 35 36/** 37 * Curves over y^2 = x^3 + b 38 * 39 * @package KoblitzPrime 40 * @author Jim Wigginton <terrafrost@php.net> 41 * @access public 42 */ 43class KoblitzPrime extends Prime 44{ 45 // don't overwrite setCoefficients() with one that only accepts one parameter so that 46 // one might be able to switch between KoblitzPrime and Prime more easily (for benchmarking 47 // purposes). 48 49 /** 50 * Multiply and Add Points 51 * 52 * Uses a efficiently computable endomorphism to achieve a slight speedup 53 * 54 * Adapted from https://git.io/vxbrP 55 * 56 * @return int[] 57 */ 58 public function multiplyAddPoints(array $points, array $scalars) 59 { 60 static $zero, $one, $two; 61 if (!isset($two)) { 62 $two = new BigInteger(2); 63 $one = new BigInteger(1); 64 } 65 66 if (!isset($this->beta)) { 67 // get roots 68 $inv = $this->one->divide($this->two)->negate(); 69 $s = $this->three->negate()->squareRoot()->multiply($inv); 70 $betas = [ 71 $inv->add($s), 72 $inv->subtract($s) 73 ]; 74 $this->beta = $betas[0]->compare($betas[1]) < 0 ? $betas[0] : $betas[1]; 75 //echo strtoupper($this->beta->toHex(true)) . "\n"; exit; 76 } 77 78 if (!isset($this->basis)) { 79 $factory = new PrimeField($this->order); 80 $tempOne = $factory->newInteger($one); 81 $tempTwo = $factory->newInteger($two); 82 $tempThree = $factory->newInteger(new BigInteger(3)); 83 84 $inv = $tempOne->divide($tempTwo)->negate(); 85 $s = $tempThree->negate()->squareRoot()->multiply($inv); 86 87 $lambdas = [ 88 $inv->add($s), 89 $inv->subtract($s) 90 ]; 91 92 $lhs = $this->multiplyPoint($this->p, $lambdas[0])[0]; 93 $rhs = $this->p[0]->multiply($this->beta); 94 $lambda = $lhs->equals($rhs) ? $lambdas[0] : $lambdas[1]; 95 96 $this->basis = static::extendedGCD($lambda->toBigInteger(), $this->order); 97 ///* 98 foreach ($this->basis as $basis) { 99 echo strtoupper($basis['a']->toHex(true)) . "\n"; 100 echo strtoupper($basis['b']->toHex(true)) . "\n\n"; 101 } 102 exit; 103 //*/ 104 } 105 106 $npoints = $nscalars = []; 107 for ($i = 0; $i < count($points); $i++) { 108 $p = $points[$i]; 109 $k = $scalars[$i]->toBigInteger(); 110 111 // begin split 112 list($v1, $v2) = $this->basis; 113 114 $c1 = $v2['b']->multiply($k); 115 list($c1, $r) = $c1->divide($this->order); 116 if ($this->order->compare($r->multiply($two)) <= 0) { 117 $c1 = $c1->add($one); 118 } 119 120 $c2 = $v1['b']->negate()->multiply($k); 121 list($c2, $r) = $c2->divide($this->order); 122 if ($this->order->compare($r->multiply($two)) <= 0) { 123 $c2 = $c2->add($one); 124 } 125 126 $p1 = $c1->multiply($v1['a']); 127 $p2 = $c2->multiply($v2['a']); 128 $q1 = $c1->multiply($v1['b']); 129 $q2 = $c2->multiply($v2['b']); 130 131 $k1 = $k->subtract($p1)->subtract($p2); 132 $k2 = $q1->add($q2)->negate(); 133 // end split 134 135 $beta = [ 136 $p[0]->multiply($this->beta), 137 $p[1], 138 clone $this->one 139 ]; 140 141 if (isset($p['naf'])) { 142 $beta['naf'] = array_map(function ($p) { 143 return [ 144 $p[0]->multiply($this->beta), 145 $p[1], 146 clone $this->one 147 ]; 148 }, $p['naf']); 149 $beta['nafwidth'] = $p['nafwidth']; 150 } 151 152 if ($k1->isNegative()) { 153 $k1 = $k1->negate(); 154 $p = $this->negatePoint($p); 155 } 156 157 if ($k2->isNegative()) { 158 $k2 = $k2->negate(); 159 $beta = $this->negatePoint($beta); 160 } 161 162 $pos = 2 * $i; 163 $npoints[$pos] = $p; 164 $nscalars[$pos] = $this->factory->newInteger($k1); 165 166 $pos++; 167 $npoints[$pos] = $beta; 168 $nscalars[$pos] = $this->factory->newInteger($k2); 169 } 170 171 return parent::multiplyAddPoints($npoints, $nscalars); 172 } 173 174 /** 175 * Returns the numerator and denominator of the slope 176 * 177 * @return FiniteField[] 178 */ 179 protected function doublePointHelper(array $p) 180 { 181 $numerator = $this->three->multiply($p[0])->multiply($p[0]); 182 $denominator = $this->two->multiply($p[1]); 183 return [$numerator, $denominator]; 184 } 185 186 /** 187 * Doubles a jacobian coordinate on the curve 188 * 189 * See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l 190 * 191 * @return FiniteField[] 192 */ 193 protected function jacobianDoublePoint(array $p) 194 { 195 list($x1, $y1, $z1) = $p; 196 $a = $x1->multiply($x1); 197 $b = $y1->multiply($y1); 198 $c = $b->multiply($b); 199 $d = $x1->add($b); 200 $d = $d->multiply($d)->subtract($a)->subtract($c)->multiply($this->two); 201 $e = $this->three->multiply($a); 202 $f = $e->multiply($e); 203 $x3 = $f->subtract($this->two->multiply($d)); 204 $y3 = $e->multiply($d->subtract($x3))->subtract( 205 $this->eight->multiply($c) 206 ); 207 $z3 = $this->two->multiply($y1)->multiply($z1); 208 return [$x3, $y3, $z3]; 209 } 210 211 /** 212 * Doubles a "fresh" jacobian coordinate on the curve 213 * 214 * See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-mdbl-2007-bl 215 * 216 * @return FiniteField[] 217 */ 218 protected function jacobianDoublePointMixed(array $p) 219 { 220 list($x1, $y1) = $p; 221 $xx = $x1->multiply($x1); 222 $yy = $y1->multiply($y1); 223 $yyyy = $yy->multiply($yy); 224 $s = $x1->add($yy); 225 $s = $s->multiply($s)->subtract($xx)->subtract($yyyy)->multiply($this->two); 226 $m = $this->three->multiply($xx); 227 $t = $m->multiply($m)->subtract($this->two->multiply($s)); 228 $x3 = $t; 229 $y3 = $s->subtract($t); 230 $y3 = $m->multiply($y3)->subtract($this->eight->multiply($yyyy)); 231 $z3 = $this->two->multiply($y1); 232 return [$x3, $y3, $z3]; 233 } 234 235 /** 236 * Tests whether or not the x / y values satisfy the equation 237 * 238 * @return boolean 239 */ 240 public function verifyPoint(array $p) 241 { 242 list($x, $y) = $p; 243 $lhs = $y->multiply($y); 244 $temp = $x->multiply($x)->multiply($x); 245 $rhs = $temp->add($this->b); 246 247 return $lhs->equals($rhs); 248 } 249 250 /** 251 * Calculates the parameters needed from the Euclidean algorithm as discussed at 252 * http://diamond.boisestate.edu/~liljanab/MATH308/GuideToECC.pdf#page=148 253 * 254 * @param BigInteger $u 255 * @param BigInteger $v 256 * @return BigInteger[] 257 */ 258 protected static function extendedGCD(BigInteger $u, BigInteger $v) 259 { 260 $one = new BigInteger(1); 261 $zero = new BigInteger(); 262 263 $a = clone $one; 264 $b = clone $zero; 265 $c = clone $zero; 266 $d = clone $one; 267 268 $stop = $v->bitwise_rightShift($v->getLength() >> 1); 269 270 $a1 = clone $zero; 271 $b1 = clone $zero; 272 $a2 = clone $zero; 273 $b2 = clone $zero; 274 275 $postGreatestIndex = 0; 276 277 while (!$v->equals($zero)) { 278 list($q) = $u->divide($v); 279 280 $temp = $u; 281 $u = $v; 282 $v = $temp->subtract($v->multiply($q)); 283 284 $temp = $a; 285 $a = $c; 286 $c = $temp->subtract($a->multiply($q)); 287 288 $temp = $b; 289 $b = $d; 290 $d = $temp->subtract($b->multiply($q)); 291 292 if ($v->compare($stop) > 0) { 293 $a0 = $v; 294 $b0 = $c; 295 } else { 296 $postGreatestIndex++; 297 } 298 299 if ($postGreatestIndex == 1) { 300 $a1 = $v; 301 $b1 = $c->negate(); 302 } 303 304 if ($postGreatestIndex == 2) { 305 $rhs = $a0->multiply($a0)->add($b0->multiply($b0)); 306 $lhs = $v->multiply($v)->add($b->multiply($b)); 307 if ($lhs->compare($rhs) <= 0) { 308 $a2 = $a0; 309 $b2 = $b0->negate(); 310 } else { 311 $a2 = $v; 312 $b2 = $c->negate(); 313 } 314 315 break; 316 } 317 } 318 319 return [ 320 ['a' => $a1, 'b' => $b1], 321 ['a' => $a2, 'b' => $b2] 322 ]; 323 } 324} 325