https://nsucrypto.nsu.ru/archive/2021/round/2/task/4/#data
Основная идея упражнения: Найдите секретный ключ $к$, имея доступ к $Enc(x, d) = Enc(x^d \bmod n), n = 1060105447831$.
я предполагаю $0 <k <n.$
$Enc$ является обычным хэшем, он возвращает тот же вывод, что и соответствующий ввод.
Я хочу найти такое столкновение, что $ хеш (к, 1) = хеш (х, d) $, это будет означать, что я нашел $k = x^d \bmod n.$
Моей первой идеей было найти генератор циклической группы $Z_{1060105447831}$, но я обнаружил, что 2 и 3 и ничего в первых 20000 номеров не работает. Я бы использовал генератор для проверки коллизий для $к$. Я знаю $2^{40} > n$. Также было бы полезно использовать генератор для вычисления дискретного логарифма и быстрее находить значение k. Я хочу проверить это, но похоже, что проблема была сделана с ручной проверкой.
Атака дня рождения не работает для 128-битного хэша, если мне нужна хорошая вероятность и эффективность.
Я также попытался получить хеш-значение небольших значений Enc(2,1), Enc(3,1) ... Enc(10, 1), чтобы увидеть, есть ли у хеша какая-либо скрытая связь между его выходами.
Кроме того, $\фи(п)$ имеет хорошую факторизацию малых чисел.
Я добавлю любые новые важные детали.
Какие значения следует выбрать, чтобы помочь найти k? Они имеют значение? Генераторы бесполезны, я не могу применить более быстрые алгоритмы для модульного возведения в степень, потому что все, что я получаю, это 128-битная строка. Все, что я могу сделать, это проверить, имеет ли число или степень числа кодировку, равную кодировке секретного числа. $к$
