Public key cryptography

S

sram

[H]ard|Gawd
Joined
Jul 30, 2007
Messages
1,699
This might not belong here but it is the most relevant place I think.

I have been discussing VPN's and how can they be utilized for secure data exchange over the internet. VPN's can support 256-bit AES encryption as most of you veterans know.

http://hardforum.com/showthread.php?t=1748457

I kept on reading about cryptography and discovered the public key cryptography(asymmetric) that is more secure compared to symmetric cryptography.

In symmetric cryptography, both sides come up with a key to encrypt/decrypt data and they both should have it, so they should agree on it in advanced without anybody knowing. In public key cryptography, you have two keys, one public and one private which must be kept private and be unknown to others. You encrypt data using the public key and the other side will decrypt using it the corresponding private key.

This is where my question come from. How can a key be able to decrypt data that were encrypted by a different key?? My reading tells me that the both keys are mathematically linked or related, and it is done in a way that it is nearly impossible to generate the private key from its corresponding public key.

Okay that's fine, but how does it really happen? I mean eventually the same exact key that encrypted data should decrypt it................isn't that right? Maybe when applying the private key and during the decryption process, the private key is converted to the public key using the mathematical relationship ?

I couldn't figure it out by further reading on the subject, hence this thread.

I appreciate all input and comments. Thaaaaaaaaaaaaaaaaaaanks.
 
I'll take a closer look at my textbooks when I get into work and get back to you. It's been a while since basic crypto for me.

EDIT: RSA is probably one of the better known public key crypto systems. It basically relies on how difficult it is to factor two very large primes: http://en.m.wikipedia.org/wiki/RSA_(algorithm)

Other more modern approaches include ElGamal http://en.m.wikipedia.org/wiki/ElGamal_encryption which relies on discrete logs over cyclic groups, and elliptic curve crypto http://en.m.wikipedia.org/wiki/Elliptic_curve_cryptography.
 
Last edited:
sram said:
This is where my question come from. How can a key be able to decrypt data that were encrypted by a different key?? My reading tells me that the both keys are mathematically linked or related, and it is done in a way that it is nearly impossible to generate the private key from its corresponding public key.

Okay that's fine, but how does it really happen? I mean eventually the same exact key that encrypted data should decrypt it................isn't that right? Maybe when applying the private key and during the decryption process, the private key is converted to the public key using the mathematical relationship ?
Click to expand...

Bob and Alice

http://en.wikipedia.org/wiki/Public-key_cryptography
 
Blackjack988 said:
I'll take a closer look at my textbooks when I get into work and get back to you. It's been a while since basic crypto for me.

EDIT: RSA is probably one of the better known public key crypto systems. It basically relies on how difficult it is to factor two very large primes: http://en.m.wikipedia.org/wiki/RSA_(algorithm)

Other more modern approaches include ElGamal http://en.m.wikipedia.org/wiki/ElGamal_encryption which relies on discrete logs over cyclic groups, and elliptic curve crypto http://en.m.wikipedia.org/wiki/Elliptic_curve_cryptography.
Click to expand...

I'll read what you posted and see.
 
sram said:
I'll read what you posted and see.
Click to expand...

Those links are the mobile links as I grabbed them on the train ride in. Definitely start with RSA as it is (at least to me) the easiest to understand. If you're really interested, work through the algorithm on pen and paper with small (1-2 digit) primes and you'll get a great understanding as to how the process works.

Then you just have to realize that the security in any of these algorithms comes from the fact that the problems (mathematical techniques) being used to create the public and private keys are computationally very hard to solve as long as the values are sufficiently large.
 
sram said:
I read this whole wiki article before, but I still didn't get it. Again, how can a key decrypt data that has been encrypted with a totally different key?? Yes, they are related, but how does this relation factor in the decryption process?:confused:
Click to expand...

To really dive into the topic, you better start studying mathematics. Asking for armchair explanations in a forum is not going to help you.

For example, http://en.wikipedia.org/wiki/RSA_(algorithm) is way past high-school math - at least in any high-school I ever attended. For the crypto field however, it's merely a layman's introduction.

The problem with crypto is that it's very easy to be horribly wrong implementing it. So either you are a mere crypto user or a crypto guru. There's not much inbetween.

To _use_ public key crypto in a simple VPN implementation, you basically only need to know its properties, even if you don't know every detail of it. Just accept the fact that one key can decrypt what the other encrypted and that it's reasonably secure with the right key size.

Edit: Also, asymmetric crypto is not "more secure" than symmetric crypto. It merely has different properties. In fact, when you're using VPNs with asymmetric crypto, what you're really using is symmetric crypto with a key exchange done using asymmetric crypto. Asym crypto is way too slow to use on huge amounts of payload. It's mostly used to encrypt a random sym crypto session key.
 
Last edited:
sram said:
I kept on reading about cryptography and discovered the public key cryptography(asymmetric) that is more secure compared to symmetric cryptography.
Click to expand...

Asymmetric ciphers are not any more secure than symmetric ciphers, just by virtue of being such (obviously you can have flawed implementations of either).

Often asymmetric ciphers are used to bootstrap a session with a symmetric cipher because symmetric ciphers are faster. This happens almost anytime you connect to an HTTPS url. A key exchange (such as diffie-hellman) is done with asymmetric cipher (like RSA) for authentication. The key material that is generated and exchanged is used to key a symmetric cipher (like AES).
 
TCM said:
To really dive into the topic, you better start studying mathematics. Asking for armchair explanations in a forum is not going to help you.

For example, http://en.wikipedia.org/wiki/RSA_(algorithm) is way past high-school math - at least in any high-school I ever attended. For the crypto field however, it's merely a layman's introduction.

The problem with crypto is that it's very easy to be horribly wrong implementing it. So either you are a mere crypto user or a crypto guru. There's not much inbetween.

To _use_ public key crypto in a simple VPN implementation, you basically only need to know its properties, even if you don't know every detail of it. Just accept the fact that one key can decrypt what the other encrypted and that it's reasonably secure with the right key size.

Edit: Also, asymmetric crypto is not "more secure" than symmetric crypto. It merely has different properties. In fact, when you're using VPNs with asymmetric crypto, what you're really using is symmetric crypto with a key exchange done using asymmetric crypto. Asym crypto is way too slow to use on huge amounts of payload. It's mostly used to encrypt a random sym crypto session key.
Click to expand...

Thanks for your reply. I actually don't want to know how exactly to generate either key form the other. Just wanted to know how it could be possible to use a key to decrypted something that has been encrypted using a different key. From the looks of it, it seems like what I said in my OP is the answer: sometime during the decryption process the private key is converted to the public one so that it can really decrypt the data.
 
sram said:
sometime during the decryption process the private key is converted to the public one so that it can really decrypt the data.
Click to expand...

Uh, no. The whole point is that you can't generate one from the other easily.
 
TCM said:
Uh, no. The whole point is that you can't generate one from the other easily.
Click to expand...

This. You're not going to be able to understand it unless you understand the mathematical functions behind the key generation process.
 
If you don't want to get into the math behind how it works you're just going to have to accept that people much much better at math than you figured it out and it does in fact work well otherwise someone even better at math than the first guy would have come along by now and cracked it wide open.
 
TCM and others, thanks again for your input. Actually, when it comes to math, I consider myself competent. I always scored full marks during high school and also during college years. If I remember correctly, the pinnacle of what we studied is differentiation and integration and how they are used to solve real life problems. I'm good at math because I love it and enjoy it.

That was a little history about me. I don't know how much harder this crypto math is(I haven't read all things posted here yet), but if it isn't much harder than college math( My degree is Electrical Electronic Engineering if you wanna know more about what kind of math courses I took), I think I can do it and understand the technicalities behind it. If, on the other hand, it requires an IQ of 200 to understand, then I don't think I'm that person.

I'll have to read all you posted. I'll then give you my a more proper comment.

You know, I just hate to read something and not fully understand it, hence this thread.


Again, thanks:)
 
This is very very very simplistic, but hopefully shed some light on how one key can encrypt, while another can decrypt.


Say we have a number "n" that we want to encrypt using the key xyz. The function that does the encryption adds x + y + z to "n" to get and encrypted number "m". The function that does the decryption adds p + q + r to "m" to get back to the original "n". For this to work (in this simple example) the two formulas are related in that (x + y + z) = -(p + q + r).


For example. My public key (xyz) is 6, (-15), 5, and the number I want to encrypt is 9.

m = 9 + 6 -15 + 5 = 5

To get back to the original value, I could choose the key (pqr) to be 8, 14, (-18)

n = 5 + 8 + 14 - 18 = 9

Now, there is no way in hell that this example could even remotely be considered secure (all you have to do is add the elements of the encryption key together and subtract that to get the original values). But hopefully I got the idea across that two different but related keys can independently encrypt and decrypt data..
 
That's way too simplistic because the math PKE uses is asymmetric, meaning it's impossible to use the same key to decrypt as you used to decrypt.

I think the thing a lot of people "don't get" about PKE encryption is the use of modulus. Basically a large percentage of the number generated by these huge exponents get straight up thrown away, and you only send the least few least significant digits on. It just so happens that due to math if you raise those LSDs to the power of the other key, and look at the LSDs of that resulting number, they're the same as the original number (basically).
 
-Dragon- said:
That's way too simplistic because the math PKE uses is asymmetric, meaning it's impossible to use the same key to decrypt as you used to decrypt.

I think the thing a lot of people "don't get" about PKE encryption is the use of modulus. Basically a large percentage of the number generated by these huge exponents get straight up thrown away, and you only send the least few least significant digits on. It just so happens that due to math if you raise those LSDs to the power of the other key, and look at the LSDs of that resulting number, they're the same as the original number.
Click to expand...


I know, and I stated as much at the beginning. My point to the example was to show that it is possible to use one set of values to encrypt and another to decrypt without having to convert one set into another.
 
I think the OP had an implied question of not only how could one key be used to decrypt something encrypted by something else but also how could the original key be able to not decrypt the original message, so while yes your example showed a way key 2 could decrypt key 1 it didn't show why key 1 couldn't decrypt key 1
 
ryan_975 said:
This is very very very simplistic, but hopefully shed some light on how one key can encrypt, while another can decrypt.


Say we have a number "n" that we want to encrypt using the key xyz. The function that does the encryption adds x + y + z to "n" to get and encrypted number "m". The function that does the decryption adds p + q + r to "m" to get back to the original "n". For this to work (in this simple example) the two formulas are related in that (x + y + z) = -(p + q + r).


For example. My public key (xyz) is 6, (-15), 5, and the number I want to encrypt is 9.

m = 9 + 6 -15 + 5 = 5

To get back to the original value, I could choose the key (pqr) to be 8, 14, (-18)

n = 5 + 8 + 14 - 18 = 9

Now, there is no way in hell that this example could even remotely be considered secure (all you have to do is add the elements of the encryption key together and subtract that to get the original values). But hopefully I got the idea across that two different but related keys can independently encrypt and decrypt data..
Click to expand...

-Dragon- said:
That's way too simplistic because the math PKE uses is asymmetric, meaning it's impossible to use the same key to decrypt as you used to decrypt.

I think the thing a lot of people "don't get" about PKE encryption is the use of modulus. Basically a large percentage of the number generated by these huge exponents get straight up thrown away, and you only send the least few least significant digits on. It just so happens that due to math if you raise those LSDs to the power of the other key, and look at the LSDs of that resulting number, they're the same as the original number (basically).
Click to expand...

ryan_975 said:
I know, and I stated as much at the beginning. My point to the example was to show that it is possible to use one set of values to encrypt and another to decrypt without having to convert one set into another.
Click to expand...

WOW. You guys are amazing. I kinda of know what going on now even though I still didn't read most of the stuff here. I just got home from outside and decided to check on the thread.

The simple example helped me, and Dragon's post expanded so that I don't get the wrong idea...............

Keep it up, although I think it will be all clear after I read the first link. Thanks again.
 
-Dragon- said:
I think the OP had an implied question of not only how could one key be used to decrypt something encrypted by something else but also how could the original key be able to not decrypt the original message, so while yes your example showed a way key 2 could decrypt key 1 it didn't show why key 1 couldn't decrypt key 1
Click to expand...

Well, if you try to decrypt using key 1, then you get m' = m + x + y + z which would not give you the original number (in the example you'd get m' = 5 + 6 - 15 + 5 = 1 ). Given the flaw that x + y + z = - (p + q + r), the example would be trivial to reverse the encryption by knowing only one key, so you're right, it's not asymmetrical, and there's a lot more math needed to make it so. but sometimes the mind just needs a concept shown in the simplest of terms to be able to wrap around a complicated subject.
 
Last edited:
You must log in or register to reply here.
Back
Top