Криптографические методы и средства защиты информации

Опубликовано: 14.02.2011 /

Рубрики: IT

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

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

Криптоанализ — данный раздел посвящен исследованию возможности чтения сообщений без знания ключей, т. е. связана непосредственно со взломом шифров. Люди, занимающиеся криптоанализом и исследованием шифров называются криптоаналитиками.

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

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

Криптографическая система — семейство преобразований шифра и совокупность ключей (т.е алгоритм + ключи). Само по себе описание алгоритма не является криптосистемой. Только дополненное схемами распределения и управления ключами оно становится системой. Примеры алгоритмов — описания DES, ГОСТ28.147-89. Дополненые алгоритмами выработки ключей, они превращаются в криптосиситемы. Как правило, описание алгоритма шифрования уже включает в себя все необходимые части.

Современные криптосистемы классифицируют следующим образом:

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

Симметричные криптосистемы (с секретным ключом — secret key systems)- данные криптосистемы построены на основе сохранения в тайне ключа шифрования. Процессы зашифрования и расшифрования используют один и тот же ключ. Секретность ключа является постулатом. Основная проблема при применении симметричных криптосистем для связи заключается в сложности передачи обоим сторонам секретного ключа. Однако данные системы обладают высоким быстродействием. Раскрытие ключа злоумышленником грозит раскрытием только той информации, что была зашифрована на этом ключе. Американский и Российский стандарты шифрования DES и ГОСТ28.147-89, кандидаты на AES — все эти алгоритмы являются представителями симметричных криптосистем.

Асимметричные криптосистемы (системы открытого шифрования — о.ш., с открытым ключом и т.д.- public key systems) — смысл данных криптосистем состоит в том, что для зашифрования и расшифрования используются разные преобразования. Одно из них — зашифрование — является абсолютно открытым для всех. Другое же — расшифрование — остается секретным. Таким образом, любой, кто хочет что-либо зашифровать, пользуется открытым преобразованием. Но расшифровать и прочитать это сможет лишь тот, кто владее секретным преобразованием. В настоящий момент во многих асимметричных криптосистемах вид преобразования определяется ключом. Т.е у пользователя есть два ключа — секретный и открытый. Открытый ключ публикуется в общедоступном месте, и каждый, кто захочет послать сообщение этому пользователю — зашифровывает текст открытым ключом. Расшифровать сможет только упомянутый пользователь с секретным ключом. Таким образом, пропадает проблема передачи секретного ключа (как у симметричных систем). Однако, несмотря на все свои преимущества, эти криптосистемы достаточно трудоемки и медлительны. Стойкость асимметричных криптосистем базируется, в основном, на алгоритмической трудности решить за приемлимое время какую-либо задачу. Если злоумышленнику удастся построить такой алгоритм, то дискредетирована будет вся система и все сообщения, зашифрованые с помощью этой системы. В этом состоит главная опасность асимметричных криптосистем в отличие от симметричных. Примеры — системы о.ш. RSA, система о.ш. Рабина и т.д.

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

Тайнопись

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

Начиная с самых древних времен, человечество обменивалось информацией, отсылая друг другу бумажные письма. В Древнем Великом Новгороде необходимо был сворачивать свои берестяные грамоты словами наружу — только таким образом они могли перевозиться и храниться, в противном случае они разворачивались самопроизвольно из-за изменения уровня влажности. Это было похоже на современные почтовые карточки, в которых текст, как известно, также открыт для чужих взоров.

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

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

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

Шифрова́ние — способ преобразования открытой информации в закрытую и обратно. Применяется для хранения важной информации в ненадёжных источниках или передачи её по незащищённым каналам связи. Согласно ГОСТ 28147-89, шифрование подразделяется на процесс зашифровывания и расшифровывания.

Стеганогра́фия (от греч. στεγανός — скрытый и греч. γράφω — пишу, буквально «тайнопись») — это наука о скрытой передаче информации путём сохранения в тайне самого факта передачи.

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

Основные принципы компьютерной стеганографии и области её применения

К. Шеннон дал нам общую теорию тайнописи, которая является базисом стеганографии как науки. В современной компьютерной стеганографии существует два основных типа файлов: сообщение— файл, который предназначен для скрытия, и контейнер—файл, который может быть использован для скрытия в нем сообщения. При этом контейнеры бывают двух типов. Контейнер—оригинал (или “Пустой” контейнер) — это контейнер, который не содержит скрытой информации. Контейнер—результат (или “Заполненный” контейнер) — это контейнер, который содержит скрытую информацию. Под ключом понимается секретный элемент, который определяет порядок занесения сообщения в контейнер.

Основными положениями современной компьютерной стеганографии являются следующие:

1. Методы скрытия должны обеспечивать аутентичность и целостность файла.

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

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

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

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

1. Защита конфиденциальной информации от несанкционированного доступа;
2. Преодоление систем мониторинга и управления сетевыми ресурсами;
3. Камуфлирования программного обеспечения;
4. Защита авторского права на некоторые виды интеллектуальной собственности.

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

Типы криптостойких систем шифрования

Абсолютно стойкие системы

Доказательство существования абсолютно стойких алгоритмов шифрования было выполнено Клодом Шенноном и опубликовано в работе «Теория связи в секретных системах».^[1] Там же определены требования к такого рода системам:

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

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

Некоторыми аналитиками утверждается, что Шифр Вернама является одновременно абсолютно криптографически стойким и к тому же единственным^{[источник не указан 360 дней]} шифром, который удовлетворяет этому условию.

Достаточно стойкие системы

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

вычислительная сложность полного перебора
известные на данный момент слабости (уязвимости) и их влияние на вычислительную сложность.

В каждом конкретном случае могут существовать дополнительные критерии оценки стойкости.

Сложность алгоритма позволяет оценить, насколько быстро растет его трудоёмкость с увеличением объема входных данных. Под трудоемкостью понимается количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма. Обычно оценка сложности алгоритма представляется в виде O(f(N)), где O – функция сложности, а N – число обрабатываемых наблюдений или примеров. Наименее затратными являются алгоритмы, для которых функция сложности имеет вид f(N) = C и f(N) = C*N, где С – константа. В первом случае вычислительные затраты не зависят от количества обрабатываемых данных, а во втором – линейно возрастают. Самыми затратными являются алгоритмы, сложность которых имеет степенную и факториальную зависимости от числа обрабатываемых наблюдений.

Длина ключа

Количество информации в ключе, как правило, измеряется в битах.

Для современных симметричных алгоритмов (AES, CAST5, IDEA, Blowfish, Twofish) основной характеристикой криптостойкости является длина ключа. Шифрование с ключами длиной 128 бит и выше считается сильным, так как для расшифровки информации без ключа требуются годы работы мощных суперкомпьютеров. Для асимметричных алгоритмов, основанных на проблемах теории чисел (проблема факторизации — RSA, проблема дискретного логарифма — Elgamal) в силу их особенностей минимальная надёжная длина ключа в настоящее время — 1024 бит. Для асимметричных алгоритмов, основанных на использовании теории эллиптических кривых (ECDSA, ГОСТ Р 34.10-2001, ДСТУ 4145-2002), минимальной надёжной длиной ключа считается 163 бит, но рекомендуются длины от 191 бит и выше.

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

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

Порядок использования систем с симметричными ключами:

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

Доступными сегодня средствами, в которых используется симметричная методология, являются:

Kerberos, который был разработан для аутентификации доступа к ресурсам в сети, а не для верификации данных. Он использует центральную базу данных, в которой хранятся копии секретных ключей всех пользователей.
Сети банкоматов (ATM Banking Networks). Эти системы являются оригинальными разработками владеющих ими банков и не продаются. В них также используются симметричные методологии.

Сравнение с асимметричными криптосистемами

Достоинства

скорость (по данным Applied Cryptography — на 3 порядка выше)
простота реализации (за счёт более простых операций)
меньшая требуемая длина ключа для сопоставимой стойкости
изученность (за счёт большего возраста)

Недостатки

сложность управления ключами в большой сети. Означает квадратичное возрастание числа пар ключей, которые надо генерировать, передавать, хранить и уничтожать в сети. Для сети в 10 абонентов требуется 45 ключей, для 100 уже 4950, для 1000 — 499500 и т. д.
сложность обмена ключами. Для применения необходимо решить проблему надёжной передачи ключей каждому абоненту, так как нужен секретный канал для передачи каждого ключа обеим сторонам.

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

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

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

Все асимметричные криптосистемы являются объектом атак путем прямого перебора ключей, и поэтому в них должны использоваться гораздо более длинные ключи, чем те, которые используются в симметричных криптосистемах, для обеспечения эквивалентного уровня защиты. Это сразу же сказывается на вычислительных ресурсах, требуемых для шифрования, хотя алгоритмы шифрования на эллиптических кривых могут смягчить эту проблему. Брюс Шнейер в книге «Прикладная криптография: протоколы, алгоритмы и исходный текст на C» приводит следующие данные об эквивалентных длинах ключей.

Длина симметричного ключа	Длина открытого ключа
56 бит	384 бит
64 бита	512 бит
80 бит	768 бит
112 бит	1792 бита
128 бит	2304 бита

Для того чтобы избежать низкой скорости алгоритмов асимметричного шифрования, генерируется временный симметричный ключ для каждого сообщения и только он шифруется асимметричными алгоритмами. Само сообщение шифруется с использованием этого временного сеансового ключа и алгоритма шифрования/расшифровки, описанного в пункте 2.1.1.1. Затем этот сеансовый ключ шифруется с помощью открытого асимметричного ключа получателя и асимметричного алгоритма шифрования. После этого этот зашифрованный сеансовый ключ вместе с зашифрованным сообщением передается получателю. Получатель использует тот же самый асимметричный алгоритм шифрования и свой секретный ключ для расшифровки сеансового ключа, а полученный сеансовый ключ используется для расшифровки самого сообщения.

В асимметричных криптосистемах важно, чтобы сеансовые и асимметричные ключи были сопоставимы в отношении уровня безопасности, который они обеспечивают. Если используется короткий сеансовый ключ ( например, 40-битовый DES), то не имеет значения, насколько велики асимметричные ключи. Хакеры будут атаковать не их, а сеансовые ключи. Асимметричные открытые ключи уязвимы к атакам прямым перебором отчасти из-за того, что их тяжело заменить. Если атакующий узнает секретный асимметричный ключ, то будет скомпрометирован не только текущее, но и все последующие взаимодействия между отправителем и получателем.

Порядок использования систем с асимметричными ключами:

Безопасно создаются и распространяются асимметричные открытые и секретные ключи (см. раздел 2.2 ниже). Секретный асимметричный ключ передается его владельцу. Открытый асимметричный ключ хранится в базе данных X.500 и администрируется центром выдачи сертификатов (по-английски — Certification Authority или CA). Подразумевается, что пользователи должны верить, что в такой системе производится безопасное создание, распределение и администрирование ключами. Более того, если создатель ключей и лицо или система, администрирующие их, не одно и то же, то конечный пользователь должен верить, что создатель ключей на самом деле уничтожил их копию.
Создается электронная подпись текста с помощью вычисления его хэш-функции. Полученное значение шифруется с использованием асимметричного секретного ключа отправителя, а затем полученная строка символов добавляется к передаваемому тексту (только отправитель может создать электронную подпись).
Создается секретный симметричный ключ, который будет использоваться для шифрования только этого сообщения или сеанса взаимодействия (сеансовый ключ), затем при помощи симметричного алгоритма шифрования/расшифровки и этого ключа шифруется исходный текст вместе с добавленной к нему электронной подписью — получается зашифрованный текст (шифр-текст).
Теперь нужно решить проблему с передачей сеансового ключа получателю сообщения.
Отправитель должен иметь асимметричный открытый ключ центра выдачи сертификатов (CA). Перехват незашифрованных запросов на получение этого открытого ключа является распространенной формой атаки. Может существовать целая система сертификатов, подтверждающих подлинность открытого ключа CA. Стандарт X.509 описывает ряд методов для получения пользователями открытых ключей CA, но ни один из них не может полностью защитить от подмены открытого ключа CA, что наглядно доказывает, что нет такой системы, в которой можно было бы гарантировать подлинность открытого ключа CA.
Отправитель запрашивает у CA асимметричный открытый ключ получателя сообщения. Этот процесс уязвим к атаке, в ходе которой атакующий вмешивается во взаимодействие между отправителем и получателем и может модифицировать трафик, передаваемый между ними. Поэтому открытый асимметричный ключ получателя «подписывается» CA. Это означает, что CA использовал свой асимметричный секретный ключ для шифрования асимметричного отркытого ключа получателя. Только CA знает асимметричный секретный ключ CA, поэтому есть гарантии того, что открытый асимметричный ключ получателя получен именно от CA.
После получения асимметричный открытый ключ получателя расшифровывается с помощью асимметричного открытого ключа CA и алгоритма асимметричного шифрования/расшифровки. Естественно, предполагается, что CA не был скомпрометирован. Если же он оказывается скомпрометированным, то это выводит из строя всю сеть его пользователей. Поэтому можно и самому зашифровать открытые ключи других пользователей, но где уверенность в том, что они не скомпрометированы?
Теперь шифруется сеансовый ключ с использованием асимметричного алгоритма шифрования-расшифровки и асимметричного ключа получателя (полученного от CA и расшифрованного).
Зашифрованный сеансовый ключ присоединяется к зашифрованному тексту (который включает в себя также добавленную ранее электронную подпись).
Весь полученный пакет данных (зашифрованный текст, в который входит помимо исходного текста его электронная подпись, и зашифрованный сеансовый ключ) передается получателю. Так как зашифрованный сеансовый ключ передается по незащищенной сети, он является очевидным объектом различных атак.
Получатель выделяет зашифрованный сеансовый ключ из полученного пакета.
Теперь получателю нужно решить проблему с расшифровкой сеансового ключа.
Получатель должен иметь асимметричный открытый ключ центра выдачи сертификатов (CA).
Используя свой секретный асимметричный ключ и тот же самый асимметричный алгоритм шифрования получатель расшифровывает сеансовый ключ.
Получатель применяет тот же самый симметричный алгоритм шифрования-расшифровки и расшифрованный симметричный (сеансовый) ключ к зашифрованному тексту и получает исходный текст вместе с электронной подписью.
Получатель отделяет электронную подпись от исходного текста.
Получатель запрашивает у CA асимметричный открытый ключ отправителя.
Как только этот ключ получен, получатель расшифровывает его с помощью открытого ключа CA и соответствующего асимметричного алгоритма шифрования-расшифровки.
Затем расшифровывается хэш-функция текста с использованием открытого ключа отправителя и асимметричного алгоритма шифрования-расшифровки.
Повторно вычисляется хэш-функция полученного исходного текста.
Две эти хэш-функции сравниваются для проверки того, что текст не был изменен.

Особенности системы

Применение

Алгоритмы криптосистемы с открытым ключом можно использовать^[7]

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

Преимущества

Преимущество асимметричных шифров перед симметричными шифрами состоит в отсутствии необходимости предварительной передачи секретного ключа по надёжному каналу.
В симметричной криптографии ключ держится в секрете для обеих сторон, а в асимметричной криптосистеме только один секретный.
При симметричном шифровании необходимо обновлять ключ после каждого факта передачи, тогда как в асимметричных криптосистемах пару (E,D) можно не менять значительное время.
В больших сетях число ключей в асимметричной криптосистеме значительно меньше, чем в симметричной.

Недостатки

Преимущество алгоритма симметричного шифрования над несимметричным заключается в том, что в первый относительно легко внести изменения.
Хотя сообщения надежно шифруются, но «засвечиваются» получатель и отправитель самим фактом пересылки шифрованного сообщения.^[8]
Несимметричные алгоритмы используют более длинные ключи, чем симметричные. Ниже приведена таблица, сопоставляющая длину ключа симметричного алгоритма с длиной ключа несимметричного алгоритма с аналогичной криптостойкостью:

Длина симметричного ключа, бит	Длина несимметричного ключа, бит
56	384
64	512
80	768
112	1792
128	2304

Процесс шифрования-расшифрования с использованием пары ключей проходит на два-три порядка медленнее, чем шифрование-расшифрование того же текста симметричным алгоритмом.
В чистом виде асимметричные криптосистемы требуют существенно больших вычислительных ресурсов, потому на практике используются в сочетании с другими алгоритмами.
1. Для ЭЦП сообщение предварительно подвергается хешированию, а с помощью асимметричного ключа подписывается лишь относительно небольшой результат хеш-функции.
2. Для шифрования они используются в форме гибридных криптосистем, где большие объёмы данных шифруются симметричным шифром на сеансовом ключе, а с помощью асимметричного шифра передаётся только сам сеансовый ключ.

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

Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (Mitsuru Matsui). Предложенный им в 1993 г. (на Еврокрипте-93) алгоритм был изначально направлен на вскрытие DES и FEAL. Впоследствии линейный криптоанализ был распространён и на другие алгоритмы. На сегодняшний день наряду с дифференциальным криптоанализом является одним из наиболее распространённых методов вскрытия блочных шифров. Разработаны атаки на блочные и потоковые шифры.

Открытие линейного криптоанализа послужило толчком к построению новых криптографических схем.

Принцип работы

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

Защита от линейного криптоанализа

Для атаки на блочный шифр с помощью линейного криптоанализа достаточно, как было описано выше, получить линейное соотношение, существенно смещённое по вероятности от 1/2. Соответственно, первая цель при проектировании шифра, стойкого к атаке, — минимизировать вероятностные смещения, убедиться, что подобное соотношение не будет существовать. Другими словами, необходимо сделать так, чтобы при любом изменении текста или ключа в получающемся шифротексте ровно половина бит меняла своё значение на противоположное, причём каждый бит изменялся с вероятностью 1/2. Обычно это достигается путём выбора высоко нелинейных S-боксов и усилением диффузии.

Данный подход обеспечивает хорошее обоснование стойкости шифра, но чтобы строго доказать защищённость от линейного криптоанализа, разработчикам шифров необходимо учитывать более сложное явление — эффект линейных оболочек (linear hull effect).

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

Управление ключами (УК) является настолько важной и развитой областью криптографии, что требует отдельного и детального рассмотрения. На системы УК возлагается огромный набор различных функций, обеспечение самых разных базовых и вновь приобретенных свойств криптосистем, которые ими укомплектованы. Подобные схемы могут выполнять хранение, пересылку, шифрование (то есть обеспечение конфиденциальности), аутентификацию, «сдачу на хранение» (депонирование) и разделение ключей. Единственным общим свойством систем УК является то, что как результат разнообразных трансформаций они должны снабдить криптосистему ключом (симметричным или асимметричным), на котором и будет произведен основной процесс шифрования документа. Техническая реализация систем управления открытыми ключами (англ. PKI — Public Key Infrastructure) описана в главе 22.

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

С предварительной частичной установкой

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

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

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

В подобной ситуации классический протокол установления ключа сеанса выглядит примерно следующим образом — рис. 20.9. Вызывающий абонент обозначен А, вызываемый абонент — В, доверенный сервер — S, ключ которым априори обменялись А и S — «A-S», ключ между абонентом В и S — «B-S».

Рис. 20.9. Запрос коммуникационного ключа у доверенного сервера

Ключи без предварительной установки

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

Первая схема выработки секретного ключа носит название схемы Шамира по фамилии ее создателя. Первоначально все стороны, участвующие в обмене ключей по данной схеме, договариваются о большом простом числе Р (не являющимся секретом), обладающим теми же свойствами, что и в схеме Эль-Гамаль. Любые два абонента (А и В), желающие создать секретный, ключ сеанса:

Создают соответственно два больших случайных числа (а и б), а также их инверсии по модулю р (а^-1 modpи b^-1mod p) и держат их на своих системах в секрете.
Вызывающая сторона генерирует ключ сеанса k(k< р-2) и возводит его в степень а по модулю р, после чего отправляет полученное выражение вызываемому абоненту: M1=ka mod p.
Вызываемая сторона возводит полученное сообщение в степень bи отправляет обратно: М2 = (M1b mod p) = (kab mod p}.
Вызывающая сторона дешифрует полученное число инверсией числа а и отправляет обратно: МЗ = (М2-b mod р) = (kb mod p).
Наконец, абонент В дешифрует последнее сообщение инверсией числа b и получает желаемый ключ сеанса: k= (МЗ-b mod p) = (k mod p).

Асимметричная криптография, которая, казалось бы, решила проблему конфиденциальности сообщений без предварительной передачи секретного ключа по защищенному каналу, оказывается, всего лишь перенесла эту проблему в несколько иную область. При поверхностном взгляде на асимметричную систему кажется — «ищи в сети открытый ключ получателя шифруй им сообщение и — конфиденциальность достигнута». Но вот тут как раз появляется злоумышленник-посредник — это он гипотетически мог расположить на множестве серверов в сети свой открытый ключ под именем абонента-получателя и свой почтовый адрес. В дальнейшем при получении любого письма он дешифрует его своим закрытым ключом, читает и пересылает истинному получателю, зашифровав уже на настоящем открытом ключе, который он действительно знает. Не спасают при этом и схемы ЭЦП, если злоумышленник подменил открытые ключи как отправителя, так и получателя. Эти соображения приводят к тому, что предварительный защищенный канал все-таки необходим — для передачи открытого ключа и почтового адреса или хотя бы какого-либо подтверждающего блока данных (например, хэш-суммы открытого ключа).

Однако, асимметричные технологии сделали гораздо больший прорыв в схемах распространения ключей, чем симметричные — были изобретены сертификаты. Сертификатом называется блок информации, содержащий данные, уникально идентифицирующие абонента, его открытый ключ и транспортный адрес, причем этот блок информации подписан с помощью ЭЦП другого лица. Абонент, о котором идет речь в сертификате, называется владельцем ключа, субъект сети, поставивший подпись под сертификатом — заверяющим лицом (в законе РФ «Об электронно-цифровой подписи» – удостоверяющий центр). Предположим, абонент А никогда не общался с абонентом С и не может проверить подлинность его открытого ключа, но и А и С общались с неким абонентом В — тогда В может выступить заверяющим лицом и подписать сертификат на владельца ключа С. Тогда абонент А, получив сертификат и проверив подпись В, в чьем открытом ключе он уверен, может отныне полагаться и на открытый ключ абонента С.

В чем же заключается тот самый «прорыв» в схеме распространения ключей? Самое замечательное свойство сертификатов в том, что их использование можно объединять в цепочку. Действительно, предположим, двум желающим пообщаться абонентам А и D не удалось найти общего знакомого, но выяснилось, что А знает некоего В, a D знает некоего С, которые знакомы между собой. Значит, В может отправить А сертификат о ключе С, а С может отправить А сертификат о ключе D. В итоге А получает уверенность в том, что открытый ключ D, имеющийся у него на руках, истинен. Таким образом, была построена цепочка доверия, которая по своей сути представляет тот самый предварительный защищенный канал между А и D (отправителем и получателем), но канал этот был собран (и причем по очень несложной и надежной схеме) из нескольких уже существовавших очищенных каналов. Возможность подобного построения защищенного канала «по требованию» из нескольких коротких, уже существовавших, и есть преимущество открытой криптографии.

В настоящее время развитие описанной схемы по всему миру идет очень интенсивно. Наметились следующие основные тенденции. Во-первых, стали появляться субъекты, чьей единственной функцией является хранение и заверение ключей — центры сертификации (англ. Certification Authority —СА). Во-вторых, в процесс создания цепочек доверия стали активно включатся крупные производители программного обеспечения. Действительно, если пользователь ЭВМ приобретает лицензионное ПО в фирменной запечатанной коробке с голограммой и другими физическими степенями защиты, то задача подделки открытого ключа, находящегося на этом диске, становится на порядок более сложной. А имея несколько надежных открытых ключей крупных производителей ПО, пользователь уже в состоянии строить множество цепочек доверия к миллионам абонентов. И сами производители ПО получают в качестве дивидендов возможность аутентично присылать обновления программ по сети, подписанными теми же ключами, чьи открытые половинки были размещены на первоначальном компакт-диске.

Депонирование ключей

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

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

Среди наиболее известных реализаций первой схемы — государстве программа США по установке программно-аппаратного комплекса шифрования CLIPPER. Устройство представляет собой микросхему, работающую на криптоалгоритме Skipjack. В микросхему зашит уникальный индикатор и секретный ключ, копия которого разделена на две части и хранится в двух различных ведомствах США. Разработка и внедрение этого проекта вызвали широкий резонанс общественности США. Классическим примером второй схемы депонирования ключей является технология фирмы Microsoft — Encrypted File System (EFS) (файловая система с шифрованием). Первой ОС, в которую была встроена EFS, является Microsoft Windows 2000. Любой пользователь персональной ЭВМ, с установлено на ней EFS, может выбрать набор файлов, которые при хранении на диске будут шифроваться секретным ключом пользователя. Шифрование производится с помощью ключа сеанса, т. е. секретный ключ пользователя играет роль мастер-ключа. Однако, кроме шифрования мастер-ключом пользователя, копии ключа сеанса шифруются дополнительно открытым ключом администратора этой персональной ЭВМ и открытыми ключами тех пользователей, которых администратор определил в группу «восстановления ключей» данному пользователю. Таким образом, к каждому файлу в EFS, кроме привычного зашифрованного ключа сеанса, добавляются несколько записей депонирования (или, в терминах Microsoft, — восстановления) ключей.

Криптология довольно четко делится на две части: криптографию (шифрование) и криптоанализ. Криптограф пытается найти методы обеспечения секретности и(или) аутентичности (подлинности) сообщений. Криптоаналитик пытается выполнить обратную задачу, раскрывая шифр или подделывая кодированные сигналы таким образом, чтобы они были приняты как подлинные. Исходное сообщение, которому криптограф применяет свое искусство, называется открытым текстом, а результат его работы — шифрованным текстом сообщения — шифртекстом, или криптограммой. Для управления процессом шифрования криптограф всегда использует секретный ключ. Часто (но не всегда) он передает этот секретный ключ каким-либо надежным способом (например, в «дипломате», пристегнутом наручниками к руке курьера) человеку (или машине), которому он собирается позднее послать криптограмму, составленную с использованием этого ключа.

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

Термины

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

В настоящее время проблемами защиты информации занимается криптология (kryрtos — тайный, logos — наука). Криптология разделяется на два направления — криптографию и криптоанализ. Цели этих двух направлений криптологии прямо противоположны.

Криптография — наука о защите информации от несанкционированного прочтения ее посторонними лицами. Криптография занимается разработкой и исследованием методов шифрования информации.

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

Сфера интересов криптоанализа противоположная — разработка и исследование методов дешифрования (раскрытия) шифрограммы даже без знания секретного ключа.

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

Шифрование — преобразование информации, в результате которого исходный текст, который носит также название открытого текста, заменяется закрытым (шифрованным) текстом, то есть шифрограммой.

Дешифрование — обратный шифрованию процесс. На основе ключа зашифрованный текст (шифрограмма, шифровка) преобразуется в исходный открытый текст.

Процесс получения криптоаналитиками открытого сообщения из шифрованного сообщения без заранее известного ключа называется вскрытием или взломом шифра.

Проблема защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом, волновала человеческий ум с давних времен. История криптографии — ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была криптографической системой, так как в древних обществах ею владели только избранные. Священные книги Древнего Египта, Древней Индии тому примеры.

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

Современная криптография включает в себя четыре крупных раздела:

Симметричные криптосистемы. В симметричных криптосистемах и для шифрования, и для дешифрования используется один и тот же ключ. (Шифрование — преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом, дешифрование — обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный);
Криптосистемы с открытым ключом. В системах с открытым ключом используются два ключа — открытый и закрытый, которые математически связаны друг с другом. Информация шифруется с помощью открытого ключа, который доступен всем желающим, а расшифровывается с помощью закрытого ключа, известного только получателю сообщения.( Ключ — информация, необходимая для беспрепятственного шифрования и дешифрования текстов.);
Электронная подпись. Системой электронной подписи. называется присоединяемое к тексту его криптографическое преобразование, которое позволяет при получении текста другим пользователем проверить авторство и подлинность сообщения.
Управление ключами. Это процесс системы обработки информации, содержанием которых является составление и распределение ключей между пользователями.

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

Требования к криптосистемам

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

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

Рассмотрение задач из сферы криптографии начнем с задачи защиты данных, передаваемых по открытым каналам связи в наиболее полной постановке: В системе имеются две легальные стороны — «отправитель» и «получатель». Информационный процесс заключается в передаче сообщения от первого второму и считается протекающим нормально, если получатель получит сообщение без искажений, кроме него никто не ознакомится с содержанием сообщения, и если стороны не будут выставлять претензий друг другу. В задаче также присутствует злоумышленник, имеющий доступ к каналу передачи данных и стремящийся добиться отклонений от нормального течения процесса. Кроме того, каждая из легальных сторон может предпринять злоумышленные действия в отношении другой стороны. Перечислим возможные угрозы:

1. Угрозы со стороны злоумышленника.
1.1. Ознакомление с содержанием переданного сообщения.
1.2. Навязывание получателю ложного сообщения — как полная его фабрикация, так и внесение искажений в действительно переданное сообщение.
1.3. Изъятие переданного отправителем сообщения из системы таким образом, чтобы получатель не узнал о факте передачи сообщения;
1.4. Создание помех для нормальной работы канала передачи связи, то есть нарушение работоспособности канала связи.

2. Угрозы со стороны законного отправителя сообщения:
2.1. Разглашение переданного сообщения.
2.2. Отказ от авторства в действительности переданного им сообщения.
2.3. Утверждение, что некоторое сообщение отправлено получателю когда в действительности отправка не производилась.

3. Угрозы со стороны законного получателя сообщения:
3.1. Разглашение полученного сообщения.
3.2. Отказ от факта получения некоторого сообщения когда в действительности оно было им получено.
3.3. Утверждение, что некоторое сообщение получено от отправителя когда в действительности предъявленное сообщение сфабриковано самим получателем.

Как правило, угроза работоспособности канала связи (угроза 1.4) наиболее эффективно достигается нарушением физической среды передачи данных (разрушение линий передачи и узлов обработки данных) или созданием помех («глушение» радиосигнала, бомбардировка системы большим количеством ложных сообщений — «спам», и т.д.). Близко к ней находится угроза 1.3 — изъятие сообщения из канала связи. Эффективной защиты криптографическими средствами от этих угроз не существует, поэтому они обычно не рассматривается в работах по криптографии, проблема решается другими методами. Так, для устранения угрозы 1.3 обычно используется квитирование — высылка получателем отправителю квитанции (подтверждения) на полученное сообщение. Также в рамках криптографии отсутствует решение, которое бы устранило угрозы 2.1 и 3.1 — разглашение секретных данных одной из легальных сторон со «списыванием» этого на другую сторону или на ненадежность канала связи.

Оказалось, что сформулированная выше задача за вычетом угроз 1.3, 1.4, 2.1, 3.1 может быть разделена на три подзадачи, которые решаются независимо друг от друга и характеризуются собственными наборами угроз из приведенного списка:

· «классическая задача криптографии» — защита данных от разглашения и искажения при передаче по открытому каналу связи;
· «подпись электронного документа» — защита от отказа от авторства сообщения;
· «вручение заказного письма» — защита от отказа от факта получения сообщения;

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

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

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

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

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

2. В соответствии с некоторым регламентом (например, при каждой загрузке системы, или один раз в определенный промежуток времени, или перед запуском программы на выполнение) проверяется соответствие защищаемой единицы контрольному коду.

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

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

Задачи, решаемые криптографическими методами, отличаются друг от друга следующим:

· характером защищаемого информационного взаимодействия;
· целями злоумышленников;
· возможностями злоумышленников.

Простейший случай информационного взаимодействия — это передача данных от одного субъекта другому. Соответственно, самая распространенная задача из сферы защиты — защита передаваемой по каналам связи или хранимой в компьютерной системе информации, она исторически самая первая и до сих пор наиболее важная. Впрочем, необходимо добавить, что в последнее время в связи с проникновением электронных технологий во многие сферы жизни человека и общества возникают и принципиально новые проблемы. Одни из них первичны, такие, как уже упомянутая проблема защиты данных в каналах связи. Другие вторичны и существуют только в рамках конкретного решения той или иной первичной задачи. Например, «открытое распределение ключей» — совместная выработка двумя субъектами в ходе сеанса связи по открытому каналу общего секретного ключа таким образом, чтобы злоумышленники, «прослушивающие» канал, не смогли получить тот же самый ключ.

Что такое криптографический протокол

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

Протоколы имеют и другие отличительные черты:

Криптографическим протоколом называется такой, в основе которого лежит криптографический алгоритм. Однако целью криптографического протокола зачастую является не только сохранение информации в тайне от посторонних. Участники криптографического протокола могут быть близкими друзьями, у которых нет друг от друга секретов, а могут являться настолько непримиримыми врагами, что каждый из них отказывается сообщить другому. какое сегодня число. Тем не менее, им может понадобиться поставить свои подписи под совместным договором или удостоверить свою личность. В этом случае криптография нужна, чтобы предотвратить или обнаружим, подслушивание посторонними лицами, не являющимися участниками протокола, а также не допустить мошенничества. Поэтому часто требуется, чтобы криптографический протокол обеспечивал следующее: его участники не могут сделать или узнать больше того, что определено протоколом.
Зачем нужны криптографические протоколы
В повседневной жизни нам приходится сталкиваться с протоколами буквально на каждом шагу — играя в любые игры, делая покупки в магазинах или голосуя на выборах. Многими протоколами нас научили пользоваться родители, школьные учителя и друзья. Остальные мы сумели узнать самостоятельно.
В настоящее время люди все чаще контактируют друг с другом при помощи компьютеров. Компьютеры же, в отличие от большинства людей, в школу не ходили, у них не было родителей, да и учиться самостоятельно они не в состоянии. Поэтому компьютеры приходится снабжать формализованными протоколами, чтобы они смогли делать то, что люди выполняют особо не задумываясь. Например, если в магазине не окажется кассового аппарата, вы нее равно сможете купить в нем необходимую вещь. Однако такое кардинальное изменение протокола поставило бы бедный компьютер в полный тупик.
Большинство протоколов, которые люди используют при общении друг с другом с глазу на глаз, хорошо себя зарекомендовали только потому, что их участники имеют возможность вступить в непосредственный контакт. Взаимодействие с другими людьми через компьютерную сеть, наоборот, подразумевает анонимность. Будете ли вы играть с незнакомцем в преферанс, не видя, как он тасует колоду и раздает карты? Доверите ли вы своп деньги совершенно постороннему человеку, чтобы он купил вам что-нибудь в магазине? Пошлете ли вы свой бюллетень голосования по почте, зная, что с ним сможет ознакомиться любой из почтовых работников и потом рассказать всем о ваших нетрадиционных политических пристрастиях? Думаю, что нет.
Глупо считать, что компьютерные пользователи ведут себя более честно, чем абсолютно случайные люди. То же самое касается и сетевых администраторов, и проектировщиков компьютерных сетей. Большинство из них и в самом деле честные люди, однако есть и такие, кто может причинить нам большие неприятности. Поэтому так нужны криптографические протоколы. использование которых позволяет защититься от непорядочных людей.
Распределение ролей
Чтобы описание протоколов было более наглядным, имена их участников однозначно определяют роли, им уготованные. Пусть Антон и Борис принимают участие во всех двухсторонних протоколах. Как правило, начинает выполнение шагов, предусмотренных протоколом, Антон, а ответные действия предпринимает Борис. Если протокол является грех- или четырехсторонним, исполнение соответствующих ролей берут на себя Владимир и Георгий. Об остальных персонажах подробнее будет рассказано позже.
Роли, которые играют участники протоколов
Антон- Первый участник протоколов
Борис- Второй участник протоколов
Владимир- Участник трех- и четырехсторонних протоколов
Георгий- Участник четырехсторонних протоколов
Дмитрий- Доверенное лицо, наделенное правами арбитра
Зиновий- Злоумышленник
Кирилл- Контролер
Олег- Охранник
Петр- Подслушивает за участниками протоколов
Сергей- Свидетель
Протокол с арбитражем
Арбитр — участник протокола, которому остальные участники полностью доверяют, предпринимая соответствующие действия для завершения очередного шага протокола. Это значит, что у арбитра нет личной заинтересованности в достижении тех или иных целей, преследуемых участниками протокола, и он не может выступить на стороне любого из них. Участники протокола также принимают на веру все, что скажет арбитр, и беспрекословно следуют всем его рекомендациям.
В протоколах, которым мы следуем в повседневной жизни, роль арбитра чаще играет адвокат. Однако попытки перенести протоколы с адвокатом в качестве арбитра из повседневной жизни в компьютерные сети наталкиваются на существенные препятствия.
Легко довериться адвокату, про которого известно, что у него незапятнанная репутация, и с которым можно установить личный контакт. Однако если два участника протокола не доверяют друг другу, арбитр, не облаченный в телесную оболочку и существующий где-то в недрах компьютерной сети, вряд ли будет пользоваться у них доверием. Расценки за услуги, оказываемые адвокатом, известны. Кто и каким образом будет оплачивать издержки за аналогичные услуги арбитра в компьютерной сети? Введение арбитра в любой протокол увеличивает время, затрачиваемое на реализацию этого протокола.
Поскольку арбитр контролирует каждый шаг протокола, его участие и очень сложных протоколах может стать узким местом при их реализации. Увеличение числа арбитров позволяет избавиться от данного узкого места, однако одновременно возрастут и накладные расходы на реализацию протокола.
В силу того, что все участники протокола должны пользоваться услугами одного и того же арбитра, действия злоумышленника, который решит нанести им ущерб, будут направлены, в первую очередь, против этого арбитра. Следовательно, арбитр представляет собой слабое звено любого протокола с арбитражем.
Несмотря на отмеченные препятствия, протоколы с арбитражем находи г широкое применение на практике. В ходе дальнейшего изложения доверенное лицо, наделенное правами арбитра, будет именоваться Дмитрием.
Протокол с судейством
Чтобы снизить накладные расходы на арбитраж, протокол, в котором участвует арбитр, часто делится на две части. Первая полностью совпадает с обычным протоколом без арбитража, а ко второй прибегают только в случае возникновения разногласий между участниками. Для разрешения конфликтов между ними используется особый арбитр — судья.
Подобно арбитру, судья является незаинтересованным участником протокола, которому остальные участники доверяют. Однако в отличие от арбитра. судья участвует отнюдь не в каждом шаге протокола. Услугами судьи пользуются, только если требуется разрешить сомнения относительно правильности действий участников протокола. Если таких сомнений ни у кою не возникает, судейство не понадобится.
В компьютерных протоколах с судейством предусматривается наличие данных, проверив которые доверенное третье лицо может решить, не смошенничал ли кто-либо из участников этого протокола. Хороший протокол с судейством также позволяет выяснить, кто именно ведет себя нечестно Это служит прекрасным превентивным средством против мошенничества со стороны участников такого протокола.
Самоутверждающийся протокол
Самоутверждающийся протокол не требует присутствия арбитра для завершения каждого шага протокола. Он также не предусматривает наличие судьи для разрешения конфликтных ситуаций. Самоутверждающийся протокол устроен так, что, если один из его участников мошенничает, другие смогут моментально распознать нечестность, проявленную этим участником, и прекратить выполнение дальнейших шагов протокола.
Конечно же, хочется, чтобы существовал универсальный самоутверждающийся протокол на все случаи жизни. Однако на практике в каждом конкретном случае приходится конструировать свой специальный самоутверждающийся протокол.

Протоколы с посредником

Посредник — это незаинтересованная третья сторона, которой доверено завершение протокола (см. 1-й (а)). Незаинтересованность означает, что у посредника нет заинтересованности в результате работы протокола и склонности к одной из сторон. «Доверено» означает, что все участники протокола принимают все, что скажет посредник за истину, все его действия — как правильные, и уверены в том, что посредник выполнит свою часть протокола. Посредники помогают реализовать работу протоколов взаимодействия недоверяющих друг другу сторон.

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

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

(1) А передает право собственности юристу.

(2) Б передает чек юристу.

(3) А депонирует чек.

(4) Дождавшись оплаты чека юрист передает право собственности Б. Если чек не оплачен в течение определенного времени, А доказывает этот факт юристу, и тот возвращает право собственности А.

В этом протоколе А верит, что юрист не передаст Б право собственности до тех пор, пока чек не б у-дет оплачен, и вернет право собственности А, если чек оплачен не будет. Б верит, что юрист будет обладать правом собственности до тех пор, пока чек не будет оплачен, и передаст право собственности Бобу сразу же после оплаты чека. Юрист не заботится об оплате чека. Он в любом случае выполнит свою часть протокола, ведь ему заплатят в любом случае.

В этом примере юрист играет роль посредника. Юристы часто выступают в роли посредников при завещ а-ниях и иногда при переговорах о контракте. Различные биржи выступают в качестве посредников между пок у-пателями и продавцами.

В качестве посредника может выступить и банк — для покупки машины :

(1) Б заполняет чек и передает его в банк.

(2) Если на счету Б достаточно денег для покрытия чека, банк заверяет чек и возвращает его Б.

(3) А передает Б право собственности, а Б передает А заверенный чек.

(4) А депонирует чек.

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

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

Понятие посредника старо как мир. Всегда существовали определенные люди — вожди, жрецы и тому подобное — обладавшие влиянием, позволяющим им действовать справедливо. Посредники играют определенную роль в нашем обществе, обман доверия подорвал бы занимаемое ими положение . Юристы-посредники, нарушающие правила игра, подвергаются наказанию — например, исключению из коллегии адвокатов . Это идеальная картина, в реальном мире положение, к сожалению, может отличаться от нее .

Этот идеал можно перенести на мир компьютеров, но с компьютерными посредниками существует ряд пр о-блем:

— Легко найти нейтральную третью сторону, которой можно доверять, если вы знаете посредника и можете лично увидеть его. Две стороны, относящиеся друг к другу с подозрением, с тем же подозрением отнесутся и к безликому посреднику, затерянному где-то в сети.

— Компьютерная сеть должна обеспечить поддержку посредника. Занятость юристов общеизвестна, на кого в сети лягут дополнительные накладные расходы ?

— Существует задержка, присущая всем протоколам с посредником.

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

— Так как каждый в сети должен доверять посреднику, то посредник представляет собой слабое место сети при попытке ее взлома.

Несмотря на это посредничество все еще активно используется. В протоколах с использованием посредника эту роль будет играть Трент.

Арбитражные протоколы

Используемый из-за высокой стоимости найма посредников арбитражные протокол может быть разбит на два подпротокола нижнего уровня. Первый представляет собой протокол без посредника, используемый при желании сторон выполнить протокол. Другой представляет собой протокол с посредником, приглашаемым в исключительных обстоятельствах — при наличии разногласий между сторонами. Соответствующий специальный посредник называется арбитром.

Арбитр, как и посредник, представляет собой незаинтересованного участника протокола, которому доверяют обе стороны. В отличие от посредника он непосредственно не принимает участия в каждой отдельной реализации протокола и приглашается только для проверки честности выполнения протокола сторонами.

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

Подпротокол без посредника (выполняется всегда):

(1) А и Б договариваются об условиях контракта.

(2) А подписывает контракт.

(3) Б подписывает контракт.

Подпротокол с использованием арбитра (выполняется при наличии разногласий):

(4) А и Б предстают перед судьей.

(5) А предоставляет свои доказательства.

(6) Б предоставляет свои доказательства.

(7) Судья принимает решение на основании доказательств.

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

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

Самодостаточные протоколы

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

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

Попытки вскрытия протоколов

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

Люди могут использовать множество способов взломать протокол. Некоторые, не являясь участниками пр о-токола, могут «подслушивать» какую-то часть или весь протокол. Это называется пассивным вскрытием, так как взломщик не воздействует на протокол. Все, что он может сделать — это проследить за протоколом и поп ы-таться добыть информацию. Этот тип вскрытия соответствует вскрытию с использованием только шифротекста, обсуждавшемуся в разделе 1.1. Так как пассивные вскрытия трудно обнаружить, протоколы стремятся предо т-вращать, а не обнаруживать их. В этих протоколах роль злоумышленника будет играть Е.

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

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

Активные вскрытия более серьезны, особенно в отношении протоколов, в которых стороны не обязательно доверяют друг другу. Взломщик не обязательно кто-то совсем посторонний, он может быть зарегистрированным пользователем системы и даже системным администратором. Может быть даже несколько активных взломщ и-ков, работающих вместе. В этой книге роль злонамеренного активного взломщика будет играть Ме.

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

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

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

Идея шифрования состоит в предотвращении просмотра истинного содержания сообщения(текста, файла и т.п.) теми , у кого нет средств его дешифрования. А прочесть файл сможет лишь тот, кто сможет его дешифровать.

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

Один из самых известных методов шифрования носит имя Цезаря, который если и не сам его изобрел, то активно им пользовался. Не доверяя своим посыльным, он шифровал письма элементарной заменой А на D, В на Е и так далее по всему латинскому алфавиту. При таком кодировании комбинация XYZ была бы записана как АВС, а слово «ключ» превратилось бы в неудобоваримое «нобъ»(прямой код N+3).

Спустя 500 лет шифрование стало повсеместно использоваться при оставлении текстов религиозного содержания, молитв и важных государственных документов.

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

Основные понятия и определения криптографии

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

Некоторые основные понятия и определения.

Алфавит — конечное множество используемых для кодирования информации знаков.

Текст — упорядоченный набор из элементов алфавита.

В качестве примеров алфавитов, используемых в современных ИС можно привести следующие:

алфавит Z₃₃ — 32 буквы русского алфавита и пробел;
алфавит Z₂₅₆ — символы, входящие в стандартные коды ASCII и КОИ-8;
бинарный алфавит — Z₂ = {0,1};
восьмеричный алфавит или шестнадцатеричный алфавит;

Шифрование — преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом.

Дешифрование — обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.

Ключ — информация, необходимая для беспрепятственного шифрования и дешифрования текстов.

Криптографическая система представляет собой семейство T преобразований открытого текста. члены этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K — это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.

Криптосистемы разделяются на симметричные и с открытым ключом ( или асимметрические) .

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

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

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

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

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

количество всех возможных ключей;
среднее время, необходимое для криптоанализа.

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

Для современных криптографических систем защиты информации сформулированы следующие общепринятые требования:

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

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

Типы криптостойких систем шифрования

Абсолютно стойкие системы

Доказательство существования абсолютно стойких алгоритмов шифрования было выполнено Клодом Шенноном и опубликовано в работе «Теория связи в секретных системах».[1] Там же определены требования к такого рода системам:

ключ генерируется для каждого сообщения (каждый ключ используется один раз)

ключ статистически надёжен (то есть вероятности появления каждого из возможных символов равны, символы в ключевой последовательности независимы и случайны)

длина ключа равна или больше длины сообщения

исходный (открытый) текст обладает некоторой избыточностью (является критерием оценки правильности расшифровки)

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

Некоторыми аналитиками утверждается, что Шифр Вернама является одновременно абсолютно криптографически стойким и к тому же единственным[источник не указан 357 дней] шифром, который удовлетворяет этому условию.

Достаточно стойкие системы

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

вычислительная сложность полного перебора

известные на данный момент слабости (уязвимости) и их влияние на вычислительную сложность.

В каждом конкретном случае могут существовать дополнительные критерии оценки стойкости.

Оценка криптостойкости систем шифрования

Начальная оценка

Поскольку атака методом грубой силы (полным перебором всех ключей) возможна для всех типов криптографических алгоритмов, кроме абсолютно стойких «по Шеннону», для вновь созданного алгоритма она может являться единственной существующей. Способы её оценки основываются на вычислительной сложности, которая затем может быть выражена во времени, деньгах, и требуемой производительности вычислительных ресурсов, например, в MIPS. Эта оценка пока является максимальной и минимальной одновременно.

Текущая оценка

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

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

Важность длительной проверки и открытого обсуждения

Чем более длительным и экспертным является анализ алгоритма и реализаций, тем более достоверной можно считать его стойкость. В нескольких случаях длительный и внимательный анализ приводил к снижению оценки стойкости ниже приемлемого уровня (например, в черновых версиях FEAL). Недостаточная проверка (по мнению многих криптографов — искусственное ослабление) алгоритма потокового шифрования А5/1 привела к успешной атаке.

При́нцип Керкго́ффса — правило разработки криптографических систем, согласно которому в засекреченном виде держится только определённый набор параметров алгоритма, называемый ключом, а остальные детали могут быть открыты без снижения стойкости алгоритма ниже допустимых значений. Другими словами, при оценке надёжности шифрования необходимо предполагать, что противник знает об используемой системе шифрования всё, кроме применяемых ключей.

Впервые данный принцип сформулировал в XIX веке голландский криптограф Огюст Керкгоффс. Шеннон сформулировал этот принцип (вероятно, независимо от Керкгоффса) следующим образом: «враг может знать систему». Широко применяется в криптографии.

Общие сведения

Сущность принципа заключается в том, что чем меньше секретов содержит система, тем выше её безопасность. Так, если утрата любого из секретов приводит к разрушению системы, то система с меньшим числом секретов будет надёжней. Чем больше секретов содержит система, тем более она ненадёжна и потенциально уязвима. Чем меньше секретов в системе — тем выше её прочность.^[1]

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

Большинство широко используемых систем шифрования, в соответствии с принципом Керкгоффса, используют известные, не составляющие секрета криптографические алгоритмы. С другой стороны, шифры, используемые в правительственной и военной связи, как правило, засекречены; таким образом создаётся «дополнительный рубеж обороны».

Шесть требований Керкгоффса

Требования к криптосистеме впервые изложены в книге Керкгоффса «Военная криптография» (издана в 1883 году). Шесть основных требований к криптосистеме, все из которых до настоящего времени определяют проектирование криптографически стойких систем, в переводе с французского звучат так:

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

Второе из этих требований и стало известно как «принцип Керкгоффса».

Также важным, впервые строго сформулированным выводом «Военной криптографии» является утверждение криптоанализа как единственного верного способа испытания шифров.

Обзор известных методов криптоанализа классических шифров .

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

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

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

2.1. Типовые методы криптоанализа классических алгоритмов .

2.1.1. Метод встречи посередине .

Если множество ключей криптоалгоритма замкнуто относительно композиции, то есть для любых ключей z_i и z _jнайдется ключ z_k такой, что результат шифрования любого текста последовательно на z_i и z _j равен шифрограмме этого же числа на z_k , то есть F(z _j,F(z_i, x))= F(z _k , x), то можно воспользоваться этим свойством. Пусть нам нужно найти ключ z_k. Тогда для нахождения ключа z_k, необходимо найти эквивалентную ему пару ключей z_i , z_j. Данный метод криптоанализа основан на “парадоксе дней рождения”. Известно, что если считать, что дни рождения распределены равномерно, то в группе из 24 человек с вероятностью 0,5 у двух человек дни рождения совпадут. В общем виде этот парадокс формулируется так: если a Ц n предметов выбираются с возвращением из некоторой совокупности размером n, то вероятность того что два из них совпадут, равна 1-exp(-a² / 2) .

Пусть известен открытый текст x и его шифрограмма y. Для текста x строим базу данных, содержащую случайное множество ключей z^|и соответствующих шифрограмм w=F(z^| , x), и упорядочиваем ее по шифрограммам w. Объем базы данных выбираем О( Ц # {z} ). Затем подбираем случайным образом ключи z^{| |} для расшифровки текстов y и результат расшифрования v = F(z^{| |} , y) сравниваем с базой данных. Если текст v окажется равным одной из шифрограмм w, то ключ z^| z^{| |} эквивалентен искомому ключу z. Временная сложность метода составляет О( Ц # {z} log#{z}). Множитель log#{z} учитывает сложность сортировки. Требуемая память равна О( Ц # {z} log#{z}) бит или ОЦ # {z}) блоков ( предполагается, что длина блока и длина ключа различаются на ограниченную константу ).

Этот же метод применим, если множество ключей содержит достаточно большое подмножество, являющееся полугруппой.

Другое применение этого метода для множества, не являющегося полугруппой, можно продемонстрировать на хэш-функциях. Например, для подделки подписи надо найти два текста, обладающих одним хэш-образом. После этого можно подписанное сообщение заменить на другое, обладающее таким же хэш-образом. Поиск двух таких сообщений можно выполнить с использованием метода “встречи посередине”. Сложность поиска равна О(Ц #{h}), где #{h} — число всевозможных хэш-образов.

Этот алгоритм является вероятностным. Однако существуют и детерминированный аналог этого алгоритма “giant step — baby step” с такой же сложностью, предложенный американским математиком Д.Шенксом.

2.1.2. Метод Полларда.

Этот вероятностный метод основан на следующем факте. Если на некотором конечном множестве М определить случайное отображение f и применить его поочередно ко всем элементам М, а ребрами соответствия — y=f(x) для x,yН М. Поскольку множество М конечно, то этот граф должен содержать деревья, корни которых соединены в циклы. Для случайного отображения f длина цикла равна О(Ц #М ) и высота дерева в среднем равна О(Ц #М ).

Для нахождения ключа, например в криптоалгоритме, основанном на задаче логарифма на некоторой группе, достаточно решить задачу о встрече на графе случайного отображения. Для этого из двух разных стартовых точек x₀^|, x₀^{| |} строятся траектория до входа в цикл. Затем одна из двух конечных точек, лежащих в цикле, фиксируется, а траектория другой продолжается до встречи с фиксированной точкой. Для функции f и точки входа x₀ длина траектории составляет О(Ц #М ) шагов. Типичный вид этой траектории содержит предельный цикл длины О(Ц #М ) и отрезок до входа в цикл примерно такой же длины. В качестве индикатора замыкания траектории Поллард предложил использовать равенство x_i = x_2i , где x_i — i-я точка траектории для входа x₀. Это равенство будет выполняться всегда. Значение индекса i не превышает суммы длины пути до входа в цикл.

В среднем сложность нахождения равенства x_i = x_2iравна 3Ц (p /8)#М. Сложность встречи, когда обе точки лежат в цикле, равна 0,5Ц (p /8)#М. Таким образом, итоговая сложность равна 6,5Ц (p /8)#М.

Метод Полларда применяется для решения задачи логарифма на циклической группе, поиска частично эквивалентных ключей (коллизий), для нахождения двух аргументов, дающих одинаковое значение хэш-функции, и в некоторых других случаях. Применительно к задаче логарифмирования этот метод позволяет отказаться от использования большого объема памяти по сравнению с методом встречи посередине. Кроме того, пропадает необходимость сортировки базы данных. В результате временная сложность по сравнению с методом встречи посередине снижается на множитель О(log#М). Сложность этого метода в данном случае составляет О(Ц #М) шагов и требует памяти объема О(1) блоков. Однако не всегда требуется малая память.

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

1. Войти в цикл, используя равенство x_i = x_2i = t .

2. Измерить длину цикла m, применяя последовательно отображение f к элементу t до получения равенства f^m(t)=t .

3. Разбить цикл m на v интервалов одинаковой или близкой длины и создать базу данных, запомнив и упорядочив начальные точки интервалов.

4. Для стартовой вершины п.1 выполнять одиночные шаги до встречи с какой-либо точкой из базы данных п.3. Отметить начальную и конечную точки интервала, на котором произошла встреча.

5. Стереть предыдущую и создать новую базу данных из v точек, разбив интервал, на котором произошла встреча, на равные по длине части, запомнив и отсортировав начальные точки интервалов.

6. Повторить процедуры пп.4,5 до тех пор, пока не получится длина интервала, равная 1. Вычислить точку встречи в цикле, вычислить коллизию как пару вершин, одна из которых лежит в цикле, а друга — нет.

Этот алгоритм требует многократного выполнения О(Ц #М ) шагов до входа в цикл и выполнени сортировки базы данных. На каждом этапе при создании новой базы данных длина интервала сокращается в v раз, то есть количество повторов равно О(log_v#М ). Если v << Ц #М, то сложностью сортировки базы данных можно пренебречь. Тогда сложность алгоритма равна О(Ц #М log_v #М).

Рассмотрим возможность улучшения оценки сложности этого метода за счет увеличения доступной памяти. Напомним, что почти все вершины графа случайного отображения лежат на одном дереве. Поэтому будем решать задачу о встрече на случайном ориентированном дереве. С ростом глубины h ширина дерева b(h) уменьшается, то есть случайное отображение обладает сжимающими свойствами. Поэтому с ростом глубины вершины, с одной стороны, увеличивается сложность встречи за счет многократного применения отображения, с другой стороны, увеличивается вероятность встречи в силу сжимающих свойств. Доля вершин с глубиной не менее h равна О(1/h).

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

Сложность первого алгоритма равна km (log m). Множитель log m учитывает сложность сортировки. В силу парадокса дней рождения m = О(#M/h)^0.5. Для одного шага сложность алгоритма равна О(Ц #M log#M), то есть этот алгоритм более эффективный, чем алгоритм встречи посередине.

После первого шага от листа глубины становится равной О( log#М ). Однако в дальнейшем рост глубины с каждым шагом замедляется. Это объясняется существенно разрывным характером условной вероятности р(h|H) получения глубины h при исходной глубине H. Действительно, из определения глубины следует, что каждая вершина с глубиной H+1 связана ребром с вершиной с глубиной H. Из каждой вершины исходит единственное ребро. Поэтому в силу количественных оценок ширины графа

р(H+1|H)=[O(H^-2 — (H+1)^-2)]/O(H^-2)=1-O(H^-1).

Числитель этого выражения равен разности ширины графа на глубинах H и H+1, знаменатель учитывает то, что исходная глубина равна Н. Вероятность попасть на глубину h>H+1 определяется вероятностью непопадания на глубину H+1 и шириной графа,

р(h|H)=O(H^-1h^-2).

Сравним вероятность p_k(h) получения глубины h после k шагов при спуске от листа и вероятность p_k(h|M_k-1) глубины h после k шагов при условии, что на шаге k-1 глубина равнялась математическому ожиданию. Имеет место оценка p_k(h)» p_k(h|M_k-1). Поэтому место вероятности сложного события p_k(h) можно рассматривать вероятность простого события p_k(h|M_k-1).

Пусть стартовая вершина лежит на глубине H=O( log#M). Какова будет глубина после очередного шага? Непосредственные вычисления показывают, что математическое ожидание глубины равно H+1+O(1), то есть второй и последующий шаги увеличивают глубину спуска на О(1). Подстановка в качестве исходной глубины математического ожидания глубины спуска на предыдущем шаге дает оценку математического ожидания глубины спуска после к шагов:

h=O( log#M ) + O(k).

Поскольку оптимальное число шагов при спуске к алгоритма определяется равенством сложности спуска mk и сложности сортировки m log m, то к_опт=O(log#M). Отсюда следует, что задача встречи на случайном ориентированном дереве не менее сложна, чем задача о встрече в цикле, то есть алгоритм Полларда не улучшаем за счет увеличения доступной памяти.

2.1.3. Дифференциальный метод криптоанализа.

Дифференциальный метод криптоанализа (ДКА) был предложен Э.Бихамом и А.Шамиром в 1990 г. Дифференциальный криптоанализ — это попытка вскрытия секретного ключа блочных шифров, которые основаны на повторном применении криптографически слабой цифровой операции шифрования r раз. При анализе предполагается, что на каждом цикле используется свой подключ шифрования. ДКА может использовать как выбранные, так и известные открытые тексты .

Успех таких попыток вскрытия r-циклического шифра зависит от существования дифференциалов (r-1)-го цикла, которые имеют большую вероятность. Дифференциал i-го цикла определяется как пара ( a , b )_i такая, что пара различных открытых текстов x, x* c разностью a может привести к паре выходных текстов y, y* после i-ого цикла, имеющих разность b (для соответствующего понятия разности ). Вероятность i-циклового дифференциала (a ,b )_i — это условная вероятность P(D y(i)=b | D x= a ) того, что разность D y(i) пары шифртекстов ( y, y*) после i-ого цикла равна b при условии, что пара текстов (x, x*) имеет разность D x=a ; открытый текст x и подключи циклов к⁽¹⁾ , к⁽²⁾ ,…., к⁽ⁱ⁾ независимыми и равновероятными.

Основная процедура ДКА r- циклического шифра с использованием выбранных открытых текстов может быть следующей :

1. На этапе предвычислений ищем множество (r-1)-цикловых дифференциалов (a ₁,b ₁)_r-1 , (a ₂,b ₂)_r-1 ,…. (a _s,b _s)_r-1 . Упорядочиваем это множество дифференциалов по величине их вероятности.

2. Выбираем открытый текст x произвольным образом и вычисляем x* так, чтобы разность между x и x* была равна a ₁. Тексты x и x* шифруется на подлинном ключе и после r циклов получаем пару шифртекстов y(r) , y*(r). Предполагаем, что на выходе предпоследнего (r-1)-ого цикла разность шифртекстов равна наиболее вероятной: D y(r-1)=b ₁. Для тройки (D y(r-1), y(r) , y*(r)) находим каждое возможное (если их несколько) значение подключа последнего цикла к^(r). Добавляем его к количеству появлений каждого такого значения подключа к^(r).

3. Повторяем п.2 до тех пор, пока одно или несколько значений подключа к^(r) не станет появляться чаще других. Берем этот подключ или множество таких подключей в качестве криптографического решения для подключа к^(r).

4. Повторяем пп.1-3 для предпоследнего цикла, при этом значения y(r-1) вычисляются расшифрованием шифртекстов на найденном подключе последнего цикла к^(r). Далее действуем аналогично, пока не будут раскрыты ключи всех циклов шифрования.

Предложенный впервые для анализа конкретного шифра, ДКА оказался применимым для анализа широкого класса марковских шифров. Марковским называется шифр, у которого уравнение шифрования на одном цикле удовлетворяет условию: вероятность дифференциала не зависит от выбора открытых текстов. Тогда, если подключи циклов независимы, то последовательность разностей после каждого цикла образует марковскую цепь, где последующее состояние определяется только предыдущим. Примерами марковских шифров являются DES и FEAL .

Отличительной чертой дифференциального анализа является то, что он практически не использует алгебраические свойства шифра (линейность, аффинность, транзитивность, замкнутость и т.п.), а основан лишь на неравномерности распределения вероятности дифференциалов.

2.1.4. Линейный метод криптоанализа .

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

Обычно при шифровании используется сложение по модулю 2 текста с ключом и операции рассеивания и перемешивания. Задача криптоаналитика — найти наилучшую линейную аппроксимацию (после всех циклов шифрования ) выражения

x_i1+….+x_ir+y_j1 + y_js=z_k1+ …. + z_{k t} (3.1)

Пусть p_L — вероятность того, что (3.1) выполняется, при этом необходимо, чтобы p_L № 1/2 и величина | p_L-1/2 | должна быть максимальна. Если | p_L-1/2 | достаточно велика и криптоаналитику известно достаточное число пар открытых и соответствующих зашифрованных текстов, то сумма по модулю 2 бит ключа на соответствующей позиции в правой части (3.1) равна наиболее вероятному значению суммы по модулю 2 соответствующих бит открытых и зашифрованных текстов в левой части. Если p_L > 1/2, то сумма бит ключа в правой части (3.1) равна нулю, если сумма бит в левой части равна нулю больше, чем для половины пар зашифрованных текстов, и сумма бит ключа в правой части (3.1) равна единице, если сумма бит в левой части равна единице больше, чем для половины текстов . Если p_L< 1/2 , то наоборот : сумма бит ключа в правой части (3.1) равна нулю , если сумма бит в левой части равна единице больше , чем для половины пар открытых и зашифрованных текстов, и сумма бит ключа в правой части (3.1) равна единице, если сумма бит в левой части равна нулю больше, чем для половины текстов. Для нахождения каждого бита собственно ключа теперь нужно решить систему линейных уравнений для известных линейных комбинаций этих бит, но эта процедура не представляет сложности, так как сложность решения системы линейных уравнений описывается полиномом не более третьей степени от длины ключа.

Требуемое для раскрытия ключа количество N пар открытых и зашифрованных текстов (блоков) оценивается выражением

N » | p_L-1/2 | ^-2 .

Для раскрытия ключа шифра DES этим методом необходимо 2⁴⁷ пар известных открытых и зашифрованных текстов.

Рассеивание (diffusion) — то есть изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста;
Перемешивание (confusion) — использование преобразований, затрудняющих получение статистических зависимостей между шифротектстом и открытым текстом.

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

Общая схема

В настоящее время симметричные шифры — это:

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

поточные шифры, в которых шифрование проводится над каждым битом либо байтом исходного (открытого) текста с использованием гаммирования. Поточный шифр может быть легко создан на основе блочного (например, ГОСТ 28147-89 в режиме гаммирования), запущенного в специальном режиме.

Большинство симметричных шифров используют сложную комбинацию большого количества подстановок и перестановок. Многие такие шифры исполняются в несколько (иногда до 80) проходов, используя на каждом проходе «ключ прохода». Множество «ключей прохода» для всех проходов называется «расписанием ключей» (key schedule). Как правило, оно создается из ключа выполнением над ним неких операций, в том числе перестановок и подстановок.

Типичным способом построения алгоритмов симметричного шифрования является сеть Фейстеля. Алгоритм строит схему шифрования на основе функции F(D, K), где D — порция данных, размером вдвое меньше блока шифрования, а K — «ключ прохода» для данного прохода. От функции не требуется обратимость — обратная ей функция может быть неизвестна. Достоинства сети Фейстеля — почти полное совпадение дешифровки с шифрованием (единственное отличие — обратный порядок «ключей прохода» в расписании), что сильно облегчает аппаратную реализацию.

Операция перестановки перемешивает биты сообщения по некоему закону. В аппаратных реализациях она тривиально реализуется как перепутывание проводников. Именно операции перестановки дают возможность достижения «эффекта лавины». Операция перестановки линейна — f(a) xor f(b) == f(a xor b)

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

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

Параметры алгоритмов

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

стойкость
длина ключа
число раундов
длина обрабатываемого блока
сложность аппаратной/программной реализации
сложность преобразования

Распространенные алгоритмы

AES (англ. Advanced Encryption Standard) — американский стандарт шифрования
ГОСТ 28147-89 — отечественный стандарт шифрования данных
DES (англ. Data Encryption Standard) — стандарт шифрования данных в США до AES
3DES (Triple-DES, тройной DES)
RC6 (Шифр Ривеста )
Twofish
IDEA (англ. International Data Encryption Algorithm)
SEED — корейский стандарт шифрования данных
Camellia — сертифицированный для использовании в Японии шифр
CAST (по инициалам разработчиков Carlisle Adams и Stafford Tavares)
XTEA — наиболее простой в реализации алгоритм

Сравнение с асимметричными криптосистемами

Достоинства

скорость (по данным Applied Cryptography — на 3 порядка выше)
простота реализации (за счёт более простых операций)
меньшая требуемая длина ключа для сопоставимой стойкости
изученность (за счёт большего возраста)

Недостатки

сложность управления ключами в большой сети. Означает квадратичное возрастание числа пар ключей, которые надо генерировать, передавать, хранить и уничтожать в сети. Для сети в 10 абонентов требуется 45 ключей, для 100 уже 4950, для 1000 — 499500 и т. д.
сложность обмена ключами. Для применения необходимо решить проблему надёжной передачи ключей каждому абоненту, так как нужен секретный канал для передачи каждого ключа обеим сторонам.

Основные сведения

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

Классическим примером таких алгоритмов являются симметричные криптографические алгоритмы, перечисленные ниже:

Простая перестановка
Одиночная перестановка по ключу
Двойная перестановка
Перестановка «Магический квадрат»

Простая перестановка

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

Одиночная перестановка по ключу

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

Двойная перестановка

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

Перестановка «Магический квадрат»

Магическими квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Подобные квадраты широко применялись для вписывания шифруемого текста по приведенной в них нумерации. Если потом выписать содержимое таблицы по строкам, то получалась шифровка перестановкой букв. На первый взгляд кажется, будто магических квадратов очень мало. Тем не менее, их число очень быстро возрастает с увеличением размера квадрата. Так, существует лишь один магический квадрат размером 3 х 3, если не принимать во внимание его повороты. Магических квадратов 4 х 4 насчитывается уже 880, а число магических квадратов размером 5 х 5 около 250000. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, потому что ручной перебор всех вариантов ключа для этого шифра был немыслим.

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

Преобразование должно использовать следующие принципы:

Рассеивание (diffusion) — то есть изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста;
Перемешивание (confusion) — использование преобразований, затрудняющих получение статистических зависимостей между шифротектстом и открытым текстом.

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

Основная идея

Блочный шифр состоит из двух взаимосвязанных алгоритмов: алгоритм шифрования E и алгоритм расшифрования E⁻¹. Входными данными служат блок размером n бит и k—битный ключ. На выходе получается n-битный зашифрованный блок. Для любого фиксированного ключа функция расшифрования является обратной к функции шифрования для любого блока M и ключа K.

Для любого ключа K, E_K является биективной функцией (перестановкой) на множестве n-битных блоков.

Размер блока n — это фиксированный параметр блочного шифра, обычно равный 64 или 128 битам, хотя некоторые шифры допускают несколько различных значений. Длина 64 бита была приемлема до середины 90-х годов, затем использовалась длина 128 бит, что примерно соответствует размеру машинного слова и позволяет эффективную реализацию на большинстве распространённых вычислительных платформах. Различные схемы шифрования позволяют зашифровывать открытый текст произвольной длины. Каждая имеет определенные характеристики: вероятность ошибки, простота доступа, уязвимость к атакам. Типичными размера ключа являются 40, 56, 64, 80, 128, 192 и 256 бит. В 2006 г. 80-битный ключ способен был предотвратить атаку грубой силой.

Режимы работы блочного шифра

Простейшим режимом работы блочного шифра является ECB (Electronic CodeBook (англ.) — режим простой замены или электронной кодовой книги), где все блоки открытого текста зашифровываются независимо друг от друга. Однако, при использовании этого режима статистические свойства открытых данных частично сохраняются, так как каждому одинаковому блоку данных однозначно соответствует зашифрованный блок данных. При большом количестве данных (например, видео или звук) это может привести к утечке информации о их содержании и дать больший простор для криптоанализа. Удаление статистических зависимостей в открытом тексте возможно с помощью предварительного архивирования, но оно не решает задачу полностью, так как в файле остается служебная информация архиватора, что не всегда допустимо.

Аналогичная проблема возникает при формировании и преобразовании «хвостового» блока данных. Так как данные могут быть любой длины, а блочный шифр требует данные кратные длине блока, то «хвостовой» блок данных зачастую приходится искусственно дополнять до требуемого размера. При этом, например, заполнение хвоста одинаковыми символами облегчает атаку по известному открытому тексту. Однако, проблема легко решается заполнением случайных содержимым (к примеру, с использованием ГПСЧ)

Принципиальным решением описанных проблем является гаммирование данных и использование контекстно-зависимых режимов шифрования.

Классификация блочных шифров

При блочном шифровании информация разбивается на блоки фиксированной длины и шифруется поблочно. Блочные шифры бывают двух основных видов:

шифры перестановки (transposition, permutation, P-блоки);
шифры замены (подстановки, substitution, S-блоки).

Шифры перестановки

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

Шифры замены

Шифры замены заменяют элементы открытых данных на другие элементы по определенному правилу. Paзличают шифры простой, сложной, парной замен

Смешанное шифрование

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

Без обратной связи (ОС). Несколько битов (блок) исходного текста шифруются одновременно, и каждый бит исходного текста влияет на каждый бит шифротекста. Однако взаимного влияния блоков нет, то есть два одинаковых блока исходного текста будут представлены одинаковым шифртекстом. Поэтому подобные алгоритмы можно использовать только для шифрования случайной последовательности битов (например, ключей). Примерами являются DES в режиме ECB и ГОСТ 28147-89 в режиме простой замены.
С обратной связью. Обычно ОС организуется так: предыдущий шифрованный блок складывается по модулю 2 с текущим блоком. В качестве первого блока в цепи ОС используется инициализирующее значение. Ошибка в одном бите влияет на два блока — ошибочный и следующий за ним. Пример — DES в режиме CBC.

При блочном шифровании может также применяться ГПСЧ (генератор псевдослучайных чисел):

Поблочное шифрование потока данных. Шифрование последовательных блоков (подстановки и перестановки) зависит от ГПСЧ, управляемого ключом.
Поблочное шифрование потока данных с ОС. ГПСЧ управляется шифрованным или исходным текстом или обоими вместе.

Объединение блочных шифров

Существует множество способов объединять блочные алгоритмы для получения новых алгоритмов. Стимулом создавать подобные схемы является желание повысить безопасность, не пробираясь через тернии создания нового алгоритма. DES является безопасным алгоритмом, он подвергался криптоанализу добрых 20 лет и, тем не менее, наилучшим способом вскрытия остается грубая сила. Однако ключ слишком короток. Разве не плохо было бы использовать DES в качестве компонента другого алгоритма с более длинным ключом? Это позволило бы получить преимущества длинного ключа с гарантией двух десятилетий криптоанализа.

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

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

Двойное шифрование

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

Если блочный алгоритм образует группу, то всегда существует K₃, для которого

Если алгоритм не образует группу, то при помощи исчерпывающего поиска взломать получающийся дважды зашифрованный блок шифротекста намного сложнее. Вместо 2ⁿ (где n — длина ключа в битах), потребуется 2²ⁿ попыток. Если алгоритм использует 64-битовый ключ, для обнаружения ключей, которыми дважды зашифрован шифротекст, потребуется 2¹²⁸ попыток.

Но при вскрытии с известным открытым текстом это не так. Меркл и Хеллман придумали способ обменять память на время, который позволяет вскрыть такую схему двойного шифрования за 2ⁿ⁺¹ шифрований, а не за 2²ⁿ. (Они использовали эту схему против DES, но результаты можно обобщить на все блочные алгоритмы.)

Это вскрытие называется «встреча посередине»: с одной стороны выполняется шифрование, а с другой — дешифрирование, получившиеся посередине результаты сравниваются.

В этом вскрытии криптоаналитику известны P₁, C₁, P₂ и C₂, такие что

Для каждого возможного K (или K₁, или K₂), криптоаналитик рассчитывает E_K(P₁) и сохраняет результат в памяти. Собрав все результаты, он для каждого K вычисляет D_K(C₁) и ищет в памяти такой же результат. Если такой результат обнаружен, то возможно, что текущий ключ — K₂, а ключ для результата в памяти — K₁. Затем криптоаналитик шифрует P₁с помощью K₁и K₂. Если он получает C₂, то он может гарантировать (с вероятностью успеха 1 к 2²ⁿ^-2^m, где m — размер блока), что он узнал и K₁,и K₂. Если это не так, он продолжает поиск. Максимальное количество попыток шифрования, которое ему, возможно, придется предпринять, равно 2*2ⁿ, или 2ⁿ⁺¹. Если вероятность ошибки слишком велика, он может использовать третий блок шифротекста, обеспечивая вероятность успеха 1 к 2²ⁿ^-3^m. Существуют и другие способы оптимизации.

Для такого вскрытия нужен большой объем памяти: 2ⁿ блоков. Для 56-битового ключа нужно хранить 2⁵⁶ 64-битовых блоков, или 10¹⁷ байтов. Такой объем памяти пока еще трудно себе представить, но этого хватает, чтобы убедить самых параноидальных криптографов в том, что двойным шифрованием пользоваться не стоит.

При 128-битовом ключе для хранения промежуточных результатов потребуется 10³⁹ байтов. Если предположить, что есть способ хранить бит информации, используя единственный атом алюминия, устройство памяти, нужное для выполнения такого вскрытия, будет представлять собой алюминиевый куб с ребром, длиной 1 км. Кроме того, вам понадобится куда-то его поставить! Вскрытие «встреча посередине» кажется невозможным для ключей такого размера.

Многократное последовательное использование блочных алгоритмов

А как насчет шифрования сначала алгоритмом А и ключом К_А, а затем еще раз алгоритмом В и ключом К_В? Может быть у Алисы и Боба различные представления о том, какой алгоритм безопаснее: Алиса хочет пользоваться алгоритмом А, а Боб — алгоритмом В. Этот прием, иногда называемый последовательным использованием (cascading), можно распространить и на большее количество алгоритмов и ключей.

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

Упомянутые предостережения верны, только если различные ключи зависят друг от друга. Если все используемые ключи независимы, то сложность взлома последовательности алгоритмов, по крайней мере, не меньше, чем сложность взлома первого из применяемых алгоритмов.

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

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

Если Алиса и Боб не доверяют алгоритмам друг друга, они могут использовать их последовательно. Для потоковых алгоритмов их порядок не имеет значения. При использовании блочных алгоритмов Алиса может сначала использовать алгоритм A, а затем алгоритм B. Боб, который больше доверяет алгоритму B, может использовать алгоритм B перед алгоритмом A. Между алгоритмами они могут вставить хороший потоковый шифр. Это не причинит вреда и может значительно повысить безопасность.

Ключи для каждого алгоритма последовательности должны быть независимыми. Если алгоритм A использует 64-битовый ключ, а алгоритм B — 128-битовый ключ, то получившаяся последовательность должна использовать 192-битовый ключ. При использовании зависимых ключей у пессимистов гораздо больше шансов оказаться правыми.

Объединение нескольких блочных алгоритмов

Вот другой способ объединить несколько блочных алгоритмов, безопасность которого гарантировано будет, по крайней мере, не меньше, чем безопасность обоих алгоритмов. Для двух алгоритмов (и двух независимых ключей):

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

Этот метод можно расширить для нескольких алгоритмов, но добавление каждого алгоритма увеличивает шифротекст. Сама по себе идея хороша, но не очень практична.

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

Режим гаммирования для поточных шифров

Простейшая реализация поточного шифра изображена на рисунке. Генератор гаммы выдаёт ключевой поток (гамму): . Обозначим поток битов открытого текста . Тогда поток битов шифротекста получается с помощью применения операции XOR: , где .

Расшифрование производится операцией XOR между той же самой гаммой и зашифрованным текстом: .

Очевидно, что если последовательность битов гаммы не имеет периода и выбирается случайно, то взломать шифр невозможно. Но у данного режима шифрования есть и отрицательные особенности. Так ключи, сравнимые по длине с передаваемыми сообщениями, трудно использовать на практике. Поэтому обычно применяют ключ меньшей длины (например, 128 бит). С помощью него генерируется псевдослучайная гаммирующая последовательность ( она должна удовлетворять постулатам Голомба). Естественно, псевдослучайность гаммы может быть использована при атаке на поточный шифр.

Классификация поточных шифров

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

Синхронные поточные шифры

Определение:

Синхронные поточные шифры (СПШ) — шифры, в которых поток ключей генерируется независимо от открытого текста и шифротекста.

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

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

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

Плюсы СПШ:

отсутствие эффекта распространения ошибок (только искажённый бит будет расшифрован неверно);
предохраняют от любых вставок и удалений шифротекста, так как они приведут к потере синхронизации и будут обнаружены.

Минусы СПШ:

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

Самосинхронизирующиеся поточные шифры

Основная идея построения была запатентована в 1946 г. в США.
Определение:
Самосинхронизирующиеся поточные шифры (асинхронные поточные шифры (АПШ)) – шифры, в которых поток ключей создаётся функцией ключа и фиксированного числа знаков шифротекста.

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

Плюсы АПШ:

Размешивание статистики открытого текста. Так как каждый знак открытого текста влияет на следующий шифротекст, статистические свойства открытого текста распространяются на весь шифротекст. Следовательно, АПШ может быть более устойчивым к атакам на основе избыточности открытого текста, чем СПШ.

Минусы АПШ:

распространение ошибки (каждому неправильному биту шифротекста соответствуют N ошибок в открытом тексте);
чувствительны к вскрытию повторной передачей.

Поточные шифры на регистрах сдвига с линейной обратной связью (РСЛОС)

Теоретическая основа

Есть несколько причин использования линейных регистров сдвига в криптографии:

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

Определение: Регистр сдвига с линейной обратной связью длины L состоит из L ячеек пронумерованных ,каждая из которых способна хранить 1 бит и имеет один вход и один выход; и синхросигнала (clock), который контролирует смещение данных. В течение каждой единицы времени выполняются следующие операции:

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

Регистр сдвига с линейной обратной связью.

На первом шаге:

На втором шаге:

Следующее соотношение описывает в общем виде работу РСЛОС:

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

Обозначим: . Тогда:

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

Пример.

Пример: Возьмём неприводимый примитивный многочлен Этот многочлен можно записать, как – выписаны степени, при которых стоят ненулевые коэффициенты.
Запишем в исходном состоянии в ячейки и определим длину периода генератора:

Таблица. Определение периода генератора
Обратная связь	Ячейка0	Ячейка1	Ячейка2
1	0	0	1
0	1	0	0
1	0	1	0
1	1	0	1
1	1	1	0
0	1	1	1
0	0	1	1
1	0	0	1

Период генератора равен На выходе генератора буде последовательность:
Приведём примеры некоторых примитивных многочленов по модулю 2:

Линейная сложность

Линейная сложность бинарной последовательности – одна из самых важных характеристик работы РСЛОС. Поэтому остановимся на этой теме поподробнее.
Прежде чем дать определение линейной сложности введём некоторые обозначения.
— бесконечная последовательность с членами
– конечная последовательность длины , членами которой являются
Говорят, что РСЛОС генерирует последовательность , если существует некоторое исходное состояние, при котором выходная последовательность РСЛОС совпадает с . Аналогично, говорят, что РСЛОС генерирует конечную последовательность , если существует некоторое начальное состояние, для которого выходная последовательность РСЛОС имеет в качестве первых n членов члены последовательности .
Наконец дадим определение линейной сложности бесконечной двоичной последовательности.
Определение: Линейной сложностью бесконечной двоичной последовательности называется число , которое определяется следующим образом:

Если – нулевая последовательность , то
Если не существует РСЛОС, который генерирует , то равно бесконечности.
Иначе, есть длина самого короткого РСЛОС, который генерирует .

Определение:
Линейной сложностью конечной двоичной последовательности называется число , которое равно длине самого короткого РСЛОС, который генерирует последовательность, имеющую в качестве первых членов .
Свойства линейной сложности: Пусть и – двоичные последовательности. Тогда:
1. Для любого 0″ style=»width:35.25pt; height:10.5pt;visibility:visible;mso-wrap-style:square»> 0″> линейная сложность подпоследовательности удовлетворяет неравенствам
2. тогда и только тогда, когда – нулевая последовательность длины .
3. тогда и только тогда, когда .
4. Если – периодическая с периодом , тогда
5.
Эффективным алгоритмом определения линейной сложности конечной двоичной последовательности является алгоритм Берлекемпа-Месси.

А5 — это поточный алгоритм шифрования, используемый для обеспечения конфиденциальности передаваемых данных между телефоном и базовой станцией в европейской системе мобильной цифровой связи GSM (Group Special Mobile).

Шифр основан на побитовом сложении по модулю два (булева операция XOR) генерируемой псевдослучайной последовательности и шифруемой информации. В A5 псевдослучайная последовательность реализуется на основе трёх линейных регистров сдвига с обратной связью. Регистры имеют длины 19, 22 и 23 бита соответственно. Сдвигами управляет специальная схема, организующая на каждом шаге смещение как минимум двух регистров, что приводит к их неравномерному движению. Последовательность формируется путём операции XOR над выходными битами регистров.

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

Давайте рассмотрим проблему создания случайных и псевдослучайных чисел более детально. Наиболее часто в прикладных задачах результат формируют из счетчика тиков – системных часов. В этом случае данные о текущем часе несут примерно 16 бит информации, значение счетчика тиков – еще 16 бит. Это дает нам 32 бита информации – как вы помните, на сегодняшний день границей стойкой криптографии является значение в 40 бит, при реальных длинах ключей в 128 бит. Естественно, подобного метода крайне недостаточно. Идем дальше, к 32 битам можно добавить еще 16 бит из сверхбыстрого таймера, работающего на частоте 1,2 МГц в компьютерах архитектуры IBM PC AT и этого еще недостаточно. Кроме того, даже если мы сможем набрать длину ключа в 128 бит (что очень сомнительно), она будет нести псевдослучайный характер, поскольку основана на состоянии только лишь данной ЭВМ на момент начала шифрования. Источниками по-настоящему случайных величин могут быть только внешние объекты, например, человек.

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

По первому методу над самими введенными значениями производятся действия, повышающие случайность выходного потока. Так, например, обязательно удаляются верхние 3 бита введенного ASCII символа, часто удаляются еще один верхний и еще один нижний биты. Затем, объем полученной последовательности уменьшается еще в три раза наложением первого и второго бита на третий операцией XOR. Это, в принципе, генерирует достаточно случайную последовательность бит.

По второму методу на введенные символы алгоритм не обращает никакого внимания, зато конспектирует интервалы времени, через которые произошли нажатия. Запись моментов производится по отсчетам быстрого системного таймера (частота 1,2 МГц) или внутреннему счетчику процессора, появившемуся в процессорах, начиная с Intel Pentium (частота соответствует частоте процессора). Так как верхние и младшие биты имеют определенную корреляцию между символами (первые из-за физических характеристик человека, вторые из-за особенностей операционной системы), то они отбрасываются (обычно удаляются 0-8 старших бита и 4-10 младших).

Как более редко встречающиеся варианты можно встретить 1) комбинацию обоих клавиатурных методов и 2) метод, основанный на манипуляторе «мышь» — он выделяет случайную информацию из смещений пользователем указателя мыши.

В мощных криптосистемах военного применения используются действительно случайные генераторы чисел, основанные на физических процессах. Они представляют собой платы, либо внешние устройства, подключаемые к ЭВМ через порт ввода-вывода. Два основных источника белого Гауссовского шума – высокоточное измерение тепловых флуктуаций и запись радиоэфира на частоте, свободной от радиовещания.

Криптографическая система с открытым ключом (или Асимметричное шифрование, Асимметричный шифр) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ.^[1] Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

Схема шифрования с открытым ключом

Пусть K — пространство ключей, а e и d — ключи шифрования и расшифрования соответственно. E_e — функция шифрования для произвольного ключа e K, такая что:

E_e(m) = c

Здесь c C, где C — пространство шифротекстов, а m M, где M — пространство сообщений.

D_d — функция расшифрования, с помощью которой можно найти исходное сообщение m, зная шифротекст c :

D_d(c) = m

{E_e: e K} — набор шифрования, а {D_d: d K} — соответствующий набор для расшифрования. Каждая пара (E,D) имеет свойство: зная E_e, невозможно решить уравнение E_e(m) = c, то есть для данного произвольного шифротекста c C, невозможно найти сообщение m M. Это значит, что по данному e невозможно определить соответствующий ключ расшифрования d. E_e является односторонней функцией, а d — лазейкой.^[3]

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

Боб выбирает пару (e,d) и шлёт ключ шифрования e (открытый ключ) Алисе по открытому каналу, а ключ расшифрования d (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу, либо его подлинность должна быть гарантирована некоторым сертифицирующим органом).
Чтобы послать сообщение m Бобу, Алиса применяет функцию шифрования, определённую открытым ключом e: E_e(m) = c, c — полученный шифротекст.
Боб расшифровывает шифротекст c, применяя обратное преобразование D_d, однозначно определённое значением d.

Основные принципы построения криптосистем с открытым ключом

Начинаем с трудной задачи P. Она должна решаться сложно в смысле теории: не должно быть алгоритма, с помощью которого можно было бы перебрать все варианты решения задачи P за полиномиальное время относительно размера задачи. Более правильно сказать: не должно быть известного полиномиального алгоритма, решающего данную задачу — так как ни для одной задачи ещё пока не доказано, что для неё подходящего алгоритма нет в принципе.
Можно выделить легкую подзадачу P‘ из P. Она должна решаться за полиномиальное время, лучше, если за линейное.
«Перетасовываем и взбалтываем» P‘, чтобы получить задачу P», совершенно не похожую на первоначальную. Задача P», по крайней мере, должна выглядеть как оригинальная труднорешаемая задача P.
P» открывается с описанием, как она может быть использована в роли ключа зашифрования. Как из P» получить P‘, держится в секрете как секретная лазейка.
Криптосистема организована так, что алгоритмы расшифрования для легального пользователя и криптоаналитика существенно различны. В то время как второй решает P» задачу, первый использует секретную лазейку и решает P‘ задачу.

RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом.

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

Описание алгоритма

Введение

Криптографические системы с открытым ключом используют так называемые необратимые функции, которые обладают следующим свойством:

Если известно , то вычислить относительно просто
Если известно , то для вычисления нет простого (эффективного) пути.

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

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

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и секретным ключом (англ. secret key). Каждый ключ — это часть информации. В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и секретный ключ самостоятельно. Секретный ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и секретный ключи каждого участника обмена сообщениями образуют «согласованную пару» в том смысле, что они являются взаимно обратными, т.е

 сообщения 

, где 

 — множество допустимых сообщений.

 открытого и секретного ключа 

 и

 соответствующие функции шифрования 

 и расшифрования

Алгоритм создания открытого и секретного ключей

RSA-ключи генерируются следующим образом:^[4]

Выбираются два случайных простых числа p и q заданного размера (например, 1024 бита каждое).
Вычисляется их произведение n = pq, которое называется модулем.
Вычисляется значение функции Эйлера от числа n:

Выбирается целое число e ( ), взаимно простое со значением функции . Обычно в качестве e берут простые числа, содержащие небольшое количество единичных битов в двоичной записи, например, простые числа Ферма 17, 257, или 65537.
- Число e называется открытой экспонентой (англ. public exponent)
- Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в e.
- Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA.^[5]
Вычисляется число d, мультипликативно обратное к числу e по модулю , то есть число, удовлетворяющее условию:

или: , где k — некоторое целое число.

- Число d называется секретной экспонентой.
- Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
Пара P = (e,n) публикуется в качестве открытого ключа RSA (англ. RSA public key).
Пара S = (d,n) играет роль секретного ключа RSA (англ. RSA private key) и держится в секрете.

Шифрование и расшифрование

Схема RSA

Предположим, сторона хочет послать стороне сообщение .

Сообщением являются целые числа лежащие от до , т.е .

Алгоритм:^[4]

Взять открытый ключ стороны
Взять открытый текст
Передать шифрованное сообщение:

Алгоритм:

Принять зашифрованное сообщение
Применить свой секретный ключ для расшифровки сообщения:

Корректность схемы RSA

Уравнения и , на которых основана схема RSA, определяют взаимно обратные преобразования множества

Криптоанализ алгоритмов с открытым ключом

Казалось бы, что криптосистема с открытым ключом — идеальная система, не требующая безопасного канала для передачи ключа шифрования. Это подразумевало бы, что два легальных пользователя могли бы общаться по открытому каналу, не встречаясь, чтобы обменяться ключами. К сожалению, это не так. Рисунок иллюстрирует, как Ева, выполняющая роль активного перехватчика, может захватить систему (расшифровать сообщение, предназначенное Бобу) без взламывания системы шифрования.

В этой модели Ева перехватывает открытый ключ e, посланный Бобом Алисе. Затем создает пару ключей e’ и d’, «маскируется» под Боба, посылая Алисе открытый ключ e’, который, как думает Алиса, открытый ключ, посланный ей Бобом. Ева перехватывает зашифрованные сообщения от Алисы к Бобу, расшифровывает их с помощью секретного ключа d’, заново зашифровывает открытым ключом e Боба и отправляет сообщение Бобу. Таким образом, никто из участников не догадывается, что есть третье лицо, которое может как просто перехватить сообщение m, так и подменить его на ложное сообщение m‘. Это подчеркивает необходимость аутентификации открытых ключей. Для этого обычно используют сертификаты. Распределённое управление ключами в PGP решает возникшую проблему с помощью поручителей.^[5]

Еще одна форма атаки — вычисление закрытого ключа, зная открытый (рисунок ниже). Криптоаналитик знает алгоритм шифрования E_e, анализируя его, пытается найти D_d. Этот процесс упрощается, если криптоаналитик перехватил несколько криптотекстов с, посланных лицом A лицу B.

Большинство криптосистем с открытым ключом основаны на проблеме факторизации больших чисел. К примеру, RSA использует в качестве открытого ключа n произведение двух больших чисел. Сложность взлома такого алгоритма состоит в трудности разложения числа n на множители. Но эту задачу решить реально. И с каждым годом процесс разложения становится все быстрее. Ниже приведены данные разложения на множители с помощью алгоритма «Квадратичное решето».

Год	Число десятичных разрядов в разложенном числе	Во сколько раз сложнее разложить на множители 512-битовое число
1983	71	> 20 000 000
1985	80	> 2 000 000
1988	90	250 000
1989	100	30 000
1993	120	500
1994	129	100

Также задачу разложения потенциально можно решить с помощью Алгоритма Шора при использовании достаточно мощного квантового компьютера.

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

Аутентифика́ция (англ. Authentication) — проверка принадлежности субъекту доступа предъявленного им идентификатора; подтверждение подлинности.

Аутентификацию не следует путать с идентификацией и авторизацией

Аутентификация на основе паролей

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

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

Существует несколько способов получения секретного пароля в сети. Пользователь С может использовать программу-анализатор, или сниффер. Программы-анализаторы легко доступны в Интернете, они позволяют перехватывать сетевой трафик между компьютерами одной локальной сети. Для перехвата пароля пользователю С можно даже не находиться в одном помещении с пользователем А и не иметь доступ к его компьютеру — ему достаточно лишь сетевого подключения к той же самой локальной сети. Эти программы настолько упрощают перехват информации, что хищение пароля часто называют атакой анализатора [64]. После смены пароль остается неизвестен пользователю С только до очередного запуска программы-анализатора. Если пользователь С постоянно запускает свою программу-анализатор, то получает новый пароль пользователя А, как только он выбран.

Некоторые типы локальных сетей более уязвимы для атак анализатора. Особенно это касается тех, которые, как многоканальная сеть Ethernet, используют широковещательную среду. Сети, подобные коммутируемой сети Ethernet, не столь восприимчивы. Концентратор передает трафик только по проводам, соединяющим связывающиеся компьютеры. В этом случае, чтобы получить ту же самую информацию, пользователь С сталкивается с более трудной задачей: инсталлировать программу-анализатор на компьютер пользователя А.

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

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

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

Эволюция механизмов аутентификации началась в ответ на атаки анализаторов. Очевидно, что должна была появиться защита от этих атак в виде шифрования. Шифрование предотвращает раскрытие пароля при передаче. Но если все пользователи используют один и тот же ключ шифрования, то любой из них может использовать анализатор, получить чужой пароль и расшифровать его тем же способом, что и сервер. Если каждый пользователь имеет свой ключ, то управление этими ключами обеспечивает более сильную аутентификацию, чем пароли. Следует отметить, что пользователь А защищен и в том случае, если его пароль используется однократно. Удачная атака анализатора позволяет пользователю С получить устаревший пароль А. Ясно, что пользователю А в этом случае необходим новый пароль для каждой попытки аутентификации.

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

Тип	Описание
Пароли или PIN-коды (персональные идентификационные номера)	Что-то, что знает пользователь и что также знает другой участник взаимодействия. Обычно аутентификация производится в 2 этапа. Может организовываться обмен паролями для взаимной аутентификации.
Одноразовый пароль	Пароль, который никогда больше не используется. Часто используется постоянно меняющееся значение, которое базируется на постоянном пароле.
CHAP (протокол аутентификации запрос-ответ)	Одна из сторон инициирует аутентификацию с помощью посылки уникального и непредсказуемого значения «запрос» другой стороне, а другая сторона посылает вычисленный с помощью «запроса» и секрета ответ. Так как обе стороны владеют секретом, то первая сторона может проверить правильность ответа второй стороны.
Встречная проверка (Callback)	Телефонный звонок серверу и указание имени пользователя приводит к тому, что сервер затем сам звонит по номеру, который указан для этого имени пользователя в его конфигурационных данных.

Как показано на рис. 2.2, сервер генерирует случайный запрос и отправляет его пользователю А [208]. Вместо того чтобы в ответ отправить серверу пароль, пользователь А шифрует запрос при помощи ключа, известного только ему самому и серверу. Сервер выполняет такое же шифрование и сравнивает результат с шифртекстом, полученным от пользователя А. Если они совпадают, то аутентификация прошла успешно, в противном случае — неудачно.

Этот простой механизм имеет несколько преимуществ по сравнению с простой аутентификацией при помощи паролей. Поскольку запрос генерируется случайным образом, пользователь С не может повторно использовать шифртекст, сгенерированный пользователем А, чтобы выдавать себя за него. Значение, которое отправляет пользователь А, аутентифицирует его идентичность только один раз. Имя пользователя А передается открыто, и нет причин его скрывать. Перехват информации больше не является угрозой, и пользователь А может выполнять аутентификацию на удаленном сервере в открытой сети.
Рис. 2.2. Аутентификация «запрос-ответ»

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

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

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

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

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

Тип	Комментарии
DSA (Digital Signature Authorization)	Алгоритм с использованием открытого ключа для создания электронной подписи, но не для шифрования. Секретное создание хэш-значения и публичная проверка ее — только один человек может создать хэш-значение сообщения, но любой может проверить ее корректность. Основан на вычислительной сложности взятия логарифмов в конечных полях.
RSA	Запатентованная RSA электронная подпись, которая позволяет проверить целостность сообщения и личность лица, создавшего электронную подпись. Отправитель создает хэш-функцию сообщения, а затем шифрует ее с использованием своего секретного ключа. Получатель использует открытый ключ отправителя для расшифровки хэша, сам рассчитывает хэш для сообщения, и сравнивает эти два хэша.
MAC (код аутентификации сообщения)	Электронная подпись, использующая схемы хэширования, аналогичные MD или SHA, но хэш-значение вычисляется с использованием как данных сообщения, так и секретного ключа.
DTS (служба электронных временных меток)	Выдает пользователям временные метки, связанные с данными документа, криптографически стойким образом.

Хеширование (иногда хэширование, англ. hashing) — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения (англ. message digest).

Хеширование применяется для сравнения данных: если у двух массивов хеш-коды разные, массивы гарантированно различаются; если одинаковые — массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов входного массива; существует множество массивов, дающих одинаковые хеш-коды — так называемые коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

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

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

Среди множества существующих хеш-функций принято выделять криптографически стойкие, применяемые в криптографии. Для того, чтобы хеш-функция H считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хеш-функций в криптографии:

Необратимость: для заданного значения хеш-функции m должно быть вычислительно неосуществимо найти блок данных X, для которого H(X) = m.
Стойкость к коллизиям первого рода: для заданного сообщения M должно быть вычислительно неосуществимо подобрать другое сообщение N, для которого H(N) = H(M).
Стойкость к коллизиям второго рода: должно быть вычислительно неосуществимо подобрать пару сообщений , имеющих одинаковый хеш.

Данные требования не являются независимыми:

Обратимая функция нестойка к коллизиям первого и второго рода.
Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

Атака «дней рождения» позволяет находить коллизии для хеш-функции с длиной значений n битов в среднем за примерно 2ⁿ^{/ 2} вычислений хеш-функции. Поэтому n-битная хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к 2ⁿ^{/ 2}.

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

Требования

Для того, чтобы хеш-функция H считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хеш-функций в криптографии:

Необратимость или стойкость к восстановлению прообраза: для заданного значения хеш-функции m должно быть вычислительно невозможно найти блок данных X, для которого H(X) = m.
Стойкость к коллизиям первого рода или восстановлению вторых прообразов: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N, для которого H(N) = H(M).
Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений , имеющих одинаковый хеш.

Данные требования не являются независимыми:

Обратимая функция нестойка к коллизиям первого и второго рода.
Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

Применения

Электронная цифровая подпись

Электронная цифровая подпись(ЭЦП)— по сути шифрование сообщения алгоритмом с открытым ключом. Текст, зашифрованный секретным ключом, объединяется с исходным сообщением. Тогда проверка подписи – расшифрование открытым ключом, если получившийся текст аналогичен исходному тексту – подпись верна.

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

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

Проверка парольной фразы

В большинстве случаев парольные фразы не хранятся на целевых объектах, хранятся лишь их хеш-значения. Хранить парольные фразы нецелесообразно, так как в случае несанкционированного доступа к файлу с фразами злоумышленник узнает все парольные фразы и сразу сможет ими воспользоваться, а при хранении хеш-значений он узнает лишь хеш-значения, которые не обратимы в исходные данные, в данном случае в парольную фразу. В ходе процедуры аутентификации вычисляется хеш-значение введённой парольной фразы, и сравнивается с сохранённым.

Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows XP. В них хранятся лишь хеш-значения парольных фраз из учётных записей пользователей.

Данная система подразумевает передачу сообщения по защищенному каналу, то есть каналу, из которого криптоаналитику невозможно перехватить сообщения или послать свое. Иначе он может перехватить хеш-значение парольной фразы, и использовать его для дальнейшей нелегальной аутентификации. Защищаться от подобных атак можно при помощи метода «тройного рукопожатия».

Пусть некий клиент, с именем name, производит аутентификацию по парольной фразе, pass, на некоем сервере. На сервере хранится значение хеш-функции H(pass,R2), где R2 — псевдослучайное, заранее выбранное, число. Клиент посылает запрос (name, R1), где R1 – псевдослучайное, каждый раз новое, число. В ответ сервер посылает значение R2. Клиент вычисляет значение хеш-функции H(R1,H(pass,R2)) и посылает его на сервер. Сервер также вычисляет значение H(R1,H(pass,R2)) и сверяет его с полученным. Если значения совпадают – аутентификация верна.

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

Обзор алгоритмов ЭЦП

Технология применения системы электронной цифровой подписи (ЭЦП) предполагает наличие сети абонентов, посылающих друг другу подписанные электронные документы. Для каждого абонента генерируется пара ключей: секретный и открытый. Секретный ключ хранится абонентом в тайне и используется им для формирования ЭЦП. Открытый ключ известен всем другим пользователям и предназначен для проверки ЭЦП получателем подписанного электронного документа. Иначе говоря, открытый ключ является необходимым инструментом, позволяющим проверить подлинность электронного документа и автора подписи. Открытый ключ не позволяет вычислить секретный ключ [1].

Для генерации пары ключей (секретного и открытого) в алгоритмах ЭЦП, используются разные математические схемы, основанные на применении однонаправленных функций. Эти схемы разделяются на две группы. В основе такого разделения лежат известные сложные вычислительные задачи:

задача факторизации (разложения на множители) больших целых чисел;
задача дискретного логарифмирования.

Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США. Алгоритм получил свое название по первым буквам фамилий его авторов: Rivest, Shamir и Adleman. Надежность алгоритма основывается на трудности факторизации больших чисел.

Более надежный и удобный для реализации на персональных компьютерах ЭЦП алгоритм был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем и получил название El Gamal Signature Algorithm (EGSA).

Идея EGSA основана на том, что для обоснования практической невозможности фальсификации ЭЦП может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа – задача дискретного логарифмирования. Кроме того Эль Гамалю удалось избежать явной слабости алгоритма ЭЦП RSA, связанной с возможностью подделки ЭЦП под некоторыми сообщениями без определения секретного ключа.

Алгоритм цифровой подписи Digital Signature Algorithm (DSA) предложен в 1991г. в США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритма ЭЦП EGSA. По сравнению с алгоритмом ЭЦП EGSA алгоритм DSA имеет ряд преимуществ: сокращен объем памяти и время вычисления подписи. Недостатком же является необходимость при подписывании и проверке подписи выполнять сложные операции деления по модулю большого числа.

Российский стандарт цифровой подписи обозначается как ГОСТ Р 34.10-94. Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA. Различие между этими стандартами заключается в использовании параметров ЭЦП разного порядка, что приводит к получению более безопасной подписи при использовании российского стандарта.

Алгоритмы цифровых подписей Elliptic Curve Digital Signature Algorithm (ECDSA) и ГОСТ Р 34.10-2001 являются усовершенствованием цифровых подписей DSA и ГОСТ Р 34.10-94 соответственно. Эти алгоритмы построены на базе математического аппарата эллиптических кривых над простым полем Галуа.

ГОСТ Р 34.10-94

1. ОБЛАСТЬ ПРИМЕНЕНИЯ

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

Внедрение системы ЭЦП на базе настоящего стандарта обеспечивает

защиту передаваемых сообщений то подделки, искажения и однозначно по-

зволяет доказательно подтвердить подпись лица, подписавшего сообщение.

Издание официальное

ГОСТ Р 34.10-94

2. НОРМАТИВНЫЕ ССЫЛКИ

В настоящем стандарте использованы ссылки на следующий стандарт:

ГОСТ Р 34.11-94 Информационная технология. Криптографическая защита информации. Функция хеширования.

4. ОБЩИЕ ПОЛОЖЕНИЯ

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

Алгоритмы вычисления функции хэширования установлен в ГОСТ Р 34.11.

Процедуры цифровой подписи допускают как программную, так и аппаратную реализацию.

Система ЭЦП включает в себя процедуры выработки и проверки подписи под данных сообщением.

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

ГОСТ Р 34.10-94

Числа р, q и а, являющиеся параметрами системы, должны быть выбраны (выработаны) по процедуре, описанной в пункте 7.

Числа р, q и а не являются секретными. Конкретный набор их значений может быть общим для группы пользователей. Целое чис-

ло k, которое генерируется в процедуре подписи сообщения , должно

быть секретным и должно быть уничтожено сразу после выработки

подписи. Число k снимается с физического датчика случайных чисел

или вырабатывается псевдослучайным методом с использованием

секретных параметров.

5. ПРОЦЕДУРА ВЫРАБОТКИ ПОДПИСИ

Текст сообщения, представленный в виде двоичной последова-

тельности символов, подвергается обработке по определенному ал-

горитму, в результате которого формируется ЭЦП для данного сооб-

щения.

Процедура подписи сообщения включает в себя следующие этапы:

1. Вычислить h(M) -значение хеш-функции h от сообщения М.

Если h(M)(mod q)=0, присвоить h(M) значение 0²⁵⁵ 1.

2. Выработать целое число k, 0<k < q.

3. Вычислить два значения :

r=a^k (mod p) и r’ = r (mod q).

Если r’ =0, перейти к этапу 2 и выработать другое значение числа k.

4. С использованием секретного ключа х пользователя (отправиетля

сообщения) вычислить значение

s= (xr’ + kh(M))(mod q).

Если s=0, перейти к этапу 2, в противном случае закончить работу алгоритма.

Подписью сообщения М является вектор < r’ >₂₅₆ ½½ < s >₂₅₆ .

ГОСТ Р 34.10-94

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

6. ПРОЦЕДУРА ПРОВЕРКИ ПОДПИСИ

Получатель должен проверить подлинность сообщения и подлинность ЭЦП, осуществляя ряд операций (вычислений).

Это возможно при наличии у получателя открытого ключа отправи-

теля, пославшего сообщение,

Процедура проверки включает в себя следующие этапы:

1. Проверить условие:

0< s < q и 0 < r’ < q.

Если хотя бы одно из этих условий не выполнено, то подпись считается недействительной.

2. Вычислять h(M₁ )-значение хеш-функции h от полученного сообщения М₁ .

Если H(M₁ )(mod q)=0, присвоить h(M₁ ) значение 0²⁵⁵ 1.

3. Вычислить значение

v= (h(M₁ ))^q-2 (mod q)

4. Вычислить значения:

z₁ = sv (mod q) и

z₂ = (q-r’ ) v (mod q)

5. Вычислить значение

u = (a^s1 y^s2 (mod p)) (mod q)

6. Проверить условие: r’ = u.

ГОСТ Р 34.10-94

При совпадении значений r и u получатель принимает решение о том, что полученное сообщение подписано данным отправителем и

в процессе передачи не нарушена целостность сообщения, т.е. М =М

В противном случае подпись считается недействительной.

Подделка подписей

Анализ возможностей подделки подписей называется криптоанализ. Попытку сфальсифицировать подпись или подписанный документ криптоаналитики называют «атака».

Модели атак и их возможные результаты

В своей работе Гольдвассер, Микали и Ривест описывают следующие модели атак, которые актуальны и в настоящее время^[5]:

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

Также в работе описана классификация возможных результатов атак:

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

Ясно, что самой «опасной» атакой является адаптивная атака на основе выбранных сообщений, и при анализе алгоритмов ЭЦП на криптостойкость нужно рассматривать именно ее (если нет каких-либо особых условий).

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

Подделка документа (коллизия первого рода)

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

Документ представляет из себя осмысленный текст.
Текст документа оформлен по установленной форме.
Документы редко оформляют в виде Plain Text — файла, чаще всего в формате DOC или HTML.

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

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

Впрочем, во многих структурированных наборах данных можно вставить произвольные данные в некоторые служебные поля, не изменив вид документа для пользователя. Именно этим пользуются злоумышленники, подделывая документы.

Вероятность подобного происшествия также ничтожно мала. Можно считать, что на практике такого случиться не может даже с ненадёжными хеш-функциями, так как документы обычно большого объёма — килобайты.

Получение двух документов с одинаковой подписью (коллизия второго рода)

Куда более вероятна атака второго рода. В этом случае злоумышленник фабрикует два документа с одинаковой подписью, и в нужный момент подменяет один другим. При использовании надёжной хэш-функции такая атака должна быть также вычислительно сложной. Однако эти угрозы могут реализоваться из-за слабостей конкретных алгоритмов хэширования, подписи, или ошибок в их реализациях. В частности, таким образом можно провести атаку на SSL-сертификаты и алгоритм хеширования MD5.^[11]

Социальные атаки

Социальные атаки направлены не на взлом алгоритмов цифровой подписи, а на манипуляции с открытым и закрытым ключами^[12].

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

Использование протоколов обмена ключами и защита закрытого ключа от несанкционированного доступа позволяет снизить опасность социальных атак.

На 2009 год система шифрования на основе RSA считается надёжной, начиная с размера в 1024 бита.

Группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит.^[6] По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года. ^[7]

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

На первый шаг (выбор пары полиномов степени 6 и 1) было потрачено около полугода вычислений на 80 процессорах, что составило около 3 % времени, потраченного на главный этап алгоритма (просеивание), который выполнялся на сотнях компьютеров в течение почти двух лет. Если интерполировать это время на работу одного процессора AMD Opteron 2.2ГГц с 2Гб памяти, то получилось бы порядка 1500 лет. Обработка данных после просеивания для следующего ресурсоёмкого шага (линейной алгебры) потребовалось несколько недель на малом количестве процессоров. Заключительный шаг после нахождения нетривиальных решений ОСЛУ занял не более 12 часов.

Решение ОСЛУ проводилось с помощью метода Видемана на нескольких раздельных кластерах и длилось чуть менее 4 месяцев. При этом размер разреженной матрицы составил 192 796 550х192 795 550 при наличии 27 795 115 920 ненулевых элементов (то есть в среднем 144 ненулевых элементов на строку). Для хранения матрицы на жёстком диске понадобилось около 105 гигабайт. В то же время понадобилось около 5 терабайт сжатых данных для построения данной матрицы.

В итоге группе удалось вычислить 232-цифровой ключ, открывающий доступ к зашифрованным данным.

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

Зная разложение модуля на произведение двух простых чисел, противник может легко найти секретную экспоненту и тем самым взломать RSA. Однако на сегодняшний день самый быстрый алгоритм факторизации — решето обобщённого числового поля (General Number Field Sieve), скорость которого для k-битного целого числа составляет

для некоторого ,

не позволяет разложить большое целое за приемлемое время. Будем рассматривать возможные атаки на RSA, которые позволяют взломать эту систему, не используя прямого разложения модуля n на произведение двух простых чисел.

Элементарные атаки

Рассмотрим несколько атак связанных с неправильным использованием алгоритма RSA.

Генерация простых чисел

На случайные простые числа и накладываются следующие дополнительные ограничения:

и не должны быть слишком близки друг к другу, иначе можно будет их найти, используя метод факторизации Ферма. Однако, если оба простых числа и были сгенерированы независимо, то это ограничение с огромной вероятностью автоматически выполняется.
Необходимо выбирать «сильные» простые числа, чтобы нельзя было воспользоваться p-1 методом Полларда

Метод факторизации Ферма натурального нечетного числа n состоит в поиске таких целых чисел x и y, что x² − y² = n, что ведет к разложению .

Метод быстро работает, если n является произведением двух близких к друг другу сомножителей. В частности, именно поэтому в RSA требуют, чтобы разность между секретными простыми сомножителями модуля была велика.

Описание

Для разложения на множители нечетного числа n ищутся два числа x и y такие, что x² − y² = n, или . При этом числа (x + y) и (x − y) являются множителями n, возможно, тривиальными (т.е. одно из них равно 1, а другое — n.)

Равенство x² − y² = n равносильно x² − n = y², т. е. тому, что x² − n является квадратом. Поиск квадрата такого вида начинается с — наименьшего числа, при котором разность x² − n неотрицательна. Для каждого значения x вычисляют x² − n и проверяют, не является ли это число точным квадратом. Если нет, x увеличивают на единицу, иначе получено разложение

Если оно является тривиальным, то n — простое.

Схема с общим модулем n

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

Задача: противник хочет расшифровать сообщение стороны .

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

Защита: для каждого пользователя должен использоваться свой модуль .

Атака на подпись RSA в схеме с нотариусом

Начальные данные: — открытый ключ нотариуса. Противник получает отказ при попытке подписания нотариусом сообщения

Задача: противник хочет получить подпись нотариуса на сообщении .

Противник выбирает произвольное вычисляет и отправляет это сообщение на подпись нотариусу.

Если нотариус подписывает это сообщение:

то противник, вычислив , получает подпись сообщения .

Действительно,

Защита: при подписи добавлять в сообщение некоторое случайное число (например, время).

Основные принципы построения стегосистем:

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

Далее будем использовать слово «сообщение», так как сообщением может быть как текст или изображение, так и, например, аудиоданные. Для обозначения скрываемой информации, будем использовать именно термин сообщение.

Как и в криптографии, по типу стегоключа стегосистемы можно подразделить на два типа:

В стегосистеме с секретным ключом используется один ключ, который

должен быть определен либо до начала обмена секретными сообщениями, либо передан по защищенному каналу.

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

Сам Процесс стеганографии можно разделить на несколько этапов.

1. Выбор информационного файла.

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

2. Выбор файла-контейнера.

Вторым этапом в процессе стеганографии является выбор файла, используемый для сокрытия информации. Его ещё называют файлом-контейнером. В большинстве известных программ по стеганографии говорится, что для сокрытия информации, объём памяти файла-контейнера должен где-то в восемь раз превышать объём памяти информационного файла. Следовательно, чтобы спрятать файл размером 710КБ, понадобится графика объёмом 5600КБ.

3. Выбор стеганографической программы.

(В данной работе рассмотрен пример работы с программным продуктом Masker 7.0)

4. Кодирование файла.

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

5. Отправление сокрытого сообщения по электронной почте и его декодирование.

Пятым и последним этапом в процессе стеганографии является отправление спрятанного файла по электронной почте и его последующая расшифровка.

После краткой технической характеристики использования методов компьютерной стеганографии возникает вопрос: насколько лёгким или сложным является этот процесс? В Интернете можно найти большое количество платных и бесплатных стеганографических программ. Какова вероятность использования одной из них, либо какой-нибудь другой в преступных целях? Какую роль будет выполнять процесс стеганографии в киберпреступном мире?

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

Фактический процесс по сокрытию одного файла в другом относительно лёгкий. Сжатие видео, увеличение графического изображения, анализ программ по стеганографии – под силу даже неподготовленному пользователю.

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

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

PGP (Pretty Good Privacy) — программа, служащая для кодирования и/или подписывания сообщений, файлов и любой другой информации, представленной в электронном виде. В основе работы PGP лежит алгоритм RSA (Rivest-Shamir-Adelman), основанный на наличии двух ключей — открытого и секретного. Открытый ключ распространяется максимальному кол-ву людей (через KeyServer’а, лично, и т.п.), а секретный должен находиться только у владельца (причем в надежном месте, если к компьютеру на котором Вы работаете, имеют доступ другие люди — храните свой секретный ключ на дискете).
Криптостойкость алгоритма RSA основывается на том, что современной математике не известны алгоритмы разложения больших простых (рекомендую использовать ключи не менее 1024 бит) чисел за реальное время.

Итак, Вы хотите передать мне какой-либо файл по электронной почте и при этом быть уверенным, что никто другой кроме меня не сможет прочитать этот файл — Вы берете мой открытый ключ, кодируете им свой файл и отправляете файл мне. Никто кроме меня (включая Вас) не сможет прочитать этот закодированный файл без моего секретного ключа. Другой пример — Вы хотите, отправляя свои письма быть уверенным в том, что никто не исказил содержимого письма, для этого Вы подписываете письмо электронной подписью с помощью Вашего секретного ключа и посылаете его (письмо). Получив Ваше письмо и обладая Вашим открытым ключом я могу удостовериться в том, что ни один бит информации не был искажен при прохождении письма.
Для начала нужно создать пару ключей (открытый и закрытый). Это делается с помощью программы PGPkeys. Я советую Вам использовать ключи не менее 1024 бит. В freeware-версии программы можно создавать только ключи DSS/Diffie-Hellman. Старый тип ключей можно создать с помощью коммерческой версии, или с помощью PGP 2.6.X. Ваша пара ключей занесется в общий список доступных Вам ключей (в основном конечно открытых). Теперь имея пару ключей Вы можете легко подписывать, кодировать файлы (в стандартный explorer добавился пункт меню PGP по правой кнопке мышки), а также буфер обмена (clipboard) через программу запущенную в tray’е (при установке PGP сама прописывает эту программу в startup меню).

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

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

PGP использует для шщифрования алгоритм с открытым ключом RSA в паре с обычным методом шифрования IDEA. В методе IDEA для шифрования используется один ключ, и как и в других симметричных криптосистемах, тот же ключ дешифровывает сообщение. PGP использует алгоритм RSA для зашифровки ключа IDEA с помощью открытого ключа адресата. Адресат приняв сообщение с помощью PGP расшифрует этот секретный ключ IDEA. Далее остальная часть сообщения расшифровывается принимающей стороной методом IDEA.

Алгоритм RSA и генерация ключей
Функция шифровки, используемая в RSA выглядит так C = T^E mod N, где T представляет собой шифруемый текст, C — зашифрованный текст, а E представляет собой открытый ключ. Другими словами, T возводится в степень E по модулю N. Для примера, 2 в степени 3 дает 8, а 2 в степени3 по модулю 7 есть 8 mod 7, что равно 1. Функция дешифрования выглядит так: T = C^D mod N где D представляет собой секретный ключ. Пара ключей E и D должна быть выбрана так, что E является обратным к D по отношению к операции возведения в степень по модулю N. Иными словами, (T^E mod N)^D mod N = T^ED mod N = T.

Для того, чтобы найти подходящую пару, для которой это равенство верно, нам надо знать функцию Эйлера переноса? (Euler’s totient function), J(N) для данного значения модуля N. Функция Эйлера представляет собой количество чисел в интервале от 1 до N-1, которые являются простыми относительно N. Для нахождения функции J(N) недо, в свою очередь, найти простые факторы N.

Фундаментальная теорема арифметики: Любое не простое число может быть представлено как произведение уникального набора простых чисел.

Относительно простые числа: Два числа называются относительно простыми, если среди их простых факторов нет одинаковых.

Итоговый список шагов, необходимых для генерации ключа

Выбираем пару произвольных больших простых чисел P и Q и находим N путем умножения
Вычисляем функцию Эйлера числа N, J(N) = (P-1)(Q-1)
Выбираем число E так, чтобы оно было относительно простым по отношению к J(N)
Находим D, обратное число к E по отношению к операции умножения по модулю J(N), и тривиальные значени отбраковываем как несекретные (E=D)
Найдя подходящую пару ключей, ключ E объявляем открытым и его можно использовать для шифровки сообщений, адресованных владельчу пары E и D: C = T^E mod N
Ключ D держится в секрете и используется для дешифровки полученных сообщений: T = C^D mod N

Kremlin Domestic v3.0 русская версия — Windows не имеет криптозащиты, таким образом, не является безопасной средой. Набираемый Вами текст в редакторе постоянно сохраняется (буферезируется) на компьютере в памяти, текстовый редактор сохраняет временные копии редактируемых файлов на винчестере, а Internet проводник сохраняет всю хронологию посещенных страниц.

Kremlin поможет Вам сформировать защиту всей вашей компьютерной среды. Мало того, что он обладает сильной криптографией, для защиты ваших файлов (алгоритмы защиты: the Blowfish, DES, IDEA, и RC4), он также включает утилиту, которая надежно уничтожает необходимые данные с вашего компьютера – для этого на компьютере устанавливается дополнительная корзина Kremlin Secure Recycle Bin.

Чаще всего Kremlin используется для шифровки отельных файлов Нужно навести курсор на нужный файл/папку, щелкнуть правой кнопкой мыши на нем, далее нажатием на пункт Kremlin encript запустить Мастер выполняющий шифровку (указать пароль для шифровки).

Уничтожение данных можно выполнить путем перемещения предназначенных для уничтожения файлов в специальную корзину Kremlin Secure Recycle Bin. Когда вы завершите работу с компьютером, Kremlin отчистит соответствующие области вашего жесткого диска и сотрет все отчеты о ваших действиях, которые незаметно ведет операционная система. Kremlin может также автоматически шифровать ваши документы при выключении компьютера и расшифровывать их, когда Вы вернетесь к работе на компьютере, автоматически защищая ваши файлы от чужих любопытных глаз, имеющих доступ к Вашему компьютеру.

Kremlin также обладает мощным и интеллектуальным сжатием файлов; отпадает необходимость заблаговременно сжимать файлы в zip архивы, Вы можете зашифровать и сжать файлы с помощью программы Kremlin.

Kremlin использует проверенные криптографические алгоритмы для шифровки ваших данных. Зарегистрированные пользователи могут зашифровать свои данные по алгоритмам:

IDEA: Длина ключа: 128-bits,

Оценка защиты: 10 (0 — наименее безопасен и 10 — наиболее безопасен)

Скорость: 4 (0 — самый медленный и 10 — самый быстрый)

IDEA разработана в Цюрихе, Швейцарцем Xuejia Lai и Джеймсом Массей, вообще считается, лучшим и наиболее безопасным блочным алгоритмом, доступным сегодня общественности. Он использует 128-разрядный ключ и предназначен, и устойчив против дифференциального криптоанализа. На сегодня не известно каких либо взломщиков алгоритма IDEA.

RC4: Длина ключа: Бесконечный

Оценка защиты: 10 (0 — наименее безопасен и 10 — наиболее безопасен)

Скорость: 9 (0 — самый медленный и 10 — самый быстрый)

RC4 алгоритм – шифровальный поток от RSA Data Securities Incorporated, Хотя RC4 был первоначально очень засекречен, спустя время в 1994 году он был обнародован. Изданный алгоритм использовался в официальных RSA программах. Сейчас RC4 широко используется во многих приложениях и вообще оценивается, как вполне безопасный. На сегодня неизвестно каких либо взломщиков алгоритма RC4. Основным назначением алгоритма являлась шифровка безопасности транзакций в Internet (Интернет банкинг).
Другие алгоритмы:
Blowfish: Длина ключа: до 448-bits

Оценка защиты: 10 (0 — наименее безопасен и 10 — наиболее безопасен)

Скорость: 7 (0 — самый медленный, и 10 — самый быстрый)

Blowfish — блочный шифр, разработанный Брюсом Шнеиером, автором Прикладной Криптографии. Blowfish комбинирует Feistel Network, зависимые ключи S-Boxes, и функцию F — invertable, чтобы создать, возможно, один из наиболее безопасных доступных обычным пользователям алгоритмов. Версия Blowfish, реализованная в Kremlin выполняет 16 кратную шифровку. Известных взломщиков Blowfish не существует.
CAST: Длина ключа: 128-bits

Оценка защиты: 10 (0 — наименее безопасен и 10 — наиболее безопасен)

Скорость: 7 (0 — самый медленный и 10 — самый быстрый)

CAST разработан Carlisle Adams и Stafford Taveres, создавшими надежных алгоритм. Их проект очень схож с Blowfish, с зависимыми ключами S-Boxes, необратимой функцией f и Feistel сетеподобной структурой (называемый сетью заменных перестановок). Имеется много различных разновидностей CAST, каждый с различной длиной ключа; Kremlin использует CAST с длиной ключа 128 bit.
Safer SK-128

Длина ключа: 128-bits

Оценка защиты: 9 (0 — наименее безопасен и 10 — наиболее безопасен)

Скорость: 3 (0 — самый медленный и 10 — самый быстрый)

Safer SK-128 был разработан Робертом Массей по заказу Корпорации Cylink. 10-кратная версия Safer реализованная в Kremlin использует 128 разрядный ключ и усиленный ключевой алгоритм. Не существует известных взломщиков Safer. Однако, Брюс Шнеиер, автор Прикладной Криптографии, не рекомендует использовать Safer, вот его высказывание об этом алгоритме: “Safer был разработан для Cylink, а Cylink курируется АГЕНТСТВОМ НАЦИОНАЛЬНОЙ БЕЗОПАСНОСТИ США”.
Все вышеперечисленные алгоритмы, входящие в Kremlin обладают устойчивостью к любым формам криптоанализа, созданных самыми известными математиками мира. Когда Вы вводите вашу фразу — пароль в Kremlin, он обрабатывается 64 разрядным генератором случайных смешиваний, используемый в SHA1 (Безопасный Алгоритм Смешивания). После этого происходит 160 bit смешивание, которое используется, как вход в алгоритм шифрования. Если отобранный алгоритм — блочный, Kremlin может использовать Последовательный режим (CBC). После шифрования память компьютера надежно защищена.

Kremlin надежно удаляет все необходимые файлы и данные, многократно стирая и записывая поверх удаленных данных поток случайных чисел. Если бы 1 миллиард компьютеров осуществлял поиск 1 миллиарда ключей в секунду, это заняло бы 100.000.000.000 лет (больше чем существует жизнь), чтобы раскодировать 160 bit-ное сообщение, зашифрованное в зарегистрированной версии программы Kremlin.

После установки программы в трее появится значок – ‘замок’. С этого момента в компьютер интегрирована криптозащита. На рабочем столе появится дополнительная корзина Kremlin Secure Recycle Bin, а в меню, вызываемом кликом правой кнопкой мыши, две новые функции:
Kremlin Encrypt – зашифровка выбранных файлов (директорий)

Kremlin Secure Delete – полное удаление выбранного файла (директории) восстановить после этого их невозможно. Аналогично – если Вы поместите какую либо папку или файл в корзину Kremlin Secure Recycle Bin, расположенную на рабочем столе – они будут уничтожены без возможности восстановления. Вы можете выбирать, по какому алгоритму осуществлять шифрование данных.

Kremlin Wipe – сервисная программа, предназначенная для безвозвратного удаления ненужных данных с диска и из памяти.

Standart Wipe – отчистка свободного пространства на выбранном диске (при этом производится выбранное Вами количество перезатирания поверхности винчестера) – тем самым достигается полное уничтожение оставшихся на винчестере данных, которые злоумышленники могут при желании восстановить.

Memory – стираем свободную физическую и виртуальную память.

Thorough Wipe – вытирает свободное пространство и информацию между концом файла и кластером.

Complete Wipe – вытирает все файлы и свободное пространство с многократным перезатиранием файлов (количество перезаписи можно выбрать в меню, вызываемом кнопкой Options). Время затирания одного диска зависит от количества перезатирания, а также от скорости работы винчестера.

Kremlin Options – сердце программы. Здесь Вы сможете выбрать:

Закладка Encrypt – выбор алгоритма шифрования (описание каждого – выше).

Encription Options – настройки по извлечению файлов (при совпадении имени – стирает старый файл, запомнить последние настройки секретного удаления, осуществлять компрессию при шифровании файлов – сжатие на уровне ZIP).

Decrypt – закладка с настройками извлекаемых файлов (контроль безопасности ключевых фраз, затирать старый файл извлекаемым — новым и т.п.).

Secure Delete – Выводить сообщение о безвозвратном удалении файла, убрать пункт Kremlin Secure Delete из меню, выбор количества перезаписей на винчестере – от 1 до 999! То же самое можно делать с памятью.

Kremlin Text – Позволяет отправлять зашифрованные e-mail сообщения через SMTP с установленным количеством символов (размер письма по умолчанию – 70 буковок).

Kremlin Sentry – Настройка Kremlin для ведения безопасного режима работы по часам.

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

Криптографические методы и средства защиты информации

Типы криптостойких систем шифрования

Абсолютно стойкие системы

Достаточно стойкие системы

Сравнение с асимметричными криптосистемами

Достоинства

Недостатки

Применение

Преимущества

Недостатки

Принцип работы

Защита от линейного криптоанализа

С предварительной частичной установкой

Ключи без предварительной установки

Депонирование ключей

Основные понятия и определения криптографии

Общие сведения

Шесть требований Керкгоффса

Обзор известных методов криптоанализа классических шифров .

2.1.1. Метод встречи посередине .

2.1.2. Метод Полларда.

2.1.3. Дифференциальный метод криптоанализа.

2.1.4. Линейный метод криптоанализа .

Общая схема

Параметры алгоритмов

Распространенные алгоритмы

Сравнение с асимметричными криптосистемами

Достоинства

Недостатки

Основные сведения

Простая перестановка

Одиночная перестановка по ключу

Двойная перестановка

Перестановка «Магический квадрат»

Основная идея

Режимы работы блочного шифра

Классификация блочных шифров

Шифры перестановки

Шифры замены

Смешанное шифрование

Двойное шифрование

Многократное последовательное использование блочных алгоритмов

Объединение нескольких блочных алгоритмов

Режим гаммирования для поточных шифров

Классификация поточных шифров

Синхронные поточные шифры

Самосинхронизирующиеся поточные шифры

Поточные шифры на регистрах сдвига с линейной обратной связью (РСЛОС)

Теоретическая основа

Линейная сложность

Схема шифрования с открытым ключом

Основные принципы построения криптосистем с открытым ключом

Описание алгоритма

Введение

Алгоритм создания открытого и секретного ключей

Шифрование и расшифрование

Схема RSA

Корректность схемы RSA

Криптоанализ алгоритмов с открытым ключом

Аутентификация на основе паролей

Требования

Применения

Электронная цифровая подпись

Проверка парольной фразы

1. ОБЛАСТЬ ПРИМЕНЕНИЯ

2. НОРМАТИВНЫЕ ССЫЛКИ

4. ОБЩИЕ ПОЛОЖЕНИЯ

6. ПРОЦЕДУРА ПРОВЕРКИ ПОДПИСИ

Подделка подписей

Модели атак и их возможные результаты

Подделка документа (коллизия первого рода)

Получение двух документов с одинаковой подписью (коллизия второго рода)

Социальные атаки

Элементарные атаки

Генерация простых чисел

Описание

Схема с общим модулем n

Атака на подпись RSA в схеме с нотариусом

Хостинг, который используем мы

Аренда 1С! Дешево, качество, супер быстро!