Question about cryptography and public/private keys

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

  1. Erich Kohl

    Erich Kohl Guest

    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
    1. Advertisements

  2. Erich Kohl

    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
    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
    1. Advertisements

  3. 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
    works is because only you have access to your private key, so only you
    can "encrypt" with the private key.

    Matthew Fanto, Nov 2, 2006
  4. Erich Kohl

    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 Kohl

    Erich Kohl Guest

    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. 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

    Matthew Fanto, Nov 3, 2006
  7. Erich Kohl

    Erich Kohl Guest

    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

    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
    Erich Kohl, Nov 3, 2006
  8. 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.

, Nov 11, 2006
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.