Question about cryptography and public/private keys

Hello all,

If this isn't the correct forum, I apologize in advance. I wasn't
sure where else to post this.

I have a question about cryptography, public and private keys, and
digital certificates. I've been trying to understand the whole
concept, and I'm getting closer to that goal, but I am still perplexed
by one aspect of it.

My understanding is that public keys and private keys are inverse
functions of one another; that is, only a person's public key can
"undo" (decrypt) a message that was encrypted by their original
private key.

Okay, so the private key is kept secret. But the thing is, since the
keys are related to each other in the sense that they are
mathematically "inverse functions" of one another, can't somebody
figure out what a person's or institutions's private key is simply by
reverse engineering the public key? By figuring out what the inverse
of the public key is?

Is it just that it would take such an incredibly long time to do, that
it would be a pointless waste of effort? Or is it the purpose of a
digital certificate to prevent that from happening? Is there a
mathematical reason?

I appreciate any explanation that can be given.

Erich Kohl <ekohl@sbcglobal.net> writes:

> Hello all,
>
> If this isn't the correct forum, I apologize in advance. I wasn't
> sure where else to post this.
>
> I have a question about cryptography, public and private keys, and
> digital certificates. I've been trying to understand the whole
> concept, and I'm getting closer to that goal, but I am still perplexed
> by one aspect of it.
>
> My understanding is that public keys and private keys are inverse
> functions of one another;

As a technical nit, they are not "inverse functions" as defined in
mathematics or cryptography, but lookin gbeyond that semantic issue...

> that is, only a person's public key can
> "undo" (decrypt) a message that was encrypted by their original
> private key.

Correct. In the parlance of cryptography, yes, the public key is used
to recover the plain text message from the ciphertext.

> Okay, so the private key is kept secret. But the thing is, since the
> keys are related to each other in the sense that they are
> mathematically "inverse functions" of one another, can't somebody
> figure out what a person's or institutions's private key is simply by
> reverse engineering the public key? By figuring out what the inverse
> of the public key is?
> Is it just that it would take such an incredibly long time to do,
> that it would be a pointless waste of effort?

I think the concept left out of the model you have right now is the
notion of a one-way function -- a function easy to compute in one
direction but essentially infeasible to compute in the reverse
direction... unless there's a trap door in the algorithm or
implementation.

> Or is it the purpose of a digital certificate to prevent that from
> happening? Is there a mathematical reason?

Certificates, while also based on one-way functions, are sort of
unrelated to the issue of reversing keys.

> I appreciate any explanation that can be given.

I'm sure there are better explanations out there from someone formally
trained in cryptography but hopefully this gives some sort of start.

There is a sci.crypt group I think that specializes in this stuff that
might be worth lurking in for a while to see if they ahve a FAQ that
covers it or something.

Best Regards,
--
Todd H.
http://www.toddh.net/

Erich Kohl wrote:
> If this isn't the correct forum, I apologize in advance. I wasn't
> sure where else to post this.

A good place is the sci.crypt forum, but this works too.

> I have a question about cryptography, public and private keys, and
> digital certificates. I've been trying to understand the whole
> concept, and I'm getting closer to that goal, but I am still perplexed
> by one aspect of it.

No problem, the ideas of public key cryptography isn't the easiest
thing, and when you throw digital signing in, it becomes even harder to
understand. Once you learn a few basic points, then whole thing then
starts to make sense.

>
> My understanding is that public keys and private keys are inverse
> functions of one another; that is, only a person's public key can
> "undo" (decrypt) a message that was encrypted by their original
> private key.

As pointed out, they are inverse in that one undoes the other. But Todd
H. is incorrect in saying that the public key recovers the plaintext
from the ciphertext. It's actually the opposite. The plaintext is
encrypted with the public key, and the private key is used to recover
the plaintext from the ciphertext.

Think about it this way, if I encrypted a secret message with my
private key, and the public key was used to decrypt it, anyone would be
able to decrypt my message, since everyone has my public key.

This is actually a useful property though, and it's how we do digital
signatures. But you should distinguish between encryption and signing.
The operations are reverse of eachother.



> Okay, so the private key is kept secret. But the thing is, since the
> keys are related to each other in the sense that they are
> mathematically "inverse functions" of one another, can't somebody
> figure out what a person's or institutions's private key is simply by
> reverse engineering the public key? By figuring out what the inverse
> of the public key is?
> Is it just that it would take such an incredibly long time to do, that
> it would be a pointless waste of effort? Or is it the purpose of a
> digital certificate to prevent that from happening? Is there a
> mathematical reason?


Yes, there we is a well defined relationship between the two. In the
case of RSA, you take two really big prime numbers and multiply them
together. The primes are your private key (technically the primes are
used to find the private key, but it suffices in this discussion to say
they are the private key), and the product of those primes are your
public key.

So, generate two huge primes, p and q. Your public key is p*q. The
reason this is secure is because if I give you p*q (public), it's very
very very difficult to find what p and q is. You need p and q for the
private key. Thats why it can't be reversed. It is tied to the
difficulty of factoring.


> I appreciate any explanation that can be given.

Just to clarify a point, here is how encryption and signing works:

If you want to send me an encrypted message, you would use my public
key and encrypt the message. My private key decrypts it.

If you want to sign a message, you "encrypt" it with your private key.
The public key is used to "decrypt" this message. Anyone who has your
public key can "decrypt" it and verify the signature. The reason this
works is because only you have access to your private key, so only you
can "encrypt" with the private key.

-Matt

"Matthew Fanto" <mfanto@gmail.com> writes:

> As pointed out, they are inverse in that one undoes the other. But Todd
> H. is incorrect in saying that the public key recovers the plaintext
> from the ciphertext. It's actually the opposite. The plaintext is
> encrypted with the public key, and the private key is used to recover
> the plaintext from the ciphertext.

Doh--yer right. This is where signing and encrypting differ.
Matthew thanks for correcting that gaff.


--
Todd H.
http://www.toddh.net/

On 2 Nov 2006 07:32:48 -0800, "Matthew Fanto" <mfanto@gmail.com>
wrote:

>
>Erich Kohl wrote:
>>
>> My understanding is that public keys and private keys are inverse
>> functions of one another; that is, only a person's public key can
>> "undo" (decrypt) a message that was encrypted by their original
>> private key.
>
>As pointed out, they are inverse in that one undoes the other. But Todd
>H. is incorrect in saying that the public key recovers the plaintext
>from the ciphertext. It's actually the opposite. The plaintext is
>encrypted with the public key, and the private key is used to recover
>the plaintext from the ciphertext.
>
>Think about it this way, if I encrypted a secret message with my
>private key, and the public key was used to decrypt it, anyone would be
>able to decrypt my message, since everyone has my public key.
>

Makes sense.

>This is actually a useful property though, and it's how we do digital
>signatures. But you should distinguish between encryption and signing.
>The operations are reverse of eachother.
>
>> Okay, so the private key is kept secret. But the thing is, since the
>> keys are related to each other in the sense that they are
>> mathematically "inverse functions" of one another, can't somebody
>> figure out what a person's or institutions's private key is simply by
>> reverse engineering the public key? By figuring out what the inverse
>> of the public key is?
>> Is it just that it would take such an incredibly long time to do, that
>> it would be a pointless waste of effort? Or is it the purpose of a
>> digital certificate to prevent that from happening? Is there a
>> mathematical reason?
>
>
>Yes, there we is a well defined relationship between the two. In the
>case of RSA, you take two really big prime numbers and multiply them
>together. The primes are your private key (technically the primes are
>used to find the private key, but it suffices in this discussion to say
>they are the private key), and the product of those primes are your
>public key.
>
>So, generate two huge primes, p and q. Your public key is p*q. The
>reason this is secure is because if I give you p*q (public), it's very
>very very difficult to find what p and q is. You need p and q for the
>private key. Thats why it can't be reversed. It is tied to the
>difficulty of factoring.
>
>
>> I appreciate any explanation that can be given.
>
>Just to clarify a point, here is how encryption and signing works:
>
>If you want to send me an encrypted message, you would use my public
>key and encrypt the message. My private key decrypts it.
>
>If you want to sign a message, you "encrypt" it with your private key.
>The public key is used to "decrypt" this message. Anyone who has your
>public key can "decrypt" it and verify the signature. The reason this
>works is because only you have access to your private key, so only you
>can "encrypt" with the private key.
>
>-Matt

Ah, of course! And you *know* that the message came from a fraudulent
source if your private key couldn't unlock the ciphered data because
of its direct relationship to the *public* key. If the private key
doesn't work on it, the message wasn't encrypted with the proper
corresponding PUBLIC key. And ONLY YOU can decrypt messages meant for
YOU, because your private key is, well, private. ;-)

Am I understanding this correctly? I think I am.

But here's another question . . . who hands out these keys? Where are
they stored? Is it the job of things like VeriSign to do that?

Thanks to everyone for your help.

Erich Kohl wrote:
> Ah, of course! And you *know* that the message came from a fraudulent
> source if your private key couldn't unlock the ciphered data because
> of its direct relationship to the *public* key. If the private key
> doesn't work on it, the message wasn't encrypted with the proper
> corresponding PUBLIC key. And ONLY YOU can decrypt messages meant for
> YOU, because your private key is, well, private. ;-)
>
> Am I understanding this correctly? I think I am.


Yep, you got encryption down. Encrypting with the public key though
doesn't do anything to prove if the other person is fraudulent. Imagine
a big phone book of public keys. Anyone can look up your public key and
send you a message. That doesn't prove anything.

So here is where we use a digital signature. I actually use my private
key to "encrypt" the data. Remember that what one key does, the other
key undoes. That means that if it's encrypted with my private key, the
public key decrypts it. So if you signed a message with your private
key, I would then go look up your public key in the phone book. I would
apply that public key to the message. Since only you could have used
your private key, if the public key "works" then I know it must have
come from you*.

*there are technical details like hash functions, and more details to
signatures, but you get the idea.


> But here's another question . . . who hands out these keys? Where are
> they stored? Is it the job of things like VeriSign to do that?

It depends what you are going to use your keypair for. Verisign (or
Geotrust, or a number of others) will give out keys along with
certificates (they sign the certificate with your public key in it) if
you are using SSL. Or, you can generate your own certificates and
public/private keys for webservers (this has a few issues associated).
Or if you work for an enterprise, they might give you a keypair. You
can have tons of different keys. There is no universal authority for
giving them out, although Verisign would love to become that universal
authority.


-Matt

On 2 Nov 2006 16:16:49 -0800, "Matthew Fanto" <mfanto@gmail.com>
wrote:

>
>Erich Kohl wrote:
>> Ah, of course! And you *know* that the message came from a fraudulent
>> source if your private key couldn't unlock the ciphered data because
>> of its direct relationship to the *public* key. If the private key
>> doesn't work on it, the message wasn't encrypted with the proper
>> corresponding PUBLIC key. And ONLY YOU can decrypt messages meant for
>> YOU, because your private key is, well, private. ;-)
>>
>> Am I understanding this correctly? I think I am.
>
>Yep, you got encryption down. Encrypting with the public key though
>doesn't do anything to prove if the other person is fraudulent. Imagine
>a big phone book of public keys. Anyone can look up your public key and
>send you a message. That doesn't prove anything.
>
>So here is where we use a digital signature. I actually use my private
>key to "encrypt" the data. Remember that what one key does, the other
>key undoes. That means that if it's encrypted with my private key, the
>public key decrypts it. So if you signed a message with your private
>key, I would then go look up your public key in the phone book. I would
>apply that public key to the message. Since only you could have used
>your private key, if the public key "works" then I know it must have
>come from you*.
>
>*there are technical details like hash functions, and more details to
>signatures, but you get the idea.
>
>> But here's another question . . . who hands out these keys? Where are
>> they stored? Is it the job of things like VeriSign to do that?
>
>It depends what you are going to use your keypair for. Verisign (or
>Geotrust, or a number of others) will give out keys along with
>certificates (they sign the certificate with your public key in it) if
>you are using SSL. Or, you can generate your own certificates and
>public/private keys for webservers (this has a few issues associated).
>Or if you work for an enterprise, they might give you a keypair. You
>can have tons of different keys. There is no universal authority for
>giving them out, although Verisign would love to become that universal
>authority.
>
>-Matt

I noticed in my Internet browser's list of certificates, a certificate
is shown which represents my bank (I do a fair amount of online
banking).

I'm assuming this means that when I connect to my bank's website, the
transactions I do on it are encrypted. Are keys transferred back and
forth during a banking session like that? Which side sends which
keys?

That could be a few different certificates, depending on how it is
being used. It could be a client certificate that identifies you as a
legitimate user of the site. It could also be a key specific to that
bank that you have elected to trust without a Certificate Authority
vouching for the certificate. It could also be a Certificate Authority
(CA) certificate specifying you will trust any certificates the bank's
CA vouches for. Your browser will likely tell you the type of trust it
is assigning to the certificate.

Doug

http://SecurityBulletins.com/

Erich Kohl wrote:

> I noticed in my Internet browser's list of certificates, a certificate
> is shown which represents my bank (I do a fair amount of online
> banking).
>
> I'm assuming this means that when I connect to my bank's website, the
> transactions I do on it are encrypted. Are keys transferred back and
> forth during a banking session like that? Which side sends which
> keys?