How does the RSA public key encryption works?

Question

Someone told me the math behind it was very simple, so I'm wondering how can it be considered secure.

Whoa! And the guy said it was very simple! LOL
Nice answers guys!

Answer 1

For an accurate description go to http://en.wikipedia.org/wiki/RSA_encryption

Still I'd like to give you an earthling description, just in case it proves too mind boggling ;)

The algorithm was described in 1977 by Ron Rivest, Adi Shamir and Len Adleman at MIT; the letters RSA are the initials of their surnames.

The math is conceptually simple, but because extremely large numbers are crunched, it requires the kind of speed and precision that would be impractical without computers, still if you must know, it works like this:

1.Take two very large numbers, p and q, find their product (n=pq); n is called the modulus

2.Choose a number, e, less than n and relatively prime to (p-1)(q-1). A relatively prime number is a prime number until proven otherwise and likely to be in the region of 2 exp255, that means, pretty huge

3.Find its inverse, d, mod(p-1)(q-1), which means that ed=1mod(p-1)(q-1); e and d are called the public and private exponents respectively

4. The public key is the pair (n,e)

5. The private key is d

6. The factors p and q must be kept secret or otherwise destroyed

7. Obtaining the private key d from the public key (n,e) is difficult. If you could factor n into p and q, however, then you could obtain the public key.

The security of public key encryption rests on the assumption that factoring is dificult. A 1,024 bit key could take decades of supercomputer power to break by brute force alone.

However, an easy factoring method would break the code. So far no one has found one, but people (like you, maybe? JK) are still looking.

Answer 2

Hmm, I find encryption quite difficult to fully understand. However, you don't need to be an expert to use it. PC World has a decent article about how encryption works using both public and private keys.

"How It Works: Encryption: Encryption hides your data from prying eyes. Learn how it works and what you need to use it." -- by pcworld.com (http://www.pcworld.com/article/15230-1/article.html)

If you're not paranoid, maybe you should be. If you use a PC, unscrupulous types can intercept e-mail you send, and coworkers could be reading your documents. Encryption--the process of encoding data so that it requires a special key to be read--can protect your data from prying eyes. Once the domain of spies, encryption is fast becoming an advisable precaution for businesses and home users: It's your best tool for protecting your trade secrets and privacy.

Whether your encryption program is stand-alone or built into your e-mail app, the encryption process is the same: Data passes through a mathematical formula called an algorithm, which converts it into encrypted data called ciphertext. These formulas require one variable from you--called a key--which makes it difficult, if not impossible, for anyone else to crack the encryption.

There are two types of encryption: symmetric and asymmetric (also called public key). With symmetric encryption, you run a file through the program and create a key that scrambles the file. Then you e-mail the encrypted file to the recipient and separately transmit the decoding key (which could be a password or another data file). Running the same encryption application, the recipient uses the decoding key to unscramble the message. Symmetric encryption is fast but not as safe as asymmetric encryption because someone could intercept the key and decode the messages. But because of its speed, it's commonly used for e-commerce transactions.

Asymmetric encryption is more complex--and more secure. Two related keys are required: a public key and a private key. You make your public key available to anyone who might send you encrypted information. That key can only encode data; it cannot decode it. Your private key stays safe with you. When people wish to send you encrypted information, they encrypt it using your public key. When you receive the ciphertext, you decrypt it with your private key. Asymmetric encryption's added safety comes at a price: More computation is required, so the process takes longer.

Symmetric and asymmetric encryption use different algorithms to produce ciphertext. In symmetric encryption, the algorithm divvies up data into small chunks called blocks. It then switches letters around, changes the information in each block into numbers, compresses and expands the data, and runs those numbers through mathematical formulas that include the key. Then the algorithm repeats the process, sometimes dozens of times over. An asymmetric encryption's algorithm, on the other hand, treats the text as though it were a very large number, raises it to the power of another very large number, and then calculates the remainder after dividing it with a third very large number. Finally, the remainder number is converted back into text. Encryption programs can use the same algorithms differently, which is why the recipient needs to use the same application to decode the message that you used to encode it.

Keys are the final piece in the encryption puzzle. Keys vary in length and, consequently, in strength. The reason: The longer the key, the greater the number of possible combinations. For example, if your encryption program uses 128-bit keys, your particular key could be any of more than 3.4 trillion billion billion billion--or 2 to the power of 128--possible combinations of zeros and ones. A hacker is more likely to win the lottery than to crack that level of encryption using the brute-force method (systematically trying key combinations until they find the right one). By comparison, encryption experts can crack the average 40-bit symmetric key in about six hours on a typical home PC using brute force. However, even 128-bit encryption is vulnerable to some extent; pros have some sophisticated techniques that can help them crack even the toughest codes.

Answer 3

Based on a public key system, which means that every user has 2 digital keys - one to encrypt information, and the other to decrypt. Authentication of both sender and recipient is provided with this method.
www.vikont.com/clients/glossary.htm

It is not so much the math that makes it secure but that you need to have the 'key' to decript it.