perl/rsa.pl

   1 #!/usr/bin/env perl
   2 #http://en.wikipedia.org/wiki/RSA
   3 #http://cs.wikipedia.org/wiki/RSA
   4 use bignum; #We'll need bignum for real messages
   5
   6 sub rsa { #RSA (de)crypt function (message,modulus,exponent)
   7         my ($msg,$m,$e) = @_;
   8         ($msg**$e)%($m); #TODO: reimplement using chinese remainder theorem (this is too slow!!!)
   9 }
  10
  11 sub isprime { #Tell if number is prime or not (suboptimal)
  12         my ($num) = @_;
  13         if($num == 0) { return 1; }
  14         $num = abs($num);
  15         if($num % 2 == 0) { return 0; }
  16         for(my $i = 3; $i <= sqrt($num); $i+=2) {
  17                 if($num % $i == 0) { return 0; }
  18         }
  19         return 1;
  20 }
  21
  22 sub random_prime { #Generate random prime (suboptimal and insecure!)
  23         my ($max) = @_;
  24         for(my $i = int(rand($max)); $i => 17; $i--) {
  25                 if(isprime($i)) { return $i; }
  26         }
  27         return 17;
  28 }
  29
  30 #Generate key-pair:
  31 my $strength = 100; #How strong should be the key (insecure!)
  32 my ($p,$q) = (random_prime($strength),random_prime($strength)); #Generate some big random primes (eg: 61,53)
  33 my $phi=($p-1)*($q-1); #TODO: implement Euler's totient function for study purposes
  34 my $n = $p*$q; #modulus (public)
  35 my $e = random_prime($phi); #e=encrypt exponent (public)
  36 my $d = Math::BigInt->bmodinv(int($e), $phi); #d=decrypt exponent (PRIVATE!) (TODO: reimplement modinv() for study purposes)
  37
  38 #Example of usage:
  39 print "\t[[[ Harvie's simple RSA demo ]]]\nfor study & testing purposes only (INSECURE!!!)\n\n";
  40 print "=== KEYS ===\nPUB: ($n,$e)\nPRV: ($n,$d)\n";
  41
  42 my $msg=1337;
  43 $msg=$n-1;
  44         print "=== TEST ===\nMSG: $msg\n";
  45 my $enc=rsa($msg,$n,$e); #encrypt
  46         print "ENC: $enc\n";
  47 my $dec=rsa($enc,$n,$d); #decrypt
  48         $test=($msg==$dec);
  49         print "DEC: $dec\nTST: ".$msg.($test?"=":"!=").$dec."\n";
  50         exit !$test;