1.RSA
1 // RSA, a suite of routines for performing RSA public-key computations in 2 // JavaScript. 3 // 4 // Requires BigInt.js and Barrett.js. 5 // 6 // Copyright 1998-2005 David Shapiro. 7 // 8 // You may use, re-use, abuse, copy, and modify this code to your liking, but 9 // please keep this header. 10 // 11 // Thanks! 12 // 13 // Dave Shapiro 14 // dave@ohdave.com 15 16 function RSAKeyPair(encryptionExponent, decryptionExponent, modulus) 17 { 18 this.e = biFromHex(encryptionExponent); 19 this.d = biFromHex(decryptionExponent); 20 this.m = biFromHex(modulus); 21 22 // We can do two bytes per digit, so 23 // chunkSize = 2 * (number of digits in modulus - 1). 24 // Since biHighIndex returns the high index, not the number of digits, 1 has 25 // already been subtracted. 26 //this.chunkSize = 2 * biHighIndex(this.m); 27 28 ////////////////////////////////// TYF 29 this.digitSize = 2 * biHighIndex(this.m) + 2; 30 this.chunkSize = this.digitSize - 11; // maximum, anything lower is fine 31 ////////////////////////////////// TYF 32 33 this.radix = 16; 34 this.barrett = new BarrettMu(this.m); 35 } 36 37 function twoDigit(n) 38 { 39 return (n < 10 ? "0" : "") + String(n); 40 } 41 42 function encryptedString(key, s) 43 // Altered by Rob Saunders (rob@robsaunders.net). New routine pads the 44 // string after it has been converted to an array. This fixes an 45 // incompatibility with Flash MX's ActionScript. 46 // Altered by Tang Yu Feng for interoperability with Microsoft's 47 // RSACryptoServiceProvider implementation. 48 { 49 ////////////////////////////////// TYF 50 if (key.chunkSize > key.digitSize - 11) 51 { 52 return "Error"; 53 } 54 ////////////////////////////////// TYF 55 56 57 var a = new Array(); 58 var sl = s.length; 59 60 var i = 0; 61 while (i < sl) { 62 a[i] = s.charCodeAt(i); 63 i++; 64 } 65 66 //while (a.length % key.chunkSize != 0) { 67 // a[i++] = 0; 68 //} 69 70 var al = a.length; 71 var result = ""; 72 var j, k, block; 73 for (i = 0; i < al; i += key.chunkSize) { 74 block = new BigInt(); 75 j = 0; 76 77 //for (k = i; k < i + key.chunkSize; ++j) { 78 // block.digits[j] = a[k++]; 79 // block.digits[j] += a[k++] << 8; 80 //} 81 82 ////////////////////////////////// TYF 83 // Add PKCS#1 v1.5 padding 84 // 0x00 || 0x02 || PseudoRandomNonZeroBytes || 0x00 || Message 85 // Variable a before padding must be of at most digitSize-11 86 // That is for 3 marker bytes plus at least 8 random non-zero bytes 87 var x; 88 var msgLength = (i+key.chunkSize)>al ? al%key.chunkSize : key.chunkSize; 89 90 // Variable b with 0x00 || 0x02 at the highest index. 91 var b = new Array(); 92 for (x=0; x<msgLength; x++) 93 { 94 b[x] = a[i+msgLength-1-x]; 95 } 96 b[msgLength] = 0; // marker 97 var paddedSize = Math.max(8, key.digitSize - 3 - msgLength); 98 99 for (x=0; x<paddedSize; x++) { 100 b[msgLength+1+x] = Math.floor(Math.random()*254) + 1; // [1,255] 101 } 102 // It can be asserted that msgLength+paddedSize == key.digitSize-3 103 b[key.digitSize-2] = 2; // marker 104 b[key.digitSize-1] = 0; // marker 105 106 for (k = 0; k < key.digitSize; ++j) 107 { 108 block.digits[j] = b[k++]; 109 block.digits[j] += b[k++] << 8; 110 } 111 ////////////////////////////////// TYF 112 113 var crypt = key.barrett.powMod(block, key.e); 114 var text = key.radix == 16 ? biToHex(crypt) : biToString(crypt, key.radix); 115 result += text + " "; 116 } 117 return result.substring(0, result.length - 1); // Remove last space. 118 } 119 120 function decryptedString(key, s) 121 { 122 var blocks = s.split(" "); 123 var result = ""; 124 var i, j, block; 125 for (i = 0; i < blocks.length; ++i) { 126 var bi; 127 if (key.radix == 16) { 128 bi = biFromHex(blocks[i]); 129 } 130 else { 131 bi = biFromString(blocks[i], key.radix); 132 } 133 block = key.barrett.powMod(bi, key.d); 134 for (j = 0; j <= biHighIndex(block); ++j) { 135 result += String.fromCharCode(block.digits[j] & 255, 136 block.digits[j] >> 8); 137 } 138 } 139 // Remove trailing null, if any. 140 if (result.charCodeAt(result.length - 1) == 0) { 141 result = result.substring(0, result.length - 1); 142 } 143 return result; 144 }
2.BigInt
1 // BigInt, a suite of routines for performing multiple-precision arithmetic in 2 // JavaScript. 3 // 4 // Copyright 1998-2005 David Shapiro. 5 // 6 // You may use, re-use, abuse, 7 // copy, and modify this code to your liking, but please keep this header. 8 // Thanks! 9 // 10 // Dave Shapiro 11 // dave@ohdave.com 12 13 // IMPORTANT THING: Be sure to set maxDigits according to your precision 14 // needs. Use the setMaxDigits() function to do this. See comments below. 15 // 16 // Tweaked by Ian Bunning 17 // Alterations: 18 // Fix bug in function biFromHex(s) to allow 19 // parsing of strings of length != 0 (mod 4) 20 21 // Changes made by Dave Shapiro as of 12/30/2004: 22 // 23 // The BigInt() constructor doesn't take a string anymore. If you want to 24 // create a BigInt from a string, use biFromDecimal() for base-10 25 // representations, biFromHex() for base-16 representations, or 26 // biFromString() for base-2-to-36 representations. 27 // 28 // biFromArray() has been removed. Use biCopy() instead, passing a BigInt 29 // instead of an array. 30 // 31 // The BigInt() constructor now only constructs a zeroed-out array. 32 // Alternatively, if you pass <true>, it won't construct any array. See the 33 // biCopy() method for an example of this. 34 // 35 // Be sure to set maxDigits depending on your precision needs. The default 36 // zeroed-out array ZERO_ARRAY is constructed inside the setMaxDigits() 37 // function. So use this function to set the variable. DON'T JUST SET THE 38 // VALUE. USE THE FUNCTION. 39 // 40 // ZERO_ARRAY exists to hopefully speed up construction of BigInts(). By 41 // precalculating the zero array, we can just use slice(0) to make copies of 42 // it. Presumably this calls faster native code, as opposed to setting the 43 // elements one at a time. I have not done any timing tests to verify this 44 // claim. 45 46 // Max number = 10^16 - 2 = 9999999999999998; 47 // 2^53 = 9007199254740992; 48 49 var biRadixBase = 2; 50 var biRadixBits = 16; 51 var bitsPerDigit = biRadixBits; 52 var biRadix = 1 << 16; // = 2^16 = 65536 53 var biHalfRadix = biRadix >>> 1; 54 var biRadixSquared = biRadix * biRadix; 55 var maxDigitVal = biRadix - 1; 56 var maxInteger = 9999999999999998; 57 58 // maxDigits: 59 // Change this to accommodate your largest number size. Use setMaxDigits() 60 // to change it! 61 // 62 // In general, if you're working with numbers of size N bits, you'll need 2*N 63 // bits of storage. Each digit holds 16 bits. So, a 1024-bit key will need 64 // 65 // 1024 * 2 / 16 = 128 digits of storage. 66 // 67 68 var maxDigits; 69 var ZERO_ARRAY; 70 var bigZero, bigOne; 71 72 function setMaxDigits(value) 73 { 74 maxDigits = value; 75 ZERO_ARRAY = new Array(maxDigits); 76 for (var iza = 0; iza < ZERO_ARRAY.length; iza++) ZERO_ARRAY[iza] = 0; 77 bigZero = new BigInt(); 78 bigOne = new BigInt(); 79 bigOne.digits[0] = 1; 80 } 81 82 setMaxDigits(20); 83 84 // The maximum number of digits in base 10 you can convert to an 85 // integer without JavaScript throwing up on you. 86 var dpl10 = 15; 87 // lr10 = 10 ^ dpl10 88 var lr10 = biFromNumber(1000000000000000); 89 90 function BigInt(flag) 91 { 92 if (typeof flag == "boolean" && flag == true) { 93 this.digits = null; 94 } 95 else { 96 this.digits = ZERO_ARRAY.slice(0); 97 } 98 this.isNeg = false; 99 } 100 101 function biFromDecimal(s) 102 { 103 var isNeg = s.charAt(0) == '-'; 104 var i = isNeg ? 1 : 0; 105 var result; 106 // Skip leading zeros. 107 while (i < s.length && s.charAt(i) == '0') ++i; 108 if (i == s.length) { 109 result = new BigInt(); 110 } 111 else { 112 var digitCount = s.length - i; 113 var fgl = digitCount % dpl10; 114 if (fgl == 0) fgl = dpl10; 115 result = biFromNumber(Number(s.substr(i, fgl))); 116 i += fgl; 117 while (i < s.length) { 118 result = biAdd(biMultiply(result, lr10), 119 biFromNumber(Number(s.substr(i, dpl10)))); 120 i += dpl10; 121 } 122 result.isNeg = isNeg; 123 } 124 return result; 125 } 126 127 function biCopy(bi) 128 { 129 var result = new BigInt(true); 130 result.digits = bi.digits.slice(0); 131 result.isNeg = bi.isNeg; 132 return result; 133 } 134 135 function biFromNumber(i) 136 { 137 var result = new BigInt(); 138 result.isNeg = i < 0; 139 i = Math.abs(i); 140 var j = 0; 141 while (i > 0) { 142 result.digits[j++] = i & maxDigitVal; 143 i = Math.floor(i / biRadix); 144 } 145 return result; 146 } 147 148 function reverseStr(s) 149 { 150 var result = ""; 151 for (var i = s.length - 1; i > -1; --i) { 152 result += s.charAt(i); 153 } 154 return result; 155 } 156 157 var hexatrigesimalToChar = new Array( 158 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 159 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 160 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 161 'u', 'v', 'w', 'x', 'y', 'z' 162 ); 163 164 function biToString(x, radix) 165 // 2 <= radix <= 36 166 { 167 var b = new BigInt(); 168 b.digits[0] = radix; 169 var qr = biDivideModulo(x, b); 170 var result = hexatrigesimalToChar[qr[1].digits[0]]; 171 while (biCompare(qr[0], bigZero) == 1) { 172 qr = biDivideModulo(qr[0], b); 173 digit = qr[1].digits[0]; 174 result += hexatrigesimalToChar[qr[1].digits[0]]; 175 } 176 return (x.isNeg ? "-" : "") + reverseStr(result); 177 } 178 179 function biToDecimal(x) 180 { 181 var b = new BigInt(); 182 b.digits[0] = 10; 183 var qr = biDivideModulo(x, b); 184 var result = String(qr[1].digits[0]); 185 while (biCompare(qr[0], bigZero) == 1) { 186 qr = biDivideModulo(qr[0], b); 187 result += String(qr[1].digits[0]); 188 } 189 return (x.isNeg ? "-" : "") + reverseStr(result); 190 } 191 192 var hexToChar = new Array('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 193 'a', 'b', 'c', 'd', 'e', 'f'); 194 195 function digitToHex(n) 196 { 197 var mask = 0xf; 198 var result = ""; 199 for (i = 0; i < 4; ++i) { 200 result += hexToChar[n & mask]; 201 n >>>= 4; 202 } 203 return reverseStr(result); 204 } 205 206 function biToHex(x) 207 { 208 var result = ""; 209 var n = biHighIndex(x); 210 for (var i = biHighIndex(x); i > -1; --i) { 211 result += digitToHex(x.digits[i]); 212 } 213 return result; 214 } 215 216 function charToHex(c) 217 { 218 var ZERO = 48; 219 var NINE = ZERO + 9; 220 var littleA = 97; 221 var littleZ = littleA + 25; 222 var bigA = 65; 223 var bigZ = 65 + 25; 224 var result; 225 226 if (c >= ZERO && c <= NINE) { 227 result = c - ZERO; 228 } else if (c >= bigA && c <= bigZ) { 229 result = 10 + c - bigA; 230 } else if (c >= littleA && c <= littleZ) { 231 result = 10 + c - littleA; 232 } else { 233 result = 0; 234 } 235 return result; 236 } 237 238 function hexToDigit(s) 239 { 240 var result = 0; 241 var sl = Math.min(s.length, 4); 242 for (var i = 0; i < sl; ++i) { 243 result <<= 4; 244 result |= charToHex(s.charCodeAt(i)) 245 } 246 return result; 247 } 248 249 function biFromHex(s) 250 { 251 var result = new BigInt(); 252 var sl = s.length; 253 for (var i = sl, j = 0; i > 0; i -= 4, ++j) { 254 result.digits[j] = hexToDigit(s.substr(Math.max(i - 4, 0), Math.min(i, 4))); 255 } 256 return result; 257 } 258 259 function biFromString(s, radix) 260 { 261 var isNeg = s.charAt(0) == '-'; 262 var istop = isNeg ? 1 : 0; 263 var result = new BigInt(); 264 var place = new BigInt(); 265 place.digits[0] = 1; // radix^0 266 for (var i = s.length - 1; i >= istop; i--) { 267 var c = s.charCodeAt(i); 268 var digit = charToHex(c); 269 var biDigit = biMultiplyDigit(place, digit); 270 result = biAdd(result, biDigit); 271 place = biMultiplyDigit(place, radix); 272 } 273 result.isNeg = isNeg; 274 return result; 275 } 276 277 function biDump(b) 278 { 279 return (b.isNeg ? "-" : "") + b.digits.join(" "); 280 } 281 282 function biAdd(x, y) 283 { 284 var result; 285 286 if (x.isNeg != y.isNeg) { 287 y.isNeg = !y.isNeg; 288 result = biSubtract(x, y); 289 y.isNeg = !y.isNeg; 290 } 291 else { 292 result = new BigInt(); 293 var c = 0; 294 var n; 295 for (var i = 0; i < x.digits.length; ++i) { 296 n = x.digits[i] + y.digits[i] + c; 297 result.digits[i] = n % biRadix; 298 c = Number(n >= biRadix); 299 } 300 result.isNeg = x.isNeg; 301 } 302 return result; 303 } 304 305 function biSubtract(x, y) 306 { 307 var result; 308 if (x.isNeg != y.isNeg) { 309 y.isNeg = !y.isNeg; 310 result = biAdd(x, y); 311 y.isNeg = !y.isNeg; 312 } else { 313 result = new BigInt(); 314 var n, c; 315 c = 0; 316 for (var i = 0; i < x.digits.length; ++i) { 317 n = x.digits[i] - y.digits[i] + c; 318 result.digits[i] = n % biRadix; 319 // Stupid non-conforming modulus operation. 320 if (result.digits[i] < 0) result.digits[i] += biRadix; 321 c = 0 - Number(n < 0); 322 } 323 // Fix up the negative sign, if any. 324 if (c == -1) { 325 c = 0; 326 for (var i = 0; i < x.digits.length; ++i) { 327 n = 0 - result.digits[i] + c; 328 result.digits[i] = n % biRadix; 329 // Stupid non-conforming modulus operation. 330 if (result.digits[i] < 0) result.digits[i] += biRadix; 331 c = 0 - Number(n < 0); 332 } 333 // Result is opposite sign of arguments. 334 result.isNeg = !x.isNeg; 335 } else { 336 // Result is same sign. 337 result.isNeg = x.isNeg; 338 } 339 } 340 return result; 341 } 342 343 function biHighIndex(x) 344 { 345 var result = x.digits.length - 1; 346 while (result > 0 && x.digits[result] == 0) --result; 347 return result; 348 } 349 350 function biNumBits(x) 351 { 352 var n = biHighIndex(x); 353 var d = x.digits[n]; 354 var m = (n + 1) * bitsPerDigit; 355 var result; 356 for (result = m; result > m - bitsPerDigit; --result) { 357 if ((d & 0x8000) != 0) break; 358 d <<= 1; 359 } 360 return result; 361 } 362 363 function biMultiply(x, y) 364 { 365 var result = new BigInt(); 366 var c; 367 var n = biHighIndex(x); 368 var t = biHighIndex(y); 369 var u, uv, k; 370 371 for (var i = 0; i <= t; ++i) { 372 c = 0; 373 k = i; 374 for (j = 0; j <= n; ++j, ++k) { 375 uv = result.digits[k] + x.digits[j] * y.digits[i] + c; 376 result.digits[k] = uv & maxDigitVal; 377 c = uv >>> biRadixBits; 378 //c = Math.floor(uv / biRadix); 379 } 380 result.digits[i + n + 1] = c; 381 } 382 // Someone give me a logical xor, please. 383 result.isNeg = x.isNeg != y.isNeg; 384 return result; 385 } 386 387 function biMultiplyDigit(x, y) 388 { 389 var n, c, uv; 390 391 result = new BigInt(); 392 n = biHighIndex(x); 393 c = 0; 394 for (var j = 0; j <= n; ++j) { 395 uv = result.digits[j] + x.digits[j] * y + c; 396 result.digits[j] = uv & maxDigitVal; 397 c = uv >>> biRadixBits; 398 //c = Math.floor(uv / biRadix); 399 } 400 result.digits[1 + n] = c; 401 return result; 402 } 403 404 function arrayCopy(src, srcStart, dest, destStart, n) 405 { 406 var m = Math.min(srcStart + n, src.length); 407 for (var i = srcStart, j = destStart; i < m; ++i, ++j) { 408 dest[j] = src[i]; 409 } 410 } 411 412 var highBitMasks = new Array(0x0000, 0x8000, 0xC000, 0xE000, 0xF000, 0xF800, 413 0xFC00, 0xFE00, 0xFF00, 0xFF80, 0xFFC0, 0xFFE0, 414 0xFFF0, 0xFFF8, 0xFFFC, 0xFFFE, 0xFFFF); 415 416 function biShiftLeft(x, n) 417 { 418 var digitCount = Math.floor(n / bitsPerDigit); 419 var result = new BigInt(); 420 arrayCopy(x.digits, 0, result.digits, digitCount, 421 result.digits.length - digitCount); 422 var bits = n % bitsPerDigit; 423 var rightBits = bitsPerDigit - bits; 424 for (var i = result.digits.length - 1, i1 = i - 1; i > 0; --i, --i1) { 425 result.digits[i] = ((result.digits[i] << bits) & maxDigitVal) | 426 ((result.digits[i1] & highBitMasks[bits]) >>> 427 (rightBits)); 428 } 429 result.digits[0] = ((result.digits[i] << bits) & maxDigitVal); 430 result.isNeg = x.isNeg; 431 return result; 432 } 433 434 var lowBitMasks = new Array(0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F, 435 0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF, 436 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF); 437 438 function biShiftRight(x, n) 439 { 440 var digitCount = Math.floor(n / bitsPerDigit); 441 var result = new BigInt(); 442 arrayCopy(x.digits, digitCount, result.digits, 0, 443 x.digits.length - digitCount); 444 var bits = n % bitsPerDigit; 445 var leftBits = bitsPerDigit - bits; 446 for (var i = 0, i1 = i + 1; i < result.digits.length - 1; ++i, ++i1) { 447 result.digits[i] = (result.digits[i] >>> bits) | 448 ((result.digits[i1] & lowBitMasks[bits]) << leftBits); 449 } 450 result.digits[result.digits.length - 1] >>>= bits; 451 result.isNeg = x.isNeg; 452 return result; 453 } 454 455 function biMultiplyByRadixPower(x, n) 456 { 457 var result = new BigInt(); 458 arrayCopy(x.digits, 0, result.digits, n, result.digits.length - n); 459 return result; 460 } 461 462 function biDivideByRadixPower(x, n) 463 { 464 var result = new BigInt(); 465 arrayCopy(x.digits, n, result.digits, 0, result.digits.length - n); 466 return result; 467 } 468 469 function biModuloByRadixPower(x, n) 470 { 471 var result = new BigInt(); 472 arrayCopy(x.digits, 0, result.digits, 0, n); 473 return result; 474 } 475 476 function biCompare(x, y) 477 { 478 if (x.isNeg != y.isNeg) { 479 return 1 - 2 * Number(x.isNeg); 480 } 481 for (var i = x.digits.length - 1; i >= 0; --i) { 482 if (x.digits[i] != y.digits[i]) { 483 if (x.isNeg) { 484 return 1 - 2 * Number(x.digits[i] > y.digits[i]); 485 } else { 486 return 1 - 2 * Number(x.digits[i] < y.digits[i]); 487 } 488 } 489 } 490 return 0; 491 } 492 493 function biDivideModulo(x, y) 494 { 495 var nb = biNumBits(x); 496 var tb = biNumBits(y); 497 var origYIsNeg = y.isNeg; 498 var q, r; 499 if (nb < tb) { 500 // |x| < |y| 501 if (x.isNeg) { 502 q = biCopy(bigOne); 503 q.isNeg = !y.isNeg; 504 x.isNeg = false; 505 y.isNeg = false; 506 r = biSubtract(y, x); 507 // Restore signs, 'cause they're references. 508 x.isNeg = true; 509 y.isNeg = origYIsNeg; 510 } else { 511 q = new BigInt(); 512 r = biCopy(x); 513 } 514 return new Array(q, r); 515 } 516 517 q = new BigInt(); 518 r = x; 519 520 // Normalize Y. 521 var t = Math.ceil(tb / bitsPerDigit) - 1; 522 var lambda = 0; 523 while (y.digits[t] < biHalfRadix) { 524 y = biShiftLeft(y, 1); 525 ++lambda; 526 ++tb; 527 t = Math.ceil(tb / bitsPerDigit) - 1; 528 } 529 // Shift r over to keep the quotient constant. We'll shift the 530 // remainder back at the end. 531 r = biShiftLeft(r, lambda); 532 nb += lambda; // Update the bit count for x. 533 var n = Math.ceil(nb / bitsPerDigit) - 1; 534 535 var b = biMultiplyByRadixPower(y, n - t); 536 while (biCompare(r, b) != -1) { 537 ++q.digits[n - t]; 538 r = biSubtract(r, b); 539 } 540 for (var i = n; i > t; --i) { 541 var ri = (i >= r.digits.length) ? 0 : r.digits[i]; 542 var ri1 = (i - 1 >= r.digits.length) ? 0 : r.digits[i - 1]; 543 var ri2 = (i - 2 >= r.digits.length) ? 0 : r.digits[i - 2]; 544 var yt = (t >= y.digits.length) ? 0 : y.digits[t]; 545 var yt1 = (t - 1 >= y.digits.length) ? 0 : y.digits[t - 1]; 546 if (ri == yt) { 547 q.digits[i - t - 1] = maxDigitVal; 548 } else { 549 q.digits[i - t - 1] = Math.floor((ri * biRadix + ri1) / yt); 550 } 551 552 var c1 = q.digits[i - t - 1] * ((yt * biRadix) + yt1); 553 var c2 = (ri * biRadixSquared) + ((ri1 * biRadix) + ri2); 554 while (c1 > c2) { 555 --q.digits[i - t - 1]; 556 c1 = q.digits[i - t - 1] * ((yt * biRadix) | yt1); 557 c2 = (ri * biRadix * biRadix) + ((ri1 * biRadix) + ri2); 558 } 559 560 b = biMultiplyByRadixPower(y, i - t - 1); 561 r = biSubtract(r, biMultiplyDigit(b, q.digits[i - t - 1])); 562 if (r.isNeg) { 563 r = biAdd(r, b); 564 --q.digits[i - t - 1]; 565 } 566 } 567 r = biShiftRight(r, lambda); 568 // Fiddle with the signs and stuff to make sure that 0 <= r < y. 569 q.isNeg = x.isNeg != origYIsNeg; 570 if (x.isNeg) { 571 if (origYIsNeg) { 572 q = biAdd(q, bigOne); 573 } else { 574 q = biSubtract(q, bigOne); 575 } 576 y = biShiftRight(y, lambda); 577 r = biSubtract(y, r); 578 } 579 // Check for the unbelievably stupid degenerate case of r == -0. 580 if (r.digits[0] == 0 && biHighIndex(r) == 0) r.isNeg = false; 581 582 return new Array(q, r); 583 } 584 585 function biDivide(x, y) 586 { 587 return biDivideModulo(x, y)[0]; 588 } 589 590 function biModulo(x, y) 591 { 592 return biDivideModulo(x, y)[1]; 593 } 594 595 function biMultiplyMod(x, y, m) 596 { 597 return biModulo(biMultiply(x, y), m); 598 } 599 600 function biPow(x, y) 601 { 602 var result = bigOne; 603 var a = x; 604 while (true) { 605 if ((y & 1) != 0) result = biMultiply(result, a); 606 y >>= 1; 607 if (y == 0) break; 608 a = biMultiply(a, a); 609 } 610 return result; 611 } 612 613 function biPowMod(x, y, m) 614 { 615 var result = bigOne; 616 var a = x; 617 var k = y; 618 while (true) { 619 if ((k.digits[0] & 1) != 0) result = biMultiplyMod(result, a, m); 620 k = biShiftRight(k, 1); 621 if (k.digits[0] == 0 && biHighIndex(k) == 0) break; 622 a = biMultiplyMod(a, a, m); 623 } 624 return result; 625 }
3.Barrett
1 // BarrettMu, a class for performing Barrett modular reduction computations in 2 // JavaScript. 3 // 4 // Requires BigInt.js. 5 // 6 // Copyright 2004-2005 David Shapiro. 7 // 8 // You may use, re-use, abuse, copy, and modify this code to your liking, but 9 // please keep this header. 10 // 11 // Thanks! 12 // 13 // Dave Shapiro 14 // dave@ohdave.com 15 16 function BarrettMu(m) 17 { 18 this.modulus = biCopy(m); 19 this.k = biHighIndex(this.modulus) + 1; 20 var b2k = new BigInt(); 21 b2k.digits[2 * this.k] = 1; // b2k = b^(2k) 22 this.mu = biDivide(b2k, this.modulus); 23 this.bkplus1 = new BigInt(); 24 this.bkplus1.digits[this.k + 1] = 1; // bkplus1 = b^(k+1) 25 this.modulo = BarrettMu_modulo; 26 this.multiplyMod = BarrettMu_multiplyMod; 27 this.powMod = BarrettMu_powMod; 28 } 29 30 function BarrettMu_modulo(x) 31 { 32 var q1 = biDivideByRadixPower(x, this.k - 1); 33 var q2 = biMultiply(q1, this.mu); 34 var q3 = biDivideByRadixPower(q2, this.k + 1); 35 var r1 = biModuloByRadixPower(x, this.k + 1); 36 var r2term = biMultiply(q3, this.modulus); 37 var r2 = biModuloByRadixPower(r2term, this.k + 1); 38 var r = biSubtract(r1, r2); 39 if (r.isNeg) { 40 r = biAdd(r, this.bkplus1); 41 } 42 var rgtem = biCompare(r, this.modulus) >= 0; 43 while (rgtem) { 44 r = biSubtract(r, this.modulus); 45 rgtem = biCompare(r, this.modulus) >= 0; 46 } 47 return r; 48 } 49 50 function BarrettMu_multiplyMod(x, y) 51 { 52 /* 53 x = this.modulo(x); 54 y = this.modulo(y); 55 */ 56 var xy = biMultiply(x, y); 57 return this.modulo(xy); 58 } 59 60 function BarrettMu_powMod(x, y) 61 { 62 var result = new BigInt(); 63 result.digits[0] = 1; 64 var a = x; 65 var k = y; 66 while (true) { 67 if ((k.digits[0] & 1) != 0) result = this.multiplyMod(result, a); 68 k = biShiftRight(k, 1); 69 if (k.digits[0] == 0 && biHighIndex(k) == 0) break; 70 a = this.multiplyMod(a, a); 71 } 72 return result; 73 }
4.加密
1 public static string BytesToHexString(byte[] input) 2 { 3 StringBuilder hexString = new StringBuilder(64); 4 5 for (int i = 0; i < input.Length; i++) 6 { 7 hexString.Append(String.Format("{0:X2}", input[i])); 8 } 9 return hexString.ToString(); 10 }
1 private void init() 2 { 3 RSACryptoServiceProvider rsa = new RSACryptoServiceProvider(); 4 Session["private_key"] = rsa.ToXmlString(true); 5 RSAParameters parameter = rsa.ExportParameters(true); 6 ViewData["strPublicKeyExponent"] = LoginPasswordHelp.BytesToHexString(parameter.Exponent); 7 ViewData["strPublicKeyModulus"] = LoginPasswordHelp.BytesToHexString(parameter.Modulus); 8 }
1 setMaxDigits(129);//BigInt 2 var key = new RSAKeyPair('<%= Html.Encode(ViewData["strPublicKeyExponent"])%>', "", '<%= Html.Encode(ViewData["strPublicKeyModulus"])%>');//RSA 3 var pwdRtn = encryptedString(key, pwd);//RSA
5.后台解密
1 //转换为byte[] 2 public static byte[] HexStringToBytes(string hex) 3 { 4 if (hex.Length == 0) 5 { 6 return new byte[] { 0 }; 7 } 8 9 if (hex.Length % 2 == 1) 10 { 11 hex = "0" + hex; 12 } 13 14 byte[] result = new byte[hex.Length / 2]; 15 16 for (int i = 0; i < hex.Length / 2; i++) 17 { 18 result[i] = byte.Parse(hex.Substring(2 * i, 2), System.Globalization.NumberStyles.AllowHexSpecifier); 19 } 20 21 return result; 22 } 23 24 25 string pwd = ""; 26 try 27 { 28 ////解密 29 string strPwdToDecrypt = Request["pwd"]; 30 RSACryptoServiceProvider rsa = new RSACryptoServiceProvider(); 31 rsa.FromXmlString((string)Session["private_key"]); 32 byte[] result = rsa.Decrypt(LoginPasswordHelp.HexStringToBytes(strPwdToDecrypt), false); 33 System.Text.ASCIIEncoding enc = new ASCIIEncoding(); 34 pwd = enc.GetString(result); 35 } 36 catch (Exception ex) 37 { 38 HX.Common.Platform.Log(LogLevel.Error, ex); 39 string errorMsg = lang == "en" ? "Login session is overdue, please reload it again!" : "登录会话已过期,请刷新后再试！"; 40 return Json(new { success = false, msg = errorMsg }); 41 }