Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Дискретне логарифмування на еліптичній кривій⇐ ПредыдущаяСтр 11 из 11 Операція, обернена до множення точки на число, визначає за поданою парою (P, mP) ціле число m. В літературі ця операція називається дискретним логарифмуванням на еліптичній кривій (elliptic curve discrete logarithm problem – ECDLP). Вважається, що задача ECDLP є важкорозв’язною (нерозв’язною з обчислювальної точки зору), якщо порядок точки P – велике число. Кількість точок еліптичної кривої, побудованої над полем Fq визначається наступною теоремою. Теорема Хассе (Hasse). | E(Fq) | = q + 1 – t, де 2Ö q £ t £ 2Ö q. Число t називають «слідом Фробеніуса» числа q. З теореми Хассе прямує, що кількість точок еліптичної кривої і число q мають однаковий порядок. Для кривої, визначеної над полем Fq, легко сконструювати велике просте число p, таке, що незначно менше q, і таке, що E(Fq) містить підгрупу порядку p. Часова складність найкращого з відомих алгоритмів розв’язання задачі ECDLP має порядок O(Ö q) (оскільки p» q). Цей результат досягається застосуванням методу, заснованого на парадоксі днів народження. Як правило, в задачі ECDLP розглядається число q» 2160. Це дозволяє отримати рівень обчислювальної складності атаки на основі парадоксу днів народження 280. Для того, щоб отримати аналогічний порядок складності при обчисленні дискретного логарифму у скінченому полі необхідно, щоб число q мало порядок 21000. Слід також зауважити, при зростанні продуктивності обчислювальних засобів значення безпечного q для групи точок еліптичної кривої зростає значно повільніше ніж для довільного скінченого поля.
Алгоритм розподілу ключів Обмін ключами з використанням еліптичних кривих виконується наступним чином. Спочатку вибирається просте число p» 2180 і параметри q і r Рівняння еліптичної кривої Ep(q, r). Потім на Ep(q, r) вибирається точка генерації G = (x1,y1) таким чином, щоб найменше значення n, при якому nG = 0, було великим простим числом. Параметри Ep(q, r) і G криптосистеми відкриті, тобто відомі усім. Схема обміну ключами має наступний вигляд. Учасник А вибирає ціле число nA < n, яке є закритим ключем учасника А. Після цього учасник А обчислює відкритий ключ PA = nA G, який являє собою деяку точку на Ep(q, r). Так само учасник В вибирає закритий ключ nB і обчислює відкритий ключ PB = nB G. Учасник А обчислює спільний секретний ключ K = nA PB, аучасник В отримує значення цього ключа згідно з виразом K = nB P. Слід зауважити, що спільний секретний ключ є парою чисел (координати точки на Ep(q, r)). Для використання цього ключа як ключа сеансу у алгоритмі симетричного шифрування, треба перетворити два числа у одне.
Алгоритм цифрового підпису на основі еліптичних кривих Алгоритм ECDSA (Elliptic Curve Digest Signature Algorithm) прийнятий як стандартний у США. Згідно зі стандартом ключі створюються наступним чином. 1. Вибирається еліптична крива Ep(q, r). 2. На кривій Ep(q, r) вибирається точка GÎ Ep(q, r), яка має великий порядок n ( помножаючи G на різні цілі числа, можна отримати n різних точок на Ep(q, r). 3. Вибирається випадкове число d Î [1, n – 1]. 4. Обчислюється Q = d G. 5. Закритий ключ – d, відкритий – (E, G, n, Q).
Алгоритм розподілу ключів Обмін ключами з використанням еліптичних кривих виконується наступним чином. Спочатку вибирається просте число p» 2180 і параметри q і r Рівняння еліптичної кривої Ep(q, r). Потім на Ep(q, r) вибирається точка генерації G = (x1,y1) таким чином, щоб найменше значення n, при якому nG = 0, було великим простим числом. Параметри Ep(q, r) і G криптосистеми відкриті, тобто відомі усім. Схема обміну ключами має наступний вигляд. Учасник А вибирає ціле число nA < n, яке є закритим ключем учасника А. Після цього учасник А обчислює відкритий ключ PA = nA G, який являє собою деяку точку на Ep(q, r). Так само учасник В вибирає закритий ключ nB і обчислює відкритий ключ PB = nB G. Учасник А обчислює спільний секретний ключ K = nA PB, аучасник В отримує значення цього ключа згідно з виразом K = nB P. Слід зауважити, що спільний секретний ключ є парою чисел (координати точки на Ep(q, r)). Для використання цього ключа як ключа сеансу у алгоритмі симетричного шифрування, треба перетворити два числа у одне. Алгоритм цифрового підпису на основі еліптичних кривих Алгоритм ECDSA (Elliptic Curve Digest Signature Algorithm) прийнятий як стандартний у США. Згідно зі стандартом ключі створюються наступним чином.1. Вибирається еліптична крива Ep(q, r). 2. На кривій Ep(q, r) вибирається точка GÎ Ep(q, r), яка має великий порядок n ( помножаючи G на різні цілі числа, можна отримати n різних точок на Ep(q, r). 3. Вибирається випадкове число d Î [1, n – 1]. 4. Обчислюється Q = d G. 5. Закритий ключ – d, відкритий – (E, G, n, Q). Створення підпису 1. Вибирається випадкове число k Î [1, n – 1], яке має обернене за модулем n. 2. Обчислюється k G = (x1, y1) і r = x1 (mod n). 3. Перевіряється значення r: якщо r = 0, обирається інше значення k (перехід до 1).4. Обчислюється k -1 mod n. 5. Обчислюється s = k -1 (H(m) + dr) (mod n) (H – функціяхешування), і перевіряється його значення: якщо s не має оберненого, обирається інше k. 6. Підписом повідомлення m є пара чисел (r, s). Перевірка підпису 1. Перевіряється, чи цілі числа r, s належать діапазону [1, n – 1]. Якщо не належать, підпис не дійсний.2. Обчислюються w = s-1(mod n), і H(m). 3. Обчислюються u1 = H(m) w (mod n) і u2 = rw (mod n). 4. Обчислюється u1 G + u2Q = (x0, y0) (mod n). 5. Підпис дійсний тоді і тільки тоді, коли x0 = r. Обґрунтування. u1 G + u2Q = H(m) s-1 G + r s-1 d G = s-1 (H(m) + r d) G = kG.
|
||
Последнее изменение этой страницы: 2017-02-21; просмотров: 216; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.149.27.29 (0.005 с.) |