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

  2. Erich Kohl

    Todd H. Guest

    Erich Kohl <> 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/
     
    Todd H., Nov 2, 2006
    #2
    1. Advertising

  3. 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, Nov 2, 2006
    #3
  4. Erich Kohl

    Todd H. Guest

    "Matthew Fanto" <> 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/
     
    Todd H., Nov 2, 2006
    #4
  5. Erich Kohl

    Erich Kohl Guest

    On 2 Nov 2006 07:32:48 -0800, "Matthew Fanto" <>
    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, Nov 2, 2006
    #5
  6. 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
     
    Matthew Fanto, Nov 3, 2006
    #6
  7. Erich Kohl

    Erich Kohl Guest

    On 2 Nov 2006 16:16:49 -0800, "Matthew Fanto" <>
    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?
     
    Erich Kohl, Nov 3, 2006
    #7
  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.

    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?
     
    SecurityBulletins.com, Nov 11, 2006
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    1,403
  2. Rob Slade, doting grandpa of Ryan and Trevor

    REVIEW: "RSA and Public Key Cryptography", Richard A. Mollin

    Rob Slade, doting grandpa of Ryan and Trevor, Dec 18, 2003, in forum: Computer Security
    Replies:
    0
    Views:
    531
    Rob Slade, doting grandpa of Ryan and Trevor
    Dec 18, 2003
  3. loyola
    Replies:
    3
    Views:
    1,607
    Cerebrus
    Nov 14, 2006
  4. loyola
    Replies:
    4
    Views:
    1,452
  5. loyola
    Replies:
    3
    Views:
    1,809
    Cerebrus
    Nov 14, 2006
Loading...

Share This Page