People have always had a fascination or necessity of hiding information from others. History is filled with examples where people tried to keep information secret from adversaries.As society has evolved , the need for more sophisticated methods of protecting data has increased. Now , with the information era at hand , the need is more pronounced than ever.
This paper has two major purposes . First one is to explain RSA Algorithm , which is the most widely used encryption algorithm , in a simpler way. And the second one is to give information on the Attacks done on RSA Algorithm.
Overview of Cryptography
"Cryptography" can be described in the simplest form as "Science of writing in secret code" .It existed as an Art form from thousands of years.It has a secret influence on many world events."Cryptography" before the modern age is synonomous with "Encryption". Since World War 1 and the advent of Computers , the methods of Cryptology have become increasingly complex .In Modern day Context , Cryptography can be defined as "The practice and study of transforming a Plaintext by a function that is parameterized by a Key , into Ciphertext , for secure communication".
Get your grade
or your money back
using our Essay Writing Service!
Cryptography Algorithms can be broadly classified into :
Symmetric-key Algorithms : that use a single key that both the sender and recipient will have.
Public-key Algorithms : that use two keys , a Public key known to everyone and a Private key that only the recipient of message uses.
RSA is a Public-key Algorithm
How RSA Algorithm is born
In 1976 , Whitefield Diffie and Martin Hellman proposed a innovative method of distributing cryptographic keys through their paper "New Directions in Cryptography".This motivated three students of MIT and they developed the landmark Algorithm in the history of Cryptography names " RSA Algorithm "
The RSA Algorithm was publicly described in 1977 by Ron Rivest , Adi Shamir , Leonard Adleman . The letters RSA are the initials of their surnames.Their aim was to replace the less secure National Bureau of Standards (NBS) algorithm.
Picture 1: Inventors of RSA Algorithm
RSA implemented two important ideas :
1. Public-key encryption : This idea omits the need for a "courier" to deliver keys to recipients over another secure channel before transmitting the originally-intended message. In RSA, encryption keys are public, while the decryption keys are not, so only the person with the correct decryption key can decipher an encrypted message. Everyone has their own encryption and decryption keys. The keys must be made in such a way that the decryption key may not be easily deduced from the public encryption key.
2. Digital signatures : The receiver may need to verify that a transmitted message actually originated from the sender (signature), and didn't just come from there (authentication). This is done using the sender's decryption key, and the signature can later be verified by anyone, using the corresponding public encryption key. Signatures therefore cannot be forged. Also, no signer can later deny having signed the message.
The RSA algorithm
RSA Algorithm can be summarized as follows :
1) Receiver chooses two distinct large Prime numbers x and y and multiply them together to form n = pq
2) Receiver chooses k with gcd(k,(x-1),(y-1)) = 1
3) Receiver computes j with j * k â‰¡ 1 (mod(x-1)(y-1))
4) Receiver makes n and k public but x,y,j secret.
5) Sender encrypts m as c â‰¡ mk (mod n) and sends c to Receiver
6) Receiver decrypts by computing m â‰¡ Cj (mod n)
'Fermat's Little theorem" or "Euler's theorem" can be used to explain why RSA works.
Explanation of RSA algorithm through an Example
Learning through an example is the best method to understand
RSA Algorithm.Â Let us say that Sender has a piece of data and he wants to send it to the Receiver in such way that no others can read it except the Receiver.So, he encrypts the plain message and sends it to the Receiver. Upon receipt of this encrypted message, the Receiver wants to decrypt it so that he can read the original plain message. RSA algorithm deals this in the below fashion.
Generating Public Keys :
Always on Time
Marked to Standard
1)Pick two prime numbers. Let us select x = 3 and y = 13
2) Calculate n = x * y = 3 * 13 = 39
3) Calculate z = ( x - 1 ) * ( y - 1 ) = ( 3 - 1 ) * ( 13 - 1 ) = 24
4) Choose a prime number k. k should be co-prime to z, (i.e, z is not divisible by k.) Let us select k=5
5) The numbers ( n=39 , k=5) become the Public key.
Generating Private Keys :
1) Calculate j in such a way that k * j â‰¡ 1 ( mod z )
i.e 5 * j â‰¡ 1 (mod 24)
Which is equivalent to saying that the number (11*j) should give reminder 1 when multiplied by 24.This involve little bit mathematical calculations and we can arrive at j = 29.
2) The numbers ( n=39 , j=29) become the Public key.
Encrypting the Message :
1) The Message is turned into an Integer m ( where 0 â‰¤Â m < n ). If m >n , break the message into blocks. Let us take m = 10.
2) Ciphertext c â‰¡ mk (mod n)
â‰¡ 105 (mod 39)
3) 10 is encrypted as 4 and is sent to the receiver.
Decrypting the Message
1) The receiver knows n , k and receives m and decrypts using below formula
Actual message m â‰¡ Cj (mod n)
â‰¡ 429 (mod 39)
Why RSA Algorithm is Special
The essential requirement of the Public Key Cryptography is that secret keys should be mathematically related, but the relationship must be designed in such a way that it is very hard to determine by any outsider.Â In the above example , everything starts withÂ x and y,which gives n. The public key consists of n and k, where k is calculated from z and z is calculated from x and y. The secret key j, was calculated from k and z ,which are calculated from x and y. It means that j is also calculated from x and y.This proves that there is a mathematical relation between public and private keys.
So, if an outsider wants to find the secret key j, by only knowing n, he must break down n into the two prime numbers that were used to produce it . It is easy with the small numbers that we have used in our above example.But , decomposing a very large n into x and y is really difficult to do.This feature made RSA algorithm most secure key encryption algorithm.
Where RSA Algorithm is being used
Attacks on RSA Algorithm
No encryption technique is even perfectly secure from an attack by a realistic cryptanalyst. Methods such as brute-force are simple but lengthy and may crack a message, but not likely an entire encryption scheme. Since its initial publication, the RSA has been analysed for vulnerability by many researchers. Although this led to a number of fascinating attacks, none ofthem is devastating. They mostly illustrate the dangers of improper use of RSA.
Paul Kocher, while he was an undergraduate at Stanford , showed in 1995 that it is possible to discover the decryption exponent by carefully timing the computation times for a series of decryptions. There are ways to prevent these attacks, this development was unsettling.
Here is how this Timing attack works. Suppose any evil observer ( let us name as Eve) is able to observe the Receiver decrypting several ciphertexts y. Eve times how long this takes for each y. Knowing each y and the time required for it to be decrypted will allow Eve to find the decryption exponent d.
We need to assume that Eve knows about Sender's hardware in sufficient detail.
A common use of RSA is to transmit keys for use in DES(Data Encryption Standard) or AES (Advanced Encryption Standard).However a naive implementation could lead to a loss of security.Suppose a 56- bit DES key is written as a number m â‰ˆ 1017 . This is encrypted with RSA to obtain c â‰¡ mk (mod n). Although m is small , the ciphertext c is probably a number of the same size n , so perhaps around 200 digits. However , Eve attacks the system as follows.she makes two lists :
1.cp-k (mod n) for all p with 1â‰¤Â p â‰¤Â 109
2. qk (mod n) for all q with 1â‰¤Â q â‰¤Â 109
This Essay is
a Student's Work
This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.Examples of our work
Eve looks for a match between an element on the first list and an
element on one, then the second list. If she finds ones , then she has
cp-k â‰¡ qk for some p,q.
This yields c â‰¡ (pq)k (mod n)
So m â‰¡ pq (mod n).
Is this attack likely to succeed the ? Suppose m is the product of two integers p and q ,both less than 109. For these , Eve will obtain m .
This Attack is much more efficient than trying all 1017 possibilities for m, which is nearly impossible. In the present attack , Eve needs to compute and store a list of length 109 , then compute the elements on the other list and check each one against the first list.Therefore , Eve performs approximately
2 * 109 computaations which is possible to do.
It is easy to prevent this attack.Instead of using a small value of m,adjoin some random digits to the beginning and end of m so as to form a much longer plaintext.When Receiver decrypts the ciphertext , he simply removes those random digits and obtains m.
A very major threat to RSA would be a solution to the Riemann hypothesis. Thus a solution has neither been proven to exist nor to not exist. Development on the Riemann hypothesis is currently relatively stagnant. However, if a solution were found, prime numbers would be too easy to nd, and RSA would fall apart. Undoubtedly, much more sophisticated algorithms than RSA will continue to be developed as mathematicians discover more in the elds of number theory and cryptanalysis