Подстановочные и перестановочные шифры

Стойкость алгоритмов.

В зависимости от сложности взлома, различные алгоритмы обеспечивают различные степени защиты. Алгоритм можно считать безопасным, если: 1) взлом алгоритма обойдется дороже, чем сами зашифрованные данные, 2) время необходимое для взлома алгоритма, больше, чем время, в течении которого, защифрованные данные должны сохраняться в тайне.

Алгоритм безусловно стоек, если восстановление открытого текста невозможно при любом объеме шифротекста, полученного криптоан-ком.

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

На практике невозможно раскрыть, даже при бесконечных ресурсах, только текст, зашифрованный одноразовыми блокнотами (речь об этом способе пойдет дальше). Все остальные криптосистемы можно вскрыть лобовой атакой.

Сложность той или иной атаки можно оценить:

1. По сложности данных, т.е. по объему исходных данных, необходимых для атаки.

2. По фактору трудозатрат, т.е. по времени, необходимому для атаки.

3. По требованиям к ресурсам компьютера, необходимого для атаки.

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

В числовом измерении сложность выражается порядками величин. Например, если сложность алгоритма составляет 2128, значит, для вскрытия алг. необходимо выполнить 2128 операций. Например, ваши выч. мощ-ти позволяют выполнять миллион операций в сек., и для решения задачи вы используете миллион паралл. проц-ров. Тогда для определения ключа вышеуказанного алгоритма потребуется 1019 лет, в миллиард раз больше времени существования Вселенной.

В то время, как сложность вскрытия остается постоянной, вычислительные ресурсы постоянно растут. Закон Мура гласит, что удвоение производительности современных процессоров происходит каждые 18 месяцев (удвоение количества транзисторов в микросхемах каждые 18 месяцев). (Можно рассказать про закон Мура). Поэтому, при создании устойчивых к взлому криптосистем, необходимо принимать в расчет перспективы развития вычислительных средств на много лет вперед.

До появления ком-ров, криптография основывалась на текстовых алгоритмах. Различные криптогр. алг. выполняли или замену одних символов другими, или перестановку символов. Лучшие алг. выполняли и ту и др. операцию, причем многократно. В наше время всё усложнилось, но философия осталась прежней. Основное изменение заключ. в том, что современные алгоритмы обрабатывают биты а не символы. Как ни странно, это означает всего лишь изменение размера алфавита с 32 элементов (26 в англ.) до двух.

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

В классической криптографии различаются четыре типа подстановочн. шифров:

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

Омофонический подстановочный шифр подобен простому подстановочному, но одному символу открытого текста может быть сопоставлен один из нескольких символов шифротекста. Например, символу “А” может соотв. 4,19,34, ”Б” - 7, 21, 31 и т.д. Сложнее для вскрытия чем простые подст-ые, но не скрывают всех статистич. Свойств открытого текста. Без труда взламываются путем вскрытия с известным открытым текстом.

Полиграмный (n-граммный) подстановочный шифр – шифрует блоки символов по группам. Например, блоку “АБ” может соответствовать “КЕ”, блоку “ББ” – “ПР” и т.д. Подобный шифр использовался британцами во время Первой мировой войны.

Полиалфавитный подстановочный шифр состоит из нескольких простых подстановочных шифров, которые используются по очереди. Какой шифр используется для каждого конкретного символа зависит от его положения в открытом тексте. Изобретен в 1568 году. Использовался армией Соединенных Штатов в ходе Гражданской войны в Америке. Несмотря на то, что взлом подобных шифров не составляет труда, особенно при помощи комп-ров, такие шифры используются во многих коммерческих программных продуктах, например в WordPerfect).

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

Еще один пример подобного шифра – шифр с бегущим ключом, в котором один текст используется для шифрования другого тектса. И хотя период шифра равен длине текста, его взлом в настоящее время не составляет труда.