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