Содержание к диссертации
Введение
Глава 1. Факторизация предметной области 12
1. Общие вопросы и понятия связанные с защитой информации 12
2. Блочные алгоритмы преобразования информации 30
3. Примеры блочных алгоритмов преобразования информации в РВС 44
4. Скоростные програм»»алгоритмы преобразования информации в РВС 52
Глава 2. Анализ алгебраических свойств псевдовероятностных алгоритмов преобразования информации в РВС 70
1 .Алгоритм преобразований базирующийся на выборке подключей в зависимости от преобразуемых данных . 70
2. Методы вычисления подключей при реализации повторов 75
3. Способы повышения скорости и стойкости алгоритмов преобразования данных в РВС 85
Глава 3. Анализ алгебраических свойств недетерминированных алгоритмов преобразования информации в РВС 106
1. Построение скоростных программных алгоритмов преобразования данных с недетерминированными процедурами 106
2. Анализ алгебраических свойств преобразования 114
3. Выявление особенностей ключей - слабые и сомнительные ключи 121
4 Построение алгоритмов преобразования на основе управляемых блоков перестановок 125
Глава 4. Оценивание статистических свойств алгоритмов преобразований данных в РВС 144
1. Описание основных критериев и тестов используемых для анализа статистических свойств алгоритмов преобразований 144
2. Статистический анализ цикловой структуры алгоритма преобразования данных 151
3. Применение статистического анализа к исследуемым алгоритмам преобразования данных 154
Заключение 166
Список литературы 168
Приложение
- Блочные алгоритмы преобразования информации
- Скоростные програм»»алгоритмы преобразования информации в РВС
- Методы вычисления подключей при реализации повторов
- Выявление особенностей ключей - слабые и сомнительные ключи
Введение к работе
Актуальность темы исследования. С развитием информационных технологий особую важность приобретают способы и средства защиты информации. Наиболее математически строгим является подход к данной проблеме в рамках криптологии. Согласно классической работе Шеннона, в качестве меры раскрываемости криптограммы используется вероятность события: «выбранная оценка открытого текста, при условии известной криптограммы, совпала с истинным открытым текстом». Однако при этом не определяется строго вероятностное пространство, элементом которого является такое событие, что не позволяет построить единообразную процедуру получения содержательных оценок стойкости криптосистем. Таким образом, всякая оценка стойкости той или иной криптосистемы, полученная методами известными на сегодняшний день, не гарантирует, что не найдется новый способ (алгоритм) ее раскрытия, действующий быстрее, чем известные. Существующие методы получения оценок стойкости криптосистем с секретным ключом являются, главным образом, развитием идей Шеннона и носят эмпирический характер. При этом часто относительно возможности криптоаналитика приходится делать предположения, что он обладает неограниченными вычислительными и временными ресурсами, что, само по себе, далеко от реальности.
Одним из важных механизмов поддержания защиты функционирования распределенных вычислительных сетей является преобразование информации. Вопросы оптимизации алгоритмов защиты информации приобретают все более возрастающее значение в связи со стабильными тенденциями развития современных средств вычислительной техники, характеризующихся быстрым ростом объема устройств памяти и производительности процессоров, что приводит к увеличению информационных потоков в вычислительных сетях. Важнейшими параметрами алгоритмов преобразования являются стойкость и скорость преобразования. При обеспечении
данного уровня стойкости увеличение скорости алгоритмов защиты информации позволяет существенно повысить производительность распределенных вычислительных сетей, особенно в рамках АСУ.
Другой областью криптологии (теории секретных систем), вызывающей повышенный интерес является теория аутентификации, которая, не смотря на свою схожесть с теорией криптосистем с секретным ключом, развита значительно слабее.
Актуальность работы определяется тем, что в настоящее время не существует методов получения содержательных оценок стойкости криптосистем с секретным ключом и общих методов построения систем аутентификации, обеспечивающих совершенную аутентичность.
Известно очень большое число угроз информации, которые могут быть реализованы как со стороны внешних нарушителей, так и со стороны внутренних нарушителей. Отметим некоторые современные направления, где требуется обеспечить защиту информации в распределенных информационных системах:
Защита от несанкционированного чтения информации.
Защита от навязывания ложных сообщений (умышленных и непреднамеренных).
Идентификация законных пользователей.
Контроль целостности информации.
Аутентификация информации.
Электронная цифровая подпись.
Системы тайного электронного голосования.
Вопросы оптимизации алгоритмов защиты информации приобретают первостепенное значение. Широкое применение скоростных алгоритмов преобразования информации требует проведения оценок их стойкости. При этом стойкость оценивается по отношению к конкретным видам нападений. Обоснование надежности используемых систем осуществляется экспериментально путем моделирования различных видов нападений. При этом, как правило, при анализе стойкости предоставляются более благо-
приятные, чем на практике условия. Если в этих условиях алгоритм оказывается стойким, то он рекомендуется для данного конкретного применения.
Радикальное решение проблем защиты электронной информации может быть получено на базе использования специальных преобразований информации, которые позволяют решать важнейшие проблемы защищенной автоматизированной обработки и передачи данных. При этом современные скоростные методы преобразования данных позволяют в основном сохранить исходную производительность автоматизированных систем. Подобные преобразования данных являются наиболее эффективным средством обеспечения конфиденциальности данных, их целостности и подлинности. Только их использование в совокупности с необходимыми техническими и организационными мероприятиями могут обеспечить защиту от широкого спектра потенциальных угроз и тем самым сделать работу вычислительной системы стабильной, не смотря на внешние воздействия.
Цель работы. Разработка единого подхода к получению содержательных оценок стойкости криптосистем с секретным ключом с использованием алгоритмов скоростного преобразования информации при условии обеспечения требуемого уровня их стойкости.
В соответствии с поставленной целью в работе решаются следующие основные задачи
Формализация и обобщение понятия криптосистем, данное Шенноном;
Определение стойкости криптосистем с позиции теории вычислительной сложности с использованием вероятностного пространства, описывающего раскрытие криптограммы.
Разработка принципов построения скоростных и стойких алгоритмов преобразования информации в распределенных вычислительных сетях.
Разработка методов анализа процедур преобразований информации, циркулирующей в распределенных вычислительных сетях.
Применение разработанных методов анализа к предлагаемым алгоритмам преобразования информации.
Предмет исследования диссертации составляют скоростные алгоритмы преобразования информации, циркулирующей в распределенных вычислительных сетях.
Методы исследования. В работе использованы методы алгебры, теории чисел, дискретной математики, теории вероятностей, математической статистики, теории сложности и структурного программирования.
Научная новизна полученных в диссертации результатов заключается в следующем:
Предложены методы оценки стойкости ряда алгоритмов преобразования данных, циркулирующих в автоматизированных системах управления информационными процессами.
Предложены подходы к повышению скорости программных алгоритмов преобразования информации.
Построены скоростные алгоритмы, обладающие хорошей стойкостью.
Дано обоснование применения новой операции микропроцессора -управляемой перестановки, использование которой позволит резко повысить производительность программных алгоритмов защиты информации в РВС.
Разработан новый статистический тест для оценки цикловой структуры алгоритмов.
6. Проверены статистические свойства исследуемых алгоритмов
Практическая ценность. Предложены методы оценки стойкости ал
горитмов преобразования данных и механизмы повышения скорости про
граммных алгоритмов преобразования данных. В результате исследования
построены скоростные алгоритмы преобразования данных обладающие
хорошей стойкостью. Даны оценки стойкости и рекомендации по оптими
зации практически используемых скоростных алгоритмов.
Реализация работы. Разработанные в работе методы анализа и статистические тесты были использованы при выборе алгоритмов преобразования данных в широко применяемой системе защиты информации «СПЕКТР-Z». Построенные алгоритмы реализованы в виде программных модулей. Написаны программные модули, с помощью которых были проанализированы исследуемые алгоритмы преобразования данных.
Положения, выносимые на защиту.
Механизмы преобразования информации, основанные на псевдослучайной выборке подключей в режиме с накоплением, обладают хорошими статистическими свойствами и позволяют построить стойкие к анализу на основе подобранного текста быстрые программно-ориентированные алгоритмы защиты информации.
Для повышения стойкости скоростных псевдовероятностных алгоритмов к атакам на основе подобранных текстов может быть применен "сокращенный" раунд.
Повышение скорости псевдовероятностных алгоритмов может быть достигнуто использованием умножения для рассеивания влияния битов текста.
Добавление операций управляемых перестановок в набор команд массовых микропроцессоров позволяет повысить скорость программно ориентированных алгоритмов преобразования информации циркулирующей в РВС.
Разработан метод оценки статистических свойств преобразованных текстов, позволяющий дать необходимую оценку стойкости алгоритмов преобразования информации циркулирующей в РВС.
Внедрение результатов работы осуществлено в структуре аппарата администрации г.Ставрополя, в специальных подразделениях главного управления внутренних дел Ставропольского края, в Управлении по Северному Кавказу МВД России, в подразделениях Совета безопасности Ставропольского края и других спецподразделениях, а также в учебном процессе Томского университета систем управления и радиоэлектроники
(ТУСУР), Московской государственной академии приборостроения и Московском государственном горном университете.
Апробация работы осуществлена на I, II, III международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения и информатики, экономики и права» г. Сочи с 27 сентября по 3 октября 1999 г., на первой межрегиональной научно-практической конференции «Проблемы информационной безопасности общества и личности», «Средства и системы безопасности-2000» 24-26 мая 2000 года г. Томск, III Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения и информатики, экономики и права» г. Сочи 2-6 октября 2000 года, первой региональной научно-практической конференции «Проблемы совершенствования методов управления социально-экономическими процессами и их правовое регулирование» 18-19 мая, г. Ставрополь 2000 год.
Публикации. Основные положения диссертации изложены в 7 публикациях.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка используемой литературы и приложений. Содержит 180 страниц машинописного текста.
Блочные алгоритмы преобразования информации
Для разработки вычислительно стойких шифров в настоящее время используются два общих принципа выделенных Шенноном: рассеивание и перемешивание [6]. Рассеиванием он назвал распространение влияния одного знака открытого текста на много знаков шифртекста, что позволяет скрыть статистические свойства открытого текста. Развитием этого принципа является распространение влияния одного знака ключа на много знаков шифртекста, что предотвращает восстановление ключа по частям. Перемешиванием Шеннон назвал использование таких шифрующих преобразований, которые усложняют восстановление взаимосвязи статистических свойств открытого и шифрованного текста. Однако шифр должен не только затруднять раскрытие, но и обеспечивать легкость зашифровывания и расшифровывания (при известном ключе). Так распространенный способ достижения рассеивания и перемешивания состоит в использовании составного шифра, т.е. шифра, который может быть реализован в виде некоторой последовательности простых шифров, каждый из которых вносит небольшой вклад в значительное суммарное рассеивание и перемешивание.
В составных шифрах в качестве простых шифров чаще всего используют простые подстановки и перестановки. При перестановке просто перемешиваются символы открытого текста, причем конкретный вид перемешивания определяет секретный ключ. Распределение частот отдельных символов в шифрованном тексте то же, что и в открытом тексте, однако, распределения более высоких порядков оказываются перемешанными. При подстановке каждый символ открытого текста заменяют другим символом из того же алфавита, а конкретный вид подстановки определяет секретный ключ. Распределение частот отдельных символов в открытом тексте сохраняется неизменным и в шифртексте. Однако если подстановка делается в очень большом алфавите, а вероятность повторения каждого символа открытого текста в течение времени использования одного ключа мала, то статистические свойства шифртекста дают мало информации криптоаналитику, и такой шифр становится очень хорошим. При многократном чередовании простых перестановок и подстановок можно получить очень стойкий шифр с хорошим рассеиванием и перемешиванием.
В современных автоматизированных системах обработки информации во многих случаях предпочтительно применение блочных шифров [4]. Блочные шифры представляют собой криптосистему, которая осуществляет шифрование информации блоками фиксированной длины, например, равной Ъ бит. Этот вид криптографических преобразований называется блочным шифрованием. Для осуществления блочного шифрования данные представляются в виде последовательности 6-битовых блоков. В реальных ситуациях файлы, определенные поля в электронных документах и другие виды электронных сообщений имеют произвольную длину и, как правило, не кратную длине блока, поэтому используется некоторый способ дополнения последнего блока данных.
Последний блок принято дополнять двоичным вектором (100...0), в котором количество нулей может быть от 0 до (Ь-2). Если длина последнего блока равна Ь, то к сообщению присоединяется дополнительный Ь битовый блок имеющий структуру (100...0). Этот способ позволяет однозначно распознать присоединенный двоичный вектор и отбросить его при необходимости. Используя такой способ дополнения сообщения до длины кратной Ь, любое сообщение М можно представить в виде последовательности 6-битовых подблоков М{\
Каждый из блоков исходного сообщения может быть преобразован независимо от других блоков, поэтому при применении блочных шифров возможен произвольный доступ к зашифрованным массивам данных. Наиболее общим механизмом блочного шифрования является такой, в котором возможно преобразование любого входного блока в любой выходной блок, причем размер выходного блока равен или больше размера входного блока. Блок шифртекста не может быть меньше блока открытого текста, т.к. в этом случае одному и тому же блоку шифртекста будут соответствовать несколько различных блоков открытого текста. Это означало бы неоднозначность дешифрования. Если длина выходного блока больше Ь, то одному и тому же блоку открытого текста могут соответствовать несколько различных блоков шифртекста. В этом случае дешифрование возможно и однозначно. Поскольку увеличение длины зашифрованных данных вносит определенные ограничения на области применения, то в наиболее широко применяемых шифрах размер выходных блоков равен размеру входных. Блочные шифры задают взаимно однозначное соответствие между возможными входными блоками и возможными выходными блоками. Число возможных различных 6-битовых блоков равно 2 . Так как шифрование задает взаимно однозначное соответствие между входными и выходными значениями, а входное множество блоков совпадает с выходными и выходными значениями, то шифрование задает некоторую подстановку на множестве чисел (0, 1, 2ь-1}, которую можно представить в виде таблицы: где Дк(7) - функция шифрования по ключу К, т.е. функция, задаваемая процедурами шифрования при использовании ключа К. Функция шифрования ставит в соответствие блоку открытого текста Т блок криптограммы С, что записывается в виде С = Ек(Т). Для данного ключа реализуется одна подстановка. В общем случае различным ключам соответствуют различные подстановки. Если в шифре используется ключ длиной к бит, то этот шифр задает не более 2 различных подстановок, что составляет обычно чрезвычайно малую долю от числа возможных подстановок, которое равно 2 !. Для того чтобы реализовать все возможные подстановки, необходимо использовать ключ длиной порядка
Скоростные програм»»алгоритмы преобразования информации в РВС
Под программными шифрами понимают такие системы шифрования, которые используют операции над компьютерными словами и учитывают специфику обработки данных в компьютерных системах, что позволяет получить высокие скорости шифрования при использовании микропроцессоров широкого применения [2]. Рассмотрим особенности проектирования программных шифров.
Организация наиболее надежного защищенного режима обработки данных в компьютерных системах связана с шифрованием всех данных, хранимых в энергонезависимой памяти. В общем случае обработка информации связана с произвольными запросами на чтение и запись данных, поэтому необходимо обеспечить независимое шифрование отдельных блоков данных. Современные ЭВМ характеризуются большим объемом постоянной памяти и высокой скоростью записи и считывания. Эти два фактора определяют высокие требования к шифрам, ориентированным на применение в системах защиты информации от несанкционированного доступа, функционирующих в масштабе реального времени: (1) высокая скорость при криптоанализе на основе большого объема известного или подобранного текста, зашифрованных на одном и том же ключе, (2) высокая скорость шифрования при программной реализации.
Аддитивные поточные шифры имеют ограниченное применение в компьютерных системах, поскольку при использовании глобального шифрования (т.е. при шифровании всей информации, хранимой в энергонезависимой памяти) необходимо обеспечить произвольный доступ к хранимой информации. Поточные криптосистемы могут быть использованы для этой цели только при их дополнении специальной подсистемой генерации уникальных ключей шифрования для каждого отдельного элементарного блока данных. (Это требование связано с тем, что в поточных шифрах нельзя допустить повторного использования одинаковых участков ключевого потока.)
Наиболее подходящими для применения в компьютерных системах являются блочные шифры. Приведем примеры скоростных блочных шифров.
Шифр Blowfish был предложен Б.Шнейером [14] как альтернатива широко используемой криптосхеме DES. При его создании были использованы следующие конструктивные принципы: Высокая скорость шифрования при программной реализации. Компактность. Алгоритм не должен требовать большого объема оперативной памяти для своего размещения. Простота. Шифрующие процедуры должны быть реализованы на элементарных операциях массовых процессоров. Логическая структура алгоритма шифрования должна быть простой для анализа, что позволит избежать ошибок при реализации. Возможность использования секретного ключа произвольной длины.
Blowfish является 64-битовым блочным шифром, который состоит из двух частей: алгоритма расширения ключа и алгоритма шифрования/дешифрования. В криптосистеме Blowfish процедура расширения ключа состоит в преобразовании секретного ключа, длина которого не детерминирована и может иметь значение до 448 бит, в ключ шифрования фиксированного размера (4168 байт), представленного в виде нескольких массивов подключей: массива 32-битовых ключевых непосредственных констант и четырех последовательностей 32-битовых подключей, каждая из которых содержит 256 элементов. Пусть этими последовательностями являются следующие четыре:
Последовательности Q используются для задания функции F(X), где X - 32-битовый аргумент. При заданном X значение этой функции определяется следующим образом: 32-битовое слово X представляется в виде конкатенации четырех 8-битовых слов X = XI\X2\X\\XQ. Затем производится вычисление:
Последовательности Q(i) фактически задают большую таблицу отображения входных 32-битовых подблоков в выходные 32-битовые подблоки.
Алгоритм расширения секретного ключа включает сложные процедуры преобразований, которые трудно использовать при осуществлении криптоаналитической атаки, поэтому наиболее вероятны такие нападения на шифр Blowfish, которые основаны на анализе простых процедур шифрования при предположении, что расширенный ключ выбирается случайно. Blowfish построен в соответствии с итеративной криптосхемой Фей-стеля и состоит в выполнении 16 раундов преобразований по следующим алгоритмам:
Методы вычисления подключей при реализации повторов
Тогда если имеются два открытых текста совпадающих до ТіЛ слова включительно, то соответствующие им шифртексты будут совпадать вплоть до С,.] слова. При этом согласно алгоритму шифрования останутся теми же значения F[wM] и щ. Таким образом, получаем систему двух уравнений с двумя неизвестными F[Ui_\] и щ из которой можно определить значения F[ui.]] и щ. Теперь, действуя подобным образом для других текстов, можно будет определить всю ключевую последовательность, это позволяет вычислить значения подключей. Более того, если первый текст будет все время постоянным, а во втором тексте слово, в котором начинаются различия, сдвигать вперед на одно для каждого нового текста, то мы сможем не только определить значения слов ключевой последовательности F[ui.\], но и порядок следования этих значений. В качестве открытого постоянного текста удобно рассмотреть текст, состоящий из нулевых слов (Г,- = 0), а в качестве изменяющегося - текст, у которого все нули за исключением одного слова, в двоичной записи которого все единицы. При таком способе вычисления ключа из каждого отдельно взятой системы уравнений нельзя определить старшие разряды слова ключа и указателя щ. Невозможность определения старшего разряда является общим свойством уравнений такого типа. Это связано с тем, что при сложении но модулю 2" из старшего разряда не происходит переноса, поэтому если одновременно изменить старшие биты у F[w,-.i] и и,-, то результат не изменится. Однако из уравнения шифрования видно, что старшие биты указателя не влияют на значение ключевой последовательности, а поскольку в ключевой последовательности младший байт (і - 1 )-го элемента равняется старшему байту г-го элемента, то старшие биты ключевой последовательности восстанавливаются однозначно. Используя такой метод, мы сможем полностью определить ключ.
Покажем как решить систему уравнений С =(0 F) + ииС =(1 F) + и, где 1 обозначает число дополнительное к 1 т. е. содержащее все единиц в двоичной записи. Очевидно, что 1 F = 1 - F. Отсюда получаем 2и = С] + С2 - 1, 2F = С1 - С2 + 1, тем самым мы определили UHFC точностью до старшего бита. При этом получим следующую оценку для сложности раскрытия ключа где Wa - сложность арифметических операций по модулю 216, a Wc - сложность операций шифрования.
Аналогичные рассуждения верны и для остальных процедур. Единственным отличием будет то, что в уравнении будет три неизвестных, для первой процедуры это будет ключ К, для третьей и четвертой процедур С ,-.1. Однако это новое неизвестное достаточно найти только для одного, например, самого первого уравнения. Более существенным отличием будет то, что количество решений соответствующего уравнения может при некоторых значениях неизвестных достичь огромной величины. Поэтому целесообразно будет рассматривать избыточное количество уравнений и выбирать те из них, в которых неоднозначность наименьшая.
Теперь рассмотрим криптоалгоритмы состоящие из двух процедур. Рассмотренный выше метод раскрытия ключа можно модифицировать и на случай двух процедур. Для этого необходимо чтобы соответствующие указатели оставались постоянными для обеих последовательно примененных процедур шифрования. В качестве примера рассмотрим, для простоты, последовательное применение сначала первой, а затем второй процедур. Очевидно, что если два открытых текста отличаются только в первом слове, то при шифровании первого слова первой процедурой, в которой нумерация символов идет справа налево, первые слова шифруются на одних и тех же указателях. А так как во второй процедуре шифрование осуществляется слева направо, то хотя после первой процедуры на выходе первые слова и будут различными, но указатели все же будут одинаковыми, и, значит, мы сможем набрать достаточное количество уравнений вида [18] здесь t и с открытый и шифрованный тексты соответственно; к, а, Ъ, с и d -неизвестные соответствующие элементам ключевых последовательностей и значением указателей, которые являются одинаковыми для всех уравнений. Приведем некоторые оценки для количества решений системы уравнений такого вида в зависимости от структуры параметров к, a, b, d, е.
Выявление особенностей ключей - слабые и сомнительные ключи
Как было показано в предыдущем параграфе, в случае однораундового преобразования все ключи могут быть вычислены сравнительно просто. По сравнению с однораундовым анализ двух - трехраундового преобразо вания представляет значительную сложность. Действительно в общем случае мы не можем управлять разностью между текстами в процессе преобразования также свободно как в случае одного раунда преобразования. Однако, при некоторых значениях ключа Q, а также виде операций используемых в криптоалгоритме можно провести атаку аналогичную атаке в случае однораундового криптоалгоритма.
Рассмотрим частные случаи значений ключей, при которых анализ криптоалгоритма можно осуществить проще, чем в общем случае. Для начала остановимся на тривиальных случаях.
Пусть все подключи Q[i] совпадают. В этом случае для шифрования любого текста используются одни и те же значения подключей. Такую ситуацию легко отследить. Действительно, рассмотрим пару открытых текстов, у которых совпадают X, но различаются Y. Тогда после шифрования в шифрованных текстах также будут совпадать X и различаться Y. Тоже самое верно и для пары открытых текстов, имеющих различные X, но совпадающие Y. Для нахождения ключа можно осуществить перебор по всем возможным значениям Q[i]. Вероятность появления такого ключа, очевид-но, равна (2 ) . Этим случаем можно пренебречь.
Пусть все операции j являются операциями поразрядного сложения по модулю 2. Тогда операции циклического сдвига будут коммутировать с операциями j. При этом итоговая формула для шифртекста примет вид где (рк) и (яі) обозначают некоторые перестановки бит подключей {?[/ ] и Q[i{\ получаемые комбинированием сдвигов. Для анализа этого случая можно применить анализ разностей. При некоторых значениях последовательности подключей Q\j] в сумме Qyl @Q\P2 ...Q Qy24 будут наблюдаться отклонения от равномерного распределения, и появится возмож ность для бесключевого чтения. Вероятность случайного появления такого ключа равна З 24.
Предположим, что имеются два одинаковых подключа Q[i] = Q\j], тогда мы сможем подобрать пару открытых текстов различающихся только в байте х4 такую, что на выходе первого раунда различие также будет только в Х4 (только уже в текстах полученных после одного раунда шифрования). Такая ситуация произойдет если на последнем шаге первого раунда Q[h] будут совпадать для обоих текстов. Теперь к анализу двухраундового преобразования можно применить туже технику, какую мы применяли при анализе однораундового преобразования. В работе [4] приводятся оценки для двухраудовой модификации. В рассматриваемом случае приводятся следующие оценки сложности криптоанализа. Трудоемкость криптоанализа составляет: где Wa - обозначает сложность арифметических операций над 32-х битовыми словами. Данная оценка верна при условии, что нам неизвестна конкретная модификация операций участвующих в алгоритме. При этом вероятность появления двух одинаковых подключей можно оценить по формуле парадокса «о днях рождения»:
Для данного алгоритма существуют эквивалентные ключи. Действительно если все сдвиги равны нулю, все операции являются операциями побитового сложения по модулю 2 и все элементы Q[f] равны между собой, то при шифровании любого открытого текста Т = (X\Y) на выходе мы получим исходный текст С = Т = (X\Y). Ясно, что вероятность такого совсем вырожденного случая крайне мала, и ей можно пренебречь. Тем не менее, факт существования эквивалентных ключей представляет интерес. Возможно, существуют и другие примеры эквивалентных ключей. Оценка критического значения известной части подключен Q(j)
Рассмотрим, какая доля ключа может быть известна криптоаналитику и при этом алгоритм все еще является стойким. Будем исследовать возможность криптоанализа на основе известного открытого и шифрованного текстов. Для начала рассмотрим ситуацию, когда вид операций, а также циклические сдвиги известны криптоаналитику. Кроме того, сделаем дополнительное предположение, что выборки из ключевого массива Q\J] на каждом раунде осуществляются равномерно и независимо. Обозначим за р долю известных подключей. В случае трех раундов при шифровании открытого текста используется 24 подключа Q\j]. Рассмотрим наиболее простой случай, когда первые 22 подключа выбираются из известной части массива Q\J]. Если оставшиеся два подключа попадают в область известных подключей, то это ничего нового не дает. Интересны, таким образом, случаи, когда из оставшихся двух подключей Q\J] неизвестными являются, по крайней мере, один. Тогда из последнего (или двух последних) шага шифрования мы легко определим значение неизвестного подключа.
