密码学协议举例[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。

 

例子

 

 

x 十进制 二进制 异或运算后结果
x100 100 1100100 0101011
y100 77 1001101 0000010
p100 13 1001111

 

A告诉B:P100是613798637的最小质因子,其中613798637 = 79 * 97 * 173 * 463

B收到后,随机抽一个,假设就是抽中了这个,计算得到P100=79,再通过计算得到x100和y100

B将x100发给A

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: