Введение в криптографию
Низкая криптостойкость может быть обусловлена не только алгоритмом шифрования, но и процедурой выбора ключа: если ключ может принимать любые двоичные значения заданной разрядности, но реально для его выбора используется страдающий неоднородностью генератор псевдослучайных чи-:ел, мы можем значительно сократить объем пространства, которое реально должен будет перебрать взломщик наших сообщений (вопросы генерации равномерно распределенных псевдослучайных чисел обсуждаются во втором томе классической книги [Кнут 2000]). Еще хуже ситуация, когда в качестве ключа используются "легко запоминаемые" слова естественного языка: в этом случае реальный объем пространства ключей даже довольно большой разрядности может измеряться всего лишь несколькими тысячами различных значений.
Современные алгоритмы шифрования делятся на два основных класса: с секретным и с публичным ключом (кажущееся противоречие между термином "публичный ключ" и приведенными выше рассуждениями будет разъяснено далее).
Алгоритмы с секретным ключом, в свою очередь, делятся на потоковые (stream) и блочные (block). Потоковые алгоритмы обычно используют подстановку символов без их перестановки. Повышение криптостойкости при этом достигается за счет того, что правила подстановки зависят не только от самого заменяемого символа, но и от его позиции в потоке.
Примером простейшего – и в то же время абсолютно не поддающегося взлому – потокового алгоритма является система Вернама или одноразовый блокнот (рис. 1.10). Система Вернама основана на ключе, размер которого равен размеру сообщения или превосходит его. При передаче двоичных данных подстановка осуществляется сложением по модулю 2 (операцией исключающего или) соответствующих битов ключа и сообщения.
Рис. 1.10. Система Вернама
Если ключ порожден надежным генератором случайных чисел (например, правильно настроенным оцифровщиком теплового шума), никакая информация об автокорреляциях в исходном тексте сообщения взломщику не поможет: перебирая полное пространство ключей, взломщик вынужден будет проверить все сообщения, совпадающие по количеству символов с исходным, в том числе и все сообщения, удовлетворяющие предполагаемому автокорреляционному соотношению.
Это преимущество теряется, если один и тот же ключ будет использован для кодирования нескольких сообщений: взломщик, перехвативший их все, сможет использовать эти сообщения и предположения об их содержимом при попытках отфильтровать ключ от полезной информации – отсюда и второе название алгоритма. Применение системы Вернама, таким образом, сопряжено с дорогостоящей генерацией и, главное, транспортировкой ключей огромной длины, и поэтому она используется лишь в системах экстренной правительственной и военной связи.
Более практичным оказалось применение в качестве ключа псевдослучайных последовательностей, порождаемых детерминированными алгоритмами. В промежутке между первой и второй мировыми войнами широкое распространение получили шифровальные машины, основанные на механических генераторах таких последовательностей. Чаще всего использовались сочетания, получаемые при вращении колес с взаимно простыми количествами зубцов.