[Cryptography] The original "public" public key algorithm

Jonathan Katz jkatz at cs.umd.edu
Sun Aug 3 17:43:53 EDT 2014


On Sunday, August 3, 2014, Bill Cox <waywardgeek at gmail.com> wrote:

> Does anyone on this list know anything about this story?  I heard it while
> I was a student at Berkeley in about 1983.  It was a story making it's way
> around the CS department.  Does anyone know the original source for this
> story?
>
> The cool part is how this algorithm is so simple and easy to explain to
> just about anyone:
>
> A CS professor at Berkeley taught one of the first crypto courses.  In a
> yes/no homework problem, he asked, "Alice wants to have a private
> conversation with Bob, and keep Eve out of it, but Eve is listening to
> everything Alice and Bob send to each other.  Without any shared secrets
> between Alice and Bob, but not Eve, is it possible for Alice to exclude
> Eve?"
>
> The "correct" answer was "no".  One kid thought really hard about it.
> This is the solution that he supposedly gave, and it's the best proof for
> believing public-key crypto isn't total BS ever:
>
> Alice chooses 1,000,000 random strong passwords of 256 bits each.  Then
> she encrypts each of them with random 32-bit passwords.  She uses the
> strong passwords to encrypt the following message 1,000,000 times: "You
> guessed the right password!  Now send me a message starting with 'I love
> you more than anything', encrypted with it!"  Alice sends all 1,000,000
> weakly encrypted passwords along with their strongly encrypted verification
> messages to Bob, tells him how to know when he has guessed the correct weak
> password, and to follow the decrypted instructions.
>
> Bob then picks one of the 1,000,000 weakly encrypted strong passwords at
> random, and on average in 2^31 (2 billion) guesses, he has brute-force
> decrypted it.  He then sends Alice the message "I love you more than
> anything, except when Eve is in town, in which case I love her more"
> encrypted with the strong password.  Alice tries all 1,000,000 strong
> passwords and decrypts it in no time.  Then she starts her secret
> conversation with Bob while Eve is stuck decrypting the 1,000,000 passwords
> until she finds the one that decrypts Bob's message.  On average, that's
> 500,000 passwords she will have to crack brute force, giving Bob and Eve a
> security work factor of 500,000, or about 2^19.  If it takes both Bob and
> Eve 1 hour to crack one password, Bob has on average 500,000 hours to act
> on whatever  secret plans he forms with Alice before Eve finds out.
>
> The funny part of this story is that supposedly the professor simply
> marked the student's answer wrong.  Does anyone know the origin of this
> story from 1983?
>
> Bill
>

This sounds similar to (though worse than) "Merkle puzzles," which date
back to the '70s:
   http://en.m.wikipedia.org/wiki/Merkle's_Puzzles
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140803/4188deac/attachment.html>


More information about the cryptography mailing list