%hide
%latex
\section*{4. Cryptographic Protocols in ECC}
Elliptic curve cryptography (ECC) is a branch of {\it public key cryptography.} Therefore elliptic curve cryptosystems are {\it asymmetric} algorithms, where each user has a pair of cryptographic keys. The {\it public key} is used for encrypting documents or verifying signatures, whereas the {\it private key} is used to decrypt or sign a document. Examples of such algorithms are RSA, ElGamal and the Digital Signature Algorithm (DSA). In comparison, {\it symmetric} algorithms use the same key for encryption and decryption; examples are AES and DES.
Public key cryptosystems can have different objectives. The oldest and most familiar task is {\it encryption} and {\it decryption} of data. Public-key methods can also be used to establish a shared secret, e.g. a secret key to be used in a symmetric algorithm. This process is called {\it key establishment} or {\it key exchange.} {\it Digital signature} algorithms make up a third group. They aim at providing a functionality similar to handwritten signatures.
This chapter gives ECC examples of all three kinds of public key cryptosystems. None of these algorithms were especially designed for elliptic curves. Rather, they originally used modular arithmetic. They were then generalized to arbitrary groups and can be used with elliptic curves, since their security depends on the discrete logarithm problem.
All algorithms presented here have been standardized for elliptic curves. These standards include technical, ECC-specific details such as the generation of secure parameters and methods of defending against known attacks. We do not discuss all of those specifications in full detail, as we are more interested in the general functionality. For a complete description, please consult the relevant websites. Internationally recognized standards are regularly issued by organizations like ANSI, NIST, IEEE and ISO/IEC.
|
%hide
%latex
\subsection*{4.1 Domain Parameters}
Before executing any cryptographic protocol, appropriate domain parameters must be agreed upon. These values are public, they are fixed in advance, they are used for many executions of a protocol, and they may even be shared by a group of entities. In some applications, however, they are specific to each user. They are comprised of:
\begin{itemize}
\item The cardinality $q$ of the underlying field $\mathbb{F}_q.$ As mentioned before, $q$ is usually a prime or a power of $2.$
\item Two coefficients $a,b$ that define the equation of the elliptic curve $E$ over $\mathbb{F}_q.$
\item The base point $P \in E(\mathbb{F}_q).$
\item The order $n$ of $P.$
\item The cofactor $h = \frac{\# E(\mathbb{F}_q)}{n}.$
\end{itemize}
These parameters must satisfy certain security constraints, in particular, they should be chosen such that the ECDLP is resistant to all known attacks. We will discuss the generation of ``secure'' parameters in Chapter \nolinebreak 5.
Note that generating these parameters takes a substantial amount of computation, as the numbers are very large (we currently require $n > 2^{160}$) and some of the tasks to be performed (like finding the group order $\# E(\mathbb{F}_q)$) are computationally expensive. This is not a problem though, since parameter generation does not have to be performed very often, and it can be done in advance.
For the rest of this chapter, let $D = (q,a,b,P,n,h)$ denote the domain parameters of an elliptic curve cryptosystem as defined above.
|
%hide
%latex
\subsection*{4.2 Key Pair Generation}
In order to receive encrypted messages or generate digital signatures, a user must generate a {\it key pair,} i.e. a private and corresponding public key. Each elliptic curve key pair is associated with a particular set $D$ of domain parameters. The private key is a randomly selected number $d.$ The corresponding public key is $Q = dP,$ a point in the group $\langle P \rangle$ generated by $P.$
\medskip \noindent
{\bf Key pair generation.}\\
{\sc Input:} Domain parameters $D = (q,a,b,P,n,h).$
\begin{enumerate}
\item Select $d \in \{1,\ldots,n-1\}.$
\item Compute $Q = dP.$
\end{enumerate}
{\sc Output:} Public key $Q,$ private key $d.$
\medskip \noindent
Observe that the problem of computing a private key $d$ from the public key $Q$ is precisely the ECDLP. Hence it is crucial that the domain parameters be selected so that the ECDLP is intractable. Furthermore, it is important that the number $d$ be chosen {\it uniformly at random}, meaning that no value for $d$ is selected with a larger probability than another. That way an adversary who guesses random private keys cannot gain advantage.
Besides these important rules for selecting good key pairs, which should be observed by the generating side, there are also some checks that the other party (who uses someone else's public key) should perform. Such a process is called {\it (public) key validation} and verifies that a public key possesses certain arithmetic properties. Successful execution prevents many attacks that would otherwise be possible.
|
%hide
%latex
\subsection*{4.3 Key Establishment Protocols}
The purpose of a key establishment protocol is to provide two parties communicating over an open network with a shared secret key, often called {\it session key.} The key may then be used in a symmetric algorithm. This is useful because asymmetric encryption schemes are much slower than their symmetric counterparts. By using public-key methods to exchange symmetric keys, the functionality of public key cryptography is combined with the speed of symmetric cryptography.
We have introduced one such protocol in Chapter 2, the Diffie-Hellman key exchange, and we have already seen how it can be used with arbitrary groups such as elliptic curves. A variant of this protocol, called {\it Elliptic Curve Diffie-Hellman} (ECDH), is included in the ANSI X9.63 standard. It is part of the TLS protocol, a successor of SSL and widely used for secure internet connections, particularly HTTPS.
ECMQV is an elliptic curve version of the MQV key agreement protocol, named after its inventors Menzes, Qu, and Vanstone, and yet again based on the Diffie-Hellman key exchange. It has been standardized in ANSI X9.63, IEEE 1363-2000, and ISO/IEC 15946-3.
Note that the shared secret established in both protocols is originally a group element, i.e. a point on the curve. Some extra work has to be done in order to turn it into a useful session key. Usually, the $x$-coordinate of the point is represented as a binary string and used as input for a {\it cryptographic hash function} such as SHA-1. A cryptographic hash function takes an arbitrary length binary string as input and outputs a fixed length binary string, e.g. 160 bits in the case of SHA-1. It does this in a {\it random} way in the sense that the output cannot be predicted with the knowledge of the input without actually executing the function, in a {\it collision-free} way in the sense that two different inputs are highly likely to produce distinct outputs, and in a {\it one-way} manner in the sense that the output of the function can be efficiently calculated, but inverting the function is computationally infeasible. Such hash functions are fundamental cryptographic primitives and are part of almost all protocols used in practice. In our scenario they are useful for turning the $x$-coordinate of a point into a session key of fixed length. Sometimes, when a session key longer than the output of the hash function is required, the $x$-coordinate is concatenated with a counter and hashed several times, thus yielding a longer session key by concatenation of the subsequent outputs.
|
%hide
%latex
\subsection*{4.4 Public-Key Encryption Protocols}
Asymmetric encryption schemes are used to provide confidentiality in communication over an insecure network. The most common elliptic curve encryption algorithm is the {\it Elliptic Curve Integrated Encryption Scheme} (ECIES). It is an ECC version of the DLP-based ElGamal encryption scheme, which is again based on Diffie-Hellman. ECIES is standardized in the ANSI X9.63, ISO/IEC 15946-3, and IEEE 1363-2000 standards.
It is a common misunderstanding that public-key encryption schemes are actually used to encrypt blocks of data. First of all, they are much too slow to encrypt large amounts of data. Secondly, ElGamal requires the ``message'' to be a group element. When we're using elliptic curves as the underlying group, we'd have to first convert the given message to a point on an elliptic curve, which is a non-trivial task. In reality, ECIES is a hybrid encryption scheme in that it consists of two steps: It first uses public-key methods (i.e. ElGamal) to exchange a shared secret, which is a point on an elliptic curve. It then uses a key derivation function to map the secret to a session key, and the symmetric algorithm AES to actually encrypt the data. This is why there are not many ECC encryption protocols, and the ones there are usually not used in practice. It is much easier to directly combine ECDH with AES instead of using protocols like ECIES.
|
%hide
%latex
\subsection*{4.5 Digital Signature Schemes}
Digital signatures have a wide range of applications in cryptography. Some types of digital signatures are simply used for authentication purposes (a ``proof of origin'' functionality), whereas other types may be used as the digital counterparts to handwritten signatures and provide several additional properties, like data integrity (nobody can change a document after it has been signed) and non-repudiation (you can't say you haven't signed a document if you have). Similar to RSA, a discrete logarithm based digital signature scheme can be easily derived from ElGamal encryption. A more sophisticated version of this simple protocol is the widely used {\it Digital Signature Algorithm} (DSA), proposed by the U.S. Institute of Standards and Technology (NIST) in 1991 and adopted as a FIPS standard in 1993. The {\it Elliptic Curve Digital Signature Algorithm} (ECDSA) is the elliptic curve analogue of DSA and is the most widely standardized elliptic curve based signature scheme, appearing in the ANSI X9.62, FIPS 186-2, IEEE 1636-2000, and ISO/IEC 15946-2 standards. ECDSA is implemented in TLS and PGP.
|