MAKECERT и дублировать открытые ключи

Я надеюсь, что этот вопрос имеет смысл. Но скажем, я создаю сертификат с помощью MAKECERT.EXE следующим образом:

makecert -r -sr LocalMachine -ss my -a sha256 -sky exchange -n "CN=Hello World"

Теперь предположим, что я запускаю это на двух разных (Windows) машинах. Статистически каковы шансы, что сертификаты на двух разных машинах будут иметь один и тот же открытый ключ?

Если этот вопрос не имеет смысла, я был бы признателен за объяснение, почему это не так.

Спасибо.


windows certificate public-key-encryption makecert
person Neil Weicher    schedule 07.03.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

  • makecert по умолчанию используется 1024-битный ключ RSA.
  • По умолчанию используется фиксированное значение e=65537.
  • 1024-битный ключ RSA состоит из двух простых чисел, каждое из которых имеет длину 512 бит.
  • теорема о простых числах утверждает, что существует более 2^511/ln(2^511) простых чисел такого размера, и если мы вычтем все простые числа 511 бит и меньше, у нас останется около 10 ^ 151.
  • Таким образом, в двух прогонах вероятность того, что меньшее из двух простых чисел окажется одинаковым, составляет около 1 из 1e151.
  • Running that through the formula for the birthday problem we see that all the magic really happens around the 1e75 mark.
    • 1% chance of collision: 4.5e74
    • 10%: 1.5e75
    • 25%: 2.4e75
    • 50%: 3.7e75
    • 75%: 5.3e75
    • 99%: 9.6e75
  • All of that was for one of the two primes. If we factor in the other (and, without-loss-of-generality, assume that we always declare that p < q) then we get:
    • 5e150 * 1e151 ~= 5e301 different 1024-bit values of RSA n.
    • 1% вероятность столкновения после 1e150 запусков.
    • 10% вероятность столкновения после 3e150
    • 25% вероятность столкновения после 5e150
    • 50% вероятность столкновения после 8e150
    • 75% вероятность столкновения после 1e151
    • Вероятность столкновения 99% после 2e151

При 1 миллионе ключей в секунду (1e6) за все ~86000 секунд в день вы получаете 8.6e10 ключей в день. Чтобы получить вероятность столкновения с вероятностью «миллионная доля процента» (1/1e8), вам потребуется более 1e136 дней вычислений. Это 3e133 лет. В настоящее время считается, что Вселенной 1.4e10 лет. Таким образом, вам нужно около 2.3e123 вселенных, чтобы иметь хотя бы такой высокий шанс (плюс-минус пара вселенных).

Кстати, мой компьютер может обрабатывать только около 100 1024-битных ключей в ядро-секунду (около 10 мс в секунду), поэтому я предполагаю, что у вас есть около 10 000 из них, пытающихся решить эту проблему.

Если мы не моделируем коллизию состояний CSPRNG и откат ВМ (чтобы вызвать коллизию состояний CSPRNG), ответ таков: практически невозможно.

person bartonjs    schedule 07.03.2018
comment
Спасибо за всесторонний анализ. Интересно, что я дважды запускал одну и ту же командную строку на одной и той же машине. В итоге я получил два сертификата. У них были разные серийные номера и разные отпечатки пальцев. Однако у них обоих был один и тот же открытый ключ! Это ожидается? - person Neil Weicher; 07.03.2018
comment
@NeilWeicher Вы использовали опцию -sk? Это загружает (или создает и загружает) именованный ключ, так что это будет тот же ключ при втором запуске (на той же машине). - person bartonjs; 07.03.2018
comment
Я поставил командную строку в вопросе выше. Не использую опцию -sk, но я использую опцию -sky, которая кажется другой. Когда может быть причина для создания именованного ключа? - person Neil Weicher; 07.03.2018
comment
@NeilWeicher Каждый день узнавайте что-то новое. Если вы не укажете -pe (экспортируемый закрытый ключ), то makecert будет иметь значение по умолчанию для -sk JoeSoft, поэтому вы загрузите тот же ключ при втором запуске (если вы укажете -pe, а не -sk, тогда он использует UUID). Неудивительно, что makecert устарел. (Вы бы использовали именованный ключ, в первую очередь, когда это существующий аппаратный ключ. Или вы бы указали -sk, опустив -pe, чтобы избежать использования ключа JoeSoft :)) - person bartonjs; 07.03.2018
comment
(О, и, для полноты: хранилище сертификатов не сохраняет ключ вместе с сертификатом, а только имя ключа (см. также: аппаратные ключи); поэтому закрытому ключу нужно имя, чтобы вы могли использовать сертификат для расшифровать/подписать) - person bartonjs; 07.03.2018