Изобразить схему Файстеля, лежащую в основе большинства современных симметричных алгоритмов шифрования, объяснить преимущества, доказать корректность схемы

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

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

Рассмотрим структуру шифра Файстеля. Данный шифр относится к категории блочных. Блочные шифры предназначены для шифрования небольших блоков определенной длины. Для того, чтобы зашифровать произвольный текст, его необходимо разбить на блоки, после чего каждый блок зашифровывается отдельно (вариации рассматриваются в следующем разделе). Кроме того, как и практически все современные алгоритмы, шифр Файстеля работает с двоичным алфавитом (т.е. и открытый и зашифрованный текст представлены последовательностью битов) и предназначен для реализации на ЭВМ.

На вход алгоритма шифрования подается блок открытого текста, имеющий четную длину 2l и ключ K. Блок разделяется на две равные части – правую R0 и левую L0. Далее эти части проходят m раундов обработки, после чего снова объединяются в зашифрованный текст.

Каждый i -й раунд состоит в генерации подключа Ki (на основе общего ключа K) и применении к блоку Ri некоторого зависящего от ключа преобразования F. Результат складывается с блоком Li с помощью операции XOR (исключающее или) и получается блок Ri+1. Блок Ri без изменений берется в качестве блока Li+1.

Различные алгоритмы, использующие структуру шифра Файстеля могут отличаться следующими параметрами:

• Длина ключа. Чем длиннее ключ, предусмотренный алгоритмом, тем сложнее осуществить перебор. Сейчас надежной считается длина ключа не менее 1024 бита.
• Размер блока. Чем выше размер блока, тем больше надежность шифра, но скорость операций шифрования/дешифрования при этом снижается.
• Число раундов обработки. С каждым новым раундом обработки надежность шифра повышается.
• Функция раунда F — чем она сложнее, тем труднее криптоанализ шифра.
• Алгоритм вычисления промежуточных ключей Ki.

Преимущества:

ü прямое и обратное криптографические преобразования для такого блочного шифра имеют идентичную структуру

ü Блочный шифр, использующий такую конструкцию, является обратимым и гарантирует возможность восстановления входных данных функции на каждом цикле. Сама функция не обязательно должна быть обратимой. При задании произвольной функции не потребуется реализовывать две различные процедуры — одну для шифрования, а другую для дешифрования. Структура сети Файстеля автоматически позаботится об этом.

ü иволютивное отображение

Корректность схемы:

15.2. Составить программу (псевдокод ^[1] ), реализующую простейший алгоритм вычисления контрольной суммы (цифровой подписи) произвольного файла.

Контрольная сумма – последовательность бит фиксированной длинны, которая ставится в соответствие файлу. При изменении файла с определенной вероятностью (пропорциональной длине контрольной суммы) изменяется и его контрольная сумма. Сравнив контрольную сумму исходного и полученного файла, можно сделать вывод о том, подвергался ли он искажениям.

Простейший алгоритм подсчета контрольной суммы произвольного файла заключается в побитном сложении всех его битов (по модулю 2^[2], т.е. 1 1=0, 1 0=0, 1 0=1, 0 1=1)

Программа на псевдокоде будет выглядеть примерно так («примерно так» – цитата из лекции):

sum:=0;

for I to bit_ length (file) sum:=Sum

get_bit (file, i);

//здесь предполагается, что функция bit_ length (file) возвращает количество бит в файле file, а функция get_bit (file, i) возвращает i-ый бит файла file.

Из двух строк (последовательностей) символов выделить сигнатуру максимальной длины. Рассказать об основных подходах к выбору сигнатур в антивирусах для поиска деструктивных программ.

Рассмотрим методы обнаружения антивирусом своих жертв.

Обнаружение, основанное на сигнатурах – метод работы антивирусов и систем обнаружения вторжений, при котором антивирус, просматривая файл (или передаваемый по сети пакет), обращается к словарю, в котором содержатся сигнатуры известных атак или вирусов. Под сигнатурой понимается фрагмент кода, однозначно идентифицирующий вирус. Например, вирус Email-Worm.Win32.Happy содержит строку <<Happy New Year 1999!!>>, которая с низкой вероятностью может встретиться в другой программе.

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

Автоматическая генерация сигнатур (особенно в условиях полиморфных вирусов^[3]) пока не дает удовлетворительных результатов.

Каждый современный антивирус имеет обширную (несколько сот тысяч) базу сигнатур, которая регулярно обновляется. Проблема обнаружения, основанного на сигнатурах, заключаеся в том, что новый вирус (сигнатуры которого еще нет в базе) может беспрепятственно обойти антивирусную защиту. При этом создание сигнатуры и доставка ее пользователем занимает несколько десятков часов, в то время как теоретически, вирус может захватить весь интернет меньше, чем за 30 секунд.

Программа, выделяющая сигнатуру максимальной длины в двух строках, получает на вход две строки str1 и str2, после чего просматривает все возможные фрагменты строки str1 (сначала подстроки разной длины, начинающиеся с первого символа, затем подстроки, начинающиеся со второго символа и т.д., то есть используют два вложенных цикла). Каждая из этих подстрок проверяется, например, вхождением в str2. Если вхождение существует, проверяется длина подстроки, и если она больше ранее запомненной, эта подстрока запоминается вместе со своей длиной. Результатом работы программы будет самая длинная из найденных подстрок.

len:=0; {изначально максимальная длина подстроки = 0}

signature:=” “;

for i:=1 to length (str1)-1 do

for j:=i+1 to length (str1) do begin

substr:=copy (str1,I,j);

if pos (substr, str2)>0 then

if length (substr)>len then begin

signature:=substr;

len:=length (substr);

end;

end;

{результатом является подстрока signature}

ЭКОНОМИКА

Поиск по сайту: