使用OpenSSL库的DSA算法

2019/12/03

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

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\)。如果满足则签名验证成功。

补充

之前我在阅读LibtomCrypt库的DSA代码实现中,我发现它在生成随机数\(k\)的时候,需要计算一次随机数\(k\)与素数\(q\)的最大公约数是否为1,如果不满足这个条件则重新生成一个随机数\(k\)。为什么要满足这个条件呢?因为后续的步骤中需要计算随机数\(k\)在模\(q\)的逆元。但是我觉得这一步是没有必要的,因为\(q\)本身是一个素数,所以在[0,q-1]范围内的所有数都与\(q\)互素,因此随机数\(k\)与素数\(q\)的最大公约数为1是必然的。

OpenSSL

OpenSSL是一个开放源代码的软件库包,应用程序可以使用这个包来进行安全通信,避免窃听,同时确认另一端连接者的身份。这个包广泛被应用在互联网的网页服务器上。

安装OpenSSL

以Ubuntu为例

  1. 在官网上下载最新的OpenSSL安装包,假设文件为openssl-1.1.1d.tar.gz。

  2. 执行下面的命令:

     tar -xzvf openssl-1.1.1d.tar.gzd
     ./config
     make
     sudo make install
     sudo mv /usr/bin/openssl /usr/bin/openssl.old
     sudo ln -s /usr/local/bin/openssl /usr/bin/openssl
     cd /etc/
     sudo echo "usr/local/lib" >> ld.so.conf
     ldconfig
     # 查看是否安装正确
     openssl version
    
  3. 测试代码,保存到dsa.c。

     #include <stdio.h>
     #include <string.h>
     #include <stdlib.h>
     #include <openssl/dsa.h>
        
     int main(int argc, char** argv) {
         DSA* dsa = DSA_new();
         unsigned char* input_string;
         unsigned char* sign_string;
         unsigned int sig_len;
         unsigned int i;
        
         // 检查输入的参数
         if (argc != 2) {
             fprintf(stderr, "%s <plain text>\n", argv[0]);
             exit(-1);
         }
        
         // 设置输入的字符串
         input_string = (unsigned char*)calloc(strlen(argv[1]) + 1, sizeof(unsigned char));
         if (input_string == NULL) {
             fprintf(stderr, "Unable to allocate memory for input_string\n");
             exit(-1);
         }
         strncpy((char*)input_string, argv[1], strlen(argv[1]));
        
         // 生成1024位的DSA参数
         // Old version:
         // dsa = DSA_generate_parameters(1024, NULL, 0, NULL, NULL, NULL, NULL);
         DSA_generate_parameters_ex(dsa, 1024, NULL, 0, NULL, NULL, NULL);
        
         // 生成DSA的密钥对
         DSA_generate_key(dsa);
        
         // 创建签名字段
         sign_string = (unsigned char*)calloc(DSA_size(dsa), sizeof(unsigned char));    
         if (sign_string == NULL) {
             fprintf(stderr, "Unable to allocate memory for sign_string\n");
             exit(-1);
         }
        
         // 对输入的字符串进行签名
         if (DSA_sign(0, input_string, strlen((char*)input_string), sign_string, &sig_len, dsa) == 0) {
             fprintf(stderr, "Sign Error.\n");
             exit(-1);
         }
        
         // 对上述的签名进行验证
         int is_valid_signature = DSA_verify(0, input_string, strlen((char*)input_string), sign_string, sig_len, dsa);
        
         // 打印DSA的参数以及验证结果
         DSAparams_print_fp(stdout, dsa);
         printf("input_string = %s\nsigned_string = ", input_string);
         for (i=0; i<sig_len; i++) {
             printf("%x%x", (sign_string[i] >> 4) & 0xf, sign_string[i] & 0xf);    
         }
         printf("\nis_valid_signature = ");
         if (is_valid_signature == 1) {
             printf("true\n");
         } else {
             printf("false\n");
         }
         return 0;
     }
    
  4. 编译

     gcc -o dsa_test dsa.c -L/usr/local/lib -I/usr/local/include -lssl -lcrypto
     # 对字符串"ABCDEFG"进行签名和验证。
     ./dsa_test ABCDEFG
    
  5. 上面第4步中,-L参数指定的是OpenSSL的lib目录,-I参数指定的是OpenSSL的include目录,这两个目录都是经过软链接的。如果安装目录不同需要更改该参数,例如安装目录在/usr/local/openssl,那么可以这样写:

     gcc -o dsa_test dsa.c -L/usr/local/openssl/lib -I/usr/local/openssl/include -lssl -lcrypto
     # 对字符串"ABCDEFG"进行签名和验证。
     ./dsa_test ABCDEFG
    

Search

    Table of Contents