Fighting with computers

Computers are not always friendly.

Wednesday, September 28, 2011

A bit more RSA

I really don't like when I do not understand anyone's code, so it takes me a bit of effort till I do my own homework to create my own version of things I can understand. Being a teacher, I always find troubling not to be able to explain things to my students, so I used some time to create my very own RSA implementation. I've found a very good reference text here.

My perl program takes three parameters data, encryption (or decryption) exponent and module and it returns the encrypted (or decrypted) version. As it uses BigInt library it should be happy dealing with any of your big numbers. You can find a Java implementation in the above mentioned text too.

#!/usr/bin/perl 
use Math::BigInt;
if($#ARGV<2) 
     {print "Usage: exp, module\n"; exit 2;}
$a = Math::BigInt->new($ARGV[0]);
$b = Math::BigInt->new($ARGV[1]);
$c = Math::BigInt->new($ARGV[2]);
print "out=".($dec = $a->bmodpow($b,$c))."\n";
Contrary to what may look, bmodpow has been implemented to be computationally efficient using repeated squaring technique.
Example:
I have created an RSA keypair before choosing public exponent to be 3. The numbers seem to come out of thin air but I created them with a software tool mentioned in the previous RSA post. The plaintext 1234567890 (as a number and not as string) was selected as it was easy to type.
$ perl myRSA.pl 1234567890 3 0x102421060aad49ec2521203b28
ffdccc73b2b55b7e4f6e73b5ad31dcc240cdc8883fd220fff0a218d16
ec6cbd8a713aa907bd9ac46fd4f622b639de83aa5f4f752f6953960a
363e7c18d3bbdb7b93ff5c9ee07a2de7ba1fe46545da35d1cb92f926
c691e7415b253ad9047547285bc79e0ad915ac2b2b83722ad3d8fc
001aab7
cyphertext = 1881676371789154860897069000

$ perl myRSA.pl 1881676371789154860897069000 0xac2c0aeb1
c8dbf2c36b6ad21b553ddda27723925434f44d23c8cbe8818089305
ad536c0aaa06c108b9f2f32906f6271b5a7e672d9fe34ec1ced13f02
7194df9e19960c0e9b793efd65c4a68f9cabfa1dbe904d5ade76bf2d
83091c17d687b6d04323abd935676379e5ada2cf6892846586360d9
80c9a2cec1bd7cff55566a6b 0x102421060aad49ec2521203b28ffdc
cc73b2b55b7e4f6e73b5ad31dcc240cdc8883fd220fff0a218d16ec6c
bd8a713aa907bd9ac46fd4f622b639de83aa5f4f752f6953960a363e7
c18d3bbdb7b93ff5c9ee07a2de7ba1fe46545da35d1cb92f926c691e
7415b253ad9047547285bc79e0ad915ac2b2b83722ad3d8fc001aab7
cyphertext = 1234567890

Update: I've found that Crypt::OpenSSL::Bignum is more than a thousand times faster doing the modular exponentiation of RSA. So avoid the BigInt approach if speed matters to you.

0 Comments:

Post a Comment

<< Home