How to use PHP and GMP to perform RSA encryption and decryption algorithms for large integers

How to use PHP and GMP to perform RSA encryption and decryption algorithm for large integers

RSA encryption algorithm is an asymmetric encryption algorithm that is widely used in the field of data security. It implements the process of public key encryption and private key decryption based on two particularly large prime numbers and some simple mathematical operations. In the PHP language, the calculation of large integers can be realized through the GMP (GNU Multiple Precision) library, and the encryption and decryption functions can be realized by combining the RSA algorithm. This article will introduce how to use PHP and GMP libraries to implement RSA encryption and decryption algorithms for large integers, and give corresponding code examples.

1. Generate RSA public and private key pairs

In the RSA algorithm, both the public key and the private key are generated from a pair of large prime numbers. First, we need to generate two large prime numbers $p$ and $q$.

function generatePrime($bits) {
    do {
        $num = gmp_strval(gmp_random_bits($bits));
    } while (!gmp_prob_prime($num));
    return gmp_init($num);
}

$bits = 1024; // 生成的素数位数
$p = generatePrime($bits);
$q = generatePrime($bits);

Next, we need to calculate $n$ and $phi(n)$, where $n=pq$, $phi(n)=(p-1)(q-1)$.

$n = gmp_mul($p, $q);
$phi_n = gmp_mul(gmp_sub($p, 1), gmp_sub($q, 1));

Then, we choose an integer $e$ as the public key index, satisfying $1

$e = gmp_init(65537); // 公钥指数（一般固定为65537）

Using the extended Euclidean algorithm, we can calculate the private key index $d$, which satisfies $dequiv e^{-1}pmod{phi(n)}$.

function extendedEuclidean($a, $b) {
    if (gmp_cmp($b, 0) === 0) {
        return ['x' => gmp_init(1), 'y' => gmp_init(0)];
    }
    $result = extendedEuclidean($b, gmp_mod($a, $b));
    return [
        'x' => $result['y'],
        'y' => gmp_sub($result['x'], gmp_mul(gmp_div_q($a, $b), $result['y']))
    ];
}

$d = extendedEuclidean($e, $phi_n)['x'];

Finally, we got the RSA public key $(n, e)$ and private key $(n, d)$.

2. Encryption and decryption process

Using the generated public key and private key, we can perform the RSA encryption and decryption process.

function rsaEncrypt($msg, $n, $e) {
    $msg = gmp_init($msg);
    $result = gmp_powm($msg, $e, $n);
    return gmp_strval($result);
}

function rsaDecrypt($cipher, $n, $d) {
    $cipher = gmp_init($cipher);
    $result = gmp_powm($cipher, $d, $n);
    return gmp_strval($result);
}

During the encryption process, we convert the plaintext message into a large integer $msg$, and then use the public key exponent $e$ and the modulus $n$ to calculate to obtain the ciphertext $cipher$. During the decryption process, we convert the ciphertext $cipher$ into a large integer, and then use the private key exponent $d$ and the modulus $n$ to perform calculations to obtain the decrypted plaintext message.

3. Sample code

The following is a complete sample code, including the generation of RSA public and private key pairs and the encryption and decryption process.

function generatePrime($bits) {
    do {
        $num = gmp_strval(gmp_random_bits($bits));
    } while (!gmp_prob_prime($num));
    return gmp_init($num);
}

function extendedEuclidean($a, $b) {
    if (gmp_cmp($b, 0) === 0) {
        return ['x' => gmp_init(1), 'y' => gmp_init(0)];
    }
    $result = extendedEuclidean($b, gmp_mod($a, $b));
    return [
        'x' => $result['y'],
        'y' => gmp_sub($result['x'], gmp_mul(gmp_div_q($a, $b), $result['y']))
    ];
}

function rsaEncrypt($msg, $n, $e) {
    $msg = gmp_init($msg);
    $result = gmp_powm($msg, $e, $n);
    return gmp_strval($result);
}

function rsaDecrypt($cipher, $n, $d) {
    $cipher = gmp_init($cipher);
    $result = gmp_powm($cipher, $d, $n);
    return gmp_strval($result);
}

$bits = 1024; // 生成的素数位数
$p = generatePrime($bits);
$q = generatePrime($bits);

$n = gmp_mul($p, $q);
$phi_n = gmp_mul(gmp_sub($p, 1), gmp_sub($q, 1));

$e = gmp_init(65537); // 公钥指数（一般固定为65537）

$d = extendedEuclidean($e, $phi_n)['x'];

$msg = 'Hello, RSA!';
$cipher = rsaEncrypt($msg, $n, $e);
$decryptedMsg = rsaDecrypt($cipher, $n, $d);

echo "明文消息：" . $msg . "
";
echo "加密后的密文：" . $cipher . "
";
echo "解密后的明文消息：" . $decryptedMsg . "
";

The above code implements the RSA encryption and decryption algorithm for large integers using PHP through the GMP library. You can modify the parameters and logic in the code according to your specific needs. Through understanding and practice, I believe everyone can master and flexibly apply this basic cryptographic algorithm.

The above is the detailed content of How to use PHP and GMP to perform RSA encryption and decryption algorithms for large integers. For more information, please follow other related articles on the PHP Chinese website!