Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A thread for learning RSA algorithm

  1. Jul 13, 2005 #1
    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.
     
  2. jcsd
  3. Jul 13, 2005 #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.
     
  4. Jul 13, 2005 #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: Jul 13, 2005
  5. Jul 13, 2005 #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).
     
  6. Jul 13, 2005 #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).
     
  7. Jul 13, 2005 #6
    I sent remaining as a attachment.
     

    Attached Files:

    • rsa.doc
      rsa.doc
      File size:
      16 KB
      Views:
      57
  8. Jul 13, 2005 #7
    post tutorials about prime no generation,Large integer multiblication & extented euclidean algorithm.It will be useful for beginners.Make this thread more active
     
  9. Aug 23, 2005 #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
     
  10. Aug 24, 2005 #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.
     
  11. Sep 11, 2005 #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...:)
     
  12. Sep 11, 2005 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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)
     
  13. Oct 3, 2010 #12
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A thread for learning RSA algorithm
  1. RSA help please (Replies: 3)

  2. RSA-200 Factored (Replies: 13)

  3. Eigenvalue Algorithm (Replies: 0)

  4. Householder algorithm (Replies: 13)

Loading...