dxdt.blog: занимательный интернет-журнал

Ещу раз отмечу один локально-положительный момент у этой истории вокруг тривиальных ключей в программах доверия браузеров. Я уже упоминал о том, что использую данное направление в качестве источника тем для курсовых работ студентов профильных вузов (обычно, эта тема – для второго курса). И вот в сообщении Google буквально указаны алгоритмы, которые и лежат в основе данной темы, которые прямо используются в реализации. Тема могла показаться слишком оторванной от реальности, но только не теперь.

А именно, то, что в англоязычной традиции называется Baby-Step Giant-Step (BSGS), известно как алгоритм Гельфонда (или Гельфонда-Шенкса) для дискретного логарифма; а вторая часть – разностный метод, – это, в принципе, обобщение предыдущего алгоритма, но с использованием других таблиц. Оба алгоритма на практике могут успешно работать только с небольшим подмножеством скаляров (потому что выигрыш там достигается из использования предвычисленных таблиц, но уже 2^64 – это слишком много по памяти). Этого оказалось достаточно, в данном практическом и шумном случае. Опять же, это математические детали.

Главное тут в другом – данный глобальный практический случай с eMudhra идеально отвечает на всякие сомнения в практической полезности изучения тривиальных логарифмов на эллиптических кривых: даже Google не использовал эти проверки, из-за чего глобальные программы доверия корневым ключам в браузерах оказались скомпрометированы на долгое время. Так что тема оказалась более чем к месту.

Адрес записки: https://dxdt.blog/2026/10/28/19546/