Cryptography

Elliptic Curve Cryptography Problem #1

Given Cryptosystem Parameters:

·         E₁₁ (1, 6)

·         G = (2, 7)

·         B’s Secret Key: n_B = 7

To Find:

1.      B’s Public Key: P_B

2.      Given message P_m = (10, 9) and random value k = 3. Determine C_m

3.      Find P_m form C_m

Solution:

·         P_B = n_B * G = 7 (2, 7) = 2 (2 (2, 7) + (2, 7) ) + (2, 7)

2 (2,7)

λ = (3x_P² + a) / (2y_P) mod p 

λ = (3*2² + 1) / (2*7) mod 11

   = (13 mod 11/14 mod 11) mod 11 = (2/3) mod 11 = (2*3^-1) mod 11 = (2 * 4) mod 11

   = 8 mod 11

λ = 8

x_R = (λ² - x_P - x_Q) mod p

     = (8² – 2 - 2) mod 11 = (64-2-2) mod 11 = 60 mod 11 = 5

y_R = (λ (x_P - x_R) -y_P) mod p

     = (8 (2-5) – 7) mod 11 = (8 (-3) – 7) mod 11 = -31 mod 11 = 2

2 (2, 7) = (5, 2)

3 (2,7) = 2 (2, 7) + (2, 7) = (5, 2) + (2, 7)

λ = (y_Q – y_P) / (x_Q – x_P) mod p

λ = (7-2) / (2-5) mod 11 = (5/-3) mod 11 = (-5 * 3^-1) mod 11= (-5*4) mod 11

   = -20 mod 11 = 2

λ = 2

x_R = (λ² - x_P - x_Q) mod p

     = (2²-5-2) mod 11 = (4-5-2) mod 11 = (4-7) mod 11 = -3 mod 11 = 8

y_R = (λ (x_P - x_R) -y_P) mod p

     = (2(5-8)-2) mod 11 = (2(-3)-2) mod 11 = (-6-2) mod 11 = -8 mod 11 = 3

3 (2, 7) = (8, 3)

6 (2, 7) = 2 (2 (2, 7) + (2, 7) ) = 2 (8, 3)

λ = (3x_P² + a) / (2y_P) mod p 

λ = (3*8²) +1) / (2*3) mod 11 = ((192 mod 11 + 1) / 6) mod 11 = ((5+1) / 6) mod 11 = 1

λ = 1

x_R = (λ² - x_P - x_Q) mod p

     = (1²-8-8) mod 11 = -15 mod 11 = 7

y_R = (λ (x_P - x_R) -y_P) mod p

     = (1(8-7) -3) mod 11 = (1-3) mod 11 = -2 mod 11 = 9

6 (2, 7) = (7, 9)

7 (2, 7) = 6 (2, 7) + (2, 7) = (7, 9) + (2, 7)

λ = (y_Q – y_P) / (x_Q – x_P) mod p

λ = (7-9) / (2-7) mod 11 = (-2/-5) mod 11 = (2*5^-1) mod 11 = (2*9) mod 11 = 18 mod 11  

λ = 7

x_R = (λ² - x_P - x_Q) mod p

     = (7²-7-2) mod 11 = (49-7-2) mod 11 = 40 mod 11 = 7

y_R = (λ (x_P - x_R) -y_P) mod p

     = (7(7-7) – 9) mod 11 = -9 mod 11 = 2

7 (2, 7) = (7, 2)

 P_B = (7, 2) 

·         C_m = {kG, P_m+kP_B}

kG = 3 (2, 7)

      = (8, 3)      [See Previous Calculations]

kP_B  = 3 (7, 2) = 2(7, 2) + (7, 2)

2 (7, 2)

λ = (3x_P² + a) / (2y_P) mod p 

λ = (3*7²+1) / (2*2) mod 11 = (148/4) mod 11 = 37 mod 11 = 4

λ = 4

x_R = (λ² - x_P - x_Q) mod p

     = (4² – 7 – 7) mod 11 = (16-14) mod 11 = 2

y_R = (λ (x_P - x_R) -y_P) mod p

     = (4 (7-2) -2) mod 11 = (4(5) – 2) mod 11 = 18 mod 11 = 7

2 (7, 2) = (2, 7)

3(7, 2) = 2(7,2) + (7, 2) = (2, 7) + (7, 2)

λ = (y_Q – y_P) / (x_Q – x_P) mod p

λ = (2 – 7) / (7 – 2) mod 11 = (-5 / 5) mod 11 = -1 mod 11 = 10

λ = 10

x_R = (λ² - x_P - x_Q) mod p

     = (10² – 2 - 7) mod 11 = 91 mod 11 = 3

y_R = (λ (x_P - x_R) -y_P) mod p

     = (10 (2-3)) – 7) mod 11 = (-10-7) mod 11 = -17 mod 11 = 5

3(7, 2) = (3, 5)

kP_B = (3, 5)

P_m + kP_B     = (10, 9) + (3, 5)

λ = (y_Q – y_P) / (x_Q – x_P) mod p

λ = (5-9) / (3-10) mod 11 = (-4 / -7) mod 11 = 4*7^-1 mod 11 = (4*8) mod 11 = 10

λ = 10

x_R = (λ² - x_P - x_Q) mod p

     = (10² – 10 -3) mod 11 = 87 mod 11 = 10

y_R = (λ (x_P - x_R) -y_P) mod p

     = (10 (10-10) – 9) mod 11 = -9 mod 11 = 2

P_m + kP_B = (10, 2)

C_m = {kG, P_m+kP_B} = {(8, 3), (10, 2)}

·         Recovering Plaintext P_m

P_m = (P_m + kP_B) - (n_B * kG)

      = (10, 2) – 7 (8, 3)

7 (8, 3) = 2 (2(8, 3) + (8, 3)) + (8, 3)

2 (8, 3) = (7, 9)            [See Previous calculations]

(7, 9) + (8, 3)

λ = (y_Q – y_P) / (x_Q – x_P) mod p

λ = (3-9) / (8-7) mod 11 = -6 mod 11 = 5

λ = 5

x_R = (λ² - x_P - x_Q) mod p

     = (5² – 7 -8) mod 11 = 10 mod 11 = 10

y_R = (λ (x_P - x_R) -y_P) mod p

     = (5(7-10) – 9) mod 11 = (-15-9) mod 11 = -24 mod 11 = 9

3(8, 3) = (10, 9)

6(8, 3) = 2(10, 9)

λ = (3x_P² + a) / (2y_P) mod p 

λ = (3*10² + 1) / (2*9) mod 11 = 301 mod 11 / 18 mod 11 = 4 * 7^-1 mod 11

   = (4 * 8) mod 11 = 32 mod 11 = 10

λ = 10

x_R = (λ² - x_P - x_Q) mod p

     = (10² – 10 -10) mod 11 = 80 mod 11 = 3

y_R = (λ (x_P - x_R) -y_P) mod p

     = (10(10-3) -9) mod 11 = 61 mod 11 = 6

6(8, 3) = 2(10, 9) = (3, 6)

7(8, 3) = (3, 6) + (8, 3)

λ = (y_Q – y_P) / (x_Q – x_P) mod p

λ = (3-6) / (8-3) mod 11 = - 3*5^-1 mod 11 = (-3*9) mod 11 = -27 mod 11 = 6

λ = 6

x_R = (λ² - x_P - x_Q) mod p

     = (36-3-8) mod 11 = 25 mod 11 =3

y_R = (λ (x_P - x_R) -y_P) mod p

     = (6(3-3) – 6) mod 11 = -6 mod 11 = 5

7(8, 3) = (3, 5)

P_m = (10, 2) – 7(8, 3) = (10, 2) – (3, 5) = (10, 2) + (3, -5)

(10, 2) + (3, -5)

λ = (y_Q – y_P) / (x_Q – x_P) mod p

λ = (-5-2) / (3-10) mod 11 = (-7 / -7) mod 11 = 1

λ = 1

x_R = (λ² - x_P - x_Q) mod p

     = (1-10-3) mod 11 = -12 mod 11 = 10

y_R = (λ (x_P - x_R) -y_P) mod p

     = (1(10-10) -2) mod 11 = -2 mod 11 = 9

P_m = (10, 9)