A thread for learning RSA algorithm

[aravindsubramanian]

Hai friends
I am aravind,doing post graduate in computer science .In this thread I explain about the maths behind RSA algorithm in a simple way.I think this thread is useful for beginners who are interested in learning RSA algorithm.If anyone interested in this thread give reply.

 

[aravindsubramanian]

requirement for RSA algorithm

With the ever-increasing popularity of electronic communication, data security is becoming a more and more important issue nowadays. Till 1960's, Cryptography was used as tool to protect national secrets and strategies. In late 1960's, due to the usage of computers and communication systems, cryptography is in demand from the private sector for their protection of information and security. At those days key distribution is the biggest problem in cryptography. In the most striking development in the history of cryptography came 1n 1976 when the Diffie and Hellman published their paper "New Directions in Cryptography”. This paper introduces a revolutionary concept of public key cryptography and also provided a new and ingenious method for key exchange. In 1978, Rivest, Shamir, and Adleman proposed the RSA public-key cryptosystem which is the first usable public-key cryptosystem used for both data encryption and authentication, based on the one-way function of integer factorisation, where it is easy to construct a large number which is the product of prime powers, but hard to factorise the resultant number back into its constituents. RSA has been expanded and improved upon and is currently the most widely used cryptosystem. The basis behind this algorithm is quite mathematical in nature, and uses several concepts from number theory and abstract algebra.

 

[aravindsubramanian]

A One Way Function

The challenge of public-key cryptography is developing a system in which it is impossible (or at least intractable) to deduce the private key from the public key. This can be accomplished by utilizing a one-way function.With a one-way function, given some input values, it is relatively simple to compute a result. But we start with the result, it is extremely difficult to compute the original input values. In mathematical terms, given x, computing f(x) is easy, but given f(x), it is extremely difficult to determine x.
It turns out that multiplication can be a one-way function. It is easy (especially on computers) to multiply two big prime numbers. But for most very large numbers, it is extremely time-consuming to factor them.
We can utilize this one-way function in cryptography. We want to build a cryptosystem which somehow uses two large prime numbers to build the private key and the product of those primes to build the public key. The RSA algorithm uses this concept.

 

[aravindsubramanian]

Euler’s Phi-function

In the eighteenth century, the mathematician Leonhard Euler (pronounced “Oiler”) described f(n) as the number of numbers less than n that are relatively prime to n. The character f is the Greek letter “phi”. This is known as Euler’s phi-function. Remember that relatively prime means that the two numbers have a GCD of 1. In fact it is true that for any prime number, p: f(p) = p - 1.Then for any number n that is the product of two distinct (i.e. not the same) primes p and q: f(n) = f(p)f(q). i.e. f(n) = (p - 1) (q - 1).

 

[aravindsubramanian]

Euler’s Phi-function

In the eighteenth century, the mathematician Leonhard Euler (pronounced “Oiler”) described f(n) as the number of numbers less than n that are relatively prime to n. The character f is the Greek letter “phi”. This is known as Euler’s phi-function. Remember that relatively prime means that the two numbers have a GCD of 1. In fact it is true that for any prime number, p: f(p) = p - 1.Then for any number n that is the product of two distinct (i.e. not the same) primes p and q: f(n) = f(p)f(q). i.e. f(n) = (p - 1) (q - 1).

 

[aravindsubramanian]

I sent remaining as a attachment.

 

[aravindsubramanian]

post tutorials about prime no generation,Large integer multiblication & extented euclidean algorithm.It will be useful for beginners.Make this thread more active

 

[Castilla]

Aravind, do you know if there is some public key criptography that uses tools from calculus? I understand that is not the case of RSA criptography.

Regards,

Castilla

 

[aravindsubramanian]

I don't know about it.May be some probaplistic public key algorithms uses the tools from calculus.I am not sure about it.

 

[narenst]

hi ppl,
yeah this is a nice thread reg rsa algorithm.aravind cud u tell in detail abt the working of a public key algorithm,with an example if possible.
gud work n keep going...:)

 

[matt grime]

Google for it; don't wait for someone to post it. RSA is well known and relatively simple to understand (obvisouly it toook a while for anyone to see potential)

 

[Devhans]

When I wanted to learn and understand the RSA algorithm, I found this interesting animation describring the ideas and maths behind the cipher:
http://cryptool.org/download/RSA/RSA-Flash-en/player.html

Good luck!