1<?php 2 3/** 4 * Prime Finite Fields 5 * 6 * PHP version 5 and 7 7 * 8 * @category Math 9 * @package BigInteger 10 * @author Jim Wigginton <terrafrost@php.net> 11 * @copyright 2017 Jim Wigginton 12 * @license http://www.opensource.org/licenses/mit-license.html MIT License 13 */ 14 15namespace phpseclib3\Math\PrimeField; 16 17use ParagonIE\ConstantTime\Hex; 18use phpseclib3\Math\BigInteger; 19use phpseclib3\Math\Common\FiniteField\Integer as Base; 20 21/** 22 * Prime Finite Fields 23 * 24 * @package Math 25 * @author Jim Wigginton <terrafrost@php.net> 26 * @access public 27 */ 28class Integer extends Base 29{ 30 /** 31 * Holds the PrimeField's value 32 * 33 * @var BigInteger 34 */ 35 protected $value; 36 37 /** 38 * Keeps track of current instance 39 * 40 * @var int 41 */ 42 protected $instanceID; 43 44 /** 45 * Holds the PrimeField's modulo 46 * 47 * @var array<int, BigInteger> 48 */ 49 protected static $modulo; 50 51 /** 52 * Holds a pre-generated function to perform modulo reductions 53 * 54 * @var array<int, callable(BigInteger):BigInteger> 55 */ 56 protected static $reduce; 57 58 /** 59 * Zero 60 * 61 * @var BigInteger 62 */ 63 protected static $zero; 64 65 /** 66 * Default constructor 67 * 68 * @param int $instanceID 69 */ 70 public function __construct($instanceID, BigInteger $num = null) 71 { 72 $this->instanceID = $instanceID; 73 if (!isset($num)) { 74 $this->value = clone static::$zero[static::class]; 75 } else { 76 $reduce = static::$reduce[$instanceID]; 77 $this->value = $reduce($num); 78 } 79 } 80 81 /** 82 * Set the modulo for a given instance 83 * 84 * @param int $instanceID 85 * @return void 86 */ 87 public static function setModulo($instanceID, BigInteger $modulo) 88 { 89 static::$modulo[$instanceID] = $modulo; 90 } 91 92 /** 93 * Set the modulo for a given instance 94 * 95 * @param int $instanceID 96 * @return void 97 */ 98 public static function setRecurringModuloFunction($instanceID, callable $function) 99 { 100 static::$reduce[$instanceID] = $function; 101 if (!isset(static::$zero[static::class])) { 102 static::$zero[static::class] = new BigInteger(); 103 } 104 } 105 106 /** 107 * Delete the modulo for a given instance 108 */ 109 public static function cleanupCache($instanceID) 110 { 111 unset(static::$modulo[$instanceID]); 112 unset(static::$reduce[$instanceID]); 113 } 114 115 /** 116 * Returns the modulo 117 * 118 * @param int $instanceID 119 * @return BigInteger 120 */ 121 public static function getModulo($instanceID) 122 { 123 return static::$modulo[$instanceID]; 124 } 125 126 /** 127 * Tests a parameter to see if it's of the right instance 128 * 129 * Throws an exception if the incorrect class is being utilized 130 * 131 * @return void 132 */ 133 public static function checkInstance(self $x, self $y) 134 { 135 if ($x->instanceID != $y->instanceID) { 136 throw new \UnexpectedValueException('The instances of the two PrimeField\Integer objects do not match'); 137 } 138 } 139 140 /** 141 * Tests the equality of two numbers. 142 * 143 * @return bool 144 */ 145 public function equals(self $x) 146 { 147 static::checkInstance($this, $x); 148 149 return $this->value->equals($x->value); 150 } 151 152 /** 153 * Compares two numbers. 154 * 155 * @return int 156 */ 157 public function compare(self $x) 158 { 159 static::checkInstance($this, $x); 160 161 return $this->value->compare($x->value); 162 } 163 164 /** 165 * Adds two PrimeFieldIntegers. 166 * 167 * @return static 168 */ 169 public function add(self $x) 170 { 171 static::checkInstance($this, $x); 172 173 $temp = new static($this->instanceID); 174 $temp->value = $this->value->add($x->value); 175 if ($temp->value->compare(static::$modulo[$this->instanceID]) >= 0) { 176 $temp->value = $temp->value->subtract(static::$modulo[$this->instanceID]); 177 } 178 179 return $temp; 180 } 181 182 /** 183 * Subtracts two PrimeFieldIntegers. 184 * 185 * @return static 186 */ 187 public function subtract(self $x) 188 { 189 static::checkInstance($this, $x); 190 191 $temp = new static($this->instanceID); 192 $temp->value = $this->value->subtract($x->value); 193 if ($temp->value->isNegative()) { 194 $temp->value = $temp->value->add(static::$modulo[$this->instanceID]); 195 } 196 197 return $temp; 198 } 199 200 /** 201 * Multiplies two PrimeFieldIntegers. 202 * 203 * @return static 204 */ 205 public function multiply(self $x) 206 { 207 static::checkInstance($this, $x); 208 209 return new static($this->instanceID, $this->value->multiply($x->value)); 210 } 211 212 /** 213 * Divides two PrimeFieldIntegers. 214 * 215 * @return static 216 */ 217 public function divide(self $x) 218 { 219 static::checkInstance($this, $x); 220 221 $denominator = $x->value->modInverse(static::$modulo[$this->instanceID]); 222 return new static($this->instanceID, $this->value->multiply($denominator)); 223 } 224 225 /** 226 * Performs power operation on a PrimeFieldInteger. 227 * 228 * @return static 229 */ 230 public function pow(BigInteger $x) 231 { 232 $temp = new static($this->instanceID); 233 $temp->value = $this->value->powMod($x, static::$modulo[$this->instanceID]); 234 235 return $temp; 236 } 237 238 /** 239 * Calculates the square root 240 * 241 * @link https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm 242 * @return static|false 243 */ 244 public function squareRoot() 245 { 246 static $one, $two; 247 if (!isset($one)) { 248 $one = new BigInteger(1); 249 $two = new BigInteger(2); 250 } 251 $reduce = static::$reduce[$this->instanceID]; 252 $p_1 = static::$modulo[$this->instanceID]->subtract($one); 253 $q = clone $p_1; 254 $s = BigInteger::scan1divide($q); 255 list($pow) = $p_1->divide($two); 256 for ($z = $one; !$z->equals(static::$modulo[$this->instanceID]); $z = $z->add($one)) { 257 $temp = $z->powMod($pow, static::$modulo[$this->instanceID]); 258 if ($temp->equals($p_1)) { 259 break; 260 } 261 } 262 263 $m = new BigInteger($s); 264 $c = $z->powMod($q, static::$modulo[$this->instanceID]); 265 $t = $this->value->powMod($q, static::$modulo[$this->instanceID]); 266 list($temp) = $q->add($one)->divide($two); 267 $r = $this->value->powMod($temp, static::$modulo[$this->instanceID]); 268 269 while (!$t->equals($one)) { 270 $i = clone $one; 271 272 while (!$t->powMod($two->pow($i), static::$modulo[$this->instanceID])->equals($one)) { 273 $i = $i->add($one); 274 } 275 276 if ($i->compare($m) >= 0) { 277 return false; 278 } 279 $b = $c->powMod($two->pow($m->subtract($i)->subtract($one)), static::$modulo[$this->instanceID]); 280 $m = $i; 281 $c = $reduce($b->multiply($b)); 282 $t = $reduce($t->multiply($c)); 283 $r = $reduce($r->multiply($b)); 284 } 285 286 return new static($this->instanceID, $r); 287 } 288 289 /** 290 * Is Odd? 291 * 292 * @return bool 293 */ 294 public function isOdd() 295 { 296 return $this->value->isOdd(); 297 } 298 299 /** 300 * Negate 301 * 302 * A negative number can be written as 0-12. With modulos, 0 is the same thing as the modulo 303 * so 0-12 is the same thing as modulo-12 304 * 305 * @return static 306 */ 307 public function negate() 308 { 309 return new static($this->instanceID, static::$modulo[$this->instanceID]->subtract($this->value)); 310 } 311 312 /** 313 * Converts an Integer to a byte string (eg. base-256). 314 * 315 * @return string 316 */ 317 public function toBytes() 318 { 319 $length = static::$modulo[$this->instanceID]->getLengthInBytes(); 320 return str_pad($this->value->toBytes(), $length, "\0", STR_PAD_LEFT); 321 } 322 323 /** 324 * Converts an Integer to a hex string (eg. base-16). 325 * 326 * @return string 327 */ 328 public function toHex() 329 { 330 return Hex::encode($this->toBytes()); 331 } 332 333 /** 334 * Converts an Integer to a bit string (eg. base-2). 335 * 336 * @return string 337 */ 338 public function toBits() 339 { 340 // return $this->value->toBits(); 341 static $length; 342 if (!isset($length)) { 343 $length = static::$modulo[$this->instanceID]->getLength(); 344 } 345 346 return str_pad($this->value->toBits(), $length, '0', STR_PAD_LEFT); 347 } 348 349 /** 350 * Returns the w-ary non-adjacent form (wNAF) 351 * 352 * @param int $w optional 353 * @return array<int, int> 354 */ 355 public function getNAF($w = 1) 356 { 357 $w++; 358 359 $mask = new BigInteger((1 << $w) - 1); 360 $sub = new BigInteger(1 << $w); 361 //$sub = new BigInteger(1 << ($w - 1)); 362 $d = $this->toBigInteger(); 363 $d_i = []; 364 365 $i = 0; 366 while ($d->compare(static::$zero[static::class]) > 0) { 367 if ($d->isOdd()) { 368 // start mods 369 370 $bigInteger = $d->testBit($w - 1) ? 371 $d->bitwise_and($mask)->subtract($sub) : 372 //$sub->subtract($d->bitwise_and($mask)) : 373 $d->bitwise_and($mask); 374 // end mods 375 $d = $d->subtract($bigInteger); 376 $d_i[$i] = (int) $bigInteger->toString(); 377 } else { 378 $d_i[$i] = 0; 379 } 380 $shift = !$d->equals(static::$zero[static::class]) && $d->bitwise_and($mask)->equals(static::$zero[static::class]) ? $w : 1; // $w or $w + 1? 381 $d = $d->bitwise_rightShift($shift); 382 while (--$shift > 0) { 383 $d_i[++$i] = 0; 384 } 385 $i++; 386 } 387 388 return $d_i; 389 } 390 391 /** 392 * Converts an Integer to a BigInteger 393 * 394 * @return BigInteger 395 */ 396 public function toBigInteger() 397 { 398 return clone $this->value; 399 } 400 401 /** 402 * __toString() magic method 403 * 404 * @access public 405 * @return string 406 */ 407 public function __toString() 408 { 409 return (string) $this->value; 410 } 411 412 /** 413 * __debugInfo() magic method 414 * 415 * @access public 416 * @return array 417 */ 418 public function __debugInfo() 419 { 420 return ['value' => $this->toHex()]; 421 } 422} 423