---

НАЦІОНАЛЬНИЙ СТАНДАРТ УКРАЇНИ

Інформаційні технології

КРИПТОГРАФІЧНИЙ ЗАХИСТ
ІНФОРМАЦІЇ
ЦИФРОВИЙ ПІДПИС, ЩО ҐРУНТУЄТЬСЯ
НА ЕЛІПТИЧНИХ КРИВИХ

Ф

БЗ № 12-2002/580

ормування та перевіряння

ДСТУ 4145-2002

Видання офіційне

Київ
ДЕРЖАВНИЙ КОМІТЕТ УКРАЇНИ
З ПИТАНЬ ТЕХНІЧНОГО РЕГУЛЮВАННЯ
ТА СПОЖИВЧОЇ ПОЛІТИКИ
200

3ПЕРЕДМОВА

1. РОЗРОБЛЕНО Малим підприємством «Дика»

ВНЕСЕНО Департаментом спеціальних телекомунікаційних систем та захисту інформації Служби Безпеки України

2. ЗАТВЕРДЖЕНО ТА НАДАНО ЧИННОСТІ наказом Державного комітету України з питань техніч­ного регулювання та споживчої політики від 28 грудня 2002 р. № 31

3. ВВЕДЕНО ВПЕРШЕ

4. РОЗРОБНИКИ: О. Шаталов (керівник розробки); А. Кочубінський, канд. фіз.-мат. наук

Право власності на цей документ належить державі.

Відтворювати, тиражувати і розповсюджувати цей документ повністю чи частково
на будь-яких носіях інформації без офіційного дозволу Державного комітету України
з питань технічного регулювання та споживчої політики заборонено.

Стосовно врегулювання прав власності звертатись до Державного комітету України
з питань технічного регулювання та споживчої політики

Державний комітет України з питань

технічного регулювання та споживчої політики, 2003

ЗМІСТ

с.

Вступ V

1. Сфера застосування 1

2. Нормативні посилання 1

3. Терміни та визначення понять 1

4. Позначення 5

5. Зображення даних і перетворення даних 6

   1. Зображення цілих натуральних чисел 6

   2. Зображення основного поля 6

   3. Зображення елементів основного поля 6

   4. Зображення еліптичної кривої 6

   5. Зображення точок еліптичної кривої 6

   6. Зображення результату обчислення функції гешування (геш-коду) 7

   7. Зображення цифрового підпису 7

   8. Перетворення елемента основного поля на ціле число 7

   9. Перетворення геш-коду на елемент основного поля 7

   10. Перетворення пари цілих чисел на цифровий підпис 7

   11. Перетворення двійкового рядка на пару цілих чисел 8

6. Обчислювальні алгоритми 8

   1. Генератор випадкових послідовностей 8

   2. Функція гешування 8

   3. Обчислення випадкового цілого числа 8

   4. Обчислення випадкового елемента основного поля 9

   5. Обчислення сліду елемента основного поля 9

   6. Обчислення напівсліду елемента основного поля 9

   7. Розв'язання квадратного рівняння в основному полі 9

   8. Обчислення випадкової точки еліптичної кривої 10

   9. Стискання точки еліптичної кривої 10

   10. Відновлення точки еліптичної кривої 10

   11. Перевіряння примітивності многочлена 11

   12. Перевіряння простоти порядку базової точки еліптичної кривої 11

   13. Перевіряння виконання умови Менезеса-Окамото-Венстона 11

7. Обчислення загальних параметрів цифрового підпису 12

   1. Вибір основного поля 12

   2. Вибір еліптичної кривої і порядку базової точки 13

   3. Обчислення базової точки еліптичної кривої 13

8. Перевіряння правильності загальних параметрів цифрового підпису 13

   1. Перевіряння правильності вибору основного поля 13

   2. Перевіряння правильності вибору рівняння еліптичної кривої і порядку базової точки 13

   3. Перевіряння правильності базової точки 14

9. Обчислення ключів цифрового підпису 14

   1. Обчислення особистого ключа цифрового підпису 14

   2. Обчислення відкритого ключа цифрового підпису 14

10. Перевіряння правильності ключів цифрового підпису 14

    1. Перевіряння правильності відкритого ключа цифрового підпису 15

    2. Перевіряння правильності особистого ключа 15

11. Обчислення цифрового передпідпису 15

12. Обчислення цифрового підпису 15

13. Перевіряння цифрового підпису 16

Додаток А Генератор випадкових двійкових послідовностей 17

Додаток Б Приклади обчислень цифрового підпису 18

Б.1 Обчислення й перевіряння цифрового підпису в поліноміальному базисі 18

Б.2 Обчислення й перевіряння цифрового підпису в оптимальному нормальному базисі 20

Додаток В Основні математичні поняття, які використано у стандарті 21

Додаток Г Рекомендовані еліптичні криві 28

Додаток Д Бібліографія ЗОВСТУП

Необхідність забезпечення надійного функціювання комп’ютеризованих систем оброблення інформації ставить високі вимоги щодо цілісності та автентичності даних, які надходять, збері­гаються та обробляються в цих системах. Автентифікація є процедура, яка встановлює досто­вірність твердження, що об’єкт (чи суб’єкт) має очікувані властивості. Зокрема, автентифікація повідомлення — перевіряння того, що повідомлення було передано без порушення цілісності з очікуваного джерела. Автентифікація здійснюється, виходячи з аналізу структури відповідних даних, за узгодженими алгоритмами.

Одним з найефективніших та найнадійніших підходів, які застосовуються для розв’язання задач, пов’язаних з автентифікацією даних та джерел повідомлень, є процедури цифрового підписування, побудовані на основі асиметричних криптографічних алгоритмів.

Цифровий підпис повідомлення — це блок даних невеликого розміру, одержаний в результаті криптографічного перетворення повідомлення довільної довжини з використанням особистого (таємного) ключа відправника. Процедура обчислення цифрового підпису побудована таким чи­ном, що кожний цифровий підпис має унікальну структуру, пов'язану з повідомленням та іденти­фікаційними даними власника особистого ключа. Перевіряння цифрового підпису полягає в уста­новленні істинності деяких алгебричних співвідношень між цифровим підписом та величинами, обчисленими за повідомленням, виходячи із зв’язку між відкритим та особистим ключами. Цей зв'я­зок не дає змоги відновити особистий ключ з відкритого. Таким чином, відкритий ключ є унікаль­ний параметр, що дає змогу здійснити перевірку цифрового підпису конкретної особи. Унікальність цифрового підпису і відкритого ключа означає, що обчислювально неможливо визначити особис­тий ключ цифрового підпису за доступними даними й обчислювально неможливо знайти два по­відомлення з однаковим цифровим підписом.

Цифровий підпис забезпечує автентичність повідомлення та неспростовність застосування особистого ключа (автентифікація власника цифрового підпису).

Цей стандарт установлює механізм цифрового підписування, що ґрунтується на властивостях груп точок еліптичних кривих над полями GF(2^m), та правила застосування цього механізму до пові­домлень, що їх пересилають каналами зв'язку та/або обробляють у комп’ютеризованих системах загального призначення.ДСТУ 4145-2002

НАЦІОНАЛЬНИЙ СТАНДАРТ УКРАЇНИ

ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ
КРИПТОГРАФІЧНИЙ ЗАХИСТ ІНФОРМАЦІЇ
ЦИФРОВИЙ ПІДПИС, ЩО ҐРУНТУЄТЬСЯ
НА ЕЛІПТИЧНИХ КРИВИХ

Формування та перевіряння

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ
ЦИФРОВАЯ ПОДПИСЬ, ОСНОВАННАЯ
НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ

Формирование и проверка
INFORMATION TECHNOLOGY
CRYPTOGRAPHIC TECHNIQUES
DIGITAL SIGNATURES BASED
ON ELLIPTIC CURVES

Generation and verification

Чинний від 2003-07-01

1. СФЕРА ЗАСТОСУВАННЯ

Цей стандарт установлює механізм цифрового підписування, що ґрунтується на властивостях груп точок еліптичних кривих над полями GF(2^m), та правила застосування цього механізму до пові­домлень, що їх пересилають каналами зв’язку та/або обробляють у комп’ютеризованих системах загального призначення. Застосування цього стандарту гарантує цілісність підписаного повідом­лення, автентичність його автора та неспростовність авторства.

2. НОРМАТИВНІ ПОСИЛАННЯ

У цьому стандарті є посилання на такі стандарти:

ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм крип­тографического преобразования.

ГОСТ 34.311-95 Информационная технология. Криптографическая функция хеширования.

З ТЕРМІНИ ТА ВИЗНАЧЕННЯ ПОНЯТЬ

Нижче подано визначення термінів, використаних у цьому стандарті.

en bit string [19]; fr iigne binaire [20]; ги двоичная строка [18]

Послідовність символів 0 і 1.

en bit string length [19]; fr longueur d’une Iigne binaire [20]; ru длина двоичной строки [18] Кількість символів, що складають двійковий рядок.

Видання офіційне

en concatenation [19], fr concatenation [20], ru конкатенация [18]

Конкатенація S||R двійкових рядків S та R є двійковий рядок, що утворюється з двійкового рядка S дописуванням до нього справа двійкового рядка R.

en message [19]; fr message [20]; ru сообщение [18]

Двійковий рядок довільної довжини L_T.

en hash function [19]; fr fonction de hachage [20]; ru функция хеширования [18]

Криптографічне перетворення повідомлення Т довільної довжини у двійковий рядок Н(Т) фіксо­ваної довжини L_H. Двійковий рядок Н(Т) називається результатом гешування або геш-кодом. Алго­ритм обчислення конкретної функції гешування може накладати обмеження на допустиму довжи­ну повідомлення L_T. Значення параметра L_H визначається конкретним алгоритмом обчислення функції гешування.

en random bit string [19]; fr ligne binaire aleatoire [20]; ru случайная двоичная строка [18]

Двійковий рядок, отриманий в результаті декількох звернень до генератора випадкових по­слідовностей, використання якого дозволено цим стандартом.

en digital signature [19]; fr signature numerique [20]; ru цифровая подпись [18]

Двійковий рядок D довжини L_d, обчислений за правилами, встановленими цим стандартом. Довжина L_d цифрового підпису визначається, виходячи з конкретних умов реалізації цього стан­дарту.

en prime field [19]; fr corps premier [20]; ru простое поле

Поле, що містить два елементи: 0 і 1.

en base field [19]; fr corps de base [20]; ru основное поле

Скінченне поле GF(2^m), яке є розширенням степеня т поля GF(2). За означенням це поле має характеристику 2. Допустимі значення степеня поля т визначаються цим стандартом. Прави­ла виконання операцій в основному полі наведено в додатку В.

en trace [19]; fr trace [20]; ru след

Значення виразу tr(х) = £х²’.

і-О

Слід елемента завжди дорівнює 0 або 1 і є елементом поля GF(2). Слід нульового елемента основного поля завжди дорівнює 0. Слід одиничного елемента основного поля дорівнює 1 тоді і тільки тоді, коли степінь основного поля т — непарне число.

en half trace [19]; fr demi-trace [20]; ru полуслед

Елемент основного поля, який обчислюється за формулою htr(x) = У, х⁴'.

en element order [19]; fr ordre d'un dldment [20]; ru порядок элемента [18]

Найменше натуральне число k, таке що х* = 1.

en primitive element [19]; fr element primitif [20]; ru примитивный элемент

де коефіцієнти многочлена f,e GF(2), / = 0,..., m-1.

en irreducible polynomial [19]; fr polynome irreductible [20]; ru неприводимый многочлен Многочлен ненульового степеня, що ділиться над полем GF(2) без залишку тільки на самого себе і многочлени нульового степеня.

en root of a polynomial [19]; fr racine d’un polynome [20]; ru корень многочлена Елемент x основного поля, такий що f(x)=O.

en primitive polynomial [19]; fr polynome primitif [20]; ru примитивный многочлен Незвідний многочлен, корені якого є примітивними елементами.

en primitive trinomial [19]; fr trindme primitif [20]; ru примитивный трехчлен Примітивний многочлен виду