К вопросу о реализации решения задачи открытого распределения ключей | Статья в журнале «Молодой ученый»

Авторы: ,

Рубрика: Информатика

Опубликовано в Молодой учёный №3 (83) февраль-1 2015 г.

Дата публикации: 26.01.2015

Статья просмотрена: 17 раз

Библиографическое описание:

Пряхина В. Л., Снежкина О. В. К вопросу о реализации решения задачи открытого распределения ключей // Молодой ученый. — 2015. — №3. — С. 74-76. — URL https://moluch.ru/archive/83/15263/ (дата обращения: 17.08.2018).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

+

0

1

0

0

1

1

1

0

 

*

0

1

0

0

0

1

0

1

 

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

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

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

*+*+…+*x+,

где аi ϵ GF(2)

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

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

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

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

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

р = х

р2= х2

р3= х3= х+1

р4= х4= х2

р5= х5= х2+х+1

р6= х6= х2+1

р77= 1.

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

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

c = рa(mod g), d = pb (mod g).

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

k = da = (pb)a = pab(mod g).

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

св = (ра)b = pab = k(mod g).

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

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

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

k = da =(p5)6 = p30= (p7)4p2 = p2 = x2.

Точно также, партнер В при этом вычисляет cb= (p6)5 = p2= x2 = 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

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


Похожие статьи

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов, кольцо целых чисел, изоморфизм колец.

Прямая сумма данных колец определяется как множество - наборов ( ) c . Сложения и умножения в кольце определяется...

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов

Теорема 1 (китайская теорема об остатках): Рассмотрим область главных идеалов .

2. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие.

Сложение коммутативных полугрупп натуральных чисел...

Полезная информация. Спецвыпуски.

Множество натуральных чисел является бесконечным, так как для любого натурального числа найдётся натуральное число, большее чем .

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов, кольцо целых чисел, изоморфизм колец.

Прямая сумма данных колец определяется как множество - наборов ( ) c . Сложения и умножения в кольце определяется...

Применение метода математической индукции к решению задач на...

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

Но универсальным этот метод назвать нельзя, т. к. присутствуют и недостатки: во-первых, доказывать можно только на множестве натуральных...

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов

Теорема 1 (китайская теорема об остатках): Рассмотрим область главных идеалов .

2. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие.

Эллиптические кривые в алгоритме Диффи - Хеллмана над полем...

Для аддитивной группы, заданной на множестве вычетов множества целых чисел по

Пусть — многочлены из поля . Разложим число в двоичной системе: , (6).

6. Яковлев А. В., Безбогов А. А., Родин В. В., Шамкин В. Н. Криптографическая защита информации.

Сложение коммутативных полугрупп натуральных чисел...

Полезная информация. Спецвыпуски.

Множество натуральных чисел является бесконечным, так как для любого натурального числа найдётся натуральное число, большее чем .

Алгоритмические аспекты доминирования в графах

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

Применение метода математической индукции к решению задач на...

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

Но универсальным этот метод назвать нельзя, т. к. присутствуют и недостатки: во-первых, доказывать можно только на множестве натуральных...

Анализ алгоритма RSA. Некоторые распространённые...

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

Эллиптические кривые в алгоритме Диффи - Хеллмана над полем...

Для аддитивной группы, заданной на множестве вычетов множества целых чисел по

Пусть — многочлены из поля . Разложим число в двоичной системе: , (6).

6. Яковлев А. В., Безбогов А. А., Родин В. В., Шамкин В. Н. Криптографическая защита информации.

Описание множества собственных значений одной блочной...

Полезная информация.

Пусть — компактное связанное множество, - гильбертово пространство квадратично интегрируемых (комплекснозначных)

Здесь — фиксированное вещественное число, — вещественнозначные непрерывные (ненулевые) функции на .

Анализ алгоритма RSA. Некоторые распространённые...

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

Моделирование комбинаторных систем при помощи сводимости

Здесь — некоторое конечное множество, — функции, отображающие в положительные целые числа , выход .

Пусть f — закон распределения вещественной случайной величины, , Y — семейство всех конечных наборов вещественных чисел, — заданный уровень вероятности, и...

Алгоритмические аспекты доминирования в графах

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

Описание множества собственных значений одной блочной...

Полезная информация.

Пусть — компактное связанное множество, - гильбертово пространство квадратично интегрируемых (комплекснозначных)

Здесь — фиксированное вещественное число, — вещественнозначные непрерывные (ненулевые) функции на .

Моделирование комбинаторных систем при помощи сводимости

Здесь — некоторое конечное множество, — функции, отображающие в положительные целые числа , выход .

Пусть f — закон распределения вещественной случайной величины, , Y — семейство всех конечных наборов вещественных чисел, — заданный уровень вероятности, и...

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов, кольцо целых чисел, изоморфизм колец.

Прямая сумма данных колец определяется как множество - наборов ( ) c . Сложения и умножения в кольце определяется...

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов

Теорема 1 (китайская теорема об остатках): Рассмотрим область главных идеалов .

2. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие.

Сложение коммутативных полугрупп натуральных чисел...

Полезная информация. Спецвыпуски.

Множество натуральных чисел является бесконечным, так как для любого натурального числа найдётся натуральное число, большее чем .

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов, кольцо целых чисел, изоморфизм колец.

Прямая сумма данных колец определяется как множество - наборов ( ) c . Сложения и умножения в кольце определяется...

Применение метода математической индукции к решению задач на...

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

Но универсальным этот метод назвать нельзя, т. к. присутствуют и недостатки: во-первых, доказывать можно только на множестве натуральных...

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов

Теорема 1 (китайская теорема об остатках): Рассмотрим область главных идеалов .

2. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие.

Эллиптические кривые в алгоритме Диффи - Хеллмана над полем...

Для аддитивной группы, заданной на множестве вычетов множества целых чисел по

Пусть — многочлены из поля . Разложим число в двоичной системе: , (6).

6. Яковлев А. В., Безбогов А. А., Родин В. В., Шамкин В. Н. Криптографическая защита информации.

Сложение коммутативных полугрупп натуральных чисел...

Полезная информация. Спецвыпуски.

Множество натуральных чисел является бесконечным, так как для любого натурального числа найдётся натуральное число, большее чем .

Алгоритмические аспекты доминирования в графах

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

Применение метода математической индукции к решению задач на...

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

Но универсальным этот метод назвать нельзя, т. к. присутствуют и недостатки: во-первых, доказывать можно только на множестве натуральных...

Анализ алгоритма RSA. Некоторые распространённые...

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

Эллиптические кривые в алгоритме Диффи - Хеллмана над полем...

Для аддитивной группы, заданной на множестве вычетов множества целых чисел по

Пусть — многочлены из поля . Разложим число в двоичной системе: , (6).

6. Яковлев А. В., Безбогов А. А., Родин В. В., Шамкин В. Н. Криптографическая защита информации.

Описание множества собственных значений одной блочной...

Полезная информация.

Пусть — компактное связанное множество, - гильбертово пространство квадратично интегрируемых (комплекснозначных)

Здесь — фиксированное вещественное число, — вещественнозначные непрерывные (ненулевые) функции на .

Анализ алгоритма RSA. Некоторые распространённые...

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

Моделирование комбинаторных систем при помощи сводимости

Здесь — некоторое конечное множество, — функции, отображающие в положительные целые числа , выход .

Пусть f — закон распределения вещественной случайной величины, , Y — семейство всех конечных наборов вещественных чисел, — заданный уровень вероятности, и...

Алгоритмические аспекты доминирования в графах

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

Описание множества собственных значений одной блочной...

Полезная информация.

Пусть — компактное связанное множество, - гильбертово пространство квадратично интегрируемых (комплекснозначных)

Здесь — фиксированное вещественное число, — вещественнозначные непрерывные (ненулевые) функции на .

Моделирование комбинаторных систем при помощи сводимости

Здесь — некоторое конечное множество, — функции, отображающие в положительные целые числа , выход .

Пусть f — закон распределения вещественной случайной величины, , Y — семейство всех конечных наборов вещественных чисел, — заданный уровень вероятности, и...

Задать вопрос