Интернет магазин китайских планшетных компьютеров

Компьютеры - Метод встречи в середине атаки

Данный метод применяется для атаки на блочные шифры. Обладает значительно меньшей трудоёмкостью по сравнению с методом полного перебора.

Начальные условия

Даны открытый и шифрованный тексты. Криптосистема состоит из h циклов шифрования. Цикловые ключи независимы и не имеют общих битов. Ключ K системы представляет собой сочетание из h-цикловых ключей k1,k2 ... kh

Решение

Обозначим преобразование алгоритма как Ek=b, где a-открытый текст, а b-шифротекст. Его можно представить как композицию Ek1Ek2..Ekh=b, где Eki - цикловое преобразование на ключе ki. Каждый ключ ki представляет собой двоичный вектор длины n, а общий ключ системы - вектор длины n*h.

1. Заполнение памяти.

Перебираются все значения k'=, т.е первые r цикловых ключей. На каждом таком ключе k' зашифровываем открытый текст a - Ek'=Ek1Ek2..Ekr=S. Будем считать S неким адресом памяти и по этому адресу запишем значение k'. Необходимо перебрать все значения k'.

2. Определение ключа.

Перебираются все возможные k"=. На получаемых ключах расшифровывается шифротекст b - E-1k"=E-1kh..E-1kr+1=S' . Если по адресу S' не пусто, то достаем оттуда ключ k' и получаем кандидат в ключи=k.

Однако нужно заметить, что первый же полученный кандидат k не обязательно является истинным ключом. Да, для данных a и b выполняется Ek=b, но на других значениях открытого текста a' шифротекста b', полученного из a' на истинном ключе, равенство может нарушаться. Все зависит от конкретных характеристик криптосистемы. Но иногда бывает достаточно получить такой "псевдоэквивалентный" ключ. В противном же случае после завершения процедур будет получено некое множество ключей {k',k"...}, среди которых находится истинный ключ.

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