Библиотека Интернет Индустрии I2R.ru

В системе "Люцифер" входные данные пропускаются через чередующиеся уровни блоков, которые мы обозначим символами 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-блок содержит два различных постоянных ключа, и, таким образом, может быть представлен двумя возможными различными состояниями, S₀ и S₁. Последовательность этих состояний для любого отдельного "бутерброда" составляет управляемую ключом структуру, неизвестную потенциальному оппоненту. Эта структура может быть представлена двоичным ключом, который в сущности указывает, которую из двух таблиц подстановки следует использовать, в точности как в случае двухтабличной подстановки, обсуждавшейся ранее (см. следующую ниже иллюстрацию; на диаграмме изображены 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-блока в системе существуют два возможных состояния, S₀ и S₁. Порядок, в котором они используются, определяется двоичным ключом, как показано на нижней части иллюстрации.

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

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

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

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

Полная система объединяет генератор пароля, составную криптографическую систему, такую, как "бутерброд" из S- и P-блоков, показанный на предыдущей иллюстрации, и систему коррекции ошибок. Генератор паролей вырабатывает свежий парольный блок для каждого блока данных. Отправитель, используя свой персональный ключ, вводит свои данные. Цифры пароля и данных станут неотслеживаемыми после того, как будут зашифрованы в соответствии с ключом. Дополнительные цифры кода коррекции ошибок добавляются к данным перед передачей и изымаются сразу после приема. Криптографическая система компьютерного центра расшифровывает передачу в соответствии с инвертированным ключом отправителя, который выбирается из специального защищенного файла, хранимого в центре, и извлекает цифры пароля. Если они совпадут с цифрами пароля, сгенерированного в компьютере, шлюз открывается и входные данные передаются в хранилище как имеющие законный источник.

Теперь давайте посмотрим, как "парольная схема аутентификации" обеспечивает безопасность работы членам сообщества пользователей централизованного хранилища данных, которые имеют доступ к большому центральному компьютеру. Каждый участник имеет свой собственный секретный ключ, возможно, представленный в форме последовательности двоичных цифр, записанной на магнитную карту. Ключи всех пользователей хранятся в подходящим образом защищенной форме в центральном компьютере. Предположим, что пользователь с ключом K_А хочет передать сообщение на центральный компьютер. Он вставляет карточку, на которой записан его ключ, в напоминающий пишущую машинку терминал, располагающийся на его рабочем столе, секунду или две ждет сигнала, что линия свободна, и начинает набирать свое сообщение.

Сообщение автоматически разделяется на блоки цифр (скажем, по 64 цифры), которые на каждом тике двоичного таймера объединяются с паролем (который также может иметь размер 64 цифры), соответствующим выходу таймера в этот момент времени. Результирующий блок из 128 цифр подвергается зашифрованию, для чего пропускается через сэндвич из P- и S-блоков, который полностью перемешивает цифры пароля и цифры данных.

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

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

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

Парольный тест сработал бы так же надежно, если кто-либо записал бы перехваченное сообщение и повторно передал бы его позже, когда пароль перестал быть действительным. Конечно, использование неверного ключа является причиной для немедленной отбраковки сообщения. Представляется, что предложенная система устойчива к любой мыслимой попытке обмануть ее. Каждая двоичная цифра пароля обеспечивает один бит аутентифицирующей информации. Если пароль имеет длину в n цифр, то оппонент имеет лишь один шанс из 2ⁿ (или один шанс из 2⁶⁴, если n = 64) сгенерировать любым выбранным им способом такую криптограмму, которая при расшифровании случайно даст истинный пароль. Число 2⁶⁴ равно примерно 10¹⁹. Невозможно аутентифицировать данные более эффективно.

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