Subversion Repositories oidplus

Rev

Rev 846 | Rev 1042 | 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.  * @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.  
  15. namespace phpseclib3\Math\PrimeField;
  16.  
  17. use ParagonIE\ConstantTime\Hex;
  18. use phpseclib3\Math\BigInteger;
  19. use 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.  */
  28. class 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.