系统初始化：
-
选取大素数 p 满足 2(L-1)
-
选取素数 q 满足 q|p-1，2159
-
选取 h 满足1
-
计算 g=h((p-1)/q) mod p；
-
选取 SHA-1 为哈希函数。
初始化公共参数：
public static void init(DsaCode dsa){
System.out.println("生成公共参数...");
Random random = new Random();
// 2^159
dsa.q = BigInteger.probablePrime(160, new Random());
}
System.out.println("q = "+ dsa.q);
// 2^(L-1)
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);
// a=(p-1)/q
BigInteger a=dsa.p.subtract(one).divide(dsa.q);
dsa.h= new BigInteger(300, new Random()); //实验得，h最好不要设置太大
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);
}
二、实现数字签名算法中的公、私钥；
密钥生成：
-
选取 x 满足1
-
计算 y ≡g^x mod p。
公钥为y，私钥为x。
// 该方法取一个随机x，x小于q并且大于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;
}
public static void getKey(DsaCode dsa){
dsa.x = randbint(dsa.q);
//dsa.x=BigInteger.probablePrime(100, new Random());
dsa.y=expMode(dsa.g,dsa.x,dsa.p);
System.out.println("私钥x = "+ dsa.x);
System.out.println("公钥y = "+ dsa.y);
}
三、实现数字签名算法中的签名算法；
签名：假设消息为M
-
选取 k 满足 1
-
计算：
r ≡ ( gk mod p) mod q，
s ≡ k(-1) (H(M)+xr) mod q。
消息M的签名为( r ,s )。
public static void sign(BigInteger M, DsaCode dsa){
// BigInteger k=BigInteger.probablePrime(100, new Random());
BigInteger k = randbint(dsa.q);
dsa.r=(expMode(dsa.g,k,dsa.p)).mod(dsa.q);
// q为素数，由费马小定理求逆元
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);
//푘≡푠^(−1) (퐻(푀)+푥푟) 푚표푑 푞
System.out.println("消息M的签名为(r,s)=("+dsa.r+", "+dsa.s+")");
}
四、实现数字签名算法中的验证算法
public static void verify(BigInteger M, BigInteger r,BigInteger s,DsaCode dsa){
BigInteger two=BigInteger.valueOf(2);
// 푤≡(〖푠′)〗^(−1) 푚표푑 푞, 푢_1≡(퐻(푀')푤) 푚표푑 푞
// 푢_2≡ 푟′ 푤 푚표푑 푞, 푣≡(푔^(푢_1 ) 푦^(푢_2 ) 푚표푑 푝) 푚표푑 푞；
BigInteger w=expMode(dsa.s,(dsa.q.subtract(two)),dsa.q);
BigInteger u1=(M.multiply(w)).mod(dsa.q);
BigInteger u2=(dsa.r.multiply(w)).mod(dsa.q);
//푣≡(푔^(푢_1 ) 푦^(푢_2 ) 푚표푑 푝) 푚표푑 푞；
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);
BigInteger v0=expMode(dsa.g,u1.add(dsa.x.multiply(u2)).mod(dsa.q),dsa.p).mod(dsa.q);
// emmm,我用了两种方式求了v值
System.out.println(v0+"n"+v+"n"+r);
if(v.equals(r))
{
System.out.println("验证完成，输入为有效签名");
}
else { System.out.println("验证完成，输入为无效签名"); }
}
完整代码：
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";
private static final String ALGORITHM = "DSA";
private static final BigInteger zero=BigInteger.valueOf(0);
private static final BigInteger one=BigInteger.valueOf(1);
private static final int KEY_SIZE = 512;
private final static int accuracy = 100;//素数的准确率为1-(2^(-accuracy))
BigInteger p,q,h,g;
BigInteger y,x,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;
}
public DsaCode(){}
// 该方法取一个随机x，x小于q并且大于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;
}
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 "签名验证错误";
}
}
public static void init(DsaCode dsa){
System.out.println("生成公共参数...");
Random random = new Random();
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);
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);
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);
}
public static void getKey(DsaCode dsa){
dsa.x = randbint(dsa.q);
//dsa.x=BigInteger.probablePrime(100, new Random());
dsa.y=expMode(dsa.g,dsa.x,dsa.p);
System.out.println("私钥x = "+ dsa.x);
System.out.println("公钥y = "+ dsa.y);
}
public static void sign(BigInteger M, DsaCode dsa){
// BigInteger k=BigInteger.probablePrime(100, new Random());
BigInteger k = randbint(dsa.q);
//BigInteger k=new BigInteger("23");
dsa.r=(expMode(dsa.g,k,dsa.p)).mod(dsa.q);
// q为素数
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);
//푘≡푠^(−1) (퐻(푀)+푥푟) 푚표푑 푞
System.out.println("消息M的签名为(r,s)=("+dsa.r+", "+dsa.s+")");
}
public static void verify(BigInteger M, BigInteger r,BigInteger s,DsaCode dsa){
BigInteger two=BigInteger.valueOf(2);
// 푤≡(〖푠′)〗^(−1) 푚표푑 푞, 푢_1≡(퐻(푀')푤) 푚표푑 푞
// 푢_2≡ 푟′ 푤 푚표푑 푞, 푣≡(푔^(푢_1 ) 푦^(푢_2 ) 푚표푑 푝) 푚표푑 푞；
BigInteger w=expMode(dsa.s,(dsa.q.subtract(two)),dsa.q);
BigInteger u1=(M.multiply(w)).mod(dsa.q);
BigInteger u2=(dsa.r.multiply(w)).mod(dsa.q);
//푣≡(푔^(푢_1 ) 푦^(푢_2 ) 푚표푑 푝) 푚표푑 푞；
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);
BigInteger v0=expMode(dsa.g,u1.add(dsa.x.multiply(u2)).mod(dsa.q),dsa.p).mod(dsa.q);
// System.out.println(expMode(dsa.g,dsa.x.mod(dsa.q),dsa.p)+"n"+dsa.y);
// BigInteger po=(w.multiply(M.add(dsa.x.multiply(dsa.r)))).mod(dsa.q);
// System.out.println(expMode(dsa.g,dsa.x.mod(dsa.q),dsa.p));
// System.out.println((v1.multiply(v2)).mod(dsa.p)+"n"+expMode(dsa.g,u1.add(dsa.x.multiply(u2)).mod(dsa.q),dsa.p));
System.out.println(v0+"n"+v+"n"+r);
if(v.equals(r))
{
System.out.println("验证完成，输入为有效签名");
}
else { System.out.println("验证完成，输入为无效签名"); }
}
public static void main(String[] args)
{
Scanner input=new Scanner(System.in);
DsaCode dsa=new DsaCode();
init(dsa);
getKey(dsa);
DsaCode d=new DsaCode();
String M="hello,dsa";
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);
}
}
