离散对数概述

离散对数的由来及发展

离散对数的应用

离散对数的计算实例

离散对数概述

是在整数中，一种基于同余运算和原根的一种对数运算：当模m有原根时，设L为模m的一个原根，则当?x≡L^k(mod m)时： IndLx≡?k (mod Φ(m))，此处的IndLx为 x以整数L为底，模Φ(m)时的离散对数值。

或者简单描述离散对数问题为：给定一个质数p，和有限域Zp上的一个本原元a，对Zp上整数b，寻找唯一的整数c，使得a^c≡b(mod p)。一般的，如果仔细选择p，则认为该问题是难解的，且目前还没有找到计算离散对数问题的多项式时间算法。为了抵抗已知的攻击，p至少应该是150位的十进制整数，且p-1至少有一个大的素数因子。

性质 离散对数和一般的对数有著相类似的性质：

离散对数的由来及发展

在一般参考文献中，都认为公钥密码体制是迪菲(W.Diffie)和赫尔曼(E.Hellman)发明的，可鲜为人知的是，默克勒(R.C.Merkle)甚至在他俩之前的1975年就提出了类似的思想，尽管其文章是于1978年发表的，但投稿比较早。因此，公钥密码体制的创始人应该是他们三人。 当然，他们三人只是提出了一种关于公钥密码体制与数字签名的思想，而没有真正实现。不过，他们确实是实现了一种体现公钥密码体制思想、基于离散对数问题的、在不安全的通道上进行密钥形成与交换的新技术。

所谓离散对数，就是给定正整数x，y，n，求出正整数k（如果存在的话），使y≡xk(mod n)。就目前而言，人们还没有找到计算离散对数的快速算法（所谓快速算法，是指其计算复杂性在多项式范围内的算法，即O(logn)k，其中k为常数）。虽然有快速计算离散对数的量子算法，其计算复杂性为O(logn)2+?着，但现在并没有量子计算机（实用的量子计算机也许根本就建造不出来）。

离散对数的应用

离散对数公钥加密算法是目前最为热门的公钥加密算法 ，其安全性要远远高于基于大数分解的RSA算法。

首先说明一下明一下上述三位科学家公钥密码体制的运作过程（假定A和B两个人要在一个不安全通道如因特网上形成密钥以备日后加密解密所用）。

首先，A、B两人要共同公开约定一个素数q和有限域Fq中的一个生成元g；

A选定一个随机数a∈{1，2，…，q-1}（a可以认为是A之私钥），并将g a(modq)传送给B；

B选定一个随机数b∈{1，2，…，q-1}（b可以认为是B之私钥），并将gb(modq)传送给A；

此时A可以算出(g b)a(modq)，B也可以算出(g a)b(modq)，由于(gb)a(modq) = (g a)b(modq) = g ab(modq)，因此，A和B就形成了一个公共的密钥g ab(modq)，日后便可以此钥来进行传统的加密解密计算，从而达到在不安全的通道上进行保密通讯的目的。

显然，敌方可以截获到g，q，g a(modq)，g b(modq)。因此，如果敌方有快速的求解离散对数的算法，就能从已截获的上述信息中迅速求出a或b，从而算出g ab(modq)。遗憾的是，目前世界上根本就没有快速的求解离散对数的算法，因此当所选的有限域Fq很大时，a或b就很难算出。

椭圆曲线密码算法(ECC)

椭圆曲线密码系统(ECC)就是根据除以p的余数的模算术运算来描述模p的离散对数问题。这并不是形成离散对数问题基础的唯一数学结构。1985年，Neil Koblitz和Victor Miller分别独立提出了椭圆曲线密码系统(ECC)，其安全性依靠将离散对数问题应用于椭圆曲线上的点，且存在一些有力的且能用于密码系统的独特性质。ECC即可用于数字签名方案，又可用于加密方案。

定义模素数p的椭圆曲线是形如y2=x3+ax+b(mod p)的方程的解(x,y)的集合，a与b是两个数。如果(x,y)满足前述方程，那么p=(x,y)就是椭圆曲线上的点。椭圆曲线也能定义在由2m个元素组成的有限域(finite field)上，此种表示可额外提供ECC运算的效率。可以定义椭圆曲线上的两点的"加法",假设P和Q都是曲线上的点，则P+Q总是曲线上的另一点。

椭圆曲线离散对数问题可陈述如下：固定素数p域椭圆曲线，xP表示P点"加"x次。假定Q是P的倍数,使得对x，有：Q=xP ，那么椭圆曲线离散对数问题是给定P和Q求x。

ECC的安全性依赖于椭圆曲线离散对数问题的困难性。与整数因子分解问题和模P的离散对数问题一样，目前没有有效算法解椭圆曲线离散对数问题,

ECC的优势之一是椭圆曲线连对数问题被认为比整数因子分解问题和模P的离散对数问题都难。这额外的难度意味着ECC是目前已知的最强公钥密码系统之一。

离散对数的计算实例

下面给出两个计算离散对数的实例。

【实例一】

Alice和Bob首先商议好p的值，本例假设为p=2579，则本原元为a=2。

假设Alice要发送消息x=1299给Bob，则

1）Bob选择随机数r=765作为自己的私钥，计算q=2^r mod p=2^756 mod 2579=949，作为公钥给Alice；

2）Alice选择随机数k=853，计算y=2^k mod p=2^853 mod 2579=435，作为公钥给Bob；

3）Alice计算密文e=x*q%k mod p=1299*949^853 mod 2579=2396，并传递给Bob；

4）Bob接收到密文后，计算x=e*(y^r)^(-1) mod p=2396*(435^765)^(-1) mod 2579=1299，从而得到原文。

【实例二】

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)的值。

　（数据中的&是因为百度认为数据中存在电话号码，不让发布，观众可以无视之）