| Home Page |

| Course Page |

Chapter 9. Elliptic Curve Cryptosystems

Lecture Notes

Rochester Institute of Technology—Department of Computer Science

- 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

- A cubic equation:
- y = x
^{3}+ ax + b, for some constants a and b

- y = x
- An elliptic curve is the square root of the above cubic equation:
- y = sqrt(x
^{3}+ ax + b) - Or, y
^{2}= x^{3}+ ax + b

- y = sqrt(x
- Examples
y = x ^{3}y ^{2}= x^{3}a = 0, b = 0 y = x ^{3}− 2xy ^{2}= x^{3}− 2xa = −2, b = 0 y = x ^{3}− 2x + 2y ^{2}= x^{3}− 2x + 2a = −2, b = 2

- Group elements
- All points (x,y) on some elliptic curve y
^{2}= x^{3}+ 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

- All points (x,y) on some elliptic curve y
- 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

- 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
^{2}= x^{3}+ 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
^{3}+ 27b^{2}≠ 0 (mod p) - A finite group

- All points (x,y) on some elliptic curve y
- 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}*

- 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
^{2}= x^{3}+ ax + b modulo p - Points P
_{0}= (x_{0},y_{0}) and P_{1}= (x_{1},y_{1}) on E

- Output
- The point P
_{2}:= P_{0}+ P_{1}

- The point P
- Algorithm
- If P
_{0}= O, then output P_{2}← P_{1}and stop. - If P
_{1}= O, then output P_{2}← P_{0}and stop. - If x
_{0}≠ x_{1}, then3.1. Set λ ← (y

_{0}− y_{1})/(x_{0}− x_{1}) mod p.3.2. Go to Step 7.

- If y
_{0}≠ y_{1}, then output P_{2}← O and stop. - If y
_{1}= 0, then output P_{2}← O and stop. - Set λ ← (3x
_{1}^{2}+ a)/(2y_{1}) mod p. - Set x
_{2}← λ^{2}− x_{0}− x_{1}mod p. - Set y
_{2}← (x_{1}− x_{2})λ − y_{1}mod p. - Output P
_{2}← (x_{2},y_{2}).

- If P
- 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).

- We will use the elliptic curve y
^{2}= x^{3}+ 5x + 7 (mod 19)- 4a
^{3}+ 27b^{2}= 4⋅5^{3}+ 27⋅7^{2}= 1823 = 18 ≠ 0 (mod 19), so the elliptic curve group exists

- 4a
- First we need to find all the group elements
- To find those, we need to find the numbers that are squares (mod 19)
y y ^{2}y y ^{2}y y ^{2}y y ^{2}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
^{3}+ 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
^{2}, then y = 8 or 11 - (2, 5), (2, 14), -- because if z = 6 = y
^{2}, then y = 5 or 14 - (3, 7), (3, 12), -- because if z = 11 = y
^{2}, then y = 7 or 12 - (5, 9), (5, 10), -- because if z = 5 = y
^{2}, then y = 9 or 10 - (6, 5), (6, 14), -- because if z = 6 = y
^{2}, then y = 5 or 14 - (7, 9), (7, 10), -- because if z = 5 = y
^{2}, then y = 9 or 10 - (11, 5), (11, 14), -- because if z = 6 = y
^{2}, then y = 5 or 14 - (12, 3), (12, 16), -- because if z = 9 = y
^{2}, then y = 3 or 16 - (14, 3), (14, 16), -- because if z = 9 = y
^{2}, then y = 3 or 16 - (18, 1), (18, 18), -- because if z = 1 = y
^{2}, then y = 1 or 18 - plus O -- the point at infinity

- (0, 8), (0, 11), -- because if z = 7 = y
- 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
^{−1}(mod p) - a
^{−1}= multiplicative inverse of a (mod p)

- Example: Compute P
_{0}+ P_{1}= (x_{0}, y_{0}) + (x_{1}, y_{1}) = (3, 7) + (5, 10)- λ ← (y
_{0}− y_{1})/(x_{0}− x_{1}) = (7 − 10)/(3 − 5) = (−3)/(−2) = 16/17 = 16×17^{−1}= 16×9 = 144 = 11 (mod 19) - x
_{2}← λ^{2}− x_{0}− x_{1}= 11^{2}− 3 − 5 = 113 = 18 (mod 19) - y
_{2}← (x_{1}− x_{2})λ − y_{1}= (5 − 18)×11 − 10 = (−13)×11 − 10 = 6×11 − 10 = 56 = 18 (mod 19) - Output P
_{2}← (x_{2}, y_{2}) = (18, 18) - P
_{2}is in fact an element of the group

- λ ← (y
- Example: Compute P
_{0}+ P_{1}= (x_{0}, y_{0}) + (x_{1}, y_{1}) = (11, 5) + (11, 5)- λ ← (3x
_{1}^{2}+ a)/(2y_{1}) = (3×11^{2}+ 5)/(2×5) = 368/10 = 7/10 = 7×10^{−1}= 7×2 = 14 (mod 19) - x
_{2}← λ^{2}− x_{0}− x_{1}= 14^{2}− 11 − 11 = 174 = 3 (mod 19) - y
_{2}← (x_{1}− x_{2})λ − y_{1}= (11 − 3)×14 − 5 = 8×14 − 5 = 107 = 12 (mod 19) - Output P
_{2}← (x_{2}, y_{2}) = (3, 12) - P
_{2}is in fact an element of the group

- λ ← (3x

- 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
^{2}= x^{3}+ 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 that 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.

- IEEE Std 1363-2000.

- 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-4, July 2013. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.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^{192})

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

- Public parameters: p, a, b, G (Curve P-192, say)
- Alex generates a secret random number u, 1 < u < n−1
- Alex sends uG to Blake
- Blake generates a secret random number v, 1 < v < n−1
- Blake sends vG to Alex
- Alex receives vG from Blake and computes u(vG)
- Blake receives uG from Alex and computes v(uG)
- Alex and Blake 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 = (602066282375688656758213480587526111916698976636884684818, 174050332293622031404857552280219410364023488927386650641) n = 6277101735386680763835789423176059013767194773182842284081 Alex picks a secret random number u, 1 < u < n u = 5637251092883050934974034135782244228141279863292549702928 Alex computes uG and sends uG to Blake uG = (973697636141457729657017784410888711121134871939721243872, 5411673841953064524366212602751798888735083386815984546764) Blake picks a secret random number v, 1 < v < n v = 2839528846177866422846490458713234411077080637528653828732 Blake computes vG and sends vG to Alex vG = (4308684260420081712899023104548395315152398734431254914227, 5763741726400787544768110819727646341738661500991689474804) Alex receives vG from Blake and computes K1 = u(vG) K1 = (4118877111827861632392671987908909928900571700854755697981, 3956628862413479499373206339481805439303476657793414035681) Blake receives uG from Alex and computes K2 = v(uG) K2 = (4118877111827861632392671987908909928900571700854755697981, 3956628862413479499373206339481805439303476657793414035681) They match!

- 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((64*N*/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) Z _{p}* 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)

- 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

- 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) = ab*e*(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)**- Blake's identity -- e.g., his email address -- determines his public encryption key (no need to look up Blake's public key)
- There is a trusted third party, Arthur the Authority, who hands out private keys
- Alex calculates the public key for Blake's identity
- Alex encrypts a message using that public key and sends it to Blake
- Using a secure channel, Blake proves his identity to Arthur and obtains from Arthur the private key for his identity
- Blake 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.

- D. Boneh and M. Franklin. Identity based encryption from the Weil pairing.
- 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)

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

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

- Blake decrypts a ciphertext (R, c):
- T ←
*e*(R,B) - m ← c xor Hash(T)
- This works because T =
*e*(R,B) =*e*(rP,aQ) = ra*e*(P,Q) = r*e*(aP,Q) = rS - Thus, c xor Hash(T) = m xor Hash(rS) xor Hash(T) = m xor Hash(T) xor Hash(T) = m

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

| Course Page |

| Home Page |