DSA批量认证算法

2019/09/18 密码学

DSA(Digital Signature Algorithm)是一种签名算法,其安全性依赖整数有限域离散对数难题。DSA用于数字签名和认证,发送者使用自己的私钥对文件或者消息摘要进行签名,接收者收到消息后使用发送者的公钥来验证签名的真实性。下面提出一种基于DSA签名算法的批量认证算法,并在LibtomCrypt库下实现。

DSA签名以及验证

生成参数

  1. 选择一个哈希函数,输出的结果长度为。在DSS标准中,DSA使用SHA-1哈希算法。如果消息摘要的长度大于模数的位数,那么只取用消息摘要的最左边起位值。

  2. 选择密钥长度,其中是64的倍数,满足

  3. 选择模数位数,满足并且。例如

  4. 选择一个bit的素数

  5. 选择一个bit的素数,并且满足的倍数。(也就是说,的一个素因子)

  6. 选择一个随机数

  7. 计算

到此为止,算法生成三个主要参数,这三个参数在通信双方间共享。

生成公私钥对

  1. 选择一个随机数

  2. 计算

其中为私钥,为公钥。

签名

  1. 选择一个随机数

  2. 计算

  3. 计算。如果,重新选择

签名结果为

验证

  1. 判断签名是否满足

  2. 计算

  3. 计算

  4. 计算

  5. 计算

  6. 判断是否满足&&v=r&&。如果满足则签名验证成功。

基于DSA的批量认证算法

批量认证算法是指对多个消息签名进行1次验证,该算法描述为:

当输出为True时,表示该n个签名都有效,当输出为False时,表示该n个签名中至少有1个签名没有通过。该算法的主要参数生成方法与上述DSA算法的描述一致,区别在于签名过程以及验证过程。

签名

  1. 选择一个随机数

  2. 计算

  3. 计算。如果,重新选择

签名结果为

验证

  1. 判断签名是否满足

  2. 计算

  3. 计算

  4. 计算

  5. 判断是否满足:

效率

使用DSA逐个验证签名与批量验证签名上,运算量的比较如下:

  幂运算 乘法运算 加法运算
批量认证 n+1 2n-1 n-1
逐个认证 2n n 0

表格中可以看出批量认证使用的幂运算比逐个认证少,而乘法运算比逐个认证多。一般而言幂运算耗费的时间比乘法运算要更长,因此批量认证的速度更快。

LibtomCrypt

在LibtomCrypt密码库中,提供了对DSA算法的实现。其中几个比较重要的API如下:

int dsa_sign_hash(const unsigned char *in,
                    unsigned long inlen,
                    unsigned char *out,
                    unsigned long *outlen,
                    prng_state *prng,
                    int wprng,
                    dsa_key *key);

int dsa_verify_hash(const unsigned char *sig,
                    unsigned long siglen,
                    const unsigned char *hash,
                    unsigned long inlen,
                    int *stat,
                    dsa_key *key);

这两个函数分别实现对消息的签名、验证。其中函数参数key的类型必须是PK_PRIVATE。在LibtomCrypt的实现中,DSA的密钥类型(公钥或者私钥)是通过dsa_key类中的type属性决定。

int dsa_set_pqg(const unsigned char *p, unsigned long plen,
                    const unsigned char *q, unsigned long qlen,
                    const unsigned char *g, unsigned long glen,
                    dsa_key *key);

int dsa_set_pqg_dsaparam(const unsigned char *dsaparam,
                    unsigned long dsaparamlen,
                    dsa_key *key);

int dsa_generate_pqg(prng_state *prng,
                    int wprng,
                    int group_size,
                    int modulus_size,
                    dsa_key *key);

int dsa_set_key(const unsigned char *in,
                    unsigned long inlen,
                    int type,
                    dsa_key *key);
                    
int dsa_generate_key(prng_state *prng,
                    int wprng,
                    dsa_key *key);

上面几个函数的详细使用参见LibtomCrypt的开发者文档。(不看文档的后果是什么?)

在LibtomCrypt的基础上,我实现了上述的DSA批量认证算法,代码参见github仓库

参考文献

  1. UBAPV2G: A Unique Batch Authentication Protocol for Vehicle-to-Grid Communications

Search

    Table of Contents