Subversion Repositories oidplus

Rev

Rev 846 | Rev 1042 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  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.  
  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 <terrafrost@php.net>
  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. }
  199.