1package org.bouncycastle.crypto.signers;
2
3import java.math.BigInteger;
4import java.security.SecureRandom;
5
6import org.bouncycastle.crypto.CipherParameters;
7import org.bouncycastle.crypto.DSA;
8import org.bouncycastle.crypto.params.ECDomainParameters;
9import org.bouncycastle.crypto.params.ECKeyParameters;
10import org.bouncycastle.crypto.params.ECPrivateKeyParameters;
11import org.bouncycastle.crypto.params.ECPublicKeyParameters;
12import org.bouncycastle.crypto.params.ParametersWithRandom;
13import org.bouncycastle.math.ec.ECAlgorithms;
14import org.bouncycastle.math.ec.ECConstants;
15import org.bouncycastle.math.ec.ECCurve;
16import org.bouncycastle.math.ec.ECFieldElement;
17import org.bouncycastle.math.ec.ECMultiplier;
18import org.bouncycastle.math.ec.ECPoint;
19import org.bouncycastle.math.ec.FixedPointCombMultiplier;
20
21/**
22 * EC-DSA as described in X9.62
23 */
24public class ECDSASigner
25    implements ECConstants, DSA
26{
27    private final DSAKCalculator kCalculator;
28
29    private ECKeyParameters key;
30    private SecureRandom    random;
31
32    /**
33     * Default configuration, random K values.
34     */
35    public ECDSASigner()
36    {
37        this.kCalculator = new RandomDSAKCalculator();
38    }
39
40    /**
41     * Configuration with an alternate, possibly deterministic calculator of K.
42     *
43     * @param kCalculator a K value calculator.
44     */
45    public ECDSASigner(DSAKCalculator kCalculator)
46    {
47        this.kCalculator = kCalculator;
48    }
49
50    public void init(
51        boolean                 forSigning,
52        CipherParameters        param)
53    {
54        SecureRandom providedRandom = null;
55
56        if (forSigning)
57        {
58            if (param instanceof ParametersWithRandom)
59            {
60                ParametersWithRandom rParam = (ParametersWithRandom)param;
61
62                this.key = (ECPrivateKeyParameters)rParam.getParameters();
63                providedRandom = rParam.getRandom();
64            }
65            else
66            {
67                this.key = (ECPrivateKeyParameters)param;
68            }
69        }
70        else
71        {
72            this.key = (ECPublicKeyParameters)param;
73        }
74
75        this.random = initSecureRandom(forSigning && !kCalculator.isDeterministic(), providedRandom);
76    }
77
78    // 5.3 pg 28
79    /**
80     * generate a signature for the given message using the key we were
81     * initialised with. For conventional DSA the message should be a SHA-1
82     * hash of the message of interest.
83     *
84     * @param message the message that will be verified later.
85     */
86    public BigInteger[] generateSignature(
87        byte[] message)
88    {
89        ECDomainParameters ec = key.getParameters();
90        BigInteger n = ec.getN();
91        BigInteger e = calculateE(n, message);
92        BigInteger d = ((ECPrivateKeyParameters)key).getD();
93
94        if (kCalculator.isDeterministic())
95        {
96            kCalculator.init(n, d, message);
97        }
98        else
99        {
100            kCalculator.init(n, random);
101        }
102
103        BigInteger r, s;
104
105        ECMultiplier basePointMultiplier = createBasePointMultiplier();
106
107        // 5.3.2
108        do // generate s
109        {
110            BigInteger k;
111            do // generate r
112            {
113                k = kCalculator.nextK();
114
115                ECPoint p = basePointMultiplier.multiply(ec.getG(), k).normalize();
116
117                // 5.3.3
118                r = p.getAffineXCoord().toBigInteger().mod(n);
119            }
120            while (r.equals(ZERO));
121
122            s = k.modInverse(n).multiply(e.add(d.multiply(r))).mod(n);
123        }
124        while (s.equals(ZERO));
125
126        return new BigInteger[]{ r, s };
127    }
128
129    // 5.4 pg 29
130    /**
131     * return true if the value r and s represent a DSA signature for
132     * the passed in message (for standard DSA the message should be
133     * a SHA-1 hash of the real message to be verified).
134     */
135    public boolean verifySignature(
136        byte[]      message,
137        BigInteger  r,
138        BigInteger  s)
139    {
140        ECDomainParameters ec = key.getParameters();
141        BigInteger n = ec.getN();
142        BigInteger e = calculateE(n, message);
143
144        // r in the range [1,n-1]
145        if (r.compareTo(ONE) < 0 || r.compareTo(n) >= 0)
146        {
147            return false;
148        }
149
150        // s in the range [1,n-1]
151        if (s.compareTo(ONE) < 0 || s.compareTo(n) >= 0)
152        {
153            return false;
154        }
155
156        BigInteger c = s.modInverse(n);
157
158        BigInteger u1 = e.multiply(c).mod(n);
159        BigInteger u2 = r.multiply(c).mod(n);
160
161        ECPoint G = ec.getG();
162        ECPoint Q = ((ECPublicKeyParameters)key).getQ();
163
164        ECPoint point = ECAlgorithms.sumOfTwoMultiplies(G, u1, Q, u2);
165
166        // components must be bogus.
167        if (point.isInfinity())
168        {
169            return false;
170        }
171
172        /*
173         * If possible, avoid normalizing the point (to save a modular inversion in the curve field).
174         *
175         * There are ~cofactor elements of the curve field that reduce (modulo the group order) to 'r'.
176         * If the cofactor is known and small, we generate those possible field values and project each
177         * of them to the same "denominator" (depending on the particular projective coordinates in use)
178         * as the calculated point.X. If any of the projected values matches point.X, then we have:
179         *     (point.X / Denominator mod p) mod n == r
180         * as required, and verification succeeds.
181         *
182         * Based on an original idea by Gregory Maxwell (https://github.com/gmaxwell), as implemented in
183         * the libsecp256k1 project (https://github.com/bitcoin/secp256k1).
184         */
185        ECCurve curve = point.getCurve();
186        if (curve != null)
187        {
188            BigInteger cofactor = curve.getCofactor();
189            if (cofactor != null && cofactor.compareTo(EIGHT) <= 0)
190            {
191                ECFieldElement D = getDenominator(curve.getCoordinateSystem(), point);
192                if (D != null && !D.isZero())
193                {
194                    ECFieldElement X = point.getXCoord();
195                    while (curve.isValidFieldElement(r))
196                    {
197                        ECFieldElement R = curve.fromBigInteger(r).multiply(D);
198                        if (R.equals(X))
199                        {
200                            return true;
201                        }
202                        r = r.add(n);
203                    }
204                    return false;
205                }
206            }
207        }
208
209        BigInteger v = point.normalize().getAffineXCoord().toBigInteger().mod(n);
210        return v.equals(r);
211    }
212
213    protected BigInteger calculateE(BigInteger n, byte[] message)
214    {
215        int log2n = n.bitLength();
216        int messageBitLength = message.length * 8;
217
218        BigInteger e = new BigInteger(1, message);
219        if (log2n < messageBitLength)
220        {
221            e = e.shiftRight(messageBitLength - log2n);
222        }
223        return e;
224    }
225
226    protected ECMultiplier createBasePointMultiplier()
227    {
228        return new FixedPointCombMultiplier();
229    }
230
231    protected ECFieldElement getDenominator(int coordinateSystem, ECPoint p)
232    {
233        switch (coordinateSystem)
234        {
235        case ECCurve.COORD_HOMOGENEOUS:
236        case ECCurve.COORD_LAMBDA_PROJECTIVE:
237        case ECCurve.COORD_SKEWED:
238            return p.getZCoord(0);
239        case ECCurve.COORD_JACOBIAN:
240        case ECCurve.COORD_JACOBIAN_CHUDNOVSKY:
241        case ECCurve.COORD_JACOBIAN_MODIFIED:
242            return p.getZCoord(0).square();
243        default:
244            return null;
245        }
246    }
247
248    protected SecureRandom initSecureRandom(boolean needed, SecureRandom provided)
249    {
250        return !needed ? null : (provided != null) ? provided : new SecureRandom();
251    }
252}
253