diff options
Diffstat (limited to 'ext/node/polyfills/_crypto')
43 files changed, 7824 insertions, 0 deletions
diff --git a/ext/node/polyfills/_crypto/crypto_browserify/README.md b/ext/node/polyfills/_crypto/crypto_browserify/README.md new file mode 100644 index 000000000..f618a177b --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/README.md @@ -0,0 +1,2 @@ +This directory contains the libraries ported from +[crypto-browserify](https://github.com/crypto-browserify) organization. diff --git a/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/base/buffer.js b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/base/buffer.js new file mode 100644 index 000000000..cb01476cd --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/base/buffer.js @@ -0,0 +1,167 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Fedor Indutny. All rights reserved. MIT license. + +import { Reporter } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/base/reporter.js"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +export function DecoderBuffer(base, options) { + Reporter.call(this, options); + if (!Buffer.isBuffer(base)) { + this.error("Input not Buffer"); + return; + } + + this.base = base; + this.offset = 0; + this.length = base.length; +} +// inherits(DecoderBuffer, Reporter); +DecoderBuffer.prototype = Object.create(Reporter.prototype, { + constructor: { + value: DecoderBuffer, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +DecoderBuffer.isDecoderBuffer = function isDecoderBuffer(data) { + if (data instanceof DecoderBuffer) { + return true; + } + + // Or accept compatible API + const isCompatible = typeof data === "object" && + Buffer.isBuffer(data.base) && + data.constructor.name === "DecoderBuffer" && + typeof data.offset === "number" && + typeof data.length === "number" && + typeof data.save === "function" && + typeof data.restore === "function" && + typeof data.isEmpty === "function" && + typeof data.readUInt8 === "function" && + typeof data.skip === "function" && + typeof data.raw === "function"; + + return isCompatible; +}; + +DecoderBuffer.prototype.save = function save() { + return { offset: this.offset, reporter: Reporter.prototype.save.call(this) }; +}; + +DecoderBuffer.prototype.restore = function restore(save) { + // Return skipped data + const res = new DecoderBuffer(this.base); + res.offset = save.offset; + res.length = this.offset; + + this.offset = save.offset; + Reporter.prototype.restore.call(this, save.reporter); + + return res; +}; + +DecoderBuffer.prototype.isEmpty = function isEmpty() { + return this.offset === this.length; +}; + +DecoderBuffer.prototype.readUInt8 = function readUInt8(fail) { + if (this.offset + 1 <= this.length) { + return this.base.readUInt8(this.offset++, true); + } else { + return this.error(fail || "DecoderBuffer overrun"); + } +}; + +DecoderBuffer.prototype.skip = function skip(bytes, fail) { + if (!(this.offset + bytes <= this.length)) { + return this.error(fail || "DecoderBuffer overrun"); + } + + const res = new DecoderBuffer(this.base); + + // Share reporter state + res._reporterState = this._reporterState; + + res.offset = this.offset; + res.length = this.offset + bytes; + this.offset += bytes; + return res; +}; + +DecoderBuffer.prototype.raw = function raw(save) { + return this.base.slice(save ? save.offset : this.offset, this.length); +}; + +export function EncoderBuffer(value, reporter) { + if (Array.isArray(value)) { + this.length = 0; + this.value = value.map(function (item) { + if (!EncoderBuffer.isEncoderBuffer(item)) { + item = new EncoderBuffer(item, reporter); + } + this.length += item.length; + return item; + }, this); + } else if (typeof value === "number") { + if (!(0 <= value && value <= 0xff)) { + return reporter.error("non-byte EncoderBuffer value"); + } + this.value = value; + this.length = 1; + } else if (typeof value === "string") { + this.value = value; + this.length = Buffer.byteLength(value); + } else if (Buffer.isBuffer(value)) { + this.value = value; + this.length = value.length; + } else { + return reporter.error("Unsupported type: " + typeof value); + } +} + +EncoderBuffer.isEncoderBuffer = function isEncoderBuffer(data) { + if (data instanceof EncoderBuffer) { + return true; + } + + // Or accept compatible API + const isCompatible = typeof data === "object" && + data.constructor.name === "EncoderBuffer" && + typeof data.length === "number" && + typeof data.join === "function"; + + return isCompatible; +}; + +EncoderBuffer.prototype.join = function join(out, offset) { + if (!out) { + out = Buffer.alloc(this.length); + } + if (!offset) { + offset = 0; + } + + if (this.length === 0) { + return out; + } + + if (Array.isArray(this.value)) { + this.value.forEach(function (item) { + item.join(out, offset); + offset += item.length; + }); + } else { + if (typeof this.value === "number") { + out[offset] = this.value; + } else if (typeof this.value === "string") { + out.write(this.value, offset); + } else if (Buffer.isBuffer(this.value)) { + this.value.copy(out, offset); + } + offset += this.length; + } + + return out; +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/base/node.js b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/base/node.js new file mode 100644 index 000000000..027778155 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/base/node.js @@ -0,0 +1,734 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Fedor Indutny. All rights reserved. MIT license. + +import { Reporter } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/base/reporter.js"; +import { + DecoderBuffer, + EncoderBuffer, +} from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/base/buffer.js"; +import { assert } from "internal:deno_node/polyfills/_util/asserts.ts"; + +// Supported tags +const tags = [ + "seq", + "seqof", + "set", + "setof", + "objid", + "bool", + "gentime", + "utctime", + "null_", + "enum", + "int", + "objDesc", + "bitstr", + "bmpstr", + "charstr", + "genstr", + "graphstr", + "ia5str", + "iso646str", + "numstr", + "octstr", + "printstr", + "t61str", + "unistr", + "utf8str", + "videostr", +]; + +// Public methods list +const methods = [ + "key", + "obj", + "use", + "optional", + "explicit", + "implicit", + "def", + "choice", + "any", + "contains", +].concat(tags); + +// Overrided methods list +const overrided = [ + "_peekTag", + "_decodeTag", + "_use", + "_decodeStr", + "_decodeObjid", + "_decodeTime", + "_decodeNull", + "_decodeInt", + "_decodeBool", + "_decodeList", + + "_encodeComposite", + "_encodeStr", + "_encodeObjid", + "_encodeTime", + "_encodeNull", + "_encodeInt", + "_encodeBool", +]; + +export function Node(enc, parent, name) { + const state = {}; + this._baseState = state; + + state.name = name; + state.enc = enc; + + state.parent = parent || null; + state.children = null; + + // State + state.tag = null; + state.args = null; + state.reverseArgs = null; + state.choice = null; + state.optional = false; + state.any = false; + state.obj = false; + state.use = null; + state.useDecoder = null; + state.key = null; + state["default"] = null; + state.explicit = null; + state.implicit = null; + state.contains = null; + + // Should create new instance on each method + if (!state.parent) { + state.children = []; + this._wrap(); + } +} + +const stateProps = [ + "enc", + "parent", + "children", + "tag", + "args", + "reverseArgs", + "choice", + "optional", + "any", + "obj", + "use", + "alteredUse", + "key", + "default", + "explicit", + "implicit", + "contains", +]; + +Node.prototype.clone = function clone() { + const state = this._baseState; + const cstate = {}; + stateProps.forEach(function (prop) { + cstate[prop] = state[prop]; + }); + const res = new this.constructor(cstate.parent); + res._baseState = cstate; + return res; +}; + +Node.prototype._wrap = function wrap() { + const state = this._baseState; + methods.forEach(function (method) { + this[method] = function _wrappedMethod() { + const clone = new this.constructor(this); + state.children.push(clone); + return clone[method].apply(clone, arguments); + }; + }, this); +}; + +Node.prototype._init = function init(body) { + const state = this._baseState; + + assert(state.parent === null); + body.call(this); + + // Filter children + state.children = state.children.filter(function (child) { + return child._baseState.parent === this; + }, this); + assert(state.children.length === 1, "Root node can have only one child"); +}; + +Node.prototype._useArgs = function useArgs(args) { + const state = this._baseState; + + // Filter children and args + const children = args.filter(function (arg) { + return arg instanceof this.constructor; + }, this); + args = args.filter(function (arg) { + return !(arg instanceof this.constructor); + }, this); + + if (children.length !== 0) { + assert(state.children === null); + state.children = children; + + // Replace parent to maintain backward link + children.forEach(function (child) { + child._baseState.parent = this; + }, this); + } + if (args.length !== 0) { + assert(state.args === null); + state.args = args; + state.reverseArgs = args.map(function (arg) { + if (typeof arg !== "object" || arg.constructor !== Object) { + return arg; + } + + const res = {}; + Object.keys(arg).forEach(function (key) { + if (key == (key | 0)) { + key |= 0; + } + const value = arg[key]; + res[value] = key; + }); + return res; + }); + } +}; + +// +// Overrided methods +// + +overrided.forEach(function (method) { + Node.prototype[method] = function _overrided() { + const state = this._baseState; + throw new Error(method + " not implemented for encoding: " + state.enc); + }; +}); + +// +// Public methods +// + +tags.forEach(function (tag) { + Node.prototype[tag] = function _tagMethod() { + const state = this._baseState; + const args = Array.prototype.slice.call(arguments); + + assert(state.tag === null); + state.tag = tag; + + this._useArgs(args); + + return this; + }; +}); + +Node.prototype.use = function use(item) { + assert(item); + const state = this._baseState; + + assert(state.use === null); + state.use = item; + + return this; +}; + +Node.prototype.optional = function optional() { + const state = this._baseState; + + state.optional = true; + + return this; +}; + +Node.prototype.def = function def(val) { + const state = this._baseState; + + assert(state["default"] === null); + state["default"] = val; + state.optional = true; + + return this; +}; + +Node.prototype.explicit = function explicit(num) { + const state = this._baseState; + + assert(state.explicit === null && state.implicit === null); + state.explicit = num; + + return this; +}; + +Node.prototype.implicit = function implicit(num) { + const state = this._baseState; + + assert(state.explicit === null && state.implicit === null); + state.implicit = num; + + return this; +}; + +Node.prototype.obj = function obj() { + const state = this._baseState; + const args = Array.prototype.slice.call(arguments); + + state.obj = true; + + if (args.length !== 0) { + this._useArgs(args); + } + + return this; +}; + +Node.prototype.key = function key(newKey) { + const state = this._baseState; + + assert(state.key === null); + state.key = newKey; + + return this; +}; + +Node.prototype.any = function any() { + const state = this._baseState; + + state.any = true; + + return this; +}; + +Node.prototype.choice = function choice(obj) { + const state = this._baseState; + + assert(state.choice === null); + state.choice = obj; + this._useArgs( + Object.keys(obj).map(function (key) { + return obj[key]; + }), + ); + + return this; +}; + +Node.prototype.contains = function contains(item) { + const state = this._baseState; + + assert(state.use === null); + state.contains = item; + + return this; +}; + +// +// Decoding +// + +Node.prototype._decode = function decode(input, options) { + const state = this._baseState; + + // Decode root node + if (state.parent === null) { + return input.wrapResult(state.children[0]._decode(input, options)); + } + + let result = state["default"]; + let present = true; + + let prevKey = null; + if (state.key !== null) { + prevKey = input.enterKey(state.key); + } + + // Check if tag is there + if (state.optional) { + let tag = null; + if (state.explicit !== null) { + tag = state.explicit; + } else if (state.implicit !== null) { + tag = state.implicit; + } else if (state.tag !== null) { + tag = state.tag; + } + + if (tag === null && !state.any) { + // Trial and Error + const save = input.save(); + try { + if (state.choice === null) { + this._decodeGeneric(state.tag, input, options); + } else { + this._decodeChoice(input, options); + } + present = true; + } catch (_e) { + present = false; + } + input.restore(save); + } else { + present = this._peekTag(input, tag, state.any); + + if (input.isError(present)) { + return present; + } + } + } + + // Push object on stack + let prevObj; + if (state.obj && present) { + prevObj = input.enterObject(); + } + + if (present) { + // Unwrap explicit values + if (state.explicit !== null) { + const explicit = this._decodeTag(input, state.explicit); + if (input.isError(explicit)) { + return explicit; + } + input = explicit; + } + + const start = input.offset; + + // Unwrap implicit and normal values + if (state.use === null && state.choice === null) { + let save; + if (state.any) { + save = input.save(); + } + const body = this._decodeTag( + input, + state.implicit !== null ? state.implicit : state.tag, + state.any, + ); + if (input.isError(body)) { + return body; + } + + if (state.any) { + result = input.raw(save); + } else { + input = body; + } + } + + if (options && options.track && state.tag !== null) { + options.track(input.path(), start, input.length, "tagged"); + } + + if (options && options.track && state.tag !== null) { + options.track(input.path(), input.offset, input.length, "content"); + } + + // Select proper method for tag + if (state.any) { + // no-op + } else if (state.choice === null) { + result = this._decodeGeneric(state.tag, input, options); + } else { + result = this._decodeChoice(input, options); + } + + if (input.isError(result)) { + return result; + } + + // Decode children + if (!state.any && state.choice === null && state.children !== null) { + state.children.forEach(function decodeChildren(child) { + // NOTE: We are ignoring errors here, to let parser continue with other + // parts of encoded data + child._decode(input, options); + }); + } + + // Decode contained/encoded by schema, only in bit or octet strings + if (state.contains && (state.tag === "octstr" || state.tag === "bitstr")) { + const data = new DecoderBuffer(result); + result = this._getUse(state.contains, input._reporterState.obj) + ._decode(data, options); + } + } + + // Pop object + if (state.obj && present) { + result = input.leaveObject(prevObj); + } + + // Set key + if (state.key !== null && (result !== null || present === true)) { + input.leaveKey(prevKey, state.key, result); + } else if (prevKey !== null) { + input.exitKey(prevKey); + } + + return result; +}; + +Node.prototype._decodeGeneric = function decodeGeneric(tag, input, options) { + const state = this._baseState; + + if (tag === "seq" || tag === "set") { + return null; + } + if (tag === "seqof" || tag === "setof") { + return this._decodeList(input, tag, state.args[0], options); + } else if (/str$/.test(tag)) { + return this._decodeStr(input, tag, options); + } else if (tag === "objid" && state.args) { + return this._decodeObjid(input, state.args[0], state.args[1], options); + } else if (tag === "objid") { + return this._decodeObjid(input, null, null, options); + } else if (tag === "gentime" || tag === "utctime") { + return this._decodeTime(input, tag, options); + } else if (tag === "null_") { + return this._decodeNull(input, options); + } else if (tag === "bool") { + return this._decodeBool(input, options); + } else if (tag === "objDesc") { + return this._decodeStr(input, tag, options); + } else if (tag === "int" || tag === "enum") { + return this._decodeInt(input, state.args && state.args[0], options); + } + + if (state.use !== null) { + return this._getUse(state.use, input._reporterState.obj) + ._decode(input, options); + } else { + return input.error("unknown tag: " + tag); + } +}; + +Node.prototype._getUse = function _getUse(entity, obj) { + const state = this._baseState; + // Create altered use decoder if implicit is set + state.useDecoder = this._use(entity, obj); + assert(state.useDecoder._baseState.parent === null); + state.useDecoder = state.useDecoder._baseState.children[0]; + if (state.implicit !== state.useDecoder._baseState.implicit) { + state.useDecoder = state.useDecoder.clone(); + state.useDecoder._baseState.implicit = state.implicit; + } + return state.useDecoder; +}; + +Node.prototype._decodeChoice = function decodeChoice(input, options) { + const state = this._baseState; + let result = null; + let match = false; + + Object.keys(state.choice).some(function (key) { + const save = input.save(); + const node = state.choice[key]; + try { + const value = node._decode(input, options); + if (input.isError(value)) { + return false; + } + + result = { type: key, value: value }; + match = true; + } catch (_e) { + input.restore(save); + return false; + } + return true; + }, this); + + if (!match) { + return input.error("Choice not matched"); + } + + return result; +}; + +// +// Encoding +// + +Node.prototype._createEncoderBuffer = function createEncoderBuffer(data) { + return new EncoderBuffer(data, this.reporter); +}; + +Node.prototype._encode = function encode(data, reporter, parent) { + const state = this._baseState; + if (state["default"] !== null && state["default"] === data) { + return; + } + + const result = this._encodeValue(data, reporter, parent); + if (result === undefined) { + return; + } + + if (this._skipDefault(result, reporter, parent)) { + return; + } + + return result; +}; + +Node.prototype._encodeValue = function encode(data, reporter, parent) { + const state = this._baseState; + + // Decode root node + if (state.parent === null) { + return state.children[0]._encode(data, reporter || new Reporter()); + } + + let result = null; + + // Set reporter to share it with a child class + this.reporter = reporter; + + // Check if data is there + if (state.optional && data === undefined) { + if (state["default"] !== null) { + data = state["default"]; + } else { + return; + } + } + + // Encode children first + let content = null; + let primitive = false; + if (state.any) { + // Anything that was given is translated to buffer + result = this._createEncoderBuffer(data); + } else if (state.choice) { + result = this._encodeChoice(data, reporter); + } else if (state.contains) { + content = this._getUse(state.contains, parent)._encode(data, reporter); + primitive = true; + } else if (state.children) { + content = state.children.map(function (child) { + if (child._baseState.tag === "null_") { + return child._encode(null, reporter, data); + } + + if (child._baseState.key === null) { + return reporter.error("Child should have a key"); + } + const prevKey = reporter.enterKey(child._baseState.key); + + if (typeof data !== "object") { + return reporter.error("Child expected, but input is not object"); + } + + const res = child._encode(data[child._baseState.key], reporter, data); + reporter.leaveKey(prevKey); + + return res; + }, this).filter(function (child) { + return child; + }); + content = this._createEncoderBuffer(content); + } else { + if (state.tag === "seqof" || state.tag === "setof") { + // TODO(indutny): this should be thrown on DSL level + if (!(state.args && state.args.length === 1)) { + return reporter.error("Too many args for : " + state.tag); + } + + if (!Array.isArray(data)) { + return reporter.error("seqof/setof, but data is not Array"); + } + + const child = this.clone(); + child._baseState.implicit = null; + content = this._createEncoderBuffer(data.map(function (item) { + const state = this._baseState; + + return this._getUse(state.args[0], data)._encode(item, reporter); + }, child)); + } else if (state.use !== null) { + result = this._getUse(state.use, parent)._encode(data, reporter); + } else { + content = this._encodePrimitive(state.tag, data); + primitive = true; + } + } + + // Encode data itself + if (!state.any && state.choice === null) { + const tag = state.implicit !== null ? state.implicit : state.tag; + const cls = state.implicit === null ? "universal" : "context"; + + if (tag === null) { + if (state.use === null) { + reporter.error("Tag could be omitted only for .use()"); + } + } else { + if (state.use === null) { + result = this._encodeComposite(tag, primitive, cls, content); + } + } + } + + // Wrap in explicit + if (state.explicit !== null) { + result = this._encodeComposite(state.explicit, false, "context", result); + } + + return result; +}; + +Node.prototype._encodeChoice = function encodeChoice(data, reporter) { + const state = this._baseState; + + const node = state.choice[data.type]; + if (!node) { + assert( + false, + data.type + " not found in " + + JSON.stringify(Object.keys(state.choice)), + ); + } + return node._encode(data.value, reporter); +}; + +Node.prototype._encodePrimitive = function encodePrimitive(tag, data) { + const state = this._baseState; + + if (/str$/.test(tag)) { + return this._encodeStr(data, tag); + } else if (tag === "objid" && state.args) { + return this._encodeObjid(data, state.reverseArgs[0], state.args[1]); + } else if (tag === "objid") { + return this._encodeObjid(data, null, null); + } else if (tag === "gentime" || tag === "utctime") { + return this._encodeTime(data, tag); + } else if (tag === "null_") { + return this._encodeNull(); + } else if (tag === "int" || tag === "enum") { + return this._encodeInt(data, state.args && state.reverseArgs[0]); + } else if (tag === "bool") { + return this._encodeBool(data); + } else if (tag === "objDesc") { + return this._encodeStr(data, tag); + } else { + throw new Error("Unsupported tag: " + tag); + } +}; + +Node.prototype._isNumstr = function isNumstr(str) { + return /^[0-9 ]*$/.test(str); +}; + +Node.prototype._isPrintstr = function isPrintstr(str) { + return /^[A-Za-z0-9 '()+,-./:=?]*$/.test(str); +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/base/reporter.js b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/base/reporter.js new file mode 100644 index 000000000..509f6c5b3 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/base/reporter.js @@ -0,0 +1,138 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Fedor Indutny. All rights reserved. MIT license. + +export function Reporter(options) { + this._reporterState = { + obj: null, + path: [], + options: options || {}, + errors: [], + }; +} + +Reporter.prototype.isError = function isError(obj) { + return obj instanceof ReporterError; +}; + +Reporter.prototype.save = function save() { + const state = this._reporterState; + + return { obj: state.obj, pathLen: state.path.length }; +}; + +Reporter.prototype.restore = function restore(data) { + const state = this._reporterState; + + state.obj = data.obj; + state.path = state.path.slice(0, data.pathLen); +}; + +Reporter.prototype.enterKey = function enterKey(key) { + return this._reporterState.path.push(key); +}; + +Reporter.prototype.exitKey = function exitKey(index) { + const state = this._reporterState; + + state.path = state.path.slice(0, index - 1); +}; + +Reporter.prototype.leaveKey = function leaveKey(index, key, value) { + const state = this._reporterState; + + this.exitKey(index); + if (state.obj !== null) { + state.obj[key] = value; + } +}; + +Reporter.prototype.path = function path() { + return this._reporterState.path.join("/"); +}; + +Reporter.prototype.enterObject = function enterObject() { + const state = this._reporterState; + + const prev = state.obj; + state.obj = {}; + return prev; +}; + +Reporter.prototype.leaveObject = function leaveObject(prev) { + const state = this._reporterState; + + const now = state.obj; + state.obj = prev; + return now; +}; + +Reporter.prototype.error = function error(msg) { + let err; + const state = this._reporterState; + + const inherited = msg instanceof ReporterError; + if (inherited) { + err = msg; + } else { + err = new ReporterError( + state.path.map(function (elem) { + return "[" + JSON.stringify(elem) + "]"; + }).join(""), + msg.message || msg, + msg.stack, + ); + } + + if (!state.options.partial) { + throw err; + } + + if (!inherited) { + state.errors.push(err); + } + + return err; +}; + +Reporter.prototype.wrapResult = function wrapResult(result) { + const state = this._reporterState; + if (!state.options.partial) { + return result; + } + + return { + result: this.isError(result) ? null : result, + errors: state.errors, + }; +}; + +function ReporterError(path, msg) { + this.path = path; + this.rethrow(msg); +} +// inherits(ReporterError, Error); +ReporterError.prototype = Object.create(Error.prototype, { + constructor: { + value: ReporterError, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +ReporterError.prototype.rethrow = function rethrow(msg) { + this.message = msg + " at: " + (this.path || "(shallow)"); + if (Error.captureStackTrace) { + Error.captureStackTrace(this, ReporterError); + } + + if (!this.stack) { + try { + // IE only adds stack when thrown + throw new Error(this.message); + } catch (e) { + this.stack = e.stack; + } + } + return this; +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/constants/der.js b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/constants/der.js new file mode 100644 index 000000000..807a97864 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/constants/der.js @@ -0,0 +1,60 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Fedor Indutny. All rights reserved. MIT license. + +// Helper +function reverse(map) { + const res = {}; + + Object.keys(map).forEach(function (key) { + // Convert key to integer if it is stringified + if ((key | 0) == key) { + key = key | 0; + } + + const value = map[key]; + res[value] = key; + }); + + return res; +} + +export const tagClass = { + 0: "universal", + 1: "application", + 2: "context", + 3: "private", +}; +export const tagClassByName = reverse(tagClass); + +export const tag = { + 0x00: "end", + 0x01: "bool", + 0x02: "int", + 0x03: "bitstr", + 0x04: "octstr", + 0x05: "null_", + 0x06: "objid", + 0x07: "objDesc", + 0x08: "external", + 0x09: "real", + 0x0a: "enum", + 0x0b: "embed", + 0x0c: "utf8str", + 0x0d: "relativeOid", + 0x10: "seq", + 0x11: "set", + 0x12: "numstr", + 0x13: "printstr", + 0x14: "t61str", + 0x15: "videostr", + 0x16: "ia5str", + 0x17: "utctime", + 0x18: "gentime", + 0x19: "graphstr", + 0x1a: "iso646str", + 0x1b: "genstr", + 0x1c: "unistr", + 0x1d: "charstr", + 0x1e: "bmpstr", +}; +export const tagByName = reverse(tag); diff --git a/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/decoders/der.js b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/decoders/der.js new file mode 100644 index 000000000..9ab811507 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/decoders/der.js @@ -0,0 +1,386 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Fedor Indutny. All rights reserved. MIT license. + +import bignum from "internal:deno_node/polyfills/_crypto/crypto_browserify/bn.js/bn.js"; +import { DecoderBuffer } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/base/buffer.js"; +import { Node } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/base/node.js"; +import * as der from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/constants/der.js"; + +export function DERDecoder(entity) { + this.enc = "der"; + this.name = entity.name; + this.entity = entity; + + // Construct base tree + this.tree = new DERNode(); + this.tree._init(entity.body); +} + +DERDecoder.prototype.decode = function decode(data, options) { + if (!DecoderBuffer.isDecoderBuffer(data)) { + data = new DecoderBuffer(data, options); + } + return this.tree._decode(data, options); +}; + +// Tree methods + +function DERNode(parent) { + Node.call(this, "der", parent); +} +// inherits(DERNode, Node); +DERNode.prototype = Object.create(Node.prototype, { + constructor: { + value: DERNode, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +DERNode.prototype._peekTag = function peekTag(buffer, tag, any) { + if (buffer.isEmpty()) { + return false; + } + + const state = buffer.save(); + const decodedTag = derDecodeTag(buffer, 'Failed to peek tag: "' + tag + '"'); + if (buffer.isError(decodedTag)) { + return decodedTag; + } + + buffer.restore(state); + + return decodedTag.tag === tag || decodedTag.tagStr === tag || + (decodedTag.tagStr + "of") === tag || any; +}; + +DERNode.prototype._decodeTag = function decodeTag(buffer, tag, any) { + const decodedTag = derDecodeTag( + buffer, + 'Failed to decode tag of "' + tag + '"', + ); + if (buffer.isError(decodedTag)) { + return decodedTag; + } + + let len = derDecodeLen( + buffer, + decodedTag.primitive, + 'Failed to get length of "' + tag + '"', + ); + + // Failure + if (buffer.isError(len)) { + return len; + } + + if ( + !any && + decodedTag.tag !== tag && + decodedTag.tagStr !== tag && + decodedTag.tagStr + "of" !== tag + ) { + return buffer.error('Failed to match tag: "' + tag + '"'); + } + + if (decodedTag.primitive || len !== null) { + return buffer.skip(len, 'Failed to match body of: "' + tag + '"'); + } + + // Indefinite length... find END tag + const state = buffer.save(); + const res = this._skipUntilEnd( + buffer, + 'Failed to skip indefinite length body: "' + this.tag + '"', + ); + if (buffer.isError(res)) { + return res; + } + + len = buffer.offset - state.offset; + buffer.restore(state); + return buffer.skip(len, 'Failed to match body of: "' + tag + '"'); +}; + +DERNode.prototype._skipUntilEnd = function skipUntilEnd(buffer, fail) { + for (;;) { + const tag = derDecodeTag(buffer, fail); + if (buffer.isError(tag)) { + return tag; + } + const len = derDecodeLen(buffer, tag.primitive, fail); + if (buffer.isError(len)) { + return len; + } + + let res; + if (tag.primitive || len !== null) { + res = buffer.skip(len); + } else { + res = this._skipUntilEnd(buffer, fail); + } + + // Failure + if (buffer.isError(res)) { + return res; + } + + if (tag.tagStr === "end") { + break; + } + } +}; + +DERNode.prototype._decodeList = function decodeList( + buffer, + _tag, + decoder, + options, +) { + const result = []; + while (!buffer.isEmpty()) { + const possibleEnd = this._peekTag(buffer, "end"); + if (buffer.isError(possibleEnd)) { + return possibleEnd; + } + + const res = decoder.decode(buffer, "der", options); + if (buffer.isError(res) && possibleEnd) { + break; + } + result.push(res); + } + return result; +}; + +DERNode.prototype._decodeStr = function decodeStr(buffer, tag) { + if (tag === "bitstr") { + const unused = buffer.readUInt8(); + if (buffer.isError(unused)) { + return unused; + } + return { unused: unused, data: buffer.raw() }; + } else if (tag === "bmpstr") { + const raw = buffer.raw(); + if (raw.length % 2 === 1) { + return buffer.error("Decoding of string type: bmpstr length mismatch"); + } + + let str = ""; + for (let i = 0; i < raw.length / 2; i++) { + str += String.fromCharCode(raw.readUInt16BE(i * 2)); + } + return str; + } else if (tag === "numstr") { + const numstr = buffer.raw().toString("ascii"); + if (!this._isNumstr(numstr)) { + return buffer.error( + "Decoding of string type: " + + "numstr unsupported characters", + ); + } + return numstr; + } else if (tag === "octstr") { + return buffer.raw(); + } else if (tag === "objDesc") { + return buffer.raw(); + } else if (tag === "printstr") { + const printstr = buffer.raw().toString("ascii"); + if (!this._isPrintstr(printstr)) { + return buffer.error( + "Decoding of string type: " + + "printstr unsupported characters", + ); + } + return printstr; + } else if (/str$/.test(tag)) { + return buffer.raw().toString(); + } else { + return buffer.error("Decoding of string type: " + tag + " unsupported"); + } +}; + +DERNode.prototype._decodeObjid = function decodeObjid( + buffer, + values, + relative, +) { + let result; + const identifiers = []; + let ident = 0; + let subident = 0; + while (!buffer.isEmpty()) { + subident = buffer.readUInt8(); + ident <<= 7; + ident |= subident & 0x7f; + if ((subident & 0x80) === 0) { + identifiers.push(ident); + ident = 0; + } + } + if (subident & 0x80) { + identifiers.push(ident); + } + + const first = (identifiers[0] / 40) | 0; + const second = identifiers[0] % 40; + + if (relative) { + result = identifiers; + } else { + result = [first, second].concat(identifiers.slice(1)); + } + + if (values) { + let tmp = values[result.join(" ")]; + if (tmp === undefined) { + tmp = values[result.join(".")]; + } + if (tmp !== undefined) { + result = tmp; + } + } + + return result; +}; + +DERNode.prototype._decodeTime = function decodeTime(buffer, tag) { + const str = buffer.raw().toString(); + + let year; + let mon; + let day; + let hour; + let min; + let sec; + if (tag === "gentime") { + year = str.slice(0, 4) | 0; + mon = str.slice(4, 6) | 0; + day = str.slice(6, 8) | 0; + hour = str.slice(8, 10) | 0; + min = str.slice(10, 12) | 0; + sec = str.slice(12, 14) | 0; + } else if (tag === "utctime") { + year = str.slice(0, 2) | 0; + mon = str.slice(2, 4) | 0; + day = str.slice(4, 6) | 0; + hour = str.slice(6, 8) | 0; + min = str.slice(8, 10) | 0; + sec = str.slice(10, 12) | 0; + if (year < 70) { + year = 2000 + year; + } else { + year = 1900 + year; + } + } else { + return buffer.error("Decoding " + tag + " time is not supported yet"); + } + + return Date.UTC(year, mon - 1, day, hour, min, sec, 0); +}; + +DERNode.prototype._decodeNull = function decodeNull() { + return null; +}; + +DERNode.prototype._decodeBool = function decodeBool(buffer) { + const res = buffer.readUInt8(); + if (buffer.isError(res)) { + return res; + } else { + return res !== 0; + } +}; + +DERNode.prototype._decodeInt = function decodeInt(buffer, values) { + // Bigint, return as it is (assume big endian) + const raw = buffer.raw(); + let res = new bignum(raw); + + if (values) { + res = values[res.toString(10)] || res; + } + + return res; +}; + +DERNode.prototype._use = function use(entity, obj) { + if (typeof entity === "function") { + entity = entity(obj); + } + return entity._getDecoder("der").tree; +}; + +// Utility methods + +function derDecodeTag(buf, fail) { + let tag = buf.readUInt8(fail); + if (buf.isError(tag)) { + return tag; + } + + const cls = der.tagClass[tag >> 6]; + const primitive = (tag & 0x20) === 0; + + // Multi-octet tag - load + if ((tag & 0x1f) === 0x1f) { + let oct = tag; + tag = 0; + while ((oct & 0x80) === 0x80) { + oct = buf.readUInt8(fail); + if (buf.isError(oct)) { + return oct; + } + + tag <<= 7; + tag |= oct & 0x7f; + } + } else { + tag &= 0x1f; + } + const tagStr = der.tag[tag]; + + return { + cls: cls, + primitive: primitive, + tag: tag, + tagStr: tagStr, + }; +} + +function derDecodeLen(buf, primitive, fail) { + let len = buf.readUInt8(fail); + if (buf.isError(len)) { + return len; + } + + // Indefinite form + if (!primitive && len === 0x80) { + return null; + } + + // Definite form + if ((len & 0x80) === 0) { + // Short form + return len; + } + + // Long form + const num = len & 0x7f; + if (num > 4) { + return buf.error("length octect is too long"); + } + + len = 0; + for (let i = 0; i < num; i++) { + len <<= 8; + const j = buf.readUInt8(fail); + if (buf.isError(j)) { + return j; + } + len |= j; + } + + return len; +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/decoders/pem.js b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/decoders/pem.js new file mode 100644 index 000000000..3dedfb293 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/decoders/pem.js @@ -0,0 +1,63 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Fedor Indutny. All rights reserved. MIT license. + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +import { DERDecoder } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/decoders/der.js"; + +export function PEMDecoder(entity) { + DERDecoder.call(this, entity); + this.enc = "pem"; +} +// inherits(PEMDecoder, DERDecoder); +PEMDecoder.prototype = Object.create(DERDecoder.prototype, { + constructor: { + value: PEMDecoder, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +PEMDecoder.prototype.decode = function decode(data, options) { + const lines = data.toString().split(/[\r\n]+/g); + + const label = options.label.toUpperCase(); + + const re = /^-----(BEGIN|END) ([^-]+)-----$/; + let start = -1; + let end = -1; + for (let i = 0; i < lines.length; i++) { + const match = lines[i].match(re); + if (match === null) { + continue; + } + + if (match[2] !== label) { + continue; + } + + if (start === -1) { + if (match[1] !== "BEGIN") { + break; + } + start = i; + } else { + if (match[1] !== "END") { + break; + } + end = i; + break; + } + } + if (start === -1 || end === -1) { + throw new Error("PEM section not found for: " + label); + } + + const base64 = lines.slice(start + 1, end).join(""); + // Remove excessive symbols + base64.replace(/[^a-z0-9+/=]+/gi, ""); + + const input = Buffer.from(base64, "base64"); + return DERDecoder.prototype.decode.call(this, input, options); +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/encoders/der.js b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/encoders/der.js new file mode 100644 index 000000000..3f03ef347 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/encoders/der.js @@ -0,0 +1,348 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Fedor Indutny. All rights reserved. MIT license. + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; +import { Node } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/base/node.js"; + +// Import DER constants +import * as der from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/constants/der.js"; + +export function DEREncoder(entity) { + this.enc = "der"; + this.name = entity.name; + this.entity = entity; + + // Construct base tree + this.tree = new DERNode(); + this.tree._init(entity.body); +} + +DEREncoder.prototype.encode = function encode(data, reporter) { + return this.tree._encode(data, reporter).join(); +}; + +// Tree methods + +function DERNode(parent) { + Node.call(this, "der", parent); +} +// inherits(DERNode, Node); +DERNode.prototype = Object.create(Node.prototype, { + constructor: { + value: DERNode, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +DERNode.prototype._encodeComposite = function encodeComposite( + tag, + primitive, + cls, + content, +) { + const encodedTag = encodeTag(tag, primitive, cls, this.reporter); + + // Short form + if (content.length < 0x80) { + const header = Buffer.alloc(2); + header[0] = encodedTag; + header[1] = content.length; + return this._createEncoderBuffer([header, content]); + } + + // Long form + // Count octets required to store length + let lenOctets = 1; + for (let i = content.length; i >= 0x100; i >>= 8) { + lenOctets++; + } + + const header = Buffer.alloc(1 + 1 + lenOctets); + header[0] = encodedTag; + header[1] = 0x80 | lenOctets; + + for (let i = 1 + lenOctets, j = content.length; j > 0; i--, j >>= 8) { + header[i] = j & 0xff; + } + + return this._createEncoderBuffer([header, content]); +}; + +DERNode.prototype._encodeStr = function encodeStr(str, tag) { + if (tag === "bitstr") { + return this._createEncoderBuffer([str.unused | 0, str.data]); + } else if (tag === "bmpstr") { + const buf = Buffer.alloc(str.length * 2); + for (let i = 0; i < str.length; i++) { + buf.writeUInt16BE(str.charCodeAt(i), i * 2); + } + return this._createEncoderBuffer(buf); + } else if (tag === "numstr") { + if (!this._isNumstr(str)) { + return this.reporter.error( + "Encoding of string type: numstr supports " + + "only digits and space", + ); + } + return this._createEncoderBuffer(str); + } else if (tag === "printstr") { + if (!this._isPrintstr(str)) { + return this.reporter.error( + "Encoding of string type: printstr supports " + + "only latin upper and lower case letters, " + + "digits, space, apostrophe, left and rigth " + + "parenthesis, plus sign, comma, hyphen, " + + "dot, slash, colon, equal sign, " + + "question mark", + ); + } + return this._createEncoderBuffer(str); + } else if (/str$/.test(tag)) { + return this._createEncoderBuffer(str); + } else if (tag === "objDesc") { + return this._createEncoderBuffer(str); + } else { + return this.reporter.error( + "Encoding of string type: " + tag + + " unsupported", + ); + } +}; + +DERNode.prototype._encodeObjid = function encodeObjid(id, values, relative) { + if (typeof id === "string") { + if (!values) { + return this.reporter.error("string objid given, but no values map found"); + } + // deno-lint-ignore no-prototype-builtins + if (!values.hasOwnProperty(id)) { + return this.reporter.error("objid not found in values map"); + } + id = values[id].split(/[\s.]+/g); + for (let i = 0; i < id.length; i++) { + id[i] |= 0; + } + } else if (Array.isArray(id)) { + id = id.slice(); + for (let i = 0; i < id.length; i++) { + id[i] |= 0; + } + } + + if (!Array.isArray(id)) { + return this.reporter.error( + "objid() should be either array or string, " + + "got: " + JSON.stringify(id), + ); + } + + if (!relative) { + if (id[1] >= 40) { + return this.reporter.error("Second objid identifier OOB"); + } + id.splice(0, 2, id[0] * 40 + id[1]); + } + + // Count number of octets + let size = 0; + for (let i = 0; i < id.length; i++) { + let ident = id[i]; + for (size++; ident >= 0x80; ident >>= 7) { + size++; + } + } + + const objid = Buffer.alloc(size); + let offset = objid.length - 1; + for (let i = id.length - 1; i >= 0; i--) { + let ident = id[i]; + objid[offset--] = ident & 0x7f; + while ((ident >>= 7) > 0) { + objid[offset--] = 0x80 | (ident & 0x7f); + } + } + + return this._createEncoderBuffer(objid); +}; + +function two(num) { + if (num < 10) { + return "0" + num; + } else { + return num; + } +} + +DERNode.prototype._encodeTime = function encodeTime(time, tag) { + let str; + const date = new Date(time); + + if (tag === "gentime") { + str = [ + two(date.getUTCFullYear()), + two(date.getUTCMonth() + 1), + two(date.getUTCDate()), + two(date.getUTCHours()), + two(date.getUTCMinutes()), + two(date.getUTCSeconds()), + "Z", + ].join(""); + } else if (tag === "utctime") { + str = [ + two(date.getUTCFullYear() % 100), + two(date.getUTCMonth() + 1), + two(date.getUTCDate()), + two(date.getUTCHours()), + two(date.getUTCMinutes()), + two(date.getUTCSeconds()), + "Z", + ].join(""); + } else { + this.reporter.error("Encoding " + tag + " time is not supported yet"); + } + + return this._encodeStr(str, "octstr"); +}; + +DERNode.prototype._encodeNull = function encodeNull() { + return this._createEncoderBuffer(""); +}; + +DERNode.prototype._encodeInt = function encodeInt(num, values) { + if (typeof num === "string") { + if (!values) { + return this.reporter.error("String int or enum given, but no values map"); + } + // deno-lint-ignore no-prototype-builtins + if (!values.hasOwnProperty(num)) { + return this.reporter.error( + "Values map doesn't contain: " + + JSON.stringify(num), + ); + } + num = values[num]; + } + + // Bignum, assume big endian + if (typeof num !== "number" && !Buffer.isBuffer(num)) { + const numArray = num.toArray(); + if (!num.sign && numArray[0] & 0x80) { + numArray.unshift(0); + } + num = Buffer.from(numArray); + } + + if (Buffer.isBuffer(num)) { + let size = num.length; + if (num.length === 0) { + size++; + } + + const out = Buffer.alloc(size); + num.copy(out); + if (num.length === 0) { + out[0] = 0; + } + return this._createEncoderBuffer(out); + } + + if (num < 0x80) { + return this._createEncoderBuffer(num); + } + + if (num < 0x100) { + return this._createEncoderBuffer([0, num]); + } + + let size = 1; + for (let i = num; i >= 0x100; i >>= 8) { + size++; + } + + const out = new Array(size); + for (let i = out.length - 1; i >= 0; i--) { + out[i] = num & 0xff; + num >>= 8; + } + if (out[0] & 0x80) { + out.unshift(0); + } + + return this._createEncoderBuffer(Buffer.from(out)); +}; + +DERNode.prototype._encodeBool = function encodeBool(value) { + return this._createEncoderBuffer(value ? 0xff : 0); +}; + +DERNode.prototype._use = function use(entity, obj) { + if (typeof entity === "function") { + entity = entity(obj); + } + return entity._getEncoder("der").tree; +}; + +DERNode.prototype._skipDefault = function skipDefault( + dataBuffer, + reporter, + parent, +) { + const state = this._baseState; + let i; + if (state["default"] === null) { + return false; + } + + const data = dataBuffer.join(); + if (state.defaultBuffer === undefined) { + state.defaultBuffer = this._encodeValue(state["default"], reporter, parent) + .join(); + } + + if (data.length !== state.defaultBuffer.length) { + return false; + } + + for (i = 0; i < data.length; i++) { + if (data[i] !== state.defaultBuffer[i]) { + return false; + } + } + + return true; +}; + +// Utility methods + +function encodeTag(tag, primitive, cls, reporter) { + let res; + + if (tag === "seqof") { + tag = "seq"; + } else if (tag === "setof") { + tag = "set"; + } + + // deno-lint-ignore no-prototype-builtins + if (der.tagByName.hasOwnProperty(tag)) { + res = der.tagByName[tag]; + } else if (typeof tag === "number" && (tag | 0) === tag) { + res = tag; + } else { + return reporter.error("Unknown tag: " + tag); + } + + if (res >= 0x1f) { + return reporter.error("Multi-octet tag encoding unsupported"); + } + + if (!primitive) { + res |= 0x20; + } + + res |= der.tagClassByName[cls || "universal"] << 6; + + return res; +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/encoders/pem.js b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/encoders/pem.js new file mode 100644 index 000000000..d2487e1ce --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/encoders/pem.js @@ -0,0 +1,30 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Fedor Indutny. All rights reserved. MIT license. + +import { DEREncoder } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/encoders/der.js"; + +export function PEMEncoder(entity) { + DEREncoder.call(this, entity); + this.enc = "pem"; +} +// inherits(PEMEncoder, DEREncoder); +PEMEncoder.prototype = Object.create(DEREncoder.prototype, { + constructor: { + value: PEMEncoder, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +PEMEncoder.prototype.encode = function encode(data, options) { + const buf = DEREncoder.prototype.encode.call(this, data); + + const p = buf.toString("base64"); + const out = ["-----BEGIN " + options.label + "-----"]; + for (let i = 0; i < p.length; i += 64) { + out.push(p.slice(i, i + 64)); + } + out.push("-----END " + options.label + "-----"); + return out.join("\n"); +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/mod.js b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/mod.js new file mode 100644 index 000000000..23cf79ca0 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/asn1.js/mod.js @@ -0,0 +1,96 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Fedor Indutny. All rights reserved. MIT license. + +import bignum from "internal:deno_node/polyfills/_crypto/crypto_browserify/bn.js/bn.js"; +import { Node } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/base/node.js"; +import { + DecoderBuffer, + EncoderBuffer, +} from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/base/buffer.js"; +import { Reporter } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/base/reporter.js"; +import { DEREncoder } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/encoders/der.js"; +import { PEMEncoder } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/encoders/pem.js"; +import { DERDecoder } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/decoders/der.js"; +import { PEMDecoder } from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/decoders/pem.js"; +import * as der from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/constants/der.js"; + +export const base = { + DecoderBuffer, + EncoderBuffer, + Node, + Reporter, +}; +export const encoders = { der: DEREncoder, pem: PEMEncoder }; +export const decoders = { der: DERDecoder, pem: PEMDecoder }; +export const constants = { der }; +export { bignum }; + +export function define(name, body) { + return new Entity(name, body); +} + +function Entity(name, body) { + this.name = name; + this.body = body; + + this.decoders = {}; + this.encoders = {}; +} + +Entity.prototype._createNamed = function createNamed(Base) { + const name = this.name; + + function Generated(entity) { + this._initNamed(entity, name); + } + // inherits(Generated, Base); + Generated.prototype = Object.create(Base.prototype, { + constructor: { + value: Generated, + enumerable: false, + writable: true, + configurable: true, + }, + }); + Generated.prototype._initNamed = function _initNamed(entity, name) { + Base.call(this, entity, name); + }; + return new Generated(this); +}; + +Entity.prototype._getDecoder = function _getDecoder(enc) { + enc = enc || "der"; + // Lazily create decoder + // deno-lint-ignore no-prototype-builtins + if (!this.decoders.hasOwnProperty(enc)) { + this.decoders[enc] = this._createNamed(decoders[enc]); + } + return this.decoders[enc]; +}; + +Entity.prototype.decode = function decode(data, enc, options) { + return this._getDecoder(enc).decode(data, options); +}; + +Entity.prototype._getEncoder = function _getEncoder(enc) { + enc = enc || "der"; + // Lazily create encoder + // deno-lint-ignore no-prototype-builtins + if (!this.encoders.hasOwnProperty(enc)) { + this.encoders[enc] = this._createNamed(encoders[enc]); + } + return this.encoders[enc]; +}; + +Entity.prototype.encode = function encode(data, enc, /* internal */ reporter) { + return this._getEncoder(enc).encode(data, reporter); +}; + +export default { + base, + bignum, + constants, + decoders, + define, + encoders, +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/bn.js/bn.js b/ext/node/polyfills/_crypto/crypto_browserify/bn.js/bn.js new file mode 100644 index 000000000..4e9d1187e --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/bn.js/bn.js @@ -0,0 +1,3605 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2015 Fedor Indutny. All rights reserved. MIT license. +// deno-lint-ignore-file no-var no-inner-declarations no-this-alias no-unused-vars + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +// Utils +function assert(val, msg) { + if (!val) throw new Error(msg || "Assertion failed"); +} + +// Could use `inherits` module, but don't want to move from single file +// architecture yet. +function inherits(ctor, superCtor) { + ctor.super_ = superCtor; + var TempCtor = function () {}; + TempCtor.prototype = superCtor.prototype; + ctor.prototype = new TempCtor(); + ctor.prototype.constructor = ctor; +} + +// BN +export function BN(number, base, endian) { + if (BN.isBN(number)) { + return number; + } + + this.negative = 0; + this.words = null; + this.length = 0; + + // Reduction context + this.red = null; + + if (number !== null) { + if (base === "le" || base === "be") { + endian = base; + base = 10; + } + + this._init(number || 0, base || 10, endian || "be"); + } +} +export default BN; + +BN.BN = BN; +BN.wordSize = 26; + +BN.isBN = function isBN(num) { + if (num instanceof BN) { + return true; + } + + return num !== null && typeof num === "object" && + num.constructor.wordSize === BN.wordSize && Array.isArray(num.words); +}; + +BN.max = function max(left, right) { + if (left.cmp(right) > 0) return left; + return right; +}; + +BN.min = function min(left, right) { + if (left.cmp(right) < 0) return left; + return right; +}; + +BN.prototype._init = function init(number, base, endian) { + if (typeof number === "number") { + return this._initNumber(number, base, endian); + } + + if (typeof number === "object") { + return this._initArray(number, base, endian); + } + + if (base === "hex") { + base = 16; + } + assert(base === (base | 0) && base >= 2 && base <= 36); + + number = number.toString().replace(/\s+/g, ""); + var start = 0; + if (number[0] === "-") { + start++; + this.negative = 1; + } + + if (start < number.length) { + if (base === 16) { + this._parseHex(number, start, endian); + } else { + this._parseBase(number, base, start); + if (endian === "le") { + this._initArray(this.toArray(), base, endian); + } + } + } +}; + +BN.prototype._initNumber = function _initNumber(number, base, endian) { + if (number < 0) { + this.negative = 1; + number = -number; + } + if (number < 0x4000000) { + this.words = [number & 0x3ffffff]; + this.length = 1; + } else if (number < 0x10000000000000) { + this.words = [ + number & 0x3ffffff, + (number / 0x4000000) & 0x3ffffff, + ]; + this.length = 2; + } else { + assert(number < 0x20000000000000); // 2 ^ 53 (unsafe) + this.words = [ + number & 0x3ffffff, + (number / 0x4000000) & 0x3ffffff, + 1, + ]; + this.length = 3; + } + + if (endian !== "le") return; + + // Reverse the bytes + this._initArray(this.toArray(), base, endian); +}; + +BN.prototype._initArray = function _initArray(number, base, endian) { + // Perhaps a Uint8Array + assert(typeof number.length === "number"); + if (number.length <= 0) { + this.words = [0]; + this.length = 1; + return this; + } + + this.length = Math.ceil(number.length / 3); + this.words = new Array(this.length); + for (var i = 0; i < this.length; i++) { + this.words[i] = 0; + } + + var j, w; + var off = 0; + if (endian === "be") { + for (i = number.length - 1, j = 0; i >= 0; i -= 3) { + w = number[i] | (number[i - 1] << 8) | (number[i - 2] << 16); + this.words[j] |= (w << off) & 0x3ffffff; + this.words[j + 1] = (w >>> (26 - off)) & 0x3ffffff; + off += 24; + if (off >= 26) { + off -= 26; + j++; + } + } + } else if (endian === "le") { + for (i = 0, j = 0; i < number.length; i += 3) { + w = number[i] | (number[i + 1] << 8) | (number[i + 2] << 16); + this.words[j] |= (w << off) & 0x3ffffff; + this.words[j + 1] = (w >>> (26 - off)) & 0x3ffffff; + off += 24; + if (off >= 26) { + off -= 26; + j++; + } + } + } + return this._strip(); +}; + +function parseHex4Bits(string, index) { + var c = string.charCodeAt(index); + // '0' - '9' + if (c >= 48 && c <= 57) { + return c - 48; + // 'A' - 'F' + } else if (c >= 65 && c <= 70) { + return c - 55; + // 'a' - 'f' + } else if (c >= 97 && c <= 102) { + return c - 87; + } else { + assert(false, "Invalid character in " + string); + } +} + +function parseHexByte(string, lowerBound, index) { + var r = parseHex4Bits(string, index); + if (index - 1 >= lowerBound) { + r |= parseHex4Bits(string, index - 1) << 4; + } + return r; +} + +BN.prototype._parseHex = function _parseHex(number, start, endian) { + // Create possibly bigger array to ensure that it fits the number + this.length = Math.ceil((number.length - start) / 6); + this.words = new Array(this.length); + for (var i = 0; i < this.length; i++) { + this.words[i] = 0; + } + + // 24-bits chunks + var off = 0; + var j = 0; + + var w; + if (endian === "be") { + for (i = number.length - 1; i >= start; i -= 2) { + w = parseHexByte(number, start, i) << off; + this.words[j] |= w & 0x3ffffff; + if (off >= 18) { + off -= 18; + j += 1; + this.words[j] |= w >>> 26; + } else { + off += 8; + } + } + } else { + var parseLength = number.length - start; + for ( + i = parseLength % 2 === 0 ? start + 1 : start; + i < number.length; + i += 2 + ) { + w = parseHexByte(number, start, i) << off; + this.words[j] |= w & 0x3ffffff; + if (off >= 18) { + off -= 18; + j += 1; + this.words[j] |= w >>> 26; + } else { + off += 8; + } + } + } + + this._strip(); +}; + +function parseBase(str, start, end, mul) { + var r = 0; + var b = 0; + var len = Math.min(str.length, end); + for (var i = start; i < len; i++) { + var c = str.charCodeAt(i) - 48; + + r *= mul; + + // 'a' + if (c >= 49) { + b = c - 49 + 0xa; + + // 'A' + } else if (c >= 17) { + b = c - 17 + 0xa; + + // '0' - '9' + } else { + b = c; + } + assert(c >= 0 && b < mul, "Invalid character"); + r += b; + } + return r; +} + +BN.prototype._parseBase = function _parseBase(number, base, start) { + // Initialize as zero + this.words = [0]; + this.length = 1; + + // Find length of limb in base + for (var limbLen = 0, limbPow = 1; limbPow <= 0x3ffffff; limbPow *= base) { + limbLen++; + } + limbLen--; + limbPow = (limbPow / base) | 0; + + var total = number.length - start; + var mod = total % limbLen; + var end = Math.min(total, total - mod) + start; + + var word = 0; + for (var i = start; i < end; i += limbLen) { + word = parseBase(number, i, i + limbLen, base); + + this.imuln(limbPow); + if (this.words[0] + word < 0x4000000) { + this.words[0] += word; + } else { + this._iaddn(word); + } + } + + if (mod !== 0) { + var pow = 1; + word = parseBase(number, i, number.length, base); + + for (i = 0; i < mod; i++) { + pow *= base; + } + + this.imuln(pow); + if (this.words[0] + word < 0x4000000) { + this.words[0] += word; + } else { + this._iaddn(word); + } + } + + this._strip(); +}; + +BN.prototype.copy = function copy(dest) { + dest.words = new Array(this.length); + for (var i = 0; i < this.length; i++) { + dest.words[i] = this.words[i]; + } + dest.length = this.length; + dest.negative = this.negative; + dest.red = this.red; +}; + +function move(dest, src) { + dest.words = src.words; + dest.length = src.length; + dest.negative = src.negative; + dest.red = src.red; +} + +BN.prototype._move = function _move(dest) { + move(dest, this); +}; + +BN.prototype.clone = function clone() { + var r = new BN(null); + this.copy(r); + return r; +}; + +BN.prototype._expand = function _expand(size) { + while (this.length < size) { + this.words[this.length++] = 0; + } + return this; +}; + +// Remove leading `0` from `this` +BN.prototype._strip = function strip() { + while (this.length > 1 && this.words[this.length - 1] === 0) { + this.length--; + } + return this._normSign(); +}; + +BN.prototype._normSign = function _normSign() { + // -0 = 0 + if (this.length === 1 && this.words[0] === 0) { + this.negative = 0; + } + return this; +}; + +// Check Symbol.for because not everywhere where Symbol defined +// See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Symbol#Browser_compatibility +if (typeof Symbol !== "undefined" && typeof Symbol.for === "function") { + try { + BN.prototype[Symbol.for("nodejs.util.inspect.custom")] = inspect; + } catch (e) { + BN.prototype.inspect = inspect; + } +} else { + BN.prototype.inspect = inspect; +} + +function inspect() { + return (this.red ? "<BN-R: " : "<BN: ") + this.toString(16) + ">"; +} + +/* + + var zeros = []; + var groupSizes = []; + var groupBases = []; + + var s = ''; + var i = -1; + while (++i < BN.wordSize) { + zeros[i] = s; + s += '0'; + } + groupSizes[0] = 0; + groupSizes[1] = 0; + groupBases[0] = 0; + groupBases[1] = 0; + var base = 2 - 1; + while (++base < 36 + 1) { + var groupSize = 0; + var groupBase = 1; + while (groupBase < (1 << BN.wordSize) / base) { + groupBase *= base; + groupSize += 1; + } + groupSizes[base] = groupSize; + groupBases[base] = groupBase; + } + + */ + +var zeros = [ + "", + "0", + "00", + "000", + "0000", + "00000", + "000000", + "0000000", + "00000000", + "000000000", + "0000000000", + "00000000000", + "000000000000", + "0000000000000", + "00000000000000", + "000000000000000", + "0000000000000000", + "00000000000000000", + "000000000000000000", + "0000000000000000000", + "00000000000000000000", + "000000000000000000000", + "0000000000000000000000", + "00000000000000000000000", + "000000000000000000000000", + "0000000000000000000000000", +]; + +var groupSizes = [ + 0, + 0, + 25, + 16, + 12, + 11, + 10, + 9, + 8, + 8, + 7, + 7, + 7, + 7, + 6, + 6, + 6, + 6, + 6, + 6, + 6, + 5, + 5, + 5, + 5, + 5, + 5, + 5, + 5, + 5, + 5, + 5, + 5, + 5, + 5, + 5, + 5, +]; + +var groupBases = [ + 0, + 0, + 33554432, + 43046721, + 16777216, + 48828125, + 60466176, + 40353607, + 16777216, + 43046721, + 10000000, + 19487171, + 35831808, + 62748517, + 7529536, + 11390625, + 16777216, + 24137569, + 34012224, + 47045881, + 64000000, + 4084101, + 5153632, + 6436343, + 7962624, + 9765625, + 11881376, + 14348907, + 17210368, + 20511149, + 24300000, + 28629151, + 33554432, + 39135393, + 45435424, + 52521875, + 60466176, +]; + +BN.prototype.toString = function toString(base, padding) { + base = base || 10; + padding = padding | 0 || 1; + + var out; + if (base === 16 || base === "hex") { + out = ""; + var off = 0; + var carry = 0; + for (var i = 0; i < this.length; i++) { + var w = this.words[i]; + var word = (((w << off) | carry) & 0xffffff).toString(16); + carry = (w >>> (24 - off)) & 0xffffff; + if (carry !== 0 || i !== this.length - 1) { + out = zeros[6 - word.length] + word + out; + } else { + out = word + out; + } + off += 2; + if (off >= 26) { + off -= 26; + i--; + } + } + if (carry !== 0) { + out = carry.toString(16) + out; + } + while (out.length % padding !== 0) { + out = "0" + out; + } + if (this.negative !== 0) { + out = "-" + out; + } + return out; + } + + if (base === (base | 0) && base >= 2 && base <= 36) { + // var groupSize = Math.floor(BN.wordSize * Math.LN2 / Math.log(base)); + var groupSize = groupSizes[base]; + // var groupBase = Math.pow(base, groupSize); + var groupBase = groupBases[base]; + out = ""; + var c = this.clone(); + c.negative = 0; + while (!c.isZero()) { + var r = c.modrn(groupBase).toString(base); + c = c.idivn(groupBase); + + if (!c.isZero()) { + out = zeros[groupSize - r.length] + r + out; + } else { + out = r + out; + } + } + if (this.isZero()) { + out = "0" + out; + } + while (out.length % padding !== 0) { + out = "0" + out; + } + if (this.negative !== 0) { + out = "-" + out; + } + return out; + } + + assert(false, "Base should be between 2 and 36"); +}; + +BN.prototype.toNumber = function toNumber() { + var ret = this.words[0]; + if (this.length === 2) { + ret += this.words[1] * 0x4000000; + } else if (this.length === 3 && this.words[2] === 0x01) { + // NOTE: at this stage it is known that the top bit is set + ret += 0x10000000000000 + (this.words[1] * 0x4000000); + } else if (this.length > 2) { + assert(false, "Number can only safely store up to 53 bits"); + } + return (this.negative !== 0) ? -ret : ret; +}; + +BN.prototype.toJSON = function toJSON() { + return this.toString(16, 2); +}; + +if (Buffer) { + BN.prototype.toBuffer = function toBuffer(endian, length) { + return this.toArrayLike(Buffer, endian, length); + }; +} + +BN.prototype.toArray = function toArray(endian, length) { + return this.toArrayLike(Array, endian, length); +}; + +var allocate = function allocate(ArrayType, size) { + if (ArrayType.allocUnsafe) { + return ArrayType.allocUnsafe(size); + } + return new ArrayType(size); +}; + +BN.prototype.toArrayLike = function toArrayLike(ArrayType, endian, length) { + this._strip(); + + var byteLength = this.byteLength(); + var reqLength = length || Math.max(1, byteLength); + assert(byteLength <= reqLength, "byte array longer than desired length"); + assert(reqLength > 0, "Requested array length <= 0"); + + var res = allocate(ArrayType, reqLength); + var postfix = endian === "le" ? "LE" : "BE"; + this["_toArrayLike" + postfix](res, byteLength); + return res; +}; + +BN.prototype._toArrayLikeLE = function _toArrayLikeLE(res, byteLength) { + var position = 0; + var carry = 0; + + for (var i = 0, shift = 0; i < this.length; i++) { + var word = (this.words[i] << shift) | carry; + + res[position++] = word & 0xff; + if (position < res.length) { + res[position++] = (word >> 8) & 0xff; + } + if (position < res.length) { + res[position++] = (word >> 16) & 0xff; + } + + if (shift === 6) { + if (position < res.length) { + res[position++] = (word >> 24) & 0xff; + } + carry = 0; + shift = 0; + } else { + carry = word >>> 24; + shift += 2; + } + } + + if (position < res.length) { + res[position++] = carry; + + while (position < res.length) { + res[position++] = 0; + } + } +}; + +BN.prototype._toArrayLikeBE = function _toArrayLikeBE(res, byteLength) { + var position = res.length - 1; + var carry = 0; + + for (var i = 0, shift = 0; i < this.length; i++) { + var word = (this.words[i] << shift) | carry; + + res[position--] = word & 0xff; + if (position >= 0) { + res[position--] = (word >> 8) & 0xff; + } + if (position >= 0) { + res[position--] = (word >> 16) & 0xff; + } + + if (shift === 6) { + if (position >= 0) { + res[position--] = (word >> 24) & 0xff; + } + carry = 0; + shift = 0; + } else { + carry = word >>> 24; + shift += 2; + } + } + + if (position >= 0) { + res[position--] = carry; + + while (position >= 0) { + res[position--] = 0; + } + } +}; + +if (Math.clz32) { + BN.prototype._countBits = function _countBits(w) { + return 32 - Math.clz32(w); + }; +} else { + BN.prototype._countBits = function _countBits(w) { + var t = w; + var r = 0; + if (t >= 0x1000) { + r += 13; + t >>>= 13; + } + if (t >= 0x40) { + r += 7; + t >>>= 7; + } + if (t >= 0x8) { + r += 4; + t >>>= 4; + } + if (t >= 0x02) { + r += 2; + t >>>= 2; + } + return r + t; + }; +} + +BN.prototype._zeroBits = function _zeroBits(w) { + // Short-cut + if (w === 0) return 26; + + var t = w; + var r = 0; + if ((t & 0x1fff) === 0) { + r += 13; + t >>>= 13; + } + if ((t & 0x7f) === 0) { + r += 7; + t >>>= 7; + } + if ((t & 0xf) === 0) { + r += 4; + t >>>= 4; + } + if ((t & 0x3) === 0) { + r += 2; + t >>>= 2; + } + if ((t & 0x1) === 0) { + r++; + } + return r; +}; + +// Return number of used bits in a BN +BN.prototype.bitLength = function bitLength() { + var w = this.words[this.length - 1]; + var hi = this._countBits(w); + return (this.length - 1) * 26 + hi; +}; + +function toBitArray(num) { + var w = new Array(num.bitLength()); + + for (var bit = 0; bit < w.length; bit++) { + var off = (bit / 26) | 0; + var wbit = bit % 26; + + w[bit] = (num.words[off] >>> wbit) & 0x01; + } + + return w; +} + +// Number of trailing zero bits +BN.prototype.zeroBits = function zeroBits() { + if (this.isZero()) return 0; + + var r = 0; + for (var i = 0; i < this.length; i++) { + var b = this._zeroBits(this.words[i]); + r += b; + if (b !== 26) break; + } + return r; +}; + +BN.prototype.byteLength = function byteLength() { + return Math.ceil(this.bitLength() / 8); +}; + +BN.prototype.toTwos = function toTwos(width) { + if (this.negative !== 0) { + return this.abs().inotn(width).iaddn(1); + } + return this.clone(); +}; + +BN.prototype.fromTwos = function fromTwos(width) { + if (this.testn(width - 1)) { + return this.notn(width).iaddn(1).ineg(); + } + return this.clone(); +}; + +BN.prototype.isNeg = function isNeg() { + return this.negative !== 0; +}; + +// Return negative clone of `this` +BN.prototype.neg = function neg() { + return this.clone().ineg(); +}; + +BN.prototype.ineg = function ineg() { + if (!this.isZero()) { + this.negative ^= 1; + } + + return this; +}; + +// Or `num` with `this` in-place +BN.prototype.iuor = function iuor(num) { + while (this.length < num.length) { + this.words[this.length++] = 0; + } + + for (var i = 0; i < num.length; i++) { + this.words[i] = this.words[i] | num.words[i]; + } + + return this._strip(); +}; + +BN.prototype.ior = function ior(num) { + assert((this.negative | num.negative) === 0); + return this.iuor(num); +}; + +// Or `num` with `this` +BN.prototype.or = function or(num) { + if (this.length > num.length) return this.clone().ior(num); + return num.clone().ior(this); +}; + +BN.prototype.uor = function uor(num) { + if (this.length > num.length) return this.clone().iuor(num); + return num.clone().iuor(this); +}; + +// And `num` with `this` in-place +BN.prototype.iuand = function iuand(num) { + // b = min-length(num, this) + var b; + if (this.length > num.length) { + b = num; + } else { + b = this; + } + + for (var i = 0; i < b.length; i++) { + this.words[i] = this.words[i] & num.words[i]; + } + + this.length = b.length; + + return this._strip(); +}; + +BN.prototype.iand = function iand(num) { + assert((this.negative | num.negative) === 0); + return this.iuand(num); +}; + +// And `num` with `this` +BN.prototype.and = function and(num) { + if (this.length > num.length) return this.clone().iand(num); + return num.clone().iand(this); +}; + +BN.prototype.uand = function uand(num) { + if (this.length > num.length) return this.clone().iuand(num); + return num.clone().iuand(this); +}; + +// Xor `num` with `this` in-place +BN.prototype.iuxor = function iuxor(num) { + // a.length > b.length + var a; + var b; + if (this.length > num.length) { + a = this; + b = num; + } else { + a = num; + b = this; + } + + for (var i = 0; i < b.length; i++) { + this.words[i] = a.words[i] ^ b.words[i]; + } + + if (this !== a) { + for (; i < a.length; i++) { + this.words[i] = a.words[i]; + } + } + + this.length = a.length; + + return this._strip(); +}; + +BN.prototype.ixor = function ixor(num) { + assert((this.negative | num.negative) === 0); + return this.iuxor(num); +}; + +// Xor `num` with `this` +BN.prototype.xor = function xor(num) { + if (this.length > num.length) return this.clone().ixor(num); + return num.clone().ixor(this); +}; + +BN.prototype.uxor = function uxor(num) { + if (this.length > num.length) return this.clone().iuxor(num); + return num.clone().iuxor(this); +}; + +// Not ``this`` with ``width`` bitwidth +BN.prototype.inotn = function inotn(width) { + assert(typeof width === "number" && width >= 0); + + var bytesNeeded = Math.ceil(width / 26) | 0; + var bitsLeft = width % 26; + + // Extend the buffer with leading zeroes + this._expand(bytesNeeded); + + if (bitsLeft > 0) { + bytesNeeded--; + } + + // Handle complete words + for (var i = 0; i < bytesNeeded; i++) { + this.words[i] = ~this.words[i] & 0x3ffffff; + } + + // Handle the residue + if (bitsLeft > 0) { + this.words[i] = ~this.words[i] & (0x3ffffff >> (26 - bitsLeft)); + } + + // And remove leading zeroes + return this._strip(); +}; + +BN.prototype.notn = function notn(width) { + return this.clone().inotn(width); +}; + +// Set `bit` of `this` +BN.prototype.setn = function setn(bit, val) { + assert(typeof bit === "number" && bit >= 0); + + var off = (bit / 26) | 0; + var wbit = bit % 26; + + this._expand(off + 1); + + if (val) { + this.words[off] = this.words[off] | (1 << wbit); + } else { + this.words[off] = this.words[off] & ~(1 << wbit); + } + + return this._strip(); +}; + +// Add `num` to `this` in-place +BN.prototype.iadd = function iadd(num) { + var r; + + // negative + positive + if (this.negative !== 0 && num.negative === 0) { + this.negative = 0; + r = this.isub(num); + this.negative ^= 1; + return this._normSign(); + + // positive + negative + } else if (this.negative === 0 && num.negative !== 0) { + num.negative = 0; + r = this.isub(num); + num.negative = 1; + return r._normSign(); + } + + // a.length > b.length + var a, b; + if (this.length > num.length) { + a = this; + b = num; + } else { + a = num; + b = this; + } + + var carry = 0; + for (var i = 0; i < b.length; i++) { + r = (a.words[i] | 0) + (b.words[i] | 0) + carry; + this.words[i] = r & 0x3ffffff; + carry = r >>> 26; + } + for (; carry !== 0 && i < a.length; i++) { + r = (a.words[i] | 0) + carry; + this.words[i] = r & 0x3ffffff; + carry = r >>> 26; + } + + this.length = a.length; + if (carry !== 0) { + this.words[this.length] = carry; + this.length++; + // Copy the rest of the words + } else if (a !== this) { + for (; i < a.length; i++) { + this.words[i] = a.words[i]; + } + } + + return this; +}; + +// Add `num` to `this` +BN.prototype.add = function add(num) { + var res; + if (num.negative !== 0 && this.negative === 0) { + num.negative = 0; + res = this.sub(num); + num.negative ^= 1; + return res; + } else if (num.negative === 0 && this.negative !== 0) { + this.negative = 0; + res = num.sub(this); + this.negative = 1; + return res; + } + + if (this.length > num.length) return this.clone().iadd(num); + + return num.clone().iadd(this); +}; + +// Subtract `num` from `this` in-place +BN.prototype.isub = function isub(num) { + // this - (-num) = this + num + if (num.negative !== 0) { + num.negative = 0; + var r = this.iadd(num); + num.negative = 1; + return r._normSign(); + + // -this - num = -(this + num) + } else if (this.negative !== 0) { + this.negative = 0; + this.iadd(num); + this.negative = 1; + return this._normSign(); + } + + // At this point both numbers are positive + var cmp = this.cmp(num); + + // Optimization - zeroify + if (cmp === 0) { + this.negative = 0; + this.length = 1; + this.words[0] = 0; + return this; + } + + // a > b + var a, b; + if (cmp > 0) { + a = this; + b = num; + } else { + a = num; + b = this; + } + + var carry = 0; + for (var i = 0; i < b.length; i++) { + r = (a.words[i] | 0) - (b.words[i] | 0) + carry; + carry = r >> 26; + this.words[i] = r & 0x3ffffff; + } + for (; carry !== 0 && i < a.length; i++) { + r = (a.words[i] | 0) + carry; + carry = r >> 26; + this.words[i] = r & 0x3ffffff; + } + + // Copy rest of the words + if (carry === 0 && i < a.length && a !== this) { + for (; i < a.length; i++) { + this.words[i] = a.words[i]; + } + } + + this.length = Math.max(this.length, i); + + if (a !== this) { + this.negative = 1; + } + + return this._strip(); +}; + +// Subtract `num` from `this` +BN.prototype.sub = function sub(num) { + return this.clone().isub(num); +}; + +function smallMulTo(self, num, out) { + out.negative = num.negative ^ self.negative; + var len = (self.length + num.length) | 0; + out.length = len; + len = (len - 1) | 0; + + // Peel one iteration (compiler can't do it, because of code complexity) + var a = self.words[0] | 0; + var b = num.words[0] | 0; + var r = a * b; + + var lo = r & 0x3ffffff; + var carry = (r / 0x4000000) | 0; + out.words[0] = lo; + + for (var k = 1; k < len; k++) { + // Sum all words with the same `i + j = k` and accumulate `ncarry`, + // note that ncarry could be >= 0x3ffffff + var ncarry = carry >>> 26; + var rword = carry & 0x3ffffff; + var maxJ = Math.min(k, num.length - 1); + for (var j = Math.max(0, k - self.length + 1); j <= maxJ; j++) { + var i = (k - j) | 0; + a = self.words[i] | 0; + b = num.words[j] | 0; + r = a * b + rword; + ncarry += (r / 0x4000000) | 0; + rword = r & 0x3ffffff; + } + out.words[k] = rword | 0; + carry = ncarry | 0; + } + if (carry !== 0) { + out.words[k] = carry | 0; + } else { + out.length--; + } + + return out._strip(); +} + +// TODO(indutny): it may be reasonable to omit it for users who don't need +// to work with 256-bit numbers, otherwise it gives 20% improvement for 256-bit +// multiplication (like elliptic secp256k1). +var comb10MulTo = function comb10MulTo(self, num, out) { + var a = self.words; + var b = num.words; + var o = out.words; + var c = 0; + var lo; + var mid; + var hi; + var a0 = a[0] | 0; + var al0 = a0 & 0x1fff; + var ah0 = a0 >>> 13; + var a1 = a[1] | 0; + var al1 = a1 & 0x1fff; + var ah1 = a1 >>> 13; + var a2 = a[2] | 0; + var al2 = a2 & 0x1fff; + var ah2 = a2 >>> 13; + var a3 = a[3] | 0; + var al3 = a3 & 0x1fff; + var ah3 = a3 >>> 13; + var a4 = a[4] | 0; + var al4 = a4 & 0x1fff; + var ah4 = a4 >>> 13; + var a5 = a[5] | 0; + var al5 = a5 & 0x1fff; + var ah5 = a5 >>> 13; + var a6 = a[6] | 0; + var al6 = a6 & 0x1fff; + var ah6 = a6 >>> 13; + var a7 = a[7] | 0; + var al7 = a7 & 0x1fff; + var ah7 = a7 >>> 13; + var a8 = a[8] | 0; + var al8 = a8 & 0x1fff; + var ah8 = a8 >>> 13; + var a9 = a[9] | 0; + var al9 = a9 & 0x1fff; + var ah9 = a9 >>> 13; + var b0 = b[0] | 0; + var bl0 = b0 & 0x1fff; + var bh0 = b0 >>> 13; + var b1 = b[1] | 0; + var bl1 = b1 & 0x1fff; + var bh1 = b1 >>> 13; + var b2 = b[2] | 0; + var bl2 = b2 & 0x1fff; + var bh2 = b2 >>> 13; + var b3 = b[3] | 0; + var bl3 = b3 & 0x1fff; + var bh3 = b3 >>> 13; + var b4 = b[4] | 0; + var bl4 = b4 & 0x1fff; + var bh4 = b4 >>> 13; + var b5 = b[5] | 0; + var bl5 = b5 & 0x1fff; + var bh5 = b5 >>> 13; + var b6 = b[6] | 0; + var bl6 = b6 & 0x1fff; + var bh6 = b6 >>> 13; + var b7 = b[7] | 0; + var bl7 = b7 & 0x1fff; + var bh7 = b7 >>> 13; + var b8 = b[8] | 0; + var bl8 = b8 & 0x1fff; + var bh8 = b8 >>> 13; + var b9 = b[9] | 0; + var bl9 = b9 & 0x1fff; + var bh9 = b9 >>> 13; + + out.negative = self.negative ^ num.negative; + out.length = 19; + /* k = 0 */ + lo = Math.imul(al0, bl0); + mid = Math.imul(al0, bh0); + mid = (mid + Math.imul(ah0, bl0)) | 0; + hi = Math.imul(ah0, bh0); + var w0 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w0 >>> 26)) | 0; + w0 &= 0x3ffffff; + /* k = 1 */ + lo = Math.imul(al1, bl0); + mid = Math.imul(al1, bh0); + mid = (mid + Math.imul(ah1, bl0)) | 0; + hi = Math.imul(ah1, bh0); + lo = (lo + Math.imul(al0, bl1)) | 0; + mid = (mid + Math.imul(al0, bh1)) | 0; + mid = (mid + Math.imul(ah0, bl1)) | 0; + hi = (hi + Math.imul(ah0, bh1)) | 0; + var w1 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w1 >>> 26)) | 0; + w1 &= 0x3ffffff; + /* k = 2 */ + lo = Math.imul(al2, bl0); + mid = Math.imul(al2, bh0); + mid = (mid + Math.imul(ah2, bl0)) | 0; + hi = Math.imul(ah2, bh0); + lo = (lo + Math.imul(al1, bl1)) | 0; + mid = (mid + Math.imul(al1, bh1)) | 0; + mid = (mid + Math.imul(ah1, bl1)) | 0; + hi = (hi + Math.imul(ah1, bh1)) | 0; + lo = (lo + Math.imul(al0, bl2)) | 0; + mid = (mid + Math.imul(al0, bh2)) | 0; + mid = (mid + Math.imul(ah0, bl2)) | 0; + hi = (hi + Math.imul(ah0, bh2)) | 0; + var w2 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w2 >>> 26)) | 0; + w2 &= 0x3ffffff; + /* k = 3 */ + lo = Math.imul(al3, bl0); + mid = Math.imul(al3, bh0); + mid = (mid + Math.imul(ah3, bl0)) | 0; + hi = Math.imul(ah3, bh0); + lo = (lo + Math.imul(al2, bl1)) | 0; + mid = (mid + Math.imul(al2, bh1)) | 0; + mid = (mid + Math.imul(ah2, bl1)) | 0; + hi = (hi + Math.imul(ah2, bh1)) | 0; + lo = (lo + Math.imul(al1, bl2)) | 0; + mid = (mid + Math.imul(al1, bh2)) | 0; + mid = (mid + Math.imul(ah1, bl2)) | 0; + hi = (hi + Math.imul(ah1, bh2)) | 0; + lo = (lo + Math.imul(al0, bl3)) | 0; + mid = (mid + Math.imul(al0, bh3)) | 0; + mid = (mid + Math.imul(ah0, bl3)) | 0; + hi = (hi + Math.imul(ah0, bh3)) | 0; + var w3 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w3 >>> 26)) | 0; + w3 &= 0x3ffffff; + /* k = 4 */ + lo = Math.imul(al4, bl0); + mid = Math.imul(al4, bh0); + mid = (mid + Math.imul(ah4, bl0)) | 0; + hi = Math.imul(ah4, bh0); + lo = (lo + Math.imul(al3, bl1)) | 0; + mid = (mid + Math.imul(al3, bh1)) | 0; + mid = (mid + Math.imul(ah3, bl1)) | 0; + hi = (hi + Math.imul(ah3, bh1)) | 0; + lo = (lo + Math.imul(al2, bl2)) | 0; + mid = (mid + Math.imul(al2, bh2)) | 0; + mid = (mid + Math.imul(ah2, bl2)) | 0; + hi = (hi + Math.imul(ah2, bh2)) | 0; + lo = (lo + Math.imul(al1, bl3)) | 0; + mid = (mid + Math.imul(al1, bh3)) | 0; + mid = (mid + Math.imul(ah1, bl3)) | 0; + hi = (hi + Math.imul(ah1, bh3)) | 0; + lo = (lo + Math.imul(al0, bl4)) | 0; + mid = (mid + Math.imul(al0, bh4)) | 0; + mid = (mid + Math.imul(ah0, bl4)) | 0; + hi = (hi + Math.imul(ah0, bh4)) | 0; + var w4 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w4 >>> 26)) | 0; + w4 &= 0x3ffffff; + /* k = 5 */ + lo = Math.imul(al5, bl0); + mid = Math.imul(al5, bh0); + mid = (mid + Math.imul(ah5, bl0)) | 0; + hi = Math.imul(ah5, bh0); + lo = (lo + Math.imul(al4, bl1)) | 0; + mid = (mid + Math.imul(al4, bh1)) | 0; + mid = (mid + Math.imul(ah4, bl1)) | 0; + hi = (hi + Math.imul(ah4, bh1)) | 0; + lo = (lo + Math.imul(al3, bl2)) | 0; + mid = (mid + Math.imul(al3, bh2)) | 0; + mid = (mid + Math.imul(ah3, bl2)) | 0; + hi = (hi + Math.imul(ah3, bh2)) | 0; + lo = (lo + Math.imul(al2, bl3)) | 0; + mid = (mid + Math.imul(al2, bh3)) | 0; + mid = (mid + Math.imul(ah2, bl3)) | 0; + hi = (hi + Math.imul(ah2, bh3)) | 0; + lo = (lo + Math.imul(al1, bl4)) | 0; + mid = (mid + Math.imul(al1, bh4)) | 0; + mid = (mid + Math.imul(ah1, bl4)) | 0; + hi = (hi + Math.imul(ah1, bh4)) | 0; + lo = (lo + Math.imul(al0, bl5)) | 0; + mid = (mid + Math.imul(al0, bh5)) | 0; + mid = (mid + Math.imul(ah0, bl5)) | 0; + hi = (hi + Math.imul(ah0, bh5)) | 0; + var w5 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w5 >>> 26)) | 0; + w5 &= 0x3ffffff; + /* k = 6 */ + lo = Math.imul(al6, bl0); + mid = Math.imul(al6, bh0); + mid = (mid + Math.imul(ah6, bl0)) | 0; + hi = Math.imul(ah6, bh0); + lo = (lo + Math.imul(al5, bl1)) | 0; + mid = (mid + Math.imul(al5, bh1)) | 0; + mid = (mid + Math.imul(ah5, bl1)) | 0; + hi = (hi + Math.imul(ah5, bh1)) | 0; + lo = (lo + Math.imul(al4, bl2)) | 0; + mid = (mid + Math.imul(al4, bh2)) | 0; + mid = (mid + Math.imul(ah4, bl2)) | 0; + hi = (hi + Math.imul(ah4, bh2)) | 0; + lo = (lo + Math.imul(al3, bl3)) | 0; + mid = (mid + Math.imul(al3, bh3)) | 0; + mid = (mid + Math.imul(ah3, bl3)) | 0; + hi = (hi + Math.imul(ah3, bh3)) | 0; + lo = (lo + Math.imul(al2, bl4)) | 0; + mid = (mid + Math.imul(al2, bh4)) | 0; + mid = (mid + Math.imul(ah2, bl4)) | 0; + hi = (hi + Math.imul(ah2, bh4)) | 0; + lo = (lo + Math.imul(al1, bl5)) | 0; + mid = (mid + Math.imul(al1, bh5)) | 0; + mid = (mid + Math.imul(ah1, bl5)) | 0; + hi = (hi + Math.imul(ah1, bh5)) | 0; + lo = (lo + Math.imul(al0, bl6)) | 0; + mid = (mid + Math.imul(al0, bh6)) | 0; + mid = (mid + Math.imul(ah0, bl6)) | 0; + hi = (hi + Math.imul(ah0, bh6)) | 0; + var w6 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w6 >>> 26)) | 0; + w6 &= 0x3ffffff; + /* k = 7 */ + lo = Math.imul(al7, bl0); + mid = Math.imul(al7, bh0); + mid = (mid + Math.imul(ah7, bl0)) | 0; + hi = Math.imul(ah7, bh0); + lo = (lo + Math.imul(al6, bl1)) | 0; + mid = (mid + Math.imul(al6, bh1)) | 0; + mid = (mid + Math.imul(ah6, bl1)) | 0; + hi = (hi + Math.imul(ah6, bh1)) | 0; + lo = (lo + Math.imul(al5, bl2)) | 0; + mid = (mid + Math.imul(al5, bh2)) | 0; + mid = (mid + Math.imul(ah5, bl2)) | 0; + hi = (hi + Math.imul(ah5, bh2)) | 0; + lo = (lo + Math.imul(al4, bl3)) | 0; + mid = (mid + Math.imul(al4, bh3)) | 0; + mid = (mid + Math.imul(ah4, bl3)) | 0; + hi = (hi + Math.imul(ah4, bh3)) | 0; + lo = (lo + Math.imul(al3, bl4)) | 0; + mid = (mid + Math.imul(al3, bh4)) | 0; + mid = (mid + Math.imul(ah3, bl4)) | 0; + hi = (hi + Math.imul(ah3, bh4)) | 0; + lo = (lo + Math.imul(al2, bl5)) | 0; + mid = (mid + Math.imul(al2, bh5)) | 0; + mid = (mid + Math.imul(ah2, bl5)) | 0; + hi = (hi + Math.imul(ah2, bh5)) | 0; + lo = (lo + Math.imul(al1, bl6)) | 0; + mid = (mid + Math.imul(al1, bh6)) | 0; + mid = (mid + Math.imul(ah1, bl6)) | 0; + hi = (hi + Math.imul(ah1, bh6)) | 0; + lo = (lo + Math.imul(al0, bl7)) | 0; + mid = (mid + Math.imul(al0, bh7)) | 0; + mid = (mid + Math.imul(ah0, bl7)) | 0; + hi = (hi + Math.imul(ah0, bh7)) | 0; + var w7 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w7 >>> 26)) | 0; + w7 &= 0x3ffffff; + /* k = 8 */ + lo = Math.imul(al8, bl0); + mid = Math.imul(al8, bh0); + mid = (mid + Math.imul(ah8, bl0)) | 0; + hi = Math.imul(ah8, bh0); + lo = (lo + Math.imul(al7, bl1)) | 0; + mid = (mid + Math.imul(al7, bh1)) | 0; + mid = (mid + Math.imul(ah7, bl1)) | 0; + hi = (hi + Math.imul(ah7, bh1)) | 0; + lo = (lo + Math.imul(al6, bl2)) | 0; + mid = (mid + Math.imul(al6, bh2)) | 0; + mid = (mid + Math.imul(ah6, bl2)) | 0; + hi = (hi + Math.imul(ah6, bh2)) | 0; + lo = (lo + Math.imul(al5, bl3)) | 0; + mid = (mid + Math.imul(al5, bh3)) | 0; + mid = (mid + Math.imul(ah5, bl3)) | 0; + hi = (hi + Math.imul(ah5, bh3)) | 0; + lo = (lo + Math.imul(al4, bl4)) | 0; + mid = (mid + Math.imul(al4, bh4)) | 0; + mid = (mid + Math.imul(ah4, bl4)) | 0; + hi = (hi + Math.imul(ah4, bh4)) | 0; + lo = (lo + Math.imul(al3, bl5)) | 0; + mid = (mid + Math.imul(al3, bh5)) | 0; + mid = (mid + Math.imul(ah3, bl5)) | 0; + hi = (hi + Math.imul(ah3, bh5)) | 0; + lo = (lo + Math.imul(al2, bl6)) | 0; + mid = (mid + Math.imul(al2, bh6)) | 0; + mid = (mid + Math.imul(ah2, bl6)) | 0; + hi = (hi + Math.imul(ah2, bh6)) | 0; + lo = (lo + Math.imul(al1, bl7)) | 0; + mid = (mid + Math.imul(al1, bh7)) | 0; + mid = (mid + Math.imul(ah1, bl7)) | 0; + hi = (hi + Math.imul(ah1, bh7)) | 0; + lo = (lo + Math.imul(al0, bl8)) | 0; + mid = (mid + Math.imul(al0, bh8)) | 0; + mid = (mid + Math.imul(ah0, bl8)) | 0; + hi = (hi + Math.imul(ah0, bh8)) | 0; + var w8 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w8 >>> 26)) | 0; + w8 &= 0x3ffffff; + /* k = 9 */ + lo = Math.imul(al9, bl0); + mid = Math.imul(al9, bh0); + mid = (mid + Math.imul(ah9, bl0)) | 0; + hi = Math.imul(ah9, bh0); + lo = (lo + Math.imul(al8, bl1)) | 0; + mid = (mid + Math.imul(al8, bh1)) | 0; + mid = (mid + Math.imul(ah8, bl1)) | 0; + hi = (hi + Math.imul(ah8, bh1)) | 0; + lo = (lo + Math.imul(al7, bl2)) | 0; + mid = (mid + Math.imul(al7, bh2)) | 0; + mid = (mid + Math.imul(ah7, bl2)) | 0; + hi = (hi + Math.imul(ah7, bh2)) | 0; + lo = (lo + Math.imul(al6, bl3)) | 0; + mid = (mid + Math.imul(al6, bh3)) | 0; + mid = (mid + Math.imul(ah6, bl3)) | 0; + hi = (hi + Math.imul(ah6, bh3)) | 0; + lo = (lo + Math.imul(al5, bl4)) | 0; + mid = (mid + Math.imul(al5, bh4)) | 0; + mid = (mid + Math.imul(ah5, bl4)) | 0; + hi = (hi + Math.imul(ah5, bh4)) | 0; + lo = (lo + Math.imul(al4, bl5)) | 0; + mid = (mid + Math.imul(al4, bh5)) | 0; + mid = (mid + Math.imul(ah4, bl5)) | 0; + hi = (hi + Math.imul(ah4, bh5)) | 0; + lo = (lo + Math.imul(al3, bl6)) | 0; + mid = (mid + Math.imul(al3, bh6)) | 0; + mid = (mid + Math.imul(ah3, bl6)) | 0; + hi = (hi + Math.imul(ah3, bh6)) | 0; + lo = (lo + Math.imul(al2, bl7)) | 0; + mid = (mid + Math.imul(al2, bh7)) | 0; + mid = (mid + Math.imul(ah2, bl7)) | 0; + hi = (hi + Math.imul(ah2, bh7)) | 0; + lo = (lo + Math.imul(al1, bl8)) | 0; + mid = (mid + Math.imul(al1, bh8)) | 0; + mid = (mid + Math.imul(ah1, bl8)) | 0; + hi = (hi + Math.imul(ah1, bh8)) | 0; + lo = (lo + Math.imul(al0, bl9)) | 0; + mid = (mid + Math.imul(al0, bh9)) | 0; + mid = (mid + Math.imul(ah0, bl9)) | 0; + hi = (hi + Math.imul(ah0, bh9)) | 0; + var w9 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w9 >>> 26)) | 0; + w9 &= 0x3ffffff; + /* k = 10 */ + lo = Math.imul(al9, bl1); + mid = Math.imul(al9, bh1); + mid = (mid + Math.imul(ah9, bl1)) | 0; + hi = Math.imul(ah9, bh1); + lo = (lo + Math.imul(al8, bl2)) | 0; + mid = (mid + Math.imul(al8, bh2)) | 0; + mid = (mid + Math.imul(ah8, bl2)) | 0; + hi = (hi + Math.imul(ah8, bh2)) | 0; + lo = (lo + Math.imul(al7, bl3)) | 0; + mid = (mid + Math.imul(al7, bh3)) | 0; + mid = (mid + Math.imul(ah7, bl3)) | 0; + hi = (hi + Math.imul(ah7, bh3)) | 0; + lo = (lo + Math.imul(al6, bl4)) | 0; + mid = (mid + Math.imul(al6, bh4)) | 0; + mid = (mid + Math.imul(ah6, bl4)) | 0; + hi = (hi + Math.imul(ah6, bh4)) | 0; + lo = (lo + Math.imul(al5, bl5)) | 0; + mid = (mid + Math.imul(al5, bh5)) | 0; + mid = (mid + Math.imul(ah5, bl5)) | 0; + hi = (hi + Math.imul(ah5, bh5)) | 0; + lo = (lo + Math.imul(al4, bl6)) | 0; + mid = (mid + Math.imul(al4, bh6)) | 0; + mid = (mid + Math.imul(ah4, bl6)) | 0; + hi = (hi + Math.imul(ah4, bh6)) | 0; + lo = (lo + Math.imul(al3, bl7)) | 0; + mid = (mid + Math.imul(al3, bh7)) | 0; + mid = (mid + Math.imul(ah3, bl7)) | 0; + hi = (hi + Math.imul(ah3, bh7)) | 0; + lo = (lo + Math.imul(al2, bl8)) | 0; + mid = (mid + Math.imul(al2, bh8)) | 0; + mid = (mid + Math.imul(ah2, bl8)) | 0; + hi = (hi + Math.imul(ah2, bh8)) | 0; + lo = (lo + Math.imul(al1, bl9)) | 0; + mid = (mid + Math.imul(al1, bh9)) | 0; + mid = (mid + Math.imul(ah1, bl9)) | 0; + hi = (hi + Math.imul(ah1, bh9)) | 0; + var w10 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w10 >>> 26)) | 0; + w10 &= 0x3ffffff; + /* k = 11 */ + lo = Math.imul(al9, bl2); + mid = Math.imul(al9, bh2); + mid = (mid + Math.imul(ah9, bl2)) | 0; + hi = Math.imul(ah9, bh2); + lo = (lo + Math.imul(al8, bl3)) | 0; + mid = (mid + Math.imul(al8, bh3)) | 0; + mid = (mid + Math.imul(ah8, bl3)) | 0; + hi = (hi + Math.imul(ah8, bh3)) | 0; + lo = (lo + Math.imul(al7, bl4)) | 0; + mid = (mid + Math.imul(al7, bh4)) | 0; + mid = (mid + Math.imul(ah7, bl4)) | 0; + hi = (hi + Math.imul(ah7, bh4)) | 0; + lo = (lo + Math.imul(al6, bl5)) | 0; + mid = (mid + Math.imul(al6, bh5)) | 0; + mid = (mid + Math.imul(ah6, bl5)) | 0; + hi = (hi + Math.imul(ah6, bh5)) | 0; + lo = (lo + Math.imul(al5, bl6)) | 0; + mid = (mid + Math.imul(al5, bh6)) | 0; + mid = (mid + Math.imul(ah5, bl6)) | 0; + hi = (hi + Math.imul(ah5, bh6)) | 0; + lo = (lo + Math.imul(al4, bl7)) | 0; + mid = (mid + Math.imul(al4, bh7)) | 0; + mid = (mid + Math.imul(ah4, bl7)) | 0; + hi = (hi + Math.imul(ah4, bh7)) | 0; + lo = (lo + Math.imul(al3, bl8)) | 0; + mid = (mid + Math.imul(al3, bh8)) | 0; + mid = (mid + Math.imul(ah3, bl8)) | 0; + hi = (hi + Math.imul(ah3, bh8)) | 0; + lo = (lo + Math.imul(al2, bl9)) | 0; + mid = (mid + Math.imul(al2, bh9)) | 0; + mid = (mid + Math.imul(ah2, bl9)) | 0; + hi = (hi + Math.imul(ah2, bh9)) | 0; + var w11 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w11 >>> 26)) | 0; + w11 &= 0x3ffffff; + /* k = 12 */ + lo = Math.imul(al9, bl3); + mid = Math.imul(al9, bh3); + mid = (mid + Math.imul(ah9, bl3)) | 0; + hi = Math.imul(ah9, bh3); + lo = (lo + Math.imul(al8, bl4)) | 0; + mid = (mid + Math.imul(al8, bh4)) | 0; + mid = (mid + Math.imul(ah8, bl4)) | 0; + hi = (hi + Math.imul(ah8, bh4)) | 0; + lo = (lo + Math.imul(al7, bl5)) | 0; + mid = (mid + Math.imul(al7, bh5)) | 0; + mid = (mid + Math.imul(ah7, bl5)) | 0; + hi = (hi + Math.imul(ah7, bh5)) | 0; + lo = (lo + Math.imul(al6, bl6)) | 0; + mid = (mid + Math.imul(al6, bh6)) | 0; + mid = (mid + Math.imul(ah6, bl6)) | 0; + hi = (hi + Math.imul(ah6, bh6)) | 0; + lo = (lo + Math.imul(al5, bl7)) | 0; + mid = (mid + Math.imul(al5, bh7)) | 0; + mid = (mid + Math.imul(ah5, bl7)) | 0; + hi = (hi + Math.imul(ah5, bh7)) | 0; + lo = (lo + Math.imul(al4, bl8)) | 0; + mid = (mid + Math.imul(al4, bh8)) | 0; + mid = (mid + Math.imul(ah4, bl8)) | 0; + hi = (hi + Math.imul(ah4, bh8)) | 0; + lo = (lo + Math.imul(al3, bl9)) | 0; + mid = (mid + Math.imul(al3, bh9)) | 0; + mid = (mid + Math.imul(ah3, bl9)) | 0; + hi = (hi + Math.imul(ah3, bh9)) | 0; + var w12 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w12 >>> 26)) | 0; + w12 &= 0x3ffffff; + /* k = 13 */ + lo = Math.imul(al9, bl4); + mid = Math.imul(al9, bh4); + mid = (mid + Math.imul(ah9, bl4)) | 0; + hi = Math.imul(ah9, bh4); + lo = (lo + Math.imul(al8, bl5)) | 0; + mid = (mid + Math.imul(al8, bh5)) | 0; + mid = (mid + Math.imul(ah8, bl5)) | 0; + hi = (hi + Math.imul(ah8, bh5)) | 0; + lo = (lo + Math.imul(al7, bl6)) | 0; + mid = (mid + Math.imul(al7, bh6)) | 0; + mid = (mid + Math.imul(ah7, bl6)) | 0; + hi = (hi + Math.imul(ah7, bh6)) | 0; + lo = (lo + Math.imul(al6, bl7)) | 0; + mid = (mid + Math.imul(al6, bh7)) | 0; + mid = (mid + Math.imul(ah6, bl7)) | 0; + hi = (hi + Math.imul(ah6, bh7)) | 0; + lo = (lo + Math.imul(al5, bl8)) | 0; + mid = (mid + Math.imul(al5, bh8)) | 0; + mid = (mid + Math.imul(ah5, bl8)) | 0; + hi = (hi + Math.imul(ah5, bh8)) | 0; + lo = (lo + Math.imul(al4, bl9)) | 0; + mid = (mid + Math.imul(al4, bh9)) | 0; + mid = (mid + Math.imul(ah4, bl9)) | 0; + hi = (hi + Math.imul(ah4, bh9)) | 0; + var w13 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w13 >>> 26)) | 0; + w13 &= 0x3ffffff; + /* k = 14 */ + lo = Math.imul(al9, bl5); + mid = Math.imul(al9, bh5); + mid = (mid + Math.imul(ah9, bl5)) | 0; + hi = Math.imul(ah9, bh5); + lo = (lo + Math.imul(al8, bl6)) | 0; + mid = (mid + Math.imul(al8, bh6)) | 0; + mid = (mid + Math.imul(ah8, bl6)) | 0; + hi = (hi + Math.imul(ah8, bh6)) | 0; + lo = (lo + Math.imul(al7, bl7)) | 0; + mid = (mid + Math.imul(al7, bh7)) | 0; + mid = (mid + Math.imul(ah7, bl7)) | 0; + hi = (hi + Math.imul(ah7, bh7)) | 0; + lo = (lo + Math.imul(al6, bl8)) | 0; + mid = (mid + Math.imul(al6, bh8)) | 0; + mid = (mid + Math.imul(ah6, bl8)) | 0; + hi = (hi + Math.imul(ah6, bh8)) | 0; + lo = (lo + Math.imul(al5, bl9)) | 0; + mid = (mid + Math.imul(al5, bh9)) | 0; + mid = (mid + Math.imul(ah5, bl9)) | 0; + hi = (hi + Math.imul(ah5, bh9)) | 0; + var w14 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w14 >>> 26)) | 0; + w14 &= 0x3ffffff; + /* k = 15 */ + lo = Math.imul(al9, bl6); + mid = Math.imul(al9, bh6); + mid = (mid + Math.imul(ah9, bl6)) | 0; + hi = Math.imul(ah9, bh6); + lo = (lo + Math.imul(al8, bl7)) | 0; + mid = (mid + Math.imul(al8, bh7)) | 0; + mid = (mid + Math.imul(ah8, bl7)) | 0; + hi = (hi + Math.imul(ah8, bh7)) | 0; + lo = (lo + Math.imul(al7, bl8)) | 0; + mid = (mid + Math.imul(al7, bh8)) | 0; + mid = (mid + Math.imul(ah7, bl8)) | 0; + hi = (hi + Math.imul(ah7, bh8)) | 0; + lo = (lo + Math.imul(al6, bl9)) | 0; + mid = (mid + Math.imul(al6, bh9)) | 0; + mid = (mid + Math.imul(ah6, bl9)) | 0; + hi = (hi + Math.imul(ah6, bh9)) | 0; + var w15 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w15 >>> 26)) | 0; + w15 &= 0x3ffffff; + /* k = 16 */ + lo = Math.imul(al9, bl7); + mid = Math.imul(al9, bh7); + mid = (mid + Math.imul(ah9, bl7)) | 0; + hi = Math.imul(ah9, bh7); + lo = (lo + Math.imul(al8, bl8)) | 0; + mid = (mid + Math.imul(al8, bh8)) | 0; + mid = (mid + Math.imul(ah8, bl8)) | 0; + hi = (hi + Math.imul(ah8, bh8)) | 0; + lo = (lo + Math.imul(al7, bl9)) | 0; + mid = (mid + Math.imul(al7, bh9)) | 0; + mid = (mid + Math.imul(ah7, bl9)) | 0; + hi = (hi + Math.imul(ah7, bh9)) | 0; + var w16 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w16 >>> 26)) | 0; + w16 &= 0x3ffffff; + /* k = 17 */ + lo = Math.imul(al9, bl8); + mid = Math.imul(al9, bh8); + mid = (mid + Math.imul(ah9, bl8)) | 0; + hi = Math.imul(ah9, bh8); + lo = (lo + Math.imul(al8, bl9)) | 0; + mid = (mid + Math.imul(al8, bh9)) | 0; + mid = (mid + Math.imul(ah8, bl9)) | 0; + hi = (hi + Math.imul(ah8, bh9)) | 0; + var w17 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w17 >>> 26)) | 0; + w17 &= 0x3ffffff; + /* k = 18 */ + lo = Math.imul(al9, bl9); + mid = Math.imul(al9, bh9); + mid = (mid + Math.imul(ah9, bl9)) | 0; + hi = Math.imul(ah9, bh9); + var w18 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0; + c = (((hi + (mid >>> 13)) | 0) + (w18 >>> 26)) | 0; + w18 &= 0x3ffffff; + o[0] = w0; + o[1] = w1; + o[2] = w2; + o[3] = w3; + o[4] = w4; + o[5] = w5; + o[6] = w6; + o[7] = w7; + o[8] = w8; + o[9] = w9; + o[10] = w10; + o[11] = w11; + o[12] = w12; + o[13] = w13; + o[14] = w14; + o[15] = w15; + o[16] = w16; + o[17] = w17; + o[18] = w18; + if (c !== 0) { + o[19] = c; + out.length++; + } + return out; +}; + +// Polyfill comb +if (!Math.imul) { + comb10MulTo = smallMulTo; +} + +function bigMulTo(self, num, out) { + out.negative = num.negative ^ self.negative; + out.length = self.length + num.length; + + var carry = 0; + var hncarry = 0; + for (var k = 0; k < out.length - 1; k++) { + // Sum all words with the same `i + j = k` and accumulate `ncarry`, + // note that ncarry could be >= 0x3ffffff + var ncarry = hncarry; + hncarry = 0; + var rword = carry & 0x3ffffff; + var maxJ = Math.min(k, num.length - 1); + for (var j = Math.max(0, k - self.length + 1); j <= maxJ; j++) { + var i = k - j; + var a = self.words[i] | 0; + var b = num.words[j] | 0; + var r = a * b; + + var lo = r & 0x3ffffff; + ncarry = (ncarry + ((r / 0x4000000) | 0)) | 0; + lo = (lo + rword) | 0; + rword = lo & 0x3ffffff; + ncarry = (ncarry + (lo >>> 26)) | 0; + + hncarry += ncarry >>> 26; + ncarry &= 0x3ffffff; + } + out.words[k] = rword; + carry = ncarry; + ncarry = hncarry; + } + if (carry !== 0) { + out.words[k] = carry; + } else { + out.length--; + } + + return out._strip(); +} + +function jumboMulTo(self, num, out) { + // Temporary disable, see https://github.com/indutny/bn.js/issues/211 + // var fftm = new FFTM(); + // return fftm.mulp(self, num, out); + return bigMulTo(self, num, out); +} + +BN.prototype.mulTo = function mulTo(num, out) { + var res; + var len = this.length + num.length; + if (this.length === 10 && num.length === 10) { + res = comb10MulTo(this, num, out); + } else if (len < 63) { + res = smallMulTo(this, num, out); + } else if (len < 1024) { + res = bigMulTo(this, num, out); + } else { + res = jumboMulTo(this, num, out); + } + + return res; +}; + +// Cooley-Tukey algorithm for FFT +// slightly revisited to rely on looping instead of recursion + +function FFTM(x, y) { + this.x = x; + this.y = y; +} + +FFTM.prototype.makeRBT = function makeRBT(N) { + var t = new Array(N); + var l = BN.prototype._countBits(N) - 1; + for (var i = 0; i < N; i++) { + t[i] = this.revBin(i, l, N); + } + + return t; +}; + +// Returns binary-reversed representation of `x` +FFTM.prototype.revBin = function revBin(x, l, N) { + if (x === 0 || x === N - 1) return x; + + var rb = 0; + for (var i = 0; i < l; i++) { + rb |= (x & 1) << (l - i - 1); + x >>= 1; + } + + return rb; +}; + +// Performs "tweedling" phase, therefore 'emulating' +// behaviour of the recursive algorithm +FFTM.prototype.permute = function permute(rbt, rws, iws, rtws, itws, N) { + for (var i = 0; i < N; i++) { + rtws[i] = rws[rbt[i]]; + itws[i] = iws[rbt[i]]; + } +}; + +FFTM.prototype.transform = function transform(rws, iws, rtws, itws, N, rbt) { + this.permute(rbt, rws, iws, rtws, itws, N); + + for (var s = 1; s < N; s <<= 1) { + var l = s << 1; + + var rtwdf = Math.cos(2 * Math.PI / l); + var itwdf = Math.sin(2 * Math.PI / l); + + for (var p = 0; p < N; p += l) { + var rtwdf_ = rtwdf; + var itwdf_ = itwdf; + + for (var j = 0; j < s; j++) { + var re = rtws[p + j]; + var ie = itws[p + j]; + + var ro = rtws[p + j + s]; + var io = itws[p + j + s]; + + var rx = rtwdf_ * ro - itwdf_ * io; + + io = rtwdf_ * io + itwdf_ * ro; + ro = rx; + + rtws[p + j] = re + ro; + itws[p + j] = ie + io; + + rtws[p + j + s] = re - ro; + itws[p + j + s] = ie - io; + + /* jshint maxdepth : false */ + if (j !== l) { + rx = rtwdf * rtwdf_ - itwdf * itwdf_; + + itwdf_ = rtwdf * itwdf_ + itwdf * rtwdf_; + rtwdf_ = rx; + } + } + } + } +}; + +FFTM.prototype.guessLen13b = function guessLen13b(n, m) { + var N = Math.max(m, n) | 1; + var odd = N & 1; + var i = 0; + for (N = N / 2 | 0; N; N = N >>> 1) { + i++; + } + + return 1 << i + 1 + odd; +}; + +FFTM.prototype.conjugate = function conjugate(rws, iws, N) { + if (N <= 1) return; + + for (var i = 0; i < N / 2; i++) { + var t = rws[i]; + + rws[i] = rws[N - i - 1]; + rws[N - i - 1] = t; + + t = iws[i]; + + iws[i] = -iws[N - i - 1]; + iws[N - i - 1] = -t; + } +}; + +FFTM.prototype.normalize13b = function normalize13b(ws, N) { + var carry = 0; + for (var i = 0; i < N / 2; i++) { + var w = Math.round(ws[2 * i + 1] / N) * 0x2000 + + Math.round(ws[2 * i] / N) + + carry; + + ws[i] = w & 0x3ffffff; + + if (w < 0x4000000) { + carry = 0; + } else { + carry = w / 0x4000000 | 0; + } + } + + return ws; +}; + +FFTM.prototype.convert13b = function convert13b(ws, len, rws, N) { + var carry = 0; + for (var i = 0; i < len; i++) { + carry = carry + (ws[i] | 0); + + rws[2 * i] = carry & 0x1fff; + carry = carry >>> 13; + rws[2 * i + 1] = carry & 0x1fff; + carry = carry >>> 13; + } + + // Pad with zeroes + for (i = 2 * len; i < N; ++i) { + rws[i] = 0; + } + + assert(carry === 0); + assert((carry & ~0x1fff) === 0); +}; + +FFTM.prototype.stub = function stub(N) { + var ph = new Array(N); + for (var i = 0; i < N; i++) { + ph[i] = 0; + } + + return ph; +}; + +FFTM.prototype.mulp = function mulp(x, y, out) { + var N = 2 * this.guessLen13b(x.length, y.length); + + var rbt = this.makeRBT(N); + + var _ = this.stub(N); + + var rws = new Array(N); + var rwst = new Array(N); + var iwst = new Array(N); + + var nrws = new Array(N); + var nrwst = new Array(N); + var niwst = new Array(N); + + var rmws = out.words; + rmws.length = N; + + this.convert13b(x.words, x.length, rws, N); + this.convert13b(y.words, y.length, nrws, N); + + this.transform(rws, _, rwst, iwst, N, rbt); + this.transform(nrws, _, nrwst, niwst, N, rbt); + + for (var i = 0; i < N; i++) { + var rx = rwst[i] * nrwst[i] - iwst[i] * niwst[i]; + iwst[i] = rwst[i] * niwst[i] + iwst[i] * nrwst[i]; + rwst[i] = rx; + } + + this.conjugate(rwst, iwst, N); + this.transform(rwst, iwst, rmws, _, N, rbt); + this.conjugate(rmws, _, N); + this.normalize13b(rmws, N); + + out.negative = x.negative ^ y.negative; + out.length = x.length + y.length; + return out._strip(); +}; + +// Multiply `this` by `num` +BN.prototype.mul = function mul(num) { + var out = new BN(null); + out.words = new Array(this.length + num.length); + return this.mulTo(num, out); +}; + +// Multiply employing FFT +BN.prototype.mulf = function mulf(num) { + var out = new BN(null); + out.words = new Array(this.length + num.length); + return jumboMulTo(this, num, out); +}; + +// In-place Multiplication +BN.prototype.imul = function imul(num) { + return this.clone().mulTo(num, this); +}; + +BN.prototype.imuln = function imuln(num) { + var isNegNum = num < 0; + if (isNegNum) num = -num; + + assert(typeof num === "number"); + assert(num < 0x4000000); + + // Carry + var carry = 0; + for (var i = 0; i < this.length; i++) { + var w = (this.words[i] | 0) * num; + var lo = (w & 0x3ffffff) + (carry & 0x3ffffff); + carry >>= 26; + carry += (w / 0x4000000) | 0; + // NOTE: lo is 27bit maximum + carry += lo >>> 26; + this.words[i] = lo & 0x3ffffff; + } + + if (carry !== 0) { + this.words[i] = carry; + this.length++; + } + + return isNegNum ? this.ineg() : this; +}; + +BN.prototype.muln = function muln(num) { + return this.clone().imuln(num); +}; + +// `this` * `this` +BN.prototype.sqr = function sqr() { + return this.mul(this); +}; + +// `this` * `this` in-place +BN.prototype.isqr = function isqr() { + return this.imul(this.clone()); +}; + +// Math.pow(`this`, `num`) +BN.prototype.pow = function pow(num) { + var w = toBitArray(num); + if (w.length === 0) return new BN(1); + + // Skip leading zeroes + var res = this; + for (var i = 0; i < w.length; i++, res = res.sqr()) { + if (w[i] !== 0) break; + } + + if (++i < w.length) { + for (var q = res.sqr(); i < w.length; i++, q = q.sqr()) { + if (w[i] === 0) continue; + + res = res.mul(q); + } + } + + return res; +}; + +// Shift-left in-place +BN.prototype.iushln = function iushln(bits) { + assert(typeof bits === "number" && bits >= 0); + var r = bits % 26; + var s = (bits - r) / 26; + var carryMask = (0x3ffffff >>> (26 - r)) << (26 - r); + var i; + + if (r !== 0) { + var carry = 0; + + for (i = 0; i < this.length; i++) { + var newCarry = this.words[i] & carryMask; + var c = ((this.words[i] | 0) - newCarry) << r; + this.words[i] = c | carry; + carry = newCarry >>> (26 - r); + } + + if (carry) { + this.words[i] = carry; + this.length++; + } + } + + if (s !== 0) { + for (i = this.length - 1; i >= 0; i--) { + this.words[i + s] = this.words[i]; + } + + for (i = 0; i < s; i++) { + this.words[i] = 0; + } + + this.length += s; + } + + return this._strip(); +}; + +BN.prototype.ishln = function ishln(bits) { + // TODO(indutny): implement me + assert(this.negative === 0); + return this.iushln(bits); +}; + +// Shift-right in-place +// NOTE: `hint` is a lowest bit before trailing zeroes +// NOTE: if `extended` is present - it will be filled with destroyed bits +BN.prototype.iushrn = function iushrn(bits, hint, extended) { + assert(typeof bits === "number" && bits >= 0); + var h; + if (hint) { + h = (hint - (hint % 26)) / 26; + } else { + h = 0; + } + + var r = bits % 26; + var s = Math.min((bits - r) / 26, this.length); + var mask = 0x3ffffff ^ ((0x3ffffff >>> r) << r); + var maskedWords = extended; + + h -= s; + h = Math.max(0, h); + + // Extended mode, copy masked part + if (maskedWords) { + for (var i = 0; i < s; i++) { + maskedWords.words[i] = this.words[i]; + } + maskedWords.length = s; + } + + if (s === 0) { + // No-op, we should not move anything at all + } else if (this.length > s) { + this.length -= s; + for (i = 0; i < this.length; i++) { + this.words[i] = this.words[i + s]; + } + } else { + this.words[0] = 0; + this.length = 1; + } + + var carry = 0; + for (i = this.length - 1; i >= 0 && (carry !== 0 || i >= h); i--) { + var word = this.words[i] | 0; + this.words[i] = (carry << (26 - r)) | (word >>> r); + carry = word & mask; + } + + // Push carried bits as a mask + if (maskedWords && carry !== 0) { + maskedWords.words[maskedWords.length++] = carry; + } + + if (this.length === 0) { + this.words[0] = 0; + this.length = 1; + } + + return this._strip(); +}; + +BN.prototype.ishrn = function ishrn(bits, hint, extended) { + // TODO(indutny): implement me + assert(this.negative === 0); + return this.iushrn(bits, hint, extended); +}; + +// Shift-left +BN.prototype.shln = function shln(bits) { + return this.clone().ishln(bits); +}; + +BN.prototype.ushln = function ushln(bits) { + return this.clone().iushln(bits); +}; + +// Shift-right +BN.prototype.shrn = function shrn(bits) { + return this.clone().ishrn(bits); +}; + +BN.prototype.ushrn = function ushrn(bits) { + return this.clone().iushrn(bits); +}; + +// Test if n bit is set +BN.prototype.testn = function testn(bit) { + assert(typeof bit === "number" && bit >= 0); + var r = bit % 26; + var s = (bit - r) / 26; + var q = 1 << r; + + // Fast case: bit is much higher than all existing words + if (this.length <= s) return false; + + // Check bit and return + var w = this.words[s]; + + return !!(w & q); +}; + +// Return only lowers bits of number (in-place) +BN.prototype.imaskn = function imaskn(bits) { + assert(typeof bits === "number" && bits >= 0); + var r = bits % 26; + var s = (bits - r) / 26; + + assert(this.negative === 0, "imaskn works only with positive numbers"); + + if (this.length <= s) { + return this; + } + + if (r !== 0) { + s++; + } + this.length = Math.min(s, this.length); + + if (r !== 0) { + var mask = 0x3ffffff ^ ((0x3ffffff >>> r) << r); + this.words[this.length - 1] &= mask; + } + + return this._strip(); +}; + +// Return only lowers bits of number +BN.prototype.maskn = function maskn(bits) { + return this.clone().imaskn(bits); +}; + +// Add plain number `num` to `this` +BN.prototype.iaddn = function iaddn(num) { + assert(typeof num === "number"); + assert(num < 0x4000000); + if (num < 0) return this.isubn(-num); + + // Possible sign change + if (this.negative !== 0) { + if (this.length === 1 && (this.words[0] | 0) <= num) { + this.words[0] = num - (this.words[0] | 0); + this.negative = 0; + return this; + } + + this.negative = 0; + this.isubn(num); + this.negative = 1; + return this; + } + + // Add without checks + return this._iaddn(num); +}; + +BN.prototype._iaddn = function _iaddn(num) { + this.words[0] += num; + + // Carry + for (var i = 0; i < this.length && this.words[i] >= 0x4000000; i++) { + this.words[i] -= 0x4000000; + if (i === this.length - 1) { + this.words[i + 1] = 1; + } else { + this.words[i + 1]++; + } + } + this.length = Math.max(this.length, i + 1); + + return this; +}; + +// Subtract plain number `num` from `this` +BN.prototype.isubn = function isubn(num) { + assert(typeof num === "number"); + assert(num < 0x4000000); + if (num < 0) return this.iaddn(-num); + + if (this.negative !== 0) { + this.negative = 0; + this.iaddn(num); + this.negative = 1; + return this; + } + + this.words[0] -= num; + + if (this.length === 1 && this.words[0] < 0) { + this.words[0] = -this.words[0]; + this.negative = 1; + } else { + // Carry + for (var i = 0; i < this.length && this.words[i] < 0; i++) { + this.words[i] += 0x4000000; + this.words[i + 1] -= 1; + } + } + + return this._strip(); +}; + +BN.prototype.addn = function addn(num) { + return this.clone().iaddn(num); +}; + +BN.prototype.subn = function subn(num) { + return this.clone().isubn(num); +}; + +BN.prototype.iabs = function iabs() { + this.negative = 0; + + return this; +}; + +BN.prototype.abs = function abs() { + return this.clone().iabs(); +}; + +BN.prototype._ishlnsubmul = function _ishlnsubmul(num, mul, shift) { + var len = num.length + shift; + var i; + + this._expand(len); + + var w; + var carry = 0; + for (i = 0; i < num.length; i++) { + w = (this.words[i + shift] | 0) + carry; + var right = (num.words[i] | 0) * mul; + w -= right & 0x3ffffff; + carry = (w >> 26) - ((right / 0x4000000) | 0); + this.words[i + shift] = w & 0x3ffffff; + } + for (; i < this.length - shift; i++) { + w = (this.words[i + shift] | 0) + carry; + carry = w >> 26; + this.words[i + shift] = w & 0x3ffffff; + } + + if (carry === 0) return this._strip(); + + // Subtraction overflow + assert(carry === -1); + carry = 0; + for (i = 0; i < this.length; i++) { + w = -(this.words[i] | 0) + carry; + carry = w >> 26; + this.words[i] = w & 0x3ffffff; + } + this.negative = 1; + + return this._strip(); +}; + +BN.prototype._wordDiv = function _wordDiv(num, mode) { + var shift = this.length - num.length; + + var a = this.clone(); + var b = num; + + // Normalize + var bhi = b.words[b.length - 1] | 0; + var bhiBits = this._countBits(bhi); + shift = 26 - bhiBits; + if (shift !== 0) { + b = b.ushln(shift); + a.iushln(shift); + bhi = b.words[b.length - 1] | 0; + } + + // Initialize quotient + var m = a.length - b.length; + var q; + + if (mode !== "mod") { + q = new BN(null); + q.length = m + 1; + q.words = new Array(q.length); + for (var i = 0; i < q.length; i++) { + q.words[i] = 0; + } + } + + var diff = a.clone()._ishlnsubmul(b, 1, m); + if (diff.negative === 0) { + a = diff; + if (q) { + q.words[m] = 1; + } + } + + for (var j = m - 1; j >= 0; j--) { + var qj = (a.words[b.length + j] | 0) * 0x4000000 + + (a.words[b.length + j - 1] | 0); + + // NOTE: (qj / bhi) is (0x3ffffff * 0x4000000 + 0x3ffffff) / 0x2000000 max + // (0x7ffffff) + qj = Math.min((qj / bhi) | 0, 0x3ffffff); + + a._ishlnsubmul(b, qj, j); + while (a.negative !== 0) { + qj--; + a.negative = 0; + a._ishlnsubmul(b, 1, j); + if (!a.isZero()) { + a.negative ^= 1; + } + } + if (q) { + q.words[j] = qj; + } + } + if (q) { + q._strip(); + } + a._strip(); + + // Denormalize + if (mode !== "div" && shift !== 0) { + a.iushrn(shift); + } + + return { + div: q || null, + mod: a, + }; +}; + +// NOTE: 1) `mode` can be set to `mod` to request mod only, +// to `div` to request div only, or be absent to +// request both div & mod +// 2) `positive` is true if unsigned mod is requested +BN.prototype.divmod = function divmod(num, mode, positive) { + assert(!num.isZero()); + + if (this.isZero()) { + return { + div: new BN(0), + mod: new BN(0), + }; + } + + var div, mod, res; + if (this.negative !== 0 && num.negative === 0) { + res = this.neg().divmod(num, mode); + + if (mode !== "mod") { + div = res.div.neg(); + } + + if (mode !== "div") { + mod = res.mod.neg(); + if (positive && mod.negative !== 0) { + mod.iadd(num); + } + } + + return { + div: div, + mod: mod, + }; + } + + if (this.negative === 0 && num.negative !== 0) { + res = this.divmod(num.neg(), mode); + + if (mode !== "mod") { + div = res.div.neg(); + } + + return { + div: div, + mod: res.mod, + }; + } + + if ((this.negative & num.negative) !== 0) { + res = this.neg().divmod(num.neg(), mode); + + if (mode !== "div") { + mod = res.mod.neg(); + if (positive && mod.negative !== 0) { + mod.isub(num); + } + } + + return { + div: res.div, + mod: mod, + }; + } + + // Both numbers are positive at this point + + // Strip both numbers to approximate shift value + if (num.length > this.length || this.cmp(num) < 0) { + return { + div: new BN(0), + mod: this, + }; + } + + // Very short reduction + if (num.length === 1) { + if (mode === "div") { + return { + div: this.divn(num.words[0]), + mod: null, + }; + } + + if (mode === "mod") { + return { + div: null, + mod: new BN(this.modrn(num.words[0])), + }; + } + + return { + div: this.divn(num.words[0]), + mod: new BN(this.modrn(num.words[0])), + }; + } + + return this._wordDiv(num, mode); +}; + +// Find `this` / `num` +BN.prototype.div = function div(num) { + return this.divmod(num, "div", false).div; +}; + +// Find `this` % `num` +BN.prototype.mod = function mod(num) { + return this.divmod(num, "mod", false).mod; +}; + +BN.prototype.umod = function umod(num) { + return this.divmod(num, "mod", true).mod; +}; + +// Find Round(`this` / `num`) +BN.prototype.divRound = function divRound(num) { + var dm = this.divmod(num); + + // Fast case - exact division + if (dm.mod.isZero()) return dm.div; + + var mod = dm.div.negative !== 0 ? dm.mod.isub(num) : dm.mod; + + var half = num.ushrn(1); + var r2 = num.andln(1); + var cmp = mod.cmp(half); + + // Round down + if (cmp < 0 || (r2 === 1 && cmp === 0)) return dm.div; + + // Round up + return dm.div.negative !== 0 ? dm.div.isubn(1) : dm.div.iaddn(1); +}; + +BN.prototype.modrn = function modrn(num) { + var isNegNum = num < 0; + if (isNegNum) num = -num; + + assert(num <= 0x3ffffff); + var p = (1 << 26) % num; + + var acc = 0; + for (var i = this.length - 1; i >= 0; i--) { + acc = (p * acc + (this.words[i] | 0)) % num; + } + + return isNegNum ? -acc : acc; +}; + +// WARNING: DEPRECATED +BN.prototype.modn = function modn(num) { + return this.modrn(num); +}; + +// In-place division by number +BN.prototype.idivn = function idivn(num) { + var isNegNum = num < 0; + if (isNegNum) num = -num; + + assert(num <= 0x3ffffff); + + var carry = 0; + for (var i = this.length - 1; i >= 0; i--) { + var w = (this.words[i] | 0) + carry * 0x4000000; + this.words[i] = (w / num) | 0; + carry = w % num; + } + + this._strip(); + return isNegNum ? this.ineg() : this; +}; + +BN.prototype.divn = function divn(num) { + return this.clone().idivn(num); +}; + +BN.prototype.egcd = function egcd(p) { + assert(p.negative === 0); + assert(!p.isZero()); + + var x = this; + var y = p.clone(); + + if (x.negative !== 0) { + x = x.umod(p); + } else { + x = x.clone(); + } + + // A * x + B * y = x + var A = new BN(1); + var B = new BN(0); + + // C * x + D * y = y + var C = new BN(0); + var D = new BN(1); + + var g = 0; + + while (x.isEven() && y.isEven()) { + x.iushrn(1); + y.iushrn(1); + ++g; + } + + var yp = y.clone(); + var xp = x.clone(); + + while (!x.isZero()) { + for (var i = 0, im = 1; (x.words[0] & im) === 0 && i < 26; ++i, im <<= 1); + if (i > 0) { + x.iushrn(i); + while (i-- > 0) { + if (A.isOdd() || B.isOdd()) { + A.iadd(yp); + B.isub(xp); + } + + A.iushrn(1); + B.iushrn(1); + } + } + + for (var j = 0, jm = 1; (y.words[0] & jm) === 0 && j < 26; ++j, jm <<= 1); + if (j > 0) { + y.iushrn(j); + while (j-- > 0) { + if (C.isOdd() || D.isOdd()) { + C.iadd(yp); + D.isub(xp); + } + + C.iushrn(1); + D.iushrn(1); + } + } + + if (x.cmp(y) >= 0) { + x.isub(y); + A.isub(C); + B.isub(D); + } else { + y.isub(x); + C.isub(A); + D.isub(B); + } + } + + return { + a: C, + b: D, + gcd: y.iushln(g), + }; +}; + +// This is reduced incarnation of the binary EEA +// above, designated to invert members of the +// _prime_ fields F(p) at a maximal speed +BN.prototype._invmp = function _invmp(p) { + assert(p.negative === 0); + assert(!p.isZero()); + + var a = this; + var b = p.clone(); + + if (a.negative !== 0) { + a = a.umod(p); + } else { + a = a.clone(); + } + + var x1 = new BN(1); + var x2 = new BN(0); + + var delta = b.clone(); + + while (a.cmpn(1) > 0 && b.cmpn(1) > 0) { + for (var i = 0, im = 1; (a.words[0] & im) === 0 && i < 26; ++i, im <<= 1); + if (i > 0) { + a.iushrn(i); + while (i-- > 0) { + if (x1.isOdd()) { + x1.iadd(delta); + } + + x1.iushrn(1); + } + } + + for (var j = 0, jm = 1; (b.words[0] & jm) === 0 && j < 26; ++j, jm <<= 1); + if (j > 0) { + b.iushrn(j); + while (j-- > 0) { + if (x2.isOdd()) { + x2.iadd(delta); + } + + x2.iushrn(1); + } + } + + if (a.cmp(b) >= 0) { + a.isub(b); + x1.isub(x2); + } else { + b.isub(a); + x2.isub(x1); + } + } + + var res; + if (a.cmpn(1) === 0) { + res = x1; + } else { + res = x2; + } + + if (res.cmpn(0) < 0) { + res.iadd(p); + } + + return res; +}; + +BN.prototype.gcd = function gcd(num) { + if (this.isZero()) return num.abs(); + if (num.isZero()) return this.abs(); + + var a = this.clone(); + var b = num.clone(); + a.negative = 0; + b.negative = 0; + + // Remove common factor of two + for (var shift = 0; a.isEven() && b.isEven(); shift++) { + a.iushrn(1); + b.iushrn(1); + } + + do { + while (a.isEven()) { + a.iushrn(1); + } + while (b.isEven()) { + b.iushrn(1); + } + + var r = a.cmp(b); + if (r < 0) { + // Swap `a` and `b` to make `a` always bigger than `b` + var t = a; + a = b; + b = t; + } else if (r === 0 || b.cmpn(1) === 0) { + break; + } + + a.isub(b); + } while (true); + + return b.iushln(shift); +}; + +// Invert number in the field F(num) +BN.prototype.invm = function invm(num) { + return this.egcd(num).a.umod(num); +}; + +BN.prototype.isEven = function isEven() { + return (this.words[0] & 1) === 0; +}; + +BN.prototype.isOdd = function isOdd() { + return (this.words[0] & 1) === 1; +}; + +// And first word and num +BN.prototype.andln = function andln(num) { + return this.words[0] & num; +}; + +// Increment at the bit position in-line +BN.prototype.bincn = function bincn(bit) { + assert(typeof bit === "number"); + var r = bit % 26; + var s = (bit - r) / 26; + var q = 1 << r; + + // Fast case: bit is much higher than all existing words + if (this.length <= s) { + this._expand(s + 1); + this.words[s] |= q; + return this; + } + + // Add bit and propagate, if needed + var carry = q; + for (var i = s; carry !== 0 && i < this.length; i++) { + var w = this.words[i] | 0; + w += carry; + carry = w >>> 26; + w &= 0x3ffffff; + this.words[i] = w; + } + if (carry !== 0) { + this.words[i] = carry; + this.length++; + } + return this; +}; + +BN.prototype.isZero = function isZero() { + return this.length === 1 && this.words[0] === 0; +}; + +BN.prototype.cmpn = function cmpn(num) { + var negative = num < 0; + + if (this.negative !== 0 && !negative) return -1; + if (this.negative === 0 && negative) return 1; + + this._strip(); + + var res; + if (this.length > 1) { + res = 1; + } else { + if (negative) { + num = -num; + } + + assert(num <= 0x3ffffff, "Number is too big"); + + var w = this.words[0] | 0; + res = w === num ? 0 : w < num ? -1 : 1; + } + if (this.negative !== 0) return -res | 0; + return res; +}; + +// Compare two numbers and return: +// 1 - if `this` > `num` +// 0 - if `this` == `num` +// -1 - if `this` < `num` +BN.prototype.cmp = function cmp(num) { + if (this.negative !== 0 && num.negative === 0) return -1; + if (this.negative === 0 && num.negative !== 0) return 1; + + var res = this.ucmp(num); + if (this.negative !== 0) return -res | 0; + return res; +}; + +// Unsigned comparison +BN.prototype.ucmp = function ucmp(num) { + // At this point both numbers have the same sign + if (this.length > num.length) return 1; + if (this.length < num.length) return -1; + + var res = 0; + for (var i = this.length - 1; i >= 0; i--) { + var a = this.words[i] | 0; + var b = num.words[i] | 0; + + if (a === b) continue; + if (a < b) { + res = -1; + } else if (a > b) { + res = 1; + } + break; + } + return res; +}; + +BN.prototype.gtn = function gtn(num) { + return this.cmpn(num) === 1; +}; + +BN.prototype.gt = function gt(num) { + return this.cmp(num) === 1; +}; + +BN.prototype.gten = function gten(num) { + return this.cmpn(num) >= 0; +}; + +BN.prototype.gte = function gte(num) { + return this.cmp(num) >= 0; +}; + +BN.prototype.ltn = function ltn(num) { + return this.cmpn(num) === -1; +}; + +BN.prototype.lt = function lt(num) { + return this.cmp(num) === -1; +}; + +BN.prototype.lten = function lten(num) { + return this.cmpn(num) <= 0; +}; + +BN.prototype.lte = function lte(num) { + return this.cmp(num) <= 0; +}; + +BN.prototype.eqn = function eqn(num) { + return this.cmpn(num) === 0; +}; + +BN.prototype.eq = function eq(num) { + return this.cmp(num) === 0; +}; + +// +// A reduce context, could be using montgomery or something better, depending +// on the `m` itself. +// +BN.red = function red(num) { + return new Red(num); +}; + +BN.prototype.toRed = function toRed(ctx) { + assert(!this.red, "Already a number in reduction context"); + assert(this.negative === 0, "red works only with positives"); + return ctx.convertTo(this)._forceRed(ctx); +}; + +BN.prototype.fromRed = function fromRed() { + assert(this.red, "fromRed works only with numbers in reduction context"); + return this.red.convertFrom(this); +}; + +BN.prototype._forceRed = function _forceRed(ctx) { + this.red = ctx; + return this; +}; + +BN.prototype.forceRed = function forceRed(ctx) { + assert(!this.red, "Already a number in reduction context"); + return this._forceRed(ctx); +}; + +BN.prototype.redAdd = function redAdd(num) { + assert(this.red, "redAdd works only with red numbers"); + return this.red.add(this, num); +}; + +BN.prototype.redIAdd = function redIAdd(num) { + assert(this.red, "redIAdd works only with red numbers"); + return this.red.iadd(this, num); +}; + +BN.prototype.redSub = function redSub(num) { + assert(this.red, "redSub works only with red numbers"); + return this.red.sub(this, num); +}; + +BN.prototype.redISub = function redISub(num) { + assert(this.red, "redISub works only with red numbers"); + return this.red.isub(this, num); +}; + +BN.prototype.redShl = function redShl(num) { + assert(this.red, "redShl works only with red numbers"); + return this.red.shl(this, num); +}; + +BN.prototype.redMul = function redMul(num) { + assert(this.red, "redMul works only with red numbers"); + this.red._verify2(this, num); + return this.red.mul(this, num); +}; + +BN.prototype.redIMul = function redIMul(num) { + assert(this.red, "redMul works only with red numbers"); + this.red._verify2(this, num); + return this.red.imul(this, num); +}; + +BN.prototype.redSqr = function redSqr() { + assert(this.red, "redSqr works only with red numbers"); + this.red._verify1(this); + return this.red.sqr(this); +}; + +BN.prototype.redISqr = function redISqr() { + assert(this.red, "redISqr works only with red numbers"); + this.red._verify1(this); + return this.red.isqr(this); +}; + +// Square root over p +BN.prototype.redSqrt = function redSqrt() { + assert(this.red, "redSqrt works only with red numbers"); + this.red._verify1(this); + return this.red.sqrt(this); +}; + +BN.prototype.redInvm = function redInvm() { + assert(this.red, "redInvm works only with red numbers"); + this.red._verify1(this); + return this.red.invm(this); +}; + +// Return negative clone of `this` % `red modulo` +BN.prototype.redNeg = function redNeg() { + assert(this.red, "redNeg works only with red numbers"); + this.red._verify1(this); + return this.red.neg(this); +}; + +BN.prototype.redPow = function redPow(num) { + assert(this.red && !num.red, "redPow(normalNum)"); + this.red._verify1(this); + return this.red.pow(this, num); +}; + +// Prime numbers with efficient reduction +var primes = { + k256: null, + p224: null, + p192: null, + p25519: null, +}; + +// Pseudo-Mersenne prime +function MPrime(name, p) { + // P = 2 ^ N - K + this.name = name; + this.p = new BN(p, 16); + this.n = this.p.bitLength(); + this.k = new BN(1).iushln(this.n).isub(this.p); + + this.tmp = this._tmp(); +} + +MPrime.prototype._tmp = function _tmp() { + var tmp = new BN(null); + tmp.words = new Array(Math.ceil(this.n / 13)); + return tmp; +}; + +MPrime.prototype.ireduce = function ireduce(num) { + // Assumes that `num` is less than `P^2` + // num = HI * (2 ^ N - K) + HI * K + LO = HI * K + LO (mod P) + var r = num; + var rlen; + + do { + this.split(r, this.tmp); + r = this.imulK(r); + r = r.iadd(this.tmp); + rlen = r.bitLength(); + } while (rlen > this.n); + + var cmp = rlen < this.n ? -1 : r.ucmp(this.p); + if (cmp === 0) { + r.words[0] = 0; + r.length = 1; + } else if (cmp > 0) { + r.isub(this.p); + } else { + if (r.strip !== undefined) { + // r is a BN v4 instance + r.strip(); + } else { + // r is a BN v5 instance + r._strip(); + } + } + + return r; +}; + +MPrime.prototype.split = function split(input, out) { + input.iushrn(this.n, 0, out); +}; + +MPrime.prototype.imulK = function imulK(num) { + return num.imul(this.k); +}; + +function K256() { + MPrime.call( + this, + "k256", + "ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f", + ); +} +inherits(K256, MPrime); + +K256.prototype.split = function split(input, output) { + // 256 = 9 * 26 + 22 + var mask = 0x3fffff; + + var outLen = Math.min(input.length, 9); + for (var i = 0; i < outLen; i++) { + output.words[i] = input.words[i]; + } + output.length = outLen; + + if (input.length <= 9) { + input.words[0] = 0; + input.length = 1; + return; + } + + // Shift by 9 limbs + var prev = input.words[9]; + output.words[output.length++] = prev & mask; + + for (i = 10; i < input.length; i++) { + var next = input.words[i] | 0; + input.words[i - 10] = ((next & mask) << 4) | (prev >>> 22); + prev = next; + } + prev >>>= 22; + input.words[i - 10] = prev; + if (prev === 0 && input.length > 10) { + input.length -= 10; + } else { + input.length -= 9; + } +}; + +K256.prototype.imulK = function imulK(num) { + // K = 0x1000003d1 = [ 0x40, 0x3d1 ] + num.words[num.length] = 0; + num.words[num.length + 1] = 0; + num.length += 2; + + // bounded at: 0x40 * 0x3ffffff + 0x3d0 = 0x100000390 + var lo = 0; + for (var i = 0; i < num.length; i++) { + var w = num.words[i] | 0; + lo += w * 0x3d1; + num.words[i] = lo & 0x3ffffff; + lo = w * 0x40 + ((lo / 0x4000000) | 0); + } + + // Fast length reduction + if (num.words[num.length - 1] === 0) { + num.length--; + if (num.words[num.length - 1] === 0) { + num.length--; + } + } + return num; +}; + +function P224() { + MPrime.call( + this, + "p224", + "ffffffff ffffffff ffffffff ffffffff 00000000 00000000 00000001", + ); +} +inherits(P224, MPrime); + +function P192() { + MPrime.call( + this, + "p192", + "ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff", + ); +} +inherits(P192, MPrime); + +function P25519() { + // 2 ^ 255 - 19 + MPrime.call( + this, + "25519", + "7fffffffffffffff ffffffffffffffff ffffffffffffffff ffffffffffffffed", + ); +} +inherits(P25519, MPrime); + +P25519.prototype.imulK = function imulK(num) { + // K = 0x13 + var carry = 0; + for (var i = 0; i < num.length; i++) { + var hi = (num.words[i] | 0) * 0x13 + carry; + var lo = hi & 0x3ffffff; + hi >>>= 26; + + num.words[i] = lo; + carry = hi; + } + if (carry !== 0) { + num.words[num.length++] = carry; + } + return num; +}; + +// Exported mostly for testing purposes, use plain name instead +BN._prime = function prime(name) { + // Cached version of prime + if (primes[name]) return primes[name]; + + var prime; + if (name === "k256") { + prime = new K256(); + } else if (name === "p224") { + prime = new P224(); + } else if (name === "p192") { + prime = new P192(); + } else if (name === "p25519") { + prime = new P25519(); + } else { + throw new Error("Unknown prime " + name); + } + primes[name] = prime; + + return prime; +}; + +// +// Base reduction engine +// +function Red(m) { + if (typeof m === "string") { + var prime = BN._prime(m); + this.m = prime.p; + this.prime = prime; + } else { + assert(m.gtn(1), "modulus must be greater than 1"); + this.m = m; + this.prime = null; + } +} + +Red.prototype._verify1 = function _verify1(a) { + assert(a.negative === 0, "red works only with positives"); + assert(a.red, "red works only with red numbers"); +}; + +Red.prototype._verify2 = function _verify2(a, b) { + assert((a.negative | b.negative) === 0, "red works only with positives"); + assert(a.red && a.red === b.red, "red works only with red numbers"); +}; + +Red.prototype.imod = function imod(a) { + if (this.prime) return this.prime.ireduce(a)._forceRed(this); + + move(a, a.umod(this.m)._forceRed(this)); + return a; +}; + +Red.prototype.neg = function neg(a) { + if (a.isZero()) { + return a.clone(); + } + + return this.m.sub(a)._forceRed(this); +}; + +Red.prototype.add = function add(a, b) { + this._verify2(a, b); + + var res = a.add(b); + if (res.cmp(this.m) >= 0) { + res.isub(this.m); + } + return res._forceRed(this); +}; + +Red.prototype.iadd = function iadd(a, b) { + this._verify2(a, b); + + var res = a.iadd(b); + if (res.cmp(this.m) >= 0) { + res.isub(this.m); + } + return res; +}; + +Red.prototype.sub = function sub(a, b) { + this._verify2(a, b); + + var res = a.sub(b); + if (res.cmpn(0) < 0) { + res.iadd(this.m); + } + return res._forceRed(this); +}; + +Red.prototype.isub = function isub(a, b) { + this._verify2(a, b); + + var res = a.isub(b); + if (res.cmpn(0) < 0) { + res.iadd(this.m); + } + return res; +}; + +Red.prototype.shl = function shl(a, num) { + this._verify1(a); + return this.imod(a.ushln(num)); +}; + +Red.prototype.imul = function imul(a, b) { + this._verify2(a, b); + return this.imod(a.imul(b)); +}; + +Red.prototype.mul = function mul(a, b) { + this._verify2(a, b); + return this.imod(a.mul(b)); +}; + +Red.prototype.isqr = function isqr(a) { + return this.imul(a, a.clone()); +}; + +Red.prototype.sqr = function sqr(a) { + return this.mul(a, a); +}; + +Red.prototype.sqrt = function sqrt(a) { + if (a.isZero()) return a.clone(); + + var mod3 = this.m.andln(3); + assert(mod3 % 2 === 1); + + // Fast case + if (mod3 === 3) { + var pow = this.m.add(new BN(1)).iushrn(2); + return this.pow(a, pow); + } + + // Tonelli-Shanks algorithm (Totally unoptimized and slow) + // + // Find Q and S, that Q * 2 ^ S = (P - 1) + var q = this.m.subn(1); + var s = 0; + while (!q.isZero() && q.andln(1) === 0) { + s++; + q.iushrn(1); + } + assert(!q.isZero()); + + var one = new BN(1).toRed(this); + var nOne = one.redNeg(); + + // Find quadratic non-residue + // NOTE: Max is such because of generalized Riemann hypothesis. + var lpow = this.m.subn(1).iushrn(1); + var z = this.m.bitLength(); + z = new BN(2 * z * z).toRed(this); + + while (this.pow(z, lpow).cmp(nOne) !== 0) { + z.redIAdd(nOne); + } + + var c = this.pow(z, q); + var r = this.pow(a, q.addn(1).iushrn(1)); + var t = this.pow(a, q); + var m = s; + while (t.cmp(one) !== 0) { + var tmp = t; + for (var i = 0; tmp.cmp(one) !== 0; i++) { + tmp = tmp.redSqr(); + } + assert(i < m); + var b = this.pow(c, new BN(1).iushln(m - i - 1)); + + r = r.redMul(b); + c = b.redSqr(); + t = t.redMul(c); + m = i; + } + + return r; +}; + +Red.prototype.invm = function invm(a) { + var inv = a._invmp(this.m); + if (inv.negative !== 0) { + inv.negative = 0; + return this.imod(inv).redNeg(); + } else { + return this.imod(inv); + } +}; + +Red.prototype.pow = function pow(a, num) { + if (num.isZero()) return new BN(1).toRed(this); + if (num.cmpn(1) === 0) return a.clone(); + + var windowSize = 4; + var wnd = new Array(1 << windowSize); + wnd[0] = new BN(1).toRed(this); + wnd[1] = a; + for (var i = 2; i < wnd.length; i++) { + wnd[i] = this.mul(wnd[i - 1], a); + } + + var res = wnd[0]; + var current = 0; + var currentLen = 0; + var start = num.bitLength() % 26; + if (start === 0) { + start = 26; + } + + for (i = num.length - 1; i >= 0; i--) { + var word = num.words[i]; + for (var j = start - 1; j >= 0; j--) { + var bit = (word >> j) & 1; + if (res !== wnd[0]) { + res = this.sqr(res); + } + + if (bit === 0 && current === 0) { + currentLen = 0; + continue; + } + + current <<= 1; + current |= bit; + currentLen++; + if (currentLen !== windowSize && (i !== 0 || j !== 0)) continue; + + res = this.mul(res, wnd[current]); + currentLen = 0; + current = 0; + } + start = 26; + } + + return res; +}; + +Red.prototype.convertTo = function convertTo(num) { + var r = num.umod(this.m); + + return r === num ? r.clone() : r; +}; + +Red.prototype.convertFrom = function convertFrom(num) { + var res = num.clone(); + res.red = null; + return res; +}; + +// +// Montgomery method engine +// + +BN.mont = function mont(num) { + return new Mont(num); +}; + +function Mont(m) { + Red.call(this, m); + + this.shift = this.m.bitLength(); + if (this.shift % 26 !== 0) { + this.shift += 26 - (this.shift % 26); + } + + this.r = new BN(1).iushln(this.shift); + this.r2 = this.imod(this.r.sqr()); + this.rinv = this.r._invmp(this.m); + + this.minv = this.rinv.mul(this.r).isubn(1).div(this.m); + this.minv = this.minv.umod(this.r); + this.minv = this.r.sub(this.minv); +} +inherits(Mont, Red); + +Mont.prototype.convertTo = function convertTo(num) { + return this.imod(num.ushln(this.shift)); +}; + +Mont.prototype.convertFrom = function convertFrom(num) { + var r = this.imod(num.mul(this.rinv)); + r.red = null; + return r; +}; + +Mont.prototype.imul = function imul(a, b) { + if (a.isZero() || b.isZero()) { + a.words[0] = 0; + a.length = 1; + return a; + } + + var t = a.imul(b); + var c = t.maskn(this.shift).mul(this.minv).imaskn(this.shift).mul(this.m); + var u = t.isub(c).iushrn(this.shift); + var res = u; + + if (u.cmp(this.m) >= 0) { + res = u.isub(this.m); + } else if (u.cmpn(0) < 0) { + res = u.iadd(this.m); + } + + return res._forceRed(this); +}; + +Mont.prototype.mul = function mul(a, b) { + if (a.isZero() || b.isZero()) return new BN(0)._forceRed(this); + + var t = a.mul(b); + var c = t.maskn(this.shift).mul(this.minv).imaskn(this.shift).mul(this.m); + var u = t.isub(c).iushrn(this.shift); + var res = u; + if (u.cmp(this.m) >= 0) { + res = u.isub(this.m); + } else if (u.cmpn(0) < 0) { + res = u.iadd(this.m); + } + + return res._forceRed(this); +}; + +Mont.prototype.invm = function invm(a) { + // (AR)^-1 * R^2 = (A^-1 * R^-1) * R^2 = A^-1 * R + var res = this.imod(a._invmp(this.m).mul(this.r2)); + return res._forceRed(this); +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/aes.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/aes.js new file mode 100644 index 000000000..991b238fe --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/aes.js @@ -0,0 +1,244 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +// based on the aes implimentation in triple sec +// https://github.com/keybase/triplesec +// which is in turn based on the one from crypto-js +// https://code.google.com/p/crypto-js/ + +// deno-lint-ignore-file no-var no-inner-declarations + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +function asUInt32Array(buf) { + if (!Buffer.isBuffer(buf)) buf = Buffer.from(buf); + + var len = (buf.length / 4) | 0; + var out = new Array(len); + + for (var i = 0; i < len; i++) { + out[i] = buf.readUInt32BE(i * 4); + } + + return out; +} + +function scrubVec(v) { + for (var i = 0; i < v.length; v++) { + v[i] = 0; + } +} + +function cryptBlock(M, keySchedule, SUB_MIX, SBOX, nRounds) { + var SUB_MIX0 = SUB_MIX[0]; + var SUB_MIX1 = SUB_MIX[1]; + var SUB_MIX2 = SUB_MIX[2]; + var SUB_MIX3 = SUB_MIX[3]; + + var s0 = M[0] ^ keySchedule[0]; + var s1 = M[1] ^ keySchedule[1]; + var s2 = M[2] ^ keySchedule[2]; + var s3 = M[3] ^ keySchedule[3]; + var t0, t1, t2, t3; + var ksRow = 4; + + for (var round = 1; round < nRounds; round++) { + t0 = SUB_MIX0[s0 >>> 24] ^ SUB_MIX1[(s1 >>> 16) & 0xff] ^ + SUB_MIX2[(s2 >>> 8) & 0xff] ^ SUB_MIX3[s3 & 0xff] ^ keySchedule[ksRow++]; + t1 = SUB_MIX0[s1 >>> 24] ^ SUB_MIX1[(s2 >>> 16) & 0xff] ^ + SUB_MIX2[(s3 >>> 8) & 0xff] ^ SUB_MIX3[s0 & 0xff] ^ keySchedule[ksRow++]; + t2 = SUB_MIX0[s2 >>> 24] ^ SUB_MIX1[(s3 >>> 16) & 0xff] ^ + SUB_MIX2[(s0 >>> 8) & 0xff] ^ SUB_MIX3[s1 & 0xff] ^ keySchedule[ksRow++]; + t3 = SUB_MIX0[s3 >>> 24] ^ SUB_MIX1[(s0 >>> 16) & 0xff] ^ + SUB_MIX2[(s1 >>> 8) & 0xff] ^ SUB_MIX3[s2 & 0xff] ^ keySchedule[ksRow++]; + s0 = t0; + s1 = t1; + s2 = t2; + s3 = t3; + } + + t0 = ((SBOX[s0 >>> 24] << 24) | (SBOX[(s1 >>> 16) & 0xff] << 16) | + (SBOX[(s2 >>> 8) & 0xff] << 8) | SBOX[s3 & 0xff]) ^ keySchedule[ksRow++]; + t1 = ((SBOX[s1 >>> 24] << 24) | (SBOX[(s2 >>> 16) & 0xff] << 16) | + (SBOX[(s3 >>> 8) & 0xff] << 8) | SBOX[s0 & 0xff]) ^ keySchedule[ksRow++]; + t2 = ((SBOX[s2 >>> 24] << 24) | (SBOX[(s3 >>> 16) & 0xff] << 16) | + (SBOX[(s0 >>> 8) & 0xff] << 8) | SBOX[s1 & 0xff]) ^ keySchedule[ksRow++]; + t3 = ((SBOX[s3 >>> 24] << 24) | (SBOX[(s0 >>> 16) & 0xff] << 16) | + (SBOX[(s1 >>> 8) & 0xff] << 8) | SBOX[s2 & 0xff]) ^ keySchedule[ksRow++]; + t0 = t0 >>> 0; + t1 = t1 >>> 0; + t2 = t2 >>> 0; + t3 = t3 >>> 0; + + return [t0, t1, t2, t3]; +} + +// AES constants +var RCON = [0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36]; +var G = (function () { + // Compute double table + var d = new Array(256); + for (var j = 0; j < 256; j++) { + if (j < 128) { + d[j] = j << 1; + } else { + d[j] = (j << 1) ^ 0x11b; + } + } + + var SBOX = []; + var INV_SBOX = []; + var SUB_MIX = [[], [], [], []]; + var INV_SUB_MIX = [[], [], [], []]; + + // Walk GF(2^8) + var x = 0; + var xi = 0; + for (var i = 0; i < 256; ++i) { + // Compute sbox + var sx = xi ^ (xi << 1) ^ (xi << 2) ^ (xi << 3) ^ (xi << 4); + sx = (sx >>> 8) ^ (sx & 0xff) ^ 0x63; + SBOX[x] = sx; + INV_SBOX[sx] = x; + + // Compute multiplication + var x2 = d[x]; + var x4 = d[x2]; + var x8 = d[x4]; + + // Compute sub bytes, mix columns tables + var t = (d[sx] * 0x101) ^ (sx * 0x1010100); + SUB_MIX[0][x] = (t << 24) | (t >>> 8); + SUB_MIX[1][x] = (t << 16) | (t >>> 16); + SUB_MIX[2][x] = (t << 8) | (t >>> 24); + SUB_MIX[3][x] = t; + + // Compute inv sub bytes, inv mix columns tables + t = (x8 * 0x1010101) ^ (x4 * 0x10001) ^ (x2 * 0x101) ^ (x * 0x1010100); + INV_SUB_MIX[0][sx] = (t << 24) | (t >>> 8); + INV_SUB_MIX[1][sx] = (t << 16) | (t >>> 16); + INV_SUB_MIX[2][sx] = (t << 8) | (t >>> 24); + INV_SUB_MIX[3][sx] = t; + + if (x === 0) { + x = xi = 1; + } else { + x = x2 ^ d[d[d[x8 ^ x2]]]; + xi ^= d[d[xi]]; + } + } + + return { + SBOX: SBOX, + INV_SBOX: INV_SBOX, + SUB_MIX: SUB_MIX, + INV_SUB_MIX: INV_SUB_MIX, + }; +})(); + +export function AES(key) { + this._key = asUInt32Array(key); + this._reset(); +} + +AES.blockSize = 4 * 4; +AES.keySize = 256 / 8; +AES.prototype.blockSize = AES.blockSize; +AES.prototype.keySize = AES.keySize; +AES.prototype._reset = function () { + var keyWords = this._key; + var keySize = keyWords.length; + var nRounds = keySize + 6; + var ksRows = (nRounds + 1) * 4; + + var keySchedule = []; + for (var k = 0; k < keySize; k++) { + keySchedule[k] = keyWords[k]; + } + + for (k = keySize; k < ksRows; k++) { + var t = keySchedule[k - 1]; + + if (k % keySize === 0) { + t = (t << 8) | (t >>> 24); + t = (G.SBOX[t >>> 24] << 24) | + (G.SBOX[(t >>> 16) & 0xff] << 16) | + (G.SBOX[(t >>> 8) & 0xff] << 8) | + (G.SBOX[t & 0xff]); + + t ^= RCON[(k / keySize) | 0] << 24; + } else if (keySize > 6 && k % keySize === 4) { + t = (G.SBOX[t >>> 24] << 24) | + (G.SBOX[(t >>> 16) & 0xff] << 16) | + (G.SBOX[(t >>> 8) & 0xff] << 8) | + (G.SBOX[t & 0xff]); + } + + keySchedule[k] = keySchedule[k - keySize] ^ t; + } + + var invKeySchedule = []; + for (var ik = 0; ik < ksRows; ik++) { + var ksR = ksRows - ik; + var tt = keySchedule[ksR - (ik % 4 ? 0 : 4)]; + + if (ik < 4 || ksR <= 4) { + invKeySchedule[ik] = tt; + } else { + invKeySchedule[ik] = G.INV_SUB_MIX[0][G.SBOX[tt >>> 24]] ^ + G.INV_SUB_MIX[1][G.SBOX[(tt >>> 16) & 0xff]] ^ + G.INV_SUB_MIX[2][G.SBOX[(tt >>> 8) & 0xff]] ^ + G.INV_SUB_MIX[3][G.SBOX[tt & 0xff]]; + } + } + + this._nRounds = nRounds; + this._keySchedule = keySchedule; + this._invKeySchedule = invKeySchedule; +}; + +AES.prototype.encryptBlockRaw = function (M) { + M = asUInt32Array(M); + return cryptBlock(M, this._keySchedule, G.SUB_MIX, G.SBOX, this._nRounds); +}; + +AES.prototype.encryptBlock = function (M) { + var out = this.encryptBlockRaw(M); + var buf = Buffer.allocUnsafe(16); + buf.writeUInt32BE(out[0], 0); + buf.writeUInt32BE(out[1], 4); + buf.writeUInt32BE(out[2], 8); + buf.writeUInt32BE(out[3], 12); + return buf; +}; + +AES.prototype.decryptBlock = function (M) { + M = asUInt32Array(M); + + // swap + var m1 = M[1]; + M[1] = M[3]; + M[3] = m1; + + var out = cryptBlock( + M, + this._invKeySchedule, + G.INV_SUB_MIX, + G.INV_SBOX, + this._nRounds, + ); + var buf = Buffer.allocUnsafe(16); + buf.writeUInt32BE(out[0], 0); + buf.writeUInt32BE(out[3], 4); + buf.writeUInt32BE(out[2], 8); + buf.writeUInt32BE(out[1], 12); + return buf; +}; + +AES.prototype.scrub = function () { + scrubVec(this._keySchedule); + scrubVec(this._invKeySchedule); + scrubVec(this._key); +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/auth_cipher.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/auth_cipher.js new file mode 100644 index 000000000..c4bd5ebe4 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/auth_cipher.js @@ -0,0 +1,146 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +// deno-lint-ignore-file no-var no-inner-declarations + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; +import * as aes from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/aes.js"; +import Transform from "internal:deno_node/polyfills/_crypto/crypto_browserify/cipher_base.js"; +import { GHASH } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/ghash.js"; +import { xor } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/xor.ts"; +import { incr32 } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/incr32.js"; + +function xorTest(a, b) { + var out = 0; + if (a.length !== b.length) out++; + + var len = Math.min(a.length, b.length); + for (var i = 0; i < len; ++i) { + out += a[i] ^ b[i]; + } + + return out; +} + +function calcIv(self, iv, ck) { + if (iv.length === 12) { + self._finID = Buffer.concat([iv, Buffer.from([0, 0, 0, 1])]); + return Buffer.concat([iv, Buffer.from([0, 0, 0, 2])]); + } + var ghash = new GHASH(ck); + var len = iv.length; + var toPad = len % 16; + ghash.update(iv); + if (toPad) { + toPad = 16 - toPad; + ghash.update(Buffer.alloc(toPad, 0)); + } + ghash.update(Buffer.alloc(8, 0)); + var ivBits = len * 8; + var tail = Buffer.alloc(8); + // Fixed from the original + // https://github.com/crypto-browserify/browserify-aes/issues/58#issuecomment-451778917 + tail.writeUIntBE(ivBits, 2, 6); + ghash.update(tail); + self._finID = ghash.state; + var out = Buffer.from(self._finID); + incr32(out); + return out; +} +export function StreamCipher(mode, key, iv, decrypt) { + Transform.call(this); + + var h = Buffer.alloc(4, 0); + + this._cipher = new aes.AES(key); + var ck = this._cipher.encryptBlock(h); + this._ghash = new GHASH(ck); + iv = calcIv(this, iv, ck); + + this._prev = Buffer.from(iv); + this._cache = Buffer.allocUnsafe(0); + this._secCache = Buffer.allocUnsafe(0); + this._decrypt = decrypt; + this._alen = 0; + this._len = 0; + this._mode = mode; + + this._authTag = null; + this._called = false; +} + +// StreamCipher inherts Transform +StreamCipher.prototype = Object.create(Transform.prototype, { + constructor: { + value: StreamCipher, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +StreamCipher.prototype._update = function (chunk) { + if (!this._called && this._alen) { + var rump = 16 - (this._alen % 16); + if (rump < 16) { + rump = Buffer.alloc(rump, 0); + this._ghash.update(rump); + } + } + + this._called = true; + var out = this._mode.encrypt(this, chunk); + if (this._decrypt) { + this._ghash.update(chunk); + } else { + this._ghash.update(out); + } + this._len += chunk.length; + return out; +}; + +StreamCipher.prototype._final = function () { + if (this._decrypt && !this._authTag) { + throw new Error("Unsupported state or unable to authenticate data"); + } + + var tag = xor( + this._ghash.final(this._alen * 8, this._len * 8), + this._cipher.encryptBlock(this._finID), + ); + if (this._decrypt && xorTest(tag, this._authTag)) { + throw new Error("Unsupported state or unable to authenticate data"); + } + + this._authTag = tag; + this._cipher.scrub(); +}; + +StreamCipher.prototype.getAuthTag = function getAuthTag() { + if (this._decrypt || !Buffer.isBuffer(this._authTag)) { + throw new Error("Attempting to get auth tag in unsupported state"); + } + + return this._authTag; +}; + +StreamCipher.prototype.setAuthTag = function setAuthTag(tag) { + if (!this._decrypt) { + throw new Error("Attempting to set auth tag in unsupported state"); + } + + this._authTag = tag; +}; + +StreamCipher.prototype.setAAD = function setAAD(buf) { + if (this._called) { + throw new Error("Attempting to set AAD in unsupported state"); + } + + this._ghash.update(buf); + this._alen += buf.length; +}; + +export default StreamCipher; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/decrypter.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/decrypter.js new file mode 100644 index 000000000..6a92a4574 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/decrypter.js @@ -0,0 +1,138 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +// deno-lint-ignore-file no-var + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; +import AuthCipher from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/auth_cipher.js"; +import StreamCipher from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/stream_cipher.js"; +import Transform from "internal:deno_node/polyfills/_crypto/crypto_browserify/cipher_base.js"; +import * as aes from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/aes.js"; +import ebtk from "internal:deno_node/polyfills/_crypto/crypto_browserify/evp_bytes_to_key.ts"; +import { MODES } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/mod.js"; + +function Decipher(mode, key, iv) { + Transform.call(this); + + this._cache = new Splitter(); + this._last = void 0; + this._cipher = new aes.AES(key); + this._prev = Buffer.from(iv); + this._mode = mode; + this._autopadding = true; +} + +Decipher.prototype = Object.create(Transform.prototype, { + constructor: { + value: Decipher, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +Decipher.prototype._update = function (data) { + this._cache.add(data); + var chunk; + var thing; + var out = []; + while ((chunk = this._cache.get(this._autopadding))) { + thing = this._mode.decrypt(this, chunk); + out.push(thing); + } + return Buffer.concat(out); +}; + +Decipher.prototype._final = function () { + var chunk = this._cache.flush(); + if (this._autopadding) { + return unpad(this._mode.decrypt(this, chunk)); + } else if (chunk) { + throw new Error("data not multiple of block length"); + } +}; + +Decipher.prototype.setAutoPadding = function (setTo) { + this._autopadding = !!setTo; + return this; +}; + +function Splitter() { + this.cache = Buffer.allocUnsafe(0); +} + +Splitter.prototype.add = function (data) { + this.cache = Buffer.concat([this.cache, data]); +}; + +Splitter.prototype.get = function (autoPadding) { + var out; + if (autoPadding) { + if (this.cache.length > 16) { + out = this.cache.slice(0, 16); + this.cache = this.cache.slice(16); + return out; + } + } else { + if (this.cache.length >= 16) { + out = this.cache.slice(0, 16); + this.cache = this.cache.slice(16); + return out; + } + } + + return null; +}; + +Splitter.prototype.flush = function () { + if (this.cache.length) return this.cache; +}; + +function unpad(last) { + var padded = last[15]; + if (padded < 1 || padded > 16) { + throw new Error("unable to decrypt data"); + } + var i = -1; + while (++i < padded) { + if (last[i + (16 - padded)] !== padded) { + throw new Error("unable to decrypt data"); + } + } + if (padded === 16) return; + + return last.slice(0, 16 - padded); +} + +export function createDecipheriv(suite, password, iv) { + var config = MODES[suite.toLowerCase()]; + if (!config) throw new TypeError("invalid suite type"); + + if (typeof iv === "string") iv = Buffer.from(iv); + if (config.mode !== "GCM" && iv.length !== config.iv) { + throw new TypeError("invalid iv length " + iv.length); + } + + if (typeof password === "string") password = Buffer.from(password); + if (password.length !== config.key / 8) { + throw new TypeError("invalid key length " + password.length); + } + + if (config.type === "stream") { + return new StreamCipher(config.module, password, iv, true); + } else if (config.type === "auth") { + return new AuthCipher(config.module, password, iv, true); + } + + return new Decipher(config.module, password, iv); +} + +export function createDecipher(suite, password) { + var config = MODES[suite.toLowerCase()]; + if (!config) throw new TypeError("invalid suite type"); + + var keys = ebtk(password, false, config.key, config.iv); + return createDecipheriv(suite, keys.key, keys.iv); +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/encrypter.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/encrypter.js new file mode 100644 index 000000000..6a95a719c --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/encrypter.js @@ -0,0 +1,128 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +// deno-lint-ignore-file no-var + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; +import AuthCipher from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/auth_cipher.js"; +import StreamCipher from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/stream_cipher.js"; +import Transform from "internal:deno_node/polyfills/_crypto/crypto_browserify/cipher_base.js"; +import * as aes from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/aes.js"; +import ebtk from "internal:deno_node/polyfills/_crypto/crypto_browserify/evp_bytes_to_key.ts"; +import { MODES } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/mod.js"; + +function Cipher(mode, key, iv) { + Transform.call(this); + + this._cache = new Splitter(); + this._cipher = new aes.AES(key); + this._prev = Buffer.from(iv); + this._mode = mode; + this._autopadding = true; +} + +Cipher.prototype = Object.create(Transform.prototype, { + constructor: { + value: Cipher, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +Cipher.prototype._update = function (data) { + this._cache.add(data); + var chunk; + var thing; + var out = []; + + while ((chunk = this._cache.get())) { + thing = this._mode.encrypt(this, chunk); + out.push(thing); + } + + return Buffer.concat(out); +}; + +var PADDING = Buffer.alloc(16, 0x10); + +Cipher.prototype._final = function () { + var chunk = this._cache.flush(); + if (this._autopadding) { + chunk = this._mode.encrypt(this, chunk); + this._cipher.scrub(); + return chunk; + } + + if (!chunk.equals(PADDING)) { + this._cipher.scrub(); + throw new Error("data not multiple of block length"); + } +}; + +Cipher.prototype.setAutoPadding = function (setTo) { + this._autopadding = !!setTo; + return this; +}; + +function Splitter() { + this.cache = Buffer.allocUnsafe(0); +} + +Splitter.prototype.add = function (data) { + this.cache = Buffer.concat([this.cache, data]); +}; + +Splitter.prototype.get = function () { + if (this.cache.length > 15) { + const out = this.cache.slice(0, 16); + this.cache = this.cache.slice(16); + return out; + } + return null; +}; + +Splitter.prototype.flush = function () { + var len = 16 - this.cache.length; + var padBuff = Buffer.allocUnsafe(len); + + var i = -1; + while (++i < len) { + padBuff.writeUInt8(len, i); + } + + return Buffer.concat([this.cache, padBuff]); +}; + +export function createCipheriv(suite, password, iv) { + var config = MODES[suite.toLowerCase()]; + if (!config) throw new TypeError("invalid suite type"); + + if (typeof password === "string") password = Buffer.from(password); + if (password.length !== config.key / 8) { + throw new TypeError("invalid key length " + password.length); + } + + if (typeof iv === "string") iv = Buffer.from(iv); + if (config.mode !== "GCM" && iv.length !== config.iv) { + throw new TypeError("invalid iv length " + iv.length); + } + + if (config.type === "stream") { + return new StreamCipher(config.module, password, iv); + } else if (config.type === "auth") { + return new AuthCipher(config.module, password, iv); + } + + return new Cipher(config.module, password, iv); +} + +export function createCipher(suite, password) { + var config = MODES[suite.toLowerCase()]; + if (!config) throw new TypeError("invalid suite type"); + + var keys = ebtk(password, false, config.key, config.iv); + return createCipheriv(suite, keys.key, keys.iv); +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/ghash.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/ghash.js new file mode 100644 index 000000000..ac896f921 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/ghash.js @@ -0,0 +1,96 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. +// Copyright 2009-2015, Emily Stark, Mike Hamburg and Dan Boneh at Stanford University. All rights reserved. + +// deno-lint-ignore-file no-var + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +var ZEROES = Buffer.alloc(16, 0); + +function toArray(buf) { + return [ + buf.readUInt32BE(0), + buf.readUInt32BE(4), + buf.readUInt32BE(8), + buf.readUInt32BE(12), + ]; +} + +function fromArray(out) { + var buf = Buffer.allocUnsafe(16); + buf.writeUInt32BE(out[0] >>> 0, 0); + buf.writeUInt32BE(out[1] >>> 0, 4); + buf.writeUInt32BE(out[2] >>> 0, 8); + buf.writeUInt32BE(out[3] >>> 0, 12); + return buf; +} + +export function GHASH(key) { + this.h = key; + this.state = Buffer.alloc(16, 0); + this.cache = Buffer.allocUnsafe(0); +} + +// from http://bitwiseshiftleft.github.io/sjcl/doc/symbols/src/core_gcm.js.html +// by Juho Vähä-Herttua +GHASH.prototype.ghash = function (block) { + var i = -1; + while (++i < block.length) { + this.state[i] ^= block[i]; + } + this._multiply(); +}; + +GHASH.prototype._multiply = function () { + var Vi = toArray(this.h); + var Zi = [0, 0, 0, 0]; + var j, xi, lsbVi; + var i = -1; + while (++i < 128) { + xi = (this.state[~~(i / 8)] & (1 << (7 - (i % 8)))) !== 0; + if (xi) { + // Z_i+1 = Z_i ^ V_i + Zi[0] ^= Vi[0]; + Zi[1] ^= Vi[1]; + Zi[2] ^= Vi[2]; + Zi[3] ^= Vi[3]; + } + + // Store the value of LSB(V_i) + lsbVi = (Vi[3] & 1) !== 0; + + // V_i+1 = V_i >> 1 + for (j = 3; j > 0; j--) { + Vi[j] = (Vi[j] >>> 1) | ((Vi[j - 1] & 1) << 31); + } + Vi[0] = Vi[0] >>> 1; + + // If LSB(V_i) is 1, V_i+1 = (V_i >> 1) ^ R + if (lsbVi) { + Vi[0] = Vi[0] ^ (0xe1 << 24); + } + } + this.state = fromArray(Zi); +}; + +GHASH.prototype.update = function (buf) { + this.cache = Buffer.concat([this.cache, buf]); + var chunk; + while (this.cache.length >= 16) { + chunk = this.cache.slice(0, 16); + this.cache = this.cache.slice(16); + this.ghash(chunk); + } +}; + +GHASH.prototype.final = function (abl, bl) { + if (this.cache.length) { + this.ghash(Buffer.concat([this.cache, ZEROES], 16)); + } + + this.ghash(fromArray([0, abl, 0, bl])); + return this.state; +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/incr32.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/incr32.js new file mode 100644 index 000000000..65172eefb --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/incr32.js @@ -0,0 +1,19 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +export function incr32(iv) { + let len = iv.length; + let item; + while (len--) { + item = iv.readUInt8(len); + if (item === 255) { + iv.writeUInt8(0, len); + } else { + item++; + iv.writeUInt8(item, len); + break; + } + } +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/mod.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/mod.js new file mode 100644 index 000000000..abf5bde5f --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/mod.js @@ -0,0 +1,13 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +import { MODES } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/mod.js"; + +export * from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/encrypter.js"; +export * from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/decrypter.js"; + +export function getCiphers() { + return Object.keys(MODES); +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cbc.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cbc.js new file mode 100644 index 000000000..837adf32f --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cbc.js @@ -0,0 +1,22 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +import { xor } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/xor.ts"; + +export const encrypt = function (self, block) { + const data = xor(block, self._prev); + + self._prev = self._cipher.encryptBlock(data); + return self._prev; +}; + +export const decrypt = function (self, block) { + const pad = self._prev; + + self._prev = block; + const out = self._cipher.decryptBlock(block); + + return xor(out, pad); +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb.js new file mode 100644 index 000000000..8bfd81463 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb.js @@ -0,0 +1,41 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +import { xor } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/xor.ts"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +function encryptStart(self, data, decrypt) { + const len = data.length; + const out = xor(data, self._cache); + self._cache = self._cache.slice(len); + self._prev = Buffer.concat([self._prev, decrypt ? data : out]); + return out; +} + +export const encrypt = function (self, data, decrypt) { + let out = Buffer.allocUnsafe(0); + let len; + + while (data.length) { + if (self._cache.length === 0) { + self._cache = self._cipher.encryptBlock(self._prev); + self._prev = Buffer.allocUnsafe(0); + } + + if (self._cache.length <= data.length) { + len = self._cache.length; + out = Buffer.concat([ + out, + encryptStart(self, data.slice(0, len), decrypt), + ]); + data = data.slice(len); + } else { + out = Buffer.concat([out, encryptStart(self, data, decrypt)]); + break; + } + } + + return out; +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb1.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb1.js new file mode 100644 index 000000000..2af8824f0 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb1.js @@ -0,0 +1,47 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +function encryptByte(self, byteParam, decrypt) { + let pad; + let i = -1; + const len = 8; + let out = 0; + let bit, value; + while (++i < len) { + pad = self._cipher.encryptBlock(self._prev); + bit = (byteParam & (1 << (7 - i))) ? 0x80 : 0; + value = pad[0] ^ bit; + out += (value & 0x80) >> (i % 8); + self._prev = shiftIn(self._prev, decrypt ? bit : value); + } + return out; +} + +function shiftIn(buffer, value) { + const len = buffer.length; + let i = -1; + const out = Buffer.allocUnsafe(buffer.length); + buffer = Buffer.concat([buffer, Buffer.from([value])]); + + while (++i < len) { + out[i] = buffer[i] << 1 | buffer[i + 1] >> (7); + } + + return out; +} + +export const encrypt = function (self, chunk, decrypt) { + const len = chunk.length; + const out = Buffer.allocUnsafe(len); + let i = -1; + + while (++i < len) { + out[i] = encryptByte(self, chunk[i], decrypt); + } + + return out; +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb8.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb8.js new file mode 100644 index 000000000..262494a81 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb8.js @@ -0,0 +1,30 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +function encryptByte(self, byteParam, decrypt) { + const pad = self._cipher.encryptBlock(self._prev); + const out = pad[0] ^ byteParam; + + self._prev = Buffer.concat([ + self._prev.slice(1), + Buffer.from([decrypt ? byteParam : out]), + ]); + + return out; +} + +export const encrypt = function (self, chunk, decrypt) { + const len = chunk.length; + const out = Buffer.allocUnsafe(len); + let i = -1; + + while (++i < len) { + out[i] = encryptByte(self, chunk[i], decrypt); + } + + return out; +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ctr.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ctr.js new file mode 100644 index 000000000..fd1781ab2 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ctr.js @@ -0,0 +1,35 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +import { xor } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/xor.ts"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; +import { incr32 } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/incr32.js"; + +function getBlock(self) { + const out = self._cipher.encryptBlockRaw(self._prev); + incr32(self._prev); + return out; +} + +const blockSize = 16; +export const encrypt = function (self, chunk) { + const chunkNum = Math.ceil(chunk.length / blockSize); + const start = self._cache.length; + self._cache = Buffer.concat([ + self._cache, + Buffer.allocUnsafe(chunkNum * blockSize), + ]); + for (let i = 0; i < chunkNum; i++) { + const out = getBlock(self); + const offset = start + i * blockSize; + self._cache.writeUInt32BE(out[0], offset + 0); + self._cache.writeUInt32BE(out[1], offset + 4); + self._cache.writeUInt32BE(out[2], offset + 8); + self._cache.writeUInt32BE(out[3], offset + 12); + } + const pad = self._cache.slice(0, chunk.length); + self._cache = self._cache.slice(chunk.length); + return xor(chunk, pad); +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ecb.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ecb.js new file mode 100644 index 000000000..b4f99cffb --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ecb.js @@ -0,0 +1,12 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +export const encrypt = function (self, block) { + return self._cipher.encryptBlock(block); +}; + +export const decrypt = function (self, block) { + return self._cipher.decryptBlock(block); +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/mod.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/mod.js new file mode 100644 index 000000000..b30ed0b25 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/mod.js @@ -0,0 +1,221 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +import * as ECB from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ecb.js"; +import * as CBC from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cbc.js"; +import * as CFB from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb.js"; +import * as CFB8 from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb8.js"; +import * as CFB1 from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/cfb1.js"; +import * as OFB from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ofb.js"; +import * as CTR from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ctr.js"; + +const GCM = CTR; + +const modeModules = { + ECB, + CBC, + CFB, + CFB8, + CFB1, + OFB, + CTR, + GCM, +}; + +export const MODES = { + "aes-128-ecb": { + "cipher": "AES", + "key": 128, + "iv": 0, + "mode": "ECB", + "type": "block", + }, + "aes-192-ecb": { + "cipher": "AES", + "key": 192, + "iv": 0, + "mode": "ECB", + "type": "block", + }, + "aes-256-ecb": { + "cipher": "AES", + "key": 256, + "iv": 0, + "mode": "ECB", + "type": "block", + }, + "aes-128-cbc": { + "cipher": "AES", + "key": 128, + "iv": 16, + "mode": "CBC", + "type": "block", + }, + "aes-192-cbc": { + "cipher": "AES", + "key": 192, + "iv": 16, + "mode": "CBC", + "type": "block", + }, + "aes-256-cbc": { + "cipher": "AES", + "key": 256, + "iv": 16, + "mode": "CBC", + "type": "block", + }, + "aes128": { + "cipher": "AES", + "key": 128, + "iv": 16, + "mode": "CBC", + "type": "block", + }, + "aes192": { + "cipher": "AES", + "key": 192, + "iv": 16, + "mode": "CBC", + "type": "block", + }, + "aes256": { + "cipher": "AES", + "key": 256, + "iv": 16, + "mode": "CBC", + "type": "block", + }, + "aes-128-cfb": { + "cipher": "AES", + "key": 128, + "iv": 16, + "mode": "CFB", + "type": "stream", + }, + "aes-192-cfb": { + "cipher": "AES", + "key": 192, + "iv": 16, + "mode": "CFB", + "type": "stream", + }, + "aes-256-cfb": { + "cipher": "AES", + "key": 256, + "iv": 16, + "mode": "CFB", + "type": "stream", + }, + "aes-128-cfb8": { + "cipher": "AES", + "key": 128, + "iv": 16, + "mode": "CFB8", + "type": "stream", + }, + "aes-192-cfb8": { + "cipher": "AES", + "key": 192, + "iv": 16, + "mode": "CFB8", + "type": "stream", + }, + "aes-256-cfb8": { + "cipher": "AES", + "key": 256, + "iv": 16, + "mode": "CFB8", + "type": "stream", + }, + "aes-128-cfb1": { + "cipher": "AES", + "key": 128, + "iv": 16, + "mode": "CFB1", + "type": "stream", + }, + "aes-192-cfb1": { + "cipher": "AES", + "key": 192, + "iv": 16, + "mode": "CFB1", + "type": "stream", + }, + "aes-256-cfb1": { + "cipher": "AES", + "key": 256, + "iv": 16, + "mode": "CFB1", + "type": "stream", + }, + "aes-128-ofb": { + "cipher": "AES", + "key": 128, + "iv": 16, + "mode": "OFB", + "type": "stream", + }, + "aes-192-ofb": { + "cipher": "AES", + "key": 192, + "iv": 16, + "mode": "OFB", + "type": "stream", + }, + "aes-256-ofb": { + "cipher": "AES", + "key": 256, + "iv": 16, + "mode": "OFB", + "type": "stream", + }, + "aes-128-ctr": { + "cipher": "AES", + "key": 128, + "iv": 16, + "mode": "CTR", + "type": "stream", + }, + "aes-192-ctr": { + "cipher": "AES", + "key": 192, + "iv": 16, + "mode": "CTR", + "type": "stream", + }, + "aes-256-ctr": { + "cipher": "AES", + "key": 256, + "iv": 16, + "mode": "CTR", + "type": "stream", + }, + "aes-128-gcm": { + "cipher": "AES", + "key": 128, + "iv": 12, + "mode": "GCM", + "type": "auth", + }, + "aes-192-gcm": { + "cipher": "AES", + "key": 192, + "iv": 12, + "mode": "GCM", + "type": "auth", + }, + "aes-256-gcm": { + "cipher": "AES", + "key": 256, + "iv": 12, + "mode": "GCM", + "type": "auth", + }, +}; + +for (const mode of Object.values(MODES)) { + mode.module = modeModules[mode.mode]; +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ofb.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ofb.js new file mode 100644 index 000000000..20ccdf015 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/modes/ofb.js @@ -0,0 +1,22 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +import { xor } from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/xor.ts"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +function getBlock(self) { + self._prev = self._cipher.encryptBlock(self._prev); + return self._prev; +} + +export const encrypt = function (self, chunk) { + while (self._cache.length < chunk.length) { + self._cache = Buffer.concat([self._cache, getBlock(self)]); + } + + const pad = self._cache.slice(0, chunk.length); + self._cache = self._cache.slice(chunk.length); + return xor(chunk, pad); +}; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/stream_cipher.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/stream_cipher.js new file mode 100644 index 000000000..432730f91 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/stream_cipher.js @@ -0,0 +1,40 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +import * as aes from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/aes.js"; +import Transform from "internal:deno_node/polyfills/_crypto/crypto_browserify/cipher_base.js"; + +export function StreamCipher(mode, key, iv, decrypt) { + Transform.call(this); + + this._cipher = new aes.AES(key); + this._prev = Buffer.from(iv); + this._cache = Buffer.allocUnsafe(0); + this._secCache = Buffer.allocUnsafe(0); + this._decrypt = decrypt; + this._mode = mode; +} + +// StreamCipher inherits Transform +StreamCipher.prototype = Object.create(Transform.prototype, { + constructor: { + value: StreamCipher, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +StreamCipher.prototype._update = function (chunk) { + return this._mode.encrypt(this, chunk, this._decrypt); +}; + +StreamCipher.prototype._final = function () { + this._cipher.scrub(); +}; + +export default StreamCipher; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/xor.ts b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/xor.ts new file mode 100644 index 000000000..6b9327ebc --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_aes/xor.ts @@ -0,0 +1,17 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2014-2017 browserify-aes contributors. All rights reserved. MIT license. +// Copyright 2013 Maxwell Krohn. All rights reserved. MIT license. +// Copyright 2009-2013 Jeff Mott. All rights reserved. MIT license. + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +export function xor(a: Buffer, b: Buffer): Buffer { + const length = Math.min(a.length, b.length); + const buffer = Buffer.allocUnsafe(length); + + for (let i = 0; i < length; ++i) { + buffer[i] = a[i] ^ b[i]; + } + + return buffer; +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/browserify_rsa.js b/ext/node/polyfills/_crypto/crypto_browserify/browserify_rsa.js new file mode 100644 index 000000000..b158462b8 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/browserify_rsa.js @@ -0,0 +1,47 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 crypto-browserify. All rights reserved. MIT license. + +import { BN } from "internal:deno_node/polyfills/_crypto/crypto_browserify/bn.js/bn.js"; +import { randomBytes } from "internal:deno_node/polyfills/_crypto/crypto_browserify/randombytes.ts"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +function blind(priv) { + const r = getr(priv); + const blinder = r.toRed(BN.mont(priv.modulus)).redPow( + new BN(priv.publicExponent), + ).fromRed(); + return { blinder: blinder, unblinder: r.invm(priv.modulus) }; +} + +function getr(priv) { + const len = priv.modulus.byteLength(); + let r; + do { + r = new BN(randomBytes(len)); + } while ( + r.cmp(priv.modulus) >= 0 || !r.umod(priv.prime1) || !r.umod(priv.prime2) + ); + return r; +} + +function crt(msg, priv) { + const blinds = blind(priv); + const len = priv.modulus.byteLength(); + const blinded = new BN(msg).mul(blinds.blinder).umod(priv.modulus); + const c1 = blinded.toRed(BN.mont(priv.prime1)); + const c2 = blinded.toRed(BN.mont(priv.prime2)); + const qinv = priv.coefficient; + const p = priv.prime1; + const q = priv.prime2; + const m1 = c1.redPow(priv.exponent1).fromRed(); + const m2 = c2.redPow(priv.exponent2).fromRed(); + const h = m1.isub(m2).imul(qinv).umod(p).imul(q); + return m2.iadd(h).imul(blinds.unblinder).umod(priv.modulus).toArrayLike( + Buffer, + "be", + len, + ); +} +crt.getr = getr; + +export default crt; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/cipher_base.js b/ext/node/polyfills/_crypto/crypto_browserify/cipher_base.js new file mode 100644 index 000000000..ceb143fc5 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/cipher_base.js @@ -0,0 +1,110 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 crypto-browserify. All rights reserved. MIT license. +// deno-lint-ignore-file no-var + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; +import { Transform } from "internal:deno_node/polyfills/stream.ts"; +import { StringDecoder } from "internal:deno_node/polyfills/string_decoder.ts"; + +export function CipherBase(hashMode) { + Transform.call(this); + this.hashMode = typeof hashMode === "string"; + if (this.hashMode) { + this[hashMode] = this._finalOrDigest; + } else { + this.final = this._finalOrDigest; + } + if (this._final) { + this.__final = this._final; + this._final = null; + } + this._decoder = null; + this._encoding = null; +} +// inherits(CipherBase, Transform) +CipherBase.prototype = Object.create(Transform.prototype, { + constructor: { + value: CipherBase, + enumerable: false, + writable: true, + configurable: true, + }, +}); + +CipherBase.prototype.update = function (data, inputEnc, outputEnc) { + if (typeof data === "string") { + data = Buffer.from(data, inputEnc); + } + + var outData = this._update(data); + if (this.hashMode) return this; + + if (outputEnc) { + outData = this._toString(outData, outputEnc); + } + + return outData; +}; + +CipherBase.prototype.setAutoPadding = function () {}; +CipherBase.prototype.getAuthTag = function () { + throw new Error("trying to get auth tag in unsupported state"); +}; + +CipherBase.prototype.setAuthTag = function () { + throw new Error("trying to set auth tag in unsupported state"); +}; + +CipherBase.prototype.setAAD = function () { + throw new Error("trying to set aad in unsupported state"); +}; + +CipherBase.prototype._transform = function (data, _, next) { + var err; + try { + if (this.hashMode) { + this._update(data); + } else { + this.push(this._update(data)); + } + } catch (e) { + err = e; + } finally { + next(err); + } +}; +CipherBase.prototype._flush = function (done) { + var err; + try { + this.push(this.__final()); + } catch (e) { + err = e; + } + + done(err); +}; +CipherBase.prototype._finalOrDigest = function (outputEnc) { + var outData = this.__final() || Buffer.alloc(0); + if (outputEnc) { + outData = this._toString(outData, outputEnc, true); + } + return outData; +}; + +CipherBase.prototype._toString = function (value, enc, fin) { + if (!this._decoder) { + this._decoder = new StringDecoder(enc); + this._encoding = enc; + } + + if (this._encoding !== enc) throw new Error("can't switch encodings"); + + var out = this._decoder.write(value); + if (fin) { + out += this._decoder.end(); + } + + return out; +}; + +export default CipherBase; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/evp_bytes_to_key.ts b/ext/node/polyfills/_crypto/crypto_browserify/evp_bytes_to_key.ts new file mode 100644 index 000000000..a8599651a --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/evp_bytes_to_key.ts @@ -0,0 +1,55 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 crypto-browserify. All rights reserved. MIT license. + +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; +import { createHash } from "internal:deno_node/polyfills/internal/crypto/hash.ts"; + +// deno-lint-ignore camelcase +export function EVP_BytesToKey( + password: string | Buffer, + salt: string | Buffer, + keyBits: number, + ivLen: number, +) { + if (!Buffer.isBuffer(password)) password = Buffer.from(password, "binary"); + if (salt) { + if (!Buffer.isBuffer(salt)) salt = Buffer.from(salt, "binary"); + if (salt.length !== 8) { + throw new RangeError("salt should be Buffer with 8 byte length"); + } + } + + let keyLen = keyBits / 8; + const key = Buffer.alloc(keyLen); + const iv = Buffer.alloc(ivLen || 0); + let tmp = Buffer.alloc(0); + + while (keyLen > 0 || ivLen > 0) { + const hash = createHash("md5"); + hash.update(tmp); + hash.update(password); + if (salt) hash.update(salt); + tmp = hash.digest() as Buffer; + + let used = 0; + + if (keyLen > 0) { + const keyStart = key.length - keyLen; + used = Math.min(keyLen, tmp.length); + tmp.copy(key, keyStart, 0, used); + keyLen -= used; + } + + if (used < tmp.length && ivLen > 0) { + const ivStart = iv.length - ivLen; + const length = Math.min(ivLen, tmp.length - used); + tmp.copy(iv, ivStart, used, used + length); + ivLen -= length; + } + } + + tmp.fill(0); + return { key, iv }; +} + +export default EVP_BytesToKey; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/package.json b/ext/node/polyfills/_crypto/crypto_browserify/package.json new file mode 100644 index 000000000..db986192c --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/package.json @@ -0,0 +1,4 @@ +{ + "//": "Sets type module to make compat mode interpret .js as ESM", + "type": "module" +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/asn1.js b/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/asn1.js new file mode 100644 index 000000000..9023cf259 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/asn1.js @@ -0,0 +1,117 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 crypto-browserify. All rights reserved. MIT license. +// from https://github.com/crypto-browserify/parse-asn1/blob/fbd70dca8670d17955893e083ca69118908570be/asn1.js + +import asn1 from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/mod.js"; +import certificate from "internal:deno_node/polyfills/_crypto/crypto_browserify/parse_asn1/certificate.js"; +export { certificate }; + +export const RSAPrivateKey = asn1.define("RSAPrivateKey", function () { + this.seq().obj( + this.key("version").int(), + this.key("modulus").int(), + this.key("publicExponent").int(), + this.key("privateExponent").int(), + this.key("prime1").int(), + this.key("prime2").int(), + this.key("exponent1").int(), + this.key("exponent2").int(), + this.key("coefficient").int(), + ); +}); + +export const RSAPublicKey = asn1.define("RSAPublicKey", function () { + this.seq().obj( + this.key("modulus").int(), + this.key("publicExponent").int(), + ); +}); + +export const PublicKey = asn1.define("SubjectPublicKeyInfo", function () { + this.seq().obj( + this.key("algorithm").use(AlgorithmIdentifier), + this.key("subjectPublicKey").bitstr(), + ); +}); + +const AlgorithmIdentifier = asn1.define("AlgorithmIdentifier", function () { + this.seq().obj( + this.key("algorithm").objid(), + this.key("none").null_().optional(), + this.key("curve").objid().optional(), + this.key("params").seq().obj( + this.key("p").int(), + this.key("q").int(), + this.key("g").int(), + ).optional(), + ); +}); + +export const PrivateKey = asn1.define("PrivateKeyInfo", function () { + this.seq().obj( + this.key("version").int(), + this.key("algorithm").use(AlgorithmIdentifier), + this.key("subjectPrivateKey").octstr(), + ); +}); +export const EncryptedPrivateKey = asn1.define( + "EncryptedPrivateKeyInfo", + function () { + this.seq().obj( + this.key("algorithm").seq().obj( + this.key("id").objid(), + this.key("decrypt").seq().obj( + this.key("kde").seq().obj( + this.key("id").objid(), + this.key("kdeparams").seq().obj( + this.key("salt").octstr(), + this.key("iters").int(), + ), + ), + this.key("cipher").seq().obj( + this.key("algo").objid(), + this.key("iv").octstr(), + ), + ), + ), + this.key("subjectPrivateKey").octstr(), + ); + }, +); + +export const DSAPrivateKey = asn1.define("DSAPrivateKey", function () { + this.seq().obj( + this.key("version").int(), + this.key("p").int(), + this.key("q").int(), + this.key("g").int(), + this.key("pub_key").int(), + this.key("priv_key").int(), + ); +}); + +export const DSAparam = asn1.define("DSAparam", function () { + this.int(); +}); + +export const ECPrivateKey = asn1.define("ECPrivateKey", function () { + this.seq().obj( + this.key("version").int(), + this.key("privateKey").octstr(), + this.key("parameters").optional().explicit(0).use(ECParameters), + this.key("publicKey").optional().explicit(1).bitstr(), + ); +}); + +const ECParameters = asn1.define("ECParameters", function () { + this.choice({ + namedCurve: this.objid(), + }); +}); + +export const signature = asn1.define("signature", function () { + this.seq().obj( + this.key("r").int(), + this.key("s").int(), + ); +}); diff --git a/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/certificate.js b/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/certificate.js new file mode 100644 index 000000000..484aa41c4 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/certificate.js @@ -0,0 +1,91 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 crypto-browserify. All rights reserved. MIT license. +// from https://github.com/crypto-browserify/parse-asn1/blob/fbd70dca8670d17955893e083ca69118908570be/certificate.js + +import * as asn from "internal:deno_node/polyfills/_crypto/crypto_browserify/asn1.js/mod.js"; + +const Time = asn.define("Time", function () { + this.choice({ + utcTime: this.utctime(), + generalTime: this.gentime(), + }); +}); + +const AttributeTypeValue = asn.define("AttributeTypeValue", function () { + this.seq().obj( + this.key("type").objid(), + this.key("value").any(), + ); +}); + +const AlgorithmIdentifier = asn.define("AlgorithmIdentifier", function () { + this.seq().obj( + this.key("algorithm").objid(), + this.key("parameters").optional(), + this.key("curve").objid().optional(), + ); +}); + +const SubjectPublicKeyInfo = asn.define("SubjectPublicKeyInfo", function () { + this.seq().obj( + this.key("algorithm").use(AlgorithmIdentifier), + this.key("subjectPublicKey").bitstr(), + ); +}); + +const RelativeDistinguishedName = asn.define( + "RelativeDistinguishedName", + function () { + this.setof(AttributeTypeValue); + }, +); + +const RDNSequence = asn.define("RDNSequence", function () { + this.seqof(RelativeDistinguishedName); +}); + +const Name = asn.define("Name", function () { + this.choice({ + rdnSequence: this.use(RDNSequence), + }); +}); + +const Validity = asn.define("Validity", function () { + this.seq().obj( + this.key("notBefore").use(Time), + this.key("notAfter").use(Time), + ); +}); + +const Extension = asn.define("Extension", function () { + this.seq().obj( + this.key("extnID").objid(), + this.key("critical").bool().def(false), + this.key("extnValue").octstr(), + ); +}); + +const TBSCertificate = asn.define("TBSCertificate", function () { + this.seq().obj( + this.key("version").explicit(0).int().optional(), + this.key("serialNumber").int(), + this.key("signature").use(AlgorithmIdentifier), + this.key("issuer").use(Name), + this.key("validity").use(Validity), + this.key("subject").use(Name), + this.key("subjectPublicKeyInfo").use(SubjectPublicKeyInfo), + this.key("issuerUniqueID").implicit(1).bitstr().optional(), + this.key("subjectUniqueID").implicit(2).bitstr().optional(), + this.key("extensions").explicit(3).seqof(Extension).optional(), + ); +}); + +export const X509Certificate = asn.define("X509Certificate", function () { + this.seq().obj( + this.key("tbsCertificate").use(TBSCertificate), + this.key("signatureAlgorithm").use(AlgorithmIdentifier), + this.key("signatureValue").bitstr(), + ); +}); + +export default X509Certificate; diff --git a/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/fix_proc.js b/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/fix_proc.js new file mode 100644 index 000000000..9c78f7bb2 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/fix_proc.js @@ -0,0 +1,37 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 crypto-browserify. All rights reserved. MIT license. +// from https://github.com/crypto-browserify/parse-asn1/blob/fbd70dca8670d17955893e083ca69118908570be/fixProc.js + +import evp from "internal:deno_node/polyfills/_crypto/crypto_browserify/evp_bytes_to_key.ts"; +import * as ciphers from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/mod.js"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +const findProc = + /Proc-Type: 4,ENCRYPTED[\n\r]+DEK-Info: AES-((?:128)|(?:192)|(?:256))-CBC,([0-9A-H]+)[\n\r]+([0-9A-z\n\r+/=]+)[\n\r]+/m; +const startRegex = /^-----BEGIN ((?:.*? KEY)|CERTIFICATE)-----/m; +const fullRegex = + /^-----BEGIN ((?:.*? KEY)|CERTIFICATE)-----([0-9A-z\n\r+/=]+)-----END \1-----$/m; +export default function (okey, password) { + const key = okey.toString(); + const match = key.match(findProc); + let decrypted; + if (!match) { + const match2 = key.match(fullRegex); + decrypted = Buffer.from(match2[2].replace(/[\r\n]/g, ""), "base64"); + } else { + const suite = "aes" + match[1]; + const iv = Buffer.from(match[2], "hex"); + const cipherText = Buffer.from(match[3].replace(/[\r\n]/g, ""), "base64"); + const cipherKey = evp(password, iv.slice(0, 8), parseInt(match[1], 10)).key; + const out = []; + const cipher = ciphers.createDecipheriv(suite, cipherKey, iv); + out.push(cipher.update(cipherText)); + out.push(cipher.final()); + decrypted = Buffer.concat(out); + } + const tag = key.match(startRegex)[1]; + return { + tag: tag, + data: decrypted, + }; +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/mod.js b/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/mod.js new file mode 100644 index 000000000..66aa2227f --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/parse_asn1/mod.js @@ -0,0 +1,138 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 crypto-browserify. All rights reserved. MIT license. +// from https://github.com/crypto-browserify/parse-asn1/blob/fbd70dca8670d17955893e083ca69118908570be/index.js + +import * as asn1 from "internal:deno_node/polyfills/_crypto/crypto_browserify/parse_asn1/asn1.js"; +import fixProc from "internal:deno_node/polyfills/_crypto/crypto_browserify/parse_asn1/fix_proc.js"; +import * as ciphers from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_aes/mod.js"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; +import { pbkdf2Sync } from "internal:deno_node/polyfills/internal/crypto/pbkdf2.ts"; + +const aesid = { + "2.16.840.1.101.3.4.1.1": "aes-128-ecb", + "2.16.840.1.101.3.4.1.2": "aes-128-cbc", + "2.16.840.1.101.3.4.1.3": "aes-128-ofb", + "2.16.840.1.101.3.4.1.4": "aes-128-cfb", + "2.16.840.1.101.3.4.1.21": "aes-192-ecb", + "2.16.840.1.101.3.4.1.22": "aes-192-cbc", + "2.16.840.1.101.3.4.1.23": "aes-192-ofb", + "2.16.840.1.101.3.4.1.24": "aes-192-cfb", + "2.16.840.1.101.3.4.1.41": "aes-256-ecb", + "2.16.840.1.101.3.4.1.42": "aes-256-cbc", + "2.16.840.1.101.3.4.1.43": "aes-256-ofb", + "2.16.840.1.101.3.4.1.44": "aes-256-cfb", +}; +export function parseKeys(buffer) { + let password; + if (typeof buffer === "object" && !Buffer.isBuffer(buffer)) { + password = buffer.passphrase; + buffer = buffer.key; + } + if (typeof buffer === "string") { + buffer = Buffer.from(buffer); + } + + const stripped = fixProc(buffer, password); + + const type = stripped.tag; + let data = stripped.data; + let subtype, ndata; + switch (type) { + case "CERTIFICATE": + ndata = asn1.certificate.decode(data, "der").tbsCertificate + .subjectPublicKeyInfo; + // falls through + case "PUBLIC KEY": + if (!ndata) { + ndata = asn1.PublicKey.decode(data, "der"); + } + subtype = ndata.algorithm.algorithm.join("."); + switch (subtype) { + case "1.2.840.113549.1.1.1": + return asn1.RSAPublicKey.decode(ndata.subjectPublicKey.data, "der"); + case "1.2.840.10045.2.1": + ndata.subjectPrivateKey = ndata.subjectPublicKey; + return { + type: "ec", + data: ndata, + }; + case "1.2.840.10040.4.1": + ndata.algorithm.params.pub_key = asn1.DSAparam.decode( + ndata.subjectPublicKey.data, + "der", + ); + return { + type: "dsa", + data: ndata.algorithm.params, + }; + default: + throw new Error("unknown key id " + subtype); + } + // throw new Error('unknown key type ' + type) + case "ENCRYPTED PRIVATE KEY": + data = asn1.EncryptedPrivateKey.decode(data, "der"); + data = decrypt(data, password); + // falls through + case "PRIVATE KEY": + ndata = asn1.PrivateKey.decode(data, "der"); + subtype = ndata.algorithm.algorithm.join("."); + switch (subtype) { + case "1.2.840.113549.1.1.1": + return asn1.RSAPrivateKey.decode(ndata.subjectPrivateKey, "der"); + case "1.2.840.10045.2.1": + return { + curve: ndata.algorithm.curve, + privateKey: asn1.ECPrivateKey.decode(ndata.subjectPrivateKey, "der") + .privateKey, + }; + case "1.2.840.10040.4.1": + ndata.algorithm.params.priv_key = asn1.DSAparam.decode( + ndata.subjectPrivateKey, + "der", + ); + return { + type: "dsa", + params: ndata.algorithm.params, + }; + default: + throw new Error("unknown key id " + subtype); + } + // throw new Error('unknown key type ' + type) + case "RSA PUBLIC KEY": + return asn1.RSAPublicKey.decode(data, "der"); + case "RSA PRIVATE KEY": + return asn1.RSAPrivateKey.decode(data, "der"); + case "DSA PRIVATE KEY": + return { + type: "dsa", + params: asn1.DSAPrivateKey.decode(data, "der"), + }; + case "EC PRIVATE KEY": + data = asn1.ECPrivateKey.decode(data, "der"); + return { + curve: data.parameters.value, + privateKey: data.privateKey, + }; + default: + throw new Error("unknown key type " + type); + } +} +export default parseKeys; +parseKeys.signature = asn1.signature; +function decrypt(data, password) { + const salt = data.algorithm.decrypt.kde.kdeparams.salt; + const iters = parseInt( + data.algorithm.decrypt.kde.kdeparams.iters.toString(), + 10, + ); + const algo = aesid[data.algorithm.decrypt.cipher.algo.join(".")]; + const iv = data.algorithm.decrypt.cipher.iv; + const cipherText = data.subjectPrivateKey; + const keylen = parseInt(algo.split("-")[1], 10) / 8; + const key = pbkdf2Sync(password, salt, iters, keylen, "sha1"); + const cipher = ciphers.createDecipheriv(algo, key, iv); + const out = []; + out.push(cipher.update(cipherText)); + out.push(cipher.final()); + return Buffer.concat(out); +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/mgf.js b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/mgf.js new file mode 100644 index 000000000..5bb41f896 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/mgf.js @@ -0,0 +1,22 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Calvin Metcalf. All rights reserved. MIT license. + +import { createHash } from "internal:deno_node/polyfills/internal/crypto/hash.ts"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +export default function (seed, len) { + let t = Buffer.alloc(0); + let i = 0; + let c; + while (t.length < len) { + c = i2ops(i++); + t = Buffer.concat([t, createHash("sha1").update(seed).update(c).digest()]); + } + return t.slice(0, len); +} + +function i2ops(c) { + const out = Buffer.allocUnsafe(4); + out.writeUInt32BE(c, 0); + return out; +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/mod.js b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/mod.js new file mode 100644 index 000000000..a91197aef --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/mod.js @@ -0,0 +1,15 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Calvin Metcalf. All rights reserved. MIT license. + +import { publicEncrypt } from "internal:deno_node/polyfills/_crypto/crypto_browserify/public_encrypt/public_encrypt.js"; +import { privateDecrypt } from "internal:deno_node/polyfills/_crypto/crypto_browserify/public_encrypt/private_decrypt.js"; + +export { privateDecrypt, publicEncrypt }; + +export function privateEncrypt(key, buf) { + return publicEncrypt(key, buf, true); +} + +export function publicDecrypt(key, buf) { + return privateDecrypt(key, buf, true); +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/private_decrypt.js b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/private_decrypt.js new file mode 100644 index 000000000..9b485b3db --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/private_decrypt.js @@ -0,0 +1,111 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Calvin Metcalf. All rights reserved. MIT license. + +import parseKeys from "internal:deno_node/polyfills/_crypto/crypto_browserify/parse_asn1/mod.js"; +import { createHash } from "internal:deno_node/polyfills/internal/crypto/hash.ts"; +import mgf from "internal:deno_node/polyfills/_crypto/crypto_browserify/public_encrypt/mgf.js"; +import { xor } from "internal:deno_node/polyfills/_crypto/crypto_browserify/public_encrypt/xor.js"; +import { BN } from "internal:deno_node/polyfills/_crypto/crypto_browserify/bn.js/bn.js"; +import { withPublic } from "internal:deno_node/polyfills/_crypto/crypto_browserify/public_encrypt/with_public.js"; +import crt from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_rsa.js"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +export function privateDecrypt(privateKey, enc, reverse) { + let padding; + if (privateKey.padding) { + padding = privateKey.padding; + } else if (reverse) { + padding = 1; + } else { + padding = 4; + } + + const key = parseKeys(privateKey); + const k = key.modulus.byteLength(); + if (enc.length > k || new BN(enc).cmp(key.modulus) >= 0) { + throw new Error("decryption error"); + } + let msg; + if (reverse) { + msg = withPublic(new BN(enc), key); + } else { + msg = crt(enc, key); + } + const zBuffer = Buffer.alloc(k - msg.length); + msg = Buffer.concat([zBuffer, msg], k); + if (padding === 4) { + return oaep(key, msg); + } else if (padding === 1) { + return pkcs1(key, msg, reverse); + } else if (padding === 3) { + return msg; + } else { + throw new Error("unknown padding"); + } +} + +function oaep(key, msg) { + const k = key.modulus.byteLength(); + const iHash = createHash("sha1").update(Buffer.alloc(0)).digest(); + const hLen = iHash.length; + if (msg[0] !== 0) { + throw new Error("decryption error"); + } + const maskedSeed = msg.slice(1, hLen + 1); + const maskedDb = msg.slice(hLen + 1); + const seed = xor(maskedSeed, mgf(maskedDb, hLen)); + const db = xor(maskedDb, mgf(seed, k - hLen - 1)); + if (compare(iHash, db.slice(0, hLen))) { + throw new Error("decryption error"); + } + let i = hLen; + while (db[i] === 0) { + i++; + } + if (db[i++] !== 1) { + throw new Error("decryption error"); + } + return db.slice(i); +} + +function pkcs1(_key, msg, reverse) { + const p1 = msg.slice(0, 2); + let i = 2; + let status = 0; + while (msg[i++] !== 0) { + if (i >= msg.length) { + status++; + break; + } + } + const ps = msg.slice(2, i - 1); + + if ( + (p1.toString("hex") !== "0002" && !reverse) || + (p1.toString("hex") !== "0001" && reverse) + ) { + status++; + } + if (ps.length < 8) { + status++; + } + if (status) { + throw new Error("decryption error"); + } + return msg.slice(i); +} +function compare(a, b) { + a = Buffer.from(a); + b = Buffer.from(b); + let dif = 0; + let len = a.length; + if (a.length !== b.length) { + dif++; + len = Math.min(a.length, b.length); + } + let i = -1; + while (++i < len) { + dif += a[i] ^ b[i]; + } + return dif; +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/public_encrypt.js b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/public_encrypt.js new file mode 100644 index 000000000..9642128ba --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/public_encrypt.js @@ -0,0 +1,104 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Calvin Metcalf. All rights reserved. MIT license. + +import parseKeys from "internal:deno_node/polyfills/_crypto/crypto_browserify/parse_asn1/mod.js"; +import { randomBytes } from "internal:deno_node/polyfills/_crypto/crypto_browserify/randombytes.ts"; +import { createHash } from "internal:deno_node/polyfills/internal/crypto/hash.ts"; +import mgf from "internal:deno_node/polyfills/_crypto/crypto_browserify/public_encrypt/mgf.js"; +import { xor } from "internal:deno_node/polyfills/_crypto/crypto_browserify/public_encrypt/xor.js"; +import { BN } from "internal:deno_node/polyfills/_crypto/crypto_browserify/bn.js/bn.js"; +import { withPublic } from "internal:deno_node/polyfills/_crypto/crypto_browserify/public_encrypt/with_public.js"; +import crt from "internal:deno_node/polyfills/_crypto/crypto_browserify/browserify_rsa.js"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +export function publicEncrypt(publicKey, msg, reverse) { + let padding; + if (publicKey.padding) { + padding = publicKey.padding; + } else if (reverse) { + padding = 1; + } else { + padding = 4; + } + const key = parseKeys(publicKey); + let paddedMsg; + if (padding === 4) { + paddedMsg = oaep(key, msg); + } else if (padding === 1) { + paddedMsg = pkcs1(key, msg, reverse); + } else if (padding === 3) { + paddedMsg = new BN(msg); + if (paddedMsg.cmp(key.modulus) >= 0) { + throw new Error("data too long for modulus"); + } + } else { + throw new Error("unknown padding"); + } + if (reverse) { + return crt(paddedMsg, key); + } else { + return withPublic(paddedMsg, key); + } +} + +function oaep(key, msg) { + const k = key.modulus.byteLength(); + const mLen = msg.length; + const iHash = createHash("sha1").update(Buffer.alloc(0)).digest(); + const hLen = iHash.length; + const hLen2 = 2 * hLen; + if (mLen > k - hLen2 - 2) { + throw new Error("message too long"); + } + const ps = Buffer.alloc(k - mLen - hLen2 - 2); + const dblen = k - hLen - 1; + const seed = randomBytes(hLen); + const maskedDb = xor( + Buffer.concat([iHash, ps, Buffer.alloc(1, 1), msg], dblen), + mgf(seed, dblen), + ); + const maskedSeed = xor(seed, mgf(maskedDb, hLen)); + return new BN(Buffer.concat([Buffer.alloc(1), maskedSeed, maskedDb], k)); +} +function pkcs1(key, msg, reverse) { + const mLen = msg.length; + const k = key.modulus.byteLength(); + if (mLen > k - 11) { + throw new Error("message too long"); + } + let ps; + if (reverse) { + ps = Buffer.alloc(k - mLen - 3, 0xff); + } else { + ps = nonZero(k - mLen - 3); + } + return new BN( + Buffer.concat([ + Buffer.from([ + 0, + reverse ? 1 : 2, + ]), + ps, + Buffer.alloc(1), + msg, + ], k), + ); +} +function nonZero(len) { + const out = Buffer.allocUnsafe(len); + let i = 0; + let cache = randomBytes(len * 2); + let cur = 0; + let num; + while (i < len) { + if (cur === cache.length) { + cache = randomBytes(len * 2); + cur = 0; + } + num = cache[cur++]; + if (num) { + out[i++] = num; + } + } + return out; +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/with_public.js b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/with_public.js new file mode 100644 index 000000000..5e94c7bc9 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/with_public.js @@ -0,0 +1,15 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Calvin Metcalf. All rights reserved. MIT license. + +import { BN } from "internal:deno_node/polyfills/_crypto/crypto_browserify/bn.js/bn.js"; +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; + +export function withPublic(paddedMsg, key) { + return Buffer.from( + paddedMsg + .toRed(BN.mont(key.modulus)) + .redPow(new BN(key.publicExponent)) + .fromRed() + .toArray(), + ); +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/xor.js b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/xor.js new file mode 100644 index 000000000..25c4b8a40 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/public_encrypt/xor.js @@ -0,0 +1,11 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 Calvin Metcalf. All rights reserved. MIT license. + +export function xor(a, b) { + const len = a.length; + let i = -1; + while (++i < len) { + a[i] ^= b[i]; + } + return a; +} diff --git a/ext/node/polyfills/_crypto/crypto_browserify/randombytes.ts b/ext/node/polyfills/_crypto/crypto_browserify/randombytes.ts new file mode 100644 index 000000000..d70ada282 --- /dev/null +++ b/ext/node/polyfills/_crypto/crypto_browserify/randombytes.ts @@ -0,0 +1,47 @@ +// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license. +// Copyright 2017 crypto-browserify. All rights reserved. MIT license. +import { Buffer } from "internal:deno_node/polyfills/buffer.ts"; +import { nextTick } from "internal:deno_node/polyfills/_next_tick.ts"; + +// limit of Crypto.getRandomValues() +// https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getRandomValues +const MAX_BYTES = 65536; + +// Node supports requesting up to this number of bytes +// https://github.com/nodejs/node/blob/master/lib/internal/crypto/random.js#L48 +const MAX_UINT32 = 4294967295; + +export function randomBytes( + size: number, + cb?: (err: Error | null, b: Buffer) => void, +) { + // phantomjs needs to throw + if (size > MAX_UINT32) { + throw new RangeError("requested too many random bytes"); + } + + const bytes = Buffer.allocUnsafe(size); + + if (size > 0) { // getRandomValues fails on IE if size == 0 + if (size > MAX_BYTES) { // this is the max bytes crypto.getRandomValues + // can do at once see https://developer.mozilla.org/en-US/docs/Web/API/window.crypto.getRandomValues + for (let generated = 0; generated < size; generated += MAX_BYTES) { + // buffer.slice automatically checks if the end is past the end of + // the buffer so we don't have to here + globalThis.crypto.getRandomValues( + bytes.slice(generated, generated + MAX_BYTES), + ); + } + } else { + globalThis.crypto.getRandomValues(bytes); + } + } + + if (typeof cb === "function") { + return nextTick(function () { + cb(null, bytes); + }); + } + + return bytes; +} |