Какой алгоритм выбрать?

Мы разговаривали со многими криптографами, и все они начинали с объяснения, что такое шифр Цезаря. Он прост и удобен в обращении, но имеет один существенный недостаток - раскрыть его может каждый школьник. Поэтому не будем на нем останавливаться и сразу перейдем к шифру Виженера, либо Вернама, либо любому другому, в котором шифрование сводится к наложению одной последовательности на другую. Как признают все криптографы, при одноразовом использовании такого типа шифров дешифровать сообщение невозможно.

Простейший способ построить программу шифрования - реализовать генератор случайной последовательности, знаки которой можно последовательно складывать со знаками исходного сообщения. Для наложения, конечно, нужна не любая последовательность, а именно случайная. Что это такое? На первый взгляд нет проблем. Различных генераторов известно великое множество. Какой из них выбрать? Ответ очевиден - тот, который вырабатывает последовательность, наиболее близкую к случайной.

А теперь попробуйте дать определение случайной последовательности. Для эксперимента попросите кого-нибудь это сделать, и он наверняка скажет вам, что это такая последовательность, в которой каждый элемент случайно, независимо от других элементов и равновероятно может принимать каждое из возможных значений, или что-нибудь вроде ``это последовательность, являющаяся реализацией схемы независимых испытаний'', или - ``полученная в результате выборки из множества всех последовательностей с равномерным распределением''.

Недостаток использования такого рода определений для целей криптографии становится очевидным при взгляде на последовательность

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.

Она является одной из реализаций схемы последовательных независимых испытаний и ни в чем не уступает любой другой последовательности, например,

1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1,

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

38765043353179975014693910353191097086635896251806230

29822890926723711514115245155566479256098717968310496

83605391251330391031054184702591128155858755970005635

69377039492262413967236168374702472481350482084517454

3990212200528238143667515252273 ?

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

Каковы возможные критерии похожести? Легко сформулировать условия похожести одной последовательности на другую. Но как сформулировать, что значит ``последовательность похожа на случайную последовательность''? Эта проблема не имеет однозначного ответа. Есть много подходов к определению понятия ``похожести'', но каждый из них страдает односторонностью. Поэтому от выбранного вами подхода во многом зависит качество шифрования.