更新时间:2024-01-31 16:01
普遍大家都认为公钥密码体制是迪菲(W.Diffie)和赫尔曼(E.Hellman)发明的,可鲜为人知的是,默克勒(R.C.Merkle)甚至在他俩之前的1975年就提出了类似的思想,尽管其文章是于1978年发表的,但投稿比较早。因此,公钥密码体制的创始人应该是他们三人。 当然,他们三人只是提出了一种关于公钥密码体制与数字签名的思想,而没有真正实现。不过,他们确实是实现了一种体现公钥密码体制思想、基于离散对数问题的、在不安全的通道上进行密钥形成与交换的新技术。
在整数中,离散对数(英语:Discrete logarithm)是一种基于同余运算和原根的一种对数运算。而在实数中对数的定义 logba是指对于给定的a和b,有一个数x,使得bx=a。相同地在任何群G中可为所有整数k定义一个幂数为bK,而离散对数logba是指使得bK=a的整数k。
离散对数在一些特殊情况下可以快速计算。然而,通常没有具非常效率的方法来计算它们。公钥密码学中几个重要算法的基础,是假设寻找离散对数的问题解,在仔细选择过的群中,并不存在有效率的求解算法。
当模m有原根时,设l为模m的一个原根,则当 时:
此处的 为x以整数l为底,模 时的离散对数值。
离散对数和一般的对数有着相类似的性质:
A和B先约定公共的q=2739·(7149-1)/6+1和g=7。
A选随机数a,并计算7a(modq),且将其送给B(注:a不能向外泄漏);
B将收到7a=127402180119973946824269244334322849749382042586931621654557735290322914679095998681860978813046&595166455458144280588076766033781。
B选随机数b,并计算7b(modq),且将其送给A(注:b不能向外泄漏);
A将收到7b=180162285287453124447828348367998950159670&466953466973130251&2173405995377205847595817691062538069210165184866236213793&4026803049。
此时A和B都能计算出密钥7ab(modq),但别人不太容易算出,因为别人不知道a和b。有兴趣的读者不妨将此作为一个练习,试着计算出7ab(modq)的值。