DSA批量认证算法

2019/09/18 密码学

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

DSA签名以及验证

生成参数

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

  2. 选择密钥长度\(L\),其中\(L\)是64的倍数,满足\(512<=L<=1024\)。

  3. 选择模数位数\(N\),满足\(N<L\)并且\(N<Len\)。例如\((L,N) = (1024, 160)\)。

  4. 选择一个\(N\)bit的素数\(q\)。

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

  6. 从\({2...p-2}\)选择一个随机数\(h\)。

  7. 计算\(g=h^{(p-1)/q}\mod p\)。

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

生成公私钥对

  1. 从\({2...q-1}\)选择一个随机数\(x\)。

  2. 计算\(y=g^{x}\mod p\)。

其中\(x\)为私钥,\(y\)为公钥。

签名

  1. 从\({1...q-1}\)选择一个随机数\(k\)。

  2. 计算\(r=(g^{k}\mod p)\mod q\)。

  3. 计算\(s=(k^{-1}(H(m)+xr))\mod q\)。如果\(s=0\),重新选择\(k\)。

签名结果为\((r,s)\)。

验证

  1. 判断签名是否满足\(0<r<q and 0<s<q\)。

  2. 计算\(w=s^{-1}\mod q\)。

  3. 计算\(u_{1}=H(m)*w\mod q\)。

  4. 计算\(u_{2}=rw\mod q\)。

  5. 计算\(v=(g^{u_{1}}y^{u_{2}}\mod p)\mod q\)。

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

基于DSA的批量认证算法

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

\[DSABatchAuth(Sig_{1},Sig_{2},...,Sig{n}) \in \{True, False\}\]

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

签名

  1. 从\({1...q-1}\)选择一个随机数\(k\)。

  2. 计算\(r=g^{k}\mod p\)。

  3. 计算\(s=(k^{-1}(H(m)+xr))\mod q\)。如果\(s=0\),重新选择\(k\)。

签名结果为\((r,s)\)。

验证

  1. 判断签名是否满足\(0<r_{i}<q and 0<s_{i}<q\)。

  2. 计算\(w_{i}=(s^{-1})_{i}\mod q\)。

  3. 计算\(u_{i}=H(m_{i})*w_{i}\mod q\)。

  4. 计算\(v_{i}=r_{i}w_{i}\mod q\)。

  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