Как безопасно и случайным образом перебрать ключ, полученный из Scrypt?

Я разрабатываю способ детерминированной генерации закрытых ключей для произвольных эллиптических кривых на основе некоторого пользовательского ввода (мозгового кошелька). В настоящее время я использую алгоритм хеширования паролей Scrypt с надежными параметрами сложности, чтобы хэшировать ряд входных параметров в ключ.

Вывод Scrypt должен быть равномерно распределен между $[0, 2^{б})$ куда ${б}$ - это количество выходных битов, используемых на выходе алгоритма Scrypt. Но действительные закрытые ключи эллиптической кривой должны быть меньше конечного порядка полей кривой. $N$, распределяется равномерно среди $[0, N)$. Таким образом, использование вывода Scrypt напрямую в качестве мода приватного ключа $N$ создаст небольшое смещение в результирующих ключах, которые генерируются - плохие новости, поэтому мне нужно избегать этого.

Обычно, если вы генерировали закрытые ключи с использованием защищенного ГСЧ, вы просто повторяли ГСЧ, пока не получили число меньше $N$, и вы можете смело использовать его как закрытый ключ.

Существует ли безопасный способ детерминированной итерации вывода Scrypt, чтобы сохранить псевдослучайное распределение вывода Scrypt без повторного запуска Scrypt с новыми параметрами?

Одним из способов, который я рассматривал, было хэширование вывода scrypt с помощью SHA256 или SHA512 до тех пор, пока оно не станет меньше $N$, но это не будет работать так хорошо для кривых размером более 512 бит, таких как P521.

Другое менее элегантное решение состоит в том, чтобы просто отклонить любые входные параметры, которые дают ключ больше, чем $N$. Это должно происходить очень редко, так что, возможно, мне это сойдет с рук? Существуют ли какие-либо общие кривые, порядок которых $N$ не является значительной долей его следующей по величине степени двойки?

Во-первых, использование закрытого ключа, детерминировано полученного из пароля, почти всегда неправильно.Пароли часто скомпрометированы или забыты, и поэтому их необходимо изменить. Если для смены пароля требуется нечто большее, чем обновление небольшого количества данных в одном месте, у вас возникнут серьезные операционные трудности. Поэтому обычно единственное, что вы должны делать с ключом, полученным из пароля, это упаковка ключей, т. е. полученный из пароля ключ используется только для симметричного шифрования файла, содержащего «настоящие» ключи. Эти настоящие ключи хранятся, и они не генерируются детерминировано из чего-либо, они просто генерируются случайным образом. Когда пользователь обновит пароль, повторно зашифруйте этот файл с помощью нового ключа, полученного из пароля, и удалите предыдущую версию.

При этом для детерминированного получения ключа эллиптической кривой первым шагом является рассмотрение типа кривой.

• Для Curve25519 и Curve448 ключи вычисляются из фиксированной равномерно распределенной битовой строки, как указано в RFC 7748 §5. Существует точный процесс, который берет 256-битный или 448-битный равномерно распределенный ввод, форсирует определенные биты, интерпретирует биты как число (с прямым порядком байтов) и сводит к каноническому репрезентативному модулю. $р$. Так как $р$ очень близко к следующей степени $2$, сокращение по модулю оставляет число неизменным с подавляющей вероятностью. Реализации Curve25519/Curve448 обычно ("ДОЛЖНЫ") принимать ключи в неканонической форме, поэтому вам не нужно ничего делать, кроме предоставления равномерно распределенной 32-байтовой или 56-байтовой строки.

• Для Ed25519 и Ed448 закрытые ключи указаны в RFC 8032 §5.1.5 и §5.2.5 в виде единой 32-байтовой или 57-байтовой строки соответственно. Процесс подписи начинается с хеширования этого ввода (объединенного с другими строками) и использования результата в виде целого числа.

• Для кривых NIST и вообще кривых в форме Вейерштрасса не существует единого общепринятого процесса перехода от битовых строк к закрытым ключам. ФИПС 186-4 В §B.4 описаны два возможных метода генерации закрытого ключа из выходных данных генератора случайных чисел, и эти методы в равной степени применимы для получения закрытого ключа из равномерно распределенного битового потока, полученного с помощью алгоритма получения симметричного ключа. Чтобы получить закрытый ключ на кривой, порядок которой $р$ является $n$-битное число:

  1. («Дополнительные случайные биты») Получить $n + 64$ биты равномерно распределенного ((псевдо)случайного) секретного ввода. Интерпретируйте этот ввод как целое число с обратным порядком байтов, уменьшите его по модулю $p-1$ и добавить $1$ чтобы получить число в диапазоне $[1, р-1]$. Некоторые ключи кажутся немного более вероятными, чем другие, но, поскольку $2^{-64}$, это не дает никакого практического преимущества противнику.
  2. («Тестирование кандидатов») Получить $n$ биты равномерно распределенного ((псевдо)случайного) секретного ввода. Интерпретируйте этот ввод как целое число с обратным порядком байтов. Если результат $\ge p-1$, начните процесс снова с самого начала. В противном случае добавьте $1$. Это вообще не имеет смещения и не требует манипулирования числами больше, чем $n$ бит, но у него есть и обратная сторона: вы не знаете заранее, сколько равномерно распределенных входных данных вам потребуется: это потенциально неограничено.

  Первый метод, как правило, более удобен, поскольку вы точно знаете, сколько (псевдо)случайного ввода необходимо.

Если вам действительно нужно связать это с алгоритмом получения ключа на основе пароля, таким как scrypt, есть два метода.

• Прямой метод заключается в том, чтобы запросить у scrypt столько входных данных, сколько вам нужно. Для кривых Вейерштрасса это делает метод тестирования кандидатов непрактичным. Так что получите 32 байта из scrypt для Curve25519 или Ed25519; 40 байт для P256R1 или P256K1; 56 байт для P384R1 или P384K1; 57 байт для Ed448 и т. д.
• Косвенный метод заключается в запросе фиксированного количества битов у scrypt. Этого должно быть достаточно, чтобы нельзя было угадать грубой силой. 128 бит (16 байт) вполне подойдут. Используйте это как начальное значение для обычной (не основанной на пароле) функции получения ключа, такой как один из NIST SPÂ 800-108 или же ХКДФ, или как начальное значение для алгоритма генератора псевдослучайных чисел, такого как один из NIST SPÂ 800-90A. Используйте этот вывод PRNG для получения закрытого ключа.