Обрезка равномерно случайного ввода для закрытых ключей эллиптической кривой

Представьте, что есть 256-битная униформа. вход из CSPRNG. Предположим, что имеется кривая типа secp256r1, порядок кривой которой чуть меньше 256 бит.

Мы не можем просто мод (ввод, кривая_порядок) потому что это приведет к смещению по модулю. Что, если мы урежем 256 бит до 255 бит, что меньше, чем порядок кривой? Тогда все значения в пределах 255 бит будут иметь равные шансы появления.

ed25519, кажется, делает именно это с их ~ 252-битным порядком кривой - они регулируют 3 бита.

Выборка отклонения из NIST SP 800-56A rev 3, раздел 5.6.1.2.2 не является постоянной, поэтому ищите что-то более простое.

Дополнительный вопрос: что, если мы также настроим последний 1 бит, чтобы ключи 0 и 1 никогда не появится при использовании |= 2 это заставит их всегда быть 1 (так же, как мы всегда заставляем начало быть 0?

Вот как кодовая база Monero генерирует случайные скаляры для использования с ed25519:

Для кривой ed25519 порядок $\ell$ группы базовой точки $2^{252}+27742317777372353535851937790883648493$.

Чтобы сгенерировать несмещенное случайное число меньше $\ell$, мы сначала определяем, что максимальное кратное $\ell$ который может поместиться в 32 байта $15$.

Чтобы сгенерировать несмещенное случайное число, мы многократно генерируем случайную 32-байтовую последовательность и проверяем, меньше ли она $15\элл$. Как только мы найдем такое число, мы можем уменьшить это число. $mod\ell$ без введения смещения по модулю. Вероятность найти подходящее случайное число на первой итерации составляет ок. 94%.

Тот же метод применим к secp256r1, где вы должны использовать $3 \ell$ вместо $15\элл$ из-за того, что порядок группы базовой точки для secp256r1 больше (см. 2.4.2 Рекомендуемые параметры secp256r1).Вероятность найти подходящее случайное число на первой итерации составляет ок. 95%.