Требуется специалист в области полей Галуа

·

Требуется специалист в области полей Галуа (точнее GF(2^n)). Меня интересует следующее:
1. Криптостойкость алгоритма умножения на фиксированный элемент в поле GF(2^n).
2. Возможность быстрого нахождения всех неприводимых многочленов степени n в кольце над Z_2.

GD Star Rating
loading...

похожие публикации

  1. Задача про многочлен
  2. есть ли среди нас специалист по оптике?
  3. А кто нибудь может подсказать ?
  4. В чём сложность ?
Tagged with → •  

7 Responses to Требуется специалист в области полей Галуа

  1. EvBig:
    17/10/2009 в 03:15

    2. пыщь
    1. Не понял. Что значит криптостойкость в данном случае? Обращение индуцированной умножением перестановки? Честно говоря, не знаю, но умножение на элемент — это, из общих соображений, очень хреновая односторонняя перестановка, потому что вся перестановка восстанавливается по одной паре (прообраз,образ).
    Делить в GF(2^n) вроде бы за приемлемое время можно, гугл кучу ссылок по теме выдаёт.

    Ответить
  2. Peels:
    17/10/2009 в 03:30

    Я не специалист, просто мимо прохожу:
    1) Мне навскидку кажется, что умножать и делить многочлены по модулю другой многочлен — это просто. Откуда там подозрения на криптостойкость? Или я ошибаюсь?

    2) Я когда–то видел статью где дядя показывал как быстро находить случайные неприводимые многочлены. Может поможет.

    Ответить
  3. NoBig:
    17/10/2009 в 09:37

    К сожалению статья по ссылке платная.

    Алгоритм устроен следующим образом. Есть сообщение (строка битов) длины n. Берётся некоторый неприводимый многочлен степени n в Z_2[*]. Кольцо над Z_2 по этому многочлену факторизуется. Сообщение будет элементом построенного поля. Затем фиксируется какой–то элемент из поля (обратный к нему легко считается) и элемент–сообщение с ним перемножаются, и сообщение в итоге зашифровалось. Дешифрация — это просто умножение на обратный многочлен.

    Теперь пусть противник знает длину сообщения и у него есть много пар (*,y), где * — исходное сообщение, а y — его шифртекст. Вопрос — сможет ли он за приемлемое время найти такой неприводимый многочлен и такой элемент в получившемся поле, чтобы расшифровать сообщение? Причём пусть он может проверять расшифровано сообщение или нет на каком–то предикате P(*,y). То есть в предикат P подставляются исходное сообщение и результат дешифрации сообщения и он (предикат) говорит нам правильно расшифровалось сообщение или нет.

    Ответить
  4. Peels:
    17/10/2009 в 10:48

    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)/ключ должно быть возможно восстановить модуль.

    Ответить
  5. Rafol:
    18/10/2009 в 21:07

    Пусть при шифровании * –> 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 определяется мгновенно.

    Ответить
  6. DRusba:
    19/10/2009 в 13:49

    В одной научно–популярной книжке по криптографии поля Галуа применялись для генерации очень хороших последовательностей псевдослучайных чисел. Если такая последовательность есть, то текст сообщения можно просто проксорить с ней. Речь наверное об этом.

    Ответить
  7. NoBig:
    19/10/2009 в 18:14

    Вот. Это то, что мне было нужно. Спасибо.

    Ответить

Добавить комментарий