Криптосистемы на эллиптических кривых, кодирование и декодирование текста

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФФЕСИОНАЛЬНОГО ОБРАЗОВАНИЯ «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «МЭИ»

Кафедра информационной и экономической безопасности

КУРСОВОЙ ПРОЕКТ

по учебной дисциплине

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

На тему: «Криптосистемы на эллиптических кривых, кодирование и декодирование текста»

Выполнил:

студент ИЭ-43-14

Кирсанов Алексей Михайлович

Научный руководитель:

Евтеев Борис Васильевич

Москва 2016

Содержание

Введение

Глава 1. Криптосистемы в эллиптических кривых

1.1 Основные понятия эллиптических кривых

1.2 Эллиптические кривые над конечными полями

1.3 Криптографические схемы на эллиптических кривых

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

Глава 2. Кодирование и декодирование текста

2.1 Понятие кодирования и декодирования

2.2 Процесс кодирования

2.3 Виды кодов

Заключение

Список используемой литературы

эллиптический кривой криптографический кодирование

Введение

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

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

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

Объект исследования - эллиптические кривые.

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

изучить основные понятия эллиптических кривых;

рассмотреть эллиптические кривые над конечными полями;

рассмотреть криптографические схемы на эллиптических кривых;

изучить понятия и процесс кодирования и декодирования;

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

Глава 1. Криптосистемы в эллиптических кривых

1.1 Основные понятия эллиптических кривых

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

у2+а1ху+а3у=х3+а2х2+а4х+а6 (1)

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

у2=х3+ах+b. (2)

Рис.2. Пространственный график эллиптической кривой

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

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

1. Любая вертикальная (параллельная оси Оу) прямая, не пересекает кривую ни разу или пересекает ее дважды.

2. Любая другая прямая пересекает кривую один или три раза.

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

R + R' = O - для вертикальных прямых,

P + Q+R = O - для невертикальных прямых (см. рис. 1).

Первое соотношение определяет правило отрицания - аддитивным обратным элементом для любой точки R эллиптической кривой является другая точка пересечения кривой и вертикальной прямой: R' = -R. Второе соотношение определяет правило сложения точек: суммой двух точек кривой является отрицание третьей точки пересечения кривой и прямой, проведенной через первые две: Р + Q = -R = = R' (см. рис. 1). Для определенных таким образом аддитивных операций выполняются все требования к операциям в абелевых группах:

Операция сложения точек очевидным образом коммутативна: для любых точек Р, Q эллиптической кривой справедливо Р + Q = Q + Р.

В проективной геометрии доказывается ассоциативность операции сложения точек: для любых трех точек Р, Q, R эллиптической кривой справедливо (Р + Q) + R = P + (Q+R).

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

1.2 Эллиптические кривые над конечными полями

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

Следует указать, что не для всякого конечного поля уравнение кривой может быть приведено к виду (2). Так, для конечного поля характеристики 3 невозможно избавиться от члена а2х2, если а2 отлично от нуля. Для полей характеристики 2 уравнение (1) может быть приведено к одному из следующих видов:

у2+ау=х3+Ьх+с (3) (суперсингулярная кривая);

у2+аху=х3+bх2+с (4) (несуперсингулярная кривая).

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

1.3 Криптографические схемы на эллиптических кривых

Большинство криптосистем современной криптографии естественным образом можно "переложить" на эллиптические кривые. Ниже мы рассмотрим варианты некоторых наиболее распространенных криптосистем. Во всех описаниях Алиса и Боб считаются законными участниками информационного процесса. Криптосистема RSA - шифрование с открытым ключом и ЭЦП В табл. 2 приведены основные соотношения алгоритмов криптосистемы RSA. В варианте RSA на эллиптических кривых используется кривая у2 = х3 + b с условием p = q = 5(mod 6) или кривая у2 = x3 + ax с условием p = q = 3(mod 4). В обоих случаях эллиптическая кривая рассматривается не над конечным полем, а над кольцом вычетов по составному модулю п. Параметры b и а соответственно не задаются пользователем, а "стихийно складываются" при выборе Бобом (отправителем сообщения) случайного числа у. Для операций с точками кривой знать параметр b нет необходимости, а параметр, а легко находится с помощью расширенного алгоритма Евклида по заданной точке (х, у) из уравнения y2 = x3 + ax.

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

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

Главная проблема состоит в том, что истинная сложность ECDLP ещё не осознана полностью. Недавнее исследование показало, что некоторые использовавшиеся для отработки алгоритмов шифрования эллиптические кривые, фактически не подходят для таких операций. Например, если координаты базовой точки P равны положению p, то ECDLP имеет простое решение. Такие кривые являются “аномальными” кривыми.

Исследования в этой области продолжаются по сей день, но потенциальные пользователи все еще проявляют осторожность и выжидают.

Несовместимые системы

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

Это отличает системы на основе эллиптических кривых от систем RSA, которые теоретически являются совместимыми.

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

Лицензии и Патенты

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

Обработка

Как уже было упомянуто, системы на основе эллиптической кривой используют ключи малых размеров. Это снижает требования к вычислительным мощностям по сравнению с требованиями систем на основе RSA. Как это влияет на скорость обработки? Следующая таблица показывает сравнительные характеристики алгоритмов RSA и ECDSA (нечетный) при создании и проверки подписей; оба алгоритма выполнялись на параллельных процессорах Motorola 56303 DSP (66 МГЦ). Обратите внимание, что функция проверки подписи RSA использует при проверке подписи e = 65537.

Ясно, что различные способы выполнения покажут различное время, но примерная скорость ясна. При увеличении размеров ключа создание подписей с помощью ECDSA производится значительно быстрее, чем в аналогичных RSA системах. Это различие в ещё большей степени проявляется для однопроцессорных систем. С другой стороны, проверка подписи с помощью ECDSA производится намного медленнее, чем эта же процедура в системах RSA и опять же это различие усиливается для систем с одним процессором. Обратите внимание, что обработка ECDSA несколько ускориться в “четном” случае. Мощность процессора, затраченная на проверку подписи при использовании, скажем, ECDSA, может замедлить выполнение других приложений в системе. Множество систем имеют большое количество удаленных устройств, соединенных с центральным сервером и время, затраченное удаленным устройством для создания подписи - несколько секунд - не влияет на производительность системы в целом, но сервер должен также и подтверждать подписи, причем очень быстро и в некоторых случаях системы RSA (даже использующие большие ключи) возможно, будут более приемлемы для использования, чем криптосистемы на основе эллиптической кривой.

Глава 2. Кодирование и декодирование текста

2.1 Понятие кодирования и декодирования

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

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

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

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

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

2.2 Процесс кодирования

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

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

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

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

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

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

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

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

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

2.3 Виды кодов

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

За единицу количества информации принимается 1 бит, т.е. один двоичный разряд (0 или 1). Буквы, десятичные цифры и другие символы внутри ЭВМ представляются в виде групп двоичных разрядов. Операция представления их в таком виде называется двоичным кодированием. Группа из n двоичных чисел позволяет закодировать 2n различных символов. Такая группа называется байтом.

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

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

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

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

Заключение

Криптосистемы на основе эллиптической кривой получают все большее распространение скорее, как альтернатива, а не замена системам на основе RSA, поскольку системы на основе ECDLP имеют некоторые преимущества, особенно при использовании в устройствах с маломощными процессорами и/или маленькой памятью. Типичные области применения:

m-commerce (мобильная торговля) (например, WAP сотовые телефоны, карманные компьютеры)

смарт-карты (например, EMV)

e-commerce (электронная торговля) и банковские операции (например, SET)

интернет приложения (например, SSL)

Существуют, однако, и некоторые проблемы, которые ограничивают широкое распространение систем на основе эллиптических кривых:

трудность генерации подходящих кривых

несовместимость

лицензирование и патентование

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

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

Список используемой литературы

1. Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. - М.: КомКнига, 2006. -280 с.

2. ГОСТ Р 34.10.2001. Процессы формирования и проверки электронной цифровой подписи.

3. Кобниц Н. Курс теории чисел и криптографии. - Москва: научное издательство ТВП, 2001, х+254с.

4. Ростовцев А.Г. Маховенко Е.Б. Теоретическая криптография. - Санкт - Петербург: НПО «ПРОФЕССИОНАЛ», 2004. -478с.

5. В. Ф. Сытник АСУП и оптимальное програмирование 1977г. 312 стр.

6. http://www/5ballov.ru/

Размещено на Allbest.ru