1<?php 2 3/** 4 * Binary Finite Fields 5 * 6 * Utilizes the factory design pattern 7 * 8 * PHP version 5 and 7 9 * 10 * @category Math 11 * @package BigInteger 12 * @author Jim Wigginton <terrafrost@php.net> 13 * @copyright 2017 Jim Wigginton 14 * @license http://www.opensource.org/licenses/mit-license.html MIT License 15 */ 16 17namespace phpseclib3\Math; 18 19use phpseclib3\Common\Functions\Strings; 20use phpseclib3\Math\BinaryField\Integer; 21use phpseclib3\Math\Common\FiniteField; 22 23/** 24 * Binary Finite Fields 25 * 26 * @package Math 27 * @author Jim Wigginton <terrafrost@php.net> 28 * @access public 29 */ 30class BinaryField extends FiniteField 31{ 32 /** 33 * Instance Counter 34 * 35 * @var int 36 */ 37 private static $instanceCounter = 0; 38 39 /** 40 * Keeps track of current instance 41 * 42 * @var int 43 */ 44 protected $instanceID; 45 46 /** @var BigInteger */ 47 private $randomMax; 48 49 /** 50 * Default constructor 51 */ 52 public function __construct(...$indices) 53 { 54 $m = array_shift($indices); 55 $val = str_repeat('0', $m) . '1'; 56 foreach ($indices as $index) { 57 $val[$index] = '1'; 58 } 59 $modulo = static::base2ToBase256(strrev($val)); 60 61 $mStart = 2 * $m - 2; 62 $t = ceil($m / 8); 63 $finalMask = chr((1 << ($m % 8)) - 1); 64 if ($finalMask == "\0") { 65 $finalMask = "\xFF"; 66 } 67 $bitLen = $mStart + 1; 68 $pad = ceil($bitLen / 8); 69 $h = $bitLen & 7; 70 $h = $h ? 8 - $h : 0; 71 72 $r = rtrim(substr($val, 0, -1), '0'); 73 $u = [static::base2ToBase256(strrev($r))]; 74 for ($i = 1; $i < 8; $i++) { 75 $u[] = static::base2ToBase256(strrev(str_repeat('0', $i) . $r)); 76 } 77 78 // implements algorithm 2.40 (in section 2.3.5) in "Guide to Elliptic Curve Cryptography" 79 // with W = 8 80 $reduce = function ($c) use ($u, $mStart, $m, $t, $finalMask, $pad, $h) { 81 $c = str_pad($c, $pad, "\0", STR_PAD_LEFT); 82 for ($i = $mStart; $i >= $m;) { 83 $g = $h >> 3; 84 $mask = $h & 7; 85 $mask = $mask ? 1 << (7 - $mask) : 0x80; 86 for (; $mask > 0; $mask >>= 1, $i--, $h++) { 87 if (ord($c[$g]) & $mask) { 88 $temp = $i - $m; 89 $j = $temp >> 3; 90 $k = $temp & 7; 91 $t1 = $j ? substr($c, 0, -$j) : $c; 92 $length = strlen($t1); 93 if ($length) { 94 $t2 = str_pad($u[$k], $length, "\0", STR_PAD_LEFT); 95 $temp = $t1 ^ $t2; 96 $c = $j ? substr_replace($c, $temp, 0, $length) : $temp; 97 } 98 } 99 } 100 } 101 $c = substr($c, -$t); 102 if (strlen($c) == $t) { 103 $c[0] = $c[0] & $finalMask; 104 } 105 return ltrim($c, "\0"); 106 }; 107 108 $this->instanceID = self::$instanceCounter++; 109 Integer::setModulo($this->instanceID, $modulo); 110 Integer::setRecurringModuloFunction($this->instanceID, $reduce); 111 112 $this->randomMax = new BigInteger($modulo, 2); 113 } 114 115 /** 116 * Returns an instance of a dynamically generated PrimeFieldInteger class 117 * 118 * @param string $num 119 * @return Integer 120 */ 121 public function newInteger($num) 122 { 123 return new Integer($this->instanceID, $num instanceof BigInteger ? $num->toBytes() : $num); 124 } 125 126 /** 127 * Returns an integer on the finite field between one and the prime modulo 128 * 129 * @return Integer 130 */ 131 public function randomInteger() 132 { 133 static $one; 134 if (!isset($one)) { 135 $one = new BigInteger(1); 136 } 137 138 return new Integer($this->instanceID, BigInteger::randomRange($one, $this->randomMax)->toBytes()); 139 } 140 141 /** 142 * Returns the length of the modulo in bytes 143 * 144 * @return int 145 */ 146 public function getLengthInBytes() 147 { 148 return strlen(Integer::getModulo($this->instanceID)); 149 } 150 151 /** 152 * Returns the length of the modulo in bits 153 * 154 * @return int 155 */ 156 public function getLength() 157 { 158 return strlen(Integer::getModulo($this->instanceID)) << 3; 159 } 160 161 /** 162 * Converts a base-2 string to a base-256 string 163 * 164 * @param string $x 165 * @param int|null $size 166 * @return string 167 */ 168 public static function base2ToBase256($x, $size = null) 169 { 170 $str = Strings::bits2bin($x); 171 172 $pad = strlen($x) >> 3; 173 if (strlen($x) & 3) { 174 $pad++; 175 } 176 $str = str_pad($str, $pad, "\0", STR_PAD_LEFT); 177 if (isset($size)) { 178 $str = str_pad($str, $size, "\0", STR_PAD_LEFT); 179 } 180 181 return $str; 182 } 183 184 /** 185 * Converts a base-256 string to a base-2 string 186 * 187 * @param string $x 188 * @return string 189 */ 190 public static function base256ToBase2($x) 191 { 192 if (function_exists('gmp_import')) { 193 return gmp_strval(gmp_import($x), 2); 194 } 195 196 return Strings::bin2bits($x); 197 } 198} 199