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