Материал: MethodFull

Проблема в том, что генератор случайных чисел не создает случайной последовательности. Он, возможно, не выдает ничего даже отдаленно напоминающего случайную последовательность. Конечно, невозможно созда­вать на компьютере что-то по настоящему случайное. Дональд Кнут приписывал фон Нейману следующие слова: "Каждый, кто занимается арифметическими методами получения случайных чисел, определенно грешит ". Компьютеры – это детерминированные бестии: закладывается известный материал, выполняются полно­стью предсказуемые действия, и что-то отличное выползает с другого конца. Подача одного и того же на вход в двух различных случаях приведет к одному и тому же результату. Заложите одинаковые исходные данные в два идентичных компьютера, и оба они подсчитают одно и то же. Компьютер может находиться только в ограниченном числе состояний (очень большом, но все же ограниченном), и выдаваемый результат всегда будет строго определяться исходными данными и текущим состоянием компьютера. Это значит, что любой генератор слу­чайных чисел на компьютере (по меньшей мере, на конечном автомате), по определению, периодичен. А все, что периодично, по определению, предсказуемо. А все, что предсказуемо, не может быть случайным. Для на­стоящего генератора случайных чисел нужно подавать на вход что-нибудь случайное, компьютер же не может обеспечить это требование.

Псевдослучайные последовательности

Лучшее, что может сделать компьютер - это генератор псевдослучайных последовательностей. Что это такое? Многие пытались дать его формальное определение, но мы уклонимся от этого. Псевдослучайная последовательность – это что-то, выглядящее как случайное. Период последовательности должен быть достаточно велик, поэтому конечная последовательность разумной длины – которая в действительности и используется – не периодична. Если вам нужен миллиард случайных бит, не пользуйтесь генератором последовательности, повторяющейся каждые шестнадцать тысяч бит. Эти относительно короткие непериодические подпоследовательности должны быть, насколько это возможно, неотличимы от случайных последовательностей. Например, в них должно быть примерно одинаковое количество единиц и нулей, около половины серий (последовательностей одинаковых бит) должны быть единичной длины, четверть - состоять из двух бит, восьмая часть - из трех, и т.д. Эти последовательности должны быть несжимаемы. Распределение длин серий для нулей и единиц должно быть одинаковым. Эти свойства могут быть измерены опытным путем и затем сравнены с ожидаемыми статистически с помощью статистики хи-квадрат. Для наших целей генератор последовательности считается псевдослучайным, если он обладает следующим свойством:

1. Он выглядит случайно. Это означает, что он проходит все тесты на случайность, которые нам удалось найти.

Множество усилий было затрачено на создание хороших псевдослучайных последовательностей на компьютере. Обсуждение генераторов в большом количестве можно найти в академической литературе вместе с различными тестами на случайность. Все эти генераторы периодичны (этого невозможно избежать), но, если их период 2²⁵⁶и выше, они могут быть использованы в самых серьезных приложениях.

Проблема именно в этих таинственных корреляциях и странных результатах. Каждый генератор псевдослу­чайных последовательностей создает такие странности, если вы используете его определенным образом. А это именно то, что нужно криптоаналитику для взлома системы.

Криптографически безопасные псевдослучайные последовательности

Криптографические приложения предъявляют к генератору псевдослучайных последовательностей более высокие требования по сравнению с другими приложениями. Криптографическая случайность не ограничивается статистической случайностью, хотя и включает ее. Чтобы последовательность была криптографически безопасной псевдослучайной последовательностью, она должна обладать следующим свойством:

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

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

Как и любой криптографический алгоритм, генераторы криптографически безопасных псевдослучайных последовательностей представляют собой предмет вскрытия. Так же как криптографический алгоритм, может быть взломан и генератор криптографически безопасных псевдослучайных последовательностей . Создание ус­тойчивых к вскрытию генераторов является основой криптографии.

Настоящие случайные последовательности

Теперь мы вторгаемся в область, принадлежащую философам. Существует ли такая вещь как случайность? Что такое случайная последовательность? Как узнать, что последовательность случайна? Является ли "101110100" более случайной чем "101010101"? Квантовая механика убеждает нас в том, что в реальном мире существует настоящая случайность. Но как сохранить эту случайность в предопределенном мире компьютерных микросхем и конечных автоматов?

В сторону философию, с нашей точки зрения генератор последовательности действительно случаен, если он обладает третьим свойством:

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

Выход генератора, удовлетворяющего всем трем приведенным требованиям, будет достаточно хорош для одноразового блокнота, генерации ключа и других криптографических применений, требующих генерации действительно случайных последовательностей. Трудность в том, чтобы понять, действительно ли последовательность случайна? Если я повторно зашифрую строку, используя DES и заданный ключ, я получу хороший, вы­глядящий случайным образом результат, вы не сможете сказать, что он не случаен, пока вы не наймете взломщика DES.

Типы алгоритмов и криптографические режимы

Существует два основных типа симметричных алгоритмов: блочные шифры и потоковые шифры. Блочные шифры работают с блоками открытого текста и шифротекста – обычно длиной 64 бита, но иногда длиннее.Потоковые шифры работают с битовыми или байтовыми потоками открытого текста и шифротекста (иногда да­же с потоками 32-битных слов). Блочный шифр, использующий один и тот же ключ, при шифровании всегда превращает один и тот же блок открытого текста в один и тот же блок шифротекста. Потоковый шифр при каж­дом шифровании превращает один и тот же бит или байт открытого текста в различные биты или байты шифротекста.

Криптографический режим обычно объединяет базовый шифр, какую-то обратную связь и ряд простых операций. Операции просты, потому что безопасность является функцией используемого шифра, а не режима. Бо­лее того, режим шифра не должен компрометировать безопасность используемого алгоритма.

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

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

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