The Recycle Bin

A repository of comments, code, and opinions.

Public Key Cryptography – RSA

with 2 comments

In this post I plan to discuss the concept of public key cryptography and explain how the RSA algorithm works.  The inspiration for this post is two fold.  First, I’m currently working on a encrypted messaging application named Scytale which should be released relatively soon and secondly because I find it particularly fascinating.

Crypto-systems fall into two separate categories, symmetric and asymmetric.  Symmetric systems use a single key for encrypting and decrypting.  A simple example of this is the Caesarian Shift cipher, which takes the alphabet and shifts it a certain number of characters.  Below is an example of a Caesarian cipher with a shift of 4 characters.

Alphabet: abcdefghijklmnopqrstuvwxyz
Shift:       defghijklmnopqrstuvwxzyabc

attack at dawn = dwwdfn aw gdyq

The symmetric key used here would be 4.  This key would have to be known by both parties involved, and kept secret from any enemies.  Of course, this is a trivial example and not a very secure was to encrypt any information.  A more modern example would be the previous encryption standard DES, or the current standard Rijndael. 

Asymmetric crypto-systems are an entirely different breed.  They are called asymmetric because one key is used for encryption and another for decryption.   The parties involved can post their respective encryption keys publicly, and keep their decryption keys to themselves.  These systems are deeply rooted in mathematics and number theory.  In this post I will explain one of the more popular asymmetric systems, RSA.

The security of RSA is based on the difficulty of calculating the prime factors of large composite numbers.  The system has three components:  Key generation, encryption, and decryption.

Key Generation
RSA Key generation
Each party that wishes to receive encrypted messages must first generate a key.  This key will have two parts, a public key and a private key.  To generate the key, two sufficiently large prime numbers are selected, p and q.  These two primes are multiplied together to form the composite number n.  The size of n is the strength of the system.  If the person wants 2048 bit encryption, then n must be a 2048 bit number.  The encrypting exponent e is now selected at random.  This can be any number, as long as it is greater than 1 and less than the Euler totient of n, and is coprime to the Euler totient of n.  The Euler totient of a number n is defined to be the number of positive integers less than n that are coprime to n. Because n is a composite number generated from two prime numbers, it is very easy to calculate it’s Euler totient (p-1)(q-1), if the two prime factors are known.  Now the decrypting, d, exponent must be calculated.  d is simply the inverse of e modulus the Euler totient of n.  The modulus operator (mod) is simply the remainder of division.  5 mod 2 is equivalent to 2, because 5/2=4 with 1 remaining.  Inverse in modulus arithmetic is trivial to find if the modding interger m (in this case the Euler totient of n) is known.  I wrote a Powershell script to solve the inverse mod which can be found here.  If the modding integer is not known however, it is quite difficult.  Here in lies the security of RSA:  for d to be calculated, the totient(n) must be known and for the totient(n) to be calculated, the prime factors of n (p and q) must be known.  Now the participants can publish their public key {e, n} while making sure to keep their private key {d, p, q} to themselves.

Encryption
RSA encryption
A plaintext message M is converted into a series of numbers (usually base 64), and split into blocks the size of n.  Each block is encrypted separately and combined together to produce the cipher text.  Each block is raised to the exponent e and modded by n.  This is generally a quick calculation because e is usually small.

Decryption
 RSA decryption
A cipher text C is broken into blocks the size of n and decrypted separately.  Each block is raised to the decrypting exponent d and modded by n.  This operation can be done quite quickly by utilizing Chinese Remainder Theorem and Fermat’s Little theorem.  CRT states that if the modding integer can be broken into prime factors, then the operation can be broken into two smaller operations and then combined together.  This is shown below:
 CRT

Yes, that looks pretty ugly, but it is significantly faster than computing the exponent without the theorem.  Because p and q are prime, d can be reduced quickly to d mod p-1 or d mod q-1, depending on the equation.  Also, since C will be larger than p and q, C can be quickly reduced to C mod p, or C mod q.  This greatly reduces the time needed to compute the plain text.

Let’s do an example.

RSA example

Simple, eh? 

RSA has it’s drawbacks though.  For starters, the cipher text size is rounded up to powers of n, meaning the message will get very large quickly.  Also, the security of the system is based the difficulty to factor n into its two prime factors.  This is a very difficult problem if n is large.  The problem is, how large does n have to be?  So far, a 1024 bit n has been factored in a fairly reasonable amount of time.  For a message to be secure, a key size of 2048 bits to 4096 bits is recommended.  As technology improves, the key size will have to grow accordingly.  Elliptic curve cryptology, which can be adapted to any algorithm, is now being used in place of standard RSA to combat the key size problem.  I will introduce elliptic cryptology in a later post.

Later I will present several other crypto-systems and introduce Scytale when it is complete.

Advertisements

Written by Nathan

November 4, 2007 at 7:32 pm

Posted in Uncategorized

Tagged with ,

2 Responses

Subscribe to comments with RSS.

  1. Thanks!! I finally ‘get’ Public key encryption for my exam tomorrow. Thanks very much! Also useful was Security Now podcast 34 [http://twit.tv/sn34]

    Ian

    May 22, 2008 at 2:42 pm

  2. Hello,
    thanks for the post! I’ve found it really easy and ‘cos you seem an expert I’m going to ask you one thing:
    do I have a mimimun key length for signing a 256-bits message with the RSA algorithm? which is it?
    Thanks in advance.

    Manuel

    November 27, 2008 at 5:36 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: