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




ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ - часть 2


Самая важная характеристика генератора псевдослучайных чисел - информационная длина периода, после которого числа либо начнут просто повторяться, либо их можно будет предсказывать. Эта длина фактически определяет возможное число ключей системы и зависит от алгоритма получения псевдослучайных чисел. Требуемую длину периода определяет степень секретности данных. Чем длиннее ключ, тем труднее его подобрать. Однако не только длина ключа гарантирует его стойкость к взлому. В том случае, если содержание шифрованного сообщения жизненно важно для государства и им заинтересуется национальная служба безопасности, то заранее нужно быть готовым к неудаче в столь неравном состязании. Люди из спецслужб легко найдут требуемый ключ своими специфическими неджентльменскими методами, далекими от математики и криптографии. Скорее всего, ключ им даст сам владелец на блюдечке с голубой каемкой и будет этому искренне рад.
     Вторая проблема состоит в следующем: на основании чего можно сделать заключение, что гамма конкретного генератора является непредсказуемой? Пока в мире нет еще универсальных и практически проверяемых критериев, позволяющих утверждать это. Неизвестна и общая теория криптоанализа, которая могла бы быть применена для такого доказательства, за исключением все возрастающего количества конкретных способов анализа, выработанных для различных практических целей. Интуитивно случайность воспринимается как непредсказуемость. Чтобы гамма считалось случайной, как минимум необходимо, чтобы ее период был очень большим, а различные комбинации бит определенной длины равномерно распределялись по всей ее длине. Итак, второе требование к ряду заключается в подтверждаемом статистически подобии его свойств настоящей случайной выборки. Каждый порядок элементов гаммы должен быть так же случаен, как и любой другой. Это требование статистики можно толковать и как сложность закона формирования ряда псевдослучайных чисел. Практически, если по достаточно длинной реализации этот закон вскрыть не удается ни на статистическом уровне, ни аналитически, то этим нужно удовлетвориться. Чем длиннее требуемая длина ряда, тем жестче к нему требования. Теперь подробнее расскажем, как вскрывались скрытые закономерности в последовательностях чисел. С древнейших времен люди наблюдали и изучали периодически повторяющиеся процессы, как фазы Луны, движения планет, чередования времен года, но не все такие цикличности выражены явно. Например, солнечные пятна, наблюдаемые невооруженным глазом с начала нашей эры и в телескопы с начала XVII века, дают пример скрытой периодичности в II лет, впервые обнаруженной Генрихом Швабе лишь в 1843 году. А вот среднегодовые температуры и изменение климата Земли связаны с циклами в 19 лет. Работы Винера и Хинчина поставили анализ периодичностей с головы на ноги. Ими предложено оценивать спектр случайных колебаний значений элементов гаммы как преобразование Фурье функции автокорреляции. При этом шумоподобному равномерному спектру гаммы без скрытых периодичностей соответствует автокорреляционная функция в виде одиночного выброса в нуле, то есть так называемая дельта-функция. Этот результат можно интерпретировать как непохожесть последовательности на себя при любом ее сдвиге.
     И, наконец, последнее третье требование связано с возможностью практической реализации генератора в виде программы или электронного устройства, быстродействием, необходимым для применения в современных коммуникациях, а также удобством его практического использования.




Содержание  Назад  Вперед