| 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; |