Реализация операций на эллиптической кривой

Задача аутентификации документов решается с помощью использования механизма электронной цифровой подписи, который реализуется методами криптографии с открытым ключом. В основу алгоритмов цифровой подписи положены асимметричные криптографические преобразования, стойкость которых основана на сложности решения некоторой математической задачи. В последние годы широко ведутся исследования криптографических преобразований, основанных на операциях в группе точек эллиптической кривой. Арифметика эллиптических кривых, определенных над простыми и/или расширенными полями Галуа легла в основу стандартов электронной цифровой подписи многих стран, включая Украину. Это, например, такие стандарты:  ДСТУ 4145-2002, ГОСТ Р 34.10-2001, ECDSA, EC-GDSA, ECSS, EC-KCDSA.

Ниже представлена реализация в математическом пакете Maple операций сложения, удвоения точек эллиптической кривой, а также операции умножения точки кривой на число в простом поле Галуа.

Сложение точек эллиптической кривой P3=P1+P2

sum_Point:=proc(P1,P2,p)
local x1, y1, x2, y2, x3, y3, Lamda, P3:
x1:=P1[0]: y1:=P1[1]: x2:=P2[0]: y2:=P2[1]:
if (x1=0 and y1=0) then x3:=x2: y3:=y2:
else
if (x2=0 and y2=0) then x3:=x1: y3:=y1:
else
if (x1=x2 and y1=(-y2)mod p) then x3:=0: y3:=0:
else
Lamda:=((y2-y1)/(x2-x1) mod p):
x3:=(Lamda^2-x1-x2)mod p:
y3:=(Lamda*(x1-x3)-y1)mod p:
end if:
end if:
end if:
P3:=array(0..1,[x3,y3]);
end:
Читать далее →

Лекция 1. Общие понятия и определения

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

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

Защита информации – это комплекс организационно-технических мер, направленных на предотвращение НСД к содержащемуся в ней смыслу.

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

Основные угрозы безопасности информации:

  1. Уничтожение.
  2. Копирование (ознакомление).
  3. Искажение.
  4. Нарушение работоспособности системы (Например, отказ в обслуживании).

Защита информации направлена на сохранение свойств информации:

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

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

3. Доступность – свойство компонента или ресурса быть доступным для авторизованных законных субъектов системы.

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

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

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

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

Уровни защиты информации:

1. Правовой (законодательный). Закон Украины про информацию (10.02.1992). Закон Украины про защиту информации в автоматизированных системах (05.07.1994). Государственный стандарт Украины ДСТУ 3396.0-96 – «техническая защита информации, основные положения». ДСТУ 3396.1-96 – «защита информации, техническая защита информации». ДСТУ 3396.2-97 – «защита информации, техническая защита информации, сроки и определения».
2. Морально-этический.
3. Административный.
4. Физический.
5. Аппаратно-программный.

Распространенные угрозы:

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

2. Компьютерный вирус – подобно живому организму рождается, размножается и умирает. Первое определение, данное Фрэдом Коэном из Университета Южной Калифорнии: «Компьютерный вирус – это программа, которая может заражать другие программы, модифицируя их посредствам включения в них своей, возможно измененной копии, причем последняя сохраняет  способность к дальнейшему размножению». Наиболее опасны загрузочные вирусы.

3. Сетевой «червь» – разновидность программного вируса. Распространяется по глобальной сети и не оставляет своей копии на магнитном носителе. Термин «червь» пришел из фантастического романа Джона Брунера «По бурным волнам». Первоначально черви были разработаны для поиска в сети компьютеров со свободными ресурсами, чтобы получить возможность выполнять распределенные вычисления. При правильном использовании технология «червей» может быть весьма полезной. «Червь» использует механизмы поддержки сети для определения узла, который может быть поражен. Затем, с помощью этих же механизмов, передает свое тело в этот узел и либо активизируется, либо ищет подходящие условия для активизации.

 Для защиты от указанных вредоносных программ необходимо принятие ряда мер:
1)      исключение НДС к исполняемым файлам;
2)      предварительное тестирование приобретаемых программных средств;
3)      контроль целостности исполняемых файлов и системных областей;
4)      создание замкнутой среды исполнения программ.

Алгоритм модульного возведения в степень

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

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

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

Алгоритм. Бинарное модульное возведение в степень.
Исходные данные: показатель степени n¹0, основание a, модуль m.
Результат: y=an(mod m).
1. Если n =1, то y:=(mod m); закончить работу алгоритма.
2. k:=ln–2; y:=a (mod m), где ln – длина числа n в битах;
3. Для i, принимающего значения от k до 0, выполнить шаги 4-5.
4. y := y2 mod m.
5. Если i-й бит n  равен 1, то y := y*a mod m.
6. Закончить работу алгоритма.

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

1 0 1 1 1
S SX SX SX

Двигаясь слева направо, получим определяющую строку SSXSXSX. Помня, что S — это возведение в квадрат, а X – умножение на основание, получаем следующую последовательность операций:

(((((((((((a2mod p)2)mod p)*a) mod p)2 mod p)*a) mod p)2 mod p)*a) mod p)=a23 mod p,

что соответствует действительности.

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

1. Кнут Д. Искусство программирования для ЭВМ. Получисленные алгоритмы / Д.Кнут. – М.: Мир. – Том 2. – 1976. – 788 с.

2. Вельшенбах М. Криптография на Си и С++ в действии. Учебное пособие  / Вельшенбах М. – М.: Издательство Триумф. – 2004. – 464 с.

Основа алгоритмов цифровой подписи

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

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

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

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

Литература

  1. ГОСТ Р 34.10-2001. Государственный стандарт российской федерации. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки цифровой подписи. М.: Госстандарт России, 2001.
  2. ДСТУ 4145-2002. Державний стандарт України. Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривих. Формування та перевірка. Київ:-Держстандарт України, 2003.
  3. Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA)//Certicom Research,Canada, 2001.
  4. J.H. Silverman “The Arithmetic of Elliptic Curve”, GTM 106,Springer-Verlag,New York, 1986
  5. Koblitz N. Elliptic Curve Cryptosystems // Mathematics of Computation. 1987. Vol. 48, №  177.P.203-209.
  6. Штанько С.В. Эллиптические кривые в криптографии // Проблемы информационной безопасности. Компьютерные системы. № 2, 2003, С. 65-74.
  7. Ростовцев А.Г. Алгебраические основы криптографии.– СПб.: НПО «Мир и семья», ООО «Интерлайн», 2000.–354с.

 

Криптография и цифровая подпись

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

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

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

На сегодняшний день в Украине уже имеется возможность доказать юридическую значимость электронных документов, подписанных с помощью цифрового ключа. Этому, безусловно, способствовали Закон Украины «Про електронні документи та електронний документообіг»[1],  устанавливающий основные организационно-правовые положения электронного документооборота и использования электронных документов, и закон Украины «Про електронний цифровий підпис», определяющий правовой статус электронной цифровой подписи и регулирующий отношения, которые возникают при использовании электронной цифровой подписи. Читать далее →

Безопасность информационных систем

Эта дисциплина читается магистрам, обучающимся по специальности «Программное обеспечение систем».

Цикл лабораторных работ включает такие темы, как «Донаучная криптология», «Симметричные шифры», «Криптография с открытым ключом», «Протоколы цифровой подписи на эллиптических кривых», «Стеганография»

Основная литература:
1. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях / Под ред. В.Ф. Шаньгина. – 2-е изд., перераб. и доп. – М.: Радио и связь, 2001. – 376 с.
2. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. М.Ж КУДИЦ-ОБРАЗ, 2001 – 386с.
3. Виноградов И.М. Основы теории чисел. – М.: Наука, 1981. – 168 с.