Subversion Repositories oidplus

Rev

Rev 1042 | Rev 1339 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

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