离散对数加密算法首先,A、B两人要共同公开约定一个素数q和有限域Fq中的一个生成元g；A选定一个随机数a∈{1,2,…,q-1}（a可以认为是A之私钥）,并将ga(modq)传送给B；B选定一个随机

Question

离散对数加密算法
首先,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),日后便可以此钥来进行传统的加密解密计算,
1 我想问的是此时有明文M如何用g^ab加密和解密,以及算法的数学基础.
2 还是说只能用公钥g^a和g^b分别加密,那这种情况的数学基础是什么,数学基础要具体的运算式子,谁都知道是离散对数!

Answer 1

加密的时候直接用X=M*g^{ab}来实现,mod q就不写了,反正你知道域的概念.
至于解密,就是要知道g^{-ab}.以A为例,A已经掌握的信息是g,a,q,g^b,那么
g^{-ab}=g^{-ab+b(q-1)}=g^{b(q-1-a)}=(g^b)^{q-1-a}
这里唯一需要的条件就是g^{q-1}=1,注意{1,2,…,q-1}的乘法构成群,所以由Lagrange定理可得到g^{q-1}=1.
原理就是这样,这种方法叫Diffie–Hellman交换.