20699

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

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

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

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

Украинкский

2013-07-31

168.01 KB

29 чел.

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

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

Кафедра ОТ

Лабораторна робота №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.

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


 

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

66332. Особливості використання методики ейдотехніки на уроках у першому класі початкової школи 246.5 KB
  Механічне запамятовування через силу постійні повторювання негативно впливають на фізичний стан нервову та емоційну сферу дітей значно ускладнюють процес їхнього адаптування до навчання у школі; у засвоєнні знань часто дають зворотний ефект.
66333. Що треба знати, обираючи фах 32 KB
  Адже саме в процесі праці сформувалася людина і завдяки праці змінюється її власна природа в якій вона досягає своєї свідомої мети прагне до її реалізації конструює свій життєвий шлях. Людина зобовязана працювати щоб залишити на землі свій власний слід...
66334. Малювання фарбами. Оздобления новорічних iгpaшок, виготовлених iз солоного тіста 48 KB
  Вчитель пропонує учневі зачитати вірш Миколай Коли замерзла річка І став біленький гай Зійшов у темну нічку На землю Миколай. На кого схожий Святий Миколай На Діда Мороза На яке свято приходить Дід Мороз Новий Рік Що робить Дід Мороз...
66335. Сценарій презентації поетичної збірки В.Федорової «Місце під сонцем» 41 KB
  Вітаємо вас у цій світлиці, у цьому затишному куточку Красноріченського освітнього округу, де зібралися люди, небайдужі до чистоти духовних криниць, до натхненної творчої праці та наділені великою любов’ю до культурного розквіту нашого краю.
66336. ШКОЛА ЮНОГО ФЕНОЛОГА 12.94 MB
  Дерева хоч і не вкрилися листям але вже пробудилися від зимових холодів. Багряне та золоте листя вірна ознака осені. Буває що частина листя жовкне задовго до осінніх днів. Іноді жовте листя на кущах і деревах зявляється ще в середині літа коли сухо та спекотно.
66337. Фестиваль юних обдарувань 55 KB
  Оформлення: святковоуричисто прикрашений актовий зал; емблема; кольрові кульки; квіти; виставка творчих робіт поробок; Державний прапор України; грамоти призерам; картки творчих досягнень; стрічки домінантам: Інтелектуал року Ерудит року Творча особистість Золоті руки Спортсмен року...
66338. Фестиваль європейських країн 112 KB
  Віддавна народи світу Мають власні прапори Наче долю горду й світлу Піднімають дороги 3й учень. Наш водій обирається учень якому дається кермо та головний убір водія рушаймо Пісню заспіваймо Учні і вчитель співають пісню Голубий вагон муз.
66339. Polymerase Chain Reaction (PCR) 40 KB
  Two primers, each about 20 bases long with sequence complementary to the sequence immediately adjacent to the DNA segment of interest.
66340. Функционирование русского языка в Республике Казахстан. Безударные гласные в корне слова (проверяемые, непроверяемые) 84.5 KB
  Языков на свете очень много – свыше двух тысяч. Точно установить их количество пока не удалось. Язык – явление общественное, он создается на протяжении длительного исторического периода. Язык возник в глубокой древности в процессе совместной трудовой деятельности людей.