RSA algorithm (slow, inefficient but easy to read) implemented in PHP.

rsa.php

<?php
// Very, very, VERY inefficient (but clear and easy to follow) implementation
// of encryption and decryption using the RSA algorithm.
// FOR LEARNING PURPOSES ONLY
// Tested with PHP 5.6+
// Uses the BC Math libraries to handle large numbers: http://php.net/manual/en/book.bc.php
// Run on the command line: `$ php RSA.php`

// https://www.reddit.com/r/PHPhelp/comments/1gztrp/question_calculate_modular_multiplicative_inverse/
function mod_inv($a, $b) {
    $b0 = $b;
    $x0 = 0;
    $x1 = 1;
    if ($b == 1) return 1;
    while ($a > 1) {
        $q = floor(bcdiv($a, $b));
        $t = $b;
        $b = bcmod($a, $b);
        $a = $t;
        $t = $x0;
        $x0 = bcsub($x1, bcmul($q, $x0));
        $x1 = $t;
    }
    if ($x1 < 0) $x1 = bcadd($x1, $b0);
    return $x1;
}

// http://stackoverflow.com/a/17497617/133764
function gcd ($a, $b) {
    return $b ? gcd($b, bcmod($a, $b)) : $a;
}

// Borrowed from a comment in
// http://php.net/manual/en/ref.math.php
function lcm ($n, $m) {
   return bcmul($m, bcdiv($n, gcd($n, $m)));
}

// Calculation of the RSA keys
function keys($p, $q, $e) {
    $n = bcmul($p, $q);
    $p_1 = bcsub($p, 1);
    $q_1 = bcsub($q, 1);
    $lambda = lcm($p_1, $q_1);

    assert(1 < $e, "e must be bigger than 1");
    assert($e < $lambda, "e must be smaller than lambda");
    assert(gcd($e, $lambda) == 1, "GCD(e, lambda) must be 1");

    $d = mod_inv($e, $lambda);
    assert(bcmul($e, $d) % $lambda == 1, "e * d MOD lambda must be 1");

    $public = [$e, $n];
    $private = [$d, $n];
    return [$public, $private];
}

// RSA encryption
function encrypt($message, $e, $n) {
    return bcmod(bcpow($message, $e), $n);
}

// RSA decryption
function decrypt($encrypted, $d, $n) {
    return bcmod(bcpow($encrypted, $d), $n);
}

// http://stackoverflow.com/a/18454946/133764
function stopwatch($function) {
    $time_start = microtime(true);
    $ret = $function();
    $time_end = microtime(true);
    $time_spent = $time_end - $time_start;
    return [$ret, $time_spent];
}

function display($message, $keys) {
    $public = $keys[0];
    $private = $keys[1];

    $lambda_enc = function() use ($message, $public) {
        return encrypt($message, $public[0], $public[1]);
    };
    $enc = stopwatch($lambda_enc);
    $encrypted = $enc[0];
    $encrypted_time = $enc[1];

    $lambda_dec = function() use ($encrypted, $private) {
        return decrypt($encrypted, $private[0], $private[1]);
    };
    $dec = stopwatch($lambda_dec);
    $decrypted = $dec[0];
    $decrypted_time = $dec[1];
    assert($message == $decrypted, "The decrypted message must be equal to the original");

    echo("Message: $message\n");
    echo("Encrypted: $encrypted (time: $encrypted_time)\n");
    echo("Decrypted: $decrypted (time: $decrypted_time)\n");
    echo("\n");
}

$keys = keys(61, 53, 17);
print_r($keys);

// Example taken from Wikipedia
// https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation
$message = 65;
display($message, $keys);

// Example from Twitter
// https://twitter.com/kosamari/status/838738015010848769
$keys = [[5, 323], [29, 323]];
$message = 123;
display($message, $keys);

// Very small prime numbers
$keys = keys(13, 19, 17);
$message = 123;
display($message, $keys);

// With some big prime numbers from
// http://www.bigprimes.net/
$keys = keys(541, 461, 107);
$message = 67890;
display($message, $keys);

$keys = keys(1181, 929, 173);
$message = 123456;
display($message, $keys);

// This takes around 10 seconds on a MacBook Air
$keys = keys(1181, 929, 1987);
$message = 123456;
display($message, $keys);

// This takes longer, around 40 seconds in a MacBook Air
$keys = keys(1181, 929, 17);
$message = 123456;
display($message, $keys);