DSA

发表于 2020-12-09 更新于 2023-05-29 分类于运维，基础，加密和安全

同余定理

两个不同的整数 a、b，被一个整数 m 相除时，得到相同的余数，那么我就可以称 a、b 对 m 同余。

换言之，(a-b)/m 得到一个整数，因为 a、b 相减时把余数抵消掉了。

a、b 对 m 同余，记做 a≡b(mod m)

例如：4≡7(mod 3)

欧拉函数

(其中 p1, p2……pn 为 x 的所有质因数，x 是不为 0 的整数)

欧拉函数表示小于或等于 n 的正整数中与 n 互质的数的数目。定义：φ(1) = 1

举例：φ(8)=4，因为 1,3,5,7 均和 8 互质

阶

设 m>1，且 a、m 互质，那么使得 a^r≡1(mod m)成立的最小的正整数 r 称为 a 对模 m 的阶，记为 δm(a)

原根

原根是一种数学符号，设 m 是正整数，a 是整数，若 a 模 m 的阶等于 φ(m)，则称 a 为模 m 的一个原根

离散对数

离散就是不连续的意思

在整数中，离散对数（英语：Discrete logarithm）是一种基于同余运算和原根的一种对数运算

log_ba：对于给定的 a 和 b 实数，有一个实数 x，使得 b^x=a

log_ba：对于给定的 a 和 b 整数，有一个整数 k，使得 b^k=a

DSA 算法

该算法的安全性依赖于计算模数的离散对数的难度。

公开参数：

参数	说明
p	512~1024 位的素数（可以在一组用户中共享）
q	160 位长，并与 p-1 互素的因子（可以在一组用户中共享）
g	g=h^(p-1)/q mod p，其中 h 小于 p-1 并且 h^(p-1)/q mod p > 1
y	y=g^x mod p （一个 p 位的数）

私密参数：

参数	说明
x	x<q

签名过程：

对于报文 m, 挑选秘密随机数 k: k ∈ (0, q)
r = ( g^k mod p ) mod q
s = ( k^(-1) (H(m) + xr)) mod q，H()应该是 hash 算法，dsa 只支持 sha
签名结果即为(m, r, s)

校验过程：

w = s^(-1)mod q
a = ( H( m ) * w ) mod q
b = ( r * w ) mod q
v = (( g^a * y^b ) mod p ) mod q
若 v = r，则认为签名有效。

openssl 实现

生成 1024 位 DSA 参数集 p、q、g，并输出到参数文件 dsa.param：

[root@centos8 data]$openssl dsaparam -out dsa.param 1024
Generating DSA parameters, 1024 bit long prime
This could take some time
....................++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
....................+......................+.+...........+....+............+..........+...+...+.+........................+..........+.......+.+.+.............+.......+....+......+.....+....+.+....+..................+.+.+....+...+.......+..........................................+........+..................+.+....+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
[root@centos8 data]$cat dsa.param
-----BEGIN DSA PARAMETERS-----
MIIBHgKBgQCXWtR0zjsNLT010pR/Oelvbk1N+vSv2k3bUahkWMuZ6Z5BYQP7+QvK
6D1/+RWD/zHIicOLGYNkOFnX3PBPlx218KqFX1wNkmYz0vqPu1+RYeIVqaVFDEB2
dibqiFhKDhKipR7G3tCwqC94AkTJtduQNnBiM/YRz86nE6nqYVTfrwIVAK+NYZGg
cv5MtoJVdu/rr2wEypp1AoGAZgDa/zIKudSI99nlIUJOODkS064l+rT0JdEIbdcv
TEKeCmWhRMzWdU8y56AWsiTCmChuXHlMsgt6VKcgBMO7FgGTPeIiDegGZvZmXG8B
bL6/gejSrMQmEG1CrJZ6vCqkDRkaKvVSX6ysOMbPk9GcjqAw8KwdkUi4Bxv2wyNL
JK8=
-----END DSA PARAMETERS-----
[root@centos8 data]$openssl dsaparam -in dsa.param --noout -C
static DSA *get_dsa1024(void)
{
    static unsigned char dsap_1024[] = {
        0x97, 0x5A, 0xD4, 0x74, 0xCE, 0x3B, 0x0D, 0x2D, 0x3D, 0x35,
        0xD2, 0x94, 0x7F, 0x39, 0xE9, 0x6F, 0x6E, 0x4D, 0x4D, 0xFA,
        0xF4, 0xAF, 0xDA, 0x4D, 0xDB, 0x51, 0xA8, 0x64, 0x58, 0xCB,
        0x99, 0xE9, 0x9E, 0x41, 0x61, 0x03, 0xFB, 0xF9, 0x0B, 0xCA,
        0xE8, 0x3D, 0x7F, 0xF9, 0x15, 0x83, 0xFF, 0x31, 0xC8, 0x89,
        0xC3, 0x8B, 0x19, 0x83, 0x64, 0x38, 0x59, 0xD7, 0xDC, 0xF0,
        0x4F, 0x97, 0x1D, 0xB5, 0xF0, 0xAA, 0x85, 0x5F, 0x5C, 0x0D,
        0x92, 0x66, 0x33, 0xD2, 0xFA, 0x8F, 0xBB, 0x5F, 0x91, 0x61,
        0xE2, 0x15, 0xA9, 0xA5, 0x45, 0x0C, 0x40, 0x76, 0x76, 0x26,
        0xEA, 0x88, 0x58, 0x4A, 0x0E, 0x12, 0xA2, 0xA5, 0x1E, 0xC6,
        0xDE, 0xD0, 0xB0, 0xA8, 0x2F, 0x78, 0x02, 0x44, 0xC9, 0xB5,
        0xDB, 0x90, 0x36, 0x70, 0x62, 0x33, 0xF6, 0x11, 0xCF, 0xCE,
        0xA7, 0x13, 0xA9, 0xEA, 0x61, 0x54, 0xDF, 0xAF
    };
    static unsigned char dsaq_1024[] = {
        0xAF, 0x8D, 0x61, 0x91, 0xA0, 0x72, 0xFE, 0x4C, 0xB6, 0x82,
        0x55, 0x76, 0xEF, 0xEB, 0xAF, 0x6C, 0x04, 0xCA, 0x9A, 0x75
    };
    static unsigned char dsag_1024[] = {
        0x66, 0x00, 0xDA, 0xFF, 0x32, 0x0A, 0xB9, 0xD4, 0x88, 0xF7,
        0xD9, 0xE5, 0x21, 0x42, 0x4E, 0x38, 0x39, 0x12, 0xD3, 0xAE,
        0x25, 0xFA, 0xB4, 0xF4, 0x25, 0xD1, 0x08, 0x6D, 0xD7, 0x2F,
        0x4C, 0x42, 0x9E, 0x0A, 0x65, 0xA1, 0x44, 0xCC, 0xD6, 0x75,
        0x4F, 0x32, 0xE7, 0xA0, 0x16, 0xB2, 0x24, 0xC2, 0x98, 0x28,
        0x6E, 0x5C, 0x79, 0x4C, 0xB2, 0x0B, 0x7A, 0x54, 0xA7, 0x20,
        0x04, 0xC3, 0xBB, 0x16, 0x01, 0x93, 0x3D, 0xE2, 0x22, 0x0D,
        0xE8, 0x06, 0x66, 0xF6, 0x66, 0x5C, 0x6F, 0x01, 0x6C, 0xBE,
        0xBF, 0x81, 0xE8, 0xD2, 0xAC, 0xC4, 0x26, 0x10, 0x6D, 0x42,
        0xAC, 0x96, 0x7A, 0xBC, 0x2A, 0xA4, 0x0D, 0x19, 0x1A, 0x2A,
        0xF5, 0x52, 0x5F, 0xAC, 0xAC, 0x38, 0xC6, 0xCF, 0x93, 0xD1,
        0x9C, 0x8E, 0xA0, 0x30, 0xF0, 0xAC, 0x1D, 0x91, 0x48, 0xB8,
        0x07, 0x1B, 0xF6, 0xC3, 0x23, 0x4B, 0x24, 0xAF
    };
    DSA *dsa = DSA_new();
    BIGNUM *p, *q, *g;

    if (dsa == NULL)
        return NULL;
    if (!DSA_set0_pqg(dsa, p = BN_bin2bn(dsap_1024, sizeof(dsap_1024), NULL),
                           q = BN_bin2bn(dsaq_1024, sizeof(dsaq_1024), NULL),
                           g = BN_bin2bn(dsag_1024, sizeof(dsag_1024), NULL))) {
        DSA_free(dsa);
        BN_free(p);
        BN_free(q);
        BN_free(g);
        return NULL;
    }
    return dsa;
}

使用参数文件 dsa.param 生成 DSA 私钥文件 dsa.key，并将私钥 3DES 加密：

[root@centos8 data]$openssl gendsa -out dsa.key -des3 dsa.param
Generating DSA key, 1024 bits
Enter PEM pass phrase:
Verifying - Enter PEM pass phrase:
[root@centos8 data]$cat dsa.key
-----BEGIN DSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,5E11A0F348D0EAB7

xlH02528Xuza/YkK4jMWiFoFTMkfvLEPFPdhlh1Zpdb4MGi6pWeHsQf0bXkQ7s1H
JNrcsiPNvYK6eiyYw0QTvGivmSs1IvkeGJPJQnHPkclzn7A6QYG4PXFGQGWxSNr9
6kbSMrlBqSZyo05TN+Hkv76HFIb2Haszo6b5n+h0LMqancDh8hzO4qCLtgL2GSp1
WcsjjVlox7askeZPMHA0FKKx2Sku0yGQtxqBIR2Z/Rf2ePW2aJd3gLRYMTWZO/B2
lIz+ttBZJ84LJsfAZ0oRyRUTpse3pHlp4ohdwFJf4mVkZMbg4BIqGhZjamOuLJeP
RhnfM4MXeI1JZGViUanpipAHmuSxDH12+/UsFdGMeqY2PXIenpLCVna443BV3avh
sP3srdYcKxhOgRa8XAJsrJ/K/T6xR28uE3zAVQ52USo5ifgx4gtu3rEZ0/XqUJ1q
T5I8WwInPzvCMEhyIFL/n/gqhMMaRkAJXaMrZvhnFnCYQg7fFvgKbhJB7CEu1+j3
lfFod1Sb3/IgMlMmwMG87N3DpDn4Q7P+ypY4KDIScc7OJQy+Oy1y7Mm7aWB4xP/R
i/AAXrsOWcdeY2zt/LSWzg==
-----END DSA PRIVATE KEY-----

使用私钥生成公钥文件 dsapublickey.pem：

[root@centos8 data]$openssl dsa -in dsa.key -pubout -out dsa.key.pub
read DSA key
Enter pass phrase for dsa.key:
writing DSA key
[root@centos8 data]$cat dsa.key.pub
-----BEGIN PUBLIC KEY-----
MIIBtjCCASsGByqGSM44BAEwggEeAoGBAJda1HTOOw0tPTXSlH856W9uTU369K/a
TdtRqGRYy5npnkFhA/v5C8roPX/5FYP/MciJw4sZg2Q4Wdfc8E+XHbXwqoVfXA2S
ZjPS+o+7X5Fh4hWppUUMQHZ2JuqIWEoOEqKlHsbe0LCoL3gCRMm125A2cGIz9hHP
zqcTqephVN+vAhUAr41hkaBy/ky2glV27+uvbATKmnUCgYBmANr/Mgq51Ij32eUh
Qk44ORLTriX6tPQl0Qht1y9MQp4KZaFEzNZ1TzLnoBayJMKYKG5ceUyyC3pUpyAE
w7sWAZM94iIN6AZm9mZcbwFsvr+B6NKsxCYQbUKslnq8KqQNGRoq9VJfrKw4xs+T
0ZyOoDDwrB2RSLgHG/bDI0skrwOBhAACgYBJ3oCNHNh7xflq3VaHL30MMl+4Qqrm
Jv0WfHTiOqhYWkezA/ueMcJe/X/pW05ARESVbkrrQx/wxPuR8CO1pFTCPqyI02Rc
AXCz7ejp4OmrdF6RNHds+uT2YZ5sRI7zWX1YXdSIG0TGJ9+jOgeRVpPdNGgVdUxS
SgeCn5UKw6nJew==
-----END PUBLIC KEY-----

从 dsa.key 中读取私钥，解密并输入新口令进行加密，然后写回文件 dsa.key

1	openssl dsa -in dsa.key -out dsa.key -des3 -passin