[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * BCMath Barrett Modular Exponentiation Engine
   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   * @link      http://pear.php.net/package/Math_BigInteger
  12   */
  13  
  14  namespace phpseclib3\Math\BigInteger\Engines\BCMath\Reductions;
  15  
  16  use phpseclib3\Math\BigInteger\Engines\BCMath\Base;
  17  
  18  /**
  19   * PHP Barrett Modular Exponentiation Engine
  20   *
  21   * @author  Jim Wigginton <terrafrost@php.net>
  22   */
  23  abstract class Barrett extends Base
  24  {
  25      /**
  26       * Cache constants
  27       *
  28       * $cache[self::VARIABLE] tells us whether or not the cached data is still valid.
  29       *
  30       */
  31      const VARIABLE = 0;
  32      /**
  33       * $cache[self::DATA] contains the cached data.
  34       *
  35       */
  36      const DATA = 1;
  37  
  38      /**
  39       * Barrett Modular Reduction
  40       *
  41       * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
  42       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
  43       * so as not to require negative numbers (initially, this script didn't support negative numbers).
  44       *
  45       * Employs "folding", as described at
  46       * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
  47       * 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."
  48       *
  49       * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
  50       * usable on account of (1) its not using reasonable radix points as discussed in
  51       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
  52       * radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
  53       * (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
  54       * comments for details.
  55       *
  56       * @param string $n
  57       * @param string $m
  58       * @return string
  59       */
  60      protected static function reduce($n, $m)
  61      {
  62          static $cache = [
  63              self::VARIABLE => [],
  64              self::DATA => []
  65          ];
  66  
  67          $m_length = strlen($m);
  68  
  69          if (strlen($n) > 2 * $m_length) {
  70              return bcmod($n, $m);
  71          }
  72  
  73          // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
  74          if ($m_length < 5) {
  75              return self::regularBarrett($n, $m);
  76          }
  77          // n = 2 * m.length
  78  
  79          if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
  80              $key = count($cache[self::VARIABLE]);
  81              $cache[self::VARIABLE][] = $m;
  82  
  83              $lhs = '1' . str_repeat('0', $m_length + ($m_length >> 1));
  84              $u = bcdiv($lhs, $m, 0);
  85              $m1 = bcsub($lhs, bcmul($u, $m));
  86  
  87              $cache[self::DATA][] = [
  88                  'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
  89                  'm1' => $m1 // m.length
  90              ];
  91          } else {
  92              extract($cache[self::DATA][$key]);
  93          }
  94  
  95          $cutoff = $m_length + ($m_length >> 1);
  96  
  97          $lsd = substr($n, -$cutoff);
  98          $msd = substr($n, 0, -$cutoff);
  99  
 100          $temp = bcmul($msd, $m1); // m.length + (m.length >> 1)
 101          $n = bcadd($lsd, $temp); // m.length + (m.length >> 1) + 1 (so basically we're adding two same length numbers)
 102          //if ($m_length & 1) {
 103          //    return self::regularBarrett($n, $m);
 104          //}
 105  
 106          // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
 107          $temp = substr($n, 0, -$m_length + 1);
 108          // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
 109          // if odd:  ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
 110          $temp = bcmul($temp, $u);
 111          // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
 112          // if odd:  (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
 113          $temp = substr($temp, 0, -($m_length >> 1) - 1);
 114          // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
 115          // if odd:  (m.length - (m.length >> 1)) + m.length     = 2 * m.length - (m.length >> 1)
 116          $temp = bcmul($temp, $m);
 117  
 118          // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
 119          // number from a m.length + (m.length >> 1) + 1 digit number.  ie. there'd be an extra digit and the while loop
 120          // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
 121  
 122          $result = bcsub($n, $temp);
 123  
 124          //if (bccomp($result, '0') < 0) {
 125          if ($result[0] == '-') {
 126              $temp = '1' . str_repeat('0', $m_length + 1);
 127              $result = bcadd($result, $temp);
 128          }
 129  
 130          while (bccomp($result, $m) >= 0) {
 131              $result = bcsub($result, $m);
 132          }
 133  
 134          return $result;
 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 string $x
 144       * @param string $n
 145       * @return string
 146       */
 147      private static function regularBarrett($x, $n)
 148      {
 149          static $cache = [
 150              self::VARIABLE => [],
 151              self::DATA => []
 152          ];
 153  
 154          $n_length = strlen($n);
 155  
 156          if (strlen($x) > 2 * $n_length) {
 157              return bcmod($x, $n);
 158          }
 159  
 160          if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
 161              $key = count($cache[self::VARIABLE]);
 162              $cache[self::VARIABLE][] = $n;
 163              $lhs = '1' . str_repeat('0', 2 * $n_length);
 164              $cache[self::DATA][] = bcdiv($lhs, $n, 0);
 165          }
 166  
 167          $temp = substr($x, 0, -$n_length + 1);
 168          $temp = bcmul($temp, $cache[self::DATA][$key]);
 169          $temp = substr($temp, 0, -$n_length - 1);
 170  
 171          $r1 = substr($x, -$n_length - 1);
 172          $r2 = substr(bcmul($temp, $n), -$n_length - 1);
 173          $result = bcsub($r1, $r2);
 174  
 175          //if (bccomp($result, '0') < 0) {
 176          if ($result[0] == '-') {
 177              $q = '1' . str_repeat('0', $n_length + 1);
 178              $result = bcadd($result, $q);
 179          }
 180  
 181          while (bccomp($result, $n) >= 0) {
 182              $result = bcsub($result, $n);
 183          }
 184  
 185          return $result;
 186      }
 187  }