IX Международная студенческая научная конференция Студенческий научный форум - 2017
О ЯВНЫХ КОНСТРУКЦИЯХ ДЛЯ РЕШЕНИЯ ОДНОЙ КРИПТОГРАФИЧЕСКОЙ ЗАДАЧИ
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Постановка задачи требует предложить для каждого натурального явную конструкцию подмножества множества всех битовых строк длины n, удовлетворяющего следующим двум условиям:
1) каждый элемент может быть представлен в виде , где – различные элементы множества ;
2) для всех различныхсправедливо .
В предлагаемой работе излагаются подходы к решению этой проблемы.
Как показывают вычислительные эксперименты,
Это оправдывает подход к построению множества L в виде кривой при четном n= 2m.
Пусть n= 2m (); представим в виде декартова произведения , а множество L – в виде кривой, состоящей из точек (x, y) этой плоскости, удовлетворяющих некоторому уравнению.
Будем искать уравнение кривой L в явном виде
y= f(x), (1)
где , f: .
Будем считать полем Галуа и строить f в виде многочлена.
Если взять f в виде y= f(x) = x3, то оба условия выполняются. Так что L – "кубическая парабола".
Проверяя 2), найдем
y = f(x1+ x2+ x3)=(x1+ x2+ x3)3=(x13+ x23+ x33)+3(x1+ x2)(x1+ x3)(x2+ x3), (2)
Следовательно, равенство в равносильно (x1+ x2)(x1+ x3)( x2+ x3)=0, что в поле характеристики два равносильно тому, что или x1+ x2, или x1+ x3, илиx1+ x3. А это противоречит условию различности точек x1 ≠ x2 ≠ x3 ≠ x1.
Приступим теперь к проверке условия 1).
В поле характеристики два имеем следующее
0 ≠ w = u3+v = (x1+ x2)( x1+ x3)( x2+ x3). (3)
Условие 1) сводится, значит, к условию
1') для любых u, v таких, что u3+v ≠ 0, существуют такие (все различные) x1, x2 и x3, что справедливо (3).
Утверждение. Кубическая параболаy= x3 при n= 2m дает явную конструкцию множества L как кривой на плоскости F2, где F = GF(2m).
Для нечетного n поиск явной конструкции пока не дал результатов.
Литература
1. nsucrypto.nsu.ru.
2. Глуско Кр. Л., Титов С. С. Арифметический алгоритм решения квадратных уравнений в конечных полях характеристики два. // Доклады ТУСУРа. – 2012. № 1(25), ч.2. С. 148–152.
3. Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию: алгебраические и алгоритмические основы. М.: КомКнига, – 2006.
4. Болотов А. А., Гашков С. Б., Фролов А. Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. М.: КомКнига, – 2006.
5. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, – 1988.
6. Геут К. Л., Титов С. С. О свойствах поликвадратичных расширений бинарных полей. // Проблемы теоретической и прикладной математики: Труды 44-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН. 2013. С. 17–19.