[转] 离散对数问题
发布时间：2016-5-13 09:55
分类名称：PKI
Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度。
简言之，可以如下定义离散对数：首先定义一个素数p的原根，为其各次幂产生从1 到p-1的所有整数根，也就是说，如果a是素数p的一个原根，那么数值
a mod p, a^2 mod p, ..., a^( p-1) mod p
是各不相同的整数，并且以某种排列方式组成了从1到p-1的所有整数。
对于一个整数b和素数p的一个原根a，可以找到惟一的指数i，使得
b = a^i mod p 其中0 ≤ i ≤ (p-1)
指数i称为b的以a为基数的模p的离散对数或者指数。该值被记为inda ,p(b)。
基于此背景知识，可以定义Diffie-Hellman密钥交换算法。该算法描述如下：
1、有两个全局公开的参数，一个素数q和一个整数a，a是q的一个原根。
2、假设用户A和B希望交换一个密钥，用户A选择一个作为私有密钥的随机数XA<q，并计算公开密钥YA=a^XA mod q。A对XA的值保密存放而使YA能被B公开获得。类似地，用户B选择一个私有的随机数XB<q，并计算公开密钥YB=a^XB mod q。B对XB的值保密存放而使YB能被A公开获得。
3、用户A产生共享秘密密钥的计算方式是K = (YB)^XA mod q。同样，用户B产生共享秘密密钥的计算是K = (YA)^XB mod q。这两个计算产生相同的结果：
K = (YB)^XA mod q
= (a^XB mod q)^XA mod q
= (a^XB)^XA mod q （根据取模运算规则得到）
= a^XBXA mod q
= (a^XA)^XB mod q
= (a^XA mod q)^XB mod q
= (YA)^XB mod q
因此相当于双方已经交换了一个相同的秘密密钥。
4、因为XA和XB是保密的，一个敌对方可以利用的参数只有q、a、YA和YB。因而敌对方被迫取离散对数来确定密钥。例如，要获取用户B的秘密密钥，敌对方必须先计算
XB = inda ,q(YB)
然后再使用用户B采用的同样方法计算其秘密密钥K。
Diffie-Hellman密钥交换算法的安全性依赖于这样一个事实：虽然计算以一个素数为模的指数相对容易，但计算离散对数却很困难。对于大的素数，计算出离散对数几乎是不可能的。
下面给出例子。密钥交换基于素数q = 97和97的一个原根a = 5。A和B分别选择私有密钥XA = 36和XB = 58。每人计算其公开密钥
YA = 536 = 50 mod 97
YB = 558 = 44 mod 97
在他们相互获取了公开密钥之后，各自通过计算得到双方共享的秘密密钥如下：
K = (YB)XA mod 97 = 4436 = 75 mod 97
K = (YA)XB mod 97 = 5058 = 75 mod 97
从|50，44|出发，攻击者要计算出75很不容易。
=======================================
链接：http://www.zhihu.com/question/26030513/answer/32228619
来源：知乎
DH 用到的数学: A=g^a (mod p), 离散对数问题是指从已知的A, g, p，很难求得a，这里的计算很难的关键是p是个很大的素数，比如1024-bit, 2048-bit, 3076-bit。
ECC算法定义在域Fp (或者F2^m)：r=kq(mod p) ，从已知的r, q, p,很难求得k。这里的p也是大数才安全，但是相对DH比特数可以少很多。ECC里192-bit,224-bit,256-bit 的安全性相当于DH1024-bit, 2048-bit, 3076-bit。因为基于ECC的离散对数问题比DH的基于指数模的离散对数问题难度更大。
还有一个RSA算法，安全性是基于大数的质因数分解。由于历史原因，RSA应该仍然是目前使用最广泛的PK算法。它Key的长度跟DH类似，现在推荐用2048-bit。
个人建议只要对这些原理性的东西知道个大概就可以了。如果想深入理解需要很强的数学功底，做工程的实在是没必要。