28558

Новое направление в криптографии, постулаты У. Диффи и М. Хеллмана

Доклад

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

Это означает что если А является примитивным корнем простого числа Q тогда числа A mod Q A2 mod AQ1 mod Q являются различными и состоят из целых от 1 до Q 1 с некоторыми перестановками. В этом случае для любого целого B Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х такую что Y =AX mod Q где 0≤ X ≤ Q1. Экспонента X называется дискретным логарифмом или индексом Y по основанию A mod Q. Общеизвестные элементы Q Простое число A A Q и A является примитивным корнем Q Создание...

Русский

2013-08-20

23.14 KB

9 чел.

38. Новое направление в криптографии , постулаты  У. Диффи и М. Хеллмана

В середине 70-х гг. ХХ столетия произошел настоящий прорыв в современной криптографии – появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь

отправной точкой принято считать работу, опубликованную Уитфилдом Диффи и Мартином Хеллманом в 1976 г. под названием "Новые направления в современной криптографии". В ней впервые сформулированы принципы обмена шифрованной информацией без обмена секретным ключом.

Независимо к идее асимметричных криптосистем подошел Ральф Меркли. Несколькими годами позже Рон Ривест, Ади Шамир и Леонард Адлеман открыли систему RSA, первую практическую асимметричную криптосистему, стойкость которой была основана на проблеме факторизации больших простых чисел. Асимметричная криптография открыла сразу несколько новых прикладных направлений, в частности системы электроннойцифровой подписи (ЭЦП) и электронных денег.

В 1980–90-е гг. появились совершенно новые направления криптографии: вероятностное шифрование, квантовая криптография и другие. Осознание их практической ценности еще впереди. Актуальной остается и задача совершенствования симметричных криптосистем. В этот же период были разработаны нефейстелевские шифры (SAFER, RC6 и др.), а в 2000 г.после открытого международного конкурса был принят новый национальный стандарт шифрования США – AES.

Постулаты У. Диффи и М. Хеллмана:

1.   Ключ  KA для шифрования сообщений входящих к абоненту А должен изготовить сам абонент А. Он же изготавливает ключ KA-1  - для расшифрования данных сообщений.

2.   Ключ KA рассылается всем желающим, отправлять сообщения абоненту A, ключ KA-1 держится в секрете.

3.   Ключ KA-1 не восстанавливается по ключу KA.

Алгоритм Диффи-Хелмана (1976) использует функцию дискретного возведения в степень и используется для открытого распределения ключей по открытому каналу связи. 

Первая публикация данного алгоритма открытого ключа появилась в статье Диффи и Хеллмана, в которой вводились основные понятия криптографии с открытым ключом и в общих чертах упоминался алгоритм обмена ключа Диффи-Хеллмана.

Цель алгоритма состоит в том, чтобы два участника могли безопасно обменяться ключом, который в дальнейшем может использоваться в каком-либо алгоритме симметричного шифрования. Сам алгоритм Диффи-Хеллмана может применяться только для обмена ключами.

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

               A mod Q, A2 mod ……AQ-1 mod Q

 

являются различными и состоят из целых от 1 до Q – 1 с некоторыми перестановками. В этом случае для любого целого B < Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х, такую, что

Y =AX mod Q  ,где    0≤ X ≤ (Q-1).

Экспонента X называется дискретным логарифмом, или индексом Y, по основанию A mod Q. Это обозначается как

        indA,Q(Y)

Теперь опишем алгоритм обмена ключей Диффи-Хеллмана.

Общеизвестные элементы

Q

Простое число

A

A < Q и A является примитивным корнем Q

 

Создание пары ключей пользователем I

Выбор случайного числа  X i (закрытый ключ)

Xi<Q

Вычисление числа   Y i (открытый ключ)

Yi=AXimod Q

Создание открытого ключа пользователем J

Выбор случайного числа X j (закрытый ключ)

X j< Q

Вычисление случайного числа  Y j (открытый ключ)

Yj=A Ximod Q

Создание общего секретного ключа пользователем I

  K= (Yi)Ximod Q

Создание общего секретного ключа пользователем J

K=(Yj)Xjmod Q

Предполагается, что существуют два известных всем числа: простое число Q и целое A, которое является примитивным корнем Q. Теперь предположим, что пользователи I и J хотят обменяться ключом для алгоритма симметричного шифрования. Пользователь I выбирает случайное число Xi< Q и вычисляет  Y i=AXi mod Q. Аналогично пользователь J независимо выбирает случайное целое число Xj<Q и вычисляет Y i=AXj mod Q. Каждая сторона держит значение Х в секрете и делает значение Y доступным для другой стороны. Теперь пользователь I вычисляет ключ как  K=(Yi)Xi mod Q, и пользователь J вычисляет ключ как K= (Yj)Xj mod Q. В результате по правилам модульной арифметики оба получат одно и то же значение:

K= (Yj)Xi  mod Q= (AXj mod Q)Xi mod Q = (A Xj)Xi mod Q = A XjXi mod Q =

(A Xi)Xj mod Q= ( A Xi mod Q)Xj mod Q = ( Yi)Xj mod Q.

Таким образом, две стороны обменялись секретным ключом. Так как Xi и Xj являются закрытыми, противник может получить только следующие значения: Q, A, Yi и Yj. Для вычисления ключа атакующий должен взломать дискретный логарифм, т. е. вычислить

Xj = ind a,q(Yj)

Безопасность обмена ключа в алгоритме Диффи-Хеллмана вытекает из того факта, что, хотя относительно легко вычислить экспоненты по модулю простого числа, очень трудно вычислить дискретные логарифмы. Для больших простых чисел задача считается неразрешимой.

Следует заметить, что данный алгоритм уязвим для атак типа «man-in-the-middle». Если противник может осуществить активную атаку, т.е. имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников Yi и Y j, создать свою пару открытого и закрытого ключа   и послать каждому из участников свой открытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником. Если нет контроля целостности, то участники не смогут обнаружить подобную подмену.


 

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

27970. Восприятие как процесс категоризации в трудах Дж. Брунера 36.92 KB
  Личность и психика развитие личности и развитие психики: соотношение понятий. Личность и психика развитие личности и развитие психики: соотношение понятий. Понятие личности обозначает человеческого индивида как члена общества обобщает интегрированные в нем социально значимые черты. Петровский Ярошевский Развитие личности процесс качественных психологических личностных изменений в личности а также результат этих изменений.
27971. Память как высшая психическая функция 23.01 KB
  Психология этнической социализации и этнической идентичности. Психология этнической социализации и этнической идентичности. Этническая социализация выполняет функцию формирования множественной и многоуровневой идентичности личности способствующей конструктивному функционированию этничности в жизни индивида и общества: позитивной этнической идентичности и толерантного этнического взаимодействия. Одним из основных институтов этнической социализации является семья.
27972. Эффект Зейгарник. Этническая идентичность: общее описание, структура, становление и формирование, изменения этнической идентичности 18.62 KB
  Механизмы и эффекты межличностного восприятия Этническая идентичность: общее описание структура становление и формирование изменения этнической идентичности. Эффект Зейгарник. Эффект незавершенного действия эффект Зейгарник явление характеризующее влияние на процессы памяти перерывов в деятельности.
27973. Долговременная, кратковременная, оперативная и иконическая память 27.68 KB
  Социальнопсихологический тренинг как средство повышения точности межличностного восприятия Особенности межкультурной коммуникации развитие культурной сензитивности. Непосредственный отпечаток полезен в тех случаях когда сигнал действует очень недолго как при просмотре к ф; он обеспечивает также непрерывность восприятия при моргании или движении глаз. Социальнопсихологический тренинг как средство повышения точности межличностного восприятия В процессе общения должно присутствовать взаимопонимание между участниками этого процесса....
27974. Активное и пассивное, продуктивное и репродуктивное воображение 35.57 KB
  Феномен аттракции в межличностных отношениях различные уровни аттракции. Феномен аттракции в межличностных отношениях различные уровни аттракции. Область исследований связанных с выявлением механизмов образования различных эмоциональных отношений к воспринимаемому человеку получила название исследования аттракции. Феномен аттракции связан с перцептивной стороной межличностного общения возникает при включении в процесс восприятия эмоциональных регуляторов.
27975. Основные свойства внимания и методы их оценки 43.91 KB
  Основные свойства внимания и методы их оценки. В зависимости от объекта выделяют формы внимания: сенсорное перцептивное: зрительное и слуховое интеллектуальное моторное двигательное исполнительское. Внешнее внимание сенсорноперцептивное обращено на объекты внешнего мира необходимое условие познания и преобразования окружающего мира Внимание внутреннее интеллектуальное обращено на объекты субъективного мира человека необходимое условие самопознания и самовоспитания Виды внимания Джеймс По объекту: а чувственное...
27976. Когнитивные теории внимания и их критика. Этноцентризм и этнические стереотипы 28.85 KB
  Допускается существование группы механизмов селекции в канале ограниченной емкости в результате возникают отсеивание информации еще до момента ее полной идентификации в блоке Р. это процесс в котором два или более индивида или группы активно ищут возможность помешать друг другу достичь определенной цели предотвратить удовлетворение интересов соперника или изменить его взгляды и социальные позиции. когда группы с противоречивыми интересами поляризуются по этническому признаку. Всем известный пример внутригрушювого фаворитизма ...
27977. Мышление как регулятор деятельности и как самостоятельная деятельность Психология управления: объект, предмет, задачи. Основные теоретические школы менеджмента 65.33 KB
  Роль посредника в разрешении конфликтов Психология управления: объект предмет задачи. Поэтому в современном менеджменте навык управления конфликтами рассматривается как один из критически важных для менеджера. Цикл конфликта Первое чему необходимо научиться для успешного управления конфликтом это вовремя распознавать сигналы его эскалации. Схема выбора способа управления конфликтом Уровни конфликта в организации и их источники В любой организации существует несколько уровней конфликтов: внутриличностные межличностные межгрупповые...
27978. Мышление и интеллект, структура интеллекта, тестирование интеллекта и креативности 74.06 KB
  Проблема группы в социальной психологии. Оценка интеллекта Наибольшей популярностью пользуется так называемый коэффициент интеллектуальности сокращенно обозначаемый IQ который позволяет соотнести уровень интеллектуальных возможностей индивида со средними показателями своей возрастной и профессиональной группы. Две другие группы по 16 в каждой результаты которых соответствуют крайним показателям шкалы рассматриваются или как умственно отсталые люди со сниженным интеллектом IQ от 10 до 84 или как обладающие высокими выше среднего...