Вопрос№7

В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A[NxN] находит максимальный элемент в каждой строке. for i:=1 to N do begin max:=A[i,1]; for j:=1 to N do begin if A[i,j]>max then max:=A[i,j] end; writeln(max); end; В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N^2). Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%. При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

Определение сложности

Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов. Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определённое число инструкций (например, вывод на печать), то на оценку сложности это практически не влияет. Если же в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм. Если же процедура вызывается внутри цикла, то влияние может быть намного больше. В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(N^2). procedure Slow; var i,j,k: integer; begin for i:=1 to N do for j:=1 to N do for k:=1 to N do {какое-то действие} end; procedure Fast; var i,j: integer; begin for i:=1 to N do for j:=1 to N do Slow; end; procedure Both; begin Fast; end; Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2 )*O(N^3 )=O(N^5). Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2 )+O(N^3 )=O(N^3). Следующий фрагмент имеет именно такую сложность: procedure Slow; var i,j,k: integer; begin for i:=1 to N do for j:=1 to N do for k:=1 to N do {какое-то действие} end; procedure Fast; var i,j: integer; begin for i:=1 to N do for j:=1 to N do {какое-то действие} end; procedure Both; begin Fast; Slow; end;

Алгоритм называется полиномиальным, если время его работы оценивается некоторым полиномом от размерности задачи n. Полиномиальные алгоритмы считаются «хорошими», практически эффективными. Алгоритм называется экспоненциальным, если его выполнение требует количество операций, увеличивающихся с ростом n экспоненциально. Такие алгоритмы высокозатратные, поэтому их считают плохими.

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

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

Трудноразрешаемая задача характеризуется, как правило, конечным по мощности экспоненциальным множеством вариантов, среди которых нужно найти решение, и поэтому она может быть решена алгоритмом полного перебора. Такой, например, является задача о рюкзаке. Ясно, что решение данной задачи надо искать среди 2ⁿ двоичных векторов длины n, где n — число предметов. Перебрав это экспоненциальное множество векторов, задача (1.1) - (1.2) будет решена. Очевидно, что переборный алгоритм имеет экспоненциальную сложность и может хорошо работать только для небольших размеров задачи. С ростом размера задачи число вариантов быстро растет, и задача становится практически неразрешимой методом перебора.

№10

Подстановочным шифром называется шифр, который каждый символ открытого текста в шифротексте заменяет другим символом. Получатель инвертирует подстановку шифротекста, восстанавливая открытый текст. В классической криптографии существует четыре типа подстановочных шифров:

    - простой подстановочный шифр, или моноалфавитный шифр, - это шифр, который каждый символ открытого текста заменяет соответствующим символом шифротекста. Простыми подстановочными шифрами являются криптограммы в газетах;

    - однозвучный подстановочный шифр похож на простую подстановочную криптосистему за исключением того, что один символ открытого текста отображается на несколько символов шифротекста. Например, A может соответствовать 5, 13, 25 или 56, B - 7, 19, 31 или 42 и так далее;

    - полиграммный подстановочный шифр - это шифр, который блоки символов шифрует по группам. Например, ABA может соответствовать RTQ, ABB может соответствовать SLL и так далее;

    - полиалфавитный подстановочный шифр состоит из нескольких простых подстановочных шифров. Например, могут быть использованы пять различных простых подстановочных фильтров; каждый символ открытого текста заменяется с использованием одного конкретного шифра.

 

Знаменитый шифр Цезаря, в котором каждый символ открытого текста заменяется символом, находящегося тремя символами правее по модулю 26 (A заменяется на D, B - на E, ... W - на Z , X - на A, Y - на B, Z - на C), представляет собой простой подстановочный фильтр. Он действительно очень прост, так как алфавит шифротекста представляет собой смещенный, а не случайно распределенный алфавит открытого текста.

 S-блок - это просто подстановка: отображение m-битовых входов на n-битовые выходы. Применяется большая таблица подстановок 64-битовых входов на 64-битовые выходы. Такая таблица представляет собой S-блок размером 64*64 бит. S-блок с m-битовым входом и n-битовым выходом называется m*n-битовым S-блоком. Как правило, обработка в S-блоках - единственная нелинейная операция в алгоритме. Именно S-блоки обеспечивают стойкость блочного шифра. В общем случае, чем больше S-блоки, тем лучше. Часть подозрений в скрытой слабости S-перестановок была снята S-блоки алгоритма DES оказались намного более устойчивыми к атакам, чем если бы их выбрали случайно. Это означает, что такая техника анализа была известна АНБ ещё в 70-х годах XX века.

шифры типа «Шифра Цезаря» (то есть моноалфавитные шифры, в которых каждой букве кодируемого текста ставится в соответствие однозначно какя-то шифрованная буква) довольно-таки легко поддаются криптоанализу. Возникла потребность в разработке таких шифров, ручная расшифровка которых может потребовать очень значительных усилий. И на смену моноалфавитным шифрам пришли полиалфавитные шифрыВводить понятие полиалфавитного шифра удобнее всего, сначала определив моноалфавитный шифр, что было сделано в исторических сведениях.

Суть полиалфавитного шифра заключается в циклическом применении нескольких моноалфавитных шифров к определённому числу букв шифруемого текста. Например, пусть у нас имеется некторое сообщение x₁ , x₂ , x₃ , ….. x_n , …… x_2n , ….., которое надо зашифровать. При использовании полиалфавитного шифра имеется несколько моноалфавитных шифров (например, n штук). И в нашем случае к первой букве применяется первый моноалфавитный шифр, ко второй букве— второй, к третей— третий….. к n-ой букве— n-ый, а к n+1 опять первый, ну и так далее. Таким образом, получаётся довольно-таки сложная последовательность, которую уже не так просто вскрыть, как один моноалфавитный шифр. Самым важным эффектом, достигаемым при использовании полиалфавитного шифра, является маскировка частот появления тех или иных букв в тексте, на основании которой обычно очень легко вскрываются моноалфавитные шифры.

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

Исходный текст: hello Зашифрованный текст: KHOOR

№12

Шифры перестановки уязвимы к нескольким видам атак только для зашифрованного текста.

Статистическая атака

Шифр перестановки не изменяет частоту букв в зашифрованном тексте; он только переставляет буквы. Так что первая атака, которая может быть применена, - анализ частоты отдельной буквы. Этот метод может быть полезен, если длина зашифрованного текста достаточно большая. Мы такую атаку рассматривали раньше. Однако шифры перестановки не сохраняют частоту пар и триграмм. Это означает, что Ева не может использовать такие инструментальные средства. Фактически, если шифр не сохраняет частоту пар и триграмм, но сохраняет частоту отдельных букв, то вероятнее всего, что это шифр перестановки.

Атака грубой силы

Ева, чтобы расшифровать сообщение, может попробовать все возможные ключи. Однако число ключей может быть огромно 1! + 2! + 3! + … + L!, где L — длина зашифрованного текста. Лучший подход состоит в том, чтобы попробовать отгадать число столбцов. Ева знает, что число столбцов делится на L. Например, если длина шифра — 20 символов, то

20=1×2×2×5

. Это означает, что номером столбцов может быть комбинация этих коэффициентов (1, 2, 4, 5, 10, 20). Однако только один столбец и только одна строка — маловероятные варианты.

Пример 4.28

Предположим, что Ева перехватила сообщение зашифрованного текста "EEMYNTAACTTKONSHITZG". Длина сообщения L = 20, число столбцов может быть 1, 2, 4, 5, 10 или20. Ева игнорирует первое значение, потому что это означает только один столбец и оно маловероятно.

a. Если число столбцов — 2, единственные две перестановки — (1,2) и (2, 1). Первое означает, что перестановки не было. Ева пробует вторую комбинацию. Она делит зашифрованный текст на модули по два символа "EE MY NT AA CT TK ON SH IT ZG". Затем она пробует переставлять каждый модуль из них, получая текст "ee ym nt aa tc kt no hs ti gz", который не имеет смысла.

b. Если номер столбцов — 4, тогда имеется 4! = 24 перестановки. Первая перестановка (1 2 3 4) означает, что не было никакой перестановки. Ева должна попробовать остальные. После испытания всех 23 возможностей Ева находит, что никакой исходный текст при таких перестановках не имеет смысла.

c. Если число столбцов — 5, тогда есть 5! = 120 перестановок. Первая (1 2 3 4 5) означает отсутствие перестановки. Ева должна попробовать остальные. Перестановка (2 5 13 4) приносит плоды — исходный текст "enemyattackstonightz", который имеет смысл после удаления фиктивной буквы z и добавления пробелов.

Атака по образцу

Другая атака шифра перестановки может быть названа атакой по образцу. Зашифрованный текст, созданный с помощью ключевого шифра перестановки, имеет некоторые повторяющиеся образцы. Следующий пример показывает зашифрованный текст, относительно которого известно, что каждый символ в зашифрованном тексте в примере 4.28 получается из исходного текста по следующему правилу:

1 -й символ в зашифрованном тексте получается из 3 -го символа исходного текста. 2 -й символ в зашифрованном тексте получается из 8 -го символа исходного текста. 20 -й символ в зашифрованном тексте получается из 17 -го символа исходного текста, и так далее. У нас имеются образцы в вышеупомянутом списке. Мы имеем пять групп: (3, 8, 13, 18), (1, 6, 11, 16), (4, 9, 14, 19), (5, 10, 15, 20) и (2, 7, 12, 17). Во всех группах разность между двумя смежными номерами — 5. Эта регулярность может использоваться криптоаналитиком, чтобы взломать шифр. Если Ева знает или может предположить число столбцов (в этом случае оно равняется 5 ), она может преобразовать зашифрованный текст в группы по четыре символа. Перестановка групп может обеспечить ключ к нахождению исходного текста.