От ручных шифров — к шифрмашииам и компьютерным программам

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

Тот же принцип сохранился и в электрических машинах, названных дисковыми, или роторными. Все эти машины реализуют шифр замены. Принцип работы дисков был предложен одновременно несколькими криптографами: американцем Э. Хеберном (1918), голландцем X. Кохом (1919), шведом А. Даммом (1919) и немцем А. Шербиусом (1927). Последний сконструировал знаменитую дисковую машину «Энигма» («Загадка»). Из четырех изобретателей только Дамму удалось добиться коммерческого успеха. В Швеции фирма АО «Криптография» (управляющий — Борис Хагелин, долгое время живший в России) выпустила весьма компактную и удобную в работе машину «Хагелин». Несколько ее модификаций были выпущены в огромном количестве и проданы в различных странах. Только США в период войны заказали 140 000 машин, появившихся у пользователей под названием «Конвертер М-209». После войны фирма перекочевала в Швейцарию, г. Цуг, поменяв название на нынешнее «CRYPTO AG».

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

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

В отличие от поточных блочные шифры с использованием (как правило) неизменного отображения обрабатывают блоки информации, размер блока чаще всего составляет 64 или 128 битов. Необходимость в электронных блочных шифрах замены назрела в начале 1970;х гг. в связи с обработкой компьютерной информации. Немаловажно, что развитие информационнотелекоммуникационных сетей сопровождалось рядом важных изменений не только в криптологии, но и в более широкой научной области — теории информационной безопасности. Усложнились математические и инженерные модели объектов информационной защиты; хранение, обработка и передача информации в компьютерных сетях привели к необходимости защищать ресурсы компьютерных сетей. Произошло стремительное развитие научных направлений и технологий, связанных с криптологией и со смежными науками. Получили развитие теория чисел, теория сложности вычислений и моделирование вычислений, в том числе в задачах дешифрования. Объектами исследования стали различные модели параллельных вычислений (кластерных и распределенных), квантовые вычисления.

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

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

Новизна задачи построения СБШ состояла в разработке криптографически стойких, удобно реализуемых (аппаратно и программно) шифров замены алфавита большого порядка.

Первым опытом создания блочного шифра явился разработанный американской фирмой IBM шифр «Люцифер». Блоки открытого и шифрованного текста, обрабатываемые «Люцифером», представляют собой двоичные векторы длины 128 битов. Шифр построен по принципу «сэндвича», составленного из нескольких чередующихся слоев — преобразований замены (substitution) блоков и преобразований перестановки (pennutation) координат блоков. Такие схемы получили название SP-сетей (сетей перестановок и замен). Криптографическая идея SP-сети заключается в построении сложного преобразования с помощью композиции нескольких относительно простых, удобно реализуемых преобразований.

При реализации этой в целом перспективной криптографической идеи не обошлось без издержек: схема получилась громоздкой, имела низкую производительность. Скорость шифрования различных программных и аппаратных реализаций «Люцифера» не превышала соответственно 8 и 97 Кбайт/с. К тому же, подтвердились опасения по поводу криптографической стойкости шифра. Однако накопленный при создании «Люцифера» опыт вскоре пригодился.

В 1973 г. Национальное бюро стандартов (NBS) США объявило конкурс, целью которого стала разработка стандарта шифрования данных. Победила фирма IBM, представившая в 1974 г. алгоритм шифрования, известный под названием DES — Data Encryption Standart.

Алгоритм DES шифрует 64-битовые блоки данных с помощью 56-битового ключа. Подобно «Люциферу» он построен по итеративному принципу, т. е. на основе композиции нескольких однотипных преобразований. В дальнейшем итеративный принцип построения использовался в подавляющем большинстве разработок СБШ.

Алгоритм был опубликован (беспрецедентный исторический факт для «действующего» шифра!) и явился не только предметом активного изучения со стороны специалистов многих стран, но и мощным импульсом для развития коммерческой (невоенной) криптологии. Масштабы использования /ЖУ-алгоритма в коммерческом секторе были впечатляющими. Его стали использовать во многих странах мира далеко за пределами США.

Между тем с самого начала DES подвергался критике из-за короткой длины ключа, что повлекло запрет на его использование для защиты государственных секретов США. Последовавшие за опубликованием алгоритма десятилетия показали, что гипотетические методы вскрытия DES на основе распараллеливания перебора ключей постепенно превратились в реальность. Кроме того, производительность DES-алгоритма в силу особенностей реализации на современных процессорах стала отставать от растущих потребностей пользователей.

В условиях объективно назревающей потребности в замене действующего стандарта наряду с его критикой криптографы неустанно разрабатывали блочные шифры, достойные заменить DES. К ним относятся как различные схемы усложнения 7Ж?-алгоритма (с независимыми цикловыми ключами, кратного шифрования, с увеличенными размерами блоков и ключей), так и оригинальные схемы NewDES, FEAL, IDEA и др.

В 1997 г. NIST^[1] объявил о начале программы по принятию A ES {Advanced Encryption Standard) — стандарта XXI в. для криптографической защиты данных. Был проведен трехэтапный международный конкурс с целью разработки отвечающего современным требованиям блочного шифра с высокими эксплуатационными качествами и криптографической стойкостью. Победителем конкурса стал разработанный бельгийцами (авторы — Дж. Даймон и В. Реймен) алгоритм RIJNDAEL_y который и был объявлен новым криптографическим стандартом, вступившим в силу в 2002 г.

Еще одним крупнейшим событием в истории криптологии XX в. стало изобретение криптосистем с открытым ключом, отмеченное в параграфе 12.3.

В заключение заметим, что история развития криптологии в XX в. оказалась чрезвычайно насыщенной. К основным событиям следует отнести:

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

• [1] NIST — National Institute for Standards and Technology (до 1988 г. — NBS, NationalBureau of Standards), Национальный институт по стандартам и вычислительной технике, являющийся подразделением министерства торговли США. По решению Конгресса СШАNIST отвечает за стандарты, касающиеся ЭВМ и соответствующих систем связи.