[Summary view] [Print] [Text view]

   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 <[email protected]>
  13   * @copyright 2017 Jim Wigginton
  14   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  15   */
  16  
  17  namespace phpseclib3\Math;
  18  
  19  use phpseclib3\Common\Functions\Strings;
  20  use phpseclib3\Math\BinaryField\Integer;
  21  use phpseclib3\Math\Common\FiniteField;
  22  
  23  /**
  24   * Binary Finite Fields
  25   *
  26   * @package Math
  27   * @author  Jim Wigginton <[email protected]>
  28   * @access  public
  29   */
  30  class 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  }