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
"Sahil Malik [MVP]" <co*****************@nospam.com> wrote in message

news:%2****************@tk2msftngp13.phx.gbl...

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/