密码学协议举例[3]–另类的密钥交换协议

  • A+
所属分类:密码学协议
摘要从生活中的例子来解读关于另类的密钥交换协议,讲一种古老的密钥交换协议,体验一下那时候人们的智慧。

另类的密钥交换协议

这是密码学协议的第三篇文章, 前面两篇的链接分别为:

 

想法与简单的想法

密钥是密码的命根,一切不安全的秘密交换都源于不安全的密钥交换。目前,绝大多数协议采取RSA算法进行密钥交换,但在RSA算法出现之前,人们又是怎么做的呢?

据说,第一个密钥交换算法是一个名叫Ralph Merkel的人在1974年发明的,算法叫做Merkle's Puzzles。这是一个非常奇特、非常邪恶的密钥交换协议。

假设A和B想进行秘密通信,他们需要选取一个密钥。A准备好很多很多个形如"密钥编号为X_i,密钥是Y_i"的消息,其中X_i是一个随机标识符,Y_i是一个随机密钥。消息的个数越多越好,起码要有几十万几百万条。

然后,A把这些消息都编码为一个个难题,比方说对第i条消息异或一个大质数P_i,并宣称P_i是某个数N_i最小的那个质因子。A把所有编码后的消息全部发给B。B收到这些消息之后,随便选择一条消息进行暴力破解(在上例中就是暴力分解某个N_i),得到某一对对应的x和y。B用明文给A发一个消息,说"我们就用编号为x的密钥吧"。

由于A知道这个x对应的是哪个y,因此A知道B说的密钥是哪个。

这个协议的核心就是,第三者不知道B当时选的是哪条消息。如果有第三者截获了他们之间的通信,要想获得密钥y,他必须一一破解所有的难题,直至解开了那个编号为x的密钥消息。由于这样的难题数量大得惊人,第三者要花费的努力是B的上百万倍。假如用计算机暴力破解一个难题需要一个小时的时间,那么第三者即使有百倍于B的计算能力,他也需要平均一年多才能解到正确的x和y。

 

举例说明

密码学协议举例[3]--另类的密钥交换协议
  • A告诉B:P100是613798637的最小质因子,其中613798637 = 79 * 97 * 173 * 463
  • B收到后,随机抽一个,假设就是抽中了这个,计算得到P100=79,再通过计算得到x100和y100, x100是一个随机标识符, y100是随机密钥
  • B将x100发给A, A就知道B用哪个加密了.
  • A收到后,使用y100进行加密,发给B,此时B也知道密钥为y100了。

 

  • 微信公众号
  • 关注微信公众号
  • weinxin
  • QQ群
  • 我们的QQ群号
  • weinxin
王 茂南

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: