source: trip-planner-front/node_modules/node-forge/lib/prime.js@ 1ad8e64

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

initial commit

  • Property mode set to 100644
File size: 8.6 KB
Line 
1/**
2 * Prime number generation API.
3 *
4 * @author Dave Longley
5 *
6 * Copyright (c) 2014 Digital Bazaar, Inc.
7 */
8var forge = require('./forge');
9require('./util');
10require('./jsbn');
11require('./random');
12
13(function() {
14
15// forge.prime already defined
16if(forge.prime) {
17 module.exports = forge.prime;
18 return;
19}
20
21/* PRIME API */
22var prime = module.exports = forge.prime = forge.prime || {};
23
24var BigInteger = forge.jsbn.BigInteger;
25
26// primes are 30k+i for i = 1, 7, 11, 13, 17, 19, 23, 29
27var GCD_30_DELTA = [6, 4, 2, 4, 2, 4, 6, 2];
28var THIRTY = new BigInteger(null);
29THIRTY.fromInt(30);
30var op_or = function(x, y) {return x|y;};
31
32/**
33 * Generates a random probable prime with the given number of bits.
34 *
35 * Alternative algorithms can be specified by name as a string or as an
36 * object with custom options like so:
37 *
38 * {
39 * name: 'PRIMEINC',
40 * options: {
41 * maxBlockTime: <the maximum amount of time to block the main
42 * thread before allowing I/O other JS to run>,
43 * millerRabinTests: <the number of miller-rabin tests to run>,
44 * workerScript: <the worker script URL>,
45 * workers: <the number of web workers (if supported) to use,
46 * -1 to use estimated cores minus one>.
47 * workLoad: the size of the work load, ie: number of possible prime
48 * numbers for each web worker to check per work assignment,
49 * (default: 100).
50 * }
51 * }
52 *
53 * @param bits the number of bits for the prime number.
54 * @param options the options to use.
55 * [algorithm] the algorithm to use (default: 'PRIMEINC').
56 * [prng] a custom crypto-secure pseudo-random number generator to use,
57 * that must define "getBytesSync".
58 *
59 * @return callback(err, num) called once the operation completes.
60 */
61prime.generateProbablePrime = function(bits, options, callback) {
62 if(typeof options === 'function') {
63 callback = options;
64 options = {};
65 }
66 options = options || {};
67
68 // default to PRIMEINC algorithm
69 var algorithm = options.algorithm || 'PRIMEINC';
70 if(typeof algorithm === 'string') {
71 algorithm = {name: algorithm};
72 }
73 algorithm.options = algorithm.options || {};
74
75 // create prng with api that matches BigInteger secure random
76 var prng = options.prng || forge.random;
77 var rng = {
78 // x is an array to fill with bytes
79 nextBytes: function(x) {
80 var b = prng.getBytesSync(x.length);
81 for(var i = 0; i < x.length; ++i) {
82 x[i] = b.charCodeAt(i);
83 }
84 }
85 };
86
87 if(algorithm.name === 'PRIMEINC') {
88 return primeincFindPrime(bits, rng, algorithm.options, callback);
89 }
90
91 throw new Error('Invalid prime generation algorithm: ' + algorithm.name);
92};
93
94function primeincFindPrime(bits, rng, options, callback) {
95 if('workers' in options) {
96 return primeincFindPrimeWithWorkers(bits, rng, options, callback);
97 }
98 return primeincFindPrimeWithoutWorkers(bits, rng, options, callback);
99}
100
101function primeincFindPrimeWithoutWorkers(bits, rng, options, callback) {
102 // initialize random number
103 var num = generateRandom(bits, rng);
104
105 /* Note: All primes are of the form 30k+i for i < 30 and gcd(30, i)=1. The
106 number we are given is always aligned at 30k + 1. Each time the number is
107 determined not to be prime we add to get to the next 'i', eg: if the number
108 was at 30k + 1 we add 6. */
109 var deltaIdx = 0;
110
111 // get required number of MR tests
112 var mrTests = getMillerRabinTests(num.bitLength());
113 if('millerRabinTests' in options) {
114 mrTests = options.millerRabinTests;
115 }
116
117 // find prime nearest to 'num' for maxBlockTime ms
118 // 10 ms gives 5ms of leeway for other calculations before dropping
119 // below 60fps (1000/60 == 16.67), but in reality, the number will
120 // likely be higher due to an 'atomic' big int modPow
121 var maxBlockTime = 10;
122 if('maxBlockTime' in options) {
123 maxBlockTime = options.maxBlockTime;
124 }
125
126 _primeinc(num, bits, rng, deltaIdx, mrTests, maxBlockTime, callback);
127}
128
129function _primeinc(num, bits, rng, deltaIdx, mrTests, maxBlockTime, callback) {
130 var start = +new Date();
131 do {
132 // overflow, regenerate random number
133 if(num.bitLength() > bits) {
134 num = generateRandom(bits, rng);
135 }
136 // do primality test
137 if(num.isProbablePrime(mrTests)) {
138 return callback(null, num);
139 }
140 // get next potential prime
141 num.dAddOffset(GCD_30_DELTA[deltaIdx++ % 8], 0);
142 } while(maxBlockTime < 0 || (+new Date() - start < maxBlockTime));
143
144 // keep trying later
145 forge.util.setImmediate(function() {
146 _primeinc(num, bits, rng, deltaIdx, mrTests, maxBlockTime, callback);
147 });
148}
149
150// NOTE: This algorithm is indeterminate in nature because workers
151// run in parallel looking at different segments of numbers. Even if this
152// algorithm is run twice with the same input from a predictable RNG, it
153// may produce different outputs.
154function primeincFindPrimeWithWorkers(bits, rng, options, callback) {
155 // web workers unavailable
156 if(typeof Worker === 'undefined') {
157 return primeincFindPrimeWithoutWorkers(bits, rng, options, callback);
158 }
159
160 // initialize random number
161 var num = generateRandom(bits, rng);
162
163 // use web workers to generate keys
164 var numWorkers = options.workers;
165 var workLoad = options.workLoad || 100;
166 var range = workLoad * 30 / 8;
167 var workerScript = options.workerScript || 'forge/prime.worker.js';
168 if(numWorkers === -1) {
169 return forge.util.estimateCores(function(err, cores) {
170 if(err) {
171 // default to 2
172 cores = 2;
173 }
174 numWorkers = cores - 1;
175 generate();
176 });
177 }
178 generate();
179
180 function generate() {
181 // require at least 1 worker
182 numWorkers = Math.max(1, numWorkers);
183
184 // TODO: consider optimizing by starting workers outside getPrime() ...
185 // note that in order to clean up they will have to be made internally
186 // asynchronous which may actually be slower
187
188 // start workers immediately
189 var workers = [];
190 for(var i = 0; i < numWorkers; ++i) {
191 // FIXME: fix path or use blob URLs
192 workers[i] = new Worker(workerScript);
193 }
194 var running = numWorkers;
195
196 // listen for requests from workers and assign ranges to find prime
197 for(var i = 0; i < numWorkers; ++i) {
198 workers[i].addEventListener('message', workerMessage);
199 }
200
201 /* Note: The distribution of random numbers is unknown. Therefore, each
202 web worker is continuously allocated a range of numbers to check for a
203 random number until one is found.
204
205 Every 30 numbers will be checked just 8 times, because prime numbers
206 have the form:
207
208 30k+i, for i < 30 and gcd(30, i)=1 (there are 8 values of i for this)
209
210 Therefore, if we want a web worker to run N checks before asking for
211 a new range of numbers, each range must contain N*30/8 numbers.
212
213 For 100 checks (workLoad), this is a range of 375. */
214
215 var found = false;
216 function workerMessage(e) {
217 // ignore message, prime already found
218 if(found) {
219 return;
220 }
221
222 --running;
223 var data = e.data;
224 if(data.found) {
225 // terminate all workers
226 for(var i = 0; i < workers.length; ++i) {
227 workers[i].terminate();
228 }
229 found = true;
230 return callback(null, new BigInteger(data.prime, 16));
231 }
232
233 // overflow, regenerate random number
234 if(num.bitLength() > bits) {
235 num = generateRandom(bits, rng);
236 }
237
238 // assign new range to check
239 var hex = num.toString(16);
240
241 // start prime search
242 e.target.postMessage({
243 hex: hex,
244 workLoad: workLoad
245 });
246
247 num.dAddOffset(range, 0);
248 }
249 }
250}
251
252/**
253 * Generates a random number using the given number of bits and RNG.
254 *
255 * @param bits the number of bits for the number.
256 * @param rng the random number generator to use.
257 *
258 * @return the random number.
259 */
260function generateRandom(bits, rng) {
261 var num = new BigInteger(bits, rng);
262 // force MSB set
263 var bits1 = bits - 1;
264 if(!num.testBit(bits1)) {
265 num.bitwiseTo(BigInteger.ONE.shiftLeft(bits1), op_or, num);
266 }
267 // align number on 30k+1 boundary
268 num.dAddOffset(31 - num.mod(THIRTY).byteValue(), 0);
269 return num;
270}
271
272/**
273 * Returns the required number of Miller-Rabin tests to generate a
274 * prime with an error probability of (1/2)^80.
275 *
276 * See Handbook of Applied Cryptography Chapter 4, Table 4.4.
277 *
278 * @param bits the bit size.
279 *
280 * @return the required number of iterations.
281 */
282function getMillerRabinTests(bits) {
283 if(bits <= 100) return 27;
284 if(bits <= 150) return 18;
285 if(bits <= 200) return 15;
286 if(bits <= 250) return 12;
287 if(bits <= 300) return 9;
288 if(bits <= 350) return 8;
289 if(bits <= 400) return 7;
290 if(bits <= 500) return 6;
291 if(bits <= 600) return 5;
292 if(bits <= 800) return 4;
293 if(bits <= 1250) return 3;
294 return 2;
295}
296
297})();
Note: See TracBrowser for help on using the repository browser.