6.4 Новый американский стандарт aes

В 1997 г. NIST (National Institute of Standards and Technology) анонсировал конкурс на создание AES (Advanced Encryption Standard) - нового государственного криптографического стандарта США 10.4.8, 10.4.28, 10.5.1, 10.5.2. Тогда же были оговорены следующие первичные требования, которым должен удовлетворять AES: это должен быть незасекреченный, открыто опубликованный алгоритм шифрования, бесплатно доступный по всему миру. Спустя некоторое время было уточнено, что AES должен быть блочным шифром, реализующим криптографическую процедуру с симметричным ключом, причем алгоритм (как минимум) должен поддерживать 128-битную длину шифруемого блока текста и длины ключей 128, 192 и 256 бит.

В 1998 г. были отобраны 15 алгоритмов-кандидатов, которые продолжили дальнейшую борьбу. Из них во второй раунд вышли следующие 5 алгоритмов:

• MARS - предложен фирмой IBM (США);

• RC6 - предложен RSA Laboratories (США), компанией, основанной разработчиками самого известного алгоритма шифрования с открытым ключом, и являющийся развитием широко применяемого алгоритма RC5;

• Rijndael - предложен бельгийскими криптоаналитиками Джоаном Дайеменом (Joan Daemen) и Винсентом Риджеменом (Vincent Rijmen);

• Serpent - предложен международной командой видных криптоаналитиков Россом Андерсоном (Ross Anderson, Великобритания), Эли Бихамом (Eli Biham, Израиль) и Ларсом Кнудсеном (Lars Knudsen, Норвегия);

• TwoFish - предложен группой американских криптоаналитиков под руководством президента компании Counterpane Systems Брюса Шнайера (Bruce Schneier), автора известного алгоритма BlowFish.

Предполагается, что обсуждение основных достоинств и недостатков этих алгоритмов будет вестись до 15 мая 2000 года, после чего NIST предложит стандарт AES (с одним или несколькими финалистами) в качестве федерального стандарта (FIPS). Ожидается, что он будет введен в действие к лету 2001 года.

7. Асимметричные Системы с открытым ключом

7.1 Математические основы шифрования с открытым ключом

Центральным понятием криптографии с открытым ключом является понятие “односторонней функции”.

Односторонней называется функция F: X  Y, обладающая двумя свойствами:

1. существует полиномиальный алгоритм вычисления значений F(x);

2. не существует полиномиального алгоритма инвертирования функции F (т.е. решения уравнения F(x) = y относительно x.

Вопрос о существовании односторонних функций пока открыт. Частным случаем односторонней функции является так называемая “функция с секретом” (функция с ловушкой).

Функцией с секретом K называется функция F_K: X  Y, зависящая от параметра K и обладающая тремя свойствами:

1. при любом K существует полиномиальный алгоритм вычисления значений F_K (x);

2. при неизвестном K не существует полиномиального алгоритма инвертирования F_K (x);

3. при известном K существует полиномиальный алгоритм инвертирования F_K (x).

Про существование функций с секретом можно сказать то же самое, что сказано про односторонние функции. Для практических целей криптографии было построено несколько функций, которые могут оказаться функциями с секретом. Для них свойство б) пока строго не доказано, но считается, что задача инвертирования эквивалентна некоторой давно изучаемой трудной математической задаче. Наиболее известной и популярной из них является теоретико-числовая функция, на основе которой построен алгоритм RSA.

Применение функций с секретом в криптографии позволяет:

• организовать обмен шифрованными сообщениями с использованием только открытых каналов связи, т.е. отказаться от секретных каналов связи для предварительного обмена ключами;

• включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;

• решать новые криптографический задачи, отличные от шифрования (цифровая подпись и др.).

Для реализации обмена шифрованными сообщениями используется следующая схема:

Пользователь А, который хочет получать шифрованные сообщения, должен выбрать какую-нибудь функцию F_K с секретом K. Он сообщает всем заинтересованным (например, публикует) описание функции F_K в качестве своего алгоритма шифрования. Но при этом значение секрета K он никому не сообщает и держит в секрете. Если теперь пользователь В хочет послать пользователю А защищаемую информацию x  X, то он вычисляет y = F_K (x) и посылает y по открытому каналу пользователю А. Поскольку А для своего секрета K умеет инвертировать , то он вычисляет x по полученному y. Никто другой не знает K и поэтому в силу свойства б) функции с секретом не сможет за полиномиальное время по известному шифрованному сообщению F_K (x) вычислить защищаемую информацию x.

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

Несмотря на то, что системы с открытым ключом хорошо зарекомендовали себя на практике, представляется маловероятным, что их когда-либо станут использовать для шифрования секретной информации на государственном уровне. Дело в том, что существует метод, развиваемый американским математиком Петером Шором (Peter Schoor), позволяющий разложить сколь угодно большие величины на составляющие, что является необходимой предпосылкой для вскрытия существующих сегодня шифров с открытым ключом, например генерируемых на основе RSA-алгоритмов 10.4.3.

Единственная загвоздка, позволяющая пока еще спать спокойно тем, кто несет ответственность за миллиардные денежные потоки, - для реализации разработок Петера Шора неприменимы даже супермощные современные компьютеры. Только принципиально новая генерация ЭВМ, так называемые квантовые компьютеры, воспринимающие последовательность нулей и единиц не по принципу “есть ток – нет тока”, а “квантовое состояние 1 – квантовое состояние 2” (т.е. различающих энергетические уровни ионов и электронов и поляризацию фотонов), сможет справиться с колоссальным объемом вычислений, порождаемых алгоритмом декодирования Шора. Кстати, эти алгоритмы пригодны только для вскрытия шифров – с их генерированием они не имеют ничего общего.

Хотя появление квантовых компьютеров – дело относительно отдаленного будущего (сам П.Шор отводит на их разработку от 10 до 50 лет), резонанс, вызванный работами американца, уже привел к беспокойству в экономике, что соответственно дало импульсы развития в “лагере брони”. “Шифровальщики уже трудятся над совершенствованием методик кодирования”, - констатирует отец “виртуальной отмычки” получивший за свой вклад престижную премию на Международном математическом конгрессе, прошедшем в Берлине во второй половине августа 1999 года.