Построение и исследование свойств системы защиты данных на кубической кривой общего вида

ПОСТРОЕНИЕ И ИССЛЕДОВАНИЕ СВОЙСТВ СИСТЕМЫ ЗАЩИТЫ ДАННЫХ НА КУБИЧЕСКОЙ КРИВОЙ ОБЩЕГО ВИДА

Содержание

Содержание.................................................................................................................................... 2

Введение........................................................................................................................................ 3

1. Кубические кривые................................................................................................................... 4

1.1. Уравнение. Вид кривой..................................................................................................... 4

1.2. Сложение и удвоение точек. Геометрическая и аналитическая форма....................... 4

1.3. Кубические кривые по модулю простого числа............................................................. 9

2. Пример кубической кривой................................................................................................... 11

2.1. Пример нахождения координат точек.......................................................................... 11

2.2. Пример сложения и удвоения точек.............................................................................. 11

3. Описание криптосистемы на кубической кривой общего вида........................................ 13

3.1. Общая структура криптосистемы................................................................................... 13

3.2. Описание процесса шифровки – дешифровки............................................................. 13

3.3. Ключи................................................................................................................................ 14

3.4. Оценка криптостойкости................................................................................................ 14

4. Пример применения............................................................................................................... 15

Заключение.................................................................................................................................. 17

Литература................................................................................................................................... 18

Введение

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

Криптосистемы должны удовлетворять требованиям:

-  процесс шифровки и дешифровки должен быть простым и быстро выполняемым;

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

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

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

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

1. Кубические кривые

1.1. Уравнение. Вид кривой.

Плоская кубическая кривая общего вида определяется алгебраическим уравнением третьей степени от двух переменных x и y. Однако, делая замену переменных, можно понизить степень одной из переменных, например y, до двух. В итоге уравнение кривой приобретает вид у2 = х3+ ax2 + bx + c. Невырожденность кривой означает, что многочлен третьей степени в правой части уравнения не имеет кратных корней. График этой кривой над действительными числами в общем виде выглядит следующим образом:

 

1.2. Сложение и удвоение точек. Геометрическая и аналитическая форма

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

Геометрически:

Выберем две точки P и Q на кривой, затем через них проведём прямую, из точки пересечения этой прямой и одной ветви кривой C опустим перпендикуляр к оси ОХ до пересечению его с другой ветвью кривой в точке R. Эта точка и принимается за сумму точек P и Q.

 

Аналитически:

Пусть R (х3, у3), P (х1, у1) и Q (х2, у2), причём x1 ¹ x2. Абсцисса точки R равна абсциссе точки C, но ордината точки R противоположна ординате точки C. Учтём это замечание при выводе формулы. Т. к. все точки P, Q и C лежат на одной прямой, но в то же время все они принадлежат данной кривой, то координаты этих точек удовлетворяют следующей системе уравнений:

(1)

Из первого уравнения системы выразим y, и подставим его во второе уравнение:

k2 x2 + 2kmx + m2 = x3 + ax2 + bx + c;

x3 + (a – k2)x2 + (b – 2km)x + (c – m2) = 0;

Из первого уравнения системы (1) выражаем k и m:

, ,

По теореме, обратной теореме Виета для кубических уравнений, получим:

x1+ x2 + x3 = k2 – a,

x3 = k2 – a – x1 – x2,

Но из первого уравнения системы (1) следует:

y3= k x3 + m,

Применяя замечание о перемене знака у3, подставляем k и m, тогда получаем:

,

,

Итак, формулы нахождения координат точки, являющейся суммой двух точек, для невырожденной кубической кривой общего вида выглядят следующим образом:

, (2)

. (3)

Теперь выведем формулы нахождения координат удвоенной точки.

Геометрически:

Выведенные ранее формулы для сложения двух точек (удвоение можно представить как сумму двух одинаковых точек?) не годятся, т. к. через точку можно провести бесчисленное множество прямых. Тогда выберем точку P, принадлежащую данной кубической кривой, проведём через неё касательную к кривой, а дальше построим точку 2Р аналогично построению точки R, т. е. продолжим касательную до пересечения её с кривой, затем опустим перпендикуляр к оси Х, он пересечёт кривую в точке равной удвоенной точки Р.

 

Аналитически:

Пусть Р (х1, у1), 2Р (х3, у3), причём x1 не совпадает ни с одним из корней кубического многочлена из правой части уравнения кривой. Из уравнения кривой
у2 = х2+ ax2 + bx + c выразим у:

у = ,

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

у – у1 = у¢(х1)(х – х1).

По определению производной

.

В итоге получим систему уравнений из уравнения касательной, применимого к нашему случаю, и уравнения кривой:

Теперь выразим y из первого уравнения системы и подставим его во второе уравнение:

По теореме, обратной теореме Виета:

Тогда, помня об изменении знака y3, получим:

Таким образом, мы получили формулы нахождения координат удвоенной точки.

,

.

Эти формулы и формулы сложения точек будут использоваться для нахождения координат точки nP, где n – любое натуральное число. Надо ещё сказать, что для унификации обозначений и вычислений вводится понятие бесконечно удалённой или бесконечной точки, ведь если у точек, через которые проводится прямая, одинаковые абсциссы, то реально эта прямая не пересекает кривую, но сложение точек всё равно осуществляется, т. е. считается, что вертикальная прямая пересекает кривую в какой-то точке, которую условились называть бесконечной точкой. Эта бесконечная точка обозначается Ό.

Для точки P = (x, y) данной кубической кривой по определению полагаем -P = (x, -y). Далее, P + (-P) = Ό. Если x – корень уравнения x3 + ax2 + bx + c = 0, то полагаем 2P = P + P = Ό. Считаем, что для любой точки P кривой выполняется
P + Ό = Ό + P = P.

1.3. Кубические кривые по модулю простого числа

Далее для целей криптографии мы будем рассматривать координаты точек кривых по модулю p. Необходимо пояснить, почему число р должно быть простым. Пусть р – составное, тогда р = mn (где m ¹ 1, n ¹ 1, m ¹ 0, m ¹ 0), значит mn º 0 (mod p), но ни m, ни n не сравнимы с 0 по модулю p. Однако в таком случае ни m, ни n не имеют обратных по модулю p. Действительно, если, например, ms º 1 (mod p), то mns º n (mod p), но mns º 0s º 0 (mod p) и, следовательно, n º 0 (mod p). Это противоречие доказывает утверждение. Т. о., предыдущие формулы сложения точек выполняются не для всех точек кривой, т. к. в них присутствует деление. Это обстоятельство не позволяет построить эффективно работающую криптосистему.

Кривые по модулю простого числа существенно отличаются от кривых над действительными числами – в кривых по модулю простого числа все вычисления происходят по модулю, поэтому при использовании формул сложения и удвоения точек используется только вычисления по модулю. Но и геометрически кривые различаются. Например, x2 + y2 = 4 – уравнение, графиком которого является окружность с центром в начале координат и радиусом равным 2, а графиком уравнения x2 + y2 º 4 (mod 7) является набор точек с натуральными координатами, не превышающими 7 и удовлетворяющими данному сравнению, т. е. (0; 2), (0; 5),
(2; 0), (3; 3), (3; 4), (4; 3), (4; 4), (5; 0). Причём множество точек конечно, т. к. максимально возможное количество точек не превышает удвоенного модуля.

2. Пример кубической кривой

2.1. Пример нахождения координат точек

В качестве примера исследуем функцию y2 º x3 + 2x2 - x +1 (mod 37). Рассмотрим несколько случаев нахождения координат точек, а остальные лишь приведём в таблице. Для одного х может существовать как два у, так и одно соответствующее значение у, а может не существовать вовсе. Рассмотрим нахождение координат точек при х = 10. Левая часть данного сравнения равна 1191 (mod 37) = 7, значит, у должен удовлетворять условию у2 º 7 (mod 37). Перебираем все значения y: 0 £ у £ 36. Те из них, которые подходят, и есть ординаты точек. Но если
у = 0, то ординаты точек при таком х совпадают. Такая ситуация имеет место при х = 15. Левая часть равна 3811 (mod 37) = 0, при этом у = 0. А при х = 2 левая часть равна 15 (mod 37) = 15, но не существует такого у, который удовлетворял бы условию у2 º 15 (mod 37). В итоге, получается следующая таблица:

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
y1	1	15	-	-	-	-	-	18	2	-	9	3	9	9	-	0	-	6	5
y2	36	22	-	-	-	-	-	19	35	-	28	34	28	28	-	0	-	31	32

x	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
y1	-	7	-	-	-	-	4	12	5	-	-	-	14	3	11	-	15	15
y2	-	30	-	-	-	-	33	25	32	-	-	-	23	34	26	-	22	22

2.2. Пример сложения и удвоения точек

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

Произведём сложение двух точек P (17; 6) и Q (7; 18), причём P + Q = R, R(y3, x3). Используя выведенные формулы, найдём y3 и x3. Т. к. вычисления производятся по модулю 37, то получим:

.

Чтобы найти значение дроби по модулю необходимо найти число z, удовлетворяющее условию . Перебирая целые z от 0 до 36, получаем, что . Аналогично производятся все деления по модулю, тогда

.

.

Эти координаты есть в таблице, что косвенно свидетельствует о верности вычислений.

Теперь произведём удвоение точки P(11; 3), причем 2P(x3, y3):

,

.

Эти координаты также есть в таблице, что тоже косвенно свидетельствует о верности вычислений.

3. Описание криптосистемы на кубической кривой общего вида

3.1. Общая структура криптосистемы

Объясним принцип работы криптосистемы на невырожденной кубической кривой общего вида.

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

3.2. Описание процесса шифровки – дешифровки

Остановимся подробнее на процессе шифровки и дешифровки. Первоначальное соответствие символов и точек кривой необходимо изменить так, чтобы тем же символам соответствовали другие точки этой же кривой, причём между первоначальным и полученным соответствием должно существовать взаимно однозначная связь. Итак, допустим, символ а соответствует точка P, тогда
nP = Q (где n – ключ шифровки). Следовательно, этому же символу теперь соответствует точка Q, а ей, в свою очередь, в результате демаркировки соответствует символ, отличный от символа а. Т. о. символ а зашифрован.

Операция дешифровки противоположна процедуре шифровки. Зашифрованному символу а соответствует точка Q. Необходимо найти такой дешифровальный ключ, что mn º 1 (mod p) (где p – модуль сравнений). Тогда mQ = mnP = P, т. е. мы вернулись к первоначальному соответствию, символ а расшифрован.

3.3. Ключи

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

3.4. Оценка криптостойкости

Оценим криптостойкость полученной криптосистемы. Первоначально, имеется зашифрованный набор знаков. Этот набор может быть текстом, но если он короткий, то использовать методы статистики невозможно. Тогда используется метод перебора. Для того чтобы дать оценку криптостойкости необходимо найти количество возможных переборов комбинаций коэффициентов кривой, модуля p и шифровального ключа, чтобы найти верную. Т. к. коэффициенты кривой удовлетворяют условию 0 ≤ a, b, c ≤ po – 1, (где po – максимально возможный модуль), модуль p находится среди 3 ≤ p ≤ po, а шифровальный ключ n среди 2 ≤ n ≤ 2po, т. е. криптостойкость данной криптосистемы находится как произведение правых частей полученных неравенств: . Тогда для нашего случая при po = 37, криптостойкость полученной криптосистемы находится между 108 и 1,2×108 операциями перебора.

4. Пример применения

В качестве примера работы полученной криптосистемы зашифруем и расшифруем слово «всё!». Сначала сопоставим с помощью таблицы знаки и точки кривой:

Символы	а	б	в	г	д	е	ё	ж	з	и	й	к	л	м
x	0	36	0	36	1	35	1	35	7	33	7	33	8	32
y	1	15	36	22	15	15	22	22	18	11	19	26	2	13

Символы	н	о	п	р	с	т	у	ф	х	ц	ч	ш	Щ
x	8	32	10	31	10	31	11	27	11	27	12	26	12
y	35	34	9	14	28	23	3	5	34	32	9	12	28

Символы	ъ	ы	ь	э	ю	я	.	,	?	!	_	:	;
x	26	13	20	13	20	15	18	17	18	17	Ό	25	25
y	25	9	7	28	30	0	5	6	32	31	Ό	33	4

(где Ό - бесконечная точка, которая тоже входит во множество точек кривой)

Пусть n = 5. Применяя формулы сложения и удвоения точек, изменяем соответствие точек и знаков. Рассмотрим расчёты для шифрования символа «с», которому соответствует точка F с координатами (10; 28). Чтобы найти точку 5F, т. е. зашифровать символ «с», мы удвоим точку F:

то , тогда

, а

то , тогда

.

Теперь удвоим точку 2F(11; 34):

, тогда

а

тогда

.

Сложим F(10; 28) и 4F(12; 9):

а

следовательно,

.

Мы нашли точку 5F(20; 30), т. е. зашифровали символ «с», т. к. точке 5F(20; 30) в соответствии с первоначальным значением отвечает символ «ю». Символ «ё», которому соответствует точка с координатами (1; 22), шифруется в точку с координатами (13; 28), которому соответствует символ «э», символ «!» шифруется в символ «б», а символ «в» шифруется в символ «а», т. е. слово «всё!» в зашифрованном виде выглядит как «аюэб». При дешифровке возвращаемся к первоначальному соответствию, и набор символов «аюэб» расшифровывается в слово «всё!», т. е. криптосистема функционирует корректно.

Заключение

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

В дальнейшем следовало бы:

-  исследовать структуру множества точек кривой, т. е. определить, являются ли все её точки кратными одной точки или нет;

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

-  увеличить криптостойкость, используя маркировку по несколько символов исходного текста;

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

Литература

1.  Введение в криптографию. Под общ. Ред. . – М.: МЦНМО, «ЧеРо», 1998.

2.  , . Алгебраическая геометрия и теория чисел: рациональные и эллиптические кривые. – М.: Изд-во Московского центра непрерывного математического образования, 2001.

3.  Соболева в истории России (История криптографической службы России XVIII – начала XX в.) – М.: Междунар. Отношения, 1994.