Can you explain RSA encryption keys in simple enough language for me?

Asked by Jeruba (45850) March 25th, 2012

I’ve read about RSA encryption, public and private keys, and Diffie-Hellman again and again, and I’m still having trouble with the concept.

One of the things that slow me down is the public vs. private key part. If you have a private key, what do you want a public key for? What’s the point of using a lock anybody can pick along with a lock to which there’s literally only one key? Why bother with the public key at all?

To make it simple enough for me, you’ll probably have to use an analogy or metaphor. Never mind a mathematical formula; they just hit my blind spot.

Observing members: 0 Composing members: 0

As I understand it (general disclaimer)

The public key serves two purposes

1) “Hey, I’m using <blank> encryption, so we’ll have to converse using that, ok?”
2) “Here’s the decoder ring I’m going to use on your private key, make sure it matches”

So the public key has to be public because there’s nothing that comes before it but it’s also under the control of the side that is theoretically holding the valuable information, so can be changed at any time. It’s the lock, there for anyone to try their key in, the private key is the key brought by the person trying to enter.

If I don’t want your key to work anymore, I just change the lock, since I can’t necessarily take your key.

Thanks, @funkdaddy. I need the whole picture and not just that part of it.

Jeruba (45850)

Again, As I understand it

Encryption methods generally differ in the math portion, and the scheme, so without talking about the math, there’s only a few types.

So RSA, minus the math, is really similar to any public/private key scheme (sort of) discussed above.

It can be used in a lot of different ways so maybe a real world example is what you’re looking for? Something less theoretical? Or do you have a use in mind and someone walking through that use step by step would help?

Suppose that you have a public site which you want people to communicate with confidentially. That is, you want to ensure that if a message that is sent to you is intercepted by someone else, the contents will be unreadable. To do this, you make known your public key, with which anyone can encrypt data to send to you. The only way that the message can be decrypted is by using your private key.

Without going into the gory details, the determination of the private key from the public key is a puzzle that could, in principle, by solved by someone who knows the public key, but the time required to do so, even with the most advanced computers, is most unreasonable. The essence of the idea behind the public key is that it is a number with hundreds of digits that is the product of two prime numbers. Knowing the prime factorization provides a back door to solving the puzzle. Currently there is no efficient way of finding the prime factors of a number.

Public/private keys are called asymmetric, because the encoding key is different from the decoding key. In practice, public key encryption is not very efficient, compared to symmetric keys, where the encoding key and the decoding key are the same . The way that public key encryption is used is to encrypt a symmetric key that is used to encrypt the rest of the message. The recipient of the message uses the private key to decode the symmetric key, which is then used to decode the rest of the message. For obvious reasons, the symmetric key cannot be made public.

Once you encrypt a message with a public key, you cannot use the same public key to decrypt it. You need the private key. Pretty slick!:
http://en.wikipedia.org/wiki/Public-key_cryptography

RocketGuy (9097)

I appreciate all answers. But I’m still not getting the help I need. You’re assuming I know more than I do. The problem with these explanations—and those I find by looking up articles in Wikipedia and such places—is that they don’t get basic enough. No use explaining an internal combustion engine to me if I don’t really know what a car’s motor does.

So okay, I understand the basic idea of cryptographic encoding, which is to make the contents of a message readable only to an authorized recipient. This is an ancient idea that has been executed in many forms over the millennia.

In computer technology, secure sending and receiving of electronic data depend on encryption and decryption using various algorithms that supposedly can’t be known to or guessed at by unauthorized third parties. In practice many such algorithms can be broken by deduction or brute force.

Right so far?

So then—here’s where I am. RSA keys come into the picture by altering the basic logic of encryption and decryption keys to create encryption that is practically impossible to compromise. Right? And the logic of their approach is ____.

And what this means in practice is ____.

As an analogy, this would be like ____.

For example, ____. (?)

I thank you.

Jeruba (45850)

@Jeruba I think the problem is that you understand more than people are assuming you do, not less. :)

I think that you might enjoy this work of popular science.

dappled_leaves (15834)

You’ve probably gotten a lot of this from your reading, but hopefully can help with at least one piece by walking through it.

RSA uses keys based on two big prime numbers. Your public key is a consistent algorithm using those two numbers, plus some fluff mixed in to make the ends neat and make that little bit harder to figure out what’s “meat” and what’s “fluff”.

The reason this is useful is because there isn’t a quick way to find all the factors of a big number. For example, you can tell if a number is divisible by two or three pretty easily, but if I give you a Real Big Number (RBN) and the number 43,769,461 the only way to figure out if it’s a factor of RBN is to try it out.

They use prime numbers because then there’s only one path each way to get our two unique factors from RBN. There are no “false” matches where it just happens to match up with what we’re looking for because it’s another factor. Some types of encryption can have more than one matching answer so you might have two or more, making it take half the time (or less) to find a “solution”.

So an analogy might be if I gave you a string of 40 numbers that included a section that was the product of multiplying my social security number by my phone number and then asked you to give me a call. Even if you knew the format of both numbers, you’d have a hard time figuring out one without the other. It would be even harder if the numbers were of unknown length, and harder still if they varied in length from say 15 to 30 digits (or more). It’s just a lot of ground to cover.

So to cover that ground, you’d basically have to take the RBN, determine what’s fluff, trim the fluff, take a guess at a possible factor, get the other factor, run it through your algorithm and then test that against your message to see if you got anything useful. If not, you try again.

If there are millions or billions (I really have no idea) of possibilities, that’s a computationally intensive routine to keep running, and takes real time no matter what kind of processing power you have. Since you’re basically just making a guess, and then figuring out what the next possible guess would be, and trying that.

The private key includes one of the numbers, so it can easily figure out the other with that and is the reason you can easily read the message with the key.

The math, the algorithm, the number length, how the numbers are generated, and the other details are all variables that can be used to keep it from being one process from start to finish. Which leaves some blanks for anyone trying to read the message to fill in.

RSA has a set algorithm, but as I understand it, leaves the rest up to implementation.

Help at all?

Thanks for trying but…

You know that old joke where the little kid comes home from school and asks his mother, “Where did I come from?” She knew this day would come, and so she takes a deep breath, sits down, and patiently explains to him all about mommies and daddies and how when they love each other they can make babies. The kid listens wide-eyed. When she finally stops and asks if that’s what he wanted to know, he says, “No. There’s a new kid at school and he says he comes from Cleveland. Where did I come from?”

Well, I just want the equivalent of Cleveland here. I don’t want to know about algorithms and prime numbers. That’s the kind of stuff I keep reading about, and it’s too close a focus. It’s the engine and not the car. I’m still driving a horse and buggy, say. I need a framework. What I want to know is, what’s the basic logic that makes this crypto solution different? What was the breakthrough? What does it do?

Like—like this, ok? People have been writing for centuries. In all past eras, writing involved some form of applying signs and symbols to a concrete object. Whether it was a wedge pressed into soft clay, a chisel cutting stone, or a transfer of a visible substance from one surface to another, writing meant generating hard copy. Computers and word processing have created a new model for writing in which the symbols are stored as digital values without there necessarily ever being any material representation of the text at all. This is different. It entails a different process and a different logic from charcoal on bark or ink on a printing press.

How would you explain this kind of crypto encoding to someone who didn’t know anything about computers? How would you explain the difference between this and, say, the old favorite key based on two people having copies of the same book? or the alphabet substitution cipher using a single ten-letter word as a key? or a set of angles and dots with agreed-upon meaning? What is special about the Diffie-Hellman/RSA solution?

Getting very close to giving up here.

Jeruba (45850)

The Diffie-Hellman/RSA solutions are about assigning and interpreting encryption keys – as I understand it, they act sort of like decoder rings. The keys carry the information about how to interpret the text.

The keys themselves are based on the problem of factorizing large prime numbers. The book I provided a link for is about that problem, and other interesting properties of primes (really, it’s worth a read). Trying to predict when the next prime number occurs becomes harder and harder (like, ridiculously hard) when the numbers are large. RSA keys take advantage of this classic problem by using two very large prime numbers (as @funkdaddy explained above). If it were easy to factorize primes, it would be easy to hack an RSA encrypted text. But it’s not. Is that the “breakthrough” you are asking about?

dappled_leaves (15834)

One last shot, then I’ll leave it to others better equipped.

Basically there’s no magic about RSA. So there’s no huge breakthrough, it’s just a clever trick to make big numbers manageable with the key, but unmanageable without.

So screw the numbers and messages, we’re protecting gold, and we’ve decided to protect our gold with bricks.

Your examples (the same book, or an alphabet substitution) are like one layer of bricks. Once you figure out the substitution, or the book, you’re through, and you get the gold. And everyone has to go through the bricks, whether it’s your gold or not. Everyone has to crack the code to get in.

An advance in wall building might use multiple layers of bricks, for a stronger wall, so even if someone comes with a sledgehammer, backhoe, tank, or explosives, depending on how many layers of bricks you have you might still keep the gold. But you’d need an equal or greater way to get through yourself if you ever wanted to spend your gold, it’s not very efficient. Effective, but not efficient.

So adding a door in your wall may be considered an advance in gold protection, but now you have to consider that you’ve just made a weak spot that can be attacked and exploited.

A perfect system based on those rules would have a huge number of bricks, more than anyone would care to break down AND a magical backdoor so you could still check on your gold. You might also hope that if there was an advance in wall breaching, you could add more bricks as needed.

RSA does this by making it extremely easy to throw more and more bricks in your wall without making it appreciably harder to get through the back door. If someone ever does come along that has the new BrickBreaker 4000, you just make a few changes, and you can increase the number of bricks by a HUGE amount without really changing the effort of getting gold if you have the door.

So instead of bricks, it uses huge numbers, and instead of the back door, that’s your private key. The only magic of this particular method is the mathematical trick they use to that makes the wall thicker without making access any harder for your intended audience.

The primes, the factorization, the algorithm are all just components of that trick and what make the whole thing a preferred method.

^ Nice.

dappled_leaves (15834)

Used to be that you used one key to lock and unlock messages. You had to give the other person your key, but if someone stole the key your system would be compromised. With RSA you give out the public key to lock. Once locked the message can’t be unlocked without your private key. Your system cannot be compromised by carelessness on the sender’s part or by the courier of the public key. The private key never leaves your possession.

This is good for e-commerce because you don’t need customers or Internet providers to keep the key secure. In fact you can give out the same public key to everyone and still keep customers’ credit card info encrypted until you use your private key.

RocketGuy (9097)

@RocketGuy, that’s it—that’s getting really close to filling in what I’m not getting. I don’t care what kind of key (or lock) it is. What I’m after is the logic—the abstract idea that’s being implemented. You’re getting me there with “one key to lock, another key to open.” That’s a paradigm shift, a radical departure from “one key to lock and the same (or a duplicate) key to open.”

So—you said:
With RSA you give out the public key to lock.
Why? How well locked can something be if the key is public?

Once locked the message can’t be unlocked without your private key.
So how does the recipient open it?

In fact you can give out the same public key to everyone and still keep customers’ credit card info encrypted until you use your private key.
How exactly does the credit card number come into this picture?

Jeruba (45850)

Key here is a generic term. Maybe substitute code or password.

I’m not having a problem with the idea of a key.

Jeruba (45850)

The credit card number is part of what is encrypted.

It seems to me that what you want to know is how knowledge of the public key is not sufficient to decode the message. At the same time, you do not care to know the details of the algorithm. This makes things difficult. Let me give it one last shot. What I will try to show is that knowing the encoding process is not sufficient knowledge for being able to decode

By way of analogy, suppose that the encryption scheme was to convert the message to a number n and then transmit. n^2, The solution to this is of course to just take the square root. Taking the square root, however, is somewhat more difficult than squaring the number. Now instead of square root, suppose that the number n is raised to the power of the public key, e, where e is a number containing hundreds of digits. Now you are going to object by saying that this would be a horribly huge number. Which is true. I am hoping that you have some basic understanding of modular arithmetic. Along with the public key, there is associated some number m, which is also public. To find the number that is transmitted, take n^e, divide by m, and use the remainder. To be able to go backwards to solve for n is considerably more difficult than finding a square root, so difficult that it would take forever for a computer to solve the equation. What makes it possible to find the decryption key d associated with the encryption key e, is the fact that m=pq, where p and q are prime numbers. While it is easy to multiply two prime numbers, the reverse process of going from e to finding the two prime factors is an impossibly difficult operation, given that m, like e, contains hundreds of digits.

The basic idea is that going in one direction, encryption, is easy, but being able to go in the other direction to solve the equation is considerably harder.

@Jeruba

With RSA you give out the public key to lock.
Why? How well locked can something be if the key is public?

Only one of the keys is public. Since it takes two keys to open the lock, and the other key is virtually unfindable by an outsider, the lock is still secure. It does not become “half secure” because one key is public.

Once locked the message can’t be unlocked without your private key.
So how does the recipient open it?

The recipient is the one who has the private key. The sender uses the public key for encryption. The recipient uses the private key for decryption.

In fact you can give out the same public key to everyone and still keep customers’ credit card info encrypted until you use your private key.
How exactly does the credit card number come into this picture?

The credit card number is the message to be encrypted/decrypted.

dappled_leaves (15834)

The public key + the encryption program drives the encryption. e.g. if the encryption program shifts the alphabet x letters to the right, the public key of +2 will make a -> c, b -> d. Your text would become encrypted.

The private key + the encryption program drives the un-encryption e.g. if you put in a private key of -2, then c -> a, and d -> b. Your encrypted text would go back to normal.

In RSA, the public key drives some equation that cannot be reversed with the public key, and data becomes encrypted. When you put the private key into the same equation, the encrypted data is “re-encrypted” but looks exactly like the original text.

RocketGuy (9097)

Ah! Ok, @RocketGuy! I think I get it now. The little light in my brain just went on.

I appreciate all your help, @funkdaddy, @dappled_leaves, @LostInParadise—it’s not your fault that you encountered a stubborn thick spot in my cerebral cortex. You did contribute to my understanding.

You ought to hear my husband and me go around on stuff like this, as he gets increasingly exasperated with my persistent questions and I get more and more frustrated that he isn’t telling me what I’m missing. How can I explain what I don’t know?

So—to fill in the blanks in the little template I suggested above, I might say this. Check me now.

——

So then— here’s where I am. RSA keys come into the picture by altering the basic logic of encryption and decryption keys to create encryption that is practically impossible to compromise. Right? And the logic of their approach is ____.
•    to keep the private key in the hands of the recipient. No one else has it. But there’s a relationship between the public and private keys such that what’s locked with one can be unlocked by the other. And that relationship is the reason why you need both.

And what this means in practice is ____.
•    that senders of information can transmit data securely because no one can open it until it gets to the intended recipient.

As an analogy, this would be like ____.
•    handing out duplicate padlocks to anyone who wants to send you a box with a message in it; but you have the only key. (I found this in a book, and I didn’t really get it, but now I think I do.)

For example, ____. (?)
•    if I want to order securely from Amazon, when I transmit my data I am automatically(?) invoking Amazon’s locking device. But only Amazon can unlock what I send because no one else has their key.

——

Do I have it?

Jeruba (45850)

Given that the processing is digital, a combination lock might be a better analogy. You could eventually open the lock by trying all combinations, but the time required would be prohibitive. That is what it would be like trying to figure out the decryption key from the encryption key.

@Jeruba – you are exactly correct: it is like you are giving out the same padlocks to everyone. They can use it to lock their data, but they cannot grab another (identical) padlock to open someone else’s padlock.

The old paradigm was that you gave out lockboxes and a key. The one key could both lock and unlock. The lockbox was secure in transit, but the key could be stolen at some point. Then all lockboxes would be at risk..

RocketGuy (9097)

Thank you, thank you, thank you! Blissful clarity at last.

For the moment, anyway.

Again, I’m grateful for all efforts to help me disperse the fog.

Jeruba (45850)

or