Криптография

kIlka и AssassiN

Спецвыпуск Xakep, номер #041, стр. 041-004-2

Сеть Файстеля и DES

Самое время поговорить о каком-нибудь современном криптоалгоритме. Пожалуй, самым известным алгоритмом, использующим один ключ, являются DES (Data Encription Standart). До недавнего времени он был официальным американским стандартом для защиты линий связи и компьютерных данных. История его принятия в этом качестве не менее интересна, чем сам алгоритм. Поговаривают, что NSA (National Security Agency) предполагала, что будут существовать лишь аппаратные реализации DES (то есть, что он будет реализован лишь в специальных микросхемах). Однако NSA и NBS (National Bureau of Standarts) не договорились. И в итоге опубликованное описание алгоритма оказалось настолько полным, что можно было без труда выполнить и программную реализацию. Так алгоритм стал доступен широким массам трудящихся =).

Один раунд шифрования в сети Файстеля

Основой для DES послужил разработанный инженерами IBM алгоритм Люцифер. Люцифер основывался на принципе, предложенном Хорстом Файстелем и получившем название сеть Файстеля. В сущности, сеть Файстеля базируется все на том же XOR’е (то есть представляет собой гаммирование). Хитрость - в выборе гаммы. Легче всего понять алгоритм из рисунка. Блок данных определенной длины (для DES это 64 бита) делится на две части (равные или нет, зависит от типа сети – сбалансированной или нет соответственно). Правая часть Rj ставится на место левой. Левая же часть XOR’ится с Fj. Fj – функция гаммирования, зависящая от Rj и Kj (исходный ключ преобразуется на j шаге в Kj). В алгоритме таких шагов (называемых раундами) может быть несколько. DES состоит из 16 раундов. Длина его ключа – 64 бита, правда, реально работают лишь 56 (8 используются для проверки четности). Еще одна интересная особенность DES – его симметричность. Для дешифровки используется тот же алгоритм, что и для шифрования. Это связано с симметрией последовательности Kj. Среди 2^56 возможных ключей DES существуют 80 так называемых слабых. Однако определение того, является ли ключ слабым, элементарно. И все же ключ длиной в 56 бит по нынешним меркам коротковат. Поэтому многие сейчас используют тройное шифрование при помощи DES с различными ключами – тройной DES. Американцы же в 2001 году приняли новый стандарт AES на базе алгоритма Rijndael. Длина ключа Rijndael варьируется от 128 до 256 битов.