The RSA Encryption Algorithm Explained

RSA is one of the most popular encryption algorithms around. It was invented in 1977 by three MIT scientists; Ronald Rivest, Adi Shamir and Leonard Adelman. This algorithm uses very very large prime numbers to generate public and private keys. For more details about the implementation of the RSA algorithm, read on.

The entire RSA algorithm is based on the concept of factoring. Factoring is very easy to calculate i.e. an algorithm based on factoring can easily be carried out, however, the strength of an algorithm based on factoring lies in the fact that factoring is quite difficult to reverse. So, encrypting data using a factoring algorithm can be done without much of a problem, however to decrypt or crack an algorithm using a factoring algorithm is not that easy.

Say you have two numbers x and y. Now it is relatively easier to find out the final numbers when they are multiplied by a number N, however on the other hand, if only N is know to us, then it is not easy to calculate x and y. On top of this in RSA, N is very large number. This makes the calculation all the more difficult. RSA uses factors of around 150 digits, making it not only impossible for manual calculation but also making sure that the RSA encryption cannot be cracked within a feasible amount of time.

In case of the encryption process, as RSA is a block encryption algorithm, the entire data is broken into blocks and each block is treated as a sequence of bits, with the number of digits being just a little less than N. Each block is considered as a single digit, and multiplied ‘e’ number of times by itself, [In the case of PGP, e is normally 17]. The result thus obtained, is divided by N and the remainder obtained is the final encrypted message.

In case of the decryption process, the recipient, makes use of another special number; ‘k’ where (ke-1) is divisible by (p-1)(q-1). The value k is chosen such that multiplying the encrypted message k times by itself and then dividing by N, gives the original message as the remainder. So basically to find out k, p and q should be known.

e and N constitute the public key which can be freely distributed, while k forms the private key, which should be kept a secret.

Note: In this case, e and k and symmetric.

To understand the working of the RSA algorithm, study the following Perl program which implements it.

#!/usr/local/bin/perl -s-- #export-a-crypto-system sig, RSA in 4 lines PERL:

#

# -d (decrypt)

# or -e (encrypt)

#

# $k is exponent, $n is modulus; $k and $n in hex

#

# use of -s was contributed by Jeff Friedl, a cool perl hacker

#

# the $e-$d (grok that? awesome hack by Jeff also) checks for -d or -e:

#

# when perl -s sets $x for -x so that means $d is set for -d, $e for -e

# if they are both set 1-1 = 0 so it fails if neither are set it fails

# and if either one is set we're ok! This is to get around using | ,

# as | has higher precedence than & things group wrongly.

#

$e-$d&(($k,$n)=@ARGV)==2||die"$0 -d|-e key mod <in >out\n";

#

# $v will be the digits of output per block, $w the digits of input per block.

# If encrypting need to reduce $w so input is guaranteed to be less than

# modulus; for decrypting reduce $v to match.

#

# blocks are based on modulus size in hex digits rounded up to nearest even

# length (~1&1+length$n) so that things will unpack properly

#

$v=$w=1+length$n&~1;

$v-=$d*2:$w-=$e*2;

#

# Make $_ be the exponent $k as a binary bit string

#

# Add a leading 0 to make length of $k be even so that it will fill

# Bytes when packed as 2 digits per byte

#

$_=unpack('B*',pack('H*',1&length$k?"0$k":$k));

#

# strip leading 0's from $_

#

s/^0+//;

#

# Turn every 0 into "d*ln%", every 1 into "d*ln%lm*ln%". These are dc codes

# which construct an exponentiation algorithm for that exponent.

# "d*ln%" is duplicate, square, load n, modulus; e.g. square the number

# on the stack, mod n. "d*ln%lm*ln%" does this then, load m, multiply,

# load n, modulus; e.g. then multiply by m mod n. This is the square and

# multiply algorithm for modular exponentiation.

#

# (Kudos to Hal for shortened this one by 4 chars)

#

s/1/0lM*ln%/g;

s/0/d*ln%/g;

#

# Encryption/decryption loop. Read $w/2 bytes of data to $m.

#

while(read(STDIN,$m,$w/2)){

#

# Turn data into equivalent hex digits in $m

#

$m=unpack("H$w",$m);

#

# Run dc: 16 bit radix for input and output; $m into dc register "M";

# $n into dc register "n"; execute $_, the exponentiation program above.

# "\U...\E" forces upper case on the hex digits as dc requires.

# Put the result in $e.

#

$a=`echo 16oOi\U$m SM$n\Esn1$_ p|dc`;

#

# Pad the result with leading 0's to $v digits, pack to raw data and output.

#

print pack("H$v",'0'x($v+1-length$a).$a);

}

[Ankit Fadia's Algorithms Explained]