DSA 签名算法 Java 实现：生成密钥、签名和验证

import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
import java.security.*;
import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.util.Random;
import java.util.Scanner;
// id=318

public class DsaCode {

    // 签名算法使用的哈希算法
    private static final String SIGNATURE_ALGORITHM = 'SHA-1';
    // DSA 算法名称
    private static final String ALGORITHM = 'DSA';
    private  static final BigInteger zero=BigInteger.valueOf(0);
    private  static final BigInteger one=BigInteger.valueOf(1);
    // DSA 密钥长度
    private static final int KEY_SIZE = 512;
    // 素性测试的准确率，这里设置为 100，表示准确率为 1-(2^(-100))
    private final static int accuracy = 100;
    // DSA 公共参数
    BigInteger p,q,h,g;
    // DSA 私钥和公钥
    BigInteger y,x;
    // DSA 签名结果
    BigInteger r,s;

    // 快速幂算法实现
    private static BigInteger expMode(BigInteger base, BigInteger exp, BigInteger mod) {
        BigInteger res = BigInteger.ONE;
        // 拷贝一份防止修改原引用
        BigInteger tempBase = new BigInteger(base.toString());
        for (int i = 0; i < exp.bitLength(); i++) {
            if (exp.testBit(i)) {// 判断对应二进制位是否为 1
                res = (res.multiply(tempBase)).mod(mod);
            }
            tempBase = tempBase.multiply(tempBase).mod(mod);
        }
        return res;
    }

    // 生成一个随机的 BigInteger，小于 n 且大于 0
    private static BigInteger randbint(BigInteger n) {
        Random rnd = new Random();
        int maxNumBitLength = n.bitLength();
        BigInteger aRandomBigInt;
        do {
            aRandomBigInt = new BigInteger(maxNumBitLength, rnd);
        } while (aRandomBigInt.compareTo(n) > 0);
        return aRandomBigInt;
    }

    // SHA-1 哈希算法，用于将消息 M 转换为哈希值
    public static String getSha1(String str) {
        char[] hexDigit = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
        try {
            MessageDigest md = MessageDigest.getInstance('SHA-1');
            md.update(str.getBytes());
            byte[] digest = md.digest();

            StringBuffer hexstr = new StringBuffer();
            String shaHex = '';
            for (int i = 0; i < digest.length; i++) {
                shaHex = Integer.toHexString(digest[i] & 0xFF);
                if (shaHex.length() < 2) {
                    hexstr.append(0);
                }
                hexstr.append(shaHex);
            }
            String mySignature = hexstr.toString();
            return mySignature;
        } catch (NoSuchAlgorithmException e) {
            return '签名验证错误';
        }
    }

    // 生成 DSA 公共参数
    public static void init(DsaCode dsa) {
        System.out.println('生成公共参数...');
        Random random = new Random();
        // 生成一个 160 位的素数 q
        dsa.q = BigInteger.probablePrime(160, new Random());
        // 判断是否为素数，如果不是则重新生成
        while (!dsa.q.isProbablePrime(accuracy)) {
            dsa.q = BigInteger.probablePrime(160, new Random());
        }
        System.out.println('q = ' + dsa.q);
        // 生成一个 512~1024 位的素数 p，满足 p-1 是 q 的倍数
        int L=random.nextInt(8) * 64 + 352;
        BigInteger mul=new BigInteger(L, new Random());
        dsa.p = dsa.q.multiply(mul).add(one);
        while (!dsa.p.isProbablePrime(accuracy)) {
            L=random.nextInt(8) * 64 + 352;
            mul= new BigInteger(L, new Random());
            dsa.p = dsa.q.multiply(mul).add(one);
        }
        System.out.println('p = ' + dsa.p);
        // 计算 g=h^((p-1)/q) mod p，其中 h 为 1~(p-1) 之间的整数，满足 g 不等于 1
        BigInteger a=dsa.p.subtract(one).divide(dsa.q);
        dsa.h= new BigInteger(300, new Random());
        dsa.g=expMode(dsa.h,a,dsa.p);
        while (dsa.g.compareTo(one)!=1) {
            dsa.h= new BigInteger(300, new Random());
            dsa.g=expMode(dsa.h,a,dsa.p);
        }
        System.out.println('h = ' + dsa.h);
        System.out.println('g = ' + dsa.g);
    }

    // 生成 DSA 密钥对
    public static void getKey(DsaCode dsa) {
        // 随机生成一个私钥 x，满足 0<x<q
        dsa.x = randbint(dsa.q);
        // 根据公式 y=g^x mod p 计算出公钥 y
        dsa.y=expMode(dsa.g,dsa.x,dsa.p);
        System.out.println('私钥 x = ' + dsa.x);
        System.out.println('公钥 y = ' + dsa.y);

    }

    // DSA 签名算法，输入哈希值 M 和 DSA 私钥，输出签名结果
    public static void sign(BigInteger M, DsaCode dsa) {
        // 随机生成一个 r，满足 0<r<q
        BigInteger k = randbint(dsa.q);
        dsa.r=(expMode(dsa.g,k,dsa.p)).mod(dsa.q);
        // 计算 s
        BigInteger two=BigInteger.valueOf(2);
        BigInteger ink=expMode(k,(dsa.q.subtract(two)),dsa.q);
        BigInteger m=M.add(dsa.x.multiply(dsa.r));
        dsa.s=(ink.multiply(m)).mod(dsa.q);
        System.out.println('消息 M 的签名为 (r,s)=(' + dsa.r + ', ' + dsa.s + ')');
    }

    // DSA 验证算法，输入哈希值 M、签名结果 r、s 和 DSA 公共参数，输出签名是否有效
    public static void verify(BigInteger M, BigInteger r,BigInteger s,DsaCode dsa) {
        // 计算 w=s^(-1) mod q
        BigInteger two=BigInteger.valueOf(2);
        BigInteger w=expMode(s,(dsa.q.subtract(two)),dsa.q);
        // 计算 u1=H(M)*w mod q 和 u2=r*w mod q
        BigInteger u1=(M.multiply(w)).mod(dsa.q);
        BigInteger u2=(r.multiply(w)).mod(dsa.q);
        // 计算 v=(g^u1 * y^u2 mod p) mod q
        BigInteger v1=expMode(dsa.g,u1,dsa.p);
        BigInteger v2=expMode(dsa.y,u2,dsa.p);
        BigInteger v=((v1.multiply(v2)).mod(dsa.p)).mod(dsa.q);
        // 比较 v 和 r 是否相等，如果相等则签名有效，否则签名无效
        if(v.equals(r))
        {
            System.out.println('验证完成，输入为有效签名');
        }
        else { System.out.println('验证完成，输入为无效签名'); }

    }

    public static void main(String[] args)
    {
        // 创建 Scanner 对象，用于读取用户输入
        Scanner input=new Scanner(System.in);
        // 创建 DSA 对象
        DsaCode dsa=new DsaCode();
        // 生成 DSA 公共参数
        init(dsa);
        // 生成 DSA 密钥对
        getKey(dsa);
        // 待签名的消息
        String M='hello,dsa';
        // 将消息 M 进行 SHA-1 哈希
        String HM=getSha1(M);
        System.out.println('SHA-1 加密后的消息为' + HM);
        BigInteger Hm=new BigInteger(HM,16);
        // 对消息进行签名
        System.out.println('生产签名中...');
        sign(Hm,dsa);
        // 读取用户输入的签名结果，并进行验证
        System.out.println('请输入需验证的签名：');
        BigInteger r= input.nextBigInteger();
        BigInteger s= input.nextBigInteger();
        verify(Hm, r, s, dsa);
    }
}

代码流程内容：

导入必要的包和类。
定义常量 SIGNATURE_ALGORITHM 和 ALGORITHM，分别表示签名算法使用的哈希算法和 DSA 算法名称。
定义 DsaCode 类，并声明一些成员变量，包括 DSA 公共参数、DSA 私钥和公钥、DSA 签名结果。
实现快速幂算法 expMode，用于计算 g^x mod p 等指数运算。
实现 randbint 方法，用于生成一个随机的 BigInteger，小于 n 且大于 0。
实现 getSha1 方法，用于将字符串转换为 SHA-1 哈希值。
实现 init 方法，用于生成 DSA 公共参数。
实现 getKey 方法，用于生成 DSA 密钥对。
实现 sign 方法，用于对消息进行签名。
实现 verify 方法，用于验证签名是否有效。
实现 main 方法，用于测试 DSA 签名算法。
在 main 方法中，首先创建 Scanner 对象，用于读取用户输入。
然后创建 DSA 对象 dsa，并调用 init 和 getKey 方法生成 DSA 公共参数和密钥对。
接着定义待签名的消息 M，将其进行 SHA-1 哈希，并将哈希值转换为 BigInteger 类型。
调用 sign 方法对消息进行签名，并输出签名结果。
读取用户输入的签名结果 r 和 s，并调用 verify 方法验证签名是否有效。