24 Elliptic Curve

Hiteishi Diwanji

Elliptic Curve

Which steps are involved?

  • 1) choose an elliptic curve Ep(a, b).
  • 2) Chooses another prime q the private key d.
  • 3) Choose e1(…, …), a point on the curve.
  • 4) calculates e2(…, …) = d × e1(…, …).
  • 5) Public key is (a, b, p, q, e1, e2); private key is d.

ECDSA signing and verifying:

 

Elliptic curves in Cryptography

  • Elliptic Curve (EC) systems as applied to cryptography were first proposed in 1985 independently by Neal Koblitz and Victor Miller.
  • The discrete logarithm problem on elliptic curve groups is believed to be more difficult than the corresponding problem in (the multiplicative group of nonzero elements of) the underlying finite field.

Elliptic Curve on a finite set of Integers

  • Consider y2 = x3 + 2x + 3 (mod 5)
  • x = 0 Þ y2 = 3 Þ no solution (mod 5)
  • x = 1 Þ y2 = 6 = 1 Þ y = 1,4 (mod 5)
  • x = 2 Þ y2 = 15 = 0 Þ y = 0 (mod 5)x = 3 Þ y2 = 36 = 1 Þ y = 1,4 (mod 5)x = 4 Þ y2 = 75 = 0 Þ y = 0 (mod 5)
  • Then points on the elliptic curve are (1,1) (1,4) (2,0) (3,1) (3,4) (4,0) and the point at infinity: ¥

ECDSA involves four elements

  1. All participants use the same global domain parameters .
  2. First public, private key pair is generated by sender. Signer selects a random or pseudorandom number for the private key. Signer computes another point on the elliptic curve using the random number and the point of origin and that is signer’s public key.
  3. A hash value is generated for the message to be signed. Signature is generated using the private key, the domain parameters and hash value. The signature consists of two integers r and s.
  4. To verify the signature, the verifier inputs signer’s public key, the domain parameters and the integer s. The output is a value v and is compared with r. The signature is verified if v=r.

Global Domain Parameters

  • Prime curves over Zp are used.
  • q – a prime number
  • a,b – integers that specify the elliptic curve equation defined over Zq with the equation y2=x3+ax+b
  • G – a base point represented by G=(xg,yg) on elliptic curve equation
  • n- order of point G. n is smallest positive integer such that nG=O. These are points on curve.

Simple elliptic curve

 

 

Encryption

  • Consider ‘m’ has the point ‘M’ on the curve ‘E’. Randomly select ‘k’ from [1 – (n-1)].
  • Two cipher texts will be generated let it be C1 and C2. C1 = k*PC2 = M + k*Q
  • C1 and C2 will be sent.

Decryption

  • M = C2 – d * C1  M is the original message that has been sent.

Proof

  • M = C2 – d * C1
  • ‘M’ can be represented as ‘C2 – d * C1’
  • C2 – d * C1 = (M + k * Q) – d * ( k * P )( C2 = M + k * Q and C1 = k * P )
  • = M + k * d * P – d * k *P ( canceling out k * d * P ) = M ( Original Message )

Key generation

  • Signer generates private and public key in following way.
  1. Select a random integer d, dε[1,n-1]
  2. Compute Q=dG. This is a point in Eq(a,b)
  3. Bob’s public key is Q and private key is d.

Digital signature generation and Authentication

  • Digital signature of 320 bytes for message m is generated using following steps:
  1. Select a random or pseudorandom integer k, kε[1,n-1]
  2. Compute point P=(x,y) =kG and r=x mod n. if r=0 then goto step 1
  3. Compute t=k-1 mod n
  4. Compute e=H(m) where H is the SHA-1 hash function, which produces a 160 bit hash function.
  5. Compute s=k-1 (e+dr) mod n. If s=O then goto step 1.
  6. The signature of message m is the pair (r,s)

The receiver having message m, digital signature – verifies the signature using following steps.

  1. Verify that r and s are integers in the range 1 through n-1
  2. Using SHA-1 compute the 160 bit hash value e=H(m)
  3. Compute w=s-1 mod n
  4. Compute u1=ew and u2=rw
  5. Compute the point X=(x1,y1)=u1G+u2Q
  6. If X=O, reject the signature else compute v=x1 mod n
  7. Accept Sender’s signature if and only if v=r. consider an elliptic curve over the field F23. Ref:https://www.certicom.com/index.php/31-example-of-an-elliptic-curve-group-over-fp
  • With a = 1 and b = 0, the elliptic curve equation is y2= x3 + x.
  • The point (9,5) satisfies this equation since: y2 mod p = x3 + x mod p

25 mod 23 = 729 + 9 mod 23

25 mod 23 = 738 mod 232 = 2

The 23 points which satisfy this equation are: (0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5)(13,18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10) (18,13) (19,1) (19,22) (20,4) (20,19) (21,6) (21,17)

All points on graph

 

1.  Point Addition, L = J + K

2.  Point Doubling, L = 2J Example:

If k = 23;

then, kP = 23*P= 2(2(2(2P) + P) + P) + P

Point Addition 🙁 Geometrically)

 

  • Consider two distinct points J and K such that J = (xJ, yJ) and K = (xK, yK) Let L = J + K where L = (xL, yL), then
  • xL = s2 – xJ – xK
  • yL = -yJ + s (xJ – xL)

s = (yJ – yK)/(xJ – xK), s is slope of the line through J and K

 

Consider a point J such that J = (xJ, yJ), where yJ ≠ 0  Let L = 2J where L = (xL, yL), Then

• xL = s2 – 2xJ
• yL = -yJ + s(xJ – xL)

 

s = (3xJ2 + a) / (2yJ), s is the tangent at point J and a is one of the parameters chosen with the elliptic curve

 

Suggested Reading:

  1. Cryptography and Network Security Principles and Practice by William Stallings, sixth Edition, PEARSON.
  2. Security in Computing by Charles Pfleeger & Shari Lawrence Pfleeger, fourth Edition, PEARSON.
  3. Network Security by Charlie Kaufman, Radia Perlman, Mike Speciner, second Edition, PHI.
  4. The Complete Reference – Network Security by Roberta Bragg, Mark Rhodes-Ousley & Keith Strassberg, Tata McGraw Hill
  5. Network Security Bible by Eric Cole, Ronald Krutz, James Conley, Wiley
  6. Hacking 6 Exposed by Stuart McClure, Joel Scambray & George Kurtz , Tata McGraw Hill .
  7. www.snort.org
  8. https://nmap.org