На засіданні технічного комітету зі стандартизації "Криптографічний захист інформації" (ТК 26) затверджений проект документа "Методичні рекомендації за завданням параметрів еліптичних кривих відповідно до ГОСТ Р 34.10-2012", створеного фахівцями нашої компанії. У цій замітці розповідається про мету цього документа і про принципи вибору кривих, якими ми керувалися.

Першого січня 2013 року на території Росії введено новий стандарт процесів формування та перевірки електронного підпису ГОСТ Р 34.10-2012 [ 1 ], Покликаний замінити попередній стандарт ГОСТ Р 34.10-2001. Новий стандарт дозволяє працювати як з ключами електронного підпису довжини 256 біт (довжина відкритого ключа - 512 біт), так і з ключами довжини 512 біт (довжина відкритого ключа - 1024 біта) і повинен використовуватися виключно спільно з алгоритмом хешування ГОСТ Р 34.11-2012 [ 2 ]. Якби не останнє обмеження, можна було б сказати, що новий стандарт є лише розширенням старого для роботи з ключами 512 біт - справа в тому, що в частині процесів формування та перевірки підпису, створеної за допомогою ключа довжини 256 біт, новий і старий стандарти ідентичні.

Російський стандарт електронного підпису ГОСТ Р 34.10-2012, як і його попередник ГОСТ Р 34.10-2001, заснований на обчисленнях в групі точок еліптичних кривих і має структуру, близьку до схеми ECDSA. У певному сенсі ГОСТ Р 34.10-2001 і ГОСТ Р 34.10-2012 є аналогами ГОСТ Р 34.10-94 при заміні класу використовуваних циклічних груп з мультиплікативний груп простих полів на групи точок еліптичних кривих - точно так само, як ECDSA є аналогом DSA при аналогічних змінах . Схеми ГОСТ Р 34.10-94 і DSA по структурі перетворень, в свою чергу, близькі до класичної схеми підпису Ель-Гамаля (1984 рік), зокрема, грунтуються на тому ж класі теоретико-сложностних припущень про труднощі завдання знаходження дискретного полулогаріфма. Суворе обгрунтування стійкості ГОСТ Р 34.10-2001 (переносний без будь-яких змін на ГОСТ Р 34.10-2012) в умовах прийнятих у світовій криптографічного практиці припущень, можна знайти, наприклад, в роботі [ 3 ].

Отже, стійкість стандарту ГОСТ Р 34.10-2012 базується на труднощі вирішення задачі знаходження дискретного полулогаріфма в групі точок еліптичної кривої. Нагадаємо, що група точок еліптичної кривої над кінцевим полем лишків за модулем N - це безліч рішень рівняння y2 = x3 + ax + b mod N, де a і b є визначальними криву параметрами (наводиться опис в часто респонденти користуються послугами формі Вейерштрасса). Таким чином, для завдання кривої досить зафіксувати параметри N, a і b, а для використання зі стандартом ГОСТ Р 34.10-2012 також зафіксувати деяку її циклічну підгрупу і точку (x0, y0), що є породжує елементом цієї підгрупи.

Особливістю стандарту ГОСТ Р 34.10-2012 є те, що в документі не зафіксовано будь-які криві, рекомендовані для використання, присутній тільки набір вимог до них. Для конкретних прикладів кривих, наведених в стандарті, явно обумовлено, що вони повинні використовуватися суто в тестових цілях. У цьому наш стандарт істотно відрізняється, наприклад, від документа, що визначає схему ECDSA: в FIPS PUB 186-4 [ 4 ] Наведені рекомендовані (навіть з позначкою "для використання в державних установах") криві. З одного боку, даний підхід дозволяє зберігати стандарт незмінним навіть при появі нових результатів про "слабких" класах еліптичних кривих: досить буде перевірити нові обмеження для використовуваних на практиці кривих і при необхідності швидко провести їх заміну - але не міняти державний стандарт. З іншого боку, відсутність рекомендованих для використання параметрів вимагає додаткових дій від криптографічного спільноти з вибору й обгрунтування конкретних параметрів, а також узгодженням їх з регулюючими органами та створення методичних рекомендацій.

Як вже було зазначено, з точки зору алгоритмики роботи в групі точок еліптичної кривої в разі ключів довжини 256 біт новий стандарт ідентичний попередникові. Тому для спрощення переходу на новий стандарт було вирішено криві з модулем довжини 256 біт використовувати існуючі, описані в документі [ 5 ] І повсюдно впроваджені в існуючих криптографічних засобах.

Для кривих з модулем 512 біт було вирішено будувати криві виходячи з таких принципів:

• Мінімізація вимог до модифікації існуючих програмних і апаратних реалізацій ГОСТ Р 34.10-2001 (для кривих з модулем 256 біт) для роботи з новими кривими (з модулем 512 біт).
• Забезпечення найменшою трудомісткості операцій на нових кривих.
• Доказова псевдовипадковий нових кривих.

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

Відповідно до цих принципів була створена методика вироблення кривих, побудована навколо наступних ключових моментів:

• Для підвищення ефективності операцій в базових полях відрахувань визначають поля прості числа вибираються близькими до ступенями двійки (в нашому випадку, до 2511 і 2512).
• Криві вибираються в короткій формі Вейерштрасса, як і існуючі криві для довжини модуля 256 біт.
• Вибираються еліптичні криві з групою точок, що має порядок, рівний простому числу.
• Розглядаються тільки криві з коефіцієнтом a в формі Вейерштрасса рівному мінус трьох.
• Враховується вимога можливості певної верифікації "випадковості" кривої.

Вибір параметрів еліптичної кривої проводиться відповідно до принципу «перевіряється випадковості», що полягає у виробленні параметрів за допомогою односторонньої функції, або, на практиці, за допомогою деякого «важко» оборотного перетворення (в нашому випадку - на основі криптографічного хеш-функції ГОСТ Р 34.11 -2012). На вхід даного перетворення подаються випадкові рядки. В силу властивостей односторонньої функції, навіть спеціальний підбір вхідних рядків не дозволяє здійснювати вибір остаточних параметрів для приналежності певного класу свідомо "слабких" (хоча зауважимо, що вимоги до кривих, що пред'являються в тексті стандарту, вже гарантують відсутність приналежності кривих відомим класам "слабких" кривих ). Як параметр, значення якого належало рівним виходу хеш-функції, обраний параметр r = a 3 / b 2 mod N (див. [ 6 ]), Що задає два класи еквівалентних кривих.

Після породження r, фіксації a = -3 і вибору однієї з двох можливих кривих фіксацією b, необхідно перевірити весь набір необхідних в методиці властивостей. Велика частина з них перевіряється за параметрами a і b тривіальним чином (перевірками деяких співвідношень на a і b), деякі ж вимагають застосування дуже потужних і трудомістких алгоритмів (наприклад, для перевірки того факту, що порядок групи точок кривої є простим числом, використовується алгоритм Шуфа-ЕЛКІС-Аткіна (1985, 1988, 1991), з яким може знадобитися кілька хвилин машинного часу для перевірки однієї кривої). Після отримання кривої, що задовольняє всім перевірялися властивостями, залишається тільки вибрати її циклічну підгрупу і її породжує елемент - але так як порядок групи точок є простим числом, то цей крок тривіальний: вся група є циклічною, а будь-який її ненульовий елемент є породжує. Для додаткового прискорення обчислень при роботі на даній кривій в якості породжує елемента вибирається точка кривої (x0, y0) з малим значенням x0.

Отримані дві еліптичні криві отримали схвалення для використання з ГОСТ Р 34.10-2012; технічним комітетом із стандартизації "Криптографічний захист інформації" прийняті відповідні методичні рекомендації, кривим присвоєні об'єктні ідентифікатори. У КріптоПро CSP 4.0 дані еліптичні криві використовуються для повного спектра операцій, що використовують ключі алгоритму ГОСТ Р 34.10-2012 довжини 512 біт. І зрозуміло, все позитивні властивості цих еліптичних кривих, що були закладені нами на етапі розробки рекомендацій, використовуються в КріптоПро CSP 4.0 в повному обсязі.

література

1. ГОСТ Р 34.10-2012. Інформаційна технологія. Криптографічний захист інформації. Процеси формування та перевірки електронного цифрового підпису.

2. ГОСТ Р 34.11-2012. Інформаційна технологія. Криптографічний захист інформації. Функція хешування.

3. Варновскій Н.П. Стійкість схем електронного підпису в моделі з захищеним модулем. Дискретна математика, 2008, т. 20, вип. 3, с. 147-159.

4. FIPS PUB 186-4. FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION. Digital Signature Standard (DSS).

5. V.Popov, I. Kurepkin, S. Leontiev. RFC 4357. Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms.

6. ISO / IEC 15946-5: 2009. Information technology - Security techniques - Cryptographic techniques based on elliptic curves - Part 5: Elliptic curve generation.

завантажити проект документа "Методичні рекомендації за завданням параметрів еліптичних кривих відповідно до ГОСТ Р 34.10-2012".

завантажити з крипт з верифікацією затверджених наборів параметрів.

Смишляєв С.В., к.ф.-м.н.