[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * BCMath 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\BCMath\Reductions;
  17  
  18  use phpseclib3\Math\BigInteger\Engines\BCMath\Base;
  19  
  20  /**
  21   * PHP Barrett Modular Exponentiation Engine
  22   *
  23   * @package PHP
  24   * @author  Jim Wigginton <[email protected]>
  25   * @access  public
  26   */
  27  abstract class Barrett extends Base
  28  {
  29      /**
  30       * Cache constants
  31       *
  32       * $cache[self::VARIABLE] tells us whether or not the cached data is still valid.
  33       *
  34       * @access private
  35       */
  36      const VARIABLE = 0;
  37      /**
  38       * $cache[self::DATA] contains the cached data.
  39       *
  40       * @access private
  41       */
  42      const DATA = 1;
  43  
  44      /**
  45       * Barrett Modular Reduction
  46       *
  47       * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
  48       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
  49       * so as not to require negative numbers (initially, this script didn't support negative numbers).
  50       *
  51       * Employs "folding", as described at
  52       * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
  53       * 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."
  54       *
  55       * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
  56       * usable on account of (1) its not using reasonable radix points as discussed in
  57       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
  58       * radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
  59       * (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
  60       * comments for details.
  61       *
  62       * @param string $n
  63       * @param string $m
  64       * @return string
  65       */
  66      protected static function reduce($n, $m)
  67      {
  68          static $cache = [
  69              self::VARIABLE => [],
  70              self::DATA => []
  71          ];
  72  
  73          $m_length = strlen($m);
  74  
  75          if (strlen($n) > 2 * $m_length) {
  76              return bcmod($n, $m);
  77          }
  78  
  79          // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
  80          if ($m_length < 5) {
  81              return self::regularBarrett($n, $m);
  82          }
  83          // n = 2 * m.length
  84  
  85          if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
  86              $key = count($cache[self::VARIABLE]);
  87              $cache[self::VARIABLE][] = $m;
  88  
  89              $lhs = '1' . str_repeat('0', $m_length + ($m_length >> 1));
  90              $u = bcdiv($lhs, $m, 0);
  91              $m1 = bcsub($lhs, bcmul($u, $m));
  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  
 103          $lsd = substr($n, -$cutoff);
 104          $msd = substr($n, 0, -$cutoff);
 105  
 106          $temp = bcmul($msd, $m1); // m.length + (m.length >> 1)
 107          $n = bcadd($lsd, $temp); // 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, $m);
 110          //}
 111  
 112          // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
 113          $temp = substr($n, 0, -$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 = bcmul($temp, $u);
 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 = substr($temp, 0, -($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 = bcmul($temp, $m);
 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 = bcsub($n, $temp);
 129  
 130          //if (bccomp($result, '0') < 0) {
 131          if ($result[0] == '-') {
 132              $temp = '1' . str_repeat('0', $m_length + 1);
 133              $result = bcadd($result, $temp);
 134          }
 135  
 136          while (bccomp($result, $m) >= 0) {
 137              $result = bcsub($result, $m);
 138          }
 139  
 140          return $result;
 141      }
 142  
 143      /**
 144       * (Regular) Barrett Modular Reduction
 145       *
 146       * For numbers with more than four digits BigInteger::_barrett() is faster.  The difference between that and this
 147       * is that this function does not fold the denominator into a smaller form.
 148       *
 149       * @param string $x
 150       * @param string $n
 151       * @return string
 152       */
 153      private static function regularBarrett($x, $n)
 154      {
 155          static $cache = [
 156              self::VARIABLE => [],
 157              self::DATA => []
 158          ];
 159  
 160          $n_length = strlen($n);
 161  
 162          if (strlen($x) > 2 * $n_length) {
 163              return bcmod($x, $n);
 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 = '1' . str_repeat('0', 2 * $n_length);
 170              $cache[self::DATA][] = bcdiv($lhs, $n, 0);
 171          }
 172  
 173          $temp = substr($x, 0, -$n_length + 1);
 174          $temp = bcmul($temp, $cache[self::DATA][$key]);
 175          $temp = substr($temp, 0, -$n_length - 1);
 176  
 177          $r1 = substr($x, -$n_length - 1);
 178          $r2 = substr(bcmul($temp, $n), -$n_length - 1);
 179          $result = bcsub($r1, $r2);
 180  
 181          //if (bccomp($result, '0') < 0) {
 182          if ($result[0] == '-') {
 183              $q = '1' . str_repeat('0', $n_length + 1);
 184              $result = bcadd($result, $q);
 185          }
 186  
 187          while (bccomp($result, $n) >= 0) {
 188              $result = bcsub($result, $n);
 189          }
 190  
 191          return $result;
 192      }
 193  }