Elliptic Curve Cryptography, by Riddhiman Dasgupta and Anirban Ghose
Posted on January 2, 2013
Public Key Cryptography:
Publickey cryptography refers to a cryptographic system requiring two separate keys, one of which is secret and one of which is public. Although different, the two parts of the key pair are mathematically linked. One key locks or encrypts the plaintext, and the other unlocks or decrypts the ciphertext. Neither key can perform both functions.
One of these keys is published or public, while the other is kept private.
Publickey cryptography uses asymmetric key algorithms (such as RSA), and can also be referred to by the more generic term “asymmetric key cryptography.” The algorithms used for public key cryptography are based on mathematical relationships (the most notable ones being the integer factorization and discrete logarithm problems) that have no efficient solution. Although it is computationally easy for the intended recipient to generate the public and private keys, to decrypt the message using the private key, and easy for the sender to encrypt the message using the public key, it is extremely difficult (or effectively impossible) for anyone to derive the private key, based only on their knowledge of the public key. This is why, unlike symmetric key algorithms, a public key algorithm does not require a secure initial exchange of one (or more) secret keys between the sender and receiver. The use of these algorithms also allows the authenticity of a message to be checked by creating a digital signature of the message using the private key, which can then be verified by using the public key. In practice, only a hash of the message is typically encrypted for signature verification purposes.
Publickey cryptography is a fundamental, important, and widely used technology. It is an approach used by many cryptographic algorithms and cryptosystems. It underpins such Internet standards as Transport Layer Security (TLS), PGP, and GPG. There are three primary kinds of public key systems: public key distribution systems, digital signature systems, and public key cryptosystems, which can perform both public key distribution and digital signature services. Diffie–Hellman key exchange is the most widely used public key distribution system, while the Digital Signature Algorithm is the most widely used digital signature system.
Elliptic Curve Cryptography:
Elliptic curve cryptography (ECC) is an approach to publickey cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S. Miller in 1985. Publickey cryptography is based on the intractability of certain mathematical problems. Early publickey systems are secure assuming that it is difficult to factor a large integer composed of two or more large prime factors. For ellipticcurvebased protocols, it is assumed that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is infeasible. The size of the elliptic curve determines the difficulty of the problem.
The primary benefit promised by ECC is a smaller key size, reducing storage and transmission requirements—i.e., that an elliptic curve group could provide the same level of security afforded by an RSAbased system with a large modulus and correspondingly larger key—e.g., a 256bit ECC public key should provide comparable security to a
3072bit RSA public key.
Before delving into elliptic curve cryptography, a brief understanding of elliptic curves and finite fields is provided below.
Elliptic Curves:
An elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a
(necessarily commutative) group — and O serves as the identity element. Often the curve itself, without O specified, is called an elliptic curve.
Any elliptic curve can be written as a plane algebraic curve defined by an equation of the form:
Y2 = x3 + ax + b
where x, y, a and b are real numbers. If x^3 + ax + b contains no repeated factors, or equivalently if 4a3 + 27b2 is not
0, then the elliptic curve y^2 = x^3 + ax + b can be used to form a group. An elliptic curve group over real numbers consists of the points on the corresponding elliptic curve, together with a special point O called the point at infinity. This type of equation is called a Weierstrass equation.
Although the formal definition of an elliptic curve is fairly technical and requires some background in algebraic geometry, it is possible to describe some features of elliptic curves over the real numbers using only high school algebra and geometry. The definition of elliptic curve also requires that the curve be nonsingular. Geometrically, this means that the graph has no cusps, selfintersections, or isolated points. Algebraically, this involves calculating the discriminant 16(4a3 + 27b2). The curve is nonsingular if and only if the discriminant is not equal to zero.
The (real) graph of a nonsingular curve has two components if its discriminant is positive and one component if it is negative. For example, in the graphs shown in figure above, the discriminant in the first case is 64, and in the second case is −368.
A catalogue of elliptic curves. Region shown is [−3,3]2 (For a = 0 and b = 0 the function is not smooth and therefore not an elliptic curve.)
Finite Fields:
In abstract algebra, a finite field or Galois field (so named in honour of Évariste Galois) is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois Theory, cryptography, coding theory and Quantum error correction. The finite fields are classified by size; there is exactly one finite field up to isomorphism of size pk for each prime p and positive integer k. A finite field consists of a finite set of elements together with two binary operations called addition and multiplication, which satisfy certain arithmetic properties. The order of a finite field is the number of elements in the field. There exists a finite field of order q if and only if q is a prime power. If q is a prime power, then there is essentially only one finite field of order q; this field is denoted by Fq. There are, however, many ways of representing the elements of Fq. Some representations may lead to more efficient implementations of the field arithmetic in hardware or in software. If q=pm where p is a prime and m is a positive integer, then p is called the characteristic of Fq and m is called the extension degree of Fq.
Prime Fields Fp:
Let p be a prime number. The finite field Fp called a prime field, is comprised of the set of integers {0,1,2,….,p1} with the following arithmetic operations:
 Addition: If a, b ε Fp then a+b=r, where r is the remainder when a+b is divided by p and 0 ≤ r ≤ p1 known as addition modulo p.
 Multiplication: If a, b ε Fp then a.b=s, where s is the remainder when a.b is divided by p and 0 ≤ s ≤ p1
known as multiplication modulo p.
 Inverse: If is a nonzero element in Fp, the inverse of modulo a modulo p, denoted by a1, is the unique
integer c ε Fp for which a.c=1.
Set of affine points of elliptic curve y2 = x3 − x over finite field F61.
Binary Fields F2m:
The field F2m, called a characteristic two finite field or a binary finite field, can be viewed as a vector space of dimension m over the field F2 which consists of the two elements 0 and 1. That is, there exist m elements α0, α1,…, αm1 in F2m such that each element α can be uniquely written in the form:
α= a0 α0+a1 α1+……….+am1 αm1, where a is{0,1}
Such a set {α0, α1,…, αm1} is called a basis of F2m over F2. Given such a basis, a field element α can be represented as the bit string (a0 a1 ……….+am1) Addition of field elements is performed by bitwise XORing the vector representations. The multiplication rule depends on the basis selected.
Elliptic Curve Point Multiplication:
Elliptic curve point multiplication is the operation of successively adding a point along an elliptic curve to itself repeatedly. It is used in elliptic curve cryptography as a means of producing a trap door function. Point multiplication is achieved by two basic elliptic curve operations.
 Point addition, adding two points J and K to obtain another point L i.e. L= J + K.
 Point doubling, adding a point J to itself to obtain another point L i.e. L = 2J.
Point Addition:
Point addition is defined as taking two points along a curve E and computing where a line through them intersects the curve. We use the negative of the intersection point as the result of the addition. The operation is denoted by:
P + Q = R or, (xP, yP) + (xQ, yQ) = (xR, yR), where
L = (yQ – yP)/(xQ – xP), xR = L2 – xP – xQ and yR = L(xP – xR) – yP
Point Doubling:
Like point addition except we take the tangent of a single point and find the intersection with the tangent line.

xR = L

− 2x , y = L(x − x ) − y and L = (3x2 + a)/2y
Point Multiplication:
The straight forward way of computing a point multiplication is through repeated addition (with the exception of the first addition since adding a point to itself is usually undefined since the slope of the line through the point is 0). However, this is a fully exponential approach to computing the multiplication. The more efficient way to multiply points on elliptic curves is to use the doubleandadd method, which is similar to multiplyandsquare in modular exponentiation. A recursive version of the algorithm is as follows:
f(P, n) is
if n = 0 then return 0 # computation complete
else if n mod 2 = 1 then
P + f(P, n1) # addition when n is odd else
f(2P, n/2) # doubling when n is even
where f is the function for doubling, P is the coordinate to double, n is the number of times to double the
coordinate. Example: 100P can be written as 2(2(P+2(2(2(P+2P))))) and thus requires six doublings and two additions.
100P would be equal to f(P,100).
Several newer algorithms exist for calculating point multiplication for elliptic curves, but all of them are simply improvements on the basic doubleandadd method. Some of the more popular and efficient methods are:
 Windowed Method
 Sliding Windowed Method
 wNAF Method
 Montgomery Ladder
Coordinate Systems:
Standard elliptic curve points have x and y coordinates. These are traditionally known as affine coordinates. To improve calculation speed and efficiency, the affine points are transformed to projective coordinate systems, such as standard projective systems for Fp curves, an Jacobian projective systems for F2m curves. Their usage might give a speed benefit over Affine Coordinates when the cost for field inversions is significantly higher than field multiplications. In Standard Projective Coordinates the triple (X, Y, Z) represents the affine point (X / Z, Y / Z).
Discrete Logarithm Problem:
Discrete logarithms are ordinary logarithms involving group theory. An ordinary logarithm loga(b) is a solution of the equation ax = b over the real or complex numbers. Similarly, if g and h are elements of a finite cyclic group G then a solution x of the equation gx = h is called a discrete logarithm to the base g of h in the group G, i.e. logg(h). A group with an operation * is defined on pairs of elements of G. The operations satisfy the following properties:
 Closure: a * b ε G for all a, b ε G.
 Associativity: a * (b * c) = (a * b) * c for all a, b ε G.
 Existence of Identity: There exists an element e ε G, called the identity, so that e * a = a * e = a for all a ε G.
 Existence of inverse: For each a ε G there is an element b ε G such that a * b = b * a = e. The element b is
called the inverse of a.
Moreover, a group G is said to be abelian if a * b = b * a for all a, b ε G. The order of a group G is the number of elements in G. The discrete logarithm problem is to find an integer x, 0 ≤ x ≤ n1, such that gx ≡ h (mod p), for given g ε Z*p of order n and given h ε Z*p. The integer x is called the discrete logarithm of h to the base g.
Elliptic Curve Discrete Logarithm Problem:
An elliptic curve Ek, [3] defined over a field K of characteristic ≠ 2 or 3 is the set of solutions (x, y) ε K’ to the equation y2 = x3 + ax + b where a, b ε K (where the cubic on the right has no multiple roots). Two nonnegative integers, a and b, less than p that satisfy 4a3 + 27b2 (mod p) ≠0. Then Ep (a, b) denotes the elliptic group mod p whose elements (x,
y) are pairs of nonnegative integers less than p satisfying y2 ≡ x3 + ax + b (mod p) together with the point at infinity O.
The elliptic curve discrete logarithm problem can be stated as follows:
Fix a prime p and an elliptic curve. Q= xP where xP represents the point P on elliptic curve added to itself x times. Then the elliptic curve discrete logarithm problem is to determine x given P and Q. It is relatively easy to calculate Q given x and P, but it is very hard to determine x given Q and P. Elliptic curve cryptography is based on ECDLP.
The best known algorithm for solving ECDLP is PollardRho algorithm which is fully exponential having a running time
of √(Π*n /2).
Elliptic Curve Domain Parameters:
To use ECC all parties must agree on all the elements defining the elliptic curve, that is, the domain parameters of the scheme. The field is defined by p in the prime case and the pair of m and f in the binary case. The elliptic curve is defined by the constants a and b used in its defining equation.
Finally, the cyclic subgroup is defined by its generator (aka. base point) G. For cryptographic application the order of G, that is the smallest nonnegative number n such that, n*G = O is normally prime. Since n is the size of a subgroup of E(Fp) it follows from Lagrange’s theorem that the number h = E/n is an integer. In cryptographic applications this number h, called the cofactor, must be small, preferably less than 4, and usually just 1.
To summarize, for prime curves, the domain parameters are (p,a,b,G,n,h), while for binary curves, they are
(m,f,a,b,G,n,h).
Unless there is an assurance that domain parameters were generated by a party trusted with respect to their use, the domain parameters must be validated before use. The generation of domain parameters is not usually done by each participant since this involves counting the number of points on a curve which is timeconsuming and troublesome to implement. As a result several standard bodies published domain parameters of elliptic curves for several common field sizes. Such domain parameters are commonly known as “standard curves” or “named curves”; a named curve can be referenced either by name or by the unique object identifier defined in the standard documents:
 NIST
 SECG
 ECC Brainpool
SECG test vectors are also available.[6]. NIST has approved many SECG curves, so there is a significant overlap between the specifications published by NIST and SECG. EC domain parameters may be either specified by value or by name.
Elliptic Curve Cryptography Schemes:
Several discrete logarithmbased protocols have been adapted to elliptic curves, such as:
 The Elliptic Curve Diffie– Hellman (ECDH) key agreement scheme is based on the Diffie–Hellman scheme
 The Elliptic Curve Integrated Encryption Scheme (ECIES), also known as Elliptic Curve Augmented Encryption
Scheme or simply the Elliptic Curve Encryption Scheme
 The Elliptic Curve Digital Signature Algorithm (ECDSA) is based on the Digital Signature Algorithm
 The ECMQV key agreement scheme is based on the MQV key agreement scheme
 The ECQV implicit certificate scheme
Elliptic Curve Diffie Hellman Key Agreement:
Diffie–Hellman key exchange is a specific method of exchanging cryptographic keys. It is one of the earliest practical examples of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher. The scheme was first published by Whitfield Diffie and Martin Hellman in 1976.
Diffie–Hellman establishes a shared secret that can be used for secret communications by exchanging data over a public network. The following diagram illustrates the general idea of the key exchange by using colours instead of a very large number. The key part of the process is that Alice And Bob exchange their secret colours in a mix only.
Finally this generates an identical key that is almost impossible to reverse for another party that might have been listening in on them. Alice and Bob now use this common secret to encrypt and decrypt their sent and received data.
Elliptic Curve DiffieHellman Key Exchange is a variant of the Diffie–Hellman protocol using elliptic curve cryptography. It is an anonymous key agreement protocol that allows two parties, each having an elliptic curve publicprivate key pair, to establish a shared secret over an insecure channel.
ECDH Protocol: Initially, Alice and Bob agree upon the domain parameters of the elliptic
curve to be used during key exchange:
(p,a,b,G,n,h). Each party has a key pair(d,Q) suitable for elliptic curve cryptography:
 d is a randomly selected integer in the interval [1,n1]
 Q is the public key which is computed by Q=dG
 Each party must have the other’s public key.
 Alice computes daQb.
 Bob computes dbQa
The shared secret key calculated by both the parties is the same daQb=dadbG=dbdaG=dbQa
The only information about the private key that a party would expose is the corresponding public key. So no other
party can determine the private key unless somebody can solve the Elliptic Curve Discrete Logarithm Problem.
Elliptic Curve Digital Signature Algorithm:
A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit. Digital signatures are commonly used for software distribution, financial transactions, and in other cases where it is important to detect forgery or tampering. A digital signature scheme typically consists of three algorithms:
 A key generation algorithm that selects a private key uniformly at random from a set of possible private keys. The algorithm outputs the private key and a corresponding public key.
 A signing algorithm that, given a message and a private key, produces a signature.
 A signature verifying algorithm that, given a message, public key and a signature, either accepts or rejects the message’s claim to authenticity.
The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature Standard (DSS), specified in FIPS 186, adopted in 1993. A minor revision was issued in 1996 as FIPS 1861. The standard was expanded further in 2000 as FIPS 1862 and again in 2009 as FIPS 1863.Its security is based on the computational intractability of the Discrete Logarithm Problem in primeorder subgroups of Zp*.
The Elliptic Curve Digital Signature Algorithm (ECDSA) is a variant of the Digital Signature Algorithm (DSA) which uses elliptic curve cryptography. Ideally, a digital signature scheme should be existentially nonforgeable under chosen message attack. The ECDSA have a smaller key size, which leads to faster computation time and reduction in processing power, storage space and bandwidth. This makes the ECDSA ideal for constrained devices such as pagers, cellular phones and smart cards.
ECDSA Key Generation:
A party’s key pair is associated with a particular set of EC domain parameters D = (p,a,b,G,n,h).The following steps are performed:
 Select a random integer d in the interval [1, n 1].
 Compute Public Key Q = dP where P is a point of prime order n on the elliptic curve.
ECDSA Signature Generation:
The party with domain parameters D = (p,a,b,G,n,h) signs a given message m using the following steps:
 Select a random or pseudorandom integer k in the interval [1,n1].
 Compute kP =(x0, y0) and = x0 mod n. If r = 0 then go back to step 1.
 Compute kinv = k modInverse n.
 Compute s= kinv {h (m)+ dr} mod n, where h is the Secure Hash Algorithm (SHA1). If s = 0, then go back to step 1.
 The signature for the message m is the pair of integers (r, s).
ECDSA Signature Verification:
The other party obtains an authentic copy of the domain parameters D = (p,a,b,G,n,h) used to generate the signature
(r,s) on the message m. The signature is verified by using the following steps:
 Verify that r and s are integers in the interval [1, n1]
 Compute w = s modInverse n and h(m)
 Compute u1 = h(m)w mod n and u2 = rw mod n.
 Compute u1P + u2Q =(x0, y0) and v= x0 mod n.
 Accept the signature if and only if v = r
Comments are currently closed.
オークリー サングラス…
Elliptic Curve Cryptography, by Riddhiman Dasgupta and Anirban Ghose  ACM @ HITK…