Subversion Repositories oidplus

Rev

Rev 846 | 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.  * In a binary finite field numbers are actually polynomial equations. If you
  7.  * represent the number as a sequence of bits you get a sequence of 1's or 0's.
  8.  * These 1's or 0's represent the coefficients of the x**n, where n is the
  9.  * location of the given bit. When you add numbers over a binary finite field
  10.  * the result should have a coefficient of 1 or 0 as well. Hence addition
  11.  * and subtraction become the same operation as XOR.
  12.  * eg. 1 + 1 + 1 == 3 % 2 == 1 or 0 - 1 == -1 % 2 == 1
  13.  *
  14.  * PHP version 5 and 7
  15.  *
  16.  * @category  Math
  17.  * @package   BigInteger
  18.  * @author    Jim Wigginton <terrafrost@php.net>
  19.  * @copyright 2017 Jim Wigginton
  20.  * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  21.  */
  22.  
  23. namespace phpseclib3\Math\BinaryField;
  24.  
  25. use ParagonIE\ConstantTime\Hex;
  26. use phpseclib3\Math\BigInteger;
  27. use phpseclib3\Math\BinaryField;
  28. use phpseclib3\Math\Common\FiniteField\Integer as Base;
  29.  
  30. /**
  31.  * Binary Finite Fields
  32.  *
  33.  * @package Math
  34.  * @author  Jim Wigginton <terrafrost@php.net>
  35.  * @access  public
  36.  */
  37. class Integer extends Base
  38. {
  39.     /**
  40.      * Holds the BinaryField's value
  41.      *
  42.      * @var string
  43.      */
  44.     protected $value;
  45.  
  46.     /**
  47.      * Keeps track of current instance
  48.      *
  49.      * @var int
  50.      */
  51.     protected $instanceID;
  52.  
  53.     /**
  54.      * Holds the PrimeField's modulo
  55.      *
  56.      * @var array<int, string>
  57.      */
  58.     protected static $modulo;
  59.  
  60.     /**
  61.      * Holds a pre-generated function to perform modulo reductions
  62.      *
  63.      * @var callable[]
  64.      */
  65.     protected static $reduce;
  66.  
  67.     /**
  68.      * Default constructor
  69.      */
  70.     public function __construct($instanceID, $num = '')
  71.     {
  72.         $this->instanceID = $instanceID;
  73.         if (!strlen($num)) {
  74.             $this->value = '';
  75.         } else {
  76.             $reduce = static::$reduce[$instanceID];
  77.             $this->value = $reduce($num);
  78.         }
  79.     }
  80.  
  81.     /**
  82.      * Set the modulo for a given instance
  83.      * @param int $instanceID
  84.      * @param string $modulo
  85.      */
  86.     public static function setModulo($instanceID, $modulo)
  87.     {
  88.         static::$modulo[$instanceID] = $modulo;
  89.     }
  90.  
  91.     /**
  92.      * Set the modulo for a given instance
  93.      */
  94.     public static function setRecurringModuloFunction($instanceID, callable $function)
  95.     {
  96.         static::$reduce[$instanceID] = $function;
  97.     }
  98.  
  99.     /**
  100.      * Tests a parameter to see if it's of the right instance
  101.      *
  102.      * Throws an exception if the incorrect class is being utilized
  103.      */
  104.     private static function checkInstance(self $x, self $y)
  105.     {
  106.         if ($x->instanceID != $y->instanceID) {
  107.             throw new \UnexpectedValueException('The instances of the two BinaryField\Integer objects do not match');
  108.         }
  109.     }
  110.  
  111.     /**
  112.      * Tests the equality of two numbers.
  113.      *
  114.      * @return bool
  115.      */
  116.     public function equals(self $x)
  117.     {
  118.         static::checkInstance($this, $x);
  119.  
  120.         return $this->value == $x->value;
  121.     }
  122.  
  123.     /**
  124.      * Compares two numbers.
  125.      *
  126.      * @return int
  127.      */
  128.     public function compare(self $x)
  129.     {
  130.         static::checkInstance($this, $x);
  131.  
  132.         $a = $this->value;
  133.         $b = $x->value;
  134.  
  135.         $length = max(strlen($a), strlen($b));
  136.  
  137.         $a = str_pad($a, $length, "\0", STR_PAD_LEFT);
  138.         $b = str_pad($b, $length, "\0", STR_PAD_LEFT);
  139.  
  140.         return strcmp($a, $b);
  141.     }
  142.  
  143.     /**
  144.      * Returns the degree of the polynomial
  145.      *
  146.      * @param string $x
  147.      * @return int
  148.      */
  149.     private static function deg($x)
  150.     {
  151.         $x = ltrim($x, "\0");
  152.         $xbit = decbin(ord($x[0]));
  153.         $xlen = $xbit == '0' ? 0 : strlen($xbit);
  154.         $len = strlen($x);
  155.         if (!$len) {
  156.             return -1;
  157.         }
  158.         return 8 * strlen($x) - 9 + $xlen;
  159.     }
  160.  
  161.     /**
  162.      * Perform polynomial division
  163.      *
  164.      * @return string[]
  165.      * @link https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_division
  166.      */
  167.     private static function polynomialDivide($x, $y)
  168.     {
  169.         // in wikipedia's description of the algorithm, lc() is the leading coefficient. over a binary field that's
  170.         // always going to be 1.
  171.  
  172.         $q = chr(0);
  173.         $d = static::deg($y);
  174.         $r = $x;
  175.         while (($degr = static::deg($r)) >= $d) {
  176.             $s = '1' . str_repeat('0', $degr - $d);
  177.             $s = BinaryField::base2ToBase256($s);
  178.             $length = max(strlen($s), strlen($q));
  179.             $q = !isset($q) ? $s :
  180.                 str_pad($q, $length, "\0", STR_PAD_LEFT) ^
  181.                 str_pad($s, $length, "\0", STR_PAD_LEFT);
  182.             $s = static::polynomialMultiply($s, $y);
  183.             $length = max(strlen($r), strlen($s));
  184.             $r = str_pad($r, $length, "\0", STR_PAD_LEFT) ^
  185.                  str_pad($s, $length, "\0", STR_PAD_LEFT);
  186.         }
  187.  
  188.         return [ltrim($q, "\0"), ltrim($r, "\0")];
  189.     }
  190.  
  191.     /**
  192.      * Perform polynomial multiplation in the traditional way
  193.      *
  194.      * @return string
  195.      * @link https://en.wikipedia.org/wiki/Finite_field_arithmetic#Multiplication
  196.      */
  197.     private static function regularPolynomialMultiply($x, $y)
  198.     {
  199.         $precomputed = [ltrim($x, "\0")];
  200.         $x = strrev(BinaryField::base256ToBase2($x));
  201.         $y = strrev(BinaryField::base256ToBase2($y));
  202.         if (strlen($x) == strlen($y)) {
  203.             $length = strlen($x);
  204.         } else {
  205.             $length = max(strlen($x), strlen($y));
  206.             $x = str_pad($x, $length, '0');
  207.             $y = str_pad($y, $length, '0');
  208.         }
  209.         $result = str_repeat('0', 2 * $length - 1);
  210.         $result = BinaryField::base2ToBase256($result);
  211.         $size = strlen($result);
  212.         $x = strrev($x);
  213.  
  214.         // precompute left shift 1 through 7
  215.         for ($i = 1; $i < 8; $i++) {
  216.             $precomputed[$i] = BinaryField::base2ToBase256($x . str_repeat('0', $i));
  217.         }
  218.         for ($i = 0; $i < strlen($y); $i++) {
  219.             if ($y[$i] == '1') {
  220.                 $temp = $precomputed[$i & 7] . str_repeat("\0", $i >> 3);
  221.                 $result ^= str_pad($temp, $size, "\0", STR_PAD_LEFT);
  222.             }
  223.         }
  224.  
  225.         return $result;
  226.     }
  227.  
  228.     /**
  229.      * Perform polynomial multiplation
  230.      *
  231.      * Uses karatsuba multiplication to reduce x-bit multiplications to a series of 32-bit multiplications
  232.      *
  233.      * @return string
  234.      * @link https://en.wikipedia.org/wiki/Karatsuba_algorithm
  235.      */
  236.     private static function polynomialMultiply($x, $y)
  237.     {
  238.         if (strlen($x) == strlen($y)) {
  239.             $length = strlen($x);
  240.         } else {
  241.             $length = max(strlen($x), strlen($y));
  242.             $x = str_pad($x, $length, "\0", STR_PAD_LEFT);
  243.             $y = str_pad($y, $length, "\0", STR_PAD_LEFT);
  244.         }
  245.  
  246.         switch (true) {
  247.             case PHP_INT_SIZE == 8 && $length <= 4:
  248.                 return $length != 4 ?
  249.                     self::subMultiply(str_pad($x, 4, "\0", STR_PAD_LEFT), str_pad($y, 4, "\0", STR_PAD_LEFT)) :
  250.                     self::subMultiply($x, $y);
  251.             case PHP_INT_SIZE == 4 || $length > 32:
  252.                 return self::regularPolynomialMultiply($x, $y);
  253.         }
  254.  
  255.         $m = $length >> 1;
  256.  
  257.         $x1 = substr($x, 0, -$m);
  258.         $x0 = substr($x, -$m);
  259.         $y1 = substr($y, 0, -$m);
  260.         $y0 = substr($y, -$m);
  261.  
  262.         $z2 = self::polynomialMultiply($x1, $y1);
  263.         $z0 = self::polynomialMultiply($x0, $y0);
  264.         $z1 = self::polynomialMultiply(
  265.             self::subAdd2($x1, $x0),
  266.             self::subAdd2($y1, $y0)
  267.         );
  268.  
  269.         $z1 = self::subAdd3($z1, $z2, $z0);
  270.  
  271.         $xy = self::subAdd3(
  272.             $z2 . str_repeat("\0", 2 * $m),
  273.             $z1 . str_repeat("\0", $m),
  274.             $z0
  275.         );
  276.  
  277.         return ltrim($xy, "\0");
  278.     }
  279.  
  280.     /**
  281.      * Perform polynomial multiplication on 2x 32-bit numbers, returning
  282.      * a 64-bit number
  283.      *
  284.      * @param string $x
  285.      * @param string $y
  286.      * @return string
  287.      * @link https://www.bearssl.org/constanttime.html#ghash-for-gcm
  288.      */
  289.     private static function subMultiply($x, $y)
  290.     {
  291.         $x = unpack('N', $x)[1];
  292.         $y = unpack('N', $y)[1];
  293.  
  294.         $x0 = $x & 0x11111111;
  295.         $x1 = $x & 0x22222222;
  296.         $x2 = $x & 0x44444444;
  297.         $x3 = $x & 0x88888888;
  298.  
  299.         $y0 = $y & 0x11111111;
  300.         $y1 = $y & 0x22222222;
  301.         $y2 = $y & 0x44444444;
  302.         $y3 = $y & 0x88888888;
  303.  
  304.         $z0 = ($x0 * $y0) ^ ($x1 * $y3) ^ ($x2 * $y2) ^ ($x3 * $y1);
  305.         $z1 = ($x0 * $y1) ^ ($x1 * $y0) ^ ($x2 * $y3) ^ ($x3 * $y2);
  306.         $z2 = ($x0 * $y2) ^ ($x1 * $y1) ^ ($x2 * $y0) ^ ($x3 * $y3);
  307.         $z3 = ($x0 * $y3) ^ ($x1 * $y2) ^ ($x2 * $y1) ^ ($x3 * $y0);
  308.  
  309.         $z0 &= 0x1111111111111111;
  310.         $z1 &= 0x2222222222222222;
  311.         $z2 &= 0x4444444444444444;
  312.         $z3 &= -8608480567731124088; // 0x8888888888888888 gets interpreted as a float
  313.  
  314.         $z = $z0 | $z1 | $z2 | $z3;
  315.  
  316.         return pack('J', $z);
  317.     }
  318.  
  319.     /**
  320.      * Adds two numbers
  321.      *
  322.      * @param string $x
  323.      * @param string $y
  324.      * @return string
  325.      */
  326.     private static function subAdd2($x, $y)
  327.     {
  328.         $length = max(strlen($x), strlen($y));
  329.         $x = str_pad($x, $length, "\0", STR_PAD_LEFT);
  330.         $y = str_pad($y, $length, "\0", STR_PAD_LEFT);
  331.         return $x ^ $y;
  332.     }
  333.  
  334.     /**
  335.      * Adds three numbers
  336.      *
  337.      * @param string $x
  338.      * @param string $y
  339.      * @return string
  340.      */
  341.     private static function subAdd3($x, $y, $z)
  342.     {
  343.         $length = max(strlen($x), strlen($y), strlen($z));
  344.         $x = str_pad($x, $length, "\0", STR_PAD_LEFT);
  345.         $y = str_pad($y, $length, "\0", STR_PAD_LEFT);
  346.         $z = str_pad($z, $length, "\0", STR_PAD_LEFT);
  347.         return $x ^ $y ^ $z;
  348.     }
  349.  
  350.     /**
  351.      * Adds two BinaryFieldIntegers.
  352.      *
  353.      * @return static
  354.      */
  355.     public function add(self $y)
  356.     {
  357.         static::checkInstance($this, $y);
  358.  
  359.         $length = strlen(static::$modulo[$this->instanceID]);
  360.  
  361.         $x = str_pad($this->value, $length, "\0", STR_PAD_LEFT);
  362.         $y = str_pad($y->value, $length, "\0", STR_PAD_LEFT);
  363.  
  364.         return new static($this->instanceID, $x ^ $y);
  365.     }
  366.  
  367.     /**
  368.      * Subtracts two BinaryFieldIntegers.
  369.      *
  370.      * @return static
  371.      */
  372.     public function subtract(self $x)
  373.     {
  374.         return $this->add($x);
  375.     }
  376.  
  377.     /**
  378.      * Multiplies two BinaryFieldIntegers.
  379.      *
  380.      * @return static
  381.      */
  382.     public function multiply(self $y)
  383.     {
  384.         static::checkInstance($this, $y);
  385.  
  386.         return new static($this->instanceID, static::polynomialMultiply($this->value, $y->value));
  387.     }
  388.  
  389.     /**
  390.      * Returns the modular inverse of a BinaryFieldInteger
  391.      *
  392.      * @return static
  393.      */
  394.     public function modInverse()
  395.     {
  396.         $remainder0 = static::$modulo[$this->instanceID];
  397.         $remainder1 = $this->value;
  398.  
  399.         if ($remainder1 == '') {
  400.             return new static($this->instanceID);
  401.         }
  402.  
  403.         $aux0 = "\0";
  404.         $aux1 = "\1";
  405.         while ($remainder1 != "\1") {
  406.             list($q, $r) = static::polynomialDivide($remainder0, $remainder1);
  407.             $remainder0 = $remainder1;
  408.             $remainder1 = $r;
  409.             // the auxiliary in row n is given by the sum of the auxiliary in
  410.             // row n-2 and the product of the quotient and the auxiliary in row
  411.             // n-1
  412.             $temp = static::polynomialMultiply($aux1, $q);
  413.             $aux = str_pad($aux0, strlen($temp), "\0", STR_PAD_LEFT) ^
  414.                    str_pad($temp, strlen($aux0), "\0", STR_PAD_LEFT);
  415.             $aux0 = $aux1;
  416.             $aux1 = $aux;
  417.         }
  418.  
  419.         $temp = new static($this->instanceID);
  420.         $temp->value = ltrim($aux1, "\0");
  421.         return $temp;
  422.     }
  423.  
  424.     /**
  425.      * Divides two PrimeFieldIntegers.
  426.      *
  427.      * @return static
  428.      */
  429.     public function divide(self $x)
  430.     {
  431.         static::checkInstance($this, $x);
  432.  
  433.         $x = $x->modInverse();
  434.         return $this->multiply($x);
  435.     }
  436.  
  437.     /**
  438.      * Negate
  439.      *
  440.      * A negative number can be written as 0-12. With modulos, 0 is the same thing as the modulo
  441.      * so 0-12 is the same thing as modulo-12
  442.      *
  443.      * @return object
  444.      */
  445.     public function negate()
  446.     {
  447.         $x = str_pad($this->value, strlen(static::$modulo[$this->instanceID]), "\0", STR_PAD_LEFT);
  448.  
  449.         return new static($this->instanceID, $x ^ static::$modulo[$this->instanceID]);
  450.     }
  451.  
  452.     /**
  453.      * Returns the modulo
  454.      *
  455.      * @return string
  456.      */
  457.     public static function getModulo($instanceID)
  458.     {
  459.         return static::$modulo[$instanceID];
  460.     }
  461.  
  462.     /**
  463.      * Converts an Integer to a byte string (eg. base-256).
  464.      *
  465.      * @return string
  466.      */
  467.     public function toBytes()
  468.     {
  469.         return str_pad($this->value, strlen(static::$modulo[$this->instanceID]), "\0", STR_PAD_LEFT);
  470.     }
  471.  
  472.     /**
  473.      * Converts an Integer to a hex string (eg. base-16).
  474.      *
  475.      * @return string
  476.      */
  477.     public function toHex()
  478.     {
  479.         return Hex::encode($this->toBytes());
  480.     }
  481.  
  482.     /**
  483.      * Converts an Integer to a bit string (eg. base-2).
  484.      *
  485.      * @return string
  486.      */
  487.     public function toBits()
  488.     {
  489.         //return str_pad(BinaryField::base256ToBase2($this->value), strlen(static::$modulo[$this->instanceID]), '0', STR_PAD_LEFT);
  490.         return BinaryField::base256ToBase2($this->value);
  491.     }
  492.  
  493.     /**
  494.      * Converts an Integer to a BigInteger
  495.      *
  496.      * @return string
  497.      */
  498.     public function toBigInteger()
  499.     {
  500.         return new BigInteger($this->value, 256);
  501.     }
  502.  
  503.     /**
  504.      *  __toString() magic method
  505.      *
  506.      * @access public
  507.      */
  508.     public function __toString()
  509.     {
  510.         return (string) $this->toBigInteger();
  511.     }
  512.  
  513.     /**
  514.      *  __debugInfo() magic method
  515.      *
  516.      * @access public
  517.      */
  518.     public function __debugInfo()
  519.     {
  520.         return ['value' => $this->toHex()];
  521.     }
  522. }
  523.