camisade
asked on
Public Key Encryption Question
I'm looking for confirmation of the following understanding of public key encryption and signing:
Given another party's public key, and your own public/private key pair, and a plain text message: Is it possible or impossible (or computationally infeasible), to generate the cipher text message/string that would decrypt into the intended plain text message?
That's confusing, I know. So here's a simplistic, concrete example:
Given Party A and Party B, each with a key pair and each other's public keys.
Suppose a plain text message of: 1234567890
And suppose that if Party A encrypted this message using his key pair and Party B's public key, he ended up with cipher text of "4tqgh9wetffeqwiu".
Could Party B, starting with the plain text of 1234567890, and using his own key pair and party A's public key, predict (or generate) the ciphered message that Party A would send (4tqgh9wetffeqwiu), which, when decrypted, would result in that unciphered message of 1234567890?
Intuition tells me no, that this would invalidate the security provided by signing a message, since someone could spoof a ciphered message and say it came from you. But I'm not clear on the difference between a ciphered message and the accompanying signature, so would like confirmation of the above.
Thanks!
Given another party's public key, and your own public/private key pair, and a plain text message: Is it possible or impossible (or computationally infeasible), to generate the cipher text message/string that would decrypt into the intended plain text message?
That's confusing, I know. So here's a simplistic, concrete example:
Given Party A and Party B, each with a key pair and each other's public keys.
Suppose a plain text message of: 1234567890
And suppose that if Party A encrypted this message using his key pair and Party B's public key, he ended up with cipher text of "4tqgh9wetffeqwiu".
Could Party B, starting with the plain text of 1234567890, and using his own key pair and party A's public key, predict (or generate) the ciphered message that Party A would send (4tqgh9wetffeqwiu), which, when decrypted, would result in that unciphered message of 1234567890?
Intuition tells me no, that this would invalidate the security provided by signing a message, since someone could spoof a ciphered message and say it came from you. But I'm not clear on the difference between a ciphered message and the accompanying signature, so would like confirmation of the above.
Thanks!
ASKER
Thank you. I do already have a fair grasp of public key encryption, and thank you for the explanation of how signing can be verified by the receiver using the sender's public key. But your response does not actually seem to answer the specific question that I'm asking, which is:
Could Party B, starting with the plain text of 1234567890, and using his own key pair and party A's public key, predict (or generate) the ciphered message that Party A would send (4tqgh9wetffeqwiu), which, when decrypted by Party B, would result in that unciphered message of 1234567890?
An analogy would be: If given the answer could I "back into" the question, where the "question" in this case is knowing what the actual ciphered text would need to be for me to then decrypt it to the "known" answer.
Thanks!
Could Party B, starting with the plain text of 1234567890, and using his own key pair and party A's public key, predict (or generate) the ciphered message that Party A would send (4tqgh9wetffeqwiu), which, when decrypted by Party B, would result in that unciphered message of 1234567890?
An analogy would be: If given the answer could I "back into" the question, where the "question" in this case is knowing what the actual ciphered text would need to be for me to then decrypt it to the "known" answer.
Thanks!
No, "chossen plain-text" is not a very viable "attack" against most public cryptography, but signing has this draw back is most cases. PKI is a very robust system, simple and secure if it's fully implimented: http://en.wikipedia.org/wiki/Chosen_plaintext_attack
It's the Private key that decrypts, and the Public key that encrypts...
Confidentiality Using Asymmetric Key Pairs (Encryption)
* Trading Partner A desires to send a confidential message to Trading Partner B
* Trading Partner A retrieves Trading Partner B's public key and encrypts the message with it
Confidentiality Using Asymmetric Key Pairs (Decryption)
* Trading Partner B receives the message and decrypts the message with the secretly held, private key
* The only key that can possibly decrypt a message that is encrypted with Trading Partner B's public key is Trading Partner B's private key
Digital Signatures Using Asymmetric Key Pairs (Encryption)
* Trading Partner A desires to send a digitally signed message to Trading Partner B
* Trading Partner A uses their own private key to encrypt a part of the message
* Trading Partner A sends the encrypted part of the message to B
Digital Signatures Using Asymmetric Key Pairs (Decryption)
* Trading Partner B receives Trading Partner A's message and obtains A's public key
* Trading Partner B tries to decrypt the encrypted portion of Trading Partner A's message
* If it decrypts, Then Trading Partner B knows it has to be from A because the only thing A's public key will decrypt is something encrypted with A's private key and only A has access to that private key
http://www.cs.umbc.edu/~wyvern/ta/encryption.html http://en.wikipedia.org/wiki/Cryptography#Public-key_cryptography
-rich
It's the Private key that decrypts, and the Public key that encrypts...
Confidentiality Using Asymmetric Key Pairs (Encryption)
* Trading Partner A desires to send a confidential message to Trading Partner B
* Trading Partner A retrieves Trading Partner B's public key and encrypts the message with it
Confidentiality Using Asymmetric Key Pairs (Decryption)
* Trading Partner B receives the message and decrypts the message with the secretly held, private key
* The only key that can possibly decrypt a message that is encrypted with Trading Partner B's public key is Trading Partner B's private key
Digital Signatures Using Asymmetric Key Pairs (Encryption)
* Trading Partner A desires to send a digitally signed message to Trading Partner B
* Trading Partner A uses their own private key to encrypt a part of the message
* Trading Partner A sends the encrypted part of the message to B
Digital Signatures Using Asymmetric Key Pairs (Decryption)
* Trading Partner B receives Trading Partner A's message and obtains A's public key
* Trading Partner B tries to decrypt the encrypted portion of Trading Partner A's message
* If it decrypts, Then Trading Partner B knows it has to be from A because the only thing A's public key will decrypt is something encrypted with A's private key and only A has access to that private key
http://www.cs.umbc.edu/~wyvern/ta/encryption.html http://en.wikipedia.org/wiki/Cryptography#Public-key_cryptography
-rich
You need to know the other parties private key, which the public key is derived, you cannot determine the private key with much less than brute force... and that would take forever, as the private key is hash of a password, and the public key is derived from that hash...
I believe you question is more about "shared key/linked key" or key agreement...
http://en.wikipedia.org/wiki/Image:Public_key_shared_secret.svg
-rich
I believe you question is more about "shared key/linked key" or key agreement...
http://en.wikipedia.org/wiki/Image:Public_key_shared_secret.svg
-rich
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Okay, that answers my question.
To clarify (because this is really an unorthodox question and a rather unusual way to approach public key encryption):
What I understand (or what you maintain) is that if you and I are exchanging ciphered messages, so you have my public key, and if I challenge you to generate (predict, as it were) the cipher text I would send you which, when you decrypted it, would result in a decrypted message of "20142163812" you would be unable to do so, except by using brute force, which is computationally infeasible (with the understanding that the shorter the message body, the more possible a brute force approach would become).
That about sum it up? I'm looking for a reasonably high degree of confidence.
To clarify (because this is really an unorthodox question and a rather unusual way to approach public key encryption):
What I understand (or what you maintain) is that if you and I are exchanging ciphered messages, so you have my public key, and if I challenge you to generate (predict, as it were) the cipher text I would send you which, when you decrypted it, would result in a decrypted message of "20142163812" you would be unable to do so, except by using brute force, which is computationally infeasible (with the understanding that the shorter the message body, the more possible a brute force approach would become).
That about sum it up? I'm looking for a reasonably high degree of confidence.
I (in this case "A") want to send you a message, I use your pub key to encrypt it. You ("B") use your private key to decrypt it. You send me a reply, encrypting the reply with my pub key, I use my private key to decrypt it.
If "A" uses A's own Public key to send a message to "B", B cannot decrypt the message.
If "A" uses A's own Public key to encrypt a message, and tells "B" the plain-text of that message, B would need an enormous amount of brute force to figure out A's private key.
B can do this for himself, use A's public key, encrypt a message and B of course knows the plain-text already. If A's Private key were used to encrypt the message, and then told "B" the plain-text of that message, less BF would be needed, but would still take a lot of time. The private keys must remain private to remain secure. I think you summed it up.
-rich
If "A" uses A's own Public key to send a message to "B", B cannot decrypt the message.
If "A" uses A's own Public key to encrypt a message, and tells "B" the plain-text of that message, B would need an enormous amount of brute force to figure out A's private key.
B can do this for himself, use A's public key, encrypt a message and B of course knows the plain-text already. If A's Private key were used to encrypt the message, and then told "B" the plain-text of that message, less BF would be needed, but would still take a lot of time. The private keys must remain private to remain secure. I think you summed it up.
-rich
It works like this:
Party A encrypts using his/her private key, and then using Party B's public key. The fact that Party A uses his/her private key, means that only Party A's public key can decrypt the message. Party B's public key used by Party A, means that only Party B can read that message.
When party B receives the message, they use Party A's public key and then Party B's private key to read the message. The chances of cracking this algorithm by bruteforce are quite slim (unless you are a surveillance agency and its your job to do this), but as computing power progresses, it will become possible.
There are different algorithms. RSA is used mostly for this purpose.
A hashing algo is a one-way function that generates a checksum of a message/file. This checksum is wrapped with the message and sent to the recipient. If the sender encrypts the hash using his private key, then the message is said to have been digitally signed by the sender using his private key. This can be verified by the receiver using the public key of sender to get to the hash. After that, the receiver generates a hash of the message and compares both. If they match, the message was received unaltered. There are many hashing algorithms such as MD5, SHA1, SHA-256.
You can read more about cryptography in Bruce Schneier's excellent book "Applied Cryptography". There is also a presentation on this at http://www.mirrors.wiretapped.net/security/info/books/crypto-tutorial/