Public Private Key Pairs - How do they work?
-----------------------------------------------

I was looking at a presentation recently in which it was suggested that -

User 1 Encrypts a message using User 2's Public Key.
User 2 Decrypts the transmission using his Private Key to get the orignal
message.

Is the above correct?
Comment #1: The above seems to suggest that Public keys allow me to encrypt,
and private keys allow me to decrypt, but vice versa is not possible (or the
above wouldn't be secure)

If it is, then a subsequent slide shows the following for digital signatures

User1 creates a hash digest.
User1 uses his private key to encrypt the digest to create a digital
signature
The digital signature + the original message go to user 2
User2 segregates the digital signature and message.
User 2 creates hash of the message
User2 decrypts the encrypted hash using User1's public key, if this equals
the hash calculated in the previous step - then the message has been not
tampered with.

Is the above correct?
Comment #2: This seems to suggest that Public keys allow me to decrypt, but
vice versa is not possible (or the signature would not work).

... QUESTION ...
How can both Comment #1 and Comment #2 hold true? What am I missing?

Please help. Thanks !!

- Sahil Malik [MVP]
http://codebetter.com/blogs/sahil.malik/

You're right I think. With secure non-repudiatable communications the
sequence goes:

clear-text message
User 1 decrypts message with User 1's private key.
User 1 encrypts message with User 2's public key.
Message is sent.
User 2 decrypts message with User 2's private key.
User 2 encrypts message with User 1's public key.

So I think that in Comment 2, it should be that User 1 uses their private
key to decrypt the message, not encrypt it. Similarly User 2 encrypts the
message with User 1's public key, resulting in cleartext.

Show quoteHide quote

Hi Sean.

Sean Hederman wrote:
Why should user 1 decrypt a clear-text message? There is nothing to decrypt
as it's clear text already. The user  _en_crypts the message (or creates a
hash and encrypts that hash) with his private key. This is to make sure
everyone can ensure the message originates from user 1.

This is to make sure nobody except user 2 can decrypt and read the message.

Only User 2 can do so because he is the only one to know his private key.

Why sholud user 2 encrypt the message again ? He wants clear text to read.
So he will decrypt it (or the hash value) with user 1's public key to ensure
it was sent by user 1.

Encryption will not result in clear text but in an encrypted message ;-)
We might be arguing about what we must call encryption or decryption, but
usually, if the result is clear text, I would call it decryption. If the
result is encrypted text, I would call it encryption.

[...rest snipped...]

Just my two cent
Michael

news:42847131$1@news...
Show quoteHide quoteWe're talking about the direction of the encryption here. Since an
assymetric cipher allows a third party to encrypt but not decrypt, by
"decrypting" the message we are in fact turning it into ciphertext, but
ciphertext that can be turned into cleartext by encrypting with the public
key, which as you say allows one to ensure that the message originates from
user 1.

[Snip]
In a sense you're right, but what I'm trying to get across here is the
direction of the "encryption". With public key encryption there are two
directions, one direction being possible with the public key and one
direction with the private key. The point is that if you run a decryption on
cleartext, you get ciphertext that can only be turned to cleartext by
encryption.

Show quoteHide quote

Sahil Malik wrote:

Show quoteHide quoteYou own a key pair: a public key and a corresponding private key.
Public keys are available to public (hence "Public" key, published on the
internet or similar). The corresponding private key is not published; you
keep it in a secure location. You can encrypt something with each key; it
can be decrypted with the other key of the key pair only.

So if someone encrypts something with your public key this ensures it can be
decrypted with your private key only. Since the only person knowing your
private key is you, the only person to decrypt whatever was encrypted is
you. This ensures that no one else is able to read messages encrypted with
your public key. So the above is correct.

Show quoteHide quoteWhy shouldn't it be possible to encrypt with your public key and decrypt
with your private key ?

As stated above, something encrypted with any key of a public/private key
pair can be decrypted with the other key of the pair only.
You create a hash value for your message and encrypt it with your public
key. This hash can be decrypted by everyone with your public key only. If
the (decrypted) hash equals the (newly calculated) message hash, this
indicates, that
1.) the message has not been altered
2.) the key used for decryption is the other key of the key pair the hash
was encrypted with, so the message is confirmed to be encrypted by you.

Encrypting with a private key makes sure the message originates from you
since it (or a corresponding hash) can only be encrypted with "your"
(published) public key, this is a signature. The message can be read by
everyone.

Encrypting with a public key makes sure the message can only be read by the
owner of the corresponding private key. This makes it a secret message.

If you want to make sure only the intended receiver of a message can read
the message and the receiver can ensure that you are the origin of the
message, you would encrypt the message with the receivers public key (can be
decrypted by the intended receiver with his private key only) and you would
encrypt the messages hash value with your private key, making sure the
receiver can encrypt it with your public key and compare it with the newly
calculated hash, so he knows it was sent by you and has not been altered.

hth
Michael

Hi,
Both statements are correct. <nitpicking> (Well sort of since #2 assumes use
of particular signature scheme - signature with message recovery and could
be thought as description of either RSA or Rabin signature, but there are
other types of signatures that don't fit to #2). </nitpicking>

Since you've asked - here is a bit of theory about asymmetric encryption
schemes that I've tried to express simplest way I could :-):
All asymmetric encryption schemes are based on use of some primitive
function (permutation). Of course, there are infinitely many different
permutations, but only some special could be used for asymmetric encryption.
These are called one-way trapdoor permutation (ie. permutation that is one
way, unless you possess some extra information that allows you to invert
permutation).
Where do we going now? Well, you surely heard about cryptographic hashes
(ex. SHA1). One of the most requested properties of any cryptographic hash
functions is one-way-ness (ie. having hash value, you can't perform some
reverse calculation that reveals you source data).
Now, if we cut off all the gibberish crypto-terminology, we could think of
cryptographic hash as some keeper of some field with some
million-billion-trillions of pigeonholes each of these contains a Pandora
box with an unique ornament. The keeper's name is Oracle (like in Matrix)
and she knows everything... Whenever she receives a packet from Alice (ex.
picks it up from her mail box) she (Oracle) goes to the only pigeonhole
which is destined to keep that package, put the package inside Pandora box,
lock the box, destroys the key and mails picture of closed Pandora box back
to Alice.
At some time later - when she receive another package containing the same
message from Bob - she (Oracle) goes to the same pigeonhole where she
already put that message before, takes picture of closed Pandora box and
mail it back to Bob.
After that, whenever Alice and Bob meet in person, they can compare photos
of Pandora's Box they received from Oracle. If box's decorations on both
photos are identical - they know for sure that the message from Alice was
the same as the message from Bob. But if Oscar steals or makes a copy of the
picture of Pandora's box, he could never figure out what was the message
that is stored inside that box (even if Oscar decides to wander to Oracle's
million-billion-trillions of pigeonholes field, and find the box, the box is
still safely locked and the only key is destroyed).

If we describe asymmetric cryptography in that model it will be almost the
same. except for minor details:

- Asymmetric encryption case:
When Oracle picks package from Alice, she puts it into the only destined
pigeonhole's Pandora's box and locks package inside. but instead of
destroying the key - she securely transports it to the Bob together with
detailed map showing which pigeonhole contains the Box.
When Bob decides to check what Alice has mailed to him, he can wander to the
million-billion-trillions of pigeonholes field, use map to quickly locate
designated pigeonhole, uses the only key to open Pandora's Box and retrieve
Alice's message. If Oscar steals a picture of Pandora's Box that Oracle
sends back to Alice - he has no chance to figure out what Alice was trying
to say to Bob. And that is asymmetric encryption in action :-).

- Now to signature case:
Oracle picks package from Bob, and before going to the only destined Pandora's
Box she securely acquires the key from Bob to that very Pandora's box, and
in case if key matches the box, she lock the package inside and destroys the
key. After that she sends picture of Pandora's Box (but without the map)
back to Bob. But if the key was a fake that was somehow switched by Oscar,
then Oracle would not be able to open the box and so she stops all further
actions. When Alice wants to verify Bob's signature, she send the package
with the same message to Oracle, Oracle mails photo of Pandora's box back to
Alice and Alice can now compare here photo to photo that Bob received from
the Oracle. And that's signature in action.

But now you are probably asking about a public key. what the hell does it
mean in the pigeonhole theory of asymmetric cryptography?
Well, think that our Oracle was put to manage not one field filled with
million-billion-trillions of pigeonholes, but a million-billion-trillions of
fields filled with million-billion-trillions of pigeonholes. Even Oracle
would not manage to find correct hole if she isn't given some hint about
which pigeonholes field she supposes to use. And the public key is nothing
more than just a hint to one single field filled with
million-billion-trillions of pigeonholes. That's it - and that would be a
"pigeonholes theory of asymmetric cryptography" T :-).

In reality it happens a little bit different than on our mystique Oracle
wandering around million-billion-trillions fields of
million-billion-trillions of pigeonholes, but the principle is the same.
One-way trapdoor permutation is what we referred as the Oracle in our model.
One-way trapdoor permutations of most interest are based on two mathematical
problems:

1. Difficulty of factoring integers that was first described by J.S.Jevons
in 1873 (a century before RSA invention);
2. The difficulty of calculation of discrete logarithm in some Fields;

Both problems are shown to be NP-complete, but both shown to have some
sub-exponential solutions (i.e. short-cut solutions that is much easier than
simple brute-force), therefore you hear that people says that 1024 bit RSA
key provides about 80 bits of security (math problem #1).
When it concerns to math problem #2 - estimating security bits depends on
the Field that this discrete logarithm is applied to. If we talk about Z*n
(multiplicative field of natural numbers modulo prime number n) that is used
in classic DSA (DSS), ElGammal  ( and Cramer-Shoup and Zheng-Seberry and
many others), or GFp^n Galois Fields - it would be even worse than with
integer factoring. However when the same problem is used with elliptic
curves, it gives about a square root bits of security (i.e. 164 bit ECDSA
provides you with about 80 bits of security).

But that again just gibberish crypto-math-terminology that has nothing to do
with our pigeonhole theory of asymmetric encryption :-).

Hope that would clear some or your questions.

-Valery.
http://www.harper.no/valery

Show quoteHide quote

Thank you very much for your answers.

I am absolutely crystal clear about all this now.

- Sahil Malik [MVP]
http://codebetter.com/blogs/sahil.malik/



Show quoteHide quote

Distributed winforms application security
ASP.NET Uploading Security Issue?
system.security.securityexception
WindowsIdentity role caching in ASP.NET
Check for certian privileges
High-strength crypto problems
IsInRole groupname with white space.
Restricting Upload File Types
Impersonation code
Pls Help! Passing credential between two web sites on same machin