[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