В колонках играет - QueenКриптография: основные методы построения криптоалгоритмов
Базовые определения и принципы криптографии
Прежде всего, мне хотелось бы ввести несколько определений, которые будут использоваться в данной статье. Открытым текстом (plaintext) называются исходные данные, которые подлежат шифрованию, шифротекстом (ciphertext) называются зашифрованные данные. Шифрованием или криптографическим преобразованием называется процедура, отображающая открытый текст в шифротекст, и, соответственно, дешифрованием или обратным криптографическим преобразованием называют процесс расшифровки шифротекста в открытый текст. Для шифрования/дешифрования текста в одноключевых (симметричных) системах необходим так называемый секретный ключ (secret key), который должен быть известен только тем людям, которые имеют право доступа к открытому тексту, и не должен оказаться в руках злоумышленника. В некоторых алгоритмах используется так называемый открытый ключ (public key), который может (и должен) быть известен всем. Он необходим для двухключевых (или ассиметричных) криптоалгоритмов, в которых текст, зашифрованный с помощью открытого ключа, можно восстановить только с помощью секретного ключа.
Криптостойкостью или прочностью криптоалгоритма называют его устойчивость к разнообразным атакам, которых существует очень много (линейный и дифференциальный криптоанализ, различные атаки, базирующиеся на известных криптоаналитику открытых текстах и/или шифротекстах и прямой перебор всевозможных ключей (лобовая атака, brute-force attack)). Цель любой атаки – заполучить секретный ключ. Атаки на основе дифференциального анализа осуществляются на основе изучения несходства шифротекстов, получаемых шифрованием открытых текстов с небольшими различиями (аналог дифференциала), путем пропускания их через шифр с одним и тем же секретным ключом. Линейный анализ использует так называемые линейные приближения. Линейное приближение – это бит, с определенной вероятностью истинности являющийся результатом сложения по модулю 2 (XOR) некоторых битов ключа. Метод получения таких приближений состоит в XOR-сложении определенных бит открытого текста и соответствующих бит шифротекста. Результат применения операции XOR от получившихся результатов дает некий бит, называемый линейным приближением. Атаки, основанные на прямом переборе всего множества ключей, точно могут гарантировать нахождение нужного ключа, но осуществить их для больших ключей за разумное время должно быть невозможно. Часто бывает невозможно осуществить другие, теоретически верные атаки, на порядки менее трудоемкие, чем лобовая, но не только из-за недостаточной мощности вычислительных средств, а чаще из-за большого, а то и огромного количества памяти, нужной для хранения промежуточных результатов (срабатывает золотое правило программирования).
Считается, что криптоалгоритм обладает идеальной прочностью, если не существует способа получить секретный ключ за меньшее время, чем требуется для лобовой атаки. (Доказать это теоретически трудно, а практически невозможно – вдруг найдется более быстрый способ, поэтому подчас бывает намного легче опровергнуть надежность алгоритма, чем ее доказать.) При этом, как правило, увеличение длины ключа ведет за собой не меньше, чем экспоненциальное увеличение времени полного перебора (но не забывайте о законах, ограничивающих использование определенных криптосистем с длинными ключами). Но независимо от длины используемого ключа, у некоторых алгоритмов есть слабые ключи, для получения которых не обязательно делать полный перебор, а, например, достаточно иметь несколько пар “открытый текст шифротекст”.
Некоторые обозначения
Договоримся, что в формулах, приводимых в этой статье, будут использоваться следующие обозначения:
· k – ключ (key);
· Ek – процедура шифрования по ключу k (encrypt);
· Dk – процедура дешифрования по ключу k (decrypt);
· – побитовая операция сложения по модулю 2 (т.е. обычный XOR или побитовое исключающее ИЛИ);
· (mod ) – такая конструкция, стоящая в конце формулы, означает, что все операции в данной формуле выполняются по модулю .
Общие принципы
Основная схема, для которой используют криптоалгоритмы, выглядит так: есть так называемый открытый канал связи (например, Интернет или локальная сеть, где каждый пакет данных может быть прочитан посторонним человеком), по которому необходимо передать или обменяться конфиденциальными сообщениями между людьми A и B. Этот канал связи может прослушиваться неким злоумышленником C, который может перехватить любое сообщение (пассивный перехват) и даже подменить своим (активный перехват)! В криптографической литературе вошло в традицию называть этих людей именами по первым буквам: Алисой, Бобом и Кларком (Alice, Bob, Clark). В такой схеме сообщение перед отправкой, например, Алисой, шифруется при помощи
Читать далее...