Системы шифрования с открытыми ключами: RSA, системы Эль-Гамаля, системы на основе «проблемы рюкзака».

 

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

RSA. Общая схема алгоритма:

1) каждый пользователь генерирует пару ключей: один для зашифрования и один для расшифрования;

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

3) посылая пользователю В сообщение, пользователь А зашифровывает его открытым ключам пользователя В;

4) пользователь В расшифровывает полученное сообщение с помощью своего секретного ключа.

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

В зависимости от поставленной задачи (шифрование / ЭЦП), один из ключей засекречивается, а второй помещается в общий доступ. Криптостойкость данной системы основана на сложности разложения числа на простые множители и . Для обеспечения лучшей криптостойкости числа и должны различаться по размеру на несколько десятичных разрядов, иметь небольшой НОД (в идеале 1) и не должны содержаться в списках известных больших простых чисел.

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

Система на основе «проблемы рюкзака». Безопасность алгоритмов рюкзака опирается на проблему рюкзака, NP -полную проблему. Проблема рюкзака заключается в следующем: пусть дан набор значений M­₁,M₂,…,M_n и сумма S. Необходимо найти значения b_i такие, что: , где может быть либо нулем, либо единицей. Существует 2 проблемы рюкзака. Проблема рюкзака является «Легкой», если перечень значений (M_i) представляет собой сверхвозрастающую последовательность (когда каждый член больше суммы всех предыдущих). Решение заключается в сравнении суммы (S) с самым большим числом последовательности. Если S больше, либо равен этому числу (M_i), то b_i принимают за «1». Уменьшаем S на значение M_i и переходим к следующему числу последовательности. Процесс повторяется, пока последовательность не закончится. Если по окончании S равно нулю, то решение найдено. Проблема рюкзака является «Трудной», если перечень значений (M_i) – не сверхвозрастающая или нормальная последовательность. Алгоритма быстрого решения не найдено.

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

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

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

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

Реальные рюкзаки должны содержать не менее 250 элементов. Длина каждого члена сверхвозрастающей последовательности должна быть где-то между 200 и 400 битами, а длина модуля должна быть от 100 до 200 битов. В таком случае, полный перебор для взлома будет бессмысленным. На сегодняшний день существуют алгоритмы достаточно быстрого взлома оригинальной схемы и большинства её модификаций. Также есть варианты алгоритма рюкзака, считающиеся безопасными на сегодняшний день.

Цифровая подпись. Общие положения. Цифровые подписи на основе шифросистемы с открытыми ключами стандартов ГОСТ Р и DSS.

Электронная подпись - информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией и которая используется для определения лица, подписывающего информацию. (Федеральный закон от 6 апреля 2011 г. N 63-ФЗ "Об электронной подписи")

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

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

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

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

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

DSS (Digital Signature Standard) – Американский стандарт цифровой подписи, использующий алгоритм DSA. Данный алгоритм представляет собой вариант подписи ElGamal. Выбирается простое число длиной L битов, где L принимает значение, кратное 64, в диапазоне от 512 до 1024. Выбирается простое число - (множитель р-1) длиной 160 бит. Выбирается , где - любое число, меньшее , такое что . - закрытый ключ , - открытый ключ. Параметры - открыты и могут быть общими для группы пользователей.

Выработка ЭЦП: считается хеш-функция (хеш-код сообщения М по методу SHA-1), генерируется случайное , вычисляются: которые являются подписью.

Проверка ЭЦП: вычисляются числа: Если , то подпись верна.

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

Используемые параметры:

— простое число — модуль эллиптической кривой;

— эллиптическая кривая E, задается своим инвариантом J(E) или коэффициентами , где Fp — конечное поле из p элементов. , причем (значит не тождественно);

— целое число — порядок группы точек эллиптической кривой;

— простое число q - порядок некоторой циклической подгруппы группы точек эллиптической кривой, то есть выполняется m=nq, для некоторого . <q< ;

— точка эллиптической кривой E, являющаяся генератором подгруппы порядка q, то есть и для всех k = 1, 2, …, q-1, где — нейтральный элемент группы точек эллиптической кривой E;

— h(M) — хэш-функция (ГОСТ Р 34.11-94), отображает сообщения M в двоичные векторы длины 256 бит.

Ключ шифрования: d-целое число, лежащее в пределах 0<d<q; ключ расшифрования: вычисляемый как .

Дополнительные требования: где ; (пожалуй можно забыть, взято из госта)