RSA Algorithm in Perl

The RSA algorithm is very cool. It basically allows the exchange of data between two parties by using a private and public key. I’m not going to try and convince or explain what RSA is. I will however show you how to do RSA in Perl from the ground up.

The Crypt::RSA module should probably be used instead. I’m not trying to reinvent this module, but rather give a practical way to describe how the algorithm works with some real Perl code.

So let’s go!

First, we do some basic setup, loading some modules that we need. The main thing here is the bignum module, which allows Perl to use some really big numbers. You should know that the RSA algorithm will have some really big numbers. This is a must. The Math::Prime::Util module is also required to generate the prime numbers. More on that next.

#!/usr/bin/perl

use strict;
use bignum;
use Math::Prime::Util ‘:all’;

Before we can do anything, we need our own public and private key pair.  Let’s get going and generate the two prime numbers.

my $p = random_strong_prime(256);
my $q = random_strong_prime(256);

Next, we calculate n=pq

my $n = $p * $q;

And we also need to calculate phi.

my $phi = ($p – 1) * ($q – 1);

We also need to pick a number for e. For some practical reason, I decided to pick 257. This will end up becoming your encryption key.

my $e = 257;

We now need to calculate the decryption key. This will end up becoming your private key, so keep this one private.

my $x = $e ** 1;
my $d = $x->bmodinv($phi);

Now we can prepare our message. The encoding is probably not the most efficient text-to-numeric conversion, but for the purpose of the example, this will suffice. Do note the the +1 -1 bit. This is to change the $m variable into a number, and not text. For some reason, the bignum module will use this. After this function, the text “hello world” will be converted into a nice big number.

At this point you can now send the public key (n and e) to the other party. They will now be able to encrypt the message.

my $message = “hello world”;
my $m = (join ( ”, map (sprintf (“%03d”,ord), split (//,$message)) )) + 1 – 1;

The message can now be encrypted using the formula c = (m ** e) % n. The numbers are getting very big, so the normal Perl formulas won’t work. Instead, we will use bignum’s bmodpow function instead.

my $c = $m->bmodpow($e,$n);

They will send you the encrypted message (c), which you will now have to decrypt using the same function.

my $M = $c->bmodpow($d,$n);

Since the message was encoded in a text-to-numeric mode, I’ll use the same mechanism to decode it.

print join (”, map(sprintf(“%s”,chr), ($M =~ /\d{3}/g))) . “\n”;

If you run the script, and you see “hello world”, the encryption and decryption worked ok.

Here’s the full script.

#!/usr/bin/perl
 
# RSA Encryption example by Phil Massyn (www.massyn.net)
# July 10th 2013
 
use strict;
use bignum;
use Math::Prime::Util ':all';
 
# == key generation
my $p = random_strong_prime(256);
my $q = random_strong_prime(256);
 
my $n = $p * $q;
 
my $phi = ($p - 1) * ($q - 1);
 
my $e = 257; # need to figure out how to calculate it
 
my $x = $e ** 1;
my $d = $x->bmodinv($phi);
 
# == encryption
my $message = "hello world";
my $m = (join ( '', map (sprintf ("%03d",ord), split (//,$message)) )) + 1 - 1;
 
my $c = $m->bmodpow($e,$n);
 
# == decryption
my $M = $c->bmodpow($d,$n);
 
print join ('', map(sprintf("%s",chr), ($M =~ /\d{3}/g))) . "\n";
 
exit(0);

Tags:

Leave a Reply

Your email address will not be published. Required fields are marked *