Криптосистеми

Контрольна робота

Криптосистеми

Суттєвим недоліком криптосистем з відкритим ключем є їх недостатня швидкість. До того ж, їх виникнення і розвиток стимулювали дослідження в теорії чисел, що призвело до створення все нових алгоритмів криптоаналізу систем з відкритим ключем. Тому для досягнення задовільної стійкості доводиться постійно збільшувати довжину ключа. Так, якщо донедавна довжина ключа у 512 біт була достатньою, то на сьогоднішній день потрібно використовувати ключі у 1024 біти і в недалекому майбутньому цю довжину, імовірно, доведеться ще збільшити. Але чим довший ключ, тим повільніше працює система. Виходить замкнене коло. Потрібно було шукати принципово нові підходи. Одним з таких підходів виявилося використання в криптографії еліптичних кривих над скінченими полями - добре вивченого математичного об'єкта з області алгебраїчної геометрії.

Нехай - довільне поле. Загальне рівняння еліптичної кривої над полем має вигляд

де - елементи і операції додавання та множення в (1) - операції у полі .

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

В залежності від характеристики поля рівняння (1) заміною змінних зводиться до рівнянь більш простого виду. А саме:

1) Нехай .

Тоді рівняння (1) набуває виду

(2)

а умова гладкості виглядає так:

2) .

В цьому випадку рівняння (1) зводиться до одного з двох наступних:

або

Умова гладкості: .

3) .

Рівняння приймає вид:

і кубічний чотиричлен справа не повинен мати кратних коренів.

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

над полем мають вигляд, що зображений на рис.1 або 2.

Рис. 1 Рис.2

Визначимо операцію додавання на точках таким чином:

1) Нейтральний елемент групи:

покладемо для будь-якої точки .

2) Протилежні елементи:

покладемо -= ;

Так як входить у рівняння (2) лише у другому степені, то з випливає, що - - графік кривої симетричний відносно осі .

3) Якщо , то через точки і проведемо січну. Неважко показати, що вона перетне ще в точності в одній точці, якщо тільки січна не виявиться дотичною у точці або . Позначимо цю точку . Якщо ж пряма, що проходить через точки і є дотичною в , то покладемо (рис.2), якщо ж в - то . В будь-якому з цих випадків покладемо (рис.1).

4) Якщо , то . (Вважається, що точка лежить на нескінченності в додатному напряму осі . Природно вважати її третьою точкою перетину з вертикальною прямою, що проходить через точки ).

5) Нехай P = Q. Проведемо в точці P дотичну до Е і позначимо R - точку перетину цієї дотичної з Е. Тоді P + Q = 2 P = - R. Якщо ж точки R не існує, то Р - точка перегину і покладемо 2 P = - Р.

Виразимо тепер координати суми P + Q через координати точок P і Q.

Нехай .

- рівняння січної, що проходить через точки P і Q.

Таким чином,

Точка, що лежить на січній, має координати . Якщо точка лежить також і на Е, то її координати задовольняють рівнянню (2):

(6)

Так як точки P, Q лежать одночасно на січній і на Е, то є коренями рівняння (6). Третім коренем цього рівняння є - координата точки R. За теоремою Вієта . Отже,

(7)

Для координат точки формули дещо відрізняються. А саме, - кутовий коефіцієнт дотичної в точці P: .

З (2) маємо

Отже, для 2 P:

(8)

де визначається формулою (7).

У випадку ЕК, заданих над скінченим полем F_q, операції додавання точок не мають геометричної інтерпретації, як для ЕК над полем дійсних чисел (відсутні поняття січної та дотичної). Але ці операції при виконуються за тими самими формулами

(7) - (8), що й для F = R. Потрібно лише зауважити, що у формулах (7) - (8) ділення при цьому треба розуміти як операцію у скінченому полі, тобто .

Природно, ЕК над скінченним полем має скінченну кількість точок.

Означення

Кількість точок ЕК, враховуючи точку на нескінченності, називається порядком ЕК.

Розглянемо приклад еліптичної кривої над простим скінченним полем. Нехай

- рівняння еліптичної кривої Е₁ над полем GF(11). Знайдемо всі точки даної еліптичної кривої. Для того, щоб точка Р = (х_Р, у_Р) належала кривій Е₁, потрібно, щоб значення виразу в правій частині (7) при х = х_Р являло собою квадратичний лишок за модулем 11. У нашому маленькому прикладі неважко знайти всі квадратичні лишки, піднісши всі елементи GF(11) до квадрата. Квадратичними лишками за модулем 11 є: 1, 3, 4, 5, 9.

Підставимо елементи GF(11) у праву частину (4) і підрахуємо відповідні значення у, якщо у правій частині одержали квадратичний лишок:

Таким чином, еліптична крива Е складається з точок: (0, 1), (0, 10), (1, 5), (1, 6), (2, 0), (3, 3), (3, 8), (4, 5), (4, 6), (6, 5), (6, 6), (8, 2), (8, 9) і точки на нескінченності О_Е. Тож порядок її дорівнює 14, і криву Е можна зобразити на площині так:

Рис.3. Графічне зображення еліптичної кривої над полем GF(11).

Порахуємо суму точок Р = (8,9), та Q = (1,5) еліптичної кривої Е₁ над GF(11) (рис.1).

Таким чином, = (3,8).

Подвоїмо точку Р:

Отже, 2Р = (0,1).

Точка, протилежна до Р: - Р = (8,-9) = (8,2).

Точки Р, Q, , 2Р, -Р зображені на рис.1.

Групова операція на точках еліптичних кривих над полями характеристики 2

Формули, що визначають групову операцію на точках еліптичних кривих над полем характеристики 2, дещо відрізняються від формул попереднього пункту. А саме, нехай і дві точки еліптичної кривої над GF(2^m) в афінних координатах.

Координати протилежної точки визначаються так:

-Р = .

Сума точок обчислюється за наступними правилами.

Якщо , то координати точки обчислюються за формулами:

Якщо , то 2P=O. Якщо, то координати подвоєної точки обчислюються за формулами:

Скористаємося цими формулами для обчислень у групі точок еліптичної кривої Е₂ над GF(2³), побудованої у п.3.1. Нехай Р = (g², 1), Q = (g⁵, g³). Тоді, використовуючи таблицю індексів (2), маємо:

- Р = (g², g² + 1) = (g², g⁶).

Якщо , то

отже,

Якщо , то

Таким чином,

Множення точки еліптичної кривої на ціле число

Операція обчислення суми k точок Р еліптичної кривої Р + Р +... + Р (k разів) називається множенням точки на натуральне число і позначається kР. За означенням , тому можна говорити про множення точки на довільне ціле число.

Це основна операція на точках еліптичної кривої, що використовується у криптографії. Тому її прискорення має велике практичне значення. Для множення точки на велике ціле число можна використовувати способи, цілком аналогічні тим, що застосуються для піднесення цілого числа до степеня . Якщо двійкове зображення числа k, то точку можна обчислити наступним чином:

1.Приймають .

2.Для i від t-1 до 0 обчислюють ; якщо , то додатково обчислюють .

Наприклад, двійковий розклад числа 100 є: 100 = 2⁶ + 2⁵ + 2². Щоб обчислити 100Р, виконуємо таку послідовність операцій:

100Р = 2(2(Р + 2(2(2(Р + 2 Р))))).

Для ЕК над полями характеристики 3 також існують формули додавання і подвоєння точок, схожі на (7) - (8), але з деякими відмінностями. Так як ЕК над полями характеристики 3 в криптографії не використовуються, ми не будемо наводити ці формули.

У формули () - () та () - () виконання групової операції на точках ЕК входить операція ділення, яка у скінчених полях виконується за допомогою узагальненого алгоритму Евкліда. Хоча цей алгоритм має поліноміальну складність (його складність у полі F_q має порядок ), але операція ділення займає багато часу порівняно з операціями додавання та множення. Змогу уникнути ділення дає проективне зображення ЕК. Якщо бути більш точними, рівняння (1) - (4) називаються рівняннями ЕК у афінних координатах. Відомі також рівняння ЕК у проективних координатах.

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

Точки проективної площини з утворюють так званий „горизонт” проективної площини. Кожному рівнянню ЕК в афінних координатах відповідає рівняння у проективних координатах, варто лише замінити на та помножити обидві частини рівняння на . Наприклад, рівняння (2) у проективній формі набирає вигляду

і є однорідним рівнянням 3-го степеня. Якщо в цьому рівнянні покласти , то і , отже, єдина точка „горизонту”, що задовольняє (), є , яка і відповідає точці на нескінченності О_Е у афінному зображенні ЕК.

Проективне зображення зручне тим, що в проективних координатах формули додавання та подвоєння точок ЕК не містять операції ділення, щоправда, за рахунок більшого числа операцій додавання та множення у полі F. Але загалом виконання групової операції на точках ЕК у проективних координатах виявляється більш ефективним. Ми не наводимо формул додавання та подвоєння точок ЕК у проективних координатах з огляду на їх громіздкість.

Так як формули додавання та подвоєння точок ЕК містять обмежену кількість (не більше 20) операцій додавання, множення та ділення у скінченому полі F_q, складність виконання яких має порядок , то неважко бачити, що складність операції скалярного множення kР має порядок .

У випадку ЕК, заданих над скінченим полем F_q, операції додавання точок не мають геометричної інтерпретації, як для ЕК над полем дійсних чисел (відсутні поняття січної та дотичної). Але ці операції при виконуються за тими самими формулами

() - (), що й для F = R. Потрібно лише зауважити, що у формулах () - () ділення при цьому треба розуміти як операцію у скінченому полі, тобто .

Для ЕК над полями характеристики 3 також існують формули додавання і подвоєння точок, схожі на () - (), але з деякими відмінностями. Так як ЕК над полями характеристики 3 в криптографії не використовуються, ми не будемо наводити ці формули.

У формули () - () та () - () виконання групової операції на точках ЕК входить операція ділення, яка у скінчених полях виконується за допомогою узагальненого алгоритму Евкліда. Хоча цей алгоритм має поліноміальну складність (його складність у полі F_q має порядок ), але операція ділення займає багато часу порівняно з операціями додавання та множення. Змогу уникнути ділення дає проективне зображення ЕК. Якщо бути більш точними, рівняння (1) - (4) називаються рівняннями ЕК у афінних координатах. Відомі також рівняння ЕК у проективних координатах.

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

Точки проективної площини з утворюють так званий „горизонт” проективної площини. Кожному рівнянню ЕК в афінних координатах відповідає рівняння у проективних координатах, варто лише замінити на та помножити обидві частини рівняння на . Наприклад, рівняння (2) у проективній формі набирає вигляду

і є однорідним рівнянням 3-го степеня. Якщо в цьому рівнянні покласти , то і , отже, єдина точка „горизонту”, що задовольняє (), є , яка і відповідає точці на нескінченності О_Е у афінному зображенні ЕК.

Проективне зображення зручне тим, що в проективних координатах формули додавання та подвоєння точок ЕК не містять операції ділення, щоправда, за рахунок більшого числа операцій додавання та множення у полі F. Але загалом виконання групової операції на точках ЕК у проективних координатах виявляється більш ефективним. Ми не наводимо формул додавання та подвоєння точок ЕК у проективних координатах з огляду на їх громіздкість.

Так як формули додавання та подвоєння точок ЕК містять обмежену кількість (не більше 20) операцій додавання, множення та ділення у скінченому полі F_q, складність виконання яких має порядок , то неважко бачити, що складність операції скалярного множення kР має порядок .