首页 能链洞察 区块链百科

数字签名 | 基于离散对数的签名方案

数字签名 | 基于离散对数的签名方案

发布时间:2020.07.09

在数字时代中,数字化文档的认证性、完整性和不可否认性,是实现信息化安全的基本要求。数字签名则是满足上述要求的主要方式之一,亦是现代密码学的研究内容之一。

 

数字签名有哪些形式?基于密码学的数字签名优势几何?有哪些常用的数字签名实现方案?使用过程中又潜藏何等风险?我们将先从理解概念为始,再为大家逐步深入介绍。

 

我们在数字签名概念篇中介绍过,公钥密码体制是目前数字签名技术研究的主要方向。1985年,T.ElGamal提出了基于离散对数的公钥加密和签名方法,并奠定了离散对数密码学基础。从那时起,围绕离散对数系统产生了不少研究成果,本文阐述离散对数的基本概念,然后介绍基于离散对数的ElGamal的公钥加密方法和数字签名方法。

 

一、数论基础

 

与前章所述RSA公钥加密体制类似,离散对数加密算法也属于公钥加密体制,而且整个公钥密码体制的复杂性(RSA、离散对数、椭圆曲线)都建立在一些数学难题之上,例如RSA的安全性依赖于大整数因子分解的困难性,而离散对数则依赖有限域离散对数求解的困难性。因此,在介绍具体算法前,我们有必要理解与离散对数有关的数学知识。

 

离散对数:在整数中,离散对数(Discrete logarithm)是一种基于同余运算和原根的一种对数运算。通过离散对数的定义,我们可拆解为三个关键词:对数、同余、原根

 

对数:是我们初中数学就学习过的概念,即对指数运算的逆运算,正如除法是乘法的倒数,反之亦然。这意味着一个数字的对数是必须产生另一个固定数字的指数。

 

同余定理:数论中的重要概念,即给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)。之所以把同余当作一种运算,是因为同余满足运算的诸多性质。比如,同余满足等价关系。具体地说,它满足自反性(一个数永远和自己同余)、对称性(a和b同余,b和a也就同余)和传递性(a和b同余,b和c同余可以推出a和c同余)。

 

原根:是一种数学符号,设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根。(其中φ(m)表示m的欧拉函数)。

 

1617年之前纳皮尔发现了“对数”;

1637年法国数学家笛卡儿提出了“指数”的概念;

1770年欧拉将这两者完美统一,提出“对数源于指数”。

 

二、基于离散对数的签名方案

 

离散对数被誉为当代密码学领域的三大基础之一。基于有限域上离散对数问题的公钥加密体制,最著名的是EIGamal加密体制。

 

该密码体制即可用于加密,又可用于数字签名,美国NIST确立的数字签名标准(Digital Signature Standard,DSS)即是在它的基础上修订的。

 

EIGamal数字签名方案是一种非确定性的签名方案,即对于给定的一个消息,由于选择的随机数不同,将产生不同的数字签名,并且验证算法均会判断有效。同样,下面分成密钥生成、签名算法和验证算法三部分分别介绍:

 

密钥生成算法

EIGamal加密体制的公钥密钥对生成过程如下:

数字签名

 

签名算法

假设待签名的消息为m,签名者选择随机数k进行如下运算,其中h为安全的Hash函数,数字签名为(r,s)。

数字签名

 

验证算法

签名接收者B收到消息m和签名(r,s)后,首先利用上述Hash函数h计算消息摘要h(m),然后检验下列等式是否成立?若成立,则签名有效;否则,签名无效。

数字签名

 

三、基于离散对数的签名方案解析

 

由此可见,离散对数的逆运算,就是普通的指数运算再叠加上取模运算,若已知 g、x、p,是比较容易计算出 y 的,但已知 y、g、p,需要计算 x,那是非常困难的

 

此外,随机数k的选取和保管,对于私钥x的保密性起着重要作用。因此,k值不可对外泄露,不能重复使用,并且由于签名者多次签名时所选取的多个k之间无关联,即对同一个消息进行签名也会产生不同效果,从而避免了出现签名重用的问题,增加安全性

 

但ElGamal加密算法的一个缺点是传递密文的长度是明文长度的两倍,使得传递密文的过程中,通信的信息量增大。而这些问题将在下章椭圆曲线签名方案中得到解决