[Cryptography] The original "public" public key algorithm

[Bill Cox]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140803/442dbf10/attachment.html>