 |
|
Проблемы криптографии
Из Первой Книги.
С.131
Генерация неприводимых многочленов.
До сих пор неизвестен детерминированный алгоритм, который за полиномиальное от n время генерирует какой-нибудь неприводимый многочлен степени n над полем GF(p).
Очень мало известно результатов о существовании неприводимых многочленов с какими-либо ограничениями на коэффициенты (впрочем, известна формула для числа возвратных неприводимых многочленов, см., например, [Jungnickel D. Finite fields: Structure and arithmetics. Wissenschaftsverlag, 1995.])
C.135
Генерация примитивных многочленов.
«Из таблиц [184,185] видно, что в случае p=2 всегда существуют примитивные пятичлены или семичлены, но, кажется, теоретически это никто ещё не доказал.»
Ссылки на
184. Zivkovic M. A table of primitive binary polynomials. // Math. Comp. 1994. 62. P. 385-386
185. Zivkovic M. A table of primitive binary polynomials. II // Math. Comp. 1994. 63. P. 301-306.
Из Второй Книги.
С.121
О билинейной проблеме Диффи-Хеллмана (BDHP).
Труднорешаемость BDHP влечёт за собой труднорешаемость обычной проблемы Диффи-Хеллмана (DHP) и проблемы дискретного логарифмирования (DLP) в обеих группах G1, G2. Но справедливость обратного утверждения не установлена.
С. 87
Протокол Мэсси-Омуры.
Протокол Мэсси-Омуры позволяет передать сообщение от абонента А абоненту В по открытому каналу связи без предварительной передачи какой бы то ни было ключевой информации.
Аналог передачи секрета при помощи ящика (чемоданчика), запираемого на два замка:
абонент А запирает ящик с письмом своим ключом и пересылает ящик абоненту В, который запирает ящик своим ключом и отправляет его к А; тот снимает свой замок (открывая его своим ключом) и возвращает ящик к В, который снимает свой замок (открывая его своим ключом) и достаёт письмо.
Необходимое условие реализации – перестановочность действий по запиранию-отпиранию ключей. Математическая реализация поэтому – в соответствующих абелевых группах. Проблема – в построении этих групп, удобных в приложениях. Известен мультипликативный вариант – в группе умножения ненулевых вычетов по большому простому модулю и аддитивный вариант – в группе точек эллиптической кривой.
Есть ли ещё удобные и стойкие реализации?
А на основе многочленов?
C. 84.
О проблеме Диффи-Хеллмана (DHP) и проблеме дискретного логарифма (DLP).
Классическая проблема Диффи-Хеллмана (DHP) формулируется применительно к мультипликативной группе конечного поля. Она заключается в вычислении элемента axy по элементам a , a x и a y.
Не известно, возможно ли её решение без предварительного вычисления индексов x и y, т.е. минуя проблему дискретного логарифма (DLP).
Применительно к циклической подгруппе группы точек эллиптической кривой эта проблема заключается в том, чтобы по трём известным точкам – точке P на кривой E(F) и двум её кратным xP и yP найти точку xyP.
Также не известно, можно ли это сделать без предварительного вычисления констант x и y, т.е. не решая проблему дискретного логарифма (DLP) для эллиптических кривых.
Проблема неприводимых сумм геометрической прогрессии.
Как известно, многочлен f(x)=1+x+x2+x3+ …+xn над полем GF(2) неприводим тогда и только тогда, когда p=n+1 есть простое число и двойка – первообразный корень по модулю p. Вопрос: можно ли придумать конструкцию, дающую бесконечную серию таких неприводимых многочленов (что даёт так называемый нормальный базис первого типа) ?