Алгоритм AES (Rijndael)
В 1997 году, когда низвержение DES стало очевидным, NIST объявил о конкурсе на поиск преемника DES – улучшенного стандарта шифрования (Advanced Encryption Standard – AES). Многие криптографы с мировым именем представили на рассмотрение свои алгоритмы. Среди требований к алгоритму AES были следующие:
• подобно DES, он должен быть симметричным блочным алгоритмом с секретным ключом;
• его криптостойкость и скорость зашифрования и расширования данных должны быть выше, чем у алгоритма 3-DES;
• время жизни нового стандарта должно быть, по крайней мере, 20–30 лет;
• он должен поддерживать ключи длиной 128, 192 и 256 бит;
• он должен удовлетворять условиям свободного распространения, не должен быть запатентован, и на него нельзя предъявить права собственности.
В течение нескольких месяцев NIST рассмотрел 15 различных заявок, шесть из которых были отклонены почти немедленно как не удовлетворяющие предъявляемым требованиям. К 1999 году NIST сузил число претендентов до пяти финалистов: MARS, RC6, Rijndael, Serpent и Twofish.
Отбор кандидатов занял еще один год, потому что нужно было тщательно протестировать каждого кандидата и удостовериться, что он удовлетворяет требованиям работы при различных условиях эксплуатации. Ведь AES должен был работать везде, начиная с портативных кредитных карточек с микропроцессором и обычных 32-разрядных настольных компьютеров и до 64-разрядных высококачественных оптимизированных компьютеров. Поскольку все из финалистов удовлетворяли требованиям безопасности, то решающим критерием выбора стала скорость обработки данных и удобство реализации алгоритма (которое в этом случае предполагало объем используемой памяти).
В конечном счете в октябре 2000 года победителем был объявлен алгоритм Rijndael («рейн-долл»). Прежде всего по причине высокой производительности программной или аппаратной реализации и невысоких требований к памяти. Алгоритм Rijndael был предложен бельгийскими криптографами докторами Джоаном Дименом (Joan Daemen) и Винсентом Риджменом (Vincent Rijmen). Ожидается, что он стоек к перспективным атакам будущего.
Как работает AES/Rijndael? Вместо использования циклов Фейстеля в каждом раунде, как это сделано в DES, в Rijndael, как и в IDEA, используются повторяющиеся раунды (алгоритм IDEA обсуждается в следующей секции). Данные разбиваются на блоки по 128 бит, которые группируются в 4 группы по 4 байта в каждом. Число раундов алгоритма зависит от размеров ключа. При ключе длиной 128 бит выполняется 9 раундов, 192 бит – 11 раундов и 256 бит – 13 раундов. Каждый раунд состоит из шага побитовой подстановки в S-блоках порции данных и следующим за ним шагом псевдоперестановки, в котором биты перетасовываются между группами. Затем каждая группа перемножается как матрица и результат складывается с подключом этого раунда.