Does reverse Public/Private key encryption exist? | Tech Off

Disclaimer: I'm not a crypto expert Smiley

Public key encryption works like this... You give everyone a copy of your public key, they encrypt some junk and only you, with the private key can decrypt it... Simple... Effective...

But does the reverse exist? ... Can you effectively give everyone a copy of the private key (to decrypt stuff) but only allow you to encrypt it, thus assuring them of whom the sender is?

I am talking about using it as sender authentication/identification, not as a method of encryption (the encryption is a means to that end).

Sven Groot

Yeah, this exists, just not as encryption.

You can sign something with a private key. The holders of the public key can validate whether the signature is correct, but they cannot generate the signature from scratch. This verifies that the document comes from whoever holds the private key, and hasn't been tampered with.

Signed executables use precisely this principle. So does .Net strong name signing (although the latter doesn't use certificates but its own key pairs). Applications like PGP will also let you sign e-mail in this fashion (and I believe Outlook can sign your mail based on a personal certificate if you have one).

EDIT: To add a little bit of crypto theory: this principle is called a Zero Knowledge Proof. You have a secret (the private key) and manage to prove to the recipient that you have this private key (from which they can assert that you are who you say you are) without the recipient gaining any knowledge to what the secret actually is (so they can't impersonate you afterwards).

littleguru

Most of the public/private key encryption mechanism use math functions that are hard to invert. For example the product of two very very high prim numbers. It's easy (quite easy) to create big prim numbers and to make the product of them. But it is hard to convert it back to the two prim numbers.

That's the idea of most algorithms.

Basically you can get the keys by trying. But with very very large prim numbers it takes you quite a lot time to try everything.

Matthew van Eerde

The private key is what makes you "you". If you give everyone a copy of your private key, they can be "you." This is rarely a good idea.

The public key allows other people to verify signatures you have made with your private key. It also allows people to encrypt things "to you" so that only someone with your private key ("you") can decrypt them.

Consider two people: John and Sarah. John has a public and private key. Sarah has a public and private key.

John and Sarah swap public keys. So John's keyring looks like this:

JOHN'S KEYRING:
John's public key
Sarah's public key
--
John's private key

And Sarah's keyring looks like this:

SARAH'S KEYRING:
John's public key
Sarah's public key
--
Sarah's private key

Suppose John wants to post a message publically, so that anyone can read it - but he wants to sign it, so that everyone with a copy of his public key can verify that it really was John that wrote the message.

He can use his private key to generate a signature and attach it to the message. Then Sarah can use her copy of John's public key to verify the signature.

Suppose John wants to send a secret message to Sarah that only she can read. He can encrypt the message to her public key, using his copy of her public key. Sarah can use her copy of her private key to decrypt it. (If Sarah wasn't careful with her private key, and someone else got a hold of it, they can decrypt it too.)

Note that the encrypted message is not necessarily signed. Sarah can read the message... which could have a "-- John" at the end of it... but she can not be cryptographically certain that John really sent it.

This can be solved if John first signs the message using his private key, then encrypts the resulting signed message to Sarah's public key.

Sarah would then be able to decrypt the encrypted message with her private key (only Sarah can read it) and she would have a readable message with a verifiable signature. She could use her copy of John's public key to verify the signature.

John could do it the other way around, too... he could encrypt first, and then sign.

Manip

Sven Groot wrote:

Yeah, this exists, just not as encryption.

You can sign something with a private key. The holders of the public key can validate whether the signature is correct, but they cannot generate the signature from scratch. This verifies that the document comes from whoever holds the private key, and hasn't been tampered with.

EDIT: To add a little bit of crypto theory: this principle is called a Zero Knowledge Proof. You have a secret (the private key) and manage to prove to the recipient that you have this private key (from which they can assert that you are who you say you are) without the recipient gaining any knowledge to what the secret actually is (so they can't impersonate you afterwards).

Thanks that kind of helpful.

Can you name more specifically which mathematical algorithms are used to generate a reverse private/public key pare (or signature)?

Matthew van Eerde wrote:

The private key is what makes you "you". If you give everyone a copy of your private key, they can be "you." This is rarely a good idea.

The public key allows other people to verify signatures you have made with your private key. It also allows people to encrypt things "to you" so that only someone with your private key ("you") can decrypt them.

Perhaps you could have saved yourself a lot of time if you had taken thirty seconds to read my post... If you had you would know that I know how public/private cryptography works, and that I am not looking for traditional public-private cryptography... I am looking for something else.

Programous

The answer to your question is yes. Anything encrypted with the private key can be decrypted by the public key, and anything encrypted by the public key can be decrypted by the private key. That is the mechanism that provides the authorization of servers via SSL.

staceyw

Manip wrote:

Sven Groot wrote: Yeah, this exists, just not as encryption.

You can sign something with a private key. The holders of the public key can validate whether the signature is correct, but they cannot generate the signature from scratch. This verifies that the document comes from whoever holds the private key, and hasn't been tampered with.

EDIT: To add a little bit of crypto theory: this principle is called a Zero Knowledge Proof. You have a secret (the private key) and manage to prove to the recipient that you have this private key (from which they can assert that you are who you say you are) without the recipient gaining any knowledge to what the secret actually is (so they can't impersonate you afterwards).

Thanks that kind of helpful.

Can you name more specifically which mathematical algorithms are used to generate a reverse private/public key pare (or signature)?

Matthew van Eerde wrote:
The private key is what makes you "you". If you give everyone a copy of your private key, they can be "you." This is rarely a good idea.

The public key allows other people to verify signatures you have made with your private key. It also allows people to encrypt things "to you" so that only someone with your private key ("you") can decrypt them.

Perhaps you could have saved yourself a lot of time if you had taken thirty seconds to read my post... If you had you would know that I know how public/private cryptography works, and that I am not looking for traditional public-private cryptography... I am looking for something else.

First, I assume your wanting a .Net solution as you did not say. Second, you don't need to "reverse" it, you just use the .Net RSA stuff as is - but use it for your needs. Here is one way:

1) everyone gets your public key. This part can be a weak spot in the whole protocol - hence why SSL uses certs and does the cert walk. You can still do it without certs, but you need a secure way for people to know they got the "your" public key and not a third party. You can do this via out-of-band methods such as email, ssl web site, mail, etc. But lets assume they have "your" public key.

2) You can now use RSACryptoServiceProvider.SignData() to sign your data with your public key. This does not encrypt the data, it is just a digital signature that proves you own the private key.

3) The client side uses your public key and uses RSACryptoServiceProvider.VerifyData() to verify the data was signed by the private key and has not changed along the way. As only you own the private key, this proves you sent it.

If you also want to encypt data on your side, then you get "their" public key and encyrpt the data before sending and Sign it with your private key so they can again verify you sent it.

You can roll this yourself, but not recommended as these protocols already exist in various forms in the framework (i.e. ssl, negotiatedStream, WCF, WSE, etc.) It can be very difficult to get right and verify it is secure. Example of how "not" simple it can be is one I did here:
http://channel9.msdn.com/ShowPost.aspx?PostID=103242

staceyw

Programous wrote:

The answer to your question is yes. Anything encrypted with the private key can be decrypted by the public key, and anything encrypted by the public key can be decrypted by the private key. That is the mechanism that provides the authorization of servers via SSL.

Not quite. Two keys are used - one in each direction. .Net (and I think win32) does not allow encyption with the private key (outside of creating a signature) only decryption. And you can only encypt with the a public key. Third party solutions exist, but have no experience with them (i.e. secureblackbox, etc.)

littleguru

Manip wrote:

Can you name more specifically which mathematical algorithms are used to generate a reverse private/public key pare (or signature)?

This is an example of the thing i tried to explain in my first reply:
http://en.wikipedia.org/wiki/RSA

It is quite easy to write your own RSA encryption/decryption classes. Smiley

If you do so and try to sell it, make sure you don't violate the law... Encryption/Decryption technologies have the same state as weapons in a lot countries.

Matthew van Eerde

Manip wrote:

Perhaps you could have saved yourself a lot of time if you had taken thirty seconds to read my post...

Ouch.

Manip wrote:
If you had you would know that I know how public/private cryptography works, and that I am not looking for traditional public-private cryptography... I am looking for something else.

Well, I did read your post. Perhaps I didn't understand it the way you intended.

What I got out of your post was you were looking for a way to prove you wrote such-and-such text. That's known as "signing," and the existing public/private-key system supports that in the way I suggested.

As to the exact mechanism used, it's all about taking two large primes and multiplying them together.

Consider my office number: 4709. Also, consider my previous home address: 533.

Neither of these are prime, but they are both products of two primes (each.)

With some effort you could figure out the two primes that are multiplied to make each of these numbers. Or I could just tell you, which would be much faster.

If I picked much larger primes and multiplied them together, it would take you much, much longer to figure out the two primes I used. If I picked REALLY large primes it would take you practically forever, even with a very powerful computer. (Although if you're a major government or a zombiemaster, you have a better chance than most: see the RSA Factoring Challenge page on Wikipedia)

The product-of-primes is my public key. The pair-of-primes is my private key.

For more, see the Wikipedia article on RSA

Note this sentence: "It was the first algorithm known to be suitable for signing¹ as well as encryption"

¹Which is what you want

Shark_M

Matthew van Eerde wrote:

Manip wrote:Perhaps you could have saved yourself a lot of time if you had taken thirty seconds to read my post...

Ouch.

Manip wrote:If you had you would know that I know how public/private cryptography works, and that I am not looking for traditional public-private cryptography... I am looking for something else.

Well, I did read your post. Perhaps I didn't understand it the way you intended.

What I got out of your post was you were looking for a way to prove you wrote such-and-such text. That's known as "signing," and the existing public/private-key system supports that in the way I suggested.

As to the exact mechanism used, it's all about taking two large primes and multiplying them together.

Consider my office number: 4709. Also, consider my previous home address: 533.

Neither of these are prime, but they are both products of two primes (each.)

With some effort you could figure out the two primes that are multiplied to make each of these numbers. Or I could just tell you, which would be much faster.

If I picked much larger primes and multiplied them together, it would take you much, much longer to figure out the two primes I used. If I picked REALLY large primes it would take you practically forever, even with a very powerful computer. (Although if you're a major government or a zombiemaster, you have a better chance than most: see the RSA Factoring Challenge page on Wikipedia)

The product-of-primes is my public key. The pair-of-primes is my private key.

For more, see the Wikipedia article on RSA

Note this sentence: "It was the first algorithm known to be suitable for signing¹ as well as encryption"

¹Which is what you want

Thanks , This is really helpfull. At least I get a good review of the basic concepts.

My question though is, since your transfering keys over ISP network, would it not be possible for ISPs to read your public key? and perhaps access your pc somehow to get your private, since they are the "Medium" the transaction is occuring over? Most cases only the people you want to talk to would know of your Public Key , but ISPs like AT & T would also know it simply because they have your packet logs would that not be the case?

In such a case, how to protect your public key if you only want someone specifically to know about it?

Secondly, the Key pairs are mathematically related? So if I encrypt a message to you using one key you can, in theory , use the other key to decrypt the message and vice versa, is this true?

The signing part, is it simply a Hash of the message that the reciver compares to the hash digest of the message that the reciver recalculates? if the hashes match, then the message is unaltered.

Secrete Packet:
Mauritus Is a Good C9 member. MD5Hash as signiture. EndOfPacket.
then Encrypt it
}{AEF}ASEFkwarjweriopwi542-05lkslvkmslkvmalkmflakmlwkerklwjerlwk

something like that, so its unreadable.

Is it possible for any one who is sniffing encrypted data to decrypt it if they dont have the secret PRIVATE key?

Also, what if you have multi-layer of encryption does this help secure date more or is it useless to think that way because its not adding any real security to the data.

Like do this, Symetic encryption, RC crypto, Asymmetric SSL, + some other layer like one-time pads . Would this make things UNBreakable for the next 200 million years?

Finally what is the most secure encryption protocol in existance today aside from SSL? is it one-time pads?