Обмен ключами по схеме Диффи-Хеллмана

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

Для любого целого числа b и любого первообразного корня a простого числа p однозначно определяется показатель степени i, при котором . Этот показатель степени называется дискретным логарифмом.

Рассмотрим теперь обмен ключами по схеме Диффи-Хеллмана. В этой схеме имеются два открытых для всех числа: простое число q и целое число , являющееся первообразным корнем q. Предположим, что пользователи A и B намерены обменяться ключами. Пользователь A выбирает случайное целое число и вычисляет . Аналогично пользователь B независимо выбирает случайное целое число и вычисляет . Каждая сторона сохраняет X в тайне, а значение Y делает свободно доступным другой стороне. Пользователь A вычисляет ключ по формуле , а пользователь B – по формуле . Эти две формулы при вычислении дают одинаковый результат. Защищенность обмена ключами по схеме Диффи-Хеллмана опирается на то, что в то время, как степени по модулю некоторого простого числа вычисляются относительно легко, вычислять дискретные логарифмы оказывается очень трудно. Для больших простых чисел эта задача считается практически неразрешимой.

Пример. Обмен ключами строится на использовании простого числа q=71 и его первообразного корня . Пользователи A и B выбирают секретные ключи . Каждый вычисляет свой открытый ключ: и . После того как пользователи обменяются открытыми ключами, каждый из них сможет вычислить общий секретный ключ: и . Имея {51,4}, противнику не удастся с легкостью вычислить 30.

3. Задания

Для RSA-системы с простыми p=7 и q=13 и ключом шифрования e=5, вычислите:

1. значение частного ключа d;

2. используя данную систему, зашифруйте сообщение и проверьте, что можно дешифровать получившийся в результате код обратно в сообщение.

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

4. Контрольные вопросы

1. Как осуществляется распределение ключей в криптосистемах с общим ключом?

2. Дайте определение односторонней функции?

3. Что представляет собой криптосистема RSA?

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

Связность сети

1. Цель работы

Научиться определять насколько хорошо различные части сети соединены друг с другом, и какие в ней имеются маршруты.

2. Краткие теоретические сведения

Ключевой концепцией коммутации является связность, которая определяет, насколько легко добираться из одной точки сети в другую. Для решения этой проблемы используют теорию графов. В этом случае сеть представляется в виде набора узлов, объединенных связями. Направленные связи обеспечивают трафик (поток обмена информацией) в одном направлении, тогда как ненаправленные связи обеспечивают двухсторонний трафик. Узлы называются смежными, если имеются прямые связи между ними. Степенью узла называют количество связей, заканчивающихся на этом узле. Минимальная степень всей сети определяется минимальной степенью любого из ее узлов. Регулярный граф состоит из узлов одинаковой степени. Примером регулярного графа степени 2 является кольцо.

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

Рис. 7 Сети с разделенными связями и узлами

Пути ABCDE и AFGHE первой сети (а) имеют разделенные связи, а маршруты ABCDE и ABC – нет. Во второй сети (б) разделенными связями обладают пути STUWX и SUX. Пути с разделенными узлами – это такие пути, у которых нет общих узлов. Пути ABCDE и AFGHE сети (а) имеют разделенные узлы, а маршруты STUWX и SUX сети (б) – нет. Концепция разделенных путей важна при рассмотрении надежности сети. Два пути между узлами M и N в сети (в) разделены как по связям, так и по узлам, и если связь или узел в одном из соединяющих их маршрутов отказывают, то все еще существует доступный путь для передачи данных между этими двумя источниками. С другой стороны, между узлами M и P существует два возможных пути, но они не разделены по связям и узлам, так что если узел N или O или связь Q откажут, то никакого альтернативного пути существовать не будет и соединение прервется.

Н адежность сети, т.е. ее способность противостоять отказу узла или связи, зависит от количества разделенных узлов или связей между узлами источника и адресата. Связность по звеньям между двумя узлами определяется как минимальное число звеньев, которые должны быть удалены, чтобы отсоединить источник от адресата.

Рис 8. Различные отсечения на образце сети

Например, минимальное число связей, которые должны быть удалены для отсоединения узла C от узла J, показанной, на рисунке равно 3. Это значение можно определить, проводя на графе отсекающие линии (cs1, cs2, ...). Минимальным является то отсечение, которое пересекает самое малое число связей. Размер минимального отсечения – это число разделенных путей между узлами C и J, что и определяет их связность по звеньям.

Степень связности определяет относительную устойчивость сети. Существует несколько алгоритмов, которые отвечают на вопрос, имеет ли данная сеть связность, равную m. Пригодность используемого алгоритма зависит от скорости достижения им соответствующего заключения, которая зависит от размеров сети. Рассмотрим два таких алгоритма – Клейтмана и Ивена.