Хорст Файстель. Криптография и компьютерная безопасность. Перевод А.Винокурова. Часть 4.
В системе "Люцифер" входные данные пропускаются через чередующиеся уровни блоков, которые мы обозначим символами P и S. P обозначает блок перестановок, в котором n является большим числом (128 или 64), а S обозначает блок подстановок, в котором n мало (4). Несмотря на то, что P-блоки в отдельности и S-блоки в отдельности составили бы слабую систему, их стойкость в комбинации друг с другом весьма значительна.
Мы проиллюстрируем меру стойкости подобных конструкций на примере изображенного ниже на рисунке устройства, в котором для простоты P-блоки имеют размер n = 15, а S-блоки n = 3. Если мы изобразим этот бутерброд из блоков, "озадаченный" специально сконструированным входным числом, составленным из 14-ти нулей и одной единственной единицы, то легко будет увидеть перемешивание и рассеивание в работе. Первый блок, P, передает единственную единицу на вход некоторого блока S, который, будучи нелинейным устройством, может преобразовать единицу в трехцифровой выход, содержащий в потенциале целых три единицы. В показанном на диаграмме варианте он вырабатывает две единицы. Следующий блок, P, тасует две единицы и передает их на вход двух различных S-блоков, которые вместе имеют потенциал по выработке целых шести единиц. Дальше диаграмма говорит сама за себя: по мере того, как входной блок данных проходит через последовательные уровни, узор из сгенерированных единиц расширяется и дает в результате непредсказуемый каскад цифр. Конечный результат, получающийся на выходе всей цепочки, будет содержать в среднем половину нулей и половину единиц, в зависимости от ключей перестановки, использованных в различных P- и S-блоках.
Составная шифрующая система объединяет S-блоки и P-блоки в единую конструкцию. P-блоки имеют большое количество входов (на рисунке показано 15), а S-блоки - столько входов, сколько подобные устройства в состоянии обслужить - три в данном случае. P-блоки тасуют цифры, обеспечивая рассеивание. S-блоки предусматривают нелинейные подстановки и таким образом обеспечивают перемешивание. В этом упрощенном примере вход системы включает одну единицу и четырнадцать нулей. Поскольку S-блоки нелинейны, они потенциально увеличивают число единиц, тогда как P-блоки просто двигают единицы с места на место. Результатом может быть непредсказуемая лавина единиц.
Очень важный факт заключается в том, что все выходные цифры потенциально стали очень сложными функциями всех входных цифр. Поскольку все блоки имеют независимые ключи, поток вырабатываемых цифр и окончательный результат не могут быть предсказаны. Целью разработчика, конечно, является сделать предельно трудным для оппонента проследить цепочки назад и, таким образом, реконструировать ключи в P- и S-блоках.
В реальной системе "Люцифер" мы сочли целесообразным внести в описанную схему несколько важных изменений. Например, S-блок, являясь достаточно общим преобразованием, может случайно быть снабжен таким ключом, что будет вести себя в точности как P-блок, и в этом случае вся система будет не более стойкой, чем один слой P, который может быть раскрыт описанной выше процедурой "щекотания". Чтобы этого избежать, блоки обоих типов, S и P, снабжаются постоянными ключами, которые должны быть сильными; эти постоянные ключи будут известны каждому, кто имеет доступ к системе. Следовательно, нам необходим другой способ использовать ключи, при этом желательно, чтобы они могли быть представлены двоичными числами. Этого можно достигнуть построением "бутерброда", в котором каждый S-блок содержит два различных постоянных ключа, и, таким образом, может быть представлен двумя возможными различными состояниями, S0 и S1. Последовательность этих состояний для любого отдельного "бутерброда" составляет управляемую ключом структуру, неизвестную потенциальному оппоненту. Эта структура может быть представлена двоичным ключом, который в сущности указывает, которую из двух таблиц подстановки следует использовать, в точности как в случае двухтабличной подстановки, обсуждавшейся ранее (см. следующую ниже иллюстрацию; на диаграмме изображены 25 S-блоков, и таким образом, ключ имеет длину 25 цифр, в реальных устройствах может быть много больше S-блоков, и соответственно более длинный ключ.) Цифры ключа могут быть загружены в ключевой регистр криптографического устройства и могут быть записаны на ключевую магнитную карту, закрепленную за законным пользователем системы. Когда два состояния S-блоков используются подобным образом, результирующая криптограмма показывает наличие существенных межсимвольных зависимостей, которые делают все цифры выхода сложными функциями не только всех цифр входа, но и всех цифр ключа. Мы, таким образом, показали, что система устойчива к попыткам проникновения с помощью математических методов анализа.
Шаблон из S0 и S1. S1 S0 S1 S0 S0 S0 S1 S0 S1 S1 S1 S1 S1 S0 S1 S1 S0 S1 S0 S1 S1 S1 S0 S1 S0 Двоичный "шаблонный" ключ 1 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 0 Возможность использования индивидуальных ключей необходима, потому что ключи, встроенные в S- и P-блоки, известны всем, кто имеет доступ к системе. Эта возможность может быть обеспечена способом, показанным на данном рисунке. Для каждого S-блока в системе существуют два возможных состояния, S0 и S1. Порядок, в котором они используются, определяется двоичным ключом, как показано на нижней части иллюстрации.
Хотя сильная межсимвольная зависимость является необходимым (но не достаточным) показателем криптографической стойкости, она имеет и оборотную сторону: она влечет за собой очень большую чувствительность к шуму или помехам во время передачи. Погрешность в единственной цифре может через эффект "обратной лавины" привести к полному искажению расшифрованных данных. Современные средства коммуникации делают, однако, проблему менее актуальной по крайней мере для невоенного использования.
Более того, сильные взаимозависимости между цифрами могут принести удивительную и неожиданную пользу: поскольку система так чувствительна к изменениям и так резко реагирует на них, она автоматически становится идеальным средством обнаружения таких изменений, как произошедших случайно, так и сделанных умышленно. И мы, таким образом, одним выстрелом убиваем двух зайцев - имеем одновременно высокую секретность сообщений и неподдающийся обману сигнализатор ошибок.
Чтобы извлечь пользу из этой дополнительной особенности шифра нам необходимо всего лишь зарезервировать место для "пароля" внутри заданного блока цифр сообщения. Пароль - это последовательность цифр, автоматически вводимая в поток цифр сообщения передающей аппаратурой без какого-либо участия лица, использующего систему. Роль пароля заключается в том, чтобы сообщить приемной аппаратуре, что сообщение не было преднамеренно искажено или серьезно испорчено шумом в процессе передачи. Процесс зашифрования оставляет оппонента в неведении, как биты сообщения и пароля отображены в криптограмме. Если цифры пароля не могут быть восстановлены декодером на принимающем конце без ошибок, сообщение отвергается.
Решающую роль в этой схеме играет генератор пароля, который должен быть как на приемнике, так и на передатчике, как показано на следующем ниже рисунке. Генератор пароля на самом деле является не чем иным, как двоичным таймером или счетчиком, определяющим время или порядковый номер сообщения в двоичной записи, и добавляющим эту группу цифр к каждому блоку цифр передаваемого сообщения. Мы подразумеваем, что в определенный момент времени, скажем в 8:00, таймеры на обоих концах канала передачи были синхронизированы и их частоты одинаковы.
Полная система объединяет генератор пароля, составную криптографическую систему, такую, как "бутерброд" из S- и P-блоков, показанный на предыдущей иллюстрации, и систему коррекции ошибок. Генератор паролей вырабатывает свежий парольный блок для каждого блока данных. Отправитель, используя свой персональный ключ, вводит свои данные. Цифры пароля и данных станут неотслеживаемыми после того, как будут зашифрованы в соответствии с ключом. Дополнительные цифры кода коррекции ошибок добавляются к данным перед передачей и изымаются сразу после приема. Криптографическая система компьютерного центра расшифровывает передачу в соответствии с инвертированным ключом отправителя, который выбирается из специального защищенного файла, хранимого в центре, и извлекает цифры пароля. Если они совпадут с цифрами пароля, сгенерированного в компьютере, шлюз открывается и входные данные передаются в хранилище как имеющие законный источник.
Теперь давайте посмотрим, как "парольная схема аутентификации" обеспечивает безопасность работы членам сообщества пользователей централизованного хранилища данных, которые имеют доступ к большому центральному компьютеру. Каждый участник имеет свой собственный секретный ключ, возможно, представленный в форме последовательности двоичных цифр, записанной на магнитную карту. Ключи всех пользователей хранятся в подходящим образом защищенной форме в центральном компьютере. Предположим, что пользователь с ключом KА хочет передать сообщение на центральный компьютер. Он вставляет карточку, на которой записан его ключ, в напоминающий пишущую машинку терминал, располагающийся на его рабочем столе, секунду или две ждет сигнала что линия свободна, и начинает набирать свое сообщение.
Сообщение автоматически разделяется на блоки цифр (скажем, по 64 цифры), которые на каждом тике двоичного таймера объединяются с паролем (который также может иметь размер 64 цифры), соответствующим выходу таймера в этот момент времени. Результирующий блок из 128 цифр подвергается зашифрованию, для чего пропускается через сэндвич из P- и S-блоков, который полностью перемешивает цифры пароля и цифры данных.
Поскольку результирующая криптограмма очень чувствительна к ошибкам передачи, она усиливается с помощью подходящего кода исправления ошибок, который должен соответствовать шумовым характеристикам используемых телефонных линий. Добавление этого кода удлиняет блок, содержащий цифры пароля и сообщения, еще на несколько цифр. Результирующий блок шифрограммы предваряется адресом отправителя в открытом виде и передается на центральный компьютер. Когда сообщение доходит до адресата, ключ KА, принадлежащий пользователю А, отыскивается в списке и его обращение загружается в декодер для того, чтобы расшифровать криптограмму.
Теперь решающей проверкой является, будет ли совпадать пароль из полученной криптограммы с паролем, локально выработанным двоичным таймером на принимающей стороне. При отсутствии искажений и если криптограмма была действительно зашифрована на ключе пользователя А выход декодера будет состоять из блока цифр данных и блока цифр пароля. Это считается достаточным свидетельством в пользу того, что криптограмма действительно создана участником А. Данные принимаются системой как имеющие законный источник.
Что же случится, если произошло искажение данных? Если оно было вызвано спорадическими всплесками шума в линии передачи, код исправления ошибок устранит его и сообщение успешно пройдет аутентификацию. Если, однако, искажения имеют такую природу, что не могут быть устранены кодом коррекции ошибок, то даже одна неверная цифра произведет эффект лавины в декодирующем устройстве и превратит весь выход в мусор. Пароли больше не будут совпадать. Система воспримет сообщение как имеющее подозрительное происхождение и отвергнет его.
Парольный тест сработал бы так же надежно, если кто-либо записал бы перехваченное сообщение и повторно передал бы его позже, когда пароль перестал быть действительным. Конечно, использование неверного ключа является причиной для немедленной отбраковки сообщения. Представляется, что предложенная система устойчива к любой мыслимой попытке обмануть ее. Каждая двоичная цифра пароля обеспечивает один бит аутентифицирующей информации. Если пароль имеет длину в n цифр, то оппонент имеет лишь один шанс из 2n (или один шанс из 264, если n = 64) сгенерировать любым выбранным им способом такую криптограмму, которая при расшифровании случайно даст истинный пароль. Число 264 равно примерно 1019. Невозможно аутентифицировать данные более эффективно.
Нет причин, которые бы препятствовали распространению системы, описанной только что для одного пользователя, на всех пользователей сети для обеспечения их безопасной работы. В нашей лаборатории, как и в других местах продолжается также исследование и других криптографических подходов. Было бы удивительно, если бы криптография, будучи традиционным средство обеспечения конфиденциальности связи, не смогла бы обеспечить безопасность сообществу пользователей банков данных.
[Титульный лист] [Предыдущий раздел] [Следующий раздел]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]
Версия от 23.12.00. (c) 1998-2000 Андрей Винокуров.
