4003-482-01/4005-705-01 Cryptography
Chapter 9. Elliptic Curve Cryptosystems
Lecture Notes

Abstract Groups

• A group consists of:
  • A set of group elements, G
  • A group operation, symbolized as #

• The group must obey these properties:
  • Closure: For every A, B ∈ G, (A # B) ∈ G
  • Associativity: For every A, B, C ∈ G, (A # B) # C = A # (B # C)
  • Identity: There is an element I such that for every A ∈ G, (A # I) = A
  • Inverse: For every A ∈ G, there is an element −A such that (A # −A) = I

• Logarithms
  • Suppose B = A # A # . . . # A (A repeated n times)
  • Then n is called the logarithm of B with respect to A

• Infinite groups
  • G is an infinite set
  • (G = real numbers, # = addition) is an infinite group

• Finite groups
  • G is a finite set
  • (G = {1, 2, . . ., p−1}, # = multiplication mod p}), where p is a prime, is a finite group, namely Z_p*
  • The Discrete Logarithm Problem: Find the logarithm of B with respect to A in a finite group

Elliptic Curves

• A cubic equation:
  • y = x³ + ax + b, for some constants a and b

• An elliptic curve is the square root of the above cubic equation:
  • y = sqrt(x³ + ax + b)
  • Or, y² = x³ + ax + b

• Examples

  y = x3		y2 = x3	a = 0, b = 0

  y = x3 − 2x		y2 = x3 − 2x	a = −2, b = 0

  y = x3 − 2x + 2		y2 = x3 − 2x + 2	a = −2, b = 2

Elliptic Curve Group Over the Reals

• Group elements
  • All points (x,y) on some elliptic curve y² = x³ + ax + b; plus . . .
  • O, the "point" infinitely far up (and down) the Y axis (that's the letter oh, not the number zero)
  • An infinite group

• The group operation is customarily called "point addition" and is symbolized with the + sign

• Group operation: C = A + B, where A ≠ B
  • Draw a straight line between points A and B
  • The line intersects the elliptic curve at a third point (u,v)
  • Reflect this point across the X axis: (u,−v)
  • Then C = A + B = (u,−v)

  

• Group operation: C = A + A = 2A
  • Draw a tangent to the elliptic curve at point A
  • The tangent line intersects the elliptic curve at another point (u,v)
  • Reflect this point across the X axis: (u,−v)
  • Then C = A + A = 2A = (u,−v)

  

• The group operation is associative: (A + B) + C = A + (B + C)

• Identity element is O

• Let A = (x,y), then the inverse of A = −A = (x,−y)

• Repeated group operation: C = A + A + . . . + A (A repeated n times) = nA
  • Customarily called "point multiplication by a scalar n" or just "point multiplication"
  • n is the logarithm of C with respect to A

Elliptic Curve Group Over GF(p)

• p is a prime greater than 3

• GF(p) = the set of integers mod p = {0, 1, 2, . . ., p−1}

• Group elements
  • All points (x,y) on some elliptic curve y² = x³ + ax + b, where x, y ∈ GF(p); plus . . .
  • O, the "point" infinitely far up (and down) the Y axis
  • Also, a, b ∈ GF(p) and 4a³ + 27b² ≠ 0 (mod p)
  • A finite group

• The group operation (point addition) is the same as before, except all arithmetic is done (mod p)

• Point addition in the elliptic curve group mod p is analogous to multiplication in Z_p*

• Point multiplication in the elliptic curve group mod p is analogous to exponentiation in Z_p*

Point Addition Algorithm

• IEEE Std 1363-2000. IEEE Standard Specifications for Public-Key Cryptography. January 30, 2000. Appendix A.10.1.

• Inputs
  • A prime p > 3
  • Coefficients a, b for an elliptic curve E: y² = x³ + ax + b modulo p
  • Points P₀ = (x₀,y₀) and P₁ = (x₁,y₁) on E

• Output
  • The point P₂ := P₀ + P₁

• Algorithm

  1. If P₀ = O, then output P₂ ← P₁ and stop.

  2. If P₁ = O, then output P₂ ← P₀ and stop.

  3. If x₀ ≠ x₁, then

     3.1. Set λ ← (y₀ − y₁)/(x₀ − x₁) mod p.

     3.2. Go to Step 7.

  4. If y₀ ≠ y₁, then output P₂ ← O and stop.

  5. If y₁ = 0, then output P₂ ← O and stop.

  6. Set λ ← (3x₁² + a)/(2y₁) mod p.

  7. Set x₂ ← λ² − x₀ − x₁ mod p.

  8. Set y₂ ← (x₁ − x₂)λ − y₁ mod p.

  9. Output P₂ ← (x₂,y₂).

• The above algorithm requires three or four modular multiplications and a modular inversion.

• To subtract the point P = (x,y), add the point −P = (x,−y).

Point Addition Examples

• We will use the elliptic curve y² = x³ + 5x + 7 (mod 19)
  • 4a³ + 27b² = 4⋅5³ + 27⋅7² = 1823 = 18 ≠ 0 (mod 19), so the elliptic curve group exists

• First we need to find all the group elements

• To find those, we need to find the numbers that are squares (mod 19)

  y			y2		y			y2		y			y2		y			y2
  0			0		5			6		10			5		15			16
  1			1		6			17		11			7		16			9
  2			4		7			11		12			11		17			4
  3			9		8			7		13			17		18			1
  4			16		9			5		14			6

• Then for each value of x, we ask if z = x³ + 5x + 7 is a square (mod 19)

  x		z		Square?		x		z		Square?		x		z		Square?		x		z		Square?
  0		7		Yes		5		5		Yes		10		12		-		15		18		-
  1		13		-		6		6		Yes		11		6		Yes		16		3		-
  2		6		Yes		7		5		Yes		12		9		Yes		17		8		-
  3		11		Yes		8		8		-		13		8		-		18		1		Yes
  4		15		-		9		2		-		14		9		Yes

• Looking at the "Yes" entries, we see that the group elements (x, y) are:
  • (0, 8), (0, 11), -- because if z = 7 = y², then y = 8 or 11
  • (2, 5), (2, 14), -- because if z = 6 = y², then y = 5 or 14
  • (3, 7), (3, 12), -- because if z = 11 = y², then y = 7 or 12
  • (5, 9), (5, 10), -- because if z = 5 = y², then y = 9 or 10
  • (6, 5), (6, 14), -- because if z = 6 = y², then y = 5 or 14
  • (7, 9), (7, 10), -- because if z = 5 = y², then y = 9 or 10
  • (11, 5), (11, 14), -- because if z = 6 = y², then y = 5 or 14
  • (12, 3), (12, 16), -- because if z = 9 = y², then y = 3 or 16
  • (14, 3), (14, 16), -- because if z = 9 = y², then y = 3 or 16
  • (18, 1), (18, 18), -- because if z = 1 = y², then y = 1 or 18
  • plus O -- the point at infinity

• And we see that the group order is 21

• We also need to find the multiplicative inverses (mod 19), using the Extended Euclidean Algorithm

  x		x−1		x		x−1		x		x−1		x		x−1
  0		-		5		4		10		2		15		14
  1		1		6		16		11		7		16		6
  2		10		7		11		12		8		17		9
  3		13		8		12		13		3		18		18
  4		5		9		17		14		15

• When doing arithmetic (mod p), keep in mind that:
  • After every operation, divide by p and keep the remainder
  • −a = p − a (mod p)
  • b/a = b×a⁻¹ (mod p)
  • a⁻¹ = multiplicative inverse of a (mod p)

• Example: Compute P₀ + P₁ = (x₀, y₀) + (x₁, y₁) = (3, 7) + (5, 10)
  • λ ← (y₀ − y₁)/(x₀ − x₁) = (7 − 10)/(3 − 5) = (−3)/(−2) = 16/17 = 16×17⁻¹ = 16×9 = 144 = 11 (mod 19)
  • x₂ ← λ² − x₀ − x₁ = 11² − 3 − 5 = 113 = 18 (mod 19)
  • y₂ ← (x₁ − x₂)λ − y₁ = (5 − 18)×11 − 10 = (−13)×11 − 10 = 6×11 − 10 = 56 = 18 (mod 19)
  • Output P₂ ← (x₂, y₂) = (18, 18)
  • P₂ is in fact an element of the group

• Example: Compute P₀ + P₁ = (x₀, y₀) + (x₁, y₁) = (11, 5) + (11, 5)
  • λ ← (3x₁² + a)/(2y₁) = (3×11² + 5)/(2×5) = 368/10 = 7/10 = 7×10⁻¹ = 7×2 = 14 (mod 19)
  • x₂ ← λ² − x₀ − x₁ = 14² − 11 − 11 = 174 = 3 (mod 19)
  • y₂ ← (x₁ − x₂)λ − y₁ = (11 − 3)×14 − 5 = 8×14 − 5 = 107 = 12 (mod 19)
  • Output P₂ ← (x₂, y₂) = (3, 12)
  • P₂ is in fact an element of the group

Point Multiplication Algorithm

• n⋅G = G + G + . . . + G
  • G is a point (elliptic curve group element)
  • n is an integer
  • n⋅G is n copies of G added together using point addition
  • This is called point multiplication

• Example: In the elliptic curve y² = x³ + 5x + 7 (mod 19), compute 19⋅(3, 12)

• First compute the following multiples of (3, 12) by repeatedly doubling using point addition:
  1⋅(3, 12) = (3, 12)
  2⋅(3, 12) = (3, 12) + (3, 12) = (0, 11)
  4⋅(3, 12) = (0, 11) + (0, 11) = (7, 9)
  8⋅(3, 12) = (7, 9) + (7, 9) = (5, 10)
  16⋅(3, 12) = (5, 10) + (5, 10) = (6, 5)

• Then compute the point multiplication by adding the proper multiples of (3, 12):
  19⋅(3, 12)
  = (16 + 2 + 1)⋅(3, 12)
  = 16⋅(3, 12) + 2⋅(3, 12) + 1⋅(3, 12)
  = (6, 5) + (0, 11) + (3, 12)
  = (14, 3) + (3, 12)
  = (0, 8)

• There's another algorithm than can be faster than the above double-and-add algorithm:
  • IEEE Std 1363-2000. IEEE Standard Specifications for Public-Key Cryptography. January 30, 2000. Appendix A.10.3.

Elliptic Curve Parameter Generation

• Elliptic curve cryptographic algorithms require parameters:

• Prime modulus p

• Elliptic curve coefficients a and b

• A generator (a point on the elliptic curve) G = (G_x,G_y)
  • We are going to be doing point multiplication on G
  • The order of G is the value n such that nG = O
  • n should be a large prime number
  • The security of the algorithm depends on the size of n

• Generating suitable elliptic curve parameters is complicated

• Fortunately, NIST has recommended several sets of elliptic curve parameters
  • Digital Signature Standard (DSS). Federal Information Processing Standards Publication 186-3, June 2009. http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf

• Curve P-192 (from DSS Appendix D.1.2.1)
  • p = 6277101735386680763835789423207666416083908700390324961279
  • a = −3
  • b = 64210519 e59c80e7 0fa7e9ab 72243049 feb8deec c146b9b1 hexadecimal
  • G_x = 188da80e b03090f6 7cbf20eb 43a18800 f4ff0afd 82ff1012 hexadecimal
  • G_y = 07192b95 ffc8da78 631011ed 6b24cdd5 73f977a1 1e794811 hexadecimal
  • n = 6277101735386680763835789423176059013767194773182842284081 (approximately 2¹⁹²)

• Curves P-224, P-256, P-384, and P-521 are also defined

Elliptic Curve Diffie-Hellman Key Exchange

• Public parameters: p, a, b, G (Curve P-192, say)

• Alice generates a secret random number u, 1 < u < n−1

• Alice sends uG to Bob

• Bob generates a secret random number v, 1 < v < n−1

• Bob sends vG to Alice

• Alice receives vG from Bob and computes u(vG)

• Bob receives uG from Alice and computes v(uG)

• Alice and Bob now have a shared secret value, uvG

• (All the usual warnings about man-in-the-middle, etc. still apply)

• Example

  ELLIPTIC CURVE DIFFIE-HELLMAN KEY EXCHANGE DEMO
  
  Elliptic curve: y^2 = x^3 + ax + b (mod p)
  p = 6277101735386680763835789423207666416083908700390324961279
  a = 6277101735386680763835789423207666416083908700390324961276
  b = 2455155546008943817740293915197451784769108058161191238065
  
  Generator of order n:
  G = (602046282375688656758213480587526111916698976636884684818,
       174050332293622031404857552280219410364023488927386650641)
  n = 6277101735386680763835789423176059013767194773182842284081
  
  Alice picks a secret random number u, 1 < u < n
  u = 5637251092883050934974034135782244228141279863292549702928
  
  Alice computes uG and sends uG to Bob
  uG = (973697636141457729657017784410888711121134871939721243872,
        5411673841953064524346212602751798888735083386815984546764)
  
  Bob picks a secret random number v, 1 < v < n
  v = 2839528846177866422846490458713234411077080637528653828732
  
  Bob computes vG and sends vG to Alice
  vG = (4308684260420081712899023104548395315152398734431254914227,
        5763741726400787544768110819727646341738661500991689474804)
  
  Alice receives vG from Bob and computes K1 = u(vG)
  K1 = (4118877111827861632392671987908909928900571700854755697981,
        3954628862413479499373206339481805439303476657793414035681)
  
  Bob receives uG from Alice and computes K2 = v(uG)
  K2 = (4118877111827861632392671987908909928900571700854755697981,
        3954628862413479499373206339481805439303476657793414035681)
  
  They match!
  

Elliptic Curve Security

• The fastest known elliptic curve discrete logarithm algorithm (Pohlig-Hellman) has complexity O(2^n/2)
  • n = generator order size in bits
  • Exponential time algorithm

• The fastest known Z_p* discrete logarithm algorithm (general number field sieve) has complexity O(exp((64N/9)^1/3 (log N)^2/3))
  • N = generator order size in bits
  • Subexponential time algorithm

• So roughly speaking, an elliptic curve algorithm of size n and a Z_p* algorithm of size N should have the same security level for:

  Elliptic curve size n (bits)		Zp* size N (bits)
  160		1024
  256		3072
  384		7680
  512		15360

• Therefore, with elliptic curves we can use a smaller prime p than with Z_p*, and still get the same security level
  • Less CPU time
  • Less memory
  • Less network bandwidth
  • Fewer gates (in a hardware implementation)

Topics Not Covered

• Point compression
  • Instead of storing (x,y), store only x plus the least significant bit of y; recompute y from x when needed
  • Cuts storage for, and network bandwidth to transmit, an elliptic curve point by about half
  • May be important in low-end environments

• Elliptic curves over GF(2^m)
  • A "field of characteristic 2"
  • Finite field arithmetic can be implemented more efficiently than in GF(p)
  • Polynomial basis representation
  • Normal basis representation
  • A different point addition algorithm is used

• Parameter generation
  • Choosing elliptic curves
  • Choosing generators

• Elliptic curve public key algorithms
  • Key exchange, encryption, digital signatures . . . anything based on the discrete logarithm problem

• See IEEE Std 1363-2000

Pairing-Based Cryptography

• Suppose we have an additive group G
  • That is, the group operation is "addition" in the general sense

• Suppose we have a second additive group H

• Suppose there is a pairing function e such that:
  • e takes two arguments that are members of G
  • e's result is a member of H
  • e is efficiently computable (in polynomial time)
  • e is nondegenerate in the first argument
    • e(P,R) = e(Q,R) if and only if P = Q
  • e is a bilinear mapping
    • e(aP,bQ) = abe(P,Q)

• Certain elliptic curve groups have efficiently computable pairing functions
  • Weil pairing
  • Tate-Lichtenbaum pairing

• Then we can do lots of interesting cryptography involving the pairing function

• Example: Identity-based encryption (IBE)
  • Bob's identity -- e.g., his email address -- determines his public encryption key (no need to look up Bob's public key)
  • There is a trusted third party, Arthur the Authority, who hands out private keys
  • Alice calculates the public key for Bob's identity
  • Alice encrypts a message using that public key and sends it to Bob
  • Using a secure channel, Bob proves his identity to Arthur and obtains from Arthur the private key for his identity
  • Bob decrypts the message using that private key
  • Problem: Arthur knows all the private keys, so Arthur can decrypt any message -- Arthur has to be trusted not to do this and not to get hacked

• IBE using a pairing function
  • D. Boneh and M. Franklin. Identity based encryption from the Weil pairing. SIAM Journal on Computing, 32(3)586-615, 2002.

• Arthur's setup:
  • Choose groups G and H
  • Choose a pairing function e for G and H
  • Choose P, a generator for G
  • Choose a secret random number a and compute aP
  • Publish (G, H, e, P, aP)

• Alice encrypts a message m for Bob using Arthur's published parameters:
  • Choose a secret random number r
  • R ← rP
  • Q ← Hash(Bob's identity)
  • S ← e(aP,Q)
  • c ← m xor Hash(rS)
  • Ciphertext = (R, c)

• Arthur computes Bob's private key and sends it securely to Bob:
  • Q ← Hash(Bob's identity)
  • B ← aQ
  • Bob's private key = B

• Bob decrypts a ciphertext (R, c):
  • T ← e(R,B)
  • m ← c xor Hash(T)
  • This works because T = e(R,B) = e(rP,aQ) = rae(P,Q) = re(aP,Q) = rS
  • Thus, c xor Hash(T) = m xor Hash(rS) xor Hash(T) = m xor Hash(T) xor Hash(T) = m

• Pairing-based crypto is a hot research topic, stimulated by efficiently computable pairing functions on elliptic curve groups

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 26-Apr-2013. Please send comments to ark­@­cs.rit.edu.