Вычисление множества точек удвоения заданной эллиптической кривой

Для вычисления открытого ключа абонента-отправителя сообщения «М» К_ОА изначально необходимо вычислить все удвоения генераторной точки «G» до [128] G, т.к. число 128 является максимальным числом степени 2ⁿ в составе числового значения закрытого ключа К_ЗА = 236. Значение закрытого ключа К_ЗА по числам 2ⁿ можно отобразить как 236 = 4 + 8 + 32 + 64 + 128, т.е. на первом этапе для вычисления открытого ключа абонента-отправителя сообщения «М» К_ОА = [К_ЗА] G = [236] G необходимо вычислить следующие точки удвоения: [4] G; [8] G; [32] G; [64] G; [128] G, а затем вычислить все композиции полученных числовых значений. Методика вычисления операций удвоения и композиций была изложена в разделе «Основные операции криптографических преобразований в метрике эллиптических кривых».

После вычисления множеств удвоения генераторной точки «G» по значению максимального нижнего предела степени 2ⁿ, т.е. n = 7 2ⁿ ≤ 236;

128 ≤ 236 определяется композиция полученного множества. Следовательно, К_ОА = [К_ЗА] G = [236] G = [4] G + [8] G + [32] G + + [64] G + [128] G.

Вычисление удвоения генераторной точки G (X₁; Y₁) = G (18; 11) → [2] G:

- Вычисляется угловой коэффициент касательной заданной эллиптической кривой Z_P (a; b): Y² = X³ + 8*X + 5 mod 293 в генераторной точке G(X₁; Y₁) = G(18; 11):

K = mod P = mod 293 = mod 293 = 980 * 22^-1 mod 293 = 980 * 22²⁹¹ mod 293 = 980 * 40 mod 293 = 39200 mod 293 = 231 mod 293 → 231.

- Вычисляются координаты удвоения генераторной точки G - [2]G = G(X₂; Y₂) (координаты генераторной точки «G» определены выше G(X₁; Y₁) = G(18; 11)):

X₂ = (K² – 2X₁) mod P = (231² - 2*18) mod 293 = 292 mod 293 → 292;

Y₂ = (K*(X₁ – X₂) – Y₁) mod P = (231*(18 – 292) – 11) mod 293 =

= 276 mod 293 → 276.

Следовательно, [2]G = (X₂; Y₂) = (292; 276), координаты точки [2]G определены как X₂ = 292; Y₂ = 276.

Вычисление операции удвоения полученной точки [2]G, т.е. вычисление точки [4]G = (X₄; Y₄):

- вычисление углового коэффициента касательной в точке [2]G = (X₂; Y₂) = (292; 276)

K = mod P = mod 293 = 60 mod 293 → 60.

- вычисление координат точки [4]G = (X₄; Y₄)

X₄ = (K² – 2X₂) mod P = (60² - 2*292) mod 293 = 86 mod 293 → 86;

Y₄ = (K*(X₂ – X₄) – Y₂) mod P = (60*(292 – 86) – 276) mod 293 =

= 71 mod 293 → 71.

Следовательно, [4]G = (X₄; Y₄) = (86; 71), координаты точки [4]G определены как X₄ = 86; Y₄ = 71.

Вычисление координат точки [8]G, как результат удвоения точки [4]G:

- вычисление углового коэффициента касательной в точке [4]G = (X₄; Y₄) = (86; 71)

K = mod P = mod 293 = mod 293 = 22196 * 142^-1 mod 293 = 22196 * 142²⁹¹ mod 293 = 22196 * 130 mod 293 = 221 * 130 mod 293 = 28730 mod 293 = 16 mod 293 → 16.

- вычисление координат точки [8]G = (X₈; Y₈)

X₈ = (K² – 2X₄) mod P = (16² - 2*86) mod 293 = 84 mod 293 → 84;

Y₈ = (K*(X₄ – X₈) – Y₄) mod P = (16*(86 – 84) – 71) mod 293 =

= 254 mod 293 → 254.

Следовательно, [8]G = (X₈; Y₈) = (84; 254), координаты точки [8]G определены как X₈ = 84; Y₈ = 254.

Вычисление координат точки [16]G, как результат удвоения точки [8]G:

- вычисление углового коэффициента касательной в точке [8]G = (X₈; Y₈) = (84; 254)

K = mod P = mod 293 = mod 293 = 21176 * 508^-1 = 21176 * 508²⁹¹ mod 293 = 80 * 154 mod 293 = 12320 mod 293 =

= 14 mod 293 → 14.

- вычисление координат точки [16]G = (X₁₆; Y₁₆)

X₁₆ = (K² – 2X₈) mod P = (14² - 2*84) mod 293 = (196 – 168) mod 293 =

= 28 mod 293 → 28;

Y₁₆ = (K*(X₈ – X₁₆) – Y₈) mod P = (14*(84 – 28) – 254) mod 293 = (784 – 254) mod 293 = 530 mod 293 = 237 mod 293 → 237.

Следовательно, [16]G = (X₁₆; Y₁₆) = (28; 237), координаты точки [16]G определены как X₁₆ = 28; Y₁₆ = 237.

Вычисление координат точки [32]G, как результат удвоения точки [16]G:

- вычисление углового коэффициента касательной в точке [16]G = (X₁₆; Y₁₆) = (28; 237)

K = mod P = mod 293 = mod 293 = 2360 * 474^-1 mod 293 = 2360 * 474²⁹¹ mod 293 = 16 * 34 mod 293 = 544 mod 293 =

= 251mod 293 → 251.

- вычисление координат точки [32]G = (X₃₂; Y₃₂)

X₃₂ = (K² – 2X₁₆) mod P = (251² - 2*28) mod 293 = (63001 – 56) mod 293 = = 62945 mod 293 = 243 mod 293 → 243;

Y₃₂ = (K*(X₁₆ – X₃₂) – Y₁₆) mod P = (251*(28 – 243) – 237) mod 293 = - 54202 mod 293 = - 290 mod 293 = (293 – 290) mod 293 = 3 mod 293 → 3.

Следовательно, [32]G = (X₃₂; Y₃₂) = (243; 3), координаты точки [32]G определены как X₃₂ = 243; Y₃₂= 3.

Вычисление точки [64]G, как результат удвоения точки [32]G:

- вычисление углового коэффициента касательной в точке [32]G = (X₃₂; Y₃₂) = (243; 3)

K = mod P = mod 293 = 177155 * 6^-1 mod 293 =

= 177155 * 6²⁹¹ mod 293 = 183 * 49 mod 293 = 8967 mod 293 = 177 mod 293 → 177.

- вычисление координат точки [64]G = (X₆₄; Y₆₄)

X₆₄ = (K² – 2X₃₂) mod P = (177² - 2*243) mod 293 = 30843 mod 293 = 78 mod 293 → 78;

Y₆₄ = (K*(X₃₂ – X₆₄) – Y₃₂) mod P = (177*(243 – 78) – 3) mod 293 = 29202 mod 293 = 195 mod 293 → 195.

Следовательно, [64]G = (X₆₄; Y₆₄) = (78; 195), координаты точки [64]G определены как X₆₄ = 78; Y₆₄ = 195.

Вычисление точки [128]G, как результат удвоения точки [64]G:

- вычисление углового коэффициента касательной в точке [64]G = (X₆₄; Y₆₄) = (78; 195)

K = mod P = mod 293 = mod 293 = 18260 * 390²⁹¹ = 94 * 145 mod 293 = 13630 mod 293 = 152 mod 293 → 152.

- вычисление координат точки [128]G = (X₁₂₈; Y₁₂₈)

X₁₂₈ = (K² – 2X₆₄) mod P = (152² - 2*78) mod 293 = 22948 mod 293 = 94 mod 293 → 94;

Y₁₂₈ = (K*(X₆₄ – X₁₂₈) – Y₆₄) mod P = (152*(78 – 94) – 195) mod 293 =

= 10 mod 293 → 10.

Следовательно, [128]G = (X₁₂₈; Y₁₂₈) = (94; 10), координаты точки [128]G определены как X₁₂₈ = 94; Y₁₂₈ = 10.