We talked about the ideas behind public key cryptography last lecture. How do we implement such a scheme? This is where number theory comes to the rescue in the form of the RSA crypto system. RSA stands for Rivest, Shamir and Adelman, who discovered the scheme in 1977. Clifford Cocks had independently discovered this earlier in 1973, but his work was classified and remained unknown for many years.
A link to the original RSA paper is here.
Messages As Numbers
First, let us get some preliminary concepts out of the way. We will regard messages as numbers. The idea is that your message is encoded as a number through a scheme such as ASCII. The rest of this presentation will deal with encrypting and decrypting numbers.
Basic Idea
Suppose Alice wished to send a message
Upon receiving the message from Alice, Bob decrypts it using his private key. No one else can decrypt the message unless they have Bob's private key.
How do we implement this in practice?
The basic idea behind RSA is to create a one-way function
The reason
However, if it is hard for someone to invert
We will assume that using the private key, Bob has a function
that will allow him to compute.
So our scheme should give us functions
Number Theory to the Rescue
The basic scheme for RSA uses a really large number
The public key is a pair of numbers
The private key is a pair of numbers
.
Each message
The basic idea is to encrypt a message
Example
Let us take a message
We will simply compute
On the first sight, this modular exponentiation looks like an atrociously hard computation. But remember that
Therefore, we can first compute this by repeated squaring and modulo operations. Here is how we compute for our example using python interpreter
Example Computation
bash$ python Python 2.7.6 [v2.7.6:3a1db0d2747e, Nov 10 2013, 00:42:54] [GCC 4.2.1 [Apple Inc. build 5666] [dot 3]] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> c1 = [1098 **2] % 41989 >>> c1 29912 >>> c2 = [c1 **2] % 41989 >>> c2 26132 >>> c3 = [c2 **2] %41989 >>> c3 14317 >>> c4 = [c3 * c2] % 41989 >>> c4 9854 >>> c5 = [c4 * 1098] % 41989 >>> c5 28519
However, a snooper who simply sees the encrypted message
So far, we have identified our one way function
Now the idea is to find a private key
This means that we need
In other words, we require that
The question is how can we find a pair
Some Preliminaries
We say that two numbers
Euler's Theorem
You can skip this section on a first read
The answer comes from a result proved by Euler in 1741, called the Euler's Totient theorem. We will first examine the Totient function.
As an example, consider
Therefore
Interestingly, given a number
Totient Function for Prime Numbers
Theorem: The totient function
The proof is simply to note that every number
Another important result about Totient functions is as follows:
Totient functions for products of primes
If
Let us look at all numbers between
Here is what Euler's theorem says:
Euler's Theorem
Let
The proof is rather elegant. Let
Therefore,
We therefore conclude that
RSA Scheme
We are now ready to talk about the basic RSA scheme.
The idea is to choose two different large prime numbers
We now wish to find a pair
Choosing any message
Therefore, if we choose any positive
Therefore,
Our goal is now to find
In other words,
We follow the following steps to do so:
Choose large primes
with.Let
.Let
.Choose a number
withthat is relatively prime with.Compute
such thatfor some. This is done using the Euclidean Algorithm.
Finally, we discard
Encryption
Encrypting a message
Likewise, decryption uses the private key
Decryption
Given cipher-text
Let us illustrate this:
Encryption: Take a message
Example: Using public key
To decrypt, we have to compute
Breaking RSA
Let us assume that some one has access to the public key
After all,
Problem [Factoring] Given a number
In order to convince you that factoring a large number say
Combinatorially Hard Problems
There are problems in CS which do not have any known algorithms. The class of problems is called NP standing for Non-Deterministic Polynomial Time.
Claim Factoring a number
Naive Algorithm
int factor[int n]{ int i; for [i = 0; i < n;++i] if [Divides[i,n]] return i; return NO_FACTOR; }
Time taken to factor by best known algorithm is roughly
The best known factoring algorithm is the general number field sieve. Even though it is worst case exponential, it has been used to factor large number of upto a