source: trip-planner-front/node_modules/node-forge/lib/rsa.js@ fa375fe

Last change on this file since fa375fe was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • Property mode set to 100644
File size: 55.7 KB
Line 
1/**
2 * Javascript implementation of basic RSA algorithms.
3 *
4 * @author Dave Longley
5 *
6 * Copyright (c) 2010-2014 Digital Bazaar, Inc.
7 *
8 * The only algorithm currently supported for PKI is RSA.
9 *
10 * An RSA key is often stored in ASN.1 DER format. The SubjectPublicKeyInfo
11 * ASN.1 structure is composed of an algorithm of type AlgorithmIdentifier
12 * and a subjectPublicKey of type bit string.
13 *
14 * The AlgorithmIdentifier contains an Object Identifier (OID) and parameters
15 * for the algorithm, if any. In the case of RSA, there aren't any.
16 *
17 * SubjectPublicKeyInfo ::= SEQUENCE {
18 * algorithm AlgorithmIdentifier,
19 * subjectPublicKey BIT STRING
20 * }
21 *
22 * AlgorithmIdentifer ::= SEQUENCE {
23 * algorithm OBJECT IDENTIFIER,
24 * parameters ANY DEFINED BY algorithm OPTIONAL
25 * }
26 *
27 * For an RSA public key, the subjectPublicKey is:
28 *
29 * RSAPublicKey ::= SEQUENCE {
30 * modulus INTEGER, -- n
31 * publicExponent INTEGER -- e
32 * }
33 *
34 * PrivateKeyInfo ::= SEQUENCE {
35 * version Version,
36 * privateKeyAlgorithm PrivateKeyAlgorithmIdentifier,
37 * privateKey PrivateKey,
38 * attributes [0] IMPLICIT Attributes OPTIONAL
39 * }
40 *
41 * Version ::= INTEGER
42 * PrivateKeyAlgorithmIdentifier ::= AlgorithmIdentifier
43 * PrivateKey ::= OCTET STRING
44 * Attributes ::= SET OF Attribute
45 *
46 * An RSA private key as the following structure:
47 *
48 * RSAPrivateKey ::= SEQUENCE {
49 * version Version,
50 * modulus INTEGER, -- n
51 * publicExponent INTEGER, -- e
52 * privateExponent INTEGER, -- d
53 * prime1 INTEGER, -- p
54 * prime2 INTEGER, -- q
55 * exponent1 INTEGER, -- d mod (p-1)
56 * exponent2 INTEGER, -- d mod (q-1)
57 * coefficient INTEGER -- (inverse of q) mod p
58 * }
59 *
60 * Version ::= INTEGER
61 *
62 * The OID for the RSA key algorithm is: 1.2.840.113549.1.1.1
63 */
64var forge = require('./forge');
65require('./asn1');
66require('./jsbn');
67require('./oids');
68require('./pkcs1');
69require('./prime');
70require('./random');
71require('./util');
72
73if(typeof BigInteger === 'undefined') {
74 var BigInteger = forge.jsbn.BigInteger;
75}
76
77var _crypto = forge.util.isNodejs ? require('crypto') : null;
78
79// shortcut for asn.1 API
80var asn1 = forge.asn1;
81
82// shortcut for util API
83var util = forge.util;
84
85/*
86 * RSA encryption and decryption, see RFC 2313.
87 */
88forge.pki = forge.pki || {};
89module.exports = forge.pki.rsa = forge.rsa = forge.rsa || {};
90var pki = forge.pki;
91
92// for finding primes, which are 30k+i for i = 1, 7, 11, 13, 17, 19, 23, 29
93var GCD_30_DELTA = [6, 4, 2, 4, 2, 4, 6, 2];
94
95// validator for a PrivateKeyInfo structure
96var privateKeyValidator = {
97 // PrivateKeyInfo
98 name: 'PrivateKeyInfo',
99 tagClass: asn1.Class.UNIVERSAL,
100 type: asn1.Type.SEQUENCE,
101 constructed: true,
102 value: [{
103 // Version (INTEGER)
104 name: 'PrivateKeyInfo.version',
105 tagClass: asn1.Class.UNIVERSAL,
106 type: asn1.Type.INTEGER,
107 constructed: false,
108 capture: 'privateKeyVersion'
109 }, {
110 // privateKeyAlgorithm
111 name: 'PrivateKeyInfo.privateKeyAlgorithm',
112 tagClass: asn1.Class.UNIVERSAL,
113 type: asn1.Type.SEQUENCE,
114 constructed: true,
115 value: [{
116 name: 'AlgorithmIdentifier.algorithm',
117 tagClass: asn1.Class.UNIVERSAL,
118 type: asn1.Type.OID,
119 constructed: false,
120 capture: 'privateKeyOid'
121 }]
122 }, {
123 // PrivateKey
124 name: 'PrivateKeyInfo',
125 tagClass: asn1.Class.UNIVERSAL,
126 type: asn1.Type.OCTETSTRING,
127 constructed: false,
128 capture: 'privateKey'
129 }]
130};
131
132// validator for an RSA private key
133var rsaPrivateKeyValidator = {
134 // RSAPrivateKey
135 name: 'RSAPrivateKey',
136 tagClass: asn1.Class.UNIVERSAL,
137 type: asn1.Type.SEQUENCE,
138 constructed: true,
139 value: [{
140 // Version (INTEGER)
141 name: 'RSAPrivateKey.version',
142 tagClass: asn1.Class.UNIVERSAL,
143 type: asn1.Type.INTEGER,
144 constructed: false,
145 capture: 'privateKeyVersion'
146 }, {
147 // modulus (n)
148 name: 'RSAPrivateKey.modulus',
149 tagClass: asn1.Class.UNIVERSAL,
150 type: asn1.Type.INTEGER,
151 constructed: false,
152 capture: 'privateKeyModulus'
153 }, {
154 // publicExponent (e)
155 name: 'RSAPrivateKey.publicExponent',
156 tagClass: asn1.Class.UNIVERSAL,
157 type: asn1.Type.INTEGER,
158 constructed: false,
159 capture: 'privateKeyPublicExponent'
160 }, {
161 // privateExponent (d)
162 name: 'RSAPrivateKey.privateExponent',
163 tagClass: asn1.Class.UNIVERSAL,
164 type: asn1.Type.INTEGER,
165 constructed: false,
166 capture: 'privateKeyPrivateExponent'
167 }, {
168 // prime1 (p)
169 name: 'RSAPrivateKey.prime1',
170 tagClass: asn1.Class.UNIVERSAL,
171 type: asn1.Type.INTEGER,
172 constructed: false,
173 capture: 'privateKeyPrime1'
174 }, {
175 // prime2 (q)
176 name: 'RSAPrivateKey.prime2',
177 tagClass: asn1.Class.UNIVERSAL,
178 type: asn1.Type.INTEGER,
179 constructed: false,
180 capture: 'privateKeyPrime2'
181 }, {
182 // exponent1 (d mod (p-1))
183 name: 'RSAPrivateKey.exponent1',
184 tagClass: asn1.Class.UNIVERSAL,
185 type: asn1.Type.INTEGER,
186 constructed: false,
187 capture: 'privateKeyExponent1'
188 }, {
189 // exponent2 (d mod (q-1))
190 name: 'RSAPrivateKey.exponent2',
191 tagClass: asn1.Class.UNIVERSAL,
192 type: asn1.Type.INTEGER,
193 constructed: false,
194 capture: 'privateKeyExponent2'
195 }, {
196 // coefficient ((inverse of q) mod p)
197 name: 'RSAPrivateKey.coefficient',
198 tagClass: asn1.Class.UNIVERSAL,
199 type: asn1.Type.INTEGER,
200 constructed: false,
201 capture: 'privateKeyCoefficient'
202 }]
203};
204
205// validator for an RSA public key
206var rsaPublicKeyValidator = {
207 // RSAPublicKey
208 name: 'RSAPublicKey',
209 tagClass: asn1.Class.UNIVERSAL,
210 type: asn1.Type.SEQUENCE,
211 constructed: true,
212 value: [{
213 // modulus (n)
214 name: 'RSAPublicKey.modulus',
215 tagClass: asn1.Class.UNIVERSAL,
216 type: asn1.Type.INTEGER,
217 constructed: false,
218 capture: 'publicKeyModulus'
219 }, {
220 // publicExponent (e)
221 name: 'RSAPublicKey.exponent',
222 tagClass: asn1.Class.UNIVERSAL,
223 type: asn1.Type.INTEGER,
224 constructed: false,
225 capture: 'publicKeyExponent'
226 }]
227};
228
229// validator for an SubjectPublicKeyInfo structure
230// Note: Currently only works with an RSA public key
231var publicKeyValidator = forge.pki.rsa.publicKeyValidator = {
232 name: 'SubjectPublicKeyInfo',
233 tagClass: asn1.Class.UNIVERSAL,
234 type: asn1.Type.SEQUENCE,
235 constructed: true,
236 captureAsn1: 'subjectPublicKeyInfo',
237 value: [{
238 name: 'SubjectPublicKeyInfo.AlgorithmIdentifier',
239 tagClass: asn1.Class.UNIVERSAL,
240 type: asn1.Type.SEQUENCE,
241 constructed: true,
242 value: [{
243 name: 'AlgorithmIdentifier.algorithm',
244 tagClass: asn1.Class.UNIVERSAL,
245 type: asn1.Type.OID,
246 constructed: false,
247 capture: 'publicKeyOid'
248 }]
249 }, {
250 // subjectPublicKey
251 name: 'SubjectPublicKeyInfo.subjectPublicKey',
252 tagClass: asn1.Class.UNIVERSAL,
253 type: asn1.Type.BITSTRING,
254 constructed: false,
255 value: [{
256 // RSAPublicKey
257 name: 'SubjectPublicKeyInfo.subjectPublicKey.RSAPublicKey',
258 tagClass: asn1.Class.UNIVERSAL,
259 type: asn1.Type.SEQUENCE,
260 constructed: true,
261 optional: true,
262 captureAsn1: 'rsaPublicKey'
263 }]
264 }]
265};
266
267/**
268 * Wrap digest in DigestInfo object.
269 *
270 * This function implements EMSA-PKCS1-v1_5-ENCODE as per RFC 3447.
271 *
272 * DigestInfo ::= SEQUENCE {
273 * digestAlgorithm DigestAlgorithmIdentifier,
274 * digest Digest
275 * }
276 *
277 * DigestAlgorithmIdentifier ::= AlgorithmIdentifier
278 * Digest ::= OCTET STRING
279 *
280 * @param md the message digest object with the hash to sign.
281 *
282 * @return the encoded message (ready for RSA encrytion)
283 */
284var emsaPkcs1v15encode = function(md) {
285 // get the oid for the algorithm
286 var oid;
287 if(md.algorithm in pki.oids) {
288 oid = pki.oids[md.algorithm];
289 } else {
290 var error = new Error('Unknown message digest algorithm.');
291 error.algorithm = md.algorithm;
292 throw error;
293 }
294 var oidBytes = asn1.oidToDer(oid).getBytes();
295
296 // create the digest info
297 var digestInfo = asn1.create(
298 asn1.Class.UNIVERSAL, asn1.Type.SEQUENCE, true, []);
299 var digestAlgorithm = asn1.create(
300 asn1.Class.UNIVERSAL, asn1.Type.SEQUENCE, true, []);
301 digestAlgorithm.value.push(asn1.create(
302 asn1.Class.UNIVERSAL, asn1.Type.OID, false, oidBytes));
303 digestAlgorithm.value.push(asn1.create(
304 asn1.Class.UNIVERSAL, asn1.Type.NULL, false, ''));
305 var digest = asn1.create(
306 asn1.Class.UNIVERSAL, asn1.Type.OCTETSTRING,
307 false, md.digest().getBytes());
308 digestInfo.value.push(digestAlgorithm);
309 digestInfo.value.push(digest);
310
311 // encode digest info
312 return asn1.toDer(digestInfo).getBytes();
313};
314
315/**
316 * Performs x^c mod n (RSA encryption or decryption operation).
317 *
318 * @param x the number to raise and mod.
319 * @param key the key to use.
320 * @param pub true if the key is public, false if private.
321 *
322 * @return the result of x^c mod n.
323 */
324var _modPow = function(x, key, pub) {
325 if(pub) {
326 return x.modPow(key.e, key.n);
327 }
328
329 if(!key.p || !key.q) {
330 // allow calculation without CRT params (slow)
331 return x.modPow(key.d, key.n);
332 }
333
334 // pre-compute dP, dQ, and qInv if necessary
335 if(!key.dP) {
336 key.dP = key.d.mod(key.p.subtract(BigInteger.ONE));
337 }
338 if(!key.dQ) {
339 key.dQ = key.d.mod(key.q.subtract(BigInteger.ONE));
340 }
341 if(!key.qInv) {
342 key.qInv = key.q.modInverse(key.p);
343 }
344
345 /* Chinese remainder theorem (CRT) states:
346
347 Suppose n1, n2, ..., nk are positive integers which are pairwise
348 coprime (n1 and n2 have no common factors other than 1). For any
349 integers x1, x2, ..., xk there exists an integer x solving the
350 system of simultaneous congruences (where ~= means modularly
351 congruent so a ~= b mod n means a mod n = b mod n):
352
353 x ~= x1 mod n1
354 x ~= x2 mod n2
355 ...
356 x ~= xk mod nk
357
358 This system of congruences has a single simultaneous solution x
359 between 0 and n - 1. Furthermore, each xk solution and x itself
360 is congruent modulo the product n = n1*n2*...*nk.
361 So x1 mod n = x2 mod n = xk mod n = x mod n.
362
363 The single simultaneous solution x can be solved with the following
364 equation:
365
366 x = sum(xi*ri*si) mod n where ri = n/ni and si = ri^-1 mod ni.
367
368 Where x is less than n, xi = x mod ni.
369
370 For RSA we are only concerned with k = 2. The modulus n = pq, where
371 p and q are coprime. The RSA decryption algorithm is:
372
373 y = x^d mod n
374
375 Given the above:
376
377 x1 = x^d mod p
378 r1 = n/p = q
379 s1 = q^-1 mod p
380 x2 = x^d mod q
381 r2 = n/q = p
382 s2 = p^-1 mod q
383
384 So y = (x1r1s1 + x2r2s2) mod n
385 = ((x^d mod p)q(q^-1 mod p) + (x^d mod q)p(p^-1 mod q)) mod n
386
387 According to Fermat's Little Theorem, if the modulus P is prime,
388 for any integer A not evenly divisible by P, A^(P-1) ~= 1 mod P.
389 Since A is not divisible by P it follows that if:
390 N ~= M mod (P - 1), then A^N mod P = A^M mod P. Therefore:
391
392 A^N mod P = A^(M mod (P - 1)) mod P. (The latter takes less effort
393 to calculate). In order to calculate x^d mod p more quickly the
394 exponent d mod (p - 1) is stored in the RSA private key (the same
395 is done for x^d mod q). These values are referred to as dP and dQ
396 respectively. Therefore we now have:
397
398 y = ((x^dP mod p)q(q^-1 mod p) + (x^dQ mod q)p(p^-1 mod q)) mod n
399
400 Since we'll be reducing x^dP by modulo p (same for q) we can also
401 reduce x by p (and q respectively) before hand. Therefore, let
402
403 xp = ((x mod p)^dP mod p), and
404 xq = ((x mod q)^dQ mod q), yielding:
405
406 y = (xp*q*(q^-1 mod p) + xq*p*(p^-1 mod q)) mod n
407
408 This can be further reduced to a simple algorithm that only
409 requires 1 inverse (the q inverse is used) to be used and stored.
410 The algorithm is called Garner's algorithm. If qInv is the
411 inverse of q, we simply calculate:
412
413 y = (qInv*(xp - xq) mod p) * q + xq
414
415 However, there are two further complications. First, we need to
416 ensure that xp > xq to prevent signed BigIntegers from being used
417 so we add p until this is true (since we will be mod'ing with
418 p anyway). Then, there is a known timing attack on algorithms
419 using the CRT. To mitigate this risk, "cryptographic blinding"
420 should be used. This requires simply generating a random number r
421 between 0 and n-1 and its inverse and multiplying x by r^e before
422 calculating y and then multiplying y by r^-1 afterwards. Note that
423 r must be coprime with n (gcd(r, n) === 1) in order to have an
424 inverse.
425 */
426
427 // cryptographic blinding
428 var r;
429 do {
430 r = new BigInteger(
431 forge.util.bytesToHex(forge.random.getBytes(key.n.bitLength() / 8)),
432 16);
433 } while(r.compareTo(key.n) >= 0 || !r.gcd(key.n).equals(BigInteger.ONE));
434 x = x.multiply(r.modPow(key.e, key.n)).mod(key.n);
435
436 // calculate xp and xq
437 var xp = x.mod(key.p).modPow(key.dP, key.p);
438 var xq = x.mod(key.q).modPow(key.dQ, key.q);
439
440 // xp must be larger than xq to avoid signed bit usage
441 while(xp.compareTo(xq) < 0) {
442 xp = xp.add(key.p);
443 }
444
445 // do last step
446 var y = xp.subtract(xq)
447 .multiply(key.qInv).mod(key.p)
448 .multiply(key.q).add(xq);
449
450 // remove effect of random for cryptographic blinding
451 y = y.multiply(r.modInverse(key.n)).mod(key.n);
452
453 return y;
454};
455
456/**
457 * NOTE: THIS METHOD IS DEPRECATED, use 'sign' on a private key object or
458 * 'encrypt' on a public key object instead.
459 *
460 * Performs RSA encryption.
461 *
462 * The parameter bt controls whether to put padding bytes before the
463 * message passed in. Set bt to either true or false to disable padding
464 * completely (in order to handle e.g. EMSA-PSS encoding seperately before),
465 * signaling whether the encryption operation is a public key operation
466 * (i.e. encrypting data) or not, i.e. private key operation (data signing).
467 *
468 * For PKCS#1 v1.5 padding pass in the block type to use, i.e. either 0x01
469 * (for signing) or 0x02 (for encryption). The key operation mode (private
470 * or public) is derived from this flag in that case).
471 *
472 * @param m the message to encrypt as a byte string.
473 * @param key the RSA key to use.
474 * @param bt for PKCS#1 v1.5 padding, the block type to use
475 * (0x01 for private key, 0x02 for public),
476 * to disable padding: true = public key, false = private key.
477 *
478 * @return the encrypted bytes as a string.
479 */
480pki.rsa.encrypt = function(m, key, bt) {
481 var pub = bt;
482 var eb;
483
484 // get the length of the modulus in bytes
485 var k = Math.ceil(key.n.bitLength() / 8);
486
487 if(bt !== false && bt !== true) {
488 // legacy, default to PKCS#1 v1.5 padding
489 pub = (bt === 0x02);
490 eb = _encodePkcs1_v1_5(m, key, bt);
491 } else {
492 eb = forge.util.createBuffer();
493 eb.putBytes(m);
494 }
495
496 // load encryption block as big integer 'x'
497 // FIXME: hex conversion inefficient, get BigInteger w/byte strings
498 var x = new BigInteger(eb.toHex(), 16);
499
500 // do RSA encryption
501 var y = _modPow(x, key, pub);
502
503 // convert y into the encrypted data byte string, if y is shorter in
504 // bytes than k, then prepend zero bytes to fill up ed
505 // FIXME: hex conversion inefficient, get BigInteger w/byte strings
506 var yhex = y.toString(16);
507 var ed = forge.util.createBuffer();
508 var zeros = k - Math.ceil(yhex.length / 2);
509 while(zeros > 0) {
510 ed.putByte(0x00);
511 --zeros;
512 }
513 ed.putBytes(forge.util.hexToBytes(yhex));
514 return ed.getBytes();
515};
516
517/**
518 * NOTE: THIS METHOD IS DEPRECATED, use 'decrypt' on a private key object or
519 * 'verify' on a public key object instead.
520 *
521 * Performs RSA decryption.
522 *
523 * The parameter ml controls whether to apply PKCS#1 v1.5 padding
524 * or not. Set ml = false to disable padding removal completely
525 * (in order to handle e.g. EMSA-PSS later on) and simply pass back
526 * the RSA encryption block.
527 *
528 * @param ed the encrypted data to decrypt in as a byte string.
529 * @param key the RSA key to use.
530 * @param pub true for a public key operation, false for private.
531 * @param ml the message length, if known, false to disable padding.
532 *
533 * @return the decrypted message as a byte string.
534 */
535pki.rsa.decrypt = function(ed, key, pub, ml) {
536 // get the length of the modulus in bytes
537 var k = Math.ceil(key.n.bitLength() / 8);
538
539 // error if the length of the encrypted data ED is not k
540 if(ed.length !== k) {
541 var error = new Error('Encrypted message length is invalid.');
542 error.length = ed.length;
543 error.expected = k;
544 throw error;
545 }
546
547 // convert encrypted data into a big integer
548 // FIXME: hex conversion inefficient, get BigInteger w/byte strings
549 var y = new BigInteger(forge.util.createBuffer(ed).toHex(), 16);
550
551 // y must be less than the modulus or it wasn't the result of
552 // a previous mod operation (encryption) using that modulus
553 if(y.compareTo(key.n) >= 0) {
554 throw new Error('Encrypted message is invalid.');
555 }
556
557 // do RSA decryption
558 var x = _modPow(y, key, pub);
559
560 // create the encryption block, if x is shorter in bytes than k, then
561 // prepend zero bytes to fill up eb
562 // FIXME: hex conversion inefficient, get BigInteger w/byte strings
563 var xhex = x.toString(16);
564 var eb = forge.util.createBuffer();
565 var zeros = k - Math.ceil(xhex.length / 2);
566 while(zeros > 0) {
567 eb.putByte(0x00);
568 --zeros;
569 }
570 eb.putBytes(forge.util.hexToBytes(xhex));
571
572 if(ml !== false) {
573 // legacy, default to PKCS#1 v1.5 padding
574 return _decodePkcs1_v1_5(eb.getBytes(), key, pub);
575 }
576
577 // return message
578 return eb.getBytes();
579};
580
581/**
582 * Creates an RSA key-pair generation state object. It is used to allow
583 * key-generation to be performed in steps. It also allows for a UI to
584 * display progress updates.
585 *
586 * @param bits the size for the private key in bits, defaults to 2048.
587 * @param e the public exponent to use, defaults to 65537 (0x10001).
588 * @param [options] the options to use.
589 * prng a custom crypto-secure pseudo-random number generator to use,
590 * that must define "getBytesSync".
591 * algorithm the algorithm to use (default: 'PRIMEINC').
592 *
593 * @return the state object to use to generate the key-pair.
594 */
595pki.rsa.createKeyPairGenerationState = function(bits, e, options) {
596 // TODO: migrate step-based prime generation code to forge.prime
597
598 // set default bits
599 if(typeof(bits) === 'string') {
600 bits = parseInt(bits, 10);
601 }
602 bits = bits || 2048;
603
604 // create prng with api that matches BigInteger secure random
605 options = options || {};
606 var prng = options.prng || forge.random;
607 var rng = {
608 // x is an array to fill with bytes
609 nextBytes: function(x) {
610 var b = prng.getBytesSync(x.length);
611 for(var i = 0; i < x.length; ++i) {
612 x[i] = b.charCodeAt(i);
613 }
614 }
615 };
616
617 var algorithm = options.algorithm || 'PRIMEINC';
618
619 // create PRIMEINC algorithm state
620 var rval;
621 if(algorithm === 'PRIMEINC') {
622 rval = {
623 algorithm: algorithm,
624 state: 0,
625 bits: bits,
626 rng: rng,
627 eInt: e || 65537,
628 e: new BigInteger(null),
629 p: null,
630 q: null,
631 qBits: bits >> 1,
632 pBits: bits - (bits >> 1),
633 pqState: 0,
634 num: null,
635 keys: null
636 };
637 rval.e.fromInt(rval.eInt);
638 } else {
639 throw new Error('Invalid key generation algorithm: ' + algorithm);
640 }
641
642 return rval;
643};
644
645/**
646 * Attempts to runs the key-generation algorithm for at most n seconds
647 * (approximately) using the given state. When key-generation has completed,
648 * the keys will be stored in state.keys.
649 *
650 * To use this function to update a UI while generating a key or to prevent
651 * causing browser lockups/warnings, set "n" to a value other than 0. A
652 * simple pattern for generating a key and showing a progress indicator is:
653 *
654 * var state = pki.rsa.createKeyPairGenerationState(2048);
655 * var step = function() {
656 * // step key-generation, run algorithm for 100 ms, repeat
657 * if(!forge.pki.rsa.stepKeyPairGenerationState(state, 100)) {
658 * setTimeout(step, 1);
659 * } else {
660 * // key-generation complete
661 * // TODO: turn off progress indicator here
662 * // TODO: use the generated key-pair in "state.keys"
663 * }
664 * };
665 * // TODO: turn on progress indicator here
666 * setTimeout(step, 0);
667 *
668 * @param state the state to use.
669 * @param n the maximum number of milliseconds to run the algorithm for, 0
670 * to run the algorithm to completion.
671 *
672 * @return true if the key-generation completed, false if not.
673 */
674pki.rsa.stepKeyPairGenerationState = function(state, n) {
675 // set default algorithm if not set
676 if(!('algorithm' in state)) {
677 state.algorithm = 'PRIMEINC';
678 }
679
680 // TODO: migrate step-based prime generation code to forge.prime
681 // TODO: abstract as PRIMEINC algorithm
682
683 // do key generation (based on Tom Wu's rsa.js, see jsbn.js license)
684 // with some minor optimizations and designed to run in steps
685
686 // local state vars
687 var THIRTY = new BigInteger(null);
688 THIRTY.fromInt(30);
689 var deltaIdx = 0;
690 var op_or = function(x, y) {return x | y;};
691
692 // keep stepping until time limit is reached or done
693 var t1 = +new Date();
694 var t2;
695 var total = 0;
696 while(state.keys === null && (n <= 0 || total < n)) {
697 // generate p or q
698 if(state.state === 0) {
699 /* Note: All primes are of the form:
700
701 30k+i, for i < 30 and gcd(30, i)=1, where there are 8 values for i
702
703 When we generate a random number, we always align it at 30k + 1. Each
704 time the number is determined not to be prime we add to get to the
705 next 'i', eg: if the number was at 30k + 1 we add 6. */
706 var bits = (state.p === null) ? state.pBits : state.qBits;
707 var bits1 = bits - 1;
708
709 // get a random number
710 if(state.pqState === 0) {
711 state.num = new BigInteger(bits, state.rng);
712 // force MSB set
713 if(!state.num.testBit(bits1)) {
714 state.num.bitwiseTo(
715 BigInteger.ONE.shiftLeft(bits1), op_or, state.num);
716 }
717 // align number on 30k+1 boundary
718 state.num.dAddOffset(31 - state.num.mod(THIRTY).byteValue(), 0);
719 deltaIdx = 0;
720
721 ++state.pqState;
722 } else if(state.pqState === 1) {
723 // try to make the number a prime
724 if(state.num.bitLength() > bits) {
725 // overflow, try again
726 state.pqState = 0;
727 // do primality test
728 } else if(state.num.isProbablePrime(
729 _getMillerRabinTests(state.num.bitLength()))) {
730 ++state.pqState;
731 } else {
732 // get next potential prime
733 state.num.dAddOffset(GCD_30_DELTA[deltaIdx++ % 8], 0);
734 }
735 } else if(state.pqState === 2) {
736 // ensure number is coprime with e
737 state.pqState =
738 (state.num.subtract(BigInteger.ONE).gcd(state.e)
739 .compareTo(BigInteger.ONE) === 0) ? 3 : 0;
740 } else if(state.pqState === 3) {
741 // store p or q
742 state.pqState = 0;
743 if(state.p === null) {
744 state.p = state.num;
745 } else {
746 state.q = state.num;
747 }
748
749 // advance state if both p and q are ready
750 if(state.p !== null && state.q !== null) {
751 ++state.state;
752 }
753 state.num = null;
754 }
755 } else if(state.state === 1) {
756 // ensure p is larger than q (swap them if not)
757 if(state.p.compareTo(state.q) < 0) {
758 state.num = state.p;
759 state.p = state.q;
760 state.q = state.num;
761 }
762 ++state.state;
763 } else if(state.state === 2) {
764 // compute phi: (p - 1)(q - 1) (Euler's totient function)
765 state.p1 = state.p.subtract(BigInteger.ONE);
766 state.q1 = state.q.subtract(BigInteger.ONE);
767 state.phi = state.p1.multiply(state.q1);
768 ++state.state;
769 } else if(state.state === 3) {
770 // ensure e and phi are coprime
771 if(state.phi.gcd(state.e).compareTo(BigInteger.ONE) === 0) {
772 // phi and e are coprime, advance
773 ++state.state;
774 } else {
775 // phi and e aren't coprime, so generate a new p and q
776 state.p = null;
777 state.q = null;
778 state.state = 0;
779 }
780 } else if(state.state === 4) {
781 // create n, ensure n is has the right number of bits
782 state.n = state.p.multiply(state.q);
783
784 // ensure n is right number of bits
785 if(state.n.bitLength() === state.bits) {
786 // success, advance
787 ++state.state;
788 } else {
789 // failed, get new q
790 state.q = null;
791 state.state = 0;
792 }
793 } else if(state.state === 5) {
794 // set keys
795 var d = state.e.modInverse(state.phi);
796 state.keys = {
797 privateKey: pki.rsa.setPrivateKey(
798 state.n, state.e, d, state.p, state.q,
799 d.mod(state.p1), d.mod(state.q1),
800 state.q.modInverse(state.p)),
801 publicKey: pki.rsa.setPublicKey(state.n, state.e)
802 };
803 }
804
805 // update timing
806 t2 = +new Date();
807 total += t2 - t1;
808 t1 = t2;
809 }
810
811 return state.keys !== null;
812};
813
814/**
815 * Generates an RSA public-private key pair in a single call.
816 *
817 * To generate a key-pair in steps (to allow for progress updates and to
818 * prevent blocking or warnings in slow browsers) then use the key-pair
819 * generation state functions.
820 *
821 * To generate a key-pair asynchronously (either through web-workers, if
822 * available, or by breaking up the work on the main thread), pass a
823 * callback function.
824 *
825 * @param [bits] the size for the private key in bits, defaults to 2048.
826 * @param [e] the public exponent to use, defaults to 65537.
827 * @param [options] options for key-pair generation, if given then 'bits'
828 * and 'e' must *not* be given:
829 * bits the size for the private key in bits, (default: 2048).
830 * e the public exponent to use, (default: 65537 (0x10001)).
831 * workerScript the worker script URL.
832 * workers the number of web workers (if supported) to use,
833 * (default: 2).
834 * workLoad the size of the work load, ie: number of possible prime
835 * numbers for each web worker to check per work assignment,
836 * (default: 100).
837 * prng a custom crypto-secure pseudo-random number generator to use,
838 * that must define "getBytesSync". Disables use of native APIs.
839 * algorithm the algorithm to use (default: 'PRIMEINC').
840 * @param [callback(err, keypair)] called once the operation completes.
841 *
842 * @return an object with privateKey and publicKey properties.
843 */
844pki.rsa.generateKeyPair = function(bits, e, options, callback) {
845 // (bits), (options), (callback)
846 if(arguments.length === 1) {
847 if(typeof bits === 'object') {
848 options = bits;
849 bits = undefined;
850 } else if(typeof bits === 'function') {
851 callback = bits;
852 bits = undefined;
853 }
854 } else if(arguments.length === 2) {
855 // (bits, e), (bits, options), (bits, callback), (options, callback)
856 if(typeof bits === 'number') {
857 if(typeof e === 'function') {
858 callback = e;
859 e = undefined;
860 } else if(typeof e !== 'number') {
861 options = e;
862 e = undefined;
863 }
864 } else {
865 options = bits;
866 callback = e;
867 bits = undefined;
868 e = undefined;
869 }
870 } else if(arguments.length === 3) {
871 // (bits, e, options), (bits, e, callback), (bits, options, callback)
872 if(typeof e === 'number') {
873 if(typeof options === 'function') {
874 callback = options;
875 options = undefined;
876 }
877 } else {
878 callback = options;
879 options = e;
880 e = undefined;
881 }
882 }
883 options = options || {};
884 if(bits === undefined) {
885 bits = options.bits || 2048;
886 }
887 if(e === undefined) {
888 e = options.e || 0x10001;
889 }
890
891 // use native code if permitted, available, and parameters are acceptable
892 if(!forge.options.usePureJavaScript && !options.prng &&
893 bits >= 256 && bits <= 16384 && (e === 0x10001 || e === 3)) {
894 if(callback) {
895 // try native async
896 if(_detectNodeCrypto('generateKeyPair')) {
897 return _crypto.generateKeyPair('rsa', {
898 modulusLength: bits,
899 publicExponent: e,
900 publicKeyEncoding: {
901 type: 'spki',
902 format: 'pem'
903 },
904 privateKeyEncoding: {
905 type: 'pkcs8',
906 format: 'pem'
907 }
908 }, function(err, pub, priv) {
909 if(err) {
910 return callback(err);
911 }
912 callback(null, {
913 privateKey: pki.privateKeyFromPem(priv),
914 publicKey: pki.publicKeyFromPem(pub)
915 });
916 });
917 }
918 if(_detectSubtleCrypto('generateKey') &&
919 _detectSubtleCrypto('exportKey')) {
920 // use standard native generateKey
921 return util.globalScope.crypto.subtle.generateKey({
922 name: 'RSASSA-PKCS1-v1_5',
923 modulusLength: bits,
924 publicExponent: _intToUint8Array(e),
925 hash: {name: 'SHA-256'}
926 }, true /* key can be exported*/, ['sign', 'verify'])
927 .then(function(pair) {
928 return util.globalScope.crypto.subtle.exportKey(
929 'pkcs8', pair.privateKey);
930 // avoiding catch(function(err) {...}) to support IE <= 8
931 }).then(undefined, function(err) {
932 callback(err);
933 }).then(function(pkcs8) {
934 if(pkcs8) {
935 var privateKey = pki.privateKeyFromAsn1(
936 asn1.fromDer(forge.util.createBuffer(pkcs8)));
937 callback(null, {
938 privateKey: privateKey,
939 publicKey: pki.setRsaPublicKey(privateKey.n, privateKey.e)
940 });
941 }
942 });
943 }
944 if(_detectSubtleMsCrypto('generateKey') &&
945 _detectSubtleMsCrypto('exportKey')) {
946 var genOp = util.globalScope.msCrypto.subtle.generateKey({
947 name: 'RSASSA-PKCS1-v1_5',
948 modulusLength: bits,
949 publicExponent: _intToUint8Array(e),
950 hash: {name: 'SHA-256'}
951 }, true /* key can be exported*/, ['sign', 'verify']);
952 genOp.oncomplete = function(e) {
953 var pair = e.target.result;
954 var exportOp = util.globalScope.msCrypto.subtle.exportKey(
955 'pkcs8', pair.privateKey);
956 exportOp.oncomplete = function(e) {
957 var pkcs8 = e.target.result;
958 var privateKey = pki.privateKeyFromAsn1(
959 asn1.fromDer(forge.util.createBuffer(pkcs8)));
960 callback(null, {
961 privateKey: privateKey,
962 publicKey: pki.setRsaPublicKey(privateKey.n, privateKey.e)
963 });
964 };
965 exportOp.onerror = function(err) {
966 callback(err);
967 };
968 };
969 genOp.onerror = function(err) {
970 callback(err);
971 };
972 return;
973 }
974 } else {
975 // try native sync
976 if(_detectNodeCrypto('generateKeyPairSync')) {
977 var keypair = _crypto.generateKeyPairSync('rsa', {
978 modulusLength: bits,
979 publicExponent: e,
980 publicKeyEncoding: {
981 type: 'spki',
982 format: 'pem'
983 },
984 privateKeyEncoding: {
985 type: 'pkcs8',
986 format: 'pem'
987 }
988 });
989 return {
990 privateKey: pki.privateKeyFromPem(keypair.privateKey),
991 publicKey: pki.publicKeyFromPem(keypair.publicKey)
992 };
993 }
994 }
995 }
996
997 // use JavaScript implementation
998 var state = pki.rsa.createKeyPairGenerationState(bits, e, options);
999 if(!callback) {
1000 pki.rsa.stepKeyPairGenerationState(state, 0);
1001 return state.keys;
1002 }
1003 _generateKeyPair(state, options, callback);
1004};
1005
1006/**
1007 * Sets an RSA public key from BigIntegers modulus and exponent.
1008 *
1009 * @param n the modulus.
1010 * @param e the exponent.
1011 *
1012 * @return the public key.
1013 */
1014pki.setRsaPublicKey = pki.rsa.setPublicKey = function(n, e) {
1015 var key = {
1016 n: n,
1017 e: e
1018 };
1019
1020 /**
1021 * Encrypts the given data with this public key. Newer applications
1022 * should use the 'RSA-OAEP' decryption scheme, 'RSAES-PKCS1-V1_5' is for
1023 * legacy applications.
1024 *
1025 * @param data the byte string to encrypt.
1026 * @param scheme the encryption scheme to use:
1027 * 'RSAES-PKCS1-V1_5' (default),
1028 * 'RSA-OAEP',
1029 * 'RAW', 'NONE', or null to perform raw RSA encryption,
1030 * an object with an 'encode' property set to a function
1031 * with the signature 'function(data, key)' that returns
1032 * a binary-encoded string representing the encoded data.
1033 * @param schemeOptions any scheme-specific options.
1034 *
1035 * @return the encrypted byte string.
1036 */
1037 key.encrypt = function(data, scheme, schemeOptions) {
1038 if(typeof scheme === 'string') {
1039 scheme = scheme.toUpperCase();
1040 } else if(scheme === undefined) {
1041 scheme = 'RSAES-PKCS1-V1_5';
1042 }
1043
1044 if(scheme === 'RSAES-PKCS1-V1_5') {
1045 scheme = {
1046 encode: function(m, key, pub) {
1047 return _encodePkcs1_v1_5(m, key, 0x02).getBytes();
1048 }
1049 };
1050 } else if(scheme === 'RSA-OAEP' || scheme === 'RSAES-OAEP') {
1051 scheme = {
1052 encode: function(m, key) {
1053 return forge.pkcs1.encode_rsa_oaep(key, m, schemeOptions);
1054 }
1055 };
1056 } else if(['RAW', 'NONE', 'NULL', null].indexOf(scheme) !== -1) {
1057 scheme = {encode: function(e) {return e;}};
1058 } else if(typeof scheme === 'string') {
1059 throw new Error('Unsupported encryption scheme: "' + scheme + '".');
1060 }
1061
1062 // do scheme-based encoding then rsa encryption
1063 var e = scheme.encode(data, key, true);
1064 return pki.rsa.encrypt(e, key, true);
1065 };
1066
1067 /**
1068 * Verifies the given signature against the given digest.
1069 *
1070 * PKCS#1 supports multiple (currently two) signature schemes:
1071 * RSASSA-PKCS1-V1_5 and RSASSA-PSS.
1072 *
1073 * By default this implementation uses the "old scheme", i.e.
1074 * RSASSA-PKCS1-V1_5, in which case once RSA-decrypted, the
1075 * signature is an OCTET STRING that holds a DigestInfo.
1076 *
1077 * DigestInfo ::= SEQUENCE {
1078 * digestAlgorithm DigestAlgorithmIdentifier,
1079 * digest Digest
1080 * }
1081 * DigestAlgorithmIdentifier ::= AlgorithmIdentifier
1082 * Digest ::= OCTET STRING
1083 *
1084 * To perform PSS signature verification, provide an instance
1085 * of Forge PSS object as the scheme parameter.
1086 *
1087 * @param digest the message digest hash to compare against the signature,
1088 * as a binary-encoded string.
1089 * @param signature the signature to verify, as a binary-encoded string.
1090 * @param scheme signature verification scheme to use:
1091 * 'RSASSA-PKCS1-V1_5' or undefined for RSASSA PKCS#1 v1.5,
1092 * a Forge PSS object for RSASSA-PSS,
1093 * 'NONE' or null for none, DigestInfo will not be expected, but
1094 * PKCS#1 v1.5 padding will still be used.
1095 *
1096 * @return true if the signature was verified, false if not.
1097 */
1098 key.verify = function(digest, signature, scheme) {
1099 if(typeof scheme === 'string') {
1100 scheme = scheme.toUpperCase();
1101 } else if(scheme === undefined) {
1102 scheme = 'RSASSA-PKCS1-V1_5';
1103 }
1104
1105 if(scheme === 'RSASSA-PKCS1-V1_5') {
1106 scheme = {
1107 verify: function(digest, d) {
1108 // remove padding
1109 d = _decodePkcs1_v1_5(d, key, true);
1110 // d is ASN.1 BER-encoded DigestInfo
1111 var obj = asn1.fromDer(d);
1112 // compare the given digest to the decrypted one
1113 return digest === obj.value[1].value;
1114 }
1115 };
1116 } else if(scheme === 'NONE' || scheme === 'NULL' || scheme === null) {
1117 scheme = {
1118 verify: function(digest, d) {
1119 // remove padding
1120 d = _decodePkcs1_v1_5(d, key, true);
1121 return digest === d;
1122 }
1123 };
1124 }
1125
1126 // do rsa decryption w/o any decoding, then verify -- which does decoding
1127 var d = pki.rsa.decrypt(signature, key, true, false);
1128 return scheme.verify(digest, d, key.n.bitLength());
1129 };
1130
1131 return key;
1132};
1133
1134/**
1135 * Sets an RSA private key from BigIntegers modulus, exponent, primes,
1136 * prime exponents, and modular multiplicative inverse.
1137 *
1138 * @param n the modulus.
1139 * @param e the public exponent.
1140 * @param d the private exponent ((inverse of e) mod n).
1141 * @param p the first prime.
1142 * @param q the second prime.
1143 * @param dP exponent1 (d mod (p-1)).
1144 * @param dQ exponent2 (d mod (q-1)).
1145 * @param qInv ((inverse of q) mod p)
1146 *
1147 * @return the private key.
1148 */
1149pki.setRsaPrivateKey = pki.rsa.setPrivateKey = function(
1150 n, e, d, p, q, dP, dQ, qInv) {
1151 var key = {
1152 n: n,
1153 e: e,
1154 d: d,
1155 p: p,
1156 q: q,
1157 dP: dP,
1158 dQ: dQ,
1159 qInv: qInv
1160 };
1161
1162 /**
1163 * Decrypts the given data with this private key. The decryption scheme
1164 * must match the one used to encrypt the data.
1165 *
1166 * @param data the byte string to decrypt.
1167 * @param scheme the decryption scheme to use:
1168 * 'RSAES-PKCS1-V1_5' (default),
1169 * 'RSA-OAEP',
1170 * 'RAW', 'NONE', or null to perform raw RSA decryption.
1171 * @param schemeOptions any scheme-specific options.
1172 *
1173 * @return the decrypted byte string.
1174 */
1175 key.decrypt = function(data, scheme, schemeOptions) {
1176 if(typeof scheme === 'string') {
1177 scheme = scheme.toUpperCase();
1178 } else if(scheme === undefined) {
1179 scheme = 'RSAES-PKCS1-V1_5';
1180 }
1181
1182 // do rsa decryption w/o any decoding
1183 var d = pki.rsa.decrypt(data, key, false, false);
1184
1185 if(scheme === 'RSAES-PKCS1-V1_5') {
1186 scheme = {decode: _decodePkcs1_v1_5};
1187 } else if(scheme === 'RSA-OAEP' || scheme === 'RSAES-OAEP') {
1188 scheme = {
1189 decode: function(d, key) {
1190 return forge.pkcs1.decode_rsa_oaep(key, d, schemeOptions);
1191 }
1192 };
1193 } else if(['RAW', 'NONE', 'NULL', null].indexOf(scheme) !== -1) {
1194 scheme = {decode: function(d) {return d;}};
1195 } else {
1196 throw new Error('Unsupported encryption scheme: "' + scheme + '".');
1197 }
1198
1199 // decode according to scheme
1200 return scheme.decode(d, key, false);
1201 };
1202
1203 /**
1204 * Signs the given digest, producing a signature.
1205 *
1206 * PKCS#1 supports multiple (currently two) signature schemes:
1207 * RSASSA-PKCS1-V1_5 and RSASSA-PSS.
1208 *
1209 * By default this implementation uses the "old scheme", i.e.
1210 * RSASSA-PKCS1-V1_5. In order to generate a PSS signature, provide
1211 * an instance of Forge PSS object as the scheme parameter.
1212 *
1213 * @param md the message digest object with the hash to sign.
1214 * @param scheme the signature scheme to use:
1215 * 'RSASSA-PKCS1-V1_5' or undefined for RSASSA PKCS#1 v1.5,
1216 * a Forge PSS object for RSASSA-PSS,
1217 * 'NONE' or null for none, DigestInfo will not be used but
1218 * PKCS#1 v1.5 padding will still be used.
1219 *
1220 * @return the signature as a byte string.
1221 */
1222 key.sign = function(md, scheme) {
1223 /* Note: The internal implementation of RSA operations is being
1224 transitioned away from a PKCS#1 v1.5 hard-coded scheme. Some legacy
1225 code like the use of an encoding block identifier 'bt' will eventually
1226 be removed. */
1227
1228 // private key operation
1229 var bt = false;
1230
1231 if(typeof scheme === 'string') {
1232 scheme = scheme.toUpperCase();
1233 }
1234
1235 if(scheme === undefined || scheme === 'RSASSA-PKCS1-V1_5') {
1236 scheme = {encode: emsaPkcs1v15encode};
1237 bt = 0x01;
1238 } else if(scheme === 'NONE' || scheme === 'NULL' || scheme === null) {
1239 scheme = {encode: function() {return md;}};
1240 bt = 0x01;
1241 }
1242
1243 // encode and then encrypt
1244 var d = scheme.encode(md, key.n.bitLength());
1245 return pki.rsa.encrypt(d, key, bt);
1246 };
1247
1248 return key;
1249};
1250
1251/**
1252 * Wraps an RSAPrivateKey ASN.1 object in an ASN.1 PrivateKeyInfo object.
1253 *
1254 * @param rsaKey the ASN.1 RSAPrivateKey.
1255 *
1256 * @return the ASN.1 PrivateKeyInfo.
1257 */
1258pki.wrapRsaPrivateKey = function(rsaKey) {
1259 // PrivateKeyInfo
1260 return asn1.create(asn1.Class.UNIVERSAL, asn1.Type.SEQUENCE, true, [
1261 // version (0)
1262 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1263 asn1.integerToDer(0).getBytes()),
1264 // privateKeyAlgorithm
1265 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.SEQUENCE, true, [
1266 asn1.create(
1267 asn1.Class.UNIVERSAL, asn1.Type.OID, false,
1268 asn1.oidToDer(pki.oids.rsaEncryption).getBytes()),
1269 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.NULL, false, '')
1270 ]),
1271 // PrivateKey
1272 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.OCTETSTRING, false,
1273 asn1.toDer(rsaKey).getBytes())
1274 ]);
1275};
1276
1277/**
1278 * Converts a private key from an ASN.1 object.
1279 *
1280 * @param obj the ASN.1 representation of a PrivateKeyInfo containing an
1281 * RSAPrivateKey or an RSAPrivateKey.
1282 *
1283 * @return the private key.
1284 */
1285pki.privateKeyFromAsn1 = function(obj) {
1286 // get PrivateKeyInfo
1287 var capture = {};
1288 var errors = [];
1289 if(asn1.validate(obj, privateKeyValidator, capture, errors)) {
1290 obj = asn1.fromDer(forge.util.createBuffer(capture.privateKey));
1291 }
1292
1293 // get RSAPrivateKey
1294 capture = {};
1295 errors = [];
1296 if(!asn1.validate(obj, rsaPrivateKeyValidator, capture, errors)) {
1297 var error = new Error('Cannot read private key. ' +
1298 'ASN.1 object does not contain an RSAPrivateKey.');
1299 error.errors = errors;
1300 throw error;
1301 }
1302
1303 // Note: Version is currently ignored.
1304 // capture.privateKeyVersion
1305 // FIXME: inefficient, get a BigInteger that uses byte strings
1306 var n, e, d, p, q, dP, dQ, qInv;
1307 n = forge.util.createBuffer(capture.privateKeyModulus).toHex();
1308 e = forge.util.createBuffer(capture.privateKeyPublicExponent).toHex();
1309 d = forge.util.createBuffer(capture.privateKeyPrivateExponent).toHex();
1310 p = forge.util.createBuffer(capture.privateKeyPrime1).toHex();
1311 q = forge.util.createBuffer(capture.privateKeyPrime2).toHex();
1312 dP = forge.util.createBuffer(capture.privateKeyExponent1).toHex();
1313 dQ = forge.util.createBuffer(capture.privateKeyExponent2).toHex();
1314 qInv = forge.util.createBuffer(capture.privateKeyCoefficient).toHex();
1315
1316 // set private key
1317 return pki.setRsaPrivateKey(
1318 new BigInteger(n, 16),
1319 new BigInteger(e, 16),
1320 new BigInteger(d, 16),
1321 new BigInteger(p, 16),
1322 new BigInteger(q, 16),
1323 new BigInteger(dP, 16),
1324 new BigInteger(dQ, 16),
1325 new BigInteger(qInv, 16));
1326};
1327
1328/**
1329 * Converts a private key to an ASN.1 RSAPrivateKey.
1330 *
1331 * @param key the private key.
1332 *
1333 * @return the ASN.1 representation of an RSAPrivateKey.
1334 */
1335pki.privateKeyToAsn1 = pki.privateKeyToRSAPrivateKey = function(key) {
1336 // RSAPrivateKey
1337 return asn1.create(asn1.Class.UNIVERSAL, asn1.Type.SEQUENCE, true, [
1338 // version (0 = only 2 primes, 1 multiple primes)
1339 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1340 asn1.integerToDer(0).getBytes()),
1341 // modulus (n)
1342 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1343 _bnToBytes(key.n)),
1344 // publicExponent (e)
1345 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1346 _bnToBytes(key.e)),
1347 // privateExponent (d)
1348 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1349 _bnToBytes(key.d)),
1350 // privateKeyPrime1 (p)
1351 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1352 _bnToBytes(key.p)),
1353 // privateKeyPrime2 (q)
1354 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1355 _bnToBytes(key.q)),
1356 // privateKeyExponent1 (dP)
1357 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1358 _bnToBytes(key.dP)),
1359 // privateKeyExponent2 (dQ)
1360 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1361 _bnToBytes(key.dQ)),
1362 // coefficient (qInv)
1363 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1364 _bnToBytes(key.qInv))
1365 ]);
1366};
1367
1368/**
1369 * Converts a public key from an ASN.1 SubjectPublicKeyInfo or RSAPublicKey.
1370 *
1371 * @param obj the asn1 representation of a SubjectPublicKeyInfo or RSAPublicKey.
1372 *
1373 * @return the public key.
1374 */
1375pki.publicKeyFromAsn1 = function(obj) {
1376 // get SubjectPublicKeyInfo
1377 var capture = {};
1378 var errors = [];
1379 if(asn1.validate(obj, publicKeyValidator, capture, errors)) {
1380 // get oid
1381 var oid = asn1.derToOid(capture.publicKeyOid);
1382 if(oid !== pki.oids.rsaEncryption) {
1383 var error = new Error('Cannot read public key. Unknown OID.');
1384 error.oid = oid;
1385 throw error;
1386 }
1387 obj = capture.rsaPublicKey;
1388 }
1389
1390 // get RSA params
1391 errors = [];
1392 if(!asn1.validate(obj, rsaPublicKeyValidator, capture, errors)) {
1393 var error = new Error('Cannot read public key. ' +
1394 'ASN.1 object does not contain an RSAPublicKey.');
1395 error.errors = errors;
1396 throw error;
1397 }
1398
1399 // FIXME: inefficient, get a BigInteger that uses byte strings
1400 var n = forge.util.createBuffer(capture.publicKeyModulus).toHex();
1401 var e = forge.util.createBuffer(capture.publicKeyExponent).toHex();
1402
1403 // set public key
1404 return pki.setRsaPublicKey(
1405 new BigInteger(n, 16),
1406 new BigInteger(e, 16));
1407};
1408
1409/**
1410 * Converts a public key to an ASN.1 SubjectPublicKeyInfo.
1411 *
1412 * @param key the public key.
1413 *
1414 * @return the asn1 representation of a SubjectPublicKeyInfo.
1415 */
1416pki.publicKeyToAsn1 = pki.publicKeyToSubjectPublicKeyInfo = function(key) {
1417 // SubjectPublicKeyInfo
1418 return asn1.create(asn1.Class.UNIVERSAL, asn1.Type.SEQUENCE, true, [
1419 // AlgorithmIdentifier
1420 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.SEQUENCE, true, [
1421 // algorithm
1422 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.OID, false,
1423 asn1.oidToDer(pki.oids.rsaEncryption).getBytes()),
1424 // parameters (null)
1425 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.NULL, false, '')
1426 ]),
1427 // subjectPublicKey
1428 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.BITSTRING, false, [
1429 pki.publicKeyToRSAPublicKey(key)
1430 ])
1431 ]);
1432};
1433
1434/**
1435 * Converts a public key to an ASN.1 RSAPublicKey.
1436 *
1437 * @param key the public key.
1438 *
1439 * @return the asn1 representation of a RSAPublicKey.
1440 */
1441pki.publicKeyToRSAPublicKey = function(key) {
1442 // RSAPublicKey
1443 return asn1.create(asn1.Class.UNIVERSAL, asn1.Type.SEQUENCE, true, [
1444 // modulus (n)
1445 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1446 _bnToBytes(key.n)),
1447 // publicExponent (e)
1448 asn1.create(asn1.Class.UNIVERSAL, asn1.Type.INTEGER, false,
1449 _bnToBytes(key.e))
1450 ]);
1451};
1452
1453/**
1454 * Encodes a message using PKCS#1 v1.5 padding.
1455 *
1456 * @param m the message to encode.
1457 * @param key the RSA key to use.
1458 * @param bt the block type to use, i.e. either 0x01 (for signing) or 0x02
1459 * (for encryption).
1460 *
1461 * @return the padded byte buffer.
1462 */
1463function _encodePkcs1_v1_5(m, key, bt) {
1464 var eb = forge.util.createBuffer();
1465
1466 // get the length of the modulus in bytes
1467 var k = Math.ceil(key.n.bitLength() / 8);
1468
1469 /* use PKCS#1 v1.5 padding */
1470 if(m.length > (k - 11)) {
1471 var error = new Error('Message is too long for PKCS#1 v1.5 padding.');
1472 error.length = m.length;
1473 error.max = k - 11;
1474 throw error;
1475 }
1476
1477 /* A block type BT, a padding string PS, and the data D shall be
1478 formatted into an octet string EB, the encryption block:
1479
1480 EB = 00 || BT || PS || 00 || D
1481
1482 The block type BT shall be a single octet indicating the structure of
1483 the encryption block. For this version of the document it shall have
1484 value 00, 01, or 02. For a private-key operation, the block type
1485 shall be 00 or 01. For a public-key operation, it shall be 02.
1486
1487 The padding string PS shall consist of k-3-||D|| octets. For block
1488 type 00, the octets shall have value 00; for block type 01, they
1489 shall have value FF; and for block type 02, they shall be
1490 pseudorandomly generated and nonzero. This makes the length of the
1491 encryption block EB equal to k. */
1492
1493 // build the encryption block
1494 eb.putByte(0x00);
1495 eb.putByte(bt);
1496
1497 // create the padding
1498 var padNum = k - 3 - m.length;
1499 var padByte;
1500 // private key op
1501 if(bt === 0x00 || bt === 0x01) {
1502 padByte = (bt === 0x00) ? 0x00 : 0xFF;
1503 for(var i = 0; i < padNum; ++i) {
1504 eb.putByte(padByte);
1505 }
1506 } else {
1507 // public key op
1508 // pad with random non-zero values
1509 while(padNum > 0) {
1510 var numZeros = 0;
1511 var padBytes = forge.random.getBytes(padNum);
1512 for(var i = 0; i < padNum; ++i) {
1513 padByte = padBytes.charCodeAt(i);
1514 if(padByte === 0) {
1515 ++numZeros;
1516 } else {
1517 eb.putByte(padByte);
1518 }
1519 }
1520 padNum = numZeros;
1521 }
1522 }
1523
1524 // zero followed by message
1525 eb.putByte(0x00);
1526 eb.putBytes(m);
1527
1528 return eb;
1529}
1530
1531/**
1532 * Decodes a message using PKCS#1 v1.5 padding.
1533 *
1534 * @param em the message to decode.
1535 * @param key the RSA key to use.
1536 * @param pub true if the key is a public key, false if it is private.
1537 * @param ml the message length, if specified.
1538 *
1539 * @return the decoded bytes.
1540 */
1541function _decodePkcs1_v1_5(em, key, pub, ml) {
1542 // get the length of the modulus in bytes
1543 var k = Math.ceil(key.n.bitLength() / 8);
1544
1545 /* It is an error if any of the following conditions occurs:
1546
1547 1. The encryption block EB cannot be parsed unambiguously.
1548 2. The padding string PS consists of fewer than eight octets
1549 or is inconsisent with the block type BT.
1550 3. The decryption process is a public-key operation and the block
1551 type BT is not 00 or 01, or the decryption process is a
1552 private-key operation and the block type is not 02.
1553 */
1554
1555 // parse the encryption block
1556 var eb = forge.util.createBuffer(em);
1557 var first = eb.getByte();
1558 var bt = eb.getByte();
1559 if(first !== 0x00 ||
1560 (pub && bt !== 0x00 && bt !== 0x01) ||
1561 (!pub && bt != 0x02) ||
1562 (pub && bt === 0x00 && typeof(ml) === 'undefined')) {
1563 throw new Error('Encryption block is invalid.');
1564 }
1565
1566 var padNum = 0;
1567 if(bt === 0x00) {
1568 // check all padding bytes for 0x00
1569 padNum = k - 3 - ml;
1570 for(var i = 0; i < padNum; ++i) {
1571 if(eb.getByte() !== 0x00) {
1572 throw new Error('Encryption block is invalid.');
1573 }
1574 }
1575 } else if(bt === 0x01) {
1576 // find the first byte that isn't 0xFF, should be after all padding
1577 padNum = 0;
1578 while(eb.length() > 1) {
1579 if(eb.getByte() !== 0xFF) {
1580 --eb.read;
1581 break;
1582 }
1583 ++padNum;
1584 }
1585 } else if(bt === 0x02) {
1586 // look for 0x00 byte
1587 padNum = 0;
1588 while(eb.length() > 1) {
1589 if(eb.getByte() === 0x00) {
1590 --eb.read;
1591 break;
1592 }
1593 ++padNum;
1594 }
1595 }
1596
1597 // zero must be 0x00 and padNum must be (k - 3 - message length)
1598 var zero = eb.getByte();
1599 if(zero !== 0x00 || padNum !== (k - 3 - eb.length())) {
1600 throw new Error('Encryption block is invalid.');
1601 }
1602
1603 return eb.getBytes();
1604}
1605
1606/**
1607 * Runs the key-generation algorithm asynchronously, either in the background
1608 * via Web Workers, or using the main thread and setImmediate.
1609 *
1610 * @param state the key-pair generation state.
1611 * @param [options] options for key-pair generation:
1612 * workerScript the worker script URL.
1613 * workers the number of web workers (if supported) to use,
1614 * (default: 2, -1 to use estimated cores minus one).
1615 * workLoad the size of the work load, ie: number of possible prime
1616 * numbers for each web worker to check per work assignment,
1617 * (default: 100).
1618 * @param callback(err, keypair) called once the operation completes.
1619 */
1620function _generateKeyPair(state, options, callback) {
1621 if(typeof options === 'function') {
1622 callback = options;
1623 options = {};
1624 }
1625 options = options || {};
1626
1627 var opts = {
1628 algorithm: {
1629 name: options.algorithm || 'PRIMEINC',
1630 options: {
1631 workers: options.workers || 2,
1632 workLoad: options.workLoad || 100,
1633 workerScript: options.workerScript
1634 }
1635 }
1636 };
1637 if('prng' in options) {
1638 opts.prng = options.prng;
1639 }
1640
1641 generate();
1642
1643 function generate() {
1644 // find p and then q (done in series to simplify)
1645 getPrime(state.pBits, function(err, num) {
1646 if(err) {
1647 return callback(err);
1648 }
1649 state.p = num;
1650 if(state.q !== null) {
1651 return finish(err, state.q);
1652 }
1653 getPrime(state.qBits, finish);
1654 });
1655 }
1656
1657 function getPrime(bits, callback) {
1658 forge.prime.generateProbablePrime(bits, opts, callback);
1659 }
1660
1661 function finish(err, num) {
1662 if(err) {
1663 return callback(err);
1664 }
1665
1666 // set q
1667 state.q = num;
1668
1669 // ensure p is larger than q (swap them if not)
1670 if(state.p.compareTo(state.q) < 0) {
1671 var tmp = state.p;
1672 state.p = state.q;
1673 state.q = tmp;
1674 }
1675
1676 // ensure p is coprime with e
1677 if(state.p.subtract(BigInteger.ONE).gcd(state.e)
1678 .compareTo(BigInteger.ONE) !== 0) {
1679 state.p = null;
1680 generate();
1681 return;
1682 }
1683
1684 // ensure q is coprime with e
1685 if(state.q.subtract(BigInteger.ONE).gcd(state.e)
1686 .compareTo(BigInteger.ONE) !== 0) {
1687 state.q = null;
1688 getPrime(state.qBits, finish);
1689 return;
1690 }
1691
1692 // compute phi: (p - 1)(q - 1) (Euler's totient function)
1693 state.p1 = state.p.subtract(BigInteger.ONE);
1694 state.q1 = state.q.subtract(BigInteger.ONE);
1695 state.phi = state.p1.multiply(state.q1);
1696
1697 // ensure e and phi are coprime
1698 if(state.phi.gcd(state.e).compareTo(BigInteger.ONE) !== 0) {
1699 // phi and e aren't coprime, so generate a new p and q
1700 state.p = state.q = null;
1701 generate();
1702 return;
1703 }
1704
1705 // create n, ensure n is has the right number of bits
1706 state.n = state.p.multiply(state.q);
1707 if(state.n.bitLength() !== state.bits) {
1708 // failed, get new q
1709 state.q = null;
1710 getPrime(state.qBits, finish);
1711 return;
1712 }
1713
1714 // set keys
1715 var d = state.e.modInverse(state.phi);
1716 state.keys = {
1717 privateKey: pki.rsa.setPrivateKey(
1718 state.n, state.e, d, state.p, state.q,
1719 d.mod(state.p1), d.mod(state.q1),
1720 state.q.modInverse(state.p)),
1721 publicKey: pki.rsa.setPublicKey(state.n, state.e)
1722 };
1723
1724 callback(null, state.keys);
1725 }
1726}
1727
1728/**
1729 * Converts a positive BigInteger into 2's-complement big-endian bytes.
1730 *
1731 * @param b the big integer to convert.
1732 *
1733 * @return the bytes.
1734 */
1735function _bnToBytes(b) {
1736 // prepend 0x00 if first byte >= 0x80
1737 var hex = b.toString(16);
1738 if(hex[0] >= '8') {
1739 hex = '00' + hex;
1740 }
1741 var bytes = forge.util.hexToBytes(hex);
1742
1743 // ensure integer is minimally-encoded
1744 if(bytes.length > 1 &&
1745 // leading 0x00 for positive integer
1746 ((bytes.charCodeAt(0) === 0 &&
1747 (bytes.charCodeAt(1) & 0x80) === 0) ||
1748 // leading 0xFF for negative integer
1749 (bytes.charCodeAt(0) === 0xFF &&
1750 (bytes.charCodeAt(1) & 0x80) === 0x80))) {
1751 return bytes.substr(1);
1752 }
1753 return bytes;
1754}
1755
1756/**
1757 * Returns the required number of Miller-Rabin tests to generate a
1758 * prime with an error probability of (1/2)^80.
1759 *
1760 * See Handbook of Applied Cryptography Chapter 4, Table 4.4.
1761 *
1762 * @param bits the bit size.
1763 *
1764 * @return the required number of iterations.
1765 */
1766function _getMillerRabinTests(bits) {
1767 if(bits <= 100) return 27;
1768 if(bits <= 150) return 18;
1769 if(bits <= 200) return 15;
1770 if(bits <= 250) return 12;
1771 if(bits <= 300) return 9;
1772 if(bits <= 350) return 8;
1773 if(bits <= 400) return 7;
1774 if(bits <= 500) return 6;
1775 if(bits <= 600) return 5;
1776 if(bits <= 800) return 4;
1777 if(bits <= 1250) return 3;
1778 return 2;
1779}
1780
1781/**
1782 * Performs feature detection on the Node crypto interface.
1783 *
1784 * @param fn the feature (function) to detect.
1785 *
1786 * @return true if detected, false if not.
1787 */
1788function _detectNodeCrypto(fn) {
1789 return forge.util.isNodejs && typeof _crypto[fn] === 'function';
1790}
1791
1792/**
1793 * Performs feature detection on the SubtleCrypto interface.
1794 *
1795 * @param fn the feature (function) to detect.
1796 *
1797 * @return true if detected, false if not.
1798 */
1799function _detectSubtleCrypto(fn) {
1800 return (typeof util.globalScope !== 'undefined' &&
1801 typeof util.globalScope.crypto === 'object' &&
1802 typeof util.globalScope.crypto.subtle === 'object' &&
1803 typeof util.globalScope.crypto.subtle[fn] === 'function');
1804}
1805
1806/**
1807 * Performs feature detection on the deprecated Microsoft Internet Explorer
1808 * outdated SubtleCrypto interface. This function should only be used after
1809 * checking for the modern, standard SubtleCrypto interface.
1810 *
1811 * @param fn the feature (function) to detect.
1812 *
1813 * @return true if detected, false if not.
1814 */
1815function _detectSubtleMsCrypto(fn) {
1816 return (typeof util.globalScope !== 'undefined' &&
1817 typeof util.globalScope.msCrypto === 'object' &&
1818 typeof util.globalScope.msCrypto.subtle === 'object' &&
1819 typeof util.globalScope.msCrypto.subtle[fn] === 'function');
1820}
1821
1822function _intToUint8Array(x) {
1823 var bytes = forge.util.hexToBytes(x.toString(16));
1824 var buffer = new Uint8Array(bytes.length);
1825 for(var i = 0; i < bytes.length; ++i) {
1826 buffer[i] = bytes.charCodeAt(i);
1827 }
1828 return buffer;
1829}
1830
1831function _privateKeyFromJwk(jwk) {
1832 if(jwk.kty !== 'RSA') {
1833 throw new Error(
1834 'Unsupported key algorithm "' + jwk.kty + '"; algorithm must be "RSA".');
1835 }
1836 return pki.setRsaPrivateKey(
1837 _base64ToBigInt(jwk.n),
1838 _base64ToBigInt(jwk.e),
1839 _base64ToBigInt(jwk.d),
1840 _base64ToBigInt(jwk.p),
1841 _base64ToBigInt(jwk.q),
1842 _base64ToBigInt(jwk.dp),
1843 _base64ToBigInt(jwk.dq),
1844 _base64ToBigInt(jwk.qi));
1845}
1846
1847function _publicKeyFromJwk(jwk) {
1848 if(jwk.kty !== 'RSA') {
1849 throw new Error('Key algorithm must be "RSA".');
1850 }
1851 return pki.setRsaPublicKey(
1852 _base64ToBigInt(jwk.n),
1853 _base64ToBigInt(jwk.e));
1854}
1855
1856function _base64ToBigInt(b64) {
1857 return new BigInteger(forge.util.bytesToHex(forge.util.decode64(b64)), 16);
1858}
Note: See TracBrowser for help on using the repository browser.