Влияние современной электронной техники
В годы, непосредственно последовавшие за Второй мировой войной, электронные технологии, разработанные для поддержки радаров и недавно открытого цифрового компьютера, были адаптированы к криптомашинам. Первые такие устройства были не более чем роторными машинами, в которых роторы были заменены электронными заменителями. Преимуществом этих электронных машин была скорость работы; недостатками были слабости криптоанализа, унаследованные от механических роторных машин, и принцип циклического смещения простых подстановок для реализации более сложных подстановок продукта. Фактически, роторные машины и электронные машины сосуществовали в 1970-х и начале 80-х годов. В открытой литературе мало информации об электронных шифровальных машинах, используемых различными национальными криптологическими службами, поэтому наиболее достоверные сведения о развитии криптографии в период от последнего поколения роторных машин - KL-7, разработанных США для Организации Североатлантического договора (НАТО), до появления DES и систем с открытым ключом в 1976 году - можно найти в коммерческом оборудовании. (KL-7 был снят с эксплуатации в июне 1983 года; в 1985 году стало известно, что шпионская группа семьи Уокер передала Советскому Союзу устройство KL-7 и материалы для изготовления ключей).
Одним из классов электронных устройств, функционирующих подобно роторам, является генератор Фибоначчи (также называемый генератором Кокена в честь его изобретателя), названный в честь последовательности Фибоначчи из теории чисел. В классической последовательности Фибоначчи 1, 1, 2, 3, 5, 8, 13... каждый последующий член, начиная с 2, является суммой двух членов слева от него, т.е. Fi = Fi - 1 + Fi - 2. По свободной аналогии, любая последовательность, в которой каждый член является суммой набора более ранних членов в фиксированных (относительных) местах, называется последовательностью Фибоначчи.
В n-ступенчатом генераторе Фибоначчи содержимое n-битного регистра сдвигается вправо на одну позицию на каждом шаге - крайний правый бит сдвигается и теряется - и новый левый бит определяется логической суммой (1 + 1 = 1, 0 + 1 = 1 + 0 = 0 + 0 = 0; обозначается ⊕) битов, находящихся в заданных местах регистра сдвига до сдвига. Например, для n = 5 и xi = xi - 1 ⊕ xi - 4 ⊕ xi - 5 получается 31-битный цикл
которая является последовательностью максимальной длины, реализуемой с помощью пятиступенчатого генератора. Актуальность генераторов Фибоначчи для криптографии видна, если считать последовательность по пять бит за раз, последовательно сдвигая одну битовую позицию влево. Это дает скремблированный порядок целых чисел от 1 до 31, который напоминает скремблированный порядок, создаваемый роторами.
Криптографическая проблема заключается в том, что операция объединения, используемая для определения последовательных состояний в последовательности, является линейной и, следовательно, легко инвертируемой, даже если последовательность может иметь длину 2n - 1 бит до повторения. Другая проблема заключается в том, как будет использоваться ключ. Очевидный выбор - т.е. просто использовать ключ для определения количества шагов в цикле от кортежа открытого текста n до кортежа шифрованного текста n - криптографически небезопасен, поскольку известный криптоанализ открытого текста быстро раскроет ключ. Часто изобретаемым решением этой проблемы является использование числа, находящегося в выбранных местах одного регистра сдвига с обратной связью максимальной длины, в котором ключ используется в качестве начального заполнения регистра, для контроля числа шагов от открытого текста n кортежа до шифротекста n кортежа в цикле другого линейного регистра сдвига с обратной связью. В схемах такого рода ключевой регистр обычно сдвигается вперед, чтобы скрыть сам ключ до начала шифрования открытого текста, а затем продвигается на достаточное количество шагов между шифрованиями, чтобы обеспечить распространение переменных ключа. Для шифрования n-битного блока открытого текста, текст загружается в главный сдвиговый регистр и машина проходит определенное количество шагов, обычно кратное количеству битов в ключе, достаточное для распространения информации в открытом тексте и в ключе по всем позициям в результирующем шифротексте. Для расшифровки полученного шифротекста необходимо иметь обратную комбинаторную функцию или чтобы исходная функция шифрования была инволютивной - т.е. функции шифрования и расшифровки были идентичны, так что шифрование шифротекста восстанавливает открытый текст. Нетрудно спроектировать логику обратной связи для создания эвольвентной машины. Изобразительно машина просто повторяет свои шаги в цикле (циклах). Однако линейность в логике является мощным подспорьем для криптоаналитика, особенно если возможна атака с подбором открытого текста/шифротекста.
С небольшими изменениями, этот подход составляет основу нескольких коммерчески доступных криптографических устройств, которые функционируют в манере, весьма схожей с шифровальными машинами pin-and-lug, описанными ранее. Одна из таких криптомашин имеет шесть линейных сдвиговых регистров с обратной связью максимальной длины, шагом которых управляет другой сдвиговый регистр; содержимое последнего используется для обращения к (нелинейной) таблице поиска, определяемой ключами, предоставляемыми пользователем.
Чтобы избежать проблем, связанных с линейностью, криптографы разработали ряд нелинейных логик с обратной связью, которые обладают такими желательными свойствами, как распространение информации (для распространения эффектов небольших изменений в тексте) и крупноцикловая структура (для предотвращения исчерпывающего поиска), но которые вычислительно невозможно инвертировать, работая в обратном направлении от выходной последовательности к начальному состоянию (состояниям), даже при очень большом количестве пар совпадающих открытого текста/шифротекста. Нелинейная логика обратной связи, используемая для определения следующего бита в последовательности, может быть использована точно так же, как и линейная логика обратной связи. Однако осложняющее влияние ключа на шифротекст в нелинейной логике значительно увеличивает трудности, с которыми сталкивается криптоаналитик. Электронные шифровальные машины этого общего типа широко использовались как на коммерческой основе, так и национальными криптологическими службами.
Важность приведенных выше исторических замечаний заключается в том, что они естественным образом ведут к самому распространенному и используемому шифру в истории криптографии - стандарту шифрования данных (DES).