\documentclass[12pt]{article}
%\setlength{\oddsidemargin}{0in}
%\setlength{\textwidth}{6.5in}
%
%\setlength{\topmargin}{-0.25in}
%\setlength{\headheight}{0in}
%\setlength{\headsep}{0in}
%\setlength{\textheight}{9.25in}
\PassOptionsToPackage{hyphens}{url}\usepackage[colorlinks=true,urlcolor=blue,linkcolor=blue,citecolor=blue]{hyperref}
%\usepackage{url}
%\usepackage{graphicx}
\usepackage[all]{hypcap}
\usepackage{graphics}
\usepackage{amsthm}
\usepackage{amsfonts} % provides \mathbb, which produces poor-man bold for N, Z, Q, R...
%\usepackage{amssymb} % also provides \mathbb
\usepackage{fancyhdr}
\pagestyle{fancy}
%\fancyhead{}
%\fancyfoot{}
\lhead{PJCL Version 0.9}
%\chead{{\copyright} Copyright 2018 Pomcor}
\rhead{\thepage}
%\fancyfoot{}
\fancyfoot[C]{{\copyright} Copyright 2018 Pomcor}
%\fancyfoot[C]{Pomcor Confidential}
%\fancyfoot[RO,RE] {\thepage}
\renewcommand{\headrulewidth}{0pt}
\fancypagestyle{plain}%
{%
\renewcommand{\headrulewidth}{0pt}%
\fancyhf{}%
\fancyfoot[C]{{\copyright} Copyright 2018 Pomcor}
}
%\newcommand{\mydash}{\mbox{\Huge -}}
%\newcommand{\rmLCM}{\mbox{\rm LCM}}
%\newtheorem{fact}{Fact}
%\newtheorem{theorem}{Theorem}
%\newtheorem{corollary}{Corollary}
%\newtheorem{informal}{Informal Statement}
%\newtheorem{iconclusion}{Informal Conclusion}
\begin{document}
\title{Pomcor JavaScript Cryptographic Library (PJCL)}
\author{Version 0.90r1 (beta test version)}
\date{}
\maketitle
%\renewcommand\abstractname{Executive Summary}
%\begin{abstract}
%\end{abstract}
%\pagebreak
\tableofcontents
%\listoffigures
%\listoftables
\section{Changes in Revision 1 of Version 0.9}
Revision 1 fixes the following bugs in Version 0.9:
\begin{itemize}
\item Several loop variables meant to be local were undeclared and
were thus global.
\item Several global loop variables were not prefixed by ``{\tt pjcl}".
\end{itemize}
Revision 1 also makes a change to {\tt pjclECDSAVerify} for the sake
of code clarity. The change does not affect the output of the
function but brings the code closer to its mathematical specification.
\section{Functionality provided in Version 0.9}
The primary goal of this version of the library is to support the
implementation of cryptographic authentication and remote identity
proofing. To that purpose it provides:
\begin{itemize}
\item Big integer arithmetic, including:
\begin{itemize}
\item Long multiplication and Karatsuba multiplication \cite[\S~15.1.2]{gmp-manual}.
\item Montgomery reduction \cite[\S~14.3.2]{Menezes97handbookof}.
\item Sliding window exponentiation \cite[Algorithm
14.85]{Menezes97handbookof} in a generic monoid, with
specializations including modular
exponentiation with Montgomery reduction and scalar
multiplication of a point of an elliptic curve.
(The latter may be implemented differently in a future version.)
Our implementation of
modular exponentiation with Montgomery reduction is several times
faster than the one in the Stanford JavaScript Cryptographic
Library (SJCL) \cite{sjcl} according to the performance testing
described below in Section~\ref{s:modexpperf}.
\end{itemize}
\item Elliptic curve group operations, in the NIST curves P-256
\cite[\S~D.2.3]{DSS-4} and P-384 \cite[\S~D.2.4]{DSS-4}. Other
curves may be supported in the future.
\item The following hash functions and message authentication codes:
\begin{itemize}
\item SHA-256 and SHA-384 \cite{FIPS180-4-2015}.
\item HMAC-SHA256 and HMAC-SHA384 \cite{RFC2104,FIPS198-1}.
\end{itemize}
\item Pseudo-random number generation based on the NIST Hash-Based
Deterministic Random Bit Generator (Hash\_DRBG) \cite{SP800-90Ar1}
with hash functions SHA-256 and SHA-384.
\item Prime number generation using the Miller-Rabin algorithm.
\item DSA \cite{DSS-4} with 128 bits of security strength, which
requires a 256-bit private key and a 3072-bit public key
\cite[Table~2]{sp800-57part1rev4}, including:
\begin{itemize}
\item Generation of domain parameters.
\item Key pair generation.
\item Signature generation.
\item Signature verification.
\end{itemize}
\item ECDSA \cite{ECDSACerticom},
\cite[\S~2.6.2]{washington2003elliptic} with NIST curves P-256 and
P-384, which provide 128 and 196 bits of security strength
respectively \cite[Table 2]{sp800-57part1rev4}, including:
\begin{itemize}
\item Key pair generation.
\item Public key validation \cite[\S~6.2]{ECDSACerticom}.
\item Signature generation.
\item Signature verification.
\end{itemize}
\end{itemize}
Future versions of the PJCL may support secure messaging and data
protection at rest, and to that purpose may provide encryption and key
agreement functionality.
\section{Requirements}
PJCL does not require any recent features of JavaScript, nor any
particular JavaScript engine, runtime environment or framework. The
PJCL API is a collection of global functions and variables whose names
are all prefixed by {\tt pjcl} to avoid name conflicts. (The PJCL
acronym and the {\tt pjcl} prefix are trademarks of Pomcor.) Therefore
PJCL can be used wherever JavaScript is used. It can be used in a
browser, in a native app (e.g.\ using React Native
\cite{react-native}), or in a server (e.g.\ using node.js
\cite{node-js}).
The PJCL pseudo-random bit generator must be seeded with random bits
with sufficient entropy obtained from a true random source. It may be
reseeded before generating random bits for the sake of prediction
resistance \cite[\S~8.8]{SP800-90Ar1}. You are responsible for
providing the random bits used for seeding or reseeding. Methods for
obtaining entropy are discussed below in Section~\ref{s:entropy}.
{\tt Math.random} does not provide entropy.
\section{License}
The PJCL library can be used subject to the terms of the
PJCL license, which can be found at
\url{https://pomcor.com/pjcl/pjcl-license.txt}.
\section{Downloadable zip archive}
The current version of the PJCL library can be downloaded as a zip archive
that can be found at
\url{https://pomcor.com/pjcl/pjcl-090.zip}. The archive contains
a {\tt pjcl} directory, which itself contains the following files:
\begin{itemize}
\item The file {\tt pjcl.js} contains the PJCL library.
\item The file {\tt pjcl-withArgChecking.js} differs from {\tt pjcl.js} in
that most of the API functions include code that checks the validity
of their arguments. This may be useful for debugging applications
that use the library, and as a precise specification of the
properties of the arguments expected by the functions.
\item The directory {\tt KaratsubaThresholds} contains files that let you estimate
optimal thresholds for Karatsuba multiplication and Karatsuba squaring
in a particular JavaScript environment,
as described below in Section~\ref{s:karatsuba-thresholds}.
\item The file {\tt browserEntropy.js} contains examples of how to generate random bits in browsers that support the Web Crypto API.
\item The directory {\tt ModExpPerfTesting} contains files that allow you to
test the performance of modular exponentiation on a browser using
long multiplication or Karatsuba multiplication and compare it to
the performance of SJCL, as described below in
Section~\ref{s:modexpperf}.
\item The directory {\tt DSAPerfTesting} contains files that allow you to
test the performance of DSA on a browser using
long multiplication or Karatsuba multiplication, as described below in
Section~\ref{s:dsaperf}. ECDSA performance testing
may be provided in the future.
\end{itemize}
\section{Data encodings}
\label{s:encodings}
\subsection{Numbers in JavaScript}
With some exceptions, JavaScript numbers are represented in IEEE 754
double-precision (64-bit) floating point format
\cite{IEEE-double-precision}, which allows every nonnegative integer
$n$ in the range $0 \leq n < 2^{53}$ to be represented exactly.
\subsection{Big integers in PJCL}
\label{s:big-integers}
PJCL represents nonnegative integers of arbitrary size in base $B =
2^\beta$, with $\beta = 24$. Following tradition, we refer to the
digits of the base-$B$ representation as {\em limbs}. A limb is thus
a 24-bit quantity. It is unlikely but not impossible that the number of bits per limb
will change in the future. Your own code should use the variables
of Section~\ref{s:global-vars} to avoid hardcoding the number of bits per limb.
The limbs are stored in an array.
For performance reasons, the least significant limb is the first element of the array,
i.e.\ the element with index 0.
Thus, the index of each limb is its weight in the base-$B$
representation: limb $\lambda_i$ of the nonnegative integer $N =
\sum_{0 \leq i < n} \lambda_i B^i$ is stored at position
$i$ in the $n$-limb array that represents $N$.
The order in which the limbs are stored in the array only matters
for understanding the implementation of the library; it should not
matter to developers who use the API, and it does not affect the
API-level metaphors. For example, ``shifting left by one limb'' shall
mean shifting by one limb towards the most significant end of the
array, i.e.\ multiplying by $B$, even though the most significant
limb is the array element with the highest index, which is the rightmost
element in an array literal; and the ``leading limb'' shall
mean the most significant limb.
JavaScript arrays are not objects, but can have properties like
objects. A negative integer is represented by encoding its absolute
value as an array of limbs, and giving the array a property {\tt
negative} with value {\tt true}. A nonnegative integer does not
have a {\tt negative} property.
We use the term {\em big integer} to refer to an integer represented in base $B$ as an
array of limbs with an optional {\tt negative property}.
A big integer has a unique representation. Leading zero limbs are not
allowed, i.e.\ the most significant limb must not be zero. The
big integer zero is represented as an empty array without a {\tt negative}
property.
For the sake of performance and code footprint minimization, some
functions ignore the {\tt negative} property of big integer arguments
and thus operate on the absolute values of those arguments, while
other functions take the {\tt negative} property into account and thus
operate on their relative values. The latter functions are
distinguished by the suffix {\tt Rel} in their names. For example,
{\tt pjclAdd(x,y)} adds the absolute values of the parameters {\tt x}
and {\tt y}, while {\tt pjclAddRel} adds their relative values.
\subsection{Other data types}
\label{s:other-data-types}
A {\em bit array} is a JavaScript array whose elements are JavaScript
floating point numbers with value 0 or 1. Bit arrays are used for
encoding the inputs and outputs of hash functions and random bit
generators, and sometimes for encoding a nonnegative integer or a
sequence of fixed-length nonnegative integers,
each integer being mapped to a sequence of bits comprising the {\em
binary representation} of the integer, with the most significant bit
being first, i.e.\ having the lowest array index.
A {\em hex string} is a JavaScript string whose characters are
hexadecimal digits: 0\ldots 9, A\ldots F or a\ldots f. Functions that
take a hex string as input accept both upper and lower case
hexadecimal digits. Functions that produce a hexadecimal string as
output use the JavaScript method {\tt toString(16)}, which may produce
upper or lower hexadecimal digits depending on the JavaScript engine
that interprets the function. JavaScript encodes strings in UTF-16,
so each hex digit in a hex string is encoded as a 16-bit UTF-16
character.
An {\em ASCII string} is a JavaScript string whose characters are
ASCII characters. Although ASCII characters can be encoded in 7 bits,
they are stored as 16-bit UTF-16 characters in a JavaScript ASCII
string.
In a function name such as, for example, {\tt pjclUTF16toBitArray},
the substring {\tt UTF16} is used to refer to a JavaScript string
where all 16 bits of the UTF-16 encoding of each character matter,
even if all the characters in the string happen to be within the ASCII
range of UTF-16 and have UTF-16 encodings whose most significant 9
bits are 0.
An {\em unsigned 32-bit integer} is a nonnegative integer $n$ in the
range $0 \leq n < 2^{32}$, represented in JavaScript as an IEEE double precision
floating point number. In function names the
substring {\tt UI32} refers to an unsigned 32-bit integer and the
substring {\tt UI32Array} to an array of unsigned 32-bit integers.
Notice that {\tt UI32Array} refers to an ordinary JavaScript array,
not to the {\em typed array\/} {\tt UInt32Array}. Typed arrays are
not used in PJCL. However, an application that uses typed arrays may
pass an argument of type {\tt UInt32Array} to a PJCL function that
expects an ordinary JavaScript array of 32-bit unsigned integers.
\section{API}
\label{s:api}
This section describes the global variables and functions that
comprise the API in the order in which they are declared in {\tt
pjcl.js}.
\subsection{Argument expectations}
When a description of a function states that a parameter is {\em
expected\/} to have some property, it is an error if the expectation
is not met. In {\tt pjcl-withArgChecking.js}, most of the API functions
have argument checking code that throws an exception if such
expectations are not met.
\subsection{Side effects}
Functions have no side effects unless otherwise indicated in their documentation. The following functions have side effects in the current version of the library: {\tt pjclShortShiftLeft, pjclShiftLeft, pjclShortShiftRight,\\pjclShiftRight, pjclPreExp} and {\tt pjclPreExp2}.
\subsection{Global variables and functions related to the representation of big integers}
\subsubsection{\tt var pjclBaseBitLength\\var pjclBase\\var pjclBaseMask\\var pjclBaseMaskMinusOne\\var pjclBaseInv\\var pjclBaseAsBigInt\\var pjclHalfBase}
\label{s:global-vars}
These global variables encapsulate most of the dependencies on the
fact that a limb has 24 bits. Your code should not hardcode the fact
that a limb has 24 bits.
\begin{itemize}
\item The value of {\tt pjclBaseBitLength} is $\beta$, i.e.\ 24.
\item The value of {\tt pjclBase} is $B$, i.e. $2^{24}$, encoded as a JavaScript number.
\item The value of {\tt pjclBaseMask} if $B-1$, encoded as a JavaScript number,
which is viewed as
$$
\underbrace{00000000}_8\underbrace{111111111111111111111111}_{24}
$$
by JavaScript bitwise operators.
\item The value of {\tt pjclBaseMaskMinusOne} is $B-2$, encoded as a JavaScript number,
which is viewed as
$$
\underbrace{00000000}_8\underbrace{111111111111111111111110}_{24}
$$
by JavaScript bitwise operators.
\item The value of {\tt pjclBaseInv} is $1/B$ encoded as a JavaScript (floating point) number.
\item The value of {\tt pjclBaseAsBigInt} is $B$, encoded as a big integer.
\item The value of {\tt pjclHalfBase} is $B/2$, encoded as a JavaScript number,
which is viewed as
$$
\underbrace{00000000}_8\underbrace{100000000000000000000000\tt }_{24}
$$
by JavaScript bitwise operators.
\end{itemize}
\subsubsection{\tt function pjclWellFormed(x)}
Returns {\tt true} if the parameter {\tt x} is a well-formed big
integer, or {\tt false} otherwise. It is used for argument checking.
\subsection{Conversion functions}
\subsubsection{\tt function pjclHex2BitArray(s)}
The parameter {\tt s} is expected to be a hex string, which the
function converts to a bit array by mapping each hex digit in {\tt s}
to the four bits comprising the binary representation of the digit.
\subsubsection{\tt function pjclASCII2BitArray(s)}
The parameter {\tt s} is expected to be an ASCII string, which the
function converts to a bit array by mapping each ASCII character in
{\tt s} to the eight bits that comprise the 8-bit binary
representation of the {\em ASCII code\/} of the character. Since an
ASCII code is an integer in the range 0\ldots 127, the first of the 8
bits is 0. Note that although each character is encoded as a 16-bit
UTF character in the JavaScript string {\tt s}, it is mapped to only 8
bits in the resulting bit array.
\subsubsection{\tt function pjclUTF16toBitArray(s)}
The parameter {\tt s} is expected to be a JavaScript string, which the
function converts to a bit array by mapping each character to the
16-bit binary representation of its UTF-16 code.
\subsubsection{\tt function pjclByte2BitArray(byte)}
The parameter {\tt byte} is expected to be a JavaScript floating point
number whose value is an integer $n$ in the range $0\leq n < 2^8$,
which is converted to a bit array whose elements are the 8 bits of the
binary representation of $n$.
\subsubsection{\tt function pjclUI32toBitArray(ui32)}
The parameter {\tt ui32} is expected to be an unsigned 32-bit integer,
i.e.\ an integer $n$ in the range $0 \leq n < 2^{32}$, which is
converted to a bit array whose elements are the 32 bits of the binary
representation of $n$.
\subsubsection{\tt function pjclUI32Array2BitArray(x)}
The parameter {\tt x} is expected to be an array where each element is
a JavaScript number whose value is an integer $n$ in the range $0 \leq
n < 2^{32}$. The function converts {\tt x} to a bit array by mapping
each integer $n$ to the 32 bits of its binary representation. As
discussed above in Section~\ref{s:encodings}, PJCL does not use typed
arrays, but an application may pass a {\tt UInt32Array} as an argument
to the function instead of an ordinary JavaScript array.
\subsubsection{\tt function pjclBigInt2BitArray(x)}
The parameter {\tt x} is expected to be a big integer with mathematical value $x$.
The {\tt negative} property of {\tt x}, if present, is ignored.
The function returns a bit array representing the binary encoding of
$|x|$ without leading zeros.
If $x = 0$ the bit array is empty.
\subsubsection{\tt function pjclBigInt2SizedBitArray(x,size)}
The parameter {\tt x} is expected to be a big integer with
value $x$.
The {\tt negative} property of {\tt x}, if present, is ignored.
The parameter {\tt size} is expected to be a JavaScript number whose
value is a nonnegative integer $n$. The function returns a bit array
of length $n$. If $|x| < 2^n$, the
bit array is the $n$-bit binary representation of $|x|$ (with leading zero bits as needed). If $|x| >= 2^n$,
the bit array is the $n$-bit binary representation of $|x| \bmod 2^n$.
\subsubsection{\tt function pjclBitLengthOfBigInt(x)}
The parameter {\tt x} is expected to be a big integer with
value $x$.
The {\tt negative} property of {\tt x}, if present, is ignored.
The function returns the length of the binary
representation of $|x|$, i.e.\ the length of the bit array that would be
returned by {\tt pjclBigInt2BitArray(x)}.
\subsubsection{\tt function pjclBitArray2UI32Array(bitArray)}
The parameter {\tt bitArray} is expected to be a bit array of length
$32n$. The function returns an array of $n$ 32-bit unsigned integers
obtained by partitioning the bit array into groups of 32 bits and
viewing each group as the binary representation of a nonnegative
integer.
\subsubsection{\tt function pjclBitArray2BigInt(bitArray)}
The parameter {\tt bitArray} is expected to be a bit array of any length. The
function returns the nonnegative big integer whose binary representation is the
bit array.
\subsubsection{\tt function pjclBitArray2Hex(bitArray)}
The parameter {\tt bitArray} is expected to be a bit array of any length. The
function returns a hex string obtained by: (i) prepending leading zero
bits to the bit array as needed to make the length of the array a
multiple of 4 (notice the difference with {\tt
pjclBitArray2UI32Array}, which expects the length of its argument to
be a multiple of 32 and does not prepend any leading zeros); and (ii)
partitioning the resulting bit array into groups of four bits and
viewing each group as the binary representation of a hexadecimal
digit; if the hexadecimal digit is greater than nine, whether it is
encoded as an upper or lower case letter depends on the implementation
of the {\tt toString(16)} method by the JavaScript engine.
\subsubsection{\tt function pjclHex2BigInt(s)}
The parameter {\tt s} is expected to be a hex string. The function
returns the big integer having {\tt s} as its hexadecimal representation.
\subsubsection{\tt function pjclBigInt2Hex(x)\\function pjclBigInt2Hex(x,minHexLength)}
The parameter {\tt x} is expected to be a big integer, and the
parameter {\tt minHexLength}, if the function is called with two
arguments, a JavaScript number whose value is a nonnegative integer. The function returns a hex string
consisting of the hexadecimal representation of the big integer,
prepended with hexadecimal zero digits as needed to bring its length
to the value of {\tt minHexLength}.
\subsubsection{\tt function pjclUI32toHex(x)}
The parameter {\tt x} is expected to be an unsigned 32-bit integer, which is
converted to its hexadecimal representation encoded as a hex string.
\subsubsection{\tt function pjclUI32Array2Hex(x)}
The parameter {\tt x} is expected to be an array of
unsigned 32-bit integers. The function converts {\tt x} to a hex string by mapping
each integer to its hexadecimal representation.
\subsection{Basic arithmetic functions}
\subsubsection{\tt function pjclGreaterThan(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big integers
with mathematical values $x$ and $y$. Their {\tt negative}
properties, if present, are ignored. The function returns {\tt true}
if $|x| > |y|$, {\tt false} otherwise.
\subsubsection{\tt function pjclGreaterThanRel(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big integers
with mathematical values $x$ and $y$. The function returns {\tt true}
if $x > y$, {\tt false} otherwise.
\subsubsection{\tt function pjclGreaterThanOrEqual(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big integers
with mathematical values $x$ and $y$. Their {\tt negative}
properties, if present, are ignored. The function returns {\tt true}
if $|x| \geq |y|$, {\tt false} otherwise.
\subsubsection{\tt function pjclGreaterThanOrEqualRel(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big integers
with mathematical values $x$ and $y$. The function returns {\tt true}
if $x \geq y$, {\tt false} otherwise.
\subsubsection{\tt function pjclEqual(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big integers
with mathematical values $x$ and $y$. Their {\tt negative}
properties, if present, are ignored. The function returns {\tt true}
if $|x| = |y|$, {\tt false} otherwise.
\subsubsection{\tt function pjclEqualRel(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big integers
with mathematical values $x$ and $y$. The function returns {\tt true}
if $x = y$, {\tt false} otherwise.
\subsubsection{\tt function pjclAdd(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big integers
with mathematical values $x$ and $y$. Their {\tt negative}
properties, if present, are ignored. The function returns the
nonnegative big integer representing $|x| + |y|$. Thus if $x, y \geq 0$,
it simply returns the big integer representing $x+y$.
\subsubsection{\tt function pjclAddRel(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big integers
with mathematical values $x$ and $y$. The function returns
the big integer representing $x+y$, which may be negative.
\subsubsection{\tt function pjclSub(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big integers
with mathematical values $x$ and $y$. Their {\tt negative}
properties, if present, are ignored. {\em The function expects
that\/} $|x| \geq |y|$, and returns the nonnegative big integer
representing $|x| - |y|$.
\subsubsection{\tt function pjclSubRel(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big
integers with mathematical values $x$ and $y$. The function returns
the big integer representing $x-y$, which may be negative.
\subsubsection{\tt var pjclMult\\function pjclMult\_Long(x,y)\\function pjclMult\_Karatsuba(x,y)}
Big integer multiplication is performed by calling the function {\tt
pjclMult(x,y)}. However, there is no definition of that function.
Instead, {\tt pjclMult} is a global variable which must be assigned
either the function {\tt pjclMult\_Long}, which implements long
multiplication, or the function {\tt pjclMult\_Karatsuba}, which
implements Karatsuba multiplication. Both implementations may be used
within the same application by assigning different implementations to
{\tt pjclMult} at different times.
Both implementations expect the parameters {\tt x} and {\tt y} to be
big integers with mathematical values $x$ and $y$, ignore the {\tt
negative} properties of the parameters if present, and return the big integer representing the
product of the absolute values of $x$ and $y$, $|x|\cdot|y|$.
Long multiplication uses an optimized version of the same algorithm
that is used for multiplication by hand. Karatsuba multiplication
uses the recursive algorithm described in
\cite[\S~15.1.2]{gmp-manual}, carefully implemented for good performance on JavaScript.
The Karatsuba algorithm is asymptotically faster than long
multiplication, so it is faster for larger operands but slower for
smaller operands. During an execution of the algorithm, recursive calls
fall back on long multiplication when the size of the operands becomes
less than a {\em Karatsuba multiplication threshold}. The optimal threshold
depends on the platform (machine and JavaScript engine) being used, and can be
estimated for a particular machine and engine combination using the
tool described below in Section~\ref{s:karatsuba-thresholds}. The
estimated threshold, expressed as a number of limbs, should be assigned
to the global variable {\tt pjclKaratsubaThresholdMult} before using
{\tt pjclMult\_Karatsuba}. An exception is thrown if {\tt pjclMult\_Karatsuba}
is called when {\tt pjclKaratsubaThresholdMult} is undefined, but
a default is provided to avoid the exception.
\subsubsection{\tt function MultRel(x,y)}
The parameters {\tt x} and {\tt y} are expected to be big integers,
with mathematical values $x$ and $y$. Returns a big integer whose
mathematial value is the product $xy$.
\subsubsection{\tt function pjclShortMult(x,y)}
The parameter {\tt x} is expected to be a big integer, with
mathematical value $x$, whose {\tt negative} property, if present, is
ignored. The parameter {\tt y} is expected to be a JavaScript number
whose mathematical value $y$ is an integer in the range $0 \leq y < B = 2^{24}$. The
function returns the big integer representing the product $|x| \cdot y$.
\subsubsection{\tt var pjclSqr\\function pjclSqr\_Long(x,y)\\function pjclSqr\_Karatsuba(x,y)}
Big integer squaring is performed by calling the function {\tt
pjclSqr(x)}. Computing {\tt pjclSqr(x)} is
faster than computing {\tt pjclMult(x,x)}.
As is the case for big integer multiplication, two
implementations of the algorithm are available, which can be selected
by assigning either {\tt pjclSqr\_Long} or {\tt pjclSqr\_Karatsuba} to
the global variable {\tt pjclSqr}.
Both implementations expect the parameter {\tt x} to be a
big integer with mathematical value $x$ and return the big integer representing $x^2$.
There is a {\em Karatsuba squaring threshold} analogous to the Karatsuba multiplication
threshold. An optimal value of this threshold should be estimated using the
tool described below in Section~\ref{s:karatsuba-thresholds} and assigned to {\tt pjclKaratsubaThresholdSqr}, replacing the default, before using {\tt pjclSqr\_Karatsuba}.
\subsubsection{\tt function pjclShortShiftLeft(x,k)}
As discussed above in Section~\ref{s:big-integers}, ``shifting left'' a big integer
means shifting it towards its most significant end, i.e.\ multiplying it by a power of 2.
For performance reasons, {\tt pjclShortShiftLeft} operates by side-effect, modifying its first argument and returning no result; see {\tt pjclMultByPowerOf2} for an alternative without side-effect.
The parameter {\tt x} is expected to be a big integer, possibly negative, with
mathematical value $x$. The parameter {\tt k} is expected to be a JavaScript number
whose mathematical value $k$ is a nonnegative integer in the range $0
\leq k < \beta = 24$. The function operates by side-effect, computing the big integer representing
$x\cdot2^k$ and assigning it to {\tt x}.
Although at the API level the parameter {\tt x} is expected to be a
big integer, which must not have leading zero limbs, internally, in
{\tt pjclDiv}, the function {\tt pjclShortShiftLeft} is used with a
first argument that may have leading zero limbs. In {\tt
pjcl-withArgChecking} the argument checking code of {\tt
pjclShortShiftLeft} throws an exception if {\tt x} has leading zero
limbs, which {\tt pjclDiv} catches and cancels.
\subsubsection{\tt function pjclShiftLeft(x,k)\\function pjclMultByPowerOf2(x,k)}
As discussed above in Section~\ref{s:big-integers}, ``shifting left'' a big integer
means shifting it towards its most significant end, i.e.\ multiplying it by a power of 2.
For performance reasons, {\tt pjclShiftLeft} operates by side-effect, modifying its first argument and returning no result; on the other hand {\tt pjclMultByPowerOf2} is a wrapper that avoids the side-effect, at the cost of a small performance penalty, by making a copy of its first argument before modifying it and returning the result.
The parameter {\tt x} is expected to be a big integer, possibly negative. The parameter {\tt k} is expected to be a JavaScript number
whose mathematical value $k$ is a nonnegative integer. The function
returns the big integer representing $x\cdot2^k$. The functions compute the big integer representing
$x\cdot2^k$; {\tt pjclShiftLeft} assigns this big integer to its first argument,
while\\{\tt pjclMultByPowerOf2} returns the result without modifying its arguments.
\subsubsection{\tt function pjclShortShiftRight(x,k)}
This function is analogous to {\tt pjclShortShiftLeft}, shifting towards the least significant rather than the most significant end. It differs from {\tt pjclShortShiftLeft} in that {\tt x} is expected to be nonnegative. Without argument checking, the {\tt negative} property is ignored and {\tt x} may become ill-formed if its negative property is set and it becomes the empty array as a result of the shift.
\subsubsection{\tt function pjclShiftRight(x,k)\\function pjclDivByPowerOf2(x,k)}
These functions are analogous to {\tt pjclShiftLeft} and {\tt pjclMultByPowerOf2},
but like {\tt pjclShortShiftRight} they expect {\tt x} to be nonnegative. They shift towards the least significant end, thus dividing by a power of 2, i.e. computing $\lfloor
x/2^k \rfloor$.
\subsubsection{\tt function pjclDiv(x,y)}
The parameter {\tt x} and {\tt y} are expected to be big integers, with
mathematical values $x$ and $y$, whose {\tt negative} properties, if present, are
ignored; $y$ must not be zero. The function divides $|x|$ by $|y|$
using Algorithm 14.20 of \cite{Menezes97handbookof} and returns an object with
properties {\tt quotient} and {\tt remainder} whose values are big
integer representations of the quotient and the remainder.
\subsubsection{\tt function pjclDivRel(x,y)}
The parameter {\tt x} is expected to be a (relative) big integer with
mathematical value $x$, the parameter {\tt y} a positive big integer
with mathematical value $y$. The function returns an object with properties {\tt
quotient} and {\tt remainder} whose values are big integer
representations of the quotient and remainder of the division of $x$
by $y$. The mathematical values $q$ and $r$ of the {\tt quotient} and
{\tt remainder} properties are defined as follows: $q$ is
the largest (relative) integer such that $qy <= x$, and $r = x - qy$.
\subsubsection{\tt function pjclShortDiv(x,y)}
The parameter {\tt x} is expected to be a big integer, with
mathematical value $x$, whose {\tt negative} property, if any, is ignored. The parameter {\tt y}
is expected to be a nonzero limb, i.e.\ a JavaScript number
whose mathematical value $y$ is an integer in the range $0 < y < B = 2^{24}$. Returns an object
with a property {\tt quotient} whose value is the big integer
representation of the quotient of the division of $|x|$ by $y$, and a
property {\tt remainder} whose value is a JavaScript number representing the remainder.
This function relies on the fact that the JavaScript floating-point \% operator is not the same as the ``remainder" operation defined by IEEE 754, as explained in \cite[\S11.5.3]{ecmascript51}.
\subsubsection{\tt function pjclMod(x,m)}
The parameter {\tt x} is expected to be a big integer with
mathematical value $x$, the parameter {\tt m} a positive big integer
with mathematical value $m$. The function returns the big integer
representing $x \bmod m$.
\subsubsection{\tt function pjclTruncate(x,t)\\function pjclModPowerOf2(x,t)}
The parameter {\tt x} is expected to be a nonnegative big integer,
with mathematical value $x$ and the parameter {\tt t}
a JavaScript number whose mathematical value $t$ is a positive
integer. Both functions compute the big integer representing $x \bmod
2^t$. For performance reasons, {\tt pjclTruncate} operates by side-effect, modifying its first argument and returning no result; on the other hand {\tt pjclModPowerOf2} is a wrapper that avoids the side-effect, at the cost of a small performance penalty, by making a copy of its first argument before modifying it and returning the result.
Please note that {\tt pjclModPowerOf2} can only be used to reduce a nonnegative integer. You may use {\tt pjclMod} to reduce relative integers, at a much higher computational cost.
\subsubsection{\tt function pjclModLimb(x,m)}
The parameter {\tt x} is expected to be a nonnegative big integer with
mathematical value $x$, the parameter {\tt m} a JavaScript number
whose mathematical value $m$ is a positive integer less than $B$, i.e.\ less than $2^{24}$. Returns a
JavaScript number whose mathematical value is $x \bmod m$.
\subsubsection{\tt function pjclEGCD(a,b)\\function pjclEGCD(a,b,computeBothBezoutCoeffs)}
The parameters {\tt a} and {\tt b} are expected to be nonnegative big
integers with mathematical values $a$ and $b$. If the function is
called with three arguments and {\tt computeBothBezoutCoeffs} is or
type-converts to {\tt true,} the function implements the Extended
Euclidean Algorithm and returns an object with properties {\tt gcd},
{\tt x} and {\tt y} whose mathematical values are $d$, $x$
and $y$, where $d$ is the greatest common divisor of $a$ and $b$, and
$(x,y)$ is a pair of integers, called B\'ezout coefficients, that
satisfy $d = ax + by$. If only two arguments are passed to the
function, $y$ is not computed and the object returned by the function
does not have {\tt y} property.
\subsubsection{\tt function pjclModInv(x,m)}
The parameter {\tt x} is expected to be a big integer with
mathematical value $x$, the parameter {\tt m} a positive big integer
with mathematical value $m$. The function returns {\tt
undefined} if $x$ and $m$ are not coprime. Otherwise it returns a
big integer whose mathematical value is the inverse of $x$ modulo $m$.
\subsection{Montgomery reduction}
\label{s:montred}
Our implementation of Montgomery reduction is based on Section 14.3.2
of the Menezes et al.\ Handbook of Applied Cryptography
\cite{Menezes97handbookof}. More specifically, it is based on the
optimzed Algorithm 14.32, further optimized and adapted for use with
our big integer representation.
In this Section~\ref{s:montred} we use the same mathematical variables
as in algorithm 14.32, except that we write $B$ instead of $b$, since $B = 2^\beta = 2^{24}$ is
the base of our representation of big integers, as defined in Section~\ref{s:big-integers}.
Thus $m$ is the modulus, which must be coprime with $B$, i.e.\ odd;
$n$ is the number of limbs of the big integer representation
$(m_{n-1} \ldots m_1,m_0)_B$ of $m$;
$R=B^n$;
$m' = -m^{-1} \bmod B$; and $T$ is the nonnegative integer to be reduced, which must be
less than $mR$ and therefore have a big integer representation with no
more than $2n$ limbs.
In our implementation, the big integer representation of $m$ must have
at least two limbs. This is not required by algorithm 14.32, but it
it is required by our further optimization of the algorithm. For one-limb
moduli you may use ordinary modular reduction as provided by {\tt
pjclModLimb}.
Montgomery reduction is much faster than ordinary modular reduction,
but instead of computing $T \bmod m$, it computes $TR^{-1} \bmod m$.
It is intended to be used in an algorithm that requires many
multiplications (and/or squarings), such as modular exponentiation.
All quantities in the algorithm are modified to incorporate the factor
$R$. Instead of multiplying $x$ by $y$ to obtain $z = xy$ and then
reducing $z$ modulo $m$, the modified algorighm multiplies $xR$ by
$yR$ to obtain $(xR)(yR)$, then uses Montgomery reduction to compute
$(xR)(yR)R^{-1} = xyR = zR$. $zR$ can then be further multiplied by
$uR$ and Montgomery-reduced to produce $vR$ with $v=zu$, and so on.
Our implementation includes a function {\tt pjclPreMontRed} that
precomputes $m'$ and a function {\tt pjclMontRed} that computes the
Montgomery reduction of $T$ modulo $m$ using $m'$.
\subsubsection{\tt function pjclPreMontRed(m)}
The parameter {\tt m} is expected to be an odd positive big integer
with at least two limbs, whose mathematical value is the modulus $m$.
The function returns a JavaScript number whose mathematical value is
$m' = -m^{-1} \bmod B$.
\subsubsection{\tt function pjclMontRed(t,m,m1)}
The parameter {\tt t} is expected to be a nonnegative big integer,
the parameter {\tt m} an odd big integer having at least two limbs,
and {\tt m1} a JavaScript number whose mathematical value is $m' = -m^{-1} \bmod B$,
as returned by {\tt pjclPreMontRed(m)}.
The mathematical values $T$ of {\tt t} and $m$ of {\tt m} must satisfy
$T < mR$ with $R = B^n$, where $n$ is the number of limbs of the
modulus. The function returns a big integer with mathematical value
$TR^{-1} \bmod m$.
\subsection{Generic sliding window exponentiation in a monoid}
\subsubsection{\tt function pjclOptimalWindowSize(l)\\function pjclPreExp(slidingWindowSize,context)\\function pjclExp(exponent,context)}
\label{s:exp}
The function {\tt pjclExp(exponent,context)} implements generic
sliding window exponentiation in some monoid $M$ using a slightly
optimized version of Algorithm 14.85 of \cite{Menezes97handbookof}.
In this section we refer to the monoid operation as multiplication,
but {\tt pjclExp} can be used, and we do use it in this version of the
library, to implement scalar multiplication in monoids where the
operation is usually written as addition;\footnote{``Scalar multiplication'' and ``exponentiation'' are alternative names given
to the same external operation in a monoid, the term ``scalar multiplication''
being used when the operation is called ``addition'' while the term
``exponentiation is used when the operation is called
``multiplication''.}
{\tt pjclExp} is used by
{\tt pjclPlainExp} to implement exponentiation in $\mathbb{N}$, by
{\tt pjclModExp} to implement modular exponentiation with ordinary
reduction, by {\tt pjclMontExp} to implement modular exponentiation
with Montgomery reduction, and, as desribed below in
Section~\ref{s:scalar-mult}, by {\tt pjclScalarMult} to implement
scalar multiplication in the group of points of an en elliptic curve.
(In a future version of the library we plan to implement a sliding
window exponentiation function further optimized for groups by using nonadjacent form (NAF) to represent the exponent, and use
it to implement {\tt pjclScalarMult}, taking adantage of the fact that
the points of an elliptic curve form a group and point subtraction can
be implemented efficiently.)
The parameter {\tt exponent} of {\tt pcjlExp} is expected to be a big
integer whose mathematical value is a positive integer $e$. (We
exclude the case $e=0$, where the function would return the unit of
the monoid, but the functions that call {\tt pjclExp}, i.e.\ {\tt pjclPlainExp}, {\tt pjclModExp}, {\tt pjclMontExp} and {\tt pjclScalarMult}, take care of this special case). The parameter {\tt context}
is expected to be an object with a property {\tt context.g} specifying
the base $g \in M$ of the exponentiation, whose encoding depends on
the nature of $M$. The function returns an encoding of the element
$g^e$ of $M$.
The parameter {\tt context} must also have a method {\tt context.mult}
implementing the monoid operation, a method {\tt context.sqr} such
that {\tt context.\\sqr(x)} produces the same result as {\tt
context.mult(x,x)}, and a property {\tt context.preComputed} whose
value must be an array providing the results of the precomputation that takes place
at step 1 of Algorithm 14.85. It may also have additional properties
specific to a particular monoid, such as {\tt context.m}, whose value
is the modulus $m$, when {\tt pjclExp} is called by {\t pjclModExp} or
{\tt pjclMontExp}, and {\tt context.m1}, whose value is $m' = -m^{-1}
\bmod B$ where $B=2^\beta=2^{24}$ when it is called by {\tt pjclMontExp}.
The function {\tt pjclPreExp(slidingWindowSize,context)} is a side-effect function
that performs the
precomputation of step 1 of Algorithm 14.85. The parameter {\tt
slidingWindowSize} is expected to be a Javascript number whose
mathematical value is a positive integer, called $k$ in the algorithm,
to be used as the window size. The parameter {\tt context} is
expected to be an object with the above-mentioned properties and
methods {\tt context.g}, {\tt context.mult} and {\tt context.sqr}.
The function creates and fills the array {\tt context.preComputed}.
It does not return a result.
The function {\tt pjclOptimalWindowSize(l)} gives the optimal window
size for a given exponent size. The parameter {\tt l} is expected to
be a JavaScript number whose mathematical value is a positive integer that should be the approximate
bitlength of the exponent. The function retuns a JavaScript number
whose mathematical value is the optimal window size.
\subsection{Exponentiation in $\mathbb{N}$}
\subsubsection{\tt function pjclPlainExp(g,x)}
The function {\tt pjclPlainExp(g,x)} performs exponentiation in the
monoid $(\mathbb{N},+)$. The parameters {\tt g} and {\tt x} are
expected to be nonnegative big integers with mathematical values $g$
and $x$. The function returns the big integer representation of
$g^x$.
Notice that the result of this function will be unmanageable if the
exponent has more than one limb: if {\tt g} and {\tt x} have big
integer representations [2] and [0,1], with mathematical values $g =
2$ and $x = 2^{24}$, then the result of the function should have the mathematical
value $2^{2^{24}}$, whose big integer representation has 3,659,183
limbs.
\subsection{Modular exponentiation with ordinary reduction}
\subsubsection{\tt function pjclModExp(g,x,m)}
The function {\tt pjclModExp(g,x,m)} performs exponentiation in the
monoid $(\mathbb{Z}_m,\times)$, where $m$ is the mathematical value of
the parameter {\tt m}, and $\mathbb{Z}$ is the set of integers modulo
$m$. The parameters {\tt g}, {\tt x} and {\tt m} are expected to be
big integers with mathematical values $g \geq 0$, $x \geq 0$ and $m \geq 1$.
The function returns the big integer representation of $g^x \bmod m$.
Although {\tt pjclModExp} does not produce unmanageable results like
{\tt pjclModExp}, it is too slow to be used in most cryptographic
applications.
\subsection{Modular exponentiation with Montgomery reduction}
\subsubsection{\tt function pjclMontExp(g,x,m)}
The function {\tt pjclMontExp(g,x,m)} produces the same result as {\tt
pjclModExp(\\g,x,m)}, but using Montgomery reduction rather than
ordinary reduction, which makes it fast enough to be used in
cryptographic applications.
The parameters {\tt g} and {\tt x} are expected to be nonnegative big
integers, with mathematical values $g$ and $x$. The
parameter {\tt m} is expected to be a nonnegative big integer with $n \geq 2$
limbs whose mathematical value $m$ is odd.
Recall that $B = 2^\beta = 2^{24}$ was defined in
Section~\ref{s:montred} as the base of the big integer representation.
Let $R = B^n$. Using Montgomery reduction amounts to performing the
exponentiation in the isomorphic image of the monoid
$(\mathbb{Z}_m,\times)$ by the function $\phi_R$ that maps $u \in
\mathbb{Z}_m$ to $uR$. If we call $\ast_R$ the operator of the image
monoid, the product $uR \ast_R vR$ of two elements of
$\phi_R(\mathbb{Z}_m)$ is $uvR \bmod m$, which is computed in two steps
by first multiplying $uR$ and $vR$ to obtain $uvR^2$ then performing a
Montgomery reduction to obtain $(uvR^2)R^{-1} \bmod m = uvR \bmod m$.
{\tt pjclMontExp} assigns the big integer representation of $gR$ to
{\tt context.g} and uses {\tt pjclExp} to raise $gR$ to $x$ in the
image monoid by performing multiplications followed by Montgomery
reduction using {\tt pjclContextualMontMult} and squarings followed by
Montgomery reduction using {\tt pjclContextualMontSqr}. The result
$g^xR \bmod m$ is converted to $g^x \bmod m$ by one final Montgomery
reduction.
\subsection{Generic double exponentiation in a commutative monoid}
\subsubsection{\tt function pjclOptimalWindowSize2(l)\\function pjclPreExp2(slidingWindowSize,context)\\function pjclExp2(exponentG,exponentY,context)}
These functions are like those of Section~\ref{s:exp}, with the difference that {\tt pjclExp2} computes the product of two exponentials, with exponents {\tt exponentG} and {\tt exponentY} and corresponding bases {\tt context.g} and {\tt context.y}, using ``Shamir's trick"
of combining the squarings of the two exponentiations.
Either exponent, but not both, may be (the big integer) zero.
In this version of the library,
{\tt pjclExp2} is used by {\tt pjclMontExp2} and {\tt pjclScalarMult2}. The array {\tt context.preComputed} computed by {\tt pjclPreExp2} as a side-effect
is doubly indexed, and {\tt pjclOptimalWindowSize2} computes the optimal window size for double exponentiation, taking as input the bit length of the longest of the two exponents.
\subsection{Double exponentiation with Montgomery reduction}
\subsubsection
[\tt function pjclMontExp2(\\\mbox{}\hspace{.2in}g,y,exponentG,exponentY,m)]
{\tt function pjclMontExp2(g,y,exponentG,exponentY,m)}
The function pjclMontExp2(g,y,exponentG,exponentY,m) produces the
same result as
\begin{verbatim}
pjclMod(pjclMult(pjclMontExp(g,exponentG,m),pjclMontExp(y,exponentY,m)),m)
\end{verbatim}
but substantially faster, using {\tt pjclExp2}.
\subsection{Hash functions and message authentication codes (SHA, HMAC)}
\subsubsection{\tt function pjclSHA256(bitArray)}
The function {\tt pjclSHA256} takes as input a sequence of bits
encoded as a bit array and returns a bit array that encodes the result
of applying the function SHA-256 of \cite{FIPS180-4} to the input.
\subsubsection{\tt function pjclSHA384(bitArray)}
The function {\tt pjclSHA384} takes as input a sequence of bits
encoded as a bit array and returns a bit array that encodes the result
of applying the function SHA-384 of \cite{FIPS180-4} to the input.
\subsubsection{\tt function pjclHMAC\_SHA256(key,text)}
The function {\tt pjclHMAC\_SHA256} implements the HMAC algorithm of
\cite{FIPS198-1} in conjunction with the hash function SHA-256 of
\cite{FIPS180-4}. The parameters {\tt key} and {\tt text} are
expected to be bit arrays, and the result is a bit array.
\subsubsection{\tt function pjclHMAC\_SHA384(key,text)}
The function {\tt pjclHMAC\_SHA384} performs an HMAC computation using
the hash function SHA-384 instead of SHA-256.
\subsubsection{\tt function pjclHMAC\_SHA256PreComputeKeyHashes(key)\\function pjclHMAC\_SHA256WithPreCompute(\\\mbox{}\hspace{.2in}iKeyHash,oKeyHash,text)}
An HMAC computation consists of two hash computations, and the first
block of each computation does not depend on the text. When you need
to perform many HMAC computations with the same key, you can use
{\tt pjclHMAC\_SHA256PreComputeKeyHashes(key)} to precompute the hashes
of those two blocks. The result is an object with properties {\tt iKeyHash}
and {\tt oKeyHash}, whose values you can pass as arguments to\\{\tt
pjclHMAC\_SHA256WithPreCompute(iKeyHash,oKeyHash,text)} to obtain the
value of the HMAC computation for each {\tt text}.
\subsubsection{\tt function pjclHMAC\_SHA384PreComputeKeyHashes(key)\\function pjclHMAC\_SHA384WithPreCompute(\\\mbox{}\hspace{.2in}iKeyHash,oKeyHash,text)}
The functions {\tt pjclHMAC\_SHA384PreComputeKeyHashes} and\\{\tt
pjclHMAC\_SHA384WithPreCompute} perform a split HMAC precomputation
like {\tt pjclHMAC\_SHA256PreComputeKeyHashes} and\\{\tt
pjclHMAC\_SHA256WithPreCompute} using the hash function SHA-384
instead of SHA-256.
\subsection{Statistically random data vs.\ cryptographically random data}
We make a distinction between statistically random d[ata and
cryptographically random data. We say that data produced by a data
source is {\em statistically random\/} if it is uniformly distributed
over a given range but may be predictable from data previously
generated by the source. By contrast we say that data produced by a
data source is {\em cryptographically random\/} if it is uniformly
distributed and unpredictable from data previously generated by the
source.
We use the built-in JavaScript function {\tt Math.random} to generate
statistically random data, and a pseudo-random bit generator
implemented as specified in \cite[\S~10.1.1]{SP800-90Ar1} to generate
cryptographically random data. {\tt Math.random} is well suited for generating statistically random data because its output is specified as having an approximately uniform distribution
\cite[15.8.2.14]{ecmascript51}. It must not be used to
generate cryptographically random data, or to seed or reseed the random
bit generator, because its output may be predictable.
\subsection{Random bit generation (RBG) vs.\ random number generation (RNG)}
We make a distinction between random bit generation and random number
generation. Generating $l$ random bits is equivalent to generating a
random number $n$ in the range $0 \leq n < 2^l$. We use the term {\em random bit
generation (RBG)\/} to refer to the generation of random bits or to the
generation of a number in such a range. On the other hand we use the
term {\em random number generation (RNG)} to refer to the generation
of a random number $n$ in a range $a \leq n < b$, where $a$ may not be
zero and $b-a$ may not be a power of two.
\subsection{Generation of statistically random data}
\subsubsection{\tt function pjclStRndLimb()}
The function {\tt pjclStRndLimb} takes no arguments and returns a
statistically random JavaScript number that can serve as big integer
limb, i.e.\ whose mathematical value $n$ is an integer in the range $0
\leq n < B = 2^\beta = 2^{24}$.
\subsubsection{\tt function pjclStRndBigInt(n)}
The parameter {\tt n} is expected to be a JavaScript number whose
mathematical value is a nonnegative number $n$. The function returns
a statistically random big integer with up to $n$ limbs, i.e.\ whose
mathematical value $x$ is uniformly distributed in the range $0 \leq x
< B^n$.
\subsubsection{\tt function pjclStRndHex(n)}
The parameter {\tt n} is expected to be a JavaScript number whose
mathematical value is a nonegative number $n$. The function returns a
hex string consisting of $n$ statistically random hex digits. Whether hex
digits greater than 9 are in upper or lower case depends on the
implementation of the {\tt toString(16)} method by the JavaScript
engine.
\subsubsection{\tt function pjclStatisticalRNG(a,b)}
The parameters {\tt a} and {\tt b} are expected to be big integers
with mathematical values $a$ and $b$ such that $0 \leq a < b$. The
function returns a statistically random big integer whose mathematical
value $x$ is uniformly distributed in the range $a \leq x < b$.
\subsection{Cryptographic random number generation}
\label{cryptorandom}
The functions in this section implement a deterministic random bit
generator (DRBG) based on hash functions. More specifically, they
implement the {\em Hash\_DRBG mechanism\/} of of
\cite[\S~10.1.1]{SP800-90Ar1}, using the hash functions SHA-256 for
128 bits of security strength and SHA-384 for 192 bits of security
strength.
\subsubsection{\tt function pjclRBG128Instantiate(\\\mbox{}\hspace{.2in}rbgStateStorage,entropy)\\function pjclRBG128Instantiate(\\\mbox{}\hspace{.2in}rbgStateStorage,entropy,nonce)}
\label{s:entropy}
This function instantiates the DRBG based on SHA-256 specified in
Section 10.1.1.2 of \cite{SP800-90Ar1}. No {\tt
personalization\_string} is used.
The parameter {\tt rbgStateStorage} may be a JavaScript object or, in
a JavaScript runtime environment that implements the {\em W3C Web
Storage} specification \cite{local-storage}, a {\em storage object},
i.e.\ either {\tt localStorage} or {\tt sessionStorage}.
The parameter {\tt entropy} is expected to be an array of at least 128
bits. An exception is thrown
otherwise by both the argument checking and the production versions of
the library. However this is only a sanity check, since there is no
way for the function to know if the value of the parameter has {\em
full entropy}. (A bit string is said to have full entropy if its
entropy is equal to its length.)
Do not use {\tt Math.random} to generate the value of the {\tt
entropy} parameter. In a JavaScript runtime environment that
implements the {\em Web Cryptography API\/} you may use {\tt
crypto.getRandomValues()} to generate entropy;
notice, however, that the Web Cryptography API
does not explicitly guarantee that the output of {\tt
crypto.getRandomValue()} has full entropy.
Examples of how to do this are provided by two functions {\tt pjclBrowserEntropy128Bits}
and {\tt pjclBrowserEntropy192Bits}, which
can be found in the file {\tt browserEntropy.js}.
The first of them is used for DSA performance testing.
Notice, however, that the Web Cryptography API
does not explicitly guarantee that the output of {\tt
crypto.getRandomValue()} has full entropy.
In a JavaScript runtime
environment that provides access to an underlying Unix-like OS you may
use {\tt /dev/random}, which is supposed to provide full entropy but
may block if not enough entropy is available, or {\tt /dev/urandom},
which does not block but is not guaranteed to provide full entropy. A
web application may want to download entropy from the back-end to the
front-end if a source of full entropy is available on the back-end.
The parameter {\tt nonce} is also expected to be a bit array, but it is optional.
(The use of this input is motivated in Section 8.6.7 of \cite{SP800-90Ar1}.) If no value is
supplied, the function uses a value derived from {\tt Data.getTime()}.
The function instantiates the DRBG by storing its initial internal
state in three properties of {\tt rbgStateStorage}, {\tt
rbgStateStorage.pjclRBG128\_v}, {\tt rbgStateStorage.pjclRBG128\_c}
and\\{\tt rbgStateStorage.pjclRBG128\_reseed\_counter}. The function
does not return a value.
\subsubsection{\tt function pjclRBG128Reseed(\\\mbox{}\hspace{.2in}rbgStateStorage, entropy)}
This function reseeds a DRBG based on SHA-256 as specified in Section
10.1.1.3 of \cite{SP800-90Ar1}. No {\tt additional\_input} is used.
The parameter {\tt rbgStateStorage} is expected to be a JavaScript
object or storage object ({\tt localStorage} or {\tt sessionStorage})
containing the internal state of a DRBG in three properties {\tt
rbgStateStorage.pjclRBG128\_v}, {\tt rbgStateStorage.pjclRBG128\_c}
and\\{\tt rbgStateStorage.pjclRBG128\_reseed\_counter}.
As in {\tt pjclRBG128Instantiate}, the parameter {\tt entropy} is
expected to be an array of at least 128 bits, and an exception is thrown otherwise by both the
argument checking and the production versions of the library. The
function updates the internal state of the DRBG at {\tt
rbgStateStorage} and returns no value.
\subsubsection{\tt function pjclRBG128InstantiateOrReseed(\\\mbox{}\hspace{.2in}rbgStateStorage,entropy,nonce)}
This is a convenience function that uses {\tt entropy} and {\tt nonce}
to initialize a DRBG at {\tt rbgStateStorage} unless one already
exists there, in which case the existing DRBG is reseeded using both
{\tt entropy} and {\tt nonce} as entropy inputs. The parameters entropy and nonce are expected to be bit arrays.
\subsubsection{function pjclRBG128Gen(rbgStateStorage, bitLength)}
This function generates bits from a DRBG based on SHA-256 as
specicified in Section 10.1.1.4 of \cite{SP800-90Ar1}.
The parameter {\tt rbgStateStorage} is expected to be a JavaScript
object or storage object ({\tt localStorage} or {\tt sessionStorage})
containing the internal state of a DRBG in three properties
{\tt rbgStateStorage.pjclRBG128\_v}, {\tt rbgStateStorage.pjclRBG128\_c} and\\{\tt rbgStateStorage.pjclRBG128\_reseed\_counter}.
The {\tt bitLength} parameter is expected to be a JavaScript number
specifying the number of bits to be returned, whose mathematical value must be a positive integer no greater
than $2^{19}$ according to Table~2 of \cite{SP800-90Ar1}. The
function throws an exception otherwise.
The function returns a bit array with the specified number of bits.
\subsubsection{\tt function pjclCryptoRNG128(rbgStateStorage,a,b)}
The parameter {\tt rbgStateStorage} is expected to be a JavaScript
object or storage object ({\tt localStorage} or {\tt sessionStorage})
containing the internal state of a DRBG in three properties {\tt
rbgStateStorage.pjclRBG128\_v}, {\tt rbgStateStorage.pjclRBG128\_c}
and\\{\tt rbgStateStorage.pjclRBG128\_reseed\_counter}. The parameters
{\tt a} and {\tt b} are expected to be big integers with mathematical
values $a$ and $b$ such that $0 \leq a < b$. The function returns a
cryptographically random big integer whose mathematical value $x$ is
uniformly distributed in the range $a \leq x < b$. To ensure a
quasi-uniform distribution, the function uses the ``extra random
bits'' method used in Section B.1.1 of \cite{DSS-4} for key pair
generation and in Section B.2.1 for per-message secret number
generation.
\subsubsection{\tt function pjclRBG192Instantiate(\\\mbox{}\hspace{.2in}rbgStateStorage,entropy,nonce)\\function pjclRBG192Reseed(\\\mbox{}\hspace{.2in}rbgStateStorage,entropy)\\function pjclRBG192InstantiateOrReseed(\\\mbox{}\hspace{.2in}rbgStateStorage,entropy,nonce)\\function pjclRBG192Gen(\\\mbox{}\hspace{.2in}rbgStateStorage,bitLength)\\function pjclCryptoRNG192(rbgStateStorage,a,b)}
The functions {\tt pjclRBG192*} and {\tt pjclCryptoRNG192} are like
the corresponding functions {\tt pjclRBG128*} and {\tt
pjclCryptoRNG128} except that they use SHA-384 as the hash function
and accordingly provide 192 bits of security strength. The value of
the {\tt entropy} parameter in {\tt pjclRBG192Instantiate}, {\tt
pjclRBG192Reseed} and {\tt pjclRBG192InstantiateOrReseed} must be a
bit array of length at least 192.
\subsection{Primality testing}
\subsubsection{\tt function pjclIsPrime(n,t)\\function pjclMillerRabin(n,t)}
The function {\tt pjclIsPrime} performs a probabilistic primality test
on a big integer {\tt n}, using the Miller-Rabin test if the big
integer has more than one limb, and checking for divisibility by a
12-bit prime if it has only one limb. This is one place in the
library where the number of bits per limb is hardwired.
The function
{\tt pjclMillerRabin}, which is called by {\tt pjclIsPrime}, implements the Miller-Rabin probabilistic
primality test as described in Algorithm 4.42 of
\cite{Menezes97handbookof} with a number of repetitions specified by the parameter {\tt t}.
In
cryptographic applications the number to be tested is usually
cryptographically random, but the potential witnesses to compositness only need to be
statistically random, so the function {\tt pjclIsPrime} uses the
function {\tt pjclStatisticalRNG} to generate witnesses.
In both functions the parameter {\tt n} is expected to be a nonnegative integer and the parameter {\tt t} a JavaScript number whose mathematical value is a positive integer. In {\tt pjclMillerRabin}
the parameter {\tt n} must have two limbs and be odd.
\subsection{DSA}
This version of the library provides an implementation of DSA
\cite{DSS-4} with only one security strength, 128 bits, which requires
a 256-bit private key and a 3072-bit public key according to Table~2
of \cite{sp800-57part1rev4}. Higher security strengths are deemed
impractical by NIST according to Table~2.
\subsubsection{\tt function pjclDSAGenPQ(domainParameterSeed)\\function pjclDSAGenPQ()}
The function {\tt pjclDSAGenPQ} generates probable primes $p$ and $q$
of bit lengths $L = 3072$ and $N = 256$ respectively, with $q$
dividing $p-1$, as specified in Section A.1.1.2 of \cite{DSS-4} using
SHA-256 as the hash function, Miller-Rabin with 64 repetitions as the
probabilistic primality test, and a seed length of 256 bits.
The algorithm of A.1.1.2 is non-deterministic: a domain parameter seed
with the specified seed length is chosen at step 5, then a
deterministic attempt at generating a probable prime $q$ is made,
going back to step 5 if the attempt fails. Once an attempt at
generating $q$ succeeds, a deterministic attempt at generating a
probable prime $p$ such that $q$ divides $p-1$ is made, going back to
step 5 if the attempt fails. The algorithm returns $p$, $q$, the last
domain parameter seed chosen at step 5 and a counter. The returned
values can be used in algorithm A.1.1.3 to validate prime numbers $p$
and $q$ if generated by a non-trusted party. We may provide an
implementation of algorithm A.1.1.3 in a future verion of the library.
The optional parameter {\tt domainParameterSeed} is expected to be a bit array,
which can be chosen arbitrarily and is used as the initial domain
parameter seed of step 5 of the NIST algorithm. If not supplied, a bit array with 256 statistically random bits is used.
The function returns
an object with properties {\tt p}, {\tt q}, {\tt domainParameterSeed}
and {\tt counter} corresponding to the values returned by Algorithm
A.1.1.2, {\tt p} and {\tt q} being big integers, {\tt
domainParameterSeed} being a bit array, and {\tt counter} being a
JavaScript number.
\subsubsection{\tt function pjclDSAGenG(\\\mbox{}\hspace{.2in}p,q,domainParameterSeed,index)}
The function {\tt pjclDSAGenG} produces a big integer whose value is
the generator $g$ as specified in Section A.2.3 of \cite{DSS-4} using
SHA-256 as the hash function. The values of the parameters {\tt p},
{\tt q}, {\tt domainParameterSeed} must be the corresponding
properties of the object returned by {\tt pjclDSAGenPQ}, and {\tt
index} must be a bit array of length 8, which may be chosen
arbitrarily. With argument checking, the function verifies that {\tt
p} and {\tt q} are well-formed nonnegative big integers with bit lengths are
3072 and 256 and {\tt domainParameterSeed} and {\tt index} are bit
arrays of lengths 256 and 8 respectively.
\subsubsection{\tt function pjclDSAGenPQG(\\\mbox{}\hspace{.2in}domainParameterSeed,index)}
Calls {\tt pjclDSAGenPQ} then {\tt pjclDSAGenG}. Returns an object with
the properties {\tt p}, {\tt q}, {\tt domainParameterSeed} and {\tt
counter} returned by {\tt pjclDSAGenPQ}, and a property {\tt g}
whose value is the big integer returned by {\tt pjclDSAGenG}.
\subsubsection{\tt function pjclDSAGenKeyPair(rbgStateStorage,p,q,g)\\function pjclDSAGenKeyPair(rbgStateStorage)}
Generates a DSA key pair $(x,y)$ with 128 bits of security strength,
i.e.\ with a 256-bit private key $x$ and a 3072-bit public key $y$, as
specified in Section B.1.1 of \cite{DSS-4}.
The parameter {\tt rbgStateStorage} is expected to be a JavaScript
object or storage object ({\tt localStorage} or {\tt sessionStorage})
containing the internal state of a DRBG in three properties {\tt
rbgStateStorage.pjclRBG128\_v}, {\tt rbgStateStorage.pjclRBG128\_c}
and\\{\tt rbgStateStorage.pjclRBG128\_reseed\_counter}.
The optional parameters {\tt p}, {\tt q} and {\tt g} are expected to
be domain parameters such as returned by {\tt pjclDSAGenPQG}. With
argument checking, besides verifying that {\tt p}, {\tt q} and {\tt g}
are well-formed nonnegative big integers, the function verifies that the bit
lengths of {\tt p} and {\tt q} are 3072 and 256 respectively.
The function returns an object with properties {\tt x} and {\tt y},
whose values are the big integer representations of $x$ and $y$.
\subsubsection{\tt function pjclDSASign(rbgStateStorage,p,q,g,x,msg)}
The function {\tt pjclDSASign} computes a DSA signature
with 128 bits of security strength on the parameter {\tt msg}
as described in Section 4.6 of \cite{DSS-4}.
The internal variable {\tt k} is the per-message secret, or nonce,
whose value $k$ is generated cryptographically at random
using {\tt pjclCryptoRNG128}, which provides 128-bits of security
strength assuming that it is seeded with 128 bits of entropy.
The function should not be modified to take $k$ as an argument;
$k$ should not be precomputed, because that may facilitate a timing attack,
as discusssed in Section~\ref{s:side-channel}; and $k$ must
be treated as a secret, because the private key can be computed from
$k$ and the signature.
The parameter {\tt rbgStateStorage} is expected to be a JavaScript
object or storage object ({\tt localStorage} or {\tt sessionStorage})
containing the internal state of a DRBG in three properties {\tt
rbgStateStorage.pjclRBG128\_v}, {\tt rbgStateStorage.pjclRBG128\_c}
and\\{\tt rbgStateStorage.pjclRBG128\_reseed\_counter}. The parameters
{\tt p}, {\tt q} and {\tt g} are expected to be nonnegative big integers,
representing the domain parameters as generated by {\tt
pjclDSAGenPQG}. The parameter {\tt x} is expected to be a big
integer, representing the private key, as generated by {\tt pjclDSAGenKeyPair}.
The parameter {\tt msg} is expected to be a bit array, which is hashed using SHA-256.
The function returns an object with properties {\tt r} and {\tt s}
whose values are big integer representations of the components of the
signature $(r,s)$.
\subsubsection{\tt function pjclDSAVerify(p,q,g,y,msg,r,s)}
The function {\tt pjclDSAVerify} verifies a signature as described in
Section 4.7 of \cite{DSS-4}. The parameters {\tt p}, {\tt q} and {\tt
g} are expected to be big integers, representing the domain
parameters. The parameter {\tt y} is expected to be a big integer,
representing the public key.
The parameter {\tt msg} is expected to be
a bit array representing the message. The
parameters {\tt r} and {\tt s} are expected to be big integers,
representing the components of the signature. The function returns
{\tt true} if verification succeeds, {\tt false otherwise}.
\subsection{Elliptic curves}
\subsubsection{NIST curves}
The Digital Signature Standard of NIST specifies five elliptic curves
over prime fields \cite[\S~D.2]{DSS-4}: P-192, P-224, P-256, P-384 and
P-521. Descriptions of these curves can also be found in
\cite[\S 10.2]{ECDSACerticom}, \cite{NISTCurves} and \cite{X9.62}. This version of
the library implements ECDSA on curves P-256 and P-384. Other NIST
and non-NIST curves may be supported in future versions.
The term ``Weierstrass equation'' is defined with various degrees of
generality. Here we shall use the term to refer to an equation of the
form $y^2 = x^3 + ax + b$ over a field $F$, where $a,b\in F$ are
constants such that $4a^3+27b^2\not=0$. We shall refer to a curve
with a Weierstrass equation as a Weierstrass curve. Here we shall
only be concerned with Weierstrass curves over a prime field
$F=\mathbb{F}_p$.
NIST curves over prime fields have Weierstrass equations where the
coefficient $a$ is $-3$. An explanation of the motivation for
choosing $a=-3$ can be found in
\cite[\S~2.6.2]{washington2003elliptic}. This version of the library
hardcodes the fact that $a = -3$.
The domain parameters for ECDSA on a Weierstrass curve over a prime
field $\mathbb{F}_p$ include, in addition to $p$, $a$, and $b$, the
choice of a base point $G$. The base point is a point of prime order
$n$, i.e.\ a point that generates a subgroup of order $n$ of the group
$E(\mathbb{F}_p)$ of points of the curve. By Lagrange's theorem, $n$
divides the order $\#E(\mathbb{F}_p)$ of (the group of points of) the
curve. The quotient $h = \#E(\mathbb{F}_p) / n$, called the cofactor,
is another domain parameter. In all the NIST curves over prime fields
the order of the curve is a prime number, and therefore the cofactor
is 1.
NIST \cite[\S~D.2]{DSS-4} suggests taking advantage of the fact that
the primes $p$ in the five curves over prime fields are Generalized
Mersenne Primes whose exponents are multiples of 32 in order to
improve the performance of reduction modulo $p$. However the
suggested method is only suitable for big integer representations with
32-bit limbs. But those primes are also Pseudo-Mersenne Primes
(see Section~\ref{s:pseudo-mersenne}) and
reduction modulo a Pseudo-Mersenne prime can be performed using
Algorithm 14.47 of \cite{Menezes97handbookof} with about the same
performance improvement \cite{Taschwer2001}. This is what the library
does.
\subsubsection{Affine vs.\ projective vs. Jacobian coordinates}
(This section can be skipped without loss of continuity.)
An elliptic curve has a ``point at infinity'' that cannot be
represented in affine coordinates, but can be represented in
projective coordinates or, preferably for performance reasons, in
Jacobian coordinates.
A point with affine coordinates $(X,Y)$ in a two-dimensional space over a field $F$ has projective
coordinates $(x,y,z)$ such that $z\not=0$, $x=Xz$ and $y=Yz$, which are
the coordinates in the three-dimensional space of the points of the
line containing the origin and the point $(X,Y,1)$, excluding the
origin. On the other hand the projective coordinates of a point at
infinity are the coordinates of the points of a line that goes through
the origin and lies in the plane $z=0$, again not including the origin
itself, i.e.\ there are the triples $(x,y,z)$ such that $z\not=0$ and
$ax+by=0$ for some $a,b\in F$ not both equal to zero.
A line with equation $aX+bY+c=0$ in affine coordinates has equation
$a\frac{x}{z}+b\frac{y}{z}+c=0, z\not=0$ in projective coordinates,
which becomes $ax+by+cz=0$ when the point at infinity of the line is
included. The projective coordinates of the point at infinity are
obtained by making $z=0$ but $x,y\not=0$ in the equation, i.e.\ they
are the triples $(x,y,0)$ other than the origin $(0,0,0)$
such that $ax+by=0$.
An elliptic curve with affine equation $Y^2 = X^3 + aX + b$ has a
projective equation $\frac{y^2}{z^2} = \frac{x^3}{z^3} + a\frac{x}{z}
+ b$, $z\not=0$, which becomes $y^2z = x^3 + axz^2 + bz^3$ when
completed with the point at infinity. The projective coordinates of
the point at infinity of the ellipical curve are obtained by making
$z=0$ but $x,y\not=0$ in the equation, i.e.\ they are the triples
$(x,y,0)$ other than $(0,0,0)$ such that $x^3=0$, which implies $x=0$.
A point with affine coordinates $(X,Y)$ has Jacobian coordinates
$(x,y,z)$ such that $z\not=0$, $x=Xz^2$ and $y=Yz^3$, while a point at
infinity in Jacobian space has the set of coordinates $(x,y,z)$ such that $z\not=0$ and
$ax^3+by^2=0$ for some $a,b\in F$ not both equal to zero.
An elliptic curve with affine equation $Y^2=X^3+aX+b$ has a
projective equation $\frac{y^2}{z^6} = \frac{x^3}{z^6} +
a\frac{x}{z^2} + b$, $z\not=0$, which becomes $y^2 = x^3 + axz^4 + bz^6$ when
completed with the point at infinity. The Jacobian coordinates of the
point at infinity of the elliptical curve are obtained by making
$z=0$ but $x,y\not=0$ in the equation, i.e.\ they are the triples
$(x,y,0)$ other than $(0,0,0)$ such that $y^2 = x^3$.
\subsubsection{Jacobian representation of a point}
In the library, a point of an elliptic curve is represented in
Jacobian coordinates, as a JavaScript object with three properties
{\tt x}, {\tt y} and {\tt z} whose values are big integers
representing the Jacobian coordinates $x$, $y$ and $z$ of the point.
We shall refer to such an object as {\em a Jacobian representation\/}
of the point.
\subsubsection{Affine representation as a special case of Jacobian representation}
\label{s:affine}
If $(x,y,1)$ are Jacobian coordinates of a point $P$, then $(x,y)$ are
its affine coordinates. In the library, the {\em affine
representation\/} of a finite point is a special case of a Jacobian
representation where the value of the {\tt z} property is the big
integer representation of 1, i.e.\ [1]. The function {\tt
pjclJacobian2Affine} produces that affine representation.
\subsubsection{Jacobian-affine optimization of point addition}
\label{s:jacobian-affine-optimization}
The function {\tt pjclPointAdd} takes as arguments two Jacobian
representations, but checks if the second one is an affine
representation and optimizes that special case.
\subsubsection{\tt function pjclModSpecial(x,t,xc,m)}
The function {\tt pjclModSpecial} computes $x \bmod m$, where
$m=2^t-c$, using Algorithm 14.47 of \cite{Menezes97handbookof}, which
is applicable when $0 < c < 2^{t-1}$ and efficient when $c$ is ``small''
compared to $2^{t-1}$, which we shall write $c \ll 2^{t-1}$.
The parameter {\tt x} is expected to be a nonnegative big integer representing the
integer $x$ to be reduced. The parameter {\tt t} is
expected to be a JavaScript number representing the exponent $t$, which must be a positive integer.
The parameter {\tt xc}, read ``times c'', is expected to be a function
that takes as its only argument a positive big integer and returns a
big integer representing its product by $c$; different such functions can be
written and optimized for different values of $c$. The parameter {\tt m} is
expected to be a positive big integer representing the modulus $m = 2^t - c$.
The function returns a big integer representing $x \bmod m$.
In this version of the library, the function {\tt pjclModSpecial} is
used to compute reductions modulo Pseudo-Mersenne primes. Note,
however, that {\tt pjclModSpecial} can also be used in cases where $m$
is not a prime.
\subsubsection{Pseudo-Mersenne representation of a prime}
\label{s:pseudo-mersenne}
A Pseudo-Mersenne Prime is a prime of the form $p=2^t-c$ with
$0 < c \ll 2^{t-1}$. Modular reduction by such a prime $p$ can thus be sped up
by using {\tt pjclModSpecial} instead of {\tt pjclMod}.
A {\em Pseudo-Mersenne representation\/} of $p$ is
a triple of JavaScript values consisting of the JavaScript number
representing $t$, a function that multiplies a big integer by $c$, and
the big integer representation of $p$ suitable to be passed as second, third and fourth arguments to
{\tt pjclModSpecial}.
\subsubsection{\tt var pjclCurve\_P256}
The value of the global variable {\tt pjclCurve\_P256} is an
object whose properties describe the ECDSA domain parameters for NIST
curve P-256, which is the curve with equation
$$
y^2 = x^3 - 3x^2 + b
$$
over prime field $\mathbb{F}_p$, where\footnote{A typo in the value of $p$ has been
fixed after release. The error was only in the documentation. The code was correct.}
$$
p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1
$$
and $b$ has the big integer representation shown in the code as the
value of the property {\tt b}. The prime $p$ can be written $p=2^t-c$
with
$$
c = 2^{224} - 2^{192} - 2^{96} + 1
$$
The object has the following properties and methods:
\begin{itemize}
\item Three properties {\tt t}, {\tt xc} and {\tt p} comprising the
Pseudo-Mersenne representation of the prime $p$.
\item A property {\tt b} whose value is a big integer representing the
coefficient $b$ of the curve.
\item A property {\tt n} whose value is a big integer representing
the order $n$ of the curve, which is also the order of the base
point, since the cofactor is 1.
\item A property {\tt G} whose value is the affine representation of
the base point of the curve. (Recall that, in the library, an affine representation
is a special case of a Jacobian representation, as explained in Section~\ref{s:affine}.)
\end{itemize}
\subsubsection{\tt var pjclCurve\_P384}
The value of the global variable {\tt pjclCurve\_P384} is an
object whose properties describe the ECDSA domain parameters for NIST
curve P-384, which is the curve with equation
$$
y^2 = x^3 - 3x^2 + b
$$
over prime field $\mathbb{F}_p$, where
$$
p = 2^{384} - 2^{128} - 2^{96} + 2^{32} - 1
$$
and $b$ has the big integer presentation shown in the code as the
value of the property {\tt b}. The prime $p$ can be written $p=2^t-c$
with
$$
c = 2^{128} + 2^{96} - 2^{32} + 1
$$
The object has properties and methods like those of {\tt
pjclCurve\_P256}.
\subsubsection{\tt function pjclJacobian2Affine(P,curve)}
The parameter {\tt P} is expected to be a Jacobian representation of
a finite point $P$ over a prime field $\mathbb{F}_p$. The
parameter {\tt curve} is expected to be an object with properties {\tt t}, {\tt xc} and {\tt p} that comprise a Pseudo-Mersenne representation of the prime number $p$,
such as one of the curve objects {\tt pjclCurve\_P256} or {\tt pjclCurve\_P384}.
The function returns the affine representation of $P$.
(Recall that, in the library, an affine representation
is a special case of a Jacobian representation, as explained in Section~\ref{s:affine}.)
\subsubsection{\tt function pjclPointAdd(P1,P2,curve)}
The parameters {\tt P1} and {\tt P2} are expected to be Jacobian
representations of two points $P_1$ and $P_2$ of a Weierstrass curve
over a prime field $\mathbb{F}_p$, and the parameter {\tt curve} is expected to be an object representing the curve. There are two objects representing curves in the current version of the library: {\tt pjclCurve\_P256} and {\tt pjclCurve\_P384}.
If one of the points $P_1$, $P_2$ is the point at infinity of the curve, the function represents the value of the parameter representing the other point.
Otherwise,
if $P_1\not=P_2$, the function returns a Jacobian representation of
the sum $P_1+P_2$ and
if $P_1=P_2$ the function calls {\tt pjclPointDouble(P1,curve)} and
returns the result.
The function optimizes the case where $P_2$ is given by an affine
representation. (Recall that, in the library, an affine representation
is a special case of a Jacobian representation, as explained in Section~\ref{s:affine}.) This is useful for scalar multiplication,
as explained below.
\subsubsection{\tt function pjclPointDouble(P,curve)}
The parameter {\tt P} is expected to be the Jacobian representation of
a point $P$ of a Weierstrass curve with coefficient $a=-3$, and the parameter {\tt curve} is expected to be an object representing the curve. There are two objects representing curves in the current version of the library, {\tt pjclCurve\_P256} and {\tt pjclCurve\_P384}, both representing Weierstrass curves with coefficient $a=-3$.
The function returns a Jacobian representation of the point
$2P=P+P$.
\subsubsection{\tt function pjclScalarMult(P,k,curve)}
\label{s:scalar-mult}
The parameter {\tt P} is expected to be a Jacobian representation of
a point $P$ of a Weierstrass curve with coefficient $a=-3$,
the parameter {\tt k} is expected to be a big
integer whose mathematical value is a nonnegative integer $k$, and the parameter {\tt curve} is expected to be an object representing the curve. There are two objects representing curves in the current version of the library, {\tt pjclCurve\_P256} and {\tt pjclCurve\_P384}, both representing Weierstrass curves with coefficient $a=-3$.
The function returns a Jacobian representation of the point
$kP=\underbrace{P+\cdots+P}_k$, calculated using the sliding window
algorithm implemented by {\tt pjclExp},\footnote{Recall that ``scalar multiplication'' and ``exponentiation'' are alternative names given
to the same external operation in a monoid, the term ``scalar multiplication''
being used when the operation is called ``addition'' while the term
``exponentiation is used when the operation is called
``multiplication''.} after calling {\tt pjclPreExp} to perform the precomputation.
The call to {\tt pjclPreExp} is followed by a loop that calls {\tt pjclJacobian2Affine} on
all the precomputed values, so that {\tt pjclPointAdd} can take advantage of the
Jacobian-affine optimization mentioned above in Section~\ref{s:jacobian-affine-optimization}
when used in {\tt pjclExp}.
In a future version of the library we plan to use NAF to further optimize scalar multiplication.
Different code will then be used for modular exponentiation and scalar multiplication.
\subsubsection
[\tt function pjclScalarMult2(\\\mbox{}\hspace{.2in}P1,P2,u1,u2,curve)]
{\tt function pjclScalarMult2(P1,P2,u1,u2,curve)}
The function pjclScalarMult2(P1,P2,u1,u2,curve) produces the
same result as
\begin{verbatim}
pjclPointAdd(pjclScalarMult(P1,u1,curve),pjclScalarMult(P2,u2,curve))
\end{verbatim}
but substantially faster, by combining the point doublings of the two
exponentiations. It calls {\tt pjclPreExp2} and {\tt pjclExp2}, and,
like {\tt pjclScalarMult}, calls {\tt pjclJacobian2Affine} on the values precomputed
by {\tt pjclPreExp2} before using them in {\tt pjclExp2}.
\subsection{ECDSA}
\subsubsection{\tt function pjclECDSA128GenKeyPair(rbgStateStorage,curve) }
This function generates an ECDSA key pair with 128 bits of security strength. It uses the DRBG based on SHA-256 described at the beginning of Section \ref{cryptorandom},
which provides that strength.
The parameter {\tt rbgStateStorage} is expected to be an object containing the state of the DRBG.
The parameter {\tt curve} is expected to be an object representing a Weierstrass curve with coefficient $a=3$ providing that security strength, i.e., in this version of the library, {\tt pjclCurve\_P256}. The function returns an object containing two properties {\tt d} and {\tt Q} representing the private and public keys respectively. The value of the property {\tt d} is a big integer whose mathematical value $d$ is in the range $1 \leq d < n$, where $n$ is the order of the curve, i.e.\ the mathematical value of {\tt curve.n}. The value of the property {\tt Q}
is a Jacobian representation of the point $Q=dG$ where $G$ is the base point of the curve, i.e.\ the value of {\tt curve.G}.
\subsubsection{\tt function pjclECDSA192GenKeyPair(rbgStateStorage,curve) }
This function generates an ECDSA key pair with 192 bits of security strength, using the DRBG based on SHA-384 described at the beginning of Section \ref{cryptorandom}. It should be passed a curve that provides the same security strength, i.e., {\tt pjclCurve\_P384}. It is otherwise like {\tt pjclECDSA128GenKeyPair}.
\subsubsection{\tt function pjclECDSAValidatePublicKey(Q,curve)}
The function {\tt pjclECDSAValidatePublicKey(Q,curve)} implements
Algorithm~6 of \cite{ECDSACerticom} for ECDSA public key validation
after verifying that {\tt Q} is finite and converting it to its affine representation,
except that it omits the last step of the algorithm, which is unnecessary if the
cofactor is 1, since in that case (with the notations of Algorithm~6)
$n = \#E(\mathbb{F}_p)$, and
therefore $n\mathcal{Q} = \mathcal{O}$. This hardcodes the fact that the cofactor is 1
in NIST curves, and will change in the future if the library supports curves with other
cofactors.
\subsubsection{\tt function pjclECDSASign(curve,d,h,k)}
THIS IS NOT AN API FUNCTION. DO NOT USE IT IN YOUR CODE.
This function computes an ECDSA signature on the hash {\tt h} of a message, using a nonce {\tt k} passed as an argument. It is used by pjclECDSA128Sign and pjclECDSA192Sign. Use one of those functions instead. Using this function with a value of {\tt h} that is not a cryptographic hash of a message would not be secure, because an ECDSA signature is not secure against existential forgery if the message is not hashed. Using this function with a precomputed value of $k$ might facilitate a timing attack: see Section~\ref{s:side-channel}.
\subsubsection{\tt function pjclECDSA128Sign(rbgStateStorage,curve,d,msg)}
This function computes an ECDSA signature with 128 bits of security strength, using a DRBG of that strength to generate the nonce. The parameter {\tt rbgStateStorage}
is expected to be an object containing the internal state of the DRBG. The
parameter {\tt curve} is expected to be an object representing a
Weiesrstrass curve with coefficient $a=-3$ that provides
128 bits of security strength, i.e., in this version of the library, {\tt pjclCurve\_P256}.
The parameter {\tt d} is expected to be a nonnegative big integer whose value is the private key. The parameter {\tt msg} is the message to be signed encoded as a bit array. The function returns the signature as an object with two properties {\tt r} and {\tt s} whose values are big integers.
\subsubsection{\tt function pjclECDSA192Sign(rbgStateStorage,curve,d,msg)}
This function computes an ECDSA signature with 192 bits of security strength. It must be passed a curve of that strength. The other parameters and the result are as in {\tt pjclECDSA128Sign}.
\subsubsection{\tt function pjclECDSAVerify(curve,Q,msg,r,s)}
THIS IS NOT AN API FUNCTION. DO NOT USE IN YOUR OWN CODE. Use {\tt pjclECDSA128Verify} or {\tt pjclECDSA192Verify} instead.
\subsubsection{\tt function pjclECDSA128Verify(curve,Q,msg,r,s)}
This function verifies an ECDSA signature with 128 bits of security strength computed using the curve referenced by the first parameter, returning {\tt true} if successful or {\tt false} otherwise. In the current version of the library there is one object representing a curve with 128 bits of security strength, {\tt pjclCurve\_P256},
which you may use as the first argument.
The parameter {\tt Q} is the public key. The parameter {\tt msg} is the signed message, encoded as a bit array. The parameters {\tt r} and {\tt s} are the properties of the signature object, as returned by {\tt pjclECDSA128Sign} or {\tt pjclECDSA192Sign}.
\subsubsection{\tt function pjclECDSA192Verify(curve,Q,msg,r,s)}
This function verifies an ECDSA signature with 192 bits of security strength computed using the curve referenced by the first parameter, returning {\tt true} if successful or {\tt false} otherwise. In the current version of the library there is one object representing a curve with 192 bits of security strength, {\tt pjclCurve\_P384},
which you may use as the first argument.
The parameter {\tt Q} is the public key. The parameter {\tt msg} is the signed message, encoded as a bit array. The parameters {\tt r} and {\tt s} are the properties of the signature object, as returned by {\tt pjclECDSA192Sign} or {\tt pjclECDSA192Sign}.
\section{Estimation of the Karatsuba thresholds}
\label{s:karatsuba-thresholds}
The directory {\tt KaratsubaThresholds} contains a facility for estimating the optimal Karatsuba thresholds for multiplication and squaring on a target browser in a particular machine. JavaScript does not provide a means of measuring the number of clock cycles used in a computation, so the estimates are computed by measuring elapsed time, using the {\tt performance.now()} method of the User Timing API. Results may be highly inaccurate if there is other activity on the machine where the browser is running.
To compute the optimal thresholds, simply visit the file\\{\tt KaratsubaThresholds.html} found in the {\tt KaratsubaThresholds} directory with the target browser. You may place the {\tt KaratsubaThresholds} directory in a server and access the file using an {\tt http} or {\tt https} URL, or in the same machine where the browser is running and access the file using a {\tt file} URL or open the file with the browser. However the facility cannot be used with Chrome if the file is local, and it cannot be used at all with Safari or Internet Explorer because those browsers do not support the User Timing API in web workers. There are no problems with Firefox or Edge. You must place the file {\tt pjcl.js} containing the PJCL library in the parent directory of the {\tt KaratsubaThresholds} directory.
The computation of the optimal thresholds is performed in the background by a web worker, which is launched automatically as soon as you visit the file, It takes a couple of minutes and may be monitored on the browser console. You may want to repeat the computation several times, discard outliers that might be caused by other activity on the machine, and average the retained results.
Once computed, the optimal thresholds should be assigned to the global variables {\tt pjclKaratsubaThresholdMult} and {\tt pjclKaratsubaThresholdSqr}, overriding the defaults. The default thresholds should be adequate for ordinary laptops. They may be too high for some smartphones, and too low for machines with very fast floating-point multiplication. Karatsuba is unlikely to be useful for elliptic curve computations.
\section{Performance testing}
\subsection{Testing the performance of modular exponentiation}
\label{s:modexpperf}
The directory {\tt ModExpPerfTesting} contains files that allow you to
test the performance of modular exponentiation on a browser using
long multiplication or Karatsuba multiplication, and to compare it to
the performance of SJCL.
For the performance test, simply visit the file {\tt ModExpPerfTest.html} found in the {\tt pjcl/ModExpPerfTesting} directory with a browser, and follow the instructions in the file. As when measuring the optimal Karatsuba thresholds, you may place the directory in a server and access the file using an {\tt http} or {\tt https} URL, or in the same machine where the browser is running and access the file using a {\tt file} URL or open the file with the browser; but the facility cannot be used with Chrome if the file is local, and it cannot be used at all with Safari or Internet Explorer because those browsers do not support the User Timing API in web workers. There are no problems with Firefox or Edge. You must place the file {\tt pjcl.js} containing the PJCL library in the parent directory of the {\tt ModExpPerfTesting} directory.
For the performance comparison, place in the same directory the
{\tt pjcl} directory found in the PJCL zip archive downloaded from
\url{https://pomcor.com/pjcl/pjcl-090.zip}
and the {\tt sjcl} directory found in the SJCL zip archive downloaded from
\url{https://github.com/bitwiseshiftleft/sjcl}.
(If you are using Windows, be sure to move the {\tt pjcl} and {\tt sjcl}
directories out of the wrapping directories that Windows creates when
unzipping the archives.) The SJCL code used in the comparison is in the
files {\tt sjcl/sjcl.js} and {\tt sjcl/bn/core.js}.
Tables \ref{t:firefox}, \ref{t:chrome} and \ref{t:edge} provide
some measurements that we have made ourselves, using the default
Karatsuba thresholds, 150 limbs = 3600 bits for multiplication
and 175 limbs = 4200 for squaring. The SJCL performance figures have been
obtained with a version of the SJCL library downloaded
on November 15, 2017.
\begin{table}[p]\label{t:firefox}
\begin{center}
\begin{tabular}{|r|r|r|r|r|}\hline
\multicolumn{5}{|l|}{Machine: Surface with Intel Core i5-6300U CPU @ 2.40 GHz 2.50 GHz}\\
\multicolumn{5}{|l|}{Browser: Firefox 56.0.2 (64-bit)}\\\hline
Modulus & Exponent & Long & Karatsuba & SJCL\\
and base & & multiplication & multiplication & \\
& & and squaring & and squaring & \\\hline
3072 bits & 256 bits & 22 ms & 22 ms & 186 ms \\
15360 bits & 512 bits & 819 ms & 845 ms & 7559 ms \\\hline
\end{tabular}
\end{center}
\caption{Modular exponentiation performance in Firefox}
\end{table}
\begin{table}[p]\label{t:chrome}
\begin{center}
\begin{tabular}{|r|r|r|r|r|}\hline
\multicolumn{5}{|l|}{Machine: Surface with Intel Core i5-6300U CPU @ 2.40 GHz 2.50 GHz}\\
\multicolumn{5}{|l|}{Browser: Chrome 62.0.3202.89 (64-bit)}\\\hline
Modulus & Exponent & Long & Karatsuba & SJCL\\
and base & & multiplication & multiplication & \\
& & and squaring & and squaring & \\\hline
3072 bits & 256 bits & 25 ms & 27 ms & 170 ms \\
15360 bits & 512 bits & 1098 ms & 1005 ms & 6756 ms \\\hline
\end{tabular}
\end{center}
\caption{Modular exponentiation performance in Chrome}
\end{table}
\begin{table}[p]\label{t:edge}
\begin{center}
\begin{tabular}{|r|r|r|r|r|}\hline
\multicolumn{5}{|l|}{Machine: Surface with Intel Core i5-6300U CPU @ 2.40 GHz 2.50 GHz}\\
\multicolumn{5}{|l|}{Browser: Edge 41.16299.15.0, EdgeHTML 16.16299}\\\hline
Modulus & Exponent & Long & Karatsuba & SJCL\\
and base & & multiplication & multiplication & \\
& & and squaring & and squaring & \\\hline
3072 bits & 256 bits & 21 ms & 22 ms & 233 ms \\
15360 bits & 512 bits & 811 ms & 763 ms & 7009 ms \\\hline
\end{tabular}
\end{center}
\caption{Modular exponentiation performance in Edge}
\end{table}
\begin{table}[p]\label{t:dsaperf}
\begin{center}
\begin{tabular}{|l|r|r|r|}\hline
&
\multicolumn{1}{c|}{Key pair generation} &
\multicolumn{1}{c|}{Signature} &
\multicolumn{1}{c|}{Verification} \\\hline
Firefox & 21 ms & 21 ms & 26 ms \\
Chrome & 22 ms & 26 ms & 38 ms \\\hline
\end{tabular}
\end{center}
\caption{DSA performance}
\end{table}
\subsection{Testing the performance of DSA}
\label{s:dsaperf}
The directory {\tt DSAPerfTesting} contains files that allow you to
test the performance of DSA key pair generation, signature and verification.
To use this facility, visit the file {\tt DSAPerfTest.html} found in the\\{\tt DSAPerfTesting} directory with a browser, and follow the instructions in the file. As when measuring the optimal Karatsuba thresholds or the performance of modular exponentiation, you may place the directory in a server and access the file using an {\tt http} or {\tt https} URL, or in the same machine where the browser is running and access the file using a {\tt file} URL or open the file with the browser. You must place the file {\tt pjcl.js} containing the PJCL library in the parent directory of the {\tt DSAPerfTesting} directory.
The facility can be used in Firefox, and in Chrome if the directory {\tt DSAPerfTesting} is installed on a remote server. It cannot be used in Chrome if the directory is local because Chrome does not assign a common web origin to local files. It cannot be used in Edge because {\tt crypto.getRandomValues()} is not available in worker context. It cannot be used in Safari or Internet Explorer because those browsers do not support the User Timing API in web workers.
Table \ref{t:dsaperf} shows some measurements that we have made ourselves using Firefox and Chrome on a Windows machine with a processor identified as
Intel Core i5-6300U CPU @ 2.40 GHz 2.50 GHz.
The version of Firefox is 56.0.2 (64-bit) and
the version of Chrome is 62.0.3202.89 (64-bit).
\clearpage
\bibliographystyle{unsrt}
\flushleft
\bibliography{/Users/fcore/Documents/general}
\end{document}