[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * PHP Barrett Modular Exponentiation Engine
   5   *
   6   * PHP version 5 and 7
   7   *
   8   * @category  Math
   9   * @package   BigInteger
  10   * @author    Jim Wigginton <[email protected]>
  11   * @copyright 2017 Jim Wigginton
  12   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  13   * @link      http://pear.php.net/package/Math_BigInteger
  14   */
  15  
  16  namespace phpseclib3\Math\BigInteger\Engines\PHP\Reductions;
  17  
  18  use phpseclib3\Math\BigInteger\Engines\PHP;
  19  use phpseclib3\Math\BigInteger\Engines\PHP\Base;
  20  
  21  /**
  22   * PHP Barrett Modular Exponentiation Engine
  23   *
  24   * @package PHP
  25   * @author  Jim Wigginton <[email protected]>
  26   * @access  public
  27   */
  28  abstract class Barrett extends Base
  29  {
  30      /**
  31       * Barrett Modular Reduction
  32       *
  33       * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
  34       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
  35       * so as not to require negative numbers (initially, this script didn't support negative numbers).
  36       *
  37       * Employs "folding", as described at
  38       * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
  39       * it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x."
  40       *
  41       * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
  42       * usable on account of (1) its not using reasonable radix points as discussed in
  43       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
  44       * radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
  45       * (x >> 1) + (x >> 1) != x / 2 + x / 2.  If x is even, they're the same, but if x is odd, they're not.  See the in-line
  46       * comments for details.
  47       *
  48       * @param array $n
  49       * @param array $m
  50       * @param class-string<PHP> $class
  51       * @return array
  52       */
  53      protected static function reduce(array $n, array $m, $class)
  54      {
  55          static $cache = [
  56              self::VARIABLE => [],
  57              self::DATA => []
  58          ];
  59  
  60          $m_length = count($m);
  61  
  62          // if (self::compareHelper($n, $static::square($m)) >= 0) {
  63          if (count($n) > 2 * $m_length) {
  64              $lhs = new $class();
  65              $rhs = new $class();
  66              $lhs->value = $n;
  67              $rhs->value = $m;
  68              list(, $temp) = $lhs->divide($rhs);
  69              return $temp->value;
  70          }
  71  
  72          // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
  73          if ($m_length < 5) {
  74              return self::regularBarrett($n, $m, $class);
  75          }
  76          // n = 2 * m.length
  77  
  78          if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
  79              $key = count($cache[self::VARIABLE]);
  80              $cache[self::VARIABLE][] = $m;
  81  
  82              $lhs = new $class();
  83              $lhs_value = &$lhs->value;
  84              $lhs_value = self::array_repeat(0, $m_length + ($m_length >> 1));
  85              $lhs_value[] = 1;
  86              $rhs = new $class();
  87              $rhs->value = $m;
  88  
  89              list($u, $m1) = $lhs->divide($rhs);
  90              $u = $u->value;
  91              $m1 = $m1->value;
  92  
  93              $cache[self::DATA][] = [
  94                  'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
  95                  'm1' => $m1 // m.length
  96              ];
  97          } else {
  98              extract($cache[self::DATA][$key]);
  99          }
 100  
 101          $cutoff = $m_length + ($m_length >> 1);
 102          $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
 103          $msd = array_slice($n, $cutoff);    // m.length >> 1
 104  
 105          $lsd = self::trim($lsd);
 106          $temp = $class::multiplyHelper($msd, false, $m1, false); // m.length + (m.length >> 1)
 107          $n = $class::addHelper($lsd, false, $temp[self::VALUE], false); // m.length + (m.length >> 1) + 1 (so basically we're adding two same length numbers)
 108          //if ($m_length & 1) {
 109          //    return self::regularBarrett($n[self::VALUE], $m, $class);
 110          //}
 111  
 112          // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
 113          $temp = array_slice($n[self::VALUE], $m_length - 1);
 114          // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
 115          // if odd:  ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
 116          $temp = $class::multiplyHelper($temp, false, $u, false);
 117          // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
 118          // if odd:  (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
 119          $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1);
 120          // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
 121          // if odd:  (m.length - (m.length >> 1)) + m.length     = 2 * m.length - (m.length >> 1)
 122          $temp = $class::multiplyHelper($temp, false, $m, false);
 123  
 124          // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
 125          // number from a m.length + (m.length >> 1) + 1 digit number.  ie. there'd be an extra digit and the while loop
 126          // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
 127  
 128          $result = $class::subtractHelper($n[self::VALUE], false, $temp[self::VALUE], false);
 129  
 130          while (self::compareHelper($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) {
 131              $result = $class::subtractHelper($result[self::VALUE], $result[self::SIGN], $m, false);
 132          }
 133  
 134          return $result[self::VALUE];
 135      }
 136  
 137      /**
 138       * (Regular) Barrett Modular Reduction
 139       *
 140       * For numbers with more than four digits BigInteger::_barrett() is faster.  The difference between that and this
 141       * is that this function does not fold the denominator into a smaller form.
 142       *
 143       * @param array $x
 144       * @param array $n
 145       * @param string $class
 146       * @return array
 147       */
 148      private static function regularBarrett(array $x, array $n, $class)
 149      {
 150          static $cache = [
 151              self::VARIABLE => [],
 152              self::DATA => []
 153          ];
 154  
 155          $n_length = count($n);
 156  
 157          if (count($x) > 2 * $n_length) {
 158              $lhs = new $class();
 159              $rhs = new $class();
 160              $lhs->value = $x;
 161              $rhs->value = $n;
 162              list(, $temp) = $lhs->divide($rhs);
 163              return $temp->value;
 164          }
 165  
 166          if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
 167              $key = count($cache[self::VARIABLE]);
 168              $cache[self::VARIABLE][] = $n;
 169              $lhs = new $class();
 170              $lhs_value = &$lhs->value;
 171              $lhs_value = self::array_repeat(0, 2 * $n_length);
 172              $lhs_value[] = 1;
 173              $rhs = new $class();
 174              $rhs->value = $n;
 175              list($temp, ) = $lhs->divide($rhs); // m.length
 176              $cache[self::DATA][] = $temp->value;
 177          }
 178  
 179          // 2 * m.length - (m.length - 1) = m.length + 1
 180          $temp = array_slice($x, $n_length - 1);
 181          // (m.length + 1) + m.length = 2 * m.length + 1
 182          $temp = $class::multiplyHelper($temp, false, $cache[self::DATA][$key], false);
 183          // (2 * m.length + 1) - (m.length - 1) = m.length + 2
 184          $temp = array_slice($temp[self::VALUE], $n_length + 1);
 185  
 186          // m.length + 1
 187          $result = array_slice($x, 0, $n_length + 1);
 188          // m.length + 1
 189          $temp = self::multiplyLower($temp, false, $n, false, $n_length + 1, $class);
 190          // $temp == array_slice($class::regularMultiply($temp, false, $n, false)->value, 0, $n_length + 1)
 191  
 192          if (self::compareHelper($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) {
 193              $corrector_value = self::array_repeat(0, $n_length + 1);
 194              $corrector_value[count($corrector_value)] = 1;
 195              $result = $class::addHelper($result, false, $corrector_value, false);
 196              $result = $result[self::VALUE];
 197          }
 198  
 199          // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
 200          $result = $class::subtractHelper($result, false, $temp[self::VALUE], $temp[self::SIGN]);
 201          while (self::compareHelper($result[self::VALUE], $result[self::SIGN], $n, false) > 0) {
 202              $result = $class::subtractHelper($result[self::VALUE], $result[self::SIGN], $n, false);
 203          }
 204  
 205          return $result[self::VALUE];
 206      }
 207  
 208      /**
 209       * Performs long multiplication up to $stop digits
 210       *
 211       * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
 212       *
 213       * @see self::regularBarrett()
 214       * @param array $x_value
 215       * @param bool $x_negative
 216       * @param array $y_value
 217       * @param bool $y_negative
 218       * @param int $stop
 219       * @param string $class
 220       * @return array
 221       */
 222      private static function multiplyLower(array $x_value, $x_negative, array $y_value, $y_negative, $stop, $class)
 223      {
 224          $x_length = count($x_value);
 225          $y_length = count($y_value);
 226  
 227          if (!$x_length || !$y_length) { // a 0 is being multiplied
 228              return [
 229                  self::VALUE => [],
 230                  self::SIGN => false
 231              ];
 232          }
 233  
 234          if ($x_length < $y_length) {
 235              $temp = $x_value;
 236              $x_value = $y_value;
 237              $y_value = $temp;
 238  
 239              $x_length = count($x_value);
 240              $y_length = count($y_value);
 241          }
 242  
 243          $product_value = self::array_repeat(0, $x_length + $y_length);
 244  
 245          // the following for loop could be removed if the for loop following it
 246          // (the one with nested for loops) initially set $i to 0, but
 247          // doing so would also make the result in one set of unnecessary adds,
 248          // since on the outermost loops first pass, $product->value[$k] is going
 249          // to always be 0
 250  
 251          $carry = 0;
 252  
 253          for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
 254              $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
 255              $carry = $class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
 256              $product_value[$j] = (int) ($temp - $class::BASE_FULL * $carry);
 257          }
 258  
 259          if ($j < $stop) {
 260              $product_value[$j] = $carry;
 261          }
 262  
 263          // the above for loop is what the previous comment was talking about.  the
 264          // following for loop is the "one with nested for loops"
 265  
 266          for ($i = 1; $i < $y_length; ++$i) {
 267              $carry = 0;
 268  
 269              for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
 270                  $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
 271                  $carry = $class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
 272                  $product_value[$k] = (int) ($temp - $class::BASE_FULL * $carry);
 273              }
 274  
 275              if ($k < $stop) {
 276                  $product_value[$k] = $carry;
 277              }
 278          }
 279  
 280          return [
 281              self::VALUE => self::trim($product_value),
 282              self::SIGN => $x_negative != $y_negative
 283          ];
 284      }
 285  }