---

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

Математичне підґрунтя для еліптичних кривих:

Еліптична крива Е є несингулярна кубічна крива, визначена на деякому полі К. Еліптична крива може бути наведена як множина рішень (х, у) (х, у є К) рівняння

У² = X³ + аХ + b

разом з особливою точкою q — точкою в нескінченності.

Еліптичні криві наділені властивостями бінарної дії °: Е ■ Е -> Е, приєднуючи до кожної пари (Р1, Р2) точок в Е третю точку Р1о Р2. Відносно цієї дії Е є Абелевою групою з нейтральним еле­ментом q.

Нехай Р є деякою точкою на еліптичній кривій Е, яка генерує циклічну групу <Р> із граничною чисельністю q відносно групової дії “о". Тоді кожен елемент із <Р> є деяким ступенем F^^k від Р, де Р¹⁴ є абревіатурою k-кратної операції (Р ° Р °... ° Р).

Дискретне піднесення до степеня F(, Р) на <Р> визначають як

F(k, Р) = Р*^к для к є {1,..., q - 1}.

Зазначимо, що для довільних h, к є {1,..., q - 1} виконується рівняння

якщо група <Р>, генерована Р, є Абелевою.

З іншого боку, якщо задана довільна точка Q є <Р>, то однозначно визначене ціле х є {1,..., q-1} таке, що Q = р№ означується як дискретний логарифм Q з основою Р.

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

Система познак:

У цьому додатку будемо дотримуватися термінології, введеної в попередньому розділі.

Крім того, зафіксуємо такі познаки:

К є скінченним полем, яке складається з точно р^п елементів, де р є простим числом, більшим за 3, а п — додатне ціле.

Е є еліптична крива на К і Р є точкою на Е, яка генерує циклічну групу <Р> із чисельністю q. Припускаємо, що q є простим числом і множина Н = {1,..., q - 1}.

Кожний суб’єкт X має особистий ключ h_xy Н, відомий лише X, і відкритий ключ Р_х= G^[hX], відо­мий всім іншим суб’єктам.

Зазначимо, що особисті ключі є суворо простими цілими, в той час як таємні — це точки на кривій. Цим система відрізняється від систем із відкритим ключем, основаним на дискретних логарифмах із простим модулем, де обидва ключі є об’єктами того самого типу. Ця різниця між двома типами ключів у випадку еліптичних кривих є причиною того, чому необхідно ввести додат­кову функцію, яка відображає точки <Р> в цілі в Н, якщо хтось бажає перевести протоколи додатка В в еліптичні криві.

Нехай я: <Р> ->Не функцією такою, що об’єднання я і F(°,P), задане як

к -> F¹^ -> n(F*^k])

односпрямоване.Примітка 1. Критичним параметром для безпеки системи із відкритим ключем на основі еліптичних кривих є величина простого числа q. Ціле q повинно бути достатньо великим, щоб F(°,P) могла вважатися односпрямованою функцією. Врахо­вуючи алгоритми, які існують на тепер, Р(° ,Р) є односпрямованою, якщо q > 2™.

Примітка 2. На відміну від систем, основаних на GFfp)* дискретних логарифмах (подібній до DSA), є можливість об­рати параметри q і р" приблизно однієї величини.

Примітка 3. Є ще декілька умов відносно простих р і q (наприклад, р * q) і параметрів кривої а і Ь, яких необхідно до­тримуватися, щоб зробити обчислення дискретного логарифма на еліптичній кривій неможливим.

Примітка 4. Є багато можливостей визначити %. Одним простим методом є виконати проекцію точок із <Р> на їх х-координати і «читати» ці елементи поля, як цілі по mod q.

С.1 Неінтерактивне узгодження ключа типу Діффі-Гелмана

Це приклад узгодження ключа механізму 1.

Конструювання ключа (А1)

З використанням свого власного особистого ключа узгодження ключів h_A і відкритого ключа узгодження ключів Р_вА обчислює розподілений ключ як

Кав = (Рв)^[М}.

Конструювання ключа (S1)

З використанням свого власного особистого ключа узгодження ключів h_B і відкритого ключа узгодження ключів Р_АВ обчислює розподілений ключ як

K_AB= (P_A)^[hB}.

С.2 Узгодження ключа типу ЕльГамаля

Це приклад узгодження ключа механізму 2.

Конструювання маркера ключа (А1)

А випадково і таємно генерує гвН, обчислює (Р_е)^и> конструює маркер ключа

КТ_Д1 = (Р)^[И

і надсилає його до В.

Конструювання ключа (А2)

А обчислює розподілений ключ

Кав = (Рв)^[И = Р¹^¹

Конструювання ключа (S1)

В обчислює зі своїм власним особистим ключем розподілений ключ із КТ_Л1 так

Кав = (КТ_А1)^[ЛЄ1 = = р^ІГЙВ’_

С.З Узгодження ключа за Нюберг-Рюппелем.

Це приклад узгодження ключа механізму 3.

Протокол не є копією один до одного протоколу ВЗ, але він слідує суттєвим ідеям ВЗ.

Систему підпису і систему узгодження ключів обирають так, щоб система підпису визнача­лася ключами (h_x, Рх)-

Щоб запобігти повторенню старих маркерів ключів, цей приклад використовує позначку часу або порядковий номер TVP, і криптографічну ґеш-функцію hash, яка відображає рядки бітів довільної довжини у випадкові цілі, наприклад в Н.

Конструювання ключа (А1.1)

А випадково і таємно генерує г в Н і обчислює

R = рМ

Додатково, А обчислює розподілений таємний ключ як

Кав = (Рв)^[И.

З використанням розподіленого таємного ключа К_АВ, А обчислює криптографічне контролю- вальне значення у точці R, на розрізнювальному ідентифікаторі посилана А і порядковому номері або позначці часу TVP

е = hash(RK_ABATVP).

Підпис маркера ключа (Д1.2)

А обчислює підпису - (r- h_A-e)modq формує маркер ключа

КТ_Д1 = (Я|И||Л/Р||у) і надсилає його до В.

Конструювання ключа (81.1)

З використанням свого особистого ключа узгодження ключа h_B, В обчислює розподілений таємний ключ

// _ UhB]
- К .

З використанням розподіленого таємного ключа К_АВ, В обчислює криптографічне контролю- вальне значення на розрізнювальному ідентифікаторі А та TVP і обчислює

е = К_ЛВ||А[|TVP).

Верифікація підпису (81.2)

В контролює достовірність TVP і верифікує з використанням відкритого ключа посилана Р_А тотожність

R = рМ<>(Р_А)^Іе]

С.4 Узгодження ключа типу Діффі-Гелмана

Це приклад узгодження ключа механізму 4.

Конструювання маркера ключа (Д1)

А випадково і таємно генерує г_А в Н і обчислює Р^гА конструює маркер ключа кт_л, = P™

надсилає його до В.

Конструювання маркера ключа (81)

В випадково і таємно генерує г_в в Н, обчислює P^[fB конструює маркер ключа

KT_S1 = Р™

надсилає його до А

Конструювання ключа (/12)

А обчислює розподілений ключ як

К_АВ⁼

Конструювання ключа (82)

В обчислює розподілений ключ як

Кав - (Р⁽'^Л])^[/в] = Р^[л4ИгЄ].

С.5 Узгодження ключа типа А(0) Мацумото-Такашима-Імаі

Це приклад узгодження ключа механізму 5.

Конструювання маркера ключа (А1)

А випадково і таємно генерує г_Ав Н, обчислює маркер ключа КТ_Д1 = Р*^гА]

і надсилає його до В.

Конструювання маркера ключа (81)

В випадково і таємно генерує г_в в Н, обчислює маркер ключа КТві = P^!rS]

і надсилає його до А.

Конструювання ключа (82)

В обчислює розподілений ключ як

К_дв = МКТл,'*⁸¹. p/^sl),

Конструювання ключа (Д2)

А обчислює розподілений ключ як

Кав = со(КТ_в1^[М1, Р/^В1).

С.6 Пересилання ключа типу ЕльГамаля

Це приклад передавання ключа механізму 1.

Конструювання маркера ключа (А1)

А отримав ключ К є Н і хоче передати його надійно до В.

А випадково і таємно генерує ціле г є Н, обчислює точку на кривій Р^ІГ1 і зашифровує К як

BE = (К л((Р_е^[г1)) mod q.

Потім А конструює маркер ключа

КТ_Л1 = ВЕ||Р^[Г1

і надсилає його до В.

Розібрання маркера ключа (В1)

Щоб відновити ключ К, суб’єкт В визначає з (P^[rl) із використанням свого особистого ключа узгодження ключа h_B, точку на кривій (P₀)^[r] = (P^[y^hB] і на наступному — проекцію tc((P_s)^w).

Остаточно В отримує ключ К обчисленням

К = (ВЕ)-(7г((РвТ^вІ)Г¹ modq.

С.7 Пересилання ключа типу ЕльГамаля з підписом автора

Це приклад передавання ключа механізму 2. Особистий і відкритий ключі узгодження ключів суб’єкта В є, відповідно, Л_в і

Рв = (P)^[hB1.

Особисте і відкрите перетворення підписування суб’єкта А, відповідно, означимо Sa і У_а; (Sa, V_a) можуть означувати будь-яку систему підпису, наприклад систему підпису, визначену в ISO/IEC 9796.

Зашифровування ключа (А1.1)

А отримав ключ К і хоче переслати його надійно до В. А випадково і таємно генерує ціле г є Н, точки на кривій F*^r P_s^[d і зашифровує блок даних ключа АЦК як

BE = (AK)-(n((PB^lr]))modq.

Зазначимо, що К треба обирати так, щоб значення (А||К) було меншим за просте число q.

Конструювання маркера ключа (Д1.2)

А формує блок даних маркера, який складається з розрізнювального ідентифікатора одержу­вача В, необов’язкової позначки часу або порядкового номера ТУРІ зашифрованого блоку BE. Потім А підписує блок даних маркера з використанням свого приватного перетворення підписування Sa і надсилає остаточний маркер ключа

КТаі = (В||ТУР||Р^[И||ВЕ)

і його підпис

SA(S||7VP|rtBE)

ДО В.

Верифікація маркера ключа (£31.1)

В використовує відкрите перетворення верифікації посилана Va для верифікації цифрового підпису одержаного маркера ключа КТаі. Потім В контролює ідентифікацію одержувача В і, нео­бов’язково, TVP.

Розшифровування ключа (В1.2)

В розшифровує блок BE з використанням свого особистого ключа узгодження ключа h_B об­численням

(АЦК) = (ВЕ)-(тг((Р_в^и)^thfl1))-¹ modq.

Потім В контролює ідентифікацію посилана А. Якщо всі перевірки успішні, В приймає ключ К.ДОДАТОКD

(довідковий)

БІБЛІОГРАФІЯ

1. ANSI Х9.30 199х, Public Key Cryptography Using Irreversible Algorithms for the Financial Servi­ces Industry, Part 1: The Digital Signature Algorithm (DSA)

2. ANSI X9.30 199x, Public Key Cryptography Using Irreversible Algorithms for the Financial Servi­ces Industry, Part 3: Certificate Management for DSA

3. ANSI X9.31 199x, Public key cryptography using reversible algorithms for the financial services industry — Pan 4: Management of symmetric algorithm keys using RSA

4. Beller M.J., Yacobi Y., Fully-fledged two-way public authentication and key agreement for low- cost terminals. Electronic Letters, Vol. 29, no. 11 (27 May 93), pp 999—1001

5. RIPE, Integrity Primitives for Secure Information Systems — Final Report of RACE Integrity Primitives Evaluation (RIPE-RACE 1040), LNCS 1007, A. Bos-selaers, B. Preneel, Eds., Springer-Verlag, 1995

6. Diffie W., Hellman M.E., New Directions in Cryptography, IEEE Trans, on Inform. Theory, vol. IT- 22, pp. 644—654, Nov. 1976

7. EIGamal, T., A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans, on Inform. Theory, vol. IT-31, pp. 469—472, July 1985

8. Girault M., Pailles J.C., An identity-based scheme providing zero-knowledge authentication and authenticated key exchange. Proceedings of ESORICS 90, pp. 173—184

9. ISO 8732:1988, Banking — Key Management (Wholesale)

10. ISO/IEC 9594-8:1990, (CCITT X.509), Information technology — Open Systems Interconnection — The Directory — Authentication framework

11. ISO/IEC 9796:1991 Information technology — Security techniques — Digital signature scheme giving message recovery

12. ISO/IEC 9797:1994 Information technology — Security techniques - Data integrity mechanism using a cryptographic check function employing a block cipher algorithm

13. ISO/IEC 10118-2:1994 Information technology — Security techniques — Hash-functions — Part 2: Hash-functions using an n-bit block cipher algorithm

14. ISO/IEC 10118-3:1998 Information technology — Security techniques — Hash-functions — Part 3: Dedicated hash functions

15. ISO/IEC 10118-4:1998 Information technology— Security techniques — Hash-functions — Part 4: Mechanisms using modular arithmetic

16. ISO 11166-1:1994 Banking — Key Management by means of asymmetric algorithms — Part 1: Principles, Procedures and Formats

17. Matsumoto T., TakashimaY, Imai H., On Seeking Smart Public-Key-Distribution Systems, Trans, of the IECE of Japan, vol.E69 no.2, Feb. 1986 pp. 99—106

18. Menezes A., Elliptic Curve Public Key Cryto-systems, Kluwer Academic Publishers, 1993

19. Nyberg K., Rueppel R.A., Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem, Proceedings of Eurocrypt’94, Springer-Verlag, 1994

20. Okamoto E., Proposal for identity-based key distribution system. Electronic Letters, Vol. 22, n°24, 20 Nov. 86, pp. 1283—4

21. Tanaka K., Okamoto E., Key distribution system for mail systems using ID-related information directory, Computers & Security, Vol.10, 1991, pp. 25—33

22. ISO/IEC 10118-2:1994 Information technology — Security techniques — Hash-functions — Part 2: Hash-functions using an n-bit block cipher algorithm

23. ISO/IEC 10118-3:1998 Information technology — Security techniques — Hash-functions — Part 3: Dedicated hash functions

24. ISO/IEC 10118-4:1998 Information technology — Security techniques — Hash-functions — Part 4: Mechanisms using modular arithmetic