function is_prime($n, $k)
{
    if ($n == 2) {
        return true;
    }
    if ($n < 2 || $n % 2 == 0) {
        return false;
    }
    $d = $n - 1;
    $s = 0;
    while ($d % 2 == 0) {
        $d /= 2;
        $s++;
    }
    for ($i = 0; $i < $k; $i++) {
        $a = rand(2, $n - 1);
        $x = bcpowmod($a, $d, $n);
        if ($x == 1 || $x == $n - 1) {
            continue;
        }
        for ($j = 1; $j < $s; $j++) {
            $x = bcmod(bcmul($x, $x), $n);
            if ($x == 1) {
                return false;
            }
            if ($x == $n - 1) {
                continue 2;
            }
        }
        return false;
    }
    return true;
}

function powmod($base, $exponent, $modulus)
{
    if (function_exists('gmp_powm')) {
        // fast
        return gmp_strval(gmp_powm($base, $exponent, $modulus));
    }
    if (function_exists('bi_powmod')) {
        // not tested
        return bi_sto_str(bi_powmod($base, $exponent, $modulus));
    }
    if (function_exists('bcpowmod')) {
        // slow
        return bcpowmod($base, $exponent, $modulus);
    }
    // emulation, slow
    $square = bcmod($base, $modulus);
    $result = 1;
    while (bccomp($exponent, 0) > 0) {
        if (bcmod($exponent, 2)) {
            $result = bcmod(bcmul($result, $square), $modulus);
        }
        $square = bcmod(bcmul($square, $square), $modulus);
        $exponent = bcdiv($exponent, 2);
    }
    return $result;
}

 public static function encryptPortion($portion, $n, $e)
 {
     $plain = '0';
     foreach (array_reverse($portion) as $k => $v) {
         $plain = bcadd($plain, bcmul($v, bcpowmod(256, $k, $n)));
     }
     $t = self::dec2hex(bcpowmod($plain, $e, $n));
     return $t;
 }

 protected function expmod($b, $e, $m)
 {
     //if($e==0){return 1;}
     $t = bcpowmod($b, $e, $m);
     if ($t[0] === '-') {
         $t = bcadd($t, $m);
     }
     return $t;
 }

 public static function encrypt($text)
 {
     $text = self::bchexdec(bin2hex($text));
     $n = bcpowmod($text, self::$rsa_exp, self::$rsa_mod);
     $ret = '';
     while ($n > 0) {
         $ret = chr(bcmod($n, 256)) . $ret;
         $n = bcdiv($n, 256, 0);
     }
     return $ret;
 }

/**
 * powmod
 * Raise a number to a power mod n
 * This could probably be made faster with some Montgomery trickery, but it's just fallback for now
 * @param string Decimal string to be raised
 * @param string Decimal string of the power to raise to
 * @param string Decimal string the modulus
 * @return string Decimal string
 */
function powmod($num, $pow, $mod)
{
    if (function_exists('bcpowmod')) {
        return bcpowmod($num, $pow, $mod);
    }
    // Emulate bcpowmod
    $result = '1';
    do {
        if (!bccomp(bcmod($pow, '2'), '1')) {
            $result = bcmod(bcmul($result, $num), $mod);
        }
        $num = bcmod(bcpow($num, '2'), $mod);
        $pow = bcdiv($pow, '2');
    } while (bccomp($pow, '0'));
    return $result;
}

 function biDecryptedString($s, $utf8_decoded = FALSE)
 {
     $blocks = split(",", $s);
     $result = "";
     for ($i = 0; $i < count($blocks); $i++) {
         $block = bcpowmod(self::biFromHex($blocks[$i]), $this->d, $this->m);
         for ($j = 0; $block !== "0"; $j++) {
             $curchar = bcmod($block, 256);
             $result .= chr($curchar);
             $block = bcdiv($block, 256, 0);
         }
     }
     $result = str_replace(chr(255), chr(0), $result);
     $result = substr($result, 0, strpos($result, chr(254)));
     return $utf8_decoded ? utf8_decode($result) : $result;
 }

 private function _computeK()
 {
     $hash_input = str_pad($this->_Ahex, strlen($this->_srp->Nhex()), "0", STR_PAD_LEFT) . str_pad($this->_Bhex, strlen($this->_srp->Nhex()), "0", STR_PAD_LEFT);
     $hash_input = pack("H*", $hash_input);
     $this->_uhex = $this->_srp->hash($hash_input);
     $this->_udec = hex2dec($this->_uhex);
     $Stmp = bcpowmod($this->_vdec, $this->_udec, $this->_srp->Ndec());
     // v^u (mod N)
     $Stmp = bcmod(bcmul($Stmp, $this->_Adec), $this->_srp->Ndec());
     //v^u*A (mod N)
     $Stmp = bcpowmod($Stmp, $this->_bdec, $this->_srp->Ndec());
     // (v^u*A)^b (mod N)
     $this->_Sdec = $Stmp;
     $this->_Shex = dec2hex($this->_Sdec);
     $this->_Shex = str_pad($this->_Shex, strlen($this->_srp->Nhex()), "0", STR_PAD_LEFT);
     $this->_Khex = $this->_srp->keyHash(pack("H*", $this->_Shex));
 }

 public static function modular_exp($base, $exponent, $modulus)
 {
     if (extension_loaded('gmp') && USE_EXT == 'GMP') {
         if ($exponent < 0) {
             return new ErrorException("Negative exponents (" . $exponent . ") not allowed");
         } else {
             $p = gmp_strval(gmp_powm($base, $exponent, $modulus));
             return $p;
         }
     } elseif (extension_loaded('bcmath') && USE_EXT == 'BCMATH') {
         if ($exponent < 0) {
             return new ErrorException("Negative exponents (" . $exponent . ") not allowed");
         } else {
             $p = bcpowmod($base, $exponent, $modulus);
             return $p;
         }
     } else {
         throw new ErrorException("Please install BCMATH or GMP");
     }
 }

 /**
  * Create signature for given data
  *
  * @param string $data
  *
  * @return string
  */
 public function sign($data)
 {
     // Make data hash (16 bytes)
     $base = hash('md4', $data, true);
     // Add 40 random bytes
     for ($i = 0; $i < 10; ++$i) {
         $base .= pack('V', mt_rand());
     }
     // Add length of the base as first 2 bytes
     $base = pack('v', strlen($base)) . $base;
     // Modular exponentiation
     $dec = bcpowmod($this->reverseToDecimal($base), $this->power, $this->modulus);
     // Convert result to hexadecimal
     $hex = gmp_strval($dec, 16);
     // Fill empty bytes with zeros
     $hex = str_repeat('0', 132 - strlen($hex)) . $hex;
     // Reverse byte order
     $hexReversed = '';
     for ($i = 0; $i < strlen($hex) / 4; ++$i) {
         $hexReversed = substr($hex, $i * 4, 4) . $hexReversed;
     }
     return strtolower($hexReversed);
 }

 /**
  * Create a signature for the given data
  *
  * @param string $data
  *
  * @return string
  */
 public function sign($data)
 {
     // Make data hash (16 bytes)
     $base = hash('md4', $data, true);
     // Add 40 random bytes
     for ($i = 0; $i < 10; ++$i) {
         $base .= pack('V', mt_rand());
     }
     // Add the length of the base (56 = 16 + 40) as the first 2 bytes
     $base = pack('v', mb_strlen($base, self::MB_ENCODING)) . $base;
     // Modular exponentiation
     $dec = bcpowmod(self::reverseToDecimal($base), $this->power, $this->modulus, 0);
     // Convert to hexadecimal
     $hex = self::dec2hex($dec);
     // Fill empty bytes with zeros
     $hex = str_repeat('0', 132 - mb_strlen($hex, self::MB_ENCODING)) . $hex;
     // Reverse byte order
     $hexReversed = '';
     for ($i = 0; $i < mb_strlen($hex, self::MB_ENCODING) / 4; ++$i) {
         $hexReversed = mb_substr($hex, $i * 4, 4, self::MB_ENCODING) . $hexReversed;
     }
     return mb_strtolower($hexReversed, self::MB_ENCODING);
 }

 /**
  * Performs modular exponentiation.
  *
  * Here's a quick 'n dirty example:
  * <code>
  * <?php
  *    include('Math/BigInteger.php');
  *
  *    $a = new Math_BigInteger('10');
  *    $b = new Math_BigInteger('20');
  *    $c = new Math_BigInteger('30');
  *
  *    $c = $a->modPow($b, $c);
  *
  *    echo $c->toString(); // outputs 10
  * ?>
  * </code>
  *
  * @param Math_BigInteger $e
  * @param Math_BigInteger $n
  * @return Math_BigInteger
  * @access public
  * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and
  *    and although the approach involving repeated squaring does vastly better, it, too, is impractical
  *    for our purposes.  The reason being that division - by far the most complicated and time-consuming
  *    of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
  *
  *    Modular reductions resolve this issue.  Although an individual modular reduction takes more time
  *    then an individual division, when performed in succession (with the same modulo), they're a lot faster.
  *
  *    The two most commonly used modular reductions are Barrett and Montgomery reduction.  Montgomery reduction,
  *    although faster, only works when the gcd of the modulo and of the base being used is 1.  In RSA, when the
  *    base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
  *    the product of two odd numbers is odd), but what about when RSA isn't used?
  *
  *    In contrast, Barrett reduction has no such constraint.  As such, some bigint implementations perform a
  *    Barrett reduction after every operation in the modpow function.  Others perform Barrett reductions when the
  *    modulo is even and Montgomery reductions when the modulo is odd.  BigInteger.java's modPow method, however,
  *    uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
  *    the other, a power of two - and recombine them, later.  This is the method that this modPow function uses.
  *    {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
  */
 function modPow($e, $n)
 {
     $n = $n->abs();
     if ($e->compare(new Math_BigInteger()) < 0) {
         $e = $e->abs();
         $temp = $this->modInverse($n);
         if ($temp === false) {
             return false;
         }
         return $temp->modPow($e, $n);
     }
     switch (MATH_BIGINTEGER_MODE) {
         case MATH_BIGINTEGER_MODE_GMP:
             $temp = new Math_BigInteger();
             $temp->value = gmp_powm($this->value, $e->value, $n->value);
             return $temp;
         case MATH_BIGINTEGER_MODE_BCMATH:
             // even though the last parameter is optional, according to php.net, it's not optional in
             // PHP_Compat 1.5.0 when running PHP 4.
             $temp = new Math_BigInteger();
             $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
             return $temp;
     }
     if (empty($e->value)) {
         $temp = new Math_BigInteger();
         $temp->value = array(1);
         return $temp;
     }
     if ($e->value == array(1)) {
         list(, $temp) = $this->divide($n);
         return $temp;
     }
     if ($e->value == array(2)) {
         $temp = $this->_square();
         list(, $temp) = $temp->divide($n);
         return $temp;
     }
     // is the modulo odd?
     if ($n->value[0] & 1) {
         return $this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY);
     }
     // if it's not, it's even
     // find the lowest set bit (eg. the max pow of 2 that divides $n)
     for ($i = 0; $i < count($n->value); $i++) {
         if ($n->value[$i]) {
             $temp = decbin($n->value[$i]);
             $j = strlen($temp) - strrpos($temp, '1') - 1;
             $j += 26 * $i;
             break;
         }
     }
     // at this point, 2^$j * $n/(2^$j) == $n
     $mod1 = $n->_copy();
     $mod1->_rshift($j);
     $mod2 = new Math_BigInteger();
     $mod2->value = array(1);
     $mod2->_lshift($j);
     $part1 = $mod1->value != array(1) ? $this->_slidingWindow($e, $mod1, MATH_BIGINTEGER_MONTGOMERY) : new Math_BigInteger();
//.........这里部分代码省略.........

 function powmod($base, $exponent, $modulus)
 {
     if (function_exists('bcpowmod')) {
         return bcpowmod($base, $exponent, $modulus);
     } else {
         return $this->_powmod($base, $exponent, $modulus);
     }
 }

 /**
  * Gets the remainder of this integer number raised to the integer `$exponent`, divided by the integer `$modulus`
  *
  * This method is faster than doing `$num->pow($exponent)->mod($modulus)`
  * and is primarily useful for cryptographic functionality.
  *
  * @throws fValidationException  When `$exponent` or `$modulus` is not a valid number
  *
  * @param  fNumber|string $exponent  The power to raise to - all non integer values will be truncated to integers
  * @param  fNumber|string $modulus   The value to divide by - all non integer values will be truncated to integers
  * @return fNumber  The remainder
  */
 public function powmod($exponent, $modulus)
 {
     $exp = self::parse($exponent, 'array');
     $mod = self::parse($modulus, 'array');
     if ($this->value[0] == '-') {
         throw new fProgrammerException('The method %s can only be called for positive number, however this number is negative', 'powmod()');
     }
     if ($exp['integer'][0] == '-') {
         throw new fProgrammerException('The exponent specified, %s, must be a positive integer, however it is negative', $exponent);
     }
     if ($mod['integer'][0] == '-') {
         throw new fProgrammerException('The modulus specified, %s, must be a positive integer, however it is negative', $modulus);
     }
     // All numbers involved in this need to be integers
     $exponent = $exp['integer'];
     $modulus = $mod['integer'];
     $len = strpos($this->value, '.') !== FALSE ? strpos($this->value, '.') : strlen($this->value);
     $value = substr($this->value, 0, $len);
     if (function_exists('bcpowmod')) {
         $result = bcpowmod($value, $exponent, $modulus, 0);
     } else {
         $exponent = self::baseConvert($exponent, 10, 2);
         $result = '+1';
         self::performDiv($value, $modulus, $first_modulus);
         for ($i = 0; $i < strlen($exponent); $i++) {
             self::performDiv(self::performMul($result, $result), $modulus, $result);
             if ($exponent[$i] == '1') {
                 self::performDiv(self::performMul($result, $first_modulus), $modulus, $result);
             }
         }
     }
     return new fNumber($result);
 }

 /**
  * Raises an arbitrary precision number to another,
  * reduced by a specified modulus.
  *
  * @param  string  $a        The first number.
  * @param  string  $b        The exponent.
  * @param  string  $c        The modulus.
  * @return string            The result of the operation.
  */
 public function powmod($a, $b, $c)
 {
     return bcpowmod($this->bcNormalize($a), $this->bcNormalize($b), $this->bcNormalize($c));
 }

 /**
  * Decrypts a given string with the $dec_key and the $enc_mod
  *
  * @param string $encrypted
  * @param int $dec_key
  * @param int $enc_mod
  * @return string
  */
 public function decrypt($encrypted, $dec_key, $enc_mod)
 {
     //replaced split with explode
     $blocks = explode(' ', $encrypted);
     $result = "";
     $max = count($blocks);
     for ($i = 0; $i < $max; $i++) {
         $dec = $this->_hex2bint($blocks[$i]);
         $dec = bcpowmod($dec, $dec_key, $enc_mod);
         $ascii = $this->_bint2char($dec);
         $result .= $ascii;
     }
     return $this->_redundacyCheck($result);
 }

 /**
  * powmod using bcmath extension
  */
 function _powmodBcmath($x, $y, $mod)
 {
     if (function_exists('bcpowmod')) {
         return bcpowmod($x, $y, $mod);
     } else {
         if (bccomp($y, 1) == 0) {
             return bcmod($x, $mod);
         } else {
             if (bcmod($y, 2) == 0) {
                 return bcmod(bcpow(Security_DSA::_powmodBcmath($x, bcdiv($y, 2), $mod), 2), $mod);
             } else {
                 return bcmod(bcmul($x, Security_DSA::_powmodBcmath($x, bcsub($y, 1), $mod)), $mod);
             }
         }
     }
 }

/**
 * Attempt to create a shared secret with the OpenID Provider.
 *
 * @param $op_endpoint URL of the OpenID Provider endpoint.
 *
 * @return $assoc_handle The association handle.
 */
function openid_association($op_endpoint)
{
    //@todo Remove Old Associations:
    $openid_association = Database::get_main_table(TABLE_MAIN_OPENID_ASSOCIATION);
    $sql = "DELETE FROM {$openid_association}\n            WHERE created + expires_in < '" . api_get_utc_datetime() . "'";
    Database::query($sql);
    // Check to see if we have an association for this IdP already
    $op_endpoint = Database::escape_string($op_endpoint);
    $sql = "SELECT assoc_handle\n            FROM {$openid_association}\n            WHERE idp_endpoint_uri = '{$op_endpoint}'";
    $assoc_handle = Database::query($sql);
    if (Database::num_rows($assoc_handle) <= 1) {
        $mod = OPENID_DH_DEFAULT_MOD;
        $gen = OPENID_DH_DEFAULT_GEN;
        $r = _openid_dh_rand($mod);
        $private = bcadd($r, 1);
        $public = bcpowmod($gen, $private, $mod);
        // If there is no existing association, then request one
        $assoc_request = openid_association_request($public);
        $assoc_message = _openid_encode_message(_openid_create_message($assoc_request));
        $assoc_headers = array('Content-Type' => 'application/x-www-form-urlencoded; charset=utf-8');
        //TODO
        $assoc_result = openid_http_request($op_endpoint, $assoc_headers, 'POST', $assoc_message);
        if (isset($assoc_result->error)) {
            return FALSE;
        }
        $assoc_response = _openid_parse_message($assoc_result->data);
        if (isset($assoc_response['mode']) && $assoc_response['mode'] == 'error') {
            return FALSE;
        }
        if ($assoc_response['session_type'] == 'DH-SHA1') {
            $spub = _openid_dh_base64_to_long($assoc_response['dh_server_public']);
            $enc_mac_key = base64_decode($assoc_response['enc_mac_key']);
            $shared = bcpowmod($spub, $private, $mod);
            $assoc_response['mac_key'] = base64_encode(_openid_dh_xorsecret($shared, $enc_mac_key));
        }
        //TODO
        $openid_association = Database::get_main_table(TABLE_MAIN_OPENID_ASSOCIATION);
        Database::query(sprintf("INSERT INTO {$openid_association} (idp_endpoint_uri, session_type, assoc_handle, assoc_type, expires_in, mac_key, created) VALUES('%s', '%s', '%s', '%s', %d, '%s', %d)", $op_endpoint, $assoc_response['session_type'], $assoc_response['assoc_handle'], $assoc_response['assoc_type'], $assoc_response['expires_in'], $assoc_response['mac_key'], api_get_utc_datetime()));
        $assoc_handle = $assoc_response['assoc_handle'];
    }
    return $assoc_handle;
}

 /**
  * Computes the shared secret from the private DH value $dh and the other
  * party's public value in $pub_key
  *
  * @param string $pub_key other party's public value
  * @param mixed $dh Diffie-Hellman key
  * @return string
  * @throws Zend\OpenId\Exception
  */
 public static function computeDhSecret($pub_key, $dh)
 {
     if (function_exists('openssl_dh_compute_key')) {
         $ret = openssl_dh_compute_key($pub_key, $dh);
         if (ord($ret[0]) > 127) {
             $ret = "" . $ret;
         }
         return $ret;
     } else {
         if (extension_loaded('gmp')) {
             $bn_pub_key = self::binToBigNum($pub_key);
             $bn_secret = gmp_powm($bn_pub_key, $dh['priv_key'], $dh['p']);
             return self::bigNumToBin($bn_secret);
         } else {
             if (extension_loaded('bcmath')) {
                 $bn_pub_key = self::binToBigNum($pub_key);
                 $bn_secret = bcpowmod($bn_pub_key, $dh['priv_key'], $dh['p']);
                 return self::bigNumToBin($bn_secret);
             }
         }
     }
     throw new Exception('The system doesn\'t have proper big integer extension', Exception::UNSUPPORTED_LONG_MATH);
 }

         $_SESSION["userId"] = $currentUser->userId;
     } else {
         $_SESSION["s"] = "112233445566778899aabbccddeeff00112233445566778899aabbccddeeff00";
         $_SESSION["v"] = "112233445566778899aabbccddeeff00112233445566778899aabbccddeeff00";
     }
     $_SESSION["b"] = clipperz_randomSeed();
     //				$_SESSION["b"] = "5761e6c84d22ea3c5649de01702d60f674ccfe79238540eb34c61cd020230c53";
     $_SESSION["B"] = dec2base(bcadd(base2dec($_SESSION["v"], 16), bcpowmod($srp_g, base2dec($_SESSION["b"], 16), $srp_n)), 16);
     $result["s"] = $_SESSION["s"];
     $result["B"] = $_SESSION["B"];
     //=============================================================
 } else {
     if ($message == "credentialCheck") {
         $u = clipperz_hash(base2dec($_SESSION["B"], 16));
         $A = base2dec($_SESSION["A"], 16);
         $S = bcpowmod(bcmul($A, bcpowmod(base2dec($_SESSION["v"], 16), base2dec($u, 16), $srp_n)), base2dec($_SESSION["b"], 16), $srp_n);
         $K = clipperz_hash($S);
         $M1 = clipperz_hash($A . base2dec($_SESSION["B"], 16) . $K);
         //$result["B"] = $_SESSION["B"];
         //$result["u"] = $u;
         //$result["A"] = $A;
         //$result["S"] = $S;
         //$result["K"] = $K;
         //$result["M1"] = $M1;
         //$result["_M1"] = $parameters["parameters"]["M1"];
         if ($M1 == $parameters["parameters"]["M1"]) {
             $_SESSION["K"] = $K;
             $M2 = clipperz_hash($A . $M1 . $K);
             $result["M2"] = $M2;
             $result["connectionId"] = "";
             $result["loginInfo"] = array();