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

 

 

СОДЕРЖАНИЕ

 

 

ВВЕДЕНИЕ

1. ИСПОЛЬЗУЕМЫЕ МЕТОДЫ И АЛГОРИТМЫ
1. Требования к свойствам криптопараметров
2. Бинарный алгоритм возведения в степень по модулю
3. Формирование рабочих ключей
4. Алгоритм формирования ЭЦП
5. Алгоритм проверки ЭЦП
6. Постановка задачи реализации
2. ОПИСАНИЕ ПРОГРАММЫ

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

2.2 Функциональное назначение

2.3 Описание логической структуры

2.4 Используемые технические средства

2.5 Вызов и загрузка программы

6. Входные и выходные данные

ВЫВОДЫ

ПЕРЕЧЕНЬ ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ А

 

ВВЕДЕНИЕ

 

 

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

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

Целостность – избежание несанкционированной модификации информации.

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

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

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

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

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

Другие криптосистемы  с открытым ключом основаны на трудности  вычисления дискретных логарифмов в конечном поле. Дискретное логарифмирование (DLOG) – это задача обращения функции g^x в некоторой конечной мультипликативной группе G. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.

Одной из таких криптосистем является схема Эль–Гамаля. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи.

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

 

1 ИСПОЛЬЗУЕМЫЕ МЕТОДЫ  И АЛГОРИТМЫ

 

 

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

 

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

Для оценки вычислительной сложности алгоритмов используется общий метод решета числового поля (GNFS англ. general number field sieve) и рассчитывается по формуле (1.1).

 

   (1.1)

 

Здесь n – это количество битов двоичного представления рассматриваемого числа (криптопараметра).

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

Таблица 1.1 – Разложение на множители  с помощью решета общего поля чисел

Количество бит	Сколько mips-лет нужно для разложения
512	30000
768	2∙108
1024	2∙1011
1280	2∙1014
1536	2∙1016
2048	2∙1020

 

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

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

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

Пусть n ∈ N, n нечетно, n > 1. Вероятностный тест на простоту проводится следующим образом. Выбирается случайное a ∈ N, 1 £ a < n, и для него проверяется выполнение некоторых условий. Если какое-то из условий не выполнено, то число n - составное, поскольку для простых чисел эти условия являются необходимыми. Если же все условия выполнены, то из этого еще не следует простота n. Однако  можно будет считать, что «n - простое число с некоторой вероятностью». Кроме того, обычно доказывают оценку снизу для этой вероятности. Чем больше значений a мы протестируем, тем ближе эта вероятность к единице.

Тест простоты Ферма – это тест простоты натурального числа n, основанный на малой теореме Ферма. Если n – простое число, то оно удовлетворяет сравнению для любого a. Выполнение сравнения является необходимым, но не достаточным признаком простоты числа n. То есть если хотя бы для одного a не справедливо , то число n составное, в противном случае ничего сказать нельзя, хотя вероятность того, что число является простым, увеличивается. Однако существуют составные числа, для которых сравнение выполняется для всех a взаимно простых с n – это числа Кармайкла. Чисел Кармайкла – бесконечное множество, наименьшее число Кармайкла – 561. Тем не менее, тест Ферма довольно эффективен для обнаружения составных чисел.

Тест Соловея-Штрассена – вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном. Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные. Тест Соловея-Штрассена опирается на малую теорему Ферма и свойства символа Якоби: если – нечетное составное число, то количество целых чисел , взаимнопростых с и меньших , удовлетворяющих сравнению не превосходит по значению. Составные числа удовлетворяющие этому сравнению называются псевдопростыми Эйлера-Якоби по основанию . Вероятность ошибки теста Соловея-Штрассена равна . Как уже отмечалось выше для ее уменьшения следует тестировать число не одноразово. При тестированиях вероятность ошибки вычисляется как .

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

Алгоритм был разработан Гари Миллером в 1976 году и модифицирован Майклом Рабином в 1980 году. Тест основан на понятие свидетеля простоты и теореме Рабина: пусть – нечётное число большее 1. Число однозначно представляется в виде , где нечётно. Целое число , называется свидетелем простоты числа , если выполняется одно из условий: или , или существует целое число , , такое, что . Теорема Рабина утверждает, что составное нечётное число имеет не более различных свидетелей простоты, где – функция Эйлера.

Тест Лемана: если для какого–либо целого числа a < P не выполняется условие , то число P – составное. Если это условие выполняется, то число P – возможно простое, причем вероятность ошибки не превышает 50%.

И снова, вероятность  того, что случайное число a будет свидетелем составной природы числа P, не меньше 50%. Повторите эту проверку k раз. Если результат вычислений равен 1 или –1, но не всегда равен 1, то P является простым числом с вероятностью ошибки .

Алгоритм тестирования:

1. Выбрать случайно число a , меньшее P .
2. Вычислить
3. Если , то P не является простым.
4. Если, то вероятность того, что число P не является простым, не больше 50 %.
5. Повторить эту проверку k раз.
6. Если результат вычислений  равен 1 или -1, но не всегда  равен 1, то P является простым числом с вероятностью ошибки  .

Для защиты от специальных методов криптоанализа  используют сильные простые числа, которые усложняют задачу разложения числа на простые множители. Сильное простое число – это простое число с определёнными свойствами:

1. Наибольший общий делитель p – 1 и q – 1 должен быть небольшим.
2. И p – 1, и q – 1 должны иметь среди своих множителей большие простые числа, соответственно p' и q'.
3. И p' – 1, и q' – 1 должны иметь среди своих множителей большие простые числа.
4. И p + 1, и q + 1 должны иметь среди своих множителей большие простые числа.
5. И (p – 1)/2, и (q – 1)/2 должны быть простыми.

Такие числа можно представить в  виде

 

,      (1.2)

 

где R - тоже простое число. В ряде случаев к числу P ставится условие, что бы в каноническом разложении числа P-1 содержалось большое простое число, скажем q, тогда

 

(1.3)

 

В схеме Эль–Гамаля такими числами являются криптопараметры p и g.

Число p – это простое число, которое является одним из составляющих открытого ключа

 

(1.4)

 

Число g – это первообразный корень по модулю p, для которого есть некоторые условия.

Необходимые условия:

 

(1.5)

 

Необходимые и достаточные условия:

 

(1.6)

 

(1.7)

 

2. Бинарный алгоритм возведения в степень по модулю

 

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

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

Исходные данные: показатель степени n, основание a, модуль m. 
Результат: .

Если n = 1, то ; закончить работу алгоритма.

1. k = l_n – 2;  y = a (mod m), где l_n – длина числа n в битах.
2. Для i, принимающего значения от k до 0, выполнить шаги 4–5. 
3. y = y² (mod) m.
4. Если i–й бит n  равен 1, то y = y ∙ a (mod m).
5. Закончить работу алгоритма.

Этот алгоритм называется также SX–алгоритмом. Смысл такого названия состоит в следующем: считаем, что S (squaring) соответствует операции возведения в квадрат, а X – операции умножения на основание. К примеру, возведем основание a  в степень 23 по модулю  p. Запишем 23 в двоичной системе счисления как 10111. Далее, пропуская самый левый бит, который всегда равен 1, запишем под каждой цифрой 1 SX, а под каждой цифрой 0 – X (см. Табл. 1.2).