Криптография, комбинаторные алгоритмы и вычислительная техника

Зададимся теперь вопросом: от прогресса в каких областях науки зависят оценки практической стойкости шифров? Внимательный читатель сам из предыдущего изложения ответит на этот вопрос: в первую очередь это – теория сложности алгоритмов и вычислений, а также сложность реализации алгоритмов на вычислительной технике. В последние годы эти области бурно развиваются, в них получены интересные результаты, которые, в частности, влияют на оценки практической стойкости шифров. Многие полезные результаты носят характер «ухищрений» для ускорения алгоритмов и поэтому быстро входят в массовую практику программистов. Особенно это относится к области комбинаторных алгоритмов, выросшей из хорошо известных типичных задач быстрого поиска и сортировки данных. Систематическое подробное изложение этих вопросов содержится в популярном трехтомнике Д. Кнута «Искусство программирования для ЭВМ».

Отметим, что к области комбинаторных алгоритмов относятся также алгоритмы для хорошо известных игр‑головоломок типа «кубика Рубика».

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

Подумайте сами:

1. Докажите, что наименьший элемент среди чисел { x ₁,..., x _n } нельзя найти меньше, чем за n −1 сравнение.

2. Предложите алгоритм расположения чисел { x ₁,..., x _n } в порядке возрастания, использующий меньше, чем n (n −1)/2 сравнений (т.е. более эффективный, чем тривиальный алгоритм последовательного сравнения каждого числа с каждым).

3. На полке в беспорядке стоят n томов собрания сочинений. Хозяин, увидев два тома, стоящие в неправильном порядке, меняет их местами. Докажите, что не позднее, чем через n ² таких перестановок, тома будут расставлены по порядку.

4. На сортировочной станции имеется несколько поездов. Разрешается либо расцепить поезд, состоящий из нескольких вагонов, на два поезда, либо удалить поезд, если в нём всего один вагон. Докажите, что, выполняя эти действия в произвольном порядке, мы рано или поздно удалим все вагоны.

5. Задумано и введено в компьютер n натуральных чисел a ₁,..., a _n. За один шаг разрешается ввести в компьютер любые n других натуральных чисел b ₁,..., b _n. После этого компьютер вычисляет сумму a ₁ b ₁+...+ a _n b _n и выводит результат на экран. Ясно, что этот результат содержит некоторую информацию о задуманных числах. За какое минимальное число шагов всегда можно угадать задуманные числа?