Вопрос правильный, что любой закрытый ключ меньше 250 может быть найдена из открытого ключа, и метод, который он описывает, будет практичным. Однако
- Есть гораздо лучшие методы, которые могут найти ключ меньше, чем к2 с усилием, пропорциональным к (например. Поллард Ро) и мало памяти, со значительной вероятностью. Таким образом 250 операций достаточно, чтобы найти ключ меньше 2100 со значительной вероятностью.
- 250 — это небольшое число для количества операций по взлому криптографии. В 1970-х годах АНБ согласилось, что DES имеет 256 ключи, потому что они знали, что могут сломать это, если потребуется. К 2000 году базовый уровень безопасности составлял 280. Современная базовая линия может быть 296, а практика для новых систем порядка 2128 или больше. Это еще до того, как приступить к учету приведенных выше атак.
есть ли верхняя граница?
Да. Для каждого метода и кривой подписи на основе эллиптических кривых существует предписанный набор закрытых ключей. За ЭЦДСА, это интервал [1, н-1] где н порядок генератора (а не н в вопросе). Значение н зависит от кривой. Для кривой secp256k1, н чуть ниже 2256. Таким образом, ожидаемое усилие найти закрытый ключ с помощью открытого ключа с использованием ро Полларда (или любого другого известного метода) составляет порядка 2128 операции (добавления на эллиптической кривой) и многое другое.
Если верхняя граница будет превышена, закрытый ключ будет отклонен соответствующим программным обеспечением. Если бы он не был отклонен, и программное обеспечение работало бы правильно с математической точки зрения, а для систем подписи, где закрытый ключ - это непосредственно то, что умножает генератор для формирования открытого ключа (как в вопросе и ECDSA), ключ работал бы как если бы оно было уменьшено по модулю н (порядок генератора), как для генерации открытого ключа, так и для подписи.
Правила генерации закрытого ключа зависят от системы подписи; например Эд25519 указывает пространство для закрытого ключа, которое намного больше, чем н, чтобы повысить устойчивость к некоторым атакам (но не для нахождения закрытого ключа, генерирующего действительную подпись).
Удаление возможных ключей известным злоумышленнику способом уменьшается безопасности, потому что у противника меньше ключей для проверки. Это терпимый удалить несколько возможных ключей. Ни в коем случае не желательно.
Обычный/рекомендуемый/лучший способ выбрать закрытый ключ: равномерно случайным образом в наборе допустимых значений закрытых ключей. Можно исключить некоторые значения (например, небольшие значения, как в вопросе), но это только до тех пор, пока отклоняется лишь небольшая часть значений. Например. для ECDSA на secp256k1 было бы нормально отклонить закрытые ключи меньше 2192, потому что это удаляет лишь незначительную долю около 2-64 (0.000000000000000005%) пространства ключей. Но это также бессмысленно, потому что маловероятно, что будет сгенерирован один из исключенных ключей. А увеличение нижней границы, чтобы эта пропорция стала не пренебрежимо малой, существенно уменьшит наш выбор ключей, позволяя специально разработанному алгоритму поиска ключа найти его легче, чем при равномерно случайном выборе.
Закрытый ключ ECDSA на secp256k1 можно сгенерировать путем свертывания шестигранный кубик 64 раза (если все первые 23 броска дают одинаковое значение, спросите кости и остановитесь). Добросовестно используйте 64 результата в обратном порядке. Результатом является действительный закрытый ключ (проведенный нами тест гарантирует, что результат находится в соответствующем интервале).
