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