Требуется специалист в области полей Галуа (точнее GF(2^n)). Меня интересует следующее:
1. Криптостойкость алгоритма умножения на фиксированный элемент в поле GF(2^n).
2. Возможность быстрого нахождения всех неприводимых многочленов степени n в кольце над Z_2.
GD Star Rating
loading...
loading...
2. пыщь
1. Не понял. Что значит криптостойкость в данном случае? Обращение индуцированной умножением перестановки? Честно говоря, не знаю, но умножение на элемент это, из общих соображений, очень хреновая односторонняя перестановка, потому что вся перестановка восстанавливается по одной паре (прообраз,образ).
Делить в GF(2^n) вроде бы за приемлемое время можно, гугл кучу ссылок по теме выдаёт.
Я не специалист, просто мимо прохожу:
1) Мне навскидку кажется, что умножать и делить многочлены по модулю другой многочлен это просто. Откуда там подозрения на криптостойкость? Или я ошибаюсь?
2) Я когдато видел статью где дядя показывал как быстро находить случайные неприводимые многочлены. Может поможет.
К сожалению статья по ссылке платная.
Алгоритм устроен следующим образом. Есть сообщение (строка битов) длины n. Берётся некоторый неприводимый многочлен степени n в Z_2[*]. Кольцо над Z_2 по этому многочлену факторизуется. Сообщение будет элементом построенного поля. Затем фиксируется какойто элемент из поля (обратный к нему легко считается) и элементсообщение с ним перемножаются, и сообщение в итоге зашифровалось. Дешифрация это просто умножение на обратный многочлен.
Теперь пусть противник знает длину сообщения и у него есть много пар (*,y), где * исходное сообщение, а y его шифртекст. Вопрос сможет ли он за приемлемое время найти такой неприводимый многочлен и такой элемент в получившемся поле, чтобы расшифровать сообщение? Причём пусть он может проверять расшифровано сообщение или нет на какомто предикате P(*,y). То есть в предикат P подставляются исходное сообщение и результат дешифрации сообщения и он (предикат) говорит нам правильно расшифровалось сообщение или нет.
1) Ну на вот
2) Опять же, рискую сказать глупость, но все же:
Положим у тебя есть три пары (*1, y1), (*2, y2), (*3, y3). Тогда
a *1 = y1 + k1 z
a *2 = y2 + k2 z
a *3 = y3 + k3 z
Где a ключ, z модуль, k_i целое.
Три линейных уравнения, три неизвестных. И вроде ничего что кольцо.
3) Наконец, если говорить о секьюрити under chosen plaintext attack, то ее наверняка нет, ибо попросив зашифровать многочлен 1 (или скажем * и *+1) ключ сливается напрямую, а попросив зашифровать чтото вроде (t^n+1)/ключ должно быть возможно восстановить модуль.
Пусть при шифровании * > y, u > v. y = ax, v = au и значит uy = vx. Вспоминаем, что * = * + (P), y = Y + (P), u = U + (P), v = V + (P), где *, Y, U, V полиномы над Z_2 степени не выше n 1, а (P) идеал порожденный ключом, т. е. неприводимым полиномом P. P делит UY VX и значит для нахождения P нужно факторизовать полином степени не выше 2n 2.
Если мы имеем еще пару t > s, то TY SX тоже делится на P, а значит на P делится и НОД(TY SX, UY VX). Переход к НОД скорее всего понизит степень, и следовательно упростит факторизацию.
После того, как P найдено, множитель a определяется мгновенно.
В одной научнопопулярной книжке по криптографии поля Галуа применялись для генерации очень хороших последовательностей псевдослучайных чисел. Если такая последовательность есть, то текст сообщения можно просто проксорить с ней. Речь наверное об этом.
Вот. Это то, что мне было нужно. Спасибо.