20699

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

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

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

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

Украинкский

2013-07-31

168.01 KB

28 чел.

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

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

Кафедра ОТ

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

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


 

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

54365. День Святого Миколая - душа весело співає 158 KB
  Хлопчик Краснії подарунки дітям приносить В кожен дім діти знають: з радістю приходить. Звучить чарівна мелодія зявляються дівчаткаянголи які виконують дивовижний танок сповіщаючи прихід Миколая стук у двері до господи входить Святий Миколай Вчитель Діти а хто до нас прийшов Діти Святий Миколай Св. Добрий день вам любі діти Діти Добрий день Св. Бачу ви усі привітні...
54366. Сценарій ранку «Ми чекаємо Святого Миколая» 60 KB
  Ми всі з нетерпінням чекаємо дня Святого Миколая. З лопатами і з піснею Працюємо разом 2куплет: Ми цю пісню будемо співати І всі дружно станем працювати Щоб Миколай прийшов до всіх Приніс дарунків повен міх 1 чортик Ну що ж мене вам не здолати я вам нашлю нову біду Чари мариТепер вас треба всіх розчарувати а для цього треба все про святого Миколая розповісти а ви про нього нічого і не знаєте.
54367. Народні свята. День Святого Миколая 81 KB
  Співом його привітаєм Разом пісню заспіваєм Співають пісню Ой хто хто Миколая любить Ой хто хто Миколая любить Ой хто хто Миколаю служить Тому святий Миколай На всякий час помагай Миколаю Ой хто хто спішить в твої двори Того ти на землі й на морі. Все хорониш від напасти Не даєш му в гріхи впасти Миколаю Ой хто хто к ньому прибігає На поміч його призиває Той все з горя вийде ціло Охоронить душу й тіло Миколаю Миколай молися за нами Благаєм тебе зі сльозами Ми тя будем вихваляти Ім'я твоє величати Миколаю 2...
54368. Свято Миколая 62.5 KB
  Коли святий Миколай З небес на землю йде То кожен дім і школа Мов вулик бджіл гуде. Це Святий Миколай. Як затанцюють за вікном сніжинки І білим килимом укриють край То знай що до Івася і Галинки Святий прибуде з неба Миколай. Я не хочу щоб Святий Миколай приходив до вас хвалив за якісь гарні вчинки дарував вам гостинці.
54369. Свято Василя та Меланки 209.5 KB
  Цього дня батько ховається від своїх дітей за символом багатства та щедрості — за пирогами. Діти повинні вдавати, що в цю мить батька не бачать — так велить традиція. Вони мусять запитувати в матері, де ж тато подівся. А «здивована» мати бажає, аби й наступного року діти за пирогами батька не помітили.
54370. Классный час «Милосердие» 61.5 KB
  Суть бескорыстного доброго отношения к человеку хорошо выразил другой римский философ Марк Аврелий: Когда ты сделал комуто добро и это добро принесло плод зачем ты как безрассудный домогаешься еще похвалы и награды за свое доброе дело Видимо сознание сделанного добра высшая награда для человека. Внутренний психический мир человека. Наука изучающая процессы и закономерности психологической деятельности человека.
54371. Смотри, не забудь, человеком будь 110.5 KB
  Какие чувства у вас возникали когда вы смотрели на эти фотографии Заставили ли вас эти фотографии сочувствовать сопереживать Как можно одним словом назвать способность человека к сопереживанию к совершению добрых и бескорыстных поступков по отношению к больным маленьким детям престарелым инвалидам животным да и ко всем живым существам Милосердие Какое сердце должно быть у...
54372. Арифметичні дії зі звичайними дробами 2.61 MB
  Отже яка основна властивість дробів Дощик капає на парту Парасольку я беру Потягнулися до сонця І сховались від дощу. Отже як знайти суму двох дробів з різними знаменниками 4тема. Отже чому дорівнює добуток двох дробів Отже зараз ми виконали певну роботу. Скорочення дробів.
54373. Культура Киевской Руси 24.76 KB
  Первые киевские князья (Олег, Игорь, Святослав, Владимир, Ярослав) стремились расширить территорию государства за счет присоединения не вошедших в состав Киевской Руси славянских племен