Криптографические основы

План

• Предисловие
• Базовая терминология
• Основные алгоритмы шифрования
• Цифровые подписи
• Криптографические хэш-функции
• Криптографические генераторы случайных чисел
• Обеспечиваемая шифром степень защиты
• Криптоанализ и атаки на криптосистемы

Предисловие

Слово шифрование по-разному понимается людьми. Дети играют в игрушечные шифры и секретные языки. Однако это не имеет никакого отношения к настоящей криптографии. У настоящей криптографии (strong cryptography) должен быть соответствующий уровень секретности. Она должна надежно защищать критическую информацию от расшифровки крупными организациями – такими как мафия, транснациональные корпорации и крупные государства. Настоящая криптография в прошлом применялась лишь в военных целях. Но в настоящее время, с становлением информационного общества, она становится важнейшим инструментом для обеспечения конфиденциальности.

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

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

Основные термины

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

В терминах криптографии исходное послание называют открытым текстом (plaintext или cleartext). Шифрованием (encryption) называют изменение исходного текста с целью скрыть его содержание от прочих. Зашифрованное сообщение называют шифротекстом (ciphertext). Дешифровка (decryption) – это процесс, при котором из шифротекста осуществляется извлечение открытого текста. Как правило, в процессе шифровки и дешифровки используется некий ключ (key) и алгоритм обеспечивает успешное дешифрование только лишь при наличии этого ключа.

Под криптографией понимается наука об обеспечении секретности сообщения. Криптография включает все практические стороны секретного обмена сообщениями. Сюда входят электронные деньги, цифровые подписи, аутенфикация и многое другое. Криптоанализ представляет из себя науку о том, как вскрыть шифрованное сообщение, то есть как, не зная ключа, достать открытый текст. Криптография – предмет занятия криптографов, а криптоанализ – поле деятельности криптоаналитиков.

Раздел математики, изучающий математические основы криптографических методов называется криптологией.

Базовые алгоритмы шифрования

Шифром (cipher) называют метод шифровки или дешифровки. Некоторые алгоритмы шифрования основаны на секретности самого метода (алгоритма) шифрования. Теперь такие методы не имеют практического значения и интересны лишь с исторической точки зрения. Для управления шифровкой и дешифровкой во всех современных алгоритмах используется ключ. Дешифрование сообщения может быть успешным только в том случае, если известен ключ. В большинстве алгоритмов ключи, используемые для дешифровки и шифрования совпадают, однако не исключена возможность несовпадения этих двух ключей.

Можно выделить два класса алгоритмов, в которых используется ключ: алгоритмы с секретным ключом (т.е. симметричные) и алгоритмы с открытым ключом (т.е. асимметричные). Эти два класса отличаются тем, что одни (симметричные алгоритмы) используют один и тот же ключ для шифрования и для дешифрования (или же ключ для дешифровки просто вычисляется по ключу шифровки), а другие (асимметричные алгоритмы) используют разные ключи, и ключ для дешифровки невозможно вычислить по ключу шифровки.

Асимметричные шифры (или алгоритмы с открытым ключом, или – в более общем плане – криптография с открытым ключом) допускают всеобщую доступность открытого ключа (он может быть опубликован в газете). Любой может зашифровать таким образом сообщение. Однако расшифровать это сообщение сможет только тот, кто владеет ключом дешифровки. Ключ для шифрования называется открытым ключом, а ключ для дешифрования --- закрытым ключом или секретным ключом.

Симметричные алгоритмы делят на два вида: блочные шифры и потоковые шифры. С помощью потоковых осуществляется побитовая шифровка информации, а блочные используют при работе определенный набор бит данных (типовой размер блока составляет 64 бита) и шифруют этот набор единым целым. Основные сведения по этому вопросу приведены в статье об алгоритмах.

Современные алгоритмы шифровки/дешифровки невозможно проводить вручную ввиду их большой сложности. Настоящие разработанные криптографические алгоритмы используются только с помощью компьютеров или специальных аппаратных устройств. В большинстве приложений криптография осуществляется программным обеспечением и разработано большое число доступных криптографических пакетов.

Заметим, что асимметричные алгоритмы работают медленнее, чем симметричные. Оба типа алгоритмов часто используются вместе на практике: алгоритм с открытым ключом применяется для того, чтобы сгенерированный секретный ключ был случайным образом передан, а затем использован для дешифровки сообщения.

Большое число качественных криптографических алгоритмов являются широко доступными – в библиотеке, патентном бюро, книжном магазине или в Интернет. Одни из самых известных симметричных алгоритмов – это IDEA и DES. Что касается асимметричных алгоритмов, то здесь RSA вне конкуренции. В списке литературы приведен перечень хороших учебников по криптографии и смежным вопросам.

Цифровые подписи

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

Цифровые подписи можно использовать для удостоверения (сертификации – to certify) того, что документ принадлежит определенному лицу. Это делается так: открытый ключ и информация о том, кому он принадлежит, подписываются стороной, которой доверяем. При этом доверять подписывающей стороне мы можем на основании того, что ее ключ был подписан третьей стороной. Таким образом возникает иерархия доверия. Очевидно, что некоторый ключ должен быть основой иерархии (то есть ему мы доверяем не потому, что он кем-то подписан, а потому, что мы верим, что ему точно можно доверять). В централизованной инфраструктуре ключей имеется очень небольшое количество корневых ключей сети (например, облеченные полномочиями государственные агентства; их также называют сертификационными агентствами – certification authorities). В распределенной инфраструктуре не нужно иметь универсальные для всех корневые ключи, и каждая из сторон может доверять своему набору корневых ключей (скажем своему собственному ключу и ключам, ею подписанным). Эта концепция носит название сети доверия (web of trust) и реализована, например, в PGP.

Цифровые подписи также применяются для подтверждения, что сообщение пришло действительно от данного отправителя (притом, что только у отправителя есть секретный ключ, соответствующий его открытому ключу). Кроме того, подписи используются для проставления штампа времени (timestamp) на документах. Сторона, которой мы доверяем, подписывает документ со штампом времени с помощью своего секретного ключа и, таким образом, подтверждает, что документ уже существовал в момент, объявленный в штампе времени.

Создание цифровой подписи документа обычно происходит так: из документа генерируется так называемый дайджест (message digest) и к нему добавляется информация о том, кто подписывает штамп времени, документ и прочее. Далее получившаяся строка зашифровывается секретным ключом подписывающего с использованием того или иного алгоритма. Получившийся зашифрованный набор бит и представляет собой подпись. К подписи обычно прикладывается открытый ключ подписывающего. Получатель сначала решает для себя доверяет ли он тому, что открытый ключ принадлежит именно тому, кому должен принадлежать (с помощью сети доверия или априорного знания), и затем дешифрует подпись с помощью открытого ключа. Если подпись нормально дешифровалась, и ее содержимое соответствует документу (дайджест и др.), то сообщение считается подтвержденным.

Свободно доступны несколько методов проверки и создания цифровых подписей, наиболее известен из них алгоритм RSA.

Криптографические хэш-функции

Криптографические хэш-функции используются обычно для генерации дайджеста сообщения при создании цифровой подписи. Хэш-функции отображают сообщение в имеющее фиксированный размер хэш-значение (hash value) таким образом, что все множество возможных сообщений распределяется равномерно по множеству хэш-значений. При этом криптографическая хэш-функция делает это таким образом, что практически невозможно подогнать документ к заданному хэш-значению.

Криптографические хэш-функции обычно производят значения длиной в 128 и более бит. Это число значительно больше, чем количество собщений, которые когда-либо будут существовать в мире.

Много хороших криптографических хэш-функций доступно бесплатно. Широко известные включают MD5 и SHA.

Криптографические генераторы случайных чисел

Криптографические генераторы случайных чисел производят случайные числа, которые используются в криптографических приложениях, например - для генерации ключей. Обычные генераторы случайных чисел, имеющиеся во многих языках программирования и программных средах, не подходят для нужд криптографии (они создавались с целью получить статистически случайное распределение, криптоаналитики могут предсказать поведение таких случайных генераторов).

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

Когда нет настоящего физического источника шума, приходится пользоваться псевдослучайными числами. Такая ситуация нежелательна, но часто возникает на компьютерах общего назначения. Всегда желательно получить некий шум окружения --- скажем от величины задержек в устройствах, цифры статистики использования ресурсов, сетевой статистики, прерываний от клавиатуры или чего-то иного. Задачей является получить данные, непредсказуемые для внешнего наблюдателя. Для достижения этого случайный пул должен содержать как минимум 128 бит настоящей энтропии.

Криптографические генераторы псевдослучайных чисел обычно используют большой пул (seed-значение), содержащий случайную информацию. Биты генерируется путем выборки из пула с возможным прогоном через криптографическую хэш-функцию, чтобы спрятать содержимое пула от внешнего наблюдателя. Когда требуется новая порция бит, пул перемешивается путем шифровки со случайным ключом (его можно взять из неиспользованной пока части пула) так, чтобы каждый бит пула зависел от каждого другого бита. Новый шум окружения должен добавляться к пулу перед перемешиваниям, дабы сделать предсказание новых значений пула еще более сложным.

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

Несколько примеров криптографических генераторов случайных чисел доступны.

Атаки на криптосистемы и криптоанализ

Наука о дешифровке закодированных сообщений без знания ключей называется криптоанализом. Ниже приведены некоторые из самых важных для разработчиков криптоаналитических подходов, но вообще их имеется большое количество.

• Атака с заданным текстом (chosen-plaintext attack): Задачей нападающего является нахождение ключа, он имеет возможность получить шифрованный документ для любого нужного ему текста, но не знает ключа. Необходимо тщательно следить, используя алгоритмы, подобные RSA , заданный атакующим текст не мог быть зашифрован. Некоторые методы шифрования и, в частности, RSA, очень уязвимы для атак этого типа.
• Атака с использованием таймера (timing attack): Это новый тип атак и он основан на последовательном измерении времен, которые нужно потерять, чтобы выполнить операции возведения в степень по модулю целого числа. По крайней мере ей подвержены такие шифры: Диффи-Хеллман, RSA, а также метод эллиптических кривых. Этот метод подробно рассмотрен в статье Пола Кочера.
• Атака со знанием лишь шифрованного текста (ciphertext-only attack): Это ситуация, когда атакующий не знает ничего о содержании сообщения. Ему приходится работать лишь с самим шифрованным текстом. Так как многие сообщения имеют стандартные заголовки, часто на практике можно сделать правдоподобные предположения о структуре текста. Также часто можно предположить, что некоторый блок информации содержит заданное слово. Даже обычные письма и документы начинаются с легко предсказуемой информации.
• Атака со знанием содержимого шифровки (known-plaintext attack): Задача атакующего заключается в расшифровке части не угаданного сообщения, поскольку он знает или может угадать содержимое всего или части зашифрованного текста. Это можно сделать или путем вычисления ключа шифровки, или избежав это.
• Атака с подставкой (Man-in-the-middle attack): Атака направлена на протокол обмена ключами, а также на обмен шифрованными сообщениями. Идея заключается во внедрении противника на линии обмена сообщениями между двумя сторонами, которые обмениваются ключами для секретной коммуникации. При этом обычно используется шифр Диффи-Хелмана (Diffie-Hellman). Затем противник выдает каждой стороне свои ключи. В результате, каждая из сторон будет иметь разные ключи, каждый из которых известен противнику. Теперь противник будет расшифровывать каждое сообщение своим ключом и затем зашифровывать его с помощью другого ключа перед отправкой адресату. Стороны будут иметь иллюзию секретной переписки, тогда как на самом деле противник читает все сообщения.

Одним из способов предотвратить такой тип атак заключается в том, что стороны при обмене ключами вычисляют криптографическую хэш-функцию значения протокола обмена (или по меньшей мере значения ключей), подписывают ее алгоритмом цифровой подписи и посылают подпись другой стороне. Получатель проверит подпись и то, что значение хэш-функции совпадает с вычисленным значением. Такой метод используется, в частности, в системе Фотурис (Photuris).

Существует много других криптоаналитических подходов и атак. Но наиболее важными для практической разработки систем являются способы, приведенные выше. Для создания своего алгоритма шифрования необходимо понимать данные вопросы значительно глубже. Одно из мест, где можно начать систематическое изучение информации – это замечательная книга Брюса Шнейера "Прикладная криптография" (Bruce Schneier, Applied Cryptography).

Степень защиты, обеспечиваемая шифром

Для реализации криптографических систем не требуется очень больших усилий. Единственное, что требуется – это базовые знания и аккуратность. Разработчик обязан перекрыть все возможности для вскрытия системы. Все механизмы, которые могут использоваться для взлома системы надо задокументировать и довести до сведения конечных пользователей. Хорошие криптографические системы создаются таким образом, чтобы сделать их вскрытие как можно более трудным делом. Можно построить системы, которые на практике вскрыть невозможно (хотя этот факт доказать обычно нельзя).

Теоретически, любой шифровальный алгоритм с использованием ключа может быть вскрыт методом перебора всех значений ключа. Если ключ подбирается методом грубой силы (brute force), требуемая мощность компьютера растет экспоненциально с увеличением длины ключа. Ключ длиной в 32 бита требует 2³² (около 10⁹) шагов, эту задачу сможет решить любой дилетант на домашнем компьютере. Системы с 40-битным ключом (например, экспортный американский вариант алгоритма RC4) требуют 2⁴⁰ шагов – такие компьютерные мощности имеются в большинстве университетов и даже в небольших компаниях. Системы с 56-битными ключами (DES) требуют для вскрытия заметных усилий, однако могут быть легко вскрыты с помощью специальной аппаратуры. Стоимость такой аппаратуры значительна, но доступна для мафии, крупных компаний и правительств. Ключи длиной 64 бита в настоящий момент, возможно, могут быть вскрыты крупными государствами и уже в ближайшие несколько лет будут доступны для вскрытия преступными организациями, крупными компаниями и небольшими государствами. Ключи длиной 80 бит могут в будущем стать уязвимыми.

Ключи длиной 128 бит в ближайшем будущем скорее всего останутся недоступными для вскрытия методом грубой силы. Можно использовать и более длинные ключи. Однако, длина ключа это еще не все: многие шифры можно вскрыть и не перебирая всех возможных комбинаций. Очень трудно придумать шифр, который нельзя было бы вскрыть другим более эффективным способом. Разработка собственных шифров может стать приятным занятием, но для реальных приложений использовать самодельные шифры не рекомендуется если вы не являетесь экспертом и не уверены на 100 процентов в том, что делаете.

Длины ключей, используемых в криптографии с открытым ключом обычно значительно больше, чем в симметричных алгоритмах. Здесь проблема заключается не в подборе ключа, а в подборе секретного ключа по открытому. В случае RSA проблема эквивалентна разложению на множители большого целого числа, которое является произведением пары неизвестных простых чисел. В случае некоторых других криптосистем, проблема эквивалентна вычислению дискретного логарифма по модулю большого целого числа (такая задача считается примерно аналогичной по трудности задаче разложения на множители). Имеются криптосистемы, которые используют другие проблемы.

Чтобы дать представление о степени сложности вскрытия RSA, скажем, что модули длиной 256 бит легко факторизуются обычными программистами. Ключи в 384 бита могут быть вскрыты исследовательской группой университета или компании. 512-битные ключи находятся в пределах досягаемости крупных государств. Ключи длиной в 768 бит вероятно не будут надежны продолжительное время. Ключи длиной в 1024 бит могут считаться безопасными до тех пор, пока не будет существенного прогресса в алгоритме факторизации; ключи длиной в 2048 большинство считает надежными на десятилетия. Более подробную информацию о длинах ключей RSA можно почерпнуть из статьи Брюса Шнайера.

Следует держаться в стороне от неопубликованных или секретных алгоритмов. Часто разработчик такого алгоритма не уверен в его надежности, или же надежность зависит от секретности самого алгоритма. Вообще говоря, ни один алгоритм, секретность которого зависит от секретности самого алгоритма не является надежным. В частности, имея шифрующую программу, можно нанять программиста, который дизассемблирует ее и восстановит алгоритм методом обратной инженерии. Опыт показывает, что большинство секретных алгоритмов, ставших впоследствии достоянием общественности, оказались удивительно ненадежными.

Степень надежности криптографической системы определяется ее слабейшим звеном. Необходимо учитывать все стороны разработки системы - от выбора алгоритма до политики использования и распространения ключей.

Перевод статьи Tatu Ylonen "Introduction to Cryptography"