# Question about cryptography and public/private keys

Discussion in 'Computer Security' started by Erich Kohl, Nov 2, 2006.

1. ### Erich KohlGuest

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, Nov 2, 2006

2. ### Todd H.Guest

As a technical nit, they are not "inverse functions" as defined in
mathematics or cryptography, but lookin gbeyond that semantic issue...
Correct. In the parlance of cryptography, yes, the public key is used
to recover the plain text message from the ciphertext.
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.
Certificates, while also based on one-way functions, are sort of
unrelated to the issue of reversing keys.
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., Nov 2, 2006

3. ### Matthew FantoGuest

A good place is the sci.crypt forum, but this works too.
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.
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.

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.

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
can "encrypt" with the private key.

-Matt

Matthew Fanto, Nov 2, 2006
4. ### Todd H.Guest

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

Todd H., Nov 2, 2006
5. ### Erich KohlGuest

Makes sense.
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, Nov 2, 2006
6. ### Matthew FantoGuest

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.

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

Matthew Fanto, Nov 3, 2006
7. ### Erich KohlGuest

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?

Erich Kohl, Nov 3, 2006
8. ### SecurityBulletins.comGuest

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/

SecurityBulletins.com, Nov 11, 2006