Кpиптогpафия от папиpуса до компьютеpа


Анализ псевдослучайных последовательностей - часть 3


Другой, алгебраический метод, предложенный Зенгом, Янгом и Рао, использует скрытые линейности генераторов гаммы. Он, как и пример выше, основан на точной оценке непротиворечивости системы линейных алгебраических уравнений со случайными коэффициентами. Этот метод пытается по отрезку гаммы выделить подключ из общего ключа и составить систему линейных уравнений такую, что коэффициенты матрицы зависят только от под ключа. Если подключ выделен правильно, то соответствующая система уравнений с большой вероятностью будет удовлетворять требованию нспротиворечивости. Далее по оставшейся части последовательности можно найти весь ключ. Для определения подключа применим метод полного перебора подключей. При этом непротиворечивость системы линейных уравнений служит критерием идентификации ключа. Успешный результат этого метода означает, что лишь подключ определяет стойкость, а остальная часть ключа избыточна. Так как оба рассмотренных метода анализа требуют применения полного перебора для поиска ключа, их можно считать способами обнаружения избыточности ключей генераторов гаммы, а не практическими алгоритмами раскрытия текста шифра.
     Чтобы сбить с толку криптоаналитиков. многие генераторы гаммы основаны на комбинации двух или более генераторов с использованием нелинейных логических функций. Один из наиболее простых способов комбинации двух сдвиговых регистров с линейными обратными связями состоит в применении переключателя с отношением переключаемых разрядов 2:1 и носит имя генератора Джеффи. Слабое место такого генератора связано с тем, что такая система может быть легко раскрыта методом криптоанализа с использованием так называемых линейных синдромов. При современном состоянии техники сдвиговых регистров с линейными обратными связями выходная последовательность может быть раскрыта по перехваченному сегменту гаммы длиной в строку текста. Известен еще один генератор этого типа - генератор Дженнинга - тоже использующий переключатель для объединения двух регистров с линейными обратными связями. И он довольно несложно вскрывается криптоаналитиками. Таким образом, хотя множество возможных нелинейных комбинаций последовательностей, образующих гамму, очень большое, вклад их в криптографическую стойкость системы в целом незначителен и необходимо применять перестановки, как это сделано в DES.
     Следует иметь в виду, что большая линейная сложность генераторов на сдвиговых регистрах является лишь одним из требований, которым они должны удовлетворять. Известно много хороших методов, гарантирующих большой нижний предел этой сложности. Многие из опубликованных в последнее время результатов исследований по криптографии необоснованно обращают внимание только на проблемы большого периода генерируемых последовательностей и большой линейной сложности генераторов. Криптологи же считают, что обнаружение и устранение статистических и скрытых систематических зависимостей, особенно линейных, имеет важнейшее значение при проектировании конкретной криптографической системы, так как любые зависимости в гамме приводят к избыточности ключа.
     Теперь приведу вольный пересказ старой газетной статьи. Шпион несколько раз прикурил, фотографируя спрятанным в зажигалке фотоаппаратом открытую шифровальную машину с разных сторон. Затем, введя ключ из одних пробелов, он несколько сот раз нажал букву А. Полученная перфолента шифровки была после внимательного рассматривания туго свернута в рулон и небрежно отброшена, но в конце концов незаметно очутилась в его кармане. Теперь вопрос: почему шпиона заинтересовала шифровка дурацкого текста из одной повторяющейся буквы? Надеюсь, что читатели смогут теперь ответить на этот вопрос точно и обстоятельно.




- Начало -  - Назад -  - Вперед -



Книжный магазин