91630

Алгоритм Диффи-Хеллмана

Доклад

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

Для обмена информацией первый пользователь выбирает случайное число x1 равновероятное из целых. Это число он держит в секрете а другому пользователю посылает число y1 = x mod р Аналогично поступает и второй пользователь генерируя x2 и вычислив y2 отправляя его первому пользователю. Для того чтобы вычислить k12 первый пользователь возводит y2 в степень x1. То же делает и второй пользователь.

Русский

2015-07-21

41.76 KB

0 чел.

Алгоритм Диффи-Хеллмана

Диффи и Хелман предложили для создания криптографических систем с открытым ключом функцию дискретного возведения в степень.

Необратимость преобразования в этом случае обеспечивается тем, что достаточно легко вычислить показательную функцию в конечном поле Галуа состоящим из рэлементов. (р - либо простое число, либо простое в любой степени). Вычисление же логарифмов в таких полях - значительно более трудоемкая операция.

Если y=x,, 1<x<р-1, где - фиксированный элемент поля GF(р), то x=log y над GF(р). Имея x, легко вычислить y. Для этого потребуется 2 ln(x+y) операций умножения.

Обратная задача вычисления x из y будет достаточно сложной. Если р выбрано достаточно правильно, то извлечение логарифма потребует вычислений, пропорциональных

L(р) = exр { (ln р ln ln р)0.5 }

Для обмена информацией первый пользователь выбирает случайное число x1, равновероятное из целых 1...р-1. Это число он держит в секрете, а другому пользователю посылает число

y1 = x mod р

Аналогично поступает и второй пользователь, генерируя x2 и вычислив y2, отправляя его первому пользователю. В результате этого они могут вычислять k12 = x1x2 mod р.

Для того, чтобы вычислить k12, первый пользователь возводит y2 в степень x1. То же делает и второй пользователь. Таким образом, у обоих пользователей оказывается общий ключ k12, который можно использовать для шифрования информации обычными алгоритмами. В отличие от алгоритма RSA, данный алгоритм не позволяет шифровать собственно информацию.

Не зная x1 и x2, злоумышленник может попытаться вычислить k12, зная только перехваченные y1 и y2. Эквивалентность этой проблемы проблеме вычисления дискретного логарифма есть главный и открытый вопрос в системах с открытым ключом. Простого решения до настоящего времени не найдено. Так, если для прямого преобразования 1000-битных простых чисел требуется 2000 операций, то для обратного преобразования (вычисления логарифма в поле Галуа) - потребуется около 1030 операций.

Как видно, при всей простоте алгоритма Диффи-Хелмана, вторым его недостатком по сравнению с системой RSA является отсутствие гарантированной нижней оценки трудоемкости раскрытия ключа.

Кроме того, хотя описанный алгоритм позволяет обойти проблему скрытой передачи ключа, необходимость аутентификации остается. Без дополнительных средств, один из пользователей не может быть уверен, что он обменялся ключами именно с тем пользователем, который ему нужен. Опасность имитации в этом случае остается.

В качестве обобщения сказанного о распределении ключей следует сказать следующее. Задача управления ключами сводится к поиску такого протокола распределения ключей, который обеспечивал бы:

* возможность отказа от центра распределения ключей;

* взаимное подтверждение подлинности участников сеанса;

* подтверждение достоверности сеанса механизмом запроса-ответа, использование для этого программных или аппаратных средств;

* использование при обмене ключами минимального числа сообщений.



 

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

36943. Робота з масивами в СКМ Mathcad 24.73 KB
  Дано дві матриці А та В.7150 Транспонувати матриці А В С.1600 Знайти найменший елемент 3го стовпчику матриці С.1600 Вивести стовбець матриці С який містить максимальний елемент у виді окремого вектору.
36944. Побудова вибіркової функції розподілу засобами комп’ютерних технологій 363.5 KB
  Лабораторна робота №2 Тема: побудова вибіркової функції розподілу засобами комп’ютерних технологій. У MthCD існують дві функції що дозволяють зробити обробку вибірки для наступної побудови гістограм. Оскільки методика створення гістограм з використанням функції hist досить складна надамо її по пунктах: Для початку представимо експериментальні дані у вигляді вектора.
36945. Розрахувати найбільшу похибку відлікового пристрою і встановити раціональну точність виготовлення елементів багатооборотного індикатора 543.84 KB
  1 Функції перетворення синусного механізму: Для кулісного механізму Передаточне відношення від веденої ланкистрілки до кінцевої ланки кулісного механізму Вихідна функція з кулісного механізму враховуючи що вихід синусного є входом кулісного.
36946. Обладнання та драйвери. Використання Device Manager та System Information 316.54 KB
  Вивести властивості пристрою 1. Вивести список драйверів що забезпечують роботу даного пристрою відобразити у звіті рис. Імітуючи несправність пристрою неправильно під’єднаний шлейф SCSIпристрою запустити програму Troubleshooter Діагностика 1. Також я знайшов IRQ ресурси певних пристроїв та визначив які драйвера потрібні для роботи дискового пристрою відображені на рис2.
36947. Використання вбудованих функцій MathCAD, MS Exсel для обчислення характеристик вибірки 61.5 KB
  Для обчислення числових характеристик вибірки що утримується в масиві Х розмірності m×n в MthCD призначені наступні функції: mxХ – для пошуку найбільшого елемента в масиві даних; minХ – пошук мінімального елемента в масиві даних; sortХ – побудова варіаційного ряду тобто сортування вихідних даних по зростанню; menХ – обчислення вибіркового середнього по масиву даних: vrХ – для визначення вибіркової дисперсії; stdevХ – для обчислення середньоквадратичного відхилення; medin – для розрахунку значення медіани –...
36948. Мова програмування Matlab / Simulink 20.48 KB
  Скласти программу-функцію Matlab/Simulink для розв’язання задачі обробки одновимірного масиву у загальному вигляді, а обчислення на комп’ютері виконати для конкретних даних згідно з варіантом. Cформувати масив W з елементів масиву V, що задовольняють умову
36949. Використання засобів MathCAD, MS Excel для формування послідовностей випадкових чисел 56 KB
  Київ – 2011 Лабораторна робота №4 Тема: Використання засобів MthCD MS Exсel для формування послідовностей випадкових чисел. Мета: ознайомитися з основними видами розподілів випадкових чисел основними інструментами що використовуються при формування послідовностей випадкових чисел розглянути реалізацію методів формування цих послідовностей за допомогою різних інструментальних засобів MthCD Excel. Теоретична довідка У табличному процесорі Excel для формування послідовності випадкових чисел використовується...
36950. Побудова графіків в Matlab / Simulink 233.79 KB
  Висновок: під час лабораторної роботи я вивчив графічні можливості СКМ Matlab/Simulink.
36951. Вивчення універсального вимірювача Е7-11 при вимірюваннях індуктивності, ємності, опору, тангенса кута втрат й добротності елементів 378 KB
  Мета: Навчитись вимірювати індуктивність, ємність, опір, тангенса кута втрат й добротність елементів універсальним вимірювачем Е7-11.