Страница 7: ДСТУ 4145-2002. Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що грунтується на еліптичних кривих. Формування та перевіряння (62765)

Цей елемент називається нейтральним елементом групи. У мультиплікативному запису ней­тральний елемент називається одиничним елементом групи, в адитивному запису він називається нульовим елементом групи.

• Для кожного елемента а групи існує єдиний обернений елемент <7“¹ (в адитивному запису єдиний протилежний елемент -а), такий що

аа~^л= а~^Аа = 1 (а + (-а) = (-«) + « = 0).

Вираз а + (- Ь) скорочено записується а - b і така операція називається відніманням. Якщо п — натуральне число, то добуток п елементів а позначається а^п. За означенням я° = 1, а~^л= («^-1)^п. Операція обчислення а^п називається піднесенням елемента а до степеня п. В адитивному запису групи сума п елементів а позначається па і операція обчислення цієї суми називається множен­ням елемента а на натуральне число п. За означенням 0« = 0, (-п)а = п(-а).

Число елементів групи N називається порядком групи. Завжди a^N=' (Na = 0). Найменше натуральне число п таке, що в мультиплікативному запису а^П = 1, а в адитивному запису па = 0, називається порядком елемента а. Порядок елемента завжди ділить порядок групи. Елемент а порядку п породжує циклічну підгрупу Н порядку п групи G вигляду

Н = {1,а,(7²,..._|«^л_1} або Н = {0,а,2а,..., (п-1)а).

Елемент а називається твірним елементом циклічної групи або примітивним елементом.

Задача розв’язання рівняння виду

b = а^к, be Н, 0 < к< п або

b = ka, be H_t 0 < к<п

відносно к називається задачею дискретного логарифмування в групі Н.

Скінченним полем (полем Галуа) називається скінченна множина F_q= GF(q), що містить q елементів і в якій визначено дві операції, одна з яких записується адитивно, а інша — мультипли­кативно. Відносно адитивної операції множина F_q є скінченною абелевою групою. Відносно муль- типлікативної операції скінченною абелевою групою є множина ненульових елементів F_q. Ці дві операції пов’язані між собою відношеннями дистрибутивності: для будь-яких елементів поля х, у, z виконується х(у + z) = ху + xz. Число елементів поля називається порядком поля. Порядок скінчен­ного поля завжди є степенем деякого простого числа, q = p^m, число т називається степенем поля, а просте число р — його характеристикою. Мультиплікативна група скінченного поля є циклічною групою порядку р^т-1, її твірний елемент називається примітивним елементом поля.

У стандарті використано скінченні поля GF(2^m) характеристики 2, q = 2^m, степінь розширення т — просте число, 163 < т < 509. Нульовий елемент скінченного поля позначається символом 0, одиничний елемент скінченного поля позначається символом 1. У полі характеристики 2 проти­лежним для елемента х є сам елемент х. Таким чином, у такому скінченному полі операції дода­вання й віднімання ідентичні.

Найпростішим скінченним полем є скінченне поле GF(2), яке складається з двох елементів 0 і 1. У цьому полі операції додавання й множення виконуються наступним чином: 0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1+1=0, 00=10 = 0-1=0, 1-1 = 1. Будь-яке скінченне поле GF(2^m) є л?-вимірним векторним простором над полем GF(2).

Многочлен f(t) степеня т над полем GF(2) є многочлен вигляду f(t) = t^m+ + ...+ fg,

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

Операції над такими многочленами виконуються як операції над звичайними многочленами, тільки операції над коефіцієнтами виконуються в полі GF(2). Зокрема, многочлен g(t) ділиться з залишком r(t) на многочлен f(f), якщо g(t) = + r(t), де степінь многочлена r(t) менший

за степінь многочлена f(t). Многочлен h(t) називається неповною часткою. Операція обчислення залишку від ділення многочлена g(t) на многочлен f(t) називається зведенням многочлена g(t) за модулем f(f) і позначається g(t) mod f(t). Якщо r(t) = O, то многочлен g(t) ділиться на многочлен f(t) без залишку. Многочлени h(t) і g(t) конгруентні за модулем многочлена f(t), f(t)*O, якщо много­член h(t)-g(t} ділиться на многочлен f(t} без залишку, записується h(t) = g(t) mod f(t).

Многочлен f(t) ненульового степеня називається незвідним над полем GF(2), якщо він ділиться без залишку над цим полем тільки на самого себе і на многочлени нульового степеня. Елемент х скінченного поля GF(2^m) називається коренем многочлена f(t), якщо f(x) = O. Незвідний многочлен f(t) називається примітивним, якщо його корені є примітивними елементами поля.

Примітивним тричленом називається примітивний многочлен виду

f(t) = t^m+ t^k+ 1, 0<к<т.

Примітивним п’ятичленом називається примітивний многочлен виду

f(t) = t^m+ t¹+ t^k + 1, 0 <k<j<l< т.

Якщо х — корінь незвідного многочлена f(t) степеня т, то елементи (х"’^-1,..., 1) утворюють базис скінченного поля GF(2^m) як векторного простору над полем GF(2). Цей базис називається поліноміальним. Будь-який елемент основного поля однозначно виражається через елементи полі- номіального базису. Найзручніше поліноміальний базис задавати примітивним многочленом.

Якщо х — такий елемент основного поля GF(2^m), що елементи основного поля (х, х²,..., х² ) лінійно незалежні над GF(2), то ці елементи утворюють базис поля GF(2^m), який називається нормаль­ним. Нормальний базис існує для кожного скінченного поля характеристики 2. Нормальний базис називається гаусівським оптимальним нормальним базисом типу 2, якщо число р’-2т+ 1 — просте і для найменшого натурального числа к, такого що 2^к = 1 mod (д'), виконується одна з на­ступних умов:

1. к=2т

2. р'=3 mod 4 і к-т.

Надалі гаусівський оптимальний нормальний базис типу 2 називається просто оптимальним нормальним базисом. Оптимальний нормальний базис існує не для всіх скінченних полів характе­ристики 2. Якщо такий базис існує, то він однозначно задається степенем т основного поля. Елементи оптимального нормального базису є коренями деякого незвідного многочлена p(f), який називається нормальним многочленом скінченного поля. Цей многочлен утворюють таким чином:

1. Приймають q(t} = 1, p(t) = t + 1.

2. Від 1 до m-1 обчислюють: r(t) = q(t); q(t) = p(t); p(t) = tq(t} + r(t).

Слідом tr(x) елемента x скінченного поля називається елемент цього поля, рівний їг(х) = £х² .

/=о

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

Напівслідом htr(x) елемента х основного поля непарного степеня т називається елемент цього / І ! поля, рівний htr(x)= х⁴ • /=0

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

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

Множення двох елементів скінченного поля виконується як множення відповідних многочленів з наступним зведенням результату за модулем примітивного многочлена.

Піднесення до квадрата у полі характеристики 2 — лінійна операція, тобто (х + у)²=х² + у². Тому піднесення до квадрата у такому полі проста операція.

Найлрацемісткіша операція в скінченних полях — обчислення оберненого елемента. Звичайно для цього використовується узагальнений алгоритм Евкліда обчислення найбільшого спільного дільника двох многочленів f(f) І с(ї), тобто многочлена найбільшого степеня, що ділить обидва ці многочлени. Цей алгоритм виражає найбільший спільний дільник d(t) як d(t) = + t>(t)c(t),

де a(t) і b(t) — деякі многочлени, що обчислюються при виконанні узагальненого алгоритму Ев­кліда. Цей алгоритм діє наступним чином:

1. Приймають «(/)= 1, d(t) = f(t), u(t) = O, v(f) = c(f).

.. d(t) + f(t)a(t)

2. Якщо v(t) = 0, то приймають b(t) = — та закінчують виконання алгоритму.

3. За допомогою ділення з залишком обчислюють d(t) = q(t)v(t) + r(t), далі обчислюють w(t) = = a(t) + = d(t} = v(t), u(t) = w(t), v(t) = r(t) та переходять до кроку 2.

Якщо як f(t) взяти примітивний многочлен поля, а замість c(f) — многочлен, що зображує еле­мент поля, то d(t) є одиничний многочлен і наведене вище співвідношення за модулем примітив­ного многочлена перетворюється у співвідношення Ь(0с(0=1 mod f(t), тобто многочлен b(t) зоб­ражує елемент, обернений до c(t).

При виконанні обчислень у скінченному полі часто доводиться зводити результат за модулем примітивного многочлена. Якщо як примітивний многочлен обрано примітивний тричлен або п'ятичлен, то зведення виконується набагато швидше у порівнянні зі звичайним зведенням за Барретом [9] або Монтгомері [10], не кажучи вже про просте ділення з залишком. Наприклад, якщо використовується примітивний тричлен f(t) = t^m+ t^k + 1, 0<к<т, то зведення многочлена д(^{)~92т-2^^2т~^{2 +}-+ 9^ + д₀ степеня не вищого за 2т-2 за модулем цього примітивного тричлена виконується так:

Для і від 2m-2 до т обчислюємо g,__m«- g^+g,- і 9і-тік+9ь

Отриманий в результаті многочлен д_т_^ f^m~¹ +...+ g^t + g₀— шуканий.

Подібний алгоритм існує для зведення за модулем примітивного п’ятичлена.

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

Додавання виконується так само, як у поліноміальному базисі, тобто шляхом порозрядного додавання зображень елементів поля за модулем 2.

Піднесення до квадрата в оптимальному нормальному базисі є просто циклічний зсув вправо на одну позицію зображення елемента поля.

Множення в оптимальному нормальному базисі виконується складніше. Для виконання множен­ня спочатку треба обчислити мультиплікативну матрицю М, що складається з рядків, які є розкла­дом в оптимальному нормальному базисі т добутків елементів базису вигляду х х^2>, ; = 0,..., т-1, тобто

хх

2^іXX

х- X

Перший розряд добутку z двох елементів поля х і у обчислюється за формулою z_m-i = xMy^T, де х — вектор-рядок, а у^Т— вектор-стовпчик.

Наступні розряди добутку обчислюються за цією самою формулою, тільки замість самих векто­рів х і у^т використовуються їх послідовні циклічні зсуви на один розряд вліво. Нагадаємо, що при використанні оптимального нормального базису крайній правий розряд зображення елемента поля відповідає елементу базису х . Складність множення визначається числом ненульових елементів у матриці М. В загальному випадку в цій матриці не менше 2т -1 ненульових елементів. Якщо нормальний базис оптимальний, то ненульових елементів рівно 2/п-1, власне, з цієї причини такий базис і називається оптимальним. Повний опис умов існування оптимальних нормальних базисів надано в [11].

Практично замість мультиплікативної матриці обчислюються явні формули, які виражають один розряд добутку через розряди співмножників.

Для обчислення оберненого елемента в оптимальному нормальному базисі використовується наступна формула: х"¹ = х² "², х^О. Для обчислення правої частини цієї формули існує ефективний алгоритм [12]: нехай т₀— двійковий розклад цілого числа т-1. Тоді обчислення оберне­ного елемента виконують таким чином:

1. b <- х; к <- 1.

2. Для і від г- 1 до 0 обчислюють:

   1. с*-Ь;

   2. Для / від 1 до к обчислюють:

      1. с«-с²;

   3. Ь <—Ьс,

   4. к^2к;

   5. Якщо т,= 1, то Ь <- Ь²х і к<- к + 1.

3. х^-1 = b².

Добуток всіх незвідних многочленів над полем GF(2), степінь яких ділить ціле число к, дорів­нює t²+t. Тому многочлен f(t) степеня т незвідний над полем GF(2) тоді і тільки тоді, коли найбіль­ший спільний дільник многочленів t^+t і f(t) дорівнює 1 для всіх к таких, що 1 < к < LW2 J. Ця властивість дає ефективний алгоритм перевірки незвідності многочленів.

Нехай p-і,..., р_г— прості дільники числа 2^т-1. Незвідний многочлен над полем GF(2) при­мітивний тоді і тільки тоді, коли 2^-1

t ^р> * 1 mod f (ґ) для всіх /, 1 < і < г.