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

Эллиптические кривые - математический объект, который может определен над

любым полем (конечным, действительным, рациональным или комплексным). В

криптографии обычно используются конечные поля. Эллиптическая кривая есть

множество точек (x,y), удовлетворяющее следующему уравнению:

y² = x³ + ax + b,

а также бесконечно удаленная точка. Для точек на кривой довольно легко

вводится операция сложения, которая играет ту же роль, что и операция

умножения в криптосистемах RSA и Эль-Гамаля.

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

y² = x³ + ax + b mod p,

где р - простое.

Проблема дискретного логарифма на эллиптической кривой состоит в следующем: дана

точка G на эллиптической кривой порядка r (количество точек на кривой) и другая

точка Y на этой же кривой. Нужно найти единственную точку x такую, что

Y = x G, то есть Y есть х -я степень G.

Эллиптические фунции – реализация метода открытых ключей

Системы с открытым ключом

Как бы ни бы­ли слож­ны и на­деж­ны крип­то­гра­фи­че­ские сис­те­мы - их

сла­бое ме­ст при прак­ти­че­ской реа­ли­за­ции - про­блема

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

кон­фи­ден­ци­аль­ной ин­фор­ма­ци­ей ме­ж­ду дву­мя субъ­ек­та­ми ИС, ключ

дол­жен быть сге­не­ри­ро­ван од­ним из них, а за­тем ка­ким-то об­ра­зом опять

же в кон­фи­ден­ци­аль­ном по­ряд­ке пе­ре­дан дру­го­му. То есть, в об­щем

слу­чае для пе­ре­да­чи клю­ча опять же тре­бу­ет­ся ис­поль­зо­ва­ние

ка­кой-то крип­то­си­сте­мы.

Для ре­ше­ния этой про­бле­мы на ос­но­ве ре­зуль­та­тов, по­лу­чен­ных

классической и со­вре­мен­ной ал­геб­рой, бы­ли пред­ло­же­ны сис­те­мы с

от­кры­тым клю­чом.

Суть их со­сто­ит в том, что ка­ж­дым ад­ре­са­том ИС ге­не­ри­ру­ют­ся два

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

объ­яв­ля­ет­ся от­кры­тым, а дру­гой за­кры­тым. От­кры­тый

ключ пуб­ли­ку­ет­ся и дос­ту­пен лю­бо­му, кто же­ла­ет по­слать со­об­ще­ние

ад­ре­са­ту. Секретный ключ сохраняется в тайне.

Ис­ход­ный текст шиф­ру­ет­ся от­кры­тым клю­чом адресата и пе­ре­да­ет­ся

ему. За­шиф­ро­ван­ный текст в прин­ци­пе не мо­жет быть рас­шиф­ро­ван тем

же от­кры­тым клю­чом. Де­шиф­ро­ва­ние со­об­ще­ние воз­мож­но толь­ко с

ис­поль­зо­ва­ни­ем за­кры­то­го клю­ча, ко­то­рый из­вес­тен толь­ко

са­мо­му ад­ре­са­ту.

 

Система с открытым ключом

 

 

Система с открытым ключом

 

Рис.2.1.Реализация процедуры шифрования с открытым ключом.

Крип­то­гра­фи­че­ские сис­те­мы с от­кры­тым клю­чом ис­поль­зу­ют так

называемые не­об­ра­ти­мые или од­но­сто­рон­ние функ­ции, ко­то­рые

об­ла­да­ют сле­дую­щим свой­ст­вом: при за­дан­ном зна­че­нии x

от­но­си­тель­но про­сто вы­чис­лить зна­че­ние f(x), од­на­ко ес­ли

y = f(x), то нет про­сто­го пу­ти для вы­чис­ле­ния зна­че­ния x.

Мно­же­ст­во клас­сов не­об­ра­ти­мых функ­ций и по­ро­ж­да­ет все

раз­но­об­ра­зие сис­тем с от­кры­тым клю­чом. Од­на­ко не вся­кая

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

В са­мом оп­ре­де­ле­нии не­об­ра­ти­мо­сти при­сут­ст­ву­ет

не­оп­ре­де­лен­ность. Под необратимостью понимается не теоретическая

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

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

По­это­му что­бы га­ран­ти­ро­вать на­деж­ную за­щи­ту ин­фор­ма­ции, к

сис­те­мам с от­кры­тым клю­чом (СОК) предъ­яв­ля­ют­ся два важ­ных и

оче­вид­ных тре­бо­ва­ния:

1. Пре­об­ра­зо­ва­ние ис­ход­но­го тек­ста долж­но быть не­об­ра­ти­мым и

ис­клю­чать его вос­ста­нов­ле­ние на ос­но­ве от­кры­то­го клю­ча.

2. Оп­ре­де­ле­ние за­кры­то­го клю­ча на ос­но­ве от­кры­то­го так­же

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

При этом же­ла­тель­на точ­ная ниж­няя оцен­ка сложности (ко­ли­че­ст­ва

опе­ра­ций) рас­кры­тия шиф­ра.

Ал­го­рит­мы шиф­ро­ва­ния с от­кры­тым клю­чом по­лу­чи­ли ши­ро­кое

рас­про­стра­не­ние в со­вре­мен­ных ин­фор­ма­ци­он­ных сис­те­мах. Так,

ал­го­ритм RSA стал ми­ро­вым стан­дар­том де-фак­то для от­кры­тых сис­тем и

ре­ко­мен­до­ван МККТТ.

Вообще же все предлагаемые сегодня криптосистемы с открытым ключом опираются

на один из следующих типов необратимых преобразований:

1. 1. Разложение больших чисел ан простые множители.

2. 2. Вычисление логарифма в конечном поле.

3. 3. Вычисление корней алгебраических уравнений.

Здесь же сле­ду­ет от­ме­тить, что ал­го­рит­мы криптосистемы с открытым

ключом (СОК) мож­но ис­поль­зо­вать в трех на­зна­че­ни­ях.

1. Как са­мо­стоя­тель­ные сред­ст­ва за­щи­ты пе­ре­да­вае­мых и

хра­ни­мых дан­ных.

2. Как сред­ст­ва для рас­пре­де­ле­ния клю­чей. Ал­го­рит­мы СОК бо­лее

тру­до­ем­ки, чем тра­ди­ци­он­ные крип­то­си­сте­мы. По­это­му час­то на

прак­ти­ке ра­цио­наль­но с по­мо­щью СОК рас­пре­де­лять клю­чи, объ­ем

ко­то­рых как ин­фор­ма­ции не­зна­чи­те­лен. А по­том с по­мо­щью обыч­ных

ал­го­рит­мов осу­ще­ст­в­лять об­мен боль­ши­ми ин­фор­ма­ци­он­ны­ми

по­то­ка­ми.

3. 3. Сред­ст­ва ау­тен­ти­фи­ка­ции поль­зо­ва­те­лей. Об этом бу­дет

рас­ска­за­но в главе «Электронная подпись».

Ниже рассматриваются наиболее распространенные системы с открытым ключом.

Не­смот­ря на до­воль­но боль­шое чис­ло раз­лич­ных СОК, наиболее популярна -

криптосистема RSA, разработанная в 1977 году и по­лу­чив­шая на­зва­ние в честь

ее соз­да­те­лей: Рона Ри­ве­ста^[4]

^[4], Ади Ша­ми­ра и Леонарда Эй­дель­ма­на.

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

чи­сел в вы­чис­ли­тель­ном от­но­ше­нии осу­ще­ст­в­ля­ет­ся лег­ко, но

раз­ло­же­ние на мно­жи­те­ли про­из­ве­де­ния двух та­ких чи­сел

прак­ти­че­ски не­вы­пол­ни­мо. До­ка­за­но (тео­ре­ма Ра­би­на), что

рас­кры­тие шиф­ра RSA эк­ви­ва­лент­но та­ко­му раз­ло­же­нию. По­это­му для

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

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

ком­пь­ю­те­ров оце­нить и не­об­хо­ди­мое на это вре­мя.

Воз­мож­ность га­ран­ти­ро­ван­но оце­нить за­щи­щен­ность ал­го­рит­ма RSA

ста­ла од­ной из при­чин по­пу­ляр­но­сти этой СОК на фо­не де­сят­ков

дру­гих схем. По­это­му ал­го­ритм RSA ис­поль­зу­ет­ся в бан­ков­ских

ком­пь­ю­тер­ных се­тях, осо­бен­но для ра­бо­ты с уда­лен­ны­ми кли­ен­та­ми

(об­слу­жи­ва­ние кре­дит­ных кар­то­чек).

В настоящее время алгоритм RSA используется во многих стандартах, среди которых

SSL, S-HHT P, S-MIME, S/WAN, STT и P CT.