windows - MAKECERT og duplicate Public Keys

Indlæg af Hanne Mølgaard Plasc

Problem



Jeg håber, at dette spørgsmål giver mening. Men lad os sige, at jeg opretter et certifikat med MAKECERT.EXE som dette:


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


Lad os nu sige, at jeg kører dette på to forskellige (Windows) maskiner. Statistisk set, hvad er chancerne for, at certifikaterne på de to forskellige maskiner vil have samme offentlige nøgle?


Hvis dette spørgsmål ikke giver mening, værdsætter jeg en forklaring på hvorfor det ikke gør det.


Tak.

Bedste reference



  • makecert er standard til en 1024-bit RSA-nøgle.

  • Det er en standard e=65537.

  • En 1024-bit RSA-nøgle har to primere, hver 512 bit lange.

  • Prime-tallets sætning siger, at der er mere end 2 ^ 511/ln (2 ^ 511) primere af denne størrelse, og hvis vi trækker alle 511- og mindre bitprimerne tilbage, går vi med ca. 10 ^ 151 .

  • Så på tværs af to kurser er oddsene for de mindre af de to primater ens, ca. 1 i 1e151.

  • Kører det gennem formlen til fødselsdagsproblemet ser vi, at alt magien virkelig sker omkring 1e75 mærket.


    • 1\% chance for kollision: 4.5e74

    • 10\%: 1.5e75

    • 25\%: 2.4e75

    • 50\%: 3.7e75

    • 75\%: 5.3e75

    • 99\%: 9.6e75


  • Alt dette var for et af de to primater. Hvis vi faktor i den anden (og uden tab af generalitet) antager vi altid erklærer p < q) så får vi:


    • 5e150 * 1e151 ~=5e301 forskellige 1024-bit værdier af RSA n.

    • 1\% kollisions chance efter 1e150 kører.

    • 10\% kollisions chance efter 3e150

    • 25\% kollisions chance efter 5e150

    • 50\% kollisions chance efter 8e150

    • 75\% kollisions chance efter 1e151

    • 99\% kollisions chance efter 2e151




Ved 1 million nøgler pr. Sekund (1e6) for alle ~ 86000 sekunder om dagen får du 8.6e10 nøgler om dagen. At have en 'millionth of a percent' chance (1/1e8) af en kollision, du har brug for over 1e136 dage af beregning. Det er 3e133 år. Universet er for tiden antaget at være 1.4e10 år gammel. Så, du har brug for omkring 2.3e123 universer til at have lige så høj en chance (giv eller tag et par universer). [30] [31]


BTW, min computer kan kun lave 100 10024 bit nøgler pr. Kerne-sekund (lige omkring 10 ms pr.), Så jeg antager, at du har omkring 10.000 af dem kvæle væk på dette problem.


Medmindre vi model i CSPRNG-statskollision og VM-tilbagekaldelse (for at forårsage CSPRNG-statskollision), er svaret: effektivt umuligt.