source: trip-planner-front/node_modules/node-forge/lib/aes.js@ bdd6491

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

initial commit

  • Property mode set to 100644
File size: 38.1 KB
Line 
1/**
2 * Advanced Encryption Standard (AES) implementation.
3 *
4 * This implementation is based on the public domain library 'jscrypto' which
5 * was written by:
6 *
7 * Emily Stark (estark@stanford.edu)
8 * Mike Hamburg (mhamburg@stanford.edu)
9 * Dan Boneh (dabo@cs.stanford.edu)
10 *
11 * Parts of this code are based on the OpenSSL implementation of AES:
12 * http://www.openssl.org
13 *
14 * @author Dave Longley
15 *
16 * Copyright (c) 2010-2014 Digital Bazaar, Inc.
17 */
18var forge = require('./forge');
19require('./cipher');
20require('./cipherModes');
21require('./util');
22
23/* AES API */
24module.exports = forge.aes = forge.aes || {};
25
26/**
27 * Deprecated. Instead, use:
28 *
29 * var cipher = forge.cipher.createCipher('AES-<mode>', key);
30 * cipher.start({iv: iv});
31 *
32 * Creates an AES cipher object to encrypt data using the given symmetric key.
33 * The output will be stored in the 'output' member of the returned cipher.
34 *
35 * The key and iv may be given as a string of bytes, an array of bytes,
36 * a byte buffer, or an array of 32-bit words.
37 *
38 * @param key the symmetric key to use.
39 * @param iv the initialization vector to use.
40 * @param output the buffer to write to, null to create one.
41 * @param mode the cipher mode to use (default: 'CBC').
42 *
43 * @return the cipher.
44 */
45forge.aes.startEncrypting = function(key, iv, output, mode) {
46 var cipher = _createCipher({
47 key: key,
48 output: output,
49 decrypt: false,
50 mode: mode
51 });
52 cipher.start(iv);
53 return cipher;
54};
55
56/**
57 * Deprecated. Instead, use:
58 *
59 * var cipher = forge.cipher.createCipher('AES-<mode>', key);
60 *
61 * Creates an AES cipher object to encrypt data using the given symmetric key.
62 *
63 * The key may be given as a string of bytes, an array of bytes, a
64 * byte buffer, or an array of 32-bit words.
65 *
66 * @param key the symmetric key to use.
67 * @param mode the cipher mode to use (default: 'CBC').
68 *
69 * @return the cipher.
70 */
71forge.aes.createEncryptionCipher = function(key, mode) {
72 return _createCipher({
73 key: key,
74 output: null,
75 decrypt: false,
76 mode: mode
77 });
78};
79
80/**
81 * Deprecated. Instead, use:
82 *
83 * var decipher = forge.cipher.createDecipher('AES-<mode>', key);
84 * decipher.start({iv: iv});
85 *
86 * Creates an AES cipher object to decrypt data using the given symmetric key.
87 * The output will be stored in the 'output' member of the returned cipher.
88 *
89 * The key and iv may be given as a string of bytes, an array of bytes,
90 * a byte buffer, or an array of 32-bit words.
91 *
92 * @param key the symmetric key to use.
93 * @param iv the initialization vector to use.
94 * @param output the buffer to write to, null to create one.
95 * @param mode the cipher mode to use (default: 'CBC').
96 *
97 * @return the cipher.
98 */
99forge.aes.startDecrypting = function(key, iv, output, mode) {
100 var cipher = _createCipher({
101 key: key,
102 output: output,
103 decrypt: true,
104 mode: mode
105 });
106 cipher.start(iv);
107 return cipher;
108};
109
110/**
111 * Deprecated. Instead, use:
112 *
113 * var decipher = forge.cipher.createDecipher('AES-<mode>', key);
114 *
115 * Creates an AES cipher object to decrypt data using the given symmetric key.
116 *
117 * The key may be given as a string of bytes, an array of bytes, a
118 * byte buffer, or an array of 32-bit words.
119 *
120 * @param key the symmetric key to use.
121 * @param mode the cipher mode to use (default: 'CBC').
122 *
123 * @return the cipher.
124 */
125forge.aes.createDecryptionCipher = function(key, mode) {
126 return _createCipher({
127 key: key,
128 output: null,
129 decrypt: true,
130 mode: mode
131 });
132};
133
134/**
135 * Creates a new AES cipher algorithm object.
136 *
137 * @param name the name of the algorithm.
138 * @param mode the mode factory function.
139 *
140 * @return the AES algorithm object.
141 */
142forge.aes.Algorithm = function(name, mode) {
143 if(!init) {
144 initialize();
145 }
146 var self = this;
147 self.name = name;
148 self.mode = new mode({
149 blockSize: 16,
150 cipher: {
151 encrypt: function(inBlock, outBlock) {
152 return _updateBlock(self._w, inBlock, outBlock, false);
153 },
154 decrypt: function(inBlock, outBlock) {
155 return _updateBlock(self._w, inBlock, outBlock, true);
156 }
157 }
158 });
159 self._init = false;
160};
161
162/**
163 * Initializes this AES algorithm by expanding its key.
164 *
165 * @param options the options to use.
166 * key the key to use with this algorithm.
167 * decrypt true if the algorithm should be initialized for decryption,
168 * false for encryption.
169 */
170forge.aes.Algorithm.prototype.initialize = function(options) {
171 if(this._init) {
172 return;
173 }
174
175 var key = options.key;
176 var tmp;
177
178 /* Note: The key may be a string of bytes, an array of bytes, a byte
179 buffer, or an array of 32-bit integers. If the key is in bytes, then
180 it must be 16, 24, or 32 bytes in length. If it is in 32-bit
181 integers, it must be 4, 6, or 8 integers long. */
182
183 if(typeof key === 'string' &&
184 (key.length === 16 || key.length === 24 || key.length === 32)) {
185 // convert key string into byte buffer
186 key = forge.util.createBuffer(key);
187 } else if(forge.util.isArray(key) &&
188 (key.length === 16 || key.length === 24 || key.length === 32)) {
189 // convert key integer array into byte buffer
190 tmp = key;
191 key = forge.util.createBuffer();
192 for(var i = 0; i < tmp.length; ++i) {
193 key.putByte(tmp[i]);
194 }
195 }
196
197 // convert key byte buffer into 32-bit integer array
198 if(!forge.util.isArray(key)) {
199 tmp = key;
200 key = [];
201
202 // key lengths of 16, 24, 32 bytes allowed
203 var len = tmp.length();
204 if(len === 16 || len === 24 || len === 32) {
205 len = len >>> 2;
206 for(var i = 0; i < len; ++i) {
207 key.push(tmp.getInt32());
208 }
209 }
210 }
211
212 // key must be an array of 32-bit integers by now
213 if(!forge.util.isArray(key) ||
214 !(key.length === 4 || key.length === 6 || key.length === 8)) {
215 throw new Error('Invalid key parameter.');
216 }
217
218 // encryption operation is always used for these modes
219 var mode = this.mode.name;
220 var encryptOp = (['CFB', 'OFB', 'CTR', 'GCM'].indexOf(mode) !== -1);
221
222 // do key expansion
223 this._w = _expandKey(key, options.decrypt && !encryptOp);
224 this._init = true;
225};
226
227/**
228 * Expands a key. Typically only used for testing.
229 *
230 * @param key the symmetric key to expand, as an array of 32-bit words.
231 * @param decrypt true to expand for decryption, false for encryption.
232 *
233 * @return the expanded key.
234 */
235forge.aes._expandKey = function(key, decrypt) {
236 if(!init) {
237 initialize();
238 }
239 return _expandKey(key, decrypt);
240};
241
242/**
243 * Updates a single block. Typically only used for testing.
244 *
245 * @param w the expanded key to use.
246 * @param input an array of block-size 32-bit words.
247 * @param output an array of block-size 32-bit words.
248 * @param decrypt true to decrypt, false to encrypt.
249 */
250forge.aes._updateBlock = _updateBlock;
251
252/** Register AES algorithms **/
253
254registerAlgorithm('AES-ECB', forge.cipher.modes.ecb);
255registerAlgorithm('AES-CBC', forge.cipher.modes.cbc);
256registerAlgorithm('AES-CFB', forge.cipher.modes.cfb);
257registerAlgorithm('AES-OFB', forge.cipher.modes.ofb);
258registerAlgorithm('AES-CTR', forge.cipher.modes.ctr);
259registerAlgorithm('AES-GCM', forge.cipher.modes.gcm);
260
261function registerAlgorithm(name, mode) {
262 var factory = function() {
263 return new forge.aes.Algorithm(name, mode);
264 };
265 forge.cipher.registerAlgorithm(name, factory);
266}
267
268/** AES implementation **/
269
270var init = false; // not yet initialized
271var Nb = 4; // number of words comprising the state (AES = 4)
272var sbox; // non-linear substitution table used in key expansion
273var isbox; // inversion of sbox
274var rcon; // round constant word array
275var mix; // mix-columns table
276var imix; // inverse mix-columns table
277
278/**
279 * Performs initialization, ie: precomputes tables to optimize for speed.
280 *
281 * One way to understand how AES works is to imagine that 'addition' and
282 * 'multiplication' are interfaces that require certain mathematical
283 * properties to hold true (ie: they are associative) but they might have
284 * different implementations and produce different kinds of results ...
285 * provided that their mathematical properties remain true. AES defines
286 * its own methods of addition and multiplication but keeps some important
287 * properties the same, ie: associativity and distributivity. The
288 * explanation below tries to shed some light on how AES defines addition
289 * and multiplication of bytes and 32-bit words in order to perform its
290 * encryption and decryption algorithms.
291 *
292 * The basics:
293 *
294 * The AES algorithm views bytes as binary representations of polynomials
295 * that have either 1 or 0 as the coefficients. It defines the addition
296 * or subtraction of two bytes as the XOR operation. It also defines the
297 * multiplication of two bytes as a finite field referred to as GF(2^8)
298 * (Note: 'GF' means "Galois Field" which is a field that contains a finite
299 * number of elements so GF(2^8) has 256 elements).
300 *
301 * This means that any two bytes can be represented as binary polynomials;
302 * when they multiplied together and modularly reduced by an irreducible
303 * polynomial of the 8th degree, the results are the field GF(2^8). The
304 * specific irreducible polynomial that AES uses in hexadecimal is 0x11b.
305 * This multiplication is associative with 0x01 as the identity:
306 *
307 * (b * 0x01 = GF(b, 0x01) = b).
308 *
309 * The operation GF(b, 0x02) can be performed at the byte level by left
310 * shifting b once and then XOR'ing it (to perform the modular reduction)
311 * with 0x11b if b is >= 128. Repeated application of the multiplication
312 * of 0x02 can be used to implement the multiplication of any two bytes.
313 *
314 * For instance, multiplying 0x57 and 0x13, denoted as GF(0x57, 0x13), can
315 * be performed by factoring 0x13 into 0x01, 0x02, and 0x10. Then these
316 * factors can each be multiplied by 0x57 and then added together. To do
317 * the multiplication, values for 0x57 multiplied by each of these 3 factors
318 * can be precomputed and stored in a table. To add them, the values from
319 * the table are XOR'd together.
320 *
321 * AES also defines addition and multiplication of words, that is 4-byte
322 * numbers represented as polynomials of 3 degrees where the coefficients
323 * are the values of the bytes.
324 *
325 * The word [a0, a1, a2, a3] is a polynomial a3x^3 + a2x^2 + a1x + a0.
326 *
327 * Addition is performed by XOR'ing like powers of x. Multiplication
328 * is performed in two steps, the first is an algebriac expansion as
329 * you would do normally (where addition is XOR). But the result is
330 * a polynomial larger than 3 degrees and thus it cannot fit in a word. So
331 * next the result is modularly reduced by an AES-specific polynomial of
332 * degree 4 which will always produce a polynomial of less than 4 degrees
333 * such that it will fit in a word. In AES, this polynomial is x^4 + 1.
334 *
335 * The modular product of two polynomials 'a' and 'b' is thus:
336 *
337 * d(x) = d3x^3 + d2x^2 + d1x + d0
338 * with
339 * d0 = GF(a0, b0) ^ GF(a3, b1) ^ GF(a2, b2) ^ GF(a1, b3)
340 * d1 = GF(a1, b0) ^ GF(a0, b1) ^ GF(a3, b2) ^ GF(a2, b3)
341 * d2 = GF(a2, b0) ^ GF(a1, b1) ^ GF(a0, b2) ^ GF(a3, b3)
342 * d3 = GF(a3, b0) ^ GF(a2, b1) ^ GF(a1, b2) ^ GF(a0, b3)
343 *
344 * As a matrix:
345 *
346 * [d0] = [a0 a3 a2 a1][b0]
347 * [d1] [a1 a0 a3 a2][b1]
348 * [d2] [a2 a1 a0 a3][b2]
349 * [d3] [a3 a2 a1 a0][b3]
350 *
351 * Special polynomials defined by AES (0x02 == {02}):
352 * a(x) = {03}x^3 + {01}x^2 + {01}x + {02}
353 * a^-1(x) = {0b}x^3 + {0d}x^2 + {09}x + {0e}.
354 *
355 * These polynomials are used in the MixColumns() and InverseMixColumns()
356 * operations, respectively, to cause each element in the state to affect
357 * the output (referred to as diffusing).
358 *
359 * RotWord() uses: a0 = a1 = a2 = {00} and a3 = {01}, which is the
360 * polynomial x3.
361 *
362 * The ShiftRows() method modifies the last 3 rows in the state (where
363 * the state is 4 words with 4 bytes per word) by shifting bytes cyclically.
364 * The 1st byte in the second row is moved to the end of the row. The 1st
365 * and 2nd bytes in the third row are moved to the end of the row. The 1st,
366 * 2nd, and 3rd bytes are moved in the fourth row.
367 *
368 * More details on how AES arithmetic works:
369 *
370 * In the polynomial representation of binary numbers, XOR performs addition
371 * and subtraction and multiplication in GF(2^8) denoted as GF(a, b)
372 * corresponds with the multiplication of polynomials modulo an irreducible
373 * polynomial of degree 8. In other words, for AES, GF(a, b) will multiply
374 * polynomial 'a' with polynomial 'b' and then do a modular reduction by
375 * an AES-specific irreducible polynomial of degree 8.
376 *
377 * A polynomial is irreducible if its only divisors are one and itself. For
378 * the AES algorithm, this irreducible polynomial is:
379 *
380 * m(x) = x^8 + x^4 + x^3 + x + 1,
381 *
382 * or {01}{1b} in hexadecimal notation, where each coefficient is a bit:
383 * 100011011 = 283 = 0x11b.
384 *
385 * For example, GF(0x57, 0x83) = 0xc1 because
386 *
387 * 0x57 = 87 = 01010111 = x^6 + x^4 + x^2 + x + 1
388 * 0x85 = 131 = 10000101 = x^7 + x + 1
389 *
390 * (x^6 + x^4 + x^2 + x + 1) * (x^7 + x + 1)
391 * = x^13 + x^11 + x^9 + x^8 + x^7 +
392 * x^7 + x^5 + x^3 + x^2 + x +
393 * x^6 + x^4 + x^2 + x + 1
394 * = x^13 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1 = y
395 * y modulo (x^8 + x^4 + x^3 + x + 1)
396 * = x^7 + x^6 + 1.
397 *
398 * The modular reduction by m(x) guarantees the result will be a binary
399 * polynomial of less than degree 8, so that it can fit in a byte.
400 *
401 * The operation to multiply a binary polynomial b with x (the polynomial
402 * x in binary representation is 00000010) is:
403 *
404 * b_7x^8 + b_6x^7 + b_5x^6 + b_4x^5 + b_3x^4 + b_2x^3 + b_1x^2 + b_0x^1
405 *
406 * To get GF(b, x) we must reduce that by m(x). If b_7 is 0 (that is the
407 * most significant bit is 0 in b) then the result is already reduced. If
408 * it is 1, then we can reduce it by subtracting m(x) via an XOR.
409 *
410 * It follows that multiplication by x (00000010 or 0x02) can be implemented
411 * by performing a left shift followed by a conditional bitwise XOR with
412 * 0x1b. This operation on bytes is denoted by xtime(). Multiplication by
413 * higher powers of x can be implemented by repeated application of xtime().
414 *
415 * By adding intermediate results, multiplication by any constant can be
416 * implemented. For instance:
417 *
418 * GF(0x57, 0x13) = 0xfe because:
419 *
420 * xtime(b) = (b & 128) ? (b << 1 ^ 0x11b) : (b << 1)
421 *
422 * Note: We XOR with 0x11b instead of 0x1b because in javascript our
423 * datatype for b can be larger than 1 byte, so a left shift will not
424 * automatically eliminate bits that overflow a byte ... by XOR'ing the
425 * overflow bit with 1 (the extra one from 0x11b) we zero it out.
426 *
427 * GF(0x57, 0x02) = xtime(0x57) = 0xae
428 * GF(0x57, 0x04) = xtime(0xae) = 0x47
429 * GF(0x57, 0x08) = xtime(0x47) = 0x8e
430 * GF(0x57, 0x10) = xtime(0x8e) = 0x07
431 *
432 * GF(0x57, 0x13) = GF(0x57, (0x01 ^ 0x02 ^ 0x10))
433 *
434 * And by the distributive property (since XOR is addition and GF() is
435 * multiplication):
436 *
437 * = GF(0x57, 0x01) ^ GF(0x57, 0x02) ^ GF(0x57, 0x10)
438 * = 0x57 ^ 0xae ^ 0x07
439 * = 0xfe.
440 */
441function initialize() {
442 init = true;
443
444 /* Populate the Rcon table. These are the values given by
445 [x^(i-1),{00},{00},{00}] where x^(i-1) are powers of x (and x = 0x02)
446 in the field of GF(2^8), where i starts at 1.
447
448 rcon[0] = [0x00, 0x00, 0x00, 0x00]
449 rcon[1] = [0x01, 0x00, 0x00, 0x00] 2^(1-1) = 2^0 = 1
450 rcon[2] = [0x02, 0x00, 0x00, 0x00] 2^(2-1) = 2^1 = 2
451 ...
452 rcon[9] = [0x1B, 0x00, 0x00, 0x00] 2^(9-1) = 2^8 = 0x1B
453 rcon[10] = [0x36, 0x00, 0x00, 0x00] 2^(10-1) = 2^9 = 0x36
454
455 We only store the first byte because it is the only one used.
456 */
457 rcon = [0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36];
458
459 // compute xtime table which maps i onto GF(i, 0x02)
460 var xtime = new Array(256);
461 for(var i = 0; i < 128; ++i) {
462 xtime[i] = i << 1;
463 xtime[i + 128] = (i + 128) << 1 ^ 0x11B;
464 }
465
466 // compute all other tables
467 sbox = new Array(256);
468 isbox = new Array(256);
469 mix = new Array(4);
470 imix = new Array(4);
471 for(var i = 0; i < 4; ++i) {
472 mix[i] = new Array(256);
473 imix[i] = new Array(256);
474 }
475 var e = 0, ei = 0, e2, e4, e8, sx, sx2, me, ime;
476 for(var i = 0; i < 256; ++i) {
477 /* We need to generate the SubBytes() sbox and isbox tables so that
478 we can perform byte substitutions. This requires us to traverse
479 all of the elements in GF, find their multiplicative inverses,
480 and apply to each the following affine transformation:
481
482 bi' = bi ^ b(i + 4) mod 8 ^ b(i + 5) mod 8 ^ b(i + 6) mod 8 ^
483 b(i + 7) mod 8 ^ ci
484 for 0 <= i < 8, where bi is the ith bit of the byte, and ci is the
485 ith bit of a byte c with the value {63} or {01100011}.
486
487 It is possible to traverse every possible value in a Galois field
488 using what is referred to as a 'generator'. There are many
489 generators (128 out of 256): 3,5,6,9,11,82 to name a few. To fully
490 traverse GF we iterate 255 times, multiplying by our generator
491 each time.
492
493 On each iteration we can determine the multiplicative inverse for
494 the current element.
495
496 Suppose there is an element in GF 'e'. For a given generator 'g',
497 e = g^x. The multiplicative inverse of e is g^(255 - x). It turns
498 out that if use the inverse of a generator as another generator
499 it will produce all of the corresponding multiplicative inverses
500 at the same time. For this reason, we choose 5 as our inverse
501 generator because it only requires 2 multiplies and 1 add and its
502 inverse, 82, requires relatively few operations as well.
503
504 In order to apply the affine transformation, the multiplicative
505 inverse 'ei' of 'e' can be repeatedly XOR'd (4 times) with a
506 bit-cycling of 'ei'. To do this 'ei' is first stored in 's' and
507 'x'. Then 's' is left shifted and the high bit of 's' is made the
508 low bit. The resulting value is stored in 's'. Then 'x' is XOR'd
509 with 's' and stored in 'x'. On each subsequent iteration the same
510 operation is performed. When 4 iterations are complete, 'x' is
511 XOR'd with 'c' (0x63) and the transformed value is stored in 'x'.
512 For example:
513
514 s = 01000001
515 x = 01000001
516
517 iteration 1: s = 10000010, x ^= s
518 iteration 2: s = 00000101, x ^= s
519 iteration 3: s = 00001010, x ^= s
520 iteration 4: s = 00010100, x ^= s
521 x ^= 0x63
522
523 This can be done with a loop where s = (s << 1) | (s >> 7). However,
524 it can also be done by using a single 16-bit (in this case 32-bit)
525 number 'sx'. Since XOR is an associative operation, we can set 'sx'
526 to 'ei' and then XOR it with 'sx' left-shifted 1,2,3, and 4 times.
527 The most significant bits will flow into the high 8 bit positions
528 and be correctly XOR'd with one another. All that remains will be
529 to cycle the high 8 bits by XOR'ing them all with the lower 8 bits
530 afterwards.
531
532 At the same time we're populating sbox and isbox we can precompute
533 the multiplication we'll need to do to do MixColumns() later.
534 */
535
536 // apply affine transformation
537 sx = ei ^ (ei << 1) ^ (ei << 2) ^ (ei << 3) ^ (ei << 4);
538 sx = (sx >> 8) ^ (sx & 255) ^ 0x63;
539
540 // update tables
541 sbox[e] = sx;
542 isbox[sx] = e;
543
544 /* Mixing columns is done using matrix multiplication. The columns
545 that are to be mixed are each a single word in the current state.
546 The state has Nb columns (4 columns). Therefore each column is a
547 4 byte word. So to mix the columns in a single column 'c' where
548 its rows are r0, r1, r2, and r3, we use the following matrix
549 multiplication:
550
551 [2 3 1 1]*[r0,c]=[r'0,c]
552 [1 2 3 1] [r1,c] [r'1,c]
553 [1 1 2 3] [r2,c] [r'2,c]
554 [3 1 1 2] [r3,c] [r'3,c]
555
556 r0, r1, r2, and r3 are each 1 byte of one of the words in the
557 state (a column). To do matrix multiplication for each mixed
558 column c' we multiply the corresponding row from the left matrix
559 with the corresponding column from the right matrix. In total, we
560 get 4 equations:
561
562 r0,c' = 2*r0,c + 3*r1,c + 1*r2,c + 1*r3,c
563 r1,c' = 1*r0,c + 2*r1,c + 3*r2,c + 1*r3,c
564 r2,c' = 1*r0,c + 1*r1,c + 2*r2,c + 3*r3,c
565 r3,c' = 3*r0,c + 1*r1,c + 1*r2,c + 2*r3,c
566
567 As usual, the multiplication is as previously defined and the
568 addition is XOR. In order to optimize mixing columns we can store
569 the multiplication results in tables. If you think of the whole
570 column as a word (it might help to visualize by mentally rotating
571 the equations above by counterclockwise 90 degrees) then you can
572 see that it would be useful to map the multiplications performed on
573 each byte (r0, r1, r2, r3) onto a word as well. For instance, we
574 could map 2*r0,1*r0,1*r0,3*r0 onto a word by storing 2*r0 in the
575 highest 8 bits and 3*r0 in the lowest 8 bits (with the other two
576 respectively in the middle). This means that a table can be
577 constructed that uses r0 as an index to the word. We can do the
578 same with r1, r2, and r3, creating a total of 4 tables.
579
580 To construct a full c', we can just look up each byte of c in
581 their respective tables and XOR the results together.
582
583 Also, to build each table we only have to calculate the word
584 for 2,1,1,3 for every byte ... which we can do on each iteration
585 of this loop since we will iterate over every byte. After we have
586 calculated 2,1,1,3 we can get the results for the other tables
587 by cycling the byte at the end to the beginning. For instance
588 we can take the result of table 2,1,1,3 and produce table 3,2,1,1
589 by moving the right most byte to the left most position just like
590 how you can imagine the 3 moved out of 2,1,1,3 and to the front
591 to produce 3,2,1,1.
592
593 There is another optimization in that the same multiples of
594 the current element we need in order to advance our generator
595 to the next iteration can be reused in performing the 2,1,1,3
596 calculation. We also calculate the inverse mix column tables,
597 with e,9,d,b being the inverse of 2,1,1,3.
598
599 When we're done, and we need to actually mix columns, the first
600 byte of each state word should be put through mix[0] (2,1,1,3),
601 the second through mix[1] (3,2,1,1) and so forth. Then they should
602 be XOR'd together to produce the fully mixed column.
603 */
604
605 // calculate mix and imix table values
606 sx2 = xtime[sx];
607 e2 = xtime[e];
608 e4 = xtime[e2];
609 e8 = xtime[e4];
610 me =
611 (sx2 << 24) ^ // 2
612 (sx << 16) ^ // 1
613 (sx << 8) ^ // 1
614 (sx ^ sx2); // 3
615 ime =
616 (e2 ^ e4 ^ e8) << 24 ^ // E (14)
617 (e ^ e8) << 16 ^ // 9
618 (e ^ e4 ^ e8) << 8 ^ // D (13)
619 (e ^ e2 ^ e8); // B (11)
620 // produce each of the mix tables by rotating the 2,1,1,3 value
621 for(var n = 0; n < 4; ++n) {
622 mix[n][e] = me;
623 imix[n][sx] = ime;
624 // cycle the right most byte to the left most position
625 // ie: 2,1,1,3 becomes 3,2,1,1
626 me = me << 24 | me >>> 8;
627 ime = ime << 24 | ime >>> 8;
628 }
629
630 // get next element and inverse
631 if(e === 0) {
632 // 1 is the inverse of 1
633 e = ei = 1;
634 } else {
635 // e = 2e + 2*2*2*(10e)) = multiply e by 82 (chosen generator)
636 // ei = ei + 2*2*ei = multiply ei by 5 (inverse generator)
637 e = e2 ^ xtime[xtime[xtime[e2 ^ e8]]];
638 ei ^= xtime[xtime[ei]];
639 }
640 }
641}
642
643/**
644 * Generates a key schedule using the AES key expansion algorithm.
645 *
646 * The AES algorithm takes the Cipher Key, K, and performs a Key Expansion
647 * routine to generate a key schedule. The Key Expansion generates a total
648 * of Nb*(Nr + 1) words: the algorithm requires an initial set of Nb words,
649 * and each of the Nr rounds requires Nb words of key data. The resulting
650 * key schedule consists of a linear array of 4-byte words, denoted [wi ],
651 * with i in the range 0 <= i < Nb(Nr + 1).
652 *
653 * KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)
654 * AES-128 (Nb=4, Nk=4, Nr=10)
655 * AES-192 (Nb=4, Nk=6, Nr=12)
656 * AES-256 (Nb=4, Nk=8, Nr=14)
657 * Note: Nr=Nk+6.
658 *
659 * Nb is the number of columns (32-bit words) comprising the State (or
660 * number of bytes in a block). For AES, Nb=4.
661 *
662 * @param key the key to schedule (as an array of 32-bit words).
663 * @param decrypt true to modify the key schedule to decrypt, false not to.
664 *
665 * @return the generated key schedule.
666 */
667function _expandKey(key, decrypt) {
668 // copy the key's words to initialize the key schedule
669 var w = key.slice(0);
670
671 /* RotWord() will rotate a word, moving the first byte to the last
672 byte's position (shifting the other bytes left).
673
674 We will be getting the value of Rcon at i / Nk. 'i' will iterate
675 from Nk to (Nb * Nr+1). Nk = 4 (4 byte key), Nb = 4 (4 words in
676 a block), Nr = Nk + 6 (10). Therefore 'i' will iterate from
677 4 to 44 (exclusive). Each time we iterate 4 times, i / Nk will
678 increase by 1. We use a counter iNk to keep track of this.
679 */
680
681 // go through the rounds expanding the key
682 var temp, iNk = 1;
683 var Nk = w.length;
684 var Nr1 = Nk + 6 + 1;
685 var end = Nb * Nr1;
686 for(var i = Nk; i < end; ++i) {
687 temp = w[i - 1];
688 if(i % Nk === 0) {
689 // temp = SubWord(RotWord(temp)) ^ Rcon[i / Nk]
690 temp =
691 sbox[temp >>> 16 & 255] << 24 ^
692 sbox[temp >>> 8 & 255] << 16 ^
693 sbox[temp & 255] << 8 ^
694 sbox[temp >>> 24] ^ (rcon[iNk] << 24);
695 iNk++;
696 } else if(Nk > 6 && (i % Nk === 4)) {
697 // temp = SubWord(temp)
698 temp =
699 sbox[temp >>> 24] << 24 ^
700 sbox[temp >>> 16 & 255] << 16 ^
701 sbox[temp >>> 8 & 255] << 8 ^
702 sbox[temp & 255];
703 }
704 w[i] = w[i - Nk] ^ temp;
705 }
706
707 /* When we are updating a cipher block we always use the code path for
708 encryption whether we are decrypting or not (to shorten code and
709 simplify the generation of look up tables). However, because there
710 are differences in the decryption algorithm, other than just swapping
711 in different look up tables, we must transform our key schedule to
712 account for these changes:
713
714 1. The decryption algorithm gets its key rounds in reverse order.
715 2. The decryption algorithm adds the round key before mixing columns
716 instead of afterwards.
717
718 We don't need to modify our key schedule to handle the first case,
719 we can just traverse the key schedule in reverse order when decrypting.
720
721 The second case requires a little work.
722
723 The tables we built for performing rounds will take an input and then
724 perform SubBytes() and MixColumns() or, for the decrypt version,
725 InvSubBytes() and InvMixColumns(). But the decrypt algorithm requires
726 us to AddRoundKey() before InvMixColumns(). This means we'll need to
727 apply some transformations to the round key to inverse-mix its columns
728 so they'll be correct for moving AddRoundKey() to after the state has
729 had its columns inverse-mixed.
730
731 To inverse-mix the columns of the state when we're decrypting we use a
732 lookup table that will apply InvSubBytes() and InvMixColumns() at the
733 same time. However, the round key's bytes are not inverse-substituted
734 in the decryption algorithm. To get around this problem, we can first
735 substitute the bytes in the round key so that when we apply the
736 transformation via the InvSubBytes()+InvMixColumns() table, it will
737 undo our substitution leaving us with the original value that we
738 want -- and then inverse-mix that value.
739
740 This change will correctly alter our key schedule so that we can XOR
741 each round key with our already transformed decryption state. This
742 allows us to use the same code path as the encryption algorithm.
743
744 We make one more change to the decryption key. Since the decryption
745 algorithm runs in reverse from the encryption algorithm, we reverse
746 the order of the round keys to avoid having to iterate over the key
747 schedule backwards when running the encryption algorithm later in
748 decryption mode. In addition to reversing the order of the round keys,
749 we also swap each round key's 2nd and 4th rows. See the comments
750 section where rounds are performed for more details about why this is
751 done. These changes are done inline with the other substitution
752 described above.
753 */
754 if(decrypt) {
755 var tmp;
756 var m0 = imix[0];
757 var m1 = imix[1];
758 var m2 = imix[2];
759 var m3 = imix[3];
760 var wnew = w.slice(0);
761 end = w.length;
762 for(var i = 0, wi = end - Nb; i < end; i += Nb, wi -= Nb) {
763 // do not sub the first or last round key (round keys are Nb
764 // words) as no column mixing is performed before they are added,
765 // but do change the key order
766 if(i === 0 || i === (end - Nb)) {
767 wnew[i] = w[wi];
768 wnew[i + 1] = w[wi + 3];
769 wnew[i + 2] = w[wi + 2];
770 wnew[i + 3] = w[wi + 1];
771 } else {
772 // substitute each round key byte because the inverse-mix
773 // table will inverse-substitute it (effectively cancel the
774 // substitution because round key bytes aren't sub'd in
775 // decryption mode) and swap indexes 3 and 1
776 for(var n = 0; n < Nb; ++n) {
777 tmp = w[wi + n];
778 wnew[i + (3&-n)] =
779 m0[sbox[tmp >>> 24]] ^
780 m1[sbox[tmp >>> 16 & 255]] ^
781 m2[sbox[tmp >>> 8 & 255]] ^
782 m3[sbox[tmp & 255]];
783 }
784 }
785 }
786 w = wnew;
787 }
788
789 return w;
790}
791
792/**
793 * Updates a single block (16 bytes) using AES. The update will either
794 * encrypt or decrypt the block.
795 *
796 * @param w the key schedule.
797 * @param input the input block (an array of 32-bit words).
798 * @param output the updated output block.
799 * @param decrypt true to decrypt the block, false to encrypt it.
800 */
801function _updateBlock(w, input, output, decrypt) {
802 /*
803 Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
804 begin
805 byte state[4,Nb]
806 state = in
807 AddRoundKey(state, w[0, Nb-1])
808 for round = 1 step 1 to Nr-1
809 SubBytes(state)
810 ShiftRows(state)
811 MixColumns(state)
812 AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
813 end for
814 SubBytes(state)
815 ShiftRows(state)
816 AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
817 out = state
818 end
819
820 InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
821 begin
822 byte state[4,Nb]
823 state = in
824 AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
825 for round = Nr-1 step -1 downto 1
826 InvShiftRows(state)
827 InvSubBytes(state)
828 AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
829 InvMixColumns(state)
830 end for
831 InvShiftRows(state)
832 InvSubBytes(state)
833 AddRoundKey(state, w[0, Nb-1])
834 out = state
835 end
836 */
837
838 // Encrypt: AddRoundKey(state, w[0, Nb-1])
839 // Decrypt: AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
840 var Nr = w.length / 4 - 1;
841 var m0, m1, m2, m3, sub;
842 if(decrypt) {
843 m0 = imix[0];
844 m1 = imix[1];
845 m2 = imix[2];
846 m3 = imix[3];
847 sub = isbox;
848 } else {
849 m0 = mix[0];
850 m1 = mix[1];
851 m2 = mix[2];
852 m3 = mix[3];
853 sub = sbox;
854 }
855 var a, b, c, d, a2, b2, c2;
856 a = input[0] ^ w[0];
857 b = input[decrypt ? 3 : 1] ^ w[1];
858 c = input[2] ^ w[2];
859 d = input[decrypt ? 1 : 3] ^ w[3];
860 var i = 3;
861
862 /* In order to share code we follow the encryption algorithm when both
863 encrypting and decrypting. To account for the changes required in the
864 decryption algorithm, we use different lookup tables when decrypting
865 and use a modified key schedule to account for the difference in the
866 order of transformations applied when performing rounds. We also get
867 key rounds in reverse order (relative to encryption). */
868 for(var round = 1; round < Nr; ++round) {
869 /* As described above, we'll be using table lookups to perform the
870 column mixing. Each column is stored as a word in the state (the
871 array 'input' has one column as a word at each index). In order to
872 mix a column, we perform these transformations on each row in c,
873 which is 1 byte in each word. The new column for c0 is c'0:
874
875 m0 m1 m2 m3
876 r0,c'0 = 2*r0,c0 + 3*r1,c0 + 1*r2,c0 + 1*r3,c0
877 r1,c'0 = 1*r0,c0 + 2*r1,c0 + 3*r2,c0 + 1*r3,c0
878 r2,c'0 = 1*r0,c0 + 1*r1,c0 + 2*r2,c0 + 3*r3,c0
879 r3,c'0 = 3*r0,c0 + 1*r1,c0 + 1*r2,c0 + 2*r3,c0
880
881 So using mix tables where c0 is a word with r0 being its upper
882 8 bits and r3 being its lower 8 bits:
883
884 m0[c0 >> 24] will yield this word: [2*r0,1*r0,1*r0,3*r0]
885 ...
886 m3[c0 & 255] will yield this word: [1*r3,1*r3,3*r3,2*r3]
887
888 Therefore to mix the columns in each word in the state we
889 do the following (& 255 omitted for brevity):
890 c'0,r0 = m0[c0 >> 24] ^ m1[c1 >> 16] ^ m2[c2 >> 8] ^ m3[c3]
891 c'0,r1 = m0[c0 >> 24] ^ m1[c1 >> 16] ^ m2[c2 >> 8] ^ m3[c3]
892 c'0,r2 = m0[c0 >> 24] ^ m1[c1 >> 16] ^ m2[c2 >> 8] ^ m3[c3]
893 c'0,r3 = m0[c0 >> 24] ^ m1[c1 >> 16] ^ m2[c2 >> 8] ^ m3[c3]
894
895 However, before mixing, the algorithm requires us to perform
896 ShiftRows(). The ShiftRows() transformation cyclically shifts the
897 last 3 rows of the state over different offsets. The first row
898 (r = 0) is not shifted.
899
900 s'_r,c = s_r,(c + shift(r, Nb) mod Nb
901 for 0 < r < 4 and 0 <= c < Nb and
902 shift(1, 4) = 1
903 shift(2, 4) = 2
904 shift(3, 4) = 3.
905
906 This causes the first byte in r = 1 to be moved to the end of
907 the row, the first 2 bytes in r = 2 to be moved to the end of
908 the row, the first 3 bytes in r = 3 to be moved to the end of
909 the row:
910
911 r1: [c0 c1 c2 c3] => [c1 c2 c3 c0]
912 r2: [c0 c1 c2 c3] [c2 c3 c0 c1]
913 r3: [c0 c1 c2 c3] [c3 c0 c1 c2]
914
915 We can make these substitutions inline with our column mixing to
916 generate an updated set of equations to produce each word in the
917 state (note the columns have changed positions):
918
919 c0 c1 c2 c3 => c0 c1 c2 c3
920 c0 c1 c2 c3 c1 c2 c3 c0 (cycled 1 byte)
921 c0 c1 c2 c3 c2 c3 c0 c1 (cycled 2 bytes)
922 c0 c1 c2 c3 c3 c0 c1 c2 (cycled 3 bytes)
923
924 Therefore:
925
926 c'0 = 2*r0,c0 + 3*r1,c1 + 1*r2,c2 + 1*r3,c3
927 c'0 = 1*r0,c0 + 2*r1,c1 + 3*r2,c2 + 1*r3,c3
928 c'0 = 1*r0,c0 + 1*r1,c1 + 2*r2,c2 + 3*r3,c3
929 c'0 = 3*r0,c0 + 1*r1,c1 + 1*r2,c2 + 2*r3,c3
930
931 c'1 = 2*r0,c1 + 3*r1,c2 + 1*r2,c3 + 1*r3,c0
932 c'1 = 1*r0,c1 + 2*r1,c2 + 3*r2,c3 + 1*r3,c0
933 c'1 = 1*r0,c1 + 1*r1,c2 + 2*r2,c3 + 3*r3,c0
934 c'1 = 3*r0,c1 + 1*r1,c2 + 1*r2,c3 + 2*r3,c0
935
936 ... and so forth for c'2 and c'3. The important distinction is
937 that the columns are cycling, with c0 being used with the m0
938 map when calculating c0, but c1 being used with the m0 map when
939 calculating c1 ... and so forth.
940
941 When performing the inverse we transform the mirror image and
942 skip the bottom row, instead of the top one, and move upwards:
943
944 c3 c2 c1 c0 => c0 c3 c2 c1 (cycled 3 bytes) *same as encryption
945 c3 c2 c1 c0 c1 c0 c3 c2 (cycled 2 bytes)
946 c3 c2 c1 c0 c2 c1 c0 c3 (cycled 1 byte) *same as encryption
947 c3 c2 c1 c0 c3 c2 c1 c0
948
949 If you compare the resulting matrices for ShiftRows()+MixColumns()
950 and for InvShiftRows()+InvMixColumns() the 2nd and 4th columns are
951 different (in encrypt mode vs. decrypt mode). So in order to use
952 the same code to handle both encryption and decryption, we will
953 need to do some mapping.
954
955 If in encryption mode we let a=c0, b=c1, c=c2, d=c3, and r<N> be
956 a row number in the state, then the resulting matrix in encryption
957 mode for applying the above transformations would be:
958
959 r1: a b c d
960 r2: b c d a
961 r3: c d a b
962 r4: d a b c
963
964 If we did the same in decryption mode we would get:
965
966 r1: a d c b
967 r2: b a d c
968 r3: c b a d
969 r4: d c b a
970
971 If instead we swap d and b (set b=c3 and d=c1), then we get:
972
973 r1: a b c d
974 r2: d a b c
975 r3: c d a b
976 r4: b c d a
977
978 Now the 1st and 3rd rows are the same as the encryption matrix. All
979 we need to do then to make the mapping exactly the same is to swap
980 the 2nd and 4th rows when in decryption mode. To do this without
981 having to do it on each iteration, we swapped the 2nd and 4th rows
982 in the decryption key schedule. We also have to do the swap above
983 when we first pull in the input and when we set the final output. */
984 a2 =
985 m0[a >>> 24] ^
986 m1[b >>> 16 & 255] ^
987 m2[c >>> 8 & 255] ^
988 m3[d & 255] ^ w[++i];
989 b2 =
990 m0[b >>> 24] ^
991 m1[c >>> 16 & 255] ^
992 m2[d >>> 8 & 255] ^
993 m3[a & 255] ^ w[++i];
994 c2 =
995 m0[c >>> 24] ^
996 m1[d >>> 16 & 255] ^
997 m2[a >>> 8 & 255] ^
998 m3[b & 255] ^ w[++i];
999 d =
1000 m0[d >>> 24] ^
1001 m1[a >>> 16 & 255] ^
1002 m2[b >>> 8 & 255] ^
1003 m3[c & 255] ^ w[++i];
1004 a = a2;
1005 b = b2;
1006 c = c2;
1007 }
1008
1009 /*
1010 Encrypt:
1011 SubBytes(state)
1012 ShiftRows(state)
1013 AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
1014
1015 Decrypt:
1016 InvShiftRows(state)
1017 InvSubBytes(state)
1018 AddRoundKey(state, w[0, Nb-1])
1019 */
1020 // Note: rows are shifted inline
1021 output[0] =
1022 (sub[a >>> 24] << 24) ^
1023 (sub[b >>> 16 & 255] << 16) ^
1024 (sub[c >>> 8 & 255] << 8) ^
1025 (sub[d & 255]) ^ w[++i];
1026 output[decrypt ? 3 : 1] =
1027 (sub[b >>> 24] << 24) ^
1028 (sub[c >>> 16 & 255] << 16) ^
1029 (sub[d >>> 8 & 255] << 8) ^
1030 (sub[a & 255]) ^ w[++i];
1031 output[2] =
1032 (sub[c >>> 24] << 24) ^
1033 (sub[d >>> 16 & 255] << 16) ^
1034 (sub[a >>> 8 & 255] << 8) ^
1035 (sub[b & 255]) ^ w[++i];
1036 output[decrypt ? 1 : 3] =
1037 (sub[d >>> 24] << 24) ^
1038 (sub[a >>> 16 & 255] << 16) ^
1039 (sub[b >>> 8 & 255] << 8) ^
1040 (sub[c & 255]) ^ w[++i];
1041}
1042
1043/**
1044 * Deprecated. Instead, use:
1045 *
1046 * forge.cipher.createCipher('AES-<mode>', key);
1047 * forge.cipher.createDecipher('AES-<mode>', key);
1048 *
1049 * Creates a deprecated AES cipher object. This object's mode will default to
1050 * CBC (cipher-block-chaining).
1051 *
1052 * The key and iv may be given as a string of bytes, an array of bytes, a
1053 * byte buffer, or an array of 32-bit words.
1054 *
1055 * @param options the options to use.
1056 * key the symmetric key to use.
1057 * output the buffer to write to.
1058 * decrypt true for decryption, false for encryption.
1059 * mode the cipher mode to use (default: 'CBC').
1060 *
1061 * @return the cipher.
1062 */
1063function _createCipher(options) {
1064 options = options || {};
1065 var mode = (options.mode || 'CBC').toUpperCase();
1066 var algorithm = 'AES-' + mode;
1067
1068 var cipher;
1069 if(options.decrypt) {
1070 cipher = forge.cipher.createDecipher(algorithm, options.key);
1071 } else {
1072 cipher = forge.cipher.createCipher(algorithm, options.key);
1073 }
1074
1075 // backwards compatible start API
1076 var start = cipher.start;
1077 cipher.start = function(iv, options) {
1078 // backwards compatibility: support second arg as output buffer
1079 var output = null;
1080 if(options instanceof forge.util.ByteBuffer) {
1081 output = options;
1082 options = {};
1083 }
1084 options = options || {};
1085 options.output = output;
1086 options.iv = iv;
1087 start.call(cipher, options);
1088 };
1089
1090 return cipher;
1091}
Note: See TracBrowser for help on using the repository browser.