Схеми цифрового підпису

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

На тему:

Схеми цифрового підпису (ЦП)

Функції ЦП

1. Підтвердження автентичності відправника і можливість перевірки цього.

2. Підтвердження автентичності повідомлення.

3. Підтвердження цілісності повідомлення.

4. Неможливість відмовитися від підпису (якщо ти підписав, то можна довести, що це твій підпис, і ти це не спростуєш).

5. Неможливість підроблювати підпис.

Загальна схема алгоритму:

М - повідомлення

Від нього береться одностороння хеш-функція: h(M).

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

Застосовуємо алгоритм ЦП.

Дописуємо ЦП S до M і передаємо:

секретний ключ відправника

Як перевіряється підпис?

Беремо повідомлення M | S, беремо від нього М і робимо те ж, що і при створенні ЦП.

маємо

відкритий ключ (відомий і відправнику і одержувачу)

І перевіряємо:

Відправник також називається претендентом, а одержувач верификатором.

Схема підпису RSA

Будуємо схему RSA: беремо великі p і q, знаходимо n = pq.

Вибираємо випадкове число (секретний ключ) і знаходимо відкритий ключ d з рівняння:

М - повідомлення.

1. Знаходимо . (при цьому нормування таке, що ).

2. Будуємо підпис: .

3. Відправляється (M, S).

Перевірка:

1. Будуємо (- оскільки повідомлення могло бути змінено).

2. Знаходимо .

3. Перевіряємо: .

Недоліки цієї схеми:

- трудомісткість (для стійкості повинно бути всі операції будуть повільними).

- може бути так звана «мультиплікативна атака» (маючи дещо підписаних повідомлень): якщо, то для підписів справедливо і можна послати помилкове повідомлення з реальним підписом x0.

Схема підпису Рабіна (1979 рік)

Заснована на наступному затвердженні:

якщо n = pq, де p і q - прості, те порівняння

має 4 рішення, і теорема говорить, що знаходження хоча б одного рішення по складності еквівалентно факторизації n.

(Отже, при тій же величині n стійкість даного методу буде така ж, як у RSA).

M=(m₀, …, m_t-1)) -двоїчний вигляд

r = (r₀, …, r_s-1) - шматок випадкової послідовності

Здійснюємо конкатенацію і маємо двійковий вектор (m0 ., mt-1_, r0 ., rs-1), тобто деяке число.

Цьому числу ставиться у відповідність деяке число (тут n = pq, де p і q - прості числа, вибирані відправником).

До повідомлення (M, r) застосовуємо хеш-функцію таку, що

(якщо функція дуже велика, то нормуємо (наприклад, просто укорочуємо))

Звідси маємо :

.

Хочемо довідатися, чи x0 є квадратичним вирахуванням. Це можна перевірити за допомогою символу Якобі.

- символ Лежандра, де, р - взаємно прості ((, р) = 1, р - простої)

Існує формула:

.

Якщо n - не простої, а складове, то вводиться символ Якобі .

Якщо n = p1. рк, то

.

Якщо x0- не квадратичне вирахування, то беремо іншу випадкову послідовність r, будуємоx0, знову перевіряємо, і т.д., поки не знайдемоx0, яке є квадратичним вирахуванням.

Далі з допомогою x0 будуємо ЦП.

Оскільки x0 - квадратичне вирахування, то

Якщо відоме розкладання n = pq, то знаходимо



і

Пара є ЦП (де r - це наша випадкова послідовність).

Посилається повідомлення .

Для перевірки:

1. Беремо, знаходимо .

2. Беремо, застосовуємо хеш-функцію (вона відома обом): .

3. Порівнюємо: .

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

Схема підпису Ель-Гамаля

Вибираємо велике просте число p. Вибираємо - примітивний елемент поля GF(p) (у нас був алгоритм знаходження x0). Вибираємо наступне число (до - секретний ключ).

Будуємо

.

- відкритий ключ перевірки підпису (відомий всім).

М - повідомлення. Будуємо .

Беремо випадкове число xm (раз - нове), взаємно просте з

.

Знаходимо і вирішуємо порівняння

і знаходимо звідси s.

І підписуємо:

Перевірка: одержуємо

знаходимо

мабуть:

Схема Ель-Гамаля швидше, ніж RSA. Її модифікація:

Схема підпису Шнорра

Спочатку знаходимо k, , як у Ель-Гамаля. Але вибираємо (-порядок простої підгрупи мультиплікативної групи GF(p)). Також повинно бути .

Далі вибираємо випадкове число .

Знаходимо .

Будуємо .

Вибираємо . Підписом є пара (H, s).

Перевірка підпису:

Маємо x0. Знаходимо .

Будуємо .

Мабуть: .

Цей підпис є основою для стандартів ЦП:

1. OSS (Американський стандарт)

2. ГОСТ Р.34.10-94 (російський стандарт)

В першому використовується хеш-функція SHA-1, а в другому хеш-функція будується на основі алгоритму шифрування ГОСТ 28147-89.

Хеш-функції

Хеш-функція h(M), де М задане у двійковому алфавіті, - це функція, яка відображає строку довільної довжину строку фіксованої довжини.

Де використовується хеш-функція:

Для отримання стиснутого образу повідомлення. Наприклад, для цифрового підпису, тому що:

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

Для цифрового підпису використовуються алгоритми типу RSA, які працюватимуть дуже повільно, якщо застосовувати їх до цілого повідомлення. Але можна застосувати їх до стиснутого образу, що значно збільшить швидкість роботи.

Для зберігання паролей.

У кодах аутентифікації (це той самий цифровий підпис, але тут підтверджується лише цілісньсть повідомлення без встановлення особи відправника).

Для перевірки правильності обчислень.

Криптографічні властивості хеш-функції:

Лавинний ефект.

Лавинний ефект нульового порядку: при зміні одного біту на вході кожен біт виходу зміниться з ймовірністю 1/2.

Лавинний ефект k-го порядку:

Це означення строгоголавинного ефекту.

Ослаблений лавинний ефект: при зміні на вході одного біту на виході змінитться приблизно половина бітів (тобто середнє число змінених бітів дорівнює m/2, де m - число бітів виходу).

h(M) повинна швидко обраховуватися.

Незворотність.

Функція h(M) називається стійкою у смислі незворотності, якщо майже для всіх значень функції не існує алгоритму, за яким можна відновити М. Тобто хеш-функція повинна бути однобічною.

Стійкість до колізій.

Нехай М - фіксоване повідомлення. Позначимо h(M)=H. Обчислювально неможливим знайти таке , щоб .

Ситуація, коли , називається колізією.

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

(Властивість 4 відноситься до деякого фіксованого повідомлення, а властивість 5 - до всіх повідомлень; тобто властивість 4 витікає з властивості 5.)

Однобічна слабка хеш-функція - це така хеш-функція, що задовольняє властивостям 1 - 4.

Однобічна хеш-функція - це хеш-функція, що задовольняє властивостям 1 - 5.

Зафіксуємо повідомлення М. Нехай m - довжина виходу хеш-функції. Тоді існує різних образів.

Якщо довжина виходу , то колізії існують. Головне, щоб їх неможливо було знайти обчислювальним шляхом.

Будемо навмання обирати . Оскільки обираємо випадковим чином, то з ймовірністю буде колізія. Якщо ми зробимо n спроб, то ймовірність колізії хоча б в одному випадку буде:

.

Якщо , то .

Приклад.

Нехай

Тоді . Значення доволі мале, тому можна вважати функцію безпечною.

Але безпечна слабка хеш-функція може не задовольняти властивості 5, тобто бути небезпечною.

Тепер будемо перебирати пари й дивитися, чи є колізія. Інакше кажучі, обираємо n повідомлень й дивимося чи співпадають хоча б два дз образів. Ймовірність цієї події:

Якщо , то , тобто .

Виходячи з цього, можна стверджувати, що .

Якщо (тобто , але не дуже швидко), то

Якщо , то .

Приклад.

, тобто система є небезпечною.

Теорія випадкових разміщень

Маємо N комірок. Незалежно кидаємо n часток й дивимось, чи попадуть 2 частки в одну комірку.

Якщо , то ймовірність попадання r часток у єдину комірку:

- число комірок, що утримують рівно r часток. Нас цікавить .

Існує теорема:

Якщо , то .

Ми розглядали однобічні функції без ключа.

Однобічна хеш-функція з ключем h(M,K) - це хеш-функція, яка має такі властивості:

Алгоритм є відкритим (таємність заключається у ключі K). Наприклад, алгоритм RSA;

Лавинний ефект;

Швидке обчислення h(M,K) при відомому ключі K;

Для будь-якого повідомлення М не існує ефективного обчислювального алгоритму розпізнавання h(M,K) при невідомому ключі K, при якомуймовірність розпізнавання . (Тобто усі виходи мають бути рівноймовірними.)

Неможливо знайти K обчислювальним шляхом, навіть якщо відома велика кількість пар

Неможливо знайти такі, що:

Алгоритми побудови однобічних хеш-функцій з ключем:

Треба взяти однобічну хеш-функцію , у якої довжина входу дорівнює n, а довжина виходу .

Розбиваємо повідомлення М на блоки довжини m (якщо треба, то останній блок доповнюємо нулями):

Знаходимо образ за рекурентною формулою:

,

де - два блока довжини m, що записуються підряд. - вектор ініціалізації. Тоді:

Якщо функція f така, що довжина входу дорівнює довжині виходу = n, то робимо таке:

де - XOR - операція “виключного або”.

Розглянемо систему RSA. Відкрита інформація: L - відомий ключ, .

Розбиваємо повідомлення на блоки : , - причому бовжина блоку . Позначимо K - таємний ключ.

Тоді , а перший блок

Побудова хеш-функції за допомогою блочних алгоритмів.

DES, ГОСТ: режим зчеплення шифр-блоків.

Вхід = 64 біта, тоді

, де - шифрограма з фіксованим ключем K. При цьому задається - вектор ініціалізації. (Можна вибирати його випадковим чином.)

Але така функція буде не дуже стійкою щодо оборотності.

Існують більш загальні схеми: можна подавати М не на вхід у звичайному розумінні, а на вхід ключа. У такому випадку стійкість функції щодо оборотності буде еквівалентна стійкості щодо подбору ключа.

Відповідна рекурентна формула: .

Тут А,В,С можуть мати такі значення:

const

і т.д. Всього маємо різних варіантів вироботки хеш-функції.

З цих 64 функцій 52 будуть слабкими або небезпечними, а 12 - стійкими (саме ці 12 й використовуються).

Приклад 1. . Тобто в якості ключа подається .

Приклад 2.

На сьогоднішній день застосовуються схеми MD2, MD4, MD5.

У них довжина виходу = 128 біт.

Використовуються такі операції:

диз'юнкція ()

коньюнкція ()

порозрядний булевий додаток ()

циклічний зсув

Приклад 3. SHA-1. Довжина виходу = 160. Операції: , , циклічний зсув.

Приклад 4. У нас - ГОСТ Р3411-94. Довжина виходу = 256.

Ідентифікація й Аутентифікація

Ідентифікація - це:

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

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

Аутентифікація - це метод, а також процедура встановлення істинності суб'єкта (об'єкта), цілісності даних та повідомлень.

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

Отже, виділяють три процедури входження у систему:

Ідентифікація

Аутентифікація

Авторизація

Ці процедури проходять:

Користувачі комп'ютерної мережі

Партнери по зв'язку

ОС, що працюють як суб'єкти

ЕОМ

Термінали

Повідомлення

Ці процедури забезпечують таке:

Відправник певен, що повідомлення отримав саме той, кому воно відправлено, та у незміненому вигляді.

Отримувач певен, що повідомлення отримане від того, від кого треба, та у незміненому вигляді.

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

Аутентифікатори повинні бути однозначними та такими, що неможливо підробити.

Методи, які використовуються при аутентифікації:

Відомості про деяку таємну інформацію (паролі, коди, алгоритми).

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

Незмінювані суб'єктивні характеристики (відбитки пальців, малюнок сітківки ока, тембр голосу та інші незмінні фізичні характеристики).

Динамічні суб'єктивні характеристики (“почерк” радіста, “почерк” роботи з клавіатурою ЕОМ).

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

Перевірка третьою стороною (арбітром, який завіряє підпис).

Розглянемо 1 та 2, бо вони використовують прийоми криптографії.

Аутентифікація за допомогою паролів.

а) Існує таблиця паролів, яка зберігається у комп'ютерній системі. У цій таблиці зберігаються усі паролі .

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

Наприклад, хеш-функція може використовуватися у такому вигляді:

,

де р - пароль, ID - ідентифікатор користувача.

Але у DES або ГОСТдовжина паролю має бути 64 біта, та як правило використовують паролі < 64 біт.

Тому використовують таке:

,

де K - ключ.

Така функція є більш стійкою до перебору.

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

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

Схема зі змінним паролем.

Нехай h(x) - стійка хеш-функція, що відома відправнику та отримувачу.

Ряд складається відправником А. В знає лише , що відправив йому А.

На кроці 1 А пред'являє та посилає його В. В визначає та порівнює його з тим , що він отримав від А та зберігає у таблиці паролів. Повинно бути: .

Даді у таблицю паролів записується вже , та при наступній аутентифікації А буде пред'явити в якості пароля и т.д.

Така процедура дозволяє n раз використовувати пароль без побоювань щодо його перехвату.

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

Процедура “запрос - відповідь” (“виклик - відгук”).

А та В мають спільний криптографічний алгоритм та спільний ключ K.

В - отримувач. А - відправник.

В генерує випадкове число М, обчислює , де K - спільний ключ, та посилає його до А.

А розшифровує: та відправляє до В.

В перевіряє: якщо , то все гаразд.

Це однобічний протокол (В перевіряє істинність А, але А не перевіряє нічого).

Двобічний протокол “Рукостискання”.

Є два варіанти:

з використанням хеш-функції

без використання хеш-функції

А бере свій ID та відправляє його В.

В за таблицею шукає K (спільний для А та В ключ).

Тепер А й В мають спільну криптосистему.

Далі А генерує випадкове число М, обчислює та відсилає до В. В дешифрує: . Далі вони беруть деяку спільну стійку хеш-функцію та обраховують таке:

А: та посилає до В;

В: та посилає до А.

А та В дешифрують те, що отримали. Тоді А має , а В має . Вони перевіряють співпадіння .

3. Аутентифікація за допомогою криптосистем із відкритим ключем.

Нехай А - відправник, В - отримувач.

А обирає 2 простих числа p, q та обчислює .

Функцію можна обернути лише при відомих p та q.

А об'являє число n та говорить, що він знає p та q. Якщо n - велике, то неможливо відгадати p та q. Тобтоніхто, крім А не знає цих чисел. Це і є та таємна інформація, що визначає істинність А.

В бере випадкове число х, обчислює та відправляє результат до А. А, знаючи p та q, може знайти корінь: від визначає та відправляє його доВ. В отримує та встановлює істинність А.

При використанні такої процедури не треба захищати пароль під час передачі каналом зв'язку; все передається відкритим каналом без шифрування. Це так зване “доведення без розголошення”.

Такі процедури “зашиваються” у мікросхеми, магнітні картки.

Ще один протокол. Знову: А - відправник, В - отримувач.

А знає, що деякий у можна представити у вигляді:

(тобто він знає, що у є квадратним вичетом).

А бере випадкове число v, знаходить та відправляє до В. В виробляє випадковий біт та відсилає його до А. Це є першим кроком перевірки.

А знаходить та відсилає до В.

Криптографічні системи на еліптичних кривих

Вперше криптографічні алгоритми на групах точок еліптичних кривих (ЕК) запропонували незалежно один від одного Кобліц та Міллер у 1985 році. Спочатку ці алгоритми здавались екзотичними, але згодом була доведена висока стійкість систем на ЕК та можливість їх ефективної реалізації, що і зумовило бурхливий розвиток цієї галузі криптології у наші дні.

Багато криптографічних систем з відкритим ключем базується на важкорозв'язуваній задачі дискретного логарифмування: у скінченій групі G за елементами g , знайти ціле x таке, що , де - операція у групі G. У традиційних криптосистемах в якості G використовується мультиплікативна група скінченого поля , а в якості g - твірний елемент . Найкращий на сьогоднішній день алгоритм розв'язку цієї задачі має складність порядку , тобто є субекспоненційним, і для досягнення задовільної стійкості параметр р треба брати дуже великим. Але задача дискретного логарифмування формулюється для будь-якої скінченої групи G, в тому числі і для групи точок ЕК, з тією лише різницею, що в цих групах прийнятий адитивний запис групової операції. А саме, аналог задачі дискретного логарифмування в термінах ЕК виглядає таким чином. Нехай Р - точка ЕК над скінченим полем F_q , що має великий порядок n (базова точка). Знаючи точки Р та Q = dP, знайти ціле число d.

Ця задача, на відміну від задачі дискретного логарифмування над скінченими полями, не має на сьогодні субекспоненційних методів розв'язку. Справа в тому, що у групі точок ЕК не існує аналогів простих чисел і незвідних многочленів - понять, на які спираються субекспоненційні алгоритми дискретного логарифмування у скінчених полях. Тому системи на ЕК виявляються набагато стійкішими за відповідні системи над скінченими полями, або при тій самій стійкості вимагають набагато коротшого ключа. Так, система на ЕК з довжиною ключа 160 біт має приблизно таку саму стійкість, як і традиційна система з ключем у 1024 біти, а ключу з 320 біт у системі на ЕК відповідає ключ довжиною 5600 біт у традиційній системі.

Криптографічні алгоритми, що спираються на задачу дискретного логарифмування, майже дослівно переформулюються на групи точок на ЕК із заміною операції множення на додавання і операції піднесення до степеня - на скалярне множення. Зауважимо, що криптосистеми, які використовують інші важкорозв'язувані задачі, наприклад, задачу факторизації великих чисел (система RSA), не переносяться на ЕК.

Розглянемо деякі приклади систем на ЕК.

Схема відкритого розповсюдження ключів Діффі-Хеллмана

Нехай абоненти А і В хочуть створити спільний секретний ключ (наприклад, для шифрування симетричною системою), користуючись тільки відкритим каналом. Вони обирають скінчене поле F_q (де q = p^r - велике число) та ЕК, визначену над ним, а також базову точку Р на цій кривій. Базова точка відіграє роль твірного елемента g мультиплікативної групи скінченого поля у класичному варіанті схеми Діффі-Хеллмана. Але цього разу ми не вимагаємо, щоб Р породжувала групу точок ЕК, адже остання може взагалі не бути циклічною. Необхідно лише, щоб порядок Р був великим: співпадав з порядком N ЕК або був великим простим дільником N. F_q , Е / F_q та Р - відомі параметри системи.

Абоненти А і В вибирають великі випадкові числа k_A і k_B відповідно, які вони тримають у секреті, обчислюють k_A Р (відповідно k_B Р) і обмінюються цими значеннями за допомогою відкритого каналу. А , одержавши k_B Р, обчислює k_A k_B Р; так само В обчислює k_B k_A Р, і в результаті вони одержують спільний секретний ключ Q = k_A k_B Р. Щоправда, ключ є радше числом, ніж точкою ЕК. Але з точки ЕК над скінченим полем F_q можна легко одержати число, наприклад, таким чином. Нехай q = p^r. Елемент поля F_q можна представити як многочлен степеня не вище r - 1 над F_р : .

Співставимо число у системі числення з основою p : .

Взявши -координату точки Q =( х , у ), , поставимо у відповідність їй число (як вказано вище) і одержимо секретний ключ k .

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

Система шифрування Мессі-Омури

Відкриті параметри системи: F_q ( q = p^r - велике), Е / F_q , N - порядок Е.

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

А обирає випадкове велике число k_A таке, що (k_А , N) = 1 (тобто існує ), обчислює k_A Р_М і відсилає це значення В. В вибирає випадкове велике число k_B ,

(k_В , N) = 1 , обчислює k_B k_A Р_М і відсилає назад А. Абонент А знаходить точку

k_А ^-1k_B k_A Р_М = k_B Р_М , відсилає її і В, який обчислює k_В Р_М = Р_М і, таким чином, отримує розшифроване повідомлення М.

Стійкість системи базується на складності розв'язання задачі дискретного логарифмування у групі точок ЕК.

Система шифрування Ель-Гамаля

Відкриті загальні параметри системи: F_q, Е / F_q , базова точка великого порядку. Знання порядку ЕК в даному випадку не потрібне.

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

Щоб зашифрувати і відіслати абонентові В таємне повідомлення Р_М , абонент А вибирає випадкове число k і обчислює пару , де - відкритий ключ В. Ця пара і є шифрованим повідомленням, яке А відсилає В . Для того, щоб прочитати повідомлення, В обчислює .

Таким чином, А разом з зашифрованим повідомленням посилає „ключ” для його розшифрування, яким, однак, може скористатися лише В, що знає свій секретний ключ .

Подібним чином на групи точок на ЕК переносяться і алгоритми цифрового підпису Ель-Гамаля та Шнорра.

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

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

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

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

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

1) Нехай .

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

(2)

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

2) .

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

або

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

3) .

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

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

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

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

Рис. 1 Рис.2

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

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

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

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

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

Так як входить у рівняння (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	2	3	4	5	6	7	8	9	10
	1	3	0	9	3	10	3	10	4	2	10
у	1,10	5, 6	0	3, 8	5, 6	-	5, 6	-	2, 9	-	-

Таким чином, еліптична крива Е складається з точок: (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.