20699

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

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

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

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

Украинкский

2013-07-31

168.01 KB

22 чел.

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

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

Кафедра ОТ

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

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


 

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

26985. Закон-понятие, виды 5.65 KB
  Общеизвестностькачественный признак форм правасвязанный с информированием о правилах поведенияпределах их действия. По объему и характеру действия: 1общего действияохватывают всю совокупность отношений определенного вида на данной территорииТрудовой кодекс 2ограниченного действияраспространяются на часть территории или строго определенный контингент лицнаходящийся на данной территориизакон о полиции 3исключительногочрезвычайного действияреализуются только в случае наступления исключительных обстоятельств. По времени действия: 1.
26988. Субъект правотворчества.Участие граждан,общественных организаций и народа в процессе правотворчества. Право законодательной инициативы 9.08 KB
  Правотворчество деятельностьнаправленная на подготовкуизданиесовершенствование НПА. Требования к правотворчеству соблюдение принципов: 1 законности принятие НПА только теми субъектами которые наделены соответствующими полномочиями 2 демократизма возможность принятия наиболее важных НПА в порядке референдума 3 научности планирование приоритетности принимаемых актов 4 профессионализма требует особых навыков умений и таланта 5 системности вновь принимаемые акты не должны противоречить действующим актам 6 гласности все...
26989. Порядок опубликования и вступления в силу нормативно-правовых актов 7.57 KB
  Порядок опубликования и вступления в силу нормативноправовых актов.Неопубликованные НПА не применяютсяне влекут правовых последствийкак не вступившие в силу. ФКЗФЗ подлежат официальному опубликованию в течение 7 дней после дня их подписания Президентома вступают в силу по истечении 10 днейпосле их официального опубликованияесли самими законами не установлен другой порядок вступления их в силу. ИСТОЧНИКИ:Парламентская газетаРоссийская газетаСобрание законодательства РФОфициальный интернетпортал правовой информации Кроме общего...
26992. Действие НПА во времени,пространстве и по кругу лиц 5.22 KB
  Действие НПА во временипространстве и по кругу лиц. НПАакт правотворчествапринятый в особом порядке строго определенными субъектами и содержащий норму права. Признаки: а содержание норм права; б особый порядок принятияназываемый правотворческий процессгосударственное правотворчествонепосредственное правотворчествопринятие или не принятие НПАпредлагаемых госм; в иерархическая подчиненность; г оформление в письменном виде как официальный гос.В разных странах разные правила вступления в силу НПА: с момента принятия...
26993. Понятие системы права. Основные структурные элементы 6.31 KB
  Понятие системы права. СИСИТЕМА ПРАВА–исторически сложившаяся ВНУТРЕННЯЯ ОРГАНИЗАЦИЯ ПРАВАкоторая выражается в единстве и разделении права на относительно самостоятельные части. ПРИЗНАКИ: ОБЪЕКТИВНОСТЬвнутренняя структура права обусловлена реально складывающимися общественными отношениямине создается по усмотрению правовых субъектов; ЕДИНСТВО и взаимосвязь составляющих ее ПРАВОВЫХ ПРЕДПИСАНИЙкоторые согласованны; УРОВНЕВАЯ ДИФФЕРЕНЦИАЦИЯ ЭЛЕМЕНТОВ структуры праваотражающая их функциональное назначение различного порядка. ОСНОВНЫЕ...