К вопросу о реализации решения задачи открытого распределения ключей

Развитие технологий защиты и передачи информации в настоящее время развивается весьма бурно, что стимулирует развитие криптографии, криптоанализа и других разделов информатики, обеспечивающих решение задач защиты информации. В статье рассмотрено построение полей GF(5) и GF() по выбранному во множестве многочленов . В поле GF( построен конкретный пример, реализующий решение задачи открытого распределения ключей. Основными понятиями, используемыми в данной работе являются односторонняя функция секрета К, функция Эйлера, понятие поля. Целью данной статьи является изучение математического аппарата, который используется в процедуре открытого распределения ключей и составление модели, иллюстрирующей решение этой задачи с помощью изученного математического аппарата.

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

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

В работе мы опишем основные понятия «новой криптографии» и покажем, как в ней работает соответствующий математический аппарат.

Применение односторонней функции в криптографии позволяет:

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

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

-          решать новые криптографические задачи, отличные от шифрования (шифровая подпись и др.)

Опишем идею в общем виде. Пользователь A, который хочет получать шифрованные сообщения, должен сначала выбрать какую-нибудь одностороннюю функцию F_k с секретом K. Он сообщает всем заинтересованным (например, публикует) описание функции  F_k  в качестве своего алгоритма шифрования. Но при этом значение секрета K он никому не сообщает и держит в секрете. Если теперь пользователь B хочет послать A защищаемую информацию x, то он вычисляет F_k(x)  и посылает по открытому каналу к A. Поскольку A для своего секрета K умеет инвертировать  F_k , то он вычисляет x по полученному значению  F_k(x). Никто другой не знает K и поэтому в силу свойства односторонней функции с секретом не сможет за полиномиальное время по известному шифрованному сообщению F_k(x) вычислить защищаемую информацию x.

Таким образом, построена система передачи защищаемой информации, причем выполнены два новых свойства:

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

2)                 стойкость шифра зависит от сложности решения трудной математической задачи инвертирования односторонней функции секретом.

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

Построение поля. Пусть множество GF(2) состоит из двух элементов 0 и 1, которые мы рассматриваем как остатки от деления на 2.

Введем на этом множестве операции сложения + и умножения *, которые есть, по сути, операции сложения и умножения остатков, поэтому определяется таблицами.

Аналогично можно рассмотреть остатки от деления на 4. Интересно заметить, что множество остатков от деления на 4 не является полем, так как для элемента 2 не существует обратного и вообще в этом множестве остатков, оказывается, есть делители нуля: 2×2=0. Для того чтобы множество остатков оказалось полем необходимо рассматривать остатки от деления на простое число. Например, остатки от деления на 5 образуют поле.

В криптографии, однако, используется поле GF(2) и уже с его помощью строятся другие важные поля GF(2ⁿ), для достаточно больших значений n. Покажем, как это делается.

Рассмотрим множество многочленов GF(2) [x], которое состоит из всех многочленов вида

*+*+…+*x+,

где а_i ϵ GF(2)

Ясно, что а_i =0 или а_i =1. Выберем во множестве многочленов GF(2) [x] многочлен g=x³+x+1 и рассмотрим все остатки от деления на этот многочлен.

Обозначим множество остатков GF(2³). Т. к. многочлен g(х) имеет степень 3, то все остатки от деления на него по теореме о делении с остатком, имеют степень не выше, чем 2. Таких остатков всего восемь:

GF(2³) = {0, 1, х, х+1, х², х²+1, х²+х, х²+х+1}.

Введем на этом множестве операции сложения и умножения по правилу сложения и умножения остатков.

Задача открытого распределения ключей. Опишем, как решается задача открытого распределения ключей в поле GF(2³). Выберем в этом поле примитивный элемент р = р(х) = х и представим все ненулевые элементы поля в виде степеней этого элемента:

р = х

р²= х²

р³= х³= х+1

р⁴= х⁴= х²+х

р⁵= х⁵= х²+х+1

р⁶= х⁶= х²+1

р⁷=х⁷= 1.

В качестве односторонней функции выберем функцию F(x) = р^х (mod g), где р — выбранный нами примитивный элемент, а g — многочлен g(x), выбранный нами для построения поля GF(2³). Элементы р и g являются общедоступными.

Пусть два партнера А и В выбирают независимо друг от друга по одному натуральному числу а и b соответственно._. Каждый из участников держит эти числа в секрете. Затем каждый из них вычисляет новый элемент c и d по формулам:

c = р^a(mod g), d = p^b (mod g).

По открытому каналу связи партнеры обмениваются этими элементами, после чего партнер А. Зная свой секретный элемент a и полученный от В элемент d, партнер А вычисляет новый элемент

k = d^a = (p^b)^a = p^ab(mod g).

Аналогично поступает партнер В. Он вычисляет элемент

с^в = (р^а)^b = p^ab = k(mod g).

Теперь у партнеров А и В появился общий элемент поля k. Он и есть общий ключ для А и В. При формировании этого ключа использовались известные всем элементы p, g, р^а, р^b. Посторонние пользователи сети не знают только секретные элементы а и b. При этом каждый из партнеров в результате вычисляет новый, только им известный общий элемент поля k.

Например, пусть партнеры А и В каждый выбрали по натуральному числу а = 6 и b = 5.

Партнер А вычисляет с = р⁶ = х²+1, а партнер В вычисляет d = р⁵= x²+x+1. Эти элементы они пересылают друг другу, после чего партнер А получает:

k = d^a =(p⁵)⁶ = p³⁰= (p⁷)⁴p² = p² = x².

Точно также, партнер В при этом вычисляет c^b= (p⁶)⁵ = p²= x² = k.

Разумеется, на практике используются поля GF() при достаточно больших n, но в принципе задача решается так, как показано в примере.

Литература:

1.         Бочкарева, О. В. Формирование профессиональных умений на занятиях по математике/ О. В. Бочкарева, О. В. Снежкина, М. А. Сироткина // Молодой ученый.- 2014.- № 2 (61).- С. 735–738.

2.         Ладин, Р. А. Математика в учебном процессе строительного вуза / Р. А. Ладин, О. В. Снежкина, Г. А. Левова // Вестник магистратуры. -2013.- № 12–4 (27).- С. 56–59.

3.         Бочкарева, О. В. Математические задачи как средство формирования профессиональных качеств личности / О. В. Бочкарева, Т. Ю. Новичкова, О. В. Снежкина, Р. А. Ладин // Современные проблемы науки и образования.–2014.–№ 2; URL: www.science-education.ru/116–12584