Comments 5
Если использовать M3-систему вместо классического DH, то, как понимаю, логика с простыми числами будет отсутствовать? Но при таком сценарии разве не будет возникать малых подгрупп, количество элементов в которых будет меньше заданного N? Протокол DH использует для предотвращения этому надёжные простые числа вида p=2q+1.
Также, есть ли какие-нибудь бенчмарки M3-системы в сравнении с DH? Могу ошибаться, но кажется, что классический DH с переумножением чисел будет быстрее при условии, что модуль N в M3-системе сопоставим с модулем p в DH-протоколе.
Предложенная система очень свежая и скорее является объектом академических исследований и теоретических разработок. Поэтому на ваши вопросы у меня нет полных исчерпывающих ответов, но попробую ответить как смогу.
В M3-системе логика с простыми числами вида p=2q+1 в явном виде не применяется. Здесь N выступает в роли модуля для всех арифметических операций над компонентами векторов, и обычно выбирается простое число, чтобы K было полем, чтобы не было делителей нуля. Но, подозреваю, проблема малых подгрупп всё равно актуальна. Главный вопрос здесь - длина цикла (орбиты) для заданного начального элемента a. В своих тестовых наблюдениях при разных нетривиальных параметрах (например, когда все A B C D E простые числа) и начальный вектор также выбран нетривиально (например, тоже простые числа), то цикл обычно или N или максимальный который получался N^2 / 2, но никогда не наблюдался меньше N. Возможно если выбраны вырожденные изначально случаи, то там все плохо. Когда будет больше экспериментальных данных, выложу на гитхаб.
Что касается скорости, то классический DH будет быстрее, потому что скалярная операция одна, а в векторном умножении их больше. По ощущением M3 может быть медленнее кратно. Точного бенчмарка нет.
В общем, пока тут больше фундаментальный интерес, возможно, сложность проблемы DIP не будет решаться эффективно квантовыми компьютерами, или другие схемы найдутся.
Насколько легко подобрать параметры A–E и модуль N так, чтобы гарантировать стойкость системы?
Я сейчас провожу такое исследование, через неделю примерно будут первые результаты. Сейчас предварительно могу сказать что для любого модуля N есть как минимум N/2 орбит длиной N^2. Под орбитой понимаю последовательное умножение элемента на самого себя пока не придет к себе обратно, то есть a^p = a, где p - длина орбиты. Более 80% орбит имеют длину N. Делаю тест, который будет проверять различные диапазоны на завершение цикла. Выбор коэффициентов и начальной точки в моем понимании на сегодня не сложная совершенно задача, подкреплять это утверждение пока могу статистическим распределением чисел, которые образуются по мере прохода орбиты, что они равномерно распределены.
Подозреваю, что отсутствие ассоциативности и коммутативности заодно и помешает вашу гипотезу доказать, равно как и обосновать оптимальность выбора коэффициентов A, B и C. И отсутствие вырождения доказать надо будет тоже.
Новый кандидат в односторонние функции для криптографии и PRNG