Понятие локальных вычислительных сетей, их структурные компоненты. Модель топологической структуры сети. Шифрование методом перестановки. Шифрующие таблицы, применение магических квадратов. Коммутация сообщений, маршрутизация, создание узлов сети.
Аннотация к работе
Создание элемента сети: выбрать пиктограмму элемента на панели инструментов, т.е. установить курсор мыши на соответствующую пиктограмму (при этом пиктограмма выделится рамочкой), выполнить двойное нажатие (клик) левой кнопкой мыши на пиктограмме, указатель мыши перенести в точку рабочей области, где необходимо разместить элемент, и снова выполнить клик левой кнопкой мыши, на рабочей области отобразится выбранный элемент, причем он будет размещен, начиная с ближайшей точки разметки. Выделение группы элементов: расположить курсор мыши на свободном месте рабочей области над элементами, при нажатой левой кнопке мыши переместить курсор мыши, при этом в направлении перемещения пунктирными линиями будет выделяться прямоугольная область, те элементы, которые попадут в эту область, считаются выделенными и закрашиваются синим цветом. Модель топологии сети представляет собой граф, где сегменты являются вершинами, а ретрансляторы - дугами, поэтому при исследовании модели сети можно оперировать понятиями из теории графов. Модель топологии сети представляет собой граф, где сегменты являются вершинами, а ретрансляторы - дугами, поэтому при исследовании модели сети можно оперировать понятиями из теории графов. средняя задержка запроса в сети - среднее время пребывания запроса в сети, определяемое по всем станциям с учетом времени пребывания в очереди, длительности окон наложения и времени передачи;Тема: Применение криптографических методов защиты информации Цель работы: Получить первичные навыки дешифрации информации. Теоретические сведения: Проблемой защиты информаций путем ее преобразования занимается криптология. Современная криптография включает в себя четыре крупных раздела: симметричные криптосистемы; криптосистемы с открытым ключом; системы электронной подписи; управление ключами. Криптографические методы защиты информаций в автоматизированных системах могут применятся как для защиты информаций, обрабатываемой в ЭВМ или хранящейся в различного типа ЗУ, так и для закрытия информаций, передаваемой между различными элементами системы по линиям связи. В качестве примеров алфавитов, используемых в современных ИС, можно привести следующие: алфавит Z33 - 32 буквы русского алфавита и пробел;При считывании содержимого первой таблицы по строкам и записи шифртекста группами по 5 букв получим шифрующее сообщение. Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы. для таблицы 3х3 - 36 вариантов; для таблицы 4х4 - 576 вариантов; для таблицы 5х5 - 14400 вариантов. Магические квадраты средних и больших размеров могли служить хорошей базой для обеспечения нужд шифрования того времени, поскольку практически нереально выполнить вручную перебор всех вариантов для такого шифра. При шифровании в этом полибианском квадрате находили очередную букву открытого текста и записывали в шифртекст букву, расположенную ниже ее в том же столбце. Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.).К числу таких задач относятся оптимизация пропускной способности каналов, выбор маршрутов и синтез топологической структуры сети. Обозначим через Прм путь, по которому передаются пакеты, возникающие в узле p и имеющие в качестве узла-адресата узел m. Пусть Q=||Qpm|| - матрица интенсивностей потока пакетов между узлами сети, где Qpm - интенсивность потока пакетов, возникающих в узле p и адресованных в узел m (трафик p-m). Среднее время задержки пакетов в пути (p,m) имеет, соответственно, вид: tpm ti t M i Пзь i 1 i ti где - интенсивность общего потока пакетов (пакет/с), поступающих в сеть: L L Чтобы создать узлы, надо перевести программу в режим проставления узлов - щелкнуть левой клавишей мыши по кнопке "Узлы" на панели инструментов.Основные характеристики технологии коммутации цепей: при вызове пользователи получают прямое соединение через коммутаторы в сети, прямое соединение эквивалентно паре проводов, соединяющих пользователей; коммутация цепей обеспечивает ограниченное наращивание функций. все фрагменты соединения должны иметь одинаковую пропускную способность, равную пропускной способности минимального канала. наибольшая задержка до начала передачи информации. необходимы дополнительные программные средства или микропрограммы к коммутатору, чтобы обеспечить наращиваемые функции. В отличие от коммутации цепей в телефонии коммутация сообщений является технологией типа "запомнить и послать", поскольку при коммутаторах используются запоминающие устройства, обычно дисковые накопители. Коммутаторы сообщений могут также использовать накопители на магнитных лентах для дублирования файлов с дисков, создания платежных записей или проверки счетов по всем транзакциям, обработанным коммутатором. Маршрутизация в сетях влечет использование логических средств (программных, аппаратных или микропрограммных) в коммутаторах для передвижения пакетов данных сквозь сеть к конечному назначению.
План
СОДЕРЖАНИЕ
ЛАБОРАТОРНАЯ РАБОТА № 1
ЛОКАЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СЕТИ (ЛВС) СТРУКТУРНЫЕ КОМПОНЕНТЫ ЛВС ПРОГРАММНЫЙ КОМПЛЕКС СИМЛВС ОТМЕНА ВЫДЕЛЕНИЯ ГРУППЫ ЭЛЕМЕНТОВ АНАЛИЗАТОР РЕЗУЛЬТАТОВ МОДЕЛИРОВАНИЯ МОДЕЛЬ ТОПОЛОГИЧЕСКОЙ СТРУКТУРЫ СЕТИ
ФУНКЦИЯ ДЛИТЕЛЬНОСТИ ВРЕМЕНИ ПЕРЕДАЧИ КАДРА ФУНКЦИЯ НЕСТАЦИОНАРНОСТИ ПОТОКА ЗАПРОСОВ ОТ СТАНЦИИ ФУНКЦИЯ ТЯГОТЕНИЯ
КОНТРОЛЬНЫЕ ВОПРОСЫ ВЫВОД
ЛАБОРАТОРНАЯ РАБОТА № 2 ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
ПРИМЕНЕНИЕ МАГИЧЕСКИХ КВАДРАТОВ ШИФРЫ ПРОСТОЙ ЗАМЕНЫ ПОЛИБИАНСКИЙ КВАДРАТ
АФИНСКАЯ СИСТЕМА ПОДСТАНОВОК ЦЕЗАРЯ СИСТЕМА ЦЕЗАРЯ С КЛЮЧЕВЫМ СЛОВОМ ШИФРУЮЩИЕ ТАБЛИЦЫ ТРИСЕМУСА БИГРАММНЫЙ ШИФР ПЛЕЙФЕЙРА
ШИФР ГРОНСФЕЛЬДА
СИСТЕМА ШИФРОВАНИЯ ВИЖИНЕРА
ХОД РАБОТЫ
ВЫВОД
ЛАБОРАТОРНАЯ РАБОТА № 4 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ
РАБОТА С ПРОГРАММОЙ.КОНСТРУИРОВАНИЕ ТОПОЛОГИИ СЕТИ ЗАДАНИЕ ОСНОВНЫХ ПАРАМЕТРОВ СЕТИ
ВЫБОР ЗАДАЧИ ОПТИМИЗАЦИИ ПОЛУЧЕНИЕ ИТОГОВ РАСЧЕТА
ОПТИМИЗАЦИЯ СРЕДНЕГО ВРЕМЕНИ ЗАДЕРЖКИ В СЕТИ ПРИ ОГРАНИЧЕНИИ НА
СТОИМОСТЬ
ХОД РАБОТЫ.СОЗДАНИЕ УЗЛОВ СЕТИ ВЫВОД
ЛАБОРАТОРНАЯ РАБОТА № 5 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ КОММУТАЦИЯ СООБЩЕНИЙ МАРШРУТИЗАЦИЯ
ХОД РАБОТЫ.СОЗДАНИЕ УЗЛОВ СЕТИ ИССЛЕДОВАНИЕ СЕТИ КОНТРОЛЬНЫЕ ВОПРОСЫ
ВЫВОД
Вывод
В данной лабораторной работе познакомились с принципами работы программного комплекса СИМЛВС. В программном комплексе СИМЛВС построили модель пятисегментной локальной сети, также построили ЛВС, состоящую из нескольких сегментов. Провели серию экспериментов над полученным объектом.
ЛАБОРАТОРНАЯ РАБОТА №2
Тема: Применение криптографических методов защиты информации Цель работы: Получить первичные навыки дешифрации информации. Теоретические сведения: Проблемой защиты информаций путем ее преобразования занимается криптология. Криптология разделяется на два направления - криптографию криптоанализ. Цели этих направлений прямо противоположны.
Криптография занимается поиском и исследованием математических методов преобразования информаций.
Сфера интересов криптоанализа - исследование возможности расшифровывания информаций без знания ключей.
Современная криптография включает в себя четыре крупных раздела: симметричные криптосистемы; криптосистемы с открытым ключом; системы электронной подписи; управление ключами.
Основные направление использования криптографических методов -передача конфиденциальной информаций по каналам связи (например, электронная почта), установление подлинности передаваемых сообщений, хранение информаций (документов, баз данных) на носителях в зашифрованном виде.
Криптографические методы защиты информаций в автоматизированных системах могут применятся как для защиты информаций, обрабатываемой в ЭВМ или хранящейся в различного типа ЗУ, так и для закрытия информаций, передаваемой между различными элементами системы по линиям связи.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
Алфавит - конечное множество используемых для кодирования информаций знаков.
Текст - упорядоченный набор из элементов алфавита.
В качестве примеров алфавитов, используемых в современных ИС, можно привести следующие: алфавит Z33 - 32 буквы русского алфавита и пробел;
алфавит Z256 - символы входящие в стандартные коды ASCП и КОИ-8;
бинарный алфавит - Z2 = {0,1};
восьмеричный или шестнадцатеричный алфавит.
Шифрование - преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом.
Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.
Ключ - информация, необходимая для беспрепятственного шифрования и дешифрования текстов.
Криптографическая система - представляет собой семейство Т преобразований открытого текста. Члены этого семейства индексируются или обозначаются символом k; параметр k является ключом.
Пространство ключей К - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.
Криптосистемы разделяются на симметричные и с открытым ключом. В симметричных криптосистемах и для шифрования, и для дешифрования используется один и тот же ключ.
В системах с открытым ключом используются два ключа - открытый и закрытый, которые математически связаны друг с другом. Информация шифруется с помощью открытого ключа, который доступен всем желающим, а расшифровывание с помощью закрытого ключа, известного только получателю сообщения.
Электронной (цифровой) подписью называется присоединяемое к тексту его криптографическое преобразование, которое позволяет при получений текста другим пользователем проверить авторство и подлинность сообщения.
Криптостойкостью называется характеристика шифра, определяющая его стойкость к дешифрованию без знания ключа (т.е. криптоанализу). Имеется несколько показателей криптостойкости, среди которых: количество всех возможных ключей;
среднее время, необходимое для криптоанализа.
Преобразование Тк определяется соответствующим алгоритмом и значением параметра к. Эффективность шифрования с целью зашиты данных может осуществляться как программно, так и аппаратно. Аппаратная реализация отличается существенно большей стоимостью, однако ей присущи и преимущества: высокая производительность, простота, защищенность и т.д. Программная реализация более практична, допускает известную гибкость в использований.
ШИФРОВАНИЕ МЕТОДОМ ПЕРЕСТАНОВКИ
Этот метод заключается в том, что символы шифруемого текста перестанавливаются по определенным правилам внутри шифруемого блока символов. Другими словами написать заданный текст задом на перед.
1 Изречение немецкого философа Фридриха Ницше: Имеющуюся фразу читаем с конца: ОЬТСО НЙАЧУ ЛСВТЯ РЕВЕН ИЛЕТИ ДЕБОП ПОБЕДИТЕЛИ НЕ ВЕРЯТ В СЛУЧАЙНОСТЬ О
2 Изречение немецкого ученого-гуманиста Эразма Роттердамского: Первые четыре буквы О лишние, убираем их и расшифровываем фразу: ЙЫТЫР КСТНА ЛАТЕН ТЕАДЗ ОСИИЦ АТУПЕ Р (ОООО) РЕПУТАЦИИ СОЗДАЕТ НЕ ТАЛАНТ СКРЫТЫЙ
В данном случае поступаем аналогично предыдущему варианту, с той разницей, что заполнять начинаем с верхнего левого угла (решетка размером 10х5):
ПОКОРНОСТЬ ОХЛАЖДАЕТ ГНЕВ И ДАЕТ РАЗМЕР ВЗАИМНЫМ ЧУВСТВАМ
6 Изречение политического деятеля времен А. Пугачевой: Берем решетку размером 6х5. Заполняем по спирали начиная с верхнего левого угла, идем вниз: ЭИЖЬМ НОЙАБ ОТЛМО НОККН ЭКОНЫ ОДААБ
ЭКОНОМИКА ДОЛЖНА БЫТЬ ЭКОНОМНОЙ
7 Толкование С.И. Ожеговым названия любимой дисциплины студентов экономического отделения ЛФПНИПУ: ЭАИАЛ КУПЮИ ОЧЛЩБ ННИАО ОАНЯО МЯАКТ ИДИАР КИЗКА АСУУС НЦЧЮЛ ЬТЯДТ ПВЙЕИ РЕСЯА ОНТТБ ИНВЕВ ЗОЕЛГ ВЙНЬД ОХННЕ ДОООЖ СЗЙСЗ
ЭКОНОМИКА НАУЧНАЯ ДИСЦИПЛИНА, ИЗУЧАЮЩАЯ КАКУЮ ЛИБО ОТРАСЛЬ ПРОИЗВОДСТВЕННОЙ ХОЗЯЙСТВЕННОЙ ДЕЯТЕЛЬНОСТИ
8 Используя ключевое слово "ЭКОНОМИКА" прочтите известную фразу: Для дешифровки, используя ключевое слово, нужно записать данное ключевое слово, затем расставить номера букв, как они расположены в алфавите. Данную зашифрованную фразу столбцами по три буквы записываем соответственно известным номерам: ГООСТ ОУАНЕ СОВЕО ТУЕСБ ЦЬДОП ДЛООО
Э К О Н О М И К А 9 3 7 6 8 5 2 4 1
П У С Т Ь В С Е Г
Д А Б У Д Е Т С О
Л Н Ц Е О О О О О
О О О О О О О О О
Пользуясь таблицей Вижинера зашифровать фразу: "Срочно переведите на наш счет миллион долларов за оказанную услугу". В качестве ключевого слова использовать фамилию Дудин.
С Р О Ч Н О П Е Р Е В Е Д И Т Е Н А Н
Д У Д И Н Д У Д И Н Д У Д И Н Д У Д И Х Ъ Т Ю Ы Т Ы И Ш Т Е Ш З С Ю И Э Д Ц
А Ш С Ч Е Т М И Л Л И О Н Д О Л Л А Р
Н Д У Д И Н Д У Д И Н Д У Д И Н Д У Д
Н Ь Ш Ы О Ю Р Ь П Ф Ц Т Э З Ч Ш П У Ф
О В З А О К А З А Н Н У Ю У С Л У Г У
И Н Д У Д И Н Д У Д И Н Д У Д И Н Д У
Ч П Л У Т У Н Л У С Ц Э Ь Ч Х Ф Э ЖПри выполнении данной лабораторной работы, получили первичные знания криптографии. Познакомились с некоторым и методами дешифрования. Научились подбирать верный метод для дешифровки сообщений.
ЛАБОРАТОРНАЯ РАБОТА №3
Тема: Применение криптографических методов защиты информации Цель работы: Получить первичные навыки шифрации информации.
В V в. до н.э. правители Спарты, наиболее воинственного из греческих государств, имели хорошо отработанную систему секретной военной связи и шифровали свои послания с помощью скитала, первого простейшего криптографического устройства, реализующего метод простой перестановки.
Шифрование выполняется следующим образом. На стержень цилиндрической формы, который назывался скитала, наматывали спиралью (виток к витку) полоску пергамента и писали на ней вдоль стержня несколько строк текста сообщения. Затем снимали снимали со стержня полоску пергамента с написанным текстом. Буквы на этой полоске оказывались расположены хаотечно. Такой же результат можно получить, если буквы сообщения писать не подряд, а через определенное число позиций до тех пор, пока не будет исчерпан весь текст.
Для расшифрования такого шифртекста нужно не только знать правило шифрования, но и обладать ключом в виде стержня определенного диаметра. Зная только вид шифра, но неимея ключа, расшифровать сообщение было непросто. Шифр скитала многократно совершенствовался в последующие времена.
ШИФРУЮЩИЕ ТАБЛИЦЫ
В качестве ключа в шифрующих таблицах используются: размер таблицы;
слово или фраза, задающая перестановку;
особенности структуры таблицы.
Одним из самых примитивных табличных шифров перестановок является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром скитала.
После заполнения таблицы текстом по столбцам для формирования шифртекста считывают содержимое таблицы по строкам. Шифртекст записывают группами по несколько букв.
Естественно отправитель и получатель сообщения должны заранее условиться об общем ключе в виде размера таблицы. Следует заметить, что объединение шифртекста в 5-буквенные группы не входит в ключ шифра и осущеtrialется для удобства записи несмыслового текста. При расшифровании действия выполняются в обратном порядке.
Несколько большей степенью к раскрытию обладает метод шифрования, называемый одиночной перестановкой по ключу. Этот метод отличается от предыдущего тем, что столбцы таблицы переставляются по ключевому слову, фразе или набору чисел длинной в строку таблицы.
В верхней строке первой таблицы записываем ключ, а номера под буквами ключа определены в соответствии с естественным порядком соответствующих букв ключа в алфавите. Если бы в ключе встречались одинаковые буквы, они бы были понумерованы слева направо. Во второй таблице столбцы переставлены в соответствии с упорядоченными номерами букв ключа.
При считывании содержимого первой таблицы по строкам и записи шифртекста группами по 5 букв получим шифрующее сообщение.
Для обеспечения дополнительной скрытости можно повторно зашифроватьсообщение, которое уже прошло шифрование. Такой метод шифрования называется двойной перестановкой. В случае двойной перестановки столбцов и строк таблицы перестановки определяются отдельно для столбцов и отдельно для строк. Сначала в таблицу записывается текст сообщения, а потом поочередно переставляются столбцы, а затем строки. При расшифровании порядок перестановок должен быть обратным.
Ключом к шифру двойной перестановки служит последовательность номеров столбцов и номеров строк исходной таблицы.
Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы. для таблицы 3х3 - 36 вариантов; для таблицы 4х4 - 576 вариантов; для таблицы 5х5 - 14400 вариантов.
Однако двойная перестановка не отличается высокой стойкостью и сравнительно просто "взламывается" при любом размере таблицы шиврования.
ПРИМЕНЕНИЕ МАГИЧЕСКИХ КВАДРАТОВ
В средние века для шифрования перестановкой применялись и магические квадраты
Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная от 1, которые в сумме дают по каждому столбцу, каждой строке и каждой диагонали одно и тоже число.
Шифруемый текст вписывается в магические квадраты в соответствии с нумерацией клеток. Если затем выписать содержимое такой таблицы по строкам, то получится шифртекст, сформированный благодаря перестановке букв исходного сообщения.
Число магических квадратов быстро возрастает с увеличением квадрата. Существует только один квадрат размером 3х3 (если не учитывать его повороты). Количество магических квадратов 4х4 составляет уже 880, а количество магических квадратов 5х5 - около 250000.
Магические квадраты средних и больших размеров могли служить хорошей базой для обеспечения нужд шифрования того времени, поскольку практически нереально выполнить вручную перебор всех вариантов для такого шифра.
ШИФРЫ ПРОСТОЙ ЗАМЕНЫ
При шифровании заменой (подстановко) символы шивруемого текста заменяются символами того же или другого алфавита с заранее установленным правилом замены. В шифре простой замены каждый символ исходного текста заменяется символами того же алфавита одинаково на всем протяжении текста. Часто шифры простой замены называют шифром одноалфавитной замены.
ПОЛИБИАНСКИЙ КВАДРАТ
Одним из первых шифров простой замены считается так называемый полибианский квадрат. За два века до нашей эры греческий писатель и историк Полибий изобрел для целей шифрования квадратную таблицу размером 5х5, заполненную буквами греческого алфавита в случайном порядке (таблица 1).
Таблица 1 - Полибианский квадрат, заполненный случайным образом 24 буквами греческого алфавита и пробелом
При шифровании в этом полибианском квадрате находили очередную букву открытого текста и записывали в шифртекст букву, расположенную ниже ее в том же столбце. Если буква текста оказывалась в нижней строке таблицы, то для шифртекста брали самую верхнюю букву из того же столбца.
Например, для слова получается шифртекст: Х
Концепция полибианского квадрата оказалась плодотворной и нашла применение в криптосистемах последующего времени.
Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.).
При шифровании исходного текста каждая буква заменялась на другую букву того же алфавита по следующему правилу. Заменяющая буква определялась путем смещения по алфавиту от исходной буквы на К букв. При достижении конца алфавита выполнялся циклический переход к его началу. Цезарь использовал шифр замены при смещении К = 3. Такой шифр замены можно задать таблицей подстановок, содержащей соответствующие пары букв открытого текста и шифртекста. Совокупность возможных подстановок для К = 3 показана в таблица 2.
Например, послание Цезаря VENI VIDI VICI, направленное его другу
Аминтию после победы над понтийским царем Фарнаком, сыном Митридата, выглядело бы в зашифрованном виде так: YHQL YLGL YLFL
АФИНСКАЯ СИСТЕМА ПОДСТАНОВОК ЦЕЗАРЯ
В системе шифрования Цезаря использовались только аддитивные свойства множества целых . Однако символы множества можно также умножать по модулю m. Применяя одновременно операции сложения и умножения по модулю m над элементами множества , можно получить систему подстановок, которую называют аффинной системой подстановок Цезаря.
Определим преобразование в такой системе:
(4)
где а,b - целые числа, 0<=а, b<m, НОД (a,m) = 1.
В данном преобразовании буква, соответствующая числу t, заменяется на букву, соответствующую числовому значению (at b) по модулю m. Следует заметить, что преобразование Ea,b (t) является взаимно однозначным отображением на множестве Zm только в том случае, если наибольший общий делитель чисел а и m, обозначаемый как НОД (а,m), равен единице, т.е. а и m должны быть взаимно простыми числами.
Например, пусть m=26, а=3, b=5. Тогда, очевидно, НОД (3,26) =1, и мы получаем следующее соответствие между числовыми кодами букв: Таблица 3
t 0 1 2
3t 5 5 8 11
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
14 17 20 23 0 3 6 9 12 15 18 21 24 1 4 7
19 20 21 22 23 24 25
10 13 16 19 22 25 2
Преобразуя числа в буквы английского языка, получаем следующее соответствие для букв открытого текста и шифртекста:
Таблица 4
А B C D Е F Q Н I J К
F I L O R U Х А D Q J
L М N 0 Р Q R
М Р S V Y В Е
S T U V W Х Y Z
Н K N Q Т W Z C
Исходное сообщение HOPE преобразуется в шифр AVYR
Достоинством аффинной системы является удобное управление ключами - ключи шифрования и расшифрования представляются в компактной форме в виде пары чисел (а, b). Недостатки аффинной системы аналогичны недостаткам системы шифрования Цезаря.
Аффинная система использовалась на практике несколько веков назад, а сегодня ее применение ограничивается большей частью иллюстрациями основных криптологических положений.
СИСТЕМА ЦЕЗАРЯ С КЛЮЧЕВЫМ СЛОВОМ
Система шифрования Цезаря с ключевым словом является одноалфавитной системой подстановки. Особенностью этой системы является использование ключевого слова для смещения и изменения порядка символов в алфавите подстановки.
Выберем некоторое число k, , и слово или короткую фразу в качестве ключевого слова. Желательно, чтобы все буквы ключевого слова были различными. Пусть выбраны слово DIPLOMAT в качестве ключевого слова и число k = 5.
Ключевое слово записывается под буквами алфавита, начиная с буквы, числовой код которой совпадает с выбранным числом k.
Оставшиеся буквы алфавита подстановки записываются после ключевого слова в алфавитном порядке.
Теперь мы имеем подстановку для каждой буквы произвольного сообщения.
Исходное сообщение SEND MORE MONEY шифруется как HZBY TCGZ TCBZS
Следует отметить, что требование о различии всех букв ключевого слова не обязательно. Можно просто записать ключевое слово (или фразу) без повторения одинаковых букв.
Несомненным достоинством системы Цезаря с ключевым словом является то, что количество возможных ключевых слов практически неисчерпаемо. Недостатком этой системы является возможность взлома шифртекста на основе анализа частот появления букв.
ШИФРУЮЩИЕ ТАБЛИЦЫ ТРИСЕМУСА
В 1508 г. аббат из Германии Иоганн Трисемус написал печатную работу по криптологии под названием "Полиграфия". В этой книге он впервые систематически описал применение шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получения такого шифра замены обычно использовались таблица для записи букв алфавита и ключевое слово (или фраза). В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались. Затем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку.
Поскольку ключевое слово или фразу легко хранить в памяти, то такой подход упрощал процессы шифрования и расшифрования. Поясним этот метод шифрования на примере. Для русского алфавита шифрующая таблица может иметь размер 4х8. Выберем в качестве ключа слово БАНДЕРОЛЬ (таблица 3).
Таблица 5. Шифрующая таблица с ключевым словом
Б А Н Д Е Р О Л
Ь В Г Ж 3 И Й К
М П С Т У Ф Х Ц
Ч Ш Щ Ы Ъ Э Ю Я
Как и в случае полибианского квадрата, при шифровании находят в этой таблице очередную букву открытого текста и записывают в шифртекст букву, расположенную ниже ее в том же столбце. Если буква текста оказывается в нижней строке таблицы, тогда для шифртекста берут самую верхнюю букву из того же столбца.
Например, при шифровании с помощью этой таблицы сообщения ВЫЛЕТАЕМПЯТОГО получаем шифртекст ПДКЗЫВЗЧШЛЫЙСЙ
Такие табличные шифры называются монограммными, так как шифрование выполняется по одной букве. Трисемус первым заметил, что шифрующие таблицы позволяют шифровать сразу по две буквы. Такие шифры называются биграммными.
БИГРАММНЫЙ ШИФР ПЛЕЙФЕЙРА
Шифр Плейфейра, изобретенный в 1854 г., является наиболее известным биграммным шифром замены. Он применялся Великобританией во время первой мировой войны. Основой шифра Плейфейра является шифрующая таблица со случайно расположенными буквами алфавита исходных сообщений.
Для удобства запоминания шифрующей таблицы отправителем и получателем сообщений можно использовать ключевое слово (или фразу) при заполнении начальных строк таблицы. В целом структура шифрующей таблицы системы Плейфейра полностью аналогична структуре шифрующей таблицы Трисемуса. Процедура шифрования включает следующие шаги: 1. Открытый текст исходного сообщения разбивается на пары букв (биграммы). Текст должен иметь четное количество букв и в нем не должно быть биграмм, содержащих две одинаковые буквы. Если эти требования не выполнены, то текст модифицируется даже изза незначительных орфографических ошибок.
2. Последовательность биграмм открытого текста преобразуется с помощью шифрующей таблицы в последовательность биграмм шифртекста по следующим правилам: 2.1 Если обе буквы биграммы открытого текста не попадают на одну строку или столбец (как, например, буквы А и Й в табл. на рис.8), тогда находят буквы в углах прямоугольника, определяемого данной парой букв. (В нашем примере это буквы АЙОВ. Пара букв АЙ отображается в пару 0В. Последовательность букв в биграмме шифртекста должна быть зеркально расположенной по отношению к последовательности букв в биграмме открытого текста).
2.1 Если обе буквы биграммы открытого текста принадлежат одному столбцу таблицы, то буквами шифртекста считаются буквы, которые лежат под ними. (Например, биграмма НС дает биграмму шифртекста ГЩ.) Если при этом буква открытого текста находится в нижней строке, то для шифртекста берется соответствующая буква из верхней строки того же столбца. (Например, биграмма ВШ дает биграмму шифртекста ПА.)
2.2 Если обе буквы биграммы открытого текста принадлежат одной строке таблицы, то буквами шифртекста считаются буквы, которые лежат справа от них. (Например, биграмма НО дает биграмму шифртекста ДЛ.) Если при этом буква открытого текста находится в крайнем правом столбце, то для шифра берут соответствующую букву из левого столбца в той же строке. (Например, биграмма ФЦ дает биграмму шифртекста ХМ.).
Зашифруем текст
ВСЕ ТАЙНОЕ СТАНЕТ ЯВНЫМ Разбиение этого текста на биграммы дает ВС ЕТ АЙ НО ЕС ТА НЕ ТЯ ВН ЫМ
Данная последовательность биграмм открытого текста преобразуется с помощью шифрующей таблицы (см. рис.8) в следующую последовательность биграмм шифртекста
ГП ДУ ОВ ДЛ НУ ПД ДР ЦЫ ГА ЧТ
При расшифровании применяется обратный порядок действий.
Следует отметить, что шифрование биграммами резко повышает стойкость шифров к вскрытию. Хотя книга И. Трисемуса "Полиграфия" была относительно доступной, описанные в ней идеи получили признание лишь спустя три столетия. По всей вероятности, это было обусловлено плохой осведомленностью криптографов о работах богослова и библиофила Трисемуса в области криптографии.
ШИФР ГРОНСФЕЛЬДА
Этот шифр сложной замены, называемый шифром Гронсфельда, представляет собой модификацию шифра Цезаря числовым ключом. Для этого под буквами исходного сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Шифртекст получают примерно, как в шифре Цезаря, но отсчитывают по алфавиту не третью букву (как это делается в шифре Цезаря), а выбирают ту букву, которая смещена по алфавиту на соответствующую цифру ключа. Например, применяя в качестве ключа группу из четырех начальных цифр числа e (основания натуральных логарифмов), а именно 2718, получаем для исходного сообщения ВОСТОЧНЫЙ ЭКСПРЕСС следующий шифртекст:
Таблица 6 - шифр Гронсвельда
Сообщение В О С Т
Ключ 2 7 1 8
Шифртекст Д Х Т Ь
О Ч Н Ы Й Э К С П Р Е С С
2 7 1 8 2 7 1 8 2 7 1 8 2
Р Ю О Г Л Д Л Щ С Ч Ж Щ У
Чтобы зашифровать первую букву сообщения В, используя первую цифру ключа 2, нужно отсчитать вторую по порядку букву от В в алфавите, получается первая буква шифртекста Д.
Следует отметить, что шифр Гронсфельда вскрывается относительно легко, если учесть, что в числовом ключе каждая цифра имеет только десять значений, а значит, имеется лишь десять вариантов прочтения каждой буквы шифртекста. С другой стороны, шифр Гронсфельда допускает дальнейшие модификации, улучшающие его стойкость, в частности двойное шифрование разными числовыми ключами.
Шифр Гронсфельда представляет собой по существу частный случай системы шифрования Вижинера.
СИСТЕМА ШИФРОВАНИЯ ВИЖИНЕРА
Система Вижинера впервые была опубликована в 1586 г. и является одной из старейших и наиболее известных многоалфавитных систем. Свое название она получила по имени французского дипломата XVI века Блеза Вижинера, который развивал и совершенствовал криптографические системы.
Система Вижинера подобна такой системе шифрования Цезаря, у которой ключ подстановки меняется от буквы к букве. Этот шифр многоалфавитной замены можно описать таблицей шифрования, называемой таблицей (квадратом) Вижинера. На рис.10 и 11 показаны таблицы Вижинера для русского и английского алфавитов соответственно.
Таблица Вижинера используется для зашифрования и расшифрования. Таблица имеет два входа: верхнюю строку подчеркнутых символов, используемую для считывания очередной буквы исходного открытого текста;
крайний левый столбец ключа.
Последовательность ключей обычно получают из числовых значений букв ключевого слова.
При шифровании исходного сообщения его выписывают в строку, а под ним записывают ключевое слово (или фразу). Если ключ оказался короче сообщения, то его циклически повторяют. В процессе шифрования находят в верхней строке таблицы очередную букву исходного текста и в левом столбце очередное значение ключа. Очередная буква шифртекста находится на пересечении столбца, определяемого шифруемой буквой, и строки, определяемой числовым значением ключа.
Пусть ключевая последовательность имеет длину r, тогда ключ r-алфавитной подстановки есть r-строка
Система шифрования Вижинера преобразует открытый текст в шифртекст с помощью ключа согласно правилу
(10)
где .
Таблица 7 - таблица Вижинера для русского алфавита
А Б В Г Д Е
0 А Б В Г Д Е
1 Б В Г Д Е Е
2 В Г Д Е Е Ж 3 Г Д Е Е Ж З
4 Д Е Е Ж З И 5 Е Е Ж З И Й
6 Е Ж З И Й К
7 Ж З И Й К Л
8 З И Й К Л М
9 И Й К Л М Н
10 Й К Л М Н О
11 К Л М Н О П
12 Л М Н О П Р
13 М Н О П Р С
14 Н О П Р С Т
15 О П Р С Т У
16 П Р С Т У Ф
17 Р С Т У Ф Х
18 С Т У Ф Х Ц
19 Т У Ф Х Ц Ч
20 У Ф Х Ц Ч Ш
21 Ф Х Ц Ч Ш Щ
22 Х Ц Ч Ш Щ Ъ
Е Ж З И Й К Л М Н О П Р
Е Ж З И Й К Л М Н О П Р
Ж З И Й К Л М Н О П Р С
З И Й К Л М Н О П Р С Т
И Й К Л М Н О П Р С Т У
Й К Л М Н О П Р С Т У Ф
К Л М Н О П Р С Т У Ф Х
Л М Н О П Р С Т У Ф Х Ц
М Н О П Р С Т У Ф Х Ц Ч
Н О П Р С Т У Ф Х Ц Ч Ш
О П Р С Т У Ф Х Ц Ч Ш Щ
П Р С Т У Ф Х Ц Ч Ш Щ Ъ
Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы
С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь
Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э
У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю
Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я Ю
Ц Ч Ш Щ Ъ Ы Ь Э Ю Я Ю Э
Ч Ш Щ Ъ Ы Ь Э Ю Я Ю Э Ь
Ш Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы
Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ
Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ
Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш
С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я Ю
У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я Ю Э
Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я Ю Э Ь
Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы
Ц Ч Ш Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ
Ч Ш Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ
Ш Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш
Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч
Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц
Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х
Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф
Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У
Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У Т
Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У Т С
Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У Т С Р
Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У Т С Р П
Ь Ы Ъ Щ Ш Ч Ц Х Ф У Т С Р П О
Ы Ъ Щ Ш Ч Ц Х Ф У Т С Р П О Н
Ъ Щ Ш Ч Ц Х Ф У Т С Р П О Н М
Щ Ш Ч Ц Х Ф У Т С Р П О Н М Л
Ш Ч Ц Х Ф У Т С Р П О Н М Л К
Ч Ц Х Ф У Т С Р П О Н М Л К Й
23 Ц Ч Ш Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч
24 Ч Ш Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц
25 Ш Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х
26 Щ Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф
27 Ъ Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У
28 Ы Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У Т
29 Ь Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У Т С
30 Э Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У Т С Р
31 Ю Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У Т С Р П
32 Я Ю Э Ь Ы Ъ Щ Ш Ч Ц Х Ф У Т С Р П О
Ц Х Ф У Т С Р
Х Ф У Т С Р П
Ф У Т С Р П О
У Т С Р П О Н
Т С Р П О Н М
С Р П О Н М Л
Р П О Н М Л К
П О Н М Л К Й
О Н М Л К Й И Н М Л К Й И З
П О Н М Л К Й И О Н М Л К Й И З
Н М Л К Й И З Ж М Л К Й И З Ж Е
Л К Й И З Ж Е Е
К Й И З Ж Е Е Д
Й И З Ж Е Е Д Г
И З Ж Е Е Д Г В
З Ж Е Е Д Г В Б
Ж Е Е Д Г В Б А ХОД РАБОТЫ
Зашифровать текст "Лысьвенский университетский комплекс".
Метод Скитала ЛННИИПЫСИТЙЛСКВЕКЕЬИЕТОКВЙРСМСЕУСК
Л Е Й Е Е Й Л Ы Н У Р Т К Е С С Н С С О К Ь К И И К М С В И В Т И П О
ЛЕЙЕЕ ЙЛФНУ РТКЕС СНССО КЬКИИ КМСВИ ВТИПО
Шифрующие таблицы
П Е Л И К А Н
7 2 5 3 4 1 6
Л Е Й Е Е Й Л
Ы Н У Р Т К Е
С С Н С С О К
Ь К И И К М С
В И В Т И П О
А Е И К Л Н П
1 2 3 4 5 6 7
Й Е Е Е Й Л Л
К Н Р Т У Е Ы
О С С С Н К С
М К И К И С Ь
П И Т И В О В
ЙЕЕЕЙ ЛЛКНР ТУЕЫО СССНК СМКИК ИСЬПИ ТИВОВ
Шифрующие таблицы. Двойная перестановка
1 3 5 7 6 4 2
2 Л Ы С Ь В Е Н
4 С К И Й У Н И 5 В Е Р С И Т Е
3 Т С К И Й К О
1 М П Л Е К С О
1 2 3 4 5 6 7
2 Л Н Ы Е С В Ь
4 С И К Н И У Й
5 В Е Е Т Р И С
3 Т О С К К Й И 1 М О П С Л К Е
1 2 3 4 5 6 7
1 М О П С Л К Е
3 Т О С К К Й И 2 Л Н Ы Е С В Ь
4 С И К Н И У Й
5 В Е Е Т Р И С
МОПСЛ КЕТОС ККЙИЛ НЫЕСВ ЬСИКН ИУЙВЕ ЕТРИС
Применение магических квадратов
6 2 7 Е О К
1 5 9 К Л О
8 3 4 С М П
ЕОК КЛО СМП
Полибианский квадрат
С Ф Щ В Ш Н Ь Ж Ъ А Л К Б Ю Е П
З У О Я Х Р Ц Э
Ч Й Ы Д М И Г Т
ОЩЪЕВЦЮЪЯНФ ЙЮНКЦИЪЯНФ ЯШЭОЯЪ
Система шифрования Цезаря
А Э И Е Р Н Ш Х
Б Ю Й Ж С О Щ Ц
В Я К З Т П Ъ Ч
Г А Л И У Р Ы Ш
Д Б М Й Ф С Ь Щ
Е В Н К Х Т Э Ъ
Ж Г О Л Ц У Ю Ы
З Д П М Ч Ф Я Ь
ИШОЯВКОЗЕЖ РКЕЯВНОЕПВПОЗЕЖ ЗЛЙМИЗО
Аффинская система подстановок Цезаря
Пусть m=32, а=3, b=5, тогда очевидно, что НОД (3,32) =1, и мы получаем соответствие между числовыми кодами букв: T 0 1 2 3 4
3t 5 5 8 11 14 17
5 6 7 8 9 10 11 12 13 14 15
20 23 6 29 0 3 6 9 12 15 18
16 17 18 19
21 24 27 30
20 21 22 23 24 25 26 27 28 29 30 31
1 4 7 10 13 16 19 22 25 28 31 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
А Б В Г Д Е Ж З И Й К Л М Н О П
Е И Л О С Ф Ч У Э А Г Ж Й М П Т
16 17 18 19
Р С Т У
Х Ш Ы Ю
20 21 22 23 24 25 26 27 28 29 30 31
Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
Б Д З К Н Р У Ц Щ Ь Я В
ЖЦШЩЛФМ ШГЭА ЮМЭЛФЪШЭЫФЫШГЭА ГПЙТЖФГШ
Система Цезаря с ключевым словом
В качестве ключевого слова берем имя Ольга и число k=6
А Б В Г Д Е Ж З И Й К Л М Н О П Щ Ъ Ы Э Ю Я О Л Ь Г А Б В Д Е Ж
Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
З И Й К М Н П Р С Т У Ф Х Ц Ч Ш
БФИХЫЯДИАЬГ КДЬЫЯЗИЬЙЯЙИАЬГ АЕВЖБЯАИ
Шифрующие таблицы Трисемуса
О Л Ь Г А Б В Д
Е Ж З И Й К М Н
П Р С Т У Ф Х Ц
Ч Ш Щ Ъ Ы Э Ю Я
ЖАЩЗМПЦЩФТУ ЫЦТМПШЩТЪПЪЩФТУ ФЕХЧЖПФЩ
Биграмный шифр Плейфейра
О Л Ь Г А Б В Д
Е Ж З И Й К М Н
П Р С Т У Ф Х Ц
Ч Ш Щ Ъ Ы Э Ю Я
ЛЫ СЬ ВЕ НС КИ ЙУ НИ ВЕ РС ИТ ЕТ СК ИЙ КО МП ЛЕ КС АШ ЗЩ ОМ ЗЦ ЙМ ЫУ ЙЕ ОМ СТ ЪТ ИП ФЗ КЙ ЕБ ЕХ ОЖ ЗФ Шифр Гронсвельда
Число 2718
Л Ы С Ь В Е Н С К И Й 2 7 1 8 2 7 1 8 2 7 1 Н В Т Д Д М О Щ М П К
У Н И В Е Р С И Т Е Т С К И Й
8 2 7 1 8 2 7 1 8 2 7 1 8 2 7
Ы П П Г Н Т Ш Й Ъ З Щ Т Т К Р
К О М П Л Е К С
1 8 2 7 1 8 2 7
Л Ц О Ц М Н Л Ш
Система шифрования Вижинера
Л Ы С Ь В Е Н С К И Й
Д У Д И Н Д У Д И Н Д
П П Х Щ П И Э Х У Ц Н
У Н И В Е Р С И У Д И Н Д У Д И Ч С С П И Ъ Х С
Т Е Т С К И Й
Н Д У Д И Н Д
Ю И Ш Х У Ц Н
К О М П Л Е К С
У Д И Н Д У Д И Ю Т Х Э П Ш О Ъ
Шифр "двойной квадрат" Уитстона
Ж 9Р Ъ В Ф Д Ъ Л Щ В
О А Е П Ь С И А Р Я
Ц К Ы У Й П Ц Т Й
Н Э Я Л Б Э . О У Ы
Т Г Щ . К Г Е Н Ж И С Ю Д Ч Ю Ш Б Ф Ч
Х Ш З , М З Х М Ь ,
ЛЫ СЬ ВЕ НС КИ
УБ ФШ ЛЩ ЭО ЦА
Й_ УН ИВ ЕР
ЙУ _Щ ЧЖ АП
СИ ТЕ ТС КИ Й_ КО МП ЛЕ КС
ША ГГ КА ЦА ЙУ ТЭ ЗЙ ОЩ ПАВо время выполнения данной лабораторной работы были изучены различные методы шифрования и также были применены практически.
ЛАБОРАТОРНАЯ РАБОТА №4
Тема: Аналитическое моделирование вычислительных сетей: задача оптимизации стоимостных характеристик сети при заданном среднем времени задержки;
задача оптимизации среднего времени задержки в сети при ограничении на стоимость.
Цель работы: Изучить основы построения оптимальных сетей при заданном среднем времени задержки или при ограничении на стоимость.
ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Задачи оптимизации параметров реальных сетей представляют собой весьма трудную проблему математического программирования. К числу таких задач относятся оптимизация пропускной способности каналов, выбор маршрутов и синтез топологической структуры сети.
Выбор маршрута определяется с целью передачи пакета через сеть оптимальным образом при заданном входном потоке и способе маршрутизации. Различают статическую и динамическую маршрутизацию. В первом случае маршрут выбирается между каждой парой источник-адресат в соответствии с априорно заданными входными данными, во втором -адаптивно в соответствии с текущими изменениями потока и состояния сети. В рамках статической маршрутизации задача выбора оптимального пути состоит в оптимальном распределении потоков в каналах сети.
Обозначим через Прм путь, по которому передаются пакеты, возникающие в узле p и имеющие в качестве узла-адресата узел m. Пусть Q=||Qpm|| - матрица интенсивностей потока пакетов между узлами сети, где Qpm - интенсивность потока пакетов, возникающих в узле p и адресованных в узел m (трафик p-m).
Интенсивность потока пакетов i (пакетов/с), проходящих через i - ый канал связи:
i p
Qpm m p,m :i Прм i 1,M
где i Прм означает, что сообщение, идущее по пути (p,m), проходит через i-ый канал, М - число каналов в сети.
Среднее время задержки пакетов в пути (p,m) имеет, соответственно, вид:
tpm ti t M i Пзь i 1
i ti где - интенсивность общего потока пакетов (пакет/с), поступающих в сеть:
L L
Qpm p 1 m 1
ti - среднее время пребывания пакетов в i-ом канале;
L - число узлов в сети.
Среднее время задержки в предположении о пуассоновском потоке поступления пакетов в каждый канал и экспоненциальном распределении длины сообщений со средним значением V = 1/ (бит) определяется по формуле:
M t i ti i 1
1 M i i 1 Wi i где Wi - пропускная способность i-ого канала.
ti
1
Wi i
Предполагается, что среднее время обработки в узле Т равно 0, т.к. этим временем можно пренебречь.
В общем случае, если учитывать время обработки в узле Т, среднее время задержки определяется по формуле:
t T 1 M i 1
i
Wi i
T
В формуле дополнительное слагаемое Т возникло изза того, что сообщения при их движении по сети проходят число узлов на один больше, чем число каналов.
При проектировании сетей передачи данных возникает задача оптимального выбора пропускных способностей каналов из конечного набора их возможных значений. Решение задачи дискретной оптимизации (при большом числе вариантов структуры сети) является трудоемким. Поэтому задача синтеза структуры сети может решаться в начале в постановке нелинейного программирования. Предполагается, что искомые производительности каналов связи являются непрерывными переменными, в то время как в действительности эти переменные являются дискретными. Затем может следовать дискретный поиск, т.е. выбор вариантов структуры из нескольких возможных, наиболее близких к непрерывному оптимуму.
Под стоимостью сети понимается стоимость каналов связи, а также средств передачи данных (мультиплексоров, адаптеров, модемов). Зависимость стоимости сети от пропускных способностей каналов выглядит следующим образом:
M
F KIWIAI i 1
где ki - стоимостный коэффициент в i-ом канале;
ai - коэффициент нелинейности, имеющий значение в пределах: Величины ki и ai определяются путем регрессионного анализа зависимостей пропускных способностей канала от его стоимости.
0 ai 1i 1,M
Постановка задачи минимизации среднего времени задержки пакетов при ограничении на стоимость сети
M mint i ti i 1
M i i i 1 Wi i
При ограничениях
F W1 > 0, …, WM > 0
M
KIWIAI S i 1
Оптимальное решение, найденное методом неопределенных множителей Лагранжа, находится из системы нелинейных уравнений с М 1 неизвестным
1 ai W1, …, WM, : Wi Wi 2
i i ai ki
M
KIWI ai S i 1
где - вспомогательное неизвестное (неопределенный множитель
Лагранжа).
Для частного случая аі = 1 (i = 1,M), т.е. при линейной функции стоимости, точное решение имеет вид:
Wi i
S* ki ki i
M ki i i 1
M
Где: S* S ki i S* 0 i 1
Постановка задачи минимизации стоимости сети при среднем времени задержки пакетов, не превосходящем заданного:
M
MINF KIWIAI i 1
При ограничениях
Wi i Тдоп
M t i i 1
i
Wi i
Тдоп
Оптимальное решение находится по формуле: M i i 1
ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ
При работе с лабораторным комплексом NETMASTER пользователь имеет дело со стандартным Windows-интерфейсом. А именно: главное окно программы, меню, панель инструментов, строка состояния.
В главном окне отображается рабочая область программы с изображением карты Республики Татарстан. Эта область предназначена для создания топологической структуры сети (как это делается см. далее).
Меню Файл содержит стандартные команды: создать новый документ, открыть ранее сохраненный документ, сохранить документ, список последних пяти открываемых документов, выход из программы.
Меню Аналитическая модель включает пункты Общие параметры, Параметры определения топологии сети, Сгенерировать топологию, Минимизация стоимости сети, Минимизация среднего времени задержки. С помощью первого можно задать общие параметры сети, таких как интенсивности потока пакетов между узлами сети, при решении различных оптимизационных задач. С помощью второго задаются параметры определяющие ограничения при построении оптим