От телетайпного ключа Вернама к краху DES и конкурсу AES
В годы Первой мировой войны массовое внедрение телетайпов потребовало быстрой автоматической криптографии, защищённой от перехвата. В 1917 году инженер AT&T Гилберт Вернам изобрёл релейное устройство (патент США № 1 310 719 от 22 июля 1919 г.), побитово складывавшее пятибитный код Бодо с ключевой перфолентой. Исходная замкнутая петля ленты повторялась и поддавалась взлому, пока офицер Корпуса связи США Джозеф Моборн не предложил делать ключ полностью случайным и однократным — так появился «одноразовый блокнот» (One-Time Pad). В секретном отчёте 1945 года, опубликованном в октябре 1949 года в Bell System Technical Journal под названием «Теория связи в секретных системах», математик Bell Labs Клод Шеннон доказал абсолютную секретность шифра Вернама и сформулировал принципы конфузии и диффузии для практических шифров.
Однако шифр Вернама проиграл в гражданской экономике: необходимость заранее доставить безопасный ключ длиной с само сообщение ограничила его дипломатией, разведкой и горячей линией Москва — Вашингтон (причём повторное использование одноразовых лент СССР в 1940-х позволило американскому проекту «Венона» прочесть часть переписки). Массовой банковской и компьютерной индустрии требовался короткий ключ. Утверждённый в 1977 году 56-битный стандарт DES к концу 1990-х безнадёжно устарел (в 1998 году машина EFF Deep Crack перебрала ключ DES за 56 часов), а закрытые проекты спецслужб вроде Skipjack и чипа Clipper бизнес отверг в разгар «криптовойн» из-за экспортных запретов и подозрений во встроенных лазейках. Тогда 2 января 1997 года институт NIST объявил открытый мировой конкурс. Из 15 претендентов в финал вышли пять (MARS, RC6, Rijndael, Serpent, Twofish). 2 октября 2000 года победил бельгийский шифр Rijndael Йоана Даймена и Винсента Рэймена, утверждённый 26 ноября 2001 года как федеральный стандарт FIPS 197 (AES) и вступивший в силу 26 мая 2002 года.
Математика XOR и устройство SP-сети алгоритма AES
Шифр Вернама побитово складывает открытый текст с истинно случайным одноразовым ключом по модулю 2 (операция XOR, ⊕): Ci = Pi ⊕ Ki. Пока ключ случаен, непредсказуем и не повторяется, любая осмысленная расшифровка той же длины равновероятна, и перехват шифртекста не даёт противнику ни бита информации.
AES решает противоположную задачу: с помощью короткого ключа (128, 192 или 256 бит) превратить 128-битный блок данных в непроницаемую нелинейную перестановку за 10, 12 или 14 раундов. Отказавшись от сети Фейстеля (на которой строился DES), Даймен и Рэймен применили подстановочно-перестановочную сеть (SP-сеть) над байтовой матрицей состояния 4×4. Каждый раунд объединяет четыре операции: нелинейную замену байтов SubBytes через таблицу S-box (вычисление обратного элемента в конечном поле Галуа GF(28) по модулю полинома z8 + z4 + z3 + z + 1 с аффинным преобразованием), циклический сдвиг строк ShiftRows, линейное перемешивание столбцов MixColumns (MDS-матрица в GF(28)) и наложение раундового ключа AddRoundKey из процедуры расширения ключа. Оптимизация таблицами поиска дала Rijndael лидерство по скорости от 8-битных смарт-карт до 64-битных серверов.
Победа открытой криптографии и защита глобальной инфраструктуры
Победа бельгийского открытого алгоритма разрушила монополию закрытых государственных шифров. В июне 2003 года АНБ США впервые в истории допустило публичный алгоритм для защиты государственной тайны — уровень SECRET (128 бит) и TOP SECRET (192 и 256 бит; современные требования предписывают 256 бит), а обязательная сертификация модулей по программе NIST/CSEC CMVP (FIPS 140-2) сделала совместимость с AES условием госзакупок США и Канады. Свободный от патентных отчислений стандарт (также ISO/IEC 18033-3) стал рабочей основой защищённого веба HTTPS/TLS, сетей Wi-Fi (WPA2 и WPA3), корпоративных VPN, шифрования дисков (BitLocker, FileVault, dm-crypt) и процессинга банковских карт.
В 2005 году Дэниел Бернштейн и группа Ади Шамира продемонстрировали практические атаки по сторонним каналам (кеш-тайминг-атаки на OpenSSL и dm-crypt позволяли восстановить ключ за 800 операций шифрования). Ответом индустрии стало аппаратное ускорение: с 2010–2011 годов корпорации Intel (Arrandale, Sandy Bridge) и AMD (Bulldozer) встроили в процессоры инструкции AES-NI. Это снизило затраты с 18 до 1,3 такта на байт (гигабайты в секунду) и полностью закрыло тайминг-утечки на уровне кремния.
Дискуссии о криптостойкости и испытание квантовой эпохой
Лаконичная алгебра AES в GF(28) привлекла пристальное внимание криптоаналитиков. В 2002 году Н. Куртуа и Й. Пепшик предложили теоретическую XSL-атаку на основе разреженных уравнений. Брюс Шнайер и Нильс Фергюсон выражали осторожный скепсис к простой алгебраической структуре шифра, но Винсент Рэймен назвал XSL-атаку «лишь мечтой», а дальнейший анализ подтвердил её несостоятельность из-за переоценки числа независимых уравнений. Единственная атака на полный AES-128 быстрее перебора — метод биклик (А. Богданов, Д. Ховратович, К. Рехбергер, 2011; улучшена в 2015 г.) — снижает сложность лишь вчетверо, до 2126 операций, что физически неосуществимо.
На пороге квантовой эпохи асимметричные алгоритмы RSA и эллиптические кривые уязвимы для алгоритма Шора, тогда как квантовый поиск Гровера теоретически сокращает эффективную длину симметричного ключа лишь вдвое и плохо распараллеливается. Поэтому AES-256 сохраняет статус квантово-устойчивого мирового стандарта на десятилетия вперёд, сосуществуя с потоковым ChaCha20 и российским ГОСТ Р 34.12-2015 («Кузнечик»).
