Decrypting RSA cryptosystem

This week I was busy in making my Computer Science presentation . I chose prime numbers as the topic of my presentation .

Here are some of the highlights from my presentation .

We all know what are prime numbers right ? ok let me remind you again . Prime numbers are those natural numbers which are greater than 1 and doesn't have any positive divisors other than 1 and the number itself ,

Then I presented a very simple way to generate prime numbers Sieve of Eratosthenes if you don't know what is it you can check Sieve of Eratosthenes for more details .

You must be thinking that ok prime numbers are difficult to find but what are their real world applications ? How are they useful to a layman ?

Interestingly, a layman and you too might be using prime numbers that too almost daily! How ?

We all have accounts on google,facebook,twitter,etc,. and we do online shopping also from websites like amazon,ebay,flipkart,etc,.

To keep our personal data secure these sites use some form of cryptosystem to secure our invaluable data such as messages,passwords,credit card numbers,etc,.

They use some form of RSA cryptosystem for this .

RSA algorithm is one of the most widely used algorithm in today's world . Our cyber safety relies on this method . Let's have a look how this algorithm protects us from the hackers.

Working of RSA cryptosystem -

STEP 1 - Key generation

    Public key -
    Host sites randomly generate two very large prime numbers P,Q and multiply them to get N

    For ex lets say P=53 & Q=59
    N = P*Q = 3127
    N is the first part of the public key.
    second part of the key e is selected according to the constraints that e should be 1<e<phi(N) and         gcd(e,phi(N))=1 , where phi() is Euler Totient Function.
    Click here for algorithm for gcd()
   for simplicity lets say e = 3 in our example.
   Public key is made public .That means everyone has access to numbers e and N.

  Private key -    

  This is the secret key which is not made public and is only available to host .
 
  Representing it by d it is calculating by solving d*e mod phi(N) =1 (euler's theorem is used for    calculation).

Now, you must be thinking that anyone can calculate d as everyone know N and e .This is where beauty of prime numbers lie :) .

RSA works on the principle that  Prime factorization of a number is a fundamentally hard problem . It take a lot of time to factorise a big number .It can take 1000s of years to break a very big number even with network of supercomputers with the current level of technology!

remember phi() function ? to calculate phi(N) we need to have factorisation of N known to us .

If calculation of phi is so much hard how host does it ? :) Its because host knows the factorisation of N which is P*Q and phi(Prime no.) = Prime no. - 1 and phi also obeys multiplicative property so phi(P*Q)=phi(P)*phi(Q)

STEP 2 - Encryption

Suppose user is sending a message "HI"
This message is converted to a number m by a generalised padding scheme . For simplicity lets convert alphabets to numbers according to their order i.e, A-1,B-2,C-3 and so forth.
so in our example HI gets converted to 89 H->8 I->9

Then by applying N and e on m our web browser encrypts m to c like this m^e mod N = c
Then it sends c to the host.

STEP 3 - Decryption

Host receives c and applies its secret private key d on it to get m like this c^d mod N = m
Then by reverse applying padding scheme on obtained m host gets "HI" .

This is how our data is secured. Thanks to prime numbers.

Some interesting facts -

Till now the biggest key broken is a 768 bit key . It took a team of 11 cryptographers to break it and that too in 2 years!

With present level of prime factorization technique and computational ability it is estimated that a 1024 bit key can be broken within some years.

As 1024 keys are vulnerable now, google upgraded its SSL key from 1024 bit to 2048 just 1 year back. Twitter also uses 2048 bit keys.

It is estimated that by 2030 even 2048 bit keys will be vulnerable to attacks.    

If you can break a 1024 bit key you can become famous ! and till now nobody has done that.

So,now whenever you are making an online transaction stay relaxed for security reasons as prime numbers are there to keep your data secure .

I hope you enjoyed this write up on application of prime numbers .If you want to ask or correct my mistakes do comment in the comment box .

If you liked my post subscribe to my blog for more such exciting posts . Thank You