Source code: gnu/java/security/sig/dss/DSSSignature.java
1 /* DSSSignature.java --
2 Copyright (C) 2001, 2002, 2003, 2006 Free Software Foundation, Inc.
3
4 This file is a part of GNU Classpath.
5
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or (at
9 your option) any later version.
10
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
19 USA
20
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
24 combination.
25
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
37
38
39 package gnu.java.security.sig.dss;
40
41 import gnu.java.security.Registry;
42 import gnu.java.security.hash.IMessageDigest;
43 import gnu.java.security.hash.Sha160;
44 import gnu.java.security.prng.IRandom;
45 import gnu.java.security.sig.BaseSignature;
46 import gnu.java.security.sig.ISignature;
47
48 import java.math.BigInteger;
49 import java.security.PrivateKey;
50 import java.security.PublicKey;
51 import java.security.interfaces.DSAPrivateKey;
52 import java.security.interfaces.DSAPublicKey;
53 import java.util.HashMap;
54 import java.util.Map;
55 import java.util.Random;
56
57 /**
58 * <p>The DSS (Digital Signature Standard) algorithm makes use of the following
59 * parameters:</p>
60 *
61 * <ol>
62 * <li>p: A prime modulus, where <code>2<sup>L-1</sup> < p < 2<sup>L</sup>
63 * </code> for <code>512 <= L <= 1024</code> and <code>L</code> a
64 * multiple of <code>64</code>.</li>
65 * <li>q: A prime divisor of <code>p - 1</code>, where <code>2<sup>159</sup>
66 * < q < 2<sup>160</sup></code>.</li>
67 * <li>g: Where <code>g = h<sup>(p-1)</sup>/q mod p</code>, where
68 * <code>h</code> is any integer with <code>1 < h < p - 1</code> such
69 * that <code>h<sup> (p-1)</sup>/q mod p > 1</code> (<code>g</code> has order
70 * <code>q mod p</code>).</li>
71 * <li>x: A randomly or pseudorandomly generated integer with <code>0 < x
72 * < q</code>.</li>
73 * <li>y: <code>y = g<sup>x</sup> mod p</code>.</li>
74 * <li>k: A randomly or pseudorandomly generated integer with <code>0 < k
75 * < q</code>.</li>
76 * </ol>
77 *
78 * <p>The integers <code>p</code>, <code>q</code>, and <code>g</code> can be
79 * public and can be common to a group of users. A user's private and public
80 * keys are <code>x</code> and <code>y</code>, respectively. They are normally
81 * fixed for a period of time. Parameters <code>x</code> and <code>k</code> are
82 * used for signature generation only, and must be kept secret. Parameter
83 * <code>k</code> must be regenerated for each signature.</p>
84 *
85 * <p>The signature of a message <code>M</code> is the pair of numbers <code>r</code>
86 * and <code>s</code> computed according to the equations below:</p>
87 *
88 * <ul>
89 * <li><code>r = (g<sup>k</sup> mod p) mod q</code> and</li>
90 * <li><code>s = (k<sup>-1</sup>(SHA(M) + xr)) mod q</code>.</li>
91 * </ul>
92 *
93 * <p>In the above, <code>k<sup>-1</sup></code> is the multiplicative inverse of
94 * <code>k</code>, <code>mod q</code>; i.e., <code>(k<sup>-1</sup> k) mod q = 1
95 * </code> and <code>0 < k-1 < q</code>. The value of <code>SHA(M)</code>
96 * is a 160-bit string output by the Secure Hash Algorithm specified in FIPS 180.
97 * For use in computing <code>s</code>, this string must be converted to an
98 * integer.</p>
99 *
100 * <p>As an option, one may wish to check if <code>r == 0</code> or <code>s == 0
101 * </code>. If either <code>r == 0</code> or <code>s == 0</code>, a new value
102 * of <code>k</code> should be generated and the signature should be
103 * recalculated (it is extremely unlikely that <code>r == 0</code> or <code>s ==
104 * 0</code> if signatures are generated properly).</p>
105 *
106 * <p>The signature is transmitted along with the message to the verifier.</p>
107 *
108 * <p>References:</p>
109 * <ol>
110 * <li><a href="http://www.itl.nist.gov/fipspubs/fip186.htm">Digital
111 * Signature Standard (DSS)</a>, Federal Information Processing Standards
112 * Publication 186. National Institute of Standards and Technology.</li>
113 * </ol>
114 */
115 public class DSSSignature extends BaseSignature
116 {
117
118 // Constants and variables
119 // -------------------------------------------------------------------------
120
121 // Constructor(s)
122 // -------------------------------------------------------------------------
123
124 /** Trivial 0-arguments constructor. */
125 public DSSSignature()
126 {
127 super(Registry.DSS_SIG, new Sha160());
128 }
129
130 /** Private constructor for cloning purposes. */
131 private DSSSignature(DSSSignature that)
132 {
133 this();
134
135 this.publicKey = that.publicKey;
136 this.privateKey = that.privateKey;
137 this.md = (IMessageDigest) that.md.clone();
138 }
139
140 // Class methods
141 // -------------------------------------------------------------------------
142
143 public static final BigInteger[] sign(final DSAPrivateKey k, final byte[] h)
144 {
145 final DSSSignature sig = new DSSSignature();
146 final Map attributes = new HashMap();
147 attributes.put(ISignature.SIGNER_KEY, k);
148 sig.setupSign(attributes);
149
150 return sig.computeRS(h);
151 }
152
153 public static final BigInteger[] sign(final DSAPrivateKey k, final byte[] h,
154 Random rnd)
155 {
156 final DSSSignature sig = new DSSSignature();
157 final Map attributes = new HashMap();
158 attributes.put(ISignature.SIGNER_KEY, k);
159 if (rnd != null)
160 {
161 attributes.put(ISignature.SOURCE_OF_RANDOMNESS, rnd);
162 }
163 sig.setupSign(attributes);
164
165 return sig.computeRS(h);
166 }
167
168 public static final BigInteger[] sign(final DSAPrivateKey k, final byte[] h,
169 IRandom irnd)
170 {
171 final DSSSignature sig = new DSSSignature();
172 final Map attributes = new HashMap();
173 attributes.put(ISignature.SIGNER_KEY, k);
174 if (irnd != null)
175 {
176 attributes.put(ISignature.SOURCE_OF_RANDOMNESS, irnd);
177 }
178 sig.setupSign(attributes);
179
180 return sig.computeRS(h);
181 }
182
183 public static final boolean verify(final DSAPublicKey k, final byte[] h,
184 final BigInteger[] rs)
185 {
186 final DSSSignature sig = new DSSSignature();
187 final Map attributes = new HashMap();
188 attributes.put(ISignature.VERIFIER_KEY, k);
189 sig.setupVerify(attributes);
190
191 return sig.checkRS(rs, h);
192 }
193
194 // Implementation of abstract methods in superclass
195 // -------------------------------------------------------------------------
196
197 public Object clone()
198 {
199 return new DSSSignature(this);
200 }
201
202 protected void setupForVerification(PublicKey k)
203 throws IllegalArgumentException
204 {
205 if (!(k instanceof DSAPublicKey))
206 {
207 throw new IllegalArgumentException();
208 }
209 this.publicKey = k;
210 }
211
212 protected void setupForSigning(PrivateKey k) throws IllegalArgumentException
213 {
214 if (!(k instanceof DSAPrivateKey))
215 {
216 throw new IllegalArgumentException();
217 }
218 this.privateKey = k;
219 }
220
221 protected Object generateSignature() throws IllegalStateException
222 {
223 // BigInteger p = ((DSAPrivateKey) privateKey).getParams().getP();
224 // BigInteger q = ((DSAPrivateKey) privateKey).getParams().getQ();
225 // BigInteger g = ((DSAPrivateKey) privateKey).getParams().getG();
226 // BigInteger x = ((DSAPrivateKey) privateKey).getX();
227 // BigInteger m = new BigInteger(1, md.digest());
228 // BigInteger k, r, s;
229 //
230 // byte[] kb = new byte[20]; // we'll use 159 bits only
231 // while (true) {
232 // this.nextRandomBytes(kb);
233 // k = new BigInteger(1, kb);
234 // k.clearBit(159);
235 // r = g.modPow(k, p).mod(q);
236 // if (r.equals(BigInteger.ZERO)) {
237 // continue;
238 // }
239 // s = m.add(x.multiply(r)).multiply(k.modInverse(q)).mod(q);
240 // if (s.equals(BigInteger.ZERO)) {
241 // continue;
242 // }
243 // break;
244 // }
245 final BigInteger[] rs = computeRS(md.digest());
246
247 // return encodeSignature(r, s);
248 return encodeSignature(rs[0], rs[1]);
249 }
250
251 protected boolean verifySignature(Object sig) throws IllegalStateException
252 {
253 final BigInteger[] rs = decodeSignature(sig);
254 // BigInteger r = rs[0];
255 // BigInteger s = rs[1];
256 //
257 // BigInteger g = ((DSAPublicKey) publicKey).getParams().getG();
258 // BigInteger p = ((DSAPublicKey) publicKey).getParams().getP();
259 // BigInteger q = ((DSAPublicKey) publicKey).getParams().getQ();
260 // BigInteger y = ((DSAPublicKey) publicKey).getY();
261 // BigInteger w = s.modInverse(q);
262 //
263 // byte bytes[] = md.digest();
264 // BigInteger u1 = w.multiply(new BigInteger(1, bytes)).mod(q);
265 // BigInteger u2 = r.multiply(w).mod(q);
266 //
267 // BigInteger v = g.modPow(u1, p).multiply(y.modPow(u2, p)).mod(p).mod(q);
268 // return v.equals(r);
269 return checkRS(rs, md.digest());
270 }
271
272 // Other instance methods
273 // -------------------------------------------------------------------------
274
275 /**
276 * Returns the output of a signature generation phase.<p>
277 *
278 * @return an object encapsulating the DSS signature pair <code>r</code> and
279 * <code>s</code>.
280 */
281 private Object encodeSignature(BigInteger r, BigInteger s)
282 {
283 return new BigInteger[] { r, s };
284 }
285
286 /**
287 * Returns the output of a previously generated signature object as a pair
288 * of {@link java.math.BigInteger}.<p>
289 *
290 * @return the DSS signature pair <code>r</code> and <code>s</code>.
291 */
292 private BigInteger[] decodeSignature(Object signature)
293 {
294 return (BigInteger[]) signature;
295 }
296
297 private BigInteger[] computeRS(final byte[] digestBytes)
298 {
299 final BigInteger p = ((DSAPrivateKey) privateKey).getParams().getP();
300 final BigInteger q = ((DSAPrivateKey) privateKey).getParams().getQ();
301 final BigInteger g = ((DSAPrivateKey) privateKey).getParams().getG();
302 final BigInteger x = ((DSAPrivateKey) privateKey).getX();
303 final BigInteger m = new BigInteger(1, digestBytes);
304 BigInteger k, r, s;
305
306 final byte[] kb = new byte[20]; // we'll use 159 bits only
307 while (true)
308 {
309 this.nextRandomBytes(kb);
310 k = new BigInteger(1, kb);
311 k.clearBit(159);
312 r = g.modPow(k, p).mod(q);
313 if (r.equals(BigInteger.ZERO))
314 {
315 continue;
316 }
317 s = m.add(x.multiply(r)).multiply(k.modInverse(q)).mod(q);
318 if (s.equals(BigInteger.ZERO))
319 {
320 continue;
321 }
322 break;
323 }
324
325 return new BigInteger[] { r, s };
326 }
327
328 private boolean checkRS(final BigInteger[] rs, final byte[] digestBytes)
329 {
330 final BigInteger r = rs[0];
331 final BigInteger s = rs[1];
332
333 final BigInteger g = ((DSAPublicKey) publicKey).getParams().getG();
334 final BigInteger p = ((DSAPublicKey) publicKey).getParams().getP();
335 final BigInteger q = ((DSAPublicKey) publicKey).getParams().getQ();
336 final BigInteger y = ((DSAPublicKey) publicKey).getY();
337 final BigInteger w = s.modInverse(q);
338
339 final BigInteger u1 = w.multiply(new BigInteger(1, digestBytes)).mod(q);
340 final BigInteger u2 = r.multiply(w).mod(q);
341
342 final BigInteger v = g.modPow(u1, p).multiply(y.modPow(u2, p)).mod(p).mod(q);
343 return v.equals(r);
344 }
345 }