20699

Еліптичні криві в криптографії

Лабораторная работа

Информатика, кибернетика и программирование

1КІ08 Морозов Артем Еліптична крива над полем K це множина точок проективної площини над K що задовольняють рівнянню разом з точкою на нескінченності. Отже кількість точок на кривій – парна 1 точку дає по дві точки можуть давати інші елементи поля і треба не забути про точку на нескінченності. Додавання точок виконується наступним чином: 1 Нейтральний елемент групи: для будьякої точки . 3 Якщо то сумою точок та є 4 Якщо то 5 Якщо то .

Украинкский

2013-07-31

168.01 KB

23 чел.

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

Кафедра ОТ

Лабораторна робота №8

«Еліптичні криві в криптографії»

Виконав ст..гр.1КІ-08

Морозов Артем

Еліптична крива над полем K - це множина точок проективної площини над K,

 що задовольняють рівнянню

разом з точкою на нескінченності.

        Еліптичні криві є одним з основних об'єктів вивчення в сучасній теорії чисел і криптографії. Наприклад, вони були використані Ендрю Вайлзом (спільно з Річардом Тейлором) в доведенні Великої теореми Ферма. Еліптична криптографія є самостійним розділом криптографії, що присвячений вивченню криптосистем на базі еліптичних кривих. Зокрема, на еліптичних кривих заснований російський стандарт цифрового підпису . Еліптичні криві також застосовуються в деяких алгоритмах факторизації (наприклад Алгоритм Ленстри) і тестування простоти чисел.

Для еліптичної кривої знайдемо всі т. Е9 за заданим рівнянням:

Y2=y3+x+6 (mod 11)

#E = 13.

Приклад еліптичної кривої

Розглянемо, коли точка з координатами належить еліптичній кривій. Для цього треба з’ясувати, коли має розв’язки відносно  рівняння . Для цього розглянемо 2 випадки:

1) . В такому випадку рівняння зводиться до , яке завжди має єдиний розв’язок у полі , який можна знайти як .

2) . Розділимо обидві частини рівняння на і відносно маємо рівняння , де . Зауважимо, що можна знайти як . Отримане рівняння має два розв’язки тоді, коли , де

.

Ці розв’язки можна знайти за формулою операції напівсліду: , , і, відповідно, , .

Якщо ж , то рівняння розв’язків не має.

Отже, кількість точок на кривій – парна (1 точку дає , по дві точки можуть давати інші елементи поля, і треба не забути про точку на нескінченності). На цих точках вводиться група. Додавання точок виконується наступним чином:

1) Нейтральний елемент групи: для будь-якої точки .

2) Протилежні елементи: покладемо , .

3) Якщо , то сумою точок  та є

4) Якщо , то

5) Якщо , то .

Візьмен еліптичну криву

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

(4,1); (4,6); (5,0); (6,1); (6,6); O.

Кожна з отриманих точок характеризується порядком, тобто числом k, яка її відображає в точку на нескінченності - Т.О. Для більш детального уявлення складемо таблицю (карту) точок заданої кривої, шляхом множення послідовно на числа від 1 до p-1 = 7-1 = 6:

k (4,1) (4,6) (5,0) (6,1)  (6,6) O

1 (4,1) (4,6) (5,0) (6,1) (6,6) O

2 (6,6) (6,1) O (6,6) (6,1) O

3 (5,0) (5,0) (5,0) O O O

4 (6,1) (6,6) O (6,1) (6,6) O

5 (4,6) (4,1) (5,0) (6,6) (6,1) O

6 O O O O O O

З отриманої таблиці ми можемо отримати порядок кожної точки кривої. Так точки розглянутої кривої мають такими порядками:

(4,1) - 6, (4,6) - 6, (5,0) - 2, (6,1) - 3, (6,6) - 3.

Висновки: В даній лабораторній роботі було ознайомлено з основними поняттями про еліптичні криві , вивчено основні підходи до використання еліптичних кривих в криптографії.


 

А также другие работы, которые могут Вас заинтересовать

59254. СЦЕНАРІЙ СВЯТА ПРИСВЯЧЕНОГО СВЯТОМУ МИКОЛАЮ 62.5 KB
  Отець Миколай старався всім допомогти але так щоб ніхто не знав чиїх це рук справа. Миколай відніс вночі до дому цього чоловіка мішечок з золотом і тим самим поміг йому врятувати дітей від горя і злиднів.
59256. Сценарій: Зустріч з казкою 66.5 KB
  Першою до нас в гості завітала українська народна казка Колобок яка вам вже є знайомою але уважно просимо додивитись її до кінця й тоді Ведуча: Та не треба поспішати а краще казку розпочати бо недаремно мудрі кажуть люди що краще раз побачити ніж десять раз почути.
59257. Свято Нептуна 41 KB
  І в зелену полонину Поведе Як на Пруті крига скресне Люту зиму перекреслить Оп’яніє від кохання Оп’яніє від кохання Голова Перелесник обіймає Та цілує не питає Та питає коли слати Старостів У такі зелені весни Кожен хлопець Перелесник Кожна дівчина...
59258. Скликаєм усіх на бал, на осінній карнавал 43 KB
  Осінь: Мене напевно не чекали Та вже прийшла моя пора. І ви мене усі впізнали Я – Щедра Осінь золота. Осінь: Ти Гарбуз всьому господар Ти найбільший на городі.
59260. Де Купало ночувало 43 KB
  Дівчата готують святкові строї хлопці – приладдя для парубоцьких ігор старі жіночки випікають солодощі для гостини. За день до проведення свята пізно ввечері хлопці ховають у схованки сюрпризи для дівчат а дівчата мають знайти їх пізно ввечері перед закінченням свята.
59261. Малі олімпійські ігри 43.5 KB
  Ознайомити дітей з історією Олімпійських ігор; З культурою і традиціями Стародавньої Греції символікою Олімпійських ігор прапор факел; Поглибити знання дітей про видатних спортсменів України; Розвивати інтерес до пізнання історії спорту нашої країни...
59262. ПІСНЯ – ДУША НАРОДУ 55.5 KB
  Яке диво дивне народна пісня Яку владну силу таїть вона в собі Минають віки змінюються суспільні устрої потрясають світ нищівні війни і голодомори на зміну одним поколінням приходять інші у кожного свої смаки свої уподобання.