Вычисление композиций точек удвоения [4]G; [8]G; [32]G; [64]G; [128]G заданной эллиптической кривой

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

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

Вычисление композиции точек [64]G и [128]G; [64]G + [128]G = [192]G = (X₁₉₂; Y₁₉₂). ( [64]G = (X₆₄; Y₆₄) = (78; 195); [128]G = (X₁₂₈; Y₁₂₈) = (94; 10))

- Вычисляется угловой коэффициент прямой, проходящей через точки [64]G и [128]G заданной эллиптической кривой:

K = mod P = mod 293 = - 185 * 16^-1 mod 293 = - 18 * 16²⁹¹ mod 293 = - 185 * 55 mod 293 = - 10175 mod 293 = -213 mod 293 = (293-213) mod 293 = 80 mod 293 → 80.

- Вычисляются координаты точки [192]G = (X₁₉₂; Y₁₉₂):

X₁₉₂ = (K² – X₆₄ – X₁₂₈) mod P = (80² – 78 – 94) mod 293 = 6228 mod 293 = 75 mod 293 → 75.

Y₁₉₂ = (K*(X₁₂₈ – X₁₉₂) – Y₁₂₈) mod P = (80* (94 – 75) – 10) = 1510 mod 293 = 45 mod 293 → 45

Следовательно, [192]G = (X₁₉₂; Y₁₉₂) = (75; 45), координаты точки [192]G определены как X₁₉₂ = 75; Y₁₉₂ = 45.

Вычисление композиции точек [192]G и [32]G; [192]G + [32]G = [224]G = (X₂₂₄; Y₂₂₄). ([192]G = (X₁₉₂; Y₁₉₂) = (75; 45); [32]G = (X₃₂; Y₃₂) = (243; 3)).

- Вычисляется угловой коэффициент прямой, проходящей через точки [32]G и [192]G заданной эллиптической кривой:

K = mod P = mod 293 = - 42 * 168^-1 mod 293 = - 42 * 168²⁹¹ mod 293 = 251 * 75 mod 293 = 18825 mod 293 = 73 mod 293 → 73.

- Вычисляются координаты точки [224]G = (X₂₂₄; Y₂₂₄):

X₂₂₄ = (K² – X₁₉₂ – X₃₂) mod P = (73² – 75 – 243) mod 293 = 30 mod 293 → 30.

Y₂₂₄ = (K*(X₁₉₂ – X₂₂₄) – Y₁₉₂) mod P = (73* (75 – 30) – 45) mod 293 =

= 17 mod 293 → 17.

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

Вычисление композиции точек [224]G и [8]G; [224]G + [8]G = [232]G = (X₂₃₂; Y₂₃₂). ([224]G = (X₂₂₄; Y₂₂₄) = (30; 17); [8]G = (X₈; Y₈) = (84; 254)).

- Вычисляется угловой коэффициент прямой, проходящей через точки [224]G и [8]G заданной эллиптической кривой:

K = mod P = mod 293 = mod 293 = 237 * 54^-1 mo293 = = 237 * 54²⁹¹ mod 293 = 237 * 38 mod 293 = 9006 mod 293 = 216 mod 293 → 216.

- Вычисляются координаты точки [232]G = (X₂₃₂; Y₂₃₂):

X₂₃₂ = (K² – X₂₃₂ – X₈) mod P = (216² – 30 – 84) mod 293 = 46542 mod 293 = 248 mod 293 → 248.

Y₂₃₂ = (K*(X₂₂₄ – X₂₃₂) – Y₂₂₄) mod P = (216* (30 – 248) – 17) mod 293 =

= - 47105 mod 293 = - 225 mod 293 = (293 – 225) mod 293 = 68 mod 293 → 68.

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

Вычисление композиции точек [232]G и [4]G; [232]G + [4]G = [236]G = (X₂₃₆; Y₂₃₆);. ([232]G = (X₂₃₂; Y₂₃₂) = (248; 68); [4]G = (X₄; Y₄) = (86; 71)).

- Вычисляется угловой коэффициент прямой, проходящей через точки [232]G и [4]G заданной эллиптической кривой:

K = mod P = mod 293 = - mod 293 = - 3 * 162^-1 mod 293 = - 3 * 162²⁹¹ mod 293 = -3 * 208 mod 293 = - 624 mod 293 = - 38 mod 293 = (293 – 38) mod 293 = 255 mod 293 → 255.

- Вычисляются координаты точки [236]G = (X₂₃₆; Y₂₃₆):

X₂₃₆ = (K² – X₂₃₂ – X₄) mod P = (255² – 248 – 86) mod 293 = 64691 mod 293 = = 231 mod 293 → 231.

Y₂₃₆ = (K*(X₂₃₂ – X₂₃₆) – Y₂₃₂) mod P = (255* (248 – 231) – 68) mod 293 =

= 4267 mod 293 = 165 mod 293 → 165.

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

В результате выполнения операций удвоения и композиций детерминированных множеств точек заданной эллиптической кривой определены координаты точки открытого ключа абонента «А», а, следовательно, и сам открытый ключ К_ОА = [К_ЗА]G = [236]G = (X₂₃₆; Y₂₃₆) = (231; 165). Открытый ключ абонента «А» К_ОА выбирается как значение абсциссы X₂₃₆ = 231, т.е. К_ОА = 231.

Абонент А передает абоненту В заданные параметры эллиптической кривой (P = 293; a = 8; b = 5), координаты генераторной точки G = (X_G; Y_G) = (18; 11) и координаты своего открытого ключа К_ОА = [К_ЗА]G = [236]G = (X₂₃₆; Y₂₃₆) = (231; 165) открыто по открытым каналам связи для аутентификации им принимаемых электронных сообщений, получаемых от абонента «В».

4. Действие абонента-отправителя (абонента «А») по формированию электронной цифровой подписи электронного сообщения «М».

Как и для случая формирования криптограмм открытого сообщения «М» считается, что параметры эллиптической кривой «а», «b» и модуль «Р» заданы. Для выполнения операции постановки электронной цифровой подписи и аутентификации принимаемых сообщений каждый участник электронного обмена на своем рабочем компьютере формируют секретные и открытые ключи. После чего абонент-отправитель с помощью своего закрытого (секретного) ключа формирует ЭЦП передаваемого электронного сообщения. Проверка подлинности (аутентификация) электронного сообщения осуществляется абонентом «В» с помощью открытого ключа абонента-отправителя «А».

Для формирования электронной цифровой подписи необходимо:

4.1. Изначально вычислить числовое значение функции хеширования h_В(M) передаваемого сообщения «М» (ГОСТ Р34.11-94). Для примера в качестве сообщения «М» задается слово «Криптон», функция хеширования слова «Криптон» имеет вид:

h_В(M) → { 52 48 52 48 50 42 46 46 40 56 48 48 50 54 46 42 52 56 56 52 50 50 50 50 44 52 48 48 54 50 46 42}.

4.2. Для составления криптограммы числовых значений функции хеширования h_В(M) абонент-отправитель задает случайным образом целое положительное число «К» при соблюдении следующих ограничений 1 < К < Р (для примера принимается значение К=347) и НОД (К; (Р-1)) = 1. Принимаются (для примера) следующие значения параметров эллиптической кривой:

Р =293; а = 8; b = 5

4.3. Вычисляется параметр N = [К]G = [347]G = (X_N; Y_N). N = [347]G = [347](18;11).

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

Для вычисления N изначально необходимо вычислить все удвоения точки G до [256]G, т.к. число 256 является максимальным числом степени 2ⁿ в составе числа 347 (К = 347). Значение числа К =347 числам 2ⁿ можно отобразить как 347 = 256 + 64 + 16 + 8 + 2 + 1, т.е. на первом этапе для вычисления параметра «К» необходимо вычислить следующие точки удвоения точки G: [2]G, [8]G, [16]G, [64]G, [256]G.

После вычисления множеств удвоений генераторной точки G необходимо значение их композиции. Если N = 347, то максимальный нижний предел по степени 2ⁿ = 2⁸, т.е. n = 8; 2⁸ ≤ 347; 256 ≤ 347. Следовательно:

N = [К]G = [347]G = G + [2]G + [8]G + [16]G + [64]G + [256]G, т.е. композиция чисел, определяющих значение N = [347]G, будет включать в себя значение G + [2]G + [8]G + [16]G + [64]G + [256]G. Указанные значения удвоений генераторной точки G были вычислены в разделе 3.1:

G(X₁; Y₁) = G(18;11); [2]G = (X₂; Y₂) = (292; 276); [4]G = (X₄; Y₄) = (86; 71);

[8]G = (X₈; Y₈) = (84; 254); [16]G = (X₁₆; Y₁₆) = (28; 237); [32]G = (X₃₂; Y₃₂) = (243; 3); [64]G = (X₆₄; Y₆₄) = (78; 195); [128]G = (X₁₂₈; Y₁₂₈) = (94; 10).

Указанное множество необходимо дополнить значение точки [256]G для вычисления композиции, отображающей значение точки N = [347]G, т.е.

[347]G = G + [2]G + [8]G + [16]G + [64]G + [256]G.

Вычисление координат точки [256]G заданной эллиптической кривой как результат удвоения точки [128]G = (X₁₂₈; Y₁₂₈) = (94; 10):

- вычисление значения углового коэффициента касательной в точке [128]G = (X₁₂₈; Y₁₂₈) = (94; 10):

к = mod P = mod 293 = mod 293 =

= 26516 * 20^-1 mod 293 = 146 * 20²⁹¹ mod 293 = 146 * 44 mod 293 =

= 6424 mod 293 = 271 mod 293 → 271.

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

X₂₅₆ = (K² – 2X₁₂₈) mod P = (271² - 2*94) mod 293 = (73441 – 188) mod 293 = 3 mod 293 → 3;

Y₂₅₆ = (к * (X₁₂₈ – X₂₅₆) – Y₁₂₈) mod P = (271* (94 – 3) – 10) mod 293 =

= 24651 mod 293 = 39 mod 293 → 39.

Следовательно, [256]G = (X₂₅₆; Y₂₅₆) = (3; 39), координаты точки [256]G определены как X₂₅₆ = 94; Y₂₅₆ = 10.