Merkle的难题和他的树

http://hi.baidu.com/hopeyard/blog/item/f9afc71f93067ef6e0fe0b10.html

Merkle的难题和他的树
Ralph Merkle发明了第一个公开密钥密码的设计。1974年他在Berkeley的加利福尼亚大学注册了由Lance Hoffman教的计算机安全课程。在这个学期初，他的学期论文的题目是处理“不安全的信道上的安全通信”的问题[1064]。Hoffman不理解 Merkle的建议，最终Merkle放弃了这门课程。尽管连遭失败让人们难以理解其结果，但他仍孜孜不倦地在这个问题上工作着。
Merkle的技术基于：发送者和接收者解决难题(Puzzles)比窃听者更容易。下面谈谈Alice怎样不用首先和Bob交换密钥就能把加密消息发给Bob：
（1） Bob产生220或大约1百万个这种形式的消息：“这是难题数x，这是秘密密钥数y”，其中x是随机数，y是随机的秘密密钥。每个消息的x和y都是不相同的。采用对称算法，他用不同的20比特密钥对每个消息加密，并都发给Alice。
（2） Alice随机选择一个消息，通过穷举攻击恢复明文。这个工作量是很大的，但并不是不可能的。
（3） Alice用她恢复的密钥和有些对称算法加密秘密消息，并把它和x一起发给Bob。
（4） Bob知道他用哪个秘密密钥y对消息x加密的，这样他就能解密消息。

Eve能够破译这个系统，但是她必须做比Alice和Bob多得多的工作。为了恢复第（3）步的消息，她必须完成对Bob在第（1）步中的所有220消息 的穷举攻击。这个攻击的复杂性是240。X的值不会对Eve有什么帮助。他们在第（1）步中是随机指定的。一般情况下，Eve花费的努力大约是Alice 花费的努力的平方。
按照密码的标准，n到n2没有什么优势，但在某些情况下，这可能足够（复杂）了。如果Alice和Bob每秒可试1万个，这将要花他们每个人1分钟去完成 他们的步骤，再花另外1分钟在1.544Mb/s链路上完成从Alice到Bob的通信难题。如果Eve有同样的计算设备，破译这个系统将花费她大约1年 的时间，其它算法甚至更难破译。