关于算法:奇妙的安全旅行之DSA算法

hi，大家好，我是开发者 FTD。明天咱们来介绍一下非对称加密算法中的 DSA 算法。

DSA 算法简介

DSA（Digital Signature Algorithm）是 Schnorr 和 ElGamal 签名算法的变种，被美国 NIST 作为 DSS(DigitalSignature Standard) 数字签名的规范。

DSA 是一种更高级的验证形式，它是一种公开密钥算法，不能用来加密数据，个别用于数字签名和认证。DSA 不单单只有公钥、私钥，还有数字签名。私钥加密生成数字签名，公钥验证数据及签名。在 DSA 数字签名和认证中，发送者应用本人的私钥对文件或音讯进行签名，接受者收到音讯后应用发送者的公钥来验证签名的真实性，包含数据的完整性以及数据发送者的身份。如果数据和签名不匹配则认为验证失败！数字签名的作用就是校验数据在传输过程中不被批改。

DSA 数字签名能够了解为是单向加密的降级，不仅校验数据完整性，还校验发送者身份，同时还因为应用了非对称的密钥来保障密钥的平安，所以相比音讯摘要算法更平安。

DSA 只是一种算法，和 RSA 不同之处在于它不能用作加密和解密，也不能进行密钥替换，只用于签名, 它比 RSA 要快很多。

DSA 算法签名过程

1. 应用音讯摘要算法将要发送数据加密生成信息摘要。
2. 发送方用本人的 DSA 私钥对信息摘要再加密，造成数字签名。
3. 将原报文和加密后的数字签名一并通过互联网传给接管方。
4. 接管方用发送方的公钥对数字签名进行解密，同时对收到的数据用音讯摘要算法产生同一信息摘要。
5. 将解密后的信息摘要和收到的数据在接管方从新加密产生的摘要进行比对校验，如果两者统一，则阐明在传送过程中信息没有毁坏和篡改；否则，则阐明信息曾经失去安全性和保密性。

DSA 算法原理

DSA 是基于整数无限域离散对数难题的，其安全性与 RSA 相比差不多。DSA 的一个重要特点是两个素数公开，这样，当应用他人的 p 和 q 时，即便不晓得私钥，你也能确认它们是否是随机产生的，还是作了手脚。

DSA 算法参数定义

• p：一个素模数，其值满足：2^(L-1) < p < 2^L，其中 L 是 64 的倍数，且满足 512≤ L ≤ 1024
• q：(p-1) 的素因子，其值满足 2^159 < q < 2^160，即 q 长度为 160 位。
• g：g = powm(h,(p-1)/q,p)。h 为满足 1 < h < p-1 的任意整数，从而有 powm(h,(p-1)/q,p) > 1
• x：私钥。x 为一个随机或伪随机生成的整数，其值满足 0 < x < q。
• y：公钥。y = powm(g,x,p)

注：

1. 整数 p，q，g 能够公开，也能够仅由一组特定用户共享。
2. 私钥 x 和公钥 y 称为一个密钥对 (x,y)，私钥只能由签名者自己单独持有，公钥则能够公开公布。密钥对能够在一段时间内继续应用。

DSA 签名过程：

1. 产生一个随机数 k，其值满足 0 < k < q
2. 计算 r = powm(g,k,p) mod q，其值满足 r > 0
3. 计算 s = (k^(-1)(SHA(M) + x * r)) mod q，其值满足 s > 0

注：

1. k^(-1) 示意整数 k 对于某个模数的逆元，并非指 k 的倒数。k 在每次签名时都要从新生成，用于不要将同样的 k 用于进行其余的签名运算！

   • 逆元：满足 (a b) mod m = 1 的 a 和 b 互为对于模数 m 的逆元，示意为 a = b^(-1) 或 b = a^(-1)。如 (2 5) mod 3 = 1, 则 2 和 5 互为模数 3 的逆元。
2. SHA(M)：M 的 hash 值，M 为待签名的明文。SHA 是一个单向散列函数。DSS 中选用 SHA1 算法，此时 SHA(M) 为 160 bits 长的数字串，其满足不可逆和抗碰撞性。
3. 最终的签名就是证书对 (r, s)，它们和 M 一起发送到验证方。
4. 只管 r 和 s 为 0 的概率相当小，但只有有任何一个为 0，必须从新生成 k，并从新计算 r 和 s。

DSA 验证签名过程：

咱们用 (r’, s’, M’) 来示意验证方通过某种路径取得的签名后果，之所以这样示意是因为你不能保障你这个签名的后果肯定是发送方生成的真签名相同有可能被人篡改过，甚至掉了包。为了形容简便，上面仍用 (r, s, M) 代替 (r’, s’, M’)。

为了验证 (r, s, M) 的签名是否确由发送方所签，验证方须要有 (g, p, q, y)，验证过程如下：

1. 计算 w = s^(-1) mod q
2. 计算 u1 = (SHA(M) * w) mod q
3. 计算 u2 = (r * w) mod q
4. 计算 v = (((g^u1) (y^u2)) mod p ) mod q = ((g^u1 mod p) (y^u2 mod p) mod p) mod q = (powm(g, u1, p) * powm(y, u2, p) mod p) mod q
5. 若 v 等于 r，则通过验证，否则验证失败

注：

1. 验证通过阐明：签名 (r, s) 无效，即 (r, s, M) 确为发送方的实在签名后果，真实性能够高度信赖，M 未被篡改，为无效信息。
2. 验证失败阐明：签名 (r, s) 有效，即 (r, s, M) 不牢靠，或者 M 被篡改过，或者签名是伪造的，或者 M 的签名有误，M 为有效信息。

DSA 算法实现

DSA 密钥生成：

public static Map<String, Object> initKey(String seed) throws Exception {KeyPairGenerator keygen = KeyPairGenerator.getInstance(KEY_ALGORITHM);
    // 初始化随机产生器   
    SecureRandom secureRandom = new SecureRandom();
    secureRandom.setSeed(seed.getBytes());
    keygen.initialize(1024, secureRandom);

    KeyPair keys = keygen.genKeyPair();

    PublicKey publicKey = keys.getPublic();
    PrivateKey privateKey = keys.getPrivate();

    Map<String, Object> map = new HashMap<String, Object>(2);
    map.put(PUBLIC_KEY, publicKey);
    map.put(PRIVATE_KEY, privateKey);

    return map;
}

用私钥对信息生成数字签名：

public static String sign(byte[] data, String privateKey) throws Exception {
    // 解密由 base64 编码的私钥   
    byte[] keyBytes = Base64.decodeBase64(privateKey);

    // 结构 PKCS8EncodedKeySpec 对象   
    PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);

    // KEY_ALGORITHM 指定的加密算法   
    KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);

    // 取私钥匙对象   
    PrivateKey priKey = keyFactory.generatePrivate(pkcs8KeySpec);

    // 用私钥对信息生成数字签名   
    Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);
    signature.initSign(priKey);
    signature.update(data);

    return Base64.encodeBase64String(signature.sign());
}

校验数字签名：

public static boolean verify(byte[] data, String publicKey, String sign)
        throws Exception {

    // 解密由 base64 编码的公钥   
    byte[] keyBytes = Base64.decodeBase64(publicKey);

    // 结构 X509EncodedKeySpec 对象   
    X509EncodedKeySpec keySpec = new X509EncodedKeySpec(keyBytes);

    // KEY_ALGORITHM 指定的加密算法   
    KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);

    // 取公钥匙对象   
    PublicKey pubKey = keyFactory.generatePublic(keySpec);

    Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);
    signature.initVerify(pubKey);
    signature.update(data);

    // 验证签名是否失常   
    return signature.verify(Base64.decodeBase64(sign));
}

查看残缺代码请拜访：

https://github.com/ForTheDevelopers/JavaSecurity

总结

DSA 算法应该属于数字签名届的翘楚了，非对称密钥大大加强了算法的安全性，目前曾经被广泛应用到数字签名畛域。

创作不易，如果大家喜爱本文，欢送点赞，转发，你的关注是咱们继续前进的能源 ^_^

对于作者

• GitHub：https://github.com/ForTheDevelopers
• 掘金：https://juejin.cn/user/1204720472953022/posts
• CSDN：https://blog.csdn.net/ForTheDevelopers
• segmentfault：https://segmentfault.com/u/for_the_developers

分割作者

• 微信号：ForTheDeveloper
• 公众号：ForTheDevelopers