A thread for learning RSA algorithm

In summary, the RSA algorithm is a public-key cryptosystem that uses a one-way function to protect data. It was proposed in 1978 by Rivest, Shamir, and Adleman and is currently the most widely used cryptosystem.
  • #1
aravindsubramanian
23
0
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.
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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.
 
Last edited:
  • #4
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).
 
  • #5
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).
 
  • #6
I sent remaining as a attachment.
 

Attachments

  • rsa.doc
    16 KB · Views: 218
  • #7
post tutorials about prime no generation,Large integer multiblication & extented euclidean algorithm.It will be useful for beginners.Make this thread more active
 
  • #8
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
 
  • #9
I don't know about it.May be some probaplistic public key algorithms uses the tools from calculus.I am not sure about it.
 
  • #10
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...:)
 
  • #11
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)
 
  • #12
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 [Broken]

Good luck!
 
Last edited by a moderator:

1. What is RSA algorithm?

RSA algorithm is a public-key cryptographic algorithm used for secure communication and digital signatures. It was developed by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977. RSA stands for their surnames.

2. How does RSA algorithm work?

RSA algorithm uses a combination of public and private keys to encrypt and decrypt messages. The public key is used for encryption and can be shared with anyone, while the private key is used for decryption and must be kept secret by the owner.

3. Why is RSA algorithm considered secure?

RSA algorithm is considered secure because it is based on the mathematical difficulty of factoring large prime numbers. The larger the key size, the harder it is to break the encryption. It is also difficult to determine the private key from the public key.

4. What are the common applications of RSA algorithm?

RSA algorithm is commonly used for secure communication, such as in online banking and e-commerce transactions. It is also used for digital signatures to ensure the authenticity and integrity of digital documents.

5. Are there any drawbacks to using RSA algorithm?

One potential drawback of RSA algorithm is its relatively slow speed compared to other encryption algorithms. It also requires the use of large key sizes to maintain its security, which can be resource-intensive. Additionally, if the private key is compromised, it can lead to a complete breakdown of the system's security.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Programming and Computer Science
Replies
14
Views
1K
  • Programming and Computer Science
Replies
8
Views
973
  • Quantum Physics
Replies
1
Views
744
  • STEM Career Guidance
Replies
11
Views
596
  • Quantum Physics
Replies
11
Views
2K
  • Programming and Computer Science
Replies
7
Views
931
  • STEM Academic Advising
Replies
5
Views
809
  • Feedback and Announcements
3
Replies
71
Views
3K
  • Art, Music, History, and Linguistics
Replies
11
Views
521
Back
Top