Commit | Line | Data |
---|---|---|
8d7c3587 H |
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) = @_; | |
7189c931 | 8 | ($msg**$e)%($m); #TODO: reimplement using chinese remainder theorem (this is too slow!!!) |
8d7c3587 H |
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; | |
7189c931 | 43 | $msg=$n-1; |
8d7c3587 H |
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 | |
ecdf2356 H |
48 | $test=($msg==$dec); |
49 | print "DEC: $dec\nTST: ".$msg.($test?"=":"!=").$dec."\n"; | |
50 | exit !$test; |