Skip to content

Instantly share code, notes, and snippets.

@akosma
Last active March 11, 2017 15:16
Show Gist options
  • Save akosma/9058c43c76da2e6691637b1332058ddc to your computer and use it in GitHub Desktop.
Save akosma/9058c43c76da2e6691637b1332058ddc to your computer and use it in GitHub Desktop.
RSA algorithm (slow, inefficient but easy to read) implemented in 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment