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 <terrafrost@php.net> 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 16namespace phpseclib3\Math\BigInteger\Engines\BCMath\Reductions; 17 18use phpseclib3\Math\BigInteger\Engines\BCMath\Base; 19 20/** 21 * PHP Barrett Modular Exponentiation Engine 22 * 23 * @package PHP 24 * @author Jim Wigginton <terrafrost@php.net> 25 * @access public 26 */ 27abstract 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} 194