Коллектив авторов - Защита от хакеров корпоративных сетей
Алгоритм 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-блоках порции данных и следующим за ним шагом псевдоперестановки, в котором биты перетасовываются между группами. Затем каждая группа перемножается как матрица и результат складывается с подключом этого раунда.
Насколько AES быстрее, чем 3-DES? Ответить на это вопрос трудно, потому что скорость шифрования изменяется в широких пределах в зависимости от типа используемого процессора и от того, на каких средствах выполняется шифрование: на программных или аппаратных, специально для этого разработанных. Но при одинаковой реализации AES всегда быстрее алгоритма 3-DES. Тестирование, выполненное Брайоном Гладманом (Brian Gladman), показало, что на Pentium Pro 200 с оптимизированным кодом на языке C AES (Rijndael) может зашифровать и расшифровать сообщения со средней скоростью 70.2 Mbps, в то время как скорость работы DES при соблюдении этих же условий – только 28 M6/c Другие результаты исследователя можно найти по адресу fp.gladman.plus.com/cryptography_technology/aes.
Алгоритм IDEA
IDEA – Европейский коллега алгоритма DES. Существование алгоритма IDEA доказывает, что американцы не монополисты качественной криптографии. Первоначальное название алгоритма IDEA – предлагаемый стандарт шифрования (Proposed Encryption Standard — PES). В 1990 году он был предложен криптографами Джеймсом Мэсси (James Massey) и Кседжой Лей (Xuejia Lai) как итог совместного научно-исследовательского проекта Ascom и Швейцарского федерального института технологии. Прежде чем алгоритм PES получил широкое распространение, в 1991 году авторы усилили его против атак на основе использования дифференциального криптоанализа и изменили название алгоритма на улучшенный предлагаемый стандарт шифрования (Improved PES – IPES). Наконец, в 1992 году он стал называться международным алгоритмом шифрования данных (International Data Encryption Algorithm – IDEA).
Алгоритм IDEA появился не только позднее DES. Он также значительно быстрее и безопаснее DES. Скорость работы IDEA возросла благодаря более простым операциям (операции исключающего ИЛИ – XOR, логического дополнения и умножения), используемым в каждом раунде, по сравнению с операциями цикла Фейстеля в DES. Используемые в IDEA операции проще реализовать программным способом, чем выполнить подстановку и перестановку в DES.
Алгоритм IDEA оперирует с 64-битовыми блоками открытого текста, и его ключ имеет длину 128 бит. Процесс зашифрования / расшифрования состоит из восьми раундов, в каждом из которых используется шесть 16-битных подключей. Алгоритм IDEA запатентован в США и Европе, но разрешено его свободное некоммерческое использование.
Асимметричные алгоритмы
В отличие от симметричных алгоритмов асимметричные используют два ключа – открытый и секретный (возможны алгоритмы и с большим количеством ключей). Вместо используемых в симметричных алгоритмах операций подстановки и перемешивания асимметричные алгоритмы основаны на использовании математических проблем больших целых чисел. Для большинства из них легко решается прямая задача, но сложно получить решение обратной задачи. Например, легко решить прямую задачу – перемножить два числа, но обратная задача – найти делители большого целого числа, особенно если оно состоит из сотни десятичных цифр, – практически неразрешима. Вообще говоря, безопасность асимметричных алгоритмов зависит не от возможностей атак «грубой силы», а от способности решить сложную обратную задачу и прогресса в математике, который сможет предложить новые эффективные методы их решения. В этой секции будут рассмотрены алгоритмы RSA и Диффи-Хеллмана (Diffie-Hellman) – два наиболее популярных алгоритма в настоящее время.
Алгоритм Диффи-Хеллмана
В 1976 году после публичной критики алгоритма DES и указания на сложность обработки секретных ключей Уитфилд Диффи (Whitfield Diffie) и Мартин Хеллман (Martin Hellman) опубликовали свой алгоритм обмена ключами. Это была первая публикация на тему криптографии с открытым ключом и, возможно, самый большой шаг вперед в области криптографии, сделанный когда-либо. Из-за невысокого быстродействия, свойственного асимметричным алгоритмам, алгоритм Диффи-Хеллмана не предназначен для шифрования данных. Он был ориентирован на передачу секретных ключей DES или других подобных алгоритмов через небезопасную среду. В большинстве случаев алгоритм Диффи-Хеллмана (Diffie-Hellman) не используется для шифрования сообщений, потому что он, в зависимости от реализации, от 10 до 1000 раз медленнее алгоритма DES.
До алгоритма Диффи-Хеллмана (Diffie-Hellman) было сложно совместно использовать зашифрованные данные из-за проблем хранения ключей и передачи информации. Подробнее об этом будет еще сказано. В большинстве случаев передача информации по каналам связи небезопасна, потому что сообщение может пройти десятки систем, прежде чем оно достигнет потенциального адресата, и нет никаких гарантий, что по пути никто не сможет взломать секретный ключ. Уитфилд Диффи (Whitfield Diffie) и Мартин Хеллман (Martin Hellman) предложили зашифровывать секретный ключ DES по алгоритму Диффи-Хеллмана на передающей стороне и пересылать его вместе с сообщением, зашифрованным с использованием DES. Тогда на другом конце его сможет расшифровать только получатель сообщения.
На практике обмен ключами по алгоритму Диффи-Хеллмана происходит по следующей схеме.
1. Два участника обмена договариваются о двух числах. Один выбирает большое простое число, а другой – целое число, меньшее числа первого участника. Переговоры они могут вести открыто, и это никак не отразится на безопасности.
2. Каждый из двух участников, независимо друг от друга, генерит другое число, которое они будут хранить в тайне. Эти числа выполняют роль секретного ключа. Далее в вычислениях используются секретный ключ и два предыдущих целых числа. Результат вычислений посылается участнику обмена, и он играет роль открытого ключа.
3. Участники обмена обмениваются открытыми ключами. Далее они, используя собственный секретный ключ и открытый ключ партнера, конфиденциально вычисляют ключ сессии. Каждый партер вычисляет один и тот же ключ сессии.
4. Ключ сессии может использоваться как секретный ключ для другого алгоритма шифрования, например DES. Никакое третье лицо, контролирующее обмен, не сможет вычислить ключ сессии, не зная один из секретных ключей.
Самое сложное в алгоритме Диффи-Хеллмана обмена ключами – это понять, что в нем фактически два различных независимых цикла шифрования. Алгоритм Диффи-Хеллмана применяется для обработки небольших сообщений от отправителя получателю. Но в этом маленьком сообщении передается секретный ключ для расшифровки большого сообщения.
