Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

CSCI 662—Foundations of Cryptography Chapter 9. Elliptic Curve Cryptosystems Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

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 Zp*
• The Discrete Logarithm Problem: Find the logarithm of B with respect to A in a finite group

Elliptic Curves

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

• An elliptic curve is the square root of the above cubic equation:
• y = sqrt(x3 + ax + b)
• Or, y2 = x3 + 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 y2 = x3 + 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 y2 = x3 + 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 4a3 + 27b2 ≠ 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 Zp*

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

• 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: y2 = x3 + ax + b modulo p
• Points P0 = (x0,y0) and P1 = (x1,y1) on E

• Output
• The point P2 := P0 + P1

• Algorithm

1. If P0 = O, then output P2 ← P1 and stop.

2. If P1 = O, then output P2 ← P0 and stop.

3. If x0 ≠ x1, then

3.1. Set λ ← (y0 − y1)/(x0 − x1) mod p.

3.2. Go to Step 7.

4. If y0 ≠ y1, then output P2 ← O and stop.

5. If y1 = 0, then output P2 ← O and stop.

6. Set λ ← (3x12 + a)/(2y1) mod p.

7. Set x2 ← λ2 − x0 − x1 mod p.

8. Set y2 ← (x1 − x2)λ − y1 mod p.

9. Output P2 ← (x2,y2).

• 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 y2 = x3 + 5x + 7 (mod 19)
• 4a3 + 27b2 = 4⋅53 + 27⋅72 = 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 = x3 + 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 = y2, then y = 8 or 11
• (2, 5), (2, 14), -- because if z = 6 = y2, then y = 5 or 14
• (3, 7), (3, 12), -- because if z = 11 = y2, then y = 7 or 12
• (5, 9), (5, 10), -- because if z = 5 = y2, then y = 9 or 10
• (6, 5), (6, 14), -- because if z = 6 = y2, then y = 5 or 14
• (7, 9), (7, 10), -- because if z = 5 = y2, then y = 9 or 10
• (11, 5), (11, 14), -- because if z = 6 = y2, then y = 5 or 14
• (12, 3), (12, 16), -- because if z = 9 = y2, then y = 3 or 16
• (14, 3), (14, 16), -- because if z = 9 = y2, then y = 3 or 16
• (18, 1), (18, 18), -- because if z = 1 = y2, 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−1 (mod p)
• a−1 = multiplicative inverse of a (mod p)

• Example: Compute P0 + P1 = (x0, y0) + (x1, y1) = (3, 7) + (5, 10)
• λ ← (y0 − y1)/(x0 − x1) = (7 − 10)/(3 − 5) = (−3)/(−2) = 16/17 = 16×17−1 = 16×9 = 144 = 11 (mod 19)
• x2 ← λ2 − x0 − x1 = 112 − 3 − 5 = 113 = 18 (mod 19)
• y2 ← (x1 − x2)λ − y1 = (5 − 18)×11 − 10 = (−13)×11 − 10 = 6×11 − 10 = 56 = 18 (mod 19)
• Output P2 ← (x2, y2) = (18, 18)
• P2 is in fact an element of the group

• Example: Compute P0 + P1 = (x0, y0) + (x1, y1) = (11, 5) + (11, 5)
• λ ← (3x12 + a)/(2y1) = (3×112 + 5)/(2×5) = 368/10 = 7/10 = 7×10−1 = 7×2 = 14 (mod 19)
• x2 ← λ2 − x0 − x1 = 142 − 11 − 11 = 174 = 3 (mod 19)
• y2 ← (x1 − x2)λ − y1 = (11 − 3)×14 − 5 = 8×14 − 5 = 107 = 12 (mod 19)
• Output P2 ← (x2, y2) = (3, 12)
• P2 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 y2 = x3 + 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.

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 = (Gx,Gy)
• 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

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

• 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)

• 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!
```

Elliptic Curve Security

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

• The fastest known Zp* 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 Zp* 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 Zp*, 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(2m)
• 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)
• 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.

• 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) = 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

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005