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

·

Требуется специалист в области полей Галуа (точнее 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

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

      Ответить

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