Day 75:默克勒(merkle)的谜题
18年11月5日 · 史二美—北京理工大学 1802 人阅读
默克勒(merkle)的谜题
这有一个典型的场景,爱丽丝和鲍勃想要使用不安全的线路共享一个公共密钥。默克勒的谜题提出了以下方案。
(1)爱丽丝用N个指数生成N个秘密,并将每对[秘密,指数]插入一个可以在θ( N )时间内解决的谜题中
(2)爱丽丝把所有的谜题发给鲍勃
(3)鲍勃随机挑选一个谜题,通过解谜得到一对[秘密,索引]
(4)鲍勃把索引发回爱丽丝
(5)根据索引,他们现在都有一个共同的秘密
(6)对手知道爱丽丝所有的谜题和鲍勃的索引;为了找到这个秘密,她必须解决N个谜题来比较需要θ( N )时间的指数
显而易见,为什么这个协议没有在实践中使用。为了加强对手的 Θ(2⁶⁴) 时间,爱丽丝需要生成 Θ(2³²) 谜题。更糟糕的是,有证据表明二次边界是我们能得到的最好的边界。现代的公钥方案做得更好。
我已经为N = 2的[实现了协议是的,它是Python ]用以下方式构建的谜题。
秘密是一致生成的随机值,而索引只是唯一的整数。SHA 1摘要被附加到消息中,以帮助解开谜题。然后生成一个随机密钥,作为伪随机噪声产生器的种子.我们再次使用SHA 1,因为它是一个很好的PRG。消息和随机噪声是(OTP密码)共同完成的第一部分。第二部分是部分揭示的随机密钥。要解开谜题,我们就必须通过猜测被排除的键的前两个字节来恢复进程。消息中有意包含的摘要用作我们猜测的验证机制。这个过程需要单个拼图的Θ(2¹⁶) 步骤,所有的谜题,都需要Θ(2³²) 的步骤。
实现代码
爱丽丝
鲍勃
爱丽丝
对手
Python3Turtle