DSA算法
DSA算法
Digital Signature Algorithm (DSA)是Schnorr和ElGamal签名算法的变种，被美国NIST作为DSS(DigitalSignature Standard)。算法中应用了下述参数：
p：L bits长的素数。L是64的倍数，范围是512到1024；
q：p - 1的160bits的素因子；
g：g = h^((p-1)/q) mod p，h满足h < p - 1, h^((p-1)/q) mod p > 1；
x：x < q，x为私钥；
y：y = g^x mod p ，( p, q, g, y )为公钥；
H( x )：One-Way Hash函数。DSS中选用SHA( Secure Hash Algorithm )。
p, q, g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。签名及验证协议如下：
1. P产生随机数k，k < q；
2. P计算r = ( g^k mod p ) mod q
s = ( k^(-1) (H(m) + xr)) mod q
签名结果是( m, r, s )。
3. 验证时计算w = s^(-1)mod q
u1 = ( H( m ) * w ) mod q
u2 = ( r * w ) mod q
v = (( g^u1 * y^u2 ) mod p ) mod q
若v = r，则认为签名有效。
DSA是基于整数有限域离散对数难题的，其安全性与RSA相比差不多。DSA的一个重要特点是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥，你也能确认它们是否是随机产生的，还是作了手脚。RSA算法却作不到。
JAVA实现
java code
package freenet.crypt;
import java.math.BigInteger;
import java.util.Random;
import net.i2p.util.NativeBigInteger;
/**
* Implements the Digital Signature Algorithm (DSA) described in FIPS-186
*/
public class DSA {
/**
* Returns a DSA signature given a group, private key (x), a random nonce
* (k), and the hash of the message (m).
*/
public static DSASignature sign(DSAGroup g,
DSAPrivateKey x,
BigInteger k,
BigInteger m) {
BigInteger r=g.getG().modPow(k, g.getP()).mod(g.getQ());
BigInteger kInv=k.modInverse(g.getQ());
return sign(g, x, r, kInv, m);
}
public static DSASignature sign(DSAGroup g, DSAPrivateKey x, BigInteger m, Random r) {
BigInteger k;
do {
k=new NativeBigInteger(160, r);
} while (https://www.wendangku.net/doc/c02774194.html,pareTo(g.getQ())>-1 || https://www.wendangku.net/doc/c02774194.html,pareTo(BigInteger.ZERO)==0); return sign(g, x, k, m);
}
/**
* Precalculates a number of r, kInv pairs given a random source
*/
public static BigInteger[][] signaturePrecalculate(DSAGroup g,
int count, Random r) {
BigInteger[][] result=new BigInteger[count][2];
for (int i=0; i BigInteger k; do { k=new NativeBigInteger(160, r); } while (https://www.wendangku.net/doc/c02774194.html,pareTo(g.getQ())>-1 || https://www.wendangku.net/doc/c02774194.html,pareTo(BigInteger.ZERO)==0); result[0] = g.getG().modPow(k, g.getP()); // r result[1] = k.modInverse(g.getQ()); // k^-1 } return result; } /** * Returns a DSA signature given a group, private key (x), * the precalculated values of r and k^-1, and the hash * of the message (m) */ public static DSASignature sign(DSAGroup g, DSAPrivateKey x, BigInteger r, BigInteger kInv, BigInteger m) { BigInteger s1=m.add(x.getX().multiply(r)).mod(g.getQ()); BigInteger s=kInv.multiply(s1).mod(g.getQ()); return new DSASignature(r,s); } /** * Verifies the message authenticity given a group, the public key * (y), a signature, and the hash of the message (m). */ public static boolean verify(DSAPublicKey kp, DSASignature sig, BigInteger m) { try { BigInteger w=sig.getS().modInverse(kp.getQ()); BigInteger u1=m.multiply(w).mod(kp.getQ()); BigInteger u2=sig.getR().multiply(w).mod(kp.getQ()); BigInteger v1=kp.getG().modPow(u1, kp.getP()); BigInteger v2=kp.getY().modPow(u2, kp.getP()); BigInteger v=v1.multiply(v2).mod(kp.getP()).mod(kp.getQ()); return v.equals(sig.getR()); //FIXME: is there a better way to handle this exception raised on the 'w=' line above? } catch (ArithmeticException e) { // catch error raised by invalid data return false; // and report that that data is bad. } } public static void main(String[] args) throws Exception { //DSAGroup g=DSAGroup.readFromField(args[0]); DSAGroup g = Global.DSAgroupA; Random y = new Random(); BigInteger toSign = new BigInteger(256, y); DSAPrivateKey pk=new DSAPrivateKey(g, y); DSAPublicKey pub=new DSAPublicKey(g, pk); DSASignature sig=sign(g, pk, toSign, y); int len = (sig.getR().bitLength() + sig.getS().bitLength()); System.err.println("Length: "+len+" bits"); while(true) { long startTime = System.currentTimeMillis(); for(int i=0;i<1000;i++) { boolean success = verify(pub, sig, toSign); if(!success) { System.err.println("Failure: "+pk+" "+pub+" on "+g); } } long endTime = System.currentTimeMillis(); System.out.println("Speed: "+(endTime - startTime)/1000.0+" ms/signature"); } } } ===============================================